1.3 求解案例之Cloud balancing-一一网

这是我参与更文挑战的第3天，活动详情查看：更文挑战

内容概要

上一篇文章，我们学习了OptaPlanner的基本使用，及部分基本概念。也学会构建一个课程分配的例子。这次我们继续来通过案例来学习OptaPlanner的使用。

问题描述

假设你的公司拥有一些云计算机，需要在这些计算机上运行一些进程，需要将每个进程分配到一台计算机上运行。
必须满足以下硬约束：

每台计算机必须能够处理其进程总和的最低硬件要求。
- CPU功率：一台计算机的CPU功率必须至少是分配给该计算机的进程所需的CPU功率之和。
- 内存容量：一台计算机的RAM内存必须至少是分配给该计算机的进程所需的RAM内存的总和。
- 网络容量：一台计算机的网络带宽必须至少是分配给该计算机的进程所需的网络带宽之和。

应优化以下软约束：

每台分配有一个或多个进程的计算机都会产生维护费用（每台计算机的费用是固定的）。
- 成本：使总的维护成本最小化。

这个问题是装箱问题的一种形式。下面是一个简化的例子，我们用一个简单的算法，将四个进程分配给两台有两个约束条件（CPU和RAM）的计算机。

这里使用的简单算法是贪心算法（又称贪婪算法，是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解）。

它首先分配较大的进程，然后将较小的进程分配到剩余空间。正如我们所看到的，这不是最优的，因为它没有留下足够的空间来分配黄色进程D。

OptaPlanner通过使用额外的、更智能的算法找到了更理想的解决方案。它还可以扩展：在数据（更多的进程，更多的计算机）和约束（更多的硬件要求，其他约束）方面。

问题大小

我们从下面的表格来看不同线程数、计算机数的搜索空间是多大。

业务建模

我们在建模的时候，要区分出来哪些是 Planning entities规划实体，它们的哪些属性是Planning variables规划属性。
这个例子的模型中定义出代表问题的输入数据对象，这个简单例子中，这些对象就是Computer、Progress。
在这个模型中的一个单独的对象必须代表问题的完整数据集，其中包含输入数据以及解决方案。在这个例子中，这个对象持有一个Computer的列表和一个Progress的列表。每个Progress被分配给一台Computer；Computer之间的Progress分配就是解决方案。

步骤

绘制UML图。
规划模型数据，不要出现重复数据。
写出模型内每一个实例：
- Computer: 代表一台有一定硬件和维护费用的计算机。在这个例子中，Computer的属性是：cpuPower, memory, networkBandwidth, cost.。
- Progress：代表一个有需求的进程。需要由OptaPlanner分配给一台计算机。Progress的属性有：requiredCpuPower, requiredMemory, and requiredNetworkBandwidth.
- CloudBalance：代表一个Problem。包含某个数据集的每台计算机和进程。
找出哪些字段在求解期间会发生变化。
- Planning entity：OptaPlanner在求解过程中可以改变的类。在这个例子中，它是Progress类，因为OptaPlanner可以将Progress分配给Computer。
- Planning variable: 在求解过程中发生变化的PlanningEntity类的属性。在这个例子中，它是Progress类上的属性computer。
- Problem fact: 求解数据支持的类。Computer就是提供数据，求解过程中不会改变任何信息。
- Planning solution: 代表问题解决方案的类。这个类必须代表完整的数据集并包含所有的规划实体。在这个例子中，就是CloudBalance这个类。

UML图

对象具体实现

Computer

public class CloudComputer ... {

    private int cpuPower;
    private int memory;
    private int networkBandwidth;
    private int cost;

    ... // getters
}
复制代码

Progress

Progress类非常重要，它是在求解过程中被修改的类。
我们需要告诉OptaPlanner，它可以修改属性computer。使用@PlanningEntity来注解这个类，并且用@PlanningVariable注解getter getComputer()方法。
OptaPlanner是通过setter方法进行修改的，所以需要有setter方法。

@PlanningEntity
public class CloudProcess ... {

    private int requiredCpuPower;
    private int requiredMemory;
    private int requiredNetworkBandwidth;

    private CloudComputer computer;

    ... // getters

    @PlanningVariable(valueRangeProviderRefs = {"computerRange"})
    public CloudComputer getComputer() {
        return computer;
    }

    public void setComputer(CloudComputer computer) {
        computer = computer;
    }
    ...

}
复制代码

OptaPlanner需要知道它可以选择哪些值来分配给属性computer。这些值从规划方案上的CloudBalance.getComputerList()方法中获取，该方法返回当前数据集中所有计算机的列表。
CloudProcess.getComputer()上的@PlanningVariable的valueRangeProviderRefs参数需要与CloudBalance.getComputerList()上的@ValueRangeProvider的id一一对应。

CloudBalance

CloudBalance类有一个@PlanningSolution注解，这个类是求解过程中数据的入口和最后结果的出口。它拥有Computer List 和 Progress List数据，其中Progress类中的computer就是整个最后结果的输出，因为我们求解的结果就是每个Progress分配到了哪台Computer。

@PlanningSolution
public class CloudBalance ... {

    private List<CloudComputer> computerList;

    private List<CloudProcess> processList;

    private HardSoftScore score;

    @ValueRangeProvider(id = "computerRange")
    @ProblemFactCollectionProperty
    public List<CloudComputer> getComputerList() {
        return computerList;
    }

    @PlanningEntityCollectionProperty
    public List<CloudProcess> getProcessList() {
        return processList;
    }

    @PlanningScore
    public HardSoftScore getScore() {
        return score;
    }

    public void setScore(HardSoftScore score) {
        this.score = score;
    }

    ...
}
复制代码

processList属性持有一个进程的列表。OptaPlanner可以改变进程，将它们分配给不同的计算机。因此，进程是一个ProblemEntity规划实体，processList是一个规划实体的集合。需要在getProcessList()方法上添加@PlanningEntityCollectionProperty注解。
computerList属性持有一个计算机的列表。OptaPlanner不能改变这些计算机。因此，计算机是一个ProblemFact问题事实。特别是对于使用Drools的分数计算，属性computerList需要用@ProblemFactCollectionProperty来注解，这样OptaPlanner就可以检索到计算机列表（ProblemFact），并使其对Drools引擎可用。
CloudBalance类也有一个@PlanningScore注解的属性score，它是该解决方案在当前状态下的得分。OptaPlanner在计算一个解决方案实例的Score时会自动更新它。因此，这个属性需要一个setter。

约束分值定义

到这里模型我们已经建立完毕，因为OptaPlanner是通过分数来判断每个解决方案的好坏，所以下一步我们需要编写出对应的分数计算，并且将“问题描述”内的硬/软约束编写成相对应的代码。
我们先来看一张图：

AB线程分配到XY机器上的，三个不同的结果最终的分值结果展示。
从问题的描述中，我们可以得出此问题存在硬约束和软约束，硬约束通常代表不能被打破的约束条件，软约束是一种期望不配打破的条件。

约束配置类

从问题上我们得出来，3个硬约束和1个软约束的规则。
CloudBalancingConstraintProvider.java

public class CloudBalancingConstraintProvider implements ConstraintProvider {

    @Override
    public Constraint[] defineConstraints(ConstraintFactory constraintFactory) {
        return new Constraint[] {
                requiredCpuPowerTotal(constraintFactory),
                requiredMemoryTotal(constraintFactory),
                requiredNetworkBandwidthTotal(constraintFactory),
                computerCost(constraintFactory)
        };
    }

    // ************************************************************************
    // Hard constraints - 硬约束
    // ************************************************************************

    Constraint requiredCpuPowerTotal(ConstraintFactory constraintFactory) {
        return constraintFactory.from(CloudProcess.class)
                .groupBy(CloudProcess::getComputer, sum(CloudProcess::getRequiredCpuPower))
                .filter((computer, requiredCpuPower) -> requiredCpuPower > computer.getCpuPower())
                .penalize("requiredCpuPowerTotal",
                        HardSoftScore.ONE_HARD,
                        (computer, requiredCpuPower) -> requiredCpuPower - computer.getCpuPower());
    }

    Constraint requiredMemoryTotal(ConstraintFactory constraintFactory) {
        return constraintFactory.from(CloudProcess.class)
                .groupBy(CloudProcess::getComputer, sum(CloudProcess::getRequiredMemory))
                .filter((computer, requiredMemory) -> requiredMemory > computer.getMemory())
                .penalize("requiredMemoryTotal",
                        HardSoftScore.ONE_HARD,
                        (computer, requiredMemory) -> requiredMemory - computer.getMemory());
    }

    Constraint requiredNetworkBandwidthTotal(ConstraintFactory constraintFactory) {
        return constraintFactory.from(CloudProcess.class)
                .groupBy(CloudProcess::getComputer, sum(CloudProcess::getRequiredNetworkBandwidth))
                .filter((computer, requiredNetworkBandwidth) -> requiredNetworkBandwidth > computer.getNetworkBandwidth())
                .penalize("requiredNetworkBandwidthTotal",
                        HardSoftScore.ONE_HARD,
                        (computer, requiredNetworkBandwidth) -> requiredNetworkBandwidth - computer.getNetworkBandwidth());
    }

    // ************************************************************************
    // Soft constraints - 软约束
    // ************************************************************************

    Constraint computerCost(ConstraintFactory constraintFactory) {
        return constraintFactory.from(CloudComputer.class)
                .ifExists(CloudProcess.class, equal(Function.identity(), CloudProcess::getComputer))
                .penalize("computerCost",
                        HardSoftScore.ONE_SOFT,
                        CloudComputer::getCost);
    }

}
复制代码

requiredCpuPowerTotal当前规则表示，若当前progress进程分配的目标Computer计算机，它的cpuPower小于当前Computer上所有progress进程所需的cpuPower之和，则进行惩罚处理，级别是硬约束HardSoftScore.ONE_HARD，分值是cpuPower超出的部分。
requiredMemoryTotal当前规则表示，若当前progress进程分配的目标Computer计算机，它的memory小于当前Computer上所有progress进程所需的memory之和，则进行惩罚处理，级别是硬约束HardSoftScore.ONE_HARD，分值是memory超出的部分。
requiredNetworkBandwidthTotal当前规则表示，若当前progress进程分配的目标Computer计算机，它的networkBandwidth小于当前Computer上所有progress进程所需的networkBandwidth之和，则进行惩罚处理，级别是硬约束HardSoftScore.ONE_HARD，分值是networkBandwidth超出的部分。
computerCost规则表示当前所花费的成本，用惩罚性分数来表达，分数值是每个Computer的cost。

运行CloudBalance程序

现在我们来编写一个HelloWorld类CloudBalancingHelloWorld.java。

public class CloudBalancingHelloWorld {

    public static void main(String[] args) {
        // 创建求解器
        SolverFactory<CloudBalance> solverFactory = SolverFactory.create(new SolverConfig()
                .withSolutionClass(CloudBalance.class)
                .withEntityClasses(CloudProcess.class)
                .withConstraintProviderClass(CloudBalancingConstraintProvider.class)
                .withTerminationSpentLimit(Duration.ofMinutes(2)));
        Solver<CloudBalance> solver = solverFactory.buildSolver();

        // 加载一个有400台电脑和1200个进程的数据
        CloudBalance unsolvedCloudBalance = new CloudBalancingGenerator().createCloudBalance(400, 1200);

        // 提交求解
        CloudBalance solvedCloudBalance = solver.solve(unsolvedCloudBalance);

        // 输出结果
        System.out.println("\nSolved cloudBalance with 400 computers and 1200 processes:\n"
                + toDisplayString(solvedCloudBalance));
    }

    public static String toDisplayString(CloudBalance cloudBalance) {
        StringBuilder displayString = new StringBuilder();
        for (CloudProcess process : cloudBalance.getProcessList()) {
            CloudComputer computer = process.getComputer();
            displayString.append("  ").append(process.getLabel()).append(" -> ")
                    .append(computer == null ? null : computer.getLabel()).append("\n");
        }
        return displayString.toString();
    }

}
复制代码