遗传算法实验.docx

实验四遗传算法实验一、 实验目的:熟悉和掌握遗传算法的原理、流程和编码策略,并利用遗传求解函数优化问题,理解求解TSP问题的流程并测试主要参数对结果的影响。二、 实验原理:旅行商问题,即TSP问题(TravelingSalesmanProblem)是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路经的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。 TSP问题是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。因此,任何能使该问题的求解得以简化的方法,都将受到高度的评价和关注。遗传算法的基本思想正是基于模仿生物界遗传学的遗传过程。它把问题的参数用基因代表,把问题的解用染色体代表(在计算机里用二进制码表示),从而得到一个由具有不同染色体的个体组成的群体。这个群体在问题特定的环境里生存竞争,适者有最好的机会生存和产生后代。后代随机化地继承了父代的最好特征,并也在生存环境的控制支配下继续这一过程。群体的染色体都将逐渐适应环境,不断进化,最后收敛到一族最适应环境的类似个体,即得到问题最优的解。要求利用遗传算法求解TSP问题的最短路径。三、 实验内容及要求1、 参考实验系统给出的遗传算法核心代码,用遗传算法求解TSP的优化问题,分析遗传算法求解不同规模TSP问题的算法性能。2、 对于同一个TSP问题,分析种群规模、交叉概率和变异概率对算法结果的影响。3、增加1种变异策略和1种个体选择概率分配策略,比较求解同一TSP问题时不同变异策略及不同个体选择分配策略对算法结果的影响。4、 上交源代码。四、 实验结果(根据实验报告要求)1、画出遗传算法求解TSP问题的流程图2、分析遗传算法求解不同规模的TSP问题的算法性能。遗传算法执行方式说明:适应度值计算方法:当前路线的路径长度个体选择概率分配方法:适应度比例方法选择个体方法:***赌选择交叉类型:PM)交叉变异类型:两点互换变异实验模拟结果:城币个数历次最好适应度历次最差适应度苍厅时间*^&,756927245727,^34T—城市个数运行时间/ms由图1和图2可知,遗传算法执行时间随着TSP问题规模的增大而增大,并且大致为线性增长。3、对于同一个TSP问题,分析种群规模、交叉概率和变异概率对算法结果的影响。(1)种群规模对算法结果的影响城市数:15实验次数:10最大迭代步数:100交叉概率:::历嵐最好运应匱历枚履差适应廈倉优建超ixWf<-fl-5-7-3^-4-l(Fl2-13^9-11-14S-)-1-0-6-M-5-2-10-11-12-7-3-13-1412?-353-7-l-C-ll-9-i2-0-^-4-10313-1