GB—MGA 加快遗传算法创新能力论文 编者按：本文主要从单亲演化过程；群体演化过程；实验结果与分析；结束语四个方面进行论述。其中，主要包括：TSP 的搜索空间是有限的、很可能不存在确定的算法能在多项式时间内求到问题的解、遗传算法是一种借鉴生物界自然选择和遗传机制的随机化搜索算法、用遗传算法求解 TSP 能得到令人满意的结果、个体质量的高低决定了算法的全局性能、TSP 编码表示、构建 TSP 基因库、单亲演化算法、基因段错位操作是随机确定基因段、交叉算子、局部启发式算子、选择机制和收敛准则、基于多重搜索策略的群体演化算法、所有的结果都是在 P42.0G 微机上完成、该文算法的求解质量要优于 GA、PGA、MMGA 算法等，具体材料请详见。 论文摘要：TSP 是组合优化问题的典型代表,该文在分析了遗传算法的特点后,提出了一种新的遗传算法(GB—MGA),该算法将基因库和多重搜索策略结合起来,利用基因库指导单亲遗传演化的进化方向,在多重搜索策略的基础上利用改进的交叉算子又增强了遗传算法的全局搜索能力。通过对国际 TSP 库中多个实例的测试,结果表明:算法(GB—MGA)加快了遗传算法的收敛速度,也加强了算法的寻优能力。 论文关键词：旅行商问题遗传算法基因库多重搜索策略 TSP(travelingsalesmanproblem)可以简述为:有 n 个城市1,2,…,n,一旅行商从某一城市出发,环游所有城市后回到原出发地,且各城市只能经过一次,要求找出一条最短路线。TSP 的搜索空间是有限的,假如时间不受限制的话,在理论上这种问题终会找到最优解,但对于稍大规模的 TSP,时间上的代价往往是无法接受的。这是一个典型的组合最优化问题,已被证明是 NP 难问题,即很可能不存在确定的算法能在多项式时间内求到问题的解[1]。由于 TSP 在工程领域有着广泛的应用,如货物运输、加工调度、网络通讯、电气布线、管道铺设等,因而吸引了众多领域的学者对它进行讨论。TSP 的求解方法种类繁多,主要有贪欲法、穷举法、免疫算法[2]、蚂蚁算法[3]、模拟退火算法、遗传算法等。 遗传算法是一种借鉴生物界自然选择和遗传机制的随机化搜索算法,其主要特点是群体搜索策略和群体中个体之间的信息交换,搜索不依赖于梯度信息[4]。遗传算法主要包括选择、交叉和变异 3 个操作算子,它是一种全局化搜索算法,尤其适用于传统搜索算法难于解决的复杂和非线性问题。遗传算法虽然不能保证在有限的时间内获得最优解,但随机地选择充分多个解验证后,错误的概率会降到可以接受的...
