多旅行商问题遗传算法求解及其改进.pdf

《多旅行商问题遗传算法求解及其改进.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、多旅行商问题遗传算法求解及其改进熊翠,吴慧萍,李波,,,,华中师范大学数学与统计学学院湖北武汉
!∀#,摘要旅行商问题是一个著名的组合优化问题导,,致结果不合理推销商任务不平均不能合理利,多旅行商回路是旅行商问题的扩展本文综合均用资源。,衡度提出应用遗传算法求解多旅行商问题的算,,%法设计并将其与模拟退火算法比较与结合有∃遗传算法模型效提高了运算的速度和效率。∃%∋遗传算法简介#&&&关键词多旅行商问题遗传算法均衡度模遗传算法是一种以自然选择和遗传理论为基&&拟退火算法模拟退火遗传算法,础将生物进化过程中适者生存规则与同一群染色

2、体的随机信息变换机制相结合的搜索算法。它通过∋%引言给解向量编码、形成初始种群,然后用变异、交叉重组、自然选择等算子,进行并行迭代,求得优化,旅行商问题()∗+,−./012+.−34+05∗67.−4简称。,,解由于它采用随机运算对搜索空间无特殊要求「‘〕#0,,、。)358是一个著名的组合优化问题给定个城市无需求导具有运算简单收敛速度快等优点,#有一个旅行商从某一城市出发访问每个城市各一其主要步骤为,。次&后再回到原出发城市要求找出的巡回路径最短.8先初始产生.个编码个体,,,&如果用图论来描述那就是已知带权图9:(;<8∃8

3、计算每个个体的目标函数。寻出总权值最小的=+而.>60圈8利用轮盘法选出≅个个体作为下一代变异&多旅行商回路(?)258是旅行商问题()358对象,,。?,
8对选出的个体按概率循环变异交叉选择的扩展)25是指给出≅个城市的集合?个推,,&销商从目标城市出发分别走一条旅行路线使得产生新的一代群体,,每个城市有且仅有一个推销商走过,最后回到原Ι8比较现有记录如果比现有记录更优记,。&来的出发城市且总旅程最短有关?)25问题的录下群体中最优的.个个体,,研究在现实问题中有很大的使用价值Α∃Β。诸如#交重复第二步这样遗传到足够多代后会

4、收敛,。通运输、管道铺设、路线的选择、计算机网络的拓到一个近似最优解算法结束,扑设计、邮递员送信等,都可抽象成)35或?)25根据上述步骤我们可结合多旅行商问题的特,。问题。点一一进行研究−0−>Χ6∗遗传算法(9/Δ.1/>Ε48是模拟达尔文∃%∃遗传个体的编码设计生物进化论的自然选择和遗传学机理的生物进化∃%∃%∋,旅行商问题的编码设计过程的计算模型是一种通过模拟自然进化过程搜,,,它在遗传算法中遗传个体的设计很重要需要索最优解的方法最初由美国?/ΧΕ/1+0大学,#Φ,=6.Γ+0Η教授于∋∀!Ι年首先提出来的,是求解复体现

5、个体的遗传特性在这儿设计编码如下,,以卜个城市三个推销商为例设Δ为是个城杂的组合优化问题的有效方法遗传算法在求解,,,一。市的最短距离矩阵用Δ矩阵对应的行列数∋∃)25和?)25问题中得到了厂泛的应用,,,,,,,,,
Ιϑ!Κ∀∋分别表示十个城市其而在求解多旅行商问题的时候常常只能保证。∋,,中点表示旅行商的出发城市总路程最短很少达到使每个推销商的路程均衡,,在旅行商问题中我们将这十个城市保持起,#点在第一位按次序排列表示一个结果(即染色体8,#,,,,,
,!,,,第四届中国智能计算大会论文集芜湖如.∃ϑΙΚ∀∋Ι一,∋∃

6、!一∃∋年月∃∋∃Ι日第∋页路#径表示熊,,翠吴慧萍李波ΛΛ.∃一石一Ι一
一!Κ∀∋∋,。一一一一一一运算量大表示复杂%%∃∃∃多旅行商问题的编码设计,为了简化计算可以定义均衡度为,不妨假定此多旅行商问题存在着三条路线同Φ:∋∋,∋∃,,、(心8样以十个城市为例我们需要插入两个虚点∋∋4+Ο。,,即让三条线中最长的那条尽可能短此定义方∋∃用来表示路线的起点并形成新的编码可用###,,,,式较传统的定义方式有以下几个特点来表示多旅行商问题的染色体如∋ϑΙ∃,,,,,,,/8量纲问题易处理
∋∋!Κ∋∃∀∋,对于这种定义的均

7、衡度它较传统的定义方式#三个路径表示为,在量纲的问题上更接近总路程处理起来也比较简−&.一吞一Ι一Μ−牛一∋。单&一!一Κ一一./8符合所有定义要求−3一∋。一1一.,,,实际上只要能够使得最长的路线都能保持最设置节点∋∋∋∋∃之间的距离为无穷大(即,。,,短那么三条线路的长度就相差就很小了因此它永远不能达到8到其它各点距离与∋点一致得。,也是符合均衡度的定义的·∋∃Ο∋∃到新的最短距离矩阵Ν对应的行列数,。(引/8定义非常简单运算量大大降低分别表示∋∃个节点。并且这样遗传算法选择变异。8综合考虑总路程和均衡度下的目标函数就不

8、会得到∋一∋一∋的路径,要想综合考虑总路程和均衡度首先我们需要。,。∃%遗传算法的目标函数统一量纲我们发现2与Φ的量纲是相同的,我们令了二Φ遗传算法涉及到个体选择淘汰适应性差的个#,因,。于是我们可以得到总目标函数为体此需要建立目标函数来评价