遗传算法解决tsp问题

遗传算法

遗传算法（GeneticAlgorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，通过模拟自然进化过程搜索最优解。遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。（摘自百度百科。）

问题描述

算法的基本解决步骤

初始化。先设置种群个数，交叉概率和变异概率这三个主要参数的初始值。同时先初始化m个种群的随机城市序列。
适应度函数。通过对于各个城市之间的距离计算和随机城市序列的总距离，找出距离最短的路径，距离越短，适应度函数越好，就越满足TSP要求。
选择操作。遗传算法选择操作可以采用轮盘赌法，让适应度越好的个体被选择的概率越大，同时在选择中保存适应度最高的个体。
交叉操作。选择适应度最高的两个个体，再随机产生交叉位置交换若干个基因片段。
变异操作。选取适应度最高个体，同时随机选取个体的两个基因进行交换以实现变异操作。

算法的基本数据

城市序列

pos= [41 14;37 24;34 47;25 12;7 24;2 39;48 8;11 44;24 32;43 9;14 20;18 34;22 40;3 46;11 38;25 38;24 42;27 49;31 31;44 18;37 46;18 40;13 40;42 7;22 32];
【计算智能】遗传算法解决tsp问题

简单基本参数的调整

原参数：
N=25; %%城市的个数
M=100; %%种群的个数
ITER=2000; %%迭代次数
m=2; %%适应值归一化淘汰加速指数
Pc=0.8; %%交叉概率
Pmutation=0.05; %%变异概率

算法结果
a.算法初始路径

b.初始参数迭代出的路径

c.初始最优结果
最短距离 minlen=2.078279e+02
最优路线 25 12 15 6 14 8 23 22 13 16 19 2 20 7 24 10 1 4 11 5 17 18 3 21 9
初始迭代值2000
由图易得遗传算法迭代次数越多规模越大，反而使算法的性能越差，所用时间越长，迭代次数应可以大幅减少，更改为350较为合适。根据交叉概率，变异概率和种群个数等其他主要的变化再对迭代值进行调整。

不同参数变化对tsp问题影响的分析

种群规模M对结果的影响

其他参数
ITER=2000; %%迭代次数
m=2; %%适应值归一化淘汰加速指数
Pc=0.8; %%交叉概率
Pmutation=0.05; %%变异概率
对M进行分析，取5个M值（每个M值实验5次取最优）

M=10
minlen=1.979754e+02
15 12 25 9 16 17 13 22 23 8 18 3 21 19 2 20 1 7 10 24 4 11 5 6 14
M=20
minlen=2.028531e+02
10 24 4 11 5 12 21 3 18 8 14 6 15 23 22 13 17 16 25 9 19 2 20 1 7
M=30
minlen=1.981685e+02
5 6 14 8 15 23 18 3 21 9 25 12 22 13 17 16 19 2 20 1 7 10 24 4 11
M=50
minlen=2.304120e+02
16 17 21 3 18 8 15 23 22 13 9 25 12 11 5 6 14 4 24 10 7 1 20 2 19
M=200
minlen=2.002157e+02
20 2 19 9 25 16 21 3 18 8 14 6 15 23 22 17 13 12 5 11 4 24 10 7 1

种群规模变化结论
有上述实验结果可以得出种群规模并非越小越好，在M=200和M=20的都有可能得到较优的解，其对最优解并无太大影响，但在实验过程中可以清楚地看到当M越来越大时，收敛速度明显变慢，算法效率变慢。所以进行该实验时还是建议将种群规模适当减小，才能得到更高的效率。

交叉概率Pc对结果的影响

其他参数
N=25; %%城市的个数
M=100; %%种群的个数
ITER=2000; %%迭代次数
m=2; %%适应值归一化淘汰加速指数
Pmutation=0.05; %%变异概率
对Pc进行分析，取5个值（每个值实验5次取最优）

Pc=0.001
minlen=2.233838e+02
1 20 2 19 16 17 18 3 21 13 22 12 25 9 11 5 6 14 8 23 15 4 24 10 7
Pc=0.01
迭代第2000次
minlen=2.152941e+02
14 6 5 11 9 4 24 10 7 1 20 2 19 16 25 12 22 13 17 21 3 18 23 15 8
Pc=0.1
minlen=2.286190e+02
25 12 15 23 8 14 6 5 11 4 24 10 7 20 21 3 18 17 22 13 16 9 19 2 1
Pc=0.5
minlen=2.044620e+02
12 8 14 6 5 11 4 24 10 7 1 20 2 19 16 13 22 15 23 17 18 3 21 9 25
Pc=1
minlen=2.078565e+02
22 5 6 14 8 23 15 12 25 9 11 4 24 7 10 1 20 2 19 16 21 3 18 17 13

交叉概率变化结论
由上述数据易得，当交叉概率过小时，其得出的最优解都并非最小，并且实验中易得其收敛速度在交叉概率小的时候都会慢一些。交叉概率过小将使搜索陷入迟钝状态，较难得到最优解。

变异概率Pmutation对结果的影响

其他参数
N=25; %%城市的个数
M=100; %%种群的个数
ITER=2000; %%迭代次数
m=2; %%适应值归一化淘汰加速指数
Pc=0.8; %%交叉概率
对Pmutation进行分析，取5个值（每个值实验5次取最优）

Pmutation=0.001（收敛慢）
minlen=2.588890e+02
23 12 25 9 2 19 21 3 18 17 13 22 8 14 6 5 11 10 24 7 20 4 1 16 15
Pmutation=0.01
minlen=2.271452e+02
16 12 25 9 19 4 24 10 7 1 20 2 22 23 15 11 5 6 14 8 13 17 18 3 21
Pmutation= 0.05（收敛次数快）
minlen=2.001368e+02
3 18 22 8 14 6 15 23 12 25 9 5 11 4 24 10 7 1 20 2 19 16 13 17 21
Pmutation=0.1
minlen=2.044620e+02
12 8 14 6 5 11 4 24 10 7 1 20 2 19 16 13 22 15 23 17 18 3 21 9 25
Pmutation=0.5（无法收敛，曲线波折大）
minlen=2.703925e+02
17 13 16 25 4 2 19 20 10 7 24 1 11 12 9 21 3 18 23 8 15 14 6 5 22

变异概率变化结论
由上述数据易得，当变异概率过小或者过大时，都能对实验结果产生较大的影响，都无法取得较优的实验结论；同时两种情况都会陷入收敛缓慢的境地，变异概率过大则会直接导致结果不稳定，更易陷入无法收敛的窘境.所以变异概率的值应该取适中。

简单结果检验

设置合适的参数值，实验一次看是否能够较为准确地得到优解。
该实验参数值
N=25; %%城市的个数
M=30; %%种群的个数
ITER=2000; %%迭代次数
m=2; %%适应值归一化淘汰加速指数
Pc=0.5; %%交叉概率
Pmutation=0.05; %%变异概率
实验的第一次结果
minlen=2.021133e+02
6 14 8 25 9 16 13 12 15 23 22 17 18 3 21 19 2 20 1 7 10 24 4 11 5
小总结
从第一次实验中可以看到路径已无明显交叉，且从最终数据可以看到结果已经接近最优解，了解了各个参数对该实验的影响，能有效得提高这类实验的效率，也能更快得到更好的解。