遗传算法求解TSP问题
实验内容对于同一个TSP问题，分析种群规模、交叉概率和变异概率对算法结果的影响。增加1种变异策略和1种个体选择概率分配策略，比较求解同一TSP问题时不同变异策略及不同个体选择分配策略对算法结果的影响。
分析遗传算法求解不同规模TSP问题的算法性能城市数量越大或者群体规模越大或者最大迭代数越大，运行等待结果的时间越久TSP规模越大，用时越长，但是当规模大到一定程度时，遗传算法的求解性能优于广度/宽度优先搜索算法，用时比一般的搜索算法少很多，对自身来说规模越大结果越精确。
求解流程图对同一个TSP问题，分析种群规模、交叉概率和变异概率对算法结果的影响。（1）种群规模对结果的影响：规模越大算法结果越精确，适应度越好，但是运行时间越久。设置城市数量10变异概率0.15交叉概率0.95最大迭代数500种群规模设置为50时：2组得到了最优解（2）交叉概率对结果的影响：交叉概率过低将得不到最优解，交叉概率越高平均适应度越好。设置城市数量10变异概率0.15最大迭代数500种群规模500交叉概率设置为0.99时：得到17组最优解（3）变异概率对结果的影响：变异概率过高或者过低都影响得到最优解设置城市数量10种群规模500交叉概率0.95最大迭代数500变异概率0.01时：12组得到了最优解
比较求解同一TSP问题时不同变异策略及不同个体选择分配策略对算法结果的影响。
变异策略为交换城市位置：变异策略为随机选取两个城市，他们之间的距离加倍：不同变异策略与不同个体选择策略对算法执行结果得到最优解的情况有所不同，但是程序实行得到结果的等待时间相差不多。
C++源代码遇到的问题和解决方法课程讲述的遗传算法中并没有设计交叉概率问题，默认为必然发生交叉。本次实验中需要对交叉概率对实验结果的影响进行讨论分析，于是自己修改了程序，加入了交叉概率参数与函数修改，使得可以通过手动调整交叉概率参数来分析不同交叉概率参数对实验结果的影响。
实验要求使用不同变异策略来测试，通过自己想象和合理分析之后设计出了第二种变异策略。
变异概率调整，对结果影响变化不大时，是受了种群数目和迭代次数的限制，总共发生的变异次数太少，但是设置迭代次数与规模增大时，会导致运行过于缓慢，等待结果时间太久。解决方案是在work函数中的循环里，当迭代次数大于N时，增大变异概率，不仅获取变异较少的情况解也获取了变异量较大的情况解。
心得体会这次遗传算法求解TSP问题的实验，让我体会了参数对实验结果的影响。本次实验针对种群数目，迭代次数，变异概率，交叉概率等参数进行修改设定与测试来获取最优解情况分析参数对结果的影响。在设置新函数新参数时，灵活应用程序设计结构，对遗传算法和C++语言都有了进一步的理解。以后求解规模较大的TSP问题时，如果使用搜索与松弛策略用时太久，时间复杂度过高。可以考虑使用遗传算法求解，但要保证结果的精确，因为遗传算法在规模较小时可能得到的结果不是最优解。
遗传算法实验报告
遗传算法实验报告时间：2023.7.19一、实验题目
求解线性约束优化问题的遗传算法
将物品由7个起运站运到7个目的地；已知由i站运到j地的单位运费是，表示i站的供应量，表示j地的需求量，表示从i站到j地的运量。(i,j=1,2,…,7）
约束条件：
目标函数为：
罚函数为：
其中，k=1，P=1/14，f为第t代群体的平均适应度，T为最大运行代数，为约束的违反度。
费用参数表如下：
使用策略：通用遗传算法模型、精英保存策略、轮盘赌法策略选择个体交叉和变异，对上述例子进行了算法的测试，种群个体大小为40，迭代10000次，得到比较稳定的结果。每次运行的结果是得到一个相对稳定的、代价小的目标值。实验结果：在当前条件下，在初始种群的40个个体，经过10000次迭代得到最低运费为1279，并且程序多次运行结果都稳定在1300左右。
二、实验环境
操作系统：MicrosoftWindowsXPProfessional
软件：MicrosoftVisualC++6.0
三、实验设计原理
1.实验内容分析
本实验采用遗传算法求解带约束条件的函数优化问题。
2.遗传算法的思想
生物的进化是以集团为主体的。与此相对应，遗传算法的运算对象是由M个个体所组成的集合，称为群体。与生物一代一代的自然进化过程相类似，遗传算法的运算过程也是一个反复迭代过程，第t代群体极为P（t），进过一代遗传和进化后，得到第t+1代群体，他们也是由多个个体组成的集合，记做P（t+1）。这个群体不断地经过遗传和进化操作，并且每次都按照有优胜劣汰的规则将适应度较高的个体更多地遗传到下一代，这样最终在群体中将会得到一个优良的个体X，它所对应的表现性X将达到或接近于问题的最优解。
3.算法实现步骤
①产生初始种群：产生初始种群的方法通常有两种：一种是完全随机的方法产生的，适合于对问题的解无任何先验知识的情况；另一种是将某些先验知识转变为必须满足的一组要求，然后在满足这些要求的解中再随机地选择样本，t=0,随机产生n个个体形成一个初始群体P（t），该群体代表优化问题的一些可能解的集合；
②适应度评价函数：按编码规则，将群体P（t）中的每一个个体的基因码所对应的自变量取值代入目标函数，算出其函数值，i=1,2,…,n,越大，表示该个体有较高的适应度，更适合于f所定义的生存环境，适应度为群体进化提供了依据；
③选择：按一定概率从群体P（t）中选出m个个体，作为双亲用于繁殖后代，产生新的个体加入下一个群体P（t+1）中；
④交叉（重组）：对于选中的用于繁殖的每一个个体，选择一种交叉方法，产生新的个体；
⑤变异：以一定的概率从群体P（t+1）中随机选择若干个个体，对于选中的个体，进行变异；
⑥对产生新一代的群体返回步骤③再进行评价，交叉、变异如此循环往复，使群体中个体的适应度和平均适应度不断提高，直至最优个体的适应度达到某一限值或最优个体的适应度和群体的平均适应度不再提高，则迭代过程收敛，算法结束。
4.算法流程图
5.实验调试与结果分析（问题的发现、分析、解决方案与创新）
1)程序结果如下图：
2)收敛效果如下图：
四、实验小结及附录
通过本次实验，我了解了演化计算的基本思想，并能够运用演化计算的思想解决函数最优值问题，能够编写相应的程序。实验过程中遇到很多问题，但是进过认真分析，最终能解决问题。
更多相关推荐：遗传算法实验报告遗传算法实验报告姓名：**学号：**一、实验目的：熟悉和掌握遗传算法的运行机制和求解的基本方法。遗传算法是一种基于空间搜索的算法，它通过自然选择、遗传、变异等操作以及达尔文的适者生存的理论，模拟自然进化过程来寻…
遗传算法实验报告桂林理工大学实验报告班级计算机111班学号同组实验者实验名称日期20xx年5月30日一实验目的用遗传算法求fxxsin10pix10的最大值其中x区间为12二实验内容初始化编码实现目标函数的计算将pop每行转化...
遗传算法实验报告人工智能实验报告遗传算法实验报告一问题描述对遗传算法的选择操作设种群规模为4个体用二进制编码适应度函数x的取值区间为030若遗传操作规定如下1选择概率为100选择算法为轮盘赌算法2交叉概率为1交叉算法为单点交叉...
遗传算法实验报告实验报告实验名称遗传算法实验实验目的熟悉和掌握遗传算法的运行机制和求解的基本方法实验原理通过编码设置种群设置适应度函数遗传操作解码产生需要的解fxxsinx1x02求解fx的最大值和最小值实验内容1确定数据结构...
遗传算法实验报告遗传算法实验报告专业自动化姓名张俊峰学号13351067摘要遗传算法是基于达尔文进化理论发展起来的一种应用广泛高效的随机搜索与优化方法本实验利用遗传算法来实现求函数最大值的优化问题其中的步骤包括初始化群体个体评...
遗传算法实验报告一题目12maxfxxxX最大值解空间为非负整数集求解优化问题X012311matlab源程序及说明question1mclearfigure1plot0312画出函数曲线定义遗传算法参数NIND4Number...
TSP问题的遗传算法实验报告TSP问题的遗传算法实验报告一实验题目TSP问题的遗传算法实现二实验目的1熟悉和掌握遗传算法的基本概念和基本思想2加深对遗传算法的理解理解和掌握遗传算法的各个操作算子3理解和掌握利用遗传算法进行问题求解的基本技...
遗传算法实验报告1定义种群和个体定义种群为S种群数N50其中xy是染色体中的两个基因组2算法设计1确定编码设计由于原函数的变量取值包含负数不方便进行编码所以将原函数的变量进行转换从1010转换成020相应的函数也要进行变换根据...
实验报告：遗传算法在解决旅行商问题的应用实验报告用遗传算法解决旅行商问题的简单实现实验目的编写程序实现用遗传算法解决旅行商问题研究遗传算法的工作原理和收敛性质实验者问题描述TSP是一个具有广泛应用背景和重要理论价值的组合优化难题TSP问题可以简单的描...
遗传算法求解TSP问题实验报告一实验目的加深对逻辑程序运行机理的理解掌握MATLAB语言的特点熟悉其编程环境同时为后面的人工智能程序设计做好准备1熟悉MATLAB语言编程环境的使用2了解MATLAB语言中常量变量的表示方法3了解利用MATL...
遗传算法的实验报告遗传算法的仿真一实验目的1了解遗传算法的原理2学习Matlab遗传算法工具箱的使用3使用Matlab进行遗传算法的仿真二实验设备1计算机2Matlab软件三实验内容和步骤要求计算目标函数值函数fxxsin10x...
回溯算法实验报告本科学生综合性实验报告姓名刘春云学号0103918专业实验项目名称n皇后问题的回溯算法实验指导教师及职称赵晓平教授开课学期20xx至20xx学年三学期上课时间20xx年2月20日学生实验报告3一问题描述n后问题...
遗传算法实验报告（40篇）