自然界始终是人类灵感的重要来源。仿生学直接模仿生物界的现象和原理，而另外一些研究方向则起源于对自然现象或过程的模拟，如控制论，人工神经网络，模拟退火算法，元胞自动机等。
遗传算法（geneticalgorithms）也是其中之一。早在20世纪50年代就有将进化原理应用于计算机科学的努力，但缺乏一种普遍的编码方法，只能依赖于变异而非交配产生新的基因结构。50年代末到60年代初，受一些生物学家用计算机对生物系统进行模拟的启发，Holland开始应用模拟遗传算子研究适应性。在Bagley1967年关于自适应下棋程序的论文中，他应用遗传算法搜索下棋游戏评价函数的参数集，并首次提出了遗传算法这一术语。1975年Holland出版了遗传算法历史上的经典著作《自然和人工系统中的适应性》，系统阐述了遗传算法的基本理论和方法，并提出了模式定理（schematatheorem），证明在遗传算子选择、交叉和变异的作用下，具有低阶、短定义距以及平均适应度高于群体平均适应度的模式在子代中将以指数级增长，这里的模式是某一类字符串，其某些位置有相似性。同年，DeJong完成了他的博士论文《遗传自适应系统的行为分析》，将Holland的模式理论与他的计算试验结合起来，进一步完善了选择、交叉和变异操作，提出了一些新的遗传操作技术。
进入80年代后，遗传算法得到了迅速发展，不仅理论研究十分活跃，而且在越来越多的应用领域中得到应用。1983年，Holland的学生Goldberg将遗传算法应用于管道煤气系统的优化，很好地解决了这一非常复杂的问题。1989年，Goldberg出版了《搜索、优化和机器学习中的遗传算法》一书，这本可能是遗传算法领域被引用次数最多的书为这一领域奠定了坚实的科学基础。80年代中期，Axelrod和Forrest合作，采用遗传算法研究了博奕论中的一个经典问题--囚徒困境。在机器学习方面，Holland自提出遗传算法的基本理论后就致力于研究分类器系统（classifiersystem），Holland希望系统能将外界刺激进行分类，然后送到需要的地方去，因此命名为分类器系统，这里的classifier是指一个二进制串，代表一类情况。分类器系统将某一条件是否为真与串的某一位相对应，从而将产生式系统中的规则编码为二进制串，这样就可以应用遗传算法来进行演化，同时引入了基于经济学原理的信用分配机制--桶队（bucketbrigade）算法来确定规则的相对强度。Holland和SantaFe的Arthur等人合作，用分类器系统模拟了一些经济现象，得到了满意的结果。
遗传算法已有了许多发展，但一般来说，其基本过程是：首先采用某种编码方式将解空间映射到编码空间（可以是位串、实数、有序串、树或图，Holland最初的遗传算法是基于二进制串的，类似于生物染色体结构，易于用生物遗传理论解释，各种遗传操作也易于实现。另外，可以证明，采用二进制编码式，算法处理的模式最多。但是，在具体问题中，直接采用解空间的形式进行编码，可以直接在解的表现型上进行遗传操作，从而易于引入特定领域的启发式信息，可以取得比二进制编码更高的效率。实数编码一般用于数值优化，有序串编码一般用于组合优化。），每个编码对应问题的一个解，称为染色体或个体。一般通过随机方法确定起始的一群个体，称为种群，在种群中根据适应值或某种竞争机制选择个体（适应值就是解的满意程度，可以由外部显式适应度函数计算，也可以由系统本身产生，如由协同演化时不同对策的博奕确定，或者由个体在群体中的存活量和繁殖量确定。），使用各种遗传操作算子（包括杂交，变异，倒位等等）产生下一代（下一代可以完全替代原种群，即非重叠种群；也可以部分替代原种群中一些较差的个体，即重叠种群），如此进化下去，直到满足期望的终止条件。

从上面的原理可以看出，从搜索角度，遗传算法具有许多独特的优点：
l不必非常明确描述问题的全部特征，通用性和鲁棒性强，能很快适应问题和环境的变化；对领域知识依赖程度低，不受搜索空间限制性假设的约束，不必要求连续性、可导或单峰等。
l 从多点进行搜索，如同在搜索空间上覆盖的一张网，搜索的全局性强，不易陷入局部最优；具有隐并行性，非常适合于并行计算。

在遗传算法的研究中，可以看到主要有三类研究方向：
1. 研究遗传算法本身的理论基础。
2. 用遗传算法作为工具解决工程问题，主要是进行优化，关心的是是否能在传统方法上有所提高。
3. 用遗传算法研究演化现象，一般涉及到人工生命和复杂性科学领域。

遗传算法的基本概念：

遗传算法是一类随机化算法，但是它不是简单的随机走动，它可以有效地利用已经有的信息处理来搜索那些有希望改善解质量的串，类似于自然进化，遗传算法通过作用于染色体上的基因，寻找好的染色体来求解问题。与自然界相似，遗传算法对待求解问题本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并基于适应度值来造反染色体，使适用性好的染色体比适应性差的染色体有更多的繁殖机会。

基因：组成染色体的单元，可以表示为一个二进制位，一个整数或一个字符等。

染色体或个体：表示待求解问题的一个可能解，由若干基因组成，是GA操作的基本对象。

群体：一定数量的个体组成了群体，表示GA的遗传搜索空间。

适应度或适度：代表一个个体所对应解的优劣，通常由某一适应度函数表示。

选择：GA的基本操作之一，即根据个体的适应度，在群体中按照一定的概论选择可以作为父本的个体，选择依据是适应度大的个体被选中的概率高。选择操作体现了适者生存，优胜劣汰的进化规则。

交叉：GA的基本操作之一，即将父本个体按照一定的概率随机地交换基因形成新的个体。

变异：GA的基本操作之一，即即按一定概率随机改变某个体的基因值。

在工程实践中的遗传算法应用主要是利用了其并行性和全局搜索的特点来进行优化。尽管遗传算法本身是一种通用弱方法，仍需要尽量结合特定领域的知识，实现解决特定问题的一个遗传算法特定实现，其范围可能更窄，但效果会更好。不过，我认为，从遗传算法的来源--自然界现象看，生物演化的目的并非取得某一限制条件下的某些参数的最优，而是适应环境。生物进化的途径多种多样，没有哪一种是最优的，但是，成功的生物必然是适应其环境和环境内的其它生物的，对于环境的演化和其它生物的进化（它自己也在改变着环境，人类更是前所未有地改变着环境），它能够适应新的变化，继续生存。从这一角度看，虽然目前工程实践上遗传算法的主要应用是用于优化，我认为遗传算法的真正威力却不在于此。
鉴于遗传算法和生物演化现象的紧密关系，人工生命和复杂性科学的研究与遗传算法有着极其密切的联系。在演化现象中，我感兴趣的方面主要有协同演化，学习与进化的相互作用等。
l协同进化。进化的目标不是形成一个超级物种，一个生态环境进化的结果是物种与环境相互适应、相互影响的复杂系统，虽然遗传算法被大量用于优化，但进化的目标不是优化而是适应。因此，应该研究多个物种在共同的生态环境中的协同进化。对应到遗传算法，这可以用于多目标的优化。
l 学习与进化的相互作用。可以将学习分为以下几种：（1）宗亲（phylogeneticlearning）学习：通过血亲遗传将祖先的特征遗传给后代。（2）社团学习（sociogeneticlearning）：经验和知识在群体（社团）中的共享。（3）个体学习（ontogeneticlearning）：个体生存过程中的学习。按照现代进化论的观点，自然界生物的进化主要发生于基因型，个体学习和社团学习的结果不能影响基因型，无法通过获得性遗传直接遗传给后代。然而，有些进化生物学家研究了学习对进化的间接影响，尤其著名的是"Baldwin"效应。其基本思想是：如果学习有助于生存，那么学习的最好的有机体将有最多的后代，从而影响到与学习有关的基因在种群中的频率。也就是说，获得某种所需特性的能力使有机体更能生存，从而给了基因突变独立发现所需特性的机会。但是，除了生物界的有性生殖、突变、染色体互换和倒置等等基于生理结构的进化机制外，人类社会还存在基于社会文化的进化机制，个体在社会中的学习，幼体的成长过程中对历史和文化的学习都是人类社会特有的更高级的进化机制。我们希望能在遗传算法中体现学习与进化的相互作用。

附：遗传算法简介

遗传算法发展的简要回顾
1950s，将进化原理应用于计算机科学的初步努力。
50年代末到60年代初，Holland应用模拟遗传算子研究适应性。
1967年，Bagley的论文中首次提出了遗传算法这一术语。
1975年，Holland的经典著作《自然和人工系统中的适应性》出版，系统阐述了遗传算法的基本理论和方法。
1975年，DeJong的博士论文《遗传自适应系统的行为分析》，将Holland的模式理论与他的计算试验结合起来。
1983年，Holland的学生Goldberg将遗传算法应用于管道煤气系统的优化，取得了很好的效果。

遗传算法的一些应用领域

应用领域
说明

控制
煤气管道控制，防避导弹控制，机器人控制

规划
生产规划，并行机任务分配

设计
VLSI布局，背包问题，图划分问题

图像处理
模式识别，特征抽取

信号处理
滤波器设计

机器人
路径规划

人工生命
生命的遗传进化

人工神经网络
权值训练和网络结构生成

遗传算法的基本过程：
首先采用某种编码方式将解空间映射到编码空间，每个编码对应问题的一个解，称为染色体或个体。一般通过随机方法确定起始的一群个体，称为种群，在种群中根据适应值或某种竞争机制选择个体，使用各种遗传操作算子产生下一代如此进化下去，直到满足期望的终止条件。

一个串行运算的遗传算法(Seguential Genetic Algoritm, SGA)按如下过程进行：

(1) 对待解决问题进行编码；
(2) 随机初始化群体X(0):=(x1, x2, … xn)；
(3) 对当前群体X(t)中每个个体xi计算其适应度F(xi)，适应度表示了该个体的性能好
坏；
(4) 应用选择算子产生中间代Xr(t)；
(5) 对Xr(t)应用其它的算子，产生新一代群体X(t 1)，这些算子的目的在于扩展有限
个体的覆盖面，体现全局搜索的思想；
(6) t:=t 1；如果不满足终止条件继续(3)。
GA中最常用的算子有如下几种：
(1) 选择算子(selection/reproduction): 选择算子从群体中按某一概率成对选择个
体，某个体xi被选择的概率Pi与其适应度值成正比。最通常的实现方法是轮盘赌(roulett
e wheel)模型。
(2) 交叉算子(Crossover): 交叉算子将被选中的两个个体的基因链按概率pc进行交叉
，生成两个新的个体，交叉位置是随机的。其中Pc是一个系统参数。
(3) 变异算子(Mutation): 变异算子将新个体的基因链的各位按概率pm进行变异，对
二值基因链(0,1编码)来说即是取反。
上述各种算子的实现是多种多样的，而且许多新的算子正在不断地提出，以改进GA的
某些性能。系统参数(个体数n,基因链长度l,交叉概率Pc,变异概率Pm等)对算法的收敛速度
及结果有很大的影响，应视具体问题选取不同的值。
GA的程序设计应考虑到通用性，而且要有较强的适应新的算子的能力。OOP中的类的继
承为我们提供了这一可能。
定义两个基本结构：基因(ALLELE)和个体(INDIVIDUAL)，以个体的集合作为群体类TP
opulation的数据成员，而TSGA类则由群体派生出来，定义GA的基本操作。对任一个应用实
例，可以在TSGA类上派生，并定义新的操作。

TPopulation类包含两个重要过程：
FillFitness: 评价函数，对每个个体进行解码(decode)并计算出其适应度值，具体操
作在用户类中实现。
Statistic: 对当前群体进行统计，如求总适应度sumfitness、平均适应度average、最好
个体fmax、最坏个体fmin等。

TSGA类在TPopulation类的基础上派生，以GA的系统参数为构造函数的参数，它有4个
重要的成员函数：
Select: 选择算子，基本的选择策略采用轮盘赌模型（如图2）。轮盘经任意旋转停止
后指针所指向区域被选中，所以fi值大的被选中的概率就大。
Crossover: 交叉算子，以概率Pc在两基因链上的随机位置交换子串。
Mutation: 变异算子，以概率Pm对基因链上每一个基因进行随机干扰(取反)。
Generate: 产生下代，包括了评价、统计、选择、交叉、变异等全部过程，每运行一
次，产生新的一代。

SGA的结构及类定义如下(用C 编写)：
[code] typedef char ALLELE; // 基因类型
typedef struct{
ALLELE *chrom;
float fitness; // fitness of Chromosome
}INDIVIDUAL; // 个体定义

class TPopulation{ // 群体类定义
public:
int size; // Size of population: n
int lchrom; // Length of chromosome: l
float sumfitness, average;

INDIVIDUAL *fmin, *fmax;
INDIVIDUAL *pop;

TPopulation(int popsize, int strlength);
~TPopulation();
inline INDIVIDUAL &Individual(int i){ returnpop[i];};
void FillFitness(); // 评价函数
virtual void Statistics(); // 统计函数
};

class TSGA : public TPopulation{ // TSGA类派生于群体类
public:
float pcross; // Probability of Crossover
float pmutation; // Probability of Mutation
int gen; // Counter of generation

TSGA(int size, int strlength, float pm=0.03, floatpc=0.6):
TPopulation(size, strlength)
{gen=0; pcross=pc; pmutation=pm; } ;
virtual INDIVIDUAL& Select();
virtual void Crossover(INDIVIDUAL &parent1,INDIVIDUAL &parent2,
INDIVIDUAL &child1, INDIVIDUAL&child2);
&child1, INDIVIDUAL &child2);
virtual ALLELE Mutation(ALLELE alleleval);
virtual void Generate(); // 产生新的一代
};
用户GA类定义如下：
class TSGAfit : public TSGA{
public:
TSGAfit(int size,float pm=0.0333,float pc=0.6)
:TSGA(size,24,pm,pc){};
void print();
}; [/code]

由于GA是一个概率过程，所以每次迭代的情况是不一样的；系统参数不同，迭代情况
也不同。在实验中参数一般选取如下：个体数n=50-200，变异概率Pm=0.03, 交叉概率Pc=
0.6。变异概率太大，会导致不稳定。