演化计算及其应用.ppt

演化计算及其应用,第二讲 算法搜索能力的改进,对算法搜索能力的改进,个体的适应值和选择方式 个体的编码方式，相关的杂交变异算子及其参数设置 种群的初始化方法和算法停止条件 种群规模的最优选取和自适应选取 新算子,遗传算法最主要的步骤,编码 初始化 适应值评价及转换 选择 杂交、变异以及其他算子 算法停止条件,其中，编码方式和算子息息相关（讨论课） 适应值评价、转换和选择方式密不可分,适应值评价及转换,遗传算法求解的标准问题是适应值为正的最大化问题 如何确定适应值？ 如果待优化问题是最小化问题怎么办？ 如果待优化问题适应值有负的数值怎么办？ 如果适应值差距较小怎么办？,如何确定适应值(*),大多数运筹（优化）问题都有明确的目标函数，可以将其作为适应值函数。 对于求方程根的问题，可以通过某种转换，将其转换为多峰优化问题。 对于多目标优化问题，或转换为单目标、或采用遗传算法自己的处理方法。 对于目标函数不明确的决策问题，至少要知道各种决策产生的效果哪个比哪个好。 至于好多少，不一定必须知道。,对于目标函数值计算比较费时的优化问题，如果能够找到不计算目标函数就可以比较个体目标函数值大小的方法，则可以大大简化遗传算法的优化速度。（结合基于适应值排序的选择方法）,求方程根的问题转换为优化问题,这仅仅是个简单的例子，还有很多其他转换方法,如果待优化问题是最小化问题怎么办？ (*),如果待优化问题适应值有负的数值怎么办？ (*),其中，C为一个大小适合的正常数。,如何确定C的大小： 如果事先可以估计出F(x)的下界,就可以根据下界求得C C=abs(F(x*)，其中F(x*)是当代个体中最小目标函数值。 这样，每代的最小适应值不小于0。,如果待优化问题是最小化问题且适应值有负的数值怎么办？,其中，C为一个大小适合的数。,如何确定C的大小： 如果事先可以估计出F(x)的上界,就可以根据上界求得C C=F(x*)，其中F(x*)是当代个体中最大目标函数值。 这样，每代的最小适应值不小于0。,如果适应值差距较小怎么办？ (*),选择压力：由适应值和选择方式决定的优秀个体被选择的可能性。 我们需要多大的选择压力？ 算法进行早期，希望？ 选择压力较小 有助于广度搜索（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, 1994, pp. 80-95 动态比例变换 Cheng, R. And M. Gen, Evolution Program for Resource Constrained Project Scheduling Problem, in Fogel, D. eds. Proceedings of the First IEEE Conference on Evolutionary Computation, IEEE Press, Orlando, FL, 1995, pp.736-741, 截断（Sigma Truncation）,代表当代个体适应值的平均值，代表当代个体适应值的标准差，c是一个小的正整数（1到5）。另外当计算出的 小于0时，定义其为0 。, 截断分析,在遗传算法早期，由于群体分布不均匀，同时群体总体质量较差 因此 比较小，而比较大，这就有可能使得 ，整个比例变换相当于将原适应值加上一个正数，从而降低了选择压力，使得群体多样性得以加强。 在算法晚期，由于群体分布比较均匀，同时群体总体质量较高 因此 比较大，而比较小，这使得比例变换相当于将原适应值减去一个正数，适应值比这个正数小的个体在下一代中不能生存。降低整体适应值无疑增加了选择压力， 使其快速收敛。,幂比例变换(Power Law Scaling),其中是幂变换参数，其取值范围依赖于问题的结构（对于通常优化问题，有人建议1.005）,幂比例变换分析,0时： 对应于随机搜索 1时： 对应于未对适应值进行比例变换 如果1： 则经过比例变换后，最好与最差个体的适应值的差距将以指数方式增加。 可以结合模拟退火的思想（什么是模拟退火？）,模拟退火（对于最小化问题）,在算法早期采用比较小的值， 而随着演算的进行，逐步增加的数值， 同样会使算法早期和晚期的选择压力向所希望的方向变化， 从而达到既广泛搜索又快速收敛的效果。,t 逐渐减小,上述三种比例变换方法比较(*),变换后的选择压力： 幂比例变换 线性比例变换 截断 变换所需的时间 幂比例变换 截断 线性比例变换,Boltzmann选择,T 是类似模拟退火中温度的控制参数。 分析： T 取较大值时对种群来说具有较小选择压力。 反之，则选择压力较大 。 也可以采用相应的降温策略，从而使T 随着算法的进行而逐渐减小，也就对应着选择压力的逐渐增大。,比例变换实例,初始化后的种群（与原来相同）,比例变换后的种群,变换前,变换后,采用方法：,采用/不采用线性比例变换的选择结果,变换前的 选择结果,变换后的 选择结果,个体的 适应值,采用线性比例变换 后，原来个体5 (f=0.2527) 被个体6 (f= 1.4744) 替换。 选择的效果更好了。,采用/不采用线性比例变换的结果比较,前,后,选择方式(*),基于相对适应值的选择方式 基于适应值排序的选择方式 锦标选择,基于相对适应值的选择方式(*),轮盘赌选择（Roulette Wheel Selection，RWS） 有放回的剩余随机选择（Remainder Stochastic Sampling with Replace） 无放回的剩余随机选择（Remainder Stochastic Sampling without Replace） 随机通用采样（Stochastic Universal Sampling，SUS）,“有放回的剩余随机选择”和“无放回的剩余随机选择”请参考 1、3、4,随机通用采样（SUS）,RWS的选择偏差比较大（该选的没选上，不改选的选上了）。 随机通用采样（SUS）选择方式可以在统计上避免选择偏差的存在。 Baker, J. E., Reducing Bias and Inefficiency in the Selection Algorithm, in Grefenstette, J. J., eds. Proceedings of the Second International Conference on Genetic Algorithms, Lawrence Erlabaum associates, Hillsdale, NJ, 1987, pp. 14-21,对比RWS和SUS (*),每次用一个随机数选择1个新个体 让1个指针从0度角开始旋转,只用一个随机数就可以选择出N个新个体（以N6为例说明） 让6个指针从0度角开始分别旋转,对比RWS和SUS的选择结果,采用SUS后， 适应值大于平 均适应值的个 体的被选择概 率为1。（为什么） 避免了RWS中 适应值高的个 体未被选中的 可能。,对比RWS和SUS的优化结果,RWS,SUS,RWS效果好于SUS（原因：？）,100个个体100代优化结果比较,RWS,SUS,RWS效果与 SUS接近,100个个体100代优化结果比较,RWS,SUS,SUS比RWS找 到全局最优解 的速度要快 （15代/55代）,RWS和SUS比较的初步结论,对于较小规模的实验种群，由于随机误差等原因，很难比较二者的优劣。 对于较大种群规模（实际优化问题），SUS能够比较快地搜索到全局最优解，而RWS则要慢许多。 从理论分析上，SUS适应值大于平均适应值的个体的被选择概率为1。选择误差较小。 一般建议采用SUS作为选择方式。,RWS和SUS比较的初步结论,对于较大种群规模（实际优化问题），SUS能够比较快地搜索到全局最优解，而RWS则要慢许多。 从理论分析上，SUS适应值大于平均适应值的个体的被选择概率为1。选择误差较小。 一般建议采用SUS作为选择方式。,基于适应值排序的选择方式,线性 非线性,线性排序选择方式(*),将当代种群中的染色体按照适应值大小从好到坏依次排列为 ，同时设第个i个体在该序列中的位置是 ranki 第ranki个个体的被选择概率为 其中，q为用户指定的代表选择压力的参数，r为确保个体被选择概率之和为1的参数。 q和r的关系为,为什么？,线性排序选择方式的做法(*),将当前种群的适应值进行降序排序 根据问题难度和对优化结果的要求估计q的数值 根据q和r的关系计算出r的数值 计算出每个个体的被选择概率 采用SUS或其他选择方法进行选择过程,对线性排序选择方式的讨论(*),如果q=1/N ，则r0 。这时，种群中每一个个体有相同的被选择概率，等效于随机搜索。 如果q=2/N ，则 ，对应的prob(rankN)=0，即让最差个体的被选择概率为0，对应于最严厉的选择方式。 随着q从1/N增加到q=2/N，种群的选择压力逐渐增大。,基于适应值排序的非线性选择方式参考3,锦标选择(Tournament Selection)(*),选择时先随机地在群体中选择k个个体进行比较，适应值最高的个体被选中作为生成下一代的一个父个体。 这样继续下去，直到被选择出来的父个体数目达到N 为止。然后将这N 个父个体进行杂交。 参数k 称为锦标规模，它代表了选择压力，增大会使选择压力增大。 当k=1时，对应于随机搜索。选择压力最小。 当k=N 时，对应于当代最优解全部选取为下一代。选择压力最大。,Boltzmann锦标选择,锦标选择的进一步发展 相当于模拟退火锦标选择,保存最优解（Elitist Method (*) ）,保存当代最优个体，替换下一代最劣个体； 保存迄今为止最优个体，替换下一代最劣个体； 保存当代最好的10个体，替换下一代最差的10个体 ,采用/不采用保存最优解比较,不采用elitist,采用elitist,采用elitist后， 最终收敛效果好。,采用/不采用保存最优解比较,不采用elitist,采用elitist,采用elitist后， 收敛速度快。,100个个体100代优化结果比较,不采用elitist,采用elitist,采用elitist后， 最终收敛效果好。,100个个体100代优化结果比较,不采用elitist,采用elitist,采用elitist后， 收敛速度快。,关于保存最优解的说明(*),关于遗传算法收敛性的证明大多数有保存最优解的假设。 Goldberg D.E., Segrest P. Finite Markov chain analysis of genetic algorithms. In: Proc Int Conf Genetic algorithms87, 1987 保存最优解可以加快算法收敛。 保存最优解可能导致早熟现象（收敛到局部最优解） 保存最优解要慎用。,常用的算法停止判据(*),如果当前群体的代数大于事先指定的最多迭代次数，则可以终止迭代。 如果适应值函数计算的次数大于事先指定的最多计算次数，则可以终止迭代。 如果种群的代之间的平均适应值变化缓慢或者变化幅度较小，则可以终止迭代。 事先估计出最大化问题的上界并给出裕度，如果种群中最好解与上界之间的差距小于裕度时，终止迭代。 记忆算法执行过程中出现的最好点，如果该最好点在演化过程中经过很多代都没有改变，则终止迭代。 以上原则的综合运用。,这节课学到了什么,适应值评价及转换的基本方法 比例变换的常用方法 常用的和推荐的选择方法 保存最优解策略 常用的算法停止判据,