粒子群优化算法(PSO)介绍

1. 引言

粒子群优化算法(PSO)是一种进化计算技术(evolutionary computation)，有Eberhart博士和kennedy博士发明。源于对鸟群捕食的行为研究

PSO同遗传算法类似，是一种基于叠代的优化工具。系统初始化为一组随机解，通过叠代搜寻最优值。但是并没有遗传算法用的交叉(crossover)以及变异(mutation)。而是粒子在解空间追随最优的粒子进行搜索。详细的步骤以后的章节介绍

同遗传算法比较，PSO的优势在于简单容易实现并且没有许多参数需要调整。目前已广泛应用于函数优化，神经网络训练，模糊系统控制以及其他遗传算法的应用领域

2. 背景: 人工生命

"人工生命"是来研究具有某些生命基本特征的人工系统. 人工生命包括两方面的内容

1. 研究如何利用计算技术研究生物现象
2. 研究如何利用生物技术研究计算问题

我们现在关注的是第二部分的内容. 现在已经有很多源于生物现象的计算技巧. 例如, 人工神经网络是简化的大脑模型. 遗传算法是模拟基因进化过程的.

现在我们讨论另一种生物系统- 社会系统. 更确切的是, 在由简单个体组成的群落与环境以及个体之间的互动行为. 也可称做"群智能"(swarm intelligence). 这些模拟系统利用局部信息从而可能产生不可预测的群体行为

例如floys 和 boids, 他们都用来模拟鱼群和鸟群的运动规律, 主要用于计算机视觉和计算机辅助设计.

在计算智能(computational intelligence)领域有两种基于群智能的算法. 蚁群算法 (ant colony optimization)和粒子群算法(particle swarm optimization). 前者是对蚂蚁群落食物采集过程的模拟. 已经成功运用在很多离散优化问题上.

粒子群优化算法(PSO) 也是起源对简单社会系统的模拟. 最初设想是模拟鸟群觅食的过程. 但后来发现PSO是一种很好的优化工具.

3. 算法介绍

如前所述，PSO模拟鸟群的捕食行为。设想这样一个场景：一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的就是搜寻目前离食物最近的鸟的周围区域。

PSO 从这种模型中得到启示并用于解决优化问题。PSO中，每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”。所有的例子都有一个由被优化的函数决定的适应值(fitness value)，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索

PSO 初始化为一群随机粒子(随机解)。然后通过叠代找到最优解。在每一次叠代中，粒子通过跟踪两个"极值"来更新自己。第一个就是粒子本身所找到的最优解。这个解叫做个体极值pBest. 另一个极值是整个种群目前找到的最优解。这个极值是全局极值gBest。另外也可以不用整个种群而只是用其中一部分最为粒子的邻居，那么在所有邻居中的极值就是局部极值。

在找到这两个最优值时, 粒子根据如下的公式来更新自己的速度和新的位置

v[] = v[] + c1 * rand() * (pbest[] - present[]) + c2 * rand() * (gbest[] - present[]) (a)
present[] = persent[] + v[] (b)

v[] 是粒子的速度, persent[] 是当前粒子的位置. pbest[] and gbest[] 如前定义 rand () 是介于（0， 1）之间的随机数. c1, c2 是学习因子. 通常 c1 = c2 = 2.

程序的伪代码如下

For each particle
____Initialize particle
END

Do
____For each particle
________Calculate fitness value
________If the fitness value is better than the best fitness value (pBest) in history
____________set current value as the new pBest
____End

____Choose the particle with the best fitness value of all the particles as the gBest
____For each particle
________Calculate particle velocity according equation (a)
________Update particle position according equation (b)
____End
While maximum iterations or minimum error criteria is not attained

在每一维粒子的速度都会被限制在一个最大速度Vmax，如果某一维更新后的速度超过用户设定的Vmax，那么这一维的速度就被限定为Vmax

4. 遗传算法和 PSO 的比较

大多数演化计算技术都是用同样的过程
1. 种群随机初始化
2. 对种群内的每一个个体计算适应值(fitness value).适应值与最优解的距离直接有关
3. 种群根据适应值进行复制
4. 如果终止条件满足的话，就停止，否则转步骤2

从以上步骤，我们可以看到PSO和GA有很多共同之处。两者都随机初始化种群，而且都使用适应值来评价系统，而且都根据适应值来进行一定的随机搜索。两个系统都不是保证一定找到最优解

但是，PSO 没有遗传操作如交叉(crossover)和变异(mutation). 而是根据自己的速度来决定搜索。粒子还有一个重要的特点，就是有记忆。

与遗传算法比较, PSO 的信息共享机制是很不同的. 在遗传算法中，染色体(chromosomes) 互相共享信息，所以整个种群的移动是比较均匀的向最优区域移动. 在PSO中, 只有gBest (or lBest) 给出信息给其他的粒子， 这是单向的信息流动. 整个搜索更新过程是跟随当前最优解的过程. 与遗传算法比较, 在大多数的情况下，所有的粒子可能更快的收敛于最优解

5. 人工神经网络 和 PSO

人工神经网络(ANN)是模拟大脑分析过程的简单数学模型，反向转播算法是最流行的神经网络训练算法。进来也有很多研究开始利用演化计算(evolutionary computation)技术来研究人工神经网络的各个方面。

演化计算可以用来研究神经网络的三个方面：网络连接权重，网络结构(网络拓扑结构，传递函数)，网络学习算法。

不过大多数这方面的工作都集中在网络连接权重，和网络拓扑结构上。在GA中，网络权重和/或拓扑结构一般编码为染色体(Chromosome)，适应函数 (fitness function)的选择一般根据研究目的确定。例如在分类问题中，错误分类的比率可以用来作为适应值

演化计算的优势在于可以处理一些传统方法不能处理的例子例如不可导的节点传递函数或者没有梯度信息存在。但是缺点在于：在某些问题上性能并不是特别好。2. 网络权重的编码而且遗传算子的选择有时比较麻烦

最近已经有一些利用PSO来代替反向传播算法来训练神经网络的论文。研究表明PSO 是一种很有潜力的神经网络算法。PSO速度比较快而且可以得到比较好的结果。而且还没有遗传算法碰到的问题

这里用一个简单的例子说明PSO训练神经网络的过程。这个例子使用分类问题的基准函数(Benchmark function)IRIS数据集。 (Iris 是一种鸢尾属植物) 在数据记录中，每组数据包含Iris花的四种属性：萼片长度，萼片宽度，花瓣长度，和花瓣宽度，三种不同的花各有50组数据. 这样总共有150组数据或模式。

我们用3层的神经网络来做分类。现在有四个输入和三个输出。所以神经网络的输入层有4个节点，输出层有3个节点我们也可以动态调节隐含层节点的数目，不过这里我们假定隐含层有6个节点。我们也可以训练神经网络中其他的参数。不过这里我们只是来确定网络权重。粒子就表示神经网络的一组权重，应该是4*6+6*3=42个参数。权重的范围设定为[-100，100] (这只是一个例子，在实际情况中可能需要试验调整).在完成编码以后，我们需要确定适应函数。对于分类问题，我们把所有的数据送入神经网络，网络的权重有粒子的参数决定。然后记录所有的错误分类的数目作为那个粒子的适应值。现在我们就利用PSO来训练神经网络来获得尽可能低的错误分类数目。PSO本身并没有很多的参数需要调整。所以在实验中只需要调整隐含层的节点数目和权重的范围以取得较好的分类效果。

6. PSO的参数设置

从上面的例子我们可以看到应用PSO解决优化问题的过程中有两个重要的步骤: 问题解的编码和适应度函数
PSO 的一个优势就是采用实数编码, 不需要像遗传算法一样是二进制编码(或者采用针对实数的遗传操作.例如对于问题 f(x) = x1^2 + x2^2+ x3^2 求解, 粒子可以直接编码为 (x1, x2, x3), 而适应度函数就是f(x). 接着我们就可以利用前面的过程去寻优.这个寻优过程是一个叠代过程, 中止条件一般为设置为达到最大循环数或者最小错误

PSO中并没有许多需要调节的参数,下面列出了这些参数以及经验设置

粒子数: 一般取 20 – 40. 其实对于大部分的问题10个粒子已经足够可以取得好的结果, 不过对于比较难的问题或者特定类别的问题, 粒子数可以取到100 或 200

粒子的长度: 这是由优化问题决定, 就是问题解的长度

粒子的范围: 由优化问题决定,每一维可是设定不同的范围

Vmax: 最大速度,决定粒子在一个循环中最大的移动距离,通常设定为粒子的范围宽度,例如上面的例子里,粒子 (x1, x2, x3) x1 属于 [-10, 10], 那么 Vmax 的大小就是 20

学习因子: c1 和 c2 通常等于 2. 不过在文献中也有其他的取值. 但是一般 c1 等于 c2 并且范围在0和4之间

中止条件: 最大循环数以及最小错误要求. 例如, 在上面的神经网络训练例子中, 最小错误可以设定为1个错误分类, 最大循环设定为2000, 这个中止条件由具体的问题确定.

全局PSO和局部PSO: 我们介绍了两种版本的粒子群优化算法: 全局版和局部版. 前者速度快不过有时会陷入局部最优. 后者收敛速度慢一点不过很难陷入局部最优. 在实际应用中, 可以先用全局PSO找到大致的结果,再有局部PSO进行搜索.

另外的一个参数是惯性权重, 由Shi 和Eberhart提出, 有兴趣的可以参考他们1998年的论文(题目: A modified particle swarm optimizer)

7.PSO网上资源

粒子群优化算法的研究还处于初期阶段, 还有很多未知的领域需要研究, 例如关于粒子群理论的数学证明
不过网上已经由了很多的关于粒子群的资源, 下面列出一些:

http://www.particleswarm.net 关于粒子群理论的各方面资源

http://icdweb.cc.purdue.edu/~hux/PSO.shtml 有一份比较全的文献列表以及网上论文

http://www.researchindex.com/ 可以搜索到关于PSO的很多论文及文献

参考文献

http://www.engr.iupui.edu/~eberhart/
http://users.erols.com/cathyk/jimk.html
http://www.alife.org
http://www.aridolan.com
http://www.red3d.com/cwr/boids/
http://iridia.ulb.ac.be/~mdorigo/ACO/ACO.html
http://www.engr.iupui.edu/~shi/Coference/psopap4.html
Kennedy, J. and Eberhart, R. C. Particle swarm optimization. Proc. IEEE int^l conf. on neural networks Vol. IV, pp. 1942-1948. IEEE service center, Piscataway, NJ, 1995.
Eberhart, R. C. and Kennedy, J. A new optimizer using particle swarm theory. Proceedings of the sixth international symposium on micro machine and human science pp. 39-43. IEEE service center, Piscataway, NJ, Nagoya, Japan, 1995.
Eberhart, R. C. and Shi, Y. Particle swarm optimization: developments, applications and resources. Proc. congress on evolutionary computation 2001 IEEE service center, Piscataway, NJ., Seoul, Korea., 2001.
Eberhart, R. C. and Shi, Y. Evolving artificial neural networks. Proc. 1998 Int^l Conf. on neural networks and brain pp. PL5-PL13. Beijing, P. R. China, 1998.
Eberhart, R. C. and Shi, Y. Comparison between genetic algorithms and particle swarm optimization. Evolutionary programming vii: proc. 7th ann. conf. on evolutionary conf., Springer-Verlag, Berlin, San Diego, CA., 1998.
Shi, Y. and Eberhart, R. C. Parameter selection in particle swarm optimization. Evolutionary Programming VII: Proc. EP 98 pp. 591-600. Springer-Verlag, New York, 1998.
Shi, Y. and Eberhart, R. C. A modified particle swarm optimizer. Proceedings of the IEEE International Conference on Evolutionary Computation pp. 69-73. IEEE Press, Piscataway, NJ, 1998

racer

三星会员

发表总数：64 发表於 - 2002/04/18 12:50:19
--------------------------------------------------------------------------------
1. Introduction

Particle swarm optimization (PSO) is an evolutionary computation technique developed by Dr. Eberhart (http://www.engr.iupui.edu/~eberhart/) and Dr. Kennedy (http://users.erols.com/cathyk/jimk.html) in 1995, inspired by social behavior of bird flocking or fish schooling.

Similar to genetic algorithms (GA), PSO is a population based optimization tool. The system is initialized with a population of random solutions and searches for optima by updating generations. However, unlike GA, PSO has no evolution operators such as crossover and mutation. In PSO, the potential solutions, called particles, are "flown" through the problem space by following the current optimum particles. The detailed information will be given in following sections.

Compared to GA, the advantages of PSO are that PSO is easy to implement and there are few parameters to adjust. PSO has been successfully applied in many areas: function optimization, artificial neural network training, fuzzy system control, and other areas where GA can be applied.

The remaining of the report includes six sections:

Background: artificial life.
The Algorithm
Comparisons between Genetic algorithm and PSO
Artificial neural network and PSO
PSO parameter control
Online resources of PSO

2.Background: Artificial life

The term "Artificial Life" (ALife) is used to describe research into human-made systems that possess some of the essential properties of life. ALife includes two-folded research topic: (http://www.alife.org)

1. ALife studies how computational techniques can help when studying biological phenomena
2. ALife studies how biological techniques can help out with computational problems

The focus of this report is on the second topic. Actually, there are already lots of computational techniques inspired by biological systems. For example, artificial neural network is a simplified model of human brain; genetic algorithm is inspired by the human evolution.

Here we discuss another type of biological system - social system, more specifically, the collective behaviors of simple individuals interacting with their environment and each other. Someone called it as swarm intelligence. All of the simulations utilized local processes, such as those modeled by cellular automata, and might underlie the unpredictable group dynamics of social behavior.

Some popular examples are floys (http://www.aridolan.com) and boids (http://www.red3d.com/cwr/boids/) both of the simulations were created to interpret the movement of organisms in a bird flock or fish school. These simulations are normally used in computer animation or computer aided design.

There are two popular swarm inspired methods in computational intelligence areas: Ant colony optimization (ACO) and particle swarm optimization (PSO). ACO was inspired by the behaviors of ants and has many successful applications in discrete optimization problems. (http://iridia.ulb.ac.be/~mdorigo/ACO/ACO.html)

The particle swarm concept originated as a simulation of simplified social system. The original intent was to graphically simulate the choreography of bird of a bird block or fish school. However, it was found that particle swarm model can be used as an optimizer.
(http://www.engr.iupui.edu/~shi/Coference/psopap4.html)

3. The algorithm

As stated before, PSO simulates the behaviors of bird flocking. Suppose the following scenario: a group of birds are randomly searching food in an area. There is only one piece of food in the area being searched. All the birds do not know where the food is. But they know how far the food is during each search iteration. So what’s the best strategy to find the food? The effective one is to follow the bird which is nearest to the food.

PSO learned from the scenario and used it to solve the optimization problems. In PSO, each single solution is a “bird” in the search space. We call it “particle”. All of particles have fitness values which are evaluated by the fitness function to be optimized, and have velocities which direct the flying of the particles. The particles are "flown" through the problem space by following the current optimum particles.

PSO is initialized with a group of random particles (solutions) and then searches for optima by updating generations. In every iteration, each particle is updated by following two “best” values. The first one is the best solution (fitness) it has achieved so far. (The fitness value is also stored.) This value is called pbest. Another "best" value that is tracked by the particle swarm optimizer is the best value, obtained so far by any particle in the population. This best value is a global best and called gbest. When a particle takes part of the population as its topological neighbors, the best value is a local best and is called lbest.

After finding the two best values, the particle updates its velocity and positions with following formulas.

v[] = v[] + c1 * rand() * (pbest[] - present[]) + c2 * rand() * (gbest[] - present[]) (a)
present[] = persent[] + v[] (b)

v[] is the particle velocity, persent[] is the current particle (solution). pbest[] and gbest[] are defined as stated before. rand () is a random number between (0,1). c1, c2 are learning factors. usually c1 = c2 = 2.

The pseudo code of the procedure is as follows

For each particle
____Initialize particle
END

Do
____For each particle
________Calculate fitness value
________If the fitness value is better than the best fitness value (pBest) in history
____________set current value as the new pBest
____End

____Choose the particle with the best fitness value of all the particles as the gBest
____For each particle
________Calculate particle velocity according equation (a)
________Update particle position according equation (b)
____End
While maximum iterations or minimum error criteria is not attained

Particles’ velocities on each dimension are clamped to a maximum velocity Vmax. If the sum of accelerations would cause the velocity on that dimension to exceed Vmax, which is a parameter specified by the user. Then the velocity on that dimension is limited to Vmax.

4. Comparisons between Genetic Algorithm and PSO

Most of evolutionary techniques have the following procedure:
1. Random generation of an initial population
2. Reckoning of a fitness value for each subject. It will directly depend on the distance to the optimum.
3. Reproduction of the population based on fitness values.
4. If requirements are met, then stop. Otherwise go back to 2.

From the procedure, we can learn that PSO shares many common points with GA. Both algorithms start with a group of a randomly generated population, both have fitness values to evaluate the population. Both update the population and search for the optimium with random techniques. Both systems do not guarantee success.

However, PSO does not have genetic operators like crossover and mutation. Particles update themselves with the internal velocity. They also have memory, which is important to the algorithm.

Compared with genetic algorithms (GAs), the information sharing mechanism in PSO is significantly different. In GAs, chromosomes share information with each other. So the whole population moves like a one group towards an optimal area. In PSO, only gBest (or lBest) gives out the information to others. It is a one -way information sharing mechanism. The evolution only looks for the best solution. Compared with GA, all the particles tend to converge to the best solution quickly even in the local version in most cases.

5. Artificial neural network and PSO

An artificial neural network (ANN) is an analysis paradigm that is a simple model of the brain and the back-propagation algorithm is the one of the most popular method to train the artificial neural network. Recently there have been significant research efforts to apply evolutionary computation (EC) techniques for the purposes of evolving one or more aspects of artificial neural networks.

Evolutionary computation methodologies have been applied to three main attributes of neural networks: network connection weights, network architecture (network topology, transfer function), and network learning algorithms.

Most of the work involving the evolution of ANN has focused on the network weights and topological structure. Usually the weights and/or topological structure are encoded as a chromosome in GA. The selection of fitness function depends on the research goals. For a classification problem, the rate of mis-classified patterns can be viewed as the fitness value.

The advantage of the EC is that EC can be used in cases with non-differentiable PE transfer functions and no gradient information available. The disadvantages are 1. The performance is not competitive in some problems. 2. representation of the weights is difficult and the genetic operators have to be carefully selected or developed.

There are several papers reported using PSO to replace the back-propagation learning algorithm in ANN in the past several years. It showed PSO is a promising method to train ANN. It is faster and gets better results in most cases. It also avoids some of the problems GA met.

Here we show a simple example of evolving ANN with PSO. The problem is a benchmark function of classification problem: iris data set. Measurements of four attributes of iris flowers are provided in each data set record: sepal length, sepal width, petal length, and petal width. Fifty sets of measurements are present for each of three varieties of iris flowers, for a total of 150 records, or patterns.

A 3-layer ANN is used to do the classification. There are 4 inputs and 3 outputs. So the input layer has 4 neurons and the output layer has 3 neurons. One can evolve the number of hidden neurons. However, for demonstration only, here we suppose the hidden layer has 6 neurons. We can evolve other parameters in the feed-forward network. Here we only evolve the network weights. So the particle will be a group of weights, there are 4*6+6*3 = 42 weights, so the particle consists of 42 real numbers. The range of weights can be set to [-100, 100] (this is just a example, in real cases, one might try different ranges). After encoding the particles, we need to determine the fitness function. For the classification problem, we feed all the patterns to the network whose weights is determined by the particle, get the outputs and compare it the standard outputs. Then we record the number of misclassified patterns as the fitness value of that particle. Now we can apply PSO to train the ANN to get lower number of misclassified patterns as possible. There are not many parameters in PSO need to be adjusted. We only need to adjust the number of hidden layers and the range of the weights to get better results in different trials.

6. PSO parameter control

From the above case, we can learn that there are two key steps when applying PSO to optimization problems: the representation of the solution and the fitness function. One of the advantages of PSO is that PSO take real numbers as particles. It is not like GA, which needs to change to binary encoding, or special genetic operators have to be used. For example, we try to find the solution for f(x) = x1^2 + x2^2+x3^2, the particle can be set as (x1, x2, x3), and fitness function is f(x). Then we can use the standard procedure to find the optimum. The searching is a repeat process, and the stop criteria are that the maximum iteration number is reached or the minimum error condition is satisfied.

There are not many parameter need to be tuned in PSO. Here is a list of the parameters and their typical values.

The number of particles: the typical range is 20 – 40. Actually for most of the problems 10 particles is large enough to get good results. For some difficult or special problems, one can try 100 or 200 particles as well.

Dimension of particles: It is determined by the problem to be optimized,

Range of particles: It is also determined by the problem to be optimized, you can specify different ranges for different dimension of particles.

Vmax: it determines the maximum change one particle can take during one iteration. Usually we set the range of the particle as the Vmax for example, the particle (x1, x2, x3)
X1 belongs [-10, 10], then Vmax = 20

Learning factors: c1 and c2 usually equal to 2. However, other settings were also used in different papers. But usually c1 equals to c2 and ranges from [0, 4]

The stop condition: the maximum number of iterations the PSO execute and the minimum error requirement. for example, for ANN training in previous section, we can set the minimum error requirement is one mis-classified pattern. the maximum number of iterations is set to 2000. this stop condition depends on the problem to be optimized.

Global version vs. local version: we introduced two versions of PSO. global and local version. global version is faster but might converge to local optimum for some problems. local version is a little bit slower but not easy to be trapped into local optimim. One can use global version to get quick result and use local version to refine the search.

Another factor is inertia weight, which is introduced by Shi and Eberhart. If you are interested in it, please refer to their paper in 1998. (Title: A modified particle swarm optimizer)

7. Online Resources of PSO

The development of PSO is still ongoing. And there are still many unknown areas in PSO research such as the mathematical validation of particle swarm theory.

One can find much information from the internet. Following are some information you can get online:

http://www.particleswarm.net lots of information about Particle Swarms and, particularly, Particle Swarm Optimization. lots of Particle Swarm Links.

http://icdweb.cc.purdue.edu/~hux/PSO.shtml lists an updated bibliography of particle swarm optimization and some online paper links

http://www.researchindex.com/ you can search particle swarm related papers and references.

References:

http://www.engr.iupui.edu/~eberhart/
http://users.erols.com/cathyk/jimk.html
http://www.alife.org
http://www.aridolan.com
http://www.red3d.com/cwr/boids/
http://iridia.ulb.ac.be/~mdorigo/ACO/ACO.html
http://www.engr.iupui.edu/~shi/Coference/psopap4.html
Kennedy, J. and Eberhart, R. C. Particle swarm optimization. Proc. IEEE int^l conf. on neural networks Vol. IV, pp. 1942-1948. IEEE service center, Piscataway, NJ, 1995.
Eberhart, R. C. and Kennedy, J. A new optimizer using particle swarm theory. Proceedings of the sixth international symposium on micro machine and human science pp. 39-43. IEEE service center, Piscataway, NJ, Nagoya, Japan, 1995.
Eberhart, R. C. and Shi, Y. Particle swarm optimization: developments, applications and resources. Proc. congress on evolutionary computation 2001 IEEE service center, Piscataway, NJ., Seoul, Korea., 2001.
Eberhart, R. C. and Shi, Y. Evolving artificial neural networks. Proc. 1998 Int^l Conf. on neural networks and brain pp. PL5-PL13. Beijing, P. R. China, 1998.
Eberhart, R. C. and Shi, Y. Comparison between genetic algorithms and particle swarm optimization. Evolutionary programming vii: proc. 7th ann. conf. on evolutionary conf., Springer-Verlag, Berlin, San Diego, CA., 1998.
Shi, Y. and Eberhart, R. C. Parameter selection in particle swarm optimization. Evolutionary Programming VII: Proc. EP 98 pp. 591-600. Springer-Verlag, New York, 1998.
Shi, Y. and Eberhart, R. C. A modified particle swarm optimizer. Proceedings of the IEEE International Conference on Evolutionary Computation pp. 69-73. IEEE Press, Piscataway, NJ, 1998

-----
茶能醉人不需酒，书能香我何必花
2003-6-17 18:45:31 　转贴　打包

Artificial Neural Networks Forum