人工智能实验报告

实验六

遗传算法实验II

一、实验目的：

熟悉和掌握遗传算法的原理、流程和编码策略，并利用遗传求解函数优化问题，理解求解TSP问题的流程并测试主要参数对结果的影响。

二、实验原理：

旅行商问题，即TSP问题（Traveling

Salesman

Problem）是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路经的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。TSP问题是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。因此，任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。

遗传算法的基本思想正是基于模仿生物界遗传学的遗传过程。它把问题的参数用基因代表，把问题的解用染色体代表（在计算机里用二进制码表示），从而得到一个由具有不同染色体的个体组成的群体。这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代。后代随机化地继承了父代的最好特征，并也在生存环境的控制支配下继续这一过程。群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似个体，即得到问题最优的解。要求利用遗传算法求解TSP问题的最短路径。

三、实验内容：

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

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

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

4、上交源代码。

四、实验报告要求：

1、画出遗传算法求解TSP问题的流程图。

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

规模越大，算法的性能越差，所用时间越长。

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

（1）

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

x

0

1.1

3.5

4.5

y

1.1

5.1

4.5

实验次数：10

最大迭代步数:100

交叉概率：0.85

变异概率：0.15

种群规模

平均适应度值

最优路径

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

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

如表所示，显然最短路径为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）

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

x

1.1

3.5

3.5

4.5

y

1.1

5.1

8.5

实验次数：15

种群规模：25

最大迭代步数:100

变异概率：0.15

实验结果：

交叉概率

最好适应度

最差适应度

平均适应度

最优解

0.001

28.0447

36.6567

32.6002

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

0.01

27.0935

34.9943

32.1495

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

0.1

28.0447

35.3033

31.9372

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

0.15

28.0447

34.1175

31.2183

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

0.2

28.7108

33.9512

30.9035

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

0.25

28.0447

35.1623

30.7456

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

0.3

27.0935

31.9941

29.9428

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

0.35

27.0935

32.8085

30.9945

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

0.4

27.0935

32.5313

30.1534

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

0.45

27.0935

33.2025

30.1757

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

0.5

28.0934

33.6307

30.9026

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

0.55

27.0935

33.5233

29.1304

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

0.6

27.0935

33.2512

30.7836

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

0.65

28.0447

33.7003

30.9371

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

0.7

27.0935

32.0927

29.9502

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

0.75

28.0447

32.4488

30.3699

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

0.8

27.0935

32.1551

29.9382

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

0.85

27.0935

34.5399

30.3594

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

0.9

27.0935

32.6273

30.69

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

0.95

27.0935

32.4672

29.919

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

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

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

（3）

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

x

1.1

3.5

3.5

4.5

y

1.1

5.1

8.5

实验次数：10

种群规模：25

最大迭代步数:100

交叉概率：0.85

实验结果：

变异概率

最好适应度

最差适应度

平均适应度

最优解

0.001

29.4717

34.732

32.4911

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

0.01

29.0446

34.6591

32.3714

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

0.1

28.0934

34.011

30.9417

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

0.15

27.0935

32.093

30.2568

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

0.2

27.0935

32.2349

30.3144

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

0.25

27.0935

32.718

30.1572

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

0.3

27.0935

32.4488

30.2854

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

0.35

27.0935

33.3167

30.7748

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

0.4

29.0446

34.3705

31.3041

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

0.45

27.0935

31.374

29.6816

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

0.5

27.0935

32.3752

30.2211

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

0.55

27.0935

33.3819

30.6623

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

0.6

28.0934

33.2512

30.36

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

0.65

27.0935

32.7491

30.0201

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

0.7

28.7108

32.4238

30.785

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

0.75

27.0935

31.8928

30.2451

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

0.8

28.0934

31.6135

30.3471

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

0.85

29.662

33.2392

31.1585

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

0.9

28.0447

32.0387

30.4152

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

0.95

28.0447

31.3036

30.0067

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

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

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

不同变异策略和不同个体选择分配策略几乎不影响算法运行的时间，但会影响适应度。

五、实验心得与体会

通过本实验，更加深入体会了参数设置对算法结果的影响。同一个算法，参数值不同，获得的结果可能会完全不同。

同时通过本次实验，使自己对遗传算法有了更进一步的了解。遗传算法是一种智能优化算法，它能较好的近似求解TSP问题，在问题规模比较大的时候，遗传算法的优势就明显体现出来，当然不能完全保证能得到最优解。