粒子群优化算法(PSO)

　

粒子群

 

%% 最近写的粒子群的论文，再重新巩固一下 推荐一个优化算法代码网址：http://www.Hvass-Labs.org/

1   研究背景

粒子群算法的发展过程。粒子群优化算法（Partical Swarm Optimization PSO），粒子群中的每一个粒子都代表一个问题的可能解，通过粒子个体的简单行为，群体内的信息交互实现问题求解的智能性。由于PSO操作简单、收敛速度快，因此在函数优化、 图像处理、大地测量等众多领域都得到了广泛的应用。 随着应用范围的扩大，PSO算法存在早熟收敛、维数灾难、易于陷入局部极值等问题需要解决，主要有以下几种发展方向。

（1）调整PSO的参数来平衡算法的全局探测和局部开采能力。如Shi和Eberhart对PSO算法的速度项引入了惯性权重，并依据迭代进程及粒子飞行情况对惯性权重进行线性（或非线性）的动态调整，以平衡搜索的全局性和收敛速度。2009年张玮等在对标准粒子群算法位置期望及方差进行稳定性分析的基础上，研究了加速因子对位置期望及方差的影响，得出了一组较好的加速因子取值。

（2）设计不同类型的拓扑结构，改变粒子学习模式，从而提高种群的多样性，Kennedy等人研究了不同的拓扑结构对SPSO性能的影响。针对SPSO存在易早熟收敛，寻优精度不高的缺点，于2003年提出了一种更为明晰的粒子群算法的形式：骨干粒子群算法（Bare Bones PSO，BBPSO）。

（3）将PSO和其他优化算法（或策略）相结合，形成混合PSO算法。如曾毅等将模式搜索算法嵌入到PSO算法中，实现了模式搜索算法的局部搜索能力与PSO算法的全局寻优能力的优势互补。

（4）采用小生境技术。小生境是模拟生态平衡的一种仿生技术，适用于多峰函数和多目标函数的优化问题。例如，在PSO算法中，通过构造小生境拓扑，将种群分成若干个子种群，动态地形成相对独立的搜索空间，实现对多个极值区域的同步搜索，从而可以避免算法在求解多峰函数优化问题时出现早熟收敛现象。 Parsopoulos提出一种基于“分而治之”思想的多种群PSO算法，其核心思想是将高维的目标函数分解成多个低维函数，然后每个低维的子函数由一个子粒子群进行优化，该算法对高维问题的求解提供了一个较好的思路。

不同的发展方向代表不同的应用领域，有的需要不断进行全局探测，有的需要提高寻优精度，有的需要全局搜索和局部搜索相互之间的平衡，还有的需要对高维问题进行求解。这些方向没有谁好谁坏的可比性，只有针对不同领域的不同问题求解时选择最合适的方法的区别。

2   相关模型和思想

粒子群算法（ Particle Swarm Optimization, PSO）最早是由Eberhart和Kennedy于1995年提出，它的基本概念源于对鸟群觅食行为的研究。设想这样一个场景：一群鸟在随机搜寻食物，在这个区域里只有一块食物，所有的鸟都不知道食物在哪里，但是它们知道当前的位置离食物还有多远。最简单有效的策略？寻找鸟群中离食物最近的个体来进行搜素。PSO算法就从这种生物种群行为特性中得到启发并用于求解优化问题。

用一种粒子来模拟上述的鸟类个体，每个粒子可视为N维搜索空间中的一个搜索个体，粒子的当前位置即为对应优化问题的一个候选解，粒子的飞行过程即为该个体的搜索过程．粒子的飞行速度可根据粒子历史最优位置和种群历史最优位置进行动态调整．粒子仅具有两个属性：速度和位置，速度代表移动的快慢，位置代表移动的方向。每个粒子单独搜寻的最优解叫做个体极值，粒子群中最优的个体极值作为当前全局最优解。不断迭代，更新速度和位置。最终得到满足终止条件的最优解。

算法流程如下：

1、初始化

首先，我们设置最大迭代次数，目标函数的自变量个数，粒子的最大速度，位置信息为整个搜索空间，我们在速度区间和搜索空间上随机初始化速度和位置，设置粒子群规模为M，每个粒子随机初始化一个飞翔速度。

2、 个体极值与全局最优解

定义适应度函数，个体极值为每个粒子找到的最优解，从这些最优解找到一个全局值，叫做本次全局最优解。与历史全局最优比较，进行更新。

3、 更新速度和位置的公式

4、 终止条件

（1）达到设定迭代次数；（2）代数之间的差值满足最小界限

以上就是最基本的一个标准PSO算法流程。和其它群智能算法一样，PSO算法在优化过程中，种群的多样性和算法的收敛速度之间始终存在着矛盾．对标准PSO算法的改进，无论是参数的选取、小生境技术的采用或是其他技术与PSO的融合，其目的都是希望在加强算法局部搜索能力的同时，保持种群的多样性，防止算法在快速收敛的同时出现早熟收敛。

3   总结与应用

首先总结一下PSO算法的一些优点：（1）它是一类不确定算法。不确定性体现了自然界生物的生物机制，并且在求解某些特定问题方面优于确定性算法。（2）是一类概率型的全局优化算法。非确定算法的优点在于算法能有更多机会求解全局最优解。（3）不依赖于优化问题本身的严格数学性质。（4）是一种基于多个智能体的仿生优化算法。粒子群算法中的各个智能体之间通过相互协作来更好的适应环境，表现出与环境交互的能力.（5）具有本质并行性。包括内在并行性和内含并行性。（6）具有突出性。粒子群算法总目标的完成是在多个智能体个体行为的运动过程中突现出来的。（7）具有自组织和进化性以及记忆功能，所有粒子都保存优解的相关知识。（8）都具有稳健性。稳健性是指在不同条件和环境下算法的实用性和有效性，但是现在粒子群算法的数学理论基础还不够牢固，算法的收敛性还需要讨论。

从中可以看出PSO具有很大的发展价值和发展空间，算法能够用于多个领域并创造价值，在群智能算法中具有重要的地位，同时也能够在相关产业创造价值，发挥作用。下面结合相关产业具体分析一下。

计算智能的算法，往往结合大数据平台，包括GPU运算，并行计算，HPC，多模式结合等手段，来完成更加复杂多变的业务需求。

下面具体分析在产业中的作用（1）模式识别和图像处理。PSO算法已在图像分割、图像配准、图像融合、图像识别、图像压缩和图像合成等方面发挥作用。（2）神经网络训练。PSO算法可完成人工神经网络中的连接权值的训练、结构设计、学习规则调整、特征选择、连接权值的初始化和规则提取等。但是速度没有梯度下降优化的好，需要较大的计算资源。一般都算不动。（3）电力系统设计，例如：日本的Fuji电力公司的研究人员将电力企业某个著名的RPVC(Reactive Power and Voltage Control)问题简化为函数的最小值问题，并使用改进的PSO算法进行优化求解。（4）半导体器件综合，半导体器件综合是在给定的搜索空间内根据期望得到的器件特性来得到相应的设计参数。（5）还有其他的一些相关产业。包括自动目标检测、生物信号识别、决策调度、系统识别以及游戏训练等方面也取得了一定的研究成果。

算法实现：

clc
clear 
close all
E=0.000001;
maxnum=800;%最大迭代次数
narvs=2;%目标函数的自变量个数
particlesize=50;%粒子群规模
c1=2;%每个粒子的个体学习因子，加速度常数
c2=2;%每个粒子的社会学习因子，加速度常数
w=0.6;%惯性因子
vmax=5;%粒子的最大飞翔速度
v=2*rand(particlesize,narvs);%粒子飞翔速度
x=-300+600*rand(particlesize,narvs);%粒子所在位置
%定义适应度函数
fitness=inline('(x(1)^2+x(2)^2)/10000','x');
for i=1:particlesize
	f(i)=fitness(x(i,:));	
end
personalbest_x=x;
personalbest_faval=f;
[globalbest_faval,i]=min(personalbest_faval);
globalbest_x=personalbest_x(i,:); 
k=1;
while (k<=maxnum)
	for i=1:particlesize
			f(i)=fitness(x(i,:));
		if f(i)<personalbest_faval(i)
			personalbest_faval(i)=f(i);
			personalbest_x(i,:)=x(i,:);
		end
	end
	[globalbest_faval,i]=min(personalbest_faval);
	globalbest_x=personalbest_x(i,:);
	for i=1:particlesize
		v(i,:)=w*v(i,:)+c1*rand*(personalbest_x(i,:)-x(i,:))...
			+c2*rand*(globalbest_x-x(i,:));
		for j=1:narvs
			if v(i,j)>vmax
				v(i,j)=vmax;
			elseif v(i,j)<-vmax
				v(i,j)=-vmax;
            end
		end
		x(i,:)=x(i,:)+v(i,:);

    end
    ff(k)=globalbest_faval;
    if globalbest_faval<E
        break
    end
%       figure(1)
%       for i= 1:particlesize
%       plot(x(i,1),x(i,2),'*')
%       end
	k=k+1;
end
xbest=globalbest_x;

figure(2)
set(gcf,'color','white');
plot(1:length(ff),ff)

算法结果：

相关阅读

【全源最短路问题】 --Floyd算法

Floyd算法的时间复杂度为O(n3)O(n^3)O(n3)。因此n的大小不超过200。 题目来源：codeup链接在本题中，读入一个有向图的带权邻接矩阵（

轮询调度算法(Round-Robin Scheduling)

http://blog.163.com/s_u/blog/static/1330836720105233102894/ 毫无疑问，随着互联网、移动网络接入成本的降低，互联网正在日益深入

CornerNet 算法笔记

论文：CornerNet: Detecting Objects as Paired Keypoints论文链接：https://arxiv.org/abs/1808.01244代码链接：https://github.com/u

【AC自动机】拓扑优化

之前文章中的AC自动机的劣势：要么只能一次跳fail，无法更新所有fail指的点（如图1），要么fail只能一次跳一格（如图二），更新速度最慢可以卡到O

ROI 的优化，其实是场足球赛

ROI的优化就像一场足球赛，需要根据市场条件，制定合理的战术布局，搭配不同的渠道，才能更大几率赢得比赛。ROI很重要。重要到，很多公司把