基于遗传规划的迷宫问题高效求解

崔兆顺

CUI Zhao-shun

（天水师范学院，天水 741000）

0 引言

进化算法是基于模拟自然进化的搜索过程而发展起来的一类随机搜索技术。目前研究的进化算法主要有三种典型的算法：遗传算法，进化规划和进化策略。遗传算法吸引了大量的研究者和探索者，并在许多工程领域的得到了应用，如管道线路优化，机器学习，模式识别，神经网络结构参数优化，及权重学习，精调模糊逻辑控制器，飞船控制系统优化等。遗传规划是遗传算法的扩展和延伸，它把不同领域的各种问题都看成程序归纳问题，也就是在可能的程序空间中寻找最优或满意的计算机程序。在遗传规划算法研究方面，包括问题约束，个体表示，适应度定义，选择策略和遗传算子等具体过程；在理论研究方面包括借助适应度状态图和模式定理等遗传规划的自适应机理分析。

目前遗传算法在迷宫问题上的主要解决方法都是优化路径，对搜索到的迷宫路径进行优化。本文用一组整数对程序进行编码，借鉴二进制编码的交叉，变异，并结合计算机程序的特点设计了遗传操作。使用遗传规划优化了行走程序，指导迷宫机器人在迷宫中找到一条最优的路径。实验结果表明使用遗传规划求解迷宫问题是有效的。

1 迷宫问题描述

迷宫问题可以表述为：一个二维的网格，寻找从某一个给定的起始单元格出发，经由行相邻或列相邻的单元格（可以通过的），最终可以到达目标单元格的、所走过的单元格序列。在任一个单元格中，都只能看到与它邻近的四个单元格；如果位于底边，则只有三个；位于四个角上，则只有2个。迷宫设计为以方格标示边界及障碍，空白标示可行路线，指定迷宫最左上角点为起点，最右下角为终点，对于随机迷宫，能够找到计算机程序来寻求路径，并且用遗传算法搜索到计算机程序，进行多次优化，能生成更好的程序。这与一般遗传算法求解迷宫问题的方法也不同，不是直接对路径进行探索优化。

2 基于遗传规划的迷宫问题高效求解

遗传规划的实现涉及到5个要素：染色体的编码、初始群体的设定、评估函数即适应值函数的设计、遗传操作的设计和算法控制参数的设定。

2.1 染色体编码

采用遗传算法，首先要考虑如何通过染色体的编码把问题的解空间映射到编码空间。这样，对问题的解空间的搜索，就转化为对编码空间的搜索。我们对一组指令编码，以一组指令作为一条染色体。这样最终求解问题的解就是求得一组好的指令，能指导迷宫机器人从迷宫起点到终点的行走。用一条指令来具体说明：

一条指令有四个部分，除去指令编号（0）后的三个部分为主要部分，我们会用语句在在读入一条指令时把具体操作（FIND）翻译为数码，加上后面操作成功与否后会转向的两部分（以数码形式表示的部分）作为染色体一部分。优化后输出到PathFinder_output.txt，又会需要将数码翻译为具体操作（FIND,GO,SAVE,LOAD）。一个指令集有n条指令（具体规模接收外界输入指定），那么一条染色体长度就有3*n，指令编号从0到n-1。在该长度的染色体中，所有3*n（n=0，1，2，...,n-1）位上的数码只能在{0，1，2，3}中选取，因为基本操作只有FIND,GO,SAVE,LOAD四种，而其余位上可以在数码集{0，1，2...，n-1}中选取，表示检测基本操作成功与否后会转向的指令编号。对迷宫从起点到达终点的路径的搜索就是对长度为3*n,由数码0到n-1构成的数码空间的搜索。这就构成了求解迷宫问题的遗传算法的染色体。

2.2 初始群体设定

初始群体是随机产生的，群体规模和最大代数可以由外部输入指定。定义一个randomize函数，随机生成一个长度为3*instruction.size的染色体。

2.3 适应值函数设计

评估函数是用来评估个体好坏的。在本问题中，迷宫机器人按照染色体（指令集）指导行走，我们考查到达的位置与终点位置的关系。前面已说到，每个位置以所在行、列数的有序对形式表示，我们在这里把它看为横纵坐标。机器人当前位置是已知的，我们把其横纵坐标各自与终点横纵坐标的差的绝对值，求和，作为其适应值。设已知点坐标（Xi,Yi）,终点坐标（Xg,Yg），有如下计算公式：

我们选择这样一个评估函数，而不是去考查所处位置与终点位置的绝对位置，用毕达哥拉斯定理（即勾股定理，有计算公式fitness（x）’）计算二者之间距离，好处有下列两点：

1）计算简单，避免出现浮点数，减少计算开销；

2）多个计算结果相比较，互相之间的差距与勾股定理计算结果互相之间的差距相比，更直观明显，增大了选择压力。迷宫机器人行走到某个位置，其适应值函数值越小，表明离终点越近，也就越是我们希望的结果。求迷宫问题的解转化为找适应值为0的个体，也就是说适应值为0的个体为最优个体。

2.4 遗传操作的设计

1）交叉算子的设计

前面提到杂交有多种方式，这里简单进行一下说明。

（1）一点交叉：

是由Holland提出的最基本的杂交方式，操作信息量比较小，杂交点位置的选择可能带来较大偏差。按照Holland的意思，一点交叉算子不利于长距离的保留和重组，而且位串末尾的重要基因总是被交换。

（2）两点交叉：

两点交叉对于短距模式破坏概率较大，对于长距模式破坏概率较小，满足提高低阶短距模式的重组机会，保证高阶长距模式的生存机会的搜索要求，因此在实践中大量采用。

（3）多点交叉：与两点交叉类似，但是更利于模式的重组。

（4）均匀交叉：染色体位上的每一位按相同的概率进行随机均匀交叉。

Spears和De Jong认为均匀交叉优于多点交叉，并提出了一种带偏置概率参数的均匀交叉（概率在0.5—0.8之间），不存在多点交叉算子操作引起的位置偏差，任意基因在均匀交叉作用下均可以重组，并遗传给下一子代个体。我们选择的是偏置概率为0.5的均匀交叉，即指对于选定的两个染色体，每一对基因位有50%的概率发生交换。这样的概率致使算法探索力度最大。例如，1234和4321时两个染色体串，对第一对基因位1和4而言，有50%的概率发生交换，成为4234和1321；后面三对基因位以此类推。在本文中，杂交操作是发生在随机选取的两条染色体之间，具体的操作、成功与否转向的下一步操作发生，操作互换交换，下一步操作指令编号互换。

2）变异算子的设计

随机选取一个染色体，对它的某个操作进行变异或是对下一步指令编号变异，对每一代的每个染色体，都进行了与种群规模大小一样次数的变异。

3 仿真实验与分析

本算法参数定义种群规模population_size，算法运行最大代数max_generation，指令规模（指令条数）program_size，偏置概率（设定为0.5）。种群规模影响遗传算法的有效性。规模太小，算法会很差或根本找不出问题的解，因为太小的种群数目不能提供足够的采样点；规模太大，会增加计算量，使收敛时间增大。一般种群规模定在30到160之间比较合适。在本文中一般定为100。最大代数也需要找到一个合适值，一方面是算法有效，另一方面尽量减小计算开销。在本设计中一般定为100。指令条数同样有上述考虑，一般为5—10条为宜。

图1 迷宫机器人完成行走

最后，设计了若干组实验考察了算法的重要参数设置（指令规模，种群规模，迷宫规模）对优化效果的影响，大致得出如下结论：

1）在其他参数不变的前提下，优化后指令的好坏程度随指令规模增大而增大，而迷宫规模会影响其程度。另外，测试证明运行时间会随指令规模增大而增大

2）在其他参数不变的前提下，种群规模定在100会得到更让人满意的优化结果。这也印证了理论中种群大小在30—160之间为合适。另外，测试证明运行时间随种群规模增大而增大。

4 结论

综和以上实验，我们可以得出，使用遗传规划算法解决迷宫问题，需要对各个参数进行适当设置，既要考虑算法效率，同时也要顾及计算开销，以求两方面有很好的平衡。而实验结果也证明本设计的算法是有效的，能够实际的解决迷宫问题，说明这个算法是有效的。

[1].De Jong K.Learning with Genetic Algorithms,An Overview.Machine Learning,1988,3（2,3）：121-138.

[2]刘勇,康立山,陈毓屏.非数值并行算法（第二册）[M].遗传算法.科技出版社,2003.

[3]De Jong and Spears,W.M.A formal analysis of the role of multi-point crossover in genetic algorithms.Annals of Mathematics and Artificial Intelligence,1992,5（1）：1-26.

[4]Jenking,W.M.Structural optimization with the genetic algorithm.Structural Engineer,1991,69（24）：408-422.

[5]Kadaba,N.Nygard,K.E.,and Juell,P.L.Integration of adaptive machine learning and knowledge-cased systems for routing and scheduling applications.Expert Systems with Applications,Vol 2,No.1,1991：15-27.