連続な多次元変数の最適化：滑降シンプレックス法

遺伝的アルゴリズム（Genetic Algorithms: GA）は、その枠組みのシンプルさと 特に高次元の多次元変数を持つ最適化問題における探索性能の高さ、 多目的最適化問題への対応など、実問題の要求に答えることができる最適化手法として 広く認知されています。特に連続パラメータをビット列の遺伝子に直さずにそのまま用いる Real-coded GA (RGA) はかなり強力な手法として多くの実問題に用いられています。
小生は東工大制御工学科を92年に卒業し、卒論のテーマとして「ＧＡを用いた連続関数の最適化」 に取り組みましたが、当時はニューラルネットやファジーがブームで、 ＧＡは全く知られていなかったため、卒論発表のテ−マを聞いた先生方の中には 「ガー（GA）って何だ？」と真顔で尋ねる方もおられたものです。 その卒論では、遺伝的手法（ＧＡ）が従来の最適化手法より優れている点や 得意とする問題領域を見つけることが至上命題で、 ＧＡの対抗手法として、滑降シンプレックス法を用いたのですが、 最適化するパラメータ数が４〜６個くらいの例題で実験してみると ＧＡはシンプレックス法に全く歯が立たなくて往生しました。

今では、ちょっとした最適化にもＧＡを用いて解いている研究発表をよく目にしますが、 パラメータ数が高々５〜６個程度の最適化でしたら、 ＧＡよりも滑降シンプレックス法のほうが絶対におすすめです。 パラメータ数がこれ以上だとしても、コスト関数の景観がよほど複雑な多峰性になっていて 局所解だらけだということでもない限りは、まず滑降シンプレックス法を試すべきです。

以下に滑降シンプレックス法の詳細について説明した資料を挙げます：
PDFファイル simplex.pdf

滑降シンプレックス法のJavaプログラム

最適化を行おうとする研究者やエンジニアには様々な方がおられますので、 使用する言語もいろいろです。 情報工学や制御工学等ではCやC++言語が標準的ですが、 当部門（船舶海洋システム工学部門）のように流体や構造を専門にする場合はFortranを標準的に使用しておりますし、 アプリケーションソフトの開発現場ではマイクロソフト社のVB／VBAだったりします。 ネットワークプログラムを組む場合は、Java言語がよく使われます。 Javaは携帯アプリなどにも使用されています。

ここでは滑降シンプレックス法のJavaプログラムを公開しますが、 目的関数（コスト関数）のプログラムは使う人がそれぞれに組む必要があります。 どんな言語でも使えるようにするため、滑降シンプレックス法のプログラムと 目的関数（コスト関数）のプログラムをそれぞれ独立した別々のプロセスとして 走らせて、ファイルシステムを介してデータのやりとりを行うような仕様としました。
これにより、例えば流体抵抗の計算プログラムがFortranで書かれていても、 ファイル入出力によってJavaプログラムと通信を行って最適化が行えるようになります。 さらにファイルシステムにNFS（network file system: Windowsでは外部から読み書きできる共有フォルダ） を利用すれば、探索アルゴリズムの走る計算機とパラメータのコスト関数を計算する計算機を 別々にすることも可能です。

滑降シンプレックス法のJavaソースプログラムとコンパイル済みクラスファイル

本プログラムの著作権は作者が所有しますが、プログラムの改変などは自由です。
本プログラムを使用したことによって生じたいかなる損害に対しても著作権保有者は責任を負いません。
各自の責任のもとで実行してください。
プログラムのバグなど発見された場合は、ぜひお知らせください。
  1. 滑降シンプレックス法のJavaソースファイルとクラスファイル DownHillSimplexAlgorithmUsingFileSystem.zip
  2. コスト計算プログラムのサンプルのJavaソースファイルとクラスファイル ObjectiveFunctionSampleProgram.zip

滑降シンプレックス法Javaプログラムの使い方

上記の　 DownHillSimplexAlgorithmUsingFileSystem.zip をダウンロードして展開すると、以下のファイル群が出てきます：
  1. DownHillSimplexMethod.class
  2. DownHillSimplexMethod.java
  3. FitnessFuncByFile.class
  4. FitnessFuncByFile.java
  5. FitnessFunction.class
  6. FitnessFunction.java
  7. FunctionOptimization.class　　　　　←　実行するプログラム本体
  8. FunctionOptimization.java
  9. SMPINDV.class
  10. DownHillSimplexMethod.html 　　　　　←　プログラムの使い方について
  11. simplex.pdf　　　　　　　　　　　　　←　シンプレックス法についての説明資料
  12. 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 をダウンロードして展開すると、以下のファイルが出てきます：
  1. Rosenbrock.class　　←　実行するプログラム本体
  2. Rosenbrock.java
実行するには JDK1.4以降のJava実行環境が必要です。 本プログラムは version 1.5.0_06 にて動作を確認しています。
このコスト計算プログラムを実行するには、コマンドプロンプト上（通称DOS窓）において CDコマンドによりプログラムの存在するフォルダまで移動した後、 以下のコマンドを実行します：

> java Rosenbrock

このプログラムは、実行時に自動的に config.txt ファイルを生成してパラメータ次元数を指示してきますので、 滑降シンプレックス法プログラムを実行する前に走らせておきます。
また、滑降シンプレックス法プログラムが走っているのと同じフォルダへコピーして実行する必要があります。

滑降シンプレックス法プログラムとコスト計算プログラムを別々のプロセスで走らせるには？

WindowsXPのパソコンであれば、DOS窓を２つ開いて、CDコマンドで同じそれぞれ同じフォルダへ移動して 片方で滑降シンプレックス法プログラムを実行し、もう片方でコスト計算プログラムを実行します。
デスクトップはこんな感じになります
WindowsXPのデスクトップ上でコマンドプロンプト（ＤＯＳ窓）を２つ開いた状態

Windowsの共有フォルダを使えば、滑降シンプレックス法プログラムとコスト計算プログラムを別々のパソコン上で 実行できるかと思ったのですが、困ったことにコマンドプロンプトは自分とは別のパソコンに実体のある共有フォルダ へCD （change directory）できないようです。 UNIX等でNFS (network file system) を使っている場合は別々のマシン上でうまく通信してくれます。

滑降シンプレックス法プログラムの通信仕様

Java以外の言語でコスト計算プログラム作る場合、 以下のようなファイルのやりとりによって計算するように作る必要があります。
滑降シンプレックス法プログラムの通信仕様
【初期設定】
・まず、解くべき問題のパラメータ数と、パラメータの定義域について指示するため、 config.txt ファイルにそれらを書き込んでおきます。
・シンプレックス法プログラムは config.txt ファイルを読み込んで初期設定を行います。
【最適化のための通信】
・初期設定が終了したら、以下のやりとりを繰り返します：
  1. シンプレックス法プログラムは、コスト計算プログラムに計算すべきパラメータの値を渡すため、 param.txt ファイルへパラメータの値を書き込みます
  2. シンプレックス法プログラムは、コスト計算プログラムに param.txt ファイルが用意できたことを 通知するために flag.txt ファイルを生成します。
  3. コスト計算プログラムは、flag.txt ファイルが生成されるまで待ちます。
  4. コスト計算プログラムは、flag.txt ファイルが生成されたことを確認したら param.txt ファイルを開いてパラメータの値を読み込み、コストを計算します。
  5. コスト計算プログラムは、計算結果を result.txt へ書き込みます。
  6. コスト計算プログラムは、計算終了をシンプレックス法プログラムへ通知するために flag.txt ファイルを消去します。
  7. シンプレックス法プログラムは、flag.txt ファイルが消去されるまで待ちます。
  8. シンプレックス法プログラムは、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を積んだパソコンは、複数のプロセスを走らせることが簡単なので、 このような方法はエレガントではありませんが簡単でなかなか便利です。

ご意見・お問い合わせ等は以下のURLにメールアドレス等がありますので、 そちらからお願いします：
http://sysplan.nams.kyushu-u.ac.jp/gen/index.html
九州大学　大学院工学研究院 海洋システム工学部門 木村 元