基于蚁群遗传算法混合编程的函数优化

摘要:为研究连续函数优化问题,基于图解的蚁群系统,提出二进制蚁群算法,并实现与遗传算法混合编程,以提高求解效率。算例表明,蚁群-遗传算法混合编程求解连续优化问题,收敛速度快,计算精度高,可用于求解实际工程问题。

关键词:连续优化;二进制;蚁群算法;遗传算法;混合编程

中图分类号:TP18文献标识码:A文章编号:1009-3044(2009)26-7494-03

Function Optimization Based on Programming Mixed Ant Colony Algorithm with Genetic Algorithm

ZHAO Feng-yao, GUAN Xin-Jian

(School of Water Conservancy & Environment Engineering, Zhengzhou University, Zhengzhou 450001, China)

Abstract: For the study of continuous optimization problems, a binary ant colony algorithm was introduced based on graph-based ant system. To improve soluation efficiency, the ant colony algorithm programming mixed with genetic algorithm was realized. Practical example showes that the mixed language programming can solve continuous optimization problem with a faster convergence speed and a better precision in calculation, and it can be used on engineering.

Key words: continuous optimization; binary; ant colony algorithm; genetic algorithm

蚁群算法(Ant Colony Algorithm)是一种源于大自然生物世界的新型仿生类算法[1],20世纪90年代初由意大利学者Dorigo依照蚂蚁觅食原理设计而成的一种群体智能算法。蚁群算法在求解一系列困难的组合优化问题上取得成效,成为解决TSP (traveling salesman problem)、JSP (job-shop problem)等典型问题的一种强有力算法。

遗传算法是受生物进化学说和遗传学说的启发而发展起来的,由美国的J.H.Holland教授于1975年创立[2]。它模拟自然选择和遗传过程中发生的繁殖、杂交和变异现象,进行群体智能进化计算。由于遗传算法求解复杂优化问题的巨大潜力,近年来再许多工程领域的得到应用。

本文基于连续优化目的开展基础性研究,通过蚁群算法与遗传算法的混合编程,改进算法的性能,以求解连续优化问题。

1求解连续优化问题的蚁群算法

1.1 蚁群算法的基本思想

1)状态转移规则:蚁群算法使用的状态转移规则为随机比例规则,是基于求解TSP问题提出的,它给出来位于城市i的蚂蚁k选择移动到城市j的概率。公式为:

其中τ(i,j)表示边(i,j)的适应值,即“激素”; η(i,j) 为距离L(i,j)的倒数。α,β为两个参数,分别表示蚂蚁运动过程中积累信息和启发信息的相对重要程度。

在蚁群算法中,选择方式为:

其中,q为均匀分布在[0,1]上的一个随机变量,q0为在[0,1]上的参数,而J则是根据等式(1)计算出来的概率分布来进行选择。

2)全局更新规则:蚂蚁算法有不同的更新规则,蚁群系统采用全局全局更新规则,只允许全局最优的蚂蚁释放信息素。这样做可以使蚂蚁的搜索主要集中在当前循环为止所找出的最好路径的邻域内。全局更新在所有蚂蚁都完成一次搜索后用下边(3)式进行全局更新:

其中:ρ为信息素挥发参数;Lgb为到目前为止找到的全局最优路径。

3)局部更新规则:每只蚂蚁建立一个解的过程中也同时进行激素迹的更新,规则如下:

其中, r为[0,1]间的参数。

1.2 基于图解的蚁群系统

用蚁群算法求解最优化问题,首先需要将最优化问题转化为求解最短路径问题。为此,文献[3]提出了有向图的概念,文献[4]提出了构造图的概念,他们的共同特点是通过行程对可行解进行编码,进而求解优化问题。

本文在文献[4]的基础上,以二进制为基础,编制了如图1所示的构造图。每只蚂蚁从初始子结点N00 或N01出发,顺序走过N1,N2,…,的其中一个子结点,直到终结点Nk0、Nk1,组成路径(N0t N1t N2t…Nkt),(t∈{0,1})。Nkt取二进制数0或1,路径即可代表一个二进制可行解。

在图1中,每两个相邻结点Ni, Nj之间有4个并行路径,分别连接他们的子结点:Ni0->Nj0,Ni0->Nj1,Ni1->Nj0,Ni1->Nj1,其信息值分别记为τ(i,j)1, τ(i,j)2, τ(i,j)3, τ(i,j)4,蚂蚁行进时只能选择其中的一条路径。每只蚂蚁行进开始时,首先根据τ(0,1)s,s∈{1,2,3,4},概率选择一条路径,确定前两个子结点。当第二个子结点为N10 时,根据τ(1,2)1, τ(1,2)2值的大小按概率选择下一个子结点;当第二个子结点为N11 时,根据τ(1,2)3, τ(1,2)4值的大小按概率选择下一个子结点。这样一直概率选择到最后的子结点Nk0或Nk1,即构成一个完整路径及可行解。

1.3 用于连续优化的蚁群算法

1)参数取值的二进制编码:参数取值的二进制编码与遗传算法相同。假设优化问题的可行解为{x1, x2,…,xm},其中变量xi用长度为l的二进制串表示为{bl bl-1…b2b1},其中bj∈{0,1},它对应蚁群算法结构图1中的一段路径(NL+1,t NL+2,t…NL+l,t)。设xi取值范围为[ximin, ximax ],则对应的解码公式为:

在TSP问题中,最优路径对应的是最短路径。在优化问题中,最优路径为对应目标函数值最优(最大或最小)的蚂蚁行进路径。

2 蚁群算法与遗传算法的混合编程

2.1 遗传算法及其实现

基本遗传算法程序中使用的是二进制编码,将原问题的解空间映射到位串空间{0,1}上,然后在位串空间上进行遗传操作,结果再通过解码过程还原成其表现型以进行适应度评估,其求解过程为:

1) 对待解决问题进行编码。

2) 随机初始化群体X(0)=(x1,x2,…,xn)。

3) 对当前群体X(t)中每个个体xi,解码计算其适应度F(xi)。解码公式与上式(5)相同。

4) 进行选择、交叉、变异等遗传操作,产生下一代个体。

5) 对t=t+1代继续从3)步进化计算,直到满足终止条件。终止条件一般为预定的进化代数或误差限小于设定值或。

2.2 遗传算法的常用算子

1) 选择算子(selectio):选择算子从群体中按某一概率成对选择个体,某个体被选择的概率Pi与其适应度值成正比。常用的实现方法是赌规则。

2) 交叉算子(Crossover):交叉算子将被选中的两个个体的基因链按概率Pc进行交叉,生成两个新的个体,交叉位置是随机的。

3) 变异算子(Mutation):变异算子将新个体的基因链的各位按概率Pm进行变异,对二值基因链(0,l编码)来说即取反。

2.3 蚁群算法与遗传算法的混合编程

蚁群算法有一个主要缺陷,即搜索进行到一定程度后,各个蚂蚁趋于选择同一条路径,算法出现停滞现象。遗传算法局部搜索能力较差,在应用中体现出收敛速度慢且存在未成熟收敛。但这两种智能算法工作机理不同,有很强的互补性。两者融合,互相取长补短可以产生更好的效果。

当蚁群算法与遗传算法均采用二进制编码时,很容易实现混合编程。具体实现时,蚁群算法中蚂蚁个数与遗传算法中染色体个数取相等,每进行M次蚁群搜索循环后,将蚁群的二进制路径看做遗传算法中种群的染色体,进行N次遗传算法进化计算,然后再将得到的染色体作为蚁群二进制路径,继续进行蚁群算法搜索。

3 函数优化

3.1 函数优化及其求解

函数优化在工程技术领域应用很广泛。生产优化、设计优化、投资决策等可通过数学建模直接应用优化方法求解,参数识别、系统控制等问题则可转化为优化问题再进行求解。

函数优化的解法主要有两大类。其一为数学方法,即传统方法,主要利用导数及偏导进行求解,有可靠的理论基础。由于传统方法建立在梯度局部下降的基础上,多数情况下不适合求解全局优化问题,而且对于不可微和病态函数,常常无能为力[5]。

其二是进化算法,如遗传算法、蚁群算法、免疫算法、粒子群算法等,不需要计算梯度,计算过程对函数性态依赖性较小,适应范围广、鲁棒性好,适合计算机编程计算。近年来进化算法飞速发展,具有广阔的应用前景。

3.2 数学算例

由于蚁群算法及遗传算法程序运行中均存在大量的随机操作,从理论上对其性能和效率进行分析比较困难,因此这里通过一个测试函数对本文提出的蚁群-遗传混合算法进行多参数优化效率分析。

测试函数取一简单的多元平方求和函数,即求:

在函数定义域内其最优解为:当xi=2.0(i=1,2,3), xi=5.0(i=4,5)时,目标函数取最小值0。分别用蚁群算法、基本遗传算法、蚁群-遗传进行进化寻优计算。蚂蚁或染色体数目取40,最大进化代数取200代。

在开始计算前,蚁群算法中公式(1)～(4)中的参数α,β,γ,Δτ(i,j)等都预先赋给合适的经验值,本文各参数取值为:

α=1,β=0,τ0=50,q0=0.1,δ=0.1,r=0.05,Lgb=0.016

β=0意味着不考虑启发信息的作用, Lgb=0.016时意味公式(3)中Δτ(i,j)s=62.5,即进化计算过程中Δτ(i,j)s始终取一个恒定值。

遗传算法中的主要计算参数取:交叉概率Pc=0.8,变异概率Pm=0.02。

蚁群-遗传算法中取每进行6次蚁群搜索循环,进行4次遗传算法进化计算。

在这个多参数优化问题中,最优路径为对应目标函数值最小的蚂蚁行进路径。经过200代进化计算后,三种方法的函数优化结果如表1所示。

从表1可以看出,蚁群-遗传算法得到的识别结果比蚁群算法和基本遗传算法结果明显要好,单个变量的识别值与实际值更接近,最后得到的目标函数值也更小,说明采用蚁群-遗传算法混合编程求解效率与求解精度更高。算例还表明,混合算法可以很好地进行多参数优化求解,这可为求解实际工程技术问题打下良好的基础。

4 结论

运用蚁群-遗传算法混合编程进行优化设计,不仅具有较强的全局最优解搜索性能,还有较快的收敛速度和较高的求解精度,更适合解决多参数优化实际问题,具有广阔的应用前景。

参考文献:

[1] DorigoO M.Optimization,learning,and natural algorithms[D].Milano:Politecnico di Milano,1992.

[2] 王小平,曹立明.遗传算法――理论、应用与软件实现[M].西安:西安交通大学出版社,2002.

[3] Stutzle T.Parallelization Strategies for Ant System[C]//Proceedings of Parallel Problem Solving from Nature.Eileen A,Mchoenauer T B,SchwefelH.Lecture Notesin Computer Science.Berlin:Springer-Verlag,1998(1498):722-741.

[4] Gutjahr W J.A Graph-based Ant System and its convergence[J].Future Generation Computer Systems,2000(16):873-888.

[5] 唐焕文,秦学志.实用最优化方法[M].大连:大连理工大学出版社,2000.