Memoryless cooperative graph search based on the simulated annealing algorithm

We have studied the problem of reaching a globally optimal segment for a graph-like environment with a single or a group of autonomous mobile agents. Firstly, two efficient simulated-annealing-like algorithms are given for a single agent to solve the problem in a partially known environment and an unknown environment, respectively. It shows that under both proposed control strategies, the agent will eventually converge to a globally optimal segment with probability 1. Secondly, we use multi-agent searching to simultaneously reduce the computation complexity and accelerate convergence based on the algorithms we have given for a single agent. By exploiting graph partition, a gossip-consensus method based scheme is presented to update the key parameter--radius of the graph, ensuring that the agents spend much less time finding a globally optimal segment.

Simulated annealing algorithm for detecting graph isomorphism

Evolutionary computation techniques have mostly been used to solve various optimization problems, and it is well known that graph isomorphism problem （GIP） is a nondeterministic polynomial problem. A simulated annealing （SA） algorithm for detecting graph isomorphism is proposed, and the proposed SA algorithm is well suited to deal with random graphs with large size. To verify the validity of the proposed SA algorithm, simulations are performed on three pairs of small graphs and four pairs of large random graphs with edge densities 0.5, 0.1, and 0.01, respectively. The simulation results show that the proposed SA algorithm can detect graph isomorphism with a high probability.

Annealing Harmony Search Algorithm to Solve the Nurse Rostering Problem

A real-life problem is the rostering of nurses at hospitals.It is a famous nondeterministic,polynomial time(NP)-hard combinatorial optimization problem.Handling the real-world nurse rostering problem(NRP)constraints in distributing workload equally between available nurses is still a difficult task to achieve.The international shortage of nurses,in addition to the spread of COVID-19,has made it more difficult to provide convenient rosters for nurses.Based on the literature,heuristic-based methods are the most commonly used methods to solve the NRP due to its computational complexity,especially for large rosters.Heuristic-based algorithms in general have problems striking the balance between diversification and intensification.Therefore,this paper aims to introduce a novel metaheuristic hybridization that combines the enhanced harmony search algorithm(EHSA)with the simulated annealing(SA)algorithm called the annealing harmony search algorithm(AHSA).The AHSA is used to solve NRP from a Malaysian hospital.The AHSA performance is compared to the EHSA,climbing harmony search algorithm(CHSA),deluge harmony search algorithm(DHSA),and harmony annealing search algorithm(HAS).The results show that the AHSA performs better than the other compared algorithms for all the tested instances where the best ever results reported for the UKMMC dataset.

基于LocalSearch的智能货运路线匹配设计与实现

传统物流行业中,货主需要向全国各个省市区发送货物,存在上千条线路。这就导致了货主每次招标时都要对这些线路的报价进行计算后选择2~3家承运商,靠手工Excel填写统计计算非常浪费时间。为了解决这个问题,设计并实现了基于LocalSearch的智能货运路线匹配系统,通过采用退火模拟和禁忌搜索等方式,能够在极短的时间内计算一个满足货主复杂招标要求的近似最优解,且计算结果要比手工计算优于20%以上,有助于节约人力成本,降低运费。

基于改进蚁群算法的邮船舱室模块移运路径规划

针对大型邮船舱室模块运输过程中存在的移运路线长、路线混乱、舱室模块易与障碍物发生碰撞等问题,提出应用加入动态搜索模型的蚁群算法对邮船舱室模块进行路线规划,为运输舱室模块提供清晰、便捷的移运路线。对主竖区的障碍物进行分析,建立模拟实际工况的栅格地图,采用改进蚁群算法寻找移运路径。对不同位置所经过的栅格地图和蚁群数量进行动态调整。采用模拟退火算法寻找蚁群算法的参数。采用离散点分析确定移运路径的主、支通道。仿真试验结果表明,应用改进蚁群算法建立主、支通道进行舱室模块移运可有效提高舱室模块的运输效率。

基于CAA的船舶工艺仿真环境搭建与LNS-SATSP排产优化

为解决在DELMIA原生环境下手动操作较多、工作效率低问题,提出一种基于CAA的船舶工艺仿真环境搭建与LNS-SATSP排产相结合的方法。通过CAA实现自动构建流程库与PPR树有效降低仿真环境搭建时间,并结合基于大规模邻域搜索的三次模拟退火算法(LNS-SATSP)进行排产分析,规划产品加工路线并自动优化仿真环境。以船舶肋骨段加工为例,引入自动建模,通过改进排产算法使平均加工时间缩短7.04%,并对优化后仿真环境搭建流程进行验证。

两种高效局部搜索算法求解RB模型实例

RB(revised B)模型是一种在约束可满足问题中具备精确相变增长域的随机实例模型,提出两种高效的启发式局部搜索算法用于解决RB模型生成的大值域约束可满足问题。首先为基于权重指导搜索的W-MCH算法,该算法通过约束判断和违反约束数计分来进行搜索,并引入了基于约束违反概率的权重计算公式,根据其关联的约束权重进行修正,再对变量进行迭代调整。然后提出最小化值域的MDMCH算法,该算法通过记录违反约束和逐步消除已违反约束变量的启发式策略来减少搜索空间,并在最小化后的变量域内重新校准变量赋值,进而有效提高算法的收敛速度。此外,还提出了融入模拟退火策略的WSCH和MDSCH算法,这两种算法都能根据变量的表征特点对变量域进行针对性的搜索。实验结果表明,与多种启发式算法相比,这两种算法在精度与时间效率方面均呈现明显提升,在复杂难解的实例中能够提供高效的求解效率,验证了算法的有效性和优越性。

多车场带时间窗车辆路径问题的改良自适应大邻域搜索算法

针对多车场带时间窗车辆路径问题(MDVRPTW),提出一种改良自适应大邻域搜索算法(IALNS)。首先,在构造初始解阶段改进一种路径分割算法;其次,在优化阶段利用设计的移除和修复启发式算子相互竞争择优选取算子,为各算子引入评分机制,采用轮盘赌方式选取启发式算子;同时,将迭代周期分段,动态调整各周期内的算子权重信息,有效避免算法陷入局部最优;最后,采取模拟退火机制作为解的接受准则。在Cordeau规范算例上进行实验,确定IALNS的相关参数,将所提算法求解结果与该领域其他代表性研究成果对比。实验结果表明,所提算法与变邻域搜索(VNS)算法的求解误差不超过0.8%,在某些算例上甚至更优;与多相位改进的蛙跳算法相比,算法的平均耗时减少12.8%,所提算法在绝大多数算例上运行时间更短。因此,验证了所提算法是求解MDVRPTW的有效算法。

基于改进启发式算法的机组优化排班问题研究

机组排班问题是航空公司运营规划中较为复杂的问题之一。基于极其复杂的航空运营组织大环境,航空公司为提高运输效率、降低运营成本也在不停的寻求合理的分配方案。航空公司机组人员大多数工作时间不够统一,在一定程度上比较分散,如果没有妥善进行排班工作可能会导致浪费人力资源而增加成本,或者影响工作人员的休息时间。本文主要考虑航班运营过程中的航线规划、人员分配和运营成本等因素,并提出了一种基于改进的贪婪算法、局部搜索法和模拟退火算法结合使用的求解方法,创新性地提出了机组人员“组合”与“分解”的编码过程。求得结果后,对最终解中的机组人员分配情况进行了实例分析测试。结果说明,改良后的启发式算法可在机组人员指派问题中得到更高质量的解,以达到对人力充分分配和降低成本的目的。

基于垂荡和纵摇运动模型对波浪能最大输出功率的设计

研究波浪能装置最大输出功率的设计,以运动平衡方程和能量输出系统研究为基础理论背景,建立浮子和振子的垂荡、纵摇运动模型和最优阻尼系数模型,确定给定时间下的浮子与振子的垂荡位移及速度和纵摇位移及角速度,并借助模拟退火算法和网格搜索算法分别确定两种情况下给定参数值的最大输出功率及最优阻尼系数.

考虑运输时间的多资源工序的资源分配优化

针对制造业和服务业等领域中广泛存在的多资源工序资源分配问题,考虑工件和可移动类资源的运输时间,以最小化最长完工时间为优化目标,构建一类新的资源分配混合整数线性规划模型。针对该问题特性,提出变邻域搜索模拟退火的混合算法。该算法结合变邻域搜索算法局部搜索能力强和模拟退火算法全局寻优的优势,同时克服前者容易陷入局部最优而后者局部收敛不佳的问题。在算法的设计中,引入自适应邻域结构和改进降温函数以提高算法的收敛效率。300个不同规模的仿真算例实验结果表明,在求解大规模实例中,所提算法的性能均优于CPLEX求解器、变邻域搜索算法和模拟退火算法,能提供更好的资源分配方案。

基于GA-ALNS算法的带可容忍时间窗的VRP求解

针对带可容忍时间窗的车辆路径规划问题,建立最小化配送总成本的规划模型,结合遗传算法构造改进自适应大邻域搜索算法对该问题求解.利用遗传算法构建高质量解开始自适应大邻域搜索寻优,减小算法计算时间成本;加入3种破坏算子和3种修复算子,以增加种群多样性;嵌入模拟退火接受准则以一定概率接受较差解,自适应更新破坏和修复算子权重,避免算法陷入局部最优.选取Solomon标准测试集进行3组实验,与已知最优解比较距离成本验证算法可行性;在单边容忍度时间窗模型下,与基础ALNS算法对比验证算法改进效果;在双边可容忍时间窗模型下,与相关文献的最优结果对比.实验结果表明,提出的GA-ALNS算法改进效果较为显著,求得的最优解同其他算法相比优化率较好,计算得到的最优方案能实现更低的车辆配送总成本,具有一定的可行性和有效性.

变邻域模拟退火算法在农村生活垃圾收运中的应用

针对农村地区生活垃圾的产生特点,考虑生活垃圾分类下的可变收运周期,构建以最小化运输成本、车辆延迟到达惩罚成本和环境惩罚成本的多目标生活垃圾收运路径优化模型.利用随机选择法、最近邻法相结合以重构解空间,使用带变邻域的模拟退火算法对模型进行求解.通过算例仿真及对比分析可知,本文模型和算法在收运总成本和总距离方面有较好的优化效果,均优于经典模拟退火算法和变邻域搜索算法的最优解.相较于传统的固定周期收运方案,本文所建立模型减去了环境污染成本,同时在总成本上改进超110.4%,可较好地解决农村地区垃圾收运路径优化问题.

Enhanced Autonomous Exploration and Mapping of an Unknown Environment with the Fusion of Dual RGB-D Sensors

The autonomous exploration and mapping of an unknown environment is useful in a wide range of applications and thus holds great significance. Existing methods mostly use range sensors to generate twodimensional (2D) grid maps. Red/green/blue-depth (RGB-D) sensors provide both color and depth information on the environment, thereby enabling the generation of a three-dimensional (3D) point cloud map that is intuitive for human perception. In this paper, we present a systematic approach with dual RGB-D sensors to achieve the autonomous exploration and mapping of an unknown indoor environment. With the synchronized and processed RGB-D data, location points were generated and a 3D point cloud map and 2D grid map were incrementally built. Next, the exploration was modeled as a partially observable Markov decision process. Partial map simulation and global frontier search methods were combined for autonomous exploration, and dynamic action constraints were utilized in motion control. In this way, the local optimum can be avoided and the exploration efficacy can be ensured. Experiments with single connected and multi-branched regions demonstrated the high robustness, efficiency, and superiority of the developed system and methods.

DESIGN OF MAXIMALLY FLAT FIR FILTERS BASED ON EXPLICIT FORMULAS COMBINED WITH OPTIMIZATION

A maximally flat FIR filter design method based on explicit formulas combined with simulated annealing and random search was presented. Utilizing the explicit formulas to calculate the ini- tial values, the firate-word-length FIR filter design problem was converted into optimization of the filter coefficients, An optimization method combined with local discrete random search and simulated annealing was proposed, with the result of optimum solution in the sense of Chebyshev approximation. The proposed method can simplify the design process of FIR filter and reduce the calculation burden. The simulation result indicates that the proposed method is superior to the traditional round off method and can reduce the value of the objective function to 41%～74%.

No Fit Polygon for Nesting Problem Solving with Hybridizing Ant Algorithms

In design science, these two kinds of problems are mutually nested, however, the nesting could not blind us for the fact that their problem-solving and solution justification methods are different. The ant algorithms research field, builds on the idea that the study of the behavior of ant colonies or other social insects is interesting, because it provides models of distributed organization which could be utilized as a source of inspiration for the design of optimization and distributed control algorithms. In this paper, a relatively new type of hybridizing ant search algorithm is developed, and the results are compared against other algorithms. The intelligence of this heuristic approach is not portrayed by individual ants, but rather is expressed by the colony as a whole inspired by labor division and brood sorting. This solution obtained by this method will be evaluated against the one obtained by other traditional heuristics.

A Comparison of Three Heuristic Algorithms for Molecular Docking

Three heuristic algorithms: simulated annealing, genetic algorithm, and Tabu search were compared to molecular docking procedure using 3 protein-ligand systems. Statistical analysis of the results indicated that the Tabu search showed the best performance in terms of locating solutions close to the crystallographic ligand conformation. From the comparisons, a hybrid search algorithm was proposed, which gave superior results compared with any one of the algorithms alone.

On the efficient search of punctured convolutional codes with simulated annealing algorithm

Punctured convolution codes （PCCs） have a lot of applications in modem communication system. The efficient way to search for best PCCs with longer constraint lengths is desired since the complexity of exhaustive search becomes unacceptable. An efficient search method to find PCCs is proposed and simulated. At first, PCCs＇ searching problem is turned into an optimization problem through analysis of PCCs＇ judging criteria, and the inefficiency to use pattern search （PS） for many local optimums is pointed out. The simulated annealing （SA） is adapted to the non-convex optimization problem to find best PCCs with low complexity. Simulation indicates that SA performs very well both in complexity and success ratio, and PCCs with memories varying from 9 to 12 and rates varying from 2/3 to 4/5 searched by SA are presented.

A Truck Scheduling Problem for Multi-Crossdocking System with Metaheuristics

The cross-docking is a very important subject in logistics and supply chain managements.According to the definition,cross-docking is a process dealing with transhipping inventory,in which goods and products are unloaded from an inbound truck and process through a flow-center to be directly loaded onto an outbound truck.Cross-docking is favored due to its advantages in reducing the material handing cost,the needs to store the product in warehouse,as well decreasing the labor cost by eliminating packaging,storing,pick-location and order picking.In cross-docking,products can be consolidated and transported as a full load,reducing overall distribution costs.In this paper,we focus on a truck scheduling at the multidoor,multi-crossdocking network with inventory constraints and process capability constraints.In this model,a truck can visit severals docks for loading or unloading many types products.This situation is very common in reality.This study also developed an exact mathematical model using mixedinteger linear programming(MILP)with the objective of minimizing the makespan to obtaint the benchmark in small scale problems.Large scale problems are solved through Simulated Annealing(SA)algorithm and Tabu Search(TS)algorithm.Performance of these algorithms will be compared to benchmarks obtained from solver as well as to each other.

改进粒子群算法的不相关并行批处理调度优化

针对粒子群优化(particle swarm optimization,PSO)算法在处理不相关并行批处理调度问题中存在的种群多样性丢失、易陷入局部最优等问题,提出了一种改进PSO的调度优化算法,用于最小化最大完工时间求解。采用基于工件序列的实数编码方式进行编码操作;基于该问题的混合整数规划模型,设计了一种J_B局部搜索的新策略;将模拟退火算法的Metropolis准则引入种群粒子的个体极值搜索。通过随机生成的小型、中型和大型实例对该算法的性能进行了测试,并与针对该调度问题提出的元启发式算法和其他3种元启发式算法进行了比较。实验结果和统计测试表明,该算法的性能明显优于对比算法。