粒子群演算法（PSO）

来源:https://www.cnblogs.com/wangyongwen/archive/2019/07/12/11173636.html
-Advertisement-
Play Games

這幾天看書的時候看到一個演算法，叫粒子群演算法，這個演算法挺有意思的，下麵說說我個人的理解： 粒子群演算法（PSO）是一種進化演算法，是一種求得近似最優解的演算法，這種演算法的時間複雜度可能會達到O(n!)，得到的結果不一定是最優解，往往已經很接近最優解了。最早是Kenny 和 Eberhart於1995年提出的 ...


這幾天看書的時候看到一個演算法，叫粒子群演算法，這個演算法挺有意思的，下麵說說我個人的理解：

　　粒子群演算法（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。執行上述代碼，運行一小段時間就可以得到題目中的答案了。

由於粒子群演算法的隨機性，每次執行結果可能並不是一樣的，這就意味著有時候可能得到更好的，有時候可能會差一些，但相差不會太遠的。

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 微信推送功能實現
    推送的方式： 簡訊推送(第三方) 郵件推送 微信推送 公眾號：認證的公眾號(個人的認證公眾號每天只能發一篇文章)，粉絲可以跟公眾號聊天， 未認證公眾號 服務號：企業認證(營業執照)，沙箱環境測試 主動給用戶發消息(推送)，用戶要接收到推送消息前提是需要關註對應的服務號才行 企業號 微信小程式 公眾號 ...
  • 01_線程的創建和啟動
    1、線程的使用步驟 2、第一種定義線程類的方法：繼承java.lang.Thread類 MyThread 文件： public class MyThread extends Thread { private int count=0; @Override public void run() { Sys ...
  • python小游戲貪吃蛇源碼下載
    回車鍵：開始游戲，空格鍵：暫停 / 繼續，方向鍵 或 WSAD 鍵：控制移動方向 下載地址 ...
  • leadcode的Hot100系列--347. 前 K 個高頻元素--hash表+直接選擇排序
    這個看著應該是使用堆排序，但我圖了一個簡單，所以就簡單hash表加選擇排序來做了。 使用結構體: 思路： hash表用來存儲每個值對應的頻率，每讀到一個數字，對應的頻率就加1。 然後從表中再把這些數據讀取出來。 先創建兩個長度為k的數組，一個用來記錄頻率，一個用來記錄對應的數值。 讀取數據的時候，使 ...
  • 知秋源碼解讀分享系列
    作為一個樂於分享的人，我希望通過一些成熟優秀的代碼庫，來向大家展示讀源碼思路以及闡述編程方面的技巧，也希望大家從中思考並得到屬於自己的一套編程方法論。 半年以來，已進行72小時時長的源碼解讀分享視頻錄製，額外分享時間未計，雖有諸多不足，依然歡迎進行技術交流，也希望可以影響到更多人參與到分享中來，通過 ...
  • linux maven 安裝與配置
    Apache Maven，是一個軟體（特別是Java軟體）項目管理及自動構建工具，由Apache軟體基金會所提供。基於項目對象模型（縮寫：POM）概念，Maven利用一個中央信息片斷能管理一個項目的構建、報告和文檔等步驟。曾是Jakarta項目的子項目，現為獨立Apache項目。1.軟體下載http ...
  • 淺談微服務轉型
    微服務已經流行很久了。相比前兩年而言，確實很流行了。 微服務流行不是什麼壞事，微服務本身是一個很好的架構思想，架構思想一直在改變，微服務之前的SOA也是不錯的做法。只是，在享受新思想帶來的好處時，卻不要為了新而新。 微服務解決了SOA沒有解決的一些問題，但它並不是萬能的，它本身也並非什麼高大上的新技 ...
  • Python連載22-調試&單元測試
    一、調試技術 （1）調試流程​：單元測試->集成測試->交測試部 （2）分類：i.靜態調試（說白了就是看代碼，看看有沒有錯）；ii.動態測試 1.pdb調試 ​相關連接：https://blog.csdn.net/xc_zhou/article/details/80921483 作者：周小董 2.p ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類