問題
方針
- 製造する製品の（形状、色、生産個数）をまとめて
タスクという形にまとめる。 タスクを行う順番を焼きなましで更新していく- 順番が確定した後
生産個数の部分を別の焼きなましで改善していく
タスクの作成
製品を 1個ずつ扱うと計算量が大きくなってしまうのと、基本的に切り替えのコストが大きいのである程度製品をまとめて生産するほうが良くなります。
今回は初期の生産個数を N[s][c] / K[s] と定義してタスクの生成を行いました。
焼きなましによる生産順番の改善
焼きなましによって生産の順番を改善していきます。遷移としては以下の 3つになります。
- 任意の 2つのタスクの順番の入れ替え (swap)
- 2-opt
- 任意の 1つのタスクの位置の入れ替え (insert)
スコア計算ですが1回のループで生産できる個数に制限が存在しているのと、前に設置したハンガーの再利用を考慮すると差分計算が出来ないため、基本的には再計算を行っています。 また、スコアを厳密に計算してしまうと必要な試行回数を稼げないためある程度簡易化したものを利用しました。（簡易版で試行回数 2M 程度)
簡易版では「再利用できるかどうか」の判定を簡略化しており、大まかに「前に設置した形状 s とどれだけ間隔が離れているか」を評価の基準としています。（間隔が H に近ければ近いほど評価しています。）
また、個数制限についても「直前に設置したタスクの生産個数との和が制限を超えているかどうか」だけで判定しており、この辺りの精度も落としています。
ただ、ベストスコアに関しては完全版のスコア関数を利用して比較を行います。
生産個数の焼きなまし
順番を確定させた後に、生産個数について別で焼きなましを行いました。一緒にまとめてやってしまうと非常に複雑化してしまって全然安定しなかったので「順番」→「個数」と別々で行っています。遷移としては「任意の製品を選び生産個数を変動させる」というものになります。
ここでのスコア関数は完全版を使用しています（制限時間は 0.2 sec 程度で試行回数が 20K 程度）。
感想
焼きなましの試行回数が全然稼げず終わってしまいました。簡易版を使用して誤魔化したのですがそれでもまだ足りなかったです。 「切り替えコストを少なくして、なるべくハンガーを再利用出来るようにする」と頭の中では理解していたのですが、結局それをどう評価していけばよいのかがわからず終わってしまいました。良い評価関数を作るにあたってデータ集めと解析を怠ってしまったのは個人的には反省です。
マラソンマッチにおいては「改善できなくなったら負け」なので、継続的にスコアを改善できるような仕組みを考えていきたいですね。
