第11章 Red Hat ビルドの OptaPlanner と Java Solver: クラウドバランシングのクイックスタートガイド

本書では、OptaPlanner の制約解決人工知能 (AI) を使用して Java ソルバーを作成するプロセスを説明します。

11.1. Java Solver のスタートガイド: クラウドバランシングの例

サンプルを使用して、Java コードを使用した基本的な Red Hat ビルドの OptaPlanner の開発を紹介します。

クラウドコンピューターを複数台所有し、そのクラウドコンピューターで複数のプロセスを実行する必要があると仮定します。コンピューターに各プロセスを割り当てる必要があります。

以下のハード制約を満たす必要があります。

  • すべてのコンピューターで、プロセスの合計容量を処理するのに必要なハードウェア最小要件を満たす必要があります。

    • CPU 容量: コンピューターには、最低でも、そのコンピューターに割り当てられたプロセスで必要とされる合計の CPU 処理能力が必要です。
    • メモリー容量: コンピューターには、最低でも、そのコンピューターに割り当てられたプロセスで必要とされる合計のメモリーが必要です。
    • ネットワーク容量: コンピューターには、最低でも、そのコンピューターに割り当てられたプロセスで必要とされる合計のネットワーク帯域幅が必要です。

以下のソフト制約を最適化する必要があります。

  • 1 つまたは複数のプロセスが割り当てられたコンピューターにはそれぞれ、保守コストが発生します (コンピューターごとに固定)。

    • コスト: 合計保守コストを最小限に抑えます。

これは、ビンパッキング 問題にあたります。以下に、簡単なアルゴリズムを使用して、制約が 2 つ (CPU およびメモリー) あるコンピューター 2 台に、4 つのプロセスを割り当てるという簡単な例を紹介します。

cloudBalanceUseCase

ここで使用しているアルゴリズムは FFD (First Fit Decreasing) アルゴリズムです。このアルゴリズムでは、最初に大きいプロセスを割り当ててから、残りのスペースに小さいプロセスを割り当てていきます。図からも分かるように、これは黄色いプロセス D を割り当てる容量が残っていないため、最適ではありません。

OptaPlanner は、別の、より良いアルゴリズムを使用して、より適した解 (ソリューション) を見つけます。また、データ (プロセスやコンピューター) と制約 (ハードウェア要件などの制約) の両方を増やして評価します。

以下のまとめは、この例や、「マシンの再割当て (Google ROADEF 2012)」 で説明されている、より多くの制約を使用した高度な実装に該当します。

cloudOptimizationValueProposition

表11.1 クラウドのバランス問題の規模

問題の規模コンピュータープロセス探索空間

コンピューター 2 台、プロセス 6 件

2

6

64

コンピューター 3 台、プロセス 9 件

3

9

10^4

コンピューター 4 台、プロセス 012 件

4

12

10^7

コンピューター 100 台、プロセス 300 件

100

300

10^600

コンピューター 200 台、プロセス 600 件

200

600

10^1380

コンピューター 400 台、プロセス 1200 件

400

1200

10^3122

コンピューター 800 台、プロセス 2400 件

800

2400

10^6967

11.1.1. ドメインモデルの設計

ドメインモデル を使用すると、どのクラスがプランニングエンティティーで、どのプロパティーがプランニング変数かが分かります。また、制約の簡素化、パフォーマンスの向上、これからのニーズに対する柔軟性の向上もサポートします。

11.1.1.1. ドメインモデルの設計

ドメインモデルを作成するには、問題の入力データを表現するオブジェクトをすべて定義します。この例では、オブジェクトはプロセスとコンピューターです。

ドメインモデルの個別のオブジェクトは、ソリューションおよび入力データを含む、問題の完全なデータセットを表現する必要があります。以下の例では、このオブジェクトにコンピューターの一覧とプロセスの一覧を格納します。プロセスごとにコンピューターが 1 台割り当てられ、コンピューター間のプロセスの配分が解となります。

手順

  1. ドメインモデルのクラス図を作成します。
  2. 正規化して複製データを削除します。
  3. クラスごとに サンプルインスタンス を記述します。サンプルインスタンスは、プランニングの目的に関連するエンティティープロパティーです。

    • Computer: 特定のハードウェアが搭載され、特定の保守コストが発生するコンピューターを表します。

      この例では、cpuPowermemorynetworkBandwidth、および costComputer クラスのサンプルインスタンスです。

    • Process: デマンドのあるプロセスを表します。このプロセスは、Planner によって Computer に割り当てられます。

      Process のサンプルインスタンスは requiredCpuPowerrequiredMemory、および requiredNetworkBandwidth です。

    • CloudBalance: コンピューター間のプロセスの配分を表します。CloudBalance には、特定のデータセットの Computer および Process がすべて含まれます。

      オブジェクトがすべてのデータセットおよび解を表す場合は、score を格納するサンプルインスタンスが必要です。OptaPlanner は異なる解のスコアを計算して、比較します。最高スコアの解が最適解となります。このため、CloudBalance のサンプルインスタンスは score になります。

  4. プランニング中にどの関係 (またはフィールド) が変化するか判断します。

    • Planning entity (プランニングエンティティー): 解決中に OptaPlanner が変更可能なクラス。この例では、別のコンピューターにプロセスを移動できるため Process クラスです。

      • OptaPlanner が変更できない入力データを表現するクラスは、問題ファクト として知られています。
    • Planning variable (プランニング変数): 解決時に変化するプランニングエンティティークラスのプロパティー。この例では、Process クラスの computer プロパティーがそれにあたります。
    • Planning solution (プランニングの解): 問題への解を表現するクラス。このクラスは、プランニングエンティティーをすべて含むデータセットを表す必要があります。この例では、CloudBalance クラスがそれにあたります。

以下の UML クラスの図では、OptaPlanner のコンセプトにすでにアノテーションが付けてあります。

cloudBalanceClassDiagram

examples/sources/src/main/java/org/optaplanner/examples/cloudbalancing/domain ディレクトリーに、この例のクラス定義が含まれています。

11.1.1.2. Computer クラス

Computer クラスは、データを保存する Java オブジェクトで、POJO (Plain Old Java Object) として知られています。通常、入力データを持つこの種のクラスが多くなります。

例11.1 CloudComputer.java

public class CloudComputer ... {

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

    ... // getters
}

11.1.1.3. Process クラス

Process クラスは、解決中に変更されるクラスです。

OptaPlanner に、computer プロパティーを変更できることを指示する必要があります。これには、クラスに @PlanningEntity のアノテーションを付けて、getComputer() ゲッターに @PlanningVariable のアノテーションを付けます。

当然ながら、OptaPlanner が解決中にプロパティーを変更できるように、この computer プロパティーにはセッターも必要です。

例11.2 CloudProcess.java

@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;
    }

    // ************************************************************************
    // Complex methods
    // ************************************************************************

    ...

}

OptaPlanner は、computer プロパティーに割り当てるのに、どの値を選択できるのかを把握しておく必要があります。これらの値は、プランニングの解の CloudBalance.getComputerList() メソッドから取得し、現在のデータセットに含まれる全コンピューターのリストを返します。

CloudProcess.getComputer() 上にある @PlanningVariablevalueRangeProviderRefs パラメーターは、CloudBalance.getComputerList() 上にある @ValueRangeProviderid に一致する必要があります。

注記

ゲッターの代わりにフィールドにアノテーションも使用できます。

11.1.1.4. CloudBalance クラス

CloudBalance クラスには @PlanningSolution アノテーションが付いています。

このクラスは、すべてのコンピューターおよびプロセスの一覧を保持します。プランニングの問題と、 (初期化されている場合は) プランニングの解の両方を表します。

CloudBalance クラスには、以下の主要な属性が含まれます。

  • このクラスは、OptaPlanner が変更可能なプロセスコレクションを保持します。ゲッター getProcessList()@PlanningEntityCollectionProperty アノテーションを付けて、OptaPlanner が変更できるプロセスを OptaPlanner で取得できるようにします。解を保存するには、OptaPlanner は、変更したプロセス一覧で、クラスの新規インスタンスを初期化します。

    1. これには @PlanningScore のアノテーションがついた score プロパティーも含まれており、このプロパティーは、現在の状態の解の Score を指します。OptaPlanner は、解のインスタンス向けに Score を計算すると自動的にこのプロパティーを更新するため、このプロパティーにはセッターが必要です。
    2. 特に、Drools でスコアの計算をする場合、computerList のプロパティーは @ProblemFactCollectionProperty のアノテーションを付けて、OptaPlanner がコンピューターのリスト (問題ファクト) を取得し、デシジョンエンジンに公開できるようにする必要があります。

例11.3 CloudBalance.java

@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;
    }

    ...
}

11.1.2. クラウドバランシングの Hello World アプリケーションの実行

hello world アプリケーションサンプルを実行して、Solver を例示します。

手順

  1. お好きな IDE にこの例をダウンロードして設定します。IDE へのサンプルのダウンロードおよび設定方法は、「IDE (IntelliJ、Eclipse、または Netbeans) での Red Hat ビルドの OptaPlanner サンプルの実行」 を参照してください。
  2. 以下の主要クラス org.optaplanner.examples.cloudbalancing.app.CloudBalancingHelloWorld で実行設定を作成します。

    デフォルトでは、クラウドバランシングの Hello World は 120 秒間実行するように設定されています。

結果

このアプリケーションは、以下のコードを実行します。

例11.4 CloudBalancingHelloWorld.java

public class CloudBalancingHelloWorld {

    public static void main(String[] args) {
        // Build the Solver
        SolverFactory<CloudBalance> solverFactory = SolverFactory.createFromXmlResource("org/optaplanner/examples/cloudbalancing/solver/cloudBalancingSolverConfig.xml");
        Solver<CloudBalance> solver = solverFactory.buildSolver();

        // Load a problem with 400 computers and 1200 processes
        CloudBalance unsolvedCloudBalance = new CloudBalancingGenerator().createCloudBalance(400, 1200);

        // Solve the problem
        CloudBalance solvedCloudBalance = solver.solve(unsolvedCloudBalance);

        // Display the result
        System.out.println("\nSolved cloudBalance with 400 computers and 1200 processes:\n" + toDisplayString(solvedCloudBalance));
    }

    ...
}

このコードサンプルにより、以下が行われます。

  1. Solver の設定をもとに Solver を構築します (ここでは、クラスパスの XML ファイル cloudBalancingSolverConfig.xml を使用します)。

    Solver の構築がこの手順で最も複雑な部分です。詳細は、「Solver の設定」 を参照してください。

            SolverFactory<CloudBalance> solverFactory = SolverFactory.createFromXmlResource(
                    "org/optaplanner/examples/cloudbalancing/solver/cloudBalancingSolverConfig.xml");
            Solver solver<CloudBalance> = solverFactory.buildSolver();
  2. 問題を読み込みます。

    CloudBalancingGenerator が無作為に問題を生成します。これは、たとえば、データベースなどから、実際の問題を読み込むクラスに置き換えてください。

            CloudBalance unsolvedCloudBalance = new CloudBalancingGenerator().createCloudBalance(400, 1200);
  3. 問題を解決します。

            CloudBalance solvedCloudBalance = solver.solve(unsolvedCloudBalance);
  4. 結果を表示します。

            System.out.println("\nSolved cloudBalance with 400 computers and 1200 processes:\n"
                    + toDisplayString(solvedCloudBalance));

11.1.3. Solver の設定

Solver の設定ファイルは、解決のプロセスがどのように機能するかを指定します。このファイルはコードの一部とみなされます。このファイルの名前は、examples/sources/src/main/resources/org/optaplanner/examples/cloudbalancing/solver/cloudBalancingSolverConfig.xml になります。

例11.5 cloudBalancingSolverConfig.xml

<?xml version="1.0" encoding="UTF-8"?>
<solver>
  <!-- Domain model configuration -->
  <scanAnnotatedClasses/>

  <!-- Score configuration -->
  <scoreDirectorFactory>
    <easyScoreCalculatorClass>org.optaplanner.examples.cloudbalancing.optional.score.CloudBalancingEasyScoreCalculator</easyScoreCalculatorClass>
    <!--<scoreDrl>org/optaplanner/examples/cloudbalancing/solver/cloudBalancingScoreRules.drl</scoreDrl>-->
  </scoreDirectorFactory>

  <!-- Optimization algorithms configuration -->
  <termination>
    <secondsSpentLimit>30</secondsSpentLimit>
  </termination>
</solver>

Solver の設定は、3 つの部分で設定されます。

  1. ドメインモデル設定: OptaPlanner が変更可能なものは何ですか ?

    OptaPlanner にドメインクラスを指定する必要があります。ここでは、 (@PlanningEntity または @PlanningSolution アノテーションに対して) クラスパス内の全クラスを自動的にスキャンします。

      <scanAnnotatedClasses/>
  2. スコアの設定: OptaPlanner はどのようにプランニング変数を最適化しますか ?目的は何ですか ?

    ここでは、ハード制約とソフト制約を使用するため、HardSoftScore を使用します。ただし、OptaPlanner に、ビジネス要件に合ったスコアの計算方法を指定する必要があります。後ほど、スコアの計算方法を 2 種類 (基本的な Java 実装の使用、または Drools DRL の使用) 紹介します。

      <scoreDirectorFactory>
        <easyScoreCalculatorClass>org.optaplanner.examples.cloudbalancing.optional.score.CloudBalancingEasyScoreCalculator</easyScoreCalculatorClass>
        <!--<scoreDrl>org/optaplanner/examples/cloudbalancing/solver/cloudBalancingScoreRules.drl</scoreDrl>-->
      </scoreDirectorFactory>
  3. 最適化アルゴリズムの設定: OptaPlanner をどのように最適化しますか ?この例では、 (最適化アルゴリズムが明示的に設定されていないため) 30 秒間、デフォルトの最適化アルゴリズムを使用します。

      <termination>
        <secondsSpentLimit>30</secondsSpentLimit>
      </termination>

    OptaPlanner は、数秒でも (リアルタイム計画機能を使用する場合は 15 ミリ秒未満になる場合も) 良い結果は得られるはずですが、時間が長くなればなるほど、結果は良くなります。高度なユースケースでは、ハードな時間制限以外に、終了の条件を使用することが適しています。

    デフォルトのアルゴリズムでも、人間の計画担当者やほとんどの社内実装を簡単に上回っています。高度なベンチマーク機能を使用して微調整を強化し、さらに良い結果を得ることができます。

11.1.4. スコアの設定

OptaPlanner は、スコア が最も高い ソリューション を探します。この例では、HardSoftScore を使用し、OptaPlanner がハード制約に違反していない (またはハードウェア要件を満たす) ソリューションと、ソフト制約に違反する数が最も少ない (メンテナーンスコストが最も低い) ソリューションを探します。

scoreComparisonCloudBalancing

プレーンな Java、Drools、または OptaPlanner ConstraintStream API を使用して制約を定義できます。ConstraintStream API の詳細は、「制約の定義およびスコアの計算」 を参照してください。

11.1.4.1. Java を使用したスコア計算の設定

スコア関数を定義する方法の 1 つに、Plain Java での EasyScoreCalculator インターフェイス実装があります。

手順

  1. cloudBalancingSolverConfig.xml ファイルで設定を追加するか、アンコメントします。

      <scoreDirectorFactory>
        <easyScoreCalculatorClass>org.optaplanner.examples.cloudbalancing.optional.score.CloudBalancingEasyScoreCalculator</easyScoreCalculatorClass>
      </scoreDirectorFactory>
  2. calculateScore (Solution) メソッドを実装して HardSoftScore インスタンスを返します。

    例11.6 CloudBalancingEasyScoreCalculator.java

    public class CloudBalancingEasyScoreCalculator implements EasyScoreCalculator<CloudBalance> {
    
        /**
         * A very simple implementation. The double loop can easily be removed by using Maps as shown in
         * {@link CloudBalancingMapBasedEasyScoreCalculator#calculateScore(CloudBalance)}.
         */
        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.valueOf(hardScore, softScore);
        }
    
    }

上記のコードを最適化し、Map を使用して processList を 1 回だけ反復した場合でも、インクリメンタルスコアの計算が行われないため、処理が遅いままです

これを修正するには、インクリメント Java スコア計算か、Drools スコア計算を使用します。インクリメント Java スコア計算については、本書では触れません。

11.1.4.2. Drools を使用したスコア計算の設定

Drools ルール言語 (DRL) を使用して制約を定義できます。Drools スコア計算はインクリメント計算を使用します。この計算では、1 つまたは複数のスコアルールとしてすべてのスコア制約が記述されます。

スコア計算のデシジョンエンジンを使用すると、デシジョンテーブル (XLS または Web ベース)、Business Central をはじめとしたサポート対象の機能など、Drools の他の技術と統合できます。

手順

  1. クラスパスに scoreDrl リソースを追加してスコア機能としてデシジョンエンジンを使用します。cloudBalancingSolverConfig.xml ファイルで設定を追加するか、アンコメントします。

      <scoreDirectorFactory>
        <scoreDrl>org/optaplanner/examples/cloudbalancing/solver/cloudBalancingScoreRules.drl</scoreDrl>
      </scoreDirectorFactory>
  2. ハード制約を作成します。これらの制約で、すべてのコンピューターに、十分な CPU、メモリー、ネットワーク帯域幅が割り当てられ、全プロセスがサポートされるようになります。

    例11.7 cloudBalancingScoreRules.drl - ハード制約

    ...
    
    import org.optaplanner.examples.cloudbalancing.domain.CloudBalance;
    import org.optaplanner.examples.cloudbalancing.domain.CloudComputer;
    import org.optaplanner.examples.cloudbalancing.domain.CloudProcess;
    
    global HardSoftScoreHolder scoreHolder;
    
    // ############################################################################
    // Hard constraints
    // ############################################################################
    
    rule "requiredCpuPowerTotal"
        when
            $computer : CloudComputer($cpuPower : cpuPower)
            accumulate(
                CloudProcess(
                    computer == $computer,
                    $requiredCpuPower : requiredCpuPower);
                $requiredCpuPowerTotal : sum($requiredCpuPower);
                $requiredCpuPowerTotal > $cpuPower
            )
        then
            scoreHolder.addHardConstraintMatch(kcontext, $cpuPower - $requiredCpuPowerTotal);
    end
    
    rule "requiredMemoryTotal"
        ...
    end
    
    rule "requiredNetworkBandwidthTotal"
        ...
    end
  3. ソフト制約を作成します。この制約は、保守コストを最小限に抑えます。ハード制約に該当する場合にのみ適用されます。

    例11.8 cloudBalancingScoreRules.drl - ソフト制約

    // ############################################################################
    // Soft constraints
    // ############################################################################
    
    rule "computerCost"
        when
            $computer : CloudComputer($cost : cost)
            exists CloudProcess(computer == $computer)
        then
            scoreHolder.addSoftConstraintMatch(kcontext, - $cost);
    end

11.1.5. Solver の他の開発

上記の例が機能するようになったので、さらに開発を進めてみてください。たとえば、ドメインモデルを改良して、以下のような制約を追加してみてください。

  • すべての プロセスサービス に属する。コンピューターはクラッシュする可能性があるため、同じサービスを実行するプロセスは、別のコンピューターに割り当てる必要がある (または割り当てなければならない)。
  • すべての コンピュータービル に設置されている。ビルが火災にあう可能性があるため、同じサービスのプロセスは、別のビルに設置されているコンピューターに割り当てる必要がある (割り当てなければならない)。