佛山免费发布信息的网站,酒店网络营销策略论文,网站建设基本情况,机械设备东莞网站建设实验2 遗传算法实验 一、实验目的
熟悉和掌握遗传算法的原理、流程和编码策略#xff0c;理解求解TSP问题的流程并测试主要参数对结果的影响#xff0c;掌握遗传算法的基本实现方法。 二、实验原理
旅行商问题#xff0c;即TSP问题#xff08;Traveling Salesman Proble…实验2 遗传算法实验 一、实验目的
熟悉和掌握遗传算法的原理、流程和编码策略理解求解TSP问题的流程并测试主要参数对结果的影响掌握遗传算法的基本实现方法。 二、实验原理
旅行商问题即TSP问题Traveling 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个城市设置不同的种群规模例如4070100、交叉概率00.50.851和变异概率00.150.51把结果填入表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可能需要不同的参数设置。 计算时间和资源 对于大规模的TSPGA需要较长的运行时间和计算资源来获得好的解尤其当种群大小增大或迭代次数增多时。 综上所述GA算法的性能取决于种群规模的大小、选择策略、交叉策略、变异策略等因素。在算法消耗的时间层面上种群规模越小、算子策略越简单、交叉概率越小、变异概率越小则消耗的时间越短但不能保证结果取到全局最优解。如果想得到合适的局部最优解用户需要在上述参数上进行平衡调优以得到在可接受时间范围内的最优距离解。
3、对于同一个TSP问题分析种群规模、交叉概率和变异概率对算法结果的影响。
针对种群规模、交叉概率和变异概率本实验尝试讨论其优势与劣势并得出结论最终结果如下表所示。 因子 优势 劣势 结论 种群规模 增大种群规模可以提高种群的多样性有助于算法更好地探索解空间从而增加找到更好解的可能性。 种群规模过大可能导致计算成本显著增加因为每代都需要评估和处理更多的个体。如果种群规模过大但选择策略不合适可能会导致算法收敛得过慢。 合适的种群规模取决于问题的具体情况和计算资源。它应该足够大以确保种群的多样性但不应太大以避免不必要的计算开销。 交叉概率 较高的交叉概率确保了种群中的个体有足够的机会进行重组从而有机会产生质量更高的后代。 过高的交叉概率可能导致种群的多样性减少。好的解可能会迅速主导种群从而导致过早收敛。 最终的交叉概率应该根据问题情况进行调整。变异概率通常设置得较高范围是0.7-0.9。 变异概率 变异为GA算法引入了随机性有助于保持种群的多样性确保了算法不会过早地收敛到局部最优解并有可能探索到未被访问的解空间区域。 过高的变异概率会导致算法表现得更像随机搜索可能导致好的解被破坏。 最终的变异概率应该根据问题情况进行调整。变异概率通常设置得较低范围是0.01-0.1。 五、遇到的问题及其解决方案
问题1
运行程序时出现以下报错内容。 Traceback (most recent call last): File c:\Users\86158\Desktop\plot.py, line 208, in module tempvalue fitness(origin_matrix[gen]) File c:\Users\86158\Desktop\plot.py, line 77, in fitness myret distance(x_data[id2], y_data[id2], x_data[id1], y_data[id2]) TypeError: list indices must be integers or slices, not numpy.float64
解决1
这个错误通常发生在尝试使用浮点数作为索引来访问列表或其他可索引的数据结构的情况下。Python不允许使用浮点数作为索引索引必须是整数或切片。 问题2
运行程序时出现以下报错内容。 Traceback (most recent call last): File c:\Users\86158\Desktop\plot.py, line 218, in module origin_matrix cross(origin_matrix) File c:\Users\86158\Desktop\plot.py, line 112, in cross point2 random.randint(point11,num-2) File C:\Users\86158\AppData\Local\Programs\Python\Python39\lib\random.py, line 338, in randint return self.randrange(a, b1) File C:\Users\86158\AppData\Local\Programs\Python\Python39\lib\random.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(point21,num)后解决问题。 问题4 一开始编写的交叉操作代码中每个epoch只是交叉了2组但是应该是每个个体都有0.95的交叉概率导致很快就陷入局部最优解。
解决4
先利用list(range(0,size))生成染色体的分组序列然后通过random.shuffle(rank)进行随机分组工作选择相邻的两个染色体作为彼此的交叉对象。之后对每个组个体进行概率判断如果大于轮盘概率则不交叉否则交叉。 问题5
一开始编写的变异操作代码中每个epoch只是对一个染色体进行变异判断但是应该是每个个体都有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),num1)) 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.append(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 sortout(matrix): sorted_matrix np.array(sorted(matrix,keylambda x: x[-1])) return sorted_matrix def select(c,matrix): # 按照适应度值排序从小到大 sorted_matrix sortout(matrix) # 选择最适合的c组数据替换最不适合的c组数据 for i in range(c): sorted_matrix[size-i-1]sorted_matrix[i] return sorted_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 pcross: 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,point21): # 如果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(point21,num): # 找到single1[i]所对应的字符 t single2[i] while 1: flag 0 for j in range(point1,point21): # 如果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 value 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)): tempvalue 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 sortout(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, linestyle-, colorred, linewidth0.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
