带固定半径近邻搜索3-opt的离散烟花算法求解旅行商问题

传统烟花算法求解大规模离散问题存在收敛速度慢、求解精度不高等问题.针对旅行商问题的特点,提出一种带固定半径近邻搜索3-opt的离散烟花算法.该算法基于基本烟花算法进行离散化改进,采用整数编码的路径表示方法来表示旅行商问题的解,对爆炸算子、高斯变异算子进行离散化操作策略设计.为了使算法具有较好的局部搜索能力,提出固定半径近邻搜索3-opt策略来提高算法精度和收敛速度,同时采用不检测标志策略提高算法效率.实验结果表明:该算法能有效地求解旅行商问题,其离散烟花算子在全局收敛能力、收敛精度、求解时间和稳定性等方面均优于传统烟花算子;基准测试算例的最优解平均误差率仅为0.002％,优于对比算法.     

基于自适应继承策略的帝国竞争算法求解旅行商问题

针对帝国竞争算法在求解旅行商问题时局部搜索能力不强和容易陷入局部最优的缺陷,提出一种基于自适应继承策略的帝国竞争算法.该算法采用自适应继承策略的启发式交叉算子、单点局部插入策略和固定邻域的2-opt算子来增强算法的局部优化能力,并加入帝国精英解集以保持种群的多样性.通过标准实例测试,验证了所提出的改进策略的优越性,与基于启发式交叉算子和帝国主义算法为框架的其他算法进行对比,实验结果表明,该算法求解中小规模的解旅行商问题具有较高的求解精度和较快的收敛速度.     

求解旅行商问题的探索—开发—跳跃策略单亲遗传算法

针对遗传算法求解旅行商问题(TSP)时容易早熟、收敛速度慢等问题,提出一种基于探索—开发—跳跃策略的单亲遗传算法(EDJS-PGA)。该算法将基因移位、倒序、交换三种算子组合构成探索策略,用于扩展解的搜索空间,增强算法全局搜索能力;再将logistic混沌映射和改良圈操作融合为一种混沌映射改良圈算子,用于增强算法的局部搜索能力,构成开发策略;最后针对种群中的同优个体设计了近邻变异算子,构成跳跃策略,增强了算法跳出局部最优解的能力,使其兼具个体变异、局部优化、防止早熟等多重作用。通过对18个TSP实例进行仿真实验,结果表明EDJS-PGA相较于传统单亲遗传算法具有更高的求解精度和收敛速度,且最优解偏差率和平均误差率均处于较低水平;与其他文献对比,EDJS-PGA具有更强的鲁棒性和求解效率。     

基于分段混合蛙跳算法的旅行商问题求解

针对旅行商问题(TSP)在搜索后期解的多样性和精度下降的问题,提出一种解决TSP问题的分段混合蛙跳算法(S-SFLA)。该算法在搜索初期利用逆转变异算子减少交叉路径,在搜索的后期引入邻域搜索(个体邻域,局部最优领域,全局最优邻域)增加种群多样性。在整个搜索过程中记忆全局历史最优解与局部历史最优解,进行全局更新和局部更新,避免迂回搜索。在局部更新中,每一个青蛙都有机会得到更新。实验结果表明,与遗传算法、蚁群算法、基本蛙跳算法相比,S-SFLA算法在求解中等规模的TSP问题上具有更快的搜索速度和更高的求解精度。     

一种求解旅行商问题的进化多目标优化方法

为了克服传统小生境(Niching)策略中的参数设置难题,提出一种求解旅行商问题的进化多目标优化方法:建立以路径长度和平均离群距离为目标的双目标优化模型,利用改进非支配排序遗传算法(NSGAII)进行求解.为了在全局探索能力与局部开发能力之间保持平衡,算法中采用一种使路径长度相同的可行解互不占优的评价策略,并通过一种新的离散差分进化算子和简化的2-Opt策略生成候选解.与已有算法的数值试验结果比较表明,求解旅行商问题(TSP)的改进非支配排序遗传算法(NSGAII-TSP)能够更好地保持种群多样性,从而克服局部最优解的吸引并具有更鲁棒的全局探索能力.通过借助特殊的个体评价策略,所提出的算法可以更好地进行全局优化,甚至同时得到多个全局最优解.     

自适应合并与分裂的多种群差分进化算法

针对差分进化（DE）算法存在的早熟收敛与搜索停滞问题,提出了自适应合并与分裂的多种群差分进化算法。算法将种群划分为多个子种群,引入子种群优劣因子来评价种群的优劣性,实现种群间的自适应合并与分裂;对于种群中的各个个体,采取基于精英池学习的变异算子,结合优秀个体进行自适应学习调整,使算法达到全局搜索与局部搜索能力的平衡;在算法后期引入扰乱策略,保证算法快速收敛的同时有效地跳出局部极值点,提高算法寻优的精度。在30个标准测试函数的实验结果表明,改进算法能有效解决早熟和陷入局部最优的问题。     

改进多目标进化算法求解柔性作业车间调度问题

针对加工时间为模糊数的柔性作业车间调度问题,考虑最小化模糊最大完工时间、模糊机器总负荷、模糊关键机器负荷为优化目标,提出一种有效求解该类优化问题的多目标进化算法。算法采用一种混合不同机器分配和工序排序策略的方法产生初始种群,并采用插入空隙法对染色体进行解码。定义一种新的基于可能度的个体支配关系和一种基于决策空间的拥挤算子,并将所提支配关系和拥挤算子运用于快速非支配排序。接着,提出一种基于移动模糊关键工序的局部搜索策略对种群中的优势个体进行局部搜索。通过试验研究关键参数对算法性能的影响并将所提算法与3种不同的优化算法作对比。结果表明,所提算法能够比其它算法更有效解决多目标模糊柔性作业车间调度优化问题。     

种间双系统协作蝙蝠优化算法及其性能仿真

针对单一种群算法较难权衡全局寻优能力和局部搜索能力的问题,提出一种种间双系统协作蝙蝠优化算法。根据蝙蝠个体运动状态将整个种群分为探测系统和开发系统,并通过信息交流进行进化协作。设计和运用动态变化算子实现全局寻优和局部寻优的实时平衡,利用位置更新算子减少开发系统随机性带来的影响,提高局部区域的开发效率,运用伪变异算子保持探测系统的多样性,提高全局搜索的效率。实验结果表明,该算法在快速收敛的同时能够避免陷入局部最优,可解决多局部极值的复杂优化问题。     

多种群协同进化的差分进化算法

针对差分进化算法在优化过程中容易陷入局部最优和收敛精度不高的问题,提出一种多种群协同进化的差分进化算法。首先提出双序法用于种群划分：同时使用距离系数排序和适应度值排序将种群划分为三个子种群,将离全局最优个体远且适应度值优秀的个体划分出来,可以有效的避免陷入局部最优。其次对每个子种群采用不同的变异策略和控制参数,同时对整体表现一般的种群采用概率判定机制选择变异策略,以平衡全局探测和局部搜索。最后将所提算法在CEC2017测试集上进行实验仿真,实验结果表明,所提算法在收敛精度、跳出局部最优等方面均优于其他改进DE算法。     

改进樽海鞘群算法求解柔性作业车间调度问题

针对以最小化最大完工时间的柔性作业车间调度问题,在标准樽海鞘群算法(salp swarm slgorithm, SSA)的基础上,提出一种改进的樽海鞘群算法。采用基于工序和基于设备的二维向量进行编码,并考虑设备负载进行种群初始化。基于Lévy飞行对领导者位置更新方式进行离散化改进;在追随者位置更新公式中引入自适应惯性权重,使算法的全局搜索和局部搜索能力得到更好的平衡。为提高搜索效率,设计了交叉算子和基于关键路径的变异算子来保证种群的多样性,同时引入模拟退火(simulated annealing,SA)策略,改善算法的局部搜索能力。通过采用标准算例进行对比计算,结果验证了所提算法的有效性。     

一种混合改进遗传算法的嵌套分区算法

提出一种混合改进遗传算法的嵌套分区算法用于求解旅行商问题。该算法首先使用加权抽样法产生初始最可能域,用全局数组保存每个区域的历史最优解,设计子域交叉算子和子域变异算子,并用改进的遗传算法搜索每个子域和裙域的最好解,然后对Lin-Kernighan算法进行改进,并且在搜索裙域中最好解时,对种群中优秀个体用改进的Lin-Kernighan算法进行优化。对TSPLIB中问题实例的仿真结果表明,所提出的混合改进遗传算法的嵌套分区算法在求解旅行商问题时可以获得高质量的解。     

求解TSP问题的一种改进的+进制MIMIC算法

十进制MIMIC算法是基于MIMIC二进制编码算法思想的可用来求解TSP的离散分布估计算法。着重考虑该算法在较大规模TSP问题上的算法缺陷,对其编码方式和概率模型进行了改进,提出了新的个体生成策略,在初始化种群阶段使用了贪心算法,在进化过程中引入了杂交算子、变异算子、映射算子、优化算子等演化算子,采用了动态调整方法来确定优势群体的规模。以上改进使得算法在小种群解大规模TSP问题的情况下仍可保持种群的多样性。实验结果表明,改进算法在求解规模、求解质量和寻优速度上都有明显提高。     

Genetic algorithm for the one-commodity pickup-and-delivery traveling salesman problem

In this paper, we proposed a genetic algorithm for the one-commodity pickup-and-delivery traveling salesman problem. In the proposed algorithm, we designed a new tour constructing heuristic to generate the initial population, and proposed a novel pheromone-based crossover operator that utilizes both local and global information to construct offspring. In addition, a local search procedure was embedded into the genetic algorithm to accelerate convergence. The proposed genetic algorithm was tested on benchmark instances with up to 500 customers, and the computational results show that it gives a faster and better convergence than existing heuristics.     

求解工作量平衡多旅行商问题的改进遗传算法

针对工作量平衡的多旅行商问题,提出了一种融合杂草算法繁殖机制和局部优化变异算子的改进遗传算法（Reproductive mechanism and Local optimization mutation operator based Genetic Algorithm,RLGA）。该算法利用入侵杂草优化算法中以适应度为基准的繁殖机制来产生种群并进行遗传操作,以此来提高算法的搜索效率;同时提出一种混合局部优化算子作为变异算子来提高算法的局部搜索能力,从而提高收敛精度。实验结果表明,RLGA在求解工作量平衡的多旅行商问题时可以快速收敛到较优解,并且求解精度得到了很大的提高。     

改进的嵌套分区算法求解旅行商问题

嵌套分区算法是近年来提出的一种求解大规模优化问题的新型全局优化方法。介绍了嵌套分区算法（NPM）的基本思想,将其应用于求解旅行商问题。分析确定了嵌套分区算法各个算子的策略,提出了一种改进的嵌套分区算法。该算法采用加权抽样法求得初始最可能域,用全局数组记录下每个区域的历史最优解,用3-opt局部搜索算法改进每个区域解的质量。对TSPLIB中部分实例仿真结果表明,所提出的结合3-opt算法的改进嵌套分区算法在求解 TSP问题时可以获得高质量的解。     

改进的遗传算法求解旅行商问题

提出一种解决旅行商问题的改进遗传算法.在传统遗传算法的基础上,引入贪婪算法进行种群初始化;从遗传进化代数和个体适应函数值两个方面实现遗传参数自适应调节,在加快寻优速度的同时防止寻优陷入局部最优;采用基于贪婪方法的启发式交叉算子优化交叉结果;对交叉前后的种群分别实施精英个体保留策略,保证最优基因结构得以延续.实验结果分析表明,改进的遗传算法可以在种群规模较小的情况下具有更可靠的寻优能力.     

基于小波精英解学习和多角度搜索的新型阴阳平衡优化算法

针对基本阴阳平衡优化算法计算精度低和优化速度慢等问题,提出一种新型阴阳平衡优化算法.首先,设计小波精英解学习策略,充分利用精英解的进化信息产生高质量的解,用于算法的全局勘探和局部开发;然后,将搜索角度引入解更新方程中,以实现对算法搜索空间的全方位搜索,并对所提出算法的收敛性进行理论分析;最后,采用连续优化测试函数和瓶颈旅行商问题进行数值实验,并将所提出算法与多种智能优化方法进行比较.实验结果表明,所提出算法具有更好的优化性能.     

A hybrid genetic algorithm for the traveling salesman problem with pickup and delivery

In this paper, a hybrid genetic algorithm （GA） is proposed for the traveling salesman problem （TSP） with pickup and delivery （TSPPD）. In our algorithm, a novel pheromone-based crossover operator is advanced that utilizes both local and global information to construct offspring. In addition, a local search procedure is integrated into the GA to accelerate convergence. The proposed GA has been tested on benchmark instances, and the computational results show that it gives better convergence than existing heuristics.