基于matlab遗传算法工具箱的设计思路.doc

基于MATLAB 的遗传算法工具箱设计  
本文是由北京理工大学的徐瑛和任雪梅同学所作。
2.1遗传算法工具箱的设计思想
工具箱归纳了遗传算法及其各种改进算法的相同之处，建立了一个统一的遗传算法基本流程框架，如下图1所示：

遗传算法中最重要的有三个基本操作，我们也称为算子：选择用来决定重组或者交叉的个体，以及被选的个体新产生的个体的个数。首先要计算所有个体的适应函数值，然后得到适应度。适应度可以按适应函数值的比例计算，也可以根据适应函数值排序来得到。交叉将群体内的各个个体随机搭配成对，以某个概率交换它们之间的部分染色体。变异对群体内的每一个个体，以某一概率改变某一个或某一些基因值为其它的基因值。另外，还有编解码运算和个体评价操作。
每一个算子，都可能有多种的具体算法及其实现，组合在一起从而形成了各种各样的遗传算法的改进算法。具体实现时，工具箱将每个算子的不同实现做成标准化的模块，彼此之间可以相互替换，以搭积木的方式组成了遗传算法及其各种改进。
工具箱总体上采用模块式设计，各个模块之间是相互独立的。它包括以下几个模块:命令模块、编解码模块、算子模块、结果显示模块、参数输人模块、监督和参数调整模块。其中命令模块是总控模块，从用户那里得到命令，根据这些命令调度其它模块的运行和停止。编解码是一个互逆的过程，作为一个统一的模块。算子模块由选择、重组或交叉、变异三个子模块组成是工具箱的核心计算部分。结果显示模块以多种方式如图形、图表等，直观、快捷地显示算法运算的结果，要求做到一边计算、一边显示。参数输人模块负责输人和调整遗传算法的各种选项和参数。为了减少人工干预，工具箱设有基于经验的默认的选项和参数。监督和参数调整模块用于监督算法的运行情况，动态调整参数，使算法始终高效运行。整个工具箱的模块结构和运行过程可以用图2来表示。

我设计的工具箱既具有相当的通用性，又具有相当的灵活性。通用性体现在工具箱基本实现了遗传算法的各种算子的改进及其大多数重要的改进算法。用户不用编程就可以方便地使用工具箱来解决自己特定的问题。灵活性一方面体现在用户可以在多种改进算法中自如地选择，加以组合;另一方面体现在用户还可以很容易地添加自已编写的新算法。因此，我称之为通用遗传算法工具箱。
2.2遗传算法工具箱的具体实现——任务文件和子任务的设计
在系统结构的具体实现上，我借鉴了script的思想，设计了一套以任务文件为核心的运行机制运行遗传算法，首先要定义任务文件。任务文件具有特定的格式，可以使用工具箱的用户界面方便地生成，也可以手工编写。任务文件记录了问题的定义，变量的搜索域，每个算子选用的具体算法及参数，以及其它一些选项。它包括了遗传算法运行所需要的全部信息，指定了一个任务文件，实际上也就指定了一次遗传算法的运行。相应的，执行程序负责读人任务文件的内容，对于用户没有指定的信息，则执行默认的选项或参数，运行这个任务文件所指定的算法来求解问题，并返回所得的结果。运行中还会产生一些动态信息，这些动态信息被记录下来，一方面用于显示给用户，供用户查看和分析：另一方面用于算法的动态调整。随后，在工具箱中又引人了子任务的概念。具体来说，就是在运行一个任务文件的过程中，可以再插人其它的若干个任务文件，称为子任务。甚至子任务还可以再插人下一级的任务文件。这样就形成了任务文件的嵌套。如图3所示。

通过进一步引人子任务的设计，可以实现两类算法。一类是多种群的算法，每个子任务都代表一个种群;另一类则是分层遗传算法，父任务代表高层的遗传算法，子任务代表低层的遗传算法。随着工具箱的发展，甚至可以考虑把不同的任务放到不同的机器上运行，从而实现并行的遗传算法。下面给出一个使用子任务的任务文件例子，其内容及解释如下：
Popu:init[50]表示种群需要初始化，种群的规模为50
Bounds:[-1,2]表示单变量优化，变量范围为[-1,2]
Coding:Binary表示编码方式为二进制方式
EvalFun:x*sin(10*pi*x)+2.0[]表示目标函数为f(x)=xsin(IOrzx)+2.0
CycleBegin:maxGenTerm40表示循环开始，循环的结束函数及其参数]
Select:RouletteSelect[]表示选择函数及其参数
Crossover:SimpleXover[0.8]表示交叉函数及其参数
Mutation:BinaryMutadon[0.05]表示变异函数及其参数
Subtask:one.Task60%表示某一子任务的任务文件和个体所占比例
Subtask:two.Task40%表示某一子任务的任务文件和个体所占比例
ElitistReserve:on表示使用最优保留策略
End表示循环结束
InformCollect:on表示打开运行信息收集选项
2.3工具箱对自适应性的支持
在工具箱中，把自适应的特性加以规范，把自适应性总结为对主要算法参数的调整，即所谓动态参数，并且把对参数的调整与主要算法相分离，使整个程序更为模块化，便于替换和扩充。
在工具箱中，可以对选择、交叉和变异这三种主要算子的参数进行自适应调整，方法是选定三个自适应调整函数，在任务文件中分别指定。在程序运行时，如果存在这三个自适应调整函数，则运行这些函数，并将其结果分别作为选择、交叉和变异算子的参数，代人到选择、交叉和变异的算法中运行;否则将使用选择、交叉和变异算子默认的参数。
以Srinvivas等提出的自适应遗传算法为例。遗传算法的参数中，交叉概率P和变异概率凡的选择是影响遗传算法行为和性能的关键参数，直接影响算法的收敛性，P越大，新个体产生的速度就越快。然而，P过大时遗传模式被破坏的可能性就越大，使得具有高适应度的个体结构很快就被破坏;但是如果P过小，会使搜索过程缓慢，以至停滞不前。对于变异概率P，如果P的过小，就不易产生新结构；如果P的取值过大，那么遗传算法就趋向于随机搜索了。为了避免选择合适P和P的麻烦，Srinvivas提出了自适应遗传算法，让几和凡的值能随适应度自动改变。当种群个体适应值趋于一致或者趋于局部最优时，使P和凡的值增加，当群体适应度比较分散时，使P和凡的值减少。同时，对于适应值高于群体平均适应值的个体，对应于较低的P和凡的值，使该解得以保护进人下一代，而低于群体平均适应度的个体，相对于较高的典和凡，使该解被淘汰掉。因此，自适应的P和凡能够提供相对某个问题的最佳的P和凡。自适应遗传算法在保持种群多样性的同时，保证遗传算法的收敛性。在自适应遗传算法中，Pc和Pm如下公式进行自适应调整:

其图如图4和5所示。

下面我给出使用和不使用自适应变异率的算法运行情况比较:
不使用自适应变异率的算法，其变异率固定为0.05;而使用自适应变异率的算法，其变异率则在[0.03,0.1]之间自动变动，两种算法的其余参数均相同。下图是其结果的对比，虚线表示最佳个体的适应度，实线表示全部个体平均的适应度。上面一对虚实线是自适应变异率的算法结果;下面一对虚实线是固定变异率的算法结果。可以看出自适应变异率的算法的效果要明显优于固定变异率算法的效果。

工具箱还实现了对运行动态参数的支持，可以在任何一个函数运行时将进化代数等运行动态数值作为参数。具体方法是在填写函数参数时，不填写具体数值，而是填写“gen”等变量名，在函数执行时，工具箱会自动将变量名解释为当前变量值，代人函数运行。当然，这些变量的是预置好的，其名称也是固定的。
2.4一种基于距离的Paret。
最优解算法使用遗传算法工具箱还可以实现对多目标优化的支持。现实中经常会遇到在多准则或多设计目标下设计和决策的问题，通常这些目标是无法同时达到最优的，而又需要找到全面满足这些目标的最佳设计方案。解决多目标和多约束的优化问题，即多目标优化。通常的做法是根据某加权评价函数将多目标合成单一目标来进行优化。但大多数情况下，在优化之前这种加权值是难以确知的。这样为了使决策者深人掌握优化问题的特点，有必要提供不同权值情况下相应的最优解，以便于做出合理的最终选择。
法国经济学家VPareto最早研究经济领域内的多目标优化问题，他的理论被称之为Pareto最优性理论。通过优化一组费用函数，其解不是单一点，而是一组点的集合，称之为Paret最优集。Pareto最优集中的点具有这样的特点，没有点在所有目标上都比集里的点好。

工具箱提供了一种合理简明的求Pareto最优解的算法，基于距离的Pareto最优算法。假设已经存在一组Pareto解，这些解构成了一个Pareto边界以这个边界为基准，赋予所有可行解一个标量，我称之为此可行解的逼近度，这个逼近度表示某一个可行解到Pareto边界的距离，有可能是正，也有可能是负。这个距离是这样定义的。把可行解看作是搜索空间里的一个点，搜索空间就是所有可行解的集合。当前Pareto边界把整个搜索空间分成了三个部分，一部分称为Pareto正空间，这里的点Pareto优于当前Pareto边界上的至少一个点；另一部分称为Pareto负空间，这里的点劣于Pareto边界上的至少一个点。还有一部分，这里的点即不优于当前Paret。边界上的某一点，也不劣于当前Pareto边界上的某一点，我称为Paret边界区。任意一个新个体，必定落在这三个区域中的某一个里。在这三种情况下，分别计算这个可行解到Pareto边界的逼近度。A)此点落在Pareto正空间，则逼近度为正，其大小为计算此点到所有当前Pareto解的距离，其中最小的一个距离就是逼近度的大小。B)此点落在Pareto负空间，则逼近度为负，其大小为计算此点到所有当前Pareto解的距离，最小的一个距离就是逼近度的大小。C)此点落在Pareto边界区，即此点可以作为一个Pareto边界点，则此点的逼近度为零。
此时，已经可以把这个逼近度作尺度变换后全部变换成正值，作为个体的适应度，进行遗传算法的运算了。但是，这么做有一个问题在于Pareto边界是不断更新的，一般说来每一代都不一样，于是不同代种群个体的逼近度是无法直接比较的，于是尺度变换后的适应度也无法比较。所以需要找到一个全局标准的适应度，使得可以比较不同代的种群个体的适应度，从而使用户可以直观清楚地观察到种群是如何不断进化的，也就是适应度是如何随着进化的进行而增加的。工具箱采用的方法是每进化一代，计算此代落在Pareto正空间的全部点的逼近度的均值，并将这个均值除以了N1/2（N为目标的个数），以此值作为此代Pareto边界近似的进化值。任一可行解的适应度定义为此前全部代Pareto边界的进化值的和加上此可行解对当前Paret。边界的逼近度除以了N1/2。如图7所示。

此算法提出了一个全局的表示Pareto多目标优化中进化程度的标量，从而使进化过程直观清晰第二是由于有单维的适应度，使得单目标的遗传算法和多目标的遗传算法在程序结构上实现了统一，全部的改进算法无需任何更改就既可以用于单目标，又可以用于多目标，大大简化了工具箱的编写和改进。而且，这种方法得到的适应度具有明确的物理意义，且与目标的个数无关，计算效率较高。

图8为一个工具箱的多目标Pareto优化结果图，需要最大化的两个目标X和Y满足如下的关系X*Y=10。实线为理论Pareto解，虚线为工具箱求得的Pareto解。由图可见，工具箱的解在绝大部分情况下已经非常接近理论解。