智能优化TSP旅行商问题Word文档格式.docx
《智能优化TSP旅行商问题Word文档格式.docx》由会员分享，可在线阅读，更多相关《智能优化TSP旅行商问题Word文档格式.docx（24页珍藏版）》请在冰点文库上搜索。
遗传算法是基于达尔文适者生存、优胜劣汰的进化原则，通过对群体反复使用基本的遗传操作，不断生成新的群体，使种群不断进化，并以全局并行搜索技术来搜索优化群体中的最优个体，以求得满足要求的最优解的一种问题求解策略。
由于遗传算法实现全局并行搜索，搜索空间大，并且在搜索过程中能够不断地向可能包含最优解的方向作搜索空间的调整，因此，易于寻找到最优解或准最优解。
需要解决的问题越复杂，目标越不明确，遗传算法的优越性就越大。
遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子（选择、交叉和变异）对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。
遗传算法与传统的优化方法相比，主要有以下几个特点:
（1）遗传算法不是直接作用在参变量集上，而是直接作用在参变量集的某种编码上；
（2）遗传算法不是从单个点进行搜索，而是从一个初始群体开始搜索；
（3）遗传算法利用适应度值信息，无须导数或其它信息；
（4）遗传算法利用概率转移规则，而非确定性规则。
2、遗传算法的基本概念与基本操作
根据遗传理论，遗传算法的基本操作对象被称为染色体（Chromosome）或个体。
每个个体是一个知识结构，代表了被求解问题的一个可行解。
个体通常用字符串或位串表示，一定长度的位串被称为个体的基因（Gene），基因表示了个体的某些特征。
群体或种群（Population）是由一组个体构成的，它是个体的集合，描述了遗传
算法搜索的遗传空间。
种群的大小（Populationsize）是种群个体的数量。
在搜索过程中，用适应度函数（Fitnessfunction）来评价每个个体的优劣，其值越大（适应度值大），则相应的个体所代表的解越优。
适应度函数的选择能够有效地指导搜索空间沿着最佳参数优化组合的方向逼近。
利用遗传算法求解问题的第一步就是要对问题的解以某种形式编码，并将问题的解用遗传空间的解来表示，即用字符串构造个体的过程。
与其相反的操作称为解码。
另外，编码形式的选择也是影响遗传算法效率的重要因素之一。
在对问题的解进行编码及对种群进行初始化后，对种群的遗传操作主要有以下三种:
即
选择操作、交叉操作和变异操作。
选择（Selection）操作就是根据个体的适应度值，在群体中按一定的概率选择可作为父代的个体。
选择的依据是:
适应度值大的个体被选中的概率也大，即选择的过程是一种基于适应度值优胜劣汰的过程。
选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代以繁殖下一代子孙。
主要的选择操作有轮盘赌方法和锦标赛方法等。
交叉（Crossover）操作是按一定的概率随机地交换一对父个体的基因以形成新的子个体，这个过程又称基因重组。
交叉操作是遗传算法的主要操作，通过交叉操作可得到新一代个体。
主要的交叉操作有单点交叉、两点交叉等。
变异（Mutation）操作是按一定的概率随机地改变某个个体的基因值，以形成新的子个体，它的目的是挖掘群体中个体的多样性，克服有可能陷于局部最优解的弊端。
3、遗传算法的基本流程
遗传算法的运行过程为一个典型的迭代过程，其必须完成的工作和基本步骤如下：
（l）选择编码策略，对所解决的问题进行编码，把参数集合X和域转化为位串结构空间S；
（2）定义适应度函数f（x），适应度大小表示了该个体的好坏；
（3）确定遗传策略，包括确定种群大小、选择、交叉、变异方法，以及确定交叉概率Pc，变异概率Pm等遗传参数；
（4）随机初始化种群P；
（5）计算种群中个体位串解码后的适应度值；
（6）按照遗传策略，运用选择、交叉和变异算子作用于种群，形成下一代种群；
三、算例设计
遗传算法求解TSP问题可包括:
编码、种群初始化、适应度评价、遗传操作（选择、交叉、变异）、终止条件判定、解码等步骤:
1、染色体编码
由于遗传算法不能直接处理解空间的数据，因此必须通过编码将它们表示成遗传空间的基因型串结构。
编码应具备完备性、健全性.、非冗余性等特点。
GA通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串。
正如研究生物遗传是从染色体着手，而染色体则是由基因排成的串。
对于TSP问题，主要有以下几种编码方式:
（1）顺序表示
1955年，Grefenstette等针对TSP问题提出了基于顺序表示（OrdinalRepresentation）的遗传算法基因编码[36]。
顺序表示是指将所有城市依次排列构成一个顺序表（orderList）。
对于一条旅程，可以依旅行顺序处理每个城市，每个城市在顺序表中的顺序就是一个遗传因子表示。
每次处理完一个城市，从顺序表中去掉该城市。
处理完所有的城市后，将每个城市的遗传因子表示依次连接起来，就成为一条旅程的基因表示。
例如，顺序表C=（1，2，3，4，5，6，7，8，9），如果一条旅程为1一2一4一3一8一5一9一6一7，则这条旅程的编码为:
112141311。
因为这种编码方式在进行单点杂交时，左侧部分的旅程没有发生变化，所以这种方法在适用性方面存在一定的问题。
（2）近邻表示
近邻表示（AdjacentEdgesRepresentation）是将旅程表示成n个城市的一个排列，若在第i位的城市为j，则表明从i所到达的下一个城市为j。
例如，设出发城市的编号为1，则排列（2，4，8，3，9，7，1，5，6）表示的旅程为:
1一2一4一3一8一5一9一6一7。
显然，每一条旅程都唯一对应一个近邻表示。
然而，任意一个近邻排列却不一定都能对应于一个合法旅程，例如近邻排列（2，4，8，1，9，3，5，7，6）就导致了一个不完全回路1一2一4一1，产生了非法旅程，即小圈现象。
针对小圈现象，需要在算法中加以修改，以得到合法的旅程。
（3）矩阵表示
矩阵表示（MatrixRepresentation）是将一条旅程表示成为一个n×
n矩阵，其存储量随城市规模的增加而迅速增加，其遗传操作比较复杂，并具有盲目性。
本文采用此表示方法作为遗传算法的编码方式
本程序解决的是10城市间的TSP问题，下面采用实数编码并给出了10个城市间距离矩阵，分别用数字0-9表示北京、天津、武汉、深圳、长沙、成都、杭州、西安、拉萨、南昌10个城市。
r[i][j]代表城市i与城市j之间的距离：
北京
天津
武汉
深圳
长沙
成都
杭州
西安
拉萨
南昌
1
2
3
4
5
6
7
8
9
118
1272
2567
1653
2097
1425
1177
3947
1574
1253
2511
1633
2077
1369
1157
3961
1518
1462
380
1490
821
856
3660
385
922
2335
1562
2165
3995
993
1700
1041
1135
3870
456
2311
920
2170
1920
1420
4290
626
2870
1290
4090
2、种群的初始化
因遗传算法的群体型操作需求，必须为遗传操作准备一个由若干初始解组成的初始群体。
初始群体可以随机产生，也可以通过某种算法生成，但需要保证群体的多样性。
在种群初始化时需要考虑以下几个方面的因素:
（1）根据问题固有的知识，设法把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定初始群体。
（2）随机生成一定数目的个体，然后从中挑选出最好的个体加入初始群体。
这一过程不断进行迭代，直到初始群体中个体数达到了预先确定的规模。
群体的数量对遗传算法有着很大的影响。
若群体过大，能够保证群体的多样性，但其计算量则相应地增加，而且高适应度的个体容易被淘汰;
若群体过小，则计算量较少，但容易导致早熟现象。
求解TSP的遗传算法确定初始群体的常用方法一般有两种，即随机产生初始个体组成初始群体，以及利用局部搜索算法修正后的个体组成初始群体。
随机选取初始群体是被普遍采用的初始化方法，它具有速度快、并能保证群体多样性等特点。
但随机产生的个体适应度值太低，它们需要更多的迭代次数的遗传操作来进行优化。
遗传算法的主要遗传操作—交叉操作，往往会使得群体中个体越来越趋于相同，致使种群在一定的迭代次数后很难得到进化，而此时的解离最优解可能相去甚远，这就使得这种初始化方法的优点丧失殆尽。
局部搜索算法初始化群体可以解决随机化方法造成的问题，但局部搜索算法将增加整个算法的时间开销，特别是当种群规模较大时，初始化种群操作就将占用整个算法时间的很大比重，并使得算法无法在合理的时间内完成。
针对上述两种方法的优缺点，采用快速的近似算法初始化种群将是一种折衷方案。
一般采用的群体初始化方法有最近邻法等。
3、适应度评估检测
遗传算法在搜索进化过程中一般不需要其它外部信息，仅需要采用评估函数值（适应度函数值）来评估个体的优劣，并作为以后遗传操作的依据，适应度函数设计直接影响了遗传算法的性能。
适应度评估检测可分如下步骤进行:
（1）目标函数到适应度函数的映射:
由于适应度函数的非负性，不能直接用目标函数代替适应度函数，必须对目标函数作相应的转化，这就需要一个从目标函数到适应度函数的映射。
（2）适应度函数的标定
常用的标定方法有线性标定、s截断、乘幂标定等。
在应用遗传算法时，群体中小规模异常个体的出现常常不利于群体的优化。
在遗传初期，超常的个体往往会导致未成熟的收敛现象。
在遗传进化过程中，往往出现群体平均适应度值接近最佳个体适应度值，使得优化过程趋于无目标的随机漫游过程。
所以在遗传算法中，调整群体中个体的竞争水平是必要的，从而能够得到适应度较高的个体。
对未成熟收敛现象，可通过缩小相应个体的适应度值以实现降低这些异常个体的竞争能力，从而避免未成熟现象的产生;
对于随机漫游现象，则可通过放大适应度值以实现提高个体间竞争力的方法加以避免。
常见的求解TSP问题的适应度函数为f=1/L，其中L为环路长度。
4、交叉算子
所谓交叉运算，是指对两个相互配对的染色体依据交叉概率Pc按某种方式相互交换其部分基因，从而形成两个新的个体。
交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。
本程序中交叉算子实际上是将一段路径“串”逆序。
5、变异算子
所谓变异运算，是指依据变异概率Pm将个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。
遗传算法中的变异运算是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力，同时保持种群的多样性。
交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。
（1）移位变异
移位变异（DisplacementMutation，DM）是指随机选取一段路径，然后将该段路径插入到任意点之后。
（2）交换变异
交换变异（ExchangeMutation，EM）是指随机选取环路中的任意两点，然后进行交换。
（3）插入变异
插入变异（InsertionMutation，ISM）是指从环路中随机选取一点，然后将该点插入到任意点之后。
本程序中的变异算子实际上是将种群中某两个位置的节点值互换，即交换变异。
例如：
4、选择策略
遗传算法对一个个体（解）的好坏用适值函数值来评价，适值函数值越大，解的质量越好。
适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。
遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：
适应度高的个体被遗传到下一代群体中的概率大；
适应度低的个体，被遗传到下一代群体中的概率小。
选择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。
本文中选择算子采用轮盘赌选择方法。
轮盘赌选择又称比例选择算子，它的基本思想是：
各个个体被选中的概率与其适应度函数值大小成正比。
设群体大小为n，个体i的适应度为Fi，则个体i被选中遗传到下一代群体的概率为：
轮盘赌选择方法的实现步骤：
（1）计算群体中所有个体的适应度函数值（需要解码）；
（2）利用比例选择算子的公式，计算每个个体被选中遗传到下一代群体的概率；
（3）采用模拟赌盘操作（即生成0到1之间的随机数与每个个体遗传到下一代群体的概率进行匹配）来确定各个个体是否遗传到下一代群体中。
四、仿真实验设计
程序流程图：
五、仿真实验结果分析
本程序迭代次数为200，得到最佳路径及最佳适应值。
仿真结果如下：
六、总结与展望
这一现象与使用的是遗传算法有很大关系。
遗传算法其本质是模拟生物进化过程，而生物进化的过程是一个很复杂的过程，并且进化本身就无法控制其精确向着最优结果进行。
这也是遗传算法容易陷入局部最优的根本原因。
附录：
#include<
math.h>
iostream>
time.h>
usingnamespacestd;
#definePopSize50//种群类DNA个数
#defineMaxGens200//最大代数
#defineN10//问题规模
#definePC0.8//交叉概率
#definePM0.01//突变概率
intcity[N];
//有N个城市
intbegin_city=0;
//出发城市
doubler[N][N]={//N各个城市之间的权值，用一个矩阵表示
0,118,1272,2567,1653,2097,1425,1177,3947,1574,
118,0,1253,2511,1633,2077,1369,1157,3961,1518,
1272,1253,0,1462,380,1490,821,856,3660,385,
2567,2511,1462,0,922,2335,1562,2165,3995,933,
1653,1633,380,922,0,1700,1041,1135,3870,456,
2097,2077,1490,2335,1700,0,2311,920,2170,1920,
1425,1369,821,1562,1041,2311,0,1420,4290,626,
1177,1157,856,2165,1135,920,1420,0,2870,1290,
3947,3961,3660,3995,3870,2170,4290,2870,0,4090,
1574,1518,385,993,456,1920,626,1290,4090,0
};
intgeneration;
//当前代数
intCurBest;
//最优个体
structGenoType
{
intgene[N];
//城市序列
doublefitness;
//当前城市序列对应的适应值
doublerfitness;
//适应率
doublecfitness;
//轮盘对应的起始区间值
};
structResultType
doublebest_val;
//最佳适应度
doubleavg;
//平均适应度
doublestddev;
//标准差
GenoTypepopulation[PopSize+1];
//种群
GenoTypenewpopulation[PopSize+1];
//新种群
ResultTyperesult[MaxGens];
//种群换代记录
//函数声明
voidInitIndividual（）;
//初始化个体
voidEvaluate（）;
//评价函数
voidFind_the_best（）;
//找出最优个体
voidElitist（）;
voidSelect（）;
//选择
voidCrossover（）;
//交叉
voidMutate（）;
//变异
voidReport（）;
//报告输出
intIntGenerate（）;
//产生一个城市节点
voids*,int*）;
//交换两值
voids*a,int*b）
inttemp;
temp=*a;
*a=*b;
*b=temp;
}
/*产生一个0到10的数，作为城市编号*/
intIntGenerate（）
intRANGE_MIN=0;
intRANGE_MAX=N;
intrand10=（（（double）rand（）/（double）RAND_MAX）*RANGE_MAX+RANGE_MIN）;
returnrand10;
/*初始化种群*/
voidInitIndividual（）
{
intmatrix[N];
//临时数组
intx1,x2;
//生成一个定值序列1到9，0点为开始点
for（inti=1;
i<
N;
i++）
matrix[i]=i;
for（intj=0;
j<
PopSize;
j++）
{
population[j].gene[0]=begin_city;
//gene[0]表示出发城市，i表示城市次序
for（i=0;
i++）//N次交换，产生足够多的城市序列
{
x1=0;
x2=0;
while（x1==0）
x1=IntGenerate（）;
//随机产生一个0到10的数
while（x2==0）
x2=IntGenerate（）;
s[x1],&
matrix[x2]）;
}
for（inti=1;
i++）//将产生的临时数组赋给个体
population[j].gene[i]=matrix[i];
}
/*评价函数：
计算出该种群的适应性*/
voidEvaluate（）
intcurrent_city=begin_city;
intnext_city;
for（intmem=0;
mem<
mem++）
population[mem].fitness=0;
next_city=population[mem].gene[i];
population[mem].fitness+=r[current_city][next_city];
current_city=next_city;
population[mem].fitness+=r[current_city][begin_city];
/*找出该代种群中的最优个体，并将其存储.*/
voidFind_the_best（）
intmem,i;
CurBest=0;
for（mem=1;
mem++）
if（population[mem].fitness<
population[CurBest].fitness）//一次冒泡找出最优个体
CurBest=mem
升级会员 