演化计算及其应用.ppt

演化计算及其应用 第二讲 算法有哪些信誉好的足球投注网站能力的改进 对算法有哪些信誉好的足球投注网站能力的改进 个体的适应值和选择方式 个体的编码方式，相关的杂交变异算子及其参数设置 种群的初始化方法和算法停止条件 种群规模的最优选取和自适应选取 新算子 遗传算法最主要的步骤 编码 初始化 适应值评价及转换 选择 杂交、变异以及其他算子 算法停止条件 适应值评价及转换 遗传算法求解的标准问题是适应值为正的最大化问题 如何确定适应值？ 如果待优化问题是最小化问题怎么办？ 如果待优化问题适应值有负的数值怎么办？ 如果适应值差距较小怎么办？ 如何确定适应值(*) 大多数运筹（优化）问题都有明确的目标函数，可以将其作为适应值函数。 对于求方程根的问题，可以通过某种转换，将其转换为多峰优化问题。 对于多目标优化问题，或转换为单目标、或采用遗传算法自己的处理方法。 对于目标函数不明确的决策问题，至少要知道各种决策产生的效果哪个比哪个好。 至于好多少，不一定必须知道。 对于目标函数值计算比较费时的优化问题，如果能够找到不计算目标函数就可以比较个体目标函数值大小的方法，则可以大大简化遗传算法的优化速度。（结合基于适应值排序的选择方法） 求方程根的问题转换为优化问题 如果待优化问题是最小化问题怎么办？ (*) 如果待优化问题适应值有负的数值怎么办？ (*) 如果待优化问题是最小化问题且适应值有负的数值怎么办？ 如果适应值差距较小怎么办？ (*) 选择压力：由适应值和选择方式决定的优秀个体被选择的可能性。 我们需要多大的选择压力？ 算法进行早期，希望？ 选择压力较小 有助于广度有哪些信誉好的足球投注网站（exploration) 算法进行晚期，希望？ 选择压力较大 有助于深度有哪些信誉好的足球投注网站（exploitation） 如个体间适应值差距较小，则选择压力较小：1000002和1000010的差别远远小于2和10的差别（对基于个体相对适应值的选择方式而言）。 关于Exploration和Exploitation的进一步讨论(*) Exploration和Exploitation的矛盾就是种群多样性（Population Diversity）和选择压力（Selective Pressure）的矛盾。 这对矛盾是所有对算法有哪些信誉好的足球投注网站能力改进的出发点和归宿。 一个好的算法应该是在算法运行早期增加种群多样性，降低选择压力；在算法运行的晚期，减少种群多样性，增加选择压力。 如果适应值差距较小怎么办？ (*) 如果能够找到适当的常数（事先决定）或变量（由每代中最小适应值决定），则可以将所有个体适应值减去相同的数量。（分析最小化问题适应值有负情况） 适应值比例变换（scale method） 基于排序的选择方法（rank-based selection method） 为什么需要适应值比例变换(*) 对于基于个体相对适应值的选择方法，算法早期出现“超级个体”（适应值比其他个体大很多的个体），算法迅速收敛到局部最优解上（早熟premature）怎么办？ 在早期通过适应值比例变换减小个体间适应值的差距。 到了算法晚期，个体之间的适应值都差不多，选择过程类似于随机有哪些信誉好的足球投注网站怎么办？ 在晚期通过适应值比例变换增加个体间适应值的差距 常见的比例变换方法 线性比例变换 σ 截断 幂比例变换 Boltzmann选择 约定： xk表示第k个染色体， F ’(xk) 和F(xk)分别表示第k个染色体变换前后的适应值，F=g(F’)表示比例变换函数。 线性比例变换(*) 其中a和b是变换参数，它们由比例变换的强度决定。 通常人们希望 ： 等于群体中平均适应值的个体的适应值经过比例变换后值保持不变 群体中具有最大适应值的个体经过比例变换后适应值增长为平均适应值的2倍 线性比例变换（续） 可以解得 问题：可能使 线性比例变换（续） 如果这种情况发生 ，则？ 等于群体中平均适应值的个体的适应值经过比例变换后保持不变 （与前者一样） 适应值最小的个体经过比例变换后适应值变为0 。 线性比例变换 对线性比例变换的讨论(*) 在算法进行的早期，如果出现比其他个体好很多的“超级个体 ”： 经过线性比例变换后，其适应值减小为平均适应值的2倍（原来不止2倍），这就在很大程度上避免了早熟现象的发生。 在算法进行的晚期，个体之间适应值差距不大 ： 经过比例变换后，把最好的个体的适应值增大为平均适应值的2倍，从而加快了算法的收敛速度。 其他线性比例变换方法 比例窗 Hancock, P., An Empirical Comparison of Selection Methods in Evolutionary Algorithms, in Fogarty, T. eds. Evolutionary Computing, Springer-Verlag, Berlin, 19