遗传算法 (genetic algorithm, GA )是计算数学中用于解决最佳化的搜索算法，是进化算法的一种。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的，这些现象包括遗传、突变、自然选择以及杂交等。遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。最早由美国密执安大学的Holland 教授提出，起源于60年代对自然和人工自适应系统的研究。70年代De Jong 基于遗传算法的思想在计算机上进行了大量的纯数值函数优化计算实验。在一系列研究工作的基础上，80年代由Goldberg 进行归纳总结，形成了遗传算法的基础框架。

生物学基础

生物在自然界中的生存繁衍，显示出了其对自然环境的优异自适应能力。受其启发，人们致力于对生物各种生存特性的机理研究和行为模拟，为人工自适应系统的设计和开发提供了广阔的前景。遗传算法就是这种生物行为的计算机模拟中的重要成果。基于对生物遗传和进化过程的计算机模拟，遗传算法使得各种人工系统具有优良的自适应能力和优化能力。遗传算法所借鉴的生物学基础就是生物的遗传和进化。

遗传与变异

世间万物从其亲代继承特性或性状，这种生命现象就成为遗传（Heredity），研究这种生命现象的科学称之为遗传学。由于遗传的作用，使得人们可以种瓜得瓜种豆得豆，也使得鸟能在天空中飞翔，鱼能在水中遨游。

构成生物的基本结构和功能的单位是细胞（Cell）。细胞中含有的一种微小的化合物称为染色体（Chromosome），生物的所有遗传信息均包含在这个复杂而又微小的染色体中。遗传信息是由基因（Gene）组成的，生物的各种性状由其对应的基因所控制，基因是遗传的基本单位。细胞通过分裂具有自我复制的能力，在细胞分裂的过程中，其遗传基因也被下一代所继承。经生物学家研究，现在人们已经明白控制并决定生物遗传性状的染色体主要由一种叫做DNA的物质所构成，除此之外，染色体中还含有大量的蛋白质。DNA在染色体中有规则的排列着，其基本单位是核苷酸。

遗传基因在染色体中所占有的位置称为基因座（Locus），同一基因座可能有的全部基因称为等位基因（Allele）。某种生物所特有的基因及其构成形式称为该生物的基因型，而该生物在环境中呈现出的相应的性状称为该生物的表现型。

细胞在分裂时，DNA通过复制（Reproduction）而转移到新产生的细胞中，新细胞就继承了旧细胞的基因。有性生殖生物在繁殖下一代时，两个同源染色体之间通过交叉（Crossover）而重组，即在两个染色体的某一相同位置处DNA被切断，其前后两串分别交叉组合而形成两个新的染色体。另外，在细胞复制时，虽然概率很小，但也有可能产生某些复制差错，从而使DNA发生某种变异（Mutation），产生出新的染色体。这些新的染色体表现出新的性状。如此，遗传基因或染色体在遗传的过程中由于各种各样的原因而发生变化。

进化

生物在其延续生存的过程中，逐渐适应于其生存环境，使得其品质不断得到改良，这种生命现象称之为进化（Evolution）。生物的进化是以集团的形式共同进行的，这种的一个团体称为群体（Population），组成群体的单个生物称为个体（Individual），每一个个体对其生存环境都有不同的适应能力，这种适应能力称之为个体的适应度（Fitness）。达尔文的自然选择学说构成了现代进化论的主体。自然选择学说认为，通过不同生物之间的交配及其他一些原因，生物的基因有可能发生变异而形成一种新的生物基因，这部分变异了的基因也有可能将遗传到下一代。虽然这种变化的概率是可以预测的，但具体哪一个个体发生变化却是偶然的。这种新的基因依据其与环境的适应程度决定其生殖能力，有利于生存环境的基因逐渐增多，而不利于生存环境的基因逐渐减少。通过这种自然的选择，物种将逐渐地向适应于生存环境的方向进化，从而产生出优良的物种。

遗传与进化系统观

生物的所有遗传信息均包含在其染色体中，染色体决定了生物的性状；
染色体是由基因及其有规律的排列所构成的，遗传和进化过程发生在染色体上；
生物的繁殖过程是由其基因的复制过程来完成的；
通过同源染色体之间的交叉或染色体的变异会产生新的物种，使生物呈现新的性状；
对环境适应性好的基因或染色体经常比适应性差的基因或染色体有更多的机会被遗传到下一代。

遗传算法

最优化问题

对于一个求函数最大值优化问题（最小值类似），一般可描述为下述数学规划模型： $max f(X)$

$s.t. X\in R$ $R\subseteq U$

式中，X 为决策变量，f(X) 为目标函数。对于这些最优化问题，目标函数和约束条件种类繁多，有的是线性的，有的是非线性的；有的是连续的，有的是离散的；有的是单峰值的，有的是多峰值的。随研究的深入，人们逐渐认识到很多复杂情况下要想完全精确地求解出最优解既不可能也不现实，因而求出其近似最优解或满意解是人们的主要着眼点之一。总体来讲，求最优解或近似最优解的方法主要有三种：枚举法、启发式算法和搜索算法。

遗传算法优化思路

遗传算法中，将n维决策向量 $X = [x_1, x_2, ..., x_n]^T$ 用 n 个记号 $X_i(i = 1, 2, ..., n)$ 所组成的符号串X 来表示： $X=X_1X_2...X_n \Rightarrow X=[x_1, x_2, ..., x_n]^T$ 把每一个 $X_i$ 看作是一个遗传基因，它的所有的可能取值称为等位基因，这样，X 就可看做是由n 个遗传基因所组成的一个染色体。一般情况下，染色体的长度n 是固定的，但对一些问题来讲，n 有可能是变化的。染色体 $X$ 也称为个体 $X$ ，对于每一个个体，要按照一定的规则确定其适应度。个体的适应度与其对应的个体表现型 $X$ 的目标函数值相关联， $X$ 越接近于目标函数的最优点，其适应度越大；相反，其适应度越小。

遗传算法中，决策变量 $X$ 组成了问题的解空间。对于问题最优解的搜索是通过对染色体 $X$ 的搜索过程来进行的，从而有所有的染色体 $X$ 就组成了问题的搜索空间。

生物的进化是以集团为主体的。与此相对应，遗传算法的运算对象是由 $M$ 个个体所组成的集合，称之为群体。与生物一代一代的自然进化过程相类似，遗传算法的运算过程也是一个反复迭代的过程，第 $t$ 代群体记作 $P(t)$ ，经过一代遗传和进化后，得到第 $t+1$ 代群体，它们也是由多个个体组成的集合，记作 $P(t+1)$ 。这个群体不断地经过遗传和进化操作，并且每次都按照优胜劣汰的规则将适应度较高的个体更多的遗传到下一代，这样最终在群体中将会得到一个优良的个体 $X$ ，它所对应的表现型 $X$ 将达到或接近于问题的最优解 $X^*$ 。

生物的进化过程主要是通过染色体之间的交叉和变异来完成的，与此相对应的，遗传算法中最优解的搜索过程也模仿了生物的这一进化过程，使用所谓的遗传算子作用于群体 $P(t)$ 中，进行下述操作，从而得到新一代群体 $P(t+1)$ 。

选择（Selection）：根据每个个体的适应度，按照一定的规则，从第 $t$ 代群体 $P(t)$ 中选择出一些优良的个体遗传到下一代群体 $P(t+1)$ 中。
交叉（Crossover）：将群体中 $P(t)$ 内的每个个体随机搭配成对，对每个个体，以某种概率（交叉概率）交换它们之间的部分染色体。
变异（Mutation）：对群体 $P(t)$ 中的每个给他，以某种概率（变异概率）改变某一个或者某一些基因座上的基因值为其他的等位基因。

运算过程

步骤一 ：初始化。设置进化代数计数器 $t \leftarrow 0$ ;设置最大进化代数 $T$ ；随机生成 $M$ 个个体作为初始种群 $P(0)$ 。

步骤二：个体评价。计算群体 $P(t)$ 中各个个体的适应度。

步骤三：选择运算。将选择算子作用于群体。

步骤四：交叉运算。将交叉算子作用于群体。

步骤五：变异运算。将变异算子作用于群体。群体 $P(t)$ 通过选择、交叉、变异运算过后，得到下一代群体 $P(t+1)$ 。

步骤六：终止条件判断。若 $t \leq T$ ，则： $t \leftarrow t+1$ ，转到步骤二；若 $t > T$ ，则以进化过程中得到的具有最大适应度的个体作为最优解输出，终止计算。

特点

以决策变量的编码作为运算对象
直接以目标函数值作为搜索信息
同时使用多个搜索点的搜索信息
使用概率搜索技术

基本遗传算法

构成要素

染色体编码方法。基本遗传算法使用固定长度的二进制符号串来表示群体中的个体，其等位基因是由二进制符号集 ${0, 1}$ 所组成的。初始群体中各个个体的基因值可用均匀分布的随机数来生成。如 $X=100111001000101101$ 就可以表示一个个体，该个体的染色体长度是18。
个体适应度评价。基本遗传算法按与个体适应度成正比的概率来决定当前群体中每个个体遗传到下一代群体中的机会多少。为了正确计算这个概率，这里要求所有个体的适应度必须为正数或者零。
遗传算子。基本遗传算法使用下述三种遗传算子：

选择运算使用比例选择算子；
交叉运算使用单点交叉算子；
变异运算使用基本位变异算子或均匀变异算子。

基本遗传算法的运行参数：

$M$ ：群体大小，即群体中所含个体的数量，一般取20~100；
$T$ ：遗传运算的终止进化代数，一般取100~500；
$P_c$ ：交叉概率，一般取值为0.4~0.99；
$P_m$ ：变异概率，一般取值为0.0001~0.1。

伪代码描述

Procedure SGA
begin
  initialize P(0)
  t = 0;
  while(t <= T) do
    for i=1 to M do
      Evaluate fitness of P(t)
    end for
    for i=1 to M do
      Select operation to P(t)
    end for
    for i=1 to M/2 do
      Crossover operation to P(t)
    end for
    for i=1 to M do
      Mutation operation to P(t)
    end for
    for i=1 to M do
      P(t+1) = P(t)
    end for
    t = t+1;
  end while
end

形式化定义

基本遗传算法可定义为一个八元组： $SGA = (C, E, P_0, M, \Phi, \Gamma, \Psi, T)$ 式中 $C$ –个体的编码方法； $E$ –个体适应度评价函数； $P_0$ –初始种群； $M$ –种群大小； $\Phi$ –选择算子； $\Gamma$ –交叉算子； $\Psi$ –变异算子； $T$ –运算终止条件。

实现

个体适应度评价

在遗传算法中，以个体适应度的大小来确定该个体被遗传到下一代的概率。基本遗传算法使用比例选择算子来确定群体中各个个体遗传到下一代群体中的数量。为了正确计算不同情况下各个个体的遗传概率，要求所有的个体的适应度必须为正数或者零，不能是负数。

对于求目标函数最小值的优化问题，理论上只需简单地对其增加一个负号就可将其转换为目标函数最大值的优化问题，即 $min f(x) = max(-f(x))$ 当优化目标是求函数最大值，并且目标函数总取正数时，可以直接设定个体的适应度 $F(x)$ 就等于相应的目标函数值 $f(x)$ ，即 $F(x)=f(x)$ 为了满足适应度取非负数的要求，基本遗传算法一般采用下面两种方法之一将目标函数值$f(x)$ 变换为个体的适应度 $F(x)$ 。

方法一 对于求目标函数最大值的优化问题，变换方法为 $F(x) = f(x) + C_{min}, f(x)+C_{min}>0; F(x)=0,f(x)+C_{min} <= 0$ 式中， $C_{min}$ 为一个适当相对比较小的数，可用下面几种方法来选取。

预先指定的一个较小数；
进化到当前代为止的最小目标函数值；
当前代或者近几代群体中的最小目标函数值。

方法二 对于求目标函数最小值的优化问题，变换方法为 $F(x)=C_{max}-f(x),f(x)<C_{max};F(x)=0,f(x)>=C_{max}$ 式中， $C_{max}$ 为一个适当地相对比较大的数，可用下面几种方法获取：

预先指定的一个较大的数；
进化到当前代为止的最大目标函数值；
当前代或者近几代群体中的最大目标函数值。

比例选择算子

轮盘赌

先计算出群体中所有个体的适应度的总和；

其次计算出每个个体的相对适应度的大小，它即是各个个体被遗传到下一代的概率；

最后使用模拟赌盘操作（即0~1之间的随机数）来确定各个个体被选中的次数。

交叉算子

单点交叉算子

对群体中的个体进行两两随机配对；

对每对相互配对的个体，随机设置某一基因座之后的位置为交叉点；

对每对相互配对的个体，依设定的交叉概率在其交叉点出相互交换两个个体的部分染色体，从而产生出两个新的个体。

$A$ : 1 0 1 1 0 1 1 1

0 0 $\longrightarrow$ $A^{\prime}$ : 1 0 1 1 0 1 1 1

1 1

$B$ : 0 0 0 1 1 1 0 0

1 1 $\longrightarrow$ $B^{\prime}$ : 0 0 0 1 1 1 0 0

0 0

变异算子

基本位变异算子

对个体的每一个基因座，依据变异概率指定其为变异点；

对每个指定点，对其基因值做取反运算或用其等位基因值来替代，从而产生一个新的个体。

$A$ : 1 0 1 1 0 1 1 1 $\longrightarrow$ $A^{\prime}$ : 1 0 1 1 1 1 1 1

具体应用

第一步： 确定决策变量及其各种约束条件，即确定出个体的表现型和问题的解空间；

第二步： 建立优化模型，即确定出目标函数的类型及其数学描述形式或量化方法；

第三步： 确定表示可行解的染色体编码方法，即确定出个体的基因型及遗传算法的搜索空间；

第四步： 确定编码方法，即确定出由个体基因型到个体表现型的对应关系或转换方法；

第五步： 确定个体适应度的量化评价方法，即确定出由目标函数值到个体适应度的转换规则；

第六步： 设计遗传算子，即确定出选择运算、交叉运算、变异运算等遗传算子的具体操作方法；

第七步： 确定遗传算法的有关运行参数，即确定出遗传算法的 $M$ , $T$ , $P_c$ , $P_m$ 等参数。

遗传算法简述

关于遗传算法的一篇概述