略一种基于混沌搜索的文化算法及其应用的论文_计算机应用论文

　摘要:针对文化算法求解函数优化问题存在过早收敛、不稳定等缺陷,基于文化算法框架、嵌入混沌搜索优化,提出了一种混沌文化算法。该算法模型由基于混沌的群体空间和存储知识的信念空间组成,利用标准知识和形势知识分别引导混沌搜索和混沌扰动,有效克服了文化算法过早收敛、混沌搜索优化对初值敏感、搜索效率低等缺陷。实例表明,该方法具有较强的全局搜索能力,在搜索效率、精度和稳定性上有显著表现,并能有效处理高维函数优化问题。
　　关键词:进化计算;文化算法;混沌文化算法;混沌搜索;知识引导
　　　　
　　cultural algorithm based on chaotic search and its application
　　
　　he jian-jia,xu fu-yuan,he sheng-xu,huang he
　　(school of business, university of shanghai for science & technology, shanghai 200093, china)
　　abstract:for premature convergence and instability of cultural algorithm in solving function optimization problem, based on cultural algorithm and chaos search optimization,this paper proposed a chaos cultural algorithm (cca).the algorithm model consisted of a chaos-based population space and a stored knowledge belief space, using normative knowledge and situational knowledge for chaos search and chaos perturbation respectively, and effectively avoided premature convergence of cultural algorithm and overcame chaos search optimization’s sensitivity to initial values and poor efficiency. test results show that this algorithm is strong in global search, and has good performance in searching efficiency, precision and stability, especially in solving high-dimensional optimization problem.
　　key words:evolutionary computation; cultural algorithm; chaos cultural algorithm(cca); chaos search; knowledge guide
　　0 引言
　　从20世纪50年代仿生学的创立起,人们开始模拟生物进化的机理,提出了许多诸如遗传规划、免疫算法等解决优化问题的进化计算方法。wWW.11665.COm这些算法研究主要集中在生物自然选择这一层面上。许多情况表明,文化能使种群以一定的速度进化和适应环境,而这个速度是超越单纯依靠基因遗传生物进化速度的[1]。在人类社会中,文化被看做存储信息的载体,这些信息在社会群体之间和群体内部广泛地传递,并能被社会所有成员继承,从而有效地指导成员的行为来解决问题。受此启示,reynolds[1]于1994年提出了文化算法这种全新的进化算法。
　　文化算法从微观和宏观两个层次模拟进化,不同层次间相互促进且相互影响。该算法提供了一种显性的机制来获取、保存和整合问题求解的知识,从而提高搜索效率。目前,文化算法已成为算法研究的热点,并已成功应用到多个领域,在一些问题上取得了比传统进化算法更好的结果[2~4]。
　　
　　在函数优化方面,文化算法求解效率高,但存在过早收敛、不稳定等不足;混沌搜索优化全局搜索能力强,但对初值敏感、搜索效率低。因此,本文将混沌搜索优化引入到文化算法模型中,提出了用于解决优化问题的混沌文化算法(chaos cultural algorithm,cca)。该算法利用混沌搜索优化的遍历性、随机性特性,增加算法全局搜索能力,避免算法过早收敛,同时利用文化算法的知识引导作用,提高了算法的搜索效率和精度。
　　1 文化算法的原理
　　文化算法框架是由群体空间(population space)和信念空间(belief space)两部分组成,两者分别从微观和宏观两个层面模拟进化过程,如图1所示。前者是问题的解空间,后者用于知识经验的形成、存储和传播,两者相互独立又相互联系,它们之间通过特定的协议进行信息交流。首先,accept()函数将群体空间进化过程中优秀的个体经验传递到信念空间;接着update()函数根据信念空间现有的经验和新经验更新群体经验或知识;然后influence()函数利用群体经验或知识指导群体空间的进化。另外, objective()函数是目标函数,用来评价群体空间中个体的适应值;generate()函数根据群体经验形成下一代个体;select()函数根据规则从新生成个体中选择一部分个体作为下代个体的父辈。文化算法的基本伪代码[5]如下:
　　begin
　　t=0;
　　initialize population pop(t);
　　initialize belief space blf(t);
　　repeat
　　 evaluate population pop(t);
　　update(blf(t),accept(pop(t)));
　　variation(pop(t),influence(blf(t)));
　　t=t+1;
　　select(pop(t)from pop(t-1));
　　until termination condition achieved
　　end
　　2 混沌文化算法的设计
　　本文将混沌搜索优化[6]嵌入到文化算法模型中,利用由chung等人[7,8]提出的区间模式(interval schemata)来表达信念空间中的知识,形成混沌文化算法。这样做既利用了混沌搜索的全局搜索能力,又利用了迭代过程中形成的经验知识,引导算法进行有效的搜索,提高了搜索效率。另外,算法采用混沌搜索优化的并行结构,能有效降低算法对初值的敏感性。不失一般性,非线性函数最优化问题可以表示为
　　min f(xi),i=1,…,n,s.t. ai≤xi≤bi(1)

2.1 混沌搜索优化
　　
　　混沌(chaos)是一种较为普遍的非线性现象,具有随机性、遍历性和内在规律性的特点。其中遍历性是指混沌序列能够不重复地遍历混沌吸引域内所有状态的性质,可作为优化过程中避免陷入局部极小的一种优化机制。混沌搜索优化正是利用这一特性提出的。李冰等人[6]利用logistic混沌映射(见式(2))和二次载波的概念,提出了一种混沌搜索优化算法,引起了广泛关注和大量研究。该算法具有很强的全局搜索能力,但存在初值敏感、搜索效率不高、搜索时间长等缺陷。一些文献对基于混沌搜索的优化方法进行了改进,但效果不是很理想。
　zk+1=u×zk(1-zk) k=0,1,2,…
　　0≤zk≤1u=4 (2)
　　其中:当u=4时,logistic映射为混沌状态,区间(0,1)是映射的混沌不变集[9]。
　　混沌搜索优化的基本思想就是用类似载波的方法将混沌状态引入到优化变量中,并把混沌运动的遍历范围放大到优化变量的取值范围,然后利用混沌变量进行搜索[6]。其基本步骤如下:
　　
　　a)初始化。置k=1,i=1,2,…,n,给定最大混沌运动次数m,给式(2)中的混沌变量z赋n个相异的初值z0i(不能取logistic映射的不动点:0.25,0.5,0.75),并将混沌变量z0i按式(3)映射到优化变量的取值范围,得到最初优化变量x0i,令x*=x0, f*=f(x0)。
　　
　　xi=ai+zi×|bi-ai|(3)
　　
　　b)利用式(2)和(3),计算产生混沌变量序列zki和优化变量序列xki。
　　
　　c)若k≤m,则判断f(xk)≤f*,成立则令x*=xk,f*=f(xk);不成立则x*和f*保持不变,并令k=k+1,转向b)。若k>m,混沌搜索结束。
　　logistic映射(u=4)经过一定次数的迭代后,在(0,1)上分布了大量的轨道点(混沌序列)。其概率密度函数ρ(z)[9]为
　　ρ(z)=1πz(1-z)(4)
　　该式为切比雪夫分布,如图2所示。
　　
　　从图2可知,logistic 映射混沌序列的分布特点是中间比较均匀、两头特别多、在端点达到无穷多[9]。利用logistic映射这一分布特点,结合文化算法优胜区间(下文介绍),便能使群体空间中个体的各个决策变量主要分布在对应优胜区间两端附近,减少盲目搜索,加快搜索效率。
　　2.2 信念空间的结构
　　信念空间的结构定义在文化算法框架中非常重要,其主要作用是提供一个明确的机制来获取、存储和传递知识经验。本文采用文化算法最基本的两种知识:形势知识(situational knowledge)和标准知识(normative knowledge),即b=〈s,n[n]〉。
　　在本文算法中,s是一个列表,存储了由群体空间中选择出来的当前优秀个体集合,是其他个体的“典范”,即s=〈e1,e2,…,ee〉。其数据结构[10]如图3所示。其中,每个优秀个体包含该个体各决策变量的值和所对应的适应值,且f(e1)≥f(e2)≥…≥f(ee)。
　　
　　在本文中,e直接取群体空间的规模popsize。初始化时,最优个体集合取初始群体空间的所有个体。
　　
　　n[n]存储了n组决策变量的变化区间,又称优胜区间,这些区间给出了最优解最可能出现的范围。由这个范围来引导混沌迭代,将能更快找到最优解。其数据结构[10]如图4所示,描述为
　　
　　n[j]=〈ij,lj,uj〉
　　ij=[lj,uj]={x|lj≤x≤uj,x∈r};j=1,2,…,n(5)
　　
　　其中:lj和uj表示第j个决策变量的上边界和下边界;lj和uj分别表示决策变量上、下边界对应的适应值。初始化时,lj和uj设为变量的定义域区间,lj和uj设为+∞,在进化过程中,这四个值会根据优秀个体集合所在区间不断调整。
　　
　　2.3 信念空间的更新
　　信念空间的形势知识每代更新两次,一次在混沌搜索之后,一次在混沌扰动之后;标准知识每代更新一次。
　　
　　2.3.1 形势知识的更新
　　本文对于形势知识更新的方法借鉴了锦标赛法。具体方法是:
　　
　　a)每次迭代后将种群空间中的所有个体集合和形势知识所代表的最优个体集合组成一个新的集合(本文算法新集合规模为2×popsize)。
　　b)在新集合中随机选择出c个竞争者(一般c=popsize/2),将新集合中每个个体分别与c个竞争者比较适应值,记录每个个体的胜利数,并将最优适应值的个体胜利数设置为最高,以保证形势知识存储了最优个体。
　　c)选择胜利数最靠前的e个个体(本文e=popsize)作为新的形势知识。
　　2.3.2 标准知识的更新
　　假设第i个个体影响第j个决策变量的下边界,第k个个体影响第j个决策变量的上边界,则j的上下边界及其对应的适应值分别为
　　
　　lk+1j=xki, jif xki, j≤lkj or f(xki)　　lkjotherwise(6)
　　
　　lk+1j=f(xki)if xki, j≤lkj or f(xki)　　lkjotherwise(7)
　　
　　uk+1j=xki, jif xki, j≥ukj or f(xki)　　ukjotherwise(8)
　　
　　uk+1j=f(xki)if xki, j≥ukj or f(xki)　　ukjotherwise(9)
　　2.4 接受函数
　　种群空间通过接受函数将个体经验传递到信念空间,实际上是向信念空间提供一组最优子集。在最优化问题中,一般是按一定的百分比取排行靠前的个体,通常取20%~25%,但也根据不同问题设置动态接受函数[11]、模糊接受函数[12,13]等。在本文中,由于采取了锦标赛法更新形势知识,接受函数的处理也相应作了改变。在更新形势知识时,接受函数将接受当代所有个体;在更新标准知识时,接受函数获取形势知识前top位(本文top=popsize×25%)。
　　2.5 影响函数
　　在迭代过程中,信念空间的知识通过两种方式影响优化变量:a)在标准知识所代表的优胜区间附近进行混沌搜索;b)在形势知识所代表的优秀个体附近进行混沌扰动。
　　2.5.1 利用标准知识进行混沌搜索
　　标准知识存储了最优解最可能出现的范围,该范围用优胜区间(lj,uj) 描述。由logistic映射产生的混沌变量在(0,1)上具有两头多、中间少的分布特征[9]。在本文中,对于个体的每个决策变量j,通过所对应的优胜区间(lj,uj),将其取值范围(aj,bj)划分为(aj,lj)、(lj,uj)、(uj,bj)三个区间,然后将混沌变量随机映射到三个区间里的任意一个。通过这种方法,新个体的每一维决策变量将主要分布在优胜区间附近,达到了用标准知识来指导混沌搜索的目的。
　　
　　xi, j=aj+zi×|aj-lj| if random()=0
　　lj+zi×|lj-uj|if random()=1
　　uj+zi×|uj-bj|if random()=2(10)

　2.5.2 利用形势知识进行混沌扰动
　　形势知识是存储了当前优秀个体的列表,是其他个体的典范,能用来指导其他个体的产生。其列表长度为群体空间规模大小。在本文算法中,形势知识是由混沌迭代形成的优秀个体经验,存储了优秀个体的具体位置,因此,它弥补了混沌变量受标准知识约束后丧失的全局性,具有较强的全局指导能力,能在搜索过程中起到逃逸作用。
　　本文先进行混沌搜索,然后更新形势知识,得到一些优秀个体,再在优秀个体附近进行混沌扰动,有利于挖掘出更优秀的个体,获取当前最优解的全局分布信息,因而能有效避免算法陷入局部最优解。具体描述为
　xi, j=ei+(zi-0.5)×|uj-lj|(11)
　　2.6 混沌文化算法的算法流程
　　综上所述,本文提出的求解非线性函数最优化问题的混沌文化算法流程如下:
　　a)t=0;
　　b)初始化混沌变量,随机产生初始混沌变量(不能为logistic映射不动点0.25、0.5和0.75);
　　c)初始化群体空间和相关参数;
　　d)初始化信念空间中的形势知识和标准知识;
　　e)评价群体空间内个体适应度,符合要求结束,否则往下执行;
　　f)更新信念空间中的形势知识和标准知识;
　　g)混沌变量迭代搜索,按式(2)产生新的混沌变量;
　　h)在信念空间标准知识指导下,按式(10)进行混沌搜索;
　　i)评价群体空间内个体适应度,更新信念空间中的形势知识;
　　j)在信念空间形势知识指导下,按式(11)进行混沌扰动;
　　k)t=t+1;
　　l)转到e),直到满足终止条件。
　　3 实例研究
　　混沌文化算法综合了混沌搜索优化和文化算法的优势,为了便于比较,本文分别从文献[14,15]里选取了六个函数进行优化设计,并分别与文献[15]所用基于竞争—协作式信息交互的并行混沌优化算法(算法1)和文献[14]所用基于进化规划的文化算法(算法2)进行比较。算法1和2分别是各自领域里比较前沿的算法,都能有效解决函数优化问题。本文算法取群体空间规模为popsize=20,将各个算法独立运行30次。优化函数如下:
　　f1=-0.002-25j=11j+2i=1(xi-aij)6,-65536≤xi≤65536(12)
　　
　　[aij]=-32-1601632-32…1632
　　-32-32-32-32-32-16…3232
　　
　　f2=sin2x21+x22-0.5(1+0.001(x21+x22))2-0.5,-100≤xi≤100(13)
　　
　　f3=(x21+x22)0.25[sin2 50((x21+x22)0.1)+1],-100≤xi≤100(14)
　　
　　f4=-20 exp(-0.2 1/n×ni=1x2i-exp(1/n×ni=1cos 2πxi)+20+e,-32.768≤xi≤32.768(15)
　　
　　f5=1/4000ni=1x4i-ni=1cos(xi/i)+1,-600≤xi≤600(16)
　　
　　f6=30i=1(5j=1(jaj-1ixj+1)-[6j=1(aj-1ixj)]2-1)2+x21,ai=(i-1)/29,-2≤xi≤2(17)
　　
　　其中:f1是大变量区间函数;f2和f3是存在局部极值点的函数;f4和f5是高维复杂函数,维数高达30维;f6函数比较复杂,一般方法很难取到其最优值点。混沌文化算法与其他算法的对比结果见表1。表中f*为实际最优值;f*为30次运行的平均最优值;为30次运行所用平均时间,以ms为单位;v为优胜率即30次运行中获得最优值的次数百分比)。
　　表1 混沌文化算法与其他算法的对比
　　
　　函数f
　　算法1
　　f*v
　　
　　算法2
　　f*v
　　
　　本文算法
　　f*v
　　
　　f1-1.002-0.154877286540-0.526565162653-1.002451100f2-1-0.99874596580-0.99643744576-180100
　　f300.1481571824730.01944752890059693
　　f400.284856647800573310006547100
　　f5068962.5515600.014398106755606189100
　　f60.0022880.3845782515700.0068742534500.0028462524710
　　由表1表明,本文所采用的算法要比其他两种算法优秀。算法1不仅搜索时间相对较长,且在处理高维和大变量区间时存在困难;算法2相对比较容易陷入局部极值点,导致算法稳定性不高;混沌文化算法不仅克服了上述缺陷,且在搜索效率和搜索精度方面都要优于其他算法。
　　4 结束语
　　混沌文化算法利用了混沌搜索优化遍历性、随机性,增强了算法的全局搜索能力,同时利用了文化算法的知识引导作用,减少了盲目搜索的次数,提高了算法的搜索效率和精度,增强了算法的通用性。算法在并行结构的基础上,利用标准知识引导混沌搜索,形势知识引导混沌扰动,两者交互进行,因而能有效降低算法对初值的敏感性,增强算法的稳定性,提高算法的整体性能。
　　
　　参考文献:
　　[1]reynolds r g.an introduction to cultural algorithms[c]//proc of the 3rd annual conference on evolutionary programming.san diego,river edge,nj:world scientific publishing co.,inc.,1994:131-139.
　　[2]coello c a,becerra r i.evolutionary multiobjective optimization using a cultural algorithm[c]//proc of ieee swarm intelligence symposium.indianapolis:ieee press,2003:6-13.
　　[3]saleem s,reynolds r.cultural algorithms in dynamic environments[c]//proc ofcongress on evolutionary computation.la jolla:ieee press,2000:1513-1520.
　　[4]yuan xiao-hui,yuan yan-bin.application of cultural algorithm to generation scheduling of hydrothermal systems[j].energy conversion and management,2006,47(16):2192-2201.
　　[5]reynolds r g,zhu shi-nin.knowledge-based function optimization using fuzzy cultural algorithms with evolutionary programming[j].ieee trans on systems, man, and cybernetics,part b:cybernetics, 2001,31(1):1-18.
　　[6]李冰,蒋慰孙.混沌优化方法及其应用[j].控制理论与应用,1997,14(4):613-615.
　　[7]chung c j,reynolds r g.a testbed for solving optimization problems using cultural algorithms[c]//proc of the 4th annual conference on evolutionary programming.cambridge,massachusetts: mit press,1996:225-236.

论文网首页\|会计论文\|管理论文\|计算机论文\|医药学\|经济学论文\|法学论文\|社会学论文\|文学论文\|教育论文\|理学论文\|工学论文\|艺术论文\|哲学论文\|文化论文\|外语论文\|论文格式

		用户注册设为首页
	您现在的位置：中国论文网 >> 计算机论文 >> 计算机应用论文 >> 正文	会员中心
计算机应用论文计算机理论论文计算机网络论文电子商务论文软件工程论文操作系统论文通信技术论文