1.1.1 遗传算法
1962年，美国密歇根大学J. H. Holland等人[7,8]借鉴了达尔文的生物进化论和孟德尔的遗传定律的基本思想，通过提取、简化与抽象提出了遗传算法（GA）。GA是从一个经过基因（Gene）编码的一定数目的个体（Individual）组成的种群（Population）开始的，代表了问题可行解集。每个个体实际上是染色体（Chromosome）带有特征的实体。染色体作为遗传物质的主要载体，其内部表现（基因型）是某种基因组合，它决定了个体的外部表现。例如，肤色是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射，即编码工作。由于仿照基因编码的工作很复杂，往往需要进行简化，如二进制编码。初始种群产生之后，按照适者生存和优胜劣汰的原理，逐代（Generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（Fitness）大小选择（Selection）个体，并借助于自然遗传学的遗传算子（Genetic Operators）进行组合交叉（Crossover）和变异（Mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样，后代种群比前代更加适应环境，末代种群中的最优个体经过解码（Decoding），可以作为问题近似最优解。
编码机制直接制约着GA的性能。二进制编码被广泛应用于各种GA中，但这种编码方法在连续函数离散化时存在映射误差，因而又提出了很多非二进制编码方法：格雷码、树型编码、量子比特编码等。
适应度函数将目标函数值转换成适应值，用来评价个体的优劣，并作为遗传操作的依据。适应度是指种群中各个个体对环境的适应程度，根据适应度的大小，决定某个个体是繁殖还是死亡，因此适应度是进化的驱动力。从生物学角度看，适应度相当于“适者生存，生存竞争”的生物生存能力，在进化过程中有重要意义。适应度通常是费用、盈利、方差等目标的表达式。适应度函数通常根据目标函数和约束条件来设计，要确保目标函数变化方向与适应度函数变化方向一致，这是GA的重要搜索依据。适应度函数的优劣决定着算法的收敛性能，以及算法能否跳出局部最优解，各种变换尺度策略（如线性尺度变换、指数尺度变换等）被用来调节原适应值之间的比例。
遗传算子主要通过选择、交叉和变异3种操作来实现搜索。国内外很多研究对遗传算子进行改进以提高算法性能，S. A. Jafari等人[9]设计了一种模糊准则和性别选择方法，张钹等人[10]用佳点集方法改进了交叉操作，孟伟等人[11]基于蜜蜂进化模型将最优个体与其余个体分别交叉，杨启文等人[12]借鉴数字技术中的二元逻辑设计了一种二元变异算子，这些改进都能不同程度地提高种群多样性和进化速度，克服早熟收敛。吴少岩等人[13]研究交配算子与其探索子空间的关系，提出了设计良好算子的指导性原则，并构造出了一种启发式交配算子。
总的来说，GA具有较好的全局搜索能力，算法的迭代基于概率机制以满足随机性特点，容易扩展并与其他算法融合。然而，GA不能有效利用反馈信息，往往会造成迭代的冗余，使得算法效率较低，容易进入早熟收敛，局部寻优能力需要不断改进提高。
GA是一个迭代计算过程，其实施的主要步骤包括编码、群体初始化、选择、遗传操作、评价和终止判定6步，GA流程图如图1-1所示。
图1-1 GA流程图
1. 编码
编码的主要任务是建立解空间与染色体空间中点的一一对应关系。GA通常在染色体空间中进行操作。在多数情况下，不同的编码方式决定了不同的遗传操作方式。对编码的一般原则性要求主要有完备性、健全性和非冗余性。完备性是指解空间中的所有点都能表示为染色体空间中的点，健全性是指染色体空间中的所有点都能表示为解空间中的点，非冗余性是指解空间和染色体空间中的点一一对应。
2. 群体初始化
与传统优化方法相比，GA的一个显著的特点是对群体进行操作，所以在进化开始时必须进行群体初始化，产生进化的起点群体。通常随机构造初始群体，当然也可以在初始群体中植入一些具有特殊“性状”的个体，以加速算法向全局最优解收敛。
3. 选择
GA的选择操作与生物的自然选择机制相类似，它体现了“适者生存，不适者被淘汰”的生物进化机理。实现原则为“性状”优良的个体具有较多的机会被选进交配池产生后代，而“性状”低劣的个体则具有较少的机会被选择。这里的“性状”通过评价操作进行量化。最常用的选择方式是赌轮选择、联赛选择和排序选择。
4. 遗传操作
遗传操作被视为GA的核心。它直接影响和决定了GA的优化能力，是生物进化机理在GA中最主要的体现。目前，已有适用于各种不同类型问题的多种遗传操作算子。其中，杂交与变异是最常用的遗传操作，杂交体现了同一群体中不同个体之间的信息交换，而变异则能维系群体中信息的多样性。这些遗传操作在优化中的主要作用是以不同的方式不断产生新的个体。
5. 评价
评价是GA的驱动力，是GA体现有向搜索、区别于随机搜索的标志。它将同一群体中不同个体的优劣进行数值标量化，为选择操作提供客观依据。确定GA评价准则主要依赖于要求解的问题。
6. 终止判定
通常依靠经验和运行结果给定的进化最大代数作为终止判据。
GA的早熟问题（Premature Convergence）是指进化过程收敛于非期望的局部极值或群体的最佳个体进化到问题的非最优解，进化过程就停滞不前的现象。早熟问题严重影响了GA的应用，目前，还没有一种通用的解决方法。用GA求解一个复杂的实际优化问题，无法定量、准确地判断在优化过程中何时出现早熟，因而，控制或消除早熟问题就比较困难。