[PR]当サイトはアフィリエイト広告を利用しています。
今回はエクセルのソルバーで複数解を求める方法の解説です。
基本的にエクセルのソルバーは一つの解が求まったら探索が終了するので、複数解を一度に出力することはできません。
エクセルのソルバーで複数解を求めるには初期点をいくつか試して、それぞれの初期点からソルバーを利用することになります。
今回はエクセルのソルバーで複数解を求めるという話題について原理的な側面から解説していきます。
なお今回紹介するGRG非線形ソルバーを使った複数解の探索は手動で初期値を設定しますが、VBAでソルバーを繰り返し実行して複数解を自動取得する方法も考えました。手法の詳細は以下で扱っています。
エクセルソルバーで複数解を求めるとき内部で何をやっているか
まずエクセルソルバーが探索を止めて最適解を出力するというのはどういうときなのか、という点からお話しします。
ソルバーの停止条件の原理
エクセルソルバーに搭載された最適化ソルバーは3つです。
- シンプレックスLP
- GRG非線形
- エボリューショナリー
このうち複数解を求めるのと相性が良いのがGRG非線形です。
エクセルの最適化ソルバーの種類と特徴は以下をご覧ください。
GRG非線形という最適化ソルバーは探索に目的関数を微分した値を使います。高校数学で一階の微分というのをやりますよね。出題された関数を一回だけ微分した関数に値を入れてみて、正ならその区間で関数値は増大しますし、負なら減少します。
この原理を最適化ソルバーは利用します。つまり目的関数の最小化なら微分した値が負なら変数の順方向、つまり0よりは1、1よりは5といった方向に進めば目的関数は減少していきます。微分した値が正なら逆方向、つまり5よりは1、1よりは０という方向に進めば関数は減少していきます。
そして微分した値がゼロになれば、とりあえずそれ以上関数値は減少しない「底」に到達します。
微分を利用した最適化ソルバーはこの底に到達すれば停止して、そこを最適解として出力します。
このときこの底は局所解と呼ばれます。それに対してあらゆる底の中で、最大あるいは最小となる場所を大域解と呼びます。局所解は局所的最適解、大域解を大域的最適解とも呼びます。目的関数が本当に最小になる真の最適解は大域解です。
GRG非線形は「勾配法」と呼ばれる手法の一つです。勾配、つまり微分した値を利用して探索を行います。
勾配法の基本は最急降下法です。もし勾配法の基礎と流れが知りたいときは以下の記事もご覧ください。
複数解があるということは複数の局所解があるということ
最小化の場合、局所解はそれ以上どの方向に進んでも関数は小さくなりません。しかしこれは大域解であるという証明にはなりません。
単純に局所解ではその周りではそれ以上値が小さくならないというだけで、局所解が複数存在する場合があるからです。
局所解が複数あった場合、初期点の選択によって、到達する局所解が異なります。
ある局所解の近くに初期点があれば最適化ソルバーはその局所解に向かって進んでいきますし、別の局所解の近くに初期点があればそちらに向かって進んでいきます。
最適化ソルバーは現在の点から関数が減少するような方向に進んでいるだけなのです。
本当に大域解を求めるならすべての局所解を割り出して、その中の最小となる局所解を大域解にする必要があります。
複数の最適解を求めるというのは、複数の局所解を求めるということと同義です。
そしてこの話で述べたように、複数の局所解を求めるためには、それぞれの局所解の近くに初期点を配置して、それぞれの初期点で最適化ソルバーで探索する必要がある、ということがわかると思います。
エボリューショナリーはいきなり大域解を求めることができるが複数解は苦手
エボリューショナリーは遺伝的アルゴリズムっぽい最適化ソルバーです。遺伝的アルゴリズムについては以下の記事でまとめました。
遺伝的アルゴリズムでは目的関数の値が良いか悪いかだけで次の探索点を決めていくので、基本的に微分を使って探索する手法とは原理が異なります。
微分を使っていないので、大域解をいきなり見つけるということもありますが、探索点が局所解周りに集中してしまうと、局所解に収束してしまうということもあり得ます。これを突然変異という手法で回避しているわけです。
エボリューショナリーで局所解を複数求めるときには、探索点を局所解に狙って収束させる必要があり、探索空間全体をランダム的に探索する遺伝的アルゴリズムでそれをやるのはかなり難しいです。
これがエボリューショナリーが複数解を求めるのと相性が悪い理由となります。
シンプレックスLPは複数解の求解は難しい
シンプレックスLPは線形計画法のソルバーです。
線形計画法ではシンプレックス法が使われます。シンプレックス法ではシンプレックス表という表を用いて機械的に解を更新していきます。
そしてこのシンプレックス表は制約条件や目的関数の係数で構成されています。
つまり何が言いたいかというと、シンプレックス表は初期点に依存しない解法なのです。
つまり初期点をいじって複数の解を求めるというのが難しくなります。
エクセルソルバーで複数解を求めてみる
ここからは複数解を求めることと相性が良いGRG非線形で、複数の最適解を求めてみます。
簡単な例題で複数解を求めてみましょう。
- 目的関数：\(y=\cos x\) →最小化
- 制約条件：\(0 \leq x \leq 4 \pi\)
- 変数：\(x\)
ただのコサインカーブです。
しかしこの最小値は\(x = \pi\)と\(x = 3 \pi\)のときで二つあります。
これをGRG非線形で初期点を変えることで両方求めてみましょう。
エクセルに次のように入力します。
各セルの値は次のようにします。
- B3：120
- C3：=COS(B3*PI()/180)
変数はラジアンだと面倒なので角度で指定します。180度で\(\pi\)とします。
ソルバーの設定は次のようにします。
解決すると次のようになります。
続いて初期点を変えて次のように入力します。
各セルの値は次のようにします。
- B3：500
- C3：=COS(B3*PI()/180)
初期点を500度にします。
先ほどと同じソルバーの設定で解決すると次のようになります。
ちゃんと複数の最適解が求まりました。
まとめ【複数解の出力はできないことはないが難しい】
上の例題はこの辺りに最適解があるというのがわかっていたから、その近辺に初期点を配置することで最適解が求められていました。
しかし一般に局所解がどこにあるかは未知なので、どこに初期点を配置すればよいのかというのも未知です。つまり変数空間にランダムにたくさんの初期点のパターンを作成して、その一つ一つでソルバーを回す必要があります。
根気がいる作業となりますので、大域解が一つ求まればよいならエボリューショナリーを使うとか、変数を固定して、その固定値ごとの最適解で問題が解決しないかどうかとか、そうした検討ができないか考えたほうが無難です。
複数解は求められる場合もありますが、成功率は低いです
当ブログ（シルルスのコードおきば）ではエクセルソルバー関係の記事を他にも執筆しています。参考になりましたら幸いです。
Office最新版が常に使えます。楽天なら購入するとポイントも
●ソルバーをVBAで繰り返す【初期値を変えて複数解を自動探索】
●エクセルソルバーと組み合わせ最適化問題【解法例と基礎知識】
