多点收缩混沌优化方法及全局收敛性证明

刘勇,陆军,徐裕生,李阳

(1.西安建筑科技大学理学院,陕西西安 710055;2.郑州师范高等专科学校,河南郑州 450044)

多点收缩混沌优化方法及全局收敛性证明

刘勇1,陆军2,徐裕生1,李阳1

(1.西安建筑科技大学理学院,陕西西安 710055;2.郑州师范高等专科学校,河南郑州 450044)

针对目前混沌优化算法在选取局部搜索空间时的盲目性,提出一种具有自适应调节局部搜索空间能力的多点收缩混沌优化方法.该方法在当前搜索空间搜索时保留多个较好搜索点,之后利用这些点来确定之后的局部搜索空间,以达到对不同的函数和当前搜索空间内已进行搜索次数的自适应效果.给出了该算法以概率1收敛的证明.仿真结果表明该算法有效的提高了混沌优化算法的性能,改善了混沌算法的实用性.

混沌优化;多点收缩混沌优化算法;全局收敛性;概率1收敛

1 引言

混沌是一种普遍的非线性现象,具有随机性、遍历性和内在的规律性的特点.基于混沌遍历性的混沌优化一经出现,其直观、易实现的特点就引起了广泛关注[13].但目前混沌优化发展历史较短,因此许多问题还有待进一步研究和讨论.现有的研究表明,当直接利用混沌变量进行搜索时:1)单纯的提高迭代步数不能显著的提高算法搜索的遍历程度;2)多轨道并行搜索不能显著提高混沌搜索的遍历程度;3)在粗略搜索的最优点附近进行细搜索,可能导致当前最优点偏离全局最优点[4],影响算法的搜索速度.由此可见,在大范围的搜索后对有较大概率出现全局最优点的局部空间进行再搜索是提高混沌优化算法性能的一种较为理想的改进方法.但易知不同的函数在进行局部搜索前需要进行的搜索次数是不同的,需要进行局部搜索的区域也是不同的,故对局部搜索的控制策略和局部搜索策略的选取是至关重要的.而以往的混沌算法都是在进行一定次数的混沌搜索的基础上,以固定的比例缩小搜索空间[23],显然这种局部搜索空间的选取是较为盲目的.本文提出利用多个较好搜索点来确定局部搜索空间的策略,这种策略能针对不同的函数和针对在当前搜索空间内已进行搜索的次数自适应的调节之后的局部搜索空间.通过这种改进,既保证了算法的收敛速度又可对算法的全局收敛效果进行控制,从而大大提高了混沌算法的实用性.

2 算法的初步介绍

2.1 局部搜索空间的选取策略

多点收缩混沌优化方法局部搜索空间选取策略如图1所示.其中A为当前搜索空间, “·”表示在空间A内已得到的所有搜索点,“*”表示在空间A内通过比较得出的前个较好搜索点.本文选取包含所有“*”在内的最小超长方体B为相对空间A的局部搜索空间,同样在B空间上可继续按上述过程再进行搜索并重新确定相对B空间的局部搜索空间,直到达到算法终止条件.

图1 局部搜索空间选取策略示意图

2.2 算法自适应控制能力的分析

对于性态较好的函数和在空间A内搜索点数iter相对较多时,搜索空间宜快速收缩以提高搜索效率;而在相反情况时,搜索空间则不宜缩小过快以避免搜索陷入局部最优.当按照上述方法确定局部搜索空间时,由于混沌变量具有随机性、遍历性的特点,故函数性态的好坏和iter的大小将直接决定搜索得到的num个较好点的集中和分散程度,从而决定了之后局部搜索空间的大小,而多个较好点的使用又可以极大概率的保证全局最优点落在由其决定的局部搜索空间之中,由此就实现了算法对上述不同情况的自适应控制.

3 多点收缩混沌优化算法

对于连续的全局优化模型

4 算法全局收敛性的证明

4.1预备知识

4.2 全局收敛性证明

5 数值方真

5.1 算法对随机参数自适应性测试

为了检验算法对不同函数和参数的自适应性.我们选取了两个经常被用来测试混沌化算法有效性的两个函数进行了仿真测试.

设计随机操作如下:

1)混沌变量在区间(0,1)上随机取定;

2)参数iter在100∼1000之间随机取定;

3)参数num在10∼20之间随机取定.

F1和F2理论最小值皆为0.表1为在以上的随机操作和ε=0.01的规定下我在P4(1.4G) 的PC机上连续对F1和F2进行了10次运算的结果.

图1 算法随机参数仿真结果

由表1可见对F1和F2的10次随机仿真运算均能很好的收敛到各自的理论值,并且所耗费的时间基本是相同的,而当进行随机参数实验时文[1-3]的算法均很难在短时间内收敛,这充分证明了本文算法的有效性和对不同的参数和函数的自适应性.

5.2 算法对于不同维数的自适应性

一个好的优化算法最终是为解决实际问题服务的,而实际问题一般为高维函数,为了测试本算法对高维函数的适应性,我们进行如下数值仿真.

由表可见当n=1,2,…,10时算法均能全局收敛,虽然随着函数维数的增长计算精度有所降低,且计算时间快速增长,但是由于所有计算结果都是在相同参数下计算得出的,所以整体的计算结果还是十分令人满意的.

6 结语

本文提出的多点收缩混沌优化算法,对混沌算法应如何缩小搜索空间,如何设计算法终止条件,如何选取初始控制参数和控制策略给出了一种较为理想的解决方案.由证明过程可见只要每次保留的较好搜索点数num足够大,本算法可以以概率1收敛于全局最优解.而在实际应用中可以通过控制num的取值,快速的得出满足实际需求的最优解.

图2 算法对不同维函数仿真结果

[1]李兵,蒋慰孙.混沌优化方法及其应用[J].控制理论与应用,1997,14(4):613-615.

[2]张彤,王宏伟,王子才.变尺度混沌优化方法及其应用[J].控制与决策,1999,14(3):285-288.

[3]修春波,刘向东,张宁河.双混沌机制优化方法及其应用[J].控制与决策,2003,18(6):724-726.

[4]杜守强,陈元媛.推广线搜索下一类共轭梯度法的全局收敛性[J].纯粹数学与应用数学,2004,20(3):209-212

[5]李宏,王宇平,焦永昌.解非线性两层规划问题的新的遗传算法及全局收敛性[J].系统工程理论与实践,2005, 26(3):62-71

Multipoint shrinking chaos optimization algorithm and its global convergence

LIU Yong1,LU Jun2,XU Yu-sheng1,LI Yang1
(1.School of Science,Xi’an University of Architecture and Technology,Xi’an710055,China; 2.Department of Mathematics,Zhengzhou Teachers College,Zhengzhou450044,China)

A multipoint shrinking chaos optimization algorithm which local searching space can be decided under an self-adaptive contral strategy is proposed.The method keeps multiple better searching points at present searching space to decide its local searching space later.By this way the method have a self-adaptive on different functions and different times the search has carried out before.The global convergence of the algorithm are proved.Simulation results show that the algorithm can improve the chaos optimization algorithm’s performance effectivly as well as make the chaos optimization more practical.

chaos optimization,multipoint shrinking chaos optimization algorithm,global optimization,almost sure convergence

O221

A

1008-5513(2009)03-0491-06

2007-11-28.

国家自然科学基金(70173037).

刘勇(1979-),硕士,研究方向：最优化理论.

2000MSC:40K