智能优化算法

优化问题一直是科学和工程研究领域的热点问题。传统的优化方法在处理大维数、多模态等复杂问题上存在很多不足,因此有必要研究和探讨新的优化算法。国内外许多研究学者因此提出了多种智能优化算法。本文首先提出智能优化算法的研究背景以及意义,然后介绍了智能优化算法及混合智能优化算法的研究现状,最后针对智能优化的某些局限性给出了自己的一些看法与评价。

一、智能优化算法研究的背景与意义

    最优化理论与算法是一个重要的数学分支,它所研究的问题是讨论在众多的方案中什么样的方案最优以及怎样找到最优方案。它广泛应用于农业、工业、国防、工程、交通、化工、等众多领域,并在资源分配、工程设计、生产计划安排、城建规划等领域中产生了巨大的经济效益和社会效益。同时,优化在材料科学、控制论、结构力学、环境科学、生命科学等其他科学研究领域也有广泛应用。国内外的应用实践表明,在同样的条件下,优化处理技术对系统效率的提高、资源的合理利用、能耗的降低及经济效益的提高等均有显著的效果,且效果随着处理对象规模和复杂度的增加而更加显著。

由于生产和科学研究突飞猛进地发展,特别是电子计算机日益广泛应用,使最优化问题的研究不仅成为一种迫切需要,而且有了求解的有力工具,因此最优化理论和算法迅速发展起来,同时社会对各种工程问题优化算法的需求也越来越迫切。目前,基于严格机理模型的开放式方程建模与优化被认为是国际上主流技术。各大科研机构和工程公司纷纷投入大量的人力物力财力对系统的建模与优化进行细致深入的研究,意图取得突破性的进展。然而,基于严格机理模型所得到的优化命题通常具有方程数多、非线性强、变量维数高等特点,这使得相关变量的存储、计算及命题的求解都相当困难.优化问题不仅工业界存在,国民经济的各个领域中也存在着相当多的涉及因数多、影响广、难度高和规模大的优化命题,如运输中的最优调度、生产流程的最优排产、资源的最优分配、农作物的合理布局、工程的最优设计以及国土的最优开发等等,所有这些问题的解决也必须有一个相当有效的优化工具来进行求解。面对大型问题,常规的优化算法已无能为力,无论是在计算速度、收敛性、初值敏感性等方面都远不能满足要求。因此,针对常规优化算法遇到的难点,研究智能的优化方法具有重要意义。

二、智能优化算法的介绍以及研究现状

智能优化算法又称为现代启发式算法,是一种具有全局优化性能、通用性强、并且适合于并行处理的算法。这种算法一般具有严密的理论依据,而不是单纯凭借专家经验,理论上可以在一定时间内找到最优解或近似最优解。常用的智能优化算法有模拟退火算法、遗传算法、群智能算法等。下面首先对这几种常用的智能优化算法作简要的介绍。

  1. 模拟退火算法

    模拟退火算法(Simulated Annealing,SA)是1983年由Kirkpatrick首次将其应用于组合优化领域而提出来的一种组合优化算法,它是基于Monte-Carlo迭代求解策略的一种随机寻优算法,其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法从某一较高初温出发,伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解,即在局部最优解能概率性地跳出并最终趋于全局最优。模拟退火算法是一种通用的优化算法,理论上算法具有概率的全局优化性能,目前已在工程中得到了广泛应用,诸如VLSI、生产调度、控制工程、机器学习、神经网络、信号处理等领域。   模拟退火算法是通过赋予搜索过程一种时变且最终趋于零的概率突跳性,从而可有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法。

  • 遗传算法

    遗传算法(Genetic Algorithm, GA)是一类借鉴生物界的进化规律演化而来的随机化搜索方法。它是由美国的J. Holland教授1975年首先提出,其主要特点是直接对结构对象进行操作,不存在求导和函数连续性的限定;具有内在的隐并行性和更好的全局寻优能力;采用概率化的寻优方法,能自动获取和指导优化的搜索空间,自适应地调整搜索方向,不需要确定的规则。遗传算法有三个基本算子:选择、交叉和变异. 但是遗传算法的编程实现比较复杂,首先需要对问题进行编码,找到最优解之后还需要对问题进行解码,另外三个算子的实现也有许多参数,如交叉率和变异率,并且这些参数的选择严重影响解的品质,而目前这些参数的选择大部分是依靠经验。

3、群智能算法

    随着人类对生物启发式计算的研究,一些社会性动物(如蚁群、蜂群、鸟群)的自组织行为引起了科学家的广泛关注。这些社会性动物在漫长的进化过程中形成了一个共同的特点:个体的行为都很简单,但当他们一起协同工作时,却能够“突现”非常复杂的行为特征。目前,在群智能理论研究领域有以下三种主要算法:蚁群算法(Ant Colony Optimization,ACO)、粒子群优化算法(Particle Swarm Optimization,PSO)和人工鱼群算法(Artificial Fish Swarm Algorithm,AFSA)。其中,蚁群算法模拟了蚂蚁群落食物采集过程,并已成功应用于许多离散优化问题。而粒子群优化算法也是起源于对简单社会系统的模拟,最初主要模拟了鸟群觅食的过程,但后来研究者发现它是一种很好的优化工具。我国学者李晓磊等提出的人工鱼群算法,是一种模拟鱼的觅食、聚群和追尾行为的随机搜索算法。三种群智能优化算法的主要介绍如下:

  蚁群算法(ant colony optimization, ACO),又称蚂蚁算法,是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法,初步的研究表明该算法具有许多优良的性质。针对PID控制器参数优化设计问题,将蚁群算法设计的结果与遗传算法设计的结果进行了比较,数值仿真结果表明,蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。     粒子群算法(Particle Swarm Optimization, PSO), 是近年来发展起来的一种新的进化算法(Evolu2tionary Algorithm, EA)。在研究鸟类和鱼类的群体行为基础上,Kennedy和Eberhart于1995年提出的一种群智能算法一一粒子群算法,其思想主要来源于人工生命和演化计算理论,并模仿了鸟群飞行觅食行为,通过鸟群集体的协作使群体达到最优。粒子群算法作为进化计算的一个分支,也是一种基于迭代的优化工具。系统首先初始化为一组随机解,并通过迭代搜寻最优值。其机制和原理简单,仅仅通过更新位置和速度来不断进化到全局最优解,可调参数少,无需梯度信息,算法运行效率高且容易实现。粒子群算法的基本原理:在算法中,搜索空间中的一只鸟(即粒子)当作是每个优化问题的解,所有的粒子都有一个被优化的函数决定的适应值并且有一个速度决定它们飞翔的方向和速率,粒子们追随当前的最优粒子在解空间中搜索。算法首先初始化一群随机粒子,然后通过迭代找到最优解,在每一次迭代中,粒子通过跟踪个体极值和全局极值这两个“极值”来更新自己的速度与位置。

人工鱼群算法是由李晓磊、邵之江、钱积新等人于2002年提出的一种新的群智能优

化算法。它采用了自上而下的寻优模式去模仿自然界鱼群的觅食行为,主要利用鱼的觅食、

聚群和追尾现象,构造个体的底层行为,通过鱼群中各个体的局部寻优,达到全局最优值

在群体中凸现的目的。研究表明,该算法具有较好的收敛性。

      因为单纯智能优化算法存在较大的局限性,比如蚁群算法在寻优过重中易陷入局部最优解,几乎不可能获得真正的最优解。计算参数难以确定,对于不同的问题,甚至同一问题但不同规模,都需要调整相应的参数,否则要么不能获得令人满意的结果,要么收敛时间很长,而且单纯对智能优化算法的改进,不能很好地解决算法的缺点,所以很多学者尝试将不同的优化算法相混合,于是便产生了许多混合智能优化算法。下面简要介绍混合优化算法的现状。

在混合智能优化算法中,充分发挥各种算法的优点,实现优势互补,克服单纯智能优化算法的缺点,取得了很好的效果。混合智能优化算法的研究成果显著,如文献[1-2]将蚁群算法与模拟退火算法相结合,该类算法中,首先由模拟退火算法产生较优解,然后按照蚁群算法,完成一次遍历之后,采用模拟退火算法在领域内找到一个解,最终,若路径长度差小于允许目标函数变坏范围内则接受;另外,还有文献[3]提出的蚁群算法和爬山法相结合以及文献[4]提出的蚁群算法和混沌算法相结合等等关于蚁群混合智能优化算法。在关于粒子群混合智能优化算法研究中,提出混合算法最多的是将粒子群算法和遗传算法相混合,如文献[5]和文献[6]提出结合遗传算法中选择算子,其结合思想:按粒子适应度大小赋予每个粒子一个被选中的概率,根据概率对粒子进行选择用于生成下一代;文献[7]提出结合遗传算法中变异算子,其结合思想:测试所有粒子与当前最优距离,当距离小于一定值时,以一定的变异率让粒子群随机初始化;文献[8]结合遗传算法中交叉算子,提出了带有繁殖和子种群的混合算法,在每轮迭代中随机选择一定的粒子作父代,随机两两交叉以产生具有新的空间坐标和速度的子代粒子取代父代以保持种群规模,并且把种群分为若干子种群,交叉可以在同一子种群内进行,也可在不同种群间进行。此外,还如文献[9]提出了粒子群算法与混沌算法相结合、文献[10]和文献[11]与模拟退火算法相结合等。以上混合智能优化算法的仿真实验中,均与单纯智能优化算法或改进型的智能优化算法做了比较,从比较结果来看,混合智能优化算法无论是收敛速度还是最优解的精度,都要优于智能优化算法。因此,将各种算法的优点混合利用,得到的混合智能优化算法,这种思路是可行的,值得研究。

三、针对智能优化算法的局限性的一些看法

    下面只针对粒子群优化算法的局限性提出一些看法。和其他算法相比,粒子群优化算法主要有以下特点:

(1)算法原理简单,需要调节的参数较少,且在很多情况下直接按经验值设置参数就可以获得较好的收敛性;

(2)算法采用十数编码,无需另外进行编码设计,而且可以直接取目标函数本身作为适应值函数,根据目标函数值进行迭代搜索;

    (3)算法根据粒子速度来决定搜索路径,且沿着梯度方向搜索,搜索速度快,在大多数情况下,所有的粒子都能收敛于最优解。

    但是粒子群算法算法也存在自身的不足,主要有两个方面:

   (1)为使初始种群能够均匀分布于目标区域,可以通过随机性质的初始化来实现,但是种群的质量如何则难以保证,极有可能出现的情况是:存在一部分与最优解相距甚远的个体。由于初始化和进化过程都具有一定的随机性,这使得的更新失去了明确的目标,大大制约算法的收敛性能;

    (2)个体的速度和位置的更新本质上依赖于自身信息、个体极值信息和种群极值信息这三个信息。这个过程具有正反馈性质,当前两个信息占据优势时,算法往往进行到局部最优时就停止下来。而当某些粒子的位置及其接近且小于1时,速度就越来越小,逐渐趋于零,粒子的“惰性”此时尽显无遗,随着进化的不断进行,其他粒子也会很快地聚集在这些惰性个体周围致使算法过早的收敛,难以得到最优解。

为克服粒子群算法的缺点,出现了大量的改进算法,主要有以下几种类型:基于模型的改进算法、基于种群多样性的改进算法、与其他算法的融合而形成的算法(混合智能优化算法)等,使粒子群算法有了不同程度的性能提高。




已发布

分类

来自

标签: