原创《基于改进遗传算法求解旅行商问题》：此文是一篇遗传算法论文范文,为你的毕业论文写作提供有价值的参考。
【摘 要】论文提出了一种改进的遗传算法求解旅行商问题（TSP）.该算法结合TSP的特点,采用实数编码方式减少算法计算复杂度；等位交叉方式扩大算法的搜索空间,改善寻优能力； 赌选择策略加快算法的收敛速度.通过30个城市的benchmark实例进行仿真试验,试验结果表明,改进的遗传算法改善了全局搜索能力,具有较快的收敛速度和较高的收敛精度.
【Abstract】In this paper, an improved genetic algorithm for traveling salesman problem （TSP） is proposed.The algorithm combines the characteristics of TSP, using real number encoding to reduce the computational complexity of the algorithm, a cross way to expand the search space and improve searching ability, roulette selection strategy to accelerate the convergence of the algorithm.In this paper, it has simulated benchmark examples in thirty cities.The simulation results show that the improved genetic algorithm can improve the global search ability, and its convergence speed and the convergence precision is higher.
【关键词】旅行商问题；遗传算法；收敛速度
【Keywords】traveler problem；genetic algorithm；convergence precision
【中图分类号】TP18 【文献标志码】A 【文章编号】1673-1069（2017）03-0096-03
1 引言
旅行商问题（TSP）也称货郎担问题,它旨在寻求旅行商在遍历诸多城市一次最后回到起点城市的最短路径,是数学图论中的经典问题.在实际生活中,像物流路径优化、车间调度和网络路由选址等都可归结为TSP,因此,TSP的研究具有重要的理论意义和实际价值.
Karp[1]证明了TSP是一个NP难问题,传统的优化算法在求解TSP问题时往往会陷入局部最优,尤其随着城市数量的增加,计算量也急剧增加,致使很多算法瘫痪.因此智能优化算法强的搜索效率、快速的收敛速度在求解TSP中得到了广泛应用.Aziz[2]提出了广义的蚁群算法,算法中融合了局部和全局两种信息素更新机制,提高全局迅游能力.何湘竹[3]将混沌搜索机制融入基于教和学的优化算法求解TSP,通过benchmark实例仿真试验显示,新算法性能更优越.段艳明[4]将果蝇优化算法的连续空间对应到离散规划,利用了遗传算法的交叉、变异操作进行路径的寻优,加快局部搜索能力和收敛速度.
遗传算法是一种模拟生物进化过程的随机搜索优化方法,和其他的局部搜索算法相比,遗传算法具有更强的鲁棒性,隐形的并行搜索机制增强了算法寻优能力,但遗传算法也存在缺陷,例如： 种群常常会出现早熟收敛、易陷入局部最优的问题,使算法的搜索性能大大降低[5].针对这些问题,学者提出了许多解决方法,如参数控制、多种群的运用和交配限制[6-8]等.
2 求解TSP的改进遗传算法
鉴于目前遗传算法在优化领域的优越性能,论文以TSP为例,提出了改进的遗传算法.
2.1 实数编码
对包含n个城市的TSP问题,我们提出一种新的有效编码方法——实数编码.它是指整数1到的一个全排列所构成的实数序列a1,a2,等,an,其中a∈[1,n）之间的整数,编码中ai表示编号为的城市排在路径上的第ai个位置.
2.2 赌选择
赌选择法是遗传算法中常用的选择方式,首先计算每个个体的适应度值fi,i∈[1,ps）,ps为种群规模.这里fi的值越大,说明这个个体越优秀；其次,计算每个个体的选择概率pi等于fi/（∑fi）和累积概率Pi等于∑■■pi；最后,随机产生一个实数num∈[0,1],选取满足num2.3 等位交叉
交叉算子是遗传算法中关键的操作,它涉及种群的多样性和算法的搜索效率等,论文基于等位交叉来改变两个交叉个体的局部基因片段,使每個个体都能遗传到对方的基因.具体操作如图1所示.
■
图1 等位交叉具体操作图
2.4 改进的遗传算法
基于以上操作算子,求解 TSP的改进遗传算法步骤如下：
步骤1 初始化遗传算法种群个数ps、最大迭代次数inmax、交叉概率pc和变异概率pm等；
步骤2 根据各城市的坐标计算各个城市之间的距离,记作Cij,i,j∈[1,n],代表第i个城市到第j个城市的距离,初始生成ps个个体,即ps个城市路线；
步骤3 计算每条路线的距离Si,计算适应度值根据公式fi等于1/Si,计算选择概率pi等于fi/（∑fi）和累积概率Pi等于∑■■pi；
步骤4 根据选择概率和累积概率采用 赌选择法选择要交叉的两个个体；
步骤5 根据交叉概率判断是否交叉,交叉采用等位交叉法,产生两个等位基因互换的两个交叉个体；
步骤6 根据变异概率判断是否变异,选择变异基因位置,随机产生基因片段,替换要变异的基因片段,产生新个体；
遗传算法论文参考资料：
结论：基于改进遗传算法求解旅行商问题为关于本文可作为相关专业遗传算法论文写作研究的大学硕士与本科毕业论文人工智能遗传算法论文开题报告范文和职称论文参考文献资料。
