演化计算及其应用

《演化计算及其应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、演化计算及其应用第二讲算法搜索能力的改进对算法搜索能力的改进个体的适应值和选择方式个体的编码方式，相关的杂交变异算子及其参数设置种群的初始化方法和算法停止条件种群规模的最优选取和自适应选取新算子遗传算法最主要的步骤编码初始化适应值评价及转换选择杂交、变异以及其他算子算法停止条件其中，编码方式和算子息息相关（讨论课）适应值评价、转换和选择方式密不可分适应值评价及转换遗传算法求解的标准问题是适应值为正的最大化问题如何确定适应值？如果待优化问题是最小化问题怎么办？如果待优化问题适应值有负的数值怎么办？如果适应值差距较小怎么办？4个问题循序渐进如何确定适应值(*)大多数运筹

2、（优化）问题都有明确的目标函数，可以将其作为适应值函数。对于求方程根的问题，可以通过某种转换，将其转换为多峰优化问题。对于多目标优化问题，或转换为单目标、或采用遗传算法自己的处理方法。对于目标函数不明确的决策问题，至少要知道各种决策产生的效果哪个比哪个好。至于好多少，不一定必须知道。对于目标函数值计算比较费时的优化问题，如果能够找到不计算目标函数就可以比较个体目标函数值大小的方法，则可以大大简化遗传算法的优化速度。（结合基于适应值排序的选择方法）求方程根的问题转换为优化问题这仅仅是个简单的例子，还有很多其他转换方法如果待优化问题是最小化问题怎么办？(*)如果待优化问

3、题适应值有负的数值怎么办？(*)其中，C为一个大小适合的正常数。如何确定C的大小：如果事先可以估计出F(x)的下界,就可以根据下界求得CC=abs(F(x*))，其中F(x*)是当代个体中最小目标函数值。这样，每代的最小适应值不小于0。如果待优化问题是最小化问题且适应值有负的数值怎么办？其中，C为一个大小适合的数。如何确定C的大小：如果事先可以估计出F(x)的上界,就可以根据上界求得CC=F(x*)，其中F(x*)是当代个体中最大目标函数值。这样，每代的最小适应值不小于0。如果适应值差距较小怎么办？(*)选择压力：由适应值和选择方式决定的优秀个体被选择的可能性。我们

4、需要多大的选择压力？算法进行早期，希望？选择压力较小有助于广度搜索（exploration)算法进行晚期，希望？选择压力较大有助于深度搜索（exploitation）如个体间适应值差距较小，则选择压力较小：1000002和1000010的差别远远小于2和10的差别（对基于个体相对适应值的选择方式而言）。关于Exploration和Exploitation的进一步讨论(*)Exploration和Exploitation的矛盾就是种群多样性（PopulationDiversity）和选择压力（SelectivePressure）的矛盾。这对矛盾是所有对算法搜索能力改进

5、的出发点和归宿。一个好的算法应该是在算法运行早期增加种群多样性，降低选择压力；在算法运行的晚期，减少种群多样性，增加选择压力。如果适应值差距较小怎么办？(*)如果能够找到适当的常数（事先决定）或变量（由每代中最小适应值决定），则可以将所有个体适应值减去相同的数量。（分析最小化问题适应值有负情况）适应值比例变换（scalemethod）基于排序的选择方法（rank-basedselectionmethod）为什么需要适应值比例变换(*)对于基于个体相对适应值的选择方法，算法早期出现“超级个体”（适应值比其他个体大很多的个体），算法迅速收敛到局部最优解上（早熟prema

6、ture）怎么办？在早期通过适应值比例变换减小个体间适应值的差距。到了算法晚期，个体之间的适应值都差不多，选择过程类似于随机搜索怎么办？在晚期通过适应值比例变换增加个体间适应值的差距常见的比例变换方法线性比例变换σ截断幂比例变换Boltzmann选择约定：xk表示第k个染色体，F’(xk)和F(xk)分别表示第k个染色体变换前后的适应值，F=g(F’)表示比例变换函数。线性比例变换(*)其中a和b是变换参数，它们由比例变换的强度决定。通常人们希望：等于群体中平均适应值的个体的适应值经过比例变换后值保持不变群体中具有最大适应值的个体经过比例变换后适应值增长为平均适应值

7、的2倍线性比例变换（续）可以解得问题：可能使F’FF’minF’avgF’maxFminFavgFmax遗传算法无法继续线性比例变换（续）如果这种情况发生，则？等于群体中平均适应值的个体的适应值经过比例变换后保持不变（与前者一样）适应值最小的个体经过比例变换后适应值变为0。F’FF’minF’avgF’maxFminFavgFmax线性比例变换F’FF’minF’avgF’maxFminFavgFmaxF’FF’minF’avgF’maxFminFavgFmax对线性比例变换的讨论(*)在算法进行的早期，如果出现比其他个体好很多的“超级个体”：经过线性比例变换后