パレート最適解

Report
多目的最適化問題のための
多目的GAと単一目的GAの
分散協力型モデル
Distributed Cooperation model of MOGA and SGA for
Multiobjective Optimization Problems
○
同志社大学
廣安 知之
同志社大学
三木 光範
同志社大学大学院 奥田 環
同志社大学大学院 渡邉 真也
■ 多目的最適化問題
• 複数の評価基準(目的関数)
• 各評価基準との間にトレードオフの関係
→
完全な最適解が存在しない
パレート最適解
→ 他の任意の解と比較して
総合的に劣らない解
パレート最適解集合の探索
可能領域
弱パレート最適解
パレート最適解
■ 遺伝的アルゴリズムの適用
遺伝的アルゴリズム(Genetic Algorithms:GA)
→
多点探索
一度の探索でパレート最適解集合を求めることが可能
→ 多目的最適化問題に
遺伝的アルゴリズムを適用した
多目的遺伝的アルゴリズム
(Multi Objective GA: MOGA)
に関する研究が多くなされている
■ 研究背景
多目的GA(MOGA)において,対象とする問題が難しくなる
→ 広範囲に分布するパレート解集合を得ることが困難になる
目的:広範囲に分布するパレート最適解
•
•
多目的GA個体群(MOGA個体群):多目的のパレート解の探索
単一目的GA個体群(SGA個体群):各目的関数の最適解の探索
多目的分散協力型モデル
Distributed Cooperation model
for Multiobjective Genetic Algorithms
■ DCMOGA
ー2目的の場合-
1.
2.
3.
4.
5.
6.
7.
初期個体の生成
評価計算
選択
交叉
突然変異
移住(解交換)
終了条件
■ DCMOGA
ー2目的の場合-
1.
2.
3.
4.
5.
6.
7.
初期個体の生成
評価計算
選択
交叉
突然変異
移住(解交換)
終了条件
■ DCMOGA
ー2目的の場合-
1.
2.
3.
4.
5.
6.
7.
初期個体の生成
評価計算
選択
交叉
突然変異
移住(解交換)
終了条件
■ DCMOGA
ー2目的の場合-
1.
2.
3.
4.
5.
6.
7.
初期個体の生成
評価計算
選択
交叉
突然変異
移住(解交換)
終了条件
■ 多目的0/1ナップサック問題
0/1ナップサック問題とは,
荷物(item)のセット
→
“重量”と“価値”
ナップサック → 重量制限
→ 総価値が最大になる荷物の組み合わせ
多目的0/1ナップサック問題
– 複数のナップサックと荷物のセット
– 代表的なテスト問題 (Eckart Zitzler)
ナップサック数
2
2
荷物数
750
250
■ アンテナ問題(1)
領域内の候補サイトの中から
設置するサイトとアンテナの種類を決定
設置するサイト
候補サイトの中から
アンテナを設置する
サイトの決定
アンテナの種類
電波の強さとコストの異なる
3種類のアンテナから決定
■ アンテナ問題(2)
目的
• 電波のカバー領域の最大化
• 設計コストの最小化
→目的間にトレードオフの関係
制約条件
• 電波の重なり(50%以上)
• 電波のカバー領域(80%以上)
• アンテナのコスト(1000以下)
■ 数値実験
対象問題
• 多目的0/1ナップサック問題
• アンテナ問題
適用した手法
• 従来の多目的GA(MOGA)
→ ランキング法 + パレート保存戦略
• 多目的分散協力型モデル(DCMOGA)
GAオペレータ・パラメータ
交叉
一点交叉
1.0
突然変異 ビット反転
400 / 80
個体数
1/染色体長
■ 数値実験結果(1)
多目的0/1ナップサック問題
荷物数:250
荷物数:750
■ 数値実験結果(2)
アンテナ問題
DCMOGA
MOGA
150
140
130
カバー率:0.977
コスト:100
120
110
100
90
カバー率:0.828
コスト:65
80
70
60
50
0.8
0.85
0.9
0.95
1
■ 数値実験結果(3)
カバー率:0.977
コスト:100
カバー率:0.828
コスト:65
■ 結論
多目的0/1ナップサック問題とアンテナ問題に
従来のMOGAとDCMOGAを適用した
DCMOGAは従来のMOGAと比較して,
多目的0/1ナップサック問題
– より広範囲に分布したパレート解を得ることができた
– 精度においても同等以上の結果となった
アンテナ問題
– 広範囲に分布するパレート解に関しては
精度の良いパレート解を得た
DCMOGAは有効な手法である
■
■ DCMOGA(1)
目的:広範囲に分布するパレート最適解
MOGA個体群:多目的のパレート解の探索
SGA個体群:各目的関数の最適解の探索
■ DCMOGA(2)
■ DCMOGAパラメータ
MOGA個体群
個体数
交叉率
突然変異率
移住率
SGA個体群
400
1.0
4
1.0
1/染色体長
1/染色体長
1回目:MOGA個体群が10世代後
(10×400 [評価計算] )
SGA個体群1000世代後
(1000×4 [評価計算] )
2回目以降:各個体群の最適解を比較して
次回の移住までの評価回数を決定する
■ パレートランキング法
• 解の優劣関係に基づいて
ランクを定める.
• 個体xがn個の個体に優越
されているときの個体xの
ランクrx (Fonsecaら)
rx  1  n x
A(1)
G(4)
B(1)
C(1)
F(2)
D(1)
f1(x)
E(1)

similar documents