文章目录

1 前言2 代码迁移3 蚁群算法3.1 蚂蚁类 Ant3.2 蚁群算法类 ACO_Packing4 运行结果5 后话

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

1 前言

之前我已经写过一篇禁忌搜索算法求解二维矩形装箱问题（java代码实现）,如果有对二维矩形装箱问题的背景不是很了解的朋友可以去看看

2 代码迁移

项目的大体框架（一些实体类，数据读取类等）和禁忌搜索算法求解二维矩形装箱问题（java代码实现）中的差不多，所以本文只提供蚁群算法的核心代码，大家用的时候只需要将两个禁忌搜索算法类替换为下文中的蚁群算法类即可。

3 蚁群算法

3.1 蚂蚁类 Ant

/*** @Author：WSKH* @ClassName：Ant* @ClassType：蚂蚁类* @Description：* @Date：/5/29/15:04* @Email：1187560563@* @Blog：/weixin_51545953?type=blog*/@Datapublic class Ant implements Cloneable {private List<Square> squareList; // 矩形集合private List<PlaceSquare> placeSquareList; // 已经放置的矩形集合private List<Integer> tabu; // 已经放置的矩形的索引private List<Integer> allowedCities; // 还没放置的矩形索引private double[][] delta; // 信息素变化矩阵private double alpha;private double beta;private int squareNum; // 矩形数量private int firstSquare; // 第一个放置的矩形private int currentSquare; // 当前放置的矩形private double[][] different; // 不同度矩阵// 外矩形的长宽double L, W;Instance instance;Solution localSolution;//构造函数public Ant(int squareNum, List<Square> squareList, double L, double W, Instance instance) {this.squareNum = squareNum;this.squareList = squareList;this.L = L;this.W = W;this.instance = instance;}//初始化public void initAnt(double[][] different, double a, double b) {alpha = a;beta = b;placeSquareList = new ArrayList<>();// 初始允许搜索的矩形集合allowedCities = new ArrayList<>();// 初始禁忌表tabu = new ArrayList<>();// 初始相似度的倒数矩阵this.different = different;// 初始信息数变化矩阵为0delta = new double[squareNum][squareNum];for (int i = 0; i < squareNum; i++) {Integer integer = i;allowedCities.add(integer);for (int j = 0; j < squareNum; j++) {delta[i][j] = 0.f;}}// 设置起始矩形firstSquare = new Random(System.currentTimeMillis()).nextInt(squareNum); // 随机选取第一个矩形// 允许搜索的矩形集合中移除起始矩形for (Integer i : allowedCities) {if (i == firstSquare) {allowedCities.remove(i);break;}}// 将第一个放置的矩形添加至禁忌表tabu.add(firstSquare);// 第一个矩形即为当前放置的矩形currentSquare = firstSquare;}//选择下一个矩形public void selectNextSquare(double[][] pheromone) {double[] p = new double[squareNum];double sum = 0d;// 计算分母部分for (Integer i : allowedCities) {sum += Math.pow(pheromone[currentSquare][i], alpha)* Math.pow(1.0 / different[currentSquare][i], beta);}// 计算概率矩阵for (int i = 0; i < squareNum; i++) {boolean flag = false;for (Integer j : allowedCities) {if (i == j) {p[i] = (Math.pow(pheromone[currentSquare][i], alpha) * Math.pow(1.0 / different[currentSquare][i], beta)) / sum;flag = true;break;}}if (!flag) {p[i] = 0.f;}}// 轮盘赌选择下一个矩形Random random = new Random(System.currentTimeMillis());double sleectP = random.nextDouble();int selectSquare = 0;double sum1 = 0d;for (int i = 0; i < squareNum; i++) {sum1 += p[i];if (sum1 >= sleectP) {selectSquare = i;break;}}// 从允许选择的矩形中去除select 矩形for (Integer i : allowedCities) {if (i == selectSquare) {allowedCities.remove(i);break;}}// 在禁忌表中添加select矩形tabu.add(selectSquare);currentSquare = selectSquare;}// 根据顺序进行装箱,并返回装载的矩形总面积public Solution calculateTotalPlaceSquareS() {// 根据顺序进行装箱return localSolution = packing(tabu.stream().map(index -> {return squareList.get(index);}).collect(Collectors.toList()));}// 按照顺序装载矩形private Solution packing(List<Square> squareList) {List<PlaceSquare> placeSquareList = new ArrayList<>();// 创建初始可放置角点List<PlacePoint> placePointList = new ArrayList<>();placePointList.add(new PlacePoint(0, 0, L));// 开始按照顺序和规则放置for (int i = 0; i < placePointList.size();) {PlacePoint placePoint = placePointList.get(i);double maxMark = -1.0d;int maxIndex = -1;double isRotate = -1, curMarks = -1;for (int j = 0; j < squareList.size(); j++) {Square square = squareList.get(j);double[] arr = getMarks(placePoint, square, placeSquareList);double is_rotate = arr[0];curMarks = arr[1];if (curMarks > 0 && curMarks > maxMark) {maxMark = curMarks;maxIndex = j;isRotate = is_rotate;}}if (maxIndex < 0 && i < placePointList.size()) {i++;} else if (maxIndex < 0 && i >= placePointList.size()) {break;} else {Square square = squareList.remove(maxIndex);double l = square.getL();double w = square.getW();if (isRotate > 0) {// 表示进行了旋转square.setL(w);square.setW(l);}// 移除当前角点placePointList.remove(i);//新增已放置的squareplaceSquareList.add(new PlaceSquare(placePoint.getX(), placePoint.getY(), square.getL(), square.getW()));// 新增两个可行角点double surplus = placePoint.getLen() - square.getL(); // 剩余长度if (surplus > 0) {placePointList.add(new PlacePoint(placePoint.getX() + square.getL(), placePoint.getY(), surplus));}placePointList.add(new PlacePoint(placePoint.getX(), placePoint.getY() + square.getW(), square.getL()));// 重新排序Collections.sort(placePointList);i = 0;// 还原矩形if (isRotate > 0) {// 表示进行了旋转square.setL(l);square.setW(w);}}}Solution solution = new Solution();solution.setInstance(instance);solution.setSquareList(new ArrayList<>(squareList));// 设置已经放置的矩形列表solution.setPlaceSquareList(new ArrayList<>(placeSquareList));// 计算利用率double rate = 0d;double s = 0d;for (PlaceSquare placeSquare : placeSquareList) {s += (placeSquare.getL() * placeSquare.getW());}rate = s / (L * W);solution.setRate(rate);return solution;}// 评价该点的得分private double[] getMarks(PlacePoint placePoint, Square square, List<PlaceSquare> placeSquareList) {// 返回{是否旋转，分数}double delta = 0, mark1 = -1d, mark2 = -1d;PlaceSquare placeSquare = new PlaceSquare(placePoint.getX(), placePoint.getY(), square.getL(), square.getW());if (isOverlap(placeSquareList, placeSquare)) {mark1 = -1.0d;} else {delta = Math.abs(placePoint.getLen() - square.getL());mark1 = 1 - delta / placePoint.getLen();}mark2 = -1.0d;if (instance.isRotateEnable()) {placeSquare = new PlaceSquare(placePoint.getX(), placePoint.getY(), square.getW(), square.getL());if (!isOverlap(placeSquareList, placeSquare)) {delta = Math.abs(placePoint.getLen() - square.getW());mark2 = 1 - delta / placePoint.getLen();}}if (mark1 >= mark2) {return new double[]{-1d, (int) (mark1 * 10)};}return new double[]{1d, (int) (mark2 * 10)};}// 判断放置在该位置是否超出边界或者和其他矩形重叠public boolean isOverlap(List<PlaceSquare> placeSquareList, PlaceSquare tempPlaceSquare) {// 出界if (tempPlaceSquare.getL() > L || tempPlaceSquare.getW() > W) {return true;}// 出界if (tempPlaceSquare.getX() + tempPlaceSquare.getL() > L || tempPlaceSquare.getY() + tempPlaceSquare.getW() > W) {return true;}for (PlaceSquare placeSquare : placeSquareList) {// 角点重合if (placeSquare.getX() == tempPlaceSquare.getX() && placeSquare.getY() == tempPlaceSquare.getY()) {placeSquareList.remove(placeSquare);return true;}// 判断即将要放置的块是否与之前放置的块有重叠if (isOverlap2(placeSquare, tempPlaceSquare)) {return true;}}return false;}// 判断即将要放置的块是否与之前放置的块有重叠public boolean isOverlap2(PlaceSquare placeSquare, PlaceSquare tempPlaceSquare) {double x1 = Math.max(placeSquare.getX(), tempPlaceSquare.getX());double y1 = Math.max(placeSquare.getY(), tempPlaceSquare.getY());double x2 = Math.min(placeSquare.getX() + placeSquare.getL(), tempPlaceSquare.getX() + tempPlaceSquare.getL());double y2 = Math.min(placeSquare.getY() + placeSquare.getW(), tempPlaceSquare.getY() + tempPlaceSquare.getW());if (x1 >= x2 || y1 >= y2) {return false;}return true;}}

3.2 蚁群算法类 ACO_Packing

/*** @Author：WSKH* @ClassName：ACO_Packing* @ClassType：* @Description：* @Date：/5/29/14:50* @Email：1187560563@* @Blog：/weixin_51545953?type=blog*/public class ACO_Packing {public Ant[] ants; // 蚂蚁public int antNum = 2; // 蚂蚁数量public int squareNum; // 矩形数量public int MAX_GEN = 20; // 最大迭代数public double[][] pheromone; // 信息素矩阵public double[][] different; // 不同度矩阵public double bestRate; // 最佳利用率public int[] bestSquence; // 最佳放置顺序public int bestT; //最佳迭代数public List<Square> squareList; // 矩形集合// 问题实例public Instance instance;// 大矩形（容器）的长宽double L, W;public Solution bestSolution; //最优解// 三个参数private double alpha = 1; //信息素重要程度private double beta = 5; //启发式因子重要程度private double rho = 0.5; //信息素挥发速率// 构造函数public ACO_Packing(Instance instance) {this.squareList = instance.getSquareList();this.instance = instance;this.L = instance.getL();this.W = instance.getW();squareNum = squareList.size();ants = new Ant[antNum];}// 外部调用窗口public Solution search() {long startTime = System.currentTimeMillis();initVar();bestSolution = solve();long endTime = System.currentTimeMillis();//求解完毕System.out.println("最佳迭代次数:"+bestT);System.out.println("最佳利用率为:"+bestSolution.getRate());System.out.println("程序运行了：" + (endTime - startTime) / 1000.0 + "秒");return bestSolution;}// 蚁群算法迭代求解public Solution solve() {// 迭代MAX_GEN次for (int g = 0; g < MAX_GEN; g++) {// antNum只蚂蚁for (int i = 0; i < antNum; i++) {// i这只蚂蚁走squareNum步，构成一个完整的矩形放置顺序for (int j = 1; j < squareNum; j++) {ants[i].selectNextSquare(pheromone);}// 把这只蚂蚁初始放置矩形加入其禁忌表中ants[i].getTabu().add(ants[i].getFirstSquare());// 查看这只蚂蚁装载利用率是否比当前最优解优秀ants[i].calculateTotalPlaceSquareS();if (ants[i].getLocalSolution().getRate() > bestRate) {// 比当前优秀则拷贝优秀的放置顺序bestRate = ants[i].getLocalSolution().getRate();for (int k = 0; k < squareNum; k++) {bestSquence[k] = ants[i].getTabu().get(k);}bestT = g;bestSolution = ants[i].getLocalSolution();System.out.println("蚂蚁"+(i+1)+": 当前迭代次数为："+g+",当前最佳利用率为："+bestSolution.getRate());}// 更新这只蚂蚁的信息数变化矩阵，对称矩阵for (int j = 0; j < squareNum; j++) {ants[i].getDelta()[ants[i].getTabu().get(j)][ants[i].getTabu().get(j + 1)] = (1.0 / ants[i].getLocalSolution().getRate());ants[i].getDelta()[ants[i].getTabu().get(j + 1)][ants[i].getTabu().get(j)] = (1.0 / ants[i].getLocalSolution().getRate());}}// 更新信息素updatePheromone();// 重新初始化蚂蚁for (int i = 0; i < antNum; i++) {ants[i].initAnt(different, alpha, beta);}}// 返回结果return bestSolution;}//初始化public void initVar() {bestSolution = new Solution();//初始化不同度矩阵different = new double[squareNum][squareNum];for (int i = 0; i < squareNum; i++) {for (int j = 0; j < squareNum; j++) {if (i == j) {different[i][j] = 0.0;} else {different[i][j] = getDifferent(squareList.get(i), squareList.get(j));}}}//初始化信息素矩阵pheromone = new double[squareNum][squareNum];for (int i = 0; i < squareNum; i++) {for (int j = 0; j < squareNum; j++) {pheromone[i][j] = 0.1; // 初始化为0.1}}bestRate = 0d;bestSquence = new int[squareNum];// 放置蚂蚁for (int i = 0; i < antNum; i++) {ants[i] = new Ant(squareNum,squareList,L,W,instance);ants[i].initAnt(different, alpha, beta);}}// 更新信息素private void updatePheromone() {// 信息素挥发for (int i = 0; i < squareNum; i++) {for (int j = 0; j < squareNum; j++) {pheromone[i][j] = pheromone[i][j] * (1 - rho);}}// 信息素更新for (int i = 0; i < squareNum; i++) {for (int j = 0; j < squareNum; j++) {for (int k = 0; k < antNum; k++) {pheromone[i][j] += ants[k].getDelta()[i][j];}}}}//计算矩形A对B的不同度public double getDifferent(Square A, Square B) {double different = 0d;different += Math.abs(A.getL()-B.getL())/B.getL();different += Math.abs(A.getW()-B.getW())/B.getW();return different;}}

4 运行结果

由于测试的时候我的电脑在跑其他程序，比较卡顿，所以我仅设置了2只蚂蚁，和20次迭代，最终跑出来利用率为96.7%，大家迁移完代码之后记得要设置成合适的参数，否则可能会对解的质量会产生一定的影响。

5 后话

本文仅列出了使用蚁群算法求解二维矩形装箱问题的2个核心类，如果需要整个跑通，还需要其他类，具体可以参照禁忌搜索算法求解二维矩形装箱问题（java代码实现）