連続な多次元変数の最適化：共役勾配法

制約のない多次元関数の最適化手法として代表的なのが共役勾配法です。
ラインサーチ（直線探索）と勾配情報を利用した方向転換を繰り返す勾配法の一種です。
対象とする関数がn変数の2次形式の場合、ラインサーチをn回実行することで極値へ到達できます。
勾配法なので、対象とする関数が多峰性（局所解が多数存在する）の場合は大域的最適解への到達は困難です。

以下に共役勾配法の詳細について説明した資料を挙げます：
共役勾配法のスライド
共役勾配法で使用されているラインサーチ（黄金比分割法）のスライド
上記２種類の説明を１つのPDFファイルにまとめた資料

共役勾配法のJavaプログラム

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

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

共役勾配法のJavaソースプログラムとコンパイル済みクラスファイル

本プログラムは 静岡理工科大学総合情報学部菅沼研究室のホームページ に公開されていた システムエンジニアの基礎知識 のページの 共役勾配法のプログラム例にあったJavaプログラムを利用させていただきました。 目的関数（コスト関数）のプログラムを独立させ、それらとファイルのやりとりで最適化するよう変更を加えています。
本プログラムを使用したことによって生じたいかなる損害に対しても責任を負いません。
各自の責任のもとで実行してください。
プログラムのバグなど発見された場合は、ぜひお知らせください。
  1. 共役勾配法のJavaソースファイルとクラスファイル ConjugateAlgorithmUsingFileSystem.zip
  2. 【コスト計算プログラムサンプル１】ローゼンブロック関数問題（定番ベンチマーク問題）
    Javaソースファイルとクラスファイル（シンプレックス法のプログラムで使用しているものと同一です）
    ObjectiveFunctionSampleProgram.zip
    下のグラフのローゼンブロック関数のパラメータは２次元ですが、サンプルプログラムは４次元です。
    ２次元ローゼンブロック関数
  3. 【コスト計算プログラムサンプル２】冗長自由度アームのリーチング問題 ObjectiveFuncMultiLinkArm.zip （2014.11.01更新 Javaの最新バージョンで動かない不具合修正 ）
    こちらもJavaプログラムですがWindowアプリになっていて、プログラムは複雑ですが探索の様子を視覚的に観察できます。
    探索初期 局所解 最適解
    各関節の角度をパラメータとして、アーム先端がターゲット座標に一致するパラメータを探索してください。
    ただし、各関節はリンク同士を±90度以内で繋ぐ制約があるので、なるべく関節の可動角度中央付近の角度にするのが好ましいという問題です。
    アームの先端がターゲット座標に近く、かつ各関節の可動中央角度からの偏差の２乗合計が小さいほど コスト関数が小さくなります。
    関節の個数は起動時の引数で指定できます。 空色の円で示されるターゲット座標はマウスで移動させることができます。
    このサンプルには最適化アルゴリズム（共役勾配法）も一緒に入っています。

共役勾配法Javaプログラムの使い方

上記の　 ConjugateAlgorithmUsingFileSystem.zip をダウンロードして展開すると、おおよそ以下のファイル群が出てきます：
  1. Conjugate.class
  2. Conjugate.java
  3. FitnessFuncByFile.class
  4. FitnessFuncByFile.java
  5. FitnessFunction.class
  6. FitnessFunction.java
  7. FunctionOptimization.class　　　　　←　実行するプログラム本体
  8. FunctionOptimization.java
  9. Kansu.class
  10. Kansu.java
  11. MT19937.class　　　　　　　　　　　　　乱数のクラス
  12. MT19937.java 　　　　　　　　　　　　　
  13. DownHillSimplexMethod.html 　　　　　←　プログラムの使い方について
  14. feature.gif　　　　　　　　　　　　　←　プログラム間の通信仕様についての図
実行するには JDK1.4以降のJava実行環境が必要です。 本プログラムは version 1.5.0_06 にて動作を確認しています。
共役勾配法プログラムを実行するには、コマンドプロンプト上（通称DOS窓）において CDコマンドによりプログラムの存在するフォルダまで移動した後、後で説明する config.txt があることを確認して、 以下のコマンドを実行します：

> java FunctionOptimization 1000

ここで引数 1000 は、探索を行う回数（コスト関数の評価回数）の上限を与えます。
値を大きくするといつまでも探索を続けます。
また、引数としてラインサーチにおける探索回数の最大回数を指示することも可能です（省略時100回）：

> java FunctionOptimization 1000 200

上記の例では、探索回数 1000 回、ラインサーチにおける探索回数 200回 を指示することになります。
さらに、ラインサーチの収束判定条件としての精度（省略時0.000001）と、 微分を差分近似したりラインサーチを開始するときのきざみ幅（省略時0.0001）を指示することも可能です。

> java FunctionOptimization 1000 200 0.00001 0.0001

上記の例では、探索回数 1000 回、ラインサーチにおける探索回数 200回、 ラインサーチの収束判定条件の精度 0.000001、きざみ幅 0.0001 を指示しています。
なお、微分を差分近似するきざみ幅は、上記きざみ幅の1/10で固定されます。
対象とする関数によっては問題が生じる可能性があります（特に悪スケール問題など）。 詳しくはソースコードを見てください。

コスト計算のサンプルプログラムの使い方

【サンプル１】
ローゼンブロック関数問題（シンプレックス法のプログラムで使用しているものと同一です）
上記の ObjectiveFunctionSampleProgram.zip をダウンロードして展開すると、以下のファイルが出てきます：

  1. Rosenbrock.class　　←　実行するプログラム本体
  2. 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) を使っている場合は別々のマシン上でうまく通信してくれます。
あるいは、ファイルの場所を指示するときに共有フォルダを指示すれば可能です。

共役勾配法プログラムの通信仕様

滑降シンプレックス法やJGG+REXのプログラムと全く同様です。
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を積んだパソコンは、複数のプロセスを走らせることが簡単なので、 このような方法はエレガントではありませんが簡単でなかなか便利です。
共役勾配法のプログラムの代わりに、 滑降シンプレックス法のプログラム(Java) や 実数値ＧＡ（JGG+REX）のプログラム(Java) などを同じように走らせれば、全くプログラムの変更をせずに別の手法で最適化できます。

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