遗传算法

引言

遗传算法（Genetic Algorithm，GA）是模拟生物在自然境中的遗传和进化的过程而形成的自适应全局优化的搜索算法。它借用了生物遗传学的观点，通过自然选择、遗传和变异等作用机制，实现各个个体适应性的提高。
遗传算法借鉴了达尔文进化论和孟德斯鸠的遗传学说。其本质是一种并行、高效、全局搜索方式，它能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最优解。

遗传算法基本概念

群体和个体:群体是生物进化过程中的一个集团，表示可行解集。个体是组成群体的单个生物体，表示可行解。

染色体和基因:染色体是包含生物体所有遗传信息的化合物，表示可行解的编码。基因是控制生物体某种性状（即遗传信息）的基本单位，表示可行解编码的分量。

遗传编码:遗传编码将优化变量转化为基因的组合表示形式，优化变量的编码机制有二进制编码、实数编码、格雷编码等。

适应度:适应度即生物群体中个体适应生存环境的能力。在遗传算法中，用来评价个体优劣的数学函数，称为个体的适应度函数。
遗传算法在进化搜索中基本上不用外部信息，仅以适应度函数为依据。它的目标函数不受连续可微的约束，且定义域可以为任意集合。对适应度函数的唯一要求是，针对输入可计算出能进行比较的结果。这一特点使得遗传算法应用范围很广。在具体应用中，适应度函数的设计要结合求解问题本身的要求而定。适应度函数评估是选择操作的依据，适应度函数设计直接影响到遗传算法的性能。常见的适应度函数构造方法主要有:目标函数映射成适应度函数，基于序的适应度函数等。

遗传操作，遗传操作是优选强势个体的“选择”、个体间交换基因产生新个体的“交叉”、个体基因信息突变而产生新个体的“变异”这三种变换的统称。

标准遗传算法

标准遗传算法又称为经典遗传算法，它的优化变量由二进制编码来描述，个优化变量的二进制编码串接在一起组成染色体，这种编码既适用于变异操作,又适用于交叉操作。在创建初始群体时，代表个体的二进制串是在一定字长的限制下随机产生的。交叉算子作用在按交叉概率选中的两个染色体上，随机选中交叉位置，将两个染色体上对应于这些位置上的二进制数值进行交换，生成两个新的个体;而变异算子作用在按变异概率随机选中的个体上，一般是随机选定变异位，将该位的二进制值取反，生成一个新的个体。

遗传算法的流程

遗传算法使用群体搜索技术，通过对当前群体施加选择，交叉变异等一些列遗传操作，从而产生出新一代的群体，并逐步使群体进化到包含或者接近最有解的状态。

具体步骤如下：
（1）初始化，设置进化代数计数器g=0，设置最大进化代数G，随机生成NP个个体作为初始群体P(0)。
（2）个体评价，计算群体P(t)中各个个体的适应度。
（3）选择运算，将选择算子作用与群体，根据个体的适应度，按照一定的规则和方法，选择一些优良的个体遗传到下一代群体。
（4）交叉运算，将交叉算子作用于群体，对选中的成对的个体，以某一概率交换它们之间的染色体，产生新的个体。
（5）变异运算，将变异算子作用于群体，对选中的个体，以某一概率改变一个或者某一些基因值为其他的等位基因。群体P(t)经过选择、交叉和变异运算之后得到下一代群体P(t+1)。计算其适应度值，并根据适应度值进行排序，准备进行下一次遗传操作。
（6）终止条件判断：若g≤G，则g=g+1，跳转到步骤（2）；若g>G，则此进化过程中所得到的具有最大适应度的个体作为最优解输出，终止计算。

关键参数说明

群体规模NP，NP太小，遗传优化性能一般不会太好，NP太大，虽然可以减小遗传算法陷入局部最优解的机会，但也会增加整体的计算量。一般取10~200。

交叉概率Pc：交叉概率Pc控制着交叉操作被使用的频度。较大的交叉概率可以增强遗传算法开辟新的搜索区域的能力，但高性能的模式遭到破坏的可能性增大;若交叉概率太低,遗传算法搜索可能陷入迟钝状态。一般Pc取0.25～1.00。

变异概率Pm：变异在遗传算法中属于辅助性的搜索操作，它的主要目的是保持群体的多样性。一般低频度的变异可防止群体中重要基因的可能丢失，高频度的变异将使遗传算法趋于纯粹的随机搜索。通常Pm取0.001～0.1。

遗传运算的终止进化代数G：终止进化代数G是表示遗传算法运行结束条件的一个参数，它表示遗传算法运行到指定的进化代数之后就停止运行，并将当前群体中的最佳个体作为所求问题的最优解输出。一般视具体问题而定，G的取值可在100～1000之间。