遗传算法学习及其在迷宫问题的应用代码实现精品毕业设计完整版.docx

遗传算法学习及其在迷宫问题的应用代码实现精品毕业设计完整版

目录

第一部分：

遗传算法介绍2

1.1遗传算法的产生和发展 2

1.2遗传算法的基本求解步骤  3

第二部分：

遗传算法解决迷宫问题（代码在文件夹代码中，可执行程序在文件夹程序中）4

2.1问题概述（构建迷宫）4

2.2为染色体编码6

2.3Epoch（时代）方法10

2.4参数值选择13

2.5算子函数14

2.6运行迷宫程序16

参考文献17

遗传算法学习及其在迷宫问题的应用

第一部分：

遗传算法介绍

遗传算法（genetic algorithms，GA）是一种模拟自然选择和遗传机制的寻优方法，它是建立在达尔文的生物进化论和孟德尔的遗传学说基础上的算法。

基因杂交和基因突变可能产生对环境适应性强的后代，通过优胜劣汰的自然选择，适应值高的基因结构就保存下来。

遗传算法就是模仿了生物的遗传、进化原理，并引用了随机统计原理而形成的。

1.1遗传算法的产生和发展 

50年代末60年代初，生物学家Fraser 试图通过计算的方法来模拟生物界"遗传与选择"的进化过程，这便是GA 的雏形。

受此启发，Holland 教授认识到自然遗传可以转化为人工遗传算法。

1967年Bagley 在其博士论文中首次提出了"遗传算法"这一术语。

1975年，

Holland出版了《自然与人工系统中的适应性行为》。

该书系统地阐述了遗传算法的基本理论和方法，提出了遗传算法的基本定理-模式定理，从而奠定了遗传算法的理论基础。

20世纪80年代初，Holland 

教授实现了第一个基于遗传算法的机器学习系统--分类器系统（Classifier System简称CS），开创了基于遗传算法的机器学习的新概念。

l992年，JohnR．Koza出版了专著《遗传编程》，提出了遗传编程的概念，并成功地把遗传编程的方法应用于人工智能、机器学习、符号处理等方面。

随着遗传算法的不断发展，关于遗传算法的国际学术活动越来越多，遗传算法已成为一个多学科、多领域的重要研究方向。

1.2遗传算法的基本求解步骤  

1.2.1编码:

确定用何种码制, 然后将问题参数编码形成基因码链，每一个码链代表一个个体, 表示优化问题的一个解。

1.2.2初始化:

随机产生一个规模为P的初始种群,其中每个个体为一定长度的码链, 该群体代表优化问题的一些可能解的集合。

1.2.3估计适应度:

计算种群中每个个体的适应度,适应度为群体进化时的选择提供了依据。

一般来说适应度越高, 解的素质越好。

适应度函数可以根据目标函数而定。

1.2.4再生（选择）:

根据每个个体的相对适应度,计算每个个体的再生次数,并进行再生操作, 产生新的个体加人下一代群体中,一般再生的概率与其适应度成正比。

1.2.5交叉:

从种群中随机选择两个染色体,按一定的概率进行基因交换,交换位置的选取是随机的。

1.2.6变异:

从种群中随机地选择一个染色体, 按一定的变异概率P进行基因变异,GA的搜索能力主要是由选择与交叉赋于的,变异算子则保证了算法能搜索到问题空间的每一点, 从而使算法具有全局最优性, 它进一步增强了GA的能力. 

1.2.7重复:

若发现最优解,则算法停止,否则转3,对产生的新一代群体进行重新评价、选择、交叉、变异操作, 如此循环往复,使群体中最优个体的适应度和平均适应度不断提高。

其流程图如下：

第二部分：

遗传算法解决迷宫问题（代码在文件夹代码中，可执行程序在文件夹程序中）

2.1问题概述（构建迷宫）

寻找路径问题是游戏人工智能的一块“神圣基石”下面就来创建一个遗传算法用在一个非常简单的场景中解决寻找路径问题，首先创建一个迷宫，他的左边有一个路口，右边有一个出口，并且有一些障碍物布在其中，在出发点放置一个虚拟的人鲍勃，然后要为他解决如何寻找路径的问题，使他能找到出口，并且避免与所有的障碍物相碰撞，下面讲述如何产生鲍勃的染色体的编码，但首先要解释如何来表示迷宫

迷宫是一个二维整数数组：

用0来表示开放的空间，1来表示墙壁或者障碍物，5为起始点，8为出口。

因此，假设迷宫的二维数组如下：

{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,

1,0,1,0,0,0,0,0,1,1,1,0,0,0,1,

8,0,0,0,0,0,0,0,1,1,1,0,0,0,1,

1,0,0,0,1,1,1,0,0,1,0,0,0,0,1,

1,0,0,0,1,1,1,0,0,0,0,0,1,0,1,

1,1,0,0,1,1,1,0,0,0,0,0,1,0,1,

1,0,0,0,0,1,0,0,0,0,1,1,1,0,1,

1,0,1,1,0,0,0,1,0,0,0,0,0,0,5,

1,0,1,1,0,0,0,1,0,0,0,0,0,0,1,

1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

在屏幕中的显示效果如图1所示。

图1迷宫实际显示效果图

这种地图的设计方法被封装在一个被称为CBobsMap的类中，并定义为

classCBobsMap

{

private:

//保存地图用的存储器（一个二维整数数组）

staticconstintmap[MAP_HEIGHT][MAP_WIDTH];

staticconstintm_iMapWidth;//地图宽读

staticconstintm_iMapHeight;//地图高度

/起始点在数组中的下标

staticconstintm_iStartX;

staticconstintm_iStartY;

//终点的数组下标

staticconstintm_iEndX;

staticconstintm_iEndY;

public:

//如果需要，可以利用这一数组作为Bob走过的路程的存储器

intmemory[MAP_HEIGHT][MAP_WIDTH];

CBobsMap（）

{ResetMemory（）;}

//利用一个字符串来记录Bob行进的方向，其中每个字符代表Bob所走的一步

//检查Bob离出口还有多远，返回一个与到达出口距离成正比的适应性分数

doubleTestRoute（constvector&vecPath,CBobsMap&memory）;

//Render函数利用windowsGDI在一个给定的作图表面上显示地图

voidRender（constintcxClient,constintcyClient,HDCsurface）;

//画出能够存放于存储器中的任意路径

voidMemoryRender（constintcxClient,constintcyClient,HDCsurface）;

voidResetMemory（）;

};

由上可知，只需要以常量的形式来保存地图数组以及起点与重点就行了。

这些数据在文件CBobsMap.cpp中定义的，，除了存储迷宫，这个Map类也用来记录Bob在迷宫中行走的路程：

memory[][]/这对遗传算法本身而言不是本质的，但是为了显示目的，看清Bob怎样在迷宫中漫游，设置一个记录是必须的。

2.2为染色体编码

每个染色体必须把Bob的每一步行动都编入代码中。

Bob的行动权限为四个方向：

向东，向南，向西，向北，故编码后的染色体应该是代表这四个方向信息的一个字符串。

传统的编码方法就是把方向变换成二进制的代码。

4个方向只有两位就够了，例如下表所示的那样

二进制代码

十进制译码

代表的方向

00

0

向北

01

1

向南

10

2

向东

11

3

向西

这样如果得到了一个随机的二进制字符串，就能根据它译出Bob行动时所遵循的一系列方向。

例如染色体：

111110*********110010101

代表的基因就是：

11,11,10,01,10,11,10,11,10,01,01,01

当把二进制代码转化为十进制时，就成为3,3,2,1,2,3,2,3,2,1,1,1

再把这些放进一个表格中

二进制代码

十进制译码

代表的方向

11

3

向西

11

3

向西

10

2

向东

01

1

向南

10

2

向东

11

3

向西

10

2

向东

11

3

向西

10

2

向东

01

1

向南

01

1

向南

01

1

向南

到此，所要做的全部就是将Bob置于迷宫的起点，然后告诉他根据这张表中的方向一步步的走。

如果一个方向使得Bob碰到了墙壁或者障碍物，则只需要忽略该指令并继续按下一条指令去走就行了。

这样不断下去，直到用完所有方向或Bob到达出口为止。

假如有几百个这样随机的染色体，它们中的某些就可能为Bob译码出到达出口的一套方法（问题的一个解），但是它们当中大多数是失败的。

遗传算法以随机的二进制串（染色体），作为初始群体，测试它们每一个能让Bob走到离出口有多么近，然后让其中最好的那些来孵化后代，期待它们的子孙”中能有比Bob走的离出口更近一点。

这样继续下去，直到找出一个解，或直到Bob绝望地在一个角落里被困住不动为止。

因此，必须来定义一种结构，其中包含一个二进制位串（染色体），以及一个与该染色体想联系的适应性分数。

这个结构称为SGenome结构，它的定义如structSGenome

{

vectorvecBits;

doubledFitness;

SGenome（）:

dFitness（0）{}

SGenome（constintnum_bits）:

dFitness（0）

{

//创造随机的二进制串

for（inti=0;i

{vecBits.push_back（RandInt（0,1））;}

}

};

如果在创建SGenome对象时把一个整型数作为参数传递给构造函数，则它就会自动创建一个以此整数为长度的随机二进制位串，并将其适应性分数初始化为零，完成对该基因组的设置。

SGenome结构不具备如何为染色体（vecBits）进行译码的知识，这是需要由遗传算法类自己来完成的一项任务。

下面简单介绍这个类的定义，这里将其称为CgaBob类。

classCgaBob

{

private:

vectorm_vecGenomes;//基因组群体

Intm_iPopSize;//群体的大小

Doublem_dCrossoverRate;

Doublem_dMutationRate;

Intm_iChromoLength;//每个染色体含有多少bit

Intm_iGeneLength;//每个基因有多少bits

Intm_iFittestGenome;

Doublem_dBestFitnessScore;

Doublem_dTotalFitnessScore;

Intm_iGeneration;

//为map类创建一个实例

CBobsMapm_BobsMap;

//另一个CbobsMap对象，用来保存每一代的最佳路径的一个记录

//这是被访问小格的一个数组，它仅为了显示目的而使用

CBobsMapm_BobsBrain;

//检测运行是否仍在进行中

boolm_bBusy;

voidMutate（vector&vecBits）;

voidCrossover（constvector&mum,

constvector&dad,

vector&baby1,

vector&baby2）;

SGenome&RouletteWheelSelection（）;

//用新的适应性分数来更新基因组原有的适应性分数

//并计算群体的最高适应性分数和适应性分数最高的那个成员

voidUpdateFitnessScores（）;

//把一个位向量译成为一个方向的（整数）向量

vectorDecode（constvector&bits）;

//把一个位向量变换为十进制数。

用于译码

intBinToInt（constvector&v）;

//创建一个随机的二进制伉串的初始群体

voidCreateStartPopulation（）;

public:

CgaBob（doublecross_rat,

doublemut_rat,

intpop_size,

intnum_bits,

intgene_len）:

m_dCrossoverRate（cross_rat）,

m_dMutationRate（mut_rat）,

m_iPopSize（pop_size）,

m_iChromoLength（num_bits）,

m_dTotalFitnessScore（0.0）,

m_iGeneration（0）,

m_iGeneLength（gene_len）,

m_bBusy（false）

{CreateStartPopulation（）;}

voidRun（HWNDhwnd）;

voidRender（intcxClient,intcyClient,HDCsurface）;

voidEpoch（）;

//访问用的方法

intGeneration（）{returnm_iGeneration;}

intGetFittest（）{returnm_iFittestGenome;}

boolStarted（）{returnm_bBusy;}

voidStop（）{m_bBusy=false;}

};

由上述内容可知，当这个类的一个实例被创建时，构造函数初始化所有的变量，并调用CreateStartPopulation（）。

这一短小函数创建了所需数量的基因组群体。

每个基因一开始包含的是一个由随机二进制位串组成的染色体，其适应性分数则被设置为零。

2.3Epoch（时代）方法

遗传算法类中最为实际的内容就是Epoch（）方法。

这也是之前提到的遗传算法的那个循环。

它是这个类中执行工作的部门。

这一方法与所有工作或多或少都联系在一起。

下面就对它进行详细讲述:

voidCgaBob:

:

epoch（）

{UpdateFitnessScores（）;

在每一个epoch循环内所要做的第一件事情，就是测试染色体群中每一个成员的适应性分数。

UpdateFitnessScores（）是用来对每个基因组的二进制染色体编码进行译码的函数，而由它再把译码所得到的一系列结果，也就是由代表东、南、西、北4个方向的整数，发送给CBobsMap:

:

TestRout。

后者检查Bob在地图中游走了多远，并根据Bob离开出口l的最终距离，返回一个相应的适应性分数。

计算Bob的适应性分数程序如下:

intDiffX=abs（posX-m_iEndX）;

intDiffY=abs（posY-m_iEndY）;

这里，DiffX和DiffY就是Bob所在格子的位置相对于迷宫出口的水平和垂直偏离值。

观察图2，灰色小格代表Bob通过迷宫的路程，上面写着B的小格是他最终所到达的地方。

在这一位置上，Diffx=3，DiffY=0

return1/（double）（DiffX+DiffY+1）;

上面的一行程序就是计算Bob的适应性分数。

它把DiffX与DiffY这两个数字加起来然后求倒数。

DiffX与DiffY的和数中还加了一个1，这是为了确保除法不会出现分母为零的错误，如果Bob到达出口，Diffx+DiffY=0.

B

UpdateFitnessScores也保持对每一代中适应性分数最高的基因组以及与所有基因组相关的适应性分数的跟踪。

这些数值在执行赌轮选择时要使用。

图2Bob尝试寻找迷宫出口

重新讨论Epoch函数。

由于在每一个Epoch中将会创建一个新的基因组群，因此，当它们在创建出来时（每次2个基因组），需要寻找一些地方来保存它们。

//现在创建一个新的群体

intNewBabies=0;

//为婴儿基因组创建存储器

vectorvecBabyGenomes;

现在继续讨论遗传算法循环中所处理的事务。

while（NewBabies

{

//用赌轮法选择两个上辈（parents）

SGenomemum=RouletteWheelSelection（）;

SGenomedad=RouletteWheelSelection（）;

在每次迭代过程中，需要选择两个基因组来作为两个新生婴儿的染色体的父辈，分别称为dad（父亲）和mum（母亲）。

一个基因组的适应性愈强，则由赌轮方法选择作为父母的几率也越大

//杂交操作

SGenomebaby1，baby2:

Crossover{num,vecBitsdad.vecBits,baby1.vecBits,baby2.vecBits）;

以上2行程序的工作是:

创建两个空白基因组，这就是两个婴儿;它们与所选的父辈一起传递给杂交函数Crossover（）。

这一函数执行了杂交（需依靠m_dCrossoverRate变量来进行），并把新的染色体的二进制位串存放到baby1和baby2中。

//变异操作

Mutate（baby1.vecBits）;

Mutate（baby2.vecBits）;

以上这两步是对婴儿实行突变。

这听起来可怕，但这对他们是有利的。

1个婴儿的位的突变概率依赖于mdMutationRate变景。

//把两个新生婴儿加入新群体

veaBabyGenomes.pushback（baby1）;

vecBabyGenomes.pushback（baby2）;

NewBabies+=2;

}

这两个新生后代最终要加入到新的群体中，这样就完成了一次Loop的迭代过程。

这一过程需要不断重复，直到创建出来的后代总量和初始群体的大小相同。

//把所有婴儿复制到初始群体

mvecGenome5=vecBabyGenome;

//代的数量加1

++m_iGeneration;

}

这里，原有的那个群体由新生一代所组成的群体来代替，并把代的数量加1，以跟踪当前的代。

这一Epoch函数将无止境地重复，直到染色体收敛到了一个解，或用户要求停止时为止。

在此首先讲述如何确定使用参数的值。

2.4参数值选择

程序所用的所有参数存放在文件defines.h中。

这些参数中大多数是目了然的，但有几个需要说明一下，即

#defineCROSSOVERRATE0.7

#defineMUTATION_RATE0.001

#definePOP_SIZE140

#defineCHROMO_LENGTH70

如何确定这些变量的初值，而这是价值百万美元的问题，但至今还没有快速而有效的规则，有的只是一些原则性的指导。

而且，选择这些值最终还应归结为每个用户对遗传算法的体验，用户只能通过自己的编程实践，用各种不同的参数值进行调试，看结果会发生什么，并从中选取适合的值。

不同的问题需要不同的值，但是通常来说，如果在使用二进制编码的染色体，则应把杂交率定在0.7，变异率定在0.001，这将是很好的初始默认值。

而确定群体大小的一条有用规则是将基因组的数目取为染色体长度的2倍。

因70表示Bob的35步的最大可能移动数目，所以这里选择70作为染色体长度，它比Bob为穿越地图到达出口所需的步数还要大一些。

2.5算子函数

重新阐述一下遗传算法的各种操作（或称算子）函数—选择、杂交、变异—的代码。

2.5.1赌轮选择

首先讲述赌轮选择算法，这一个函数的功能是从群体中选择一个基因组，选中的几率正比于基因组的适应性分数。

SGenome&CgaHob:

:

RouletteWheelSelection（）

{

doublefSlice=RandFloat（）*m_dTotaFitnessScore{123456789};

在从零到整个适应性分数范围内随机选取了一实数fSlice.可以将此数看作整个适应性分数饼图中的一块，如图3所示。

doublecfTotal=0;

intSelectedGenome=0;

for（inti=0;i

{

cfTotal+=mveceenomes[i].dFitness;

if（cfTotal>fslice）

{

SelectedGenome=i;

break;

}

}

returnm_vecGenomes[SelectedGenome];

}

现在，程序通过循环来考察各个基因组，把它们相应的适应性分数一个一个累加起来，直到这一部分累加和大于fSlice的值时，即返回该基因组。

2.5.2杂交算子

这一函数要求两个染色体在同一随机位置上断裂开来，然后将它们在断开点以后的部分进行互换，以形成两个新的染色体（子代）。

voidCgaBab:

:

Crossover（constvector&num,

constvector&dad,

Vector&baby1，

Vector&baby2）

{

这一函数共传入4个参数，参数传递均采用引用（reference）方式，其中前两个传入父代parent染色体（这里染色体只是一个整数型的矢std:

:

veclor）后2个则是用来复制子代染色体的空矢量

if（（RandFloat（）>m_dCrossoverRate）||（mum==dad））

{

baby1=mum;

baby2=dad;

return;}

程序的作用为:

首先进行检测，决定mum和dad两个上辈是否需要进行杂交。

杂交发生的概率是由参数m_dCrossoverRate确定的。

如果不发生杂交，则两个父辈染色体不作任何改变地就直接复制为子代，函数立即返回。

intcp=RandInt（0，m_iChromoLength-1）;

沿染色体的长度随机选择一个点断裂开染色体。

for（inti=0;i

{

baby1.push_back（mum[i]）;

baby2.pushback（dad[i]）;

}

for（i=cp;i

{

baby1.push_back（dad[i]）;

baby2.pusn_back（mum[i]）;

}

}

这两个小循环把2个parent染色体在杂交点（CP,crossoverpoint）以后的所有位进行了互换，并把新的染