全局优化的了望算法

第23卷第2期广东工业大学学报Vol.23 No.22006年6月Joumal of Guangdong University of TechnologyJune 2006全局优化的了望算法蔡延光' ,钱积新”,孙优贤2(1.广东工业大学自动化学院,广东广州510090;2.浙江大学工业控制技术国家重点实验室,浙江杭州310027)摘要:提出求解全局优化问题的了望算法.了望算法利用了望技术确定群山最高点的常识,通过了望管理机制、了望点产生策略、局部问题构造与求解机制，能在较短的时间内求解全局优化问题.大量的测试表明，了望算法具有较高的收敛率和较强的获得问题全部解的能力,对初始点几乎没有依赖,参数选择简单.了望算法能够保证在迭代过程中迭代点的质量逐步变好,所提出的三层次记忆机制极大地提高了望算法的收敛速度.大量的对比测试也表明,在收敛率和全局搜索能力等方面了望算法较遗传算法有一-定的优势,且在大多数情况下了望算法耗时较少.由于了望算法是根据人类的高级行为智能和推理智能提出的一-种智能算法,它为解决全局优化问题开辟了--条新的途径.关键词:了望算法;全局优化;智能算法中圈分类号:0224文献标识码:A文章编号:1007-7162(2006)02-000-11引言最近二十多年来,全局优化技术得到了长足的发展,模拟退火算法、遗传算法神经网络算法禁忌搜索算法( Tabu Search)、蚁群算法( Ant Colony Agrithm)等智能算法得到了广泛而深入的研究,在解决全局优化问题方面获得了很大的成功.模拟退火算法[14]是基于物理学中固体物质退火过程所表现出的特性而发展起来的一-种智能算法,属于一种低级的智能,它的计算量虽然较Monte Carlo方法显著减少,但其全局收敛性能仍然很差遗传算法[s]是基于生物本能的智能算法,是利用生物进化论中优胜劣汰、适者生存的原理及遗传机理而提出的-种智能算法,其主要优点是并行性和全局空间搜索;但其计算时间长,常常出现早熟收敛神经网络算法[89]是利用基于联结的生物神经系统协同工作原理而设计的- -种智能算法,其计算简单、快速;但它的参数鲁棒性差,容易陷于局部最优,有时可能收敛于问题的不可行解禁忌搜索算法([042]是对人类智能的--种模拟,具有较强的爬山能力和较好的局部改进能力;但它对初始解有较强的依赖性,迭代过程是串行的,参数的选择不当可能造成早熟收敛.蚁群算法[4151 是模拟蚂蚁群体行为特征而设计的一种基于动物智能的智能算法,利用正反馈原理,蚁群算法具有很强的鲁棒性和发现较好解的能力,是-种基于合作的无监督机制的并行算法;但是蚁群算法计算时间较长,参数选择更多地依靠实验和经验、没有一一个程序化的方法来确定,且容易出现迭代停止现象.以上提及的五大智能算法在解决实际问题时都容易陷于局部最优,且在迭代过程中不能保证迭代点中国煤化工收稿日期:2005-07-11MHCNMHG基金项目:国家自然科学基金资助项目(60374062);广东省自然科学基金项目(04009488);广东省科技计划项目(2004B10101038)作者简介:蔡延光( 1963-),男,博士,教授,主要研究方向为组合优化、智能优化智能决策支持系统..广东工业大学学报第23卷的质量逐步变好.本文基于了望技术确定群山最高点的常识,提出解决全局优化问题的了望算法.了望算法本质上是- -种基于监督的并行算法,在了望管理机制的协调下,把了望点产生策略和局部寻优算法有机地结合起来,能在较短的时间内求解全局优化问题.大量的测试表明,了望算法具有较高的收敛率和较强的获得问题全部解的能力,对初始点几乎没有依赖,参数选择简单,能够保证在迭代过程中迭代点的质量逐步变好.大量的对比测试也表明,在收敛率和全局搜索能力等方面了望算法较遗传算法有- -定的优势,且在大多数情况下了望算法耗时较少.为了加快了望算法的收敛速度,引人了望算法的三层次记忆机制,即基点记忆、了望点记忆、局部寻优记忆.了望算法模拟了人类的高级行为智能一视觉智 能、以及根据视觉信息分析问题的推理智能,是一种智能算法,与已知的五大智能算法在原理上有明显的不同,是解决全局优化问题的一个新尝试.为了实现方便,用C语言风格书写算法.1了望算法研究全局优化问题[minF(X),X∈RcE"(1)\R={XIg:(X)≥0,i= 1,2,.m},记G(X)=(g;(X),g2(X),",gm(X))".1.1 基本原理为了表述方便,引入几个基本概念.定义1对于问题(1),设 R'CR,x°∈R',1)把minF(x)(X∈R')称为x°处的局部优化问题,在不引起混淆时简称为局部问题;求局部问题的解称为局部寻优;2)如果在R'上F(X)是(下)单峰函数,则称R'为F(X)的(下)单峰区域,在不引起混淆时简称为单峰区域.定义2对于问题(1),1)了望基准点(简称基点)是可行域R中的-一个点;2)设x∈R是基点,基于基点x°的了望点是可行域R中的-一个点,在不引起混淆时把基于基点的了望点简称为基点的了望点或了望点;把x的全部了望点按照某种标准(例如欧氏距离、Hamming距离)分类,称x8的第k类了望点为X8的第k阶了望点.定义3局部寻优算法是一 -个基 于迭代的优化问题的求解方法,它具有固有特性:寻优过程所产生的迭代点必须在初始点所在的单峰区域内.很早以前,人类就知道通过了望确定群山最高点的常识.为了寻找(多峰)群山的最高点,人们- -般在群山中任意选取某座山的一个点作为出发点,进行局部爬高(即向该座山的最高点攀登),到达该座山的最高点(相对于群山而言是局部最高点)后.以此局部最高点作为基点进行了望,以寻找比基点“更高的点”;再以此“更高的点”所在中国煤化工点(例如,直接以.此“更高的点”作为出发点),开始下一轮的局部爬高,MHCNMH G点.那么,如何通过了望获得比基点“更高的点”呢?可以利用下面的常识解决这个问题:站得越高,望得越远;观测目标离得越近,看得越清楚,于是可对它的局部进行精细的观察;观测目标离得越远,可分辨第2期蔡延光,等:全局优化的了望算法3的尺寸越大,只能对其进行粗略的观察.选择基点的若干个了望点作为“更高的点”的候选点:在基点附近可稠密地取- -些 了望点,而在离基点远的地方了望点可取得稀疏-些.人们站在基点对了望点进行目测，当了望点在水平视线的上方,则认为了望点高于基点(如果忽略观测者自身的高度),“更高的点”就是该了望点.了望算法是利用以上常识而设计的一-种求解全局优化问题的智能算法.了望算法由了望管理机制(主要负责算法进程控制与协调)、了望点产生策略(负责产生了望点)、局部问题构造与求解机制3部分组成,其求解全局优化问题的基本思路是:1)由了望管理机制确定基点;2)由了望点产生策略产生基点的了望点;3)由了望管理机制按照- -定的标准选择了望点;4)构造所有被选定的了望点的局部问题并用局部寻优算法求解这些局部问题;5)在获得所有被选定的局部问题的解后,由了望管理机制确定下-个基点,进行新- -轮的迭代,直至算法终止条件出现,把当前最好可行解作为问题的解.针对以上基本思路,1.2节将讨论其中第1)、3)、5)项的实现问题(隐含在算法1中),第2节讨论其中第2)项的实现问题，第3节讨论其中第4)项的实现问题.1.2算法算法1是了望算法的一种实现形式,用于求解问题(1) ,其核心部分是:①外层循环:控制了望算法的进程选择基点x .当基点数超过预先设定的最大值或者允许了望标志等于False时，算法终止运行,输出最优解.②第2层循环:通过调用算法2,产生基于基点x*的各阶了望点.③内层循环:选择了望点进行局部寻优置允许了望标志的值.算法1求解问题(1)的了望算法输人:目标函数F(X)及约束条件G(X)≥0;控制参数设置:Max. Global Oulook =正整数; 1/(允许考虑的基点个数,即最大基点数,该参数为预先设定.)Max. Local Outlook =正整数; //(基点的了望点的最大阶数, Max Local Oulloo应该取得足够大,使得对于该基点，在R中不存在(或者可以忽略)基于它的大于Max .Local Oullook阶的了望点.) .初始:给定初始可行解x°∈R;x*=x°; //基点X咖= x8 ;/到 目前为止的最好可行解Oldxm*n= x"; //临时变量LocalXn= x"; //局部问题的解Outook _Flg= True; /允许了望标志，= True允许了望, = False不允许了望.Global. Outlook = 0; //基点计数Local. Outlolok=0; /门望阶数While Outlook Flg = True且Global, Outlook < Max .Global .01中国煤化工^YHCNMHGOldX*m= xi;Outlook. Flg = False;4广东工业大学学报.第23卷如果Global _Outlook =0则Local Oullook =0,否则Local Outlook=1; 1(初始时因为 x#=x0 ,故需要求解x*处的局部问题;但以后的x8本身是前面某个局部问题的解,因此不必求解x°处的局部问题.)While Local, Outlook≤Max. Local Outlok //第 2层循环开始Set. Outlook. Points= 中;Generate. Outlook Point( x8 ,Local. Outlook, Set Outlook. Points); //(产生了望点,见第2节 .)While Set _Outlook. Points≠φ //内层循环开始取集合Set Outlook. Points 中的第- -个元素x°;如果F(X°)≤F(x),则//片段 1,选择了望点进行局部寻优LocalX"in = Local Search(x"); /(片 段2. Local, Search( X):局部寻优算法.其功能是寻找X处的局部问题的解(通常把X作为初始点),返回值为局部问题的解.见第3节的讨论.)如果F(LocalX*)≤F(X")且LocalXmn≠0ldXin //片段 3X咖= Localxmi;Outlook. Flg= True;};在集合Set Oulok Points中删除x";}; //内层循环结束Local, Oullook= Local Outlook+1; /1 处理更高阶的了望点}; 1/第2层循环结束Global. .Outlook = Global, Outlook+ 1;x=xin; 11 X咖作为新的基点}; 1/外层 循环结束输出最优解xmn;结束.2、了望点产生策略1.1节所描述的关于获得了望点的常识(即在基7望点，而在离基点远的地方了望点可取得稀疏一些)可以有多种实现中国煤化工三种了望点产生策THCNMH略.本节仅讨论产生了望点的两个策略:方体了望点产土束略相你面」里瓜厂生策略.设x=(x想,x是,，x)"是基点,下面讨论在x处产生第k阶了望点的方体了望点产生策略和球面了望点产生策略..第2期蔡延光，等:全局优化的了望算法52.1方体了 望点产生策略方体了望点产生策略是在以x*为中心的棱长为2r的n维立方体表面和可行域R的交集中选取x8的第k(k=0,1,2,-.)阶了望点,其中r=H(h,k,x",F,G),它是h、k、X*、F、G的函数, h( > 0)为预先设定的-一个常数(称为基本了望步长),且ro=0< r< r2<.;当k=0时，x$是唯一的了望点.以n=2为例说明由方体了望点产生策略所产生的第k阶了望点的几何意义.例如,第h阶了望点取自于{(x+r,x土r)" ,(x士厂,程士r)"li=0,1,2,,h;j=0,1,2,-,k-1I∩R(见图1).下面讨论rn 的构造.主要考虑re是h、k的函数的情形,可以用等距法算术增距法、Fibonacci增距法、几何增距法确定T.1)等距法当可行域较小时,取r= kh,k=0,1,..(2)此时τλ1-η=h(k≥0),即rxi-r:(k=0,1,2,")是相等的.2)算术增距法图1用方体了望点产生当可行域较大时,取策略产生了望点n,= k(h+1h,k=0,1,2,-.(3)此时r+1-r=(k+ 1)h(k≥0),即{rx+1-re}是-一个公差为h的算术级数.3) Fibonacci 增距法当可行域很大时,取，ro=0,rs=Fa_h+ Tn-_,k=1,2,..(4)F其中F.是 Fibonaci 数,F。=1,F=1,F:= F-1+ F-2.易见，rk+1_τ=p(r- _)=Fk-1F:h(k≥1),即{(r.1- rn)/h }是一个Fibonaeci级数.4)几何增距法当可行域很大时,取Tk=°: (1+8)°-1h,k=0,1,2,-.(5)其中δ>0是预设的常数.易见τ+1-n=(1+δ)(r。→rn_1)=h(1+δ)*(k≥1),即{rn+1-r}是一个公比为1 + δ的几何级数.周知F +1+V5(m→∞)=(1+0.618),如果取δ =0.618, Fibnacai法就可近似地归结为2几何增距法的一种特殊形式.5) rn与x有关中国煤化工例如,当| X II ≠0时,取ro=0,r= |x* (1+8)*CNMH G(6)其期δ>0是预设的常数,1|x* |是x"的范数(例如取X如I =1宫xX ,或者取x =6广东工业大学学报第23卷21x9I).易见,r-n=δ|x* |(1+δ)* =(1+8)(r-r-)(k≥2).如果| x II =0,则式(6)中的| x II用一个较小的正数代替.根据以上讨论,可获得方体了望点产生策略产生了望点的算法.算法2:用方体了望点产生策略产生了望点Function Generate. .Outlook. Point( x8 , Local, Oullook , Set. .Outlook. Points)1*功能与参数说明:以x*为基点产生其第Local Outloloo阶的全部了望点,了望点保存在集合Set. Outlook. Points 中. *1. {for(i= - Local _Outlook; in≤Local, Outlook;iq ++ ){x= x + sigm(i)riqj; /sigp(x)为符 号函数for (i= - Local, Oullook; i≤Local. Oullook;i + ){ x2=是+sign(iz)rigy;for (ig= - Local Outlook; is ≤Local Outlook;ijz ++ ){ x3= x3+ sigm(iz)rig1;for (in = - Local Outlok; i,≤Local Outlook;in ++ ){x= x +sign(in)ri,i;如果lil,1i,-,1in I中至少有一个等于Local Outlook,且(x,x,", x)°∈R,则Set Outlook. Points = Set Outoo Points U{(x,x,., x,)"I;};|;2.2球面了望点产生策略球面了望点产生策略是在n维球面(x1-好)*+(xz- 妈)尸 +...+(x。-划)=了和可行域R的交集中选取x8的第k(k=0,1,2,-.)阶了望点,其中r与方体了望点产生策略的意义及确定方法完全相同.因为ro=0< r< r2<..., 故在球面了望点产生策略下,同阶了望点与X的距离相等,较高阶了望点离x较远.以n=2为例说明由球面了望点产生策略所产生的第k阶了望点的几何意义.如果希望至多取q个第k阶了望点,则不妨在x出发的q条射线(q条射线- -般是均匀分布的)与圆周(一好)2 +(xz-始) =芹的交点中选取可行点作为了望点(见图2).这里.n=a(h,h,X° ,F,G).类似于算法2,可获得球面了望点产生策略产生中国煤化工不再写出。YHCNMHG3局部问题构造与局部寻优算法了望算法的提出也受到下面设想的推动:为了求解目标函数是多峰函数的全局优化问题，第2期蔡延光,等:全局优化的了望算法7先把R划分为数量尽量少的两两互不相交的单峰区域(或者,把R .划分为两两互不相交的单峰区域,并使每个单峰区域尽量大),每个单峰区域对应- - 个局部问题,这样把全局优化问题分解为一系列目标函数是单峰函数的子问题(即局部问题) ;然后用目标函数是单峰函数的优化问题的求解方法获得局部问题的解;最后通过简单地比较各局部问题的解就可获得全局优化问题的解.但是,以上设想直接实现起来非常困难.了望算法充分地利用局部寻优算法的固有特性构造并求解局部问题,既不需要明确地界定单峰区域也不需要准确地划分R,结合了望点产生策略,解决全.图2用球面了望点产生局优化问题,是以上设想的一个改良.根据局部寻优算法的固有特策略产生了望点.性,显然只要给出局部寻优的初始点(为了节约计算时间,通常把了望点作为初始点),就可以获得局部问题的解;只要给出局部寻优的初始点,局部问题随之确定. .局部寻优算法可以通过对求解目标函数是单峰函数的优化问题的方法(如一维无约束优化的黄金分割法、成功-失败法牛顿法,多维无约束优化的拟牛顿法、共轭梯度法、DFP法,以及有约束优化问题罚函数法、SWIFT法、可行方向法、线性逼近法等)作-些必要 的改造得到,使其最大限度满足局部寻优算法的固有特性.按照这个思路,我们对以上提及的一- 些算法进行了改造.例如局部牛顿法是在牛顿法的基础上增加了对边界和拐点等的特别处理而获得的局部寻优算法,局部DFP法是在DFP法的基础上增加了对边界等的特别处理而获得的局部寻优算法.限于篇幅,改造过程从略.4了望算法的记忆机制为了避免在搜索过的区域进行重复搜索,提高算法的收敛速度，现引入了望算法的三层次记忆机制,即基点记忆(第- -层)了望点记忆(第二层)、局部寻优记忆(第三层).1)基点记忆基点记忆(MB)记忆全部基点.初始,MB= φ;如果x°为基点,则MB= MB∪{x}.如果实行基点记忆,则将算法1的片段3所对应的条件改为:如果F(oalxX*")≤F(xi)且LocalXrin eMB.这样,可以避免在迭代过程中重复地把一个 点作为基点.2)了望点记忆了望点记忆(M0)记忆全体构造过局部问题并实施过局部寻优的了望点.初始,MO= φ;如果x是某个基点的了望点,且求解过x°处的局部问题，则MO= MOU{x0}.如果实施了望点记忆，则将算法1的片段1所对应的条件改为:如果F(x0 )≤F(X")且不存在X'∈MO使|lX'-x° 1l≤e(ε≥0为预设的精度).这样,对任意点及其附近的点总共至多只能构造- -次局部问题.3)局部寻优记忆局部寻优记忆(ML)记忆局部寻优过程所经历的部分迭代点.初始, ML= φ;如果x是局部寻优过程所获得的一-个迭代点，且不存在X'∈ML满足X' = x≤e(e≥0为预设的精度)，则ML= MLU{xk };否则终止此局部寻优,因为如果F中国煤化工变性,继续进行局部寻优的话,则所得到的迭代点的质量-般不会比以TMCHC N M H G当有局部寻优记忆时,算法1的片段1所对应的条件也可改为:如果F(x°)≤F∈x")且不存在X'∈ML使|X' - x0 II≤ε(ε≥0为预设的精度).8广东工业大学学报第23卷MB、MO、ML体现了了望算法3个层次的记忆,显然有MBcML,MOcML,根据需要选择其中-一个或多个记忆.为了实现对MB、MO、ML中的元素进行快速查找(如二分查找),在迭代过程中应该同时对它们的元素进行排序(如二分插人排序).5测试结果与评述用了望算法对一些著名的基准问题( Benchmark Problem, 如见文献[ 16])进行大量的反复测试,结果令人满意.为了进一一步了解了望算法的性能,我们用遗传算法做对比测试.限于篇幅,这里仅列出对4个著名的基准问题所作的对比测试结果,并进行了简要的评述.所有算法使用C语言编程实现,并在赛扬2.4G台式机上执行. .问题1 F,(x)=x +3x2-9x,x∈[-5,5].该问题的解有两个:x=1,x= -5.min FI(x)= -5.周知,非智能算法如成功-失败法、0.618法很难获得该问题的解.问题2 Rosenbrock 函数:F2(x,x2)=10(x2- x)*+(1- x)",x∈[- 10,10],i=1,2.最优解(1,1)" ,min F2(x,x2)=0.问题3六驼峰- 驼背(Six Hump Camel- Back)函数: F;(x),x2)=4x-2.1项+ 9/3+ x-4x经+4xi,x∈[-5,5],i=1,2.该问题的解有两个:(0.089842, - 0. 712656)",(- 0.089842,0.712656)" ,min F3(x,xz)=- 1.0316285.问题4球体模型(Sphere Mode):F(xn,*,.",xn)=对+垃+...+ x起,x∈[- 100, 100],i=1,2,,n.取n=8.最优解x; =0(i=1,2,",n),min F4(x],x2)=0.了望算法的参数设置见表1.表1了望算法的参数设置问题参数设置1)最大基点数:[4,6]中的随机整数.2)基点的了望点的最大阶数:11.3)初始解:可行域中的随机数.4)了望点产生策略:方体了望点产生策略,其中基本了望步长为[0.9,1.1 ]中的随机数, r用等距法确定.5)局部寻优算法:局部牛顿法,精度为[ 10~4 , 10-6 ]中的随机数.6)记忆机制:基点记忆、了望点记忆.21)基点的了望点的最大阶数:22.2)局部寻优算法:局部DFP法,精度为[ 10~*, 10~°]中的随机数.3)其余参数同问题1的设置.31)基点的了望点的最大阶数:11.2)其余参数同问题2的设置.4 1)最大基点数:[2,4]中的随机整数. 2)基点的了望点的最大阶数:4.3)了望点产生策略:球面了望点产生策略,其中基本中国煤化工数,每阶了望点的数目为[4,6]中的随机整数(在对应的球面上近似均YHCNMHG定.4)局部寻优算法:局部DFP法,精度为[10-* , 10-°]中的5)其余参数同问题1的设置.第2期蔡延光,等:全局优化的了望算法遗传算法的参数设置:二进制编码方法,种群数为80,交叉概率为0.6,变异概率为0.001.收敛准则:4个问题的遗传代数分别为200、1003002000(实际上,我们对这4个问题中的每一个分别做了1002003005001000、2000、5000代的遗传算法运行测试，从时间耗费和收敛率方面综合考虑,前述所列遗传代数于相应问题为最有利的配置) .测试结果及评述见表2,其中:收敛率=收敛次数/测试次数.表2了望算法和遗传算法的对比测试结果 与评述测试平均耗收敛问题算法次数时/s 率/%评述1了望算法3000.23 100了望算法平均耗时只有遗传算法的12,两个算法的收敛率接近.遗传算法500 0.44 99 但是, 了望算法每次测试都能同时获得两个解,而遗传算法只有66%的概率同时获得两个解.22.36 100了望算法平均耗时较多,大约是遗传算法的4倍.主要原因是作为遗传算法3003.1940局部寻优算法的局部DFP法在解该问题的局部问题时效率不高统计表明,每次测试执行局部寻优算法的次数是问题1的4.6倍左右;这就是说,若该问题的局部寻优效率达到问题1的局部寻效率的1/3,则平均耗时应与遗传算法接近.遗传算法收敛率太低,不到了望算法的1/2.3了望算法3000.93 100了望算法的平均耗时稍少,两个算法的收敛率接近.了望算法同时遗传算法5001.0598获得两个解的概率为99.6%;而遺传算法所有收敛测试都只能获得-个解,且每个解单独出现的机会相等.40.82100了望算法平均耗时只有遗传算法的1/5,了望算法的收敛率比遗传遗传算法3004.1583算法高17%.下面结合测试结果,对了望算法作--些简要的讨论.1)已知的测试表明,了望算法在取最大基点数4时能够求解最优解的个数至多为2的所有测试问题(包括本文的4个基准问题).显然,最大基点数设置得越大,获得全部解的可能性就越大.然而,大量的测试表明,最大基点数增大到一定程度后,其继续增大并不会导致算法的平均耗时的明显增大.例如，问题1取最大基点数4和最大基点数6的平均耗时相差只有1毫s左右.事实上,通过分析算法1就会发现:获得了问题的全部解后到算法结束的一段运 行所耗时间很少.2)在表1中,基点的了望点的最大阶数的值是照顾到基点、了望点产生策略及基本了望步长的所有组合情况而设定的,故在大多数情况下稍嫌大了一些.为了减少算法1的第2层循环的循环次数、提高算法的收敛速度,根据该参数的含义,可以对算法1稍作修改:在第2层循环开始的前1行,根据基点、了望点产生策略、基本了望步长和可行域的结构动态设置基点的了望点的最大阶数为一-个尽可能小的值(这一点不难做到，而且动态设置的值大多数情况下比表1设置的值要小).3)基本了望步长越小,了望算法对可行域将搜索中国煤化工版之,耗时减少,但可能遗漏重要的搜索区域因此需要对基本了望步长MHCNMHG望步长设置原则:当可行域较小时,基本了望步长应取得较小(如问题1~3),反之应取得较大(如问题4).当然,也可以在算法执行过程中对每个基点动态地确定基本了望步长.10广东工业大学学报第23卷4)在同一精度下对了望算法和遗传算法进行时间耗费比较似乎更加客观.但是,我们的测试结果表明,遗传算法有些测试进行了10多个小时而最好解仍未达到事先预定的精度要求,实际上陷入局部最优,造成无法确定该测试的时间耗费.本节所列的4个问题都曾出现过这种久不收敛的测试.6结论了望算法的原理和大量的测试表明,它具有如下特点:1)收敛率高.已知的测试表明,了望算法收敛率接近100% ,高于遗传算法.2)全局搜索能力强.已知的测试表明,了望算法获得问题全部解的概率超过0.99,较遗传算法有一-定的优势.了望算法利用了望点产生策略使迭代进程逃出局部最优,保证搜索的多样性,进而实现全局搜索,能保证迭代过程中所得到的迭代点的质量逐步变好.3)速度快.在大多数情况下,了望算法的时间耗费比遗传算法要少.特别是了望算法的记忆机制的应用能极大地减少时间耗费.4)魯棒性.了望算法的鲁棒性表现在3个方面:首先是它所能解决的问题的广泛性,只要问题形如式(1);其次是它对初始点几乎没有依赖性;最后是它的控制参数选择简单.5)并行性.了望算法并行化非常容易,例如用某个处理机(作为主处理机)对算法进程进行控制和协调产生了望点等,而其它处理机构造了望点处的局部问题并用局部寻优算法求解之.6)经过一些简单的改造,了望算法能有效地利用目标函数是单峰函数的优化问题的方法进行局部寻优,而后者经过半个多世纪的研究获得了不少的快速算法.这-优势是基本遗传算法所不具有的.，致谢:感谢邹谷山同志所作的部分测试工作.参考文献:[1]Metropolis N, Rosenbluh A w, Rosenbluth M N, Teller A H, Teller E. Equations o state calulations by fast computingmachines[J]. J Chemical Physics, 1953, 23: 1087-1091.[]irkpatrick s, Celatt C D, Vecchi M P. Optumization by similated anealing[J]. Science, 1983, 220: 671-680.[3]蔡延光,钱积新，孙优贤.多重运输调度问题的模拟退火算法[J].系统工程理论与实践，198,， 18(10): 11-15.[4]i M, Tang H. Aplication of chaos in simulated anelingJ]. Chaos, Solions and Fracals, 2004, 21(4): 933-941.[S]olland J H. Adapation in Nature and Arifciad Systems[ M] .Ann Arbor MI: University of Michigan Pess, 1975.[6]蔡延光,钱积新，孙优贤.多重运输调度问题的遗传算法与遗传局部搜索[J].系统工程理论与实践，1997,17(12): 101-107.[7]Baker B M, Ayechew M A. A genetic algihim for the vehicle routing prblem[J]. Computers andOPerations Research,2003,30(5):787-800.[8]HopfieldJJ, Tamk D w. Neural coputaion of decision in opimizaion poblems[J]. Biological Cybemetis, 1985, 52:141-152.[9]Zhang Y. Global exponential convergence of recurent neural netwr cretical Computer Soi-中国煤化Ience, 2004, 312(23): 281-293.[ 10]Glover F. Heritic for integer programming using surrogate conslTYHCNMH Gr7, 8: 156166.6[11]蔡延光，钱积新,孙优贤.带时间窗的多重运输调度问题的自适应Tabu Search算法[J].系统工程理论与实践，2000, 20(12): 42-50.第2期蔡延光,等:全局优化的了望算法[12]Caricato P, Chiani G, Grieco A, Gueriero E. Parallel tabu search for a pickup and delivery problem under track cont-ention[J]. Parallel Computing, 2003, 29(5) :631-639.[13]Ho s C, Haugland D. A tabu search heunstic for the vehicle routing problem with time windows and split deliveries[J].Computers & Operations Research, 2004, 31(12): 1947-1964.[14]Colormi A, Dorigo M, Maniezo V. Distributed optimization by ant colonies[ C]/Proc. of the Fist European Conf. OnArificial Life, Paris: Elsevier Publishing, 1991: 134-142.[15]Badr A, Fahmy A. A proof of convergence for ant algorithms[J]. Information Sciences, 2004, 160(14): 267-279.[ 16]王凌.智能优化算法及其应用[M].北京:清华大学出版社, 2001.Outlook Algorithm for Global OptimizationCAI Yan-guang' ,QIAN Ji-xin2 , SUN You-xian2(1. Faculty of Automation, Guangdong University of Technology, Guangzhou 510090, China2. National Labonatory of Industrial Control Technology , Zhejiang University, Hangzhou 310027, China)Abstract: Outlook algorithm is presented to solve global optimization problems in this paper. Based onommon knowledge that one decides the highest point of mountains by outlook, by employing supervisionmechanism of outlook, strategies of generating outlook points and mechanisms of constructing and solvinglocal problems, outlook algorithm can solve any global optimization problem in a relatively short time. Alarge number of tests show that outlook algorithm is of higher convergence ratio, stronger capacity to obtainall solutions of global optimization problems, litle dependence on initial solution and simplicity in decidingits control parameters. It can be ensured that the quality of iterative points will gradually improve in the it-erative process of outlook algorithm. The three-level memory mechanism of outlook algorithm greatly in-creases its convergence rate. A large number of contrast tests also show that outlook algorithm has advan-tage over genetic algorithm in convergence ratio and capacity of global search, and spends less time thangenetic algorithm in most cases. Since outlook algorithm simulates human behavioral and inferential itell-gence, it exploits a brand new way to solve global optimization problems.Key words:outlook algorithm; global optimization; itelligent algorithm中国煤化工MYHCNMHG