实验六遗传算法求解TSP问题实验讲解.docx

资源描述

实验六遗传算法求解TSP问题实验讲解.docx

《实验六遗传算法求解TSP问题实验讲解.docx》由会员分享，可在线阅读，更多相关《实验六遗传算法求解TSP问题实验讲解.docx（25页珍藏版）》请在冰点文库上搜索。

实验六遗传算法求解TSP问题实验讲解.docx

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

实验六：

遗传算法求解TSP问题实验

一、实验目的熟悉和掌握遗传算法的原理、流程和编码策略，并利用遗传求解

函数优化问题，理解求解TSP问题的流程并测试主要参数对结果的影响。

用遗传算法对TSP问题进行了求解，熟悉遗传算法地算法流程，证明遗传算法在求解TSP问题时具有可行性。

二、实验内容

参考实验系统给出的遗传算法核心代码，用遗传算法求解TSP的优化问题，分析遗传算法求解不同规模TSP问题的算法性能。

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

增加1种变异策略和1种个体选择概率分配策略，比较求解同一TSP问题时不同变异策略及不同个体选择分配策略对算法结果的影响。

1.最短路径问题

所谓旅行商问题（TravellingSalesmanProblem,TSJP即最短路径问题，就是在给定的起始点S到终止点T的通路集合中，寻求距离最小的通路，这样的通路成为S点到T点的最短路径。

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

遗传算法方法的本质是处理复杂问题的一种鲁棒性强的启发性随机搜索算法，用遗传算法解决这类问题，没有太多的约束条件和有关解的限制，因而可以很快地求出任意两点间的最短路径以及一批次短路径。

假设平面上有n个点代表n个城市的位置,寻找一条最短的闭合路径,使得可以遍历每一个城市恰好一次。

这就是旅行商问题。

旅行商的路线可以看作是对n个城市所设计的一个环形,或者是对一列n个城市的排列。

由于对n个城市所有可能的遍历数目可达（n-1）!

个,因此解决这个问题需要0（n!

）的计算时间。

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

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

2.遗传算法

遗传算法是由美国J.Holland教授于1975年在他的专著《自然界和人工系统的适应性》中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。

通过模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子（选择、交叉和变异）对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。

遗传算法在本质上是一种不依赖具体问题的直接搜索方法，是一种求解问题的高效并行全局搜索方法。

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

搜索合适的假设从若干初始假设的群体集合开始。

当前种群成员通过模仿生物进化的方式来产生下一代群体，如随机变异和交叉。

每一步，根据给定的适应度评估当前群体的假设，而后使用概率方法选出适应度最高的假设作为产生下一代的种子。

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

（1）染色体（Chromosome）:

在使用遗传算法时，需要把问题的解编成一个适合的码子。

这种具有固定结构的符号串既是染色体，符号串的每一位代表一个基因。

符号串的总位数成为染色体的长度，一个染色体就代表问题的一个解，每个染色体也被称为一个个体。

（2）群体（Population）:

每代所产生的染色体总数成为群体，一个群体包含了该问题在这一代的一些解的集合。

（3）适应度（Fitness）:

对群体中每个染色体进行编码后，每个个体对应一个具体问题的解，而每个解对应于一个函数值。

该函数值即适应函数，就是衡量染色体对环境适应度的指标，也是反映实际问题的目标函数在前一代群体的基础上产生新一代群体的工作成为遗传操作，基本的遗传操作有：

（1）选择（Select）:

按一定的概率从上代群体中选择M对个体作为双亲，直接拷贝到下一代，染色体不发生变化。

（2）交叉（Crossover）:

对于选中进行繁殖的两个染色体X，Y,以X，丫为双亲作交叉操作，从而产生两个后代X1,Y1.

（3）变异（Mutation）对于选中的群体中的个体（染色体），随机选取某一位进行取反运算，即将该染色体码翻转。

用遗传算法求解的过程是根据待解决问题的参数集进行编码，随机产生一个种群，计算适应函数和选择率，进行选择、交叉、变异操作。

如果满足收敛条件，此种群为最好个体，否则，对产生的新一代群体重新进行选择、交叉、变异操作，循环往复直到满足条件。

遗传算法原型

GA（Fitness,Fitness_threshold,p,r,m）

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

Fitness_threshold指定终止判据的阈值

群体中包含的假设数量

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

变异率

初始化群体：

P-随机产生的p个假设

评估:

对于P中的每一个h,计算Fitness（h）

当[maxFitness（h）]

产生新的一代Ps:

（1）选择:

用概率方法选择P的（1-r）p个成员加入Ps从P中选择假设hi的概率用下面公式计算

（2）交叉:

根据上面给出的：

•，从P中按概率选择r（p/2）对假设.对

于每对假设,应用交叉算子产生两个后代•把所有的后代加入

（3）变异:

使用均匀的概率从Ps中选择m%的成员.对于选出的每个成员,在它表示中随机选择一个为取反

（4）更新:

P—Ps

（5）评估:

对于P中的每个h计算Fitness（h）

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

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

对于n个城市的问题，每个个体即每个解的长度为n,用s行，t列的pop矩阵，表示初始群体，s表示初始群体的个数，t为n+1,矩阵的每一行的前n个元素表示城市编码，最后一个元素表示这一路径的长度。

城市的位置可以手动输入，使用一个NXN矩阵D存储，D（i,

j）代表城市i和城市j之间的距离。

D（i,j）二sqrt（（Xi-Xj）八2+（Yi-Yj）“2。

在TSP的求解中，可以直接用距离总和作为适应度函数。

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

选择就是从群体中选择优胜个体、淘汰劣质个体的操作，它是建立在群体中个体适应度评估基础上。

这里采用方法是最优保存方法。

本实例中交叉采用部分匹配交叉策略，先随机选取两个交叉点，然后将两交叉点中间的基因段互换，将互换的基因段以外的部分中与互换后基因段中元素冲突的用另一父代的相应位置代替，直到没有冲突。

变异操作是以变异概率Pm对群体中个体串某些基因位上的基因值作变动，若变异后子代的适应度值更加优异，则保留子代染色体，否则，仍保留父代染色体。

这有助于增加种群的多样性，避免早熟收敛（非全局最优）。

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

结束，输出当前的最优解。

在根据适配值计算并选择的时候，记录下来的当前最优值，在变异后加入跟新的群体，保证新的迭代循环中

TSP解越来越好（不会变差）。

在选择的一种操作是拿最优的K个替换最差的K个个体，本例是按适配值选择，并使群体数目变少，当每次变异操作后，产生随机路径补充群体是群体数目不变，再次循环，一定程度上防止因初始群体的选择问题而陷入局部最优。

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

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

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

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

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

Selectp（h）fromp（n-1）表示从前一代群体中选择一对双亲，用于交叉、变异操作，P（n）代表第n代群体

Crossoverandmutationp（n）进行交叉和变异操作

Learning[p（n）];自学习过程

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

End;

流程图

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

（1）遗传算法执行方式说明：

适应度值计算方法：

当前路线的路径长度

个体选择概率分配方法：

适应度比例方法

选择个体方法：

轮盘赌选择

交叉类型：

PMX交叉

变异类型：

两点互换变异

（2）实验模拟结果：

城市个数

时间（ms）

16925

16630

18833

22596

24159

30289

35239

38608

40032

43757

47746

58143

59942

64361

71417

[ILiiii

06IQt52025303540J5505S6065?

D75BQ

坡市孰罩

图1-1

（3）分析

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

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

（1）种群规模对算法结果的影响实验次数：

最大迭代步数：

100

交叉概率：

0.85

变异概率：

0.15

表1-1

种群规

模

适应度值

最优路径

25.264

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

26.3428

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

25.1652

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

25.1652

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

25.1652

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

100

25.1652

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

150

25.1652

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

200

25.1652

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

250

25.1652

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

300

25.1652

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

如表1-1所示，显然最短路径为25.1652m,最优路径为

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

当种群规模为10,20时，并没有找到最优解。

（2）交叉概率对算法结果的影响

实验次数：

种群规模：

最大迭代步数：

100

变异概率：

0.15

实验结果：

表1-2

交叉概

率

最好适应

度

最差适应

度

平均适应

度

最优解

运行时

间

0.001

28.0447

36.6567

32.6002

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

7-3-1

310

0.01

27.0935

34.9943

32.1495

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

0-5-4

260

0.1

28.0447

35.3033

31.9372

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

5-4-8

300

0.15

28.0447

34.1175

31.2183

0-548-7-3-1

9-2-6

270

0.2

28.7108

33.9512

30.9035

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

4-7-8

280

0.25

28.0447

35.1623

30.7456

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

6-2-9

260

0.3

27.0935

31.9941

29.9428

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

5-4-7

290

0.35

27.0935

32.8085

30.9945

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

0-6-2

270

0.4

27.0935

32.5313

30.1534

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

6-2-9

279

0.45

27.0935

33.2014

30.1757

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

5-4-7

456

0.5

28.0934

33.6307

30.9026

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

8-7-4

663

0.55

27.0935

33.5233

29.1304

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

7-8-3

520

0.6

27.0935

33.2512

30.7836

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

546

4-7-8

0.65

28.0447

33.7003

30.9371

548-7-3-1-9

2-6-0

596

0.7

27.0935

32.0927

29.9502

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

0-6-2

571

0.75

28.0447

32.4488

30.3699

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

9-2-6

559

0.8

27.0935

32.1551

29.9382

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

1-3-8

358

0.85

27.0935

34.5399

30.3594

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

8-7-4

360

0.9

27.0935

32.6273

30.69

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

1-9-2

375

0.95

27.0935

32.4672

29.919

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

4-5-0

476

（注:

红色表示非最优解）

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

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

实验次数：

种群规模：

最大迭代步数：

100

交叉概率：

0.85

实验结果:

表1-3

变异概

率

最好适应

度

最差适应

度

平均适应

度

最优解

运行时

间

0.001

29.4717

34.732

32.4911

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

-4-5

245

0.01

29.0446

34.6591

32.3714

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

-3-7

274

0.1

28.0934

34.011

30.9417

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

-7-4

250

0.15

27.0935

32.093

30.2568

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

-9-2

246

0.2

27.0935

32.2349

30.3144

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

-1-3

282

0.25

27.0935

32.718

30.1572

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

-8-7

245

0.3

27.0935

32.4488

30.2854

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

-2-6

252

0.35

27.0935

33.3167

30.7748

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

-2-9

266

0.4

29.0446

34.3705

31.3041

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

-9-6

362

0.45

27.0935

31.374

29.6816

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

438

-1-9

0.5

27.0935

32.3752

30.2211

2-9-1-3-8-745

-0-6

431

0.55

27.0935

33.3819

30.6623

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

-2-9

492

0.6

28.0934

33.2512

30.36

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

-6-9

417

0.65

27.0935

32.7491

30.0201

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

-7-8

434

0.7

28.7108

32.4238

30.785

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

-2-9

432

0.75

27.0935

31.8928

30.2451

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

-8-3

475

0.8

28.0934

31.6135

30.3471

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

-2-6

327

0.85

29.662

33.2392

31.1585

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

-5-6

314

0.9

28.0447

32.0387

30.4152

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

-2-6

396

0.95

28.0447

31.3036

30.0067

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

-6-2

436

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

注：

（2）（3）的实验数据与

（1）的实验数据不同，详见附录

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

（1）两点互换变异与插入变异的比较：

试验次数（CASNUM）：

城市数（POINTCNT）:

种群规模（POPSIZE）：

100

最大迭代步数（GENERATIONS）:

®。

交叉概率（PC）：

0.85

变异概率（PM）:

0.15

选择个体方法：

轮盘赌选择

交叉类型：

PMX交叉

个体选择概率分配方法：

适应度比例方法

a.变异类型：

两点互换变异

表1-4两点互换变异程序结果

序号

最好适应

度

最差适应

度

平均适应

度

最优解

运行时

间

28.0934

30.4229

29.0891

6-2-0-547-8-3

1-9

1199

27.0935

31.1417

28.9841

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

1678

8-7

27.0935

30.4228

29.0604

0-547-8-3-1-9

2-6

1940

27.0935

30.3703

28.8787

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

2-9

1756

27.0935

31.0619

29.0755

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

7-8

1885

27.0935

31.1589

29.3942

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

1-9

1936

28.0447

31.0619

29.7648

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

5-0

1772

29.0446

31.3475

29.8415

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

7-8

1980

27.0935

30.6143

29.059

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

4-5

1940

27.0935

30.5585

29.0811

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

3-1

1872

27.0935

31.0171

29.4264

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

2-6

1517

27.0935

31.3036

29.2414

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

8-3

1541

27.0935

32.0255

29.0789

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

4-5

1517

27.0935

31.516

28.8906

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

4-5

1345

27.0935

30.4228

29.0226

6-0-547-8-3-1

9-2

1377

27.0935

30.4081

28.9081

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

4-5

1853

27.0935

30.4081

29.3316

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

5-4

1522

27.0935

30.0203

28.5243

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

2-9

1601

28.0447

31.1404

29.567

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

0-6

1609

27.0935

31.1417

29.5359

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

3-8

1311

平均

值

27.3361

30.8782

29.1877

1657

b.变异类型：

插入变异

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

最好适应

最差适

平均适

运行

序号

度

应度

最优解

时间

31.475

28.845

2-6-0-547-8-3-1

27.0935

-9

1388

28.916

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

27.0935

29.662

-4

1355

29.663

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

27.0935

28.902

-3

1637

30.524

29.511

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

28.0447

-8

1164

31.057

29.468

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

27.0935

-9

1245

28.554

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

27.0935

29.662

-9

1222

30.820

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

28.0447

29.748

-7

1148

30.524

29.390

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

27.0935

-3

1742

28.687

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

27.0935

30.423

-5

2064

30.408

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

27.0935

28.72

-4

1518

29.328

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

27.0935

31.374

-7

1240

27.0935

30.523

28.554

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

1204

-9

30.820

29.050

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

27.0935

-5

1734

31.117

29.590

0-547-8-3-1-9-2

27.0935

-6

1532

29.190

4-5

展开阅读全文