連続な多次元変数の最適化：滑降シンプレックス法
ここで説明するのはNelderらのDown-hill simplex methodです。
線形計画法の「シンプレックス法」ではありませんので念のため。
ポリトープ法（polytop method）とも呼ばれるらしいですが、よく分かりません。
遺伝的アルゴリズム（Genetic Algorithms: GA）は、その枠組みのシンプルさと
特に高次元の多次元変数を持つ最適化問題における探索性能の高さ、
多目的最適化問題への対応など、実問題の要求に答えることができる最適化手法として
広く認知されています。特に連続パラメータをビット列の遺伝子に直さずにそのまま用いる
Real-coded GA (RGA) はかなり強力な手法として多くの実問題に用いられています。
小生は東工大制御工学科を92年に卒業し、卒論のテーマとして「ＧＡを用いた連続関数の最適化」
に取り組みましたが、当時はニューラルネットやファジーがブームで、
ＧＡは全く知られていなかったため、卒論発表のテ−マを聞いた先生方の中には
「ガー（GA）って何だ？」と真顔で尋ねる方もおられたものです。
その卒論では、遺伝的手法（ＧＡ）が従来の最適化手法より優れている点や
得意とする問題領域を見つけることが至上命題で、
ＧＡの対抗手法として、滑降シンプレックス法を用いたのですが、
最適化するパラメータ数が４〜６個くらいの例題で実験してみると
ＧＡはシンプレックス法に全く歯が立たなくて往生しました。
今では、ちょっとした最適化にもＧＡを用いて解いている研究発表をよく目にしますが、
パラメータ数が高々５〜６個程度の最適化でしたら、
ＧＡよりも滑降シンプレックス法のほうが絶対におすすめです。
パラメータ数がこれ以上だとしても、コスト関数の景観がよほど複雑な多峰性になっていて
局所解だらけだということでもない限りは、まず滑降シンプレックス法を試すべきです。
以下に滑降シンプレックス法の詳細について説明した資料を挙げます：
講義に用いた資料のPDFファイル simplex.pdf
PowerPointによる解説（PDFファイル） SimplexPPT.pdf
PowerPointによる解説ページ （上の解説PDFファイルと同じ内容をブラウザで見れます）
滑降シンプレックス法のJavaプログラム
最適化を行おうとする研究者やエンジニアには様々な方がおられますので、
使用する言語もいろいろです。
情報工学や制御工学等ではCやC++言語が標準的ですが、
当部門（船舶海洋システム工学部門）のように流体や構造を専門にする場合はFortranを標準的に使用しておりますし、
アプリケーションソフトの開発現場ではマイクロソフト社のVB／VBAだったりします。
ネットワークプログラムを組む場合は、Java言語がよく使われます。
Javaは携帯アプリなどにも使用されています。
ここでは滑降シンプレックス法のJavaプログラムを公開しますが、
目的関数（コスト関数）のプログラムは使う人がそれぞれに組む必要があります。
どんな言語でも使えるようにするため、滑降シンプレックス法のプログラムと
目的関数（コスト関数）のプログラムをそれぞれ独立した別々のプロセスとして（ただし同一のフォルダ内で）
走らせて、ファイルシステムを介してデータのやりとりを行うような仕様としました。
これにより、例えば流体抵抗の計算プログラムがFortranで書かれていても、
ファイル入出力によってJavaプログラムと通信を行って最適化が行えるようになります。
さらにファイルシステムにNFS（network file system: Windowsでは外部から読み書きできる共有フォルダ）
を利用すれば、探索アルゴリズムの走る計算機とパラメータのコスト関数を計算する計算機を
別々にすることも可能です。
滑降シンプレックス法のJavaソースプログラムとコンパイル済みクラスファイル
本プログラムの著作権は作者が所有しますが、プログラムの改変などは自由です。
本プログラムを使用したことによって生じたいかなる損害に対しても著作権保有者は責任を負いません。
各自の責任のもとで実行してください。
プログラムのバグなど発見された場合は、ぜひお知らせください。
- 滑降シンプレックス法のJavaソースファイルとクラスファイル DownHillSimplexAlgorithmUsingFileSystem.zip
- コスト計算プログラムのサンプルのJavaソースファイルとクラスファイル
- 【サンプル１】ローゼンブロック関数問題（ＧＡの定番ベンチマーク問題） ObjectiveFunctionSampleProgram.zip
単純なコンソールアプリケーションになっていますので、目的に応じて改造等が簡単にできると思います。
下のグラフのローゼンブロック関数のパラメータは２次元ですが、サンプルプログラムは４次元です。
- 【サンプル２】冗長自由度アームのリーチング問題 ObjectiveFuncMultiLinkArm.zip (2014.11.01更新 Javaの最新バージョンで動かない不具合修正）
こちらもJavaプログラムですがWindowアプリになっていて、プログラムは複雑ですが探索の様子を視覚的に観察できます。
各関節の角度をパラメータとして、アーム先端がターゲット座標に一致するパラメータを探索してください。
ただし、各関節はリンク同士を±90度以内で繋ぐ制約があるので、なるべく関節の可動角度中央付近の角度にするのが好ましいという問題です。
アームの先端がターゲット座標に近く、かつ各関節の可動中央角度からの偏差の２乗合計が小さいほど
コスト関数が小さくなります。
関節の個数は起動時の引数で指定できます。
空色の円で示されるターゲット座標はマウスで移動させることができます。
圧縮ファイルを解凍すると、パラメータ探索プログラム群・パラメータのコスト計算プログラム群がそれぞれのフォルダに入った状態で出てきますが、
実行するためにはこれらのファイル群を同一のフォルダに入れてやる必要があります。
以下、個別に説明します。
滑降シンプレックス法Javaプログラムの使い方
上記の DownHillSimplexAlgorithmUsingFileSystem.zip
をダウンロードして展開すると、以下のファイル群が出てきます：
- DownHillSimplexMethod.class
- DownHillSimplexMethod.java
- FitnessFuncByFile.class
- FitnessFuncByFile.java
- FitnessFunction.class
- FitnessFunction.java
- FunctionOptimization.class ← 実行するプログラム本体
- FunctionOptimization.java
- SMPINDV.class
- DownHillSimplexMethod.html ← プログラムの使い方について
- simplex.pdf ← シンプレックス法についての説明資料
- feature.gif ← プログラム間の通信仕様についての図
実行するには JDK1.4以降のJava実行環境が必要です。
本プログラムは version 1.5.0_06 にて動作を確認しています。
この滑降シンプレックス法プログラムを実行する前に、
同じ作業フォルダ中でコスト計算プログラムを起動しておく必要があります。
この滑降シンプレックス法プログラムを起動するには、
コマンドプロンプト上（通称DOS窓）において
CDコマンドでプログラムの存在するフォルダまで移動した後、後で説明する config.txt があることを確認して、
以下のコマンドを実行します：
> java FunctionOptimization 1000
ここで引数 1000 は、探索を行う回数（コスト関数の評価回数）の上限を与えます。
値を大きくするといつまでも探索を続けます。
また、引数としてシンプレックスの個数を指示することも可能です：
> java FunctionOptimization 1000 8
上記の例では、探索回数 1000 回、シンプレックス 8個を指示することになります。
シンプレックスの個数の指示を省略したり、シンプレックスの個数が（パラメータ次元数＋１）より
小さかったりすると、自動的に（パラメータ次元数＋１）に設定されます。
コスト計算のサンプルプログラムの使い方
【サンプル１】
ローゼンブロック関数問題 ObjectiveFunctionSampleProgram.zip をダウンロードして展開すると、
以下のファイルが出てきます：
- Rosenbrock.class ← 実行するプログラム本体
- Rosenbrock.java
実行するには JDK1.4以降のJava実行環境が必要です。
本プログラムは version 1.5.0_06 にて動作を確認しています。
このコスト計算プログラムを実行するには、コマンドプロンプト上（通称DOS窓）において
CDコマンドによりプログラムの存在するフォルダまで移動した後、
以下のコマンドを実行します：
> java Rosenbrock
このプログラムは、実行時に自動的に config.txt ファイルを生成してパラメータ次元数を指示しますので、
滑降シンプレックス法プログラムを実行する前に走らせておきます。
また、滑降シンプレックス法プログラムが走っているのと同じフォルダへコピーして実行する必要があります。
【サンプル２】
冗長自由度アームのリーチング問題 ObjectiveFuncMultiLinkArm.zip (2014.11.01更新 Javaの最新バージョンで動かない不具合修正）をダウンロードして展開すると、
コスト計算プログラムとシンプレックス法による探索プログラムがセットで入っています。
それぞれ自動実行バッチファイルがありますので、これらを適宜実行するだけで動きます。
詳細は圧縮ファイル中のドキュメントを参照してください。
滑降シンプレックス法プログラムとコスト計算プログラムを別々のプロセスで走らせるには？
WindowsXPのパソコンであれば、DOS窓を２つ開いて、CDコマンドで同じそれぞれ同じフォルダへ移動して
片方で滑降シンプレックス法プログラムを実行し、もう片方でコスト計算プログラムを実行します。
デスクトップはこんな感じになります
WindowsXPのデスクトップ上でコマンドプロンプト（ＤＯＳ窓）を２つ開いた状態
Windowsの共有フォルダを使えば、滑降シンプレックス法プログラムとコスト計算プログラムを別々のパソコン上で
実行できるかと思ったのですが、困ったことにコマンドプロンプトは自分とは別のパソコンに実体のある共有フォルダ
へCD （change directory）できないようです。
UNIX等でNFS (network file system) を使っている場合は別々のマシン上でうまく通信してくれます。
滑降シンプレックス法プログラムの通信仕様
Java以外の言語でコスト計算プログラム作る場合、
以下のようなファイルのやりとりによって計算するように作る必要があります。
【初期設定】
・まず、解くべき問題のパラメータ数と、パラメータの定義域について指示するため、
config.txt ファイルにそれらを書き込んでおきます。
・シンプレックス法プログラムは config.txt ファイルを読み込んで初期設定を行います。
【最適化のための通信】
・初期設定が終了したら、以下のやりとりを繰り返します：
- シンプレックス法プログラムは、コスト計算プログラムに計算すべきパラメータの値を渡すため、
param.txt ファイルへパラメータの値を書き込みます
- シンプレックス法プログラムは、コスト計算プログラムに param.txt ファイルが用意できたことを
通知するために flag.txt ファイルを生成します。
- コスト計算プログラムは、flag.txt ファイルが生成されるまで待ちます。
- コスト計算プログラムは、flag.txt ファイルが生成されたことを確認したら
param.txt ファイルを開いてパラメータの値を読み込み、コストを計算します。
- コスト計算プログラムは、計算結果を result.txt へ書き込みます。
- コスト計算プログラムは、計算終了をシンプレックス法プログラムへ通知するために
flag.txt ファイルを消去します。
- シンプレックス法プログラムは、flag.txt ファイルが消去されるまで待ちます。
- シンプレックス法プログラムは、flag.txt ファイルの消滅を確認したら、
result.txt を読み込みます。
以上の処理を所定の回数繰り返して最適化を行います。
所定の回数を繰り返したら、シンプレックス法プログラムは、
コスト計算プログラムに計算終了を通知するため end.txt ファイルを生成して処理を終了します。
【config.txt ファイルの仕様】
解くべき問題のパラメータ数と、パラメータの定義域について指示します。
（ただし、この定義域は、初期解の生成のみに使用しています。探索中にこの領域外へ出ることがあります。）
先頭行において、文字列「NumOfParameters」と空白文字に続いて、パラメータの個数を書きます。
２行目以降は文字列「ParamRangeMin」と空白文字に続いてパラメータの定義域の下界の数値、
さらに空白文字に続いて文字列「ParamRangeMax」と空白文字に続いてパラメータの定義域の上界の数値を書きます。
この行はパラメータの個数分なければなりません。
（４次元のパラメータの最適化を指示するための config.txt ファイルの例）
NumOfParameters 4
ParamRangeMin -5 ParamRangeMax 5
ParamRangeMin -5 ParamRangeMax 5
ParamRangeMin -5 ParamRangeMax 5
ParamRangeMin -5 ParamRangeMax 5
【param.txt ファイルの仕様】
param.txt にはパラメータの数値がスペースで区切られて書き込まれます。
（４次元のパラメータを表すための param.txt ファイルの例）
1.1 1.2 0.4 0.3
【result.txt ファイルの仕様】
result.txt には、cost という文字列に続いて評価値の数値を書き込みます。
小さい値ほど良い評価であるものとします。
（result.txtファイルの例）
cost 20
【flag.txt および end.txt ファイルの仕様】
これらはファイルの有無だけが問題なので、
ファイルの中身は空です。
最近のWindowsXPを積んだパソコンは、複数のプロセスを走らせることが簡単なので、
このような方法はエレガントではありませんが簡単でなかなか便利です。
本プログラムの代わりに、
共役勾配法のプログラム(Java) や
実数値ＧＡ（JGG+REX）のプログラム(Java)
などを同じように走らせれば、全くプログラムの変更をせずに別の手法で最適化できます。
ご意見・お問い合わせ等は以下のURLにメールアドレス等がありますので、
そちらからお願いします：
http://sysplan.nams.kyushu-u.ac.jp/gen/index.html