実数値遺伝的アルゴリズムにおける計算モデルの検討

実数値遺伝的アルゴリズムにおける
計算モデルの検討
A Discussion on Computational Models of Real-coded Genetic Algorithm
知的システムデザイン研究室
16980013 : 福永隆宏
遺伝的アルゴリズム
生物の進化を模倣した
最適化アルゴリズム
f (x1, x2)
(2, 7)
候補解をビットストリングで表現
確率的な多点探索
エンコード
デコード
遺伝オペレータ
交叉
染色体
個体・・・
010111
x1
x2
突然変異
評価
選択
設計変数
Intelligent Systems Design Lab - Doshisha Univ
遺伝的アルゴリズムの問題点
ビットストリングによる染色体のコーディング
探索空間に連続性が反映されていない
連続性を考慮した探索
実数値GA
高い計算負荷
膨大な反復計算が必要なため計算負荷が高くなる
計算負荷の軽減
分散GA
Intelligent Systems Design Lab - Doshisha Univ
実数値遺伝的アルゴリズム
実数ベクトルによる
染色体のコーディング
実数値のための
遺伝オペレータ
(交叉法:BLX-α,UNDX)
親個体の形質を
効率よく引き継ぐ
連続性を考慮した探索が可能
Intelligent Systems Design Lab - Doshisha Univ
分散遺伝的アルゴリズム
サブ母集団(島)に分割
各島内で独立した遺伝操作
Distribute
島間で移住
解の高品質化が期待できる
島モデルによる分散効果
Intelligent Systems Design Lab - Doshisha Univ
研究の目的
問題点を解決するための手法
実数値GA と 分散GA
それらの組み合わせによる解探索性能の検討
交叉法
突然変異の有無
島数
4種類にモデルを設定
Intelligent Systems Design Lab - Doshisha Univ
分散実数値GAの計算モデルの検討
Model-1
Model-2
Model-3
Model-4
交叉法
突然変異の有無
BLX-α
BLX-α
UNDX
UNDX
○
×
○
×
BLX-α(Esheleman,93):設計変数間に依存関係のない問題に有効
UNDX (ono,97)
:設計変数間に依存関係のある問題に有効
<数値実験>
連続関数最小化問題に適用
設計変数間に依存関係のないRastrigin関数
Intelligent Systems Design Lab - Doshisha Univ
数値実験結果
Rastrigin関数
設計変数間に依存関係のない問題に対しては
Model-1(BLX-α,突然変異有り)
Model-3(UNDX,突然変異有り) が有効
Intelligent Systems Design Lab - Doshisha Univ
数値実験のまとめ
設計変数間に依存関係のない問題に対しては,
Model-1(BLX-α,突然変異有り)
Model-3(UNDX,突然変異有り)
が有効
これらのモデルが実問題にも有効であるか検討する
アンテナ配置問題
Intelligent Systems Design Lab - Doshisha Univ
アンテナ配置問題
概要 : アンテナ設置領域内に,あらかじめ用意されたアンテナを
配置し,設計コストを最小にする問題
制約 : 電波のカバー領域は,ある値以上でなければならない
アンテナの設置できる領域が限定されている
Intelligent Systems Design Lab - Doshisha Univ
探索の様子
実験概要
4種類のアンテナ
Radius
Cost
2
5
5
20
10
100
20
400
目的
設計コスト最小化
制約
最大設置アンテナ30本
カバー率95%
海上にアンテナは設置できない
Intelligent Systems Design Lab - Doshisha Univ
数値実験結果(設計コスト最小化)
Model-1(BLX-α,突然変異有り)が良好な結果
島モデルによる分散効果も確認
Intelligent Systems Design Lab - Doshisha Univ
結論
実数値GAにおける,計算モデルを検討した
設計変数間に依存関係のない問題に対しては,
いずれの交叉法においても,突然変異を行うことで,
良好な結果を得ることができた
島モデルによる分散効果も確認された
実数値GAを実問題に適用した
テスト関数の場合と類似した探索傾向が確認された
テスト関数によるモデルの検討は有効である
Intelligent Systems Design Lab - Doshisha Univ
Intelligent Systems Design Lab - Doshisha Univ
補足資料
Intelligent Systems Design Lab - Doshisha Univ
研究背景
最適化問題とは
与えられた制約条件の下で,ある目的関数を
最小(最大)にする設計変数を求める問題
世の中には様々な最適化問題がある.
ディーゼルエンジン燃料噴射スケジュール問題
タンパク質の立体構造解析
トラス構造物体積最小化問題
Intelligent Systems Design Lab - Doshisha Univ
BLX-αとUNDX
UNDX
BLX-α
(Eshelman 93)
(Ono 97)
• 2つの親個体の各成分距離
α倍拡張した領域内に生成
• 3つの親個体により定義される
正規分布領域内に生成
• 設計変数間に依存関係のある問題に
弱い
• 設計変数間に依存関係のある問題に
強い
Intelligent Systems Design Lab - Doshisha Univ
実数値GAの突然変異
① 一様突然変異
(Uniform mutation)
② 境界突然変異
(Boundary
mutation)
Intelligent Systems Design Lab - Doshisha Univ
遺伝的アルゴリズムの問題点
ビットストリングによる染色体のコーディング
探索空間に連続性が反映されていない
連続性を考慮した探索
実数値GA
高い計算負荷
膨大な反復計算が必要なため計算負荷が高くなる
計算モデルとしての有効
分散GA
局所解への収束
多峰性関数において局所解に陥る可能性が高い
多様性を維持した探索
世代交代モデル
Intelligent Systems Design Lab - Doshisha Univ
世代交代モデル
複製選択と生存選択を規定
SGA(Simple GA) - Goldberg,89
MGG(Minimal Generation Gap) - 佐藤,97
Intelligent Systems Design Lab - Doshisha Univ
MGG
1ペアの両親に対して
交叉を複数回行う
Intelligent Systems Design Lab - Doshisha Univ
実数値GAの計算モデルの検討(2)
交叉法
突然変異の有無
世代交代
モデル
Model-1
Model-2
Model-3
Model-4
BLX-α
BLX-α
UNDX
UNDX
○
×
○
×
SGA
Model-5
Model-6
Model-7
Model-8
BLX-α
BLX-α
UNDX
UNDX
○
×
○
×
MGG
Intelligent Systems Design Lab - Doshisha Univ
SGA(1 / 3)の結果
Rastrigin
Schwefel
Model-1,3は設計変数間に依存関係のない問題に有効
Intelligent Systems Design Lab - Doshisha Univ
SGA(2 / 3)の結果
Griewank
Rotated Rastrigin
設計変数間に依存関係のある問題には
探索性能に問題がある
Intelligent Systems Design Lab - Doshisha Univ
SGA(3 / 3)の結果
Rosenbrock関数
設計変数間に依存関係のある問題には
探索性能に問題がある
Intelligent Systems Design Lab - Doshisha Univ
MGG(1 / 3)の結果
Rastrigin
Schwefel
島モデルが解探索に悪影響を与えている
突然変異をしない単一母集団が良好な結果
Intelligent Systems Design Lab - Doshisha Univ
MGG(2 / 3)の結果
Griewank
Rotated Rastrigin
突然変異は探索に悪影響を与えている
Model-6をRotated Rastrigin関数に適用したとき
島モデルによる分散効果を確認
Intelligent Systems Design Lab - Doshisha Univ
MGG(3 / 3)の結果
Rosenbrock関数
Model-8でのみ,最適解を得ることができる
Intelligent Systems Design Lab - Doshisha Univ
全モデルのまとめ
対象問題と分散効果
依存関係のない問題は分散効果が得やすい
依存関係のある問題は分散効果が得にくい
世代交代モデルの影響
SGAと突然変異の併用は分散効果が顕著に現れる
MGGは遺伝オペレータに左右する
Intelligent Systems Design Lab - Doshisha Univ
SGAにおける設計コスト最小化
Model-1とmodel-3が良好な結果を示している
Intelligent Systems Design Lab - Doshisha Univ
探索履歴(SGA)
Rastrigin
Model-1
Schwefel
Model-3
Intelligent Systems Design Lab - Doshisha Univ
探索履歴(SGA)
Griewank
Model-4
Rosenbrock
Model-4
Intelligent Systems Design Lab - Doshisha Univ
探索履歴(アンテナ配置問題)
Model-1
Model-3
Intelligent Systems Design Lab - Doshisha Univ
アンテナ配置問題おける個体表現
アンテナに付随するパラメータ
アンテナの設置座標 (2D) : (x,y)
アンテナの有無 : e
電波の規模 : r
アンテナの本数*4個の設計変数が必要
Intelligent Systems Design Lab - Doshisha Univ
電波カバー率の決定方法
あらかじめ設定したチェック点をアンテナがカバーしている割合
決められた領域
等間隔にチェック点
を配置する
16/64 = 0.25
Intelligent Systems Design Lab - Doshisha Univ
実問題とテスト関数
実問題の最適化における問題点
評価に膨大な計算時間を要する
予備実験として,数学的テスト関数に適用する
有効な計算モデルを実問題へ適用
Intelligent Systems Design Lab - Doshisha Univ