Excelを使って遺伝的アルゴリズムで組み合わせ最適化問題を解いてみる。
遺伝的アルゴリズムで組み合わせ最適化問題も解ける
前回は遺伝的アルゴリズムで関数の最小値を求めました。
>> 【意外と簡単！】遺伝的アルゴリズムで最小値問題を解く様子をExcelでわかりやすく
今回は組み合わせ最適化問題を解いてみます。
例題は以前の記事で取り上げた以下の例を使います。
>> 【具体例で実演！】人材配置の組み合わせ最適化問題をエクセルマクロVBAで解く
ある物流センターでは、物流加工で4つの工程があります。
各工程1人ずつで受け持ち、毎日合計4人必要です。
今まで延べ7人がこの作業を行ったことがあり、各人の作業生産性（個／時間）と時給は次の通りです。
センター長は、そろそろスタッフを固定したいと思っています。
全体の生産性は一番生産性の悪い工程（ボトルネック）で決まります。
この時、全体の生産性を70以上にしながら、総時給が7,000円以内に抑えられるようにするには、どの工程に誰を割り当てたら良いでしょうか？
例えば、工程Aを鈴木さん、工程Bを高橋さん、工程Cを渡辺さん、工程Dを田中さんに割り当てる場合を考えてみましょう。
工程Bの生産性が70で一番低いため、全体の生産性は工程Bに制約されて70になります。
一方、4人の総時給は2,000＋2,090＋1,800＋1,940＝7,830円となります。
従って、この順列では生産性は70をクリアしますが、総時給は7,000円を上回ってクリアしません。
この問題は840通りも組み合わせがあり、意外と難しいのです。
Excel×遺伝的アルゴリズムで組み合わせ最適化問題を解いてみる
初期値を決める
これを遺伝的アルゴリズムで解くために、まずは佐藤さんから山本さんまでの7人に背番号を付けましょう。
すると、各組み合わせは2513とか7153のように4桁の数字で表すことができます。
前回と同じように、4つの組み合わせを適当に選んで初期値とします。
ここでは1234、2345、3456、4567を初期値とします。
これらが地球上に生まれた最初の種とします。
選別基準を決めて選別する
これら4つの初期値の生産性と人件費を計算してみると、下記のようになります。
例えば、1234の組み合わせでは生産性は31、人件費は7,190となり、条件を満たしていません。
同様に他の3つも条件を満たしていません。
これらの組み合わせを条件を満たすように進化させていくわけですが、何を優秀な種とするかの判断基準が必要です。
生産性は大きい方が良くて、人件費は小さい方が良いので、人件費／生産性が小さければ良い種になりますね。
また、これだと人件費も生産性も同じ比重で評価していることになります。
もし人件費に2倍の重みを置いて評価したい場合には、人件費／（生産性／２）とすれば良いでしょう。
ここでは人件費に3倍の重みを置いて、
総合点＝人件費／（生産性／３）
として優秀な種を選別するための評価基準とします。
上の表にある総合点は、このように計算しています。
4つの種（初期値）の中では3456が一番総合点が小さくて、これが一番優秀な種、2番目は2345になっています。
交叉させる
次にこれら3456と2345を交叉させます。
4桁を真ん中で割ってスワップさせると、3445と2356が生まれます。
でもここで注意しないといけないのは、一人で2つの工程を同時に受け持てないので、4桁の数字はすべて異なっていないといけません。
ですので、3445はダメです。
そこで、このような場合にはタブっている数字の一つを1足した数にするというルールにします。
すると3455になります。
これでもダブってしまいますので、また1を足して3465にします。
これにより3456、2345、3465、2356の4つの種ができました。
突然変異させる
次に、これらの中からランダムに1つを選んで突然変異させます。
4つの種の中から1つを選ぶためには、
=ROUNDUP(RAND()*4,0)
で1から4の乱数を発生させれば良いでしょう。
そして選ばれた種は、4桁のうちの1桁の数字を突然変異させます。
その1桁は1から4の乱数で決めます。
そして、選ばれた1桁には1から3までのランダムな数字を足すことで突然変異とします。
足した数字が7を超えてしまう場合には、7を引いた数字にすることにします。
例えば、次のようになります。
以上により、3476、2345、3465、2356の4つの種ができました。
この中で総合点が最も小さい種は3476で315点です。
初期値の中で最も総合点が小さかった種は3456で327点でしたから、12点進化しました。
選別⇒交叉⇒突然変異を繰り返す
しかし、生産性は74で条件を満たしていますが、人件費は7,780で条件を満たしていません。
ですので生産性、人件費共に条件を満たす種ができるまで、何回もこのステップを繰り返します。
繰り返した結果、13回目で下記のように条件を満たす種が見つかりました。
実は条件を満たす解は下記のように8通りあります。
まとめ
遺伝的アルゴリズムは近似解を探索する方法ですので、これら全部を求めることはできません。
しかし一つの解を求めるだけであれば、このように簡単な遺伝的アルゴリズムでも十分に対応可能であることが分かりました。