第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-05Survey on Optimization Method B ased on Chaotic Search andIts DevelopmentsLIU 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,er2g odicity and regularity.In the optimization area,the erg odic property can be used as an optimization mechanismto 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@。

收稿日期:2005-06-07目前,混沌已经成为一种新颖的优化技术。

混沌在优化中的应用主要有3种方式:(1)基于混沌搜索的优化方法,该方法直接利用混沌变量进行搜索;(2)基于混沌神经网络[1-3]的优化方法,通过将混沌动力学(Chaotic Dynamics)引入神经网络(NN)构成混沌神经网络(C NN)进行优化;(3)基于混沌分形的优化方法[4]。

本文针对基于混沌搜索的优化方法,在大量文献的基础上对该方法及其研究进展进行了总结。

1　基于混沌搜索的优化方法利用混沌运动的遍历性特点,即混沌运动能够在一定范围内按其自身的“规律”不重复地遍历所有状态,李兵等[5]首次提出一种混沌优化方法(Chaos Optimization Alg orithm,简称C OA),基本思想就是用类似载波的方法利用Logistic映射(式(1))将混沌状态引入到优化变量中,并把混沌运动的遍历范围放大到优化变量的取值范围,然后利用混沌变量进行搜索,并将此方法应用于连续复杂对象的优化问题。

　x n+1=μx n(1-x n) n=0,1,2,… 0≤x n≤1 μ=4(1)基于混沌动态的搜索过程分为2个阶段:首先,基于确定性迭代式产生的遍历性轨道对整个解空间进行考察。

当满足一定终止条件时,认为搜索过程中发现的最佳状态或已接近问题的最优解,并以此作为第二阶段的搜索起始点。

其次,以第一阶段得到的结果为中心,通过附加小幅度的扰动进一步进行局部区域内的细搜索,直至算法终止准则满足。

“粗搜索”加“细搜索”的二次载波方法由此奠定了基于混沌搜索的优化方法的基本方法。

此后基于混沌搜索的优化方法的大量工作都是在此基础上进行的研究和改进,或与其他方法结合形成混合混沌优化方法。

基于混沌搜索的优化方法还被推广应用于解决一类0-1整数规划问题[6]和TSP问题[7]。

2　改进的基于混沌搜索的优化方法进一步的仿真研究表明,李兵等提出的基本的基于混沌搜索的优化方法,对于搜索空间小时效果显著,但当搜索空间大时搜索时间较长,不能令人满意。

为了提高优化性能,一些文献对基于混沌搜索的优化方法进行了改进,改进工作主要包括:在搜索过程中利用各种方法缩小搜索范围;采用其他混沌映射代替Logistic映射;采用并行计算等。

2.1　缩小优化变量的搜索空间为提高搜索效率,张彤等[8]提出一种变尺度混沌优化方法(Mutative Scale Chaos Optimization Alg o2 rithm,MSC OA),通过变尺度地不断缩小优化变量的搜索空间,不断提高搜索精度。

针对变尺度混沌优化方法的缺陷,张火明等[9]做出一些改进,提高了收敛速度和精确性,这些改进包括:如果当前解是可行的,则以此解为中心在1/10当前邻域范围内局部搜索,直到迭代一定步数找不到更好解为止,然后再恢复大范围搜索,如此交替进行,以提高逼近最佳点的速度和精度;借鉴模拟退火的思想,按照一定比例逐渐降低变尺度的比例,并按一定比例逐次缩小扰动;同时给出适当的搜索次数的确定方法。

李祥飞等[10]将模拟退火策略引入混沌搜索,首先通过混沌粗搜索找出模糊神经网络参数系的次优解,然后采用基于模拟退火策略的时变参量自动缩小混沌变量遍历的区域范围,实现混沌细搜索的目的,并将此方法用于模糊神经网络控制器参数的优化设计。

2.2　采用其他映射研究文献后发现,大部分基于混沌搜索的优化方法都采用了李兵等的Logistic映射(式(1)),因此有一些研究工作者考虑采用其他映射来代替Logis2 tic映射,以获得更好的搜索性能。

为了克服现有混沌优化方法在大空间、多变量问题中的不足,尤勇等[11]发现一类在有限区域范围内折叠次数无限的一维迭代混沌自映射(式(2)),比一般的有限折叠次数迭代混沌自映射(如式(1)所示的Logistic映射)具有更好的混沌特性。

　x n+1=sin(2/x n) n=0,1,2,… -1≤x n≤1 x n≠0(2)为了克服混沌优化方法在缩小优化变量的搜索空间前所进行的盲目搜索,修春波等[12]提出一种具有双混沌机制的优化方法,同时利用2种不同的混沌机制Logistic映射(式(1))和立方映射(式(3))在搜索空间进行搜索,根据搜索情况来缩小搜索空间,然后继续搜索。

通过引入双混沌优化机制,不但可以增强搜索的充分性,而且可以减少盲目搜索的次数,提高搜索的效率,同时改善了算法的通用性。

　y k+1=αy3k-αy k+y k k=0,1,2,… -1≤y k≤1 α∈[313,4](3) 2.3　采用并行运算为了降低混沌系统对初始条件的敏感依赖性,加快搜索速度,梁慧勇等[13]提出并行混沌优化方法(P2Chaos),从几组不同的初始点出发进行并行运算,并在搜索到一定程度时进行二次载波,尽快找到最优解。

521总第144期 柳　贺　黄　猛　黄　道　基于混沌搜索的优化方法研究进展3　基于混沌搜索的优化方法与其他优化方法的结合基于混沌搜索的优化方法作为一种新颖的全局最优化技术,具有思路直观、无需求导等复杂计算,容易程序化实现等特点。

然而一种优化方法并不是万能的,也存在一定缺陷。

比如:搜索具有一定的盲目性;当搜索起始点选择不合适或遍历区间很大或控制参数及其控制策略选取不合适时,搜索结果很难达到或接近最优值,或者说算法可能需要花费很长的时间才能取得较好的优化性能;局部搜索能力不好等。

因此,很多研究工作试图将混沌搜索与其他算法如模拟退火算法(Simulated Annealing)、梯度下降法、遗传算法(G enetic Alg orithm)、单纯形法(Sim plex Method)、禁忌搜索(T aboo Search)、粒子群优化(Particle S warm Optimization)等结合起来,或将混沌搜索引入其他算法,或将其他算法引入混沌搜索优化方法中,或将混沌搜索与其他算法组合进行迭代。

3.1　与模拟退火算法的结合1983年K irkpatrick等将模拟退火算法(S A)用于组合优化。

S A是基于M onte Carlo迭代求解策略的一种随机寻优算法,其思想源于固体物质的退火过程。

在某一初温下,伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解。

王子才等[14]将混沌的遍历性机制引入模拟退火算法,基于混沌变量,提出一种混沌模拟退火优化方法,使得搜索过程同时具有两者的优点,其特点在于:首先,算法产生一混沌序列,在进行混沌遍历性搜索的同时,结合模拟退火算法的接受函数来确定初始温度,使得算法在此初温下具有较好的随机性(即在初温下算法几乎能接受任意状态);其次,利用混沌变量对当前点进行扰动,随着搜索的深入逐渐减小扰动的幅度。