【要約】焼きなましでシフト表を組む前に、初期解の構造を疑う [Zenn_Python] | Summary by TechDistill
> Source: Zenn_Python
Execute Primary Source
// Problem
開発者が、シフト作成の自動化を目指して焼きなまし法を実装した際に、解の品質が改善しない問題に直面した。探索ロジックや評価関数の重みを調整しても、出勤日数の偏りや制約違反が解消されなかった。主な要因は以下の通りである。
- ・近傍操作による制約の固定: 交換操作では日ごとの人数構成が変わらないため、初期解の制約違反が探索で修正不能になる。
- ・探索距離の増大: ランダムな初期解では、個人の出勤日数の偏りが大きく、最適解に到達するまでの距離が遠すぎる。
- ・収束判定の誤り: 温度が高い段階での一時的な停滞を「収束」と誤認し、探索を早期終了させてしまう。
// Approach
探索の効率を上げるため、探索ロジックをいじるのではなく、問題の構造を初期解に組み込む設計変更を行った。具体的には、以下の手法を採用した。
- ・列固定方式の導入: 1日分の正しい構成（列）を作成し、全日にコピーする。これにより、日ごとの人数バランスを構造的に保証する。
- ・列の回転による均等化: 列を日ごとに1つずつずらして配置する。これにより、個人の出勤日数のばらつきを初期解の段階で最小化する。
- ・差分評価による高速化: コスト計算を1行単位（O(D)）に限定する。これにより、1回の評価計算量を大幅に削減する。
- ・収束判定の適正化: 冷却が完了した後にのみ、改善率に基づく早期終了を適用する。
// Result
50人規模のシフト作成において、解の品質向上と計算時間の短縮を同時に実現した。設計変更により、以下の成果が得られた。
- ・出勤日数の幅の改善: ランダム初期解での10日から、最終的に1日へと劇的に縮小させた。
- ・制約遵守の達成: ハード制約（連勤上限やインターバル）の違反をゼロに抑えた。
- ・計算性能の向上: Pythonのプロトタイプでありながら、最大ケースを約1.42秒で処理する高速性を達成した。
Senior Engineer Insight
> アルゴリズムの「賢さ」に頼る前に、問題の「構造」を捉え直す設計判断の重要性を説いている。探索空間の性質（不変量）を理解し、初期解で制約を担保するアプローチは、実装の複雑さを抑えつつ実用的な解を得るための極めて実践的な戦術である。ただし、厳密解や複雑な個別制約が必要な場合は、制約ソルバーの採用を検討すべきだ。