Excelを使って遺伝的アルゴリズムで組み合わせ最適化問題を解いてみる。前へ次へ検索RSSFeedlyホーム>Excelで機械学習>Excelで試してみるExcelを使って遺伝的アルゴリズムで組み合わせ最適化問題を解いてみる。Udemyの関連講座リンクリンク遺伝的アルゴリズムで組み合わせ最適化問題も解ける前回は遺伝的アルゴリズムで関数の最小値を求めました。【意外と簡単!】遺伝的アルゴリズムで最小値問題を解く様子を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倍の重みを置いて評価したい場合には、人件費/(生産性/2)とすれば良いでしょう。総合点=人件費/(生産性/3)として優秀な種を選別するための評価基準とします。上の表にある総合点は、このように計算しています。4つの種(初期値)の中では3456が一番総合点が小さくて、これが一番優秀な種、2番目は2345になっています。交叉させる次にこれら3456と2345を交叉させます。4桁を真ん中で割ってスワップさせると、3445と2356が生まれます。ここで注意しないといけないのは、一人で2つの工程を同時に受け持てないので、4桁の数字はすべて異なっていないといけません。そこで、このような場合にはタブっている数字の一つを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点です。繰り返すしかし、生産性は74で条件を満たしていますが、人件費は7,780で条件を満たしていません。生産性、人件費共に条件を満たす種ができるまで、何回もこのステップを繰り返します。繰り返した結果、13回目で下記のように条件を満たす種が見つかりました。実は条件を満たす解は下記のように8通りあります。まとめ遺伝的アルゴリズムは近似解を探索する方法ですので、これら全部を求めることはできません。一つの解を求めるだけであれば、このように簡単な遺伝的アルゴリズムでも十分に対応可能であることが分かりました。AI数学-文系でも理解できる!高校から始めるデータ分析、AIのための数学-データ分析、機械学習に関わる数学に絞り、効率的に学習できるようカリキュラムを構成しました。文系でも理解できるよう丁寧な説明をしています。Pythonエンジニア育成推進協会認定スクールによる高品質な数学コースです。–1000人以上が受講している(株)キカガクの『脱ブラックボックスセミナー』が遂に登場!機械学習の参考書を「閉じてしまった人」への再入門に最適な講座です。微分・線形代数といった数学の基礎からPythonでの実装まで短時間で習得しましょう。永遠の旅人よろしければシェアお願いしますTwitterFacebookLinkedInB!HatenaLINELINE【初心者向け】ニューラルネットワークの仕組みをわかりやすく解説Next遺伝的アルゴリズムをExcelに実装して最小値問題を解いてみた。Prevリンクリンク関連記事サポートベクターマシンをExcelに実装して2クラス分類問題を解いてみた。...最終兵器AdamのアルゴリズムをExcelに実装して具体例を解いてみた。...【マルコフ連鎖】翌日配送が翌々日配送になると在庫は何台必要か?某物流センターでは自動梱包機を2台レンタルしています。【区間推定の使い方】タイヤの摩耗を具体例にわかりやすく解説します。TOP28【作業分析6】MMCモデル|最適なトラックドック数をSimpyでシミュレーション【作業分析5】トラックの待機台数の多さを人の表情でアニメーション(2)カンボジアの物流でお困りのことがあればお気軽にご相談下さい。学生時代にアジアの雑踏にハマる。誰もが羨むメーカーを退職し「旅するように働く」ことを目指し物流業界に転職。理工学と経営学のダブル修士。2023年1月からカンボジアのオートレスビーチ在住。