爱华网(Genetic Algorithms)简介
一、遗传算法的历史和现状
遗传算法（Genetic Algorithms）是基于生物进化理论的原理发展起来的一种广为应用的、高效的随机搜索与优化的方法。其主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息。它是在70年代初期由美国密执根（Michigan）大学的霍兰（Holland）教授发展起来的。1975年霍兰教授发表了第一本比较系统论述遗传算法的专著《自然系统与人工系统中的适应性》（《Adaptation in Natural and Artificial Systems》）。遗传算法最初被研究的出发点不是为专门解决最优化问题而设计的，它与进化策略、进化规划共同构成了进化算法的主要框架，都是为当时人工智能的发展服务的。迄今为止，遗传算法是进化算法中最广为人知的算法。
近几年来，遗传算法主要在复杂优化问题求解和工业工程领域应用，取得了一些令人信服的结果，所以引起了很多人的关注，而且在发展过程中，进化策略、进化规划和遗传算法之间差异越来越小。遗传算法成功的应用包括：作业调度与排序、可靠性设计、车辆路径选择与调度、成组技术、设备布置与分配、交通问题等等。
（一）遗传算法的特点
遗传算法是解决搜索问题的一种通用算法，对于各种通用问题都可以使用。搜索算法的共同特征为：（1）首先组成一组候选解；（2）依据某些适应性条件测算这些候选解的适应度；（3）根据适应度保留某些候选解，放弃其他候选解；（4）对保留的候选解进行某些操作，生成新的候选解。在遗传算法中，上述几个特征以一种特殊的方式组合在一起：基于染色体群的并行搜索，带有猜测性质的选择操作、交换操作和突变操作。这种特殊的组合方式将遗传算法与其它搜索算法区别开来。
遗传算法还具有以下几方面的特点：
（1）遗传算法的处理对象不是参数本身，而是对参数集进行了编码的个体。此操作使得遗传算法可直接对结构对象进行操作。
（2）许多传统搜索算法都是单点搜索算法，容易陷入局部的最优解。遗传算法同时处理群体中的多个个体，即对搜索空间中的多个解进行评估，减少了陷入局部最优解的风险，同时算法本身易于实现并行化。
（3）遗传算法基本上不用搜索空间的知识或其它辅助信息，而仅用适应度函数值来评估个体，在此基础上进行遗传操作。适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定。这一特点使得遗传算法的应用范围大大扩展。
（4）遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导他的搜索方向。
（5）具有自组织、自适应和自学习性。遗传算法利用进化过程获得的信息自行组织搜索，时硬度大的个体具有较高的生存概率，并获得更适应环境的基因结构。
（二）遗传算法的运用领域
前面描述是简单的遗传算法模型，可以在这一基本型上加以改进，使其在科学和工程领域得到广泛应用。下面列举了一些遗传算法的应用领域：
（1）优化：遗传算法可用于各种优化问题。既包括数量优化问题，也包括组合优化问题。
（2）程序设计：遗传算法可以用于某些特殊任务的计算机程序设计，如元胞计算机。
（3）机器学习：遗传算法可用于许多机器学习的应用，包括分类问题和预测问题等，如预测天气或预测蛋白质的结构。
（4）经济学：应用遗传算法对经济创新的过程建立模型，可以研究投标的策略，还可以建立市场竞争的模型。
（5）免疫系统：应用遗传算法可以对自然界中免疫系统的多个方面建立模型，研究个体的生命过程中的突变现象以及发掘进化过程中的基因资源。
（6）生态学：遗传算法可以应用于对生态学的一些现象进行建模，包括生物间的生存竞争，宿主——寄生物的共同进化，共生现象，甚至包括生物学“军备竞赛”。
（7）进化现象和学习现象：遗传算法可以用来研究个体是如何学习生存技巧的，一个物种的进化对其他物种会产生何种影响等等。
（8）社会经济问题：遗传算法可以用来研究社会系统中的各种演化现象，例如在一个多主体系统中，协作与交流的是如何演化出来的。
二、遗传算法中的基本概念
群体（population）：又称种群、染色体群，个体（individual）的集合，代表问题的解空间子集。
串（string）及串空间：串是个体的表达形式，对应着遗传学中的染色体。对应实际问题的一个解。
群体规模（population size）：染色体群中个体的数目称为群体的大小或群体规模。
基因（gene）：是指染色体的一个片段，基因可以是一个数值、一组数或一串字符。
交换（crossover）：指在一定条件下两条染色体上的一个或几个基因相互交换位置。
交换概率：判断是否满足交换条件的一个小于1的阀值。
变异（mutation）：指在一定条件下随机改变一条染色体上的一个或几个基因值
变异概率：判断是否满足变异条件的一个小于1的阀值。
后代：染色体经过交换或变异后形成的新的个体。
适应度（fittness）：用来度量种群中个体优劣（符合条件的程度）的指标值，它通常表现为数值形式。
选择（selection）：根据染色体对应的适应值和问题的要求，筛选种群中的染色体，染色体的适应度越高，保存下来的概率越大，反之则越小，甚至被淘汰。
表1 生物遗传概念在遗传算法中的对应关系
生物遗传概念 遗 传 算 法 中 的 作 用
适者生存 在算法停止时，最优目标值的解有最大的可能被留住
个体（individual） 解
染色体（chromosome） 解的编码（字符串、向量等）
基因（gene） 接种每一分量的特征（如各分量的值）
适应性（fitness） 适应函数值
群体（population） 选定的一组解
种群（reproduction） 根据适应函数值选取的一组解
交配（crossover） 用过交换原则产生的一组新解的过程
变异（mutation） 编码的某一个分量发生变化的过程
三、实例分析
用遗传算法求解 的最大值，其中 ，x为整数。
解： （1）适应函数的构造
依据问题目标函数，构造适应函数为：F(x)=x2
运用转轮法选择种群。
假设群体所能容纳的最大规模为4
第i(i=1,2,…,4)个个体入选的概率公式为
计算第i个染色体的累积概率公式为 ；
（2）染色体表达
也即是确定染色体表示的编码形式。一个简单表示解的编码的方法是二进制编码，即0、1字符串。由于变量的最大值为31，因此可以采用5位数的二进制码。如：
10000→16 11111→31 01001→9 00010→2
（3）初始种群
随机地选取8个染色体组成一个群体：
x1=(00001) x2=(11001) x3=(01111) x4=(01000)
x5=(01010) x6=(01011) x7=(00010) x8=(11000)
(4)解码和染色体评估
解码是将二进制串转换为十进制数。
根据适应函数，各染色体的适值为：
F(x1)=1 F(x2)=625 F(x3)=225 F(x4)=64
F(x5)=100 F(x6)=121 F(x7)=4 F(x8)=576
各染色体的入选概率为：
P(x1)=0.0006 P(x2)=0.3642 P(x3)=0.1311 P(x4)=0.0373
P(x5)=0.0583 P(x6)=0.0705 P(x7)=0.0023 P(x8)=0.3357
各染色体的累积概率 为：
(5) 选择
由于群体最大规模为4，采用转轮赌法，旋转转轮4次，产生[0，1]间的4个随机数： 0.2471 0.4012 0.6452 0.8632
根据转轮方法，选出新一代种群，即
x1‘=(11001) x2‘=(11000) x3‘=(01111) x4‘=(01011)
(6)交换
假设交换概率规定为Pc=0.38,随机产生4个小于1的随机数：
0.12 0.54 0.33 0.75
每个随机数对应一个染色体。选取概率小于P1的染色体作为交换对象。在本题中为x1‘=(11001)和x3‘=(01111)。每个染色体包含5个二进制码，在区间[1，5]中随机产生1个整数：2。被选的染色体各从第二位断开，交换相对应的部分，由此可得到新一代染色体：
x5‘=（11111） x6‘=（01001）
（7）变异（突变）
假设突变概率规定为PT=0.24。类似交换操作过程，x2‘=(11000)被选为突变染色体。在区间[1，5]中随机产生1个整数：4。将被选的染色体的第四位串值取反，可以得到：x7‘=(11010)
至此，我们得到了新一代染色体群体：x1‘ x2‘ x3‘ x4‘ x5‘ x6‘ x7‘
重复第（3）步。直到循环次数达到预定次数。
四、遗传算法的实施步骤
（一）遗传算法的基本步骤为：
1、构造适应函数及选择规则的：适应函数基本上依据优化问题的目标函数而定。当适应函数确定以后，自然选择规律是以适应函数值的大小以及问题的要求来确定哪些染色体适应生存，那些被淘汰。通常以第i个个体入选种群的概率以及群体规模的上限来确定其生存与淘汰，这种方法称为转轮法。
转轮法是一种正比选择策略，能够根据与适应值成正比的概率选出新的种群。转轮法由以下四步构成：
（1）计算各染色体适应值f(xi)； (2)计算种群中所有染色体的适应值的和；
（3）计算各染色体的选择概率P(xi)； (4)计算各染色体的累积概率；
选择过程就是旋转转轮群体最大规模次数，每次按如下方式选出一个染色体来构造新的种群：
步骤一：在[0，1]区间内产生一个均匀分布的伪随机数r；
步骤二：若r ,则选第i个染色体xi，若 ，则选第i+1个染色体xi+1。
2、染色体表达（编码）：是指对优化问题的解进行编码。此处我们称一个解的编码为一个染色体，组成编码的元素称为基因。编码的目的主要是用于优化问题解的表现形式和利于之后遗传算法中的计算。
3、初始种群：由多个染色体组成具有一定群体规模的染色体集合或称解的集合。遗传算法将基于这个集合进行遗传操作，每一轮操作（包括交换、突变、选择）后生存下来的染色体组成新的种群，形成可以繁衍下一代的群体。
4、解码和染色体评估：运用适值函数计算种群（包括初始种群）中各染色体的适应值,计算各染色体的入选（生存）概率。
5、选择（selection）：以适应函数值的大小以及问题的要求来确定哪些染色体适应生存，那些被淘汰。生存下来的染色体形成可以繁衍下一代的新种群。判断是否满足问题要求，如果满足，停止操作，否则继续第6步以及后面的操作。
6、交换(crossover)：这一操作随机地选定一个位置，将两个染色体对应位置上的编码（基因）交叉互换，两个染色体得到两个后代。
7、变异（突变）(mutation)：这一操作随机地改变染色体中某一位置基因的值，一个染色体得到一个后代。这一步结束后，我们就得到了新一代染色体群体，重复第4、5、6、7步骤。
（二）几点说明
1、初始群体的选取
有些学者认为：初始群体应该随机选取，只有随机选取才能达到所有状态遍历，因而最优解在遗传算法的进化中最终得以生存。但是，种子的随机选取加大了进化的代数，延长了进化时间。有些认为应该用一些其他启发式算法或经验选择一些比较好的染色体种子作为初始群体。实际上，初始群体的选取，应根据实际问题来权衡。
2，中止规则
中止规则有三种情况：
（1）给定一个最大的遗传代数MAXGEN，算法迭代在达到MAXGEN时停止。
（2）给定问题一个下界LB的计算方法，当进化中达到要求的偏差x时，算法终止。
（3）当监控得到的算法再进化已无法改进解的性能，此时停止计算。
六、计算机编程实现遗传算流程图示例
变量符号说明：
{xi}表示群体，xi表示群体中的个体（染色体）；
n表示群体规模； n0表示最大群体规模；
P1为选取交换染色体的概率阀值； P2为选取突变染色体的概率阀值；
Pc表示交换概率； PT表示突变概率；
f(x)为适应度函数； P(xi)表示个体（染色体）生存概率；N 表示循环的代数； m表示记录循环代数的变量
i、j、h为记录循环次数的中间变量； k、L为记录交换和突变染色体数的变量；
ri、rj为小于1的随机数变量
遗传算法的理论基础——模式定理和积木假说
一、模式定理
遗传算法作为一种复杂问题的智能算法，它的本质、内涵是什么？或者说，是什么力量使得遗传算法具有强鲁棒性、高适应性及全优化性等特点？其中一个重要的理论基础就是霍兰（Holland）提出的基于二值串表示的Schema模式定理。
遗传算法的解通常是由若干部分组成的，每个部分可以看作
一个“积木（building block）”，从概括的角度，遗传算法遗传算法的工作机制可以描述为通过不断发掘、强化以及组合那些好积木，从而得到问题的解。这里隐含着一个意思，即好的解是由好的积木组成的。霍兰使用了一个专用的名词“模式”来代替那些“积木”，一个模式是指一组可以用0、1和通配符*组成的模板来描述的二进制串。
定义2（模式）：基于三值字符集{0、1、*}所产生的能描述具有某些结构相似的0、1字符串集的字符串称作模式。
一长度为5的字符串为例，模式*0001描述了在位置2、3、4、5具有形式“0001”的所有字符串，即{00001，10001}；又比如模式*1**0，描述了所有在位置2为“1”及位置5为“0”的字符串。由此可以看出，模式的概念为我们提供了一种简单地用于描述在某些位置上具有结构相似性的0、1字符串集合的方法。这里需要强调的是，“*”只是一个描述符，而并非遗传算法中实际的运算符号，它是为描述方便而引入的符号。通过模式，而将多个不同的串联系起来。
定义3（模式阶）：模式H中确定位置的个数称作该模式的模式阶（schema order），记作O(H)。
例如，模式011*1*的阶数为4，而模式0* * * * *的阶数为1。显然一个模式的阶越高，其所代表的集合所包含的个体数目越少，因而确定性越高。
定义4（定义距）：模式H中的第一个确定位置和最后一个确定位置之间的距离称作该模式的定义距（defining length），记作δ(H)。
比如模式011*1*的定义距为4，而模式0 * * * *的定义距为0。
模式定理中的几个符号说明：
设H是任一个模式，P(g)={x1(g), x2(g),…, xn(g)}表示第g代群体，其规模为n，xi(g)（其中i=1，2，…，n）是该群体中的第i个个体（染色体），长度（所包含的字符数）为L；S(H，g)表示在群体P(g)中与模式H相匹配的个体（染色体）的集合；m(H，g)表示集合S(H，g)中的个体（染色体）的数目；f(H，g)表示集合S(H，g)中个体的平均适应度函数，f(x)表示某一个体的适应度函数，有如下关系：
表示群体P(g)中个体的平均适应度函数，且具有如下表达式：
定理（模式定理）：设遗传算法的交换（交叉）概率和突变（变异）概率分别为Pc和，L为个体基因链码的长度，则在g+1代群体中具有H模板的染色体数的期望值为：
证明：
选择操作对模式的影响：
在算法选择过程中，一个个体是以概率 进行选择的，其中是某一个体的适应度。假设一代中群体的大小为n，且群体中的个体两两互不相同，则m(H,g)中所有个体被选择的总体概率为：。经选择后，在g+1代中与H相匹配的串（染色体）的个数的期望值为：，即
…………①
①式表明：一模式按照其平均适应值与群体平均适应值之比成比例而生长，那些高与群体平均适应值的模式将有更多的代表串，而低于群体平均适应值的模式在下一代的代表串将减少，二等与群体平均适应值的模式将保持相同的水平。
交换操作对模式的影响：
对于模式H来说，只有交换点落在定义距之外才能使该模式生存。在简单交换（单点交换）下的H被破坏的概率为。由于交换概率为Pc，因此模式H的生存概率为： 。
这样，在考虑了选择和交换操作之后，在g+1代中与H相匹配的串（染色体）的个数的期望值满足如下关系：
…………②
突变操作对模式的影响：
由于染色体链码在某一位置发生改变的概率为PT，则该位置不被破坏的概率为1-PT。而模式H在突变操作下若要不受破坏，则其中所有的确定位置必须保持不变，因此模式H保持不变的概率为：(1-PT)O(H)。当PT<<1时，模式H在突变操作后的生存概率为：
Ps=(1-PT)O(H)≈1-O(H)PT
综合上述，模式 H在选择、交换和突变的共同作用下，其后代个体的数目的期望值满足关系： …………③
将③式展开，忽略 ，就可以得到：
证毕。
通过对模式定理证明分析，我们可得到如下结论：
在选择、交换（交叉）和变异作用下，具有低阶、短定义距以及平均适应度高于群体适应度的模式在后代中将以指数级增长。
（二）积木（基因块）假说
由前面的模式定理可知，具有低阶、短定义距以及平均适应度高于群体适应度的模式在后代中将以指数级增长。这类模式在遗传算法中非常重要，我们称之为“积木”或“基因块”(building block)。如同搭“积木”一样，这些“好”的模式在遗传操作下相互拼接、结合，产生适应度更高的个体，从而找到更优的可行解。这正是“积木假说”（building block hypothesis）所揭示的内容。
假说（积木假说）：低阶、短定义距、高平均适应度的模式在遗传算子作用下，相互结合，能生成高阶、长定义距、高平均适应度的模式，可最终生成全局最优解。
由于上述结论并没有得到证明，因此被称为假说，而非定理。目前，已有大量的实践证据支持这一假说。尽管大量的证据并不等于理论证明，但至少可以肯定，对很多经常碰到的问题，遗传算法都是适用的。
前面的模式定理保证了在一定条件下较优的模式的样本数呈指数级增长，从而满足了寻找最优解的必要条件，即遗传算法存在找到全局最优解的可能性。而积木假说则指出了遗传算法具备找到全局最优解的能力。
MATLAB函数注释模板
function [output1,output2] = function_name(input1,input2,input3)
%FUNCTION_NAME - One line description of what the function or script performs (H1 line)
%Optional file header info (to give more details about the function than in the H1 line)
%Optional file header info (to give more details about the function than in the H1 line)
%
% Syntax: [output1,output2] = function_name(input1,input2,input3)
%
% Inputs:
% input1 - Description
% input2 - Description
% input3 - Description
%
% Outputs:
% output1 - Description
% output2 - Description
%
% Example:
% Line 1 of example
% Line 2 of example
% Line 3 of example
% Line 4 of example
%
% Other m-files required: none
% Subfunctions: none
% MAT-files required: none
%
% See al
so: OTHER_FUNCTION_NAME1, OTHER_FUNCTION_NAME2
% Author: Ren Xiaoyong
% Packaging Engineering, Xi'an University of Technology .
% email :horlab@sohu.com
% QQ: 170071606
% Website: http://horlab.yculblog.com
% December 2004; Last revision: 24-May-2005
%------------- BEGIN CODE --------------
Enter your executable matlab commands here
%------------- END OF CODE --------------
