下载文档原格式
改进遗传算法解决TSP问题陈林;潘大志【摘要】针对基本遗传算法收敛速度慢，易早熟等问题，提出一种改进的遗传算法。
新算法利用贪婪思想产生初始种群来加快寻优速度，用贪婪思想来引导交叉操作，在交叉操作之前，把当前较差的一半种群替换成随机种群，最后用改进的变异算子和进化逆转操作进行寻优，利用新的遗传算法求解基本的旅行商问题。
仿真结果表明，改进的遗传算法具有全局搜索能力强、收敛速度快的特点，优化质量和寻优效率都较好。
%Aiming at the problem of slow convergence and easy premature convergence, an improved genetic algorithm is proposed. New algorithm uses greedy idea to generate the initial population for speeding up the searching speed and greedy idea to guide the crossover operation, before the crossover operation, selects the random population to replace the half of the poor population, finally with the help of the improved mutation operator and evolutionary reversal operation to realize optimization, constructs a new genetic algorithm for solving the traveling salesman problem. The simulation results show that the improved genetic algorithm has the characteristics of strong global search ability and fast convergence speed.【期刊名称】《智能计算机与应用》【年(卷),期】2016(006)005【总页数】4页(P17-19,23)【关键词】遗传算法;贪婪思想;进化逆转;旅行商问题【作者】陈林;潘大志【作者单位】西华师范大学数学与信息学院，四川南充637009;西华师范大学数学与信息学院，四川南充637009【正文语种】中文【中图分类】TP18遗传算法(GA)是一种进化算法，其基本原理是仿效生物界中的“物竞天择、适者生存”的演化法则。
遗传算法算子引言遗传算法是一种基于进化论理论的优化算法，常用于解决复杂的搜索和优化问题。
遗传算法使用模拟生物进化的方式，通过对种群的基因组进行操作来搜索最优解。
其中，算子是遗传算法中用于操作基因组的基本组成部分。
算子包括选择、交叉和变异等操作，它们的作用是模拟生物进化过程中的自然选择、基因重组和突变。
选择算子选择算子是遗传算法中最基本的操作之一，它决定了哪些个体能够生存和繁殖，从而影响种群的进化方向。
常用的选择算子包括轮盘赌选择、竞争选择和排名选择等。
轮盘赌选择轮盘赌选择是一种基于个体适应度的选择算子。
它的原理是将每个个体的适应度值按比例映射到一个区间上，然后通过随机选择一个点来确定被选中的个体。
适应度较高的个体被选中的概率较大，而适应度较低的个体被选中的概率较小。
轮盘赌选择的具体步骤如下： 1. 计算每个个体的适应度值； 2. 将每个个体的适应度值映射到一个区间上，得到一个适应度累积值； 3. 生成一个随机点，根据该随机点在适应度累积值上的位置确定被选中的个体。
轮盘赌选择的优点是简单且易于实现，但随着种群进化的进行，适应度较低的个体被选中的概率会逐渐降低，从而可能导致种群早熟收敛。
竞争选择竞争选择是一种基于竞争关系的选择算子。
它的原理是随机选取一组个体，然后从中选择适应度最高的个体作为被选中的个体。
竞争选择通常使用锦标赛选择和随机选择两种方法。
锦标赛选择的具体步骤如下： 1. 随机选取一组个体作为竞争对手； 2. 从竞争对手中选择适应度最高的个体作为被选中的个体。
竞争选择的优点是能够保留种群中适应度较高的个体，但容易导致种群中适应度较低的个体被淘汰，从而可能导致种群多样性的降低和早熟收敛的问题。
排名选择是一种基于个体排名的选择算子。
它的原理是将每个个体按照适应度从高到低进行排序，然后根据排名选择个体。
排名选择通常使用线性排名选择和指数排名选择两种方法。
线性排名选择的具体步骤如下： 1. 将种群中的个体按照适应度从高到低进行排序；2. 计算每个个体的选择概率，通常使用线性函数进行映射；3. 生成一个随机点，根据该随机点在选择概率累积值上的位置确定被选中的个体。
遗传算法的选择操作
遗传算法的选择操作是在进化过程中用于选择优秀个体的操作。
选择操作决定了哪些个体将被传递到下一代，并决定了进化过程中的多样性程度。
常见的遗传算法选择操作包括：
1. 轮盘赌选择（Roulette Wheel Selection）：按照适应度比例来选择个体，适应度高的个体被选中的概率较大。
该方法模拟了轮盘赌的选择方式。
2. 锦标赛选择（Tournament Selection）：随机选择一定数量的个体，然后从中选择适应度最高的个体作为父代个体。
该方法好处是可以保证一部分适应度较低的个体也有机会被选择。
3. 排序选择（Rank Selection）：根据个体的适应度值进行排序，然后按照排名来选择个体。
适应度较高的个体排名较靠前，被选中的概率较大。
4. 锦标赛选择（Tournament Selection）：随机选择一定数量的个体，然后从中选择适应度最高的个体作为父代个体。
该方法好处是可以保证一部分适应度较低的个体也有机会被选择。
5. 随机选择（Random Selection）：对个体进行随机选择，每个个体被选中的概率相等。
选择操作的目标是保持适应度高的个体，并且保持种群的多样性。
不同的选择操作对于种群的进化过程和效果都有影响，选择合适的选择操作能够提高算法的性能和效果。
TSP 问题及LINGO 求解技巧巡回旅行商问题(Traveling Salesman Problem ，TSP)，也称为货郎担问题。
最早可以追溯到1759年Euler 提出的骑士旅行问题。
1948年，由美国兰德公司推动，TSP 成为近代组合优化领域的一个典型难题。
它已经被证明属于NP 难题。
用图论描述TSP ，给出一个图(,)G V E =，每边e E ∈上有非负权值()w e ,寻找G 的Hamilton 圈C ，使得C 的总权()()()W C w e e E C =∑∈最小. 几十年来，出现了很多近似优化算法。
如近邻法、贪心算法、最近插入法、最远插入法、模拟退火算法以及遗传算法。
这里我们介绍利用LINGO 软件进行求解的方法。
问题1设有一个售货员从10个城市中的某一个城市出发，去其它9个城市推销产品。
10个城市相互距离如下表。
要求每个城市到达一次仅一次后，回到原出发城市。
问他应如何选择旅行路线，使总路程最短。
我们采用线性规划的方法求解设城市之间距离用矩阵d 来表示，ij d 表示城市i 与城市j 之间的距离。
设0--1矩阵X 用来表示经过的各城市之间的路线。
设01,ij i j x i j i j ⎧=⎨⎩若城市不到城市若城市到城市且在前考虑每个城市后只有一个城市，则：11,nij j j ix =≠=∑1,,i n =… 考虑每个城市前只有一个城市，则：11,nij i i jx =≠=∑1,,j n =…； 但仅以上约束条件不能避免在一次遍历中产生多于一个互不连通回路。
为此我们引入额外变量i u (1,,i n =…），附加以下充分约束条件：1,i j ij u u nx n -+≤-1i j n <≠≤；该约束的解释：如i 与j 不会构成回路，若构成回路，有：1ij x =，1ji x =，则：1i j u u -≤-，1j i u u -≤-，从而有：02≤-，导致矛盾。
贪婪算法的基本原理贪婪算法（Greedy Algorithm）是一种常见的算法设计思想，它在每一步选择中都采取当前状态下最优的选择，以期望达到全局最优解。
贪婪算法的基本原理可以概括为“局部最优选择，期望全局最优解”。
在每个步骤中做出局部最优选择是贪婪算法的关键特点。
贪婪算法通常适用于满足贪婪选择性质（Greedy Choice Property）和最优子结构（Optimal Substructure）的问题。
贪婪选择性质意味着通过做出局部最优选择，可以得到全局最优解。
最优子结构意味着一个问题的最优解可以通过一系列子问题的最优解来表示。
当一个问题具有最优子结构性质时，我们可以通过贪婪算法来求解问题。
1.定义问题的优化目标。
2.将问题分解为若干子问题，子问题必须满足最优子结构性质。
3.设计一个贪婪策略，通过局部最优选择来做出决策。
4.解决每个子问题，得到局部最优解。
5.将各个子问题的解合并，得到原问题的解。
不过，贪婪算法不一定能得到全局最优解，因为它只关注局部最优选择，并没有进行全局。
有时，贪婪算法会陷入局部最优解而无法达到全局最优解。
因此，在使用贪婪算法求解问题时，必须确保问题满足贪心选择性质和最优子结构性质。
贪婪算法在许多问题中都有广泛的应用。
以下是几个常见问题的例子：1.最小生成树问题：通过选择边的方式，连接图中的所有顶点，并使得选择的边权和最小。
2.背包问题：在给定的背包容量下，选择一些物品放入背包中，使得物品的总价值最大。
3.哈夫曼编码：通过贪心选择思想构建最优的可变长度编码，以实现数据的高效压缩。
4.集合覆盖问题：从一组集合中选择最少的集合，覆盖全集的元素。
总结起来，贪婪算法是一种简单有效的算法设计思想，它通过局部最优选择来逐步求解问题，并期望达到全局最优解。
贪婪算法适用于满足贪心选择性质和最优子结构性质的问题，但不保证一定能得到全局最优解。
在实际应用中，我们需要理解问题的特点和约束条件，并根据问题的性质选择适合的算法来解决问题。
求解TSP问题的几种算法比较侯淑静【摘要】The traveling salesman problem (TSP) is an important problem for the classical discrete optimization, which is very important to study the solving algorithm. After the introduction of the greedy algorithm, taboo search algorithm, simulated annealing algorithm, genetic algorithm, the author put forward the corresponding algorithm. Aiming at the four typical examples in the test base, we realized implementation of these algorithms with procedures, and the running time and the results of these algorithms are compared. The results show that the greedy algorithm can draw the solution in a short time, the taboo search algorithm and genetic algorithm have the same effect, and the results of simulated annealing algorithm is better than those of genetic algorithm.%旅行售货商问题(简称TSP )是离散优化的一个经典的重要问题，对求解算法的研究非常重要。
第 1 章贪婪算法虽然设计一个好的求解算法更像是一门艺术，而不像是技术，但仍然存在一些行之有效的能够用于解决许多问题的算法设计方法，你可以使用这些方法来设计算法，并观察这些算法是如何工作的。
一般情况下，为了获得较好的性能，必须对算法进行细致的调整。
但是在某些情况下，算法经过调整之后性能仍无法达到要求，这时就必须寻求另外的方法来求解该问题。
本章首先引入最优化的概念，然后介绍一种直观的问题求解方法：贪婪算法。
最后，应用该算法给出货箱装船问题、背包问题、拓扑排序问题、二分覆盖问题、最短路径问题、最小代价生成树等问题的求解方案。
1.1 最优化问题本章及后续章节中的许多例子都是最优化问题（ optimization problem），每个最优化问题都包含一组限制条件（ c o n s t r a i n t）和一个优化函数（ optimization function），符合限制条件的问题求解方案称为可行解（feasible solution），使优化函数取得最佳值的可行解称为最优解（optimal solution）。
例1-1 [ 渴婴问题] 有一个非常渴的、聪明的小婴儿，她可能得到的东西包括一杯水、一桶牛奶、多罐不同种类的果汁、许多不同的装在瓶子或罐子中的苏打水，即婴儿可得到n 种不同的饮料。
根据以前关于这n 种饮料的不同体验，此婴儿知道这其中某些饮料更合自己的胃口，因此，婴儿采取如下方法为每一种饮料赋予一个满意度值：饮用1盎司第i 种饮料，对它作出相对评价，将一个数值s i 作为满意度赋予第i 种饮料。
通常，这个婴儿都会尽量饮用具有最大满意度值的饮料来最大限度地满足她解渴的需要，但是不幸的是：具有最大满意度值的饮料有时并没有足够的量来满足此婴儿解渴的需要。
设a i是第i 种饮料的总量（以盎司为单位），而此婴儿需要t 盎司的饮料来解渴，那么，需要饮用n种不同的饮料各多少量才能满足婴儿解渴的需求呢？设各种饮料的满意度已知。
第27卷第4期2021年11月Vol.27No.4November 2021基于贪婪元胞遗传算法的工序排序优化问题*邓燕兰，熊菊霞，郑宏宇，姚光磊（广西民族大学数学与物理学院，广西南宁530006）摘要：工序排序优化问题是一类以最小化总成本为目标，工序受到优先关系约束的NP问题。
为了寻求此类问题的最优解，在元胞遗传算法的基础上提出了一种贪婪元胞遗传算法(GCGA)。
该算法首先使用拓扑排序算法生成初始方案的工序顺序；然后引入贪婪算法生成初始可行工序序列的加工资源；最后分别在交叉和变异后设置精英个体保留策略。
GCGA 算法能够使初始种群的工序顺序满足优先关系的约束，降低初始方案的总成本，保持迭代过程中加工方案的可行性，提高收敛速度和收敛精度。
为了验证算法的有效性，将算法应用于实际案例，与7种典型算法进行对比。
实验结果表明：该算法获得的解的平均质量优于已知对比算法。
关键词：工序排序优化问题；元胞遗传算法；拓扑排序算法；贪婪算法；精英个体保留策略中图分类号：TP301.6；TH162+.1文献标识码：A文章编号：1673-8462（2021）04-0079-080引言计算机辅助工艺设计(Computer Aided ProcessPlanning,CAPP)在计算机工艺规划等方面有重要的应用。
[1]CAPP 主要分为三步：第一，特征识别，即对零件的特征进行分类和识别；[2]第二，确定提取出来的特征的加工操作和加工资源；[3]第三，在设计和制造实践的条件约束下，确定加工成本最低的操作顺序及其对应的加工资源。
[4]工序排序优化问题属于第三步，在已知加工特征,及其每个特征的加工操作和候选加工资源的基础上，通过规划得到最优加工方案。
它以最小化总成本为目标；以确定满足优先关系约束的加工工序的顺序，以及每个加工工序使用的加工资源为主要任务。
工序排序优化问题的可行方案包括可行工序序列(Feasible Operation Sequence,FOS),及FOS 中每个工序对应使用的机床资源、刀具资源和进刀方向(Tool Approach Direction,TAD)。
TSP的几种求解方法及其优缺点旅行商问题（TSP）是一个组合优化问题，目的是找到一条最短的路径，使得旅行商能够访问一系列城市并返回起始点。
TSP由于其复杂性而被广泛研究，已经发展出了许多求解方法。
本文将讨论几种主要的TSP求解方法，包括贪婪算法、局部算法、遗传算法和蚁群算法，并分析它们的优缺点。
1.贪婪算法贪婪算法是一种基于贪心策略的求解方法。
它从一个起始城市开始，每次选择距离当前城市最近的未被访问过的城市作为下一步的目标城市，直到所有的城市都被访问过。
贪婪算法的优点是简单易于理解和实现，并且在处理小规模问题时效果显著。
然而，贪婪算法没有考虑全局最优解，很容易陷入局部最优解，不能保证找到最优解。
2.局部算法局部算法是一类启发式算法，它通过不断优化当前解来逐步接近最优解。
其中最典型的是2-opt算法，它通过交换路径中的两个顶点位置来改进解的质量。
局部算法的优点是可以找到局部最优解，且计算时间较短。
然而，局部算法容易陷入局部最优解，而且计算开销随问题规模增加而增加，且不能保证找到全局最优解。
3.遗传算法遗传算法是一种模拟生物进化的随机算法。
它通过模拟遗传、交叉和变异等基因操作来生成和改进解。
遗传算法的优点是可以处理大规模问题，且不容易陷入局部最优解。
同时，遗传算法能够在空间中探索多个解，提高解的多样性。
然而，遗传算法的计算开销相对较高，需要大量的迭代和种群更新。
此外，遗传算法的性能与参数设置相关，需要进行调整。
4.蚁群算法蚁群算法是一种模拟蚂蚁觅食行为的算法。
它通过模拟蚂蚁在路径上释放信息素的过程，来引导蚂蚁选择路径。
蚁群算法的优点是能够找到较好的解并具有一定的自适应性。
它适用于处理大规模问题，且能够处理问题中的不确定性。
然而，蚁群算法的计算开销较高，并且参数设置对结果影响较大。
综上所述，TSP的求解方法包括贪婪算法、局部算法、遗传算法和蚁群算法等。
每种方法都有自己的优点和缺点。
选择适合问题规模、问题特征和求解时间的方法是关键。
遗传算法一、遗传算法的简介及来源1、遗传算法简介遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它最初由美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著《自然系统和人工系统的自适应》，GA这个名称才逐渐为人所知，J.Holland教授所提出的GA通常为简单遗传算法（SGA）。
遗传算法模仿了生物的遗传、进化原理, 并引用了随机统计理论。
在求解过程中, 遗传算法从一个初始变量群体开始, 一代一代地寻找问题的最优解, 直至满足收敛判据或预先设定的迭代次数为止。
它是一种迭代式算法。
2、遗传算法的基本原理遗传算法是一种基于自然选择和群体遗传机理的搜索算法, 它模拟了自然选择和自然遗传过程中发生的繁殖、杂交和突变现象。
在利用遗传算法求解问题时, 问题的每个可能的解都被编码成一个“染色体”,即个体, 若干个个体构成了群体( 所有可能解) 。
在遗传算法开始时, 总是随机地产生一些个体( 即初始解) , 根据预定的目标函数对每个个体进行评价, 给出了一个适应度值。
基于此适应度值, 选择个体用来繁殖下一代。
选择操作体现了“适者生存”原理, “好”的个体被选择用来繁殖, 而“坏”的个体则被淘汰。
然后选择出来的个体经过交叉和变异算子进行再组合生成新的一代。
这一群新个体由于继承了上一代的一些优良性状,因而在性能上要优于上一代, 这样逐步朝着更优解的方向进化。
因此, 遗传算法可以看作是一个由可行解组成的群体逐代进化的过程。
3、遗传算法的一般算法（1）创建一个随机的初始状态初始种群是从解中随机选择出来的，将这些解比喻为染色体或基因，该种群被称为第一代，这和符号人工智能系统的情况不一样，在那里问题的初始状态已经给定了。
（2）评估适应度对每一个解(染色体)指定一个适应度的值，根据问题求解的实际接近程度来指定(以便逼近求解问题的答案)。
生产计划排程问题的遗传算法求解现代工业生产中，生产计划排程是公司经营中至关重要的一环，因为它关系到整个制造业的效率和生产成本。
而生产计划排程是一个复杂的难题，需要处理大量的数据和决策，以及考虑到员工的生产能力、机器的容量、原料库存等各方面的因素，而传统方法的计算通常会存在一些难以克服的问题。
由此，遗传算法被引入计划排程问题解决方案中，因为它可以高效地处理这些数据，并给出一种最优解决方法。
遗传算法，是一种模拟自然进化过程的算法，由生物进化原理中的基因模型和群体结构理论所构成的计算模型。
其核心思想是将一些基因通过交叉互补来产生一些新的基因，并保留一些适应度高的基因，不断迭代演化，最后得出适应度最高的基因组。
因为遗传算法的优点是在非线性、高维和复杂目标函数的求解中，有很好的求解能力，所以遗传算法在生产计划排程问题中的求解中有着广泛的应用。
在传统生产计划中，存在着“红灯点”（即限制条件），如机器台数、时间期限、工厂容量等，这些限制条件使得计划排程变得复杂，而生产计划优化就是解决这些限制条件的复杂性。
而遗传算法的一个好处是可以有效地优化计划排程问题。
在实际应用中，遗传算法已被证明是一种很有效的求解方法，其适应性和成功率都很高。
遗传算法优化生产计划排程的过程主要包括如下几个方面：1.基因表示遗传算法中，个体由基因组成，而在生产计划排程中，基因可以用来表示产品的产品工序流程，机器的任务执行情况，产品的初始工序和初始状态等。
因此，基因的表示和编码方式对于生产计划排程有着很重要的影响。
2.适应度函数适应度函数的作用是为每个个体在遗传算法中赋值一个适应度，根据适应度的高低，决定哪些个体可以进入下一阶段。
在生产计划排程中，适应度函数应该能够描述个体与目标之间的优化程度，如采用加权平均法或贪心法等。
3.群体进化过程在群体进化过程中，需要通过群体的变异、选择和交叉等过程，筛选出适应度高的基因组并生成新的个体。
在生产计划排程中，群体的进化应该通过优化既定的机器、生产线、产品流程等协同配合的模式，使得产品的生产效率最大化，同时要考虑到限制条件所带来的影响。
遗传算法的应用一、什么是遗传算法？遗传算法是一种全局概率搜索优化算法。
遗传算法( Gnectci Algortihms) ，是一种模拟自然界生物进化过程的全局随机搜索算法，由美国Mcihigna大学的Hollnad 教授于60 年代首先提出。
它将计算机科学与进化论思想有机结合起来，借助于生物进化机制与遗传学原理，根优胜劣汰和适者生存的原则，通过模拟自然界中生物群体由低级、简单到高级、复杂的生物进化过程，使所要解决的问题从初始解逐渐逼近最优解或准最优解。
作为一种新的全局优化搜索算法，遗传算法因其简单易用，对很多优化问题能够较容易地解出令人满意的解，适用于并行分布处理等特点而得到深入发展和广泛应用，已在科学研究和工程最优化领域中展现出独特魅力.二、遗传算法的发展：从20世纪40年代，生物模拟就成为了计算科学的一个组成部分；20世纪50年代中期创立了仿生学；进入60年代后，美国密切根大学教授Holland及其学生创造出遗传算法。
三、遗传算法的特点：遗传算法作为具有系统优化、适应和学习的高性能计算和建模方法的研究渐趋成熟。
遗传算法具有进化计算的所有特征，同时又具有自身的特点：（1）搜索过程既不受优化函数的连续性约束，也没有优化函数导数必须存在的要求。
（2）遗传算法采用多点搜索或者说是群体搜索，具有很高的隐含并行性，因而可以提高计算速度。
（3）遗传算法是一种自适应搜索技术，其选择、交叉、变异等运算都是以一种概率方式来进行，从而增加了搜索过程的灵活性，具有较好的全局优化求解能力。
（4）遗传算法直接以目标函数值为搜索信息，对函数的性态无要求，具有较好的普适性和易扩充性。
（5）遗传算法更适合大规模复杂问题的优化。
四、遗传算法的原理和方法：（1）编码：编码是把一个问题的可行解从其解空间转换到GA 所能处理的搜索空间的转换方法。
而解码是由GA 解空间向问题空间的转换。
编码机制直接影响着算法的整体性能，也决定了种群初始化和各种遗传算子的设计等各种过程。
