跳出局部最优的方法

《跳出局部最优的方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、跳出局部最优的方法第16卷第1期工　科　数　学Vol.16,№.12000年2月JOURNALOFMATHEMATICSFORTECHNOLOGYFeb.2000组合优化算法中摆脱局部极小值的几种策略赵天玉(江汉石油学院,荆州434102)[摘要]局部搜索算法是一种非常有效的求解组合优化问题的算法,它具有通用、灵活等特点.但是,由于搜索空间和目标函数的复杂性,目标函数在搜索空间中有许多局部极小值点,使算法在这些局部极小值点处被“卡住”,大大影响算法的效果.对于此问题,笔者查阅了大量文献资料,结合自己的研究实践,总结出几种跳出局部极小“陷井”的策略.使用这些策略,有望使算法更加完善,在求解组

2、合优化问题过程中更能发挥其作用.[关键词]局部搜索;局部极小值;策略[中图分类号]O224　　[文献标识码]A　　[文章编号]10074120(2000)010067061　引　　言在管理科学,计算机科学,大规模集成电路设计及电子工程等科技领域中存在着大量组合优化问题.求解这些问题的传统算法是局部搜索算法,它具有简便、灵活等特点,能求解多种组合优化问题,是一种非常有效的求解组合优化问题的算法.然而,局部搜索算法也有其缺点,比如,最终解是局部最优解,最终解过分依赖于初始解.由于探索空间的复杂性,目标函数在搜索空间中有许多局部极小值点,局部搜索算法最致命的弱点是在搜索过程中很容易在这些局部极小

3、值点处被“卡住”,无法摆脱.针对这个问题,笔者查阅了大量文献资料,结合自己的研究实践,总结出几种跳出局部极小“陷井”的策略.本文先介绍组合优化问题和局部搜索算法,然后给出几种在求解适定性问题和旅行商问题过程中跳出局部极小“陷井”的策略.这些策略也适用求解其它组合优化问题,有望使局部搜索算法更加完善,在组合优化问题求解过程中更能发挥其作用.2　组合优化问题与局部搜索算法11组合优化问题组合优化问题是在给定的约束条件下,求目标函数最优值(最小值或最大值)的问题.它的一个实例可以表示为一个对偶(S,f),其中解空间S为可行解集,目标函数f是一个映射,定义为:f:S→R.使目标函数取最优值的解称为

4、整体最优解.例如,设(S,f)是组合优化问题的一个实例,iopt∈S,若对所有的i∈S,都有f(iopt)≤f(i),则称iopt为最小化问题minf(i)的最优解.i∈S　[收稿日期]19981215　[基金项目]江汉石油学院科研发展基金资助.1995-2004TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.工　科　数　学　　　　　　　　　　　　　　　第16卷21邻域结构与局部搜索算法设(S,f)是组合优化问题的一个实例,一个邻域结构是一个映射:N:S→2S.其涵意为,对每一个解i∈S,有一个解的集合Si

5、“邻近”i的.集合Si称为i的邻域,每一个j∈Si,称为i的一个邻近解.另外,约定,j∈SiZi∈Sj.设(S,f)是组合优化问题的一个实例,而N是一个邻域结构,从解i的邻域Si中选取新解j的方法叫产生器.设il∈Si,若对所有的j∈Si都有f(il)≤f(j),称il为最小化问题minf(i)的局部最优解.i∈S寻求局部最优解的传统算法是局部搜索算法,其基本法则是在某一解的邻域中迭代搜索,使目标函数逐步优化,直至不能再优为止.局部搜索算法LA可描述为[1]ProcedureLOCALSEARCH;begin　INITIALIZE(i0);　i∶=i0;　repeat　GENERATEjf

6、romSi;　iff(j)

7、取.第二,引入更复杂的邻域结构,使算法能对解空间的更大范围进行搜索.这种策略需要对待解问题有透彻的了解,一般来说是很难实现的.第三,改变局部搜索算法只接受优化迭代的准则,在一定范围内接受恶化解,另外也可变换搜索空间,使目标函数在解空间中有很少的局部极小值点.这种策略是可取的.下面就以适定性问题和旅行商问题为例介绍几种跳出局部极小“陷井”的策略.3　几种跳出局部极小“陷井”的策略在组合优化问题中,适定性问题可以说是著名的,