九州大学 工学部地球環境工学科
船舶海洋システム工学コース
システム設計工学 （担当：木村）(５) 連続関数の最適化
ランダムサーチ
シミュレーテッドアニーリング（ＳＡ）
滑降シンプレックス法
遺伝的アルゴリズム

場所： 船１講義室
授業の資料等はhttp://sysplan.nams.kyushu-u.ac.jp/gen/index.html

【例：箱の寸法デザイン問題】●商品としてよく売れるような箱の寸法（比率）をデザインする→ 目的ははっきりしているが、これだけではモデル化も評価値の定義もできていない【問題のモデル化と評価の定義】
消費者は、商品に「黄金比」に近い長方形が含まれているものを好む傾向

1 5
黄金比 ＝ 1 :2

Cost   黄金比  (長辺 / 短辺)   面積23面

Cost が最小になるデザインが最もよく売れる

このモデルが現実とかけ離れていては意味がない【最適化】
箱の寸法の比率を X：Y：1 ただし X ＜ １ Y ＜ １ とおく
Cost を最小化する X および Y を求める
この例題の場合はCostの式から解析的に解けるが、例えばデータベースに基づいた計算などが加わると解析的に求められないので、解候補を次々代入して改善するしかない

箱の寸法デザイン問題におけるコスト関数の景観最小値をとるパラメータは2箇所に存在箱の寸法デザイン問題：解答

各辺の比率

１ ： 0.67676 ： 0.54626

このときのコスト： 0.09117

【例：冗長自由度アームのリーチング問題】●各関節の角度をパラメータとして、アーム先端がターゲット座標に一致するパラメータを求める問題。ただし、各関節はリンク同士を±90度以内で繋ぐ制約があるので、なるべく関節の可動角度中央付近の角度にすることが好ましい。
コスト関数＝（アーム先端座標とターゲット座標の偏差の2乗）＋（各関節の可動中央角度からの偏差の2乗）

【例：二重倒立振子制御問題】●台車の位置と速度、および2本の振子（棒）のそれぞれの角度と角速度の計６つの状態量を用いて、2本の棒が倒立した状態で安定して立つように台車を動かすようなコントローラのフィードバックゲインを設計する。ただし台車に作用させる力を制御する。

F  w1 x  w2 x  w31  w41  w5 2  w62
コスト関数＝（10000 － steps） ただし倒れた時点あるいは10000stepで打切り
1 step =0.02 sec

1

2Fx

かなり粗い１０個のパラメータを持つ問題において、各パラメータが0～1の区間の値をとるものとして、各パラメータを 0.1 刻みで全てのパラメータの組合せを評価すると、評価回数は 11 の10 乗、これをおおよそ 10 の10乗で近似しても、 10,000,000,000 回、すなわち（百億回）必要になる。
１回の評価に１秒かかるものとすると、計算には ３１７年 を要する

パラメータの探し方（探索方法）を工夫しなければ答えを見つけることができない

ベンチマーク問題： Rastrigin関数
コスト関数nf ( x1 , x2 ,  xn )  10n   xi  10 cos( 2 xi )
i 1

ただし2



 5.12  xi  5.12

n=２の場合のコスト関数の景観・局所解が多数存在する多峰性関数
・探索域中心（全て０）に最適解が存在し、その周辺に格子状に複数の局所解を持つ。

ベンチマーク問題： Rosenbrock関数
コスト関数

ただし

 2.048  xi  2.048

n=２の場合のコスト関数の景観

極小点＝最小点は１つしか無いが、そこへたどり着くには長くて曲がりくねった谷を辿らねばならない=変数間の依存関係が強いベンチマーク問題： Schwefel関数
コスト関数

nf ( x1 , x2 ,  xn )    xi sin
i 1

 xi

ただし

 512  xi  512

n=２の場合のコスト関数の景観・局所解が多数存在する多峰性関数
・最適解が探索領域の境界付近に存在坂を下っていくだけの勾配法は、多峰性関数には使えない！

勾配法＝勾配を下って極小値を探す方法

多峰性関数に勾配法は使えない！

【解決策】
１．ランダムに動く
２．多点で探す

勾配法＝勾配を下って極小値を探す方法

多峰性関数に勾配法は使えない！

【解決策】
１．ランダムに動く
２．多点で探す【ランダムサーチ・網羅探索による最適化】
モンテカルロ法とも呼ばれる
全数探索と同義な場合と区別する場合がある
・最も単純な方法で、どんな問題に対しても適用可能
・時間さえかければ、理屈の上ではいつかは最適解を発見できる・今まで生成した解候補と評価値を参考にしないので、探索効率は悪い

探索性能の下限としての比較対象
ランダムサーチによる最適化のプロセス：
新しい解候補をランダムに生成

解候補の評価

それまで見つけた最良の解候補よりも高い評価値だった場合、最良解候補を置き換える

【焼きなまし法(simulated annealing)による最適化】
統計物理学からのアナロジー：
・物質の分子結晶はいろいろな状態を遷移
・エネルギーの低い状態へ遷移しやすい傾向
・温度を下げるとエネルギー極小状態へ到達
・温度を一気に下げると局所的極小状態へ・温度をゆっくり下げると大域的極小状態へ→ 解候補「状態」「エネルギー」 → 評価値

エネルギー最小状態＝最適解とした最適化のプロセスシステムがある状態 xi になっている確率
自由エネルギー

exp( f ( xi ) T )P( xi | T )  exp( f ( x) T )xS

ギブス分布（ボルツマン分布）
Tは温度パラメータ

f (x )

状態空間x

エネルギーの低い状態ほど確率が高い

特徴：
１）時間をかければかけるほど解候補が改善され、十分時間をかければ最適解の発見が保障される
２）連続関数最適化，および組合せ問題最適化の両方に適用できる

【焼きなまし法(simulated annealing)による最適化】
処理手順

１） 初期解候補 x を生成
２） 何らかの確率分布によって解候補 x から次の解候補 x ' を生成（ランダムに x の近傍を選ぶことが多い）
３） 次の確率に従って乱数Zを生成：
ただしZは0または1の値をとる
ただし温度関数４）

T (t ) P( Z  1) kln(t  2)1
 f ( x' )  f ( x) 1  exp
T (t )
Z  1 のとき x を x' に置換える、

５）時刻 t を1進めて２）から繰返す

これでは収束が遅すぎて非実用的
k/t の関数にすることもある

「近傍」の解候補の生成方法
１） 数値最適化問題の場合： 解候補 x は連続値パラメータなので、中心値 x , 分散 2 の正規分布によって生成： x '  N ( x,  2 )分散のパラメータは設計者が問題に応じて適当に与える時間とともに小さくしていく場合もある

x' x２） 組合せ最適化の場合：
まず解候補の「近傍」を定義する必要がある→ 問題毎に個別に設定： 実行可能な表現になるよう工夫を要する
例１） ＴＳＰ
順列中の都市を入れ替える
順列中の部分順列を移動するなどＡＢＣＤＥＦ → ＡＥＣＤＢＦＡＢＣＤＥＦ → ＡＣＤＥＢＦ

例２） ＳＡＴ
論理変数の論理を反転させる

１０１１１０１ → １００１１０１

【参考】大腸菌の走性2～3秒間の直線的運動と、0.1秒ほどのランダムな方向転換の繰り返し

化学的濃度が低い（要するにエサが少ない）場合には活発に動き回り、濃度の高い領域ではあまり動かないようにすることでエサのある場所へ集まる

焼きなまし法によく似た探索をしている

勾配法＝勾配を下って極小値を探す方法

多峰性関数に勾配法は使えない！

ランダムサーチ【解決策】
１．ランダムに動く
２．多点で探すＳＡ勾配法＝勾配を下って極小値を探す方法

多峰性関数に勾配法は使えない！

【解決策】
１．ランダムに動く
２．多点で探す

滑降シンプレックス法

【制約のない関数最適化】 滑降シンプレックス法
関数の勾配を計算せず、多点探索で最小値を得る
N次元変数関数に対してN+1コ以上のシンプレックス（探索点） x j について以下を定義
1) 目的関数値が最大の点 xh← 関数最小化なので、最悪の点
2) 目的関数値が2番目に大きい点 xs3) 目的関数値が最小の点 xl← 関数最小化なので、最良点
4) i = h なる点を除いた全ての x j の重心 x g

xh を以下の xr で置き換える：
xr  (1   ) x g  xh ，ただし   0 は反射係数(操作2：拡大) x g  xr 方向に沿って xr を以下の xe に置き換える：  0 は拡大係数，ただしxe  xr  (1   ) x g(操作3：縮小) xh を以下の xc で置き換える：
xc   xh  (1   ) x g ，ただし 0    1 は縮小係数(操作4：収縮) シンプレックス全体を xl の方向へ半分に縮小する，ただし i  1,  n  1xi  0.5( xl  xi )(操作1：反射)

これらの操作を、次に述べる手順で組合せ，シンプレックスを更新する。
基本的に，最悪点をシンプレックス重心の逆側へ移動して関数値を小さくしていく。
  1,   0.5,   2 が経験的に良い

滑降シンプレックス法の動作

最悪点

xh

〔スタート〕・シンプレックスを構成する探索点の中で、評価の最悪点、２番目に悪い点、最良点
シンプレックス重心座標を求める

xl

最良点

2番目に悪い点xg

xs

最悪点を除いた
全シンプレックスの重心

滑降シンプレックス法の動作〔まずは反射操作〕

最悪点

xh

xl

最良点

2番目に悪い点xg

xs〔反射〕

xr

滑降シンプレックス法の動作

最悪点

xh

xg
2番目に悪い点〔反射の結果が最良点より良ければ、拡大操作〕

xl

最良点

xs
xr
xe 〔拡大〕滑降シンプレックス法の動作

最悪点xh

・拡大の結果が反射の結果より悪ければ、最悪点を反射点と置き換えて最初へ

xg
2番目に悪い点・拡大の結果が反射の結果より良ければ、最悪点を拡大点と置き換えて最初へ

xl

最良点

xs
xr
xe 〔拡大〕滑降シンプレックス法の動作

最悪点

xhxc

〔縮小〕

xg
2番目に悪い点〔反射の結果が最悪点より悪ければ、縮小操作〕

xl

最良点

xs
xr
xe

滑降シンプレックス法の動作

最悪点

xh
xc

・さもなければ〔収縮〕操作
新たに生成したシンプレックス〔縮小〕 の関数値を評価して最初へ

xg
2番目に悪い点・縮小の結果が最悪点より良ければ、最悪点を縮小点と置き換えて最初へ

xl

最良点

xs
xr
xe

滑降シンプレックス法の動作

最悪点

xh

〔収縮〕

2番目に悪い点

xl

最良点

xs

シンプレックス全体を最良点の方向へ移動 （最良点は動かない）

滑降シンプレックス法の動作

最悪点

xh

〔反射の結果が最悪点よりましだが２番目に悪い点より悪い
場合、最悪点を反射点に置換えて縮小操作〕

〔縮小〕

xl

xg
2番目に悪い点

xs

最良点

xc
xr
xe

滑降シンプレックス法の動作

最悪点

xh

・縮小の結果が最悪点より良ければ、最悪点を縮小点と置き換えて最初へ

・さもなければ〔収縮〕操作
新たに生成したシンプレックス〔縮小〕 の関数値を評価して最初へ

xl

xg
2番目に悪い点

xs

最良点

xc
xr
xe

滑降シンプレックス法の動作

最悪点〔反射の結果が２番目に悪い点よりましだが最良点ほどではない場合、最悪点を反射点に置き換えて最初へもどる〕

xh

xl

最良点

2番目に悪い点

xg

xs
〔反射〕

xr

勾配法＝勾配を下って極小値を探す方法

多峰性関数に勾配法は使えない！

【解決策】
１．ランダムに動く → ランダムサーチ・ＳＡ
２．多点で探す→ 滑降シンプレックス法

両方の特徴を併せ持つ最適化手法：遺伝的アルゴリズム

【遺伝的アルゴリズム（ＧＡ）による最適化】
生物の進化の仕組みを模倣
生物個体 →
優れた個体 →

Mating遺伝子によるコード化
高い評価値・生存率【一般的な処理手順】
１）設計したい物をパラメータ化 → 遺伝子２）いろいろな個体を集めて集団を作り、個体を評価に応じて自然淘汰
３）生き残った個体同士で遺伝子を交換 → 新しい個体生成
４）世代交代を繰り返し、集団を進化【探索の特徴】
・評価値の悪い個体でも生き残るチャンスが与えられる・優れた親同士を掛け合わせる
ことで、両親の優れた形質を受け継いだ子個体が生成される・集団全体が進化していく

たった１つの解候補を改善していくよりも、より優れた解や多様な評価を持つ複数の解を発見できる

【遺伝的アルゴリズムによる最適化】
実数値 GA （RGA: Real-coded GA）
連続関数最適化問題における解候補の「形質」 ＝ パラメータ空間中の座標
解候補の類似性 ＝ パラメータ空間でのユークリッド距離
２つの親個体から、「交叉」オペレーションにより形質を継承した子個体を生成する → パラメータ空間でユークリッド幾何学的に考える
例） 正規分布交叉：ＵＮＤＸ
X2

親１と親2を結ぶ主軸パラメータ空間
親２
親１

多次元正規分布子X1【遺伝的アルゴリズムによる最適化】
実数値 GA （RGA: Real-coded GA）
連続関数最適化問題における解候補の「形質」 ＝ パラメータ空間中の座標
解候補の類似性 ＝ パラメータ空間でのユークリッド距離２つの親個体から、「交叉」オペレーションにより形質を継承した子個体を生成する → パラメータ空間でユークリッド幾何学的に考える
例） 正規分布交叉：ＵＮＤＸ
X2

親１と親2を結ぶ主軸パラメータ空間
親２
親１

多次元正規分布子X1

多親交叉ＲＥＸ ［小林２００７］

対象とするコスト関数の次元数 ｎ交叉によって生成する子個体数 ｎ＋ｋp1nk

子個体の座標

親x1

親x2

x c  x g    i xi  x gi 1

親個体の重心の座標xgp2
親x0p0i2

期待値０，分散  の任意の確率分布に従う確率変数
ただし12 ｋ＝０．５ｎ～２．０ｎ を推奨

nk多親交叉ＲＥＸ ［小林２００７］



確率変数 i が一様分布に従う場合
ただし区間 ［－a, a］ で一様で、確率変数i が正規分布に従う場合
ただし期待値０，3aとする。
nk1
分散   nk2
（このとき分散 1nk2となる）

実数値 GA の交叉オペレータにおいて求められる性質
X2 パラメータ空間

親個体群

ＵＮＤＸもＳＰＸもＲＥＸもこの条件を満たしている
X1
交叉オペレータ適用後
X2 パラメータ空間

機能分担仮説（山村９８）
交叉オペレータは親個体群が張る部分空間の補間的探索に徹して、探索領域の絞込みは世代交代モデルに委ねるのが望ましい

子個体群

X1

実数値 GA の交叉オペレータにおいて求められる性質
X2 パラメータ空間親個体群

子個体群分布の統計量が親個体群の分布と同じになることが望ましい
ＵＮＤＸもＳＰＸもＲＥＸもこの条件を満たしている

X1
交叉オペレータ適用後
X2 パラメータ空間

機能分担仮説（山村９８）
交叉オペレータは親個体群が張る部分空間の補間的探索に徹して、探索領域の絞込みは世代交代モデルに委ねるのが望ましい

子個体群

X1

世代交代モデルMGG [佐藤 97]

個体集団
集団からランダムに2個体を選択し、何らかの交叉オペレーションによって子個体をnc個生成、両親と生成された全ての子を合わせた個体集合から、１つは最良個体、もう１つは評価値のランクに基づくルーレット選択により選び、両親個体と入れ替える

多親世代交代モデルＪＧＧ ［小林２００７］

ランダムに非復元抽出

np個

交叉ランキング
エリート選択np個np個親個体群
子個体を生成したら親を捨てる
子個体群
１０ｎ個を推奨
ただしｎは次元数

個体集団
親個体群と入れ替える

集団サイズは１５ｎ～５０ｎ 個を推奨
ただしｎは次元数

ＭＧＧと比較すると 2.5～13倍の性能アップ

数値最適化を行う遺伝的アルゴリズム：まとめ交叉方法： 正規分布交叉（ＵＮＤＸ）
世代交代： ＭＧＧ

レンズ系設計の最適化
プロペラ形状の最適化
船形最適化など多数の実績

しかし今後はアルゴリズムがずっと簡単かつ強力な交叉方法： 多親交叉ＲＥＸ （一様分布使用）
世代交代： 多親世代交代モデルＪＧＧを使用すべし

さらに洗練された究極の遺伝的手法とは？ … 大学院の講義にて説明

遺伝的アルゴリズム（ＧＡ）の適用における注意点●数値最適化問題において適用を試みる前に、勾配法やシンプレックス法で解けないか？
●組合せ最適化問題に適用を試みる前に、動的計画法（ＤＰ）で解ける問題ではないか？
有効なヒューリスティクスが存在しないか？
単純な問題においては遺伝的手法は非効率的●数値最適化と組合せ最適化の複合問題→ 遺伝的アルゴリズムは有望な選択肢●多目的最適化問題→ 遺伝的アルゴリズムは有効

参考文献
１）長尾 智晴： 最適化アルゴリズム，昭晃堂（２０００）．
２）W.H.Press, B.P.Flannery, S.A.Teukolsky and W.T.Vetterling:
ニューメリカルレシピ・イン・シー Ｃ言語による数値計算のレシピ，技術評論社（１９９３）．
３）小野 功，佐藤 浩，小林 重信：
単峰性正規分布交叉ＵＮＤＸを用いた実数値ＧＡによる関数最適化，
人工知能学会誌 Vol.14, No.6, pp.1146—1155 (1999)．
４）小林重信：実数値GAのフロンティア,
人工知能学会誌Vol.24, No.1, pp.147--162 (2009)

まとめ・多峰性コスト関数 →局所解が多数存在 勾配法×【勾配を利用しない探索アルゴリズム】－－－－－－－－－

・ランダムサーチ →オールマイティ 探索性能下限・焼きなまし法（ＳＡ） →ランダム探索
多峰性関数に有効・滑降シンプレックス法 →多点探索
・遺伝的アルゴリズム →多点探索＋ランダム探索
正規分布交叉，ＲＥＸ，ＭＧＧ，ＪＧＧ

【演習問題】

2018.12.23

学籍番号

氏名

（１） 実数値ＧＡにおける「形質」とは何か説明せよ。
またそれら解候補の「類似性」について説明せよ。

（２） 実数値ＧＡにおける交叉オペレータに求められる性質について説明せよ。