1.2　遗传算法

遗传算法是模拟大自然中生物遗传和进化过程而形成的全局自适应优化算法，由美国学者J. H. Holland在20世纪70年代提出。该算法通过数学方式将解决问题的求解过程类比成生物进化中染色体基因的交叉、变异等过程。遗传算法的主要思想是反复修改代表单个解的个体，基于自然选择过程来解决有约束和无约束优化问题。在遗传算法中，先从当前种群中随机选择个体作为父代，使它们生成下一代，经过若干代，得到一个最优的解决方案。遗传算法可以解决一些传统优化算法不能解决的优化问题，包括目标函数是不连续、不可微、随机或高度非线性的问题。

1.2.1　基本思想

遗传算法是一种使用群体搜索技术的优化算法，通过对当前群体进行选择、交叉、变异等一系列遗传操作，产生新一代群体，再逐步使群体进化到接近最优解的状态。

在遗传算法中，n维量X=[x₁，x₂，…，x_n]^T用n个X_i来表示：

每一个X_i作为一个遗传基因，它的变化取值就是等位基因的变化取值，因此，X可以看作n个遗传基因组成的染色体。染色体的长度既可以是固定的，又可以是变化的，简单的等位基因是由0或1组成的符号串，对应的染色体可以表示为一个二进制的符号串，这种符号串就是个体的基因型。对于每一个X，要根据适应度函数确定其适应度，X越接近目标函数的最优点，其个体的适应度就越大；反之，适应度越小。

在遗传算法中，每个X组成问题的解空间，搜索问题的最优解也就是对染色体X的搜索。因此，所有的染色体X就是问题的搜索空间。

生物的进化主要是通过染色体之间的交叉和基因的变异来完成的，与遗传算法相对应的是，最优解的搜索过程其实就是模仿生物的进化过程；经过反复迭代，群体不断地进行遗传和进化，且每次都按照优胜劣汰的规则将适应度较高的个体遗传到下一代，这样最终得到一个最优良的个体X。

遗传算法的基本操作有：

（1）选择算子。根据个体的适应度值，按照某些规则或方法，从本代中选择一些优良的个体遗传到下一代。“轮盘赌”选择法是遗传算法中的一种选择方法，它因为简单、实用，所以被广泛使用。它基于比例，个体子孙保留的可能性取决于各个个体的适应度所占比例的大小。假如某个个体i的适应度为f_i，种群大小为NP，则它保留于下一代的概率为：

适应度值越大，被选中的概率就越大。

（2）交叉算子。选择一对个体，以设定的交叉概率交换它们之间的染色体。

（3）变异算子。对于群体中的每一个个体，以设定好的变异概率将某个基因变为其等位基因。首先，判断每个个体是否要进行变异；其次，对需要变异的个体随机选择一个基因进行变异。

1.2.2　算法流程

遗传算法的具体流程如下。

步骤1：随机初始化种群。设置代数计数器，初始为g=0，最大进化代数为G，随机生成NP个个体作为初始种群p（0）。

步骤2：根据目标函数f（x），进行个体评价，计算p（t）中各个体的适应度。

步骤3：进行选择运算。使用选择算子，并根据个体的适应度，按照一定的规则或方法，选择一些优良个体遗传到下一代群体。

步骤4：进行交叉运算。将交叉算子作用于群体，对选中的成对个体，以某一概率交换它们之间的部分染色体，产生新的个体。

步骤5：进行变异运算。将变异算子作用于群体，对选中的个体，以某一概率改变某一个或某一些基因值改为其他等位基因。群体p（t）经过选择、交叉和变异运算之后得到下一代群体p（t+1）。计算其适应度值，并根据适应度值进行排序，准备进行下一次遗传操作。

步骤6：判断终止条件。若g≤G，则g=g+1，转到步骤2。若g>G，则此进化过程中所得到的具有最大适应度的个体作为最优解输出，终止计算。

1.2.3　伪代码