- 粒子群算法的定义
- 模拟鸟类捕食
- 启示
- 算法流程图
- 案例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;
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;
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]);
}
}
}
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));
}
public double getObjValue(double[] vars) {
//目标：在变量区间范围最小化 Z = x^2 + y^2 - xy - 10x - 4y +60
return 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;
public class PlotUtil extends Application {
//当前的时间轴
private Timeline nowTimeline;
//绘图位置坐标
private double[][][] positionArr;
public static void main(String[] args) {
launch(args);
}
@Override
public 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();
}
}
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;
}
}
}
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);
}
}
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;
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;
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]);
}
}
}
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));
}
public double getObjValue(double[] vars) {
// 设六元变量分别为 a b c d e f
// 目标：在变量区间范围最小化 Z = abc - bce + cd + ef - bdf
return (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.387035664320209E8 最优解坐标为：[-886.8352994556639, -748.1858708041178, -560.6940636412202, 646.2689604948565, -274.97367655848336, -404.99446493036083] 求解用时：0.028 s
