实验六：遗传算法求解TSP问题实验

实验六：遗传算法求解TSP问题实验

一、实验目的

熟悉和掌握遗传算法的原理、流程和编码策略，并利用遗传求解函数优化

问题，理解求解TSP问题的流程并测试主要参数对结果的影响。用遗传算法对

TSP问题进行了求解，熟悉遗传算法地算法流程，证明遗传算法在求解TSP问

题时具有可行性。

二、实验内容

参考实验系统给出的遗传算法核心代码，用遗传算法求解TSP的优化问题,

分析遗传算法求解不同规模TSP问题的算法性能。

对于同一个TSP问题，分析种群规模、交叉概率和变异概率对算法结果的

影响。

增加1种变异策略和1种个体选择概率分配策略，比拟求解同一TSP问题

时不同变异策略及不同个体选择分配策略对算法结果的影响。

1.最短路径问题

所谓旅行商问题即最短路径问题,就是在

(TravellingSalesmanProblemzTSP),

给定的起始点S到终止点T的通路集合中，寻求距离最小的通路，这样的通路

成为S点到T点的最短路径。

在寻找最短路径问题上，有时不仅要知道两个指定顶点间的最短路径，还需要

知道某个顶点到其他任意顶点间的最短路径。遗传算法方法的本质是处理复杂

问题的一种鲁棒性强的启发性随机搜索算法，用遗传算法解决这类问题，没有

太多的约束条件和有关解的限制，因而可以很快地求出任意两点间的最短路径

以及一批次短路径。

假设平面上有n个点代表n个城市的位置，寻找一条最短的闭合路径，使得可

以遍历每一个城市恰好一次。这就是旅行商问题。旅行商的路线口J以看作是对

n个城市所设计的一个环形，或者是对一列n个城市的排列。由于对n个城市

所有可能的遍历数目可达(n-1)!个，因此解决这个问题需要0(n!)的计算时间。

假设每个城市和其他任一城市之间都以欧氏距离直接相连。也就是说，城市间

距可以满足三角不等式，也就意味着任何两座城市之间的直接距离都小于两

城市之间的间接距离。

2.遗传算法

遗传算法是由美国J.Holland教授于1975年在他的专著《自然界和人工系统的

适应性》中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随机

化搜索算法。通过模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突

变现象，在每次迭代中都保存一组候选解，并按某种指标从解群中选取较优的

个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的

候选解群，重复此过程，直到满足某种收敛指标为止。遗传算法在本质上是一

种不依赖具体问题的直接搜索方法，是一种求解问题的高效并行全局搜索方

法。其假设常描述为二进制位串，位串的含义依赖于具体应用。搜索适宜的假

设从假设干初始假设的群体集合开始。当前种群成员通过模仿生物进化的方式

来产生下一代群体，如随机变异和交叉。每一步，根据给定的适应度评估当前

群体的假设，而后使用概率方法选出适应度最高的假设作为产生下一代的种

子。

下面介绍几个遗传算法的几个根本概念：

⑴染色体(Chromosome)：在使用遗传算法时，需要把问题的解编成一个

适合的码子。这种具有固定结构的符号串既是染色体，符号串的每一位代表一

个基因。符号串的总位数成为染色体的长度，一个染色体就代表问题的一个解,

每个染色体也被称为一个个体。

(2)群体(Population)：每代所产生的染色体总数成为群体，一个群体包含

了该问题在这一代的一些解的集合。

(3)适应度(Fitness)：对群体中每个染色体进行编码后，每个个体对应一个

具体问题的解，而每个解对应于一个函数值。该函数值即适应函数，就是衡量

染色体对环境适应度的指标，也是反映实际问题的目标函数

在前一代群体的根底上产生新一代群体的工作成为遗传操作，根本的遗传操作

有：

(1)选择(Select)：按一定的概率从上代群体中选择M对个体作为双亲，直

接拷贝到下一代，染色体不发生变化。

12)交叉(Crossover)：对于选中进行繁殖的两个染色体X,Y,以X,Y为双

亲作交叉操作，从而产生两个后代XI,Y1.

(3)变异(Mutation)：对于选中的群体中的个体(染色体)，随机选取某一

位进行取反运算，即将该染色体码翻转。

用遗传算法求解的过程是根据待解决问题的参数集进行编码，随机产生一个

种群，计算适应函数和选择率，进行选择、交叉、变异操作。如果满足收敛

条件,此种群为最好个体，否则，对产生的新一代群体重新进行选择、交叉、

变异操作，循环往复直到满足条件。

遗传算法原型：

GA(Fitness,Fitness_threshold,p,r,m)

Fitness:适应度评分函数，为给定假设赋予一个评估分数

Fitness_threshold:指定终止判据的阈值

P：群体中包含的假设数量

r:每一步中逋过交叉取代群体成员的比例

m:变异率

初始化群体:P-随机产生的p个假设

评估:对于P中的每一个h,计算Fitness(h)

S[maxFitness(h)]<Fitness_threshold/i%

产生新的一代Ps:

⑴选择:用概率方法选择P的(l-r)p个成员参加Ps.从P中选择假设hi的概率用

下面公式计算：

⑵交叉:根据上面给出的酎血】,从P中按概率选择r(p⑵对假设.对于每对假设

<hl,h2>,应用交叉算子产生两个后代.把所有的后代参加Ps

⑶变异:使用均匀的概率从Ps中选择m%的成员.对于选出的每个成员,在它表

示中随机选择一个为取反

(4)更新:P-Ps

(5)评估:对于P中的每个h计算Fitness(h)

从P中返回适应度最高的假设

3.TSP问题的遗传算法设计与实现

对于n个城市的问题，每个个体即每个解的长度为n,用s行,t歹U的pop矩阵,

表示初始群体，s表示初始群体的个数，t为n+1,矩阵的每一行的前n个元素

表示城市编码，最后一个元素表示这一路径的长度。城市的位置可以手动输入,

使用一个NXN矩阵D存储，D(i,j)代表城市i和城市j之间的距离。D(i,

AA

jj=sqrt((Xi-Xj).2+(Yi-Yj).2)o

在TSP的求解中，可以直接用距离总和作为适应度函数。个体的路径长度越小,

所得个体优越，距离的总和越大，适应度越小，进而探讨求解结果是否最优。

选择就是从群体中选择优胜个体、淘汰劣质个体的操作，它是建立在群体中个

体适应度评估根底上。这里采用方法是最优保存方法。

本实例中交叉采用局部匹配交叉策略，先随机选取两个交叉点，然后将两交叉

点中间的基因段互换，将互换的基因段以外的局部中与互换后基因段中元素冲

突的用另一父代的相应位置代替，直到没有冲突。

变异操作是以变异概率Pm对群体中个体串某些基因位上的基因值作变动，假

设变异后子代的适应度值更加优异，那么保存子代染色体，否则，仍保存父

代染色体。这有助于增加种群的多样性，防止早熟收敛(非全局最优)。

判断结束准则是固定指定了迭代的次数当算法到达迭代次数时，算法结束，

输出当前的最优解。在根据适配值计算并选择的时候，记录下来的当前最优值,

在变异后参加跟新的群体，保证新的迭代循环中TSP解越来越好(不会变差)。

在选择的一种操作是拿最优的K个替换最差的K个个体，本例是按适配值选择,

并使群体数目变少，当每次变异操作后，产生随机路径补充群体是群体数目不

变，再次循环，一定程度上防止因初始群体的选择问题而陷入局部最优。

4.TSP问题的遗传算法的具体步骤

解最短路径的遗传算法如下：

Generate[p(n)];表示程序开始时要首先产生一个群体，群体个数为n

Evaluate[p(h)];表示计算每个个体适应度，h是种群中的一个个体

RepeatroofGenerationstimes;重复下面的操作，直到满足条件为止

Selectp(h)fromp(n-l);表示从前一代群体中选择一对双亲，用于交叉、变异操

作，P(n)代表第n代群体

Crossoverandmutationp(n);进行交叉和变异操作

Learning[p(n)];自学习过程

Evaluate[p(h)];计算新生成的种群中每个个体的适应度

End;

具体流程图如下所示：

流程图

5.遗传算法求解不同规模的TSP问题的算法性能

(1)遗传算法执行方式说明：

•适应度值计算方法：当前路线的路径长度

•个体选择概率分配方法：适应度比例方法

•选择个体方法：轮盘赌选择

•交叉类型：PMX交叉

•变异类型：两点互换变异

⑵实验模拟结果:

城市个数时间(ms)

516925

1016630

1518833

2022596

2524159

3030289

3535239

4038608

4540032

5043757

5547746

6058143

6559942

7064361

7571417

图1-1

⑶分析

由图1-1可知，遗传算法执行时间随着TSP问题规模的增大而增大，并且

大致为线性增长。

五、不同参数下的计算结果比照

(1)种群规模对算法结果的影响

实验次数：10

最大迭代步数：100

交叉概率：0.85

变异概率：0.15

表1-1

种群规

模适应度值最优路径

1025.2644-5-8-7-6-3-1-0-9-2

2026.34282-9-1-0-3-6-7-5-8-4

3025.16521-3-6-7-5-8-4-2-9-0

5025.1652()-1-3-6-7-5-8-429

8025.16529-0-1-3-6-7-5-8-4-2

10025.16521-0-9-2-4-8-5-7-6-3

15025.16525-8-4-2-9-0-1-3-6-7

20025.16521-3-6-7-5-8-4-2-9-0

25025.16523・1-0-924-8-576

30025.16525-8-4-2-9-0-1-3-6-7

如表1-1所示，显然最短路径为25.1652m,最优路径为1-0・9-1-3-6-7-5-8-4-2或

3-1-0-9-2-4-8-5-7-6,注意到这是一圈,顺时针或者逆时针都可以。当种群规模

为10,20时，并没有找到最优解。

(2)交叉概率对算法结果的影响

实验次数：15

种群规模：25

最大迭代步数:100

变异概率：0.15

实验结果：

表1-2

交叉概最好适应最差适应平均适应运行时

率度度度最优解间

9-2-6-0-5-4-8-

0.00128.044736.656732.60027-3-1310

0.0127.093534.994332.14957-8-3-1-9-2-6-260

0-5-4

7-3-1-9-2-6-0-

0.128.044735.303331.93725-4-8300

0-5-4-8-7-3-1-

0.1528.044734.117531.21839-2-6270

3-1-9-2-6-5-0-

0.228.710833.951230.90354-7-8280

1-3-7-8-4-5-0-

0.2528.044735.162330.74566-2-9260

8-3-l-9-2-6-0-

0.327.093531.994129.94285-4-7290

9-1-3-8-7-4-5-

0.3527.093532.808530.99450-6-2270

1-3-8-7-4-5-0-

0.427.093532.531330.15346-2-9279

8-3-1-9-2-6-0-

0.4527.093533.202330.17575-4-7456

5-0-2-6-9-1-3-

0.528.093433.630730.90268-7-4663

1-9-2_6_0_5_4-

0.5527.093533.523329.13047-8-3520

3-1-9-2-6-0-5-

0.627.093533.251230.78364-7-8546

5-4-8-7-3-1-9-

0.6528.044733.700330.93712-6-0596

9-1-3-8-7-4-5-

0.727.093532.092729.95020-6-2571

0-5-4-8-7-3-1-

0.7528.044732.448830.36999-2-6559

7-4-5_0_6_2_9-

0.827.093532.155129.93821-3-8358

5-0-6-2-9-1-3-

0.8527.093534.539930.35948-7-4360

6-0-5-4-7-8-3-

0.927.093532.627330.691-9-2375

6-2-9-1-3-8-7-

0.9527.093532.467229.9194-5-0476

（注:红色表示非最优解）

在该情况下，交叉概率过低将使搜索陷入迟钝状态，得不到最优解。

（3）变异概率对算法结果的影响

实验次数：10

种群规模：25

最大迭代步数：100

交叉概率：0.85

实验结果：

表1-3

变异概最好适应最差适应平均适应运行时

率度度度最优解间

0-6-2-1-9-3-8-7

0.00129.471734.73232.4911-4-5245

8-4-5-0-2-6-9-1

0.0129.044634.659132.3714-3-7274

5-0-2-6-9-1-3-8

0.128.093434.01130.9417-7-4250

6-0-5-4-7-8-3-1

0.1527.093532.09330.2568-9-2246

8-7-4-5-0-6-2-9

0.227.093532.234930.3144-1-3282

4-5-0-6-2-9-1-3

0.2527.093532.71830.1572-8-7245

0-5-4-7-8-3T-9

0.327.093532.448830.2854-2-6252

1-3-8-7-4-5-0-6

0.3527.093533.316730.7748-2-9266

2-0-5-4-8-7-3T

0.429.044634.370531.3041-9-6362

2-6-0-5-4-7-8-3

0.4527.093531.37429.6816-1-9438

0.527.093532.375230.22112-9-1-3-8-7-4-5431

-0-6

1-3-8-7-4-5-0-6

0.5527.093533.381930.6623-2-9492

1-3-8-7-4-5-0-2

0.628.093433.251230.36-6-9417

3-1-9-2-6-0-5-4

0.6527.093532.749130.0201-7-8434

1-3-8-7-4-0-5-6

0.728.710832.423830.785-2-9432

1-9-2-6-0-5-4-7

0.7527.093531.892830.2451-8-3475

9-1-3-8-7-4-5-0

0.828.093431.613530.3471-2-6327

2-9-1-3-7-8-4-0

0.8529.66233.239231.1585-5-6314

0-5-4-8-7-3-1-9

0.928.044732.038730.4152-2-6396

9T-3-7-8-4-5-0

0.9528.044731.303630.0067-6-2436

又表1-3可知，当变异概率过大或过低都将导致无法得到最优解。

注：(2)(3)的实验数据与(1)的实验数据不同，详见附录。

六、不同变异策略和个体选择概率分配策略对算法结果的影响

(1)两点互换变异与插入变异的比拟：

•试验次数(CASNUM)：10

•城市数(POINTCNT):10

•种群规模(POPSIZE)：100

・最大迭代步数(GENERATIONS):1。。

•交叉概率(PC)：0.85

•变异概率(PM):0.15

•选择个体方法：轮盘赌选择

•交叉类型：PMX交叉

•个体选择概率分配方法：适应度比例方法

a,变异类型：两点互换变异

表1.4两点互换变异程序结果

最好适应最差适应平均适应运行时

序号度度度最优解间

6-2-0-5-4-7-8-3-

128.093430.422929.08911-91199

4-5-0-6-2-9-1-3-

227.093531.141728.98418-71678

0-5-4-7-8-3-1-9-

327.093530.422829.06042-61940

427.093530.370328.87871-3-8-7-4-5-0-6-1756

2-9

3-1-9-2-6-0-5-4-

527.093531.061929.07557-81885

2-6-0-5-4-7-8-3-

627.093531.158929.39421-91936

6-2-9-1-3-7-8-4-

728.044731.061929.76485-01772

4-5-0-2-6-9-1-3-

829.044631.347529.84157-81980

0-6-2-9-1-3-8-7-

927.093530.614329.0594-51940

9-2-6-0-5-4-7-8-

1027.093530.558529.08113-11872

0-5-4-7-8-3-1-9-

1127.093531.017129.42642-61517

1-9-2-6-0-5-4-7-

1227.093531.303629.24148-31541

0-6-2-9-1-3-8-7-

1327.093532.025529.07894-51517

0-6-2-9_l_3_8_7-

1427.093531.51628.89064-51345

6-0-5-4-7-8-3-1-

1527.093530.422829.02269-21377

0-6-2-9-1-3-8-7-

1627.093530.408128.90814-51853

7-8_3_1_9_2_6_0-

1727.093530.408129.33165-41522

1-3-8-7-4-5-0-6-

1827.093530.020328.52432-91601

2-9-1-3-7-8-4-5-

1928.044731.140429.5670-61609

7-4-5-0-6-2-9-1-

2027.093531.141729.53593-81311

平均

值27.336130.878229.18771657

b.变异类型：插入变异

表1・5插入变异程序结果

最好适应最差适平均适运行

序号度应度应度最优解时间

31.47528.8452-6-0-5-4-7-8-3-1

127.093533-91388

28.9165-0-6-2-9-1-3-8-7

227.093529.6628-41355

29.6631-9-2-6-0-5-4-7-8

327.0935128.902-31637

428.044730.52429.5114-5-0-6-2-9-1-3-71164

19-8

31.05729.4682-6-0-5-4-7-8-3-1

527.093552-91245

28.5542-6-0-5-4-7-8-3-1

627.093529.6626-91222

30.8203-1-9-2-6-0-5-4-8

728.0447529.748-71148

30.52429.3901-9-2-6-0-5-4-7-8

827.093517-31742

28.6870-6-2-9-1-3-8-7-4

927.093530.4238-52064

30.4085-0-6-2-9-1-3-8-7

1027.0935128.72-41518

29.3284-5-0-6-2-9-1-3-8

1127.093531.3742-71240

28.5541-3-8-7-4-5-0-6-2

1227.093530.5234-91204

30.82029.0500-6-2-9-1-3-8-7-4

1327.093558-51734

31.11729.5900-5-4-7-8-3-1-9-2

1427.093575-61532

29.1904-5-0-6-2-9-1-3-8

1527.093530.5234-71483

30.40828.8065-0-6-2-9-1-3-8-7

1627.093511-41282

31.76329.4596-0-5-4-7-8-3-1-9

1727.093591-21485

31.15829.1614-5-0-6-2-9-1-3-8

1827.093594-71601

30.40828.5972-6-0-5-4-7-8-3-1

1927.093514-91507

30.61428.8033-1-9-2-6-0-5-4-7

2027.093536-81234

30.64629.064

平均值27/p>

分析:

两点互换变异20次模拟中，4次得到非最优解；而插入变异只有2次；插

入变异的最好适应度平均值比两点互换变异小0.14755,最差适应度平均值和

总的适应度平均值都比两点互换下，并且在Release下，运行时间前者比后者

快218.3mso可见在该条件下(交叉概率，变异概率，种群规模等)，插入变

异比两点互换变异的算法效果要好。

⑵个体选择分配策略

•试验次数(CASNUMh10

•城市数(POINTCNT):10

•种群规模(POPSIZE)：100

•最大迭代步数(GENERATIONS)：1。。

•交叉概率(PC)：0.85

•变异概率(PM):0.15

•选择个体方法：轮盘赌选择

•交叉类型：PMX交叉

•变异类型：两点互换变异

a,个体选择概率分配方法：适应度比例方法

同表1-4

b.个体选择概率分配方法：非线性排序方式

表1-6非线性排序方式程序结果

最好适最差适平均适应运行时

序号应度应度度最优解间

1-9-2-6-0-5-4-7-

127.093532.172130.09048-3824

4-5_0-6_2_9-1-3-

228.044731.29729.99797-8865

2-0-5-4-7-8-3-1-

328.093432.168330.56019-6895

3-1-9-2-6-0-5~4-

427.093532.097330.34727-81067

4-5-0-6-2-9-1-3-

527.093531.51629.85318-7887

5-0-6-2-9-1-3-8-

627.093531.40829.46377-4727

3-1-9-2-6-0-5-4-

727.093531.374229.94767-8651

0-5-4-7-8-1-3~9~

829.523131.800930.55432-6901

0-5-4-7-8-3-1-9-

927.093532.714730.3912-6749

9-3-1-8-7-4-5-0-

1029.523131.5688