求解约束优化问题的粒子群算法-研究

《求解约束优化问题的粒子群算法-研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1．1问题的提出第1章绪论无论从事何种职业，优化问题都随处可见，始终伴随着人类的发展。所谓优化问题就是为了实现目标，而选择一条到达目标的最优方案。世界是复杂的，时间是动态的，往往优化问题存在着时间、空间上或者某些主客观因数的约束，这种含有约束条件的优化问题称为约束优化问题。我们看如下一个智力题：一家五口人黑夜过桥，桥最多只能通过两人，且只有一盏油灯，每次过桥需要带一盏灯，两人过去后需一人返回将灯带回。五人过桥速度不一：爷爷：8分钟；奶奶：12分钟；父亲：3分钟；母亲：6分钟；小孩：1分钟，如何使这一家用最短的时间过河。像这样的例子就可以称为约束优化问题

2、，对于上述这个问题，约束条件就是只有一盏灯和过桥最多两人，而目标就是最短时间内所有人过桥。优化理论和算法在上个世纪前就已经发展起来，并形成了一门学科。对于约束优化问题的处理，往往是采用优化问题的处理方法，将有约束转化为无约束优化问题。先后出现过诸如线性规划、整数规划、非线性规划和动态规划等方法。这些处理方法在早期处理问题时发挥了巨大作用，但是随着科技的发展、世界的变化，原先的一些静态的或者传统的方法如牛顿法、共轭梯度法、模式搜索法和单纯形法，对于复杂问题的处理已经变得薄弱，于是高效的、动态的优化算法成为了众多学者的研究热点n1。进化算法(演化算法)的产

3、生为解决约束优化问题提供了新的方法。进化算法是上世纪八十年代出现的一类智能算法，它通过模拟某些智能行为来解决现实的问题。其中包括：模拟退火算法(模拟物质燃烧退火的过程)、遗传算法(模拟自然界生物进化中的适者生存的原理，以优胜劣汰为选择根据，最终留下了优值)、神经网络(模拟人类大脑思考的过程，通过一系列的神经元来实现目标值的选取)、蚁群算法(模拟蚂蚁觅食的搜索过程)。由于这些算法都是通过模拟一些智能行为而产生的，所以有人把这类算法统称为智能优化算法。粒子群算法(ParticleSwarmOptimization，PSO)是由美国社会心理学JamesKen

4、nedy和电气工程师RussellEberhart共同提出的瞄1，其基本思想就是利用生物群体模型，模拟鸟类群体觅食的过程，因此它属于智能优化算法的一种。由于粒子群算法模拟的是群体范畴，把它和蚁群算法又叫做群体智能算法。粒子群算法由于其自身简单，收敛速度快并且需要的参数少的特点，被越来越多的学者专家关注，并且在现实生产中的应用也有所研究，先后出现了一批关于对算法本身改进以及应用的论文，促进了粒子群算法的发展沼1。但是任何一种算法毕竟有其局限性，都需要在实践中检验与改进。粒子群算法也不例外，特别是当它用来处理约束优化问题的时候，收敛速度没有处理一般优化问题

5、那么快。主要原因是粒子群算法在收敛初期较快，而后期较慢。由于约束条件的存在，往往后期逼近约束条件的时候，收敛速度慢，容易导致在局部最优点停止不前，也就是早熟现象。另外粒子群算法整体收敛性有待于提高，特别是对于高维复杂函数的收敛，其表现的能力不够强。1．2研究背景及国内外研究状况所谓约束优化问题，就是指在一定的约束条件下，寻找一个或者一组适合的数值，使目标值达到最优或者使最优性度量值得到满足。现实世界中，约束优化问题无处不在，涉及工业、农业、经济、管理等各个领域，因此约束优化问题的研究一直是一个热点。早期约束优化问题由于受到科技的限制，往往处理能力不够强

6、大，基本思想就是将多目标转化为单目标，将动态的转化为静态的，将约束转化为无约束来处理。这些技术在当时来说，很大程度促进了约束优化问题的发展。而其中一些思想和算法至今仍然保留，并在处理某些问题上有其特殊的优越性，如单纯形法H1、最速下降法、牛顿法、共轭梯度法、模式搜索法、罚函数法崎3、拉格朗日乘子法怕’等都是早期比较有效的处理约束优化问题的方法。大体上这些算法可分为三类：第一类如罚函数法，拉格朗日乘子法，它将约束问题转化为一系列无约束问题来求解；第二类如牛顿法，通过迭代点用线性函数去逼近约束问题目标函数；第三类如投影梯度法，它是将无约束问题扩展到约束问题

7、的求解中盯1。对于单目标约束优化问题的处理传统的方法是行之有效的，但是往往我们面对的是多目标约束优化问题，这时候传统的思想与方法就受到了阻碍。部分学者仍然致力于传统算法的改进，但更多的学者将目光转向了寻找新的算法。法国经济学家V．Pareto最早研究经济领域内的多目标优化问题，他提出的理论被称为Pareto最优理论。这种理论提出了一种Pareto支配原则，作为判断优化问题解优劣的依据，被多目标研究者所认同，并成为多目标求解的一个标准。智能算法是近三十年来发展起来的一种优化算法，主要包括：1983年Kirkpatrick提出的模拟退火算法哺1，20世纪9

8、0年代提出的遗传算法旧1，模拟蚂蚁寻找食物的蚁群算法n01，模拟鸟群活动的粒子群算法u¨，模拟