@[toc]
前言
本文以求解二元函数最小值为例，如果需要求解多元函数，只需要修改以下变量即可：
- varNum：变量维度数
- ub和lb：变量的上下界
- vMaxArr：每个维度的搜索速度限制
优化目标
目标：在变量区间范围最小化 Z = x^2 + y^2 - xy - 10x - 4y +60优化结果
变量取值为：[8.000000025138169, 6.000000008671988]
最优解为：7.999999999999986迭代过程可视化
注意，下图可没有加速处理！SMO算法的收敛速度就是那么快！
在SMO中，局部领导者阶段和全局领导者阶段有助于利用搜索空间，而探索则通过局部领导者决策阶段和全局领导者决策阶段完成。SMO性能分析表明，SMO在可靠性、有效性和精度方面超过了ABC、DE和PSO。
Java代码
import java.util.*;
/**
* @Author：WSKH
* @ClassName：SMO_Solver
* @ClassType：
* @Description：
* @Date：2022/6/8/13:42
* @Email：1187560563@qq.com
* @Blog：https://blog.csdn.net/weixin_51545953?type=blog
*/
public class SMO_Solver {
// 蜘蛛猴对象
class SpiderMonkey {
// 当前蜘蛛猴坐标（自变量数组）
double[] curVars;
// 当前自变量对应的目标函数值
double curObjValue;
// 适应度（解决最小化问题，所以适应度为目标函数值的倒数）
double fit;
// 全参数构造
public SpiderMonkey(double[] curVars, double curObjValue, double fit) {
this.curVars = curVars;
this.curObjValue = curObjValue;
this.fit = fit;
}
}
// 算法参数
// 蜘蛛猴群
List<SpiderMonkey[]> spiderMonkeyList = new ArrayList<>();
// 局部领导者
List<SpiderMonkey> localLeaderList = new ArrayList<>();
// 最好的蜘蛛猴(全局领导者)
SpiderMonkey bestSpiderMonkey;
// 随机数对象
Random random = new Random();
// 最大迭代次数
int maxGen = 500;
// 蜘蛛猴数量
int spiderMonkeyNum = 300;
// 局部搜索次数(一般等于蜘蛛猴数量)
int localSearchCount = spiderMonkeyNum;
// 局部领导者决策阶段的更新几率
double LLDP_PR = 0.1;
// 局部领导者阶段的更新几率
double LLP_PR = 0.8;
// 变量维度数
int varNum = 2;
// 最大组数(一般要至少保证每组里有10个蜘蛛猴)
int maxgroupNum = spiderMonkeyNum/10 ;
// 变量的上下界
double[] ub = new double[]{1000, 1000};
double[] lb = new double[]{-1000, -1000};
// 局部计数器
int[] localLimitCount = new int[]{0};
// 停止条件
int limitCnt = 50;
// 全局计数器
int globalLimitCount;
// 记录迭代过程
public double[][][] positionArr;
// 记录迭代器的行数
int curC = 0;
// 是否开启贪心机制（只接受比当前解好的解）
boolean greedy = true;
// 求解主函数
public void solve() {
// 初始化蜘蛛猴种群
initSpiderMonkeys();
// 开始迭代
for (int t = 0; t < maxGen; t++) {
// 局部领导者阶段（LLP：所有的蜘蛛猴都有机会更新自己）
LLP();
// 全局领导者阶段（GLP：轮盘赌，随机选取，偏向于对fit值大的蜘蛛猴进行更新）
GLP();
// 全局领导者学习阶段（如果全局领导者有更新，则globalLimitCount=0，否则globalLimitCount++）
GLLP();
// 局部领导者学习阶段（如果局部领导者有更新，则localLimitCount=0，否则localLimitCount++）
LLLP();
// 局部领导者决策阶段
LLDP();
// 全局领导者决策阶段
GLDP();
}
// 输出最好的结果
System.out.println("变量取值为：" + Arrays.toString(bestSpiderMonkey.curVars));
System.out.println("最优解为：" + bestSpiderMonkey.curObjValue);
}
// 全局领导者决策阶段
private void GLDP() {
if (globalLimitCount >= limitCnt) {
globalLimitCount = 0;
if (spiderMonkeyList.size() < maxgroupNum) {
// 分裂
List<SpiderMonkey> tempList = new ArrayList<>();
for (SpiderMonkey[] spiderMonkeys : spiderMonkeyList) {
tempList.addAll(Arrays.asList(spiderMonkeys));
}
tempList.sort(new Comparator<SpiderMonkey>() {
@Override
public int compare(SpiderMonkey o1, SpiderMonkey o2) {
return Double.compare(o2.fit,o1.fit);
}
});
//
int groupNum = spiderMonkeyList.size() + 1;
spiderMonkeyList = new ArrayList<>();
int avgNum = spiderMonkeyNum / groupNum;
for (int i = 0; i < groupNum - 1; i++) {
SpiderMonkey[] spiderMonkeys = new SpiderMonkey[avgNum];
for (int j = 0; j < avgNum; j++) {
spiderMonkeys[j] = copySpiderMonkey(tempList.remove(0));
}
spiderMonkeyList.add(spiderMonkeys);
}
spiderMonkeyList.add(tempList.toArray(new SpiderMonkey[0]));
localLimitCount = new int[groupNum];
} else {
// 融合
SpiderMonkey[] spiderMonkeys = new SpiderMonkey[spiderMonkeyNum];
int i = 0;
for (SpiderMonkey[] monkeys : spiderMonkeyList) {
for (SpiderMonkey monkey : monkeys) {
spiderMonkeys[i++] = copySpiderMonkey(monkey);
}
}
spiderMonkeyList = new ArrayList<>();
spiderMonkeyList.add(spiderMonkeys);
localLimitCount = new int[]{0};
}
// 更新局部领导者
localLeaderList = new ArrayList<>();
for (SpiderMonkey[] spiderMonkeys : spiderMonkeyList) {
localLeaderList.add(copySpiderMonkey(spiderMonkeys[0]));
int index = localLeaderList.size() - 1;
for (int i = 1; i < spiderMonkeys.length; i++) {
if (localLeaderList.get(index).fit < spiderMonkeys[i].fit) {
localLeaderList.set(index, copySpiderMonkey(spiderMonkeys[i]));
}
}
}
}
}
// 局部领导者决策阶段
private void LLDP() {
int c = 0;
for (int i = 0; i < spiderMonkeyList.size(); i++) {
SpiderMonkey[] spiderMonkeys = spiderMonkeyList.get(i);
if (localLimitCount[i] < limitCnt) {
for (int j = 0; j < spiderMonkeys.length; j++) {
SpiderMonkey tempSpiderMonkey = copySpiderMonkey(spiderMonkeys[j]);
for (int m = 0; m < varNum; m++) {
if (random.nextDouble() <= LLDP_PR) {
tempSpiderMonkey.curVars[m] = lb[m] + random.nextDouble() * (ub[m] - lb[m]);
} else {
double moveDist = random.nextDouble() * (bestSpiderMonkey.curVars[m] - tempSpiderMonkey.curVars[m])
+ random.nextDouble() * (spiderMonkeys[random.nextInt(spiderMonkeys.length)].curVars[m] - tempSpiderMonkey.curVars[m]);
moveSpiderMonkey(tempSpiderMonkey, m, moveDist);
}
}
tempSpiderMonkey.curObjValue = getObjValue(tempSpiderMonkey.curVars);
tempSpiderMonkey.fit = 1 / tempSpiderMonkey.curObjValue;
if(greedy){
if(tempSpiderMonkey.fit > spiderMonkeys[j].fit){
spiderMonkeys[j] = tempSpiderMonkey;
}
}else{
spiderMonkeys[j] = tempSpiderMonkey;
}
}
}
for (int j = 0; j < spiderMonkeys.length; j++) {
for (int m = 0; m < spiderMonkeys[j].curVars.length; m++) {
positionArr[curC][c][m] = spiderMonkeys[j].curVars[m];
}
c++;
}
}
curC++;
}
// 局部领导者学习阶段（如果局部领导者有更新，则localLimitCount=0，否则localLimitCount++）
private void LLLP() {
for (int i = 0; i < spiderMonkeyList.size(); i++) {
boolean isUpdate = false;
for (SpiderMonkey spiderMonkey : spiderMonkeyList.get(i)) {
if (localLeaderList.get(i).fit < spiderMonkey.fit) {
localLeaderList.set(i, copySpiderMonkey(spiderMonkey));
isUpdate = true;
}
}
if (isUpdate) {
localLimitCount[i] = 0;
} else {
localLimitCount[i]++;
}
}
}
// 全局领导者学习阶段（如果全局领导者有更新，则globalLimitCount=0，否则globalLimitCount++）
private void GLLP() {
boolean isUpdate = false;
for (int i = 0; i < spiderMonkeyList.size(); i++) {
for (SpiderMonkey spiderMonkey : spiderMonkeyList.get(i)) {
if (spiderMonkey.fit > bestSpiderMonkey.fit) {
bestSpiderMonkey = copySpiderMonkey(spiderMonkey);
isUpdate = true;
}
}
}
if (isUpdate) {
globalLimitCount = 0;
} else {
globalLimitCount++;
}
}
// 全局领导者阶段（GLP：轮盘赌，随机选取，偏向于对fit值大的蜘蛛猴进行更新）
private void GLP() {
int c = 0;
for (int i = 0; i < spiderMonkeyList.size(); i++) {
SpiderMonkey[] spiderMonkeys = spiderMonkeyList.get(i);
// 计算fit总和
double totalFit = 0;
for (SpiderMonkey spiderMonkey : spiderMonkeys) {
totalFit += spiderMonkey.fit;
}
// 轮盘赌的累计概率数组
double[] p = new double[spiderMonkeys.length];
for (int j = 0; j < p.length; j++) {
p[j] = (spiderMonkeys[j].fit / totalFit) + (j == 0 ? 0 : p[j - 1]);
}
// 局部搜索
for (int j = 0; j < localSearchCount; j++) {
double r = random.nextDouble();
for (int k = 0; k < p.length; k++) {
if (r <= p[k]) {
for (int m = 0; m < varNum; m++) {
double moveDist = random.nextDouble() * (bestSpiderMonkey.curVars[m] - spiderMonkeys[k].curVars[m])
+ (random.nextDouble() - 0.5) * 2 * (spiderMonkeys[random.nextInt(spiderMonkeys.length)].curVars[m] - spiderMonkeys[k].curVars[m]);
moveSpiderMonkey(spiderMonkeys[k], m, moveDist);
}
spiderMonkeys[k].curObjValue = getObjValue(spiderMonkeys[k].curVars);
spiderMonkeys[k].fit = 1 / spiderMonkeys[k].curObjValue;
break;
}
}
}
for (int j = 0; j < spiderMonkeys.length; j++) {
for (int m = 0; m < spiderMonkeys[j].curVars.length; m++) {
positionArr[curC][c][m] = spiderMonkeys[j].curVars[m];
}
c++;
}
spiderMonkeyList.set(i, spiderMonkeys);
}
curC++;
}
// 局部领导者阶段（LLP：所有的蜘蛛猴都有机会更新自己）
private void LLP() {
int c = 0;
for (int i = 0; i < spiderMonkeyList.size(); i++) {
SpiderMonkey[] spiderMonkeys = spiderMonkeyList.get(i);
SpiderMonkey localLeader = localLeaderList.get(i);
for (int j = 0; j < spiderMonkeys.length; j++) {
// 以一定几率更新自己
if (random.nextDouble() <= LLP_PR) {
SpiderMonkey tempSpiderMonkey = copySpiderMonkey(spiderMonkeys[j]);
for (int m = 0; m < varNum; m++) {
double moveDist = random.nextDouble() * (localLeader.curVars[m] - tempSpiderMonkey.curVars[m])
+ (random.nextDouble() - 0.5) * 2 * (spiderMonkeys[random.nextInt(spiderMonkeys.length)].curVars[m] - tempSpiderMonkey.curVars[m]);
moveSpiderMonkey(tempSpiderMonkey, m, moveDist);
}
tempSpiderMonkey.curObjValue = getObjValue(tempSpiderMonkey.curVars);
tempSpiderMonkey.fit = 1 / tempSpiderMonkey.curObjValue;
if(greedy){
if(tempSpiderMonkey.fit > spiderMonkeys[j].fit){
spiderMonkeys[j] = tempSpiderMonkey;
}
}else{
spiderMonkeys[j] = tempSpiderMonkey;
}
}
for (int m = 0; m < spiderMonkeys[j].curVars.length; m++) {
positionArr[curC][c][m] = spiderMonkeys[j].curVars[m];
}
c++;
}
spiderMonkeyList.set(i, spiderMonkeys);
}
curC++;
}
// 初始化蜘蛛猴种群
private void initSpiderMonkeys() {
positionArr = new double[3 * maxGen][spiderMonkeyNum][varNum];
SpiderMonkey[] spiderMonkeys = new SpiderMonkey[spiderMonkeyNum];
SpiderMonkey localLeader = null;
for (int i = 0; i < spiderMonkeyNum; i++) {
spiderMonkeys[i] = getRandomSpiderMonkey();
if (i == 0) {
bestSpiderMonkey = copySpiderMonkey(spiderMonkeys[0]);
localLeader = copySpiderMonkey(spiderMonkeys[0]);
} else {
if (bestSpiderMonkey.fit < spiderMonkeys[i].fit) {
bestSpiderMonkey = copySpiderMonkey(spiderMonkeys[i]);
localLeader = copySpiderMonkey(spiderMonkeys[0]);
}
}
}
spiderMonkeyList.add(spiderMonkeys);
localLeaderList.add(localLeader);
}
// 获取一个随机生成的蜘蛛猴
SpiderMonkey getRandomSpiderMonkey() {
double[] vars = new double[varNum];
for (int j = 0; j < vars.length; j++) {
vars[j] = lb[j] + random.nextDouble() * (ub[j] - lb[j]);
}
double objValue = getObjValue(vars);
return new SpiderMonkey(vars.clone(), objValue, 1 / objValue);
}
// 控制spiderMonkey在第m个维度上移动n个距离
public void moveSpiderMonkey(SpiderMonkey spiderMonkey, int m, double n) {
// 移动
spiderMonkey.curVars[m] += n;
// 超出定义域的判断
if (spiderMonkey.curVars[m] < lb[m]) {
spiderMonkey.curVars[m] = lb[m];
}
if (spiderMonkey.curVars[m] > ub[m]) {
spiderMonkey.curVars[m] = ub[m];
}
}
/**
* @param vars 自变量数组
* @return 返回目标函数值
*/
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;
}
// 复制蜘蛛猴
SpiderMonkey copySpiderMonkey(SpiderMonkey old) {
return new SpiderMonkey(old.curVars.clone(), old.curObjValue, old.fit);
}
}可视化代码
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：2022/6/6/18:31
* @Email：1187560563@qq.com
* @Blog：https://blog.csdn.net/weixin_51545953?type=blog
*/
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 {
// 调用算法获取绘图数据
SMO_Solver solver = new SMO_Solver();
solver.solve();
positionArr = solver.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);
}
}
}优化流程（图太大了，所以放最后...）
