智能优化-ppt课件

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

1、第8章智能优化1常用算法与程序设计8.1模拟退火算法模拟退火算法概述8.2遗传算法遗传算法概述遗传算法关键参数8.3粒子群优化算法粒子群算法的基本结构粒子群算法的关键参数8.4人工神经网络神经网络模型神经网络学习规则主要内容2常用算法与程序设计8.1.1物理退火过程和Metropolis准则通过对固体退火过程的研究可知，高温状态下的物质降温时其内能随之下降，如果降温过程充分缓慢，则在降温过程中物质体系始终处于平衡状态。从而降到某一低温时其内能可达最小，称这种降温为退火过程，模拟退火过程的寻优方法称为模拟退火（simulatedannealing,SA）算

2、法。3常用算法与程序设计8.1.2模拟退火算法概述1.模拟退火的基本思想模拟退火算法可以分解为解空间、目标函数和初始解三部分。4常用算法与程序设计模拟退火算法简单步骤描述如下：(1)初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)，每个T值的迭代次数L；(2)对k=1，……，L做第(3)至第6步；(3)产生新解S′；(4)计算增量Δt′=C(S′)-C(S)，其中C(S)为评价函数；(5)若Δt′<0则接受S′作为新的当前解，否则以概率exp(-Δt′/T)接受S′作为新的当前解。(6)如果满足终止条件则输出当前解作为最优解，结束程序。终止

3、条件通常取为连续若干个新解都没有被接受时终止算法。(7)T逐渐减少，且T->0，然后转第2步。5常用算法与程序设计应用举例论货郎担问题(TravellingSalesmanProblem，简记为TSP问题)：设有n个城市，用数码1,…,n代表。城市i和城市j之间的距离为d(i，j)i,j=1,…,n．TSP问题是要找遍访每个域市恰好一次的一条回路，且其路径总长度为最短。求解TSP的模拟退火算法模型可描述如下：6常用算法与程序设计解空间解空间S是遍访每个城市恰好一次的所有回路，是{1，……，n}的所有循环排列的集合，S中的成员记为(w1,w2,……，wn)

4、，并记wn+1=w1。初始解可选为(1，……，n)；目标函数此时的目标函数即为访问所有城市的路径总长度或称为代价函数：并要求此代价函数的最小值。7常用算法与程序设计新解的产生随机产生1和n之间的两相异数k和m，若km，则将(w1,w2,…，wk,wk+1,…，wm,…，wn)变为：(wm,wm-1,…，w1,wm+1,…，wk-1,wn,wn-1,…，wk)上述变换方法可简单说成是“逆转中间或者逆转两端”。也可以

5、采用其他的变换方法，有些变换有独特的优越性，有时也将它们交替使用，得到一种更好方法。代价函数差设将(w1,w2,……，wn)变换为(u1,u2,……，un),则代价函数差为：8常用算法与程序设计ProcedureTSPSA:begininit-of-T;{T为初始温度}S={1，……，n};{S为初始值}termination=false;whiletermination=falsebeginfori=1toLdobegingenerate(S′formS);{从当前回路S产生新回路S′}Δt:=f(S′))-f(S);{f(S)为路径总长}IF(Δt<

6、0)OR(EXP(-Δt/T)>Random-of-[0,1])S=S′;IFthe-halt-condition-is-TRUETHENtermination=true;End;T_lower;End;End9常用算法与程序设计8.2遗传算法遗传算法是一类模拟生物进化的智能优化算法，它是由J.H.Holland于六十年代提出的。目前，遗传算法已成为进化计算研究的一个重要分支。与传统优化方法相比，遗传算法的优点是：群体搜索，不需要目标函数的导数，概率转移准则。10常用算法与程序设计8.2.1生物的进化与遗传生物进化的基本过程群体子群变异竞争婚配淘汰的群体

7、种群11常用算法与程序设计早在20世纪60年代初期就由美国大学的教授提出，并且在1975年教授发表了系统论述遗传算法的专著自然与人工系统中的自适应，其主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息。所以它的应用范围非常广泛，尤其适合于处理传统搜索方法难于解决的复杂和非线性问题，可广泛用于组合优化，机器学习，自适应控制，规划设计和人工生命等领域，从而确立了它在21世纪的智能计算技术中的关键地位。12常用算法与程序设计8.2.2遗传算法概述遗传算法已有了许多发展，但一般来说，其基本过程是：首先采用某种编码方式将解空间映射到编码空间（可

8、以是位串、实数、有序串、树或图，Holland最初的遗传算法是基于二进制串的，类