はじめに

はじめまして、エムシーデジタルでデータサイエンティストを務めている伏下と申します。

エムシーデジタルでは、現実世界の課題を「最適化問題」として定式化し、その問題を解くプログラムを開発するようなプロジェクトに取り組んできました。このブログでは、最適化問題の解が意図通りのものになっているか、満たすべき制約に違反していないかなどを担保するために、エムシーデジタルで行っている取り組みについてご紹介します。

背景

最適化問題とは、多くの制約や選択肢がある中で、制約を満たしつつ、できるだけ良い選択肢を選ぶような問題のことです。例えば過去に行ったトラックのルート最適化のプロジェクトでは、「ドライバーの労働時間」や「トラックの積載容量」という制約がある中で、考えられる多くのルートの中からできるだけ走行距離が短くなるものを選ぶような問題に取り組みました。

エムシーデジタルではこのような最適化問題を解くために、擬似焼きなまし法などを用いたメタヒューリスティクスアルゴリズムや、線形計画問題や混合整数計画問題を解く汎用ソルバーを用いたアルゴリズムを開発することが多いです。

しかし、これらのアルゴリズムを実装したプログラムは、正しく動いていることを担保するのが難しくなりやすいと感じています。

その理由の一つに、単体テストの書きにくさが挙げられます。テストしやすいプログラムの特徴として、一つの関数やクラスが多くのことを行わず、適切な粒度に分けられていることがあると思います。しかし、複雑な探索ロジックを含むメタヒューリスティクスアルゴリズムや、全ての制約や変数を汎用ソルバーに一度に渡すアルゴリズムは、テストしやすい粒度に処理を分割することが難しい傾向にあります。

そこで私たちは、アルゴリズムが出した解の正しさを担保する道具として「チェッカー」と「コアロジックテスト」を実装することが多いです。今回はこの二つを紹介し、それぞれのメリットデメリットを比較します。

チェッカー

チェッカーとは、その名の通りアルゴリズムが出した解が制約に違反していないかをチェックするプログラムです。最適化問題の入力とアルゴリズムが出した解を受け取り、違反した制約のリストを返すようなクラス（または関数）になります。

単純な擬似コードで表すと以下のようなイメージになります。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Checker:
    """アルゴリズムが出力した解を検証するクラス

    Attributes:
        problem (Problem): 最適化問題の諸々の情報
        solution (Solution): アルゴリズムが出力した解
    """

    def __init__(self, problem: Problem, solution: Solution) -> None:
        self.problem = problem
        self.solution = solution

    def check(self) -> list[Violation]:
        """解の検証を行う

        Returns:
            list[Violation]: 検出された違反のリスト
        """

        violations = []
        violations.extend(self._check_driver_working_time())
        ...  # 他にも色々チェックする
        return violations

    def _check_driver_working_time(self) -> list[Violation]:
        """労働時間に関する制約違反がないか検証する"""
        ...

チェッカーは、お客様からいただいた実データへのアルゴリズムの出力解に対して実行されることが多いです。具体的に活躍するタイミングとしては、主に以下の三つが挙げられます。

1. 最適化コードを修正したタイミングで、バグが混入して制約違反が生じるようになっていないかを開発用の実データを使って確かめる
2. 実際にアルゴリズムを業務に組み込むフェーズで、現場でアルゴリズムによって出力された解に違反がないかを確かめる
3. ユーザーが、アルゴリズムが出力した解を直接使わずに手修正を加えたときに、手修正後の解が制約を満たしているかを確かめる

一つ目の使い方は、従来のソフトウェア開発におけるテストと近い使い方だと思います。 二つ目・三つ目の使い方は、実際にアルゴリズムを業務で活用するときに、万が一制約に違反する解が出力されても実業務に用いられないようにするという点で重要です。

チェッカーを導入することで、日々のアルゴリズム開発や運用フェーズでの不安を大幅に軽減できます。そのため、個人的には最適化プロジェクトにおいては必須の開発物だと考えています。

また、チェッカーを作成するためには存在する制約を整理し一覧化する必要があります。そのため、その過程で問題への理解が曖昧なところを洗い出せたり、解くべき最適化問題の仕様がチェッカーのコードによって半ドキュメント化されたりする副次的な効果も期待できます。

コアロジックテスト

先ほどチェッカーについてご紹介しましたが、以下のようなケースはチェッカーだけではチェックしきれないです。

• 厳密に守る必要はないソフトな制約や要望
  • チェッカーは違反してはいけない制約のみをチェックするため、「違反してもいいけどできたらこうなっていて欲しい」といったゆるい制約・要望を確かめることはできない
  • 例えば「全く同じルートを通るトラックが複数ある場合、一部のトラックに荷物を偏らせるのではなくできるだけ均等に荷物を分けて欲しい」のような要望は、完全に均等に分かれていなくてもよいのでチェッカーでは扱いにくい
• 実データに滅多に現れないようなレアな制約
  • チェッカーは実データに対して走らせるため、限られた状況のときのみ注意すべき制約に違反するようなバグは検出が遅れやすい
  • 例えば「祝日は労働時間の制限をいつもより短い 7 時間とする」のような制約はチェッカーで扱うことはできるが、普段用いている開発用のデータが祝日のものでないと事前に違反を検出できない

このようなケースに対するコードのバグを検知するために、エムシーデジタルではチェッカーの他に「コアロジックテスト¹」というものを実装することがあります。

コアロジックテストでは上記で例示したような、チェッカーでは検知しにくい具体的な制約に絞ってテストを行います。 具体的な実装としては、そのコアロジックテストでチェックしたい制約を確かめられるようなシンプルな問題設定を手作業で作成し、その問題に対してアルゴリズムを実行して解を出力させます。そして得られた解がその制約を満たしているかをチェックします。

たとえば、「全く同じルートを通るトラックが複数ある場合、一部のトラックに荷物を偏らせるのではなくできるだけ均等に荷物を分けて欲しい」という制約に対するコアロジックテストの擬似コードは、以下のようになります（実際のプロジェクトでは、もう少し抽象化して量産しやすい形で実装することが多いです）。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class CheckTwoTrucksCarrySameAmount:
    def gen_problem(self) -> Problem:
        """
        「全く同じルートを通るトラックが複数ある場合、できるだけ均等に荷物を分けて欲しい」という制約をチェックしやすいシンプルな入力をハードコードする。
        たとえば、以下のような入力になる。

        - トラックは二台のみ存在する
        - 地点 A から地点 B への荷物のみが存在する
        - 荷物の量は、一台では運びきれず二台では運びきれる程度の量
        - 各荷物は偶数個ずつあり、二つのトラックで均等に分けられる
        """
        return Problem(
            trucks=[...],
            positions=[...],
            ...
        )

    def check(self) -> CheckResult:
        problem = self.gen_problem()
        solution: Solution = self.solver.solve(problem)
        # 荷物がちょうど均等に分かれているかのみをチェック
        ...
        # チェック結果を返す
        return CheckResult(...)

コアロジックテストのテスト対象のモジュールはアルゴリズム全体という広い範囲ですが、「入力を手作成し期待通りになっているか確認する」という枠組み自体は従来の単体テストと同じようなものです。そのため、コードに修正を加えた際は自動的に全てのコアロジックテストを回すようにしています。

コアロジックテストを作る際にはいくつかの注意点があります。以下にそれらを紹介します。

• 問題設定はできるだけシンプルにする
  • 最適化アルゴリズムは常に最適解を出力することが保証されているわけではないので、あまり複雑にしすぎると最適解が出ずに意図通りのチェックができない可能性がある
  • 人間が見て最適解がパッと思い浮かぶような問題設定にしないと、管理コストが高くなってしまう
• 今回チェックしたい制約以外はチェックしないようにする
  • 擬似コードの check 関数に「荷物がちょうど均等に分かれているかのみをチェック」とあるが、ここで expected_solution: Solution のような変数を定義して完全一致しているかチェックすることも可能ではある。しかしこのようなつくりにすると、他の関係ない制約が変わったときに expected_solution も変化する可能性があり、管理コストが高くなってしまう

チェッカーに加えてコアロジックテストを導入することで、日々の開発における信頼性がさらに向上します。

さらに、コアロジックテストを用意することには、顧客からアルゴリズムの解に関する質問が来たときに調査がしやすくなるという副次的な効果があります。 最適化プロジェクトでは、顧客から「アルゴリズムの出力に納得がいかないが、なぜこうなっているのか？」という問い合わせをいただくことがよくあります²。アルゴリズムの開発者が見て一目で原因がわかることもありますが、開発者目線で見てもなぜ期待される出力が出ていないのかわからないことも多々あります。

そんなときに、コアロジックテストの枠組みが役に立ちます。コアロジックテストが用意されているということは、「問題設定を手作成し、それに対するアルゴリズムの解を確認する」という作業が簡単に行える環境であるということです。したがって、顧客からの問い合わせを受けて「簡略化されたこの問題では同じ現象が再現するか？」などの別データでの検証に、コアロジックテストの枠組みを使いまわせることがあります。

まとめ

本記事では、エムシーデジタルが最適化アルゴリズムの出力を担保するために用いている二つの手法、チェッカーとコアロジックテストについてご紹介しました。それぞれの特徴を以下の表にまとめます。

弊社では、すべての最適化プロジェクトにおいてチェッカーの作成を推奨しています。一方で、コアロジックテストは問題の複雑度や要件に応じて、必要に応じて作成する方針を取っています。

エムシーデジタルでは、技術力向上のためのイベントや勉強会なども定期的に実施しています。 もしエムシーデジタルで働くことに興味を持っていただいた方がいらっしゃいましたら、カジュアル面談も受け付けておりますので、お気軽にお声掛けください！ 採用情報や面談申込みはこちらから

脚注