遗传算法

含义：

​ 遗传算法是借鉴生物的自然选择和遗传进化机制而开发出的一种全局优化自适应概率搜索算法。

遗传算法的生物学基础：

​ 遗传：世间的生物从其亲代继承特性或性状的生命现象。

​ 染色体：细胞中含有的一种微笑的丝状化合物。

​ 遗传信息：遗传信息由基因构成。

​ 遗传基因在染色体中所占据的位置称为基因座，同一基因座可能有的全部基因称为等位基因。

​ 适应度：每个个体对其生存环境的适应能力。

遗传算法概要：

对于一个求函数最大值的优化问题（当然求最小值也类似），一般可描述为以下数学模型： \[ \left\{ \begin{array}{lr} max \quad f(X) \\ s.t. \quad X∈R &&(1-2)\\ \quad \quad \ \ \ R \subseteq U &&(1-3)\\ \end{array} \right. \] 其中，

​ \(X=\left\{ x_1,\ x_2,\ \cdots,\ x_n \right\}\)​​ 为决策变量；​​

​ \(f(X)\)​ 为目标函数；

​ 式 \((1-2)、(1-3)\)​​​ 为约束条件，U 是基本空间，R 是 U 的一个子集。

满足约束条件的解 X 称为可行解，集合 R 表示由所有满足约束条件的解组成的一个集合，称为可行解集合。

由于完全精确的求出最优解很不现实，因此求出近似最优解是人们的主要着眼点。求解方法主要有三种：

• 枚举法。枚举出可行解集合内的所有可行解，以求出精确最优解。对于连续函数，该方法要求先对其进行离散化处理，这样就有可能产生离散误差而永远达不到最优解。另外，当枚举空间比较大时，该方法的求解效率比较低，有时甚至在目前最先进的计算工具上都无法求解。
• 启发式算法。寻求一种能产生可行解的启发式规则，以找到一个最优解或近似最优解。该方法的求解效率虽然比较高，但对每一个需要求解的问题都必须找出其特有的启发式规则，这个启发式规则无通用性，不适合于其他问题。
• 搜索算法。寻求一种搜索算法，该算法在可行解集合的一个子集内进行搜索操作，以找到问题的最优解或近似最优解。该方法虽然保证不了一定能够得到问题的最优解，但若适当地利用一些启发知识，就可在近似解的质量和求解效率上达到一种较好的平衡。

遗传算法中最优解的搜索过程也模仿生物的这个进化过程，使用所谓的遗传算子（genetic operalors）作用于群体 P(t) 中，进行下述遗传操作，从而得到新一代群体 P(t+1)。

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

由该图可以看出，使用上述三种遗传算子（选择算子、交叉算子、变异算子）的遗传算法的主要运算过程如下所述。 步骤一：初始化。设置进化代数计数器 \(t\leftarrow0\)​​​​；设置最大进化代数 T；随机生成 M 个个体作为初始群体 P(0)。
步骤二：个体评价。计算群体 P(t) 中各个个体的适应度。
步骤三：选择运算。将选择算子作用于群体。
步骤四：交叉运算。将交叉算子作用于群体。
步骤五：变异运算。将变异算子作用于群体。群体 P(t) 经过选择、交叉、变异运算之后得到下一代群体 P( t+1 )。
步骤六：终止条件判断。若 \(1 ≤ T\)​​​​，则：\(t\leftarrow t+1\)​​​​，转到步骤二；若 \(t≥T\) ，则以进化过程中所得到的具有最大适应度的个体作为最优解输出，终止计算。