基于禁忌搜索的多粒子群协同优化算法研究文献综述.docx

基于禁忌搜索的多粒子群协同优化算法的研究1 引言最优化是一个长期存在的问题，它所研究的内容是讨论在众多方案中什么样的方案最优以及如何找出最优方案。最优化也定义为：在满足一定约束条件下，寻找一组参数值，使系统的某些性能指标达到最大值或最小值。最优化问题是人们在科学研究和生产实践中经常遇到的问题，长期以来，人们对优化问题进行了不懈地探讨和研究。早在17世纪，在英国科学家Newtow发明微积分时代，已经提出极值问题，后来又提出约束优化问题并提出Lagrange乘数法；1947年法国数学家Cauchy研究了函数值沿什么方向下降最快的问题，提出最快下降法；这些方法都归为传统优化方法。目前，传统优化算法能够解决许多工程、社会及经济中建立的实际优化问题。但随着技术的进步，工程实践问题变得越来越复杂，传统的计算方法面临着计算复杂度高、计算时间长等问题，特别是对一些NP难和NP完全问题，设计用于求解这些问题的精确算法往往由于起指数级的计算复杂性而令人无法接受。为了在求解时间和求解精度上取得平衡，计算机科学家们提出了形形色色具有启发式特征的计算方法，希望通过模拟大自然和人类的智慧在可接受时间内实现对问题的最优化求解。这些算法就是智能优化算法。如今，智能优化算法主要有遗传算法(Genetic Alogrithm，启发于生物种群通过遗传和自然选择不断进化的功能)[1]、人工免疫系统(Artificial Immune Systems，模拟于生物免疫系统的学习与认知功能)[2]、粒子群优化算法(Particle Swarm Optimization，简称PSO)、蚁群算法(Ant Colony Opimization，模仿蚂蚁群体在路径选择和信息传递方面的行为)[3]、模拟退火与禁忌算法等等。粒子群优化算法（PSO），又称为微粒群优化算法，源于Craig Reynols提出的Boid模型[4]，由美国的Eberhart 和Kennedy 博士于1995年提出的一种全局搜索算法【5】【6】，同时它也是一种模拟自然界生物活动以及群体智能的随机搜索算法。它同遗传算法类似，是一种基于群体迭代的计算方法，但是在算法实现过程中没有遗传的交叉、变异等操作。PSO 的基本思想是通过群体中个体之间的协作和信息共享来寻找最优解，和其它优化算法相比，它的优点在于：算法流程简单、参数简洁、易于实现，无需复杂的搜索调整；另外它速度快、搜索范围大，且对优化问题的连续性无任何要求。现在，PSO 算法已在电力系统、电磁学、经济分配、医学图像配准、多目标优化、系统设计、机器学习与训练、数据挖掘与分类、模式识别、信号控制、离散组合优化等领域得到成功应用。2 研究背景粒子群优化算法（PSO）是演化计算界的研究热点之一，目前已提出了多种改进PSO算法.但是这些算法大多着眼于PSO的参数选择或某个参数的动态修改策略，故难以克服PSO算法易陷入局部极小的固有弱点.为使PSO算法摆脱局部极小，Van Den Bergh提出了协同粒子群优化算法(PSCO)【7】，通过将决策变量与子群之间建立对应的关系实施优化，这是PSO方面的典型协同方法提出粒子扰动策略，即当PSO算法陷入局部极小点时重置粒子的速度，迫使粒子群摆脱局部极小点.但这种协同PSO算法有明显的“启动延迟”（start-up deiay）现象【8】，在迭代初期，适应值下降缓慢，换言之，收敛速度慢。文献[8]的实验结果显示粒子群数目越大，收敛越慢。为此本文在多粒子群协同优化算法中引入了禁忌搜索的思想，禁忌搜索是一种确定性德局部极小突跳策略，这种改进后的算法（即禁忌搜索的多粒子群协同优化混合算法（TS-PSCO））可以更好的跳出局部最优，加快收敛速度，获得更高精度的解。3 国内外现状粒子群算法自提出以来，由于其简洁易实现的特点，广泛的适应性，得到了学着广泛注意与研究。特别是本世纪初以来，对其进行分析、改进与应用研究日渐增长。作为一种新颖的群体智能搜索技术，研究者们的大部分精力都集中于对其算法结构和性能的提升以及初步理论基础方面的研究，主要包括：收敛性分析、参数选择与优化、粒子多样性及算法融合。(1) 粒子群算法的收敛性研究PSO算法的收敛性分析一直是研究的热点，也是难点。当前，PSO算法的收敛性研究多集中在一些简化条件下的结果，多数研究者都是通过大规模计算来对算法进行研究与分析，所采用的工具主要是随机过程、微分方程和差分方程。Van Den Bergh【9】通过采用集合论的方法研究得出：在无任何改进的情况下，标准PSO算法既不能收敛到全局最优点，也不能收敛到局部最优点，而对于某些改进的粒子群算法可以保证算法的局部或全局收敛性。Clerc【10】较完整的给出了PSO 算法的稳定性和收敛性分析，发现通过引入压缩因子可以保证算法的收敛。Trelea