求解一类组合优化问题的混沌搜索法
2001年5月系统工程理论与实践第5期 文章编号:100026788(2001)0520102204
求解一类组合优化问题的混沌搜索法
张国平1,王正欧1,袁国林2
(1.天津大学系统工程研究所,天津300072.2.中国长江三峡工程开发总公司,湖北宜昌443002)
摘要: 把混沌引入各种传统的优化计算模型中以避免系统落入局部最优陷阱,是一种行之有效的
方法Λ本文提出一种利用混沌搜索一类组合优化问题最优解的模型,并对其进行了理论分析和数值模
拟Λ与混沌神经网络模型相比,本模型避免了模型参数选择的难题,具有实现方便,寻优效果好的优
点,为解决一类组合优化问题提供了新途径Λ
关键词: 混沌;组合优化;混沌神经网络;
中图分类号: O224 文献标识码: A α
A Chao tic Search M ethod fo r a C lass of
Com b inato rial Op ti m izati on P rob lem s
ZHAN G Guo2p ing1,W AN G Zheng2ou1,YU AN Guo2lin2
(1.In stitu te of System s Engineering,T ian jin U n iversity.T ian jin,300072,Ch ina;2.Ch ina Yangtze T h ree Go rges P ro ject D evelopm en t Co rpo rati on.Y ichang,443002,Ch ina)
Abstract It is a good idea to m erge chao s in to vari ou s conven ti onal op ti m alm ethods in
o rder to escape from localm in i m a.T h is paper p ropo ses a chao tic op ti m izati on model fo r
com b inato rial op ti m izati on p rob lem s and theo retically expounds that the model is
feasib https://www.wendangku.net/doc/6b487426.html,pared w ith chao tic neu ral netw o rk models,the p resen t model w ill avo id
the param eter settings of chao tic neu ral netw o rk models w h ich is often very difficu lt,so
it is easy to operate.M o reover,it can get better resu lts acco rding to num erical
si m u lati on.
Keywords chao s;com b inato rial op ti m izati on;chao tic neu ral netw o rk
1 引言
在科学、工程和经济领域中经常出现组合优化问题,其中许多组合优化都是N P困难的ΛT SP问题(即旅行销售者问题:有m个城市,选择一条经过各城市一次且仅一次的回路,使其路径长度最短Λ)就是一个典型的N P困难问题Λ求解N P困难问题的最优解的计算量随着问题规模的扩大而呈指数量级增长Λ这类问题尚无多项式时间算法Λ因此实现一种求解组合优化问题的有效算法是很有实践意义的Λ由于难以找到N P困难问题的全局最优解,人们转而构造了许多近似算法,它们包括贪婪法、局部搜索法、不完全枚举法等,这些方法在寻求较好解方面取得了不错的效果Λ近年来,一些新的、更有效的启发式算法在组合优化方面得到了广泛的应用,这些算法包括:模拟退火算法、禁忌搜寻、遗传算法和人工神经网络等Λ
混沌具有内在确定性与外在随机性的统一,它的一个轨道可以在其吸引子中稠密Λ根据混沌吸引子的这种特性,当时间足够长,这根轨道就能以任意精度逼近吸引子中的任意点Λ因此,近年来人们开始尝试利用混沌吸引子的这种特性来求解最优化问题Λ传统的梯度下降法总是易于落入局部最优解,Hopfield网络
α收稿日期:2000201221
资助项目:国家自然科学基金(79970042)
优化计算是基于能量函数的梯度下降法,因此利用Hopfield 网络进行优化计算也易于落入局部最优解Λ把混沌引入神经网络是使神经网络避免陷入局部陷阱的有效策略Λ1987年,F reem an 首先提出了混沌神经元的概念[1];1990年,A ihara 等人通过在传统神经元的活化函数中引入时间延迟构造了一个混沌神经网络[2];同时,Inoue 等人利用两个混沌振荡子耦合成一个神经元的方法构造出一个混沌神经计算机[3],这个模型在求解T SP 问题中取得了良好的效果Λ此后,人们通过各种各样的方法构造出了性能各异的混沌神经网络,包括通过在神经网络中引入噪声来产生混沌[4],在Hopfield 网络中加入自环(即W (i ,i )≠0)来产生混沌[5],在神经网络运动差分方程中加大时间步长来产生混沌[6]Λ最近,一个引人注目的混沌神经网络模型是混沌模拟退火神经网络[5]Λ由于混沌神经网络具有全局搜索能力[7],以上这些混沌神经网络在求解组合优化问题中都不同程度地取得了较好的效果,尤其是混沌模拟退火神经网络,不仅具有全局搜索能力,而且稳定性好,收敛速度快Λ图1是一个单一神经元模型的混沌模拟退火过程的输出结果[5]Λ从图1中看出,网络的输出经历了一个反倍周期分岔过程,一开始网络处于混沌状态,随着退火过程的发展,网络进入倍周期分岔阶段,最后网络输出稳定在最优解上Λ
图1
然而,对于一个非线性动力系统,它是否会产
生混沌,要取决于系统参数的选择Λ事实上,对于一
个非线性方程组,一组不同的参数,往往会产生一
个性质不同的动力系统Λ一个非线性动力系统何时
会产生混沌,产生混沌后如何控制混沌的发展,是
一件很困难的事情Λ上述混沌神经网络模型在确定
了合适的参数后有良好的寻优能力,然而如何确定
系统的参数却是一件很费时的事情Λ虽然根据理论
分析可以确定某些参数的取值范围[7],某个参数具
体应该取什么值还只能通过试验确定,而且,这些
参数没有普适性,只能针对具体问题具体确定Λ
然而另一方面,从图1中可以看出,网络在输出稳定的最优解之前,系统实际上已经多次经历过最优解或近似最优解了,如图中虚线所示Λ只是网络当时尚处于混沌状态,系统在经历最优解或近似最优解后又漂移到了其它地方Λ这就提醒我们,只要把网络在混沌状态下经历过的最优解或近似最优解记录下来,就不必等到系统稳定后再输出最优解Λ基于这样的想法,本文提出直接利用混沌搜索问题的最优解Λ同时,这样做的另一个好处是避免了混沌模拟退火神经网络等模型的参数选择问题,使优化计算变得既简单又有效Λ
2 模型的原理
本文采用L ogistic 混沌模型[8]来产生搜索路径序列,L ogistic 映射的形式如下:
f :x (t +1)=a ×x (t )×(1-x (t ))
参数a ∈(2,4], f :[0,1]→[0,1]
L ogistic 映射有如下特性:
1)当a ∈(2,3)时,映射f 有稳定的不动点;
2)当a ∈[3,3.57]时,映射f 处于倍周期分岔阶段;
3)当a ∈(3.57,4)时,映射f 失去稳定的周期轨道,出现混沌,但难以确定在那些点上其混沌集的一维L ebesgue 测度大于0;
4)当a =4时,[0,1]是f 的混沌不变集Ζ
在L ogistic 混沌不变集中,当时间足够长,f 的任一轨道在其中稠密,即对于ΠΕ>0,以及Πx ∈[0,
1],开球B (x ,Ε
)中必包含f 的一条轨道中的点Ζ反过来看,就是f 的任一轨道能以任意精度逼近[0,1]中的所有点Ζ
301第5期求解一类组合优化问题的混沌搜索法
本文就是利用a=4时的L ogistic映射混沌不变集的上述特性搜索问题的最优解Ζ对于求解m维最优化问题,相当于在m维空间中确定一个使目标函数值最小的点Ζ为此需要用m个独立的L ogistic映射来产生该空间中点的m个坐标分量Ζ因为每一坐标分量都能在[0,1]中稠密,所以这样产生的点将能在m维单位超立方体中稠密Ζ也就是说,这些点的序列能够以任意精度逼近超立方体中所有点,当然也能以任意精度逼近超立方体中的全局最优解Ζ根据这样的分析,L ogistic混沌模型可以用于求解连续最优化问题Ζ而组合最优化是离散最优化,把L ogistic混沌模型用于本文的组合最优化问题还需要作变换Ζ本模型的搜索原理与过程如下:
m维空间中一个点有m个坐标分量,让点的第i个坐标分量对应于第i个城市C i(i=1,2,…,m)Ζ对点的m个坐标分量排序(升序或降序),相应地会得到m个城市的一种排列,即一条路径Ζ这样,一个m维单位超立方体(设为A)中的任一点代表一条T S P问题的合法路径Ζ在这个超立方体A中规定如下等价关系E:A中点x与点y等价,当且仅当点x与点y的m个坐标分量的大小排列顺序相同(升序或降序)Ζ则超立方体A关于上述等价关系E的商集的每一个元素代表了这样一类点,这些点的m个坐标分量的大小排列顺序相同Ζ也就是说,商集的每一个元素代表T S P问题的一条合法路径Ζ换一个角度看,就是等价关系E形成了A的一个划分,划分的每一个子集是一个等价类,它是一条T S P问题合法路径的吸引域Ζ这里把T S P问题的合法路径看成有m!条,例如,对于5城市来说,把C1C2C3C4C5与C2C3C4C5C1看作两条不同的路径Ζ只有这样处理才能使商集与所有合法路径一一对应起来Ζ
3 模型的描述
表1 10城市坐标城市横坐标纵坐标11.01.0 22.00.5 35.03.0 46.01.0 58.03.0 67.57.0 75.09.0 82.57.0 91.06.0 101.25.0
对于给定的m城市T SP问题,要确定一条合法回路,就是要确定这m城市的一种排列顺序Ζ根据上节模型的原理,本模型的m城市排列顺序按如下方式产生:首先在(0,1)区间中产生m个随机数X (1:m)作为解空间中一个点的坐标,第i个随机数对应于城市C i(i= 1,2,…,m)Ζ将这m个随机数按升序(或降序)排列,这些随机数所对应的城市也同时获得一个排列,就把这个排列作为第一条路径Ζ后面新的路径将通过L ogistic映射来产生Ζ把上阶段的m个随机数X(1:m)作为初值,按式X(t+1)=4X(t)(1-X(t))得到新的m个值,再对这新的m个值排序,得到新的路径Ζ依此类推Ζ除第一个路径随机产生外,后面的路径全部由L ogistic映射产生Ζ
本模型相当于利用m个单元产生m个城市的合法路径,如按Hopfield利用m×m个单元来产生合法路径[9]计算量则要大得多Ζ目标函数是使路径长度d最小化:
m in6m i=1d(c i,c i+1)
其中规定:c m+1=c1,d(c i,c i+1)为城市c i与c i+1间的距离Ζ
计算步骤如下:
1)对X(i)赋随机初值,i=1,2,…,m,最优路径长度op t_d赋较大初值,对控制参数k赋一个恰当的初值;
2)把X(i)的排序结果赋给Y(i),对照X(i),Y(i)求得一个合法路径;
3)计算路径长度d;
4)记忆最短路径长度op t_d:if d 5)判断是否结束迭代:if f lag=k then stop; 6)用L ogistic映射产生下一组X(1:m): X(t+1)=4X(t)(1-X(t));f lag=f lag+1; 401系统工程理论与实践2001年5月 7)回到第2步Ζ4 计算实例 为检验上述模型的有效性,进行仿真计算是有必要的Λ为了能够与现有混沌神经网络模型的计算结果进行比较,我们选择了文献[3]中一个10城市T SP 问题作为算例Λ这10城市的坐标参见表1Λ由于可行路径的产生与城市坐标值无关,因此城市坐标可以任意选取,而不影响本模型的计算性能Λ 根据文献[3],本T SP 问题的最短路径长度是27.35Λ 100组试验的计算结果表明,有17组寻找到最短路径27.35,所搜索的路径长度最大值为30.78,100组路径长度的平均值为28.49Λ本模型计算结果的质量接近用混沌模拟退火神经网络模型计算结果的质量[5],而与Inoue 混沌神经网络[3]相比,效果则要好得多Λ 5 结论 对于耗散系统,只要各变量有界,一个混沌动力系统必然存在奇怪吸引子[10]Λ系统的单个轨道可以在吸引子中稠密Λ利用奇怪吸引子的这种特性进行优化计算,在时间足够长的条件下,能以任意精度逼近全局最优解Λ在建立模型时,根据具体问题的性质可以选择适当的混沌动力系统,包括L ogistic 映射、H enon 映射、L o renz 方程组、Ro ssler 方程组等典型混沌模型Λ选择这些混沌动力系统来进行优化搜索,具有模型结构简单,避免了艰巨的模型参数选择和易于实现的优点Λ这种方法既可以应用于求解连续对象的优化问题,也可应用于求解组合优化问题,是解某些优化问题的新途径Λ计算实例表明,直接利用混沌搜索最优解,计算效果良好Λ 参考文献: [1] F reem an W J .Si m u lati on of chao tic EEG pattern s w ith a dynam ic model of the o lfacto ry system [J ]. B i o l Cybern 1987,56(2-3):139-150. [2] A ihara K ,T akabe T ,ToyodaM .Chao tic neu ral netw o rk s [J ].Phys L ett A .1990,144(6-7):333 -340. [3] Inoue M ,N agayo sh iA .A Chao s neu ro 2compu ter [J ].Phys L ett A ,1991,158(8):373-376. [4] A ayakaw a Y ,M arumo to A ,Saw ada Y .Effects of chao tic no ise on the perfo rm ance of a neu ral netw o rk model fo r op ti m izati on p rob lem s [J ].Phys R ev E ,1995,51(4):R 2693-R 2696. [5] Chen L ,A ihara K .Chao tic si m u lated annealing by a neu ral netw o rk model w ith tran sien t chao s [J ]. N eu ral N etw o rk s .1995,8(6):915-930.[6] W ang L ,Sm ith K .O n chao tic si m u lated annealing [J ].IEEE T ran s N eu ralN etw o rk s .1998,9(4):716-718. [7] Chen L ,A ihara K .Global search ing ab ility of chao tic neu ral netw o rk s [J ].IEEE T ran s C irc Sys , 1999,46(8):974-993. [8] 刘秉正.非线性动力学与混沌基础[M ].长春:东北师范大学出版社,1994. [9] Hopfield J ,T ank D ."N eu ral "compu tati on of decisi on s in op ti m izati on p rob lem s [J ].B i o l Cybern , 1985,52(3):141-152. [10] [美]E N 洛伦兹.混沌的本质[M ].刘式达,刘式适,严中伟译.北京:气象出版社,1997. 5 01第5期求解一类组合优化问题的混沌搜索法 混沌粒子群混合优化算法 王大均，李华平，高兴宝，赵云川 四川蜀渝石油建筑安装工程有限责任公司，四川成都（610017） 摘 要：粒子群优化算法（PSO ）具有收敛速度快但易陷入局部最优点的特点，因此本文将在结合混沌运动的遍历性、伪随机性和对初值的敏感性等特点的基础上，对粒子群优化算法进行了改进，提出了一种基于混沌思想的粒子群优化算法（CPSO ），该算法保持了群体多样性，增强了PSO 算法的全局寻优能力，提高了算法的计算精度，改善了收敛性和鲁棒性，很大程度上避免了算法停滞现象的发生，是一种有效的优化搜索算法。 关键词：混合优化算法；混沌优化算法；粒子群优化算法 1. 引言 粒子群算法PSO(Particle Swarm Optimization) 是Kennedy J 与Eberhart R 于1995年借鉴鸟群和鱼群捕食过程的社会行为提出的[1]。该算法具有程序简单、控制参数少、寻优结果与初值无关、且具有一定的并行性等特点，因此从开始研究到现在短短的十年时间里，表现出强大的优化功能，被广泛应用到函数优化、神经网络训练、人工智能、模糊系统控制等领域。PSO 作为一种更高效的并行搜索算法，非常适于对复杂环境中的优化问题的求解，成为目前进化计算研究的一个热点。但是标准的粒子群算法表现出强烈的“趋同性”，对于单调函数、严格凸函数或单峰函数，能在初始时很快向最优解靠拢，但在最优解附近收敛较慢，对于多峰函数更易出现早熟现象以及运算量较大等缺点。 混沌学的诞生是20世纪人类科学史上继相对论和量子理论之后的第三次革命，混沌是指在确定性系统中出现的随机状态，为非线性系统的一种演变现象，它不是由随机性外因引起，而由确定性规则导致的对初始条件非常敏感的无固定周期的长期行为[2]。混沌运动能在一定范围内按其自身不重复地遍历所有状态，初始值条件极其微弱的变化会引起系统行为巨大变化。因此，本文将在对标准粒子群算法改进的基础上，将混沌思想引入到粒子群算法中，避免了易陷入局部最优值的缺点，大大改善了粒子群算法的优化性能。 2. 粒子群优化算法的改进 2.1标准粒子群优化算法 假设搜索空间是D 维的，搜索空间有 m 个微粒，每个微粒的位置表示一个潜在的解，微粒群中第 i 个微粒的位置用()iD i i i x x x X ,,,21L =→ 表示，第i 个微粒的速度表示为 ()iD i i i v v v V ,,,21L =→ 。第i 个微粒经历过的最好位置 ( 有最好适应度 )记为()iD i i i p p p P ,,,21L =→ ，称为个体极值best p 。整个微粒群迄今为止搜索到的最好位置记为 ()gD g g g p p p P ,,,21L =→ ，称为全局极值best g 。对于每一个微粒，其第 d 维()D d ≤≤1， 根据如下等式变化： 摘要针对传感器的覆盖，提出*********。引言无线传感器网络被广泛应用，如医疗、环境、军事方面。无线传感器网络存在两大问题：覆盖控制和节点能量。覆盖能够延长网络生存时间，国内外许多学者在这个方面做了大量的工作。有向传感器网络是无线传感器网络的一种，本文针对有向传感器网络的覆盖做研究。近年来，许多专家学者提出了有向传感器网络覆盖控制问题和解决方法。Ma等首次提[8]出了有向传感其网络的概念，设计了一种二维有向感知模型，并研究了覆盖问题。陶丹等[4]提出了一种基于虚拟势场的有向传感器网络覆盖增强算法，引入“质心”的概念，通过质心点在虚拟力的作用下，实现节点的运动，消除重叠区和盲区，从而提高整个网络的覆盖率，[5]但是质心所受合力的计算较复杂。符祥等基于全局贪心原则，提出了一种有向传感器网络覆盖算法。以节点各方向下一重覆盖区域的大小为优先级，优先确定一重覆盖区域面积最大[13]的传感器节点方向减少重叠覆盖区域。解决控制问题的方法还有很多，如覆盖控制算法，，粒子群算法等。粒子群算法具有较快的收敛速度，但容易进入“早熟”状态。[1]顾等混沌算法能很快的找到全局覆盖最优值，只能迭代60次，但混沌搜索式的随机性，遍[6]历性不如junxiao等圆映射公式好，junxiao等考虑了移动节点的能量，很好地实现了覆盖，[11]但是只针对全向传感器。李靖等的粒子群算法融入了模拟退火和轮盘赌的思想，很好地解决了粒子群算法易陷入局部解，但此算法的覆盖提高率并不 高。[1]在本文只针对覆盖问题，在顾的基础上，寻找全局最优值，对混沌粒子群算法进行改进，进一步提高网络覆盖性。与顾和李靖的模拟退火相比此算法具有更好的优越性。该算法利用粒子群算法较快的收敛速度和混沌搜索的遍历性、随机性，不仅保证了算法的收敛速度，而且有效避免了基本粒子群算法的“早熟”现象。仿真实验证明，该算法能有效地优化节点布局，扩大网络覆盖率。本文章节如下：第2节介绍网络模型，第3节详细介绍混沌粒子群覆盖优化算法；第4节是仿真实验和仿真分析。2网络模型 2.1 有向感知模型通常把感知模型抽象为一个四元组 粒子群算法解决函数优化问题 1、群智能算法研究背景 粒子群优化算法（Particle Swarm Optimization，PSO）是由Kennedy 和Eberhart 在研究鸟类和鱼类的群体行为基础上于1995 年提出的一种群智能算法，其思想来源于人工生命和演化计算理论，模仿鸟群飞行觅食行为，通过鸟集体协作使群体达到优。 PSO算法作为一种新的群智能算法，可用于解决大量非线性、不可微和多峰值的复杂函数优化问题，并已广泛应用于科学和工程领域，如函数优化、神经网络训练、经济调度、模式识别与分类、结构设计、电磁场和任务调度等工程优化问题等。 PSO算法从提出到进一步发展，仅仅经历了十几年的时间，算法的理论基础还很薄弱，自身也存在着收敛速度慢和早熟的缺陷。如何加快粒子群算法的收敛速度和避免出现早熟收敛，一直是大多数研究者关注的重点。因此，对粒子群算法的分析改进不仅具有理论意义，而且具有一定的实际应用价值。 2、国内外研究现状 对PSO算法中惯性权重的改进：Poli等人在速度更新公式中引入惯性权重来更好的控制收敛和探索，形成了当前的标准PSO算法。 研究人员进行了大量的研究工作，先后提出了线性递减权值( LDIW)策略、模糊惯性权值( FIW) 策略和随机惯性权值( RIW) 策略。其中，FIW 策略需要专家知识建立模糊规则，实现难度较大，RIW 策略被用于求解动态系统，LDIW策略相对简单且收敛速度快， 任子晖，王坚于2009 年，又提出了基于聚焦距离变化率的自适应惯性权重PSO算法。 郑春颖和郑全弟等人，提出了基于试探的变步长自适应粒子群算 法。这些改进的PSO算法既保持了搜索速度快的特点, 又提高了全局搜索的能力。 对PSO算法的行为和收敛性的分析：1999 年采用代数方法对几种典型PSO算法的运行轨迹进行了分析，给出了保证收敛的参数选择范围。在收敛性方面Fransvan den Bergh引用Solis和Wets关于随机性算法的收敛准则，证明了标准PSO算法不能收敛于全局优解，甚至于局部优解；证明了保证收敛的PSO算法能够收敛于局部优解，而不能保证收敛于全局优解。 国内的学者：2006 年，刘洪波和王秀坤等人对粒子群优化算法的收敛性进行分析，指出它在满足收敛性的前提下种群多样性趋于减小，粒子将会因速度降低而失去继续搜索可行解的能力，提出混沌粒子群优化算法。 2008 年，黄翀鹏和熊伟丽等人分析惯性权值因子大小对PSO算法收敛性所带来的影响，对粒子群算法进行了改进。2009 年，高浩和冷文浩等人，分析了速度因子对微粒群算法影响，提出了一种基于Gaussian 变异全局收敛的粒子群算法。并证明了它能以概率 1 收敛到全局优解。 2010 年，为提高粒子群算法的收敛性,提出了基于动力系统的稳定性理论，对惯性权重粒子群模型的收敛性进行了分析，提出了使得在算法模型群模型收敛条件下的惯性权重和加速系数的参数约束关系，使算法在收敛性方面具有显著优越性。在PSO算法中嵌入别的算法的思想和技术。 1997年，李兵和蒋慰孙提出混沌优化方法； 1998年，Angeline在PSO算法中引入遗传算法中的选择算子，该算法虽然加快了算法的收敛速度，但同时也使算法陷入局部优的概率大增，特别是在优化Griewank 基准函数的优值时得到的结果不理想； 2004 年，高鹰和谢胜利将混沌寻优思想引入到粒子群优化算法中，首先对当前群体中的优粒子进行混沌寻优, 再用混沌寻优的结果随机替换群体中的一个粒子，这样提出另一种混沌粒子群优化算法。 全局搜索和局部搜索. 目前使用较普遍的、有影响的 全局搜索算法主要包括主从面算法、单曲面算法、级域算法、位码算法及NBS 算法; 局部接触搜索算法主要有基于"点面算法"、基于"小球算法"、基于光滑曲面(曲线)算法三大类. 接触界面算法目前主要有拉格朗日乘子法和罚函数法,以及扰动拉氏法和增广拉氏法. 此外,接触问题的并行计算也是不可忽视的研究内容 模拟退火算法和遗传算法等是较新发展起来的算法，算法引入了随机因素，不一定能找到最优解，但一般能快速找到满意的解。 局部搜索算法是从爬山法改进而来的。 爬山法：在没有任何有关山顶的其他信息的情况下，沿着最陡的山坡向上爬。 局部搜索算法的基本思想：在搜索过程中，始终选择当前点的邻居中与离目标最近者的方向搜索。 现实问题中，f在D上往往有多个局部的极值点。一般的局部搜索算法一旦陷入局部极值点，算法就在该点处结束，这时得到的可能是一个糟糕的结果。解决的方法就是每次并不一定选择邻域内最优的点，而是依据一定的概率，从邻域内选择一个点。指标函数优的点，被选中的概率大，指标函数差的点，被选中的概率小。考虑归一化问题，使得邻域内所有点被选中的概率和为1。 一般的局部搜索算法是否能找到全局最优解，与初始点的位置有很大的依赖关系。解决的方法就是随机生成一些初始点，从每个初始点出发进行搜索，找到各自的最优解。再从这些最优解中选择一个最好的结果作为最终的结果。起始点位置影响搜索结果示意图 爬山算法 1, n := s; 2, LOOP: IF GOAL(n) THEN EXIT(SUCCESS); 3, EXPAND(n) →{mi},计算h(mi), nextn=min{h(mi)} 4, IF h(n) 混沌粒子群优化算法¨ 计算机科学2004V01．31N-o．8 高鹰h2谢胜利1 (华南理工大学电子与信息学院广州510641)1 (广州大学信息机电学院计算机科学与技术系广州510405)2 摘要粒子群优化算法是一种新的随机全局优化进化算法。本文把混沌手优思想引入到粒子群优化算法中，这种方 法利用混沌运动的随机性、遍历性和规律性等特性首先对当前粒子群体中的最优粒子进行混池寻优，然后把混沌寻优 的结果随机替换粒子群体中的一个粒子。通过这种处理使得粒子群体的进化速度加快t从而改善了粒子群优化算法摆 脱局部极值点的能力，提高了算法的收敛速度和精度。仿真结果表明混沌粒子群优化算法的收敛性能明显优于粒子群 优化算法。 关键词粒子群优化算法。混沌手优，优化 ’ChaosParticle Swarm OptimizationAlgorithm GAO Yin91”XIESheng—Lil (College of Electronic＆Information EngineeringtSouth China University of Technology，Guangzhou 510641)1 (Dept．of Computer Science and Technology．GuangzhouUniversity·Guangzhou 510405)2 Abstract Particle swarm optimization is anewstochastic global optimization evolutionaryalgorithm．In this paper， the chaotic search is embeddedinto original particle swarm optimizers．Based on the ergodicity，stochastic property and 一般认为，NP完全问题的算法复杂性是指数级的。当问题规模达到一定程度时，这些算法显得无能为力。 局部搜索算法、模拟退火算法和遗传算法等是较新发展起来的算法，算法引入了随机因素，不一定能找到最优解，但一般能快速找到满意的解。 组合优化问题举例 TSP问题 从某个城市出发，经过n个指定的城市，每个城市只能且必须经过一次，最后回到出发城市，如何安排旅行商的行走路线以使总路程最短？ 约束机器排序问题 n个加工量为di(i=1,2,… n)的产品在一台机器上加工，机器在第t个时段的工作能力为ct,完成所有产品加工的最少时段数。 指派问题 一家公司经理准备安排N名员工去完成N项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时获得的回报是不同的。如何分配工作方案可以获得最大收益？ 0-1背包问题 设有一个容积为b的背包，n个体积分别为ai(i=1,2,… n),价值分别为ci (i=1,2,… n)的物品，如何以最大的价值装包？ 装箱问题 如何用个数最少的尺寸为1的箱子装进n个尺寸不超过1的物品？ SAT问题 称判定一个公式是否存在一个模型的问题为可满足性问题(以后简称为SAT 问题)。如果一个公式存在模型，则称该公式是可满足的，否则称为不可满足的。 皇后问题 在n×n的国际象棋棋盘上，摆放n个皇后，使得n个皇后之间不能相互“捕捉”？局部搜索算法 局部搜索算法是从爬山法改进而来的。 爬山法：在没有任何有关山顶的其他信息的情况下，沿着最陡的山坡向上爬。 局部搜索算法的基本思想：在搜索过程中，始终选择当前点的邻居中与离目标最近者的方向搜索。 爬山算法 1, n := s; 2, LOOP: IF GOAL(n) THEN EXIT(SUCCESS); 3, EXPAND(n) →{mi},计算h(mi), next n=min{h(mi)} # include H a r b i n I n s t i t u t e o f T e c h n o l o g y 智能优化课程设计 课程名称：智能优化算法 论文题目：混沌优化算法 院系： 班级： 设计者： 学号： 第一章混沌理论概述 引言 混沌是指确定动力系统长期行为的初始状态,或系统参数异常敏感, 却又不发散, 而且无法精确重复的现象, 它是非线性系统普遍具有的一种复杂的动力学行为。混沌变量看似杂乱的变化过程, 其实却含有内在的规律性。利用混沌变量的随机性、遍历性和规律性可以进行优化搜索, 其基本思想是把混沌变量线性映射到优化变量的取值区间, 然后利用混沌变量进行搜索。但是, 该算法在大空间、多变量的优化搜索上, 却存在着计算时间长、不能搜索到最优解的问题。因此, 可利用一类在有限区域内折叠次数无限的混沌自映射来产生混沌变量,并选取优化变量的搜索空间, 不断提高搜索精度等方法来解决此类难题。 混沌是非线性科学的一个重要分支, 它是非线性动力系统的一种奇异稳态演化行为, 它表征了自然界和人类社会中普遍存在的一种复杂现象的本质特征。因此, 混沌科学倡导者Shlesinger和著名物理学家Ford 等一大批混沌学者认为混沌是20 世纪物理学第三次最大的革命, 前两次是量子力学和相对论, 混沌优化是混沌学科面对工程应用领域的一个重要的研究方向。它的应用特点在于利用混沌运动的特性, 克服传统优化方法的缺陷, 从而使优化结果达到更优。 1.混沌的特征 从现象上看，混沌运动貌似随机过程，而实际上混沌运动与随机过程有着本质的区别。混沌运动是由确定性的物理规律这个内在特性引起的，是源于内在特性的外在表现，因此又称确定性混沌，而随机过程则是由外部特性的噪声引起的。混沌有着如下的特性: （1）内在随机性 混沌的定常状态不是通常概念下确定运动的三种状态:静止、周期运动和准周期运动，而是一种始终局限于有限区域且轨道永不重复的，形势复杂的运动。第一，混沌是固有的，系统所表现出来的复杂性是系统自身的，内在因素决定的，并不是在外界干扰下产生的，是系统的内在随机性的表现。第二，混沌的随机性是具有确定性的。混沌的确定性分为两个方面，首先，混沌系统是确定的系统;其次，混沌的表现是貌似随机，而并不是真正的随机，系统的每一时刻状态都受到前一状态的影响是确定出现的，而不是像随机系统那样随意出现，混沌系统的 —180 — 基于Tent 混沌序列的粒子群优化算法 田东平1,2 (1. 宝鸡文理学院计算机软件研究所，宝鸡 721007；2. 宝鸡文理学院计算信息科学研究所，宝鸡 721007) 摘 要：针对粒子群优化算法易陷入局部极值和进化后期收敛速度缓慢的问题，提出基于Tent 混沌序列的粒子群优化算法，应用Tent 映射初始化均匀分布的粒群，提高初始解的质量，设定粒子群聚集程度的判定阈值，并引入局部变异机制和局部应用Tent 映射重新初始化粒群的方法，增强算法跳出局部最优解的能力，有效避免计算的盲目性，从而加快算法的收敛速度。仿真实验结果表明，该算法是有效的。关键词：粒子群优化算法；Tent 映射；变异机制；判定阈值；收敛速度 Particle Swarm Optimization Algorithm Based on Tent Chaotic Sequence TIAN Dong-ping 1,2 (1. Institute of Computer Software, Baoji University of Arts and Science, Baoji 721007; 2. Institute of Computational Information Science, Baoji University of Arts and Science, Baoji 721007) 【Abstract 】Aiming at the problems of easily getting into the local optimum and slowly converging speed of the Particle Swarm Optimization(PSO) algorithm, a new PSO algorithm based on Tent chaotic sequence is proposed. The uniform particles are produced by Tent mapping so as to improve the quality of the initial solutions. The decision threshold of particles focusing degree is employed, and the local mutation mechanism and the local reinitializing particles are introduced in order to help the PSO algorithm to break away from the local optimum, whick can avoid the redundant computation and accelerate the convergence speed of the evolutionary process. Simulation experimental results show this algorithm is effective. 【Key words 】Particle Swarm Optimization(PSO) algorithm; Tent mapping; mutation mechanism; decision threshold; convergence speed 计 算 机 工 程 Computer Engineering 第36卷 第4期 Vol.36 No.4 2010年2月 February 2010 ·人工智能及识别技术· 文章编号：1000—3428(2010)04—0180—03 文献标识码：A 中图分类号：TP301.6 1 概述 粒子群优化(Particle Swarm Optimization, PSO)算法是种 进化算法，是Kennedy 等人在对鸟类、鱼类群集活动时所形成的协同智能进行总结而提出的[1]。与其他进化算法相比，PSO 算法简单通用、易于实现、可调参数少，具有较强的全局收敛能力和鲁棒性，且不需要借助问题的特征信息，非常适于对复杂环境中优化问题的求解。 目前，PSO 算法已被广泛应用于函数优化、神经网络训练、模糊系统控制等领域。然而，与其他全局优化算法类似，PSO 算法亦有其不足：易陷入局部极值点，进化后期收敛速度缓慢、精度较差等。 文献[2]介绍了一种自适应逃逸微粒群算法，通过逃逸运动，使微粒能够有效地进行全局和局部搜索，减弱了随机变异操作带来的不稳定性。但是，不论是基本PSO 算法还是此处的自适应逃逸PSO 算法，它们都具有不稳定性，究其原因是算法在初始化阶段微粒分布不均匀而造成的。文献[2]只指出算法不稳定性的原因，而并没有给出具体的解决方案。为此，本文提出基于Tent 混沌序列的粒子群优化算法。 2 粒子群优化算法 粒子群优化算法的基本思想源于鸟群飞行的觅食行为。在PSO 系统中，每个备选解被称为一个“粒子”，多个粒子共存与合作寻优。而每个粒子根据其自身“经验”和相邻粒子群的最佳“经验”，在问题解空间中向更好的位置“飞行”，以便搜索最优解。PSO 算法的数学表示如下： ()()()()()()11221id id id id gd id v t v t c r p t x t c r p t x t ω+=×+××?+?????? ××??? (1) ()()()11id id id x t x t v t α+=+×+ (2) 其中，()1id x t +,()id x t ,()1id v t +,()id v t 分别表示第i 个粒子在 1t +和t 时刻的空间位移与运动速度；ω为惯性因子；12,c c 分 别表示粒子个体的加速权重系数和粒子群体的加速权重系数；12,r r 为[0,1]之间的随机数；()(),id gd p t p t 分别表示第i 个粒子个体在搜索过程中的最佳位置和粒子群体在搜索过程中的最佳位置。 3 基于Tent 混沌序列的粒子群优化算法 3.1 混沌映射与混沌序列 一般将由确定性方程得到的具有随机性的运动状态称为混沌，呈现混沌状态的变量称为混沌变量。混沌是存在于非线性系统中的一种普遍现象，一个混沌变量在一定范围内具有随机性、遍历性和规律性的特点。利用混沌变量的这些特征进行优化搜索，能使算法跳出局部最优，保持群体的多样性，改善算法的全局搜索性能。 然而，不同的混沌映射算子对混沌寻优过程有很大的影 基金项目：陕西省教育厅科研计划基金资助项目(09JK335) 作者简介：田东平(1981－)，男，讲师、硕士，主研方向：模糊推理，专家系统，智能优化计算 收稿日期：2009-11-20 E-mail ：tdp211@https://www.wendangku.net/doc/6b487426.html, 第20卷第1期计算技术与自动化V o l120 N o11 2001年3月COM PU T I N G T ECHNOLO GY AND AU TOM A T I ON M arch 2001文章编号:1003—6199(2001)01—0001—05 混沌优化方法的研究进展 王 凌1,郑大钟1,李清生2 (1.清华大学自动化系,北京100084;2.北京航空航天大学理学院,北京100083) 摘 要:混沌是一种普遍的非线性现象,具有随机性、遍历性和内在规律性的特点。由于遍历性可作为避免搜 索过程陷入局部极小的有效机制,因此混沌已成为一种新颖且有潜力的优化工具。为了让混沌优化这一新兴研究方向为更多工作者所了解,此文综述了混沌优化方法的研究进展,包括基于混沌的函数优化与基于混沌神经网络的组合优化,并在分析混沌优化特点的基础上讨论了有待发展的若干研究课题。 关键词:混沌;优化;神经网络 中图分类号:TP301 文献标识码:A Survey on Chaoti c Opti m i za ti on M ethods W A N G L ing1,ZH EN G D a-zhong1,L IN Q ing-sheng2 (1.D ep t.of A utom ati on,T singhua U niversity,Beijing100084;2.D ep t.O f Physics,BUAA100083) Abstract:Chaos is a universal nonlinear phenom enon w ith stochastic p roperty,ergodic p roperty and regular p rop2 erty,w hose ergodicity can be used as a kind of m echanis m for op ti m izati on to effectively avoid the search being trapped in l ocal op ti m um,s o that chaos has been a novel and p rom ising tool for gl obal op ti m izati on.In this paper,a survey on chaotic op ti m izati on including functi onal op ti m izati on based on chaos and com binatorial op ti m izati on based on chaotic neural network has been p resented,the features of chaotic op ti m izati on have been analyzed,as w ell as s om e corres ponding studies to be i m p roved have been discussed. Key words:chaos;op ti m izati on;neural networks 1 引言 混沌是一种普遍的非线性现象,其行为复杂且类似随机,但存在精致的内在规律性。混沌的发现,对科学的发展具有空前深远的影响。近年来,混沌控制[1]、混沌同步[2]和混沌神经网络[3]受到了广泛关注,并展现出诱人的应用与发展前景。混沌具有其独特性质:①随机性,即混沌具有类似随机变量的杂乱表现;②遍历性,即混沌能够不重复地历经一定范围内的所有状态;③规律性,即混沌是由确定性的迭代式产生的。介于确定性和随机性之间,混沌具有丰富的时空动态,系统动态的演变可导致吸引子的转移。最重要的是,混沌的遍历性特点可作为搜索过程中避免陷入局部极小的一种优化机制,这与模拟退火的概率性劣向转移和禁忌搜索的禁忌表检验存在明显的区别。因此,混沌已成为一种新颖的优化技术,并受到广泛重视和大量研究。为了让混沌优化这一新兴研究方向为更多工作者所了解,本文对混沌优化方法的研究进展进行了综述,分析了各类混沌优化的特点,包括混沌在函数优化与组合优化中的应用,并讨论 收稿日期:2000-09-10 基金项目:国家自然科学基金项目(69684001)和国家攀登计划项目 作者简介:王凌,(1972—),男,博士、讲师,研究方向:优化算法及其应用、神经网络、HD S等。 第29卷增刊南 京 理 工 大 学 学 报V ol.29Supp 2005年10月Journal of N anjing U niversity of Science and T echnology Oct.2005 基于混沌搜索的优化方法的研究进展Ξ 柳 贺ΞΞ,黄 猛,黄 道 (华东理工大学工业自动化国家工程研究中心,上海200237) 摘 要:混沌是非线性系统中的一种较为普遍的现象,混沌现象具有随机性、遍历性和规律性的特点。在优化设计领域中,混沌现象的遍历性特点可以作为搜索过程中避免陷入局部极小的一种优化机制。目前混沌已经成为一种新颖的全局优化技术,基于混沌搜索的优化方法的研究受到了人们的重视。通过改进混沌搜索方法本身或是结合模拟退火、遗传等算法,优化性能获得提高。该文在大量文献的基础上,对基于混沌搜索的优化方法及其研究进展进行了总结。 关键词:混沌;混沌搜索;全局最优化 中图分类号:TP301 文献标识码:A 文章编号:1005-9830(2005)S0-0124-05 Survey on Optimization Method B ased on Chaotic Search and Its Developments LIU He,HUANG Meng,HUANG Dao (National Engineering Research Center for Industrial Automation, East China University of Science and T echnology,Shanghai200237,China) Abstract:Chaos is a universal phenomenon in nonlinear system.Chaos phenomenon has stochastic property,er2 g odicity and regularity.In the optimization area,the erg odic property can be used as an optimization mechanism to escape from local optimums.Chaos has been a kind of novel global optimization technique.People pay much attention to the research of the optimization method based on the chaotic search.By im proving the method or com2 bining it with other methods,such as simulated annedling,genetic alg orithm,etc.,the optimization performance has been im proved greatly.Based on the larg numbers of references,this paper gives a survey on the optimization method based on chaotic search and its recent research developments. K ey w ords:chaos;chaotic search;global optimization 近年来,混沌理论受到了广泛关注,随着对其研究的飞速发展,混沌已广泛渗透到各领域并展现出广阔的应用与发展前景。混沌现象行为复杂且类似随机,但存在精致的内在规律性。混沌现象具有其独特性质:(1)随机性,即混沌现象具有类似随机变量的杂乱表现;(2)遍历性,即混沌现象能够不重复地历经一定状态空间中的所有状态;(3)规律性,即混沌现象是由确定性的迭代方程产生的。在优化设计领域中,混沌现象的遍历性特点可以作为搜索过程中避免陷入局部极小的一种优化机制。 Ξ ΞΞ作者简介:柳贺(1979-),女,安徽凤阳人,博士生,主要研究方向:智能控制理论及应用,E2mail:mermerlou@https://www.wendangku.net/doc/6b487426.html,。 收稿日期:2005-06-07 变尺度混沌优化方法及其应用 X 张 彤(北京航空航天大学14系,100083) 王宏伟 王子才 (哈尔滨工业大学) 摘 要 基于混沌变量,提出一种变尺度混沌优化方法。该方法不断缩小优化变量的搜索空间并不断提高搜索精度,从而有较高的搜索效率。应用该方法对6个测试函数进行优化计算得到了满意的效果。 关键词 变尺度,优化,混沌优化方法分类号 TP 301.6 1 引 言 混沌(Chaos)是一种较为普遍的非线性现象,它看似一片混乱的变化过程实际上含有内在的规律性。一个混沌变量在一定范围内有如下特点:1)随机性,即它的表现同随机变量一样杂乱;2)遍历性,即它不重复地历经空间内的所有状态;3)规律性,该变量是由确定的迭代方程导出的。文献[1]考虑过用混沌变量进行优化搜索。其基本思想是把混沌变量线性映射到优化变量的取值区间,然后利用混沌变量进行搜索。几个测试函数优化实例的仿真结果表明混沌优化方法寻优效率明显优于其它随机搜索算法,如模拟退火、遗传算法。然而进一步的仿真计算表明该方法对于搜索空间小时效果显著,但当搜索空间大时却不能令人满意。基于此,本文提出了变尺度混沌优化方法,其特点在于:1)根据搜索进程,不断缩小优化变量的搜索空间;2)根据搜索进程,不断改变“二次搜索”的调节系数。对几个常用的复杂测试函数的仿真计算表明本文所提算法明显优于文献[1]算法。 2 变尺度混沌优化方法 本文选择(1)式产生的混沌变量来进行优化搜索 x k +1=L ?x k (1.0-x k ) (1) 其中L =4。若需优化n 个参数,则任意设定(0,1)区间n 个相异的初值(注意不能为方程(1)的 不动点0.25,0.5,0.75),得到n 个轨迹不同的混沌变量。 对连续对象的全局极小值优化问题 min f (x 1,x 2,…,x n ) x i ∈[a i ,b i ], i =1,2,…,n (2) 本文提出的优化方法步骤如下(记f (x 1,x 2,…,x n )为f (x i )): Step 1 初始化k =0,r =0。x k i =x i (0),x * i =x i (0),a r i =a i ,b r i =b i ,其中i =1,2,…,n 。这里k 为混沌变量迭代标志,r 为细搜索标志,x j (0)为(0,1)区间n 个相异的初值,x *i 为当前得到的最优混沌变量,当前最优解f *初始化为一个较大的数。 Vol.14No.3 控 制 与 决 策CON TR OL AN D DE CI S I ON 1999年5月 May 1999 X 国家高等学校博士点学科专项科研基金(9521320)资助课题 1997-11-17收稿,1998-04-07修回 禁忌搜索算法 又名“tabu搜索算法” 为了找到“全局最优解”，就不应该执着于某一个特定的区域。局部搜索的缺点就是太贪婪地对某一个局部区域以及其邻域搜索，导致一叶障目，不见泰山。禁忌搜索就是对于找到的一部分局部最优解，有意识地避开它（但不是完全隔绝），从而获得更多的搜索区间。兔子们找到了泰山，它们之中的一只就会留守在这里，其他的再去别的地方寻找。就这样，一大圈后，把找到的几个山峰一比较，珠穆朗玛峰脱颖而出。 当兔子们再寻找的时候，一般地会有意识地避开泰山，因为他们知道，这里已经找过，并且有一只兔子在那里看着了。这就是禁忌搜索中“禁忌表（tabu list）”的含义。那只留在泰山的兔子一般不会就安家在那里了，它会在一定时间后重新回到找最高峰的大军，因为这个时候已经有了许多新的消息，泰山毕竟也有一个不错的高度，需要重新考虑，这个归队时间，在禁忌搜索里面叫做“禁忌长度（tabu length）”；如果在搜索的过程中，留守泰山的兔子还没有归队，但是找到的地方全是华北平原等比较低的地方，兔子们就不得不再次考虑选中泰山，也就是说，当一个有兔子留守的地方优越性太突出，超过了“best to far”的状态，就可以不顾及有没有兔子留守，都把这个地方考虑进来，这就叫“特赦准则（aspiration criterion）”。这三个概念是禁忌搜索和一般搜索准则最不同的地方，算法的优化也关键在这里。 伪码表达： procedure tabu search; begin initialize a string vc at random,clear up the tabu list; cur:=vc; repeat select a new string vn in the neighborhood of vc; if va>best_to_far then {va is a string in the tabu list} begin cur:=va; let va take place of the oldest string in the tabu list; best_to_far:=va; end else begin cur:=vn; let vn take place of the oldest string in the tabu list; end; until (termination-condition); end; 以上程序中有关键的几点： 摘要 针对传感器的覆盖，提出*********。 引言 无线传感器网络被广泛应用，如医疗、环境、军事方面。无线传感器网络存在两大问题：覆盖控制和节点能量。覆盖能够延长网络生存时间，国内外许多学者在这个方面做了大量的工作。有向传感器网络是无线传感器网络的一种，本文针对有向传感器网络的覆盖做研究。 近年来，许多专家学者提出了有向传感器网络覆盖控制问题和解决方法。Ma等首次提出了有向传感其网络的概念，设计了一种二维有向感知模型，并研究了覆盖问题[8]。陶丹等[4]提出了一种基于虚拟势场的有向传感器网络覆盖增强算法，引入“质心”的概念，通过质心点在虚拟力的作用下，实现节点的运动，消除重叠区和盲区，从而提高整个网络的覆盖率，但是质心所受合力的计算较复杂。符祥等[5]基于全局贪心原则，提出了一种有向传感器网络覆盖算法。以节点各方向下一重覆盖区域的大小为优先级，优先确定一重覆盖区域面积最大的传感器节点方向，减少重叠覆盖区域。解决控制问题的方法还有很多，如覆盖控制算法[13]，粒子群算法等。粒子群算法具有较快的收敛速度，但容易进入“早熟”状态。 顾等[1]混沌算法能很快的找到全局覆盖最优值，只能迭代60次，但混沌搜索式的随机性，遍历性不如junxiao等[6]圆映射公式好，junxiao等考虑了移动节点的能量，很好地实现了覆盖，但是只针对全向传感器。李靖等[11]的粒子群算法融入了模拟退火和轮盘赌的思想，很好地解决了粒子群算法易陷入局部解，但此算法的覆盖提高率并不高。 在本文只针对覆盖问题，在顾[1]的基础上，寻找全局最优值，对混沌粒子群算法进行改进，进一步提高网络覆盖性。与顾和李靖的模拟退火相比此算法具有更好的优越性。该算法利用粒子群算法较快的收敛速度和混沌搜索的遍历性、随机性，不仅保证了算法的收敛速度，而且有效避免了基本粒子群算法的“早熟”现象。仿真实验证明，该算法能有效地优化节点布局，扩大网络覆盖率。 本文章节如下：第2节介绍网络模型，第3节详细介绍混沌粒子群覆盖优化算法；第4节是仿真实验和仿真分析。 2网络模型 2.1 有向感知模型 通常把感知模型抽象为一个四元组混沌粒子群混合优化算法
混沌算法
粒子群算法解决函数优化问题
局部搜索算法
混沌粒子群优化算法
局部搜索
局部搜索算法源代码
混沌优化算法算例
基于Tent混沌序列的粒子群优化算法
混沌优化方法的研究进展
基于混沌搜索的优化方法的研究进展
变尺度混沌优化方法及其应用
2013年数学建模第一题方法总结禁忌搜索算法
混沌算法