[PR]当サイトはアフィリエイト広告を利用しています。
今回は遺伝的アルゴリズムの活用例について解説していきます。
遺伝的アルゴリズムというのは数理最適化理論の中に存在する最適化手法の中の一つの進化計算と言われる分野の手法の一つです。
生物の進化のようなアルゴリズムで変数を更新し、最適解を得ることができます。
数理最適化の概要については以下をご覧ください。
また過去記事で遺伝的アルゴリズムの概要とプログラミングを行いました。遺伝的アルゴリズムについて知りたいときにご活用ください。
さて今回の目標は「遺伝的アルゴリズムの活用例を知る」ということです。
遺伝的アルゴリズムという名前を聞いたことがあっても以下のようなお悩みが生じると思われます。
- なんの役に立つのかわからない
- 活用例がわかっても、自分の目の前の問題に応用できない
- そもそも遺伝的アルゴリズムの中身（交叉・突然変異・ルーレット選択など）がよくわからない
今回はこのようなお悩みをサポートするために以下のような項目を解説していきます。
- 遺伝的アルゴリズムのアルゴリズムの概要
- 遺伝的アルゴリズムの活用例
実用レベルのスケジューリング問題などを自分で一から作成するのは高度な知識を要するので専門家にお願いするのが一般的です。
今回は活用例を基にご自身で遺伝的アルゴリズムのシステムを実装するという方向で解説するのは諦めました。実装レベルのことができるようになるには大学院修士での専門教育が必要なレベルとなり、初心者が遺伝的アルゴリズムの概要とアルゴリズムを理解したくらいでは実問題を解決できるレベルになるのが不可能だからです。
そのためシステムを作成したいときは専門家に依頼しましょう。クラウドソーシングなどでも最近は数理最適化システムの構築を請け負っている企業があるので、そうしたところにお願いすることになるかと思います。
今回の記事で遺伝的アルゴリズムの活用例の理解が深まり、ご自身の目の前の問題に数理最適化が利用できそうだ、となれば幸いです。
遺伝的アルゴリズムの概要
遺伝的アルゴリズムのアルゴリズム
詳細は以下の記事で解説していますが、おさらいとしてここではアルゴリズムの概要を解説します。
遺伝的アルゴリズムのアルゴリズムの概要は以下となります。
\(f(\boldsymbol{x})\)→最小化
制約条件：\(g_{1, 2,\ldots ,m}(\boldsymbol{x})\)
変数：\(\boldsymbol{x}=(x_{1}, x_{2},\ldots x_{p})\)
- STEP1：初期化。遺伝子群を作成。初期値を代入。初期値を基に関数の値を計算
- STEP2：終了条件を満たしていれば終了。そうでないならSTEP3に移動する
- STEP3：遺伝子群の各遺伝子でルーレット選択によって対となる二つの遺伝子を選択。これらを交叉する。その後ある一定の確率で突然変異を遺伝子に発生させる
- STEP4：交叉後の遺伝子の関数の値を計算。STEP2に戻る
実際の具体的なアルゴリズムの動きについては以下の記事をご覧ください。
遺伝的アルゴリズムの何が優れているのか
遺伝的アルゴリズムが他の最適化手法に対して優れている点は以下のようになります。
- 局所解が多数存在する複雑な目的関数でも大域解が求まりやすい
- 目的関数を微分できない組合せ最適化問題を解くことができる
数理最適化ソルバーであるエクセルのソルバー機能の中では「エボリューショナリー」が遺伝的アルゴリズムっぽい手法となります。
詳しくは上記の記事でまとめてありますが、ここでも簡単に解説します。
まず最適解には局所解と大域解が存在します。局所解はその解の周りで目的関数が変化しない（微分した値がゼロ）底のような場所です。数理最適化手法の一つである最急降下法などの勾配法で求まる最適解は局所解となります。局所解は複数存在する可能性があり、複数の局所解からどの局所解が一番小さいか判断するのは難しい問題です。
これに対して、すべての底のうちで最も小さい目的関数の値になる真の最適解が大域解です。これが変数空間で最も小さな目的関数の値をとる最適解です。
遺伝的アルゴリズムは解の探索に微分した値を利用しないので、局所解の特徴である微分した値がゼロという条件でアルゴリズムが止まりにくいため大域解を求めやすい手法となります。とはいえ何らかの値に収束することが多いので、局所解で止まる確率はゼロではありません。他の手法よりは大域解が求めやすい、くらいの性能です。
また遺伝的アルゴリズムは組み合わせ最適化問題を解く性能が高いです。組み合わせ最適化問題については以下の記事で解説しています。
●エクセルソルバーと組み合わせ最適化問題【解法例と基礎知識】
遺伝的アルゴリズムは探索に微分した値を使わないので、最急降下法などの勾配法の特徴である小数で表現される小さなステップ幅で徐々に解を更新する必要がなく、解がゼロか1となるような組み合わせ最適化問題であるナップサック問題や巡回セールスマン問題を解きやすい手法となります。
遺伝子に相当する解のパターンを作ってそれが良い値なら残し、悪いなら残さないということをやっているだけなのです。パターンの生成に離散値だけ生成するような規則を作れば簡単に、主に0か1という離散変数の問題も解けるようになります。
また総当たり法では現実的な時間で解けない最適化問題も、遺伝的アルゴリズムならアルゴリズムの繰り返しが増えるほど現在の解よりはよい解がどんどん求まっていくので、完全な大域解でないにしろ、そこそこ良い解が現実的な時間内に得られます。実用レベルでは大域解を得るよりも、限られた時間内にとりあえず現状より改善した解が得られれば十分という場面は少なくないので、これも遺伝的アルゴリズムを利用する利点となります。
遺伝的アルゴリズムの活用例
ここでは遺伝的アルゴリズムの活用例についてご紹介していきます。実際に簡単な例題で対象とする問題を解いたりしていますが、遺伝的アルゴリズムで組み合わせ最適化問題を解こうとすると、アルゴリズムに大幅な修正が必要になるので、今回はエクセルのソルバーのエボリューショナリーというソルバーで解いたら遺伝的アルゴリズムで解いたということにします。
エボリューショナリーは進化計算のソルバーなので、同じ進化計算の遺伝的アルゴリズムで解いたということにしました。
ナース・スケジューリング問題
「ナース」と付いているから看護師さんの問題かな、と思われるかもしれませんが、要するにシフト管理の問題です。制約条件から外れた結果になる変数の組み合わせを選ぶたびに目的関数にペナルティを与え、「ペナルティを最小にする組み合わせは一番制約条件を多く満たしている良い組み合わせだ」という発想のもと解を探索します。
実用レベルになると法規制や従業員の相性問題（同じメンバーだけで組み続けるといじめが生じるなど）なども制約条件に組み込むので非常に複雑な問題になります。
条件が複雑になるほど、現在のメンバーではすべての制約を満たす解が存在しなくなる傾向が高くなります。そういうときは優先したい制約のペナルティ量を多くして、最低限これだけは満たしておきたいという条件だけ満たせるという妥協案が求まる場合が多いです。
実際の研究レベルでの実装は例えば以下の文献などがあります。
星野 孝総, 安岡 優斗, 服部 綾乃, 四宮 友貴, 遺伝的アルゴリズムの看護師勤務表作成問題
への適用と一考察, 高知工科大学システム工学群, 2014年
この中で遺伝的アルゴリズムが使用されています。文献中のナース・スケジューリング問題では次のような制約を扱います。
（1）6 日間連続勤務
（2）夜勤明けの日勤
（3）準夜勤・夜勤は合わせて月 9 回以上
（4）6 日間に準夜勤・夜勤合わせて 4 回以上
（5）新人看護師の土・日・祝日出勤
（6）新人看護師の準夜勤・夜勤
具体的な最適化問題の定式化は書かれていませんが、かなり複雑な条件分岐を採用していることが予想されます。
そこでなるべく問題の概要がわかるよう、以下で簡単なバイトシフト問題を例に解説していきます。
アルバイトが4人いる。それぞれのアルバイトは二日連続で働いてはいけない。一日にアルバイトは二人必要。シフトを組まなければいけないのは月曜日から水曜日の3日。これを満たすシフト表を作成せよ。
\(\boldsymbol{x}\)は0か1
上の定式化を解説していきます。
まず制約条件\(pg\)が二日連続働いてはいけないという制約です。二日連続で働くとペナルティを課します。
続いて制約条件\(qg\)が一日に二人だけ働くという制約です。働く人数が二人以外になるとペナルティを課します。
そして制約\(pg\)と\(qg\)の合計を目的関数\(f\)とします。
これまで解説してきた数理最適化の記事にはない特徴がIf関数の利用です。ある条件を満たすかどうかというのを数式で表現するのは難しいので、プログラミング的に条件分岐で制約条件を表現しています。
こうした条件分岐が目的関数に含まれる場合、目的関数はなめらかでなくなるのでGRG非線形などの勾配法は使えません。しかし遺伝的アルゴリズムならなめらかでない目的関数でも求解できるので、ナース・スケジューリング問題と相性が良いです。目的関数の「なめらか」という条件については次の記事をご確認ください。
実際にこれをエクセルのソルバーのエボリューショナリーで解いてみます。エボリューショナリーの中身は進化計算なので、同じ進化計算のカテゴリーに入る遺伝的アルゴリズムでも同様の結果が得られると仮定しました。
エクセルのセルに以下のように入力します。
各セルの値は次のようにします。
- $B$2:$D$5：0
- F2：=IF(B2+C2=2, 10, 0)
- F3：=IF(B3+C3=2, 10, 0)
- F4：=IF(B4+C4=2, 10, 0)
- F5：=IF(B5+C5=2, 10, 0)
- G2：=IF(C2+D2=2, 10, 0)
- G3：=IF(C3+D3=2, 10, 0)
- G4：=IF(C4+D4=2, 10, 0)
- G5：=IF(C5+D5=2, 10, 0)
- H2：=IF(SUM(B2:B5)<>2,10,0)
- I2：=IF(SUM(C2:C5)<>2, 10, 0)
- J2：=IF(SUM(D2:D5)<>2, 10, 0)
- K2：=SUM(F2:F5)+SUM(G2:G5)+SUM(H2:J2)
ソルバーの設定は次のようにします。
解決方法にエボリューショナリーを選択します。解決ボタンを押すと次のようになります。
すべての制約を満たした解が得られました。
ナップサック問題
次のような問題はナップサック問題と呼ばれる組み合わせ最適化問題です。
遠足に行くときにお菓子を持っていくことになった。お菓子の条件は合計1000円までと決められている。お菓子の候補は以下となる。各お菓子には満足度が存在する。このとき条件を満たしつつ、お菓子の満足度の合計が最大になる組み合わせを求めなさい。
| お菓子 | 金額 | 満足度 |
| 1.チョコクッキー | 250円 | 2 |
| 2.ポテトチップス | 200円 | 3.5 |
| 3.チョコレート | 150円 | 2 |
| 4.フィナンシェ | 300円 | 3 |
| 5.どら焼き | 300円 | 1 |
詳細な解き方は以下の記事でまとめてあります。
●エクセルソルバーと組み合わせ最適化問題【解法例と基礎知識】
実際にエボリューショナリーで解くと次のような解となります。
- 持っていくお菓子：1, 2, 3, 4
- 合計金額：900円
- 満足度の合計：10.5
実際の研究レベルでは次のような問題が解かれています。
近田康夫, 橘謙二, 城戸隆良, 小堀為雄, GAによる既存橋梁の補修計画支援の試み, 土木学会論文集 1995 巻 513 号 p. 151-159, 1995年.
橋梁の補修に関する問題を扱っています。
制約条件は予算が橋梁の補修費の合計を超えないことです。
目的関数は橋梁の改善された評価値に補修費用を掛けたもの、の最大化となっています。傾向的に補修費用がたくさん必要な大規模な部分が大きく改善されればそれだけ良い補修をした、という状況になりやすい目的関数となります。
変数はどの橋梁のどの部分を補修するかを0か1で表したものとなります。
予算を守りつつ、という部分は上のお菓子の話の費用上限に相当します。また橋梁の目的関数はお菓子の例の満足度に相当します。
施設配置問題
以下のような問題は施設配置問題と呼ばれる組み合わせ最適化問題です。実際の解き方は以下の記事をご覧ください。
●エクセルソルバーと組み合わせ最適化問題【解法例と基礎知識】
コンビニを出店することになった。候補地は2つある。周辺には町が2つある。町からコンビニまでの距離は近い方が集客できるので町からコンビニまでの距離の合計は近い方がいい。どちらの候補地を選べばよいか。
| 候補地 | 町A | 町B |
| 候補地1 | 1km | 2km |
| 候補地2 | 1.5km | 1.2km |
最適解は候補地2です。
研究レベルでは色々な例がありますが、基本的に目的関数を設定する際にどのようなモデルを使うのかというのが重要で、単純な距離だけで良い場合や、方角や周辺都市の繫栄度などを考慮したモデルが必要な場合など多岐にわたります。
巡回セールスマン問題
過去に当ブログではエクセルのソルバーで巡回セールスマン問題を解いてみました。
かんたんに言うと、以下のようにある地点があったときに、すべての地点を回って一筆書きで出発点に戻ってくるときに、移動する総距離が最短になるような回り方を求める問題です。
上の記事ではシンプレックスLPで解きましたが、エボリューショナリーで解いても同様の解が得られました。
おそらく重要なのは巡回セールスマン問題を遺伝的アルゴリズムでどのように解くかということより、巡回セールスマン問題はどのように応用されるのかという点ですので、以下で応用例を挙げます。
- スクールバスの経路作成
- 運送会社や宅配業者のルート決定
- たくさんの目的地をめぐる旅行のルート決定
いずれもある地点からある地点に一人、あるいは複数人で順番に回る必要があり、移動距離が少ない方がうれしい問題となります。
なお通常は巡回するのが一人の問題が多いですが、複数人で回るための問題を解くためのソルバーも存在します。当ブログでは過去に複数人での巡回セールスマン問題をGoogleのOR-Toolsで解いてみました。よろしければご覧ください。
●OR-ToolsでVehicle Routing Problem(VRP)を解く
瓶パッキング問題
当ブログでは過去に瓶パッキング問題を扱いました。瓶パッキング問題も組み合わせ最適化問題の一つです。
これらの問題の大元になっている問題は以下のようになります。
次のような植物を置く棚を作ることを考えます。
突き出した部分に植物を置き、上の段の陰になる部分には園芸用品などを置きます。
これをすべて1×4材長さ182cmを使って作るとします。
必要な部品は以下となりました。
① 20cm×2
② 40cm×2
③ 60cm×2
④ 80cm×2
⑤ 94cm×2
⑥ 60cm×12
これを1×4材を効率的に使って、最小の使用量で切り出したいとき、どうやってそれを求めるか。
というのが最適化問題となります。
上の問題の最適解はSPF材の総本数8本、利用した部材の合計消費量1320cmとなります。
エボリューショナリーで解く方法は次の記事をご覧ください。
局所解が複数存在する問題の大域解の探索
遺伝的アルゴリズムの活用例として大域解の探索も重要な点です。最急降下法などの勾配法でも、複数の初期値から探索を始めれば大域解を求めることができます。
●ソルバーをVBAで繰り返す【初期値を変えて複数解を自動探索】
●エクセルソルバーで複数解を求める方法【初期値を変えるしかないです】
しかしながら、ランダムに初期点を配置するにしてもどのくらいメッシュを粗くするのかという問題が残ります。
谷が30個も存在するような目的関数の場合、初期点のバラマキ度合いが粗すぎる、例えば3つ程度でスタートすると大域解の谷に初期点が来る確率が下がってしまいます。
そういうときも遺伝的アルゴリズムならある程度柔軟に大域解を求めることができるので、最初の初期点のバラマキのメッシュの粗さを気にする必要が少ないです。
少ないと書いたのは、遺伝的アルゴリズムでも個体数の多さなどによって探索性能が上下するからです。少なすぎる個体数では精度が出ませんし、多すぎると求解に時間がかかりすぎます。
最適化のベンチマーク問題で有名なAckley functionをエクセルソルバーのエボリューショナリーとGRG非線形のランダムスタートで解いてみて結果を比較してみます。
Ackley functionは以下となります。
}\)
2変数の場合のグラフは次のようになります。
多くの山と谷がある多峰性関数となります。
エクセルの設定は次のようにします。
- B2：-10
- C2：10
- D2：=20-20*EXP(-0.2*SQRT(0.5*(B2*B2+C2*C2)))+EXP(1)-EXP(0.5*(COS(2*PI()*B2)+COS(2*PI()*C2)))
ソルバーの設定は次のようにします。
今回はGRG非線形で多数の初期点からスタートするのでオプションの設定をします。GRG非線形タブで「マルチスタートを使用する」にチェックを入れます。今回はデフォルトの初期点（母集団のサイズ）100個でやってみます。
解決すると次のようになります。
残念ながら局所解です。
続いてエボリューショナリーで解いてみます。
ほぼ最適解になりました。
このように勾配法などの微分を利用した方法の場合、きちんと大域解を求めようとすると相当数の初期点が必要になることが予想されます。
遺伝的アルゴリズムなら勾配法でたくさんの初期点を配置するよりも比較的簡単に大域解が求まります。これも遺伝的アルゴリズムの利点です。
つまり何が言いたいかというと、中身がよくわからない関数の最適化の場合、遺伝的アルゴリズムを採用すれば、あまり悩まずに大域解が求まるということです。こういう話をブラックボックス関数の最適化と言ったりします。
GRG非線形よりも時間がかかりますが、変数が500とかにならない限り現実的な時間で最適解が求まるので、とりあえず最適化したいなら遺伝的アルゴリズムを利用するというのも一つの手です。
なお当ブログでは連続変数の最適化においてより性能がよいとされているABCアルゴリズムについて概要の解説と簡単なベンチマーク問題での性能試験などをしてみました。ご興味がありましたらご覧ください。
まとめ
今回は遺伝的アルゴリズムの活用例を紹介するという内容のもと、遺伝的アルゴリズムの概要や利点、遺伝的アルゴリズムが得意な組み合わせ最適化問題の解決に関する研究例や例題の解説を行いました。
遺伝的アルゴリズムで何ができるのか、というお悩みが少しでも緩和されましたら幸いです。
組み合わせ最適化問題で力を発揮するアルゴリズムです
Office最新版が常に使えます。楽天なら購入するとポイントも
