群智能优化算法研究

ISSN 1009 3044E-mail: eduf@cce.nel.cnComputer Knowleoge and Technology电脯知识与技术htp:/://ww dnzs.net.cnVol6,No.21, July 2010, pp.5845-5846Tel:+86- -51- -5690963 5690964群智能优化算法研究王大将,蔡瑞英",徐新伟|(1.南京陆军指挥学院作战实验中心,江苏南京210045 ;2.南京T业大学信息科学与工程学院,江苏南京2100090)摘要:群智能优化算法是一种新型的优化算法。该文介绍了几种常见的群智能优化算法,包括粒子群优化算法、蚁群优化算法、人工免疫算法、人工鱼群算法,分析了它们的优缺点及使用情况,提出了群智能优化算法的发展方向。关键词:智能优化算法;粒子群优化算法;蚁群优化算法;人工免疫算法;人工鱼群算法中圈分类号:TP18文献标识码:A文章编号:1009 3044(2010)21- -5845- 02Research on Swarm Intelligence Optimization AlgorithmWANG Da-jiang', CAI Rui- ying, XU Xin-weil(1.Army Command College, Experimental Operations Center, Nanjing 210045,China; 2.Nanjing Univenity of Technology, InformationScience and Engineering. Najing 210009, China)Abstract: Intelligence optimization algorithm is a new type optimization algorithm. This paper presents several common Swarm optimiza-tion algorithms, such as particle swarn optimization algorithm, ant colony optimization algorithm, artificial immune algorithm and artificialfish swarmn algorithm, suggests evolutional trend of itelligegnce optimization algorithm based on analyzing charcterstis.Key words: itelligence optimizarion algoithm; particle swarm opinization algorithm; ant colony optimization algorithm; arifcial im-mune algorithm; artifcial fish swarm algorithm优化算法的研究是优化技术研兖的关键内容,它基于某种思想和机制,通过一定的途径或规则来得到满足用户要求的问题的解。传统的优化算法有线性规划和非线性规划法动态规划法、网络流优化算法等,其算法复杂度一般很大,只适于求解小规模向题,在实际工程中往往不适用。20世纪80年代以来,一种新颖的优化算法.如遗传算法、模拟退火算法、蚁群算法、粒子群算法.人工免疫算法及其混合优化策略等,通过模拟或揭示某些自然现象或过程面得到发展,为那些传统优化技术难以处理的组合优化问题提供了切实可行的解决方法。在优化领城,由于这些算法构造的直观性与自然机理.因此通常称作智能优化算法。1群智能优化算法智能优化算法是模拟自然界生物系统,各个生物体依赖自身的本能.通过无意识的进化、寻优行为来优化生存状态,以适应环境的依赖优化方法,具有许多与传统优化算法不同的特点。智能优化算法根据其中个体的数量.可分为基于个体的和基于群的两种,如,模拟退火算法是基于个体的,而蚁群优化算法粒子群优化算法、人工免疫算法和人工鱼群算法是基于种群的。以下对几种常用的群智能优化算法作简要研究。1.1粒子群优化算法粒子群优化(Particle Swarm Opimization,PSO)算法是J.Kennedy和R.C.Eberhart 于1995年提出的- -种高效的群集智能协同优化算法,其基本思想来源于对鸟群社会模型的研究及行为模拟,以个体的协作与竞争来完成对复杂搜索空阃内优解的搜索.即所有粒子根据个体经验和群体经验不断调整自已的速度和位置,朗着个体最优和群体最优的目标飞行来完成更新优化,具有概念简单，收敛速度快,可调参数少等优点,非常适用于复杂环境中的优化问题求解。但粒子群算法在后期难以维持种群的多样性,而且易陷人局部极值。自提出以来,很多研究者从参数设置收敛性、拓扑结构、与其它算法融合等角度对传统PS0进行研究,并针对其不足提出了各种改进.以提高算法性能。如文献[1]提出的动态离散粒子群优化算法较好地解决了动态环境下离散优化问题。文献[2]提出的并行粒子群优化算法,较好地解决了网络系统中具有异构性和动态性的资源分配优化问题。文献[3]基于混沌思想模糊自适应参数策略的粒子群优化算法,有效提高了算法的收敛速度.改善了多维空间的全局搜索能力。目前,PSO已经广泛的应用于函数优化,人工神经网络训练,模式识别,模糊控制、车辆调度等领城。1.2蚊群优化算法蚁群优化(Ant Colony Opimization, ACO)算法是根据自然界中蚂蚁群体寻优的行为提出来的一种全局启发式优化算法,它是对中国煤化工收稿日期:2010-05-12基金项目;江苏省高校自然科学基金(05K]JB520048)MHCNMHG作者简介:王大将(1983-),女,南京陆军指挥学院作战实验中心讲师,研究方向为数据挖掘,智能决策;蔡瑞英(1950-),女,南京工业大学信息科学与工程学院教授,研究方向为计算智能,虚拟制造;徐新伟(1984-),男,南京陆军指挥学院围书馆助理馆員,研究方向为计算机网络。.....人工俐及识别技术..5845万芳数据Computer Knowledge and Technology电脑知设与技术第6卷第21期(2010年7月)真实蚁群协作过程的模拟.每只蚂蚁在候选的空间中独立搜索解,并在所寻得的解上留下一定的信息量。解的性能越好蚂蚁留在其上的信息量越大,而信息量越大的解被再次选择的可能性也越大。所有解上的初始信息量相同,随若算法的推进,较优解上的信息量逐渐增加,最终收敛到最优解或近似最优解。该算法具有很强的发现较优解的能力、鲁棒性强易于计算机实现等优点,在动态环境下表现出高度的灵活性和健壮性,但也存在着一些问题,如需要较长的搜索时间,搜索速度慢，且容易出现停滞现象,不能对解空间进行全面搜索。人们针对其不足提出了多种改进,如文献[4]提出的基于混合行为的自适应蚁群算法,通过引人具有多行为的混合蚂蚁来扩大搜索空间,避免早熟和停滞现象。目前,蚊群优化算法在求解TSP问题、分配问题job- shop 调度问题等方面取得了大量较好的实验结果。13人工免疫算法人工免疫(Arificial Immune)算法是基于生物免疫系统提出的一种新型智能算法,它将要分析的数据看作抗原,将算法产生反映抗原特征的数据看作抗体,模拟免疫网络抗体抗原之间的相互刺激和作用,按照一定 的算法实现数据处理,该算法能够有效提取目标函数的绝大部分局部峰值,并具备群体数量自动调节和实数编码等优良特性,具有搜索效率高.维持多样性好和学习记忆力强等优点,为优化问题提供了新颖的解决方法和途径。但该算法频繁地抽取疫苗和接种疫苗花费了大量时间,使效率低下;求觶全局.最优解需要的群体规模相对较大,从而增加了计算量。针对其不足,人们提出了多种改进.如文献[5]提出的协作型人工免疫网络模型,新增记忆细胞间的协作算子,实现记忆细胞之间既竞争又协作的新型关系,提高了收敛速度,缩短了执行时间,保证了全局寻优能力。目前,人工免疫算法已应用于控制.数据处理、优化学习和故障诊断等领域。1.4人工鱼群算法人工鱼群(ArtificialFishSwarm)算法是基于动物行为的自治体寻优模式,通过模拟鱼群的觅食和生存活动来实现在空间中寻求全局最优的一种新思路。该算法采用自下而上的设计方法,即首先构造人工鱼的个体模型;用公告板记录最优人工鱼个体的状态,确定行为评价方法和终止条件;个体在寻优的过程中自适应地选择合适的行为;最后全局最优结果通过群体或某个个体表现出来。该算法具有良好的全局搜索力,并具有对初值.参数选择不敏感鲁棒性强简单易实现等优点。但也存在-些缺陷,如搜索精度不高,后期收敛慢等。针对不足,近年来人们提出了多种改进方法,如文献[6]提出的简化人工鱼群算法,在- -次迭代进化中同时根据人工鱼觅食结果、种群中心位置和种群最优位置.调螫下一步位置,从而增强了该算法的全局搜索能力,提高了运行速度。文献[7]提出的基于变异算子的人工鱼群算法,引入变异算子增加了群体的多样性,避免了人工鱼群算法陷入局部最优,并提高了收敛速度。目前,人工鱼群算法在机器人路径规划、电力系统优化等方面得到了应用,取得了较好的使用效果。2总结与展望各种群智能优化算法都有其应用的优势与不足,从解央实际优化向题角度出发,融合不同类型机制的优化算法,充分发挥它们各自优势,是解决问题的必然发展趋势。近年来,国内外学者正是采用智能优化算法和传统优化算法相结合、智能优化算法与智能优化算法相结合等各种混合算法.成功解决了大量实际工程问题。但从现有的成果来看,这些智能融合算法很多都是针对具体问题来进行的.所解决的问题不同,其融合策略也就存在着很多差异,不具备系统性和一般性。因此,在现有成果的基础上继续进行深入研究,努力探索智能优化算法之间或与其他优化算法相融合的统-机制将是一个非常具有理论意义和应用价值的课题。参考文献:[1]罗桂兰.动态离散粒子群优化算法J计算机工程与设计2009.3024):5708- 5711.[2]李志洁改进粒子群算法在网格资源分配中的优化[J].计算机集成制造系统2009,15(12).2375.-2382.[3]孙勇.基于混沌思想模糊自适应参数策略的粒子群优化算法[J].计算机应用研究2010,27():39--41..[4]王运涛.基于混合行为的自适应蚁群算法[],计算机仿真2002612);151-153.[5]刘丽.基于全局粒子群的协作型人工免疫网络优化算法[].模式识别与人工智能00924):653- -658.[6]王联国.一种简化的人工鱼群算却[]小型微型计算机系统,2009,30(8);1663- 1667.[7]黄华娟.基于变异算子的人工鱼群混合算法[J]计算机工程与应209,4533):28 -30.[8]李福东.联合循环发电系统燃料热值智能优化控制[J}清华大学学报2008.48(2):1737-1741.[9]刘波.融合粒子群与蚁群算法优化XML群体智能搜索[].计算机研究与发展2008.4518):1371-1378.{10]黄平.改进的粒子群优化算法求解电力经济调度[].华中科技大学学报2010,38(1);121-124.中国煤化工MYHCNMHG5846人工警 能及识别技术.....本栏目责任编辑:唐一东.