|
摘 要:从优化算法应该具有的共性出发,提出一种全新的算法——学习算法(la)。该算法记录历史最优解和当前最优解这两组关键历史信息,然后让当前解向这两种最优解聚集(即学习的过程);同时为了不放弃其他区域的搜索,让当前解的一部分完全随机地被重置。该算法原理简单,可调参数少且各参数对算法效能的影响易于掌控。在多最优函数以及复杂函数的最小化测试中,通过与ga、pso的比较,发现la确实是一种有效的优化算法,其优化效率并不低于现有算法。数值实验还表明,la在多最优解问题的寻优中相对ga和pso具有非常明显的优势。 关键词:学习算法;遗传算法;微粒群算法 new optimization algorithm:learning algorithm he yi,zhao xiang,huang ka-ma (school of electronics & information, sichuan university, chengdu 610064, china) abstract:this paper presented a new algorithm:learning algorithm based the commonness of optimization algorithms. this algorithm recorded the historical optimal solution and the current optimal solution, and then let the current solution converge to these two optimal solution(that was, the learning process), at the same time, in order not to give up the search for other regions, made a part of current solution be replaced randomly.the algorithm had simple theory and small adjustable parameters, and the effect for every parameter to algorithm was easy to control. in the test of multi-optimum function and minimization of complex function,found that compared with ga and pso, la was indeed an effective algorithm. numerical experiments also show that la has a very distinct advantage in multi-optimum problems compared with ga and pso. key words:learning algorithm(la); genetic algorithm(ga); particle swarm optimization(pso) 0 引言 在最近二十年中,各种各样的优化算法得到了飞速的发展并成功运用于各种领域,这些算法模拟不同的生物或物理现象,使各种人工系统具有优良的自适应能力和优化能力。WwW.11665.cOm例如,遗传算法(ga)[1,2]模拟生物的进化过程、微粒群算法(pso)[3]模拟鸟类群体行为、蚁群算法(ant colony optimization,aco)[4]模拟蚂蚁觅食行为、模拟退火算法(simulated annealing,sa)[5]模拟高温物体的退火过程等。 微粒群算法、蚁群算法具有原理简单、容易实现且初期收敛迅速的优点。但是,以pso为例,算法在后期很容易陷入局部最优,特别是在求解高维多峰问题上,形成所谓的“早熟”现象,这也是pso算法的最大缺点[6]。而遗传算法虽然在早期表现出较慢的收敛速度,但是在后期却拥有比pso更好的全局搜索性能。 也有学者对传统的这些算法作出了一些改动,使算法在某些方面的特性得到了一些改善。比如在pso算法中,采用线性递减[7]和模拟自适应方法[8]动态调整惯性因子,提高了算法的全局搜索能力和搜索精度;对pso算法加入收缩因子以改善其收敛性[9],借鉴遗传算法中的自然选择机制,改善局部搜索能力[10];在遗传算法中加入小生境模型[11],维护群体多样性,加大多峰搜索力度;采用最优保存策略,改善收敛速度。 然而,无论上述优化算法是在模拟何种自然现象,也无论它们得到何种改进和优化,它们的效能和优化机理都必须从优化问题本身的角度得到解释,即它们为什么一方面可以向最优解收敛,而另一方面又可以避免陷入局部最优?它们在绝大多数问题中的寻优效率为什么会高于完全随机(盲目)的搜索?这是因为它们实际上都是在利用历史搜索的信息来启发式地指导当前搜索,从而相应地完成当前解的更新。具体而言,就是它们通过历史搜索信息来推测最优解存在的所谓高可能性区域,然后通过让当前解向该区域聚集来加强该区域的搜索,与此同时,会减弱但不会完全放弃对其他区域的搜索。从这个角度上讲,这些优化算法必然会“异曲同工”和“大同小异”。 基于上述视角,从优化算法应该具有的共性出发,导出一种新型的优化算法,将其称之为学习算法(la)[12]。 1 学习算法原理 考虑如下优化问题: min f(x),x∈a �瘙 綆 n 其中:f为目标函数(或者代价函数),x为定义域a内的点(如n维的矢量)。与常规进化算法一样,学习算法将通过个体的逐代循环再生,在区域a上寻求f的最小值。对每一次迭代,评估代价值和学习过程将交替进行。 评估代价值:对当前的所有解进行评价和整理,挑选最好的m个合并到长度为m的历史最优列表中。 学习过程:一部分当前解围绕历史最优解进行轻微扰动,另一部分向当前最优解或历史最优解靠近,或者被随机重置。 算法伪代码可以描述如下:
a)均匀产生{x1,x2,…,xmini}a,评估x1,x2,…,xmini的代价,挑选最好的mbest个解插入链表l中。 b)随机产生{x1,x2,…,xm}a。 c)评估x1,x2,…,xm的代价,挑选最好的mbest个解xj1, xj2,…,xjmbest。 d)将xj1,…,xj2,…,xjmbest 合并入链表,并去除重复值。 e)按如下方案更新x1,x2,…,xm: doi=1,m ifi≤mbestthen xi=xji+ε else ifr xi=xi+r*(x(cur)nearest-best-xi)
else if r>1-p(his)learnthen
xi=xi+r*(x(his)nearest-best-xi)
else xi=r∈a
end if
end do
f)如果满足终止条件,则迭代停止;否则返回c)。
在以上代码中, ε是具有足够小长度的随机矢量;r ~ u[0,1]为随机数,r~u(a)为随机矢量;p(cur)learn和p(his)learn为当前解向当前最优解和历史最优解靠近的学习概率;x(cur)nearest-best是离该个体距离最近的当前最优解;x(his)nearest-best是离该个体距离最近的历史最优解。通过mbest、p(cur)learn和p(his)learn, 学习算法可以对不同区域分配不同的搜索强度,或者直接随机重置解;而通过x(cur)nearest-best和x(his)nearest-best,算法可以实现分布式搜索。
与ga和pso相比,它主要具有以下几个不同点:
a)ga和pso的使用需要面对复杂的可调参数,而过多的可调参数无疑加大了程序设计和使用的复杂性,并降低了运行结果的可预见性。学习算法从优化原理的本质出发,将个体分为不同的职能,分别进行更深度搜索、向邻近的历史最优点和当前最优点学习,或者随机重置,最终挑选出最优位置,因此它大大减少了可调参数的数量,增强了算法的通用性。
b)采用多最优保存策略,使用链表记录前n个最优个体的位置并不断更新,配合分布式区域选择机制,整个算法表现出分布式寻优特点,可以有效地找出多个最优,从而实现多峰优化。
2 数值实验
本文将la、ga和pso作了大量的对比测试实验。
测试1 多最优函数测试
各算法均采用迭代次数m=100,种群大小n=40。
f1:camel函数
f(x)=(4-2.1x12+x14/3)x12+x1x2+(-4+4x22)x22
x*={(-0.0898,0.7126),(0.0898,-0.7126)}
f*=-1.031628,lmini=6,gmini=2
其中:x*为最优值的条件;f*为最优值大小;lmini为局部最优值个数;gmini为全局最优值个数。以下同f2:bohachevsky函数。
f(x)=x12+x22-0.3 cos(3*pi*x1)+0.3 cos(3*pi*x2)+0.3
x*={(0,-0.24),(0,0.24)}
f*=-0.24,gmini=2
以上两个函数均具有两个全局最优,本文分别对三种算法进行了50次运行,挑选运行结果最好的一次进行个体分布比较,并采用50次的平均代价值进行收敛性能的比较。la中当前学习概率为0.7,历史学习概率为0.1;pso中惯性系数c1=c2=2.1;ga中交叉概率取为0.5,变异概率取为0.02。图1~6显示了三种算法在迭代结束时的个体分布,图7、8显示了三种算法的收敛速度比较。图中用五星标出了两个全局最优位置。可以清楚地看到,la能够准确地找到函数的两个全局最优,并且未完全放弃全局搜索,而ga与pso均只找到一个最优点。在收敛速度上,la强于ga,与pso相当。
测试2 复杂函数收敛速度比较
本文选择了以下几个著名的测试函数,分别用la、pso、ga寻求最优,以100次运行的平均值进行收敛比较。所有算法均采用迭代次数m=100,种群大小n=40。
f1:schaffer函数
f(x)=0.5+sin2x12+x22-0.5[1+0.001(x12+x22)]2,xi∈[-100,100]
x*={0}, f*=0,lmini=∞,gmini=1
f2:griewank函数
f(x)=x21+x224000-cos x1 cosx22+1,xi∈[-600,600]
x*={0}, f*=0,gmini=0
f3:ackley函数
f(x)=-20 exp(-0.21nni=1x2i)-exp(1nni=1cos(2πxi))+20+e,xi∈[-20,30]
n=10,x*={0}, f*=0,gmini=1
f4:shubert函数
f(x)={5i=1i cos((i+1)x1+i)}{5i=1i cos((i+1)x2+i)},xi∈[-10,10]
x*={(5.4828…,4.858…)(-7.7083…,-7.0835…),…}
f*=-186.73…,lmini=760,gmini=18
f5:rotate rastrigin函数[13]
f(x)=ni=1(zi-10 cos(2πzi)+10),z=(x-o)*m,x∈[-5,5]n
n=10,x*=o, f*=0
f6:shifted rosenbrock函数[13]
f(x)=n-1i=1(100(zi2-zi+1)2+(zi-1)2),z=x-o+1,x∈[-100,100]n
n=10,x=o, f*=0
图9~14为三种算法的收敛速度。表1为各算法100次运行的平均收敛值,表2为各算法100次运行的最佳收敛值。
表1 各算法100次运行的平均收敛值
算法平均收敛
f1f2f3f4f5f6
la9.42×e-36.33×e-32.47×e-4-186.4160.691.23×e9
pso7.06×e-16.82×e-35.21×e-4-183.5764.715.28×e9
ga6.11×e-31.52×e-21.56×e-1-184.8130.671.27×e7
表2 各算法100次运行的最佳收敛值
算法平均收敛
f1f2f3f4f5f6
la7.04×e-82.61×e-128.71×e-7-186.730923.691.09×e8
pso4.78×e-25.77×e-72.95×e-5-186.663826.453.56×e8
ga6.47×e-51.73×e-61.23×e-3-186.73099.6728.04×e6
通过上面的函数测试可以看出:
a)对测试1,即多最优问题的求解,la能准确地找到多个最优点,并围绕这些最优点进行分布式寻优,这样能有效地防止陷入局部最优,找到一个以上的最优点。
b)对测试2中的四个函数,la的优化结果无论是收敛速度还是精确度都比较让人满意,100次运行的最佳收敛结果(每次为step=100)明显好于pso和ga,而100次平均收敛结果,大多数情况下也强于pso和ga。
c)在各个函数测试中,三种算法都保持了参数不变的原则,这样不难看出,在对多种问题的优化中,la都能以同一组参数保持较好的性能,这样在大多数问题中,不需要面对复杂的参数设置。
d)根据“无免费午餐”定理,虽然不可能找到一种对任何问题都表现良好的算法,但la在上述典型的多最优函数以及复杂函数的最小化测试中,与现有算法相比,大多表现出了令人满意的收敛速度和优化精度。当然,对la进行更大范围和更深层次的测试有待进一步的工作。
3 结束语
本文提出了一种基于优化本质思想的新优化算法——la。在多最优函数以及复杂函数的最小化测试中,通过与ga、pso的比较,发现la确实是一种有效的优化算法,其优化效率并不低于现有算法。数值实验还表明,la在多最优解问题的寻优中相对于ga和pso具有非常明显的优势。
需要指出的是,本文提出la的根本动机并不是要再给现实世界增加一种优化算法,而是想问:对所有全局随机寻优算法(包括现有的和将要出现的),是否存在一个最简洁的版本;这个最简洁的优化算法应该具有哪些最基本的优化机制和可调参数?因为过于复杂的优化机制和过多的可调参数不但加大了程序设计和使用的复杂性,同时还降低了运行结果的可预见性。笔者希望通过学习算法能初步地探索上述问题。
未来的研究工作将会包括更深层的收敛特性分析、la的改进,以及la与其他算法的关系,并会将la应用于现实问题的优化中。
参考文献:
[1]
goldberg d e.genetic algorithms in search optimization and machine learning[m].pearson:addison-wesley,1989.
[2] holland j h.genetic algorithms[j].scientific american,1992,266(4):44-50.
[3]kennedy j,eberhart r.particle swarm optimization[c]//proc of ieee international conference on neural networks.1995.
[4]dorigo m,sttzle t.ant colony optimization[m].[s.l.]:mit press,2004.
[5]kirkpauick s,gelatt c d,vecchi m p.optimization by simulated annealing[j].science,1983,220(4598):671-680.
[6]hao zhi-feng,wang zhi-gang,huang han.a particle swarm optimization algorithm with crossover operator[c]//proc of international conference on machine learning and cybernetics.2007:1036-1040.
[7]eberhart r c,shi yu-hui.particle swarm optimization:developments,applications and resources[c]//proc of ieee international congress on evolutionary computation.piscataway:ieee,2001:81-86.
[8]shi yu-hui,eberhart r c.fuzzy adaptive particle swarm optimization[c]//proc of ieee congress on evolutionary computation.piscataway: ieee service centered,2001:101-106.
[9]clerc m.the swarm and the queen:towards a deterministic and adaptive particle swarm optimization[c]//proc of ieee congress on evolutionary computation.piscataway:ieee service centered,1999:1951-1957.
[10]angeline p j.using selection to improve particle swarm optimization[c]//proc of international conference on evolutionary computation.anchorage,ak:natural selection inc.,1998:84-89.
[11]sareni b,krahenbuhl l.fitness sharing and niching methods revisited[j].ieee trans on evolutionary computation,1998,3(2):97-106.
[12]zhao xiang,yao yuan,yan li-ping.learning algorithm for multimodal optimization[j].computers and mathematics with application,2009,57(11-12):2016-2021.
[13]suganthan p n,hansen n,liang j j,et al.problem definitions and evaluation criteria for the cec 2005 special session on real-parameter optimization[r].singapore:nanyamg technological university,2005.
|
|
