•
进化计算的基本概念
•
编码：EA常常还需要对问题的解进行编码，即 通过变换将映射到另一空间（称为基因空间）。 通常采用字符串（如位串或向量等）的形式 一个长度为的二进制串称为一个染色体（ 个 体）。染色体的每一位称为基因（ gene ），基 因的取值称为等位基因（ allele），基因所在染 色体中的位置称为基因位（1ocus）。
进化计算的自适应性
• EA 只使用解的适应性信息（即目标函数），并在增 加收益和减小开销之间进行权衡，而传统搜索算法一 般要使用导数等其它辅助信息； • EA使用随机转移规则而不是确定性的转移规则； • 进化计算具有显著的隐式并行性。 EA 虽然在每一代 只对有限解个体进行操作，但处理的信息量为群体规 模的最高次； • EA 具有很强的鲁棒性，即在存在噪音的情况下，对 同一问题的 EA 的多次求解中得到的结果是相似的。 EA的鲁棒性在大量的应用实例中得到充分证实。
进化计算的自适应性
• 策略参数：直接控制EA进程的因素， 如选择交叉和变异算子的形式及各种算 子的参数值 • ES和EP采用的自适应策略，是将步长 向量作为策略参数。步长向量作为个体 的一部分，与目标向量一起进化，由进 化过程本身自发地调节步长的大小
进化计算的自适应性
GA自适应的策略参数一般包括两个部分： • 算子概率，即在一次进化过程中使用多个进 化算子时，确定各个算子使用的概率 • 对所使用的进化算子确定其参数值，如交叉 算子的交叉概率等。 例，对于采用二进制编码的GA，可以将策 略参数编成二进制位串，与原个体位串合并 形成一个扩展的位串，作为一个个体进行进 化。
对
进行选择操作生成群体
，
其中 }
}
代表
的某个子集或空集；
进化计算的自适应性
与一般的EA相比，采用自适应机制的EA能 够对进化过程中事先难以预料的细节产生 反应，以适应在进化的各个特殊阶段的特 殊环境，并且以某种方式动态地获取和利 用关于问题的规律性知识。这是一个进化 群体进行群体自动学习的过程，它最终能 够使得算法更好地适合待解决的问题。
• J. Holland将该算法用于自然和人工系统的自适 应行为的研究之中，并于1975年出版其开创性的 著作“Adaptation in Natural and Artificial Systems”
进化计算的主要分支
——遗传算法
• 后来， J. Holland 与他的学生们将该算法加以 推广并应用到优化及机器学习等问题之中，而 且正式定名为遗传算法。遗传算法的通用编码 技术及其简单有效的遗传操为其广泛的应用和 成功奠定了基础
第四章 进化计算与遗传算法
4.1 4.2 4.3 4.4 4.5 4.6
概 述 进化计算的基本原理 进化计算的理论与分析 遗传算法的改进 进化计算的应用 小 结
4.1 概 述
• 从生物进化到进化计算
• 进化计算的主要分支 • 进化计算的主要特点
• 进化计算的理论研究
• 进化计算的应用
从生物进化到进化计算
基本遗传算法的设计和实现
• 编码设计： 1）二进制编码 2）浮点数编码 3）混合编码 • 适应度函数的设计： • 遗传操作： 1）选择 2）交叉/重组 3）变异
6.4 遗传算法的改进
• • • • • • • 递阶（层次）遗传算法 CHC算法 Messy 遗传算法 自适应遗传算法 基于小生境技术的遗传算法 混合遗传算法 基于实数编码的遗传算法
• 另外，生物进化是一个开放的过程，自然 界对进化中的生物群体提供及时的反馈信 息，或称为外界对生物的评价。由此形成 了生物进化的外部动力机制。
从生物进化到进化计算
进化计算的特点： • 进化计算采用简单的编码技术来表示各种 复杂的结构，并通过对一组编码表示进行 简单的遗传操作和优胜劣汰的自然选择来 指导学习和确定搜索的方向。 • 它采用种群（即一组表示）的方式组织搜 索，这使得它可以同时搜索解空间内的多 个区域。而且用种群组织搜索的方式使得 进化算法特别适合大规模并行计算。
•
进化计算的基本概念
• • • • 种群（ population ，或称为群体、解群、居群 等）：进化计算在求解问题时是从多个解开始 的 迭代步：称为进化代 群体的规模：一般地，元素的个数在整个进化 过程中是不变的 当前解：新解的父解（ parent ，或称为父亲、 父体等） 后代解（ offspring ，或称为儿子、后代等）： 产生的新解
进化计算的主要分支
——进化策略
• 进化策略 根据种群内的 个个体产生 个个体（用 变异和重组），然后将这 个个体进行比 较再在其中选取 个最优者
•
进化策略
）个个体中选择 个最
在新产生的 （＞ 优者
进化计算的主要特点
• 智能性：自组织、自适应和自学习性等
• 本质并行性
• 其他特征：过程性 多解性 不确定性 非定向性 内在学习性 统计性 稳健性 整体优化
自适应遗传算法
• 遗传算法的参数中，交叉概率和变异概率的选 择是影响遗传算法行为和性能的关键所在，直 接影响着算法的收敛性 • 交叉概率越大，新个体产生的速度就越快。然 而，交叉概率过大时遗传模式被破坏的可能性 也越大，使得具有高适应度的个体结构很快就 会被破坏；但是如果过小，会使搜索过程缓慢， 以至停滞不前 • 对于变异概率，如果过小，不易产生新的个体 结构；如果取值过大，那么遗传算法就变成了 纯粹的随机搜索算法。
从生物进化到进化计算
• 在赋予进化计算自组织、自适应和自学习等特 征的同时，优胜劣汰的自然选择和简单的遗传 操作使进化计算具有不受其搜索空间限制性条 件（如可微、连续、单峰等）的约束及不需要 其它辅助信息（如导数）的特点
• 这些崭新的特点使得进化计算不仅能获得较高 的效率而且具有简单、易于操作和通用的特性， 而这些特性正是进化计算越来越受到人们青睐 的主要原因之一
进化计算的主要分支
——进化策略
• （l＋1）进化策略或二元（two－membered）进 化策略： 种群中只包含一个个体，而且只使用变异作。在 每一进化代，变异后的个体与其父体进行比较再 选择两者之优。它使用的变异算子是基于正态分 布的变异操作 • 进化策略 种群内含有 个个体，随机地选取一个个体进 行变异，然后取代群体中最差的个体
生物进化过程的发生需要四个基本条件：
1）存在有多个生物个体组成的种群；
2）生物个体之间存在着差异，或群体具有多样性； 3）生物能够自我繁殖； 4）不同个体具有不同的环境生存能力，具有优良 基因结构的个体繁殖能力强，反之则弱。
从生物进化到进化计算
生物群体的进化机制可以分为三种基本形式：
• 自然选择：控制生物体群体行为的发展方 向，能够适应环境变化的生物个体具有更 高的生存能力，使得它们在种群中的数量 不断增加，同时该生物个体所具有的染色 体性状特征在自然选择过程中得以保留
6.2 进化计算的基本原理
• 进化计算的基本概念
• 进化计算的基本结构（一般框架）
• 进化计算的自适应性 • 基本遗传算法的设计和实现
进化计算的基本概念
• 进化算法（EA）是一种基于自然选择和遗传变 异等生物进化机制的全局性概率搜索算法。在 形式上，同其它启发式搜索方法一样，是一种 迭代方法 它从选定的初始解出发，通过不断迭代逐步改 进当前解，直至最后搜索到最优解或满意解。 在进化计算中，迭代计算过程采用了模拟生物 体的进化机制，从一组解（群体）出发，采用 类似于自然选择和有性繁殖的方式，在继承原 有优良基因的基础上，生成具有更好性能指标 的下一代解的群体
进化计算的主要分支
四大主要分支： • 遗传算法（genetic algorithm，简称GA）、 • 进 化 规 划 （ evolutionary programming ， 简 称 EP）
• 进化策略（evolution strategy，简称ES）
• 遗传程序设计（genetic programming，简称GP）
6.4
遗传算法的改进
• 协同多群体遗传算法 • 微种群算法 • 双种群遗传算法 • 并行遗传算法 • 基于DNA编码的遗传算法种群独立运行遗传算法一定次数 Y 性能满足否？ N N个结果种群及平均适应度值记录到R[1...N,1…n]及A [i]中 结束
CHC算法
CHC算法对遗传算法的改进之处 ： • 选择：上世代种群与通过新的交叉方法产生的 个体种群混合起来，从中按一定概率选择较优 的个体。这一策略称为跨世代精英选择 • 交叉 ：是对均匀交叉的一种改进，当两个个体 位值相异的位数为时，从中随机地选取个位置， 实行父代个体位值的互换 • 变异： CHC 算法在进化前期不采取变异操作， 当种群进化到一定的收敛时期，从优秀个体中 选择一部分个体进行初始化
自适应遗传算法
•
进化计算的主要分支
——遗传算法
• 到 20 世 纪 60 年 代 中 期 ， 美 国 Michigan 大 学 的 John Holland在A. S. Fraser和H. J. Bremermann 等人的工作的基础上提出了位串编码技术 ，这 种编码既适合于变异又适合于交配（即杂交）操 作，并且他强调将交配作为主要的遗传操作
• J. Holland 的遗传算法常被称为简单遗传算法 （简记SGA），SGA的操作对象是一群二进制 串（称为染色体、个体），即种群 （population）
进化计算的主要分支
——进化策略
• 在20世纪60年代初，当时在柏林工业大 学的I. Rechenberg和H. P. Schwefel等在 进行风洞实验时，由于在设计中描述物 体形状的参数难以用传统的方法进行优 化，从而他们利用生物变异的思想来随 机地改变参数值并获得了较好的结果 • 随后，他们便对这种方法进行了深入的 研究和发展，形成了进化计算的另一个 分支——进化策略（ES）
•
•
基因型（genetype）和表现型（phenotype）