论文部分内容阅读
【摘要】介绍了基本粒子群算法的原理和流程,归纳了离散粒子群优化算法的研究现状和改进,包括改进的二值离散粒子群优化算法、离散量子粒子群优化算法、模糊离散粒子群优化算法,简要分析了粒子群算法在各个领域的应用。
【关键词】粒子群算法 群体智能 应用
【中图分类号】O411.1 【文献标识码】A 【文章编号】1009-8585(2011)06-00-02
1 基本粒子群算法介绍
1995年美国电气工程师Eberhart和社会心理学家Kennedy 基于鸟群觅食行为提出了粒子群优化算(partical swarm optimization,PSO),简称粒子群算法。
1.1 基本粒子群算法的原理
粒子群优化算法中,每个优化问题的潜在解都是搜索空间中的一只鸟,称之为“粒子”。每个粒子的位置代表被优化问题在搜索空间中的潜在解。例如,在一个D维的目标搜索空间中,每个粒子看成是空间内的一个点。设群体由m个粒子构成,m也被称为群体规模。所有的粒子都有一个由被优化的函数决定的适应值(Fitness value),每个粒子还有一个速度决定他们飞翔的方向和距离。粒子们追随当前的最优粒子在解空间中搜索。PSO初始化为一群随机粒子(随机解),然后通过迭代找到最优解。在每一次迭代中,粒子通过跟踪两个“极值”来更新自己。一个是粒子本身所找到的最优解,称为个体极值;另一个极值是整个种群目前找到的最优解,称为全局极值。
假设在一个D维的目标搜索空间中,有m个粒子组成一个群落,其中第i个粒子表示为一个D维的向量
即第i个粒子在D维的搜索空间中的位置。将Xi代入一个目标函数就可以计算出其适应值,根据其适应值的大小衡量的优劣。第i个粒子的“飞行”速度也是一个D维的向量,记为;第i个粒子迄今为止搜索到的最优位置称为个体极值,记为
整个粒子群迄今为止搜索到的最优位置为全局极值,记为
在每次迭代中,粒子根据以下式子更新速度和位置:
其中,是迭代数,r1和r2为[0,1]之间的随机数,这两个参数是用来保持群体的多样性。c1也c2为学习因子,也称加速因子,其使粒子具有自我总结和向群体中优秀个体学习的能力,从而向自己的历史最优点(个体极值)和群体内历史最优点(全局极值)靠近。
为了改善基本粒子群算法的收敛性能,Shi和Eberhart在1998年的IEEE国际进化计算学术会议上发表了题为“A modified particle swarm optimizer”的论文,引入了惯性权重,逐渐地大家都默认这个改进粒子群算法为标准的粒子群算法。
在标准的粒子群算法中,Shi和Eberhart添加了一个惯性权重到速度更新公式,而位置更新公式与基本粒子群算法的位置更新公式相同。即
1.2 基本粒子群算法的流程
1)初始化粒子群,即随机设定各粒子的初始位置x和初始速度v;
2)计算每个粒子的适应度值;
3)对每个粒子,比较它的适应度值和它经历的最好位置的适应度值;若更好,更新;
4)对每个粒子,比较它的适应度值和群体所经历的最好位置的适应度值;若更好,更新;
5)根据位置和速度的更新公式调整粒子的位置和速度;
6)若达到结束条件(足够好的位置或最大迭代次数),结束;否则,转步骤2。
2 离散离子群算法介绍
2.1 二进制离散粒子群优化算法
由于基本粒子群优化算法主要针对连续函数进行搜索运算,但许多实际工程问题都描述为离散的组合优化问题。传统粒子群优化算法局限于速度-位移更新算子,不能有效拓展到离散及组合优化领域。为此Kennedy和Eberhart于1997年提出了一种二进制离散粒子群优化算法。
二进制离散粒子群优化算法中,每个粒子的位置使用二进制编码,粒子的速度定义为“粒子位置改变的概率”。这里的概率是指每一位取一个状态或另一状态的可能性。这时,粒子群算法离散二进制模型的粒子的速度公式为:
vid = vid＋c1r1(pid－xid)＋c2r2(pgd－xid)
其中,pid和xid在整数集{0,1}内取值,vid的值表示为概率形式,限制在[0.0,1.0]内取值,r1、r2是0～1之间的随机数。
相应地,粒子位置的更新规则如下:
其中,是(0,1)区间上均匀分布的随机变量;,用来限制速度。
为了将粒子群算法离散化,文献[5]重新给出算法由当前的状态变量决定粒子将被判定为1或0的概率,即有:
Kennedy等提出使用Sigmoid函数求参数s。Sigmoid函数是神经网络中常用的一种模糊函数,其表达式如式(2.2)所示:
当取得时,阈值s的取值范围在[0.0025,0.9975]。修改后的离散粒子群优化算法与基本粒子群优化算法流程相类似,但粒子速度和位置的更新公式修改为:
其中,是[0,1]之间的随机数,算法中其他参数都和基本粒子群优化算法的参数相同。
2.2 改进的二值离散粒子群优化算法
基本的二进制离散粒子群算法同基本粒子群优化算法类似,都会由于粒子在运动过程中产生惰性而发生早熟收敛。为解决这一问题,杨红孺等于2005年基于基本二进制离散粒子群优化算法,提出了改进的二值离散粒子群优化算法。新算法利用基本粒子群算法中“粒子依赖自身经验及粒子群全体经验,同时克服自身飞行惰性”的思想,改进了粒子的更新运动公式,并将离散的二值由0、1改为—1、1。
2.3 离散量子粒子群优化算法
Yang S.Wang等人于2004年提出离散量子粒子群优化算法(quantum discrete PSO),是量子粒子群优化算法在离散问题上的改进算法。算法将量子粒子群算法中的粒子离散化,成为离散的粒子矢量。
2.4 模糊离散粒子群优化算法
为解决旅行商问题,陈震亦于2004年提出了一种新型的模糊自适应粒子群优化算法,庞巍等于2005年提出了模糊离散粒子群优化算法。算法使用模糊矩阵表示粒子位置和速度,迭代过程中加入归一化和解模糊化运算。
3 粒子群算法的应用介绍
粒子群优化算法(Particle Swarm Optimization,简称PSO)是一类基于群体智能(Swarm Intelligence)的随机优化算法。粒子群优化算法自从提出之后,由于其概念简单、实现方便,同时又有深刻的智能背景,立刻引起了优化及演化计算等领域的学者们的广泛关注,在短期内迅速得到了国际演化计算研究领域的认可,并且由于其在解决复杂的组合优化问题方面所具有的优越性能,因而特别适合工程应用与优化。粒子群算法已被广泛地应用于函数优化、优化问题求解、工程设计优化领域、电力系统领域、机器人控制领域、交通运输领域、通信领域、计算机领域、工业生产优化领域、生物医学领域和电磁学领域 。
a)在优化问题求解方面,粒子群算法已被有效应用于约束优化问题求解(最小最大化问题)、多目标优化问题求解、整数规划问题、旅行商问题求解等。
b)在工程设计与优化方面,粒子群算法被用于神经网络进化、模糊神经元网络过则的提取、电路设计、数字滤波器设计、布局优化、半导体器件综合、控制器参数优化、系统模式与状态估计等。
c)在电力系统领域。粒子群算法被用于实现电能优化、电压控制、提高电站可靠性以及电容其优化配置问题等。在机器人控制领域中,粒子群算法被用于机器人振动抑制轨迹规划以及移动机器人路径规划等。
d)在交通运输领域,粒子群算法被用于解决车辆路径问题以及交通控制问题。在通信领域,粒子群算法被用于解决路由选择及移动通信基站布置与优化问题等。
e)在计算机领域,粒子群算法被用于任务分配、模式识别、图像处理及数据挖掘等问题。
f)在工业生产领域,粒子群算法被应用于原料混合优化和计算机控制研磨优化等问题。
g)在生物医学领域,粒子群算法被用于生物医学图像配准或图像数据的几何排列、基因分类等问题。
h)在电磁学领域,粒子群算法被应用与求解非线性磁介质磁场、电磁场中的多层平面屏蔽罩优化、原声场旁瓣槽相控阵列综合问题等。
粒子群算法概念简单,具有很强的发现较好解的能力,并不容易陷入局部最优。PSO算法的应用十分广泛,有着较好的发展前景。目前为了进一步完善粒子群算法已经提出了很多改进方法,但由于实际问题的多样性和复杂性,这些PSO算法不具有通用性,或者参数的设置要求使用者具备较高的经验,否则难以达到理想的效果,因此还有问题值得做进一步的研究。而开拓PSO算法的新的应用领域也是一项很有意义的工作。
参考文献
[1] Eberhart R C,and Kennedy J.A new optimizer using particles swarm theory,Proc.SixthInternational Symposium on Micro Machine and Human Science,Nagoya,Japan,IEEE Service Center,Piscataway,NJ,1995:39-43.
[2] Kennedy J,Eberhart R C.Particle Swarm optimization.Proceedings of IEEE International Conference on Neural Networks Vol.IV,pp.1942-1948.IEEE service center,Piscataway,NJ,1995.
[3] Shi Y. Eberhart R C. A Modified Particle Swarm Optimizer.In IEEE International conference of、Evolutionary Computation. Anchorage.Alaska.1998:69-73.
[4] Kennedy J.Eberhart R.C.A discrete binary version of the particle swarm algorithm.IEEE Press,1997:4104-4109.
[5] 杨红孺,高洪元,庞伟正等.基于离散粒子群优化算法的多用户检测器.哈尔滨工业大学学报.2005.37(9):1303-1306.
[6] Yang S.Wang M.Jiao L.A quantum particle swarm optimization.Proceeding of the 2004 IEEE Congress on Evolutionary Computation.2004.1:320-324.
[7] 陈震亦.粒子群优化算法研究及其在TSP问题中的应用[D].硕士学位论文.福州大学.2004.
[8] 庞巍,王康平,周春光等.模糊离散粒子群优化算法求解旅行商问题.小型微型计算机系统.2005.26(8):1331-1334.
[9] 纪震,廖惠连,吴青华.粒子群算法及应用[M].北京科学出版社.2009.
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文
【关键词】粒子群算法 群体智能 应用
【中图分类号】O411.1 【文献标识码】A 【文章编号】1009-8585(2011)06-00-02
1 基本粒子群算法介绍
1995年美国电气工程师Eberhart和社会心理学家Kennedy 基于鸟群觅食行为提出了粒子群优化算(partical swarm optimization,PSO),简称粒子群算法。
1.1 基本粒子群算法的原理
粒子群优化算法中,每个优化问题的潜在解都是搜索空间中的一只鸟,称之为“粒子”。每个粒子的位置代表被优化问题在搜索空间中的潜在解。例如,在一个D维的目标搜索空间中,每个粒子看成是空间内的一个点。设群体由m个粒子构成,m也被称为群体规模。所有的粒子都有一个由被优化的函数决定的适应值(Fitness value),每个粒子还有一个速度决定他们飞翔的方向和距离。粒子们追随当前的最优粒子在解空间中搜索。PSO初始化为一群随机粒子(随机解),然后通过迭代找到最优解。在每一次迭代中,粒子通过跟踪两个“极值”来更新自己。一个是粒子本身所找到的最优解,称为个体极值;另一个极值是整个种群目前找到的最优解,称为全局极值。
假设在一个D维的目标搜索空间中,有m个粒子组成一个群落,其中第i个粒子表示为一个D维的向量
即第i个粒子在D维的搜索空间中的位置。将Xi代入一个目标函数就可以计算出其适应值,根据其适应值的大小衡量的优劣。第i个粒子的“飞行”速度也是一个D维的向量,记为;第i个粒子迄今为止搜索到的最优位置称为个体极值,记为
整个粒子群迄今为止搜索到的最优位置为全局极值,记为
在每次迭代中,粒子根据以下式子更新速度和位置:
其中,是迭代数,r1和r2为[0,1]之间的随机数,这两个参数是用来保持群体的多样性。c1也c2为学习因子,也称加速因子,其使粒子具有自我总结和向群体中优秀个体学习的能力,从而向自己的历史最优点(个体极值)和群体内历史最优点(全局极值)靠近。
为了改善基本粒子群算法的收敛性能,Shi和Eberhart在1998年的IEEE国际进化计算学术会议上发表了题为“A modified particle swarm optimizer”的论文,引入了惯性权重,逐渐地大家都默认这个改进粒子群算法为标准的粒子群算法。
在标准的粒子群算法中,Shi和Eberhart添加了一个惯性权重到速度更新公式,而位置更新公式与基本粒子群算法的位置更新公式相同。即
1.2 基本粒子群算法的流程
1)初始化粒子群,即随机设定各粒子的初始位置x和初始速度v;
2)计算每个粒子的适应度值;
3)对每个粒子,比较它的适应度值和它经历的最好位置的适应度值;若更好,更新;
4)对每个粒子,比较它的适应度值和群体所经历的最好位置的适应度值;若更好,更新;
5)根据位置和速度的更新公式调整粒子的位置和速度;
6)若达到结束条件(足够好的位置或最大迭代次数),结束;否则,转步骤2。
2 离散离子群算法介绍
2.1 二进制离散粒子群优化算法
由于基本粒子群优化算法主要针对连续函数进行搜索运算,但许多实际工程问题都描述为离散的组合优化问题。传统粒子群优化算法局限于速度-位移更新算子,不能有效拓展到离散及组合优化领域。为此Kennedy和Eberhart于1997年提出了一种二进制离散粒子群优化算法。
二进制离散粒子群优化算法中,每个粒子的位置使用二进制编码,粒子的速度定义为“粒子位置改变的概率”。这里的概率是指每一位取一个状态或另一状态的可能性。这时,粒子群算法离散二进制模型的粒子的速度公式为:
vid = vid＋c1r1(pid－xid)＋c2r2(pgd－xid)
其中,pid和xid在整数集{0,1}内取值,vid的值表示为概率形式,限制在[0.0,1.0]内取值,r1、r2是0～1之间的随机数。
相应地,粒子位置的更新规则如下:
其中,是(0,1)区间上均匀分布的随机变量;,用来限制速度。
为了将粒子群算法离散化,文献[5]重新给出算法由当前的状态变量决定粒子将被判定为1或0的概率,即有:
Kennedy等提出使用Sigmoid函数求参数s。Sigmoid函数是神经网络中常用的一种模糊函数,其表达式如式(2.2)所示:
当取得时,阈值s的取值范围在[0.0025,0.9975]。修改后的离散粒子群优化算法与基本粒子群优化算法流程相类似,但粒子速度和位置的更新公式修改为:
其中,是[0,1]之间的随机数,算法中其他参数都和基本粒子群优化算法的参数相同。
2.2 改进的二值离散粒子群优化算法
基本的二进制离散粒子群算法同基本粒子群优化算法类似,都会由于粒子在运动过程中产生惰性而发生早熟收敛。为解决这一问题,杨红孺等于2005年基于基本二进制离散粒子群优化算法,提出了改进的二值离散粒子群优化算法。新算法利用基本粒子群算法中“粒子依赖自身经验及粒子群全体经验,同时克服自身飞行惰性”的思想,改进了粒子的更新运动公式,并将离散的二值由0、1改为—1、1。
2.3 离散量子粒子群优化算法
Yang S.Wang等人于2004年提出离散量子粒子群优化算法(quantum discrete PSO),是量子粒子群优化算法在离散问题上的改进算法。算法将量子粒子群算法中的粒子离散化,成为离散的粒子矢量。
2.4 模糊离散粒子群优化算法
为解决旅行商问题,陈震亦于2004年提出了一种新型的模糊自适应粒子群优化算法,庞巍等于2005年提出了模糊离散粒子群优化算法。算法使用模糊矩阵表示粒子位置和速度,迭代过程中加入归一化和解模糊化运算。
3 粒子群算法的应用介绍
粒子群优化算法(Particle Swarm Optimization,简称PSO)是一类基于群体智能(Swarm Intelligence)的随机优化算法。粒子群优化算法自从提出之后,由于其概念简单、实现方便,同时又有深刻的智能背景,立刻引起了优化及演化计算等领域的学者们的广泛关注,在短期内迅速得到了国际演化计算研究领域的认可,并且由于其在解决复杂的组合优化问题方面所具有的优越性能,因而特别适合工程应用与优化。粒子群算法已被广泛地应用于函数优化、优化问题求解、工程设计优化领域、电力系统领域、机器人控制领域、交通运输领域、通信领域、计算机领域、工业生产优化领域、生物医学领域和电磁学领域 。
a)在优化问题求解方面,粒子群算法已被有效应用于约束优化问题求解(最小最大化问题)、多目标优化问题求解、整数规划问题、旅行商问题求解等。
b)在工程设计与优化方面,粒子群算法被用于神经网络进化、模糊神经元网络过则的提取、电路设计、数字滤波器设计、布局优化、半导体器件综合、控制器参数优化、系统模式与状态估计等。
c)在电力系统领域。粒子群算法被用于实现电能优化、电压控制、提高电站可靠性以及电容其优化配置问题等。在机器人控制领域中,粒子群算法被用于机器人振动抑制轨迹规划以及移动机器人路径规划等。
d)在交通运输领域,粒子群算法被用于解决车辆路径问题以及交通控制问题。在通信领域,粒子群算法被用于解决路由选择及移动通信基站布置与优化问题等。
e)在计算机领域,粒子群算法被用于任务分配、模式识别、图像处理及数据挖掘等问题。
f)在工业生产领域,粒子群算法被应用于原料混合优化和计算机控制研磨优化等问题。
g)在生物医学领域,粒子群算法被用于生物医学图像配准或图像数据的几何排列、基因分类等问题。
h)在电磁学领域,粒子群算法被应用与求解非线性磁介质磁场、电磁场中的多层平面屏蔽罩优化、原声场旁瓣槽相控阵列综合问题等。
粒子群算法概念简单,具有很强的发现较好解的能力,并不容易陷入局部最优。PSO算法的应用十分广泛,有着较好的发展前景。目前为了进一步完善粒子群算法已经提出了很多改进方法,但由于实际问题的多样性和复杂性,这些PSO算法不具有通用性,或者参数的设置要求使用者具备较高的经验,否则难以达到理想的效果,因此还有问题值得做进一步的研究。而开拓PSO算法的新的应用领域也是一项很有意义的工作。
参考文献
[1] Eberhart R C,and Kennedy J.A new optimizer using particles swarm theory,Proc.SixthInternational Symposium on Micro Machine and Human Science,Nagoya,Japan,IEEE Service Center,Piscataway,NJ,1995:39-43.
[2] Kennedy J,Eberhart R C.Particle Swarm optimization.Proceedings of IEEE International Conference on Neural Networks Vol.IV,pp.1942-1948.IEEE service center,Piscataway,NJ,1995.
[3] Shi Y. Eberhart R C. A Modified Particle Swarm Optimizer.In IEEE International conference of、Evolutionary Computation. Anchorage.Alaska.1998:69-73.
[4] Kennedy J.Eberhart R.C.A discrete binary version of the particle swarm algorithm.IEEE Press,1997:4104-4109.
[5] 杨红孺,高洪元,庞伟正等.基于离散粒子群优化算法的多用户检测器.哈尔滨工业大学学报.2005.37(9):1303-1306.
[6] Yang S.Wang M.Jiao L.A quantum particle swarm optimization.Proceeding of the 2004 IEEE Congress on Evolutionary Computation.2004.1:320-324.
[7] 陈震亦.粒子群优化算法研究及其在TSP问题中的应用[D].硕士学位论文.福州大学.2004.
[8] 庞巍,王康平,周春光等.模糊离散粒子群优化算法求解旅行商问题.小型微型计算机系统.2005.26(8):1331-1334.
[9] 纪震,廖惠连,吴青华.粒子群算法及应用[M].北京科学出版社.2009.
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文