粒子群算法(PSO)

Roy 2019-07-12 01:4522 阅读

这几天看书的时候看到一个算法,叫粒子群算法,这个算法挺有意思的,下面说说我个人的理解:

  粒子群算法(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表示当前速度pBest和 gBest分别表示个体最优解和全局最优解。当然每个维度上的速度分量可以限定一个最大值。

  (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 = 400-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);
    }
  }

}

 

回复数量: 0
暂无评论~~
  请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!