【运筹优化】结合天际线启发式的遗传算法求解二维矩形装箱问题 + Java代码实现

---

【运筹优化】求解二维矩形装箱问题的算法合辑（Java代码实现）

一、天际线启发式

关于天际线启发式的介绍请看我的另一篇博客：【运筹优化】基于堆优化的天际线启发式算法和复杂的评分策略求解二维矩形装箱问题 + Java代码实现

二、遗传算法结合天际线启发式

遗传算法结合天际线启发式其实很简单，只需要将序列对应成一个矩形集合，传给天际线启发式算法进行求解即可。
也就是说，天际线启发式其实就是这类启发式算法的解码器（评价函数）。

三、Java代码实现

3.1 项目结构

红框以外的代码文件在上面说的博客里有，本博客只给 Run 、GA和Genome 的代码

3.2 Genome

/**
 * @Author：WSKH
 * @ClassName：Genome
 * @ClassType：
 * @Description：
 * @Date：2022/6/4/12:55
 * @Email：1187560563@qq.com
 * @Blog：https://blog.csdn.net/weixin_51545953?type=blog
 */
public class Genome {

    // 边界的宽
    private double W;
    // 边界的高
    private double H;
    // 矩形数组
    private Item[] items;
    // 是否可以旋转
    private boolean isRotateEnable;

    //基因序列
    private int[] genomeArray;
    // 适应度函数值(在二维装箱问题中，其实就是装载利用率)
    private double fitness;
    // 序列对应的装载结果
    private Solution solution;

    /**
     * @param w 边界宽度
     * @param h 边界高度
     * @param items 矩形集合
     * @param isRotateEnable 是否可以旋转
     * @param genomeArray 基因序列
     * @Description 基因对象的构造函数
     */
    public Genome(double w, double h, Item[] items, boolean isRotateEnable, int[] genomeArray) {
        W = w;
        H = h;
        this.items = items;
        this.isRotateEnable = isRotateEnable;
        this.genomeArray = genomeArray;
    }

    /**
     * @Description 获取适应值和路径长度
     */
    public void updateFitnessAndSolution() {
        Item[] items = new Item[this.items.length];
        for (int i = 0; i < genomeArray.length; i++) {
            items[i] = this.items[genomeArray[i]];
        }
        solution = new SkyLinePacking(isRotateEnable, W, H, items).packing();
        fitness = solution.getRate();
    }

    public double getW() {
        return W;
    }

    public void setW(double w) {
        W = w;
    }

    public double getH() {
        return H;
    }

    public void setH(double h) {
        H = h;
    }

    public Item[] getItems() {
        return items;
    }

    public void setItems(Item[] items) {
        this.items = items;
    }

    public boolean isRotateEnable() {
        return isRotateEnable;
    }

    public void setRotateEnable(boolean rotateEnable) {
        isRotateEnable = rotateEnable;
    }

    public int[] getGenomeArray() {
        return genomeArray;
    }

    public void setGenomeArray(int[] genomeArray) {
        this.genomeArray = genomeArray;
    }

    public double getFitness() {
        return fitness;
    }

    public void setFitness(double fitness) {
        this.fitness = fitness;
    }

    public Solution getSolution() {
        return solution;
    }

    public void setSolution(Solution solution) {
        this.solution = solution;
    }
}
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

3.3 GA

/**
 * @Author：WSKH
 * @ClassName：GA
 * @ClassType：
 * @Description：
 * @Date：2022/6/4/12:55
 * @Email：1187560563@qq.com
 * @Blog：https://blog.csdn.net/weixin_51545953?type=blog
 */
public class GA {

    // 最大的迭代次数
    private int MAX_GEN;
    // 种群数量信息
    private int popSize;
    // 变异对换次数
    private double variationExchangeCount;
    // 复制最优解的次数(选择种群的最优个体，然后复制几次，将最优个体复制多个，存到新的集合中)
    int cloneNumOfBestIndividual;
    // 基因突变概率
    private double mutationRate;
    // 基因交叉概率
    private double crossoverRate;

    // 种群总的适应度数值
    private double totalFitness;
    // 最好的适应度的对应的染色体(基因序列、路径序列)
    private Genome bestGenome;
    // 放置所有的种群基因信息
    private List<Genome> population = new ArrayList<>();
    // 新一代的种群基因信息
    private List<Genome> newPopulation = new ArrayList<>();
    // 遗传的代数(第几代)
    private int t = 0;
    // 最佳迭代次数
    private int bestT = -1;
    // 随机函数对象
    public Random random;
    // 各个个体的累积概率
    double[] probabilitys;

    // 矩形数量
    int itemNum;
    // 边界的宽
    private double W;
    // 边界的高
    private double H;
    // 矩形数组
    Item[] items;
    // 是否可以旋转
    private boolean isRotateEnable;

    /**
     * @param MAX_GEN                  迭代次数(提高这个值可以稳定地提高解质量，但是会增加求解时间)
     * @param popSize                  种群大小
     * @param variationExchangeCount   变异时的两两对换次数
     * @param cloneNumOfBestIndividual 复制最优解的次数(一般小于种群数量的5%，选择种群的最优个体，然后复制几次，将最优个体复制多个，存到新的集合中，有助于保持优良基因)
     * @param mutationRate             基因突变概率
     * @param crossoverRate            基因交叉概率
     * @param instance                 实例对象
     * @param seed                     随机数种子，如果传入null则不设置随机数种子，否则按照传入的种子进行设置，方便复现结果
     * @Description 遗传算法的构造函数
     */
    public GA(int MAX_GEN, int popSize, int variationExchangeCount, int cloneNumOfBestIndividual, double mutationRate, double crossoverRate, Instance instance, Long seed) {
        this.MAX_GEN = MAX_GEN;
        this.popSize = popSize;
        this.variationExchangeCount = variationExchangeCount;
        this.cloneNumOfBestIndividual = cloneNumOfBestIndividual;
        this.mutationRate = mutationRate;
        this.crossoverRate = crossoverRate;
        this.W = instance.getW();
        this.H = instance.getH();
        this.isRotateEnable = instance.isRotateEnable();
        this.items = Item.copy(instance.getItemList().toArray(new Item[0]));
        this.random = seed == null ? new Random() : new Random(seed);
    }

    /**
     * @return 最佳装载结果对象Solution
     * @Description 遗传算法主函数
     */
    public Solution solve() {
        initVar();
        while (t < MAX_GEN) {
            popSize = population.size();
            // 基因进化
            evolution();
            // 更新种群
            population = copyGenomeList(newPopulation);
            t++;
        }
        return bestGenome.getSolution();
    }

    /**
     * @Description 进化函数，正常交叉变异
     */
    public void evolution() {
        //更新累积概率和总适应度
        updateProbabilityAndTotalFitness();
        // 挑选某代种群中适应度最高的个体
        selectBestGenomeAndJoinNext();
        // 赌轮选择策略对剩下的scale-1个个体进行随机的交叉，变异
        while (newPopulation.size() < population.size()) {
            double r = random.nextDouble();
            for (int j = 0; j < probabilitys.length; j++) {
                if (compareDouble(r, probabilitys[j]) != 1) {
                    newPopulation.add(population.get(j));
                    break;
                }
            }
        }
        // 交叉
        if (compareDouble(random.nextDouble(), crossoverRate) != 1) {
            int r = random.nextInt(popSize);
            int k = random.nextInt(popSize);
            while (r == k) {
                r = random.nextInt(popSize);
            }
            cross(k, r);
        }
        // 变异
        for (int i = 0; i < population.size(); i++) {
            if (compareDouble(random.nextDouble(), mutationRate) != 1) {
                variation(i);
            }
        }
    }

    /**
     * @param k1 基因1的索引
     * @param k2 基因2的索引
     * @Description 对基因1和基因2进行单点映射交叉
     */
    private void cross(int k1, int k2) {
        // 获取要交叉的两个基因
        int[] genomeArray1 = newPopulation.get(k1).getGenomeArray();
        int[] genomeArray2 = newPopulation.get(k2).getGenomeArray();
        // 找到交叉位置
        int crossIndex = random.nextInt(itemNum);
        // 获取交叉片段
        for (int i = 0; i <= crossIndex; i++) {
            int temp = genomeArray1[i];
            genomeArray1[i] = genomeArray2[i];
            genomeArray2[i] = temp;
        }
        // 找到重复基因
        HashSet<Integer> set = new HashSet<>();
        // 
        HashMap<Integer, Integer> repeatMap = new HashMap<>();
        for (int i = 0; i < genomeArray1.length; i++) {
            if (!set.add(genomeArray1[i])) {
                repeatMap.put(i, genomeArray1[i]);
            }
        }
        set.clear();
        for (int i = 0; i < genomeArray2.length; i++) {
            if (!set.add(genomeArray2[i])) {
                for (int key : repeatMap.keySet()) {
                    genomeArray1[key] = genomeArray2[i];
                    genomeArray2[i] = repeatMap.get(key);
                    repeatMap.remove(key);
                    break;
                }
            }
        }
        // 交叉完毕，将基因放回个体，再将个体放回种群，并更新他们的适应值和路径长度
        newPopulation.get(k1).setGenomeArray(genomeArray1);
        newPopulation.get(k1).updateFitnessAndSolution();
        newPopulation.get(k2).setGenomeArray(genomeArray2);
        newPopulation.get(k2).updateFitnessAndSolution();
    }

    /**
     * @param k 要进行变异的基因索引
     * @Description 变异(n次两两对换)
     */
    private void variation(int k) {
        Genome genome = newPopulation.get(k);
        int[] genomeArray = genome.getGenomeArray();
        for (int i = 0; i < variationExchangeCount; i++) {
            int r1 = random.nextInt(itemNum);
            int r2 = random.nextInt(itemNum);
            while (r1 == r2) {
                r2 = random.nextInt(itemNum);
            }
            //交换
            int temp = genomeArray[r1];
            genomeArray[r1] = genomeArray[r2];
            genomeArray[r2] = temp;
        }
        //将变异后的基因序列放回个体
        genome.setGenomeArray(genomeArray);
        // 更新基因的适应值和路程长度
        genome.updateFitnessAndSolution();
        //将变异后的个体放回种群
        newPopulation.set(k, genome);
    }

    /**
     * @Description 初始化函数，进行一些初始化操作
     */
    public void initVar() {
        this.itemNum = this.items.length;
        this.population = new ArrayList<>();
        //初始化种群信息
        List<Integer> sequence = new ArrayList<>();
        for (int i = 0; i < itemNum; i++) {
            sequence.add(i);
        }
        for (int i = 0; i < popSize; i++) {
            Collections.shuffle(sequence);
            int[] initSequence = new int[itemNum];
            for (int j = 0; j < sequence.size(); j++) {
                initSequence[j] = sequence.get(j);
            }
            Genome genome = new Genome(W, H, items, isRotateEnable, initSequence.clone());
            genome.updateFitnessAndSolution();
            population.add(genome);
        }
        bestGenome = copyGenome(population.get(0));
        for (int i = 1; i < popSize; i++) {
            Genome genome = population.get(i);
            if (bestGenome.getFitness() < genome.getFitness()) {
                bestGenome = copyGenome(genome);
            }
        }
        System.out.println("初始解为：" + bestGenome.getSolution().getRate());
    }

    /**
     * @Description 挑选种群中适应度最大的个体基因，并复制n份，直接加入下一代种群
     */
    public void selectBestGenomeAndJoinNext() {
        newPopulation = new ArrayList<>();
        Genome tempBest = population.get(0);
        for (int i = 1; i < population.size(); i++) {
            if (population.get(i).getFitness() > tempBest.getFitness()) {
                tempBest = population.get(i);
            }
        }
        if (compareDouble(tempBest.getFitness(), bestGenome.getFitness()) == 1) {
            bestGenome = copyGenome(tempBest);
            bestT = t;
            System.out.println("当前代数: " + t + " : " + bestGenome.getSolution().getRate());
        }
        for (int i = 0; i < cloneNumOfBestIndividual; i++) {
            newPopulation.add(copyGenome(tempBest));
        }
    }

    /**
     * @Description 更新各个个体的累积概率和种群总适应度
     */
    public void updateProbabilityAndTotalFitness() {
        probabilitys = new double[population.size()];
        totalFitness = 0;
        for (Genome genome : population) {
            totalFitness += genome.getFitness();
        }
        double rate = 0.0;
        for (int i = 0; i < population.size(); i++) {
            rate += (population.get(i).getFitness() / totalFitness);
            probabilitys[i] = rate;
        }
    }

    /**
     * @param genome 模板基因
     * @return 返回拷贝好的基因
     * @Description 根据传入的模板基因，进行拷贝，返回拷贝好的基因
     */
    public Genome copyGenome(Genome genome) {
        Genome copy = new Genome(genome.getW(), genome.getH(), genome.getItems(), genome.isRotateEnable(), genome.getGenomeArray().clone());
        copy.setSolution(genome.getSolution());
        copy.setFitness(genome.getFitness());
        return copy;
    }

    /**
     * @param genomeList 模板基因集合
     * @return 返回拷贝好的基因集合
     * @Description 根据传入的模板基因集合，进行拷贝，返回拷贝好的基因集合
     */
    public List<Genome> copyGenomeList(List<Genome> genomeList) {
        List<Genome> copyList = new ArrayList<>();
        for (Genome genome : genomeList) {
            copyList.add(copyGenome(genome));
        }
        return copyList;
    }

    /**
     * @param d1 双精度浮点型变量1
     * @param d2 双精度浮点型变量2
     * @return 返回0代表两个数相等，返回1代表前者大于后者，返回-1代表前者小于后者，
     * @Description 判断两个双精度浮点型变量的大小关系
     */
    private int compareDouble(double d1, double d2) {
        // 定义一个误差范围，如果两个数相差小于这个误差，则认为他们是相等的 1e-06 = 0.000001
        double error = 1e-06;
        if (Math.abs(d1 - d2) < error) {
            return 0;
        } else if (d1 < d2) {
            return -1;
        } else if (d1 > d2) {
            return 1;
        } else {
            throw new RuntimeException("d1 = " + d1 + " , d2 = " + d2);
        }
    }

}
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
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313

3.4 Run

/**
 * @Author：WSKH
 * @ClassName：Run
 * @ClassType：
 * @Description：运行程序的主类
 * @Date：2022/11/6/19:39
 * @Email：1187560563@qq.com
 * @Blog：https://blog.csdn.net/weixin_51545953?type=blog
 */
public class Run extends javafx.application.Application {

    private int counter = 0;

    @Override
    public void start(Stage primaryStage) throws Exception {

        // 数据地址
        String path = "src/main/java/com/wskh/data/data.txt";
        // 根据txt文件获取实例对象
        Instance instance = new ReadDataUtil().getInstance(path);
        // 记录算法开始时间
        long startTime = System.currentTimeMillis();
        // 实例化遗传算法对象
        GA ga = new GA(1000, 300, 1, 10, 0.6, 0.98, instance, null);
        // 调用遗传算法对象进行求解
        Solution solution = ga.solve();
        // 输出相关信息
        System.out.println("------------------------------------------------------------------------------------");
        System.out.println("求解用时:" + (System.currentTimeMillis() - startTime) / 1000.0 + " s");
        System.out.println("共放置了矩形" + solution.getPlaceItemList().size() + "个");
        System.out.println("最佳利用率为:" + solution.getRate());
        // 输出画图数据
        String[] strings1 = new String[solution.getPlaceItemList().size()];
        String[] strings2 = new String[solution.getPlaceItemList().size()];
        for (int i = 0; i < solution.getPlaceItemList().size(); i++) {
            PlaceItem placeItem = solution.getPlaceItemList().get(i);
            strings1[i] = "{x:" + placeItem.getX() + ",y:" + placeItem.getY() + ",l:" + placeItem.getH() + ",w:" + placeItem.getW() + "}";
            strings2[i] = placeItem.isRotate() ? "1" : "0";
        }
        System.out.println("data:" + Arrays.toString(strings1) + ",");
        System.out.println("isRotate:" + Arrays.toString(strings2) + ",");

        // --------------------------------- 后面这些都是画图相关的代码，可以不用管 ---------------------------------------------
        AnchorPane pane = new AnchorPane();
        Canvas canvas = new Canvas(instance.getW(), instance.getH());
        pane.getChildren().add(canvas);
        canvas.relocate(100, 100);
        // 绘制最外层的矩形
        canvas = draw(canvas, 0, 0, instance.getW(), instance.getH(), true);
        // 添加按钮
        Button nextButton = new Button("Next +1");
        Canvas finalCanvas = canvas;
        nextButton.setOnAction(new EventHandler<ActionEvent>() {
            @Override
            public void handle(ActionEvent actionEvent) {
                try {
                    PlaceItem placeItem = solution.getPlaceItemList().get(counter);
                    draw(finalCanvas, placeItem.getX(), placeItem.getY(), placeItem.getW(), placeItem.getH(), false);
                    counter++;
                } catch (Exception e) {
                    Alert alert = new Alert(Alert.AlertType.WARNING);
                    alert.setContentText("已经没有可以放置的矩形了！");
                    alert.showAndWait();
                }
            }
        });
        //
        pane.getChildren().add(nextButton);
        primaryStage.setTitle("二维矩形装箱可视化");
        primaryStage.setScene(new Scene(pane, 1000, 1000, Color.AQUA));
        primaryStage.show();
    }

    private Canvas draw(Canvas canvas, double x, double y, double l, double w, boolean isBound) {
        GraphicsContext gc = canvas.getGraphicsContext2D();
        // 边框
        gc.setStroke(Color.BLACK);
        gc.setLineWidth(2);
        gc.strokeRect(x, y, l, w);
        // 填充
        if (!isBound) {
            gc.setFill(new Color(new Random().nextDouble(), new Random().nextDouble(), new Random().nextDouble(), new Random().nextDouble()));
        } else {
            gc.setFill(new Color(1, 1, 1, 1));
        }
        gc.fillRect(x, y, l, w);
        return canvas;
    }

    public static void main(String[] args) {
        launch(args);
    }

}
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

3.5 运行结果展示

输出（最后两行是在前端画图用的，可以忽略）：

初始解为：0.98811875
当前代数: 1 : 0.990175
当前代数: 2 : 0.99215625
当前代数: 24 : 0.99268125
当前代数: 25 : 0.9942
当前代数: 31 : 0.99455625
当前代数: 34 : 0.99494375
当前代数: 37 : 0.99585
当前代数: 702 : 0.9977375
当前代数: 710 : 0.9986375
------------------------------------------------------------------------------------
求解用时:17.21 s
共放置了矩形26个
最佳利用率为:0.9986375
data:[{x:0.0,y:0.0,l:100.0,w:113.0}, {x:113.0,y:0.0,l:100.0,w:108.0}, {x:283.0,y:0.0,l:29.0,w:117.0}, {x:221.0,y:0.0,l:51.0,w:62.0}, {x:283.0,y:29.0,l:40.0,w:117.0}, {x:221.0,y:51.0,l:60.0,w:62.0}, {x:283.0,y:69.0,l:80.0,w:117.0}, {x:0.0,y:100.0,l:85.0,w:113.0}, {x:113.0,y:100.0,l:21.0,w:108.0}, {x:221.0,y:111.0,l:38.0,w:62.0}, {x:113.0,y:121.0,l:64.0,w:107.0}, {x:220.0,y:149.0,l:49.0,w:63.0}, {x:283.0,y:149.0,l:71.0,w:117.0}, {x:0.0,y:185.0,l:116.0,w:113.0}, {x:113.0,y:185.0,l:117.0,w:107.0}, {x:220.0,y:198.0,l:65.0,w:63.0}, {x:321.0,y:220.0,l:118.0,w:79.0}, {x:283.0,y:220.0,l:71.0,w:38.0}, {x:220.0,y:263.0,l:41.0,w:63.0}, {x:287.0,y:291.0,l:47.0,w:34.0}, {x:0.0,y:301.0,l:99.0,w:26.0}, {x:26.0,y:301.0,l:99.0,w:79.0}, {x:105.0,y:302.0,l:98.0,w:96.0}, {x:201.0,y:304.0,l:96.0,w:84.0}, {x:285.0,y:338.0,l:61.0,w:24.0}, {x:309.0,y:338.0,l:62.0,w:91.0}],
isRotate:[0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0],
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

可视化展示（利用率 99.86%）

顺便说一下，这个结果是我偶然跑出来的，后面再跑，跑了好久才复现出来，能找到这个结果也是偶然，不一定是算法强~