二、遗传算法
（一）算法起源
遗传算法（Genetic Algorithm，GA）最初是由美国John holland教授于20世纪70年代提出，该算法受大自然中生物进化机制的启发，通过达尔文生物进化论的自然选择和遗传学机理进行的生物演化计算过程，这种过程能够通过模拟生物进化来搜索最优解，其特点是遵循适者生存、优胜劣汰的法则，保留有用的个体和去除无用的个体。目前，遗传算法以其易于计算和编码的特征已被广泛应用于组合优化、大规模系统优化、自适应控制系统、机器学习和信号处理等领域。
（二）算法基本原理
遗传算法是模拟生物进化过程的演化计算，其计算始终根据自然进化过程搜索目标最优解，其具体过程包括遗传、变异以及自然选择等。该算法在适应度函数选择不当时，因交叉选择可能会导致局部收敛而不能达到全局最优解。
遗传算法是从代表求解问题可能潜在的解集的一个种群（Population）开始，而一个种群则由经过基因编码的一定数目的个体（Individual）组成。每个个体实际上是染色体（Chromosome）带有特征的实体，染色体作为遗传物质的主要载体，即多个基因组成的集合，其内部表现为某种基因组合，这种组合决定了个体形状的外部表现。由于仿照基因编码的工作很复杂，通常情况下需要简化，例如二进制编码，第一代种群产生之后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的近似最优解，当满足一定的终止条件后，随机产生帕累托最优解。
在每一代迭代更新的过程中，可以根据问题中个体的适应度（Fitness）大小来选择个体，并且借助于生物自然进化的的遗传算子（Genetic Operators）进行组合交叉（Crossover）与变异（Mutation），产生出代表新的解集的种群。这个过程将会导致种群像自然进化一样的后生代种群比前代更加适应环境，末代种群中最优个体将经过解码以后可以作为问题的帕累托最优解。
1.相关术语
（1）染色体：和生物学中的概念一致，称之为基因型个体，一定数量的个体就组成了基因群体，群体中个体的数量称之为群体大小
（2）基因：是指染色体中的元素，主要用于表达个体的特征。例如，解码串S=0101，这个串S里面的0、1、0、1分别称之为基因，其值称为等位基因。
（3）基因位：是指在算法中表示某一个基因在串中的位置，从左往右计算，例如串S=0101中，0的基因位置有1和3。
（4）交叉：指两个染色体交换部分基因得到两个新的子代染色体。
（5）变异：染色体某些基因位的数值发生变化，例如S=0101变成0111。
（6）特征值：在串表示整数时，该基因的特征值与二进制数的权一致，例如在串S=0101中，基因位置是4中的1，它的基因位置特征是1。
（7）适应度：每个个体对环境的适应程度称之为适应度（Fitness）。它主要体现在染色体对环境的适应能力。这里为了便于度量每个染色体适应环境的能力，我们引入了适应度函数，该函数是计算每个个体在基因群体中被使用的概率。
2.算法特点
遗传算法从问题本身的串集开始搜索，而不是从单个最优解开始逐步搜索。传统算法一般首先给定一个初始解逐步迭代寻求最优解，容易陷入局部最优。而遗传算法则是从编码的串集中开始寻优搜索，覆盖面积大，利于搜索全局最优解。除此之外，遗传算法具有自组织、自适应和自学习性，可以在进化过程中根据环境信息进行自组织搜索，适应度大的个体具有较高的生存概率，并能够改善基因更加适应环境。其特征主要在于如下：
（1）首先根据问题选定一组随机候选解，用于后续步骤更新和检验。
（2）依据基因表达和特征值，结合经验选择来拟定适应性条件来测算随机候选解的适应度。
（3）选取适应度高的候选解，淘汰表现不佳的候选解。
（4）对生存下来的候选解进行遗传、突变和交叉等操作，迭代更新候选解。
（三）算法流程
（1）染色体编码：对于特定的优化问题，需要通过经验找到一种简单且不影响算法性能的编码方式，染色体编码方式将直接对染色体的交叉和变异操作构成影响。目前常用方式为二进制编码、字母编码、浮点数编码。
（2）群体初始化：群体初始化一般采用随机数初始方法，接着在给定的初始化群体中进行搜索。初始化染色体时必须注意染色体是否满足最优问题对有效解的要求。如果在初始化进行时保证初始化群体是优良的，将能够有效提高算法全局寻优能力。
（3）适应度函数评估：适应度函数用来评估各个染色体的适应值，进而对各个染色体进行区分。评估函数一般而言是通过问题的优化目标来确定。
（4）选择（算子）：种群的选择是优胜劣汰的过程，这样能够把优化的个体直接遗传到下一代。选择算子主要有适应度比例法、局部选择法、随机遍历抽样法等。
（5）交配（算子）：遗传算法起核心作用的便是遗传操作中的交叉操作，交叉是指将上一代的的两个染色体中的部分结构替换重组，形成新的染色体。通过交叉，遗传算法的寻优搜索能力将快速提高。
（6）变异（算子）：变异的核心在于对群体中的染色体的基因位做变动，对于交配后的性染色体的每一个基因位根据变异概率P判断该基因位是否进行变异。
具体算法流程图和伪代码如下：
图2-10 遗传算法流程图