文章目录
粒子群算法的定义模拟鸟类捕食启示算法流程图案例1 - 求解二元函数最小值代码运行结果迭代过程可视化可视化代码案例2 - 求解六元函数最小值代码运行结果粒子群算法的定义
粒子群优化算法(Particle Swarm optimization,PSO)又翻译为粒子群算法、微粒群算法、或微粒群优化算法。是通过模拟鸟群觅食行为而发展起来的一种基于群体协作的随机搜索算法。通常认为它是群集智能 (Swarm intelligence, SI) 的一种。它可以被纳入多主体优化系统(Multiagent Optimization System, MAOS)。粒子群优化算法是由Eberhart博士和kennedy博士发明。
模拟鸟类捕食
PSO模拟鸟群的捕食行为。一群鸟在随机搜索食物，在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的就是搜寻离食物最近的鸟的周围区域。
启示
PSO从这种模型中得到启示并用于解决优化问题。PSO中，每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值(fitnessvalue)，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。
算法流程图
案例1 - 求解二元函数最小值
Z = x^2 + y^2 - xy - 10x - 4y +60
代码
import java.util.Arrays;import java.util.Random;/*** @Author：WSKH* @ClassName：PSO_Solve* @ClassType：* @Description：* @Date：/6/6/14:59* @Email：1187560563@* @Blog：/weixin_51545953?type=blog*/public class PSO_Solve {// 粒子对象class Particle {// 粒子速度数组（每个方向都有一个速度）double[] vArr;// 当前粒子坐标（自变量数组）double[] curVars;// 当前自变量对应的目标函数值double curObjValue;// 该粒子找到过的最佳目标函数值double bestObjValue;// 该粒子最好位置时的坐标double[] bestVars;// 全参构造public Particle(double[] vArr, double[] curVars, double curObjValue, double bestObjValue, double[] bestVars) {this.vArr = vArr;this.curVars = curVars;this.curObjValue = curObjValue;this.bestObjValue = bestObjValue;this.bestVars = bestVars;}}// 粒子数量int n = 500;// 每个粒子的个体学习因子：自我认知，设置较大则不容易被群体带入局部最优，但会减缓收敛速度double c1 = 2;// 每个粒子的社会学习因子：社会认知，设置较大则加快收敛，但容易陷入局部最优double c2 = 2;// 粒子的惯性权重double w = 0.9;// 迭代的次数int MaxGen = 500;// 粒子的每个维度上的最大速度（数组）double[] vMaxArr = new double[]{1.2,1.2};// 随机数对象Random random = new Random();// 自变量个数int varNum = 2;// 自变量的上下界数组double[] lbArr = new double[]{-1000, -1000};double[] ubArr = new double[]{1000, 1000};// 粒子群Particle[] particles;// 最佳粒子Particle bestParticle;// 记录迭代过程public double[][][] positionArr;/*** @Description 初始化粒子的位置和速度*/private void initParticles() {// 初始化粒子群particles = new Particle[n];// 随机生成粒子for (int i = 0; i < particles.length; i++) {// 随机生成坐标和速度double[] vars = new double[varNum];double[] vArr = new double[varNum];for (int j = 0; j < varNum; j++) {vars[j] = random.nextDouble() * (ubArr[j] - lbArr[j]) + lbArr[j];vArr[j] = (random.nextDouble() - 0.5) * 2 * vMaxArr[j];}// 目标函数值double objValue = getObjValue(vars);particles[i] = new Particle(vArr.clone(), vars.clone(), objValue, objValue, vars.clone());}// 找到初始化粒子群中的最佳粒子bestParticle = copyParticle(particles[0]);for (int i = 1; i < particles.length; i++) {if (bestParticle.bestObjValue > particles[i].bestObjValue) {bestParticle = copyParticle(particles[i]);}}}/*** @Description 主要求解函数*/public void solve() {// 变量设置初步判断if(varNum != vMaxArr.length || varNum != lbArr.length || varNum != ubArr.length){throw new RuntimeException("变量维度不一致");}positionArr = new double[MaxGen][n][varNum];// 初始化粒子的位置和速度initParticles();// 开始迭代for (int i = 0; i < MaxGen; i++) {// 依次更新第i个粒子的速度与位置for (int j = 0; j < particles.length; j++) {// 针对不同维度进行处理for (int k = 0; k < varNum; k++) {// 更新速度double newV = particles[j].vArr[k] * w+ c1 * random.nextDouble() * (particles[j].bestVars[k] - particles[j].curVars[k])+ c2 * random.nextDouble() * (bestParticle.bestVars[k] - particles[j].curVars[k]);// 如果速度超过了最大限制，就对其进行调整if (newV < -vMaxArr[k]) {newV = -vMaxArr[k];} else if (newV > vMaxArr[k]) {newV = vMaxArr[k];}// 更新第j个粒子第k个维度上的位置double newPos = particles[j].curVars[k] + newV;// 记录迭代过程positionArr[i][j][k] = newPos;// 如果位置超出了定义域，就对其进行调整if(newPos < lbArr[k]){newPos = lbArr[k];}else if(newPos > ubArr[k]){newPos = ubArr[k];}// 赋值回去particles[j].curVars[k] = newPos;particles[j].vArr[k] = newV;}// 更新完所有维度后，再计算第j个粒子的函数值double objValueJ = getObjValue(particles[j].curVars);particles[j].curObjValue = objValueJ;if(objValueJ < particles[j].bestObjValue){particles[j].bestVars = particles[j].curVars.clone();particles[j].bestObjValue = particles[j].curObjValue;}if(objValueJ < bestParticle.bestObjValue){bestParticle = copyParticle(particles[j]);}}}// 迭代结束，输出最优粒子位置和函数值System.out.println("最优解为："+ bestParticle.bestObjValue);System.out.println("最优解坐标为："+ Arrays.toString(bestParticle.bestVars));}/*** @param vars 自变量数组* @return 返回目标函数值*/public double getObjValue(double[] vars) {//目标：在变量区间范围最小化 Z = x^2 + y^2 - xy - 10x - 4y +60return Math.pow(vars[0], 2) + Math.pow(vars[1], 2) - vars[0] * vars[1] - 10 * vars[0] - 4 * vars[1] + 60;}// 复制粒子public Particle copyParticle(Particle old) {return new Particle(old.vArr.clone(), old.curVars.clone(), old.curObjValue, old.bestObjValue, old.bestVars.clone());}}
运行结果
最优解为：8.000057527138821最优解坐标为：[8.00430921604821, 5.995551568450099]求解用时：0.019 s
迭代过程可视化
可视化代码
import javafx.animation.KeyFrame;import javafx.animation.Timeline;import javafx.application.Application;import javafx.geometry.Pos;import javafx.scene.Scene;import javafx.scene.canvas.Canvas;import javafx.scene.canvas.GraphicsContext;import javafx.scene.control.Button;import javafx.scene.input.MouseEvent;import javafx.scene.layout.BorderPane;import javafx.scene.layout.HBox;import javafx.scene.paint.Color;import javafx.stage.Stage;import javafx.util.Duration;/*** @Author：WSKH* @ClassName：PlotUtil* @ClassType：* @Description：* @Date：/6/6/18:31* @Email：1187560563@* @Blog：/weixin_51545953?type=blog*/public class PlotUtil extends Application {//当前的时间轴private Timeline nowTimeline;//绘图位置坐标private double[][][] positionArr;public static void main(String[] args) {launch(args);}@Overridepublic void start(Stage primaryStage) throws Exception {// 调用算法获取绘图数据PSO_Solve psoApi = new PSO_Solve();psoApi.solve();this.positionArr = psoApi.positionArr;// 画图try {BorderPane root = new BorderPane();root.setStyle("-fx-padding: 20;");Scene scene = new Scene(root, 1600, 900);double canvasWid = 800;double canvasHei = 800;//根据画布大小缩放坐标值this.fixPosition(canvasWid - 100, canvasHei - 100);//画布和画笔HBox canvasHbox = new HBox();Canvas canvas = new Canvas();canvas.setWidth(canvasWid);canvas.setHeight(canvasHei);canvasHbox.setPrefWidth(canvasWid);canvasHbox.getChildren().add(canvas);canvasHbox.setAlignment(Pos.CENTER);canvasHbox.setStyle("-fx-spacing: 20;" +"-fx-background-color: #87e775;");root.setTop(canvasHbox);GraphicsContext paintBrush = canvas.getGraphicsContext2D();//启动HBox hBox2 = new HBox();Button beginButton = new Button("播放迭代过程");hBox2.getChildren().add(beginButton);root.setBottom(hBox2);hBox2.setAlignment(Pos.CENTER);//启动仿真以及暂停仿真beginButton.addEventHandler(MouseEvent.MOUSE_CLICKED, event -> {nowTimeline.play();});//创建扫描线连接动画nowTimeline = new Timeline();createAnimation(paintBrush);primaryStage.setScene(scene);primaryStage.show();} catch (Exception e) {e.printStackTrace();}}/*** 修正cityPositionArr的坐标，让画出来的点在画布内** @param width* @param height*/private void fixPosition(double width, double height) {double minX = Double.MAX_VALUE;double maxX = -Double.MAX_VALUE;double minY = Double.MAX_VALUE;double maxY = -Double.MAX_VALUE;for (int i = 0; i < this.positionArr.length; i++) {for (int j = 0; j < this.positionArr[0].length; j++) {minX = Math.min(minX, this.positionArr[i][j][0]);maxX = Math.max(maxX, this.positionArr[i][j][0]);minY = Math.min(minY, this.positionArr[i][j][1]);maxY = Math.max(maxY, this.positionArr[i][j][1]);}}double multiple = Math.max((maxX - minX) / width, (maxY - minY) / height);//转化为正数数for (int i = 0; i < this.positionArr.length; i++) {for (int j = 0; j < this.positionArr[0].length; j++) {if (minX < 0) {this.positionArr[i][j][0] = this.positionArr[i][j][0] - minX;}if (minY < 0) {this.positionArr[i][j][1] = this.positionArr[i][j][1] - minY;}}}for (int i = 0; i < this.positionArr.length; i++) {for (int j = 0; j < this.positionArr[0].length; j++) {this.positionArr[i][j][0] = this.positionArr[i][j][0] / multiple;this.positionArr[i][j][1] = this.positionArr[i][j][1] / multiple;}}}/*** 用画笔在画布上画出所有的孔* 画第i代的所有粒子*/private void drawAllCircle(GraphicsContext paintBrush, int i) {paintBrush.clearRect(0, 0, 2000, 2000);paintBrush.setFill(Color.RED);for (int j = 0; j < this.positionArr[i].length; j++) {drawCircle(paintBrush, i, j);}}/*** 用画笔在画布上画出一个孔* 画第i代的第j个粒子*/private void drawCircle(GraphicsContext paintBrush, int i, int j) {double x = this.positionArr[i][j][0];double y = this.positionArr[i][j][1];double radius = 2;// 圆的直径double diameter = radius * 2;paintBrush.fillOval(x, y, diameter, diameter);}/*** 创建动画*/private void createAnimation(GraphicsContext paintBrush) {for (int i = 0; i < this.positionArr[0].length; i++) {int finalI = i;KeyFrame keyFrame = new KeyFrame(Duration.seconds(i * 0.05), event -> drawAllCircle(paintBrush, finalI));nowTimeline.getKeyFrames().add(keyFrame);}}}
案例2 - 求解六元函数最小值
设六元变量分别为 a b c d e f目标：在变量区间范围最小化 Z = abc - bce + cd + ef - bdf
代码
import java.util.Arrays;import java.util.Random;/*** @Author：WSKH* @ClassName：PSO_Solve_6d* @ClassType：* @Description：* @Date：/6/6/14:59* @Email：1187560563@* @Blog：/weixin_51545953?type=blog*/public class PSO_Solve_6d {// 粒子对象class Particle {// 粒子速度数组（每个方向都有一个速度）double[] vArr;// 当前粒子坐标（自变量数组）double[] curVars;// 当前自变量对应的目标函数值double curObjValue;// 该粒子找到过的最佳目标函数值double bestObjValue;// 该粒子最好位置时的坐标double[] bestVars;// 全参构造public Particle(double[] vArr, double[] curVars, double curObjValue, double bestObjValue, double[] bestVars) {this.vArr = vArr;this.curVars = curVars;this.curObjValue = curObjValue;this.bestObjValue = bestObjValue;this.bestVars = bestVars;}}// 粒子数量int n = 100;// 每个粒子的个体学习因子：自我认知，设置较大则不容易被群体带入局部最优，但会减缓收敛速度double c1 = 2;// 每个粒子的社会学习因子：社会认知，设置较大则加快收敛，但容易陷入局部最优double c2 = 2;// 粒子的惯性权重double w = 0.9;// 迭代的次数int MaxGen = 500;// 粒子的每个维度上的最大速度（数组）double[] vMaxArr = new double[]{1.2, 1.2, 1.2, 1.2, 1.2, 1.2};// 随机数对象Random random = new Random();// 自变量个数int varNum = 6;// 自变量的上下界数组double[] lbArr = new double[]{-1000, -1000, -1000, -1000, -1000, -1000};double[] ubArr = new double[]{1000, 1000, 1000, 1000, 1000, 1000};// 粒子群Particle[] particles;// 最佳粒子Particle bestParticle;/*** @Description 初始化粒子的位置和速度*/private void initParticles() {// 初始化粒子群particles = new Particle[n];// 随机生成粒子for (int i = 0; i < particles.length; i++) {// 随机生成坐标和速度double[] vars = new double[varNum];double[] vArr = new double[varNum];for (int j = 0; j < varNum; j++) {vars[j] = random.nextDouble() * (ubArr[j] - lbArr[j]) + lbArr[j];vArr[j] = (random.nextDouble() - 0.5) * 2 * vMaxArr[j];}// 目标函数值double objValue = getObjValue(vars);particles[i] = new Particle(vArr.clone(), vars.clone(), objValue, objValue, vars.clone());}// 找到初始化粒子群中的最佳粒子bestParticle = copyParticle(particles[0]);for (int i = 1; i < particles.length; i++) {if (bestParticle.bestObjValue > particles[i].bestObjValue) {bestParticle = copyParticle(particles[i]);}}}/*** @Description 主要求解函数*/public void solve() {// 变量设置初步判断if (varNum != vMaxArr.length || varNum != lbArr.length || varNum != ubArr.length) {throw new RuntimeException("变量维度不一致");}// 初始化粒子的位置和速度initParticles();// 开始迭代for (int i = 0; i < MaxGen; i++) {// 依次更新第i个粒子的速度与位置for (int j = 0; j < particles.length; j++) {// 针对不同维度进行处理for (int k = 0; k < varNum; k++) {// 更新速度double newV = particles[j].vArr[k] * w+ c1 * random.nextDouble() * (particles[j].bestVars[k] - particles[j].curVars[k])+ c2 * random.nextDouble() * (bestParticle.bestVars[k] - particles[j].curVars[k]);// 如果速度超过了最大限制，就对其进行调整if (newV < -vMaxArr[k]) {newV = -vMaxArr[k];} else if (newV > vMaxArr[k]) {newV = vMaxArr[k];}// 更新第j个粒子第k个维度上的位置double newPos = particles[j].curVars[k] + newV;// 如果位置超出了定义域，就对其进行调整if (newPos < lbArr[k]) {newPos = lbArr[k];} else if (newPos > ubArr[k]) {newPos = ubArr[k];}// 赋值回去particles[j].curVars[k] = newPos;particles[j].vArr[k] = newV;}// 更新完所有维度后，再计算第j个粒子的函数值double objValueJ = getObjValue(particles[j].curVars);particles[j].curObjValue = objValueJ;if (objValueJ < particles[j].bestObjValue) {particles[j].bestVars = particles[j].curVars.clone();particles[j].bestObjValue = particles[j].curObjValue;}if (objValueJ < bestParticle.bestObjValue) {bestParticle = copyParticle(particles[j]);}}}// 迭代结束，输出最优粒子位置和函数值System.out.println("最优解为：" + bestParticle.bestObjValue);System.out.println("最优解坐标为：" + Arrays.toString(bestParticle.bestVars));}/*** @param vars 自变量数组* @return 返回目标函数值*/public double getObjValue(double[] vars) {// 设六元变量分别为 a b c d e f// 目标：在变量区间范围最小化 Z = abc - bce + cd + ef - bdfreturn (vars[0] * vars[1] * vars[2] - vars[1] * vars[2] * vars[3] + vars[2] * vars[4] + vars[4] * vars[5] - vars[1] * vars[3] * vars[5]);}// 复制粒子public Particle copyParticle(Particle old) {return new Particle(old.vArr.clone(), old.curVars.clone(), old.curObjValue, old.bestObjValue, old.bestVars.clone());}}
运行结果
最优解为：-8.38703566439E8最优解坐标为：[-886.8352994556639, -748.1858708041178, -560.6940636412202, 646.2689604948565, -274.97367655848336, -404.99446493036083]求解用时：0.028 s
