首页 > > 程序设计 > Java技术 >

粒子群算法（PSO）

2019-08-16 10:16:16来源：博客园 阅读 ()

新老客户大回馈,云服务器低至5折

粒子群算法（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。执行上述代码，运行一小段时间就可以得到题目中的答案了。

由于粒子群算法的随机性，每次执行结果可能并不是一样的，这就意味着有时候可能得到更好的，有时候可能会差一些，但相差不会太远的。

 


原文链接:https://www.cnblogs.com/wangyongwen/p/11173636.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有

上一篇：SpringCloud微服务架构升级总结

下一篇：就是要让你彻底学会 @Bean 注解

相关文章

IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设

网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源

网站联盟： 联盟新闻 联盟介绍 联盟点评 网赚技巧

行业资讯： 搜索引擎 网络游戏 电子商务 广告传媒

网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它

服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护

软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷

网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash

程序设计： Java技术 C/C++ VB delphi

网络知识： 网络协议 网络安全 网络管理 组网方案 Cisco技术

操作系统： Win2000 WinXP Win2003 Mac OS Linux FreeBSD

热门词条
最新资讯
热门关注
热门标签