はじめに
HACK TO THE FUTURE 2022予選というヒューリスティック形式のコンテストが先日行われました。筆者は今年に入ってからヒューリスティック形式のコンテストを始めた比較的新入りの部類（年は取っていますが…）ですが、700人以上も参加者がいる中で最終16位というかつてない好成績を取ることができたので、どんなことを考えて取り組んだかを書いてみたいと思います。
ヒューリスティックの技術やアルゴリズム的なところではその道のエキスパートに及ばないので、試行錯誤の様子を中心に書いてみることにします。これから取り組む方の参考になると幸いです。
問題概要
詳細は公式問題文にありますが、要点を整理しておきます。
- 1000個のタスクがあり、20人のプロジェクトメンバーがいる。うまく割り当てて早く終わらせたい
- 10〜20種類のスキル要素があり、メンバーは各スキルの値が決まっているが、その値は知らされていない
- タスクにも必要となるスキルの量が決まっていて、それは予めわかっている
- タスクに必要なスキルに満たないメンバーが割当たると、足りない分の和だけ、完了するのに日数がかかる
- タスク間にはAが終わらないとBが開始できないというような依存関係がある
最初に考えたこと
- 得意なスキルに応じてタスクを割り振りたいので、そもそもメンバーのスキルを推定したい
- タスク間に依存関係があり、クリティカルパスができそうなので、パスの長いタスクを優先してやる等、タスクの割り当て方を工夫したい
そこでまずはスキルの推定から取り組むことにしました。
※説明の都合上、スキル推定に書かれていることを全部やってから、タスク割り当てに移った感じに書いていますが、実際には一部並行してやっています
メンバースキルの推定
アプローチ
- メンバースキルの手がかりは、実際にタスクをこなしてみてそれが何日かかったか、ということでしか得られない
- 10〜20種類のスキルがあるのに、1個のタスクで得られる情報は日数という1個の値だけ
- 全タスクで1000個なので、1人平均50タスクが割り当てられる。ということは50個程度の情報しか得られない
- 必要スキルを上回るスキルを持っている場合は、どれだけ上回っているかは日数には反映されない
- その上、プラスマイナス3日の誤差がついてくる
ということで、正確にスキルを見積もるのは難しそうですが、ある程度得意不得意の傾向が分かれば良いかなという程度で、以下の方向で取り組むことにしました。
- タスクにかかる時間は、そのタスクで要求量の大きいスキルの影響が強いはず
- なので、その時点で推定スキルで見積もった日数と、実際の日数の誤差を以下のように分配
- 誤差がプラス(スキルが実際より低く見積もられている)の場合は、各スキルの「要求量-現在推定量」に比例して誤差を分配
- 誤差がマイナス(スキルが実際より高く見積もられている)の場合は、各スキルの「min(要求量、現在推定量)」(つまりそのタスクで発揮したと推定されるスキル量)に比例して誤差を配分
- パラメータの決まり方から、スキルベクトルの長さと単位ベクトルに分けて推定を進める
実際の実装は、以前のコンテスト(AHC003)の時に覚えて使ったベイズ更新を使いました。その時はベータ分布を仮定してやりましたが、今回は正規分布を仮定してやってみることにしました。
試行錯誤
初期の工夫
当然のことながら単位ベクトルの各要素をベイズ更新すると長さが変わってしまうので、長さが1になるように補正するようにしました。単純に実装してみたところ、全般的にスキルの長さがあまりうまく推定できていないようでした。高いスキル要素があったとしても、あまりうまく捉えられず、結果的に全体として低く見積もってしまうようでした。そこで、以下の工夫を入れました。
- スキルの長さは何パターンか用意して固定し、それぞれで単位ベクトルを推定してみて一番良いものを使う
- 単位ベクトルの長さは補正せずにベイズ更新をしてみて、結果的に長さが1に近いものが一番良いはず
これで少し改善できましたが、全体的にまだ高スキル部分を過小評価している感じでした。
謎の補正項による改善
以前のコンテストでもあったのですが、誤差を多めに配分すると何故か改善することがあったので、今回も特に根拠のない謎の補正項を加えて誤差を多めに配分してみたところ、だいぶ改善しました。
さらに、用意するスキルの長さを増やすことで、精度をあげることができました。当然のことながら推定に必要な時間は増えてしまいました。
繰り返し学習による改善
これまでは1個結果が増えるごとに1回ベイズ更新を行っていたのですが、これまでのタスクの履歴を取っておいて、毎回最新の方から更新し直すようにしたら、精度が改善しました。さらに1個の結果が増えたときに、過去の履歴を数回ループして学習するようにしたらさらに改善しました。
ただ、時間がさらにかかってしまうので、ここで思い切ってスキルの長さも学習するように戻してみましたが、悪くなかったので、この方針でいくことにしました。
この辺りで、スキルの推定は一区切りとして、タスクの割り当てに重点を移すことにしました。
タスクの割り当て方
アプローチ
全体的には、優秀な人には難易度の高いタスクを、そうでない人はそれなりのタスクを(古い)割り当てるのが良いかなというのが直感でした。
また、クリティカルパスの問題についても予め「パスの長さ」を計算しておいて、長いものから順にこなしていくことで、少しでも早く終わらせることができると考えました。
試行錯誤
身の丈にあったタスクの割り当て
最初はメンバーのスキルと似たような要求スキル量のタスクを割り当てるのが良いのかなと思って、メンバーのスキルベクトルと、タスクのスキルベクトルの距離が近いものを選ぶようにしてみました。
各メンバーに対して、予め計算したパスの長さでソートしておいたキューの先頭X個(適当な値で調整)の中から、上記距離が最も近いものを貪欲に選んでみました。
「発揮スキル」を大きくするには
ここで問題の設定を冷静に解釈し直してみました。タスクはスキル0の人が実行したとしてもかかる日数はタスクが要求する各スキルの和になります。そこから、担当メンバーが持っているスキルで、要求スキルを上回らない分だけ差し引くことができます。この要求スキルを上回らない分のことを「発揮スキル」と呼ぶことにします。
すると、全体の所要工数は全タスクの要求スキルの総和から、発揮スキルの総和を引いたものになります。前半は各テストケースで固定ですから、今回の問題は発揮スキルの総和をいかに大きくできるかということになります。
- 発揮スキルは、タスクの要求スキルが大きければ大きいほど、頭打ちで発揮できなくなるスキルが減るので大きくなる
- しかし1個のタスクで発揮できる回数は1回なので、タスクの実行日数が長いと1日当たりに換算した発揮スキル量が低くなる
- そこで、「推定発揮スキル/推定所要日数」が大きくなるようにタスクを割り当てていきたい
各メンバーに対して、予め計算したパスの長さでソートしておいたキューの先頭X個(適当な値で調整)の中から、「推定発揮スキル/推定所要日数」が最大になるタスクを貪欲で実行するようにしました。ただしこれだとキューの先頭を誰も取らなくなってしまう可能性があるので、クリティカルパスの深さで傾斜をかけて評価するようにしました。
しかし、思ったほどにはスコアは伸びませんでした。
seed5問題
そこでスコアの低いテストケース(例えばseed5)についてビジュアライザを見てみたところ、割と早い段階でスカスカになっていました。タスクが終わらなくなる要因として、クリティカルパスが長くなりすぎてそのパスが終わらなくなるという想定はあったのですが、序盤のうちにやるタスクがなくなるということは想定できていませんでした。
これを改善するには、発揮スキルを最大にするのはさておいて、とにかく所要日数を短くなるように振る必要があると考えました。ただ、通常時は発揮スキルを大きくすることも重要なので、以下のような方法を取ることにしました。
- タスクの中で緊急でやらなければならない「ヤバい」タスクを抽出
- 全体の残りタスク数に対して、子タスクの数が多いものは「ヤバい」
- 実行可能なタスクが少ない状況での、クリティカルパス先頭のタスクは「ヤバい」
- 残りタスク数がクリティカルパスの個数×20程度より少ない場合の先頭タスクは「ヤバい」
- 「ヤバい」タスクは最短で終わらせることができる人に振る(現在タスク実行中の場合は、実行中タスクの終了までの日数も加算)
- 「ヤバくない」タスクは発揮スキル最大化のポリシーを維持
これでスコアはだいぶ改善し、やっと暫定テストで90Kを超えるようになりました。
「ヤバい」タスク割り当ての工夫
上述の時は、「ヤバい」と判断した時点で実行する人を決めて、その人が実行するようにしていたのですが、以下の欠点があることに気づきました。
- 割り当て予約した人が、その時点で持っていたタスクが思ったよりも時間がかかってしまい、なかなか終わらない
- そうこうしている内に、比較的優秀な人の手が空くが、予約済みのため割り当てられない
そこで、予約という考え方はやめて、「ヤバい」タスクについては毎日最適な人を再計算して実行するようにしました。これでスコアが2〜3K上がりました。
※実際の時系列では、この辺りと並行してスキル推定の後半に書いた改善を実行し、100Kを超えるあたりまでは到達しました。
クリティカルパスの精度改善
これまでは単純にクリティカルパス上のタスクの個数を長さとして管理していましたが、タスクの要求スキルはあらかじめわかっているので、タスクの要求スキルの和と所要日数の実際の関係の統計を取ってみて、予め平均的な所要日数を見積もり、クリティカルパスの長さを、その予想日数で評価できるようにしました。
比較優位論
ここで、全体最適・部分最適のような文脈で「比較優位」という考え方があるのを思い出しました。以下のようなことを試してみました。
- メンバーのスキル量に対して、発揮スキル/日数の平均量の統計を取ってみる
- その平均量に対して、割り当てようとしているタスクの推定発揮スキル/推定日数の比を計算してみる
- この比の大きさで割り当てるようにしたら、全体的にスキルの低い人も相対的にスキルを発揮できて全体効率が上がるのではないか？
結果的に、これはあまりうまくいかず、最終的には没にしました。
最小費用流
ここまでは、その日に空いた人に対して、キューの先頭の方X個の中で、貪欲にその人に相応しいタスクを選ぶようにしていました。キューの先頭の方のタスクがいつまでも消費されずに残ってしまうのを防ぐため、先頭の方の評価を高くする傾斜をかけていましたが、結果として対して最適ではないのに先頭の方を取ってしまい、あまりマッチしていないタスクが割当たってしまうケースがありました。
これを防ぐために、キューの先頭20個とメンバー20人でどの組み合わせが最も相応しいかをマッチングして、それで割り当てるようにすれば、傾斜をかける考え方をせずに前の方から消費できるので良くなるのではないかと考えました。
これを実現するために、今回「最小費用流」を勉強して実装しました。(蟻本の写経ですが)
これで0.6〜0.7Kくらい改善しました。
この考え方が「ヤバい」キューの方にも適用できないかと思ったのですが、それはうまくいきませんでした。
複数キュー
この時点では、通常時のキューとしてクリティカルパスの所要日数の長いものから処理するようにしていたのですが、実行可能なタスクが少ないようなテストケースではもっと優先的に処理した方が良いものがあるのではないかと考えました。
いろいろな状況に対応できるよう、実行可能なタスクを優先順位づけの異なる複数のキューに入れて、それぞれのキューの先頭からいくつかずつ取り出し、合計20個：メンバー20人で割り当てるようなやり方にしてみました。これによって、通常時においても色々な観点でなんとなく優先度の高そうなものから処理されていく状況を作ることができました。実際に使った優先度付けは以下の通りです。
- クリティカルパス上の推定所用日数の長い順
- 直下の依存タスク数の多い順
- 配下全体の依存関係数の多い順
この他にも子タスクの多い順とか、クリティカルパスの個数の長さの長い順とか色々やりましたが、上記の組み合わせがバランスが良いようでした。意外だったのが直下(つまり1個下)の依存タスク数の多い順でこれが割と有効でした。おそらく直近の実行可能タスクの枯渇に有利に働くということなのでしょう。
これで0.4Kほど改善しました。
ゴールの仕方の改善
ビジュアライザを見て思ったのは、プロジェクトの最終盤ではなるべく同じタイミングで一斉にタスクを終わらせられるのが良いということで、これを実現するために、全体の残りタスク数が少なくなった場合は発揮スキルではなく終了日数ベースで最小費用流を使うことにしました。これもわずかですが効果がありました。
炎上プロジェクト対応
この時点で、緊急ではない通常キューはタスク20対メンバー20人の最小費用流でマッチングしていましたが、「ヤバい」タスクが多発する「炎上プロジェクト」では、優秀なメンバーが緊急タスクにかかりきってしまって、通常キューでそのメンバーに割り当てるつもりのタスクがいつまでも消化されないというケースがあることに気づきました。
このような状況では、割り当て対象のメンバーは20人にするのではなく、その瞬間空いている人だけにするようにしました。
また、3000個のテストケースを生成して、結果が良くなかったワースト100個のテストケースで上述の複数キューの調整をしたりしました。
それから、開始早々にタスクが枯渇するプロジェクトで、最初に能力の低い人が重要なタスクを延々と続けてボトルネックになっているケースがあったので、最初は様子見として全員になるべく要求スキル量が一定の値以下のを渡すようにしました。
パラメータ調整
この辺りでできることがなくなってきたので、最後はパラメータ調整に専念することにしました。チューニングの精度と試行錯誤の効率も考えてテストケースは300個でなるべく安定的に良くなるようにパラメータをチューニングしました。
デフォルトの50個のテストケースでチューニングしていた人も多いのではないかと思いますが、それよりは多くのテストケースでチューニングしたせいか、暫定テストからシステムテストの過程で順位が5つ上がりました。チューニングの際のテストケースの多さはポイントとなるようです。
最終的に投稿したチューニング結果では、実は暫定テストのスコアは若干下がったのですが、300個のテストケースの方を信じてそのまま残して良かったです。
終わりに
筆者は競技プログラミング歴自体は10年以上と比較的長いのですが、ヒューリスティック形式のコンテストは食わず嫌いをしてきました。今年に入ってAtCoderでヒューリスティックコンテストが定期化されたのをきっかけに始めてみたところ、面白さに気付いてそれ以降なるべく取り組むようにしています。
こういった泥臭いやり方でも戦えるのだということで、ヒューリスティックコンテストに興味を持って参加者が増えていくと良いなと思っています。