メタヒューリスティクス合宿レポート 〜実践的な学びの場を通じて〜

2024年8月某日、株式会社グリッドでは社員の技術力向上を目指し、メタヒューリスティクスに焦点を当てた技術合宿を開催しました。
この記事では合宿の内容と成果、そして雰囲気をお伝えします！

栃木駅からふれあいバスに乗る一行。
 
学習意欲の高い精鋭エンジニアたちです！参加者はデータサイエンティスト・プロジェクトマネージャーをはじめ、電力、海運、サプライチェーンマネジメント、鉄道など、多岐にわたる分野から集まりました。
 
参加者の多くは普段は主に数理最適化や機械学習を扱っており、メタヒューリスティクスを日常的に利用している人は少数でした。
様々な分野のプロジェクトで活躍しているエンジニアが一堂に会し、メタヒューリスティクスの基礎と原理を深く理解し、講義と実装を通じてその実践的な応用方法を学ぶことが、合宿の主な目的でした。

つきました！合宿の舞台、「自然の家みかも」です。空気が澄んでいて、まさに合宿日和。
 
参加者は現地に集合し、全体方針の説明と目標確認のあと、早速グリッドのエンジニアで「ゲームで学ぶ探索アルゴリズム実践入門 ～木探索とメタヒューリスティクス」の著者である” thunder” こと青木栄太さんの講義が行われました。
座学演習に焦点を当て、構築型手法（貪欲法、ビームサーチ）と ※ 局所探索型手法（山登り法、焼きなまし法）について学びました。
 
※局所探索法を山登り法と同一視する文献もあります。本記事では以降、山登り法と山登り法を改善した手法をまとめて「局所探索『型』手法」と呼びます。
 

【合宿1日目】
1日目前半の問題は、青木さんお手製の数字集め迷路でした。この問題を使って構築型手法を学びました。青木さんの問題を使って、実際にみんなで貪欲法やビームサーチを実装してみました！
 
問題詳細はこちら: 世界四連覇AIエンジニアがゼロから教えるゲーム木探索入門 #アルゴリズム - Qiita

熱弁する青木さん！
眼光鋭く、目からビームが出そうですね。ビームサーチだけに。

黙々と考えながら実装するグループ

パソコンとにらめっこしながら、議論するグループ 

続いて1日目の後半は、グリッドの合宿運営チームが考えた問題を使って局所探索型手法（山登り法と焼きなまし法）について学びました。これらの手法は、完全な解から徐々に解を変化させていくアプローチを取り、構築途中で評価が難しい問題に適しています。また、完全な解から一部を崩しても影響が小さい問題に対して有効です。 問題の詳細はこちら。

 

（問題作成：グリッド社員）
 
縦軸がライン、横軸が日数を示すビジュアライザです。
コストは赤色に近づくほど高く、水色に近ければ低くなります。①〜④は局所探索によって生産計画のコストが改善していることを示しています。 

集中して解き進めるグループ

 見守られながら落ち着いて進めるグループ

議論が熱くなっちゃいますね、焼きなましだけに。 
 
試行錯誤を通し、参加者が山登り法や焼きなまし法を実装できるようになりました！

 
1日目の講義が終わり、晩御飯とお風呂でさっぱり！
 

 1日の終わりは飲み会だ！
 
飲み会の余興でLT会を行いました。多くの方が思い思いの発表を行い、盛り上がりました。

 キーボードへのこだわりを語る

ヨーヨーの実演

同僚の知らない一面を知れるのも合宿の醍醐味です。熱く語り合い交流を深めながら夜は更けてゆきました。

【合宿2日目】

朝食をしっかり食べて、２日目の演習に備えます。

2日目は、丸1日かけて演習問題に挑みます。参加者は学んだ理論を実際の問題解決に適用しました。
演習内容は、AtCoderのAtCoder Contest Schedulingです。
この問題を選んだ理由は、1日目に習ったビームサーチと局所探索法のどちらのアプローチも使うことができ、比較的短時間で実装できるためです。

ホワイトボードを使って実装方針を議論するグループ

問題演習後、合宿の締めくくりとして行われた発表と討論の時間では、多くの興味深い気づきがありました。

 「最初は難しそうに感じましたが、実際に手を動かしてみると、構築法や局所探索法が思ったより実装できました」
「アルゴリズムに少し工夫を加えただけで、驚くほどスコアが上がりました。これが上位解につながったんです」
といった意見には、特に多くの同意が寄せられました。
 
また、当社独自のメタヒューリスティクスライブラリについても、

 「ライブラリを使うことで、難しい部分の実装を省略でき、本質的な部分に集中できました」
「汎化部分と問題特有の実装の区別がよくわかり、今後の業務にも活かせそうです」
「ライブラリのおかげで、メタヒューリスティクスの敷居がぐっと下がった気がします」
 
といった感想が寄せられ、多くの参加者が今後の積極的な活用に意欲を示していました。
 

最終発表！

運営側の想定解発表！

青木さんの1位解法発表！（グリッドならではの恩恵ですね！）
解法記事はこちらのリンク(Introduction to Heuristics Contestの延長戦1位解法解説 #AtCoder - Qiita)でご覧になれます。
 
 
以下、参加者からの今回の合宿の感想です。
 
「（グリッド独自の）ライブラリが非常にわかりやすく、すぐに適用できる形式だった」
 
「標準化されているため、重要な点（解き方や高速化）に集中しやすい」

「焼きなまし法は、問題特有の事情をあまり考慮せずとも、ある程度の点数が出ることを確認できた」
 
「ビームサーチはこれまで実装経験がなく選択しづらかったが、今回の実装経験によって選択肢として挙げやすくなった」

「プロジェクトマネージャーとして、今後の顧客説明時などの基礎知識として役立ちそう」

「評価関数を独自に工夫し、貪欲法で短時間でもそこそこ良いスコアを取ることができた」
 
「はじめに貪欲の解を実装してスコアが出ることを確認し、その後ベースコードを用いてビームサーチを実装できた」
 
「最終的にグループ全員が自力でビームサーチを実装できるようになった」
 
ということで、合宿を通じて参加者が見事メタヒューリスティクスの基礎と原理を理解し、使いこなせるようになりました！

 最後に集合写真！みんなで、はいチーズ！

ここまで読んでいただき、ありがとうございました！
 
グリッドでは、最適化エンジニア・データサイエンティストを募集しています。
グリッドの仲間たちと一緒に楽しく働き、社会を変えるイノベーションを起こしていきませんか？
興味がある方は、ぜひこちらの求人もご覧ください。カジュアル面談も随時実施中です！
たくさんのご応募、お待ちしています！！

数理最適化エンジニア

データサイエンティスト

オープンポジション（カジュアル面談）