【运筹优化】禁忌搜索算法求解二维矩形装箱问题（java代码实现）

给定一个矩形容器和若干个小的矩形，需要在不超出容器的情况下，求出利用率最高的小矩形放置方案，一个可行的放置方案如下图所示：本文首先展示我最初的做法，该做法运行速度快，但求解质量差。最后会展示改进后的方法，改进后，虽然运行速度下降了约10倍运行速度下降了约10倍，但是解的质量提高了3%3.data.txt4.Instance类5.PlacePoint类6.PlaceSquare类7.Solution

WSKH0929

26058人浏览 · 2021-11-29 22:21:38

WSKH0929 · 2021-11-29 22:21:38 发布

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

一、何为二维矩形装箱问题？

给定一个矩形容器和若干个小的矩形，需要在不超出容器的情况下，求出利用率最高的小矩形放置方案，一个可行的放置方案如下图所示：
在这里插入图片描述
本文首先展示我最初的做法，该做法运行速度快，但求解质量差。最后会展示改进后的方法，改进后，虽然运行速度下降了约10倍运行速度下降了约10倍，但是解的质量提高了3%

二、代码编写

1.项目结构

在这里插入图片描述

2.pom文件

<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"
         xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
         xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
    <modelVersion>4.0.0</modelVersion>
    <groupId>com.wskh</groupId>
    <artifactId>2DRP</artifactId>
    <version>1.0</version>
    <properties>
        <maven.compiler.source>17</maven.compiler.source>
        <maven.compiler.target>17</maven.compiler.target>
    </properties>
    <dependencies>
        <dependency>
            <groupId>org.openjfx</groupId>
            <artifactId>javafx-controls</artifactId>
            <version>15.0.1</version>
        </dependency>
        <dependency>
            <groupId>org.projectlombok</groupId>
            <artifactId>lombok</artifactId>
            <version>1.18.20</version>
        </dependency>
        <dependency>
            <groupId>junit</groupId>
            <artifactId>junit</artifactId>
            <version>4.12</version>
        </dependency>
    </dependencies>
</project>

3.data.txt

4.Instance类

package com.wskh.entitys;

import lombok.Data;

import java.util.List;

/*
**  Create by: WSKH0929
    Date:2021-11-05
    Time:20:16
*/
@Data
public class Instance {
    private double L,W;
    // 是否可以旋转
    private boolean isRotateEnable = true;
    private List<Square> squareList;
}

5.PlacePoint类

package com.wskh.entitys;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

/*
**  Create by: WSKH0929
    Date:2021-11-05
    Time:21:08
*/
@Data
@AllArgsConstructor
@NoArgsConstructor
public class PlacePoint implements Comparable<PlacePoint>{
    private double x,y;

    @Override
    public int compareTo(PlacePoint o) {
        // 优先往下排 然后优先往左排
        int compare_y = Double.compare(y,o.y );
        if(compare_y!=0){
            return compare_y;
        }else{
            return Double.compare(x,o.x);
        }
    }
}

6.PlaceSquare类

package com.wskh.entitys;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

/*
**  Create by: WSKH0929
    Date:2021-11-05
    Time:20:18
*/
@Data
@AllArgsConstructor
@NoArgsConstructor
public class PlaceSquare {
    private double x,y,l,w;
}

7.Solution类

package com.wskh.entitys;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

import java.util.List;

/*
**  Create by: WSKH0929
    Date:2021-11-05
    Time:20:17
*/
@Data
@NoArgsConstructor
@AllArgsConstructor
public class Solution {
    private double rate;
    private Instance instance;
    private List<Square> squareList;
    private List<PlaceSquare> placeSquareList;
}

8.Square类

package com.wskh.entitys;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

/*
**  Create by: WSKH0929
    Date:2021-11-05
    Time:20:00
*/
@Data
@AllArgsConstructor
@NoArgsConstructor
public class Square {
    private String id;
    private double l,w;
}

9.TabuMapTree类

package com.wskh.model;

import com.wskh.entitys.Square;
import lombok.Data;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/*
**  Create by: WSKH0929
    Date:2021-11-26
    Time:22:21
*/
@Data
public class TabuMapTree {

    Map<String,TabuMapTree> sonTreeMap = new HashMap<>();

    Square nodeSquare;

    public void add(List<Square> squareList, int index){
        if(index>=squareList.size()){
            return;
        }
        if(nodeSquare == null){
            nodeSquare = squareList.get(index);
            index++;
        }
        Square square = squareList.get(index);
        String id = square.getId();
        if(sonTreeMap.containsKey(id)){
            sonTreeMap.get(id).add(squareList,index+1);
        }else{
            TabuMapTree tabuMapTree = new TabuMapTree();
            tabuMapTree.setNodeSquare(square);
            sonTreeMap.put(id,tabuMapTree);
            sonTreeMap.get(id).add(squareList,index+1);
        }
    }

    public boolean contains(List<Square> squareList,int index){
        if(index>=squareList.size()){
            return true;
        }
        Square square = squareList.get(index);
        String id = square.getId();
        if(sonTreeMap.containsKey(id)){
            return sonTreeMap.get(id).contains(squareList,index+1);
        }else{
            return false;
        }
    }

    public void show(){
        for (String key : sonTreeMap.keySet()) {
            String id = sonTreeMap.get(key).getNodeSquare().getId();
            sonTreeMap.get(key).show();
        }
    }

    // 判断两个Squre是否相等
    public boolean isEq(Square square1, Square square2){
        return square1.getId().equals(square2.getId());
    }

}

10.TabuSearch类

package com.wskh.model;

import com.wskh.entitys.*;
import lombok.Data;

import java.util.*;

/*
**  Create by: WSKH0929
    Date:2021-11-05
    Time:20:26
*/
@Data
public class TabuSearch {
    public  final int MAX_GEN = 300;//最大的迭代次数(提高这个值可以稳定地提高解质量，但是会增加求解时间)
    public  final int N = 50;//每次搜索领域的个数(这个值不要太大，太大的话搜索效率会降低)
    public  int sqNum ;//矩形数量，手动设置
    public HashMap<String,TabuMapTree> tabuTreeMap = new HashMap<>();
    public  List<Square> initGhh;//初始顺序
    public  List<Square> bestGh;//最佳顺序
    public  List<Square> LocalGh;//当前最好顺序
    public  List<Square> tempGh;//存放临时顺序
    public  int bestT;//最佳的迭代次数
    public Solution bestSolution;//最优解
    public  Solution LocalSolution;//每次领域搜索的最优解（领域最优解）
    public  Solution tempSolution;//临时解
    public  int t;//当前迭代
    public Random random;//随机函数对象
    // 问题实例
    public Instance instance;
    double L,W;

    public TabuSearch(Instance instance) throws Exception {
        this.instance = instance;
        this.initGhh = new ArrayList<>(instance.getSquareList());
        // 初始化变量
        random = new Random(System.currentTimeMillis());
        L = instance.getL();
        W = instance.getW();
        sqNum = initGhh.size();
    }
    public Solution search() throws Exception {
        // 获取初始解
        getInitSolution();
        System.out.println(bestSolution.getRate());
        //开始迭代，停止条件为达到指定迭代次数
        while (t<=MAX_GEN){
            //当前领域搜索次数
            int n = 0;
            LocalSolution = new Solution();
            LocalSolution.setRate(0);
            while (n <= N){
                // 随机打乱顺序 得到当前编码Ghh的邻居编码tempGh
                tempGh = generateNewGh(new ArrayList<>(initGhh),new ArrayList<>(tempGh));
                // 判断其是否在禁忌表中
                if(!judge(tempGh)){
                    // 如果不在
                    // 加入禁忌表
                    enterTabooList(tempGh);
                    tempSolution = evaluate(tempGh);
                    if(tempSolution.getRate() > LocalSolution.getRate()){
                        // 如果临时解优于本次领域搜索的最优解
                        // 那么就将临时解替换本次领域搜索的最优解
                        LocalGh = new ArrayList<>(tempGh);
                        LocalSolution = tempSolution;
                    }
                }else{
                    throw new Exception("重复");
                }
                n++;
            }
            if(LocalSolution.getRate() > bestSolution.getRate()){
                //如果本次搜索的最优解优于全局最优解
                //那么领域最优解替换全局最优解
                bestT = t;
                bestGh = new ArrayList<>(LocalGh);
                bestSolution = LocalSolution;
//                bestSolution = evaluate(bestGh);
            }
            initGhh = new ArrayList<>(LocalGh);
            t++;
            System.out.println("当前迭代次数为："+t+",当前最佳利用率为："+bestSolution.getRate());
        }
        //求解完毕
        System.out.println("最佳迭代次数:"+bestT);
        System.out.println("最佳利用率为:"+bestSolution.getRate());
        return bestSolution;
    }
    //评价函数
    public Solution evaluate(List<Square> squareList){
        Solution solution = new Solution();
        solution.setInstance(instance);
        solution.setSquareList(new ArrayList<>(squareList));
        List<PlaceSquare> placeSquareList = new ArrayList<>();
        // 创建可放置角点
        List<PlacePoint> placePointList = new ArrayList<>();
        placePointList.add(new PlacePoint(0,0));
        // 开始按照顺序和规则放置
        for (int i = 0; i < squareList.size(); i++) {
            PlacePoint placePoint = null;
            boolean b = false;
            Square square = squareList.get(i);
            for (int j = 0; j < placePointList.size(); j++) {
                placePoint = placePointList.get(j);
                PlaceSquare placeSquare = new PlaceSquare(placePoint.getX(),placePoint.getY(),square.getL(),square.getW());
                if(!isOverlap(placeSquareList,placeSquare)){
                    b = true;
                    // 移除当前角点
                    placePointList.remove(j);
                    //新增已放置的square
                    placeSquareList.add(new PlaceSquare(placePoint.getX(),placePoint.getY(),square.getL(),square.getW()));
                    // 新增两个可行角点
                    placePointList.add(new PlacePoint(placePoint.getX()+square.getL(),placePoint.getY()));
                    placePointList.add(new PlacePoint(placePoint.getX(),placePoint.getY()+square.getW()));
                    // 重新排序
                    Collections.sort(placePointList);
                    // 跳出内层循环
                    j = placePointList.size();
                }
            }
            if(!b && instance.isRotateEnable()){
                double l = square.getL();
                double w = square.getW();
                square.setL(w);
                square.setW(l);
                for (int j = 0; j < placePointList.size(); j++) {
                    placePoint = placePointList.get(j);
                    PlaceSquare placeSquare = new PlaceSquare(placePoint.getX(),placePoint.getY(),square.getL(),square.getW());
                    if(!isOverlap(placeSquareList,placeSquare)){
                        b = true;
                        // 移除当前角点
                        placePointList.remove(j);
                        //新增已放置的square
                        placeSquareList.add(new PlaceSquare(placePoint.getX(),placePoint.getY(),square.getL(),square.getW()));
                        // 新增两个可行角点
                        placePointList.add(new PlacePoint(placePoint.getX()+square.getL(),placePoint.getY()));
                        placePointList.add(new PlacePoint(placePoint.getX(),placePoint.getY()+square.getW()));
                        // 重新排序
                        Collections.sort(placePointList);
                        // 跳出内层循环
                        j = placePointList.size();
                    }
                }
                square.setL(l);
                square.setW(w);
            }
        }
        // 设置已经放置的矩形列表
        solution.setPlaceSquareList(new ArrayList<>(placeSquareList));
        // 计算利用率
        double rate = 0.0f;
        double s = 0.0f;
        for (PlaceSquare placeSquare : placeSquareList) {
            s += (placeSquare.getL()*placeSquare.getW());
        }
        rate = s/(L*W);
        solution.setRate(rate);
        return solution;
    }
    // 判断放置在该位置是否超出边界或者和其他矩形重叠
    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;

    }
    // 生成初始解
    public void getInitSolution() throws Exception {
        bestSolution = evaluate(new ArrayList<>(initGhh));
        tempSolution = bestSolution;
        bestGh = new ArrayList<>(initGhh);
        tempGh = new ArrayList<>(initGhh);
        LocalGh = new ArrayList<>(initGhh);
    }
    //加入禁忌队列
    public void enterTabooList(List<Square> squareList){
        if(tabuTreeMap == null){
            tabuTreeMap = new HashMap<>();
        }
        Square square = squareList.get(0);
        String id = square.getId();
        if(tabuTreeMap.containsKey(id)){
            tabuTreeMap.get(id).add(new ArrayList<>(squareList),1);
        }else{
            TabuMapTree tabuMapTree = new TabuMapTree();
            tabuMapTree.setNodeSquare(square);
            tabuMapTree.add(new ArrayList<>(squareList),1);
            tabuTreeMap.put(id,tabuMapTree);
        }

    }
    //生成新解
    public List<Square> generateNewGh(List<Square> localGh,List<Square> tempGh) {
        tempGh = new ArrayList<>(localGh);
        Collections.shuffle(tempGh);
        return tempGh;
    }
    //判断路径编码是否存在于禁忌表中
    public boolean judge(List<Square> Gh){
        Square square = Gh.get(0);
        if(tabuTreeMap.containsKey(square.getId())){
            return tabuTreeMap.get(square.getId()).contains(Gh,1);
        }else{
            return false;
        }
    }
    // 判断两个Squre是否相等
    public boolean isEq(Square square1,Square square2){
        return square1.getId().equals(square2.getId());
    }
}

11.ReadDataUtil类

package com.wskh.util;

import com.wskh.entitys.Instance;
import com.wskh.entitys.Square;

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.UUID;

/*
**  Create by: WSKH0929
    Date:2021-11-05
    Time:20:10
*/
public class ReadDataUtil {
    public Instance getInstance(String path) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new FileReader(path));
        String input = null;
        Instance instance = new Instance();
        List<Square> squareList = new ArrayList<>();
        boolean isFirstLine = true;
        while ((input=bufferedReader.readLine())!=null){
            String[] split = input.split(" ");
            if(isFirstLine){
                instance.setL(Double.parseDouble(split[0]));
                instance.setW(Double.parseDouble(split[1]));
                if(split[2].equals("1")){
                    instance.setRotateEnable(true);
                }else{
                    instance.setRotateEnable(false);
                }
                isFirstLine = false;
            }else{
                squareList.add(new Square(UUID.randomUUID().toString(),Double.parseDouble(split[0]),Double.parseDouble(split[1])));
            }
        }
        instance.setSquareList(squareList);
        return instance;
    }
}

12.Application类

package com.wskh;

import com.wskh.entitys.Instance;
import com.wskh.entitys.PlaceSquare;
import com.wskh.entitys.Solution;
import com.wskh.model.TabuSearch;
import com.wskh.util.ReadDataUtil;
import javafx.event.ActionEvent;
import javafx.event.EventHandler;
import javafx.scene.Camera;
import javafx.scene.PerspectiveCamera;
import javafx.scene.Scene;
import javafx.scene.canvas.Canvas;
import javafx.scene.canvas.GraphicsContext;
import javafx.scene.control.Alert;
import javafx.scene.control.Button;
import javafx.scene.input.KeyEvent;
import javafx.scene.layout.AnchorPane;
import javafx.scene.paint.Color;
import javafx.stage.Stage;

import java.lang.management.GarbageCollectorMXBean;
import java.util.List;
import java.util.Random;

/*
**  Create by: WSKH0929
    Date:2021-11-05
    Time:19:55
*/
public class Application 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";
        TabuSearch model = new TabuSearch(new ReadDataUtil().getInstance(path));
        Solution solution = model.search();
        //
        Instance instance = solution.getInstance();
        AnchorPane pane = new AnchorPane();
        pane = plot(pane,solution);
        Canvas canvas = new Canvas(instance.getL(),instance.getW());
        pane.getChildren().add(canvas);
        canvas.relocate(100,100);
        // 绘制最外层的矩形
        canvas = draw(canvas,0,0,instance.getL(),instance.getW());
        // 添加按钮
        Button nextButton = new Button("Next +1");
        Canvas finalCanvas = canvas;
        nextButton.setOnAction(new EventHandler<ActionEvent>() {
            @Override
            public void handle(ActionEvent actionEvent) {
                try {
                    PlaceSquare placeSquare = solution.getPlaceSquareList().get(counter);
                    draw(finalCanvas,placeSquare.getX(),placeSquare.getY(),placeSquare.getL(),placeSquare.getW());
                    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 AnchorPane plot(AnchorPane pane, Solution solution) {
        System.out.println(solution);

        // 绘制里面的矩形
//        List<PlaceSquare> placeSquareList = solution.getPlaceSquareList();
//        System.out.println(placeSquareList.size());
//        for (PlaceSquare placeSquare : placeSquareList) {
//            canvas = draw(canvas,placeSquare.getX(),placeSquare.getY(),placeSquare.getL(),placeSquare.getW());
//        }
        return pane;
    }

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

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

}

三、改进前运行结果(95%)

在这里插入图片描述
迭代300次，设置不允许旋转，最终求得利用率为：93%

迭代300次，设置允许旋转，最终求得利用率为95%

可以看到，虽然整体放得还是挺满了，但是放置的很不规整，导致很多空间是存在缺口的，这种现象是导致利用率不高的主要原因。后面我会对此做出改进，加入评分机制，每次放入和自己临近的矩形长或宽较为相似的矩形，以此来减少缺口的出现。

四、改进 ------ 引入评价指标，修改生成新解的规则

之前的旋转和放置都是比较盲目的，为了在单次装载中得到最好的结果，我们可以每次从庞大的候选矩形中根据一定的标准选出当前状态最佳放置矩形（即每次放入和自己临近的矩形长或宽较为相似的矩形，以此来减少缺口的出现），如此一来，便可以充分利用候选集中的优质资源，提高单次放置的利用率。
修改后的代码如下（将之前的TabuSearch、PlacePoint和Application类做了一点小修改）：

1.PlacePoint（修改后）

package com.wskh.entitys;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

/*
**  Create by: WSKH0929
    Date:2021-11-05
    Time:21:08
*/
@Data
@NoArgsConstructor
public class PlacePoint implements Comparable<PlacePoint>{
    private double x,y,len;

    public PlacePoint(double x, double y, double len) {
        this.x = x;
        this.y = y;
        this.len = len;
    }

    public PlacePoint(double x, double y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public int compareTo(PlacePoint o) {
        // 优先往下排 然后优先往左排
        int compare_y = Double.compare(y,o.y );
        if(compare_y!=0){
            return compare_y;
        }else{
            return Double.compare(x,o.x);
        }
    }
}

2.TabuSearch02类

package com.wskh.model;

import com.wskh.entitys.*;
import lombok.Data;

import java.util.*;

/*
**  Create by: WSKH0929
    Date:2021-11-05
    Time:20:26
*/
@Data
public class TabuSearch02 {
    public  final int MAX_GEN = 3000;//最大的迭代次数(提高这个值可以稳定地提高解质量，但是会增加求解时间)
    public  final int N = 200;//每次搜索领域的个数(这个值不要太大，太大的话搜索效率会降低)
    public  int sqNum ;//矩形数量，手动设置
    public HashMap<String,TabuMapTree> tabuTreeMap = new HashMap<>();
    public  List<Square> initGhh;//初始顺序
    public  List<Square> bestGh;//最佳顺序
    public  List<Square> LocalGh;//当前最好顺序
    public  List<Square> tempGh;//存放临时顺序
    public  int bestT;//最佳的迭代次数
    public Solution bestSolution;//最优解
    public  Solution LocalSolution;//每次领域搜索的最优解（领域最优解）
    public  Solution tempSolution;//临时解
    public  int t;//当前迭代
    public Random random;//随机函数对象
    // 问题实例
    public Instance instance;
    double L,W;

    public TabuSearch02(Instance instance) throws Exception {
        this.instance = instance;
        this.initGhh = new ArrayList<>(instance.getSquareList());
        // 初始化变量
        random = new Random(System.currentTimeMillis());
        L = instance.getL();
        W = instance.getW();
        sqNum = initGhh.size();
    }
    public Solution search() throws Exception {
        long start = System.currentTimeMillis();
        // 获取初始解
        getInitSolution();
        System.out.println(bestSolution.getRate());
        //开始迭代，停止条件为达到指定迭代次数
        while (t<=MAX_GEN){
            //当前领域搜索次数
            int n = 0;
            LocalSolution = new Solution();
            LocalSolution.setRate(0);
            while (n <= N){
                // 随机打乱顺序 得到当前编码Ghh的邻居编码tempGh
                tempGh = generateNewGh(new ArrayList<>(initGhh),new ArrayList<>(tempGh));
                // 判断其是否在禁忌表中
                if(!judge(tempGh)){
                    // 如果不在
                    //加入禁忌表
                    enterTabooList(tempGh);
                    tempSolution = evaluate(new ArrayList<>(tempGh));
                    if(tempSolution.getRate() > LocalSolution.getRate()){
                        // 如果临时解优于本次领域搜索的最优解
                        // 那么就将临时解替换本次领域搜索的最优解
                        LocalGh = new ArrayList<>(tempGh);
                        LocalSolution = tempSolution;
                    }
                }else{
//                    throw new Exception("重复");
                }
                n++;
            }
            if(LocalSolution.getRate() > bestSolution.getRate()){
                //如果本次搜索的最优解优于全局最优解
                //那么领域最优解替换全局最优解
                bestT = t;
                bestGh = new ArrayList<>(LocalGh);
                bestSolution = LocalSolution;
//                bestSolution = evaluate(bestGh);
            }
            initGhh = new ArrayList<>(LocalGh);
            t++;
            System.out.println("当前迭代次数为："+t+",当前最佳利用率为："+bestSolution.getRate());
        }
        //求解完毕
        System.out.println("最佳迭代次数:"+bestT);
        System.out.println("最佳利用率为:"+bestSolution.getRate());
        System.out.println("用时："+(System.currentTimeMillis()-start)+"ms");
        return bestSolution;
    }
    //评价函数
    public Solution evaluate(List<Square> squareList){
        Solution solution = new Solution();
        solution.setInstance(instance);
        solution.setSquareList(new ArrayList<>(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);
                //新增已放置的square
                placeSquareList.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);
//                System.out.println(placePointList);
                i = 0;
                // 还原矩形
                if(isRotate>0){
                    // 表示进行了旋转
                    square.setL(l);
                    square.setW(w);
                }
            }
        }
        // 设置已经放置的矩形列表
        solution.setPlaceSquareList(new ArrayList<>(placeSquareList));
        // 计算利用率
        double rate = 0.0f;
        double s = 0.0f;
        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;

    }
    // 生成初始解
    public void getInitSolution() throws Exception {
        Collections.shuffle(initGhh);
        bestSolution = evaluate(new ArrayList<>(initGhh));
        tempSolution = bestSolution;
        bestGh = new ArrayList<>(initGhh);
        tempGh = new ArrayList<>(initGhh);
        LocalGh = new ArrayList<>(initGhh);
    }
    //加入禁忌队列
    public void enterTabooList(List<Square> squareList){
        if(tabuTreeMap == null){
            tabuTreeMap = new HashMap<>();
        }
        Square square = squareList.get(0);
        String id = square.getId();
        if(tabuTreeMap.containsKey(id)){
            tabuTreeMap.get(id).add(new ArrayList<>(squareList),1);
        }else{
            TabuMapTree tabuMapTree = new TabuMapTree();
            tabuMapTree.setNodeSquare(square);
            tabuMapTree.add(new ArrayList<>(squareList),1);
            tabuTreeMap.put(id,tabuMapTree);
        }

    }
    //生成新解
//    public List<Square> generateNewGh(List<Square> localGh,List<Square> tempGh) {
//        tempGh = new ArrayList<>(localGh);
//        Collections.shuffle(tempGh);
//        return tempGh;
//    }
    public List<Square> generateNewGh(List<Square> localGh,List<Square> tempGh) {
        Square temp;
        //将Gh复制到tempGh
        tempGh = new ArrayList<>(localGh);

        for (int i = 0; i < 6; i++) {
            int r1 = 0;
            int r2 = 0;

            while (r1==r2){
                r1 = random.nextInt(tempGh.size());
                r2 = random.nextInt(tempGh.size());
            }
            //交换
            temp = tempGh.get(r1);
            tempGh.set(r1,tempGh.get(r2));
            tempGh.set(r2,temp);
        }

        return new ArrayList<>(tempGh);
    }
    //判断路径编码是否存在于禁忌表中
    public boolean judge(List<Square> Gh){
        Square square = Gh.get(0);
        if(tabuTreeMap.containsKey(square.getId())){
            return tabuTreeMap.get(square.getId()).contains(Gh,1);
        }else{
            return false;
        }
    }
    // 判断两个Squre是否相等
    public boolean isEq(Square square1,Square square2){
        return square1.getId().equals(square2.getId());
    }
}

3.Application（修改后）

package com.wskh;

import com.wskh.entitys.Instance;
import com.wskh.entitys.PlaceSquare;
import com.wskh.entitys.Solution;
import com.wskh.model.TabuSearch;
import com.wskh.model.TabuSearch02;
import com.wskh.util.ReadDataUtil;
import javafx.event.ActionEvent;
import javafx.event.EventHandler;

import javafx.scene.Scene;
import javafx.scene.canvas.Canvas;
import javafx.scene.canvas.GraphicsContext;
import javafx.scene.control.Alert;
import javafx.scene.control.Button;

import javafx.scene.layout.AnchorPane;
import javafx.scene.paint.Color;
import javafx.stage.Stage;

import java.util.Random;

/*
**  Create by: WSKH0929
    Date:2021-11-05
    Time:19:55
*/
public class Application 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";
//        TabuSearch model = new TabuSearch(new ReadDataUtil().getInstance(path));
        TabuSearch02 model = new TabuSearch02(new ReadDataUtil().getInstance(path));
        Solution solution = model.search();
        //
        Instance instance = solution.getInstance();
        AnchorPane pane = new AnchorPane();
        pane = plot(pane,solution);
        Canvas canvas = new Canvas(instance.getL(),instance.getW());
        pane.getChildren().add(canvas);
        canvas.relocate(100,100);
        // 绘制最外层的矩形
        canvas = draw(canvas,0,0,instance.getL(),instance.getW());
        // 添加按钮
        Button nextButton = new Button("Next +1");
        Canvas finalCanvas = canvas;
        nextButton.setOnAction(new EventHandler<ActionEvent>() {
            @Override
            public void handle(ActionEvent actionEvent) {
                try {
                    PlaceSquare placeSquare = solution.getPlaceSquareList().get(counter);
                    draw(finalCanvas,placeSquare.getX(),placeSquare.getY(),placeSquare.getL(),placeSquare.getW());
                    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 AnchorPane plot(AnchorPane pane, Solution solution) {
        System.out.println(solution);

        // 绘制里面的矩形
//        List<PlaceSquare> placeSquareList = solution.getPlaceSquareList();
//        System.out.println(placeSquareList.size());
//        for (PlaceSquare placeSquare : placeSquareList) {
//            canvas = draw(canvas,placeSquare.getX(),placeSquare.getY(),placeSquare.getL(),placeSquare.getW());
//        }
        return pane;
    }

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

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

五、改进后效果(利用率98.8%)

在这里插入图片描述

六、后话

其实改进的时候还改进了生成新解的方法，之前是用Collections.shuffle(list)的方式进行打乱的，这种方法是java自带的，内部的机制我也不是很清楚，猜测可能使用这种打乱方式会使新解和旧解序列相差较大，导致领域搜索失效，后来我采用两两互换重复6次的方法，即保证了较大的搜索域，又保证了不过于跳动。最终，改变随机生成新解的方法，使结果提高了0.8个百分点；其次，最重要的改进就是评分机制，它使得我们可以充分利用候选集丰富的资源，每次只选对结果最有利的矩形放入，尽可能的让剩余空间被占满，加入评分机制，使得结果提高了近3个百分点。

向您推荐>>Eolink开发者社区

权威｜前沿｜技术｜干货｜国内首个API全生命周期开发者社区

更多推荐

沃云统一开发平台介绍

沃云集成平台研发平台介绍1.平台优势2.平台原理3.研发平台使用方法4.遇到的问题5.现阶段实现的功能6.后续需要补充的功能和优化内容研发平台介绍1.平台优势解决孤岛式应用，实现能力共享；现有系统框架过于复杂，跨系统业务处理成本居高不下，协同服务共享，降低运维成本；提高项目应用资源监控能力，改善资源利用率；业务微服务化，快速发布、快速部署，快速响应业务需求变化；沃云平台不仅提供了自动化的、可快速部

云原生

(20200916 Solved)docker-compose up创建容器自动退出

问题描述如题，创建容器后自动退出了。并且docker start container无效解决方案原因是缺失了控制终端的配置，需要在docker-compose.yml中增加tty:true ，有时候这样也不行，需要再增加一个command:/bin/bash，命令不一定是这个，需要是一个不会退出的命令，然后用-d后台启动容器。Referencesdocker-compose启动容器后自动退出...

云原生

基于docker的test-containers环境百宝箱

笔者语录：我开了个公众号【Java你我他】，欢迎大家关注。在很多时候，程序猿们更关注代码本身，而不愿意把时间花费在环境搭建上，这也是Docker变得越来越受欢迎的原因之一。test-containe是Docker生态圈中的一颗新星，其主要针对测试领域、背靠Docker实现环境百宝箱功能。 test-containers：你要的环境，我都有~ 假设我们现在需要一个redis-clust