现代优化算法.ppt

1、现代优化算法,李金屏 济南大学信息科学与工程学院 模式识别与智能系统研究所 (1st version in 2002.9)2006.9,39,2,内容概要,优化算法简介运筹学 正交试验法 TABU禁忌搜索算法 模拟退火算法 遗传算法 begin INITIALIZE (i0, T0, L0); k:=0; i:=i0; repeat for l:=1 to Lk do begin GENERATE (j from Si) if f(j) f(i) then i:=j else if exp(f(i)f(j)/Tk random0,1 then i:=j end; k:=k+1; CALCULA

2、TE-LENGTH(Lk); CALCULATE-CONTROL(Tk); until stopcriterion end;,计算 冷却进度表,Markov链长,Metropolis规则,39,18,模拟退火算法,最初路径,算法结果,目前最好结果,39,19,模拟退火算法,一些文献： 1、康立山，谢云，尤矢勇等。非数值并行算法模拟退火算法。北京：科学出版社，1998年。 2、王卓鹏，高国成，杨为平。一种改进的快速模拟退火组合优化法。系统工程理论与实践，1999，(2): 7376。 3、赵玉清，余志军。加速全局优化鲍威尔法和模拟退火法的组合。电子学报，1998，26(9): 7577。 4、杨

3、若黎，顾基发。一种高效的模拟退火全局优化算法。系统工程理论与实践，1997，(5): 2935。,39,20,内容概要,优化算法简介运筹学 正交试验法 TABU禁忌搜索算法 模拟退火算法 遗传算法 现代优化算法再述 课题组的工作,39,21,遗传算法,Darwin 的物种进化的主要思想是自然选择(Natural selection)。生物通过竞争来进化，以适应环境。生物通过遗传(Heredity)、变异(Mutation)等过程实现进化。遗传和变异的物质基础是染色体(Chromosome)。染色体又是由DNA 和蛋白质组成的。基因中保留着遗传物质。通过基因的复制(production)、交叉(

4、crossover)和变异(mutation)实现生物的性状的变异和遗传。 标准遗传算法的基本框架是由Holland于20世纪60年代提出的，它使用二进制编码，采用赌轮选择和随机配对，关键是编码。这是一类模拟生物进化过程的全局性优化算法，其搜索效率取决于搜索策略或状态转移策略、编码策略、运行参数的合理配置等方面。对于具有下面数学结构的研究对象min（或max）f (x)，s.t. g(x) 0，xD 遗传算法可以具有较好的搜索效果。,39,22,遗传算法,基本思路： 第一步：建立研究对象的数学结构模型，确定目标函数类型（即求目标函数的最大值还是最小值?）。 第二步：确定表示可行解的染色体编码方

5、法，即确定个体基因型X及遗传算法的搜索空间。 第三步：确定解码方法，即确定由个体基因型X到相应表现型的对应关系或转换关系。,39,23,遗传算法,基本思路： 第四步：设计遗传算子，包括选择算子、交叉算子、变异算子等的具体操作方法。 第五步：确定个体适应度的量化评价方法，即制定由目标函数 f(x) 到个体适应度的转换规则。 第六步：确定遗传算法的有关运行参数。包括编码串长度l（对于二进制编码）、交叉概率Pc、变异概率Pm、种群规模M、终止代数T等运行参数的设置。 第七步：设计遗传算法程序，其中使用了最优保留策略。,39,24,遗传算法,为了提高其搜索效率，可以在三个方面提出改进措施： 1) 采用

6、更好的搜索策略。主要包括：精英策略（elitist strategy）；构造与模拟退火算法、局部搜索算法如最速下降法等相结合的混和遗传算法（hybrid genetic algorithm）；通过改造模式定理和引入半序关系将所有模式构成一个半序格，从而将人工智能理论中的状态空间搜索算法如A算法与遗传算法相结合而提出的统计遗传算法（statistical genetic algorithm）；基于家族优生学原理构成两两结合的家族竞争机制，通过引入正交设计法构造出“正交交配”算子，从而在每个家庭内部形成局部竞争环境的进化算法；利用小生境技术、聚类分析或狭义遗传算法而提出的分区域搜索遗传算法等。,3

7、9,25,遗传算法,2) 采用更加合理的编码策略。如采用十进制编码，多维实数编码，或根据模式定理将二进制编码的低阶、高平均适应度的长定义距模式转换为短定义距模式等。 3)合理配置运行参数。遗传算法的求解效率在很大程度上取决于编码串长度l（对于二进制编码）、种群规模M、交叉概率Pc、变异概率Pm、终止代数T、适应度函数f (M)等运行参数的设置，当然与具体的选择算子也有很大关系，这在搜索策略中已经有一定体现。 除了种群规模和终止代数之外，人们对于染色体编码、交叉和变异概率、适应度函数等进行了深入广泛的讨论。,39,26,遗传算法,编码串长度l直接决定问题的求解精度。选择策略、交叉算子和变异算子对

8、于种群早熟、收敛等有重大影响，不少工作对此进行了有益的探讨。适应度函数f (M)是遗传算法的一个瓶颈，人们针对不同问题提出了许多不同的适应度函数定义。 最近有文献研究了遗传算法的一些统计性质，提出进化截止代数和平均截止代数的概念，指出进化截止代数分布呈现典型的分布，还研究了遗传算法的优化效率。 这种研究对于深刻理解遗传算法非常有益。 事实上，进化截止代数分布之中蕴含着许多丰富的知识，比如，平均进化截止代数、成功率等主要依赖于哪些因素？种群规模M、研究对象数学结构的极值个数、极值大小分布和极值区域半径分布、染色体串长l等在进化截止代数分布中主要起到什么作用？,39,27,内容概要,优化算法简介运

9、筹学 正交试验法 TABU禁忌搜索算法 模拟退火算法 遗传算法 现代优化算法再述 课题组的工作,39,28,现代优化算法一般性描述,全局性优化理论的一般性描述 首先，需要确定的是状态的表示，即决策变量x的编码问题。通常x是以数值方式编码比如浮点数，也有二进制方式，还有符号编码如字母等。实际上编码方式不应该影响搜索的结果，只要x与其编码具有一一对应的关系，如浮点数编码与二进制编码之间就存在明确的一一对应的关系。原码编码采用决策变量本身作为状态参量，也是一种编码方式，只不过我们已经习以为常了。选择不同的编码方式对于优化效率具有不同的影响。我们采用C(x)表示的x编码，称为个体。,39,29,现代优

10、化算法一般性描述,全局性优化理论的一般性描述 两种搜索方式：单点法和多点法。 单点法是一种串行方式，即从一个初始状态（单个个体）出发，按照某种方式转移状态进行全局优化，这种方式通常要消耗较多机时； 多点法是一种并行方式，即从可行域的多个初始状态（多个个体）同时进行搜索寻找全局最优解，但是空间开销大。 根据各态历经假设，理论上二者可以具有相同的搜索效果。事实上，单CPU情况下的单点法和多点法并没有本质性的区别。,39,30,现代优化算法一般性描述,全局性优化理论的一般性描述 两种搜索策略：确定性和概率性。 由于许多实际问题的决策变量不连续，或者没有解析表达式或者解析表达式比较复杂致使无法进行理论

11、分析，而且大多数问题的极值数目未知，无法提供全局性搜索的确定性信息，因此通常采用概率性搜索策略，包括：1. 状态转移规则，2. 状态接受规则。 状态转移规则研究从当前状态C(x)如何转移到下一状态C(x)，即C(x)+C C(x)，C表示状态转移量，需要根据决策问题的数学结构来确定。这是因为C反映f(x)的邻域结构，合理的C应该保证概率性搜索的状态具有最大代表性。这就要求C符合最佳概率分布。,39,31,现代优化算法一般性描述,全局性优化理论的一般性描述 状态接受规则研究如何接受按照状态转移规则获得的新状态，即确定性接受还是概率性接受。确定性方式仍然是只接受更好的结果，拒绝恶化的结果。通常使用

12、概率性方式，也有两种做法：一种是更好结果肯定接受，恶化结果按照一定概率接受；另一种是无论好恶均以一定概率接受，只是结果越好接受概率越高。不同方式对于最终结果会有不同影响。由于状态接受规则体现优胜劣汰的思想，全局优化也会陷入局部极优解，因此必须考虑多样性问题。单点法,39,32,现代优化算法一些特例,在可行域中进行纯随机性概率搜索，将获得Monte Carlo方法，此时的状态转移完全是随机的，没有利用任何启发信息。 随机地从多个初始状态出发进行局部搜索，实际上是一种最原始的全局性和局部性优化算法的结合，即多点随机试探局部搜索法，此时的启发信息完全体现于局部搜索部分，全局性优化部分仍然是随机的和盲

13、目的。 利用禁忌表记录曾经或已经到达过的局部极优解，下次搜索时利用该表信息不再或有选择地搜索这些点，以此跳出局部极优解，增加搜索的区域，是禁忌搜索的基本思想。显然这种搜索的效率是比较高的，但参数设置是一个需要认真研究的问题，涉及到禁忌对象、禁忌长度、候选集合、评价函数、特赦规则、终止规则等的合理确定。这里的全局性启发信息体现在禁忌表。,39,33,现代优化算法一些特例,从可行域的某个初始状态出发，按照符合一定概率分布的状态转移规则搜索最优解，利用概率的方法接受新状态，即更好结果肯定接受，恶化结果按照一定概率接受，而且随着搜索的进行接受恶化解的概率逐渐变小，这是模拟退火的基本思想。这种搜索没有结

14、合局部优化算法，但具有隐含的局部优化能力。需要考虑的参数包括初始温度选取、Markov链长度（平衡态判据）、温度控制策略、终止条件等。这里的启发信息体现在状态转移规则和状态接受规则，分别指导全局性优化和局部性优化。,39,34,现代优化算法一些特例,从可行域中的多个初始状态（个体）出发进行并行搜索，在搜索过程中个体之间不断交流信息，采用概率方式接受新个体，比如赌盘形式。这是遗传算法的基本思想，采用一种群体搜索策略。这种方法具有很强的全局搜索能力和较强的局部搜索能力，自动嵌入有增加多样性的算子（交叉和变异运算），主要缺陷是容易出现“早熟”。需要考虑的因素有个体编码方式、种群规模、选择算子、交叉算

15、子、变异算子、终止代数、适应度函数等。其启发信息在于选择方式（直接影响以后搜索的区域）、个体信息交流（模式的优化组合）等。 结论：在全局性优化算法的一般性描述下各种优化算法之间存在着密切的内在联系，是不同情况下的特殊算法。其中禁忌搜索、模拟退火属于单点法，遗传算法属于多点法，Monte Carlo方法和多点随机试探局部搜索法既可以以单点法方式进行，也可以以多点法方式进行。,39,35,内容概要,优化算法简介运筹学 正交试验法 TABU禁忌搜索算法 模拟退火算法 遗传算法 现代优化算法再述 课题组的工作,39,36,课题组的工作已经完成的工作,局部优化算法的改进：梯度下降法自适应调整其学习率（步

16、长调整） 模式识别与人工智能、系统工程与电子技术 遗传算法的参数确定：遗传算法平均截止代数和成功率与种群规模之间的关系。 系统仿真学报（增刊） 遗传算法改进：与正交试验法相结合正交遗传算法。 电子学报 遗传算法改进：与梯度下降法的结合混合遗传算法。 现代信息技术理论与应用CIE-YC2002 遗传算法改进：与小生境进化算法、聚类分析相结合。 小型微型计算机系统,39,37,课题组的工作Publications,BP小波神经网络快速学习算法研究。李金屏，王风涛，杨波。 系统工程与电子技术，Vol.23,No.8,2001,72-75. 遗传算法平均截止代数和成功率与种群规模之间的关系。李金屏，何苗，杨波。系统仿真学报(增刊),2001, Vol.13, 206-210. 提高BP小波神经网络收敛速度的研究。李金屏，何苗，刘明军，杨波。模式识别与人工智能, 2002, 15(1):28-35。 正交遗传算法。史奎凡，董吉文，李金屏，曲守宁，杨波。电子学报 ，2002，Vol.30，No.10. 利用混合遗传算法提高小波神经网络收敛速度的研究。李金屏，牛业亭，卢刚。现代信息技术理论与应用：CIE-YC2002，701-705，合肥：中国科学技术大学出版社，2002.8。 基