【人工智能Ⅰ】实验2：遗传算法

本文介绍: 实验2 遗传算法实验一、实验目的熟悉和掌握遗传算法的原理、流程和编码策略，理解求解TSP问题的流程并测试主要参数对结果的影响，掌握遗传算法的基本实现方法。二、实验原理旅行商问题，即TSP问题（Trav el in g Sales m an Problem）是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，n个城市之间的相互距离已知，他必须选择所要走的路径，路经的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。用图

实验2 遗传算法实验

一、实验目的

熟悉和掌握遗传算法的原理、流程和编码策略，理解求解TSP问题的流程并测试主要参数对结果的影响，掌握遗传算法的基本实现方法。

二、实验原理

旅行商问题，即TSP问题（Trav el in g Salesman Problem）是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，n个城市之间的相互距离已知，他必须选择所要走的路径，路经的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。

用图论的术语来说，假设有一个图g=(v,e)，其中v是顶点集，e是边集，设d=(dij)是由顶点i和顶点j之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶点且每个顶点只通过一次的具有最短距离的回路。TSP问题是一个典型的组合优化问题，该问题可以被证明具有NPC计算复杂性，其可能的路径数目与城市数目n是成指数型增长的，所以一般很难精确地求出其最优解，本实验采用遗传算法求解。

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

三、实验内容

1、参考给出的遗传算法核心代码，用遗传算法求解不同规模（例如30个城市，50个城市，100个城市）的TSP问题，每个规模可多次运行，把结果填入表1。

为探究遗传算法的基本结果，本实验【1】中的测试环境中的各类参数依次是：迭代次数为500、种群大小为100、交叉概率为0.95、变异概率为0.05。

为更好地展示不同城市规模下的运行结果，本实验测试了共15次独立的运行结果（每种情况5次），并制作表1.a至表1.c，分别描述城市规模在30、50、100情况下的最优解、运行时间和适应度。

表1 遗传算法求解不同规模的TSP问题的结果

城市规模	最好适应度	平均适应度	平均运行时间/s
30	0.0010876	0.0010783	3.366
50	0.00050724	0.00048681	5.699
100	0.000120612	0.000116615	12.442

表1.a. 当城市规模为30时，不同次运行情况下的结果

运行次数序号	输出的最优解	输出的运行时间/s	最优解的倒数（适应度）
1	933.21	3.335	0.0010716
2	919.47	3.358	0.0010876
3	922.76	3.401	0.0010837
4	921.28	3.376	0.0010854
5	940.38	3.359	0.0010634
平均结果	927.42	3.366	0.0010783

表1.b. 当城市规模为50时，不同次运行情况下的结果

运行次数序号	输出的最优解	输出的运行时间/s	最优解的倒数（适应度）
1	1982.82	5.612	0.00050433
2	2245.79	5.719	0.00044528
3	2092.17	5.668	0.00047797
4	1971.46	5.701	0.00050724
5	2003.16	5.794	0.00049921
平均结果	2059.08	5.699	0.00048681

表1.c. 当城市规模为100时，不同次运行情况下的结果

运行次数序号	输出的最优解	输出的运行时间/s	最优解的倒数（适应度）
1	8291.08	12.263	0.000120612
2	8872.99	12.390	0.000112702
3	8650.03	12.579	0.000115607
4	8606.05	12.335	0.000116197
5	8477.67	12.644	0.000117957
平均结果	8579.56	12.442	0.000116615

2、对于同一个TSP问题（例如30个城市），设置不同的种群规模（例如40，70，100）、交叉概率（0，0.5，0.85，1）和变异概率（0，0.15，0.5，1），把结果填入表2。

为更好地展示不同种群规模、交叉概率和变异概率下的运行结果，本实验确定城市规模为30，测试了共27次独立的运行结果（每种情况3次），并制作表2.a至表2.i，分别描述表2中各种情况下的最优解、运行时间和适应度。

单独从群体规模来看，群体规模越大，运行时间越长，越有可能达到全局最优解。单独从交叉概率来看，交叉概率越大，运行时间越长，越有可能达到全局最优解。单独从变异概率来看，变异概率越大，运行时间越长，越有可能达到全局最优解。GA算法因为存在随机的概率问题，所以不一定能够完全达到全局最优解。

综上所述，在寻找全局最优解时，应该综合考虑群体规模、交叉概率和变异概率的设置，以达到在更优的时间内找到局部最优解的效果。

表2 不同的种群规模、交叉概率和变异概率的求解结果

种群规模	交叉概率	变异概率	最好适应度	最优距离解	平均适应度	平均运行时间/s
40	0.85	0.15	0.00108367	922.79	0.001050746	1.423
70	0.85	0.15	0.001103327	906.35	0.001096252	2.459
100	0.85	0.15	0.001094703	913.49	0.001090596	3.348
100	0	0.15	0.00110346	906.24	0.001096852	1.714
100	0.5	0.15	0.001109189	901.56	0.001099548	2.670
100	1	0.15	0.001094595	913.58	0.001092195	3.629
100	0.85	0	0.00074589	1340.68	0.000673965	3.077
100	0.85	0.5	0.001109189	901.56	0.001083609	3.868
100	0.85	1	0.00110595	904.2	0.001103193	4.719

表2.a. 当种群规模为40、交叉概率为0.85、变异概率为0.15时，不同次运行情况下的结果

运行次数序号	输出的最优解	输出的运行时间/s	最优解的倒数（适应度）
1	976.16	1.409	0.001024422
2	957.72	1.441	0.001044147
3	922.79	1.419	0.00108367
平均结果	952.22	1.423	0.001050746

表2.b. 当种群规模为70、交叉概率为0.85、变异概率为0.15时，不同次运行情况下的结果

运行次数序号	输出的最优解	输出的运行时间/s	最优解的倒数（适应度）
1	921.47	2.585	0.001085223
2	908.92	2.398	0.001100207
3	906.35	2.394	0.001103327
平均结果	912.25	2.459	0.001096252

表2.c. 当种群规模为100、交叉概率为0.85、变异概率为0.15时，不同次运行情况下的结果

运行次数序号	输出的最优解	输出的运行时间/s	最优解的倒数（适应度）
1	921.73	3.322	0.001084916
2	915.61	3.401	0.001092168
3	913.49	3.32	0.001094703
平均结果	916.94	3.348	0.001090596

表2.d. 当种群规模为100、交叉概率为0、变异概率为0.15时，不同次运行情况下的结果

运行次数序号	输出的最优解	输出的运行时间/s	最优解的倒数（适应度）
1	906.24	1.678	0.00110346
2	920.17	1.742	0.001086756
3	908.81	1.722	0.00110034
平均结果	911.74	1.714	0.001096852

表2.e. 当种群规模为100、交叉概率为0.5、变异概率为0.15时，不同次运行情况下的结果

运行次数序号	输出的最优解	输出的运行时间/s	最优解的倒数（适应度）
1	901.56	2.657	0.001109189
2	901.67	2.702	0.001109053
3	925.58	2.652	0.001080404
平均结果	909.60	2.670	0.001099548

表2.f. 当种群规模为100、交叉概率为1、变异概率为0.15时，不同次运行情况下的结果

运行次数序号	输出的最优解	输出的运行时间/s	最优解的倒数（适应度）
1	913.58	3.644	0.001094595
2	915.6	3.621	0.00109218
3	917.59	3.622	0.001089811
平均结果	915.59	3.629	0.001092195

表2.g. 当种群规模为100、交叉概率为0.85、变异概率为0时，不同次运行情况下的结果

运行次数序号	输出的最优解	输出的运行时间/s	最优解的倒数（适应度）
1	1593.27	3.063	0.00062764
2	1340.68	3.081	0.00074589
3	1542.34	3.087	0.000648365
平均结果	1492.10	3.077	0.000673965

表2.h. 当种群规模为100、交叉概率为0.85、变异概率为0.5时，不同次运行情况下的结果

运行次数序号	输出的最优解	输出的运行时间/s	最优解的倒数（适应度）
1	922.94	3.858	0.001083494
2	945.05	3.852	0.001058145
3	901.56	3.894	0.001109189
平均结果	923.18	3.868	0.001083609

表2.i. 当种群规模为100、交叉概率为0.85、变异概率为1时，不同次运行情况下的结果

运行次数序号	输出的最优解	输出的运行时间/s	最优解的倒数（适应度）
1	908.84	4.821	0.001100304
2	904.20	4.678	0.00110595
3	906.35	4.659	0.001103327
平均结果	906.46	4.719	0.001103193

3、设置种群规模为100，交叉概率为0.85，变异概率为0.15，然后增加1种变异策略（例如相邻两点互换变异、逆转变异或插入变异等）和1种个体选择概率分配策略（例如按线性排序或者按非线性排序分配个体选择概率）用于求解同一TSP问题（例如30个城市），把结果填入表3（选做）。

为更好地展示不同变异策略和个体选择概率分配策略下的运行结果，本实验确定城市规模为30，测试了共20次独立的运行结果（每种情况5次），并制作表3.a至表3.d，分别描述表3中各种情况下的最优解、运行时间和适应度。

同时，逆转变异方法和最佳个体保存方法已经在实验1和实验2中使用，分别为表3中的原始变异策略和原始选择策略。增加的变异策略为：相邻两点互换方法。增加的选择策略为：锦标赛选择方法。

根据表3分析可知，新增的变异策略和选择策略都不如原始的变异策略和选择策略，可能的原因是新增的策略较为简单。例如，在变异策略中，相邻两点互换方法只更新了2个基因点位，而逆转变异方法更新的基因点位超过2个，且样式更为复杂多样；在选择策略中，锦标赛选择方法只是随机抽取c组进行竞争覆盖，但覆盖的个体并不一定是群体最优的个体，而最佳个体保存法则是选择群体中最优的个体，覆盖掉群体中最差的c个个体，覆盖效果更好。

从运行时间上来看，新增的变异策略的运行速度不如原始的变异策略，新增的选择策略的运行速度也不如原始的选择策略。

表3 不同的变异策略和个体选择概率分配策略的求解结果

变异策略	个体选择概率分配	最好适应度	最好距离解	最差适应度	最差距离解	平均适应度	平均运行时间
相邻两点互换	锦标赛选择	0.000394882	2532.40	0.000366783	2726.41	0.000382961	3.973
相邻两点互换	原始选择策略	0.000881244	1134.76	0.00077884	1283.96	0.000813394	3.792
原始变异策略	锦标赛选择	0.000395764	2526.76	0.000358286	2791.07	0.000379782	3.679
原始变异策略	原始选择策略	0.001103327	906.35	0.001084916	921.73	0.001095091	3.360

表3.a. 当变异策略采用【相邻两点互换】、个体选择概率分配采用【锦标赛选择】时，不同次运行情况下的结果

运行次数序号	输出的最优解	输出的运行时间/s	最优解的倒数（适应度）
1	2586.94	3.878	0.000386557
2	2654.42	3.953	0.00037673
3	2565.08	4.034	0.000389851
4	2726.41	3.963	0.000366783
5	2532.40	4.038	0.000394882
平均结果	2613.05	3.9732	0.000382961

表3.b. 当变异策略采用【相邻两点互换】、个体选择概率分配采用【原始选择策略】时，不同次运行情况下的结果

运行次数序号	输出的最优解	输出的运行时间/s	最优解的倒数（适应度）
1	1134.76	3.816	0.000881244
2	1275.45	3.787	0.000784037
3	1228.09	3.803	0.000814273
4	1236.74	3.801	0.000808577
5	1283.96	3.753	0.00077884
平均结果	1231.8	3.792	0.000813394

表3.c. 当变异策略采用【原始变异策略】、个体选择概率分配采用【锦标赛选择】时，不同次运行情况下的结果

运行次数序号	输出的最优解	输出的运行时间/s	最优解的倒数（适应度）
1	2791.07	3.454	0.000358286
2	2614.29	3.789	0.000382513
3	2670.1	3.721	0.000374518
4	2578.46	3.732	0.000387828
5	2526.76	3.698	0.000395764
平均结果	2636.14	3.679	0.000379782

表3.d. 当变异策略采用【原始变异策略】、个体选择概率分配采用【原始选择策略】时，不同次运行情况下的结果

运行次数序号	输出的最优解	输出的运行时间/s	最优解的倒数（适应度）
1	921.73	3.322	0.001084916
2	915.61	3.401	0.001092168
3	913.49	3.32	0.001094703
4	908.81	3.366	0.00110034
5	906.35	3.389	0.001103327
平均结果	913.20	3.360	0.001095091

四、实验问答

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

本实验使用的GA算法同PPT的流程，因此本实验解决TSP的流程图如下图所示。其中，选择策略、变异策略、交叉策略均为实验1和实验2所探究的策略，采用PPT中使用的三类简单策略。同时，粉色模块均为只执行一次的输入或输出模块，蓝色模块均为主循环内执行多次的模块，红色模块为主循环内判断多次的模块。

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

GA算法的性能主要从问题规模与搜索空间、收敛速度、选择策略、交叉策略、变异策略等方面进行分析。针对上述影响因子，算法性能分析如下表所示。

影响因子	性能分析
问题规模与搜索空间	随着TSP问题规模（即城市数量）的增加，搜索空间呈指数增长。这导致寻找全局最优解的难度增加。对于较小规模的TSP（例如20个城市或更少），GA有可能找到接近甚至是全局最优解。对于较大规模的TSP（例如100个城市或更多），GA更多地是为了找到一个可接受的近似解，而非全局最优。
收敛速度	GA的收敛速度是由其选择、交叉和变异操作共同决定的。不当的参数设置可能导致算法过早收敛到局部最优或过慢收敛。
选择策略	选择策略如轮盘赌选择、锦标赛选择等，决定了如何从当前种群中选出个体进行交叉和变异。选择策略应确保高适应度的个体有更高的被选中几率，同时也要维持种群的多样性。
交叉策略	TSP需要特定的交叉策略，例如有序交叉、部分映射交叉等，常规的交叉策略可能导致非法路径。正确的交叉策略有助于结合父代的优良特性。
变异策略	变异策略是为了防止算法陷入局部最优而设计的。在TSP中，常见的变异策略有两点交换、逆序等。高的变异率可能导致算法行为类似于随机搜索，而低的变异率可能导致过早收敛。
算法的参数调整	GA的表现在很大程度上取决于其参数，如种群大小、交叉概率、变异概率等。不同规模的TSP可能需要不同的参数设置。
计算时间和资源	对于大规模的TSP，GA需要较长的运行时间和计算资源来获得好的解，尤其当种群大小增大或迭代次数增多时。

综上所述，GA算法的性能取决于种群规模的大小、选择策略、交叉策略、变异策略等因素。在算法消耗的时间层面上，种群规模越小、算子策略越简单、交叉概率越小、变异概率越小，则消耗的时间越短，但不能保证结果取到全局最优解。如果想得到合适的局部最优解，用户需要在上述参数上进行平衡调优，以得到在可接受时间范围内的最优距离解。

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

针对种群规模、交叉概率和变异概率，本实验尝试讨论其优势与劣势并得出结论，最终结果如下表所示。

因子	优势	劣势	结论
种群规模	增大种群规模可以提高种群的多样性，有助于算法更好地探索解空间，从而增加找到更好解的可能性。	种群规模过大可能导致计算成本显著增加，因为每代都需要评估和处理更多的个体。如果种群规模过大，但选择策略不合适，可能会导致算法收敛得过慢。	合适的种群规模取决于问题的具体情况和计算资源。它应该足够大以确保种群的多样性，但不应太大以避免不必要的计算开销。
交叉概率	较高的交叉概率确保了种群中的个体有足够的机会进行重组，从而有机会产生质量更高的后代。	过高的交叉概率可能导致种群的多样性减少。好的解可能会迅速主导种群，从而导致过早收敛。	最终的交叉概率应该根据问题情况进行调整。变异概率通常设置得较高，范围是0.7-0.9。
变异概率	变异为GA算法引入了随机性，有助于保持种群的多样性，确保了算法不会过早地收敛到局部最优解，并有可能探索到未被访问的解空间区域。	过高的变异概率会导致算法表现得更像随机搜索，可能导致好的解被破坏。	最终的变异概率应该根据问题情况进行调整。变异概率通常设置得较低，范围是0.01-0.1。

五、遇到的问题及其解决方案

问题1：

运行程序时出现以下报错内容。

Traceb ack (most re cent call las t):

File “c:Users86158Des k top p lo t.py“, line 208, in <module&g t;

temp value = fitness(origin_matrix[gen])

File “c:Users86158Des k top p lot.py“, line 77, in fitness

my ret += distance(x_data[id2], y_data[id2], x_data[id1], y_data[id2])

TypeError: list indices must be integers or sli ces, not numpy.float64

解决1：

这个错误通常发生在尝试使用浮点数作为索引来访问列表（或其他可索引的数据结构）的情况下。Pyth on不允许使用浮点数作为索引，索引必须是整数或切片。

问题2：

运行程序时出现以下报错内容。

Traceback (most recent call last):

File “c:Users86158Desk topplot.py“, line 218, in <module>

origin_matrix = cross(origin_matrix)

File “c:Users86158Desk topplot.py“, line 112, in cross

point2 = random.rand int(point1+1,num-2)

File “C:Users86158AppDataLocalProgramsPyth onPyth on39lib random.py”, line 338, in rand int

return self.rand range(a, b+1)

File “C:Users86158AppDataLocalProgramsPyth onPyth on39librandom.py”, line 316, in randrange

raise ValueError(“empty range for randrange() (%d, %d, %d)” % (istart, istop, width))

ValueError: empty range for randrange() (29, 29, 0)

解决2：

这个错误发生在 random.randint() 函数中，它要求第一个参数小于或等于第二个参数，但出现了一个空的范围。

问题3：

在某次调试过程中出现死循环，且因为循环卡死找不到报错信息。

解决3：

通过在【6：主函数】的主循环处增加打印信息，print每一个算子操作的执行，然后发现死循环出现在某次generation的cross处（即交叉操作部分）。检查交叉操作部分的代码，发现for循环出现问题，右侧的这个边界设置错了，原来是num-1，这样的话如果要抽到int(num-1)那就会报错，因为这个for循环是左闭右开的。最后改成for i in range(point2+1,num)后解决问题。

问题4：

一开始编写的交叉操作代码中，每个epoc h只是交叉了2组，但是应该是每个个体都有0.95的交叉概率，导致很快就陷入局部最优解。

解决4：

先利用list(range(0,size))生成染色体的分组序列，然后通过random.sh uffle(rank)进行随机分组工作，选择相邻的两个染色体作为彼此的交叉对象。之后对每个组个体进行概率判断，如果大于轮盘概率则不交叉，否则交叉。

问题5：

一开始编写的变异操作代码中，每个epoc h只是对一个染色体进行变异判断，但是应该是每个个体都有0.05的变异概率，导致很快就陷入局部最优解。

解决5：

使用while循环遍历 matrix 里面的染色体，对每个染色体是否变异进行随机概率判断。

六、附件

1：城市规模=30时，实验1处的路线结果示例图（每次运行后均会生成，此处仅为图例展示）

2：实验1和实验2的源程序代码（参数需要进行人工的手动调整，如迭代次数、种群大小、变异概率、交叉概率、城市规模等）

import matplotlib.pyplot as plt

import numpy as np

import random

import time

# via https://www.math.uwaterloo.ca/tsp/world/countries.html#DJ

# the first 100 sites from China, fixed points

data = [

[18200,109550],[18200,109583.3333],[18206.3889,109581.9444],[18207.5,109477.7778],[18215.8333,109700.5556],

[18216.6667,109700],[18220.5556,109510.2778],[18223.8889,109552.2222],[18229.7222,109528.3333],[18233.3333,109533.3333],

[18233.3333,109616.6667],[18233.8889,109703.8889],[18236.6667,109625],[18243.0556,109505],[18243.6111,109690.2778],

[18245.2778,109373.8889],[18246.6667,109559.7222],[18250,109516.6667],[18250,109583.3333],[18257.7778,109689.4444],

[18260.5556,109712.7778],[18263.0556,109580.8333],[18263.0556,109679.7222],[18265,109638.6111],[18266.6667,109483.3333],

[18266.6667,109566.6667],[18266.6667,109666.6667],[18271.3889,109705.8333],[18278.3333,109730.2778],[18279.4444,109675.2778],

[18281.1111,109480.8333],[18281.3889,109684.1667],[18283.3333,109400],[18283.8889,109569.7222],[18283.8889,109705.5556],

[18284.4444,109661.6667],[18296.9444,109611.6667],[18302.2222,109210],[18303.8889,109432.2222],[18304.1667,109528.3333],

[18304.4444,109335.2778],[18304.4444,109391.1111],[18307.2222,109144.1667],[18314.7222,109269.7222],[18315.2778,109626.6667],

[18316.6667,109166.6667],[18316.6667,109266.6667],[18317.2222,109331.6667],[18319.1667,109442.2222],[18319.7222,109705],

[18320.2778,109173.6111],[18321.6667,109551.1111],[18325,109673.3333],[18325.8333,109528.3333],[18327.2222,109256.3889],

[18327.7778,109247.5],[18332.5,109490.2778],[18333.3333,109450],[18335.2778,109323.0556],[18336.1111,109731.3889],

[18344.7222,109452.2222],[18347.2222,109638.8889],[18347.7778,109203.3333],[18347.7778,109587.7778],[18349.1667,109440.8333],

[18351.3889,109725.8333],[18351.3889,109726.6667],[18355.5556,109627.2222],[18356.1111,109126.6667],[18358.6111,109126.3889],

[18359.1667,108988.6111],[18362.7778,109602.2222],[18370.5556,109099.7222],[18370.8333,109005.5556],[18371.6667,109508.8889],

[18372.7778,109163.6111],[18374.7222,109244.4444],[18375.5556,109162.2222],[18376.1111,109035.2778],[18378.0556,109603.3333],

[18378.0556,109742.5],[18378.6111,109641.6667],[18388.3333,109824.7222],[18392.2222,109725],[18393.6111,109430.8333],

[18397.7778,109987.5],[18398.6111,109496.3889],[18400,109730.2778],[18400,109750],[18400.8333,109202.7778],

[18402.2222,109283.0556],[18403.6111,109020.8333],[18403.6111,109868.8889],[18404.7222,110018.6111],[18406.6667,109616.6667],

[18408.6111,109758.3333],[18409.4444,109676.3889],[18414.1667,110070.2778],[18415.8333,108933.8889],[18415.8333,109725]

]

# split x pos and y pos

x_data = [point[0] for point in data]

y_data = [point[1] for point in data]

# 用户输入城市数量，然后调用初始的China TSP数据

num = int(input(“please input your number of cities, choose from 30, 50, 100:”))

epoch = 500 # 迭代次数

size = 100 # 种群大小(40-100)

pcross = 0.95 # 交叉概率

pmute = 0.05 # 变异概率

# 【0：开始计时】

start_time = time.time()

# 【1：编码和解码】

def distance(x1, y1, x2, y2):

return ((x1–x2)**2 + (y1–y2)**2)**0.5

# 群体矩阵初始化

origin_matrix = np.zeros((int(size),num+1))

for i in range(size):

# 生成随机排序的个体

single = list(range(0,num))

random.shuffle(single)

# 当前个体的距离计算

ret = 0

for j in range(1,num):

id1 = single[j]

id2 = single[j–1]

ret += distance(x_data[id2], y_data[id2], x_data[id1], y_data[id1])

# 回到起点

id1 = single[0]

id2 = single[-1]

ret += distance(x_data[id2], y_data[id2], x_data[id1], y_data[id1])

# 将距离加在list末尾，增加矩阵行

single.app end(ret)

origin_matrix[i] = single

# test

print(“初始矩阵：“)

print(origin_matrix)

# 【2：适应度函数】

def fitness(single):

myret = 0

for j in range(1,len(single)-1):

id1 = single[j]

id2 = single[j–1]

id1 = int(id1)

id2 = int(id2)

myret += distance(x_data[id2], y_data[id2], x_data[id1], y_data[id1])

# 回到起点

id1 = single[0]

id2 = single[-2]

id1 = int(id1)

id2 = int(id2)

myret += distance(x_data[id2], y_data[id2], x_data[id1], y_data[id1])

return myret

# 【3：选择操作】

def sort out(matrix):

sorted_matrix = np.array(sorted(matrix,key=lambda x: x[-1]))

return sorted_matrix

def select(c,matrix):

# 按照适应度值排序（从小到大）

sorted_matrix = sort out(matrix)

# 选择最适合的c组数据，替换最不适合的c组数据

for i in range(c):

sorted_matrix[size–i–1]=so rted_matrix[i]

return so rted_matrix

# 【4：交叉操作】

# 我为什么每个epoch只是交叉了2组！！！！！！！！！！

# 应该是每个个体都有0.95的交叉概率

# cross有问题，会陷入死循环= =

def cross(matrix):

# 给matrix的个体俩俩分组，群体一共size个个体

rank = list(range(0,size))

random.shuffle(rank)

number1 = 0

number2 = 1

new_matrix = matrix.copy()

# 当第二个个体一直在群体内时

while number2 < size:

# 给每组个体0.95的概率交叉

chance = random.random()

# 概率之外，不交叉(if)

if chance >= pc ross:

number1 += 2

number2 += 2

continue

# 概率之内，交叉(else)

# 随机定位交叉点

ran_nums = random.sample(range(1,num–1),2)

point1 = min(ran_nums[0],ran_nums[1])

point2 = max(ran_nums[0],ran_nums[1])

idd1 = rank[number1]

idd2 = rank[number2]

single1 = matrix[idd1]

single2 = matrix[idd2]

# 交叉过程：point1左侧

for i in range(0,point1):

# 找到single1[i]所对应的字符

t = single2[i]

while 1:

flag = 0

for j in range(point1,point2+1):

# 如果t在single1的交叉区内，则继续找到交叉区所对应的single2内的值

if single1[j] == t:

flag = 1

t = single2[j]

break

if flag == 0:

break

single1[i] = t

# 交叉过程：point2右侧

“””

【谁也想不到死循环的原因竟然是？！】

右侧的这个边界设置错了，原来是num-1

这样的话如果要抽到int(num-1)那就会报错

因为这个for循环是左闭右开的

“””

for i in range(point2+1,num):

# 找到single1[i]所对应的字符

t = single2[i]

while 1:

flag = 0

for j in range(point1,point2+1):

# 如果t在single1的交叉区内，则继续找到交叉区所对应的

if single1[j] == t:

flag = 1

t = single2[j]

break

if flag == 0:

break

single1[i] = t

# 更新交叉后的fitness值

value1 = fitness(single1)

value2 = fitness(single2)

single1[-1] = value1

single2[-1] = value2

# 替换原来的matrix[i]

new_matrix[idd1] = single1.copy()

new_matrix[idd2] = single2.copy()

# 继续下一个number

number1 += 2

number2 += 2

# 返回新的矩阵

return new_matrix

# 【5：变异操作】

# 理论上应该也是每个个体有0.05的变异概率？

def mutation(matrix):

choose = int(0)

new_matrix = matrix.copy()

# 循环判断每一个个体

while choose < len(matrix):

# 生成当前个体的变异概率

check = random.random()

# 概率轮盘超出(if)

if check > pmute:

choose += 1

continue

# 概率轮盘不超出(else)

temp = matrix[choose].copy()

# 保存父代

father = temp.copy()

# 倒置变异法

p1 = random.randint(0,num–1)

while 1:

p2 = random.randint(0,num–1)

if p2 != p1:

break

# 找到p1和p2的最大值

pmin = min(p1,p2)

pmax = max(p1,p2)

# 双指针交换，求新temp

while pmin < pmax:

temp[pmin], temp[pmax] = temp[pmax], temp[pmin]

pmin += 1

pmax -= 1

# 更新temp的fitness

value = fitness(temp)

temp[-1] = value

# 如果变异后的fitness更好，则替换

if val ue < father[-1]:

new_matrix[choose] = temp

else:

new_matrix[choose] = father

# 继续下一个个体的变异判断

choose += 1

# 最后返回新的矩阵

return new_matrix

# 【6：主函数】

# 选择算子参数

ccc = int(0.05*size)

# 主循环 range内使用epoch，目前为测试

for generation in range(epoch):

# 更新适应度值 def fitness(single)

for gen in range(len(origin_matrix)):

tempval ue = fitness(origin_matrix[gen])

origin_matrix[gen][-1] = tempvalue

# print(“fitness”)

# 选择 def select(c,matrix)

origin_matrix = select(ccc,origin_matrix)

# print(“select“)

# 交叉 def cross(matrix)

origin_matrix = cross(origin_matrix)

# print(“cross”)

# 变异 def mutation(matrix)

origin_matrix = mutation(origin_matrix)

# print(“mutation“)

# 排序得到的种群

origin_matrix = so rt out(origin_matrix)

best = origin_matrix[0]

print(f“第{generation}次执行的最佳方案是：{best[-1]}“)

# 【7：停止计时】

end_time = time.time()

execution_time = (end_time – start_time)

print(f“执行时间：{execution_time}s”)

# 最后的计算结果展示

print(“最终矩阵：“)

print(origin_matrix)

print(“最优个体：“)

print(best)

# 【8：画图】

# 按照最优路线的顺序，更新x坐标集合和y坐标集合

# 没有画终点和起点的连线，为了方便用户观看位置

new_x = []

new_y = []

for cnt in range(len(best)-1):

count = int(best[cnt])

new_x.append(x_data[count])

new_y.append(y_data[count])

# 定义点和线的外形特征

plt.scatter(new_x, new_y, s = 2)

plt.plot(new_x, new_y, line style=‘-‘, color=‘red‘, line width=0.5)

# 定义图的注释

plt.xlabel(‘x-position‘)

plt.ylabel(‘y-position‘)

plt.title(‘the TSP map of points‘)

# 展示图片

plt.show()

2：实验3的源程序代码（增加的变异策略和选择策略）

增加的选择策略：锦标赛选择方法

def select2(c,matrix):

new_matrix = matrix.copy()

cnt = int(0)

# 设置hash，判断是否个体是否被选择过

check = []

# 初始化hash，全为0

for i in range(size):

check.append(0)

while 1:

# 达到预先设置的个体数量

if cnt == c:

break

# else,从群体里面随机选择两个个体（随机竞争方法）

while 1:

id11 = random.randint(0,size–1)

if check[id11] == 0:

check[id11] = 1

break

while 1:

id22 = random.randint(0,size–1)

if check[id22] == 0:

check[id22] = 1

break

# 获取对应编号的个体

compete1 = matrix[id11]

compete2 = matrix[id22]

# 比较两个个体的适应度值，选择距离小的个体，覆盖掉距离大的个体

flag = 2

if compete1[-1] > compete2[-1]:

flag = 1

# 把compete2替换为compete1

if flag == 1:

new_matrix[id22] = matrix[id11]

# 把compete1替换为compete2

else:

new_matrix[id11] = matrix[id22]

# 操作计数+1

cnt += 1

# 返回最新矩阵群体

return new_matrix

增加的变异策略：相邻两点互换方法

def mutation2(matrix):

choose = int(0)

new_matrix = matrix.copy()

# 循环判断每一个个体

while choose < len(matrix):

# 生成当前个体的变异概率

check = random.random()

# 概率轮盘超出(if)

if check > pmute:

choose += 1

continue

# 概率轮盘不超出(else)

# mp1为第一个城市位置点，mp2为第二个城市位置点，比如个体里面排序第3的城市和第5的城市

mp1 = random.randint(0,num–1)

mp2 = random.randint(0,num–1)

process = matrix[choose]

# 交换两个城市，比如第3的城市和第5的城市互换

process[mp1],process[mp2] = process[mp2],process[mp1]

# 计算新的fitnes

new_value = fitness(process)

# 判断是否变异更加优秀了

if new_value > process[-1]:

process[-1] = new_value

# 更换newmatrix的个体

new_matrix[choose] = process

# else:不更换个体

# 继续下一个个体的变异判断

choose += 1

# 最后返回新的矩阵

return new_matrix

原文地址:https://blog.csdn.net/m0_65787507/article/details/134701332

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。

如若转载，请注明出处：http://www.7code.cn/show_10319.html

如若内容造成侵权/违法违规/事实不符，请联系代码007邮箱：suwngjj01@126.com进行投诉反馈，一经查实，立即删除！

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。

tsp 实验遗传算法

相关文章

发表回复 取消回复

发表回复取消回复