论文部分内容阅读
摘 要:针对混沌优化对初始值敏感、搜索精确解效率低等不足,提出了一种群混沌优化算法。该方法令搜索从不同的初始值同时出发,降低对初始值的敏感度,能够用较少的迭代次数,迅速有效的遍历空间内所有状态,实验算例和仿真结果表明,新型混沌优化方法具有较高的搜索效率与搜索精度。
关键词:群混沌 初值敏感度 遍历空间
1 引言
混沌理论是系统从有规律突然变为无规律状态的一种演化理论,是对确定性系统中出现的内在"随机过程"形成的途径和机制的研讨。混沌是非线性动力学系统在一定条件下所表现的一种运动形式,是系统处于非平衡过程中所呈现的随机行为;产生混沌的机制往往又是简单的非线性,是丝毫不带随机因素的固定规则。混沌具有(1)随机性:混沌的表现同其他随机变量相同,都显得没有规律而杂乱。(2)遍历性:混沌能不重复地历经一定范围内的所有状态。(3)规律性:混沌是由确定的迭代方程导出的。混沌运动能在一定范围内按其自身的规律不重复地遍历所有状态。混沌的这种遍历性特点可被用来进行优化搜索且能避免陷入局部极小。因此,混沌优化搜索方法已成为一种新颖的优化技术。混沌优化就是根据其遍历性和规律性特点采用混沌变量在一定范围内进行搜索,促使混沌变量的搜索跳出局部极小点,最终达到全局最优点。
为了克服传统的优化算法的不足,目前,许多学者引入混沌动力学系统以求解复杂的优化问题。文献[6]用混沌变量进行优化搜索,其基本思想是把混沌变量线形映射到优化变量的取值区间,然后利用混沌变量进行搜索。如果搜索空间相对较大时,搜索时间就过于长。文献[7]提出了变尺度优化方法,它不断缩小优化变量的搜索空间,并不断改变"二次搜索"的调节系数。该算法在保证真正最优点仍然在缩小后的空间中,就必须在缩小空间前进行多次盲目搜索,搜索量相对非常的大,要不就很难寻到真正的最优点。文献[8]提出了双混沌机制优化方法,其特点是用两个不同的混沌变量分别进行独立搜索,根据两者的搜索的最优点距离情况来缩小搜索空间。但当搜索空间较大,函数复杂程度越高时,其结果就不能令人满意。因此怎样选择搜索起点、如何缩小搜索空间、如何设计限局部搜索方式、如何设计好两个阶段的终止准则、如何选取合适的初始控制参数及其控制策略,仍是提高上述基于混沌动态优化算法性能的关键。
基于此,本文提出了群混沌优化方法,群举出混沌变量的多个初始值同时在搜索空间进行搜索,降低了初始值的选取对最优解的不利影响,能够迅速的遍历空间内所有状态,明显加快了搜索速度。实验算例表明,该算法简单、易于实现,求解精度、求解速度和可靠性较之传统方法更优越。
2. 群混沌并行优化算法
这里的混沌动力学方程选择一种混沌特性比Logistic映射更优的折叠次数无限混沌映射:
xn ∈[-1,1],x≠0,x(n+1)=sin[a/x(n)] (1)
a∈(0,+∞) n=0,1,2……。
取a = 2,图1描述了该混沌模型的500次迭代运动轨迹。
该映射由于折叠次数无限,在区间[ - 1 ,1 ]内有无穷多个不动点和零点,因此若要由此映射产生混沌,必须注意以下2 点:
(1)迭代的初始值不能为0 ;
(2)初始值不能取为无穷多个不动点的任何一个,否则为稳定轨道, 不能产生混沌, 不动点为方程x = sin (2/x ) 的解。
混沌运动随机性强,初始值不同时,混沌优化算法收敛速度和搜索精度差别很大,收敛稳定性不强。QPCOA算法采取群并行机制,克服了混沌随机性的影响,提高了搜索效率。对于n 个变量的优化问题,QPCOA算法并行给定P€譶个混沌变量(P 为群的个数),即每一个优化变量由P个混沌变量来独立并行映射,优化结果取 P 个并行混沌变量的映射最优值。
考虑以下的一类优化问题:
min f (xn), xi={x1,x2,...,xn} , ai ≤xi ≤bi (2)
这里xi 为n 维优化变量, [ai,bi]为优化变量xi(i=1,2,…,n)的定义域。定义一下变量:
xik=xi (0), yik=yi (0),x*=xi (0), y*=yi (0), air=ai, bir =bi,k 为迭代次数;P 为群并行数,j 表示每一个并行变量,j =1,2,..,P ; xijK 表示第k 次迭代时,第i个变量对应的并行第j 个变量值;mx 表示混沌变量值, mxijk 表示第k 次迭代时, 第i个变量对应的并行第j 个混沌变量值;fpj* 为并行最优值,即每一组并行变量的当前最优值, xij* 为对应的并行最优解,f * 为整体最优值,即f*= min( fpj* ) ,xi* 为对应的整体最优解。
Step 1 初始化。k =1 , 随机产生P €?n个混沌轨迹,得到
mxijk 。xijK,xij*,xi*,f *, fpj* 取初始值,搜索范围为定义域:
Step 2 并行迭代混沌变量和优化变量。采用式(1)的折叠次数无限混沌映射来计算混沌变量:
xijk+1=sin(2/xijk)(3)
将混沌变量线性映射到优化变量的搜索区间:
mxijk=air+mxijk(bir-air)(4)
step 3 用并行优化变量独立迭代搜索。
If f(xijK)< fpj*, fpj*= f(xijK), xij*= xijK; Else,fpj*,xij*保持原值。
If fpj* Step 4 k=k+1,重复step2-step3,当重复的次数超过h次时进行下面的步骤,h可以选为3000。
Step 5 缩小个变量的搜索范围
air+1=mxi*+€%^(bir-air) (5)
bir+1=mxi*-€%^(bir-air)(6)
€%^是收缩系数,这里€%^∈[1,2],为使新范围不至越界,需做如下处理:
Ifaijr+1 Ifbijr+1
Step 6 判断是否满足终止条件,若满足,则结束;否则 r=r +1,转Step2继续迭代。
混沌运动在一定的范围内具有遍历性,但是由于混沌系统对初始值的依赖性,某些状态可能需要较长的时间才能达到,如果全局最优值恰好出现在这些状态上,则搜索时间会很长。本文提出的混沌优化算法则克服了以上的不足。从一群混沌变量初值出发,同时在全局空间内进行搜索,以此来降低混沌系统对初始条件的敏感依赖性,加快搜索速度,并在搜索到一定程度时进行二次载波[6],尽快找到最优解。本文也给出了缩小搜索空间前所进行的混沌搜索的结束条件,提高了算法的通用性。同时避免了多次的盲目搜索,减少了计算量。当群混沌机制寻优结果大部分落入某空间时,按照最大似然估计的思想,就可以估计出该空间含有真正的最优值[8]。因此,通过引入群混沌优化机制,不但可以增强搜索的充分性,还能够用较少的迭代次数,更快速有效在便利空间内所有状态,大大减少了盲目搜索的次数时间。
3 优化实例
应用本文提出的群混沌优化方法,也为了便于和其他混沌优化方法进行比较,选取3个复杂函数进行优化计算。考察它们搜索到全局最优解的概率和精度以及搜索效率。
Camel函数
f(x,y) =[4-21x2+]x2+xy+(-4+4y2)y2,-100 F2=100(x12-x2)2+(1-x1) 2,-2048≤xi≤2048 (10)
F3=[1+(x1+x2+1)2(19-14x1+3x12-14x2+6x1x2+3x22)]
·[30+(2x1-3x2)2(18-32x12+12x12+48x2-36x1x2+27x22)],
-2≤xi≤2(11)
对三个复杂函数的仿真结果见表1.
从表1中可以看出,通过上表可以看出,本文算法具有比其他两种混沌优化算法有更优的性能:用最少的时间就搜索到优化解。这主要取决于群举出一组混沌变量的初始值,同时在搜索空间内进行搜索,有效地解决了混沌运动对初始值的敏感性,提高了混沌搜索的充分性。在仿真过程中,本算法不必要针对不同的优化函数而改变寻优参数,从而改善了算法的通用性。
4结束语
在混沌优化方法的基础上,提出了群混沌优化的方法,从混沌变量的不同初始值进行搜索,有效地克服了混沌运动对初始值的敏感性的缺点,大大减少了找到全局最优值的时间。它也丰富了搜索机制的动力学特性,提高了混沌搜索的充分性,克服了在缩小搜索空间前所进行的盲目搜索的缺点,提高了搜索效率。同时也提高了算法的通用性。 实例计算表明,群混沌算法是一种简单、有效、快捷的方法。
参考文献:
[1]高海昌,冯博琴,朱利.智能优化算法求解TSP问题[J].控制与决策,2006,21(3):241-247.
[2]尤勇,王孙安,盛万兴.新型混沌优化方法的研究及应用[J].西安交通大学学报,2003,37(1):69-72.
[3]王凌,郑大钟,李清生.混沌优化方法的研究进展[J].计算技术与自动化,2001,(1):1-5.
[4]王东生,曹磊.混沌、分形及其应用[M].合肥:中国科技大学出版社,1995.
[5]赵小梅.一种改进的混沌优化方法及其应用[J].陕西科技大学学报,2006,24(2):94-98.
[6]李兵,蒋慰孙.混沌优化方法及其应用[J].控制理论与应用,1997,(4):613-615.
[7]张彤,王宏伟,王子才.变尺度混沌优化方法及其应用[J].控制与决策,1999,14(3):285-288.
[8]修春波,刘向东,张宇河,双混沌机制优化方法及其应用[J].控制与决策,2003,18(6):724-726.
[9]梁慧勇,顾幸生.采用并行计算的混沌优化方法[J].华东理工大学学报,2004,30(4):450-453.
作者介绍:黄德冲(1986-),男,汉族,天津宝坻人,天津工业大学电气工程与自动化学院本科生
关键词:群混沌 初值敏感度 遍历空间
1 引言
混沌理论是系统从有规律突然变为无规律状态的一种演化理论,是对确定性系统中出现的内在"随机过程"形成的途径和机制的研讨。混沌是非线性动力学系统在一定条件下所表现的一种运动形式,是系统处于非平衡过程中所呈现的随机行为;产生混沌的机制往往又是简单的非线性,是丝毫不带随机因素的固定规则。混沌具有(1)随机性:混沌的表现同其他随机变量相同,都显得没有规律而杂乱。(2)遍历性:混沌能不重复地历经一定范围内的所有状态。(3)规律性:混沌是由确定的迭代方程导出的。混沌运动能在一定范围内按其自身的规律不重复地遍历所有状态。混沌的这种遍历性特点可被用来进行优化搜索且能避免陷入局部极小。因此,混沌优化搜索方法已成为一种新颖的优化技术。混沌优化就是根据其遍历性和规律性特点采用混沌变量在一定范围内进行搜索,促使混沌变量的搜索跳出局部极小点,最终达到全局最优点。
为了克服传统的优化算法的不足,目前,许多学者引入混沌动力学系统以求解复杂的优化问题。文献[6]用混沌变量进行优化搜索,其基本思想是把混沌变量线形映射到优化变量的取值区间,然后利用混沌变量进行搜索。如果搜索空间相对较大时,搜索时间就过于长。文献[7]提出了变尺度优化方法,它不断缩小优化变量的搜索空间,并不断改变"二次搜索"的调节系数。该算法在保证真正最优点仍然在缩小后的空间中,就必须在缩小空间前进行多次盲目搜索,搜索量相对非常的大,要不就很难寻到真正的最优点。文献[8]提出了双混沌机制优化方法,其特点是用两个不同的混沌变量分别进行独立搜索,根据两者的搜索的最优点距离情况来缩小搜索空间。但当搜索空间较大,函数复杂程度越高时,其结果就不能令人满意。因此怎样选择搜索起点、如何缩小搜索空间、如何设计限局部搜索方式、如何设计好两个阶段的终止准则、如何选取合适的初始控制参数及其控制策略,仍是提高上述基于混沌动态优化算法性能的关键。
基于此,本文提出了群混沌优化方法,群举出混沌变量的多个初始值同时在搜索空间进行搜索,降低了初始值的选取对最优解的不利影响,能够迅速的遍历空间内所有状态,明显加快了搜索速度。实验算例表明,该算法简单、易于实现,求解精度、求解速度和可靠性较之传统方法更优越。
2. 群混沌并行优化算法
这里的混沌动力学方程选择一种混沌特性比Logistic映射更优的折叠次数无限混沌映射:
xn ∈[-1,1],x≠0,x(n+1)=sin[a/x(n)] (1)
a∈(0,+∞) n=0,1,2……。
取a = 2,图1描述了该混沌模型的500次迭代运动轨迹。
该映射由于折叠次数无限,在区间[ - 1 ,1 ]内有无穷多个不动点和零点,因此若要由此映射产生混沌,必须注意以下2 点:
(1)迭代的初始值不能为0 ;
(2)初始值不能取为无穷多个不动点的任何一个,否则为稳定轨道, 不能产生混沌, 不动点为方程x = sin (2/x ) 的解。
混沌运动随机性强,初始值不同时,混沌优化算法收敛速度和搜索精度差别很大,收敛稳定性不强。QPCOA算法采取群并行机制,克服了混沌随机性的影响,提高了搜索效率。对于n 个变量的优化问题,QPCOA算法并行给定P€譶个混沌变量(P 为群的个数),即每一个优化变量由P个混沌变量来独立并行映射,优化结果取 P 个并行混沌变量的映射最优值。
考虑以下的一类优化问题:
min f (xn), xi={x1,x2,...,xn} , ai ≤xi ≤bi (2)
这里xi 为n 维优化变量, [ai,bi]为优化变量xi(i=1,2,…,n)的定义域。定义一下变量:
xik=xi (0), yik=yi (0),x*=xi (0), y*=yi (0), air=ai, bir =bi,k 为迭代次数;P 为群并行数,j 表示每一个并行变量,j =1,2,..,P ; xijK 表示第k 次迭代时,第i个变量对应的并行第j 个变量值;mx 表示混沌变量值, mxijk 表示第k 次迭代时, 第i个变量对应的并行第j 个混沌变量值;fpj* 为并行最优值,即每一组并行变量的当前最优值, xij* 为对应的并行最优解,f * 为整体最优值,即f*= min( fpj* ) ,xi* 为对应的整体最优解。
Step 1 初始化。k =1 , 随机产生P €?n个混沌轨迹,得到
mxijk 。xijK,xij*,xi*,f *, fpj* 取初始值,搜索范围为定义域:
Step 2 并行迭代混沌变量和优化变量。采用式(1)的折叠次数无限混沌映射来计算混沌变量:
xijk+1=sin(2/xijk)(3)
将混沌变量线性映射到优化变量的搜索区间:
mxijk=air+mxijk(bir-air)(4)
step 3 用并行优化变量独立迭代搜索。
If f(xijK)< fpj*, fpj*= f(xijK), xij*= xijK; Else,fpj*,xij*保持原值。
If fpj*
Step 5 缩小个变量的搜索范围
air+1=mxi*+€%^(bir-air) (5)
bir+1=mxi*-€%^(bir-air)(6)
€%^是收缩系数,这里€%^∈[1,2],为使新范围不至越界,需做如下处理:
Ifaijr+1
Step 6 判断是否满足终止条件,若满足,则结束;否则 r=r +1,转Step2继续迭代。
混沌运动在一定的范围内具有遍历性,但是由于混沌系统对初始值的依赖性,某些状态可能需要较长的时间才能达到,如果全局最优值恰好出现在这些状态上,则搜索时间会很长。本文提出的混沌优化算法则克服了以上的不足。从一群混沌变量初值出发,同时在全局空间内进行搜索,以此来降低混沌系统对初始条件的敏感依赖性,加快搜索速度,并在搜索到一定程度时进行二次载波[6],尽快找到最优解。本文也给出了缩小搜索空间前所进行的混沌搜索的结束条件,提高了算法的通用性。同时避免了多次的盲目搜索,减少了计算量。当群混沌机制寻优结果大部分落入某空间时,按照最大似然估计的思想,就可以估计出该空间含有真正的最优值[8]。因此,通过引入群混沌优化机制,不但可以增强搜索的充分性,还能够用较少的迭代次数,更快速有效在便利空间内所有状态,大大减少了盲目搜索的次数时间。
3 优化实例
应用本文提出的群混沌优化方法,也为了便于和其他混沌优化方法进行比较,选取3个复杂函数进行优化计算。考察它们搜索到全局最优解的概率和精度以及搜索效率。
Camel函数
f(x,y) =[4-21x2+]x2+xy+(-4+4y2)y2,-100
F3=[1+(x1+x2+1)2(19-14x1+3x12-14x2+6x1x2+3x22)]
·[30+(2x1-3x2)2(18-32x12+12x12+48x2-36x1x2+27x22)],
-2≤xi≤2(11)
对三个复杂函数的仿真结果见表1.
从表1中可以看出,通过上表可以看出,本文算法具有比其他两种混沌优化算法有更优的性能:用最少的时间就搜索到优化解。这主要取决于群举出一组混沌变量的初始值,同时在搜索空间内进行搜索,有效地解决了混沌运动对初始值的敏感性,提高了混沌搜索的充分性。在仿真过程中,本算法不必要针对不同的优化函数而改变寻优参数,从而改善了算法的通用性。
4结束语
在混沌优化方法的基础上,提出了群混沌优化的方法,从混沌变量的不同初始值进行搜索,有效地克服了混沌运动对初始值的敏感性的缺点,大大减少了找到全局最优值的时间。它也丰富了搜索机制的动力学特性,提高了混沌搜索的充分性,克服了在缩小搜索空间前所进行的盲目搜索的缺点,提高了搜索效率。同时也提高了算法的通用性。 实例计算表明,群混沌算法是一种简单、有效、快捷的方法。
参考文献:
[1]高海昌,冯博琴,朱利.智能优化算法求解TSP问题[J].控制与决策,2006,21(3):241-247.
[2]尤勇,王孙安,盛万兴.新型混沌优化方法的研究及应用[J].西安交通大学学报,2003,37(1):69-72.
[3]王凌,郑大钟,李清生.混沌优化方法的研究进展[J].计算技术与自动化,2001,(1):1-5.
[4]王东生,曹磊.混沌、分形及其应用[M].合肥:中国科技大学出版社,1995.
[5]赵小梅.一种改进的混沌优化方法及其应用[J].陕西科技大学学报,2006,24(2):94-98.
[6]李兵,蒋慰孙.混沌优化方法及其应用[J].控制理论与应用,1997,(4):613-615.
[7]张彤,王宏伟,王子才.变尺度混沌优化方法及其应用[J].控制与决策,1999,14(3):285-288.
[8]修春波,刘向东,张宇河,双混沌机制优化方法及其应用[J].控制与决策,2003,18(6):724-726.
[9]梁慧勇,顾幸生.采用并行计算的混沌优化方法[J].华东理工大学学报,2004,30(4):450-453.
作者介绍:黄德冲(1986-),男,汉族,天津宝坻人,天津工业大学电气工程与自动化学院本科生