用于求解TSP问题的遗传算法改进

第２７卷第１期　

２０１１年２月　大　学　数　学　

ＣｏＩ　Ｉ　ＥＧＥ　ＭＡＴＨＥＭＡＴＩＣＳ　Ｖｏ１．２７，№．１　

Ｆｅｂ．２０１１　

基于ＴＳＰ问题的一种改进遗传算法　

徐　莉，　张冬爽　

（金华广播电视大学，浙江金华３２１０００）　

［摘　要］针对传统遗传算法（ＧＡ）在解决旅行商问题（ＴＳＰ）时存在的不足，对初始种群的选取方式和算　子的选取进行了改进，设计出了一种能够较好的求解出ＴＳＰ问题的最优解的算法。计算机仿真实验验证了　该算法的有效性．　［关键词］遗传算法；初始种群；赌轮选择策略；最优保存策略；交叉算子　［中图分类号］０２２４　［文献标识码］Ａ　［文章编号］１６７２—１４５４（２０１１）０１—００６９　０４　

ＴＳＰ问题可以简单地描述成：一名旅行商从一个城市出发，欲访遍　个城市推销商品，每个城市到　

一次且仅到一次后返回原出发城市，求总距离最短的巡回路径．ＴＳＰ问题是典型的组合优化问题中的　

一个ＮＰ难题．几十年来对于求解ＴＳＰ问题出现了很多传统方法，其中有精确算法如线性规划算法；近　

似优化算法如最近插入法等．近年来，又出现了很多解决ＴＳＰ问题的较为有效的智能优化方法，例如遗　

传算法．遗传算法是根据生物进化思想启发得出的一种全局优化算法，特别适用于大规模非线性复杂问　题的优化，其特点是搜索效率高，适于搜索复杂地形．遗传算法解决ＴＳＰ问题中一个难解决的问题是如　

何较快地找到最优解并防止早熟收敛问题．目前许多研究者提出了诸多改进方法来提高遗传算法的性　

能：文献［３］通过改进交叉算子和变异算子对算法进行了改进，使该算法在提高搜索效率和解质量方面　

取得了很好的综合平衡．基于以上理论，本文提出了一种改进遗传算法．　

１算法的改进　

１．１初始群体的选取．　

在遗传算法中，初始群体一般是随机产生的，通过种群的进化最终达到最优值．但在实际操作时，这　

样进化的速度太慢，且进化效果往往不太好．因此，本文对初始种群的选取方式做了改进．具体操作是：　

技术与方法　物流技术２０１２年第３１卷第９期（总第２６４期）　

ｄｏｉ：ｌ０．３９６９／ｊ．ｉｓｓｎ．１００５－１５２Ｘ．２０１２．０９．０７２　

基于改进遗传算法的ＴＳＰ问题求解的研究　

周泽岩，张喜　

（北京交通大学交通运输学院，北京１０００４４）　

【摘要ｌ为了解决基本遗传算法求解ＴＳＰ问题过程中容易发生“早熟”收敛的问题，并进一步提高算法的求解速度，提出了　

一种求解ＴＳＰ问题的改进的遗传算法。采取的主要改进手段是：用贪婪算法构造初始种群，以提高找到近似最优解的速度；在轮　盘赌方法的基础上融入最佳保存策略进行选择操作；采用两点三段随机交叉的方法进行交叉操作，保持种群多样性以及避免种　群过早成熟。并通过编程实现了该算法，最后通过中国１４４个城市的ＴＳＰ实验，验证了该算法的良好性能。　【关键￣］ＴＳＰ问题；遗传算法；贪婪算法；两点三段随机交叉　ｆ中图分类号］ＴＰ３０１．６　ｆ文献标识￣－Ｕ，ｌＡ　ｆ文章编号］１ｏｏ５—１５２Ｘ（２０１２）０９—０２２０－０４　

Ｓｔｕｄｙ　ｏｎ　Ｓｏｌｕｔｉｏｎ　ｏｆ　ＴＳＰ　Ｂａｓｅｄ　ｏｎ　Ｉｍｐｒｏｖｅｄ　Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ　

ＺＨＯＵＺｅ－ｙａｎ，ＺＨＡＮＧＸｉ　（ＳｃｈｏｏｌｏｆＴｒａｆｆｉｃ＆Ｔｒａｎｓｐｏｒｔａｔｉｏｎ，ＢｅｉｊｉｎｇＪｉａｏｔｏｎｇＵｎｉｖｅｒｓｉｔｙ，Ｂｅｉｊｉｎｇ１０００４４，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ｉｎ　ｔｈｉｓ　ｐａｐｅｒ　ｗｅ　ｐｒｏｐｏｓｅｄ　ａｎ　ｉｍｐｒｏｖｅｄ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ　ｔｏ　ｓｏｌｖｅ　ｔｈｅ　ｔｒａｖｅｌｉｎｇ　ｓａｌｅｓｐｅｒｓｏｎ　ｐｒｏｂｌｅｍ　ａｎｄ　ｉｎｔｒｏｄｕｃｅｄ　ｉｎ　ｄｅｔｍｌ　ｔｈｅ　ｍａｉｎ　ｉｍｐｒｏｖｅｄ　ａｓｐｅｃｔｓ：ｕｓｉｎｇ　ｔｈｅ　ｇｒｅｅｄｙ　ａｌｇｏｒｉｔｈｍ　ｔｏ　ｃｏｎｓｔｒｕｃｔ　ｔｈｅ　ｉｎｉｔｉａｌ　ｐｏｐｕｌａｔｉｏｎ　ｉｎ　ｏｒｄｅｒ　ｔｏ　ｉｍｐｒｏｖｅ　ｔｈｅ　ｓｐｅｅｄ　ｔｏ　ｏｂｔａｉｎ　ｔｈｅ　ｎｅａｒ—ｏｐｔｉｍｉｚｅｄ　ｓｏｌｕｔｉｏｎｓ；ｃｏｍｂｉｎｉｎｇ　ｔｈｅ　ｏｐｔｉｍｕｍ　ｐｒｅｓｅｒｖａｔｉｏｎ　ｓｔｒａｔｅｇｙ　ｗｉｔｈ　ｔｈｅ　ｒｏｕｌｅｔｔｅ　ｍｅｔｈｏｄ；ｃａｒｒｙｉｎｇ　ｏｕｔ　ｃｒｏｓｓ——ｏｖｅｒ　ｏｐｅｒａｔｉｏｎ　ｗｉｔｈ　ｔｗｏ—－ｐｏｉｎｔ　ｔｈｒｅｅ——ｓｅｃｔｉｏｎ　ｒａｎｄｏｍ　ｃｒｏｓｓｉｎｇ　ｍｅｔｈｏｄ　ｔｏ　ｋｅｅｐ　ｔｈｅ　ｄｉｖｅｒｓｉｔｙ　ｏｆ　ｔｈｅ　ｐｏｐｕｌａｔｉｏｎ　ａｎｄ　ａｖｏｉｄ　ｐｒｅｍａｔｕｒｉｔｙ．Ｔｈｅｎ　ｉｎ　ａ　ＴＳＰ　ｅｘｐｅｒｉｍｅｎｔ　ｗｉｔｈ　１４４　Ｃｈｉｎｅｓｅ　ｃｉｔｉｅｓ．ｗｅ　ｄｅｍｏｎｓｔｒａｔｅｄｔｈｅｇｏｏｄｐｅｒｆｏｒｍａｎｃｅｏｆｔｈｅａｌｇｏｒｉｔｈｍ．　Ｋｅｙｗｏｒｄｓ：ＴＳＰ；ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ；ｇｒｅｅｄｙａｌｇｏｒｉｔｈｍ；ｔｗｏ－ｐｏｉｎｔｔｈｒｅｅ　ｓｅｃｔｉｏｎｒａｎｄｏｍｃｒｏｓｓｉｎｇ　

1 / 10 package GA;

import java.util.*;

public class Tsp {

private String cityName[]={"北京","上海","天津","重庆","哈尔滨","长春","沈阳","呼和浩特","石家庄","太原","济南","郑州","西安","兰州","银川","西宁","乌鲁木齐","合肥","南京","杭州","长沙","南昌","武汉","成都","贵州","福建","台北","广州","海口","南宁","昆明","拉萨","香港","澳门"};

//private String cityEnd[]=new String[34];

private int cityNum=cityName.length; //城市个数

private int popSize = 50; //种群数量

private int maxgens = 20000; //迭代次数

private double pxover = 0.8; //交叉概率

private double pmultation = 0.05; //变异概率

private long[][] distance = new long[cityNum][cityNum];

private int range = 2000; //用于判断何时停止的数组区间

private class genotype {

int city[] = new int[cityNum]; //单个基因的城市序列

long fitness; //该基因的适应度

(完整)用遗传算法求解TSP问题

用遗传算法求解TSP问题

遗传算法（Genetic Algorithm——GA），是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，它是由美国Michigan大学的J。Holland教授于1975年首先提出的。J.Holland教授和它的研究小组围绕遗传算法进行研究的宗旨有两个：抽取和解释自然系统的自适应过程以及设计具有自然系统机理的人工系统。遗传算法的大致过程是这样的:将每个可能的解看作是群体中的一个个体或染色体，并将每个个体编码成字符串的形式，根据预定的目标函数对每个个体进行评价,即给出一个适应度值。开始时,总是随机的产生一些个体，根据这些个体的适应度，利用遗传算子-—选择（Selection）、交叉（Crossover)、变异（Mutation)对它们重新组合，得到一群新的个体.这一群新的个体由于继承了上一代的一些优良特性，明显优于上一代，以逐步向着更优解的方向进化.遗传算法主要的特点在于：简单、通用、鲁棒性强。经过二十多年的发展，遗传算法已经在旅行商问题、生产调度、函数优化、机器学习等领域得到成功的应用。

遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法，与传统的优化算法相比,主要有以下特点：

1、 遗传算法以决策变量的编码作为运算对象.传统的优化算法往往直接决策变量的实际植本身,而遗传算法处理决策变量的某种编码形式，使得我们可以借鉴生物学中的染色体和基因的概念，可以模仿自然界生物的遗传和进化机理，也使得我们能够方便的应用遗传操作算子.

2、 遗传算法直接以适应度作为搜索信息，无需导数等其它辅助信息。

3、 遗传算法使用多个点的搜索信息,具有隐含并行性。

4、 遗传算法使用概率搜索技术，而非确定性规则。

遗传算法是基于生物学的,理解或编程都不太难。下面是遗传算法的一般算法步骤:

1、创建一个随机的初始状态

初始种群是从解中随机选择出来的，将这些解比喻为染色体或基因，该种群被称为第一代，这和符号人工智能系统的情况不一样;在那里,问题的初始状态已经给定了。