摘　要： 运用MATLAB编程实现遗传算法，数值仿真验证了该实现方法的有效性，表明它能够对函数进行全局寻优。这种实现方法既可以熟悉MATLAB语言，又可以加深对遗传算法的认识和理解，以此来设计智能系统。
　　关键词： MATLAB 遗传算法 优化

　　遗传算法(Genetic Algoritms，简称GA)是以自然选择和遗传理论为基础，将生物进化过程中适者生存规则与群体内部染色体的随机信息交换机制相结合的搜索算法。自从1975年John H.Holland教授出版GA的经典之作“Adaptation in Natural and Artificial Systems”以来，GA已获得广泛应用。

1 遗传算法简介
　　遗传算法是具有“生成+检测”的迭代过程的搜索算法。基本流程如图1所示。可见，遗传算法是一种群体型操作，该操作以群体中的所有个体为对象。选择(selection)、交叉(crossover)和变异(mutation)是遗传算法的三个主要操作算子。遗传算法包含如下6个基本要素：
　　(1)参数编码：由于遗传算法不能直接处理解空间的解数据，因此必须通过编码将它们表示成遗传空间的基因型串结构数据。
　　(2)生成初始群体：由于遗传算法的群体型操作需要，所以必须为遗传操作准备一个由若干初始解组成的初始群体。初始群体的每个个体都是通过随机方法产生的。
　　(3)适应度评估检测：遗传算法在搜索进化过程中一般不需要其他外部信息，仅用适应度(fitness)值来评估个体或解的优劣，并作为以后遗传操作的依据。
　　(4)选择(selection)：选择或复制操作是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。个体适应度越高，其被选择的机会就越多。本文采用与适应度成比例的概率方法进行选择。具体地说，就是首先计算群体中所有个体适应度的总和(∑f)，再计算每个个体的适应度所占的比例(fi/∑f)，并以此作为相应的选择概率p_s。
　　(5)交叉操作：交叉操作是遗传算法中最主要的遗传操作。简单的交叉(即一点交叉)可分两步进行：首先对种群中个体进行随机配对；其次，在配对个体中随机设定交叉处，配对个体彼此交换部分信息。
　　(6)变异：变异操作是按位(bit)进行的，即把某一位的内容进行变异。变异操作同样也是随机进行的。一般而言，变异概率p_m都取得较小。变异操作是十分微妙的遗传操作，它需要和交叉操作配合使用，目的是挖掘群体中个体的多样性，克服有可能限于局部解的弊病。
2 基于MATLAB的遗传算法的实现
　　为简单起见，我们假设寻求一单变量函数F(x)的全局最优解，x对应于[a,b]，下面介绍实现步骤。
2.1 初始化
　　首先用二进制串表示初始种群中的个体，每一个体由一系列二进制位(0和1)组成，stringlength和popsize分别表示二进制序列的长度和初始种群的个体个数，每一个体用如图2的方式来编码，整个初始种群的数据结构由大小为popsize*(stringlength+2)的矩阵实现。
　　

　　第一列stringlength包括了初始真值x的二进制编码，该串是随机产生的，但必须满足在x的定义域[a,b]中，交叉和变异操作将会对此串进行操作，第(stringlength+1)和(stringlength+2)列分别包含x真值和x的适应度函数F(x)，于是用以下代码实现初始化过程：
　　function[pop]＝initialise(popsize,stringlength,fun);
　　 pop＝round(rand(popsize,stringlength+2));
　　 pop(:,stringlength+1)＝sum(2.＾(size(pop(;,1:stringlength),2)－1:－1:0).
　　pop(:,1:stringlength)(b－a)/(2.＾stringlength－1)+a;
　　pop(:,stringlength+2)＝fun(pop(;,stringlrngth+1);
　　end
　　在上面代码中，首先随机产生二进制串，然后用x的真值和目标函数填充到(stringlength+1)和(stringlength+2)中，其中fun为目标函数，以.m的文件形式存在。
2.2 交叉
　　交叉过程选取两个体作为父代parent1,parent2，产生出两新的子代个体child1和child2，pc表示交叉概率，交叉算子的实现过程如下：
　　function[child1,child2]＝crossover(parent1,parent2,pc);
　　　if(rand＜pc)
　　　　cpoint＝round(rand*stringlength－2))+1;
　　　　child1＝[parent(:,1:cpoint)parent2(:,cpoint1+1:stringlength)];
　　　　child2＝[parent2(:,1:cpoint)parent1(:,cpoint1+1:stringlength)];
　　　　child1(:,stringlength+1)＝sum(2.＾(size(child1(:,1:stringlength),2)－1:－1:0).
　　　　*child1(:,1:stringlength))*(b－a)/(2.＾stringlength－1)+a;
　　　　child2(:,stringlength+1)＝sum(2.＾(size(child2(:,1:stringlength),2)－1:－1:0).
　　　　*child2(:,1:stringlength))*(b－a)/(2.＾stringlength－1)+a;
　　　　child1(:,stringlength+2)＝fun(child1(:,stringlength+1));
　　　　child2(:,stringlength+2)＝fun(child1(:,stringlength+1));
　　　else
　　　　child1＝parent1;
　　　　child2＝parent2;
　　　end
　　end
　　在交叉过程的开始，先产生随机数与交叉概率相比较，如果随机数比pc小，则进行交叉运算，否则将不会进行交叉运算，直接返回父代。一旦进行交叉运算，交叉断点cpoint将在1和stringlength之间选取，交叉点cpoint是由随机函数在1和(stringlength－1)之间返回一伪随机整数，于是获得新的子代个体的真值和其适应度。
2.3 变异
　　变异操作由一个父代parent产生单个子代child，pm表示变异概率，如果在目前父代允许变异的情况下，我们选择变异点mpoint使该位取反，可同样获得新的子代的真值和适应度。
　　function[child]＝mutation(parent,pm);
　　if(rand＜pm)
　　mpoint＝round(rand*(stringlength－1))+1;
　　child＝parent;
　　child[mpoint]＝ads([parent[mpoint]－1);
　　child(:,stringlength+1)＝sum(2.＾(size(child(:,1:stringlength),2)－1:－1:0).
　　*child(:,1:stringlength))*(b－a)/(2.＾stringlength－1)+a;
　　child＝(:,stringlength+2)＝fun(child(:,stringlength+1);
　　else
　　child＝parent;
　　end
　　end
2.4 选择
　　选择或复制操作是决定哪些个体可以进入下一代。程序中采用赌轮盘选择法选择，这种方法较易实现。根据方程fi/∑f＞0计算出每个个体被选择的概率，向量prob包含了选择概率之和，向量rns包含归一化过的随机数，经过比较rns和prob向量中的元素，我们可以选择出进入下一代的个体。
　　function[newpop]＝roulette(oldpop);
　　totalfit＝sum(oldpop(:,stringlength+2);
　　prob＝oldpop(:,stringlength+2)/totalfit;
　　prob＝cumsum(prob);
　　rns＝sort(rand(popsize,1));
　　fitin＝1;newin＝1;
　　while newin＜＝popsize
　　if(rns(newin)＜prob(fitin))
　　newpop(newin,:)＝oldpop(fitin,:);
　　newin＝newin+1;
　　else
　　fitin＝fitin+1;
　　end
　　end
3 仿真例
　　为了验证基于MATLAB设计的遗传算法的全局寻优能力，举例验证。考虑一单变量函数为：
　　f(x)＝x+10*sin(5x)+7*cos(4x)          (2)
　　x∈[0,9]。按照上述方法，取popsize＝10,stringlength＝20,pc＝0.95,pm＝.08。图3为此函数的特性，图中‘+’表示随机产生的10个函数值；图4中‘o’为经过一代遗传，得到的寻优值；经过25代遗传运算，得到函数的全局最大值，如图5中的‘*’：即当x为7.8569时函数取得最大值24.8554。
　　本文用MATLAB语言实现了遗传算法的各项遗传操作，如交叉、变异和选择等，仿真例检验了该方法的有效性。采用这种方法既可以使大家熟悉MATLAB语言，又可以加深对遗传算法的认识和理解，以此来设计智能系统。

参考文献
1 D.E.Goldberg.Genetic algorithms in search,optimization and machine learning.Addison－Wesley,1989
2 孙增圻.智能控制理论与技术.北京：清华大学出版社，1997
3 席裕庚.遗传算法综述.控制理论及应用，1996，13(6)：697－708
4 Y.J.Cao,Q.H.Wu.Teaching Genetic Algorithm Using MAT－LAB.Int.Journal Electrical Engineering on Education,1998(2):139－152