【运筹优化】禁忌搜索算法求解二维矩形装箱问题(java代码实现)
给定一个矩形容器和若干个小的矩形,需要在不超出容器的情况下,求出利用率最高的小矩形放置方案,一个可行的放置方案如下图所示:本文首先展示我最初的做法,该做法运行速度快,但求解质量差。最后会展示改进后的方法,改进后,虽然运行速度下降了约10倍运行速度下降了约10倍,但是解的质量提高了3%3.data.txt4.Instance类5.PlacePoint类6.PlaceSquare类7.Solution
文章目录
一、何为二维矩形装箱问题?
给定一个矩形容器和若干个小的矩形,需要在不超出容器的情况下,求出利用率最高的小矩形放置方案,一个可行的放置方案如下图所示:
本文首先展示我最初的做法,该做法运行速度快,但求解质量差。最后会展示改进后的方法,改进后,虽然运行速度下降了约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
400 400 0
59 115
26 99
68 97
41 63
99 116
21 60
79 118
113 85
86 55
33 114
76 70
27 47
117 40
30 46
60 62
87 55
21 108
60 67
82 93
44 49
84 96
89 34
47 34
94 44
117 80
91 62
112 73
37 92
50 48
113 100
24 55
56 27
103 21
61 24
116 111
51 62
67 76
95 57
113 116
63 49
44 56
52 47
33 66
102 53
117 107
40 106
109 27
79 99
40 82
98 96
105 105
94 31
97 78
50 23
86 22
39 59
54 92
37 67
81 102
58 33
113 88
117 71
20 58
65 63
20 116
114 69
117 29
99 88
90 49
35 80
84 87
79 111
97 25
115 21
82 66
79 84
71 38
68 80
57 82
30 73
102 31
68 42
109 106
40 42
24 71
95 101
39 94
100 108
102 26
57 89
108 54
92 107
38 62
38 32
115 46
68 37
106 84
55 73
48 103
107 64
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个百分点。
更多推荐
所有评论(0)