f
max
=C
mult
• f
' avg
为了保证在以后的选择处 理中平均每个个体可贡献 一个期待的子孙到下一代
为了控制原适应度最大的 个体可贡献子孙数。 个体可贡献子孙数。 通常取 1.2〈C mult 〈 2.0
ƒˊ
' 2 f avg
ƒˊ
' 2 f avg
' f avg
' f min
' f avg
f min
GA算法分析－群体设定 算法分析－ 算法分析
群体规模太大的弊病 计算效率 由于个体被选择的概率大多采用适应度比例选择法， 由于个体被选择的概率大多采用适应度比例选择法，当规模太大 大多数个体会被淘汰，仅少量的高适应度个体生存下来， 时，大多数个体会被淘汰，仅少量的高适应度个体生存下来，影 响配对和交叉繁殖。 响配对和交叉繁殖。 群体规模太小的弊病 会使GA的搜索空间有限，引起未成熟收敛(premature GA的搜索空间有限 会使GA的搜索空间有限，引起未成熟收敛(premature convergence) 结论： 结论： 规模设定是一个tradeoff tradeoff问题 规模设定是一个tradeoff问题 可以证明，在二进制编码的前提下，为满足隐并行性， 可以证明，在二进制编码的前提下，为满足隐并行性，群体的个 l 即可。这个数目很大，一般设定为几十∽ 数只要设定为 2 即可。这个数目很大，一般设定为几十∽几百 2 进化过程中，群体规模未必保持在相同规模， 进化过程中，群体规模未必保持在相同规模，但一般情况下都保 持不变
coding
这种不统一表现问题，在葛莱编码（gray coding）有较好的表现。 Integer 0 1 2 3 4 5 6 7 binary 000 001 010 011 100 101 110 111 Gray 000 001 011 010 110 111 101 100 从上面可看到，相邻两个数之间只相差一 位，用Gray代替标准的binary，这样可以 使得相邻状态间的遗传算子的转换变得平 滑。
五、搜索的并行性
爬山法：它保持多个候选解，删除没希望 的，提高好的解决方法。上图，表明了多 个候选解在搜索空间中朝最优点收敛。
五、搜索的并行性
图中，水平轴代表在解空间中的可能点， 垂直轴反应这些解的质量。曲线上的点是 遗传算法中当前群体中的候选解成员。开 始时，候选解分散在可能解空间中，经过N 代进化后，它们趋向于聚集在质量较高的 区域。
⒈ 目标函数映射为适应度函数
许多应用中，目标函数可直接作为适应度函数，但是， 许多应用中，目标函数可直接作为适应度函数，但是，有些情况下需 将目标函数作变换，以得到适应度函数。 将目标函数作变换，以得到适应度函数。 最小化问题：将费用函数等最小化函数g(x) g(x)转化为适应度函数 ① 最小化问题：将费用函数等最小化函数g(x)转化为适应度函数
二、遗传算法的实现过程
开始 初始群体 新群体 评估每个个体 是否优解？ 选择 交叉 变异 结束
解编码
•遗传算法在进化搜索中
评估函数
遗传操作
基本上不用外部信息， 基本上不用外部信息， 仅用目标函数即适应 度函数为依据。 度函数为依据。 •适应度函数评估是选择 操作的依据。 操作的依据。 •一般需将目标函数以一 定的方式映射成适应 度函数。 度函数。
六、隐含的并行性
一般地说，GA的计算能力主要来源于它的 隐含并行性，即按照一些有效的原则，并 行地把搜索尝试分配到搜索空间的许多领 域的特性。GA的隐含并行性使GA使用相对 少的串，就可以测试搜索空间里较大范围 的区域。GA的这种隐含并行性，使其在复 杂问题的优化求解等方面优于其它算法。
算法评估－ 七、GA算法评估－适应度函数设计 算法评估
算法评估－ 七、GA算法评估－适应度函数设计 算法评估
线性标定： ① 线性标定： 设原适应度函数为f,标定后为f f,标定后为 f´ 设原适应度函数为f,标定后为f´: f´=af + b 其中， 设定要满足： 其中， a, b 设定要满足：
' f avg ( x ) = f avg ( x )
和
fi = fi
'
k
较少使用，K与求解问题相关
算法评估－ 七、GA算法评估－适应度函数设计 算法评估
3. 适应度函数与 适应度函数与GA迭代停止条件 迭代停止条件 当最优解的适应度值已知或准最优解的适应度下限可以确定时， 当最优解的适应度值已知或准最优解的适应度下限可以确定时， 可用作迭代停止条件 否则，若发现群体中个体的进化已趋于稳定， 否则，若发现群体中个体的进化已趋于稳定，即发现一定比例的 个体具有完全相同的适应度， 个体具有完全相同的适应度，则停止迭代 4. 适应度函数与问题的约束条件 GA仅靠适应度来评估和引导搜索 不能明确表示约束条件。 仅靠适应度来评估和引导搜索， GA仅靠适应度来评估和引导搜索，不能明确表示约束条件。 对策： 对策：适应度函数考虑惩罚或代价 约束优化问题 非约束问题 此类问题还可在编码和遗传操作设计方面采取一定措施
f
avg
f max
ƒ
' f min
f min
f avg
f max
ƒ
A 正常线性定标
一些坏个体适应度远小于群体平均适应 度和最大适应度， 群体平均适应度又 度和最大适应度，且群体平均适应度又 比较接近最大适应度时， 比较接近最大适应度时，为了拉开他 们，使低适应度经定标后变成负值
B 出现负适应度地线性定标
coding
二值编码： 问题空间的相邻解在编码空间 并不相邻不利于解的搜索
葛莱码： 问题空间的相邻解在编码空间 相邻有利于解的搜索
GA算法分析－群体设定 算法分析－ 算法分析
编码设计后的任务是初始群体的设定，其关键问题是群体规模。 编码设计后的任务是初始群体的设定，其关键问题是群体规模。其中 要考虑： 要考虑： 初始群体如何设定？多大规模？ ▲ 初始群体如何设定？多大规模？ 进化过程中各代的群体规模如何维持？ ▲ 进化过程中各代的群体规模如何维持？ ⒈ 初始群体的设定 GA中初始群体中的个体是随机产生的 中初始群体中的个体是随机产生的， GA中初始群体中的个体是随机产生的，也可以根据先验知识设定初 始群体 ⒉ 群体中个体的多样性 模式定理告诉我们，若群体规模为M GA可操作的模式数为 可操作的模式数为M 模式定理告诉我们，若群体规模为M，GA可操作的模式数为M³,并在 此基础上不断形成和优化积木块，直到最优解。 此基础上不断形成和优化积木块，直到最优解。 显然， 越大，GA操作的模式越多 生成有意义的积木块的机会越高。 操作的模式越多， 显然，M越大，GA操作的模式越多，生成有意义的积木块的机会越高。 换句话说，群体规模越大，群体中个体的多样性越高， 换句话说，群体规模越大，群体中个体的多样性越高，陷入局部解 的危险就越小
C max − g( x ) f (x) = 0
g ( x )〈C max
Cmax 可以是一个合适的值，也可采用迄今为止进化过程中g(x) 可以是一个合适的值，也可采用迄今为止进化过程中g(x)
的最大值或当前群体中g(x)的最大值 的最大值或当前群体中g(x)的最大值 g(x) 最大化问题：将利润函数等最大化函数u(x) u(x)转化为适应度函数 ② 最大化问题：将利润函数等最大化函数u(x)转化为适应度函数
u( x ) + C min f (x) = 0
u( x ) + C min 〉 0
其他ห้องสมุดไป่ตู้况
C min 可以是合适的输入值，也可以是当前一代或前K代中u(x) 可以是合适的输入值，也可以是当前一代或前K代中u(x)
的最小值
算法评估－ 七、GA算法评估－适应度函数设计 算法评估
适应度函数标定(scaling) ⒉ 适应度函数标定(scaling) 在应用GA尤其用GA处理小规模群体时常常会出现一些 在应用GA尤其用GA处理小规模群体时常常会出现一些 GA尤其用GA 不利于优化的现象和结果： 不利于优化的现象和结果： 进化初期的未成熟收敛现象：基于比例选择策略， 进化初期的未成熟收敛现象：基于比例选择策略，一 些异常个体竞争力太强而处于主宰地位 解决办法：降低异常个体的竞争力， 解决办法：降低异常个体的竞争力，即适应度 进化后期的随机漫游现象： 进化后期的随机漫游现象：群体的平均适应度已接近 最佳个体的适应度，此时，个体间竞争力减弱 最佳个体的适应度，此时， 解决办法：提高个体间竞争力， 解决办法：提高个体间竞争力，即适应度
X(=39)
coding
假如用遗传算子来区别十进制数6、7、8、 9。整数表示出一个自然且平局的有序空间。 因为在十进制中，下一个数只下在前一数 上加1，然而用二进制编码则有明显不同： –0110 0111 1100 1111 – 6 7 8 9 在6和7之间还有8和9之间只有一位发生变 化，但在7和8之间四位全部不相同。
人工智能人工智能-机器学习 遗传算法的评估
一、遗传算法的简介
遗传算法（Genetic Algorithms）是一 种模拟生物界自然选择和遗传的启发式 随机搜索算法。 其基本步骤包括编码、初始群体的生成、 适应度评估、选择、交叉操作和变异操 作。 GA是一种具有“生成+检测”的迭代过程 的搜索算法。
三、 评估（Evaluation） 评估（ ）
GA基本上不用外部信息， GA基本上不用外部信息，仅用适应度函数来 基本上不用外部信息 评估每个个体。 评估每个个体。 • 评估时需要解码（ decoding ），即把基因型 评估时需要解码（ ），即把基因型 genotype）解转换为表示型（phenotype） （genotype）解转换为表示型（phenotype）解，以便利 用评估函数或适应函数。 用评估函数或适应函数。
•
generation Evaluated generation