遗传算法解决TSP问题 C++、MFC界面编程 - 图文(4)

本科毕业设计说明书（论文）

3 遗传算法在TSP上的应用与实现

第 12 页 共 32 页

本文通过遗传算法来解决10个城市的旅行商问题。即一个商人需要经过10个城市去交易，每个城市必须且仅能经过一次。最后回到初始点。然后求出最短路径。

首先，本文运用基本遗传算法解决了TSP问题。然后通过改变各参数的值来观察计算结果，接着对计算结果的进行对比分析，从而验证了各参数对遗传算法的影响。主程序分为两个主模块。分别为初始种群10和100的模块。同时各模块还可以设定遗传代数、交叉率、变异率。以下对初始种群为100的模块进行代码分析。模块10代码类似，固不做分析。然后进行各参数设定后的结果对比。

3.1 算法的实现

3.1.1 遗传算法运用在TSP上的流图程

交叉操作 输出结果 以每次访问总距离的倒数作为评估函数，对每个个体进行评估，初始化代数p=0 不成立 P<=遗传代数 成立 结束 选择操作 P=p=1 以访问路径顺序进行编码 采用随机方式初始化种群 外部输入初始化种群个数、遗传代数、交叉率、变异率

变异操作 图3.1 遗传算法运用在tsp上的流程图 本科毕业设计说明书（论文）

3.1.2 编码

第 13 页 共 32 页

遗传算法设计的第一个重点就是编码。上文已经阐述过编码的各种主要方式。如：二进制表示、浮点编码、格雷码、参数编码等。由于二进制表示不自然且需要额外的修正算子，以保证个体的合法性，在实际运用中很少出现。在TSP问题中，路径表示可能是最自然、最直接的表示方式。它直接采用城市在整个路径中的相对位置来表示。遗传算法中的每个个体，就是一次访问的顺序。如有10个城市：0,1，2,3,4,5,6,7,8,9。商人的一次访问顺序为（4,2,1,0,5,8,3,9,6,7,4）。就用（4,2,1,0,5,8,3,9,6,7）作为种群中的一个个体的编码。表示商人从城市4出发路径为4,2,1,0,5,8,3,9,6,7最后回到城市4。这显然是一种非常自然的编码方式。其主要的缺点在于普通的单点、双点交叉操作后往往会引起非法路径的访问（在整个访问过程中有些城市访问了不止1次）。为了消除这一缺点，本文采用次序交叉方法代替了传统的单点、双点交叉。

本文采用数组a[10]来存放群众中的一个个体的访问顺序。City[100][10]存放种群中100个个体各自的访问顺序。 3.1.3 初始化种群

初始化种群：采用随机方式获得初始化种群。它适合与对问题的解无任何先验知识的情况。代码如下：

void CTestDlg2::chushi(int a[10],int city[100][10]) {

int trsf; int ii,jj;

for ( ii=0;ii<=99;ii++)//随机排列城市

{

for(jj=9;jj>=1;jj--) {

int n = rand()%(jj+1); trsf=a[jj]; a[jj]=a[n]; a[n]=trsf;

city[ii][jj]=a[jj];

本科毕业设计说明书（论文）

}

city[ii][0]=a[0];

第 14 页 共 32 页

} }

3.1.4 适应度函数

为了体现种群中个体的适应能力，引入了对种群中每个个体进行度量的函数，叫做适应度函数。通过它来决定个体的优劣。它体现了自然进化中优胜劣汰的原则。对于优化问题，适应度函数就是目标函数。

TSP问题的目标就是访问路径最短。本文采用路径距离和的倒数作为适应函数。本文用数组存放eval[100]每个个体的总路程。eval1[100]每个个体总路程的倒数，作为适应度函数。

for(i=0;i<=99;i++){eval1[i]=1/(eval[i]);} 3.1.5 选择操作

选择操作也称为复制操作。根据个体适应度函数所度量的优劣程度来决定个体是被淘汰还是遗传。对于求解TSP问题，常用的选择机制有轮盘赌选择、最佳个体保存选择，期望值模型机制，排序模型选择机制等。在遗传算法中，算法“早熟”是一个需要关注的问题。为了避免算法进入局部收敛，保证全局收敛性，就要维持种群个体的多样性，避免有效个体的丢失。Rudolhp C[12]提出采用精英选择策略即保持群体中最好的个体不丢失，以保证算法的收敛性。Konstantin Boukreev[14]采用联赛选择方法和最优个体保存方法相结合的方法。为了保证最好个体不丢失，本文采用轮盘赌算法和最优保存算法的结合。

(1) 轮盘算法：

将个体的适应度值按比例转换为选中的概率。使得适应度值高的个体的被选中的概率也高。令for(i=0;i<=99;i++){gailv[i]=eval1[i]/total;}。在将轮盘分成100个扇区进行100次选择。产生100个0到1之间的随机数。相当于轮盘转动100次，可以获得n次转盘停止时的指针位置，指针停放在某一个扇区。就代表选中了该扇区的个体。所以概率越大面积越大，被选中的几率越大。

(2) 最优保存算法：

在遗传算法的过程中，通过对个体进行交叉、变异等遗传操作不断产生新一代的种群个体，虽然随着不断的进化，会产生越来越多的优秀个体。但是由于遗传操作的

本科毕业设计说明书（论文）

第 15 页 共 32 页

随机性，可能破坏掉当代种群中最优秀的个体。我们希望适应度最好的个体要尽可能的保存到下一代群体中。为了实现这一目标，我们使用最优保存策略辅助轮盘算法来进行选择操作。最优保存的具体过程：首先找出当代个体中的最优个体和最差个体。如果当代个体中的最优个体比总优个体（也就是第一代种群到今的最优个体）的适应度值还要高的时候。则以当代最优个体来替换总最优个体中保存的个体。如果当代个体的最优个体比总最优个体要差，则说明最优个体被破坏，则用总最优个体替换掉当代个体中的最差个体。总最优个体不变。

下面为轮盘算法和最有保存算法代码: 轮盘算法:

int CTestDlg2::select(double gailv[100],int city[100][10])//选择函数 {

int q=0;

double suiji=(double)rand()/RAND_MAX;

while(suiji==0){ suiji=(double)rand()/RAND_MAX;} }

最优保存算法：

mi=int(Min(eval));//存放最优个体序号

for(i=0;i<=9;i++)//存放最优个体 { }

milen=int(eval[mi]);//存放当代最优路劲距离

mi1[i]=(city[mi][i]);

double leiji=0.0;

while((leiji

leiji=leiji+gailv[q]; } q--; return(q);

q++;

本科毕业设计说明书（论文）

ma=int(Max(eval));//存放当代最差个体序号

第 16 页 共 32 页

for(i=0;i<=9;i++)ma1[i]=city[ma][i];//存放最差个体 malen=int(eval[ma]);//存放当代最差路径距离 if(tmilen==0) { } else {

if(milen<=tmilen) { } else {

for(i=0;i<=9;i++)city[ma][i]=( tmi1[i]);//上代最优个体被破

tmilen=milen;//更改总最优路径距离

for(i=0;i<=9;i++)//存储首代最优路径的访问顺序 { }

tmi1[i]=( mi1[i]);

tmilen=milen;//存储首代最优路径距离 for(i=0;i<=9;i++)//存储首代最优路径顺序 { }

tmi1[i]=( mi1[i]);

坏，用上代最优个体替换本代的最差个体.总最优路径不变

}

}

其中的Min（）为求最优路径，Max（）求最差路径 int CTestDlg2::Min(double eval[100]) {

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库遗传算法解决TSP问题 C++、MFC界面编程 - 图文(4)在线全文阅读。