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

    文章目录

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

    一、天际线启发式

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

    二、蚁群算法结合天际线启发式

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

    2.1 构建序列

    让我们回顾一下蚁群算法求解TSP问题是如何处理的：在构建路径时, 蚂蚊通过当前信息素浓度, 按照一定概率选择下一个要到达的城市, 设 i \mathrm{i} i 和 j \mathrm{j} j 分别为起点和终点, τ i j ( t ) \tau_{i j}(t) τij​(t) 为时间 t \mathrm{t} t 时, 从站点 i \mathrm{i} i 到站点 j \mathrm{j} j 的信息素浓度, A k A^k Ak 为第 k \mathrm{k} k 只蚂蚊的尚末访问的邻接节点的集合, p k i j p^k{ }_{i j} pkij​ 代表第 k \mathrm{k} k 只蚂蚁从站点 i \mathrm{i} i 行驶到站 点 j \mathrm{j} j 的概率, η i j \eta_{i j} ηij​ 表示 i \mathrm{i} i 和 j \mathrm{j} j 两点间距离的倒数, 综上, 概率的计算规则可以表达如下:
    p k i j = { τ i j ( t ) η i j ∑ S ∈ A k τ i j ( t ) η i j , j ∈ A k 0 ,  其他  p^k{ }_{i j}=\left\{\begin{array}{l} \frac{\tau_{i j}(t) \eta_{i j}}{\sum_{S \in A^k} \tau_{i j}(t) \eta_{i j}}, j \in A^k \\ 0, \text { 其他 } \end{array}\right. pkij​={∑S∈Ak​τij​(t)ηij​τij​(t)ηij​​,j∈Ak0, 其他 ​

    构建路径的过程，其实就是构建序列的过程，但是有一个问题，在二维矩形装箱问题中，城市被换成了一个个矩形，城市之间存在距离，但是两个矩形之间没有距离呀！这可怎么办？没有距离的话 η i j \eta_{i j} ηij​怎么求呢？对此我们有两种解决思路。

    2.1.1 思路一

    思路1：直接舍弃掉 η i j \eta_{i j} ηij​这个参数，相当于让蚂蚁丧失基于“距离”的启发式信息

    这么做的好处是，我们不用更改太多代码，只需要将概率的计算中的距离倒数删去，或者设置为一个常数即可。

    但这么做的坏处是，丧失了基于“距离”的启发式信息，蚂蚁们前期的行走可能会较为漫无目的（这里是指迭代前期，后期信息素积累，信息素启发式信息占主导时会好一点）

    emm转念一想，蚂蚁们在前期漫无目的一点也挺好呀！模拟退火的思想不就是如此嘛，前期搜索随机性大，后期慢慢稳定。

    为了方便大家理解，直接亮Java代码：

    修改前

            // 计算分母部分
        for (Integer i : allowedItems) {
            sum += Math.pow(pheromone[currentSquare][i], alpha)
                    * Math.pow(1.0 / 距离矩阵[currentSquare][i], beta);
        }
        // 计算概率矩阵
        for (int i : allowedItems) {
            p[i] = (Math.pow(pheromone[currentSquare][i], alpha) * Math
                    .pow(1.0 / 距离矩阵[currentSquare][i], beta)) / sum;
        }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    修改后

            // 计算分母部分
        for (Integer i : allowedItems) {
            sum += Math.pow(pheromone[currentSquare][i], alpha)
                    * Math.pow(1.0, beta);
        }
        // 计算概率矩阵
        for (int i : allowedItems) {
            p[i] = (Math.pow(pheromone[currentSquare][i], alpha) * Math
                    .pow(1.0, beta)) / sum;
        }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    有一些变量不知道什么含义没关系，后面会放完整代码，里面有详细注释。主要是观察修改前后的区别，相当于把距离矩阵[currentSquare][i]这一项看为了常数1

    2.1.2 思路二

    思路2：我们可以用一种指标来衡量两个矩形之间的“距离”

    我想到的是利用两个矩形的不同度来衡量两个矩形间的距离，两个矩形越不同，则他们的距离越远，两个矩形越相似，则他们的距离越近（似不似听起来有点道理！）

    然而。。问题又来了，两个矩形的不同度怎么计算？

    这里就仁者见仁了，我采取的方法比较取巧

    首先定义边不同度，其实就是两条边的差值再除以两条边的平均长度，差值代表了两个矩形的相差度量，除以平均值是为了消除量纲。
    两条边的不同度 = ∣ 边 1 − 边 2 ∣ ➗ [ ( 边 1 + 边 2 ) / 2 ] 两条边的不同度 = |边1-边2|➗[(边1+边2)/2] 两条边的不同度=∣边1−边2∣➗[(边1+边2)/2]
    然后再定义两个矩形的不同度为他们之间最小的边不同度

    ok，搞定！真的搞定了吗！不对，差点忘了，蚁群算法构造路径时可是取的两个城市之间距离的倒数呀！如果两个矩形的不同度为0，再求倒数不就报错了吗！

    所以这里还要做一点处理，对上面方法算出来的不同度和一个大于0的极小值做max操作，使得不同度不会等于0：

    两矩形的不同度 = m a x ( 0.0001 , 两矩形不同度 ) 两矩形的不同度=max(0.0001,两矩形不同度) 两矩形的不同度=max(0.0001,两矩形不同度)

    （我这里取了0.0001，大家也可以取其他值，不要太大，会影响原本的不同度，也不要太小，不然受浮点数精度影响可能还是认为这个数是0）

    为了方便大家理解，直接亮Java代码，其中 isRotateEnable 代表矩形是否可以旋转，如果可以旋转，那就要继续用a的宽对b的高做一次边不同度计算，再a的高对b的宽做一次不同度计算。

        /**
     * @param a 矩形a
     * @param b 矩形b
     * @return 矩形a和b的不同度
     * @Description 计算矩形a对b的不同度
     */
    public double getDifferent(Item a, Item b) {
        double avgW = (a.getW() + b.getW()) / 2.0;
        double avgH = (a.getH() + b.getH()) / 2.0;
        double different = Math.abs(a.getH() - b.getH()) / avgH;
        different = Math.min(Math.abs(a.getW() - b.getW()) / avgW, different);
        if (isRotateEnable) {
            different = Math.min(Math.abs(a.getW() - b.getH()) / avgH, different);
            different = Math.min(Math.abs(a.getH() - b.getW()) / avgW, different);
        }
        return Math.max(0.0001, different);
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    2.1.3 思路N

    思路N交给你们啦，关键是怎么衡量两个矩形之间的关系，可以使得蚂蚁在前期的序列构建中不那么“随机”，评论区就交给大家自由发挥啦~~~

    三、Java代码实现

    3.1 项目结构

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

    在这里插入图片描述

    3.2 Ant

    /**
 * @Author：WSKH
 * @ClassName：Ant
 * @ClassType：蚂蚁类
 * @Description：
 * @Date：2022/11/06/15:04
 * @Email：1187560563@qq.com
 * @Blog：https://blog.csdn.net/weixin_51545953?type=blog
 */
public class Ant {
    // 矩形集合
    private Item[] items;
    // 已经放置的矩形的索引
    private List<Integer> sequence;
    // 还没放置的矩形索引
    private List<Integer> allowedItems;
    // 信息素变化矩阵
    private double[][] delta;
    // 矩形不同度矩阵
    private double[][] different;
    // 信息素重要程度
    private double alpha;
    // 启发式因子重要程度
    private double beta;
    // 矩形数量
    private int itemNum;
    // 第一个放置的矩形
    private int firstSquare;
    // 当前放置的矩形
    private int currentSquare;
    // 随机数对象
    private Random random;

    // 外矩形的长宽
    double W, H;
    // 是否允许旋转
    private boolean isRotateEnable;

    Solution localSolution;

    //构造函数
    public Ant(boolean isRotateEnable, double W, double H, Item[] items, Long seed) {
        this.itemNum = items.length;
        this.items = items;
        this.H = H;
        this.W = W;
        this.isRotateEnable = isRotateEnable;
        this.random = seed == null ? new Random() : new Random(seed);
    }

    //初始化
    public void initAnt(double[][] different, double a, double b) {
        alpha = a;
        beta = b;
        this.different = different;
        // 初始允许搜索的矩形集合
        allowedItems = new ArrayList<>();
        // 初始禁忌表
        sequence = new ArrayList<>();
        // 初始信息数变化矩阵为0
        delta = new double[itemNum][itemNum];
        // 设置起始矩形(随机选取第一个矩形)
        firstSquare = random.nextInt(itemNum);

        for (int i = 0; i < itemNum; i++) {
            if (i != firstSquare) {
                allowedItems.add(i);
            }
        }
        // 将第一个放置的矩形添加至禁忌表
        sequence.add(firstSquare);
        // 第一个矩形即为当前放置的矩形
        currentSquare = firstSquare;
    }

    //选择下一个矩形
    public void selectNextSquare(double[][] pheromone) {
        double[] p = new double[itemNum];
        double sum = 0d;

        // --------------- 思路1:直接将距离看为一个常数1 --------------------
//        // 计算分母部分
//        for (Integer i : allowedItems) {
//            sum += Math.pow(pheromone[currentSquare][i], alpha)
//                    * Math.pow(1.0, beta);
//        }
//        // 计算概率矩阵
//        for (int i : allowedItems) {
//            p[i] = (Math.pow(pheromone[currentSquare][i], alpha) * Math
//                    .pow(1.0, beta)) / sum;
//        }

        // --------------- 思路2:采用矩形的不同度代替距离 --------------------
        // 计算分母部分
        for (Integer i : allowedItems) {
            sum += Math.pow(pheromone[currentSquare][i], alpha)
                    * Math.pow(1.0 / different[currentSquare][i], beta);
        }
        // 计算概率矩阵
        for (int i : allowedItems) {
            p[i] = (Math.pow(pheromone[currentSquare][i], alpha) * Math
                    .pow(1.0 / different[currentSquare][i], beta)) / sum;
        }



        // 轮盘赌选择下一个矩形
        double sleectP = random.nextDouble();
        int selectSquare = -1;
        double sum1 = 0d;
        for (int i = 0; i < itemNum; i++) {
            sum1 += p[i];
            if (compareDouble(sum1, sleectP) != -1) {
                selectSquare = i;
                break;
            }
        }
        // 从允许选择的矩形中去除select 矩形
        for (Integer i : allowedItems) {
            if (i == selectSquare) {
                allowedItems.remove(i);
                break;
            }
        }
        // 在禁忌表中添加select矩形
        sequence.add(selectSquare);
        currentSquare = selectSquare;
    }

    // 根据顺序进行装箱,并返回装载的矩形总面积
    public void evaluate() {
        // 根据顺序进行装箱
        Item[] items = new Item[this.items.length];
        for (int i = 0; i < sequence.size(); i++) {
            items[i] = this.items[sequence.get(i)];
        }
        localSolution = new SkyLinePacking(isRotateEnable, W, H, items).packing();
    }

    /**
     * @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);
        }
    }

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

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

    public List<Integer> getSequence() {
        return sequence;
    }

    public void setSequence(List<Integer> sequence) {
        this.sequence = sequence;
    }

    public List<Integer> getAllowedItems() {
        return allowedItems;
    }

    public void setAllowedItems(List<Integer> allowedItems) {
        this.allowedItems = allowedItems;
    }

    public double[][] getDelta() {
        return delta;
    }

    public void setDelta(double[][] delta) {
        this.delta = delta;
    }

    public double[][] getDifferent() {
        return different;
    }

    public void setDifferent(double[][] different) {
        this.different = different;
    }

    public double getAlpha() {
        return alpha;
    }

    public void setAlpha(double alpha) {
        this.alpha = alpha;
    }

    public double getBeta() {
        return beta;
    }

    public void setBeta(double beta) {
        this.beta = beta;
    }

    public int getItemNum() {
        return itemNum;
    }

    public void setItemNum(int itemNum) {
        this.itemNum = itemNum;
    }

    public int getFirstSquare() {
        return firstSquare;
    }

    public void setFirstSquare(int firstSquare) {
        this.firstSquare = firstSquare;
    }

    public int getCurrentSquare() {
        return currentSquare;
    }

    public void setCurrentSquare(int currentSquare) {
        this.currentSquare = currentSquare;
    }

    public Random getRandom() {
        return random;
    }

    public void setRandom(Random random) {
        this.random = random;
    }

    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 boolean isRotateEnable() {
        return isRotateEnable;
    }

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

    public Solution getLocalSolution() {
        return localSolution;
    }

    public void setLocalSolution(Solution localSolution) {
        this.localSolution = localSolution;
    }
}

    • 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

    3.3 ACO

    /**
 * @Author：WSKH
 * @ClassName：ACO
 * @ClassType：
 * @Description：蚁群算法结合天际线算法求解二维矩形装箱问题
 * @Date：2022/11/7/11:32
 * @Email：1187560563@qq.com
 * @Blog：https://blog.csdn.net/weixin_51545953?type=blog
 */
public class ACO {

    // 蚂蚁数组
    public Ant[] ants;
    // 蚂蚁数量
    public int antNum;
    // 矩形数量
    public int itemNum;
    // 最大迭代数
    public int MAX_GEN;
    // 信息素矩阵
    public double[][] pheromone;
    // 最佳放置序列
    public List<Integer> bestSquence;
    // 最佳迭代数
    public int bestT;
    // 最优解
    public Solution bestSolution;
    // 不同度矩形
    double[][] different;

    // 三个参数
    // 信息素重要程度
    private double alpha;
    // 启发式因子重要程度
    private double beta;
    // 信息素挥发速率
    private double rho;

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

    /**
     * @param antNum   蚂蚁数量
     * @param MAX_GEN  迭代次数(提高这个值可以稳定地提高解质量，但是会增加求解时间)
     * @param alpha    信息素重要程度
     * @param beta     启发式因子重要程度
     * @param rho      信息素挥发速率
     * @param instance 实例对象
     * @param seed     随机数种子，如果传入null则不设置随机数种子，否则按照传入的种子进行设置，方便复现结果
     * @Description 构造函数
     */
    public ACO(int antNum, int MAX_GEN, double alpha, double beta, double rho, Instance instance, Long seed) {
        this.antNum = antNum;
        this.ants = new Ant[antNum];
        this.alpha = alpha;
        this.beta = beta;
        this.rho = rho;
        this.MAX_GEN = MAX_GEN;
        this.W = instance.getW();
        this.H = instance.getH();
        this.isRotateEnable = instance.isRotateEnable();
        this.items = Item.copy(instance.getItemList().toArray(new Item[0]));
        this.itemNum = this.items.length;
        this.seed = seed;
    }

    /**
     * @return 最佳装载结果对象Solution
     * @Description 蚁群算法主函数
     */
    public Solution solve() {
        // 进行初始化操作
        init();
        // 迭代MAX_GEN次
        for (int g = 0; g < MAX_GEN; g++) {
            // antNum只蚂蚁
            for (int i = 0; i < antNum; i++) {
                // i这只蚂蚁走itemNum步，构成一个完整的矩形放置顺序
                for (int j = 1; j < itemNum; j++) {
                    ants[i].selectNextSquare(pheromone);
                }
                // 查看这只蚂蚁装载利用率是否比当前最优解优秀
                ants[i].evaluate();
                if (bestSolution == null || compareDouble(ants[i].getLocalSolution().getRate(), bestSolution.getRate()) == 1) {
                    // 比当前优秀则拷贝优秀的放置顺序
                    bestSquence = new ArrayList<>(ants[i].getSequence());
                    bestT = g;
                    bestSolution = ants[i].getLocalSolution();
                    System.out.println("蚂蚁 " + (i + 1) + " 找到更优解 , 当前迭代次数为: " + g + " , 利用率为：" + bestSolution.getRate());
                }
                // 更新这只蚂蚁的信息数变化矩阵，对称矩阵
                for (int j = 0; j < itemNum; j++) {
                    ants[i].getDelta()[ants[i].getSequence().get(j)][ants[i]
                            .getSequence().get(j + 1 >= itemNum ? 0 : j + 1)] = (1.0 / ants[i]
                            .getLocalSolution().getRate());
                    ants[i].getDelta()[ants[i].getSequence().get(j + 1 >= itemNum ? 0 : j + 1)][ants[i]
                            .getSequence().get(j)] = (1.0 / ants[i]
                            .getLocalSolution().getRate());
                }
            }
            // 更新信息素
            updatePheromone();
            // 重新初始化蚂蚁
            for (int i = 0; i < antNum; i++) {
                ants[i].initAnt(different, alpha, beta);
            }
        }
        // 返回结果
        return bestSolution;
    }

    /**
     * @Description 初始化操作
     */
    private void init() {
        //初始化不同度矩阵
        different = new double[itemNum][itemNum];
        for (int i = 0; i < itemNum; i++) {
            for (int j = 0; j < itemNum; j++) {
                if (i == j) {
                    different[i][j] = 0.0;
                } else {
                    different[i][j] = getDifferent(items[i], items[j]);
                }
            }
        }
        //初始化信息素矩阵
        pheromone = new double[itemNum][itemNum];
        for (int i = 0; i < itemNum; i++) {
            for (int j = 0; j < itemNum; j++) {
                // 初始化为0.1
                pheromone[i][j] = 0.1;
            }
        }
        // 放置蚂蚁
        for (int i = 0; i < antNum; i++) {
            ants[i] = new Ant(isRotateEnable, W, H, items, seed);
            ants[i].initAnt(different, alpha, beta);
        }
    }

    /**
     * @Description 更新信息素
     */
    private void updatePheromone() {
        // 信息素挥发
        for (int i = 0; i < itemNum; i++) {
            for (int j = 0; j < itemNum; j++) {
                pheromone[i][j] = pheromone[i][j] * (1 - rho);
            }
        }
        // 信息素更新
        for (int i = 0; i < itemNum; i++) {
            for (int j = 0; j < itemNum; j++) {
                for (int k = 0; k < antNum; k++) {
                    pheromone[i][j] += ants[k].getDelta()[i][j];
                }
            }
        }
    }

    /**
     * @param a 矩形a
     * @param b 矩形b
     * @return 矩形a和b的不同度
     * @Description 计算矩形a对b的不同度
     */
    public double getDifferent(Item a, Item b) {
        double avgW = (a.getW() + b.getW()) / 2.0;
        double avgH = (a.getH() + b.getH()) / 2.0;
        double different = Math.abs(a.getH() - b.getH()) / avgH;
        different = Math.min(Math.abs(a.getW() - b.getW()) / avgW, different);
        if (isRotateEnable) {
            different = Math.min(Math.abs(a.getW() - b.getH()) / avgH, different);
            different = Math.min(Math.abs(a.getH() - b.getW()) / avgW, different);
        }
        return Math.max(0.0001, different);
    }

    /**
     * @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

    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();
        // 实例化蚁群算法对象
        ACO aco = new ACO(30, 300, 0.99, 5, 0.5, instance, null);
        // 调用蚁群算法对象进行求解
        Solution solution = aco.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 运行结果展示

    3.5.1 思路一

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

    蚂蚁 1 找到更优解 , 当前迭代次数为: 0 , 利用率为：0.94475625
蚂蚁 2 找到更优解 , 当前迭代次数为: 0 , 利用率为：0.9608875
蚂蚁 6 找到更优解 , 当前迭代次数为: 0 , 利用率为：0.96431875
蚂蚁 10 找到更优解 , 当前迭代次数为: 0 , 利用率为：0.97451875
蚂蚁 7 找到更优解 , 当前迭代次数为: 1 , 利用率为：0.9752125
蚂蚁 27 找到更优解 , 当前迭代次数为: 1 , 利用率为：0.97885625
蚂蚁 30 找到更优解 , 当前迭代次数为: 8 , 利用率为：0.980275
蚂蚁 8 找到更优解 , 当前迭代次数为: 9 , 利用率为：0.98029375
蚂蚁 16 找到更优解 , 当前迭代次数为: 10 , 利用率为：0.98356875
蚂蚁 27 找到更优解 , 当前迭代次数为: 16 , 利用率为：0.99161875
------------------------------------------------------------------------------------
求解用时:7.436 s
共放置了矩形24个
最佳利用率为:0.99161875
data:[{x:0.0,y:0.0,l:116.0,w:99.0}, {x:99.0,y:0.0,l:116.0,w:113.0}, {x:212.0,y:0.0,l:116.0,w:111.0}, {x:323.0,y:0.0,l:116.0,w:20.0}, {x:343.0,y:0.0,l:89.0,w:57.0}, {x:343.0,y:89.0,l:82.0,w:57.0}, {x:0.0,y:116.0,l:88.0,w:99.0}, {x:99.0,y:116.0,l:88.0,w:113.0}, {x:212.0,y:116.0,l:79.0,w:111.0}, {x:323.0,y:116.0,l:58.0,w:20.0}, {x:343.0,y:171.0,l:95.0,w:57.0}, {x:226.0,y:195.0,l:71.0,w:117.0}, {x:0.0,y:204.0,l:79.0,w:99.0}, {x:99.0,y:204.0,l:79.0,w:118.0}, {x:217.0,y:266.0,l:40.0,w:117.0}, {x:334.0,y:266.0,l:82.0,w:66.0}, {x:0.0,y:283.0,l:117.0,w:80.0}, {x:80.0,y:283.0,l:117.0,w:107.0}, {x:187.0,y:283.0,l:117.0,w:29.0}, {x:216.0,y:306.0,l:94.0,w:44.0}, {x:260.0,y:306.0,l:94.0,w:31.0}, {x:291.0,y:306.0,l:94.0,w:39.0}, {x:330.0,y:348.0,l:52.0,w:47.0}, {x:377.0,y:348.0,l:50.0,w:23.0}],
isRotate:[0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1],

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

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

    在这里插入图片描述

    3.5.2 思路二

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

    蚂蚁 1 找到更优解 , 当前迭代次数为: 0 , 利用率为：0.95544375
蚂蚁 2 找到更优解 , 当前迭代次数为: 0 , 利用率为：0.95601875
蚂蚁 6 找到更优解 , 当前迭代次数为: 0 , 利用率为：0.96580625
蚂蚁 13 找到更优解 , 当前迭代次数为: 0 , 利用率为：0.97780625
蚂蚁 12 找到更优解 , 当前迭代次数为: 1 , 利用率为：0.98049375
蚂蚁 20 找到更优解 , 当前迭代次数为: 13 , 利用率为：0.9811375
蚂蚁 18 找到更优解 , 当前迭代次数为: 21 , 利用率为：0.9843125
蚂蚁 1 找到更优解 , 当前迭代次数为: 37 , 利用率为：0.986
蚂蚁 13 找到更优解 , 当前迭代次数为: 63 , 利用率为：0.99160625
蚂蚁 28 找到更优解 , 当前迭代次数为: 244 , 利用率为：0.9920625
------------------------------------------------------------------------------------
求解用时:14.288 s
共放置了矩形22个
最佳利用率为:0.9920625
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:292.0,y:0.0,l:54.0,w:108.0}, {x:221.0,y:0.0,l:117.0,w:71.0}, {x:292.0,y:54.0,l:63.0,w:41.0}, {x:333.0,y:54.0,l:76.0,w:67.0}, {x:0.0,y:100.0,l:116.0,w:113.0}, {x:113.0,y:100.0,l:116.0,w:99.0}, {x:212.0,y:117.0,l:117.0,w:80.0}, {x:292.0,y:117.0,l:117.0,w:29.0}, {x:321.0,y:130.0,l:118.0,w:79.0}, {x:0.0,y:216.0,l:85.0,w:113.0}, {x:113.0,y:216.0,l:88.0,w:99.0}, {x:212.0,y:234.0,l:70.0,w:76.0}, {x:288.0,y:234.0,l:114.0,w:33.0}, {x:321.0,y:248.0,l:111.0,w:79.0}, {x:0.0,y:301.0,l:99.0,w:79.0}, {x:79.0,y:301.0,l:99.0,w:26.0}, {x:105.0,y:304.0,l:96.0,w:98.0}, {x:203.0,y:304.0,l:96.0,w:84.0}, {x:287.0,y:348.0,l:47.0,w:34.0}, {x:332.0,y:359.0,l:37.0,w:68.0}],
isRotate:[0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

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

    在这里插入图片描述

    3.5.3 思路N

    等待你们上榜哈哈哈~

    四、小结

    上面的测试结果我只跑了一遍，并不能说明思路二就比思路一好，就算跑了很多遍思路二普遍比思路一利用率高，也不能绝对说明思路二就更好，还可能是由于这个测试数据的某些特性导致思路二更好，所以，启发式嘛，最重要的就是要多调参多测试啦~

  • 相关阅读:
    Mybatis关联关系映射
    虚拟机的 Ubuntu 没有 /dev/fb0 的解决办法
    有更新：2023华为HCIA+HCIP最全Datacom题库解析（附全套文档赠送）
    （附源码）php新闻发布平台 毕业设计 141646
    《Large Language Models for Generative Information Extraction: A Survey》阅读笔录
    如何更改代理ip，变更代理ip怎么实现？
    Qt源码分析--QObject(4)
    SpringBoot配置kafka
    含文档+PPT+源码等]精品微信小程序ssm社区心理健康服务平台+后台管理系统|前后分离VUE[包运行成功]微信小程序项目源码Java毕业设计
    Python教程：读取文件有三种方法：（read、readline、readlines）详细用法
  • 原文地址：https://blog.csdn.net/weixin_51545953/article/details/127759895