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

文章目录

一、天际线启发式
二、自适应遗传算法结合天际线启发式
- 2.1 自适应交叉变异
- 2.2 自适应选择策略
三、Java代码实现

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

一、天际线启发式

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

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

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

2.1 自适应交叉变异

GA 中的交叉概率和变异概率对于算法的搜索能力和收敛速度有着重要影响，自AGA被提出以来，众多优秀的改进自适应遗传算法陆续被提出，自适应遗传算法采用基于Sigmoid 曲线改进的自适应遗传算子来进一步提升算法寻优能力。

$X={Xmax−Xmin1+exp(A2(v′−vavg)vmax−vavg)+Xmin,v′⩾vavgXmax,v′<vavg$
$B = ⎩ ⎨ ⎧ \frac{B _{m a x} - B _{m i n}}{1 + e x p ( A \frac{2 ( v - v _{a vg} )}{v _{m a x} - v _{a vg}} )} + B_{m i n}, v ⩾ v_{a vg} B_{m a x}, v < v_{a vg}$
上式中, $A = 9.903438, X$ 和 $B$ 分别表示交叉概率和变异概率, $X_{\max }$ 和 $X_{\min }$ 分别表示交叉概率最大值和最小值, $B_{\max }$ 和 $B_{\min }$ 分别表示变异概率最大值和最小值, $v^{\prime}$ 表示进行交叉的父母个体的适应度的较大值, $v$ 表示变异个体的适应度, $v_{\text {max }}$ 表示当代种群的最大适应度, $v_{a v g}$ 表示当代种群的平均适应度。

下面是自适应交叉和变异的代码

/**
     * @param g1   基因1
     * @param g2   基因2
     * @param vAvg 当前种群的平均适应度
     * @param vMax 当前种群的最大适应度
     * @return 返回交叉概率
     * @Description 计算自适应的交叉概率
     */
    private double calcCrossoverRate(Genome g1, Genome g2, double vAvg, double vMax) {
        // 基因1和基因2中较小的适应度
        double v = Math.min(g1.getFitness(), g2.getFitness());
        // 计算交叉概率并返回
        return (crossoverRateBoundArr[1] - crossoverRateBoundArr[0]) / (1 + Math.exp(2 * A * (v - vAvg) / (vMax - vAvg))) + crossoverRateBoundArr[0];
    }

    /**
     * @param v    当前可能变异的基因的适应度
     * @param vAvg 当前种群的平均适应度
     * @param vMax 当前种群的最大适应度
     * @return 返回变异概率
     * @Description 计算自适应的变异概率
     */
    private double calcMutationRate(double v, double vAvg, double vMax) {
        if (compareDouble(v, vAvg) != -1) {
            return (mutationRateBoundArr[1] - mutationRateBoundArr[0]) / (1 + Math.exp(2 * A * (v - vAvg) / vMax - vAvg)) + mutationRateBoundArr[0];
        } else {
            return mutationRateBoundArr[1];
        }
    }
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

2.2 自适应选择策略

自适应的选择策略可以不单单依靠个体适应度的由高到低的排序来进行选择，它会根据遗传算法的进化特征自适应的选择将要进入交叉操作的个体。

首先挑选出种群中的最小适应度函数值，然后将种群中的所有个体的适应度函数值都减去这个最小值，然后根据新的适应度函数值采用轮盘赌法进行选择。这种策略在计算的过程中就可以动态的改变每个个体的适应度值。这样，个体的生存环境改变，评判标准也应随之发生变化。

下面是自适应选择的代码（其实就是对累积概率矩阵的计算做了调整）

    /**
     * @Description 自适应更新各个个体的累积概率和种群总适应度
     */
    public void updateProbabilityAndTotalFitness() {
        probabilitys = new double[population.size()];
        totalFitness = 0;
        double minFitness = population.get(0).getFitness();
        for (Genome genome : population) {
            totalFitness += genome.getFitness();
            minFitness = Math.min(genome.getFitness(), minFitness);
        }
        totalFitness -= (minFitness * population.size());
        double rate = 0.0;
        for (int i = 0; i < population.size(); i++) {
            if (Math.abs(totalFitness) < 1e-10) {
                rate += (1d / population.size());
            } else {
                rate += ((population.get(i).getFitness() - minFitness) / totalFitness);
            }
            probabilitys[i] = rate;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

三、Java代码实现

3.1 项目结构

红框以外的代码文件在上面说的博客里有，本博客只给 Run 、AGA和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 AGA

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

    // 最大的迭代次数
    private int MAX_GEN;
    // 种群数量信息
    private int popSize;
    // 变异对换次数
    private double variationExchangeCount;
    // 复制最优解的次数(选择种群的最优个体，然后复制几次，将最优个体复制多个，存到新的集合中)
    int cloneNumOfBestIndividual;
    // 基因突变概率系上下界数组
    private double[] mutationRateBoundArr;
    // 基因交叉概率上下界数组
    private double[] crossoverRateBoundArr;
    // 某参数（论文中是这么设置的，不用改）
    private final double A = 9.903438;

    // 种群总的适应度数值
    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 mutationRateBoundArr     [最小基因突变概率，最大基因突变概率]
     * @param crossoverRateBoundArr    [最小基因交叉概率，最大基因交叉概率]
     * @param instance                 实例对象
     * @param seed                     随机数种子，如果传入null则不设置随机数种子，否则按照传入的种子进行设置，方便复现结果
     * @Description 遗传算法的构造函数
     */
    public AGA(int MAX_GEN, int popSize, int variationExchangeCount, int cloneNumOfBestIndividual, double[] mutationRateBoundArr, double[] crossoverRateBoundArr, Instance instance, Long seed) {
        this.MAX_GEN = MAX_GEN;
        this.popSize = popSize;
        this.variationExchangeCount = variationExchangeCount;
        this.cloneNumOfBestIndividual = cloneNumOfBestIndividual;
        this.mutationRateBoundArr = mutationRateBoundArr;
        this.crossoverRateBoundArr = crossoverRateBoundArr;
        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;
                }
            }
        }
        // 计算当前种群的最大适应度和平均适应度
        double vMax = population.get(0).getFitness();
        double vSum = 0;
        for (Genome genome : population) {
            vSum += genome.getFitness();
            vMax = Math.max(genome.getFitness(), vMax);
        }
        double vAvg = vSum / population.size();
        // 自适应交叉
        int r = random.nextInt(popSize);
        int k = random.nextInt(popSize);
        while (r == k) {
            r = random.nextInt(popSize);
        }
        if (compareDouble(random.nextDouble(), calcCrossoverRate(population.get(r), population.get(k), vAvg, vMax)) != 1) {
            cross(k, r);
        }
        // 自适应变异
        for (int i = 0; i < population.size(); i++) {
            if (compareDouble(random.nextDouble(), calcMutationRate(population.get(i).getFitness(), vAvg, vMax)) != 1) {
                variation(i);
            }
        }
    }

    /**
     * @param g1   基因1
     * @param g2   基因2
     * @param vAvg 当前种群的平均适应度
     * @param vMax 当前种群的最大适应度
     * @return 返回交叉概率
     * @Description 计算自适应的交叉概率
     */
    private double calcCrossoverRate(Genome g1, Genome g2, double vAvg, double vMax) {
        // 基因1和基因2中较小的适应度
        double v = Math.min(g1.getFitness(), g2.getFitness());
        // 计算交叉概率并返回
        return (crossoverRateBoundArr[1] - crossoverRateBoundArr[0]) / (1 + Math.exp(2 * A * (v - vAvg) / (vMax - vAvg))) + crossoverRateBoundArr[0];
    }

    /**
     * @param v    当前可能变异的基因的适应度
     * @param vAvg 当前种群的平均适应度
     * @param vMax 当前种群的最大适应度
     * @return 返回变异概率
     * @Description 计算自适应的变异概率
     */
    private double calcMutationRate(double v, double vAvg, double vMax) {
        if (compareDouble(v, vAvg) != -1) {
            return (mutationRateBoundArr[1] - mutationRateBoundArr[0]) / (1 + Math.exp(2 * A * (v - vAvg) / vMax - vAvg)) + mutationRateBoundArr[0];
        } else {
            return mutationRateBoundArr[1];
        }
    }

    /**
     * @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;
        double minFitness = population.get(0).getFitness();
        for (Genome genome : population) {
            totalFitness += genome.getFitness();
            minFitness = Math.min(genome.getFitness(), minFitness);
        }
        totalFitness -= (minFitness * population.size());
        double rate = 0.0;
        for (int i = 0; i < population.size(); i++) {
            if (Math.abs(totalFitness) < 1e-10) {
                rate += (1d / population.size());
            } else {
                rate += ((population.get(i).getFitness() - minFitness) / 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
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360

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();
        // 实例化遗传算法对象
        AGA aga = new AGA(1000, 200, 1, 10, new double[]{0.2, 1.0}, new double[]{0.92, 0.98}, instance, null);
        // 调用遗传算法对象进行求解
        Solution solution = aga.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.98063125
当前代数: 1 : 0.98559375
当前代数: 3 : 0.98716875
当前代数: 5 : 0.98799375
当前代数: 21 : 0.9898625
当前代数: 23 : 0.99146875
当前代数: 26 : 0.9920625
当前代数: 88 : 0.99400625
当前代数: 183 : 0.9951
当前代数: 208 : 0.9967
------------------------------------------------------------------------------------
求解用时:14.81 s
共放置了矩形30个
最佳利用率为:0.9967
data:[{x:0.0,y:0.0,l:29.0,w:117.0}, {x:316.0,y:0.0,l:87.0,w:84.0}, {x:261.0,y:0.0,l:87.0,w:55.0}, {x:179.0,y:0.0,l:66.0,w:82.0}, {x:117.0,y:0.0,l:91.0,w:62.0}, {x:0.0,y:29.0,l:80.0,w:117.0}, {x:179.0,y:66.0,l:40.0,w:82.0}, {x:261.0,y:87.0,l:86.0,w:55.0}, {x:316.0,y:87.0,l:96.0,w:84.0}, {x:117.0,y:91.0,l:60.0,w:62.0}, {x:179.0,y:106.0,l:93.0,w:82.0}, {x:0.0,y:109.0,l:107.0,w:117.0}, {x:117.0,y:151.0,l:51.0,w:62.0}, {x:261.0,y:173.0,l:73.0,w:55.0}, {x:316.0,y:183.0,l:106.0,w:84.0}, {x:179.0,y:199.0,l:57.0,w:82.0}, {x:117.0,y:202.0,l:38.0,w:62.0}, {x:0.0,y:216.0,l:71.0,w:117.0}, {x:117.0,y:240.0,l:47.0,w:52.0}, {x:261.0,y:246.0,l:24.0,w:55.0}, {x:169.0,y:256.0,l:107.0,w:92.0}, {x:261.0,y:270.0,l:103.0,w:21.0}, {x:282.0,y:270.0,l:47.0,w:34.0}, {x:0.0,y:287.0,l:113.0,w:100.0}, {x:102.0,y:287.0,l:76.0,w:67.0}, {x:321.0,y:289.0,l:111.0,w:79.0}, {x:282.0,y:317.0,l:59.0,w:39.0}, {x:100.0,y:363.0,l:37.0,w:68.0}, {x:168.0,y:363.0,l:37.0,w:92.0}, {x:260.0,y:376.0,l:24.0,w:61.0}],
isRotate:[0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0],
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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

在这里插入图片描述

相关阅读:
讲解器厂家深层互联重磅发布行业首个头戴式无线讲解器
WSL2下的Docker配置和使用
CentOS8 安装 erlang 和 RabbitMQ
深度学习-卷积神经网络
汇编指令概述 AT&T汇编基本语法
Vue——引入Vue的方法、VM对象和基础指令（面试）
C++ 读取txt文件，按行读取，每行按照空格分隔
第二章《补基础:不怕学不懂线性代数》笔记
Netty 入门 — Bootstrap，一切从这里开始
Buffered字节处理流

原文地址：https://blog.csdn.net/weixin_51545953/article/details/127778494