( 2) 积木块假设 积木块假设: 遗传算法通过短定义距、低阶 和高平均适应度的模式( 积木块) , 在遗传操 作下相互结合, 最终接近全局最优解。 模式定理保证了遗传算法找到全局最优解 的可能性存在,而积木块假设指出了在遗传 操作下能生成全局最优解。两者构成了分 析遗传算法进化行为的基本理论。
遗传算法的特点
产生初始种群 计算适应度
是否满足终 止条件 NO 选择 交叉 变异 YES
输出最优个体
图1 标准遗传算法流程图
标准遗传算法的基本要素
GA具有五个基本要素:参数编码、初始群体 的设定、适应度函数的设计、遗传操作设 计和控制参数设定。它们是设计GA时的核 心内容。 1、参数编码 编码机制是遗传算法的基础。在进行参数 编码设计时一般都以DeJong的编码原理为 依据。
(2)遗传算法是同时处理群体中的多个个体， 即多点搜索，在很多优化算法中，算法总 是按照某种转移准则从参数空间中的一个 单点移至下一个单点，这样做很容易在多 峰的搜索空间中找到一个非全局最高的峰 值，即局部最优值。而遗传算法是从很多 点的集合开始同时搜索的，从而减少了陷 于局部最优解的风险。
(3)遗传算法仅用适应度函数来指导搜索，以往很 多的搜索方法都需要辅助信息才能正常工作。如 梯度法需要有关导数的信息才能爬上当前的峰值 点，这就要求目标函数可导。而遗传算法则不需 要类似的辅助信息，为了有效地搜索越来越好的 编码结构，它仅需要与该编码串有关的适应度函 数即可。在适应度值的指导下，个体随着进化代 数的增大而不断进化，每一代的结果都优异于上 一代，如此逐代进化，直到得出最优化结果或符 合要求的结果。整个算法具有自适应环境的能力。
Hale Waihona Puke 2、GA的理论基础 ( 1) 模式定理 定义1: 出现在模式H 中的0 或1 的数目称为 模式H 的阶, 记作O(H)。如: O(10**1)=3。 定义2: 模式H 中第一个确定位置和最后一个 确定位置之间的距离称为模式H 的定义距, 记作δ(H)。如: δ(10**1)=4。 模式定理: 具有低阶、短定义距和平均适应 度高于种群平均适应度的模式在后代中呈 指数增长。
(4)遗传算法采用了概率转移准则而不是确 定性规则，与很多方法不同，遗传算法在 搜索过程中以概率转移准则来指导它的搜 索过程朝着更优化的解区域移动,但使用概 率并不是说遗传算法只是简单的随机搜索。 遗传算法用随机选择作为工具去指导搜索 向着搜索空间中可能的更好的区域进行。
遗传算法适于解决维数很高、总体很大的 复杂的非线性问题，如机器学习。遗传算 法具有以下优点: (1)应用的广泛性:易于写出通用算法，求解 不同优化问题。 (2)非线性性:其他多数算法都需与可导、线 性、凸性等性质相联系，遗传算法只需适 应度函数为非负，可用于具有高度非线性 的问题寻优。 (3)易于修改性:遗传算法只需少量改变算法， 即可适用于不同问题。 (4)易于并行实现。
与传统的方法相比，遗传算法以其简单、 鲁棒性强、不需很多先验知识等特点，使 它能适应于不同的环境、问题，并且在大 多数情况下都能得到最优解。遗传算法 具有很强的鲁棒性，这是因为比起普通的 优化搜索方法，它采用了许多独特的方法 和技术，归纳起来，主要有以下几个方面:
(1)遗传算法的处理对象不是参数本身，而 是对参数集进行了编码的个体，遗传算法 将待优化问题的原始参数集编码成有限字 符集上的有限长字符串，然后以一种通用 的方式去找出各编码的类似处。这样做的 好处是大大减少了约束条件的限制，如连 续性、可导性、单峰性等。因此，遗传算 法是一种框架算法，最适合于解决那些很 难用表达式表达出来的问题。
2、初始种群的设定 群体中个体一般是随机产生，当然也可从 随机生成的个体中选出最好的个体组成初 始群体。但此处有一个关键的问题，就是 如何确定群体规模的大小。根据模式定理 可知规模M越大越好，但M过大又会使计算 效率降低，并且若使用比例选择，此时会 影响群体的多样性。而M过小又会造成未成 熟收敛。故实际应用中通常取群体规模为 几十至几百。
经常采用的编码技术主要有一维染色体编 码、多参数映射编码、可变染色体长度编 码、二维染色体编码、树结构编码等。其 中一维染色体编码根据基于不同的符号集 又可分为二进制编码、实数编码和字符编 码等;多参数映射编码主要应用于多参数优 化问题中，将不同的参数映射为不同的编 码子串，然后进行相应的遗传操作;可变染 色体长度编码主要以Golbdegr等人提出的 MesysGA(mGA)为代表;后两种编码是针对不 同应用领域的特点而设计的，分别应用于 图像处理，人工智能等特定领域。
标准遗传算法的基本流程

标准遗传求解问题的基本流程如下: 1.确定染色体、种群和适应度函数。将问题的解 编码成染色体串，如二进制码串，若干个可能解 构成一组种群，适应度函数体现了在问题求解过 程中染色体求解问题的能力。 2.基因初始化，即对种群中染色体的各基因(二进 制子串)设定初值。 3.将种群的各染色体置于问题的环境中遗传进化。
遗传算法理论和特点
1、GA的基本原理 遗传算法首先采用某种编码方式将解空间映射到 编码空间, 每个编码对应问题的一个解, 称为个体 或染色体, 再随机确定起始的一群个体, 称为种群。 在后续迭代中, 按照适者生存原理, 根据适应度大 小挑选个体, 并借助各种遗传算子对个体进行交叉 和变异, 生成代表新的解集的种群, 该种群比前代 更适应环境, 如此进化下去直到满足优化准则。此 时末代个体, 经过解码, 可作为问题近似最优解。
（1）进化：根据适应度函数，计算每个染色 体的适应度。 （2）选择:选择有较大适应值的染色体进行复 制，替代适应值小的染色体。 （3）交换和变异:其目的在于产生有可能更适 应环境的新染色体。 4.重复3直至满足终止条件。这样一代代不 断进化，最终将收敛到一个最适应环境的 个体上，即问题的最优解。
图1描述了标准遗传算法的流程，从图中可 以看出GA是一种群体型操作，该操作主要 以群体中的所有个体为对象。选择、交叉、 变异是GA的3个主要操作算子，它们构成了 所谓的遗传操作。