α-domination戦略を用いた 近似パレート最適解における解抽出

α-domination戦略による
非劣解集合からの解抽出法
同志社大学
同志社大学
同志社大学
同志社大学
同志社大学
廣安知之
三木光範
金美和
渡邉真也
奥田環
研究背景
物事の決定には複数の基準を考慮する
例)最適な物件:家賃,築年数,広さ,住宅環境,外観,etc.
単目的最適化
目的:
目的:家賃
広さ
家賃
広さ
\110,000
\20,000
15畳
4畳
築年数
3年
20年
多目的最適化
目的:家賃,築年数,広さ,etc
家賃
広さ
築年数
最適解1: \50,000
8畳
5年
最適解2: \42,000
6畳
1年
複数の最適解を得られる
実行に解の選択が困難
提案:解選択を支援する手法
多目的最適化問題
互いに競合する複数の目的関数のもとで最適値を求める問題
例) 不動産屋が,顧客に最適な物件を紹介する問題.
顧客の要望:より安い家賃,なるべく新しい物件. (2目的最小化問題)
安い家賃
新築
築20年
高い家賃
互いに競合する関係
家賃
築年数
(最低家賃で新築の物件はない)
目的1:家賃
目的2:築年数
特徴:完全な最適解は存在しない
多目的最適化問題
例)顧客に紹介する最適物件: より安く,なるべく新しい物件
家賃(万円)
優越領域
優越領域
優越領域
優越領域
9
解の優越関係
優越領域に含まれる解
6
物件z:7万円,築6年
劣った解(劣解)
劣解
物件y:5万円,築22年
3
非劣解
非劣解となる物件を複数用意し,
物件x: 2万円,築17年
顧客が最終的に決断する
5
10
15
20
25
非劣解:
どの解にも劣らない解
築年数(年)
多目的最適化問題
(不動産屋)
多目的最適化:複数の非劣解が最適解
として求まる
(顧客)
家賃
意思決定者:非劣解集合から解を選ぶ
選好解
選好解
意思決定者によって
非劣解集合から選択される解
築年数
選好解決定の問題点
選好解の決定方法:各非劣解を比較し,妥協できる解を選択
物件A
家賃 : \65000
築年数 : 1ヶ月
問題点
多数の非劣解が存在する
物件B
解決策
少数の非劣解を
選好解候補として提示
家賃
全非劣解の比較は
膨大な作業となる
家賃 : \45000
築年数 : 7年
築年数
選好解決定:困難
選好解決定:容易
選好解候補を抽出するα抽出法の提案
α抽出法
α抽出法の特徴
多様な非劣解の抽出
非劣解集合の分割
より良い非劣解の抽出
α-domination戦略 【池田,2001】
部分的な解抽出
多様な非劣解
(家
賃)
選好解候補の
様々な性質の
特徴が類似してしまう
非劣解を比較できる
より良い非劣解
yの方がxよりも
良い非劣解
(築年数)
※最小化問題
非劣解集合の分割
1.各目的関数の最適値を保持した非劣解を抽出.
2.選好解候補となる非劣解を抽出.(α-domination戦略)
3.抽出した非劣解を基準に解集合を分割し再び非劣解を抽出.
多様な選好解候補
α‐domination戦略
パラメータα(0≦α<1)によって解の優越領域が変化
定義
優越領域
優越領域
解xが解yをα-dominateする
y
2目的最小化
α‐domination戦略の意義
高い
1年古い
安い
2000円安い
優越される解
合理的な解
新しい
3000円安い
古い
優越されない解
α-domination戦略で優越されない解
合理性が高い
α‐domination戦略の利用
α抽出法
α-domination戦略によって全非劣解の優越領域を拡大
合理性の高い非劣解を抽出する
優越されない解を抽出
通常の優越関係
α抽出法における優越関係
α抽出法の流れ
3
10 4
10
10
10
Step 1 各目的関数値が最適な解を抽出
3
10
Step 2 各非劣解集合に対して
α-domination戦略を用いて解を抽出
47
5
1010
10
Step 3 抽出した非劣解の評価付け
評価値 =
抽出の対象となる解集合の数
非劣解集合全体の数
多くの解から抽出された解ほど高く評価
全10個の非劣解
Step 4 抽出した非劣解を基準に解集合を分割
Step 5 評価値の高い非劣解から選好解候補として提示する
数値実験
比較対象手法:非劣解の多様性を重視した手法(中点抽出法)
テスト問題:多目的遺伝的アルゴリズムを用いて得られた非劣解集合
凸型分布【玉置,1995】
不連続分布 【 Deb,1999】
評価方法
テスト問題の最適解と,抽出した非劣解の誤差
数値実験 ー比較対象手法ー
中点抽出法:2点間の中点に最も近い解を抽出する
1.各目的関数値が最適な解を抽出
中点
中点
2.抽出した解の中点に近い解を抽出
3.解集合を分割
多様な解が得られる手法
数値実験 ーテスト問題 1 ー
2目的最小化問題【玉置,1995】
ー凸型分布ー
テスト問題の最適解
最適化によって得られた非劣解
数値実験 ーテスト問題 2 ー
2目的最小化問題【Deb,1999】
ー不連続分布ー
テスト問題の最適解
最適化によって得られた非劣解
数値実験 ー評価方法ー
スプライン補間による曲線と最適解との誤差を調べる.
抽出した非劣解
スプライン補間による曲線
誤差の求め方
目的関数f 1のサンプリングを行い
目的関数 f 2の平均誤差を
曲線と最適解集合との誤差とする
最適解
実験結果
α抽出法
中点抽出法
抽出した非劣解の数
テスト問題:不連続分布
最適解との誤差
最適解との誤差
テスト問題:凸型分布
α抽出法
中点抽出法
抽出した非劣解の数
α抽出法の方が最適解との誤差が小さい
結論
多目的最適化問題:複数の非劣解が存在
問題点 複数の非劣解の中から選好解を決定するのは困難
解決策:選好解候補の提示
多様かつ合理性の高い非劣解を抽出する
α抽出法
α抽出法
非劣解集合の中から最適解に近い非劣解を抽出
α抽出法は,複数の非劣解の中から
選好解候補を選出する有効な手法
n目的最適化問題への適応 ークラスタリングの導入ー
クラスタリング
K個のデータの類似度を求め,P個のグループに分けること.
1.各非劣解は異なるクラスタに属するものとする.
2.全てのクラスタ同士のユークリッド距離を求める.
3.最小距離dを持つクラスタCxとCyを決定し,
二つのクラスタを統合する.
4.クラスタ内の非劣解集合にα-domiantion戦略
を適用し解を抽出する.
目的関数空間
代表的な選好解決定法
対話型手法
意思決定者との対話によって選好解を引き出す手法
問題点:煩雑である.トレードオフ比を答えることは困難.
重み付けによる手法
意思決定者の価値観をあらかじめ関数として定義し,
単一目的の最適化問題として選好解を求める手法.
問題点:解探索がトレードオフ解析に基づかないため
選好を十分に反映できない.
スケーリング
各目的関数の範囲が等しくなるように値を調整すること
f 2 m ax  f 2 m i n
f  f1m i n  f1 
f 1m ax  f 1m i n
'
1
スケーリング前
スケーリング後
多目的遺伝的アルゴリズム
遺伝的アルゴリズム
特徴:多点探索
個体の生成
選択
交差
突然変異
終了条件
終了
世代 1
世代 2
世代 3