はじめに

データサイエンティストの佐藤です。

エムシーデジタルでは、現実世界の課題を「最適化問題」として定式化し、解を探索することでユーザの要望に応えるプロジェクトを多く手がけています。現実の課題は複雑で、言語化が難しい要件も少なくありません。そのため、ユーザとの対話を通じて要件を洗い出し、実現可能性や優先度を考慮しながら、最終的にユーザが業務で役立てられるプロダクトを提供することを目標に開発を進めています。

最適化問題の設計には多くのトピックがありますが、本記事では「評価関数の設計」に焦点を当て、エムシーデジタルではどのように様々な要件へ対応しているかを紹介します。

最適化問題

形式的には、「入力データ」「制約」「目的関数」が与えられれば、その問題を最適化問題として扱うことができます。本記事では、入力データについての詳説は行わず¹、制約と目的関数の周辺に関する設計にスコープを絞って説明します。

具体例

例として、出発駅から到着駅までの移動時間を最小化したい場合を考えます。最もシンプルな問題設定は次のように定式化できます。

• 入力データ
  • 路線図（駅間の所要時間）
  • 出発駅・到着駅
• 制約
  • 電車以外の交通手段を使わない
• 目的関数
  • 出発駅から到着駅までの移動時間を最小化

追加仕様例

実際の路線検索サービスを想定すると、以下の様な追加要件が追加されることが予想されます。

• 移動時間と運賃の両方を考慮して最小化できるようにしたい
• 移動時間を短く抑えつつ、乗換回数をなるべく少なくしたい
• 移動時間を短く抑えつつ、特定の路線はなるべく使いたくない
• 移動時間を短く抑えつつ、混雑している電車は避けたい
• etc…

ここで登場する「なるべく」や「AだけでなくBも」といった、数理的には曖昧な要件をどのように扱うかが重要であり、それらの仕様を決定する要素の1つとして「評価関数の設計」があります。

目的関数と評価関数

「目的関数」とは、その案件において最終的に改善すべき指標を指します。 一方、「評価関数」は「目的関数」を最適化するために最適化内部で解の状態を評価するための関数です²。

評価関数は、大きく分けて次の4つの要素から構成されることが多いです。

1. 主目的項
   最も達成したいメトリクスを表現した項

2. 副目的項
   主目的ほどではないが、同時に達成されると嬉しい項

3. 制約ペナルティ項
   通常は制約として扱われるべき条件を、状況によっては違反を許容しつつペナルティを課す形にする項

4. 精度改善用の補助項
   プロダクト要件としては不要だが、最適化アルゴリズムの精度向上のために導入する項

評価関数と目的関数が同じになる場合もありますが、精度改善用の補助項は評価関数にのみ現れる項です。

以下、それぞれの項について具体的な例を示します。

主目的項

最適化問題において、最も達成したい目的を表す項です。例としては、

• 移動時間の最小化
• コスト（料金、製造費用など）の最小化
• 利益の最大化

などが挙げられます。要件次第では「移動時間も料金も小さくしたい」といった多目的最適化の要素が含まれる場合があります。対応策として、単目的最適化になるように加重平均を取ることが考えられます。

$$ \text{minimize} \quad \alpha \cdot \text{移動時間} + (1 - \alpha) \cdot \text{料金} $$

ここで $\alpha$ はユーザが設定する重みパラメータ（0から1の値）で、移動時間と料金のどちらをより重視するか調整します。 ユーザに細かい数値の調整をさせるのは負荷が高い場合などに、UI上では実行モードの選択などで表現されることもあります。

副目的項

主目的よりは優先度が低いものの、可能ならば満たしたい要件をモデル化する項です。とくに主目的項の最適解が複数存在する場合、どの解を選ぶかを調整する役割を担います。

例えば移動時間が同じ経路候補が複数ある場合、乗換回数が少ない方を選びたいとしましょう。その場合の目的関数は次のようになります。

$$ \text{minimize} \quad \text{移動時間} + \beta \cdot \text{乗換回数} $$

ここで $\beta$ は乗換一回あたりに課すペナルティ（例：3分相当）を表します。このペナルティを調整することで、「少し遠回りでも乗換が少ない経路」と「乗換が多いが直線的な経路」のどちらを優先するかをバランスできます。

制約ペナルティ項

通常、「絶対に守るべき条件」は制約で表現しますが、状況によっては違反を完全に排除しない方が便利なケースがあります。これは制約違反に対してペナルティを課すことでモデル化します。

Hardペナルティ制約

本来は絶対に守られるべきだが、例外的に守れない場合でも“できる限り”違反を小さくするために導入するものです。たとえば、「最終電車の出発時刻までに目的地に到着する」という制約を、以下のようにペナルティ化できます。

$$ \text{minimize} \quad \text{移動時間} + M \cdot \max\bigl(0, \text{到着時刻} - \text{最終電車出発時刻}\bigr) $$

ここで $M$ は非常に大きな値（例：1000分相当）に設定します。こうすることで、どうしても間に合わない場合は「なるべく早く到着」する解を得やすくなります。

Hardペナルティ制約を違反する解は利用可能でない場合が多いですが、異常系においても解が出力されるということには原因究明の意味も含めて価値があることがしばしばあります。

Softペナルティ制約

「守ることが望ましいが、主目的や副目的を大きく改善できるなら多少は違反してもいい」という柔軟性を表す制約です。 制約として存在はしているものの、実際の運用では多少の違反を許容して柔軟に対応されているといった類の制約を扱う際に導入されます。 たとえば「特定の路線はなるべく使いたくない」という要件は、次のように書けます。

$$ \text{minimize} \quad \text{移動時間} + \gamma \cdot \text{特定路線の利用時間} $$

ここで $\gamma$ は特定路線利用に対するペナルティの重み（例：1.5倍）を表します。これにより、わずかに遠回りであっても特定路線を使わない経路が選ばれやすくなります。

精度改善用の補助項

アルゴリズム開発の際、探索を効率化するために導入される項です。プロダクト要件自体には関係しないため、ユーザへの説明が難しい場合もあります。

典型例としては、$A^*$アルゴリズムの評価関数におけるヒューリスティック関数があります。 先の電車による移動時間最小化の例に挙げると、出発駅から今いる駅までの距離を基準とした幅優先探索アルゴリズムでは状態数が非常に大きくなる可能性がありますが、 $A^*$ アルゴリズムでは出発駅から今いる駅までの距離に加え、今いる駅から到着駅までの推定距離という補助項（ヒューリスティック関数と呼ばれる）を導入することで探索効率が大幅に改善されます。

$A^*$ アルゴリズム自体は最適化案件で頻繁に採用される手法ではありませんが、ビームサーチなどの構築系の手法において同様の補助項が効果的である場合がしばしば存在します。

最適化手法毎の評価関数項の評価

代表的な最適化問題へのアプローチ3つを取り上げ、それぞれが評価関数をどのように扱うかを整理します。 評価関数の設計のしやすさは最適化問題の設定と最適化手法の組み合わせによって大きく変わるので、特性を事前に把握しておくと最適化方針選定の一助になります。

1. MIP/LP手法

Mixed Integer Programming（MIP）やLinear Programming（LP）の枠組みによるアプローチです。 GurobiやHiGHSなどの汎用ソルバを用いて解を得ます。

• 主目的項・副目的項
  線形計画問題や整数計画問題として定式化しやすい場合は、そのまま組み込みやすいです。ただし、非線形要件を線形に近似するなどの工夫が必要になるケースもあります。
• 制約ペナルティ項
  MIP/LP手法では、もともと制約として表現できるものをペナルティ項に移行することは容易です。異常系への対処や実行時間内の解生成といった観点から、制約ペナルティ項がよく導入されます。ただし、大きなペナルティを入れすぎると計算が不安定になることもあるため、調整が必要です。
• 精度改善用の補助項
  汎用ソルバを用いる場合はあまり必要ありません。汎用ソルバが高度な探索手法を内蔵しているため、補助的な項を明示的に入れなくても高精度の解を得られることが多いです。

2. 構築手法

動的計画法やビームサーチなど、解を段階的に構築するタイプのアプローチです。

• 主目的項・副目的項
  実装しやすいことが多いです。
• 制約ペナルティ項
  手法の効率とのトレードオフを考慮する必要があります。探索空間の大きさや実装の煩雑さに大きく影響するため、開発途中の仕様変更には注意が必要です。
• 精度改善用の補助項
  アルゴリズムの探索効率を大きく左右することが多く、導入されることが多いです。開発者の技量依存の側面があるため、案件としては扱いが難しい項目になります。

3. 局所探索系手法

山登り法、焼きなまし法など、解を少しずつ変形しながら探索するアプローチです。

• 主目的項・副目的項
  実装しやすいことが多いです。
• 制約ペナルティ項
  構築手法同様、効率とのトレードオフがあります。探索空間の大きさや実装の煩雑さに大きく影響するため、開発途中の仕様変更には注意が必要です。
• 精度改善用の補助項
  構築手法と比較すると効果が出るケースは稀であり、導入されないケースが多いです。

アプローチ比較のまとめ

評価関数の設計のしやすさだけを基準にすると、一般的には

MIP/LP 手法 ＞ 局所探索系手法 ＞ 構築手法

の順で扱いやすい傾向があります。ただし、実際には評価関数の設計以外にも比較検討すべき事項は存在するため、問題規模や特性、制約条件などを総合的に勘案して手法を選びます。

ケーススタディ：追加仕様対応例

冒頭で述べた「移動時間を最小化する」問題に以下の追加仕様があった場合を想定してみましょう。

1. 移動時間だけでなく料金も減らしたい
   → 主目的項に「移動時間」と「料金」を組み込み、
   $\alpha \cdot \text{移動時間} + (1-\alpha)\cdot \text{料金}$ のような形で加重平均にする

2. 乗換回数をなるべく少なくしたい
   → 副目的項として「乗換回数」にペナルティをかける
   $\text{移動時間} + \beta \cdot \text{乗換回数}$

3. 特定の路線をなるべく使わない
   → softペナルティ制約として「特定路線利用時間」を追加
   $\text{移動時間} + \gamma \cdot \text{特定路線の利用時間}$

4. 最終電車の出発時刻を過ぎた場合でも解がほしい
   → hardペナルティ制約にして
   $\text{移動時間} + M \cdot \max(0, \text{到着時刻} - \text{最終電車出発時刻})$

このように、要件を評価関数の各項としてうまく組み込むことで、「なるべく」や「複数の考慮要素を同時に満たす」といった曖昧な要求を数値モデルへ落とし込むことが可能になります。 各種ハイパーパラメータ$\alpha, \beta, \gamma$については、ドメイン知識やユーザからのフィードバックを通じて適切な値を設定することになります。

おわりに

本記事では、最適化問題における評価関数設計について、具体例や手法との対応関係を交えて紹介しました。最適化のプロジェクトでは、評価関数の設計が成否を左右する重要な要素であることを、過去の事例からも強く実感しています。

最適化ソリューションの導入は、既存のオペレーションを変えることを意味します。何かしらの差異が生じたとき、その差異が現場で歓迎されるか否かを常に意識しながら制約や評価関数を調整していくプロセスが欠かせません。

今回の内容を踏まえ、重要なポイントをまとめると以下のとおりです。

1. 曖昧な要件を数理的に翻訳する能力が重要

   • ユーザからの機能要望を主目的項・副目的項・制約ペナルティ項などの数理的な表現に落とし込み、適切な重み付けを設定することが大切。
   • ひいては、適切な評価関数の設計にはユーザから細目にフィードバックを貰うことが重要になる。

2. 最適化手法と評価関数設計は密接に関連している

   • MIP/LP、構築手法、局所探索手法などの選定と評価関数設計は同時に検討することが望ましい。
   • 明確な答えはないものの、要件や工数によって適した最適化手法は存在するため、開発者はアプローチ毎のメリットデメリットを把握し、必要に応じてどのアプローチでも精度を出せるようになっておけるとよい。

最適化問題における評価関数設計は、アルゴリズムと現実の曖昧さをつなぎ合わせる「橋渡し」のような存在です。今後も様々なプロジェクトを通じて、この橋渡しをより洗練させていきたいと考えています。

エムシーデジタルでは、技術力向上のためのイベントや勉強会などを定期的に開催しています。もしエムシーデジタルでの仕事に興味を持っていただけましたら、カジュアル面談も随時受け付けておりますので、ぜひお気軽にお問い合わせください。

採用情報や面談申込みはこちらから