講演スライドPDFファイル

講義内容
１．最適化問題とは
最適化問題 は
第14回計測自動制御学会九州支部講義会
２．近似解法とは
１）局所探索 ２）GA (Genetic Algorithms)
１）局所探索，
進化計算技術のフロンテ ア
進化計算技術のフロンティア
３．巡回セールスマン問題における近似解法の性能比較
４ 関数最適化への接近
４．関数最適化への接近
１）勾配法， ２）実数値GA (Real-coded Genetic Algorithms)
平成21年11月27日
５．実数値GA
実数値
によるイ
によるインスタンスベース政策の最適化
タ
ベ
政策の最適化
６．多目的関数最適化への接近
東京 業大学 小林重信
東京工業大学
１）世代交代モデル ２）ポートフォリオ最適化への適用
７．多目的最適化の最近の展開
１）GA then LS， ２）多峰性多目的関数最適化への接近
1
2
最適化問題と解の定義
最適化問題のクラス
min f ( x) subj.
subj to x ∈ F
目的関数
x
f： 目的関数 (objective function)
F: 実行可能領域 （feasible region）
x ∈ F ⇒ 実行可能解,
実行可能解 x ∉ F ⇒ 実行不可能解
N ( x) ⊂ F： x の近傍
„ f ( x* ) ≤ f ( x ) for ∀x ∈ N ( x* ) が成り立つとき，x*は N に対して
局所最適解（locallyy optimal
p
solution）であるという
„ f ( x* ) ≤ f ( x ) for ∀x ∈ F が成り立つとき，x*は最適解（optimal
solution）または大域的最適解（globally optimal solution）であ
るという
3
最適化問題
スカラー
スカラ
ベクトル
クトル
離散的
組み合わせ最適化
多目的
組み合わせ最適化
連続的
関数最適化
多目的
関数最適化
変数
„組み合わせ最適化（Combinatorial
組み合わせ最適化（Combinatorial Optimization）
„関数最適化（Function Optimization）
„多目的最適化（Multi-objective Optimization）
4
組み合わせ最適化問題の例
関数最適化問題の例
配送経路問題
Vehicle Routing Problem
レンズ設計問題
Lens Design Problem
各顧客に対する配送／集荷の時間的制約を充足する条件の
下に，できるだけ少ない台数のトラックを配置して，各トラック
の受け持ち地域を決め，それぞれの最短経路を求めよ
– 設計仕様：焦点距離f，明るさF，画角2w
– 設計変数：曲率，面間距離
– 評価関数：解像度＋歪曲
評価関数 解像度＋歪曲
配送先／集荷先
トラックのルート
物流センター
トリプレット型
テッサー型
エルノスター型
5
近似解法による接近
多目的最適化問題の例
ポ ト ォリオ選択問題
ポートフォリオ選択問題
Portfolio Selection problem (PSP)
ポートフォリオとは，
金融資産を分散投資する
ことで収益を確保しつつ，
リスクを回避すること
厳密解法で現実的時間内に最適解が求まる問題は限られる
厳密解法で現実的時間内
最適解 求まる問題は限られる
⇒ 現実的時間内でできるだけ良質な解を得たい
⇒ 近似解法への期待
解法
期待
„局所探索 (Local Search)
株式
１つの解の近傍を探索して改善解を発見する
の解の近傍を探索して改善解を発見する ⇒ 単点探索
„遺伝アルゴリズム (Genetic Algorithms)
– 収益(リターン)最大化
– 収益の標準偏差(リスク)最小化
2目的最適化問題
6
複数の解の近傍を探索して改善解を発見する ⇒ 多点探索
※遺伝アルゴリズムは，局所最適解を乗り越えることが期待で
※遺伝アルゴリズムは
局所最適解を乗り越えることが期待で
きるので，大域的探索を行う上で有利と考えられている
7
8
局所探索 Local
oca Search
Sea c
局所探索における近傍設計の指針
„解 x の近傍 N(x) を探索して f ( x′) < f ( x ) なる改善解 x′ が見
つかれば
れば x から x′ に移動して，改善解が見つからなくなるま
移動
改善解が
なくな ま
で反復する．山登り法（Hill Climbing）ともいう
〔指針１〕 近傍の大きさ
近傍 N(x) は大きいほうが望ましい
⇒ 局所最適解の数を減らすことができる
„一般に， N(x) には解 x の改善解が複数存在する．
改善解の選択はどうすべきか → 移動戦略
⇒ 十分時間をかければ良質な解を得ることが期待できる
„移動戦略 (move strategy)
1. first match method
最初に見 か た改善解に移動する
最初に見つかった改善解に移動する
2. best selection method
N( )内の解 をすべて調べて，最良改善解に移動する
N(x)内の解
をすべて調べて 最良改善解に移動する
〔指針２〕 解の改善確率
近傍 N(x) は現在の解 x に対して高い確率で改善解の
候補を含む とが望まし
候補を含むことが望ましい
⇒ 目的関数を効率良く改善することができる
〔指針１〕と〔指針２〕は，一般に，トレードオフの関係にある
⇒ このことを考慮して，近傍を設計する必要
„局所探索を成功させるためには，近傍 N(x) の設計が重要
9
k-opt近傍：
p 近傍 巡回
巡回セールスマン問題(TSP)
問題(
)
における代表的な近傍
10
設計指針から見たk opt近傍
設計指針から見たk-opt近傍
k-opt近傍 現在の巡回路から任意の k 本の枝(edge)を取り除き，
新たに k 本の枝を付け加える
„ k-opt近傍の大きさ
N
C k ×2k −1 × ( k − 1)!
⇒ 〔設計指針1〕の観点では，k は大きいほど望ましい
※ kがN（Nは都市数）のとき，局所探索は網羅探索となり，
局所最適解は大域的最適解となる
2-opt近傍
„ k-opt近傍の改善確率
局所探索が進むにつれて 巡回路を構成する枝は短いもの
局所探索が進むにつれて，巡回路を構成する枝は短いもの
が多くなるので， k 本の枝の置き換えで改善解を得ることは
次第に難しくなることが予想される
⇒ 〔設計指針２〕の観点では，k は小さいほど望ましい
3-opt近傍
11
12
局所探索の一般的手順
所探
般
順
LK近傍
k opt近傍における k の値を可変とするように拡張したものを
k-opt近傍における
Lin-Kernighan近傍（LK近傍）という
„LK近傍はsequential exchange制約及びpositive gain制約の下
で枝の交換について深さ優先探索（depth first search）を行うこ
とで，探索範囲を有望な領域に限定した効率的な探索を実現し
，
領
限定
効
実
ている
„LK近傍は局所探索におけるTSPの近傍としてはもっとも強力
な近傍として知られる
13
Exploitation
p
vs Exploration
p
procedure [局所探索]
1 適当な方法で実行可能解
適
xc を生成;
成 xb := xc;
2 while （終了条件が満たされない）
3
while （受理しない
（受理 な or N(xc) ≠ 0）
）
4
x∈ N(xc) をランダムに選択; N(xc) := N(xc)＼{x};
5
x の受理または棄却を決定;
の受理または棄却を決定 探査戦略によって異なる
探査戦略によ
異なる
6
if x を受理 then xc := x;
7
end
d while
hil
8
if f(xc) < f(xb) then xb := xc;
9
終了条件の判定
終了条件の判定;
10 end while
11 return
t
xb;
14
end procedure
局所探索 おける探査戦略
局所探索における探査戦略
„ Multi-Start Local Search
初期探索点を変えながら，局所探索を何度も繰り返す
Exploitation： 現在のベスト解の周辺に探索を重点化する戦略
Exploration： より良い解を探すために探索領域を拡げる戦略
局所探索の基本形はexploitationに徹した探索重点化戦略
„ Iterated Local Search
局所探索で得られた解に摂動を加え，それを初期探索点として
局所探索を行う操作を繰り返す
大域的探索を実現するためには， exploitationとexplorationの
適切なト
適切なトレードオフを考慮する必要
ドオ を考慮する必要
„ Simulated Annealing
局所探索の過程で 改悪解への移動も許容して 局所最適解か
局所探索の過程で，改悪解への移動も許容して，局所最適解か
らの脱却を図る
„ Tabu search
探索履歴を保持することにより，循環現象を回避する
ex ジョブショップスケジュ
ex.
ジョブショップスケジューリングでは良好な性能
リングでは良好な性能
局所探索における探査戦略の重要性
15
16
rat575における性能比較
GA （Genetic Algorithms）の概念図
探査戦略
近傍
平均
最良
Local Search
pos. 2-opt
7192.7(6.19%)
6992(3.23%)
0.03
〃
seq. 3-opt
6941.3(2.84%)
6835(0.92%)
0.3
〃
seq 4-opt
seq.
6884 9(1 65%)
6884.9(1.65%)
6788(0 22%)
6788(0.22%)
06
0.6
〃
seq. 5-opt
6857.4(1.25%)
6786(0.19%)
1.7
〃
seq. 6-opt
6841.8(1.02%)
6784(0.16%)
5.4
〃
seq. 7-opt
6828.7(0.82%)
6777(0.06%)
22.3
〃
seq. 8-opt
6821.0(0.71%)
6775(0.03%)
83.4
〃
LK
6879.2(1.57%)
6790(0.25%)
0.1
Iterated Local Search
LK
6778.2(0.08%)
6773(0.00%)
45.8
2 opt
2-opt
6956 5(2 71%)
6956.5(2.71%)
6888(1 70%)
6888(1.70%)
864 1
864.1
Simulated Annealing
時間(sec)
※LSは10,000試行平均，Iterated LSは30試行平均，SAは100試行平均
※Iterated LSは局所最適解をnon-sequential 4-optを用いて遷移させた後，
4-optを用いて遷移させた後
LSを再スタートする
17
GA の設計項目
第 t 世代集団
複製選択
×
×
子個体生成
適応度評価
×
第 t+1 世代集団
×
×
×
生存選択
„自然選択（人為選択）にヒントを得た最適化手法
自然選択（ 為選択）
を得 最適化手法
„集団の多様性を生かして大域的最適化を図る
18
世代交代モデル
MGG (Minimal Generation Gap) [佐藤 97]
×
„世代交代モデル
世代交代 デル
① 複製選択（reproduction），② 生存選択（survival selection）
„子の生成
子
成
① コード化（coding），② 交叉（crossover）
19
„複製選択：ランダム非復元抽出
„生存選択：家族内で最良個体とル レットで選ばれた
„生存選択：家族内で最良個体とルーレットで選ばれた
１個体を次世代に残す
従来モデルに比 て，多様性維持に優れる
„従来モデルに比べて，多様性維持に優れる
20
交叉の設計指針
交叉の設計指針
〔指針１〕
対象問題の適切な形質を親から子へ継承すること
解候補
〔指針２〕
形質を継承する割合と交叉で生成可能な解集合の大きさの
適切なトレードオフを実現すること
最適解
„TSPでは最適解の枝の存在と評価値に高い相関がある
21
順回セールスマン問題の交叉EAX
EAXの手順（１）：親Aと親Bの重ね合わせ
22
EAXの手順（２）：AB-cycle集合への分解
の手順（ ）
y 集合 の分解
EAXの手順（1）：２重グラフの生成
親Bのツアー
親Bのツア
親Aのツアー
親Aのツア
親Aと親Bの２重グラフ
23
„２重グラフはAB-cycleの集合に分解できる
24
EAXの手順（３）：AB-cycleの適用
y
EAXの手順（４）：2-optによる修正
p
2 tの適用
2-optの適用
親Bのツアー
AB-cycleの適用
生成子個体
成子個体
（緩和個体）
緩和個体
完全個体
„緩和個体は，2-optの適用により完全子個体に修正できる
p
„AB-cycleの適用はk-optに他ならない
„2-optの適用による新しい枝の挿入は，探索序盤から中盤では解の
改善をもたらす確率が高い．しかし，探索終盤では改悪になる確率が
高まる
„AB-cycleの適用により複数のサブツアーが形成されることがある
⇒ 修正操作が必要
25
rat575における性能比較
最良
EAX が成功した理由
探査戦略
近傍
Genetic Algorithms
EAX
6774.9(0.03%)
6773(0.00%)
54.0
〃
EX-2opt
6776.2(0.05%)
6774(0.01%)
5088.0
〃
EXX
6804 0(0 46%)
6804.0(0.46%)
6787(0 46%)
6787(0.46%)
12573 0
12573.0
Local Search
seq. 5-opt
6857.4(1.25%)
6786(0.19%)
1.7
〃
seq. 6-opt
6841.8(1.02%)
6784(0.16%)
5.4
〃
seq. 7-opt
6828.7(0.82%)
6777(0.06%)
22.3
〃
seq. 8-opt
6821.0(0.71%)
6775(0.03%)
83.4
〃
LK
6879.2(1.57%)
6790(0.25%)
0.1
Simulated Annealing
2-opt
6956.5(2.71%)
6888(1.70%)
864.1
LK
6778 2(0 08%)
6778.2(0.08%)
6773(0 00%)
6773(0.00%)
45 8
45.8
Iterated Local Search
平均
時間(sec)
„エ ジが形質という性質を巧みに利用している
„エッジが形質という性質を巧みに利用している
„AB-cycleの適用は近傍をペアに限定したk-optに他ならない
„サブツアーをひとつにする修正操作は2-opt適用に他ならない
⇒ 多くの場合ツアー長を短くする
„交叉による生成子個体の数が十分確保され、
しかも解の改善率がきわめて高い
„エッジを継承する割合と生成可能な解集合の大きさの間に
適切なトレードオフ
⇒ EAXは設計指針を充足している
„GAは30試行平均，LSは10,000試行平均，SAは100試行平均，
Iterated LSは30試行平均
„GA(EAX)の最適解発見率は3/30，Iterated LS(LK)は1/30
26
27
28
関数最適化とは
関数最適化手法の分類
„ 局所探索(Local Search）
„関数最適化問題
„ 目的関数の単峰性(unimodality)を仮定
„ 勾配法(Gradient Method)
ex. 最急降下法，Newton-Raphson法，共役勾配法
„ 直接探索法(Direct Search Method)
ex. 共役方向法，シンプレックス法
x ∈ X ⊂ Rn
m in f ( x ),
x
„ パラメータが連続的な値を取る最適化問題
„ 科学技術
科学技術・産業応用の現場では普遍的問題クラス
産業 用 現場
普
問題クラ
„ 高次元の関数最適化問題に対するニーズは大
„関数最適化問題の特徴
„ 大域的探索(Global
的探索
Search）
„ 変数間依存性 (epistasis)
„ 悪スケール性
悪スケ ル性 (ill-scaledness)
(ill
l d
)
„ 多峰性 (multi-modality)
„ 制約条件の充足（constraints satisfaction）
„ 目的関数の多峰性(multimodality)を仮定
„ Multi-start Local Search
„ 実数値GA (Real-coded GA)
29
30
降下法（勾配法）の 般的手順
降下法（勾配法）の一般的手順
降下法（勾配法） の原理
〔手順１〕 降下方向の決定
− ∇f ( x ) d > 0
k
k
目的関数の値を改善する降下方向を決める
のとき d k を x k における
のとき，
x2
降下方向，降下方向に次
の探索点 x k +1 を選ぶ方法
−∇f ( x A )
降 方向は局所的 解
降下方向は局所的に解
xA
〔手順２〕 ステップ幅の決定
降下方向に沿っての１次元探索（直線探索）を行う
を降下法という
dk
ex. 最急降下方向，共役方向
を改善することを保証する
ex. 黄金分割法，Fibonacci探索
※〔手順１〕と〔手順２〕を交互に繰り返す
x1
31
32
最急降下法 Steepest Descent Method
x2
降下方向の中で勾配が
もっとも急な方向を選択
して直線探索を行い，次
の探索点を求める
xB
−∇f ( x B )
−∇f ( x A )
楕円面関数における最急降下法の挙動
x
x5
3
d1
x∗
x6
x4
x1
xC
xA
楕円面関数では最急降
下法によって生成される
探索点は最適点に向か
う２つの方向ベクトル上
に存在する
x2
ステップ幅が急速に小さ
くなり,最適点への収束
が遅れる （Spiegel
（Spiegel’ss
cage と呼ばれる)
x2
d2
x1
x1
33
34
球面関数に対する最適化
楕円面関数における共役方向
直交方向の逐次探索
最急降下法
x2
x2
x2
xA
xA
d0
d1
xB
xA
d2
x∗
異なる２点 x1 と x 2 か
ら同じ方向 d 1 に直線
探索を行って得られ
る点 x Aと x B を結ぶ方
向 d 2 上に最適点が
存在する
d1
x∗
x∗
d2
x1
xB
d
x1
d 0 = −∇f ( x A )
x1
方向 d 1 と d 2は楕円
面関数に対して共役
の関係にあるという
1
x2
d 1⊥ d 2
x1
35
36
共役方向の生成問題
共役性と直交性の関係
„目的関数が２次形式で陽に与えているとき，共役方向を用
„目的関数が２次形式で陽に与えているとき
共役方向を用
いた探索法は n ステップで最適解に収束する
⇒ ２次収束性（quadratic convergence）という
x
xA
d1
d2
A
„一般に，最適点の近傍は２次形式で近似できる
しかし ２次形式の行列 A は未知である
しかし，
⇒ n 組の共役方向ベクトルをどのように生成すべきか？
d1
x∗
d2
x∗
„共役方向法（ j
„共役方向法（conjugate
direction
di i method）
h d）
変数変換
ex. Powell法
共役方向
直交方向
37
„共役勾配法（conjugate gradient method）
共役方向ベクトルを生成するために勾配ベクトルを利用
ex. Davidon-Fletcher-Powell法
38
Bit String GA [Goldberg 89]
におけるコード化
降下法（勾配法）のまとめ
„目的関数と制約関数の凸性を前提
„最適解近傍が２次形式で近似できる場合 共役
„最適解近傍が２次形式で近似できる場合，共役
方向を利用した局所探索は非常に強力
„多峰性関数に対してはマルチスタ ト以外に有
„多峰性関数に対してはマルチスタート以外に有
効な方法がない
„単峰性関数であっても評価値にノイズが乗って
いるときには脆弱
39
40
Bit String GAにおけるコ
GAにおけるコード化の影響
ド化の影響
実数値GAの設計項目
„コ ド化
„コード化
9 表現型を遺伝子型にどのように写像するか？
9 実数値GAでは，実数値変数ベクトルを直接遺伝子型とする
実数値GAでは 実数値変数ベクトルを直接遺伝子型とする
⇒ 適応度景観を変えない
9 Bit String GAの呪縛からの解放
„ 世代交代モデル
9 どのような基準で、次世代に残す個体を選ぶか？
ど ような基準
次世代 残す個体を選ぶか
9 多峰性への対処が重要
„ 交叉
„バイナリ表現よりグレイ表現の方が優れるが，変数間依存性の
„バイナリ表現よりグレイ表現の方が優れるが
変数間依存性の
ある問題に対応できない
41
実数値交叉の先駆け
9 親個体から子個体をどのようにつくるか？
9 変数間依存性・悪スケール性への対処が重要
42
機能分担仮説と統計量の遺伝
„ BLX-α[Eshelman 93]
9 両親によって定まる各変数の区
間をα倍してつくられる矩形領域
に 様分布 子個体を生成
に一様分布で子個体を生成
9 変数間依存性が強い関数におい
て性能が極端に低下
„ UNDX[小野 99]
9 両親を結ぶ主軸を主探索成分，
両親を結ぶ主軸を主探索成分
主軸に直交する超平面を副探索
成分に正規分布で子個体を生成
9 変数間依存性が強い関数に対し
て比較的良好な収束性能
9 悪スケール問題に対して脆弱
α d2
α d1
親１
機能分担仮説 [山村 98]
親２
d2
d1
世代交代 デルは個体群の分布を徐 に縮小さ
9世代交代モデルは個体群の分布を徐々に縮小さ
せるように設計することが望ましい
9交叉は探索領域の絞込みを世代交代モデルに委
ね，個体群の分布を変化させないように子個体を生
成するよう設計することが望ましい
α d1
α d2
一様分布
実数値GAを対象に操作化
統計量遺伝 [喜多 99]
9交叉により生成される子個体分布は親個体分布
の平均と分散共分散行列を継承する とが望ましい
の平均と分散共分散行列を継承することが望ましい
43
44
実数値GAの世代交代モデル
多親交叉
„ UNDX-m [喜多 00]
9 UNDXの多親拡張．m+2個の親個
体を用いて子個体を生成
9 m=n のとき統計量遺伝を満たす
9 m の推奨値は m=4～5
x1
MGG (Minimal Generation Gap)[佐藤 97]
x2
複製選択 交叉
交叉に用いる親個体数分の個体を集団からランダ
用 る親個体数分 個体を集団から
ダ
ムに非復元抽出し，親個体群とする
xg
x3
生存選択 親個体群から２個体をランダムに非復元抽出し，
子個体群 併 て家族 する 家族の中 ら評価
子個体群と併せて家族とする．家族の中から評価
値最良個体と評価値のランキングに基づくルーレッ
ト選択で 個体を選択し，家族に加えた親 個体と
ト選択で１個体を選択し，家族に加えた親２個体と
交代して，次世代集団に加える
„ SPX [樋口 01]
9 n+1個の親個体が張るシンプレック
スを n + 2 倍拡張して，その中に
倍拡張して その中に
子個体を一様に生成
x1
x3
xg
x2
9 統計量遺伝を満たす
45
MGG の再考
46
世代交代モデルJGG
„妥当と思われる点
JGG (Just Generation Gap)[秋本
秋本 07]
9 複製選択におけるランダム選択
⇒ すべての個体に平等に交叉の機会を与える
複製選択 交叉に用いる親個体数分の個体を集団からラ
ンダムに非復元抽出し，親個体群とする
„疑問と思われる点
生存選択 子個体群から評価値の高い順に親個体数分選
び，親個体群と交代して，次世代集団に加える
9 エリート保存戦略
⇒ 多峰性関数で局所解に陥るリスクを高める
9 ルーレット選択
⇒ 評価値の高い子個体が残りにくい
9 2個体入れ替えモデル
⇒ 多親交叉を考慮していない
„JGGの特徴
9複製選択はMGGに同じ
9親子間での完全な世代交代 ⇒ 集団の多様性維持
9エリート戦略を採用しない ⇒ 多峰性に対する頑健性
9ル レット戦略を採用しない ⇒ 優れた子個体の選択
9ルーレット戦略を採用しない
47
48
JGGとMGGの性能比較
SPXの再考
安定収束する集団サイズと30試行平均評価回数;生成子個体数10n
;
SPX
MGG
20次元
npop
評価回数
npop
評価回数
Sphere
300
8.23×105
300
7.30×104
Rosenbrock
300
1.29×106
1000
5.13×105
Rastrigin
500
2.46×106
500
2.00×105
UNDX n
UNDX-n
„妥当と思われる点
JGG
MGG
9 子個体を
子個体を一様に生成
様に生成
⇒ サンプリングバイアスがない
x3
JGG
npop
評価回数
20次元
npop
評価回数
Sphere
300
9 55×105
9.55×10
300
8 05×104
8.05×10
Rosenbrock
300
1.53×106
1000
4.83×105
Rastrigin
500
2.93×10
2
93×106
500
22.28×10
28×105
x1
xg
x2
„疑問と思われる点
9 分布が重心に対して非対称
⇒ Rosenbrock関数のように，変数間依存性が強い
問題では，谷を踏み外しやすくなる
49
50
REX((φ , n + k ) [小林09]]
UNDX-nn の再考
UNDX
„妥当と思われる点
n+k
xc = x g + ∑ ξ i ( xi − x g )
9 正規分布を用いて子個体を生成
規分布を
個体を生成
⇒統計量遺伝の拘束条件のもとでエントロピーが最大
i =1
„疑問と思われる点
xg ;親
親個体群の重心，
体群
，
9 SPXに比べてサンプリングバイアスが強い
9 主親の選び方により子個体生成分布が変わる
x1
x1
x2
σ ξ2 = 1 /(n + k ) のとき，統計量の遺伝
のとき 統計量の遺伝を満たす
x2
xg
xg
x3
ξ i～φ (0, σ ξ2 )
REX (φ , n + k ) は UNDX − n の自然な拡張
x3
51
52
REX(φ , n + k ) の特徴
REX(U n+1)とREX(N n+1)の子個体生成分布
REX(U,n+1)とREX(N,n+1)の子個体生成分布
SPX
REX(U,n+1)
REX(N,n+1)
分布φ は任意
2
9 φ が平均 0 ，分散がσ ξ の正規分布のとき，
⇒ σ ξ2 = 1 /(n + k )
9 φ が [− a, a ] の一様分布のとき，
⇒ a = 3 /(n + k )
親個体数 n + k は任意
n +1 ≤ n + k ≤ n pop
9
子個体生成分布は重心 x g に対して対称
54
53
多親交叉の性能比較
機能分担仮説と統計量遺伝の再考
„妥当と思われる点
安定収束する集団サイズと30試行平均評価回数；生成子個体数10n
SPX
20次元単峰
Sphere
Ellipsoid
8n,
4.38×104
9n, 6.12×104
UNDX-n
6n,
3.99×104
8n, 5.72×104
REX(N,n+1)
REX(U,n+1)
3.75×104
5n, 3.36×104
6n,
8n, 5.70×104
5n, 4.00×104
1/2n tablet
15n, 1.13×105 10n, 8.46×104 10n, 8.23×104
7n, 6.12×104
Rosenbrock
40n, 4.62×105 20n, 2.58×105 20n, 2.41×105 15n, 1.91×105
20次元多峰
SPX
UNDX-n
REX(N,n+1)
REX(U,n+1)
Bohachevsky
8n, 5.31×104
7n, 5.03×104
6n, 4.50×104
5n, 4.03×104
Ackley
kl
10n, 1.02×105
8n, 9.11×104
8n, 9.07×104
5n, 6.72×104
Schaffer
16n, 3.65×105 15n, 3.82×105 15n, 3.85×105
8n, 2.41×105
Rastrigin
40n, 4.62×105 80n, 8.71×105 40n, 3.90×105 30n, 3.56×105
55
9 個体群の分布を変化させないように子個体を生成する
（機能分担仮説）
9 子個体分布は親個体分布の分散共分散行列を継承する
（統計量遺伝）
„疑問と思われる点
9 集団が最適解をつねに覆っていることを想定
⇒ 個体群の分布を徐々に縮小させる（機能分担仮説）
⇒ 親個体分布の平均を継承する（統計量遺伝）
9 集団が最適解から離れて存在する状況は十分あり得る
関数
度
ex. Rosenbrock関数では集団は一度原点付近に集まる
⇒ 親個体分布の平均を継承することは好ましくない 56
大谷構造下での大域的降下方向の推定
構造
降
向 推
n 次元空間に 点 x1 , K , x n +1 が
大域的降下方向を用いた REX star
n+1
x c = x g + diag (ξ1t ,L, ξ nt )( x b − x g ) + ∑ ξ i ( x i − x g )
g
与えられたとき，その重心を x ，
i =1
点 x i の x g に対する鏡映点を z i
ξ
で表し，鏡映点を含めて，評価
d
値上位の n +1 個の点の重心を
t
j ～
u(0, t ); j = 1,L, n
ξ i ～ u(− 3/ n + 1,
1 3/ n + 1);
1) i = 1,
1 L, n + 1
x b とするとき，
する き，d = x b − x g を大
谷構造下での降下方向と呼ぶ
57
58
REX star とREX (u, n + 1)の性能比較
REX star
REX (u, n + 1))
２０次元関数
npop, nc, neval
npop, nc, neval
rate
Sphere
2n, 2n, 6.89E03
6n, 5n, 2.50E04
28%
Elipsoid
2n, 2n, 8.46E03
6n, 5n, 3.08E04
27%
1/4-tablet
2n, 2n, 1.05E04
7n, 6n, 4.80E05
22%
Rosenbrock(star)
5n, 3n, 5.45E04
15n, 8n, 1.57E05
35%
Rosenbrock(chain) 2n, 3n, 4.72E04
実数値 の強化学習 の応用
実数値GAの強化学習への応用
インスタンスベース政策の最適化
---------
Bohachevsky
4n 2n
4n,
2n, 1.54E04
1 54E04
6n 5n
6n,
5n, 3
3.16E04
16E04
49%
Ackley
2n, 3n, 1.44E04
6n, 6n, 5.54E04
26%
Schaffer
5n, 3n, 7.70E04
9n, 8n, 2.29E05
34%
Rastrigin
20n, 3n, 1.23E05
22n, 8n, 2.20E05
56%
59
60
既存手法SLIP［土谷 06］
政策のインスタンスベース表現と学習
交互に
• インスタンス=(状態，行動)
インスタンス=(状態 行動)
組合せGA
［組合せGA］
［実数値GA］
• 状態 → 状態空間中の位置
インスタンスの
大幅な移動
複製選択
非復元ランダム
ペアリング
複製選択
非復元ランダム
ペアリング
集団
探索序盤で有効
• エージェントは最近接の
インスタンスの行動を選択
交叉
実数値GA
インスタンスベース政策学習
• 1エピソードの獲得総報酬を最
大化するように各インスタンス
の状態と行動を最適化
インスタンスの
緻密な移動
探索終盤で有効
交叉
INDX
＋再初期化
BDX
生存選択
直系内最良個体
家族内計2個体
状態空間
生存選択
家族内
最良2個体
SLIPの枠組み
枠組
61
62
SLIPの問題点
SLIPからFLIPへ[宮前 09]
［実数値GA］
枠組み
枠組みが複雑
が
複製選択
非復元ランダム
ペアリング
– 実数値GAだけを使用
• ハイブリッドGAの枠組みがない
– 相補性を保つことが保証されない
相補性を保
とが保証されな
– 十分に性能を引き出すのが困難
集団
実数値GA
– 探索性能の向上
交叉
REX(N,n+k)
• 子個体生成方法の再構築
実数値GAの精度が低い
– 最適化精度の向上
– 交叉的突然変異INDXの性能が低い
• 高性能な実数値交叉の導入
生存選択
CBFB
FLIPの枠組み
枠組み
63
64
FLIPでの子個体生成
活性インスタンス
• 状態と行動を変更
– 評価値に直接影響を与える
不活性インスタンス
• 行動は変更
FLIPでのインスタンスの変更
主親個体
1. 主親のIBPとは別な副親のIBPを用意
1
2. 主親のインスタンスと
副親のインスタンスをペアリング
3. 実数値交叉により
子個体としてインスタンスを生成
主親
子個体
ペアリングの方法
• 他のIBPで近い位置に存在する
インスタンスは役割も近い
イ
タ
役割も近
⇒最も近いインスタンスをペアリング
– 妥当な行動獲得
• 状態は不変
– 政策を改悪しないため
65
REX(N n+k)[小林 09]による交叉的突然変異
REX(N,n+k)[小林
副親
最近傍
66
FLIPとSLIPの性能比較
実数値交叉REX(N,n+k)による子個体生成
比較項目
¾ 序盤の探索性能
¾ 終盤の最適化精度
REX(N,n+k)
；副親のインスタンス群の重心
；副親のインスタンス
集団サイズ
親個体数
生成子個体数
インスタンス数
交叉的突然変異とするために分布の基点をシフト
；主親のインスタンス
実験パラメ タ
実験パラメータ
67
FLIP SLIP
50
50
10
2
100 100
40
40
68
タスク
猫ひねりでのFLIPとSLIPの性能比較
状態変数の収束曲線
猫ひねり
車両ロボット
宇宙ロボット
69
FLIP
宇宙ロボットの姿勢制御での
FLIPとSLIPの性能比較
FLIP
SLIP
SLIP
車庫入れでのFLIPとSLIPの性能比較
安定化できない
70
71
目標にたどり着けない
72
FLIPのまとめ
ノイズを考慮したIBP最適化[菊池 09]
IBP最適化の枠組みFLIPの提案
– 子個体生成の枠組みを再構築
– 性能の高い実数値交叉を導入
– 組合せ最適化を必要としない
z FLIP における実数値GAの世代交代モデル拡張CCM
¾最良個体は親個体でも生存（エリート保存）
¾最良個体は親個体でも生存（エリ
ト保存）
¾ノイズで高く評価された解が生き残り続けることがある
FLIPの有効性
z 提案手法では世代交代モデルをJGGを採用
– SLIPと比較して優れた性能
– 対象タスクの知識を使わずに高い精度の解
¾親個体は必ず淘汰される
¾ノイズで騙された解を淘汰しやすくなる
今後の課題
z 提案手法では交叉オペレータをREXを採用
– ノイズ環境への対処
– 政策表現の拡張
73
提案手法におけるIBPの表現能力の拡張
z 最近傍インスタンスの判定（従来）：ユークリッド距離
最近傍インスタンスの判定（従来）
クリ ド距離
¾曲線的な分割に多くのインスタンスが必要
z 提案手法：マハラノビス距離を採用
¾インスタンスを超楕円体で表現
曲線的な分割が可能に
（表現能力の増大）
実験設定
z FLIP と提案手法の性能を比較
z 手法設定
提案（１）：GA変更
提案（２）：IBP拡張
提案（
） IBP拡張
¾ FLIP，FLIP（１個体につき５回評価），提案（１）のみ，提案（１）（２）
z 対象タスク（１）：Mountain
象
Car（MtC）問題
¾ 単純な制御タスク
¾ 状態２次元，行動１次元
状態２次元 行動１次元
z 対象タスク（２）：猫ひねり問題
¾ 非ホロノミック系安定化制御問題
非ホロノミ ク系安定化制御問題
¾ 状態３次元，行動２次元
z 対象タスク（３）：倒立振子振上げ安定化問題
対象タスク（３） 倒立振子振上げ安定化問題
z 少ないインスタンス数で複雑な政策が形成可能
z 行列も最適化対象となるため，探索次元は増加
¾ 制御に安定化を要するタスク
¾ 状態４次元，行動１次元
状態４次元 行動１次元
z ノイズ設定：確率0.1で行動値が変化
MtC問題の結果（１） ～評価値比較～
MtC問題の結果（２） ～空間の分割～
FLIP の空間分割
提案手法（１）（２）の空間分割
値は打ち切り後の集団内ベスト評価値，10試行統計
手法
ベスト評価値 平均評価値
FLIP（１回評価）
－132.185
－164.270
FLIP（５回評価）
－132.066
－145.059
提案（１）
－134.359
－136.847
提案（１）（２）
－133.736
－135.378
提案（１）：GA変更
提案（１）
GA変更
提案（２）：IBP拡張
z 集団内のベスト解についてはほとんど差がない
z 提案手法によって集団内の平均評価値が大きく改善
¾ 特に提案手法（１）の影響が大きい
z 提案手法はインスタンス数が少ないにも関わらず、FLIPとほ
ぼ同等の軌道生成に成功している
猫ひねり問題の結果（１）
～評価値比較～
値は打ち切り後の集団内ベスト評価値，10試行統計
手法
ベスト評価値 平均評価値
FLIP（１回評価）
－1004.252 －2119.879
FLIP（５回評価）
－983.461
983.461 －1312.012
1312.012
提案（１）
－911.093 －978.846
提案（１）（２）
－918
918.194
194 －1072
1072.408
408
z 提案手法は曲線的な分割を行っている
猫ひねり問題の結果（２）
～獲得政策の挙動～
z 猫ひねり問題における，各手法の獲得政策による状態
変数の推移を示す
z 各変数の目標値は θ と θsが0.5，
が0 5 θr が 1(=0）
提案（１）：GA変更
提案（２）：IBP拡張
z 提案手法によって性能が明らかに改善
z 猫ひねり問題においては提案手法（１）のみの方がよい
¾ （提案手法（２）は猫ひねり問題では探索次元が膨大になる）
FLIPの獲得政策
（評価値約 2150）
（評価値約－2150）
提案手法（１）（２）の獲得政策
（評価値約 1070）
（評価値約－1070）
猫ひねり問題の結果（３）
～評価回数比較～
FLIP（５回評価）の評価値推移
提案手法（１）（２）の評価値推移
提案手法（
）（ ）の評価値推移
倒立振子振上げ安定化問題の結果（１）
～評価値比較～
値は打ち切り後の集団内ベスト評価値，３試行統計
手法
ベスト評価値 平均評価値
FLIP（１回評価）
68.309
FLIP（５回評価）
144.647
提案（１）
154.096
－25493
提案（１）：GA変更
87.811 提案（２）：IBP拡張
96.010
提案（１）（２）
187 994
187.994
141 820
141.820
z こちらも提案手法によって性能が明らかに改善
z 提案手法（１）（２）はFLIP（５回評価）に比べ収束までに
要する評価回数が若干多い
する評価 数が若 多
倒立振子振上げ安定化問題の結果（２）
～評価回数比較～
FLIP（５回評価）の評価値推移
提案手法（１）（２）の評価値推移
提案手法（
）（ ）の評価値推移
z 提案手法（１）（２）を双方用いた方が結果がよい
IBP政策最適化手法のまとめ
zSLIP [土谷 07]
z政策表現：点とユークリッド距離
z最適化手法：ハイブリッドGA
適
法
ブ ド
zFLIP [宮前 09]
z政策表現：点とユークリッド距離
z最適化手法 実数値GAに基づく交叉的突然変異
z最適化手法：実数値GAに基づく交叉的突然変異
zノイズを考慮したIBP最適化[菊池 09]
z 提案手法（１）（２）はFLIP（５回評価）に比べ収束までに
要する評価回数が少なくなっており、かつ評価値も高い
する評価 数が少なくな
お
評価値も高
z 政策表現：超楕円体とマハラノビス距離
z 最適化手法：REX/JGG
多目的最適化問題
多目的最適化問題の解概念
min
i f ( x) = ( f1 ( x),
) L , f m )T
x
subj. to x ∈ X = {x | ( g1 ( x), L , gl ( x))T ≤ 0}
f2
f2
F
■完全最適解
C
A
B
f2 A
F
B
D
B
x∗ ∈ X がすべての
がすべ
x ∈ X に対して
対し f ( x∗ ) ≤ f ( x) であるとき
あるとき
C
A
■パレート最適解
すべての i ∈ {1, L , m} に対して f i ( x) ≤ fi ( x∗ ) であり，かつ
D
f1
少なくとも１つの i に対して fi ( x) < f i ( x∗ ) となる x ∈ X が
完全最適解
存在しないとき
F
E
f1
パレート最適解
パレ
ト最適解
f1
弱パレート
弱パレ
ト最適解
■弱パレート最適解
x∗ ∈ X に対して f ( x) < f ( x∗ ) となる x ∈ X が存在しないとき
85
多目的関数最適化における降下方向
−∇f1 ( x)
−∇f 2 ( x)
d2
パレ ト最適解と降下方向の関係
パレート最適解と降下方向の関係
−∇f 2 ( x)
d
d3
d1
86
X
x
望遠域における降下方向の例
−∇f1 ( x)
x
広角域における降下方向の例
実行可能領域内の点がパレート最
適のとき 降下方向は存在しない
適のとき，降下方向は存在しない
„広角域から望遠域に近づくにつれて降下方向の幅は狭くなる
87
境界上の点がパレート最適
のとき 降下方向は実行可
のとき，降下方向は実行可
能領域の外を向いている
88
多目的最適化手法
加重和最小化法
„ スカラー化手法
パラメータ付きの単目的最適化問題に変換
⇒ 単目的最適化手法を用いて，パラメータを変えながらパレー
ト最適解を１つずつ求める
ex. 加重和最小化法，最大成分最小化法，ε制約法
〔加重和最小化問題〕
x∈ X
m
f2
X
F
B
X
A
C
wB
w
A
wA
B
f1
f1
凸の場合
89
非凸の場合
90
ε制約法
〔ε 制約問題〕
〔最大成分最小化問題〕
min max {wi fi ( x)}
i
m
where w ∈ W = {w | w ≥ 0, ∑ wi = 1}
i =1
f2
„非凸部分に存在するパレート
最適解を求めることはできない
i =1
f2
最大成分最小化法
x∈ X
i =1
where w ∈ W = {w | w ≥ 0, ∑ wi = 1}
„ 局所探索
降下方向等を用いた局所探索により，初期値を変えながらパ
レート最適解を１つずつ求める
ト最適解を
ず 求める
ex. パレート降下法
„ 多目的GA
集団探索の利点を生かして近似解集合を一度に求める
ex. NSGA-II，SPEAR2
„加重和最小化問題の解は多目
的最適化問題のパレート最適
解である
m
min wT f ( x) = ∑ wi f i ( x)
„最大成分最小化問題の解は
多目的最適化問題の弱パレート
多目的最適化問題の弱パレ
ト
最適解である
„多目的最適化問題のパレート最
適解はある重み w 対する最大
成分最小化問題の解である
„パレート解曲面のギャップ（非凸
解曲面 ギャッ （非凸
部分）に存在するパレート解を
求めることができる
X
min f m ( x)
subj
bj. to
where
f ( x) ≤ ε , x ∈ X
f ( x) = ( f1 ( x), L , f m −1 ( x))T ,
ε = (ε1 , L, ε m −1 )T
f2
ε
91
εC
„多目的最適化問題のパレート最
適解はある εに対するε制約
問題の解である
„パレート解曲面のギャップ（非凸
部分）に存在するパレート解を
部分）
存在する
解を
求めることができる
X
C
w
f1
„ε制約問題の解は多目的最適
化問題のパレート最適解である
化問題のパレ
ト最適解である
x
B A
εB ε A
f1
92
降下方向とパレ ト降下方向
降下方向とパレート降下方向
局所探索法
降下方向，最急降下方向，パレート降下方向など，目的関
降下方向
最急降下方向 パレ ト降下方向など 目的関
数の勾配情報を利用して探索を行う
ex.
RDS: ランダムに生成した降下方向に探索
WSDM: 目的関数の最急降下方向の凸結合に探索
CORL: パレート降下方向あるいは降下方向に探索
レ ト降下方向あるいは降下方向に探索
パレート降下方向： 自身よりも各目的関数を同時により大きく減少させる降
下方向が存在しない降下方向
PDM: パレート降下方向に探索
d1 と d 2 がパレート降下方向のとき，
∇f1 ( x)T d1 < ∇f1 ( x)T d 2 であれば，
であれば ∇f 2 ( x)T d1 > ∇f 2 ( x)T d 2
93
が成り立つ
パレート降下法
94
パレ ト降下法における方向発見
パレート降下法における方向発見
„ 降下方向集合，パレート降下方向集合は凸錐をなす
„ 凸錐内の方向発見問題
– 凸錐に適当な線形制約を追加
• 原点を頂点に持つ凸多面体
– 原点以外の頂点
• 線形計画法で求まる
„ 実行可能な方向発見
実行 能な方向発見
– 境界情報を考慮して実現
„ パレ
パレート降下法の計算コストは小さい
ト降下法の計算コストは小さい
– 線形計画法が主たる計算
95
96
局所探索手法の性能比較
ベンチマーク１
30変数3目的問題： パレート解
集合が目的関数空間で非凸
„ 比較手法
– PDM: パレート降下法
– WSDM: 目的関数の最急降下方向の凸結合に探索
– CORL: パレート降下方向あるいは降下方向に探索
– RDS: ランダムに生成した降下方向に探索
ベンチマーク２
2変数2目的問題： パレート解
が実行可能領域境界上に存在
„ ベンチマーク問題
– 局所パレート解が存在しないもの
局所 レ ト解が存在しないもの
„ 評価方法
– 実行可能領域内に一様にランダムに生成した1000個の初
期点から探索を行ったときの，解集合とパレート解の変数
空間における平均自乗誤差（MSE)
MED2(領域B)
„ 高次元問題でも性能がよい
„ 制約を考慮して探索
→ PDMの有効性を確認
„ パレート解集合が目的空間で非凸でも，解
集合を偏ら な
集合を偏らせない
97
多目的GAの探索のイメ ジ
多目的GAの探索のイメージ
98
ランキングとシェアリング
99
ランキング： 優越関係による
解の順序付け
シェアリング： 混雑度による間引き
100
多目的GAの生存選択モデルNSGA-II
非優越関係による順序付け
Non-dominated Sorting
混雑距離による間引き
Crowding Distance Sorting
F1
F2
Pt
多目的最適化手法の性能評価の尺度
Pt +1
F3
Qt
間引き
Rt
101
多目的GAのポ トフォリオ最適化への適用
多目的GAのポートフォリオ最適化への適用
有効フロンティア
ポートフォリオ選択問題
株式
解集合から見たパレート最適
解集合への近さ
パレート最適解集合から見た
解集合の広がり
102
ポ トフォリオ最適化に対するアプロ チ
ポートフォリオ最適化に対するアプローチ
• OR手法
– リターンをε制約条件化して， QPにより逐次的に求める
• 高精度の解集合を比較的高速に求めることができる
• 線形制約の仮定が必要
z 金融資産をどの割合で持つのがよいか？
－リターン（収益の平均）を最大化したい
－リスク（収益の分散）を最小化したい
• 進化計算手法
zリスクに対する態度
– 有効フロンティアを一度に求める
• 非線形制約・組み合わせ制約に対応できる
• 高速であるが、解集合の精度に難点
－リスク志向型 (risk prone)
リ ク回避型 ((risk aversion))
－リスク回避型
有効フロンティアを求めること
103
意思決定問題
多目的最適化問題
ポ トフォリオ最適化問題の制約条件
ポートフォリオ最適化問題の制約条件
平均・分散モデル[Markowitz 54]
• 銘柄数制約
収益の分散 V(x) を最小，収益の平均 R(x) を最小とする
投資比率
– ポートフォリオへの組み入れ銘柄数をP個に
制限
限
,
を求める２目的最適化問題
• 取引コスト
105
GAにおける制約処理（1/2）
– 銘柄を売買する際に発生
– 取引コスト関数は非線形関数
取引コスト関数
– 通常は区分線形などで近似
– 実数値GAでは陽に扱うので、対処
106
GAにおける制約処理（２/2）
• 銘柄数制約
– 制約なしの有効フロンティア(EF)において，投資比率の大きい要素
• QPによって求めた有効フロンティア(EF)に含まれる銘柄
は，銘柄数制約付きEFでも高頻度で含まれる[土谷
[
07]]
ベンチマーク
構成銘柄
EPに含まれる銘柄
DAX
85銘柄
22銘柄 （25.9%）
Nikkei
225銘柄
14 銘柄 (6.2%)
銘柄数制約
銘柄数制約のための修正オペレータ
修
1. 投資比率上位P個を除いて，0
2. 残ったP個の投資比率が1.0×10-4以下だったら0
3. 変数の和が１となるように正規化
• 多くの銘柄が未使用
• 修正オペレータ
1 変数が1.0
1.
1 0×10-4以下のときは0
２．変数の総和が1となるように正規化
107
108
２目的最適化問題への接近法
目的最適化問題 の接近法
実験１ 制約なしポートフォリオ最適化問題
• パレート解集合は変数空間上で曲線をなす
– 次元数
次元数n, 目的関数の数Mとしたとき ，
パレート解集合は
• 実験の目的
– k-NN限定の効果を確認
– k-NN限定の最適な近傍サイズ
ズ
– 精度の評価 ⇒ QPとの比較
min(n,
i ( M-1)の多様体をなす[Brown03
M 1)の多様体をなす[B
03]
• 近傍を限定した交叉が有効
• 実験の設定
実験 設定
– 複製選択で選ばれる親個体群の選択範囲を
有効フロンティアの例
k-最近傍(k-NN)に限定
– ベンチマーク問題
• Hang Seng(31銘柄), DAX(85銘柄), Nikkei(225銘柄)
– 集団サイズ
• 100 (Hang
(H
S
Seng,
DAX) 200 (Nikkei)
DAX),
(Nikk i)
– 多目的GAの枠組み
109
• 交叉：UNDX，
交叉：UNDX 世代交代モデル：NSGAⅡ
– k-NN限定の近傍サイズ
• k = 5/100, 15/100, 25/100, 100/100（考慮しない）
実験１の結果（1/2）
実験１の結果（2/2）
• 探索終盤の100世代で生成された子個体の全分布
– QPによる解集合をreferenceとして比較
Ｋ-NN近傍パラメータ
Hang Seng
(31銘柄)
DAX
(85銘柄)
Nikkei
(225銘柄)
110
5/100
15/100
25/100
GD
1 42
1.42
1 15
1.15
1 23
1.23
1 50
1.50
D1R
5.72
5.56
5.51
5.63
GD
1.78
1.73
1.80
3.15
D1R
5.86
5.75
5.78
6.65
GD
4.29
2.76
3.81
8.38
D1R
5.07
3.63
4.77
8.47
赤字は最良値
●限定なし/ UNDX
● ｋ－NN/UNDX
● パレ
パレート解集合
ト解集合
100/100
k=5/100
(×10-3)
GD, D1Rの性能が向上 ⇒ k-NN限定の有効性を確認
GD
k NN限定の有効性を確認
近傍サイズを小さくしすぎると性能が悪化
k=15/100
• 近傍サイズが小さ過ぎると局所的な偏りが生じやすい
• 適切なk-NNの近傍サイズは集団サイズの15～20%
適
傍
ズ 集
ズ
111
112
実験2の結果(1/2) ~銘柄の構成 P=2
実験2の結果(2/2) ~銘柄の構成 P=10
• 獲得されたポートフォリオの構成比較
• 獲得されたポートフォリオの構成比較
– 各リスクにおいて使われている銘柄の分布
– 各リスクにおいて使われている銘柄の分布
銘柄のの構成
銘柄のの構成
リスク
k-NN/UNDX(提案手法)
k
NN/UNDX(提案手法)
リスク
リスク
MDX[土谷 07]
k-NN/UNDX(提案手法)
k
NN/UNDX(提案手法)
リスク
MDX[土谷 07]
• 提案手法はMDXとほぼ同等の性能を獲得
113
実験3 取引コスト制約付きのPSP
114
実験３の結果（1/2）
• 実験の目的
• 獲得された有効フロンティア
獲得された有効フロンテ ア(EF)
獲得された効率的ポートフォリオの解構造の分析
• 実験の設定
– ベンチマーク問題
ンチマ ク問題
HangSeng (31銘柄)
目的関数空間
取引コスト関数の特徴
（a）取引コスト・小
（b）取引コスト・大
（c） 取引コスト・急増
取引コスト関数
設定した取引コスト関数
目的関数空間
• (a)
(a), (b),
(b) (c)のEFは制約なしのPSPのEFより下に形成
• (c)のEFは高リスク側では高リターンのEFが導出されない
115
116
実験３の結果（2/2）
• 獲得されたポートフォリオ
まとめ
2銘柄
で構成
構成
取引コスト・大
3銘柄
で構成
– 交叉する親の距離を限定するk
k-最近傍限定を提案
• QPと同等の精度の解を実現(最高225次元)
– 修正オペレータを用いた実数値GAによって銘柄数制約
や取引コストを考慮したポートフォリオ最適化を実現
• 今後の課題
取引コスト・小
• 取引コスト関数の特徴を反映したポートフォリオを形成
• 研究成果
117
多目的最適化における
降下方向，改悪方向，非改悪方向
– 制約違反を生成しないような交叉の提案
– 他の多目的最適化問題における
他 多 的最適
お るk-NN限定の有効性
限定 有効性
118
降下方向の変化
119
120
非改悪方向の変化
パレ ト解から遠いときのGAの挙動
パレート解から遠いときのGAの挙動
121
122
多目的GAにおける生存選択の問題点
パレ ト解に近いときのGAの挙動
パレート解に近いときのGAの挙動
探索序盤
123
探索終盤
„ 探索序盤
– 親個体よりもパレート解に近い子個体が生き残る
親個体よりもパレ ト解に近い子個体が生き残る．
„ 探索終盤
– 親個体よりもパレート解から離れた子個体→淘汰されにくい．
– パレート解周辺に密集した親個体と一部の子個体→淘汰されやすい．
パ
解周辺 密集 た親個体と 部
個体 淘汰されやす
„ →探索の終盤ほど，解集合がなかなかパレート解に近づかず，
GAでは高精度の解を得るのが困難
„ 局所探索と組み合わせて解集合を精緻化の必要性
124
GAと局所探索の組み合わせ
GAと局所探索の組合せ
„GA with LS
GA with LS
– 局所探索によってGAが促進
– 解集合が局所パレート解に捕らわれる可能性
解集合が局所パレ ト解に捕らわれる可能性
– LSに比べると精緻化に劣ると予想
序盤の探索を加速するが
局所パレ ト解に陥る危険
局所パレート解に陥る危険
• パレート解から離れた子個体が間引きを生き残る．
パレ ト解から離れた子個体が間引きを生き残る
„GA then LS
GA then LS
– GAで局所パレート解乗り越えと多様性を実現
– LSで精緻化を実現
– 多様性へのLSの影響
GAで得られた解の精緻化
において効果的
• パレート降下方向に解を移動する
パレ ト降下方向に解を移動するLSを用いれば，影響ない
を用いれば 影響ない
125
場合1
GAとLSの組み合わせの比較
„ GA then LS > GA with LS > GA
∵ GA with LSではLSと生存選択が干
渉し合い，GA then LSに劣る
場合2
„ GA then LS ~ GA with LS > GA
∵パレート解が境界上に存在したり，
直線をなしたりするため，GAとLS
の干渉が少ない
127
126
場合3
„ GA then LS > GA > GA with LS
∵ GA with LSではLSによって解集合が局所パレート解に捕らわれ，
局所パレート解乗り越えに失敗
⇒ 組み合わせ方はGA then LSがよい
128
多目的関数最適化問題
m in f ( x ) = ( f 1 ( x )), f 2 ( x )), K , f M ( x )) t
x
su bj . to x = ( x1 , x 2 , K , x N ) t ∈ S ⊆ R N
多峰性多目的関数最適化のための
パレ ト多様体ベ スのGA
パレート多様体ベースのGA
z 変数の次元 N は目的関数の次元 M より，通常，大きい.
このとき，（局所）パレート解は，変数空間および目的関数
空間において局所的に M -1次元多様体 として存在する
ex. ２目的では曲線，３目的では曲面，４目的では空間
z 局所パレート解だけからなる多様体 を局所パレート多様体，
パレート解だけからなる多様体およびパレート解と局所パ
レート解が共存する多様体をパレート多様体と呼ぶ
ト解が共存する多様体をパ
ト多様体と呼ぶ
130
曲線ベース多目的GA
曲線ベ ス多目的GA [Harada 06]
多峰性多目的関数最適化の新しい見方
z ２目的問題の解が曲線の集合をなす事実に着目
z PDM (Pareto Descent Method)
⇒ （局所）パレート最適性を高精度で保証
z PPF (Pareto Path Following)
⇒ 勾配射影法を用いてパレート解曲線を抽出
z Curve
based Multi
objective GAを提案
Curve-based
Multi-objective
⇒ （局所）パレート解曲線単位での探索を実現
z パレート多様体をできるだけ多く網羅すること
z 各パレート多様体からパレート解をできるだけ
一様にサンプリングすること
多峰性多目的関数最適化の特徴
z 目的空間ではパレート多様体の分離は困難
z 変数空間ではパレート多様体の分離は容易
z ２目的関数最適化では完成度が非常に高い手法
目的関数最適化 は完成度が非常に高い手法
しかし、
３目的以上では 計算量的に適用が事実上困難
z ３目的以上では、計算量的に適用が事実上困難
⇒ 多様体ベースの解法の可能性
131
132
多目的GAにおける探索の単位
曲線ベースの多目的GA：複製選択・交叉
• 通常の多目的GA
– 探索の単位：点
– 複製選択・交叉：有望な新しい点を生成
複製選択 交叉 有望な新しい点を生成
– 生存選択：親と子のうち優れたものを集団サイズ分だけ選択
•
•
役割：新しい曲線の発見
役割
新
曲線 発見
点ベースの交叉を利用
–
1
1.
• 曲線ベースの多目的GA
曲線ベ スの多目的GA
– 着眼点
異なる曲線から親個体を選び，
異なる曲線から親個体を選び
交叉を適用
–
• PPFが利用可能な場合
PPFが利用可能な場合，一点でも与えられれば
一点でも与えられれば ，
PDR，PDM，PPFによって局所パレート曲線全体が求まる
2.
• 実際には，曲線の等間隔サンプル集合で表現
– 局所パレート解曲線を正確に表現する方法は存在しないから
集団にない曲線の発見を期待
子個体にPDR，PDMを適用
–
– 探索の単位：局所パレート解曲線
曲線
曲線同士の直接交叉は困難と
直接交
難
考えられるから
集団内の曲線に属さない曲線
に到達したかを
達
を
PPFクラスタリングで判定
•
133
曲線ベースの多目的GA：生存選択
→PPFを適用，新しい曲線を
→PPFを適用
新しい曲線を
集団に追加
ベンチマーク：3変数2目的Rastrigin関数
局所パレート解
•
役割：親と子の曲線集合から優れたも
役割
親と子の曲線集合から優れたも
のを集団サイズ分だけ選択
–
–
– ラストリジン関数
を回転，平行移
動したもの
– 局所パレート解
が極めて多い
非淘汰な部分が存在する曲線を
抜き出し，ランク0とする
ランクを増やしながら残りの曲線に
対しても同様にする
• 評価尺度
2 ランクのよいものから順に選択
2.
–
•
•
– 曲線間網羅率の
100回試行平均
あるランクが集団サイズをまたぐ場合
•
パレート解
• 目的関数
仮定：集団サイズ(曲線の数)を固定
1. 曲線をランク付け
曲線を
–
134
限られた集団サイズで高い多様性を
維持したい
→非淘汰な部分の目的関数空間にお
ける長さが長いものから順に選択
• パレート解曲線
のうち，求まっ
たものの割合
一度求まったパレート解曲線は探索過程で失われない
度求ま たパレ ト解曲線は探索過程で失われない
135
136
曲線ベース多目的GAの拡張
曲線間網羅率平均の変化
z ３目的以上の多峰性多目的関数最適化を対象
• 通常の多目的GA
– 曲線間網羅率を悪化させる
z 高性能な多様体ベースの多目的GAを構築
• 最終的に全試行で全ての曲線
が求まっているわけではない
– 目的関数評価回数が少ない
• 曲線ベースの多目的GA
– 曲線間網羅率を悪化させない
• 最終的に全試行で全ての曲線
が求まっている
– 目的関数評価回数が多い
→「通常の多目的GAのマルチス
タート」に対し，性能と評価回数
についてトレ ドオフの関係
についてトレードオフの関係
• 曲線ベースの多目的GAの課題
– 目的関数評価回数を削減する
• 例：交叉を工夫するなどして，新しい曲線の発見効率を高める
137
解法を設計する上で留意すべき事項
z 多数の（局所）パレート多様体の存在
大部分は局所パレ ト多様体
大部分は局所パレート多様体
z パレート多様体は変数空間に遍在
個別目的関数の最適解および有力局所解で
定まる凸包の内部とその周辺に広く分布
z パレート多様体の大きさや形状は多様
多様体の形状に即した探索が必要
138
解法の設計方針
評価指標
z 大域的探索によるInter-MCの向上
⇒ 変数空間上に遍在するパレート多様体を大よそ
すべて 捕捉するためにマルチスタートGAを採用
⇒ 解集合をクラスタリング ⇒ パレート多様体の種
z 多様体間網羅率
InterMC (Inter-Manifold Coverage)
パレート多様体の発見率
z 多様体内網羅率
z 局所探索によるIntra-MCの向
の向上
⇒ パレート多様体ごとの充填探索 (Filling Search)
⇒ パレート多様体を被覆する稠密な解集合を得る
パレ ト多様体を被覆する稠密な解集合を得る
IntraMC (Intra-Manifold Coverage)
パレート多様体ごとの網羅性・均質性
⇒ 変数空間におけるDNNI (Distance between
Nearest Neighboring Individuals) の平均と
標準偏差を尺度として評価する
z 高性能な局所探索手法による解集合の精緻化
⇒大域的探索におけるGA then LSおよび局所探索
におけるGA with LSのLS に（局所）パレート最適性を
高精度で保証する パレート降下法
レ ト降下法 PDM を採用
139
140
提案手法 MB-EMO
Manifold-Based Evolutionary Multi-objective Optimization
[第1段階GA]
大域的探索によるパレート多様体間網羅率の向上
X seed = f MGA ( { X init ( i );
) i = 11,K, m1} )
手順１： X seed = f MGA ( { X init (i ); i = 1,K, m1} )
手順2：
X ref = f PDM ( X seed ),
乱数の種を変えて、(1) ～ (4) をm回実行する
X nd = f NDS ( X reff )
(1) 初期集団の生成
手順3： { X man (i ); i = 1,..., ncl } = f clustering ( X nd )
[第2段階GA]
[第1段階GA]
第 段階
手順
手順１：マルチスタートGA
タ ト
(2) 複製選択： 集団からN+1個体を非復元ランダム抽出
(3) 交叉による子個体生成： REX(U, N+1)の適用
局所的探索によるパレート多様体内網羅率の向上
(4)生存選択：
・優越関係に基づくランキング選択
・変数空間におけるシェアリング
手順１： X fil (i ) = f filling − search ( X man (i ));
)) i = 1,...,
1 ncl
, , ncl } )
手順2： { X sol (i )} = f NDS ( { X fil (i ); i = 1,...,
141
142
ベンチマーク：4変数4目的Rastrigin関数
g
[第2段階GA]
[第
段階 ] 手順
手順１：充填探索
充填探索
X fil (i ) = f filling − search ( X man (i )); i = 1,..., ncl
提案手法MB-EMOの実験設定
提案手法MB
EMOの実験設定
各 X man (i ) ごとに、(1) ～ (5) を実行する
第1段階GA
集団サイズ
交叉オペレータ
生成 個体数
生成子個体数
世代交代数
マルチスタート回数
200
REX(U, n+1)
20
500
25
第2段階GA
初期集団
交叉オペレータ
生成子個体数
打ち切り集団サイズ
REX((U, M+1))
5
2000
(1) 初期集団を X man (i ) に設定する
(2) 複製選択： 集団から変数空間上でDNNIが最大の個
体を選び 交叉の主親とする 主親のk-NN
体を選び、交叉の主親とする．主親の
NNに存在する
個体群の中からM個の個体を選び、副親とする
( ) 交叉による子個体生成：
交叉 よる子個体生成 REX((U, M+1))の適用
適用
(3)
(4) 生成子個体のPDMによる洗練化
(5) 生存選択：
①優越関係に基づくランキング選択
①優越関係に基
くランキング選択
②変数空間におけるシェアリング
X man (i )
比較手法
143
第1段階GAでマルチスタ ト回数を1000としたもの
第1段階GAでマルチスタート回数を1000としたもの
（計算量は提案手法の約３倍）
144
提案手法 MB-EMOとMGA
MB EMOとMGA then LSの
パレート多様体ごとの最近接個体間距離の比較
Averrage DNNI
多様体体間網羅率
Aveerage DNNI
MB-EMOの第1段階GAにおける
MB
EMOの第1段階GAにおける
マルチスタート回数の効果
Solution No.
No
提案手法 MB-EMO
マルチスタート回数
145
MB EMOのまとめ
MB-EMOのまとめ
zM目的問題のパレート解集合はM-1次元多様体として存在する
z多目的最適化問題を解くとは、パレート多様体をすべて列挙し、
パレート多様体ごとに解集合を一様にサンプルすることである
z多峰性のもとでのパレート多様体集合は、一般に、目的空間で
は分離不可能であるが、変数空間では分離可能な場合が多い
上記の事実に基づいて
z2段階GAから構成される多様体
から構成される多様体ベースの
スのMB
MB-EMO
EMOを提案
z第1段階GA: multi-start GAによりパレート多様体の網羅を図る
z第2段階GA: 充填探索により多様体内の網羅と均質化を図る
zMB-EMOは、変数や目的の次元に依存することなく、高精度の
パ
パレート解集合を求めることができる
解集合を求める
が きる
147
Solution No.
MGA then LS
146