改进遗传算法在tsp问题中的应用

《改进遗传算法在tsp问题中的应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、改进遗传算法在TSP问题中的应用　　摘要：旅行商问题是典型的NP组合优化问题。提出一种旅行商问题求解应用上的改进遗传算法。引入贪心算法优化初始种群，在轮盘赌选择基础上，融入最优保存策略和掺杂算子进行选择操作，以保证群体的多样性；基于两点三段随机交叉算子优化交叉结果，基于启发式倒位变异算子提高算法的收敛速度；给出了求解旅行商问题系统的体系结构。实验结果表明，改进的遗传算法具有更好的寻优能力。　　关键词：旅行商问题；遗传算法；贪心算法；组合优化；体系结构　　DOIDOI：10.11907/rjdk.162168　　中图分类号：TP319　　

2、文献标识码：A文章编号：1672-7800（2016）012-0127-03　　0引言　　旅行商问题（TravelingSalesman9Problem，TSP）是典型的NP组合优化问题，具有重要的理论价值和良好的应用背景，诸如半导体电路设计、公路网络建设、飞机航线安排、连锁店货物配送路线等，通过TSP建模均可解决。求解TSP问题方法包括精确算法、近似算法和智能算法。文献[1]采用遗传算法基础上派生出来的分布估计算法求解TSP问题，并将种群进行分级处理，根据种群级别高低分别采用不同的策略进行交叉和变异操作；文献[2]在基本遗传算法基础上

3、引入外部最优个体集，以增加群体多样性，改善局部搜索能力，采用递归分治策略将遗传算法并行化；文献[3]采用改进的遗传算法，按种群中个体适应度高低采用不同的交叉和变异算子；文献[4]提出一种改进的遗传算法，动态调整交叉和变异概率，以降低染色体近亲繁殖可能，有效控制了进化过程；文献[5]结合遗传算法和模拟退火算法，提出了一种改进的模拟退火遗传算法；文献[6]将蚁群算法和遗传算法融合，经过蚁群算法迭代获得初始种群解集，再采用改进的遗传算法寻优；文献[7]在基本遗传算法基础上，提出改进型多宇宙量子交叉算子，利用不同宇宙间的信息交流提高算法的搜索效

4、率。　　上述求解TSP问题的研究效果很好，但都没有提到有关求解系统的设计问题。本文不但对基本遗传算法求解TSP问题进行分析并加以改进，还给出了求解TSP问题系统的体系结构。实验结果表明，改进的遗传算法具有更可靠的寻优能力，求解系统实用性较好。　　1基本问题描述　　1.1TSP问题　　TSP问题可描述为：一个旅行商要到n个城市推销商品，从一个城市出发，走一遍余下的n-1个城市再回到起点，要求所走的路程最短，即寻找一条巡回路径C=（c1，c2，...，cn），使得下列目标函数最小[8]：　　1.2遗传算法原理及应用9　　遗传算法是一种随机并

5、行搜索算法，其基本思想是：首先对个体编码，生成初始种群，然后开始进化，用适应度函数来判断个体优劣，优秀的个体将获得更多的选择、交叉和变异机会，一直进化到满足迭代的终止条件，从而得到最优解。该算法具有全局寻优能力强、计算过程简单、处理并行性、鲁棒性等优点，在组合优化问题、模式识别、图像处理、调度问题等领域得到了广泛应用[9]。　　2应用遗传算法求解TSP问题　　遗传算法已经广泛应用于求解组合化问题的近似最优解方面，TSP问题是典型的组合优化问题。应用遗传算法求解TSP问题基本方法如下：（1）确定编码方式。用遗传算法求解TSP问题常用的编码

6、方式有二进制表示、顺序表示、路径表示、边表示等，其中路径表示因自然、直观且易于加入启发式信息，是应用最多的一种表示策略。（2）初始化种群。随机产生初始个体，构成指定规模的初始种群，是应用遗传算法求解TSP问题的常用方法。（3）计算种群中每个个体的适应度值。在TSP问题中，目标函数f（C）=∑n-1i=1d（ci，ci+1）+d（cn，c1）是路径总长度，适应度函数通常取目标函数的倒数，即F（C）=1/f（C）。（4）选择算子。目前常用的选择算子有比例选择、最优保存策略、基于联赛的选择等。（5）交叉算子。按照某一交叉概率pc选择若干父体并

7、进行配对。针对路径表示的TSP遗传算法，常用的交叉算子有部分匹配交叉、贪婪交叉、次序交叉和循环交叉等。（6）变异算子。按照某一变异概率pm随机确定变异个体，常用的变异算子包括倒位变异、插入变异、移位变异和2-opt变异等。（7）迭代终止条件。若算法满足迭代的终止条件，则停止迭代；否则转至第（3）步，利用适应度函数重新计算每个个体的适应度值。基本遗传算法存在易陷入局部最优、收敛速度慢和优化精度低等缺点。改进遗传算法的目标是在提高算法收敛速度的同时确保种群多样性，从而使寻优结果接近最优解[10]。　　3求解TSP问题的改进遗传算法9　　3.

8、1个体路径编码表示　　路径表示法是TSP问题最直接的表示方法，本文算法采用此方法进行个体编码，每个个体就是一次访问城市的顺序排列。编码串（x1，x2，...，xn）表示从城市x1出发，依次经过城市x2，x3