文章目录

一、天际线启发式二、蚁群算法结合天际线启发式2.1 构建序列2.1.1 思路一2.1.2 思路二2.1.3 思路N三、Java代码实现3.1 项目结构3.2 Ant3.3 ACO3.4 Run3.5 运行结果展示3.5.1 思路一3.5.2 思路二3.5.3 思路N四、小结

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

一、天际线启发式

关于天际线启发式的介绍请看我的另一篇博客：

【运筹优化】基于堆优化的天际线启发式算法和复杂的评分策略求解二维矩形装箱问题 + Java代码实现

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

蚁群算法结合天际线启发式其实很简单，只需要将序列对应成一个矩形集合，传给天际线启发式算法进行求解即可。

也就是说，天际线启发式其实就是这类启发式算法的解码器（评价函数）。

2.1 构建序列

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

pkij={τij(t)ηij∑S∈Akτij(t)ηij,j∈Ak0,其他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,其他​

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

2.1.1 思路一

思路1：直接舍弃掉ηij\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;}

修改后

// 计算分母部分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;}

有一些变量不知道什么含义没关系，后面会放完整代码，里面有详细注释。主要是观察修改前后的区别，相当于把距离矩阵[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：

两矩形的不同度=max(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);}

2.1.3 思路N

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

三、Java代码实现

3.1 项目结构

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

3.2 Ant

/*** @Author：WSKH* @ClassName：Ant* @ClassType：蚂蚁类* @Description：* @Date：/11/06/15:04* @Email：1187560563@* @Blog：/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<>();// 初始信息数变化矩阵为0delta = 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.000001double 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;}}

3.3 ACO

/*** @Author：WSKH* @ClassName：ACO* @ClassType：* @Description：蚁群算法结合天际线算法求解二维矩形装箱问题* @Date：/11/7/11:32* @Email：1187560563@* @Blog：/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.1pheromone[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.000001double 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);}}}

3.4 Run

/*** @Author：WSKH* @ClassName：Run* @ClassType：* @Description：运行程序的主类* @Date：/11/6/19:39* @Email：1187560563@* @Blog：/weixin_51545953?type=blog*/public class Run extends javafx.application.Application {private int counter = 0;@Overridepublic 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>() {@Overridepublic 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);}}

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.99161875data:[{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],

可视化展示（利用率 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.9920625data:[{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],

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

3.5.3 思路N

等待你们上榜哈哈哈~

四、小结

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