はじめに
こんにちは、株式会社NeurestXの田中です。私は普段からAtCoderに取り組んでおり、アルゴリズム部門では緑コーダーです。
業務の中では、限られた条件の中で「できるだけ良い組み合わせ」を選ぶ場面が多くあります。例えば、作業スケジュール、配送ルート、タスク割当などです。
これらの問題は、複数の候補の中からより良い組み合わせを探索する組合せ最適化問題として捉えることができます。組合せ最適化問題では、考えられる候補が非常に多くなり、探索空間が膨大になることがあります。そのため、厳密な最適解を短時間で求められるとは限りません。そこで重要になるのが、評価関数に基づいて短い時間でできるだけ良い近似解を探索するヒューリスティック最適化です。
本記事では、AtCoderのスケジューリング問題を題材に、複数のヒューリスティック解法を実装し、それぞれの特徴を比較します。
題材にする問題
今回題材にしたのは、AtCoderのA - AtCoder Contest Schedulingという問題です。
問題内容を簡単に要約すると以下のようになります。
- 365日間、毎日1つのコンテストを開催する
- コンテストの種類は26種類ある
- 各日に各コンテストを開催したときの満足度が与えられている
- ある種類のコンテストを長期間開催しないと不満足度が増える
- 最終的な満足度ができるだけ大きくなるようにスケジュールを決める
比較する解法
今回は、以下の5つの解法を比較しました。
- 単純な周期スケジュール
- 貪欲法
- 局所探索法
- 焼きなまし法
- ビームサーチ
単純な周期スケジュール
A, B, C, ..., Z, A, B, C, ..., Zのように、コンテストタイプを周期的に並べる方法を試しました。この方法では、問題の入力内容は一切使いません。全てのタイプのコンテストを均等に開催するだけの単純な方法です。
貪欲法
貪欲法は、その時点で最も良く見える選択を繰り返す方法です。この問題では、各日ごとに「その日に開催した場合の満足度 - その日に発生する不満足度」が最大になるようにコンテストタイプを選びました。
局所探索法
局所探索法は、現在の解を少しずつ変更しながら、より良い解を探索するアルゴリズムです。この問題では、貪欲法で作成したスケジュールを初期解として使用しました。その後、ランダムに1日を選び、その日のコンテストタイプを別のものに変更します。変更後のスコアが改善した場合はその変更を採用し、悪化した場合は元に戻すようにしました。
焼きなまし法
焼きなまし法は、局所探索法が局所最適解に陥りやすいという弱点を補うための手法です。局所探索法ではスコアが悪化する変更は採用しません。一方で、焼きなまし法では、スコアが悪化する変更も一定確率で採用します。具体的には、次の確率で採用します。
$$ 採用確率 = exp(スコア差/温度) $$
ここで温度とは悪化する変更を採用する確率を調整するパラメータです。温度は次の式で計算しました。
$$ 温度 = 開始時の温度 + (終了時の温度 - 開始時の温度) * 探索の進行度 $$
この問題では、探索の序盤では温度を高くして悪化する変更を受け入れやすくし、探索が進むにつれて温度を低くして悪化する変更を受け入れる確率を下げるようにしました。
ビームサーチ
貪欲法では、各日ごとに最もスコアが高くなる候補を1つだけ選びます。一方で、ビームサーチでは、スコアが高い候補を複数個残しながら探索を進めます。この問題では、1日目から順番にスケジュールを作成し、各日において26種類のコンテストタイプを試しました。その中からスコアが高い上位の候補だけを残し、次の日の探索に進みます。この残す候補数をビーム幅と呼びます。今回の実装ではビーム幅を200に設定しました。ビーム幅を大きくすると、探索の幅は広がりますが、その分計算量も増えます。一方で、ビーム幅を小さくすると高速に探索できますが、良い候補を途中で捨ててしまう可能性があります。
結果比較
ここまで紹介した5つの手法について、同じ入力データを用いてスコアを比較しました。結果を以下の表にまとめます。
| 手法 | 得点 | 実行時間[ms] |
|---|---|---|
| 単純な周期スケジュール | 13,639 | 3 |
| 貪欲法 | 62,634,806 | 3 |
| 局所探索法 | 107,560,561 | 1,903 |
| 焼きなまし法 | 112,942,859 | 1,905 |
| ビームサーチ | 116,226,047 | 548 |
まず、単純な周期スケジュールは、他の手法と比べて得点が大きく低くなりました。この方法では、入力として与えられる各日の満足度を一切考慮していないため、問題の特徴に合わせたスケジュールが作れていないことがわかります。
貪欲法では、得点が大きく改善しました。各日ごとに、その日に得られる満足度と発生する不満足度を考慮してコンテストタイプを選んでいるため、単純な周期スケジュールよりも入力に応じた選択ができています。
局所探索法では、貪欲法で作成した初期解を少しずつ変更することで、さらに得点を伸ばすことができました。
焼きなまし法では、局所探索法よりもさらに高い得点が得られました。焼きなまし法では、スコアが一時的に悪化する変更も一定確率で採用しているため、局所探索法では抜け出しにくい局所最適解から移動でき、より良いスケジュールに到達できたと考えられます。
最も高い得点となったのはビームサーチでした。ビームサーチでは、スコアが高い複数の候補を残しながら探索するためより良いスケジューリングができたと考えられます。また、実行時間も局所探索法や焼きなまし法に比べてより短い時間となっています。
おわりに
今回は、AtCoderのスケジューリング問題を題材に、複数のヒューリスティック最適化手法を実装し、比較しました。
ヒューリスティック最適化では、単純な方法から始めて、少しずつ探索手法を発展させていくことで、得点を大きく改善できることが確認できました。特に、貪欲法で作成した初期解を局所探索法や焼きなまし法で改善する流れは、ヒューリスティック最適化の基本的な考え方を理解するうえで有効でした。
一方で、探索手法の性能は、評価関数やパラメータの設定によって大きく変わるため、問題の性質に合わせた工夫が重要になります。
参考