群智能算法发展研究

群智能算法发展研究 群智能算法发展研究 摘 要 最优化技术的应用日渐广泛，传统的优化方法对于解决复杂问题变得无能为力。群智能算法在这种背景下产生并迅速发展。目前已研究出许多种类的群智能优化算法，包括蚁群、粒子群、人工鱼群、混合蛙跳、人工蜂、萤火虫算法等。本文主要介绍群智能算法的发展，阐述上述典型算法产生的生物原理、算法思想和应用。 关键字 群智能算法； ACO； PSO； AFSA； SFLA；ABC；FA 中图分类号 Q5-3 文献标识码A 文章编号 1674-6708（2014）114-0160-02 1 群智能算法概述 群智能算法是近几十年发展起来的一类基于生物群体行为规律的全局概率搜索算法。这些算法将搜索空间中的每一个可行解视为生物个体，解的搜索和优化过程视为个体的进化或觅食过程。生物个体适应环境的能力用来度量待求解问题的目标函数，生物个体的进化或觅食过程用来模拟优化中较差的可行解被具有优势的可行解替代的迭代过程。下文将对几种典型的群智能算法进行简要的介绍。 2 典型群智能优化算法 2.1 蚁群算法 1991年意大利学者Dorigo M等受到自然界中蚁群觅食行为启发而提出了蚁群算法 （Ant Colony Optimization， ACO）。 蚁群算法的思想是：在最短路径的找寻过程中，每只蚂蚁只可以根据局部信息调整路径上的信息素，一轮循环结束后，采取全局信息对路径上的信息量再进行一次调整，且只对寻优过程中发现的最好路径上的信息素进行加强。在蚁群算法中，蚂蚁逐步地构造问题的可行解，在解的构造期间，每只蚂蚁使用概率方式向下一个节点跳转，这个节点是具有较强信息素和较高启发式因子的方向，直至无法进一步移动。此时，蚂蚁所走路径对应于待求解问题的一个可行解。 蚁群算法目前已成功地用于解决旅行商TSP问题、数据挖掘、二次指派问题、网络路由优化、机器人路径规划、图着色、物流配送车辆调度、PID控制参数优化及无线传感器网络等问题。 2.2 粒子群算法 1995年美国的Kennedy等受鸟群捕食行为的启发而提出了粒子群算法（Particle Swarm Optimization， PSO）。 粒子群算法的思想是：将群体中的任一个个体，即每个可行解，视为D维搜索空间的一个有飞行方向和速度的粒子。所有的粒子都有一个被目标函数决定的适应值，且记忆了自身曾经获得的最好位置及当前位置，视为自身的飞行经验。同时每个粒子还知道整个群体所有粒子已获得的最优位置，视为群体的飞行经验。在迭代过程中，所有的粒子将不断地统计个体的飞行经验和整个群体的飞行经验，以此动态调整本身飞行的方向和速度。在此过程中，个体逐步迁移到较优的区域，使群体最终搜索到问题的最优解。 粒子群算法的应用领域众多，如模式识别与图像处理、工程应用、神经网络训练、模糊系统控制、化工系统处理、滤波器设计、仿人智能控制参数优化、数据聚类等。 2.3 人工鱼算法 2002年由我国的李晓磊等受鱼群运动行为的启发而提出了人工鱼群算法 （Artificial Fish-Swarm Algorithm， AFSA）。 人工鱼群算法的思想是：将人工鱼随机地分布于解空间中，解空间中包含着若干局部最优值和一个全局最优值。可将最优值视为食物的浓度，而全局最优值为最大的食物浓度，且人工鱼将移动聚集到食物浓度较大的区域，通过移动策略来控制人工鱼个体的四种行为（觅食、聚群、追尾和随机），用视野来限制个体的邻域，用步长来控制个体探索的进度，用拥挤度来控制群体的过度密集。寻优期间，每次迭代执行完，人工鱼都将对比自身状态和公告板状态，如自身具有优势，则更新公告板状态，确保公告板为最优状态。 人工鱼群算法已在参数估计、组合优化、前向神经网络优化、电力系统无功优化、输电网规划、边坡稳定、非线性方程求解等方面得到应用，且取得了较好的效果。 2.4 混合蛙跳算法 2003年Eusuff等人受青蛙觅食特征的启发而提出了混合蛙跳算法【4】 （Shuffled Frog Leaping Algorithm， SFLA）。 混合蛙跳算法的思想是：将青蛙个体随机地分布于解空间中，每只青蛙表示解空间的一个解。在进化更新的过程中既有全局性的信息交流，还有内部的信息交流。根据青蛙个体的适应度值的优劣进行排序和分组，组内只有适应度最差的青蛙更新，元进化并混合各组，在各组一轮元进化后，将组中的青蛙重新排序、分组并记录全局最优解，之后再继续局部搜索的过程。青蛙更新的学习对象首先是组内最优，其次是群体最优，若两次都未能进步，则随机初始化。 混合蛙跳算法已经应用于多个领域，如水资源网络优化、数据聚类、桥面修复、风电场电力系统动态优化、装配线排序、流水车间调度、PID控制器参数调节等。 2.5 人工蜂算法 2005年由土耳其的Karaboga等受蜜蜂采蜜行为的启发而提出了人工蜂群算法（Artificial Bee Colony， ABC）。 人工蜂群算法的思想是：将虚拟蜜蜂群初始时随机分布在解空间中，将食物源的位置抽象成解空间中的点（可行解）。通过三种蜜蜂对食物源位置（解）修正，进行一次循环搜索过程。引领蜂通过对比附近食物源的花蜜量（适应度），来对现有食物源位置（解）进行修正。如果新食物源的花蜜量（适应度）比现有的高，那么引领蜂记忆新食物源（解），放弃现有的。在引领蜂的搜索过程完成后，它们通过跳舞与跟随蜂传递食物源信息。跟随蜂通过汇总和评估所有食物源信息，计算出一个关于花蜜量的概率值，通过比较概率选取食物源。跟随蜂也是根据贪婪选择策略来更新当前食物源的位置。利用侦察蜂来使得陷入局部搜索停滞的蜜蜂跳出。 人工蜂群算法已经应用于多个领域，如车辆路径问题、人工神经网络训练、作业车间调度问题、数据聚类以及各类连续优化问题等。 2.6 萤火虫算法 2009年由剑桥大学的Xin-She Yang受萤火虫发光行为的启发而提出了萤火虫算法（Firefly Algorithm， FA）。 萤火虫算法的思想是：将萤火虫个体作为解随机地分布于解空间中。解的搜索和优化过程视为每只萤火虫的移动和吸引过程。个体所在位置的优劣用来度量所求问题目标函数。个体进化的过程用来模拟优化中较差的可行解被具有优势的可行解替代的迭代过程。萤火虫根据自身亮度和吸引度两个要素来更新自己的位置。萤火虫所在位置的目标值决定其能产生的荧光亮度，所处位置（目标值）越好其亮度越高。萤火虫的亮度与吸引力成正比，视线范围内，亮度稍弱的萤火虫将被吸引，朝着较亮萤火虫的方向移动，以完成的位置进化。当亮度相同时，萤火虫则随机地进行位置移动。萤火虫之间的距离与亮度和吸引度成反比，也即距离越大，亮度和吸引度越小。 目前萤火虫算法已应用在生产调度、路径规划、神经网络训练、天线阵列设计优化、图像处理、机械结构设计优化、负载经济均衡分配问题、复杂函数优化等方面。 3 结论 本文在简述群智能算法的基础上，对近年来发展的几种典型的群智能算法的生物原理、算法思想和应用进行了阐述和研究，为群智能算法的深入研究奠定了基础。 参考文献 【1】Colomi A，Dorigo M，Maniezzo Vhe Ant System： An autocatalytic optimization process，Technical Report 91-016，Dept.of Electronics，Politecnicco di Milano，Italy，1991. 【2】Kennedy J，Eberhart RC.Particle swarm optimizationC.IEEE International Conference on Neural Networks，Perth，Piscataway，NJ，Australia： IEEE Service Center，1995，1942-1948. 【3】李晓磊，邵之江，钱积新.一种基于动物自治体的寻优模式：鱼群算法J.系统工程理论与实践，2002，11，32-38. 【5】Karaboga D.An Idea Based On Honey Bee Swarm for Numerical OptimizationR.Erciyes Uiversity，Technical Report： TR06，2005. 【6】Yang Xin-she.Nature-inspired metaheuristic algorithmsM.Luniver Press，UK.2008：83-96.