饥饿游戏搜索算法（HGS）（含java实现代码）

Hunger games search: Visions, conception, implementation, deep analysis, perspectives, and towards performance shifts

期刊:Expert Systems With Applications SCI1区

主体框架

    public HGS(){
        initialize();
        calculateFitness();
        sortTheFitness();
        calculateHungry();

        for (t = 0;t<T;t++){
            UpdateWeight();
            UpdateLocation();
            calculateFitness();
            sortTheFitness();
            calculateHungry();
            savePoints();
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

ps：经过多次的复现以后，我发现实现一个算法最快的方式就是先将算法分模块搞好，所以上来先贴一个框架图。

在这里插入图片描述

这篇论文主要分为四个模块，分别是初始化模块，适应度与饥饿值设置模块，权重更新模块，位置更新模块。

论文有意思的点：

在这篇文章里面的公式非常的多，但是在这里我只想着重介绍这篇论文的创新点：饥饿机制。

文章定义了一个叫饥饿值的东西，如下公式所示。我们发现当且仅当i适应度值最小的时候，饥饿值为0，别的情况饥饿值为上次的饥饿值加上H。也就是说，只要适应度高，那么就会越来越饥饥饿。后面我们再说这个饥饿度怎么用。值得注意的是：每一轮迭代都会更新一次hungry值

$\text { hungry }(i)=\left\{0, AllFitness (i)==BF hungry (i)+H, AllFitness (i)!=BF$

0, AllFitness (i) = = B F hungry (i) + H, AllFitness (i)! = B F

\right.

hungry (i) = {0, AllFitness (i) == BF hungry (i) + H, AllFitness (i)! = BF

其中 $BF$ 为最差的适应度，也就是最小的适应度值。 $H$ 的定义如下所示

$TH=F(i)−BFWF−BF×r6×2×(UB−LB)H={LH×(1+r),TH<LHTH,TH≥LH$

T H = \frac{F ( i ) - BF}{W F - BF} \times r_{6} \times 2 \times (U B - L B) H = {L H \times (1 + r), T H < L H T H, T H \geq L H

其中 $F (i)$ 为适应度值， $W F$ (Worse Fitness)为最大的适应度值（至今为止）， $U B 和 L B$ 为问题空间的上下界。 $L H$ (Limit Hungry)则为饥饿感的下限，r是一个随机值。

也就是说当适应度值 $F (i)$ 越小的时候， $T H$ （Temp Hungry）会越小，当低于上限的时候，本轮增加的饥饿度 $H$ ，将会被设置为大于 $T H$ 的一个随机值。

我们从上面的三个公式只要知道一个关键结论就好了：

适应度越小，越不饥饿。

适应度越大，这轮增加的饥饿度越高。

那么这个饥饿度值该怎么用呢？

$\overrightarrow{W_1(i)}=\left\{ hungry (i)⋅N SHungry ×r4,r3<l1，r3>l$

\right.

W_{1} (i) = {hungry (i) \cdot \frac{N}{SHungry} \times r_{4}, r_{3} < l 1 ， r_{3} > l

$\overrightarrow{W_2(i)}=(1-\exp (-\mid \text { hungry }(i)-\text { SHungry } \mid)) \times r_5 \times 2$

论文构建了两个向量，分别是 $W_1(i),W_2(i)$ ，这两个向量负责对个体进行变异，这里最关键的点是 $S H u n g ry$ ，这是所有 $h u n g ry$ 的总和，我们可以发现，两个向量组的规律。

对于 $W_1(i)$ 而言，hungry越小，里面的值越小

对于 $W_2(i)$ 而言，hungry越小，里面的值越接近2也就是说里面的值越大。

$\overrightarrow{X(t+1)}=\left\{ Game 1:→X(t)⋅(1+randn(1)),r1<l Game 2:→W1⋅→Xb+→R⋅→W2⋅|→Xb−→X(t)|,r1>l,r2>E Game 3:→W1⋅→Xb−→R⋅→W2⋅|→Xb−→X(t)|,r1>l,r2<E$

\right.

X (t + 1) = ⎩ ⎨ ⎧ Game_{1} : X (t) \cdot (1 + randn (1)), r_{1} < l Game_{2} : W_{1} \cdot X_{b} + R \cdot W_{2} \cdot X_{b} - X (t), r_{1} > l, r_{2} > E Game_{3} : W_{1} \cdot X_{b} - R \cdot W_{2} \cdot X_{b} - X (t), r_{1} > l, r_{2} < E

最后，每轮迭代的时候都根据上面的公式对位置进行变换，在文中，l被设置为0.08，在公式1中，其实就是一个高斯变异，烟花算法也用到这个。

公式二和三，本质上是一个DE，差分进化的两个公式都是没头脑的，就算正向学习和反向学习，很多论文也有这个。最后还有个E，这个E也是作者自己设定的一个阈值，可以参照野狗群算法，不过作者将这个搜索阈值自己自定义了：

$E=\operatorname{sech}(|F(i)-B F|)$

$\left(\operatorname{sech}(x)=\frac{2}{e^x+e^{-x}}\right)$

sech就是双曲正割函数

在这里插入图片描述

x越大，y越小，也就是说，当前解的适应度值越小，E就会越接近1，公式3被调用的概率就会变高。当前的解适应度越大，E就会越接近0，公式2被调用的概率越大。

最后再补充一个

R = 2 \times shrink \times rand - shrink shrink = 2 \times (1 - \frac{t}{T})

这个东西就是随着迭代次数，波动逐渐减少的向量，最后会收敛到0，值得注意的是R里面是有正有负的，意味着game2和game3是存在等效的情况。

实验的截图~
在这里插入图片描述

寻找sphere最小值。

实际代码

import javax.swing.*;
import java.awt.*;
import java.util.*;
import java.util.List;
import java.util.function.Consumer;

/**
 * Hunger games search: Visions, conception, implementation, deep analysis, perspectives, and towards performance shifts
 */

public class HGS {
    int N = 30;//5 10 30 50 100
    Double D;
    Double L = 0.08;
    Double H;
    Double SHungry;

    List<Double> Xb;
    double BF = Double.MAX_VALUE;
    double WF = -Double.MAX_VALUE;

    double lb = 0;
    double ub = 1;
    int dimension = 30;
    int t;
    int T = 1000;
    List<Double> R = new ArrayList<>(dimension);
    ArrayList<Point> res = new ArrayList<>();
    double LH = 10000;
    public HGS(){
        initialize();
        calculateFitness();
        sortTheFitness();
        calculateHungry();

        for (t = 0;t<T;t++){
            UpdateWeight();
            UpdateLocation();
            calculateFitness();
            sortTheFitness();
            calculateHungry();
            savePoints();
        }
    }

    public static void main(String[] args) {
        HGS hgs = new HGS();
        ArrayList<Point> points = hgs.res;

        // 创建绘制折线图的窗口
        JFrame frame = new JFrame("折线图");
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.add(new LineChart(points));
        frame.setSize(800, 600);
        frame.setLocationRelativeTo(null);
        frame.setVisible(true);
    }
    public void savePoints(){
        System.out.println("curt:"+t+",BF="+BF);
        res.add(new Point(t,(int)(BF*100000)));
    }
    List<Individual> individuals = new ArrayList<>();
    public void initialize(){
        IndividualFactory individualFactory = new IndividualFactory(dimension,lb,ub);
        individuals = individualFactory.getRandomIndividuals(N);
        t = 0;
    }
    public void calculateFitness(){
        for (Individual i:
             individuals) {
            i.UpDateFitness();
        }
    }
    public void sortTheFitness(){
        individuals.sort((a,b)->new Double(a.fitness).compareTo(b.fitness));//按照适应度排序

        WF = Math.max(WF,individuals.get(N-1).fitness);
        if(BF>individuals.get(0).fitness){
            BF = individuals.get(0).fitness;
            Xb = new ArrayList<>(individuals.get(0).position);//copy一份
        }
        BF = Math.min(BF,individuals.get(0).fitness);
    }
    public void calculateHungry(){
        for (Individual i:
             individuals) {
            if(i.fitness==BF){
                i.hungry = 0;
            }else {
                double r6 = Math.random();
                Double TH = (i.fitness-BF)/(WF-BF)*r6*2*(ub-lb);
                Double H;
                if(TH<LH){
                    H = LH*(1+Math.random());
                }else {
                    H = TH;
                }

                i.hungry = i.hungry+H;
            }
        }
    }
    public void UpdateWeight(){
        double SHungry = 0;
        for (Individual i:
             individuals) {
            SHungry+=i.hungry;
        }
        for (Individual i:
             individuals) {
            i.updateW(N,SHungry,L);
        }
    }
    public void UpdateLocation(){
        for (Individual i:
             individuals) {
            i.upDateLocation(L,t,T,Xb,BF);
        }
    }
}

class Individual{
    double hungry;

    double fitness;
    double lb;
    double ub;
    List<Double> position = new ArrayList<>();
    List<Double> w1;
    List<Double> w2;
    int dimension;

    public double getHungry() {
        return hungry;
    }

    public void setHungry(double hungry) {
        this.hungry = hungry;
    }

    public Individual(double lb, double ub, List<Double> position) {
        this.lb = lb;
        this.ub = ub;
        this.position = position;
        dimension = position.size();
        w1 = new ArrayList<>(dimension);
        w2 = new ArrayList<>(dimension);
        for (int i = 0; i < dimension; i++) {
            w1.add(0.0);
            w2.add(0.0);
        }
    }

    public void Game1(){
        //formula 2.1
        Random random = new Random();
        for (int i = 0; i < dimension; i++) {
            double originX = position.get(i);
            position.set(i,originX*(1+random.nextGaussian()));
        }
    }
    public void Game2(List<Double> R,List<Double> Xb){
        //formula 2.1
        for (int i = 0; i < dimension; i++) {
            position.set(i,w1.get(i)*Xb.get(i)+R.get(i)*w2.get(i)*Math.abs(Xb.get(i)-this.position.get(i)));
        }
    }
    public void Game3(List<Double> R,List<Double> Xb){
        //formula 2.1
        for (int i = 0; i < dimension; i++) {
            position.set(i,w1.get(i)*Xb.get(i)-R.get(i)*w2.get(i)*Math.abs(Xb.get(i)-this.position.get(i)));
        }
    }
    public void upDateLocation(double l,int t,int T,List<Double> Xb,double BF){
        double r1 = Math.random();
        double r2 = Math.random();
        if(r1<l){
            Game1();
        }else{
            List<Double> R = new ArrayList<>(dimension);
            for (int i = 0; i < dimension; i++) {
                R.add(0.0);
            }
            double shrink = 2.0*(1.0-t/T);
            for (int i = 0; i < dimension; i++) {
                R.set(i,2*shrink*Math.random()-shrink);
            }
            double E = sech(Math.abs(fitness-BF));
            if(r2>E){
                Game2(R,Xb);
            }else {
                Game3(R,Xb);
            }
        }
    }
    public static double sech(double x){
        return 2.0/(Math.exp(x)+Math.exp(-x));
    }
    public void updateW(int N,double SHungry,double l){
        for (int i = 0; i < dimension; i++) {
            //formula 2.6
            double r3 = Math.random();
            double r4 = Math.random();
            if (r3<l){
                w1.set(i,hungry*N/SHungry*r4);
            }else {
                w1.set(i,1.0);
            }
            double r5 = Math.random();
            //formula 2.6
            w2.set(i,(1-Math.exp(-Math.abs(hungry-SHungry)))*r5*2);
        }
    }
    public void UpDateFitness(){
        this.fitness = Sphere(this.position);
    }
    public static double Sphere(List<Double> x){
        double sum = 0;
        for (int i = 0; i < x.size(); i++) {
            sum += x.get(i)*x.get(i);
        }
        return sum;//修正函数
    }
}
class IndividualFactory{
    Random random = new Random();
    private int dimension;
    private double lb;
    private double ub;
    public IndividualFactory(int dimension,double lb,double ub){
        this.dimension = dimension;
        this.lb = lb;
        this.ub = ub;
    }
    public Individual getRandom(){
        List<Double> Position = new ArrayList<>(dimension);
        for (int i = 0; i < dimension; i++) {
            Position.add(lb+(ub-lb)*random.nextDouble());
        }
        Individual individual = new Individual(lb,ub,Position);
        individual.UpDateFitness();
        return individual;
    }
    public List<Individual> getRandomIndividuals(int N){
        List<Individual> individuals = new ArrayList<>(N);
        for (int i = 0; i < N; i++) {
            individuals.add(getRandom());
        }
        return individuals;
    }

}
class LineChart extends JPanel {

    private ArrayList<Point> points;

    public LineChart(ArrayList<Point> points) {
        this.points = points;
    }

    @Override
    protected void paintComponent(Graphics g) {
        super.paintComponent(g);
        Graphics2D g2d = (Graphics2D) g;
        int margin = 50; // 留出一些边距
        int width = getWidth() - 2 * margin;
        int height = getHeight() - 2 * margin;

        // 绘制坐标轴
        g2d.drawLine(margin, margin, margin, margin + height); // 垂直轴
        g2d.drawLine(margin, margin + height, margin + width, margin + height); // 水平轴

        // 计算最大和最小的x和y值
        int minX = Integer.MAX_VALUE, minY = Integer.MAX_VALUE;
        int maxX = Integer.MIN_VALUE, maxY = Integer.MIN_VALUE;
        for (Point point : points) {
            if (point.x < minX) minX = point.x;
            if (point.x > maxX) maxX = point.x;
            if (point.y < minY) minY = point.y;
            if (point.y > maxY) maxY = point.y;
        }

        // 绘制折线
        g2d.setColor(Color.BLUE);
        for (int i = 0; i < points.size() - 1; i++) {
            int x1 = margin + (points.get(i).x - minX) * width / (maxX - minX);
            int y1 = margin + height - (points.get(i).y - minY) * height / (maxY - minY);
            int x2 = margin + (points.get(i + 1).x - minX) * width / (maxX - minX);
            int y2 = margin + height - (points.get(i + 1).y - minY) * height / (maxY - minY);
            g2d.drawLine(x1, y1, x2, y2);
        }
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294

相关阅读:
MySQL 5.7安装教程（win11）
电脑定时关机
AWVS扫描web站点
C++代码示例：进制数简单生成工具
[数据结构-线性表1.1] 数组（.NET源码学习）
【scikit-learn基础】--『预处理』之缺失值处理
Edge的使用心得与深度探索
QStyleFactor和QPalette
[附源码]Python计算机毕业设计Django设备运维平台出入库模块APP
Tomcat

原文地址：https://blog.csdn.net/qq_43445553/article/details/133100679