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

发布于:2022-11-09 ⋅ 阅读:(9) ⋅ 点赞:(0) ⋅ 评论:(0)


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

一、天际线启发式

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

二、自适应遗传算法结合天际线启发式

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

2.1 自适应交叉变异

GA 中的交叉概率和变异概率对于算法的搜索能力和收敛速度有着重要影响,自AGA被提出以来,众多优秀的改进自适应遗传算法陆续被提出,自适应遗传算法采用基于Sigmoid 曲线改进的自适应遗传算子来进一步提升算法寻优能力。

X = { X max ⁡ − X min ⁡ 1 + exp ⁡ ( A 2 ( v ′ − v a v g ) v max ⁡ − v a v g ) + X m i n , v ′ ⩾ v a v g X max ⁡ , v ′ < v a v g \begin{aligned} X &=\left\{\begin{array}{l} \frac{X_{\max }-X_{\min }}{1+\exp \left(A \frac{2\left(v^{\prime}-v_{a v g}\right)}{v_{\max }-v_{a v g}}\right)}+X_{m i n}, v^{\prime} \geqslant v_{a v g} \\ X_{\max }, v^{\prime}<v_{a v g} \end{array}\right.\\ \end{aligned} X= 1+exp(Avmaxvavg2(vvavg))XmaxXmin+Xmin,vvavgXmax,v<vavg
B = { B max ⁡ − B min ⁡ 1 + exp ⁡ ( A 2 ( v − v a v g ) v max ⁡ − v a v g ) + B min ⁡ , v ⩾ v a v g B max ⁡ , v < v a v g \begin{aligned} B=\left\{\begin{array}{l} \frac{B_{\max }-B_{\min }}{1+\exp \left(A \frac{2\left(v-v_{a v g}\right)}{v_{\max }-v_{a v g}}\right)}+B_{\min }, v \geqslant v_{a v g} \\ B_{\max }, v<v_{a v g} \end{array}\right. \end{aligned} B= 1+exp(Avmaxvavg2(vvavg))BmaxBmin+Bmin,vvavgBmax,v<vavg
上式中, A = 9.903438 , X A=9.903438, X A=9.903438,X B B B 分别表示交叉概率和变异概率, X max ⁡ X_{\max } Xmax X min ⁡ X_{\min } Xmin 分别表 示交叉概率最大值和最小值, B max ⁡ B_{\max } Bmax B min ⁡ B_{\min } Bmin 分别表示变异概率最大值和最小值, v ′ v^{\prime} v 表示 进行交叉的父母个体的适应度的较大值, v v v 表示变异个体的适应度, v max  v_{\text {max }} vmax  表示当代种群 的最大适应度, v a v g v_{a v g} vavg 表示当代种群的平均适应度。

下面是自适应交叉和变异的代码

/**
     * @param g1   基因1
     * @param g2   基因2
     * @param vAvg 当前种群的平均适应度
     * @param vMax 当前种群的最大适应度
     * @return 返回交叉概率
     * @Description 计算自适应的交叉概率
     */
    private double calcCrossoverRate(Genome g1, Genome g2, double vAvg, double vMax) {
        // 基因1和基因2中较小的适应度
        double v = Math.min(g1.getFitness(), g2.getFitness());
        // 计算交叉概率并返回
        return (crossoverRateBoundArr[1] - crossoverRateBoundArr[0]) / (1 + Math.exp(2 * A * (v - vAvg) / (vMax - vAvg))) + crossoverRateBoundArr[0];
    }

    /**
     * @param v    当前可能变异的基因的适应度
     * @param vAvg 当前种群的平均适应度
     * @param vMax 当前种群的最大适应度
     * @return 返回变异概率
     * @Description 计算自适应的变异概率
     */
    private double calcMutationRate(double v, double vAvg, double vMax) {
        if (compareDouble(v, vAvg) != -1) {
            return (mutationRateBoundArr[1] - mutationRateBoundArr[0]) / (1 + Math.exp(2 * A * (v - vAvg) / vMax - vAvg)) + mutationRateBoundArr[0];
        } else {
            return mutationRateBoundArr[1];
        }
    }

2.2 自适应选择策略

自适应的选择策略可以不单单依靠个体适应度的由高到低的排序来进行选择,它会根据遗传算法的进化特征自适应的选择将要进入交叉操作的个体。

首先挑选出种群中的最小适应度函数值,然后将种群中的所有个体的适应度函数值都减去这个最小值,然后根据新的适应度函数值采用轮盘赌法进行选择。这种策略在计算的过程中就可以动态的改变每个个体的适应度值。这样,个体的生存环境改变,评判标准也应随之发生变化。

下面是自适应选择的代码(其实就是对累积概率矩阵的计算做了调整)

    /**
     * @Description 自适应更新各个个体的累积概率和种群总适应度
     */
    public void updateProbabilityAndTotalFitness() {
        probabilitys = new double[population.size()];
        totalFitness = 0;
        double minFitness = population.get(0).getFitness();
        for (Genome genome : population) {
            totalFitness += genome.getFitness();
            minFitness = Math.min(genome.getFitness(), minFitness);
        }
        totalFitness -= (minFitness * population.size());
        double rate = 0.0;
        for (int i = 0; i < population.size(); i++) {
            rate += ((population.get(i).getFitness()-minFitness) / totalFitness);
            probabilitys[i] = rate;
        }
    }

三、Java代码实现

3.1 项目结构

红框以外的代码文件在上面说的博客里有,本博客只给 Run 、AGA和Genome 的代码

在这里插入图片描述

3.2 Genome

/**
 * @Author:WSKH
 * @ClassName:Genome
 * @ClassType:
 * @Description:
 * @Date:2022/6/4/12:55
 * @Email:1187560563@qq.com
 * @Blog:https://blog.csdn.net/weixin_51545953?type=blog
 */
public class Genome {

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

    //基因序列
    private int[] genomeArray;
    // 适应度函数值(在二维装箱问题中,其实就是装载利用率)
    private double fitness;
    // 序列对应的装载结果
    private Solution solution;

    /**
     * @param w 边界宽度
     * @param h 边界高度
     * @param items 矩形集合
     * @param isRotateEnable 是否可以旋转
     * @param genomeArray 基因序列
     * @Description 基因对象的构造函数
     */
    public Genome(double w, double h, Item[] items, boolean isRotateEnable, int[] genomeArray) {
        W = w;
        H = h;
        this.items = items;
        this.isRotateEnable = isRotateEnable;
        this.genomeArray = genomeArray;
    }

    /**
     * @Description 获取适应值和路径长度
     */
    public void updateFitnessAndSolution() {
        Item[] items = new Item[this.items.length];
        for (int i = 0; i < genomeArray.length; i++) {
            items[i] = this.items[genomeArray[i]];
        }
        solution = new SkyLinePacking(isRotateEnable, W, H, items).packing();
        fitness = solution.getRate();
    }

    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 Item[] getItems() {
        return items;
    }

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

    public boolean isRotateEnable() {
        return isRotateEnable;
    }

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

    public int[] getGenomeArray() {
        return genomeArray;
    }

    public void setGenomeArray(int[] genomeArray) {
        this.genomeArray = genomeArray;
    }

    public double getFitness() {
        return fitness;
    }

    public void setFitness(double fitness) {
        this.fitness = fitness;
    }

    public Solution getSolution() {
        return solution;
    }

    public void setSolution(Solution solution) {
        this.solution = solution;
    }
}

3.3 AGA

/**
 * @Author:WSKH
 * @ClassName:AGA
 * @ClassType:
 * @Description:
 * @Date:2022/6/4/12:55
 * @Email:1187560563@qq.com
 * @Blog:https://blog.csdn.net/weixin_51545953?type=blog
 */
public class AGA {

    // 最大的迭代次数
    private int MAX_GEN;
    // 种群数量信息
    private int popSize;
    // 变异对换次数
    private double variationExchangeCount;
    // 复制最优解的次数(选择种群的最优个体,然后复制几次,将最优个体复制多个,存到新的集合中)
    int cloneNumOfBestIndividual;
    // 基因突变概率系上下界数组
    private double[] mutationRateBoundArr;
    // 基因交叉概率上下界数组
    private double[] crossoverRateBoundArr;
    // 某参数(论文中是这么设置的,不用改)
    private final double A = 9.903438;

    // 种群总的适应度数值
    private double totalFitness;
    // 最好的适应度的对应的染色体(基因序列、路径序列)
    private Genome bestGenome;
    // 放置所有的种群基因信息
    private List<Genome> population = new ArrayList<>();
    // 新一代的种群基因信息
    private List<Genome> newPopulation = new ArrayList<>();
    // 遗传的代数(第几代)
    private int t = 0;
    // 最佳迭代次数
    private int bestT = -1;
    // 随机函数对象
    public Random random;
    // 各个个体的累积概率
    double[] probabilitys;

    // 矩形数量
    int itemNum;
    // 边界的宽
    private double W;
    // 边界的高
    private double H;
    // 矩形数组
    Item[] items;
    // 是否可以旋转
    private boolean isRotateEnable;

    /**
     * @param MAX_GEN                  迭代次数(提高这个值可以稳定地提高解质量,但是会增加求解时间)
     * @param popSize                  种群大小
     * @param variationExchangeCount   变异时的两两对换次数
     * @param cloneNumOfBestIndividual 复制最优解的次数(一般小于种群数量的5%,选择种群的最优个体,然后复制几次,将最优个体复制多个,存到新的集合中,有助于保持优良基因)
     * @param mutationRateBoundArr     [最小基因突变概率,最大基因突变概率]
     * @param crossoverRateBoundArr    [最小基因交叉概率,最大基因交叉概率]
     * @param instance                 实例对象
     * @param seed                     随机数种子,如果传入null则不设置随机数种子,否则按照传入的种子进行设置,方便复现结果
     * @Description 遗传算法的构造函数
     */
    public AGA(int MAX_GEN, int popSize, int variationExchangeCount, int cloneNumOfBestIndividual, double[] mutationRateBoundArr, double[] crossoverRateBoundArr, Instance instance, Long seed) {
        this.MAX_GEN = MAX_GEN;
        this.popSize = popSize;
        this.variationExchangeCount = variationExchangeCount;
        this.cloneNumOfBestIndividual = cloneNumOfBestIndividual;
        this.mutationRateBoundArr = mutationRateBoundArr;
        this.crossoverRateBoundArr = crossoverRateBoundArr;
        this.W = instance.getW();
        this.H = instance.getH();
        this.isRotateEnable = instance.isRotateEnable();
        this.items = Item.copy(instance.getItemList().toArray(new Item[0]));
        this.random = seed == null ? new Random() : new Random(seed);
    }

    /**
     * @return 最佳装载结果对象Solution
     * @Description 遗传算法主函数
     */
    public Solution solve() {
        initVar();
        while (t < MAX_GEN) {
            popSize = population.size();
            // 基因进化
            evolution();
            // 更新种群
            population = copyGenomeList(newPopulation);
            t++;
        }
        return bestGenome.getSolution();
    }

    /**
     * @Description 进化函数,正常交叉变异
     */
    public void evolution() {
        //更新累积概率和总适应度
        updateProbabilityAndTotalFitness();
        // 挑选某代种群中适应度最高的个体
        selectBestGenomeAndJoinNext();
        // 赌轮选择策略对剩下的scale-1个个体进行随机的交叉,变异
        while (newPopulation.size() < population.size()) {
            double r = random.nextDouble();
            for (int j = 0; j < probabilitys.length; j++) {
                if (compareDouble(r, probabilitys[j]) != 1) {
                    newPopulation.add(population.get(j));
                    break;
                }
            }
        }
        // 计算当前种群的最大适应度和平均适应度
        double vMax = population.get(0).getFitness();
        double vSum = 0;
        for (Genome genome : population) {
            vSum += genome.getFitness();
            vMax = Math.max(genome.getFitness(), vMax);
        }
        double vAvg = vSum / population.size();
        // 自适应交叉
        int r = random.nextInt(popSize);
        int k = random.nextInt(popSize);
        while (r == k) {
            r = random.nextInt(popSize);
        }
        if (compareDouble(random.nextDouble(), calcCrossoverRate(population.get(r), population.get(k), vAvg, vMax)) != 1) {
            cross(k, r);
        }
        // 自适应变异
        for (int i = 0; i < population.size(); i++) {
            if (compareDouble(random.nextDouble(), calcMutationRate(population.get(i).getFitness(), vAvg, vMax)) != 1) {
                variation(i);
            }
        }
    }

    /**
     * @param g1   基因1
     * @param g2   基因2
     * @param vAvg 当前种群的平均适应度
     * @param vMax 当前种群的最大适应度
     * @return 返回交叉概率
     * @Description 计算自适应的交叉概率
     */
    private double calcCrossoverRate(Genome g1, Genome g2, double vAvg, double vMax) {
        // 基因1和基因2中较小的适应度
        double v = Math.min(g1.getFitness(), g2.getFitness());
        // 计算交叉概率并返回
        return (crossoverRateBoundArr[1] - crossoverRateBoundArr[0]) / (1 + Math.exp(2 * A * (v - vAvg) / (vMax - vAvg))) + crossoverRateBoundArr[0];
    }

    /**
     * @param v    当前可能变异的基因的适应度
     * @param vAvg 当前种群的平均适应度
     * @param vMax 当前种群的最大适应度
     * @return 返回变异概率
     * @Description 计算自适应的变异概率
     */
    private double calcMutationRate(double v, double vAvg, double vMax) {
        if (compareDouble(v, vAvg) != -1) {
            return (mutationRateBoundArr[1] - mutationRateBoundArr[0]) / (1 + Math.exp(2 * A * (v - vAvg) / vMax - vAvg)) + mutationRateBoundArr[0];
        } else {
            return mutationRateBoundArr[1];
        }
    }

    /**
     * @param k1 基因1的索引
     * @param k2 基因2的索引
     * @Description 对基因1和基因2进行单点映射交叉
     */
    private void cross(int k1, int k2) {
        // 获取要交叉的两个基因
        int[] genomeArray1 = newPopulation.get(k1).getGenomeArray();
        int[] genomeArray2 = newPopulation.get(k2).getGenomeArray();
        // 找到交叉位置
        int crossIndex = random.nextInt(itemNum);
        // 获取交叉片段
        for (int i = 0; i <= crossIndex; i++) {
            int temp = genomeArray1[i];
            genomeArray1[i] = genomeArray2[i];
            genomeArray2[i] = temp;
        }
        // 找到重复基因
        HashSet<Integer> set = new HashSet<>();
        // <index,value>
        HashMap<Integer, Integer> repeatMap = new HashMap<>();
        for (int i = 0; i < genomeArray1.length; i++) {
            if (!set.add(genomeArray1[i])) {
                repeatMap.put(i, genomeArray1[i]);
            }
        }
        set.clear();
        for (int i = 0; i < genomeArray2.length; i++) {
            if (!set.add(genomeArray2[i])) {
                for (int key : repeatMap.keySet()) {
                    genomeArray1[key] = genomeArray2[i];
                    genomeArray2[i] = repeatMap.get(key);
                    repeatMap.remove(key);
                    break;
                }
            }
        }
        // 交叉完毕,将基因放回个体,再将个体放回种群,并更新他们的适应值和路径长度
        newPopulation.get(k1).setGenomeArray(genomeArray1);
        newPopulation.get(k1).updateFitnessAndSolution();
        newPopulation.get(k2).setGenomeArray(genomeArray2);
        newPopulation.get(k2).updateFitnessAndSolution();
    }

    /**
     * @param k 要进行变异的基因索引
     * @Description 变异(n次两两对换)
     */
    private void variation(int k) {
        Genome genome = newPopulation.get(k);
        int[] genomeArray = genome.getGenomeArray();
        for (int i = 0; i < variationExchangeCount; i++) {
            int r1 = random.nextInt(itemNum);
            int r2 = random.nextInt(itemNum);
            while (r1 == r2) {
                r2 = random.nextInt(itemNum);
            }
            //交换
            int temp = genomeArray[r1];
            genomeArray[r1] = genomeArray[r2];
            genomeArray[r2] = temp;
        }
        //将变异后的基因序列放回个体
        genome.setGenomeArray(genomeArray);
        // 更新基因的适应值和路程长度
        genome.updateFitnessAndSolution();
        //将变异后的个体放回种群
        newPopulation.set(k, genome);
    }

    /**
     * @Description 初始化函数,进行一些初始化操作
     */
    public void initVar() {
        this.itemNum = this.items.length;
        this.population = new ArrayList<>();
        //初始化种群信息
        List<Integer> sequence = new ArrayList<>();
        for (int i = 0; i < itemNum; i++) {
            sequence.add(i);
        }
        for (int i = 0; i < popSize; i++) {
            Collections.shuffle(sequence);
            int[] initSequence = new int[itemNum];
            for (int j = 0; j < sequence.size(); j++) {
                initSequence[j] = sequence.get(j);
            }
            Genome genome = new Genome(W, H, items, isRotateEnable, initSequence.clone());
            genome.updateFitnessAndSolution();
            population.add(genome);
        }
        bestGenome = copyGenome(population.get(0));
        for (int i = 1; i < popSize; i++) {
            Genome genome = population.get(i);
            if (bestGenome.getFitness() < genome.getFitness()) {
                bestGenome = copyGenome(genome);
            }
        }
        System.out.println("初始解为:" + bestGenome.getSolution().getRate());
    }

    /**
     * @Description 挑选种群中适应度最大的个体基因,并复制n份,直接加入下一代种群
     */
    public void selectBestGenomeAndJoinNext() {
        newPopulation = new ArrayList<>();
        Genome tempBest = population.get(0);
        for (int i = 1; i < population.size(); i++) {
            if (population.get(i).getFitness() > tempBest.getFitness()) {
                tempBest = population.get(i);
            }
        }
        if (compareDouble(tempBest.getFitness(), bestGenome.getFitness()) == 1) {
            bestGenome = copyGenome(tempBest);
            bestT = t;
            System.out.println("当前代数: " + t + " : " + bestGenome.getSolution().getRate());
        }
        for (int i = 0; i < cloneNumOfBestIndividual; i++) {
            newPopulation.add(copyGenome(tempBest));
        }
    }

    /**
     * @Description 自适应更新各个个体的累积概率和种群总适应度
     */
    public void updateProbabilityAndTotalFitness() {
        probabilitys = new double[population.size()];
        totalFitness = 0;
        double minFitness = population.get(0).getFitness();
        for (Genome genome : population) {
            totalFitness += genome.getFitness();
            minFitness = Math.min(genome.getFitness(), minFitness);
        }
        totalFitness -= (minFitness * population.size());
        double rate = 0.0;
        for (int i = 0; i < population.size(); i++) {
            rate += ((population.get(i).getFitness() - minFitness) / totalFitness);
            probabilitys[i] = rate;
        }
    }

    /**
     * @param genome 模板基因
     * @return 返回拷贝好的基因
     * @Description 根据传入的模板基因,进行拷贝,返回拷贝好的基因
     */
    public Genome copyGenome(Genome genome) {
        Genome copy = new Genome(genome.getW(), genome.getH(), genome.getItems(), genome.isRotateEnable(), genome.getGenomeArray().clone());
        copy.setSolution(genome.getSolution());
        copy.setFitness(genome.getFitness());
        return copy;
    }

    /**
     * @param genomeList 模板基因集合
     * @return 返回拷贝好的基因集合
     * @Description 根据传入的模板基因集合,进行拷贝,返回拷贝好的基因集合
     */
    public List<Genome> copyGenomeList(List<Genome> genomeList) {
        List<Genome> copyList = new ArrayList<>();
        for (Genome genome : genomeList) {
            copyList.add(copyGenome(genome));
        }
        return copyList;
    }

    /**
     * @param d1 双精度浮点型变量1
     * @param d2 双精度浮点型变量2
     * @return 返回0代表两个数相等,返回1代表前者大于后者,返回-1代表前者小于后者,
     * @Description 判断两个双精度浮点型变量的大小关系
     */
    private int compareDouble(double d1, double d2) {
        // 定义一个误差范围,如果两个数相差小于这个误差,则认为他们是相等的 1e-06 = 0.000001
        double error = 1e-06;
        if (Math.abs(d1 - d2) < error) {
            return 0;
        } else if (d1 < d2) {
            return -1;
        } else if (d1 > d2) {
            return 1;
        } else {
            throw new RuntimeException("d1 = " + d1 + " , d2 = " + d2);
        }
    }

}

3.4 Run

/**
 * @Author:WSKH
 * @ClassName:Run
 * @ClassType:
 * @Description:运行程序的主类
 * @Date:2022/11/6/19:39
 * @Email:1187560563@qq.com
 * @Blog:https://blog.csdn.net/weixin_51545953?type=blog
 */
public class Run extends javafx.application.Application {

    private int counter = 0;

    @Override
    public void start(Stage primaryStage) throws Exception {

        // 数据地址
        String path = "src/main/java/com/wskh/data/data.txt";
        // 根据txt文件获取实例对象
        Instance instance = new ReadDataUtil().getInstance(path);
        // 记录算法开始时间
        long startTime = System.currentTimeMillis();
        // 实例化遗传算法对象
        AGA aga = new AGA(1000, 200, 1, 10, new double[]{0.2, 1.0}, new double[]{0.92, 0.98}, instance, null);
        // 调用遗传算法对象进行求解
        Solution solution = aga.solve();
        // 输出相关信息
        System.out.println("------------------------------------------------------------------------------------");
        System.out.println("求解用时:" + (System.currentTimeMillis() - startTime) / 1000.0 + " s");
        System.out.println("共放置了矩形" + solution.getPlaceItemList().size() + "个");
        System.out.println("最佳利用率为:" + solution.getRate());
        // 输出画图数据
        String[] strings1 = new String[solution.getPlaceItemList().size()];
        String[] strings2 = new String[solution.getPlaceItemList().size()];
        for (int i = 0; i < solution.getPlaceItemList().size(); i++) {
            PlaceItem placeItem = solution.getPlaceItemList().get(i);
            strings1[i] = "{x:" + placeItem.getX() + ",y:" + placeItem.getY() + ",l:" + placeItem.getH() + ",w:" + placeItem.getW() + "}";
            strings2[i] = placeItem.isRotate() ? "1" : "0";
        }
        System.out.println("data:" + Arrays.toString(strings1) + ",");
        System.out.println("isRotate:" + Arrays.toString(strings2) + ",");

        // --------------------------------- 后面这些都是画图相关的代码,可以不用管 ---------------------------------------------
        AnchorPane pane = new AnchorPane();
        Canvas canvas = new Canvas(instance.getW(), instance.getH());
        pane.getChildren().add(canvas);
        canvas.relocate(100, 100);
        // 绘制最外层的矩形
        canvas = draw(canvas, 0, 0, instance.getW(), instance.getH(), true);
        // 添加按钮
        Button nextButton = new Button("Next +1");
        Canvas finalCanvas = canvas;
        nextButton.setOnAction(new EventHandler<ActionEvent>() {
            @Override
            public void handle(ActionEvent actionEvent) {
                try {
                    PlaceItem placeItem = solution.getPlaceItemList().get(counter);
                    draw(finalCanvas, placeItem.getX(), placeItem.getY(), placeItem.getW(), placeItem.getH(), false);
                    counter++;
                } catch (Exception e) {
                    Alert alert = new Alert(Alert.AlertType.WARNING);
                    alert.setContentText("已经没有可以放置的矩形了!");
                    alert.showAndWait();
                }
            }
        });
        //
        pane.getChildren().add(nextButton);
        primaryStage.setTitle("二维矩形装箱可视化");
        primaryStage.setScene(new Scene(pane, 1000, 1000, Color.AQUA));
        primaryStage.show();
    }

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

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

}

3.5 运行结果展示

输出(最后两行是在前端画图用的,可以忽略):

初始解为:0.98063125
当前代数: 1 : 0.98559375
当前代数: 3 : 0.98716875
当前代数: 5 : 0.98799375
当前代数: 21 : 0.9898625
当前代数: 23 : 0.99146875
当前代数: 26 : 0.9920625
当前代数: 88 : 0.99400625
当前代数: 183 : 0.9951
当前代数: 208 : 0.9967
------------------------------------------------------------------------------------
求解用时:14.81 s
共放置了矩形30个
最佳利用率为:0.9967
data:[{x:0.0,y:0.0,l:29.0,w:117.0}, {x:316.0,y:0.0,l:87.0,w:84.0}, {x:261.0,y:0.0,l:87.0,w:55.0}, {x:179.0,y:0.0,l:66.0,w:82.0}, {x:117.0,y:0.0,l:91.0,w:62.0}, {x:0.0,y:29.0,l:80.0,w:117.0}, {x:179.0,y:66.0,l:40.0,w:82.0}, {x:261.0,y:87.0,l:86.0,w:55.0}, {x:316.0,y:87.0,l:96.0,w:84.0}, {x:117.0,y:91.0,l:60.0,w:62.0}, {x:179.0,y:106.0,l:93.0,w:82.0}, {x:0.0,y:109.0,l:107.0,w:117.0}, {x:117.0,y:151.0,l:51.0,w:62.0}, {x:261.0,y:173.0,l:73.0,w:55.0}, {x:316.0,y:183.0,l:106.0,w:84.0}, {x:179.0,y:199.0,l:57.0,w:82.0}, {x:117.0,y:202.0,l:38.0,w:62.0}, {x:0.0,y:216.0,l:71.0,w:117.0}, {x:117.0,y:240.0,l:47.0,w:52.0}, {x:261.0,y:246.0,l:24.0,w:55.0}, {x:169.0,y:256.0,l:107.0,w:92.0}, {x:261.0,y:270.0,l:103.0,w:21.0}, {x:282.0,y:270.0,l:47.0,w:34.0}, {x:0.0,y:287.0,l:113.0,w:100.0}, {x:102.0,y:287.0,l:76.0,w:67.0}, {x:321.0,y:289.0,l:111.0,w:79.0}, {x:282.0,y:317.0,l:59.0,w:39.0}, {x:100.0,y:363.0,l:37.0,w:68.0}, {x:168.0,y:363.0,l:37.0,w:92.0}, {x:260.0,y:376.0,l:24.0,w:61.0}],
isRotate:[0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0],

可视化展示(利用率 99.86%)

在这里插入图片描述