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

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

基于近邻牵引算子的离散黑猩猩优化算法

针对旅行商问题的特点,提出基于近邻牵引算子的离散黑猩猩优化算法.首先,引入优质片段的概念,并结合每个群组的最优个体设计其检索方法,以提高组内学习策略的效果,根据组合优化问题特点对黑猩猩群体的狩猎过程进行离散化表示;其次,通过组间交流机制消除部分个体路径交叉;最后,为了克服传统的邻域搜索算子收敛慢和搜索效率低的缺点,提出一种新的邻域搜索方式—–近邻牵引算子,其搜索目的更加明确、收敛更高效,并设计自适应概率扰动调控策略,以有效平衡算法的探索与开发.对30个TSP标准数据集进行实验,结果表明,所设计的离散黑猩猩优化算法求解质量高、收敛速度快,可以应用于组合优化问题求解.     

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

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

求解旅行商问题的离散型贝壳漫步优化算法*

提出基于离散型贝壳漫步优化算法(DMWO)的旅行商问题(TSP)求解算法.在DMWO的计算框架下构造TSP相应的评估函数及个体差异度量算子.针对离散型算法整体调整容易破坏已形成的较优路径问题,采用简单的2-opt算子进行局部调整,增强算法在求解TSP时的局部搜索能力.实验中采用多组不同规模的标准TSPLIB数据,对比同样采用2-opt算子的萤火虫优化算法和蚁群优化算法,DMWO在稳定性、解的准确性及所需的迭代次数等方面具有更好的性能.     

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

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

基于汉明距离的改进粒子群算法求解旅行商问题

针对传统粒子群算法不适合求解离散型问题,提出一种基于汉明距离的改进粒子群算法。该算法保留了粒子群算法的基本思想和流程,并基于汉明距离为粒子定义了一种新型的速度表示。同时,为了使算法寻优能力更高、避免迭代过程陷入局部最优无法跳出,设计了2-opt和3-opt算子,结合随机贪婪规则,使求解质量更高、收敛更快。在算法后期,为了提高粒子在整体解空间中的全局搜索能力,采用一部分粒子重新生成的方式去重新探索解空间。为了验证算法的有效性,采用了众多旅行商问题（TSP）标准算例进行测试。实验结果表明,对于小规模TSP,该算法可以找到历史最优解;对于大规模TSP,如城市数在100以上的问题,也可以找到满意解,与已知最优解之间偏差度较小,通常在5%以内。     

求解旅行商问题的改进离散竞争进化算法

在分析竞争进化算法原理和特点的基础上,针对旅行商问题的求解,提出一种改进的离散竞争进化算法(IDCE),其中采取三项关键策略:根据个体适值排名计算变异次数、实施逆转子变异算子和并行贪心机制执行多次子变异,目的在于提高算法的全局搜索能力和单位时间内的进化效率.IDCE算法跟另两种离散竞争进化算法对于4个对称旅行商问题算例进行了性能对比,实验结果显示,在解的整体水平、最好解质量以及求解效率上,IDCE算法都优于另两种算法.     

一种基于近邻策略求TSP问题的改进演化算法

针对贪心演化算法(GEA)在旅行商问题中存在的求解规模小、成功率低的缺点,引入Inver-over倒异算子、贪心算子,改进近邻优化、映射算子、变异算子等策略,提出一种新的改进演化算法来求解中等规模旅行商问题(TSP)。通过仿真实验,验证了该进化算法收敛速度快、求解成功率高的优点,稳定性也更好。     

带柯西变异的自学习改进烟花算法

针对烟花算法收敛速度慢和求解精度不高,论文提出了一种改进烟花算法--带柯西变异的自学习改进烟花算法.改进算法用全局搜索能力更强的柯西变异算子替代高斯变异算子,增大变异范围;用全局最优烟花个体和历史柯西火花的位置来构造新的爆炸半径使其不仅能够继承和学习历史信息,还能够自适应地调整步长;并使用可同时兼顾烟花质量与分布的"精英-随机"选择策略.使用了10个典型基准测试函数和10个0-1背包问题进行仿真实验,结果表明,与蝙蝠算法、粒子群算法、带高斯扰动的粒子群算法、烟花算法、增强烟花算法、自适应烟花算法相比.该算法在收敛速度、计算精度以及稳定性方面性能更优.     

一种求解旅行商问题的高效混合遗传算法

旅行商问题(TravellingSalesmanProblemTSP)是一个典型的组合优化难题,论文提出一种求解旅行商问题的高效混合遗传算法。该算法结合遗传算法和2-opt邻域搜索优化技术,并针对旅行商问题的特点,提出K近邻点集以缩减搜索空间从而加快求解速度。基于典型实例的仿真结果表明,此算法的求解效率比较高。     

应用LK算法求解旅行商问题的混合蚂蚁算法

目前求解TSP问题效果最好的混合算法是最大最小蚂蚁算法和局部搜索算法,文章通过对几种局部搜索的灵活运用,并结合改进的接受准则接受局部优化解,提出了一种高效的混合蚂蚁算法。算法前期使用3-opt这种简单高效的局部搜索的解初始化信息素矩阵,加快收敛速度,后期采用改进的Lin-Kernighan算法生成局部优化解然后依Metropolis接受准则概率接受,有效地避免陷入局部最优,理论分析和TSPLIB中部分实例仿真结果表明,此算法能比其他改进蚁群算法具有更多优越性。     

基于拥挤度的改进蚁群算法

针对蚁群算法在求解旅行商问题时收敛时间长,且易陷入局部最优状态的缺陷,提出一种基于拥挤度的动态信息素蚁群优化策略。该算法引入静态拥挤度和动态拥挤度算子,主动提前预防停滞现象。将拥挤度与状态转移规则相结合,使蚁群状态实时跟随路径搜索情况而改变,提高蚁群自适应能力。针对蚁群路径搜索情况,加入邻域搜索优化规则,缩小搜索区域,结合2-opt局部优化策略,加快蚁群收敛速度。仿真结果表明,本算法既有较高的搜索效率又有较强的全局搜索能力。对比其他优化算法,无论是求解质量、稳定性还是收敛速度都能达到令人满意的效果。     

锦标赛精英学习与协方差变异的烟花算法

针对传统烟花算法收敛精度低,收敛速度慢,容易陷入局部最优等问题,提出一种基于锦标赛精英学习与协方差变异的烟花算法（GLFWA-CM）。该算法在爆炸算子过程中利用核心烟花更新信息确定核心烟花在每一维上的爆炸半径,并引导核心烟花在更新方向上产生更多的爆炸火花,提高了核心烟花的搜索能力;在变异算子中用协方差变异代替原来的高斯变异,充分利用爆炸火花的信息,有效平衡了算法的局部搜索和全局搜索能力;在烟花选择过程中提出了一种基于锦标赛的精英学习策略,有效加快了算法收敛速度。在CEC2015测试函数上做仿真实验,结果表明,与多种经典烟花算法相比,该算法在收敛性和稳定性上都具有较好表现。     

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

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

求解TSP的自适应优秀系数粒子群优化算法

针对基本离散粒子群优化（PSO）算法求解旅行售货商问题（TSP）时容易陷入局部最优解和早熟收敛的问题,提出了一种基于自适应优秀系数的粒子群（SECPSO）算法。为了提高算法的全局搜索能力,在已有工作的基础上,进一步利用启发式信息对静态的路径优秀系数进行修改,使之可根据解的搜索过程进行自适应动态调整;另外,为了进一步提高解的精确性和算法的收敛速度,添加了3-opt搜索机制,提高算法的局部搜索能力。利用Matlab进行了实验仿真,用国际通用的TSP数据库（TSPLIB）中的若干经典实例对算法性能进行了测试。实验结果表明,与其他几种算法相比,SECPSO算法在全局寻优能力和更快的收敛速度方面表现更优,是求解TSP问题的一种有潜力的智能算法。     

求解0-1背包问题的二进制狮群算法

针对传统二进制群智能算法求解0-1背包问题易陷入局部最优、收敛速度慢的缺点,提出一种新的解决离散空间问题的二进制狮群算法BLSO。二进制狮群算法对狮王、母狮和幼狮的位置重新定义,引入反置运算、移动算子和学习算子建立全新的位置转移方式和局部搜索规则;加入贪心策略进行解的可行化处理和充分利用,增强局部搜索能力,进一步提高收敛速度。对9个典型的0-1背包算例进行仿真实验,实验结果表明,该算法不仅可以有效求解0-1背包问题,而且还能够以较快的速度搜索到精度较高的次优解甚至全局最优解,具有较好的稳定性;同时,对高维背包问题的求解与参考算法相比,在寻优时间和精度上更具优势。     

利用确定性退火技术的旅行商问题求解算法*

将确定性退火技术及聚类方法应用于旅行商问题,给出了求解旅行商问题的一种启发式算法.该方法将旅行商问题的离散模型转化为连续模型去求解,通过求解一系列随温度变化的物理系统的自由能函数的局部极小来获得旅行商问题的解,并给出了一个简单的显式迭代公式.算例表明,该算法性能良好.