粒子群算法（PSO）
这几天看书的时候看到一个算法，叫粒子群算法，这个算法挺有意思的，下面说说我个人的理解：
粒子群算法（PSO）是一种进化算法，是一种求得近似最优解的算法，这种算法的时间复杂度可能会达到O(n!)，得到的结果不一定是最优解，往往已经很接近最优解了。最早是Kenny 和 Eberhart于1995年提出的，算法的参数配置少，易于应用，理解起来也很简单。实现步骤如下：
（1）初始化所有的粒子，粒子的位置随机生成，计算每个粒子当前适应度，并将此设置为当前粒子的个体最优解（记为pBest）；
（2）所有粒子将自己的个体最优值发给管理者Master，管理者Master接到所有粒子的信息后，筛选出全局最优解（记为gBest）；
（3）Master将gBest通知所有粒子，所有粒子知道了全局最优解的位置；
（4）所有粒子根据自己的个体最优解和全局最优解，更新自己的速度，有了速度以后更新自己的位置。
vk+1 = c0 × rand() × vk + c1 × rand() × (pBestk – xk) + c2 × rand() × (gBestk – xk)
rand() 函数会产生一个(0,1)的随机数。 c0 = 1、 c1 = 2、 c2 = 2 ，k表示进化的代数。vk表示当前速度，pBestk 和 gBestk 分别表示个体最优解和全局最优解。当然每个维度上的速度分量可以限定一个最大值。
（5）如果粒子产生了新的个体最优解，则发送给Master，再循环步骤（2）。
可以看出每个粒子的计算有很大的随机性，但是我们可以启用大量的粒子进行计算，因此在统计学意义上是稳定的。
下面出到这个算法的题：
假设有400万元，要求4年内用完，如果第一年使用x万元，则可以得到的收益是√x万元（收益不再使用），当年不用的资金存入银行，年利率10%，尝试指定资金使用计划，使得4年收益之和最大。
很明显，不同方案有不同结果，差异也很大，例如第一年就把400万投资，那么收益就是√400 = 20万；如果前三年不用，存入银行，第四年再把本金和利息全部拿出来，总收益是√400×1.13 = 23.07 万元，优于第一个方案。
如果一个线程一个方案的话势必产生大量的线程，Akka框架的Actor模型正好适合这个，因为每个Actor可以共享同一个线程，这样不用产生大量的线程并且保证了大量的粒子。我们可以使用Actor来模拟整个粒子计算的场景。
首先，新建pBest和gBest消息类型，用于多个Actor之间传递个体最优解和全局最优解。
1 /** 2 * 全局最优解 3 */ 4 public final class GBestMsg{ 5 final PsoValue value; 6 public GBestMsg(PsoValue v){ 7 value = v; 8 } 9 public PsoValue getValue(){ 10 return value; 11 } 12 } 13 /** 14 * 个体最优解 15 */ 16 public final class PBestMsg{ 17 final PsoValue value; 18 public PBestMsg(PsoValue v){ 19 value = v; 20 } 21 public PsoValue getValue(){ 22 return value; 23 } 24 public String toString(){ 25 return value.toString(); 26 } 27 }
View Code
上面最优解中有个类是PsoValue，主要包含两个信息，一是投资规划方案，就是每一年分别需要投资多少钱；二是这个投资方案的总收益
public final class PsoValue{ final double value; final List<Double> x; public PsoValue(double v,List<Double> x){ value = v; List<Double> b = new ArrayList<Double>(5); v.addAll(x); this.x = Collections.unmodifiableList(b); } public double getValue(){ return value; } public List<Double> getX(){ return x; } public String toString(){ StringBuffer sb = new StringBuffer(); sb.append("value:").append(value).append("\n").append(x.toString()); return sb.toString(); } }
上述代码的数组x中，x[1]、x[2]、x[3]、x[4]分别表示第一年、第二年、第三年、第四年的投资额，忽略x[0]，成员变量value表示这组投资方案的收益值。根据题目的需求，x与value之间的关系可以用如下代码表示。投资收益额 = √x1+√x2+√x3+√x4 。
public class Fitness{ public static double fitness(List<Double> x){ double sum = 0; for(int i =1; i<x.size();i++){ sum += Math.sqrt(x.get(i)); } return sum; } }
下面就是实现我们的粒子了，我们就叫他Bird吧，定义以下成员变量和方法如下：
Public class Bird extends UntypedActor{ private final LoggingAdapter log = Logging.getLogger(getContext().system(),this);
//个人最优解 private PsoValue pBest = null;
//全局最优解 private PsoValue gBest = null;
//粒子在各个维度上的速度 private List<Double> velocity = new ArrayList<Double>(5);
//投资方案 private List<Double> x = new ArrayList<Double>(5); private Random r = new Random();
/**
初始化粒子
*/ @Override public void preStart(){ for(int i = 0;i<5;i++){ velocity.add(Double.NEGATIVE_INFINITY); x.add(Double.NEGATIVE_INFINITY); } x.set(1,(double)x.nextInt(401)); double max = 440-1.1*x.get(1); if(max<0) max=0; x.set(2,r.nextDouble()*max); max = 484 - 1.21*x.get(1)-1.1*x.get(2); if(max<0) max=0; x.set(3,r.nextDouble()*max); max = 532.4-1.331*x.get(1)-1.21*x.get(2)-1.1*x.get(3）; if(max<0) max=0; x.set(4,r.nextDouble()*max); doubel newFit = Fitness.fitness(x); pBest = new PsoValue(newFit,x); PBestMsg pBestMsg = new PBestMsg(pBest); ActorSelection selection = getContext().actorSelection("/user/masterbird"); selection.tell(pBestMsg,getSelf()); }
/**
接受全局最优解
*/ @Override public void onReceive(Object msg){ if(msg instanceof GBestMsg){ gBest = ((GBestMsg)msg).getValue(); for(int i =1;i<5;i++){ updateVelocity(i); } for(int i =1;i<5;i++){ updateX(i); } validateX(); double newFit = Fitness.fitness(); if(newFile>pBest.value){ pBest=new PsoValue(newFit,x); PBestMsg pBestMsg = new PBestMsg(pBest); getSender().tell(pBestMsg,getSelf()); } } else{ unhandled(msg); } }
/**
更新偏移量
*/public double updateVelocity(int i){
double v = Math.random()*velocity.get(i)
+2*Math.random()*(pBest.getX().get(i)-x.get(i))
+2*Math.random()*(gBest.getX().get(i)-x.get(i));
v = v>0?Math.min(v,5):Math.max(v,-5);
velocity.set(i,v);
return v;
}
public double update(int i){
double newX = x.get(i)+velocity.get(i);
x.set(i,newX);
return newX;
}
public void validateX(){
if(x.get(i)>400){
x.set(1,(double) r.nextInt(401));
}
double max = 440-1.1*x.get(1);
if(x.get(2)>max || x.get(2)<0){
x.set(2,r.nextDouble()*max);
}
max = 484 - 1.21*x.get(1)-1.1*x.get(2); if(x.get(3)>max || x.get(3)<0){
x.set(3,r.nextDouble()*max);
}
max = 532.4-1.331*x.get(1)-1.21*x.get(2)-1.1*x.get(3）; if(x.get(4)>max || x.get(4)<0){
x.set(4,r.nextDouble()*max);
} }
}当一个粒子被创建需要初始化粒子当前位置，粒子的每个位置代码一个投资方案，上述代码的preStart()方法就是初始化粒子，本题中投资额是有限制的，例如第一年的投资额不能超过400万元，而第二年的投资上限就是440万，粒子初始化位置后，会计算一个适应度也就是本题目中的投资收益额。Master计算出全局最优解后会将全局最优解发送给每一个粒子，粒子根据全局最优解更新自己的运行速度就是本题目中是偏移量，以及当前位置。如果粒子跑偏了就要重新随机化，也就是需要校验功能。
此外还有个MasterBird用于管理和通知全局的最优解。
public calss MasterBird extends UntypedActor{ private final LoggingAdapter log = Logging.getLogger(getContext().system(),this); private PsoValue gBest = null; @Override public void onReceive(Object msg){ if(msg instanceof PBestMsg){ PsoValue pBest = ((PBestMsg) msg).getValue(); if(gBest == null || gBest .value < pBest.value){
System.out.println(msg+"\n"); gBest = pBest; ActorSelection selection = this.getContext().actorSelection("user/bird_"); selection.tell(new GBestMsg(gBest),this.getSelf()); } }else{ unhandle(msg); } } }
上述代码定义了MasterBird，当他收到一个个体的最优解时，会将其与全局最优解进行比较，如果产生了新的最优解，就会更新这个全局最优解，并且通知各个粒子。
下面看看主函数了：
public class PSOMain{ public static final int BIRD_COUNT = 100000; public static void main(){ ActorSystem system = ActorSystem.create("psoSystem",ConfigFactory.load("samplehell.conf")); system.actorOf(Props.create(MasterBird.class),"masterbird"); for(int i=0;i<BIRD_COUNT;i++){ system.actorOf(Props.create(Bird.class),"bird_"+i) } } }
上面代码定义了10万个粒子，创建了一个MasterBird和10万个bird。执行上述代码，运行一小段时间就可以得到题目中的答案了。
由于粒子群算法的随机性，每次执行结果可能并不是一样的，这就意味着有时候可能得到更好的，有时候可能会差一些，但相差不会太远的。
相关文章