パレート最適解

多目的最適化問題のための
多目的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  nx
A(1)
G(4)
B(1)
C(1)
F(2)
D(1)
f1(x)
E(1)

Download Report