9月22日に
【初心者、中級者向け】最適化問題における遺伝的アルゴリズム(GA)をPythonで動かすハンズオン
https://liberal-arts-beginners.connpass.com/event/147304/
を聞いてきたので、メモ
資料
https://github.com/espeon011/ga
遺伝的アルゴリズム入門
今日の内容
・遺伝的アルゴリズム
・代表的開放
・遺伝的アルゴリズム
・Ｄｅａｐ
最適化問題
・制約条件の下で関数値を最大化・最小化する問題
・よくある例は回帰分析
二次関数の最小化問題
・例 式 maximize subject to :
ラグランジェの未定乗数法を使って手でとくとか
最適化問題の種類
・線形計画問題
制約条件も目的関数も一時式で描けるもの
・非線形計画問題
線形計画問題でないもの
・整数計画問題
変数が整数の場合、解くのが難しいが、現実の問題をモデリングしやすい
→ナップザック問題
最適化問題の解き方
線形計画問題
単体法、内点法他
非線形計画問題
勾配降下法：微分できる関数に限る
整数計画問題
分子限定法他
問題に合わせて適切に解き方を変える
→ＧＡは何でも使える：メタヒューリスティック
メタヒューリスティック
・汎用性の高い発見的手法
遺伝的アルゴリズムの概要
１．探索範囲内に個体を生成
２．適応度の高い個体を選抜
３．親から子を作る
４．子に突戦変異
５．２に戻る
one max問題
個体 ：01を値に取る長さ１００の配列
目的関数：すべての成分の和→最大化
→すべてを１にすれば最大になるのは自明
・Ｄｅｅｐを使う
fitnessmax
toolbox関数を登録できる（使わなくてもできる）
attr_bool：各成分の初期化
individual：各成分の初期化を使って初期値生成
population：個体生成→世代
目的関数：returnはタプルである必要性（答え１個でも ,をつける）
evaluate：何を目的関数にするか
世代交代の方法
mate :交叉２点を選んで、遺伝子を交換する ２点：cxTwoPoint 一様交叉もある
mutate：突然変異 matFlipBit突然変異させる
select：親の厳選 selTournament トーナメント ３人ランダムに選んで１人残す
toolbox.population：個体数を指定
CXPB,MUTPB,NGEN
CXPB：親を残す（変化せず）確率
MUTPB：突然変異を起こす確率
NGEN：世代数
今回の問題：個体 長さ２の配列（ｘ、ｙ）目的関数Ｘ^2+Y^2 範囲５０～-５０
イントロダクション
・クラスの作成
適応度の定義
個体の定義
・世代や個体を生成するための関数
individual 長さ指定：２
・個体の生成
ind = toolbox.individual()
・世代を生成
pop = toolbox.population(n=10)
・世代交叉関数
selectは同じ（トーナメント）
mute:ブレンド交叉
親２体がなす四角形を１＋２α倍したものの中からランダム
mutate:突然変異：ガウス分布の乱数
・個体の交叉
・突然変異
・目的関数の設定
目的関数を定義
登録
目的関数を計算させる
多目的最適化問題
minimaize:f1(x),f2(x),…
subject to: x∈Ｅ
→トレードオフ関係があると、目的関数すべてを同時に最小化できない
パレートフロント：パレートフロント上の点はパレート最適という
→上位互換が存在しない
パレートフロントを近似したい
遺伝的アルゴリズムにおいて
世代作成
トーナメント→目的関数値が良いものを選んだ：２つの個体の優劣は比べられるとは限らない
子が作られて
突然変異する
→ＮＳＧＡ－Ⅱというトーナメント方式
ＮＳＧＡ－Ⅱでのトーナメントの流れ
１．完全上位互換がいない個体を取り出し、これらをrankが１であるとする
２．rank１の個体を除いたときに完全上位互換がいないものをrank2であるとする
３．以下繰り返し
→すべての個体にrankが定まる
４．混雑度を定める
rankが１の個体の集合Ｒ１ x∈R1
d(x)=min{f1(y)|f1(y) ≧ f1(x)}-max{f1(y)|f1(y) ＜＝ f1(x)}
+min{f2(y)|f2(y) ≧ f2(x)}-max{f2(y)|f2(y) ＜＝ f2(x)}
混雑度が大きいと混雑していない
一番端は∞
※一番近くの隣の点をとっていき、そのＸの差分、Ｙの差分を足したものが混雑度
rankからとっていき、さいご、rankが同じなら、混雑度の大きいのをとってくる
A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II
https://www.iitk.ac.in/kangal/Deb_NSGA-II.pdf
ナップザック問題：重さとうれしさ
・初期世代
・制約を破ったらとてつもないペナルティを課す
・algorithms.eaMuPlusLambda(pop, toolbox, MU, LAMBDA, CXPB, MUTPB, NGEN, stats, halloffame=hof, verbose=True)
→計算してくれる
・パレートフロントが得られる
混雑度を測る方法
Hyper Volumeによる方法
・reference point rを定める
・ハイパーボリュームを定める
・xiを除いた時のハイパーボリュームの原書医療をxiの混雑度とする手もある
【初心者、中級者向け】最適化問題における遺伝的アルゴリズム(GA)をPythonで動かすハンズオン
https://liberal-arts-beginners.connpass.com/event/147304/
を聞いてきたので、メモ
資料
https://github.com/espeon011/ga
遺伝的アルゴリズム入門
今日の内容
・遺伝的アルゴリズム
・代表的開放
・遺伝的アルゴリズム
・Ｄｅａｐ
最適化問題
・制約条件の下で関数値を最大化・最小化する問題
・よくある例は回帰分析
二次関数の最小化問題
・例 式 maximize subject to :
ラグランジェの未定乗数法を使って手でとくとか
最適化問題の種類
・線形計画問題
制約条件も目的関数も一時式で描けるもの
・非線形計画問題
線形計画問題でないもの
・整数計画問題
変数が整数の場合、解くのが難しいが、現実の問題をモデリングしやすい
→ナップザック問題
最適化問題の解き方
線形計画問題
単体法、内点法他
非線形計画問題
勾配降下法：微分できる関数に限る
整数計画問題
分子限定法他
問題に合わせて適切に解き方を変える
→ＧＡは何でも使える：メタヒューリスティック
メタヒューリスティック
・汎用性の高い発見的手法
遺伝的アルゴリズムの概要
１．探索範囲内に個体を生成
２．適応度の高い個体を選抜
３．親から子を作る
４．子に突戦変異
５．２に戻る
one max問題
個体 ：01を値に取る長さ１００の配列
目的関数：すべての成分の和→最大化
→すべてを１にすれば最大になるのは自明
・Ｄｅｅｐを使う
fitnessmax
toolbox関数を登録できる（使わなくてもできる）
attr_bool：各成分の初期化
individual：各成分の初期化を使って初期値生成
population：個体生成→世代
目的関数：returnはタプルである必要性（答え１個でも ,をつける）
evaluate：何を目的関数にするか
世代交代の方法
mate :交叉２点を選んで、遺伝子を交換する ２点：cxTwoPoint 一様交叉もある
mutate：突然変異 matFlipBit突然変異させる
select：親の厳選 selTournament トーナメント ３人ランダムに選んで１人残す
toolbox.population：個体数を指定
CXPB,MUTPB,NGEN
CXPB：親を残す（変化せず）確率
MUTPB：突然変異を起こす確率
NGEN：世代数
今回の問題：個体 長さ２の配列（ｘ、ｙ）目的関数Ｘ^2+Y^2 範囲５０～-５０
イントロダクション
・クラスの作成
適応度の定義
個体の定義
・世代や個体を生成するための関数
individual 長さ指定：２
・個体の生成
ind = toolbox.individual()
・世代を生成
pop = toolbox.population(n=10)
・世代交叉関数
selectは同じ（トーナメント）
mute:ブレンド交叉
親２体がなす四角形を１＋２α倍したものの中からランダム
mutate:突然変異：ガウス分布の乱数
・個体の交叉
・突然変異
・目的関数の設定
目的関数を定義
登録
目的関数を計算させる
多目的最適化問題
minimaize:f1(x),f2(x),…
subject to: x∈Ｅ
→トレードオフ関係があると、目的関数すべてを同時に最小化できない
パレートフロント：パレートフロント上の点はパレート最適という
→上位互換が存在しない
パレートフロントを近似したい
遺伝的アルゴリズムにおいて
世代作成
トーナメント→目的関数値が良いものを選んだ：２つの個体の優劣は比べられるとは限らない
子が作られて
突然変異する
→ＮＳＧＡ－Ⅱというトーナメント方式
ＮＳＧＡ－Ⅱでのトーナメントの流れ
１．完全上位互換がいない個体を取り出し、これらをrankが１であるとする
２．rank１の個体を除いたときに完全上位互換がいないものをrank2であるとする
３．以下繰り返し
→すべての個体にrankが定まる
４．混雑度を定める
rankが１の個体の集合Ｒ１ x∈R1
d(x)=min{f1(y)|f1(y) ≧ f1(x)}-max{f1(y)|f1(y) ＜＝ f1(x)}
+min{f2(y)|f2(y) ≧ f2(x)}-max{f2(y)|f2(y) ＜＝ f2(x)}
混雑度が大きいと混雑していない
一番端は∞
※一番近くの隣の点をとっていき、そのＸの差分、Ｙの差分を足したものが混雑度
rankからとっていき、さいご、rankが同じなら、混雑度の大きいのをとってくる
A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II
https://www.iitk.ac.in/kangal/Deb_NSGA-II.pdf
ナップザック問題：重さとうれしさ
・初期世代
・制約を破ったらとてつもないペナルティを課す
・algorithms.eaMuPlusLambda(pop, toolbox, MU, LAMBDA, CXPB, MUTPB, NGEN, stats, halloffame=hof, verbose=True)
→計算してくれる
・パレートフロントが得られる
混雑度を測る方法
Hyper Volumeによる方法
・reference point rを定める
・ハイパーボリュームを定める
・xiを除いた時のハイパーボリュームの原書医療をxiの混雑度とする手もある
アクセス
トータル
ランキング
