引言
约束设计的过程就是定义的规则的过程
,包括硬约束(必须满足的条件)和软约束(尽量满足的条件)。硬约束通常用于描述问题的基本限制,比如每台计算机不能出现超频的情况。软约束用于描述优化目标,如尽量降低维护成本。
约束设计
在 OptaPlanner 中,有三种主要的分数计算方式:Easy Java, Constraint Streams, 和 Incremental Java。下面是这三种方法的对比。
Easy Java
实现EasyScoreCalculator的calculateScore(Solution)方法,使其返回一个HardSoftScore实例。
public class CloudBalancingEasyScoreCalculator
implements EasyScoreCalculator<CloudBalance, HardSoftScore> {
/**
* A very simple implementation. The double loop can easily be removed by using Maps as shown in
* {@link CloudBalancingMapBasedEasyScoreCalculator#calculateScore(CloudBalance)}.
*/
@Override
public HardSoftScore calculateScore(CloudBalance cloudBalance) {
int hardScore = 0;
int softScore = 0;
for (CloudComputer computer : cloudBalance.getComputerList()) {
int cpuPowerUsage = 0;
int memoryUsage = 0;
int networkBandwidthUsage = 0;
boolean used = false;
// Calculate usage
for (CloudProcess process : cloudBalance.getProcessList()) {
if (computer.equals(process.getComputer())) {
cpuPowerUsage += process.getRequiredCpuPower();
memoryUsage += process.getRequiredMemory();
networkBandwidthUsage += process.getRequiredNetworkBandwidth();
used = true;
}
}
// Hard constraints
int cpuPowerAvailable = computer.getCpuPower() - cpuPowerUsage;
if (cpuPowerAvailable < 0) {
hardScore += cpuPowerAvailable;
}
int memoryAvailable = computer.getMemory() - memoryUsage;
if (memoryAvailable < 0) {
hardScore += memoryAvailable;
}
int networkBandwidthAvailable = computer.getNetworkBandwidth() - networkBandwidthUsage;
if (networkBandwidthAvailable < 0) {
hardScore += networkBandwidthAvailable;
}
// Soft constraints
if (used) {
softScore -= computer.getCost();
}
}
return HardSoftScore.of(hardScore, softScore);
}
}
每次的求解就会触发这个方法重新计算分数,从代码上来看,这个显然是无法达到性能要求的,但是并不意味着EasyJava的方式是无用的。
Constraint Streams
Constraint Streams是一种函数式编程形式的增量分数计算方法,可以在普通Java中轻松阅读、编写和调试。如果熟悉Java流或SQL,API应该会感觉很熟悉。
// ************************************************************************
// Hard constraints
// ************************************************************************
Constraint requiredCpuPowerTotal(ConstraintFactory constraintFactory) {
return constraintFactory.forEach(CloudProcess.class)
.groupBy(CloudProcess::getComputer, sum(CloudProcess::getRequiredCpuPower))
.filter((computer, requiredCpuPower) -> requiredCpuPower > computer.getCpuPower())
.penalize(HardSoftScore.ONE_HARD,
(computer, requiredCpuPower) -> requiredCpuPower - computer.getCpuPower())
.asConstraint("requiredCpuPowerTotal");
}
Constraint requiredMemoryTotal(ConstraintFactory constraintFactory) {
return constraintFactory.forEach(CloudProcess.class)
.groupBy(CloudProcess::getComputer, sum(CloudProcess::getRequiredMemory))
.filter((computer, requiredMemory) -> requiredMemory > computer.getMemory())
.penalize(HardSoftScore.ONE_HARD,
(computer, requiredMemory) -> requiredMemory - computer.getMemory())
.asConstraint("requiredMemoryTotal");
}
Constraint requiredNetworkBandwidthTotal(ConstraintFactory constraintFactory) {
return constraintFactory.forEach(CloudProcess.class)
.groupBy(CloudProcess::getComputer, sum(CloudProcess::getRequiredNetworkBandwidth))
.filter((computer, requiredNetworkBandwidth) -> requiredNetworkBandwidth > computer.getNetworkBandwidth())
.penalize(HardSoftScore.ONE_HARD,
(computer, requiredNetworkBandwidth) -> requiredNetworkBandwidth - computer.getNetworkBandwidth())
.asConstraint("requiredNetworkBandwidthTotal");
}
// ************************************************************************
// Soft constraints
// ************************************************************************
Constraint computerCost(ConstraintFactory constraintFactory) {
return constraintFactory.forEach(CloudComputer.class)
.ifExists(CloudProcess.class, equal(Function.identity(), CloudProcess::getComputer))
.penalize(HardSoftScore.ONE_SOFT, CloudComputer::getCost)
.asConstraint("computerCost");
}
在求解过程中任何实例发生变化,约束流会自动检测到变化,并仅重新计算受变化影响的最小必要问题部分。下图说明了这种增量分数计算的过程:
从上图看得出,3feb
、4feb
更换了班次后,计算分数只计算变更的部分。
Incremental Java
实现接口IncrementalScoreCalculator的所有方法:
public interface IncrementalScoreCalculator<Solution_, Score_ extends Score<Score_>> {
void resetWorkingSolution(Solution_ workingSolution);
void beforeEntityAdded(Object entity);
void afterEntityAdded(Object entity);
void beforeVariableChanged(Object entity, String variableName);
void afterVariableChanged(Object entity, String variableName);
void beforeEntityRemoved(Object entity);
void afterEntityRemoved(Object entity);
Score_ calculateScore();
}
完整的代码请看Java类org.optaplanner.examples.cloudbalancing.optional.score.CloudBalancingIncrementalScoreCalculator
private void insert(CloudProcess process) {
CloudComputer computer = process.getComputer();
if (computer != null) {
int cpuPower = computer.getCpuPower();
int oldCpuPowerUsage = cpuPowerUsageMap.get(computer);
int oldCpuPowerAvailable = cpuPower - oldCpuPowerUsage;
int newCpuPowerUsage = oldCpuPowerUsage + process.getRequiredCpuPower();
int newCpuPowerAvailable = cpuPower - newCpuPowerUsage;
hardScore += Math.min(newCpuPowerAvailable, 0) - Math.min(oldCpuPowerAvailable, 0);
cpuPowerUsageMap.put(computer, newCpuPowerUsage);
int memory = computer.getMemory();
int oldMemoryUsage = memoryUsageMap.get(computer);
int oldMemoryAvailable = memory - oldMemoryUsage;
int newMemoryUsage = oldMemoryUsage + process.getRequiredMemory();
int newMemoryAvailable = memory - newMemoryUsage;
hardScore += Math.min(newMemoryAvailable, 0) - Math.min(oldMemoryAvailable, 0);
memoryUsageMap.put(computer, newMemoryUsage);
int networkBandwidth = computer.getNetworkBandwidth();
int oldNetworkBandwidthUsage = networkBandwidthUsageMap.get(computer);
int oldNetworkBandwidthAvailable = networkBandwidth - oldNetworkBandwidthUsage;
int newNetworkBandwidthUsage = oldNetworkBandwidthUsage + process.getRequiredNetworkBandwidth();
int newNetworkBandwidthAvailable = networkBandwidth - newNetworkBandwidthUsage;
hardScore += Math.min(newNetworkBandwidthAvailable, 0) - Math.min(oldNetworkBandwidthAvailable, 0);
networkBandwidthUsageMap.put(computer, newNetworkBandwidthUsage);
int oldProcessCount = processCountMap.get(computer);
if (oldProcessCount == 0) {
softScore -= computer.getCost();
}
int newProcessCount = oldProcessCount + 1;
processCountMap.put(computer, newProcessCount);
}
}
这段代码是一个私有方法,其作用是将变更的实例CloudProcess进行分数计算,可见其实现非常复杂,可以预见到后期的维护是很困难的,未来若调整约束条件等,这种方法无疑是代价最高的。
三种约束实现对比
下面是这三种方法的对比:
- Easy Java:
- 优点:易于理解和实现,适合初学者。
- 缺点:性能较差,因为它需要重新计算整个解决方案的分数,而不是仅计算变化的部分。
- 使用场景:适用于简单的问题和快速原型开发。
- Constraint Streams:
- 优点:性能较好,因为它可以增量地计算分数。它使用了类似于 Java Stream API 的声明式编程风格,使代码更简洁易读。
- 缺点:学习曲线稍微陡峭,需要熟悉 OptaPlanner 的 API 和约束流的概念。
- 使用场景:适用于复杂的问题和需要高性能的场景。
- Incremental Java:
- 优点:性能最佳,因为它可以在每次移动后立即更新分数,而无需重新计算整个解决方案。
- 缺点:实现复杂,需要手动管理分数的增量更新。容易出错,需要仔细编写和测试代码。
- 使用场景:适用于对性能要求极高的场景,或者在其他方法无法满足性能需求时使用。
结尾
总之,Easy Java 适合初学者和简单问题,Constraint Streams 提供了较好的性能和易读性,适用于大多数场景,而 Incremental Java 则适用于对性能要求极高的场景。在实际应用中,可以根据问题的复杂性和性能需求选择合适的分数计算方式。
如果您想转载我的文章,请注明原作者和出处,谢谢。