摘要：针对传统遗传算法(GA)在求解旅行商问题(TSP)时,因种群多样性丢失、局部搜索能力减弱导致算法寻优效率低、易早熟等问题,提出了一种基于策略池-扩张机制的改进遗传算法(SPEM-IGA)。根据不同目的设计了两组策略池,为增强解的搜索深度,构造由2-opt、启发式插入、贪婪算子组成的局部搜索策略池;为扩大解的搜索范围,再将近邻插入、翻转、片段交换、循环左移算子组成全局搜索策略池。根据种群多样性水平,设计了基于策略池的随机选择机制,并使种群动态扩张,能有效改善种群的多样性,平衡算法的全局与局部搜索能力。通过精英优选保留种群中的优质个体,以加快算法收敛速度。仿真实验表明,与现有文献相比,基于策略池-扩张机制的改进遗传算法具有更好的求解精度和稳定性。

摘要：针对遗传算法求解旅行商问题存在收敛速度慢、容易陷入局部最优等问题,提出了基于组合变异和分组优化的单亲遗传算法。算法设计了由双侧倒序、近邻交换、跳跃基因构成的组合变异算子,用于扩大搜索范围,增强种群的多样性;经过精英优选后,将种群按适应度优劣分为两组作局部优化,对优质互异组依次采用插入和2opt算子,加快进化收敛速度;对普通组用倒序算子,增强其跳出局部最优的能力。仿真实验表明,对于中小型规模的旅行商问题,该算法在收敛速度和求解能力上得到明显改善和增强。