最优化理论课件.ppt

《最优化理论课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、最优化理论——三大经典算法三大经典算法NO.1遗传算法NO.2模拟退火法NO.3神经网络算法遗传算法GeneticAlgorithm1遗传算法是一类借鉴生物界的进化规律（优胜劣汰，适者生存）演化而来的随机化搜索方法。广泛应用于函数优化和组合优化领域。1.函数优化：许多被构造出的各种复杂形式的测试函数“连续函数或离散函数，凹函数或凸函数，单峰函数或多峰函数等”，非线性多模型多目标的优化问题遗传算法可以方便得到较好的结果。2.组合优化：随着问题规模的增大，组合优化问题的搜索空间也增大，有时枚举法很难求出最优解，人们意识到应该把精力主

2、要放在寻求满意解上，遗传算法是最佳工具之一。生物学术语说明染色体染色体又可以叫做基因型个体，一定数量的个体组成了群体，群体中个体的数量叫做群体大小基因基因是串中的元素，基因用于表示个体的特征。eg：有一个串S=1011，则其中的1,0,1,1分别称为基因，它们的值称为等位基因基因地点（位置）表示一个与基因在串中的位置称为基因位置（基因位），基因位置在串中由左向右计算。eg：在串S=1011中，0的基因位置是3特征值在用串表示整数时，基因的特征值与二进制的权一致。eg：在S=1011中基因位置3中的1特征值是2，基因位置1中的1特

3、征值是8.适应度各个个体对环境的适应程度叫做适应度。为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量的函数，叫适应度函数。这个函数是计算个体在群体中被使用的概率。简单说来就是：繁殖过程，会发生基因交叉，基因突变，适应度低的个体会被逐步淘汰，而适应度高的个体会越来越多。那么经过N代的自然选择后，保存下来的个体都是适应度很高的，其中很可能包含史上产生的适应度最高的那个个体。1常用的选择策略是“比例选择”，也就是个体被选中的概率与其适应度函数值成正比。选择2交叉前：00000

4、011100000000

5、1000011

6、100

7、000001111110

8、00101交叉后：00000

9、000001111110

10、1000011100

11、011100000000

12、00101交叉3变异前：000001110000000010000变异后：000001110000100010000变异遗传算法的三个最基本操作选择轮盘赌算法/**按设定的概率，随机选中一个个体*P[i]表示第i个个体被选中的概率*/intRWS(){m=0;r=Random(0,1);//r为0至1的随机数for(i=1;i<=N;i++){/*产生的随机数在m~m+P[i]间则认为选中了i

13、*因此i被选中的概率是P[i]*/m=m+P[i];if(r<=m)returni;}}基本遗传算法伪代码/**Pc：交叉发生的概率*Pm：变异发生的概率*M：种群规模*G：终止进化的代数*Tf：进化产生的任何一个个体的适应度函数超过Tf，则可以终止进化过程*/初始化Pm，Pc，M，G，Tf等参数。随机产生第一代种群Popdo{计算种群Pop中每一个体的适应度F(i)。初始化空种群newPopdo{根据适应度以比例选择算法从种群Pop中选出2个个体if(random(0,1)

14、random(0,1)

15、个局部的最优解，达到全局的最优解。模拟退火法爬山算法与模拟退火法冶金学中，退火是将材料加热后再经特定速率冷却，目的是增大晶粒的体积，并且减少晶格中的缺陷。材料中的原子原来会停留在使内能有局部最小值的位置，加热使能量变大，原子会离开原来位置，而随机在其他位置中移动。退火冷却时速度较慢，使得原子有较多可能可以找到内能比原先更低的位置。其中k是一个常数，exp表示自然指数，且dE<0。温度越高，出现一次能量差为dE的降温的概率就越大；温度越低，则出现降温的概率就越小。又由于dE总是小于0，因此dE/kT<0，所以P(dE)的函数取值范

16、围是(0,1)。关于爬山算法与模拟退火，有一个有趣的比喻：爬山算法：兔子朝着比现在高的地方跳去。它找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是爬山算法，它不能保证局部最优值就是全局最优值。模拟退火：兔子喝醉了。它随机地跳了很长时间。这期间，它可能