再上一篇:7.2  应用启发式搜索算法求解 TSP
上一篇:7.3  应用模拟退火算法求解 TSP
主页
下一篇:7.5  本征值分析概述
再下一篇:7.6  连接矩阵的 λ1的推导
文章列表

7.4  应用遗传算法求解 TSP

《用于最优化的计算智能》 Nirwan Ansari Edwin Hou 著 李军 边肇祺 译 清华大学出版社

用遗传算法求解TSP,必须具备:

(1) 旅程的符号串表示。

(2) 衡量旅程适存度的适度函数。

(3) 生成新旅程的遗传操作。

正如6.4节所讨论过的,一个N 城市问题可被描述为一个被访问的城市序列并用这些城市的排列来表达。这一排列可用作遗传算法的符号串表示。

一个旅程的适度值Ξ定义为

fitness(Ξ) = Cmax - f(Ξ) (7.29)其中Cmax是整个群体里面所有符号串中的最大旅程距离,f 是由(4.24)式定义的旅程距离总和。

基于偏置轮盘概念的繁殖操作(见6.2.1节)被用来强化适者生存的规则。

用于生成新符号串的遗传操作是有序杂交( )操作[50]。 操作能保留排列并融合

OX OX

不同排列的有序结构单元。例如,假定旅程1和旅程2是10城市问题中的两个旅程:

旅程1= (J H D E F I GC B A)

旅程2= (H GE B C J I A D F)

由OX 操作随机选择交叉截点并用“‖”表示,则

旅程1= (J H D ‖ E F I ‖ GC B A)

旅程2= (H GE ‖ B C J ‖ I A D F)

用“* ”把旅程1的中段映射到旅程2,反过来也一样,可得

旅程1′= (* H D ‖ E F I ‖ G* * A)

旅程2′= (H G * ‖B C J ‖ * A D * )

将“* ”从右向左滑动直到它们都在中段,由此可得

旅程1′= (E F I ‖ * * * ‖ GA H D)

旅程2′= (B CJ ‖ * * * ‖A D H G)

用另一个旅程的中段取代“* ”串,即可得到后代

旅程1′= (E F I B CJ GA H D)

旅程2′= (B CJ E F I A D H G)

从上例可以看出,旅程1′包含其双亲的一部分(旅程1的EFI 和旅程2的BCJ)以及其余城市的随机排列。一般来说,OX操作倾向于保持城市的相对位置。

应用繁殖操作和OX操作,从随机选取的起始群体出发,10城市和20城市(表7.4)问题分别模拟运行500次。

在10城市问题的模拟运行中,用到了下列参数:

(1) 群体大小= 100。

(2) 交叉概率= 0.45。

(3) 迭代次数= 100。

#第70页-

最优解答BCADEFGHIJ 在所有500次运行中均被找到。生成的旅程总数为10000。

在20城市问题的模拟运行中,用到了下列参数:

(1) 群体大小= 300。

(2) 交叉概率= 0.45。

(3) 迭代次数= 300。

最优解答ACLBIQFTMEPRGSOJHDKN 在所有500次运行中均被找到。生成的旅程总数为90000。