インテリジェントコンピューティング

インテリジェントコンピューティング
Introduction to Soft Computing
Yuji Sato
講義内容（第6回目）
進化戦略と進化的プログラミング
1．Michalewiczの実数コードGA
2．進化戦略（Evolution Strategies: ES）
(1) (1+1)-ES
(2) (m+l)-ES, (m, l)-ES
3．進化的プログラミング
（Evolutionary Programming: EP）
Michalewiczの実数コードGA (1)
• 多次元実数空間の最適化問題では，各座標値を2進数
表現（binaryまたはGrayコード化）してGAを適用す
ると，以下の問題が生じやすい．（図4.5参照）
(1) 精度が粗い
(2) 2のべき乗での表現は必ずしも適当ではない
(3) 変化する量のスケールをGAで制御するのが困難
(4) 次元の個数だけ繋ぎ合わせたものを1個体とする
と，個体長が長くなりすぎる
Michalewiczの実数コードGA (2)
• 座標毎の実数値を遺伝子として座標値単位で遺伝的
操作を行う方法を提案
• 個体の定義
個体siをn次元ベクトルによりsi = (vi1, vi2, …, vin)と表
現する．ここで，vij, i = 1, …, N, j = 1, …, nは実数ある
いは整数などの表現型の値である．
• 問題空間と同じ表現の値であるから，実行可能解と
そうでない値との境界および，遺伝的操作での摂動
の大きさを明確にした操作が可能であるなどの点が
遺伝子型によるコード化との大きな違いとなる．
Michalewiczの実数コードGA (3)
1. 初期個体群
初期個体群は次のようにして発生さ
せる
(1) ある一定の割合の初期個体を全実行可能領域の中
にランダムに発生させる
(2) 残りの個体は実行可能領域の境界上に発生させる
ここで，個体を境界上に発生させるのは，そのよ
うな場所に最大，最小値が存在することが多いの
と，交叉で新たに発生する探索点の取り得る範囲
を広くするためである．
Michalewiczの実数コードGA (4)
2. 交叉
以下の中から，幾つか，あるいは全てを行
う
(1) 単純交叉（simple crossover）
(2) 単一算術交叉（single arithmetical crossover）図
4.6
2つの個体のある1つの座標値だけを交叉させる
(3) 全体算術交叉（whole arithmetical crossover ）図
4.7
2つのベクトルs1 ， s2を結ぶ線分上に新しい点を設
ける
Michalewiczの実数コードGA (5)
3. 突然変異
(1) 一様突然変異（uniform mutation）図4.8
突然変異の対象となった座標値の取り得る値の上限u(vi)と下
限l(vi)を求め，一様乱数によりその2値の間の値を定めて，新
しい座標とする．
(2) 境界突然変異（boundary mutation）図4.8
一様突然変異と同様にある座標値だけを変更するが，新しい
値をl(vi) ， u(vi)のいずれかの境界上にとる．
(3) 非一様突然変異（non-uniform mutation ）図4.9
これもある座標値だけを変更する．この操作では，変化させ
る値の幅を次第に狭くしていき，安定した結果が得られるよ
うにする．
進化戦略
（Evolution Strategies: ES）
• Rechenberg（ベルリン工科大学）らにより，ランダム
サーチの考え方を発展させた「突然変異ー選択ス
キーム：(1+1)-ES」が考案される．
• ESでは，突然変異が主な操作．親ベクトルに平均０
の正規乱数ベクトルを加える．乱数を作るための共
分散パラメータも動的に変化させる．
(1+1)-ES
• 別紙参照
(m +l)-ES, (m, l)-ES
• (1+1)-ESを，Schwefelが改良．
• (m+l)-ES： m個の親からl個の子供を作り，親
(m個)＋子(l個)の中から，次の世代に残す個
体を選ぶ．
• (m, l)-ES： m個の親からl個の子供を作り，子
(l個)の中から，次の世代に残す個体を選ぶ．
(m + l)-ES
親
選択
子
（世代 k +1）
（世代 k ）
(m, l)-ES
親
選択
子
（世代 k +1）
（世代 k ）
(m + l)-ES, (m, l)-ESのアルゴリズム
Procedure ES
begin
k = 0;
P(k)の初期化（個体数m）
P(k)の評価
終了条件が満たされるまで繰り返す
begin
k = k + 1;
P(k-1)の中で組み換えてl個の個体からなる新しい個体群C(k)を生成
C(k)の中で突然変異、新しい個体群C’(k)を生成
C’(k)を評価
if (m, l)-ES then
C’(k)の中から選択をして，次の世代の個体群P(k) を決定する
else
P(k-1) U C’(k)の中から選択をして，次の世代の個体群P(k) を決定する
end
end
end
ESのバリエーション
1. (1+1)-ES：山登り法
2. (1, 1)-ES：ランダム探索法
3. (1+l)-ES, (1, l)-ES：近傍探索法
4. (m+ l)-ES：エリート保存による多点探索法
5. (m, l)-ES：多点探索法
ES における，組み換え演算
• 複数の親個体を扱う場合，ESではGAと同様に組み換
え演算を子個体の生成に用いることがある．この際，
実数空間での探索であることを考慮して，実数の連
続性などを活かした方法が考えられる．
以下に，一例を示す．
(1) 成分ごとにある親の値を継承する．
(2) 親の値の中点を子の値とする．
(3) 親のベクトルの内分点を子の値とする．
(4) 各成分ごとに親の値の内分点を子の値とする．
ESでの組み換え演算の例
(個体数：n=2の場合）
x2
xB
(1)
(3)
(4)
(2)
(1)
xA
xA, xB: 親個体
x1
進化的プログラミング
（Evolutionary Programming: EP）
• L.J. Fogelらにより，有限状態機械の自動合成手法と
して考案される．
• EPでは，突然変異が主な操作．親ベクトルに平均0の
正規乱数ベクトルを加える．異なる個体間の交叉は
行われないことが多い．
EPによる有限状態機械の進化 (1)
• 有限状態機械（Finite State Machine: FSM）とは有限個の内部状
態を持ち，入力として有限種のシンボルの系列を受け取り，状
態と入力シンボルに応じてシンボル系列を出力する機械．
0/
B
0/
1/
A
1/
1/
0/
C
EPによる有限状態機械の進化 (2)
• FSMは，1. 状態の集合Q、2. 初期状態q0Q、3. 入力シンボルの
集合I、4. 出力シンボルの集合Z、5. 状態遷移規則: I  Q  Q、
6. 出力規則 : I  Q  Z、により定義される．
• L. Fogelは，上記要素のうち，事前に問題により定まる 3., 4.を
除いた1., 2., 5., 6.を遺伝子として表現し，突然変異演算として，
状態の追加や削除，状態遷移規則や出力規則などのランダムな
変異を用いて探索を行う方法（EP）を考案した。
適応度は，FSMの望ましい出力として１ステップ先のシンボル
予測を考え，予測の成功率で定義した．
EPの特徴
EPでは
1. 選択は確率的に行われる*1。
2. ESは「個体の進化」の過程を模したものであるが，EPは「種の
進化」を手本としている．従って，一般に、組み換え演算は適
用しない．
*1: μ個の個体群中の個体（親）に対して突然変異を行い，μ個の個
体を生成する．この合計2μ個の個体群中でq-トーナメント選択
を行い，新しいμ個の個体を選択する．q-トーナメント選択では，
一つの個体akに対して2μ個中q個の個体をランダムに選択し，ak
よりも劣っている個体数wkをakのスコアとする．そして，スコ
アが良い者から順にμ個を残す方法．
EPの拡張
• D. FogelはEPを実数関数の最適化問題に適用できるよ
うに拡張．（別紙参照）
EPのアルゴリズム
Procedure EP
begin
k = 0;
P(k)の初期化（個体数m）
P(k)の確率的評価
終了条件が満たされるまで繰り返す
begin
k = k + 1;
P(k-1)の個体をそれぞれ突然変異させて，新しい個体群C(k)をm個生成
C(k)を確率的評価
P(k-1) U C(k)の中から選択をして，次の世代の個体群P(k) を決定する
end
end
end
講義内容（第7回目）
遺伝的プログラミング
1．個体の表現
2．遺伝的操作
3．アルゴリズム
4．関数自動定義（ADF）
5．進化的計算の相互比較
LISP入門
• LISP言語は，1960年頃John McCarthyの指導の
基に，MITのグループにより開発．
• 主要な使用例としては，コンパイラの作成，定理
の証明，数式処理，パターン認識，計算機による
ゲーム，ロボットなど．
LISPで扱うデータ
• LISPで扱うデータはS式（S-expression）
• S式は，要素を括弧でくくってリストとして表す．例
えば，A, B, Cの3つの要素を持つリストならば，
(A B C)
と書き表す．
さらにこのリストの最初の要素がX, Y, Zの3つの要素を
持つリストであれば，
((X Y Z) B C)
と表す．
また，リストを構成する文字列や数値をアトムと呼ぶ．
LISPの関数表現
• LISPでは，プログラムとデータが同一の形で表
現され，データ構造がプログラムとして実行され
，プログラムがデータとして処理される．
• S式を処理するLISPの関数の基本的な書き方は
，以下の通りである．
(関数引数1 引数2 … 引数n)
LISPの関数の例
1.
2.
3.
4.
5.
COND：条件判定を行う関数．述語を使って評価すべ
き式を選んでその値をCOND関数自体の値として返す
AND, OR, NOT, +, *, -, /：通常の論理演算や数値計算
を行う．
SETQ：第1引数の変数に第2引数の値を代入する．
DEFUN：色々な関数を組み合わせて作った機能に名
前を付けて，その機能を後から使えるようにする．
PROGN：任意個数の引数をとり，それらを左から順に
評価する．その結果は一番最後の引数の評価値を除
いて捨てられ，最後の引数の値がこの関数の値として
返される．
遺伝的プログラミング
（Genetic Programming: GP）
• J. Kozaにより，GAの遺伝子型を拡張し，木構造表現
が扱えるようにしたもの。
• LISPプログラムの自動生成が当初の目的．ロボット
などの制御プログラムに適用されることが多い．最
近では，アナログ回路の自動生成への適用がホット
な話題となっている．
GPにおける，個体の表現
GPでは，以下の特徴を持つLISPプログラム(S式)を個体とする。
1. LISPが扱う唯一の対象は記号表現（Symbolic expression: S式）
2. S式はアトムまたはリストから構成される．
3. アトムは、0, 3.14などの数字，もしくは、X, Y, ANDなどの文字
列で表された記号．
4. リストは，0を含む任意個数のアトムやリストを左括弧 ( と右括
弧 ) で囲んだものとして再帰的に定義される．
例：(), (1 2 4), (AND (X Y))など
5. LISPでは，入力としてS式を受け取り，それを評価した結果のS
式を出力する．（従って，LISPプログラムはS式である．）
6. (F x1 x2  xn)の形のS式が入力されると，まずx1 x2  xnが評価さ
れ、次に，その結果を引数とする関数Fが評価される．
個体の木構造表現 (1)
プログラム：(3+1)2
S式：( (+ 3 1) 2)
S式は木構造表現可能である．

+
3
2
1
個体の木構造表現 (2)
if  thenモデルの生成に適用可能。
if 3 then E1
else if 1 then E2
else if 2 then E4
E1
else E3
3
1
E2
2
E4
E3
GPにおける遺伝操作
• Mutation : ノードのラベル変更
• Crossover : 異なる個体間での部分木の交換
• Inversion : 同じノードから枝別れした部分木
同士の交換
S式における例
Mutation
(+ x y)  (+ x z)
Inversion
(/ (+ 3 1) (- 4 3) )  (/ (- 4 3) (+ 3 1) )
Crossover
(/ (+ 3 1) (- 4 3) )
( (- 3.14 2) (+ ( 1.5 8) 0.13 )
(/ ( 1.5 8) (- 4 3) )
( (- 3.14 2) (+ (+ 3 1) 0.13 )
Mutationの種類
1. 終端ノードから非終端ノードへの突然変異
新しい部分木の生成を伴う
2. 終端ノードから終端ノードへの突然変異
ノードラベルの付け換えのみ
3. 非終端ノードから終端ノードへの突然変異
部分木の削除を伴う
4. 非終端ノードから非終端ノードへの突然変異
子の数が同じ：ノードラベルの付け換えのみ
子の数が異なる：部分木の生成・削除を伴う
GPのアルゴリズム
Step1: ランダムに木構造GTYPE{gt(i)}を生成
Step2: 各GTYPE{gt(i)}の表現型PTYPE {pt(i)}に対して，適合度
{ft(i)}を求める．
Step3: 適合度の大きなGTYPEに対して一定数のペアを取り出す．
Step4: 取り出したペアに対してcrossoverを適用し，適合度の小さな
GTYPEと置き換える．
Step5: 各GTYPEに関して，ランダムにinversion, mutationを適用する．
Step6: 以上によって求められた新しいGTYPEを，次の世代の
{gt+1(i)}として，Step2へ戻る．
GPの設計
GPでは以下の５つの基本要素を設計することで，課題に適用する．
1. 非終端記号
非終端ノードで使う記号．LISPのS式での関数．
2. 終端記号
終端ノード（葉）で使う記号．LISPのS式でのアトム．
3. 適合度
4. パラメータ
交叉，突然変異の確率，集団サイズなど．
5. 終了条件
自動関数定義
(Automatically Defined Functions: ADF)
• 探索の過程で木（LISPのS式）が膨大になり探索効率が劣化す
るのを防ぐために，関数を自分自身で定義して効率的に利用す
る方法（ADF）が提案されている．
• 図において，右側の枝が通常の関数定義，左側の枝にはDEFUN
を用いた定義部があり，ここで定義された関数を関数名ADF0と
して右側の定義内で参照可能．
PROGN
• 交叉は，ADF0の定義部分は
DEFUN
VALUES
ADF0の定義部分どうし，
右側の関数定義本体は
引数リスト
ADF0
VALUES
右側の定義部分どうしで
ADF0の
関数定義
交叉を行う．
定義本体
本体
進化的計算の相互比較
GP
個体表現
造
パラメータ調整
なし
適応度
ムと
GA
離散値表現
なし
ES
連続値表現
EP
連続値表現
共分散行列
木構
LISPのS式
分散
目的関数値を目的関数値を目的関数値をプログラ
スケーリングそのまま使用スケーリング
して機能評価
突然変異
補助的探索法主要な探索法
唯一の探索法
補助的探
索法
交叉
探索法
主要な探索法
補助的探索法
使わない
主要な
突然変異の比較（イメージ）
GA
どこに変異するかは等確率
-2 -1 0 1 2
親に近い程、変異する確率は高い
（正規分布に従う）
ES, EP
0.0
ボールドウィン効果
(Baldwin Effect)
• 生物の遺伝機構では個体が後天的に適応や学
習により獲得した能力は子孫には遺伝しない
と云われている．
• 一方，Baldwinは，仮に獲得形質が遺伝する
ことがなくても適応や学習が進化を誘導・加
速する可能性がることを指摘した．この効果
をボールドウィン効果（Baldwin effect）と呼
ぶ．
講義内容（第8回目A）
組合せ最適化
1．TSP
2．Nクイーン問題
3．ナップサック問題
組合せ最適化問題の例
例：巡回セールスマン問題
（Traveling Salesman Problem: TSP）
ある一人のセールスマンが幾つかの都市を次々に一度ず
つ訪問して，最後に出発点に戻らなければならないときに，
最短の距離で回る巡回路を決定する問題（プログラム例）
都市の数がnの時，n!/2n通りの組合せ
例）５都市：12通り．１０都市：181440通り．
（都市数の多項式オーダーの解法は発見されていない．）
組合せ最適化問題の例
例：Nクイーン問題
• Nクイーン問題とは，n  nのマスの中に，n個のクイ
ーンを，どのクイーンも互いに効きが当たらないよ
うに並べる問題である．但し，チェス盤の中で，ク
イーンは縦，横，斜めに関してどこまでも進むこと
ができると仮定する．
• 10クイーン問題の場合，10個のクイーンを10  10の
チェスボードに並べる組合せは，対称性などを無視
して単純に数え上げると約17兆通りになる．この組
み合わせの数を力ずくで全部調べると，1秒間に1億
通りの組み合わせを計算できる超高速コンピュータ
で処理したとしても約5時間かかる．
Nクイーン問題の解答例
図1 .1　5 クイーンの解答例１
図1 .2 5クイーンの解答例２
組合せ最適化問題の例
例：ナップサック問題（Knapsack problem）
• ナップサック問題とは，ナップサックの重量制限
の基で，それぞれ異なる重量と価値の品物を
ナップサックに詰め込むとき，総価値が最大にな
るような品物の組合せを求める問題．
TSPにおけるコード化と交叉方法 (1)
順序表現と交叉
1. 9都市の順序表現
9都市に対する順序リストをC = (1 2 3 4 5 6 7 8 9)とす
れば，巡回路 1 – 2 – 4 – 3 – 8 – 5 – 9 – 6 – 7 はリストl
としてl = (1 1 2 1 4 1 3 1 1)と表現される．
順序表現の利点は，1点交叉が使用可能であること．
TSPにおけるコード化と交叉方法 (1)
順序表現と交叉
2． 9都市の順序表現による交叉
9都市に対する順序リストをC = (1 2 3 4 5 6 7 8 9)とする．
例えば，親1，親2
親1： (1 1 2 1 4 1 3 1 1)
親2： (5 1 5 5 5 3 3 2 1)
は，それぞれ巡回路
1–2–4–3–8–5–9–6–7 5–1–7–8–9–4–6–3–2
に対応する．これらの親1，親2が，交叉点｜により1点交叉を行え
ば，以下のような子1，子2が生成される．
子1： (1 1 2 1 5 3 3 2 1)
子2： (5 1 5 5 4 1 3 1 1)
これらの子は，それぞれ巡回路
1–2–4–3–9–7–8–6–5 5–1–7–8–6–2–9–3–4
に対応し，合理的な巡回路になっている．
TSPにおけるコード化と交叉方法 (2)
パス表現と交叉
1. 9都市のパス表現
例えば，巡回路 1 – 2 – 4 – 3 – 8 – 5 – 9 – 6 – 7 は，
単に (1 2 4 3 8 5 9 6 7 )と表現される．
パス表現に対して1点交叉を行うと，「全ての都市を
一度ずつ訪問する」という制約を満たさない子が生成さ
れる可能性が高い．この問題に対処するために，部分
一致交叉，順序交叉，周期交叉などの手法が提案され
ている．
TSPにおけるコード化と交叉方法 (2)
パス表現と交叉
2．部分一致交叉
（Partially Matched Crossover: PMX）
1985年に，Goldbergらにより提案された手法．
親1から巡回路の部分列を選び，親2からでき
る限り多くの都市の順序と位置を保存すること
により，子1，子2を生成させる．巡回路の部分
列は2つの交叉点をランダムに選ぶことによっ
て選択される．
TSPにおけるコード化と交叉方法 (2)
パス表現と交叉
例） 9都市のパス表現に対するPMX
例えば，2つの交叉点｜が選択された
親1： (1 2 3 4 5 6 7 8 9)
親2： (4 5 2 1 8 7 6 9 3)
に対して，まず，2つの交叉点間の部分を交換して
子1： (x x x 1 8 7 6 x x)
子2： (x x x 4 5 6 7 x x)
を生成させる．但し，現時点ではxは未定．また，この変
換は一連の写像：
1 4，8 5，7 6，6 7
を定義していると考える．
TSPにおけるコード化と交叉方法 (2)
パス表現と交叉
次に，子1，子2のxの部分に対して，それぞれ，親1，
親2の対応する部分からまだ選択されていない都市の
みを代入すると
子1： (x 2 3 1 8 7 6 x 9)
子2： (x x 2 4 5 6 7 9 3)
が得られる．ここで，子1の最初のxの1は既に使用され
ているので，写像1 4を適用して4になる．他のxに関
しても同様に写像関係を適用して，最終的に以下に示
す子1，子2 を得る．
子1： (4 2 3 1 8 7 6 5 9)
子2： (1 8 2 4 5 6 7 9 3)
TSPにおけるコード化と交叉方法 (2)
パス表現と交叉
3．順序交叉
（Ordered Crossover: OX）
1985年に，Davisにより提案された手法．
親1から巡回路の部分列を選び，親2から都市
の相対的な順序を保存することによってを生成
する．
TSPにおけるコード化と交叉方法 (2)
パス表現と交叉
例） 9都市のパス表現に対するOX
例えば，2つの交叉点｜が選択された
親1： (1 2 3 4 5 6 7 8 9)
親2： (4 5 2 1 8 7 6 9 3)
に対して，まず最初に，2つの交叉点間の部分
がそのまま子1，子2にコピーされる．
子1： (x x x 4 5 6 7 x x)
子2： (x x x 1 8 7 6 x x)
TSPにおけるコード化と交叉方法 (2)
パス表現と交叉
次に，親1の2番目の交叉点からはじめて，まだ現れ
ていない都市のみを，親2からその順番でコピーする．
2番目の交叉点からの親2の都市の順列は
9–3–4–5–2–1–8–7–6
なので，既に現れている都市4，5，6，7を除けば
9–3–2–1–8
を得る．2番目の交叉点からこの順に子1の残りの部分
を決定して，以下に示す子1が得られる．
子1： (2 1 8 4 5 6 7 9 3)
子2も同様の手続きで得られる．
子2： (3 4 5 1 8 7 6 9 2)
TSPにおけるコード化と交叉方法 (2)
パス表現と交叉
4．周期交叉
（Cycle Crossover: CX）
1987年に，Oliverらにより提案された手法．
各都市とその位置はいずれかの親から定めら
れるような方法で子が生成される．
TSPにおけるコード化と交叉方法 (2)
パス表現と交叉
例） 9都市のパス表現に対するCX
親1： (1 2 3 4 5 6 7 8 9)
親2： (4 1 2 8 7 6 9 3 5)
に対して，親1から最初の都市を取り出して子を生成．
子1： (1 x x x x x x x x)
子の全ての都市は，いずれかの親の同じ位置から取ら
れるので，次の都市は，選ばれた都市1の下にある親2
の都市4になる．
子1： (1 x x 4 x x x x x)
TSPにおけるコード化と交叉方法 (2)
パス表現と交叉
次に，都市4の下にある親2の都市8が選ばれる．
子1： (1 x x 4 x x x 8 x)
同様にして，都市8の下にある親2の都市3，さらにその
次の都市は2となるが，都市2の選択後には，すでに選
択された都市1になるので，サイクルを完了させて
子1： (1 2 3 4 x x x 8 x)
を得る．ここで，子1の残りの都市は親2の対応する都
市をそのまま入れて，以下の結果を得る．
子1： (1 2 3 4 7 6 9 8 5)
子2に対しても同様にして，
子2： (4 1 2 8 5 6 7 3 9)
が得られる．
演習3（GAの応用）
1．TSP，Nクイーン問題，ナップサック問題の中からいずれか一つを選
択し，GAを用いた解法を設計せよ．（染色体の定義，交叉方法，突然
変異方法，適合度関数の定義，個体数，交叉率，突然変異率などに関
して検討すること．）
2．上記設計したプログラムを作成せよ．
3．上記作成したプログラム実行し，世代数と最大適合度の関係，および
世代数と平均適合度の関係を図示せよ．
4．上記世代数と最大適合度，および世代数と平均適合度の関係のグラフ
をもとに考察をせよ．余裕があれば，他の手法を使った解法との比較
を行うこと．
講義内容（第8回目B）
関数最適化
1．最適化問題
2．上下限制約のみの最適化問題
3．線形制約最適化問題
4．多目的最適化問題
最適化問題
(optimization problem)
• 最適化問題は，目的関数(objective function)
f(x1, x2, …, xn)
を，制約条件(constraints)
x1,x2,...,xn S  X
のもとで最小（最大）にする解を求める問題．
但し， f(x1, x2, …, xn)は，基本空間Xの変数x = (x1, x2, …,
xn) Xの全ての有限な値に対して定義される実数値関数
. Sは，決定変数xに対する基本空間Xの部分集合で，制
約条件を満たすxの集合を表し，実行可能領域(feasible
region) ．
最適化問題の分類
1. X = Rn (n次元実数空間)で，目的関数f(x)と制約条件が
全てxに関して線形関数：線形計画問題
2. 上記以外：非線形問題
特に，
(1) 目的関数f(x)が2次関数で制約条件が全て線形
2次計画法：有限回数の探索により最適解を求める計
算手法が存在
(2)目的関数f(x)が凸関数で実行可能領域が凸集合
凸計画法：乗数法，準ニュートン法などの解法が存在
最適化問題の分類
3. 非凸計画問題，関数の連続性や微分可能性が満たされ
ない一般の最適化問題
有効な最適化手法は存在しない→ランダム探索
4. XあるいはSが離散集合のような組合せ的構造
組合せ最適化問題：分岐限定法，動的計画法
→組合せ爆発の問題
大規模で多峰性を有する探索空間や，実行可能領域が
離散集合である場合などへの高速近似解法としてGAが
有効
ランダム法
• ランダム法は，問題の性質は全く利用しないで，基本空
間Xから解xを無作為(random)に多数個選びだし，これら
の解の実行可能性を調べ，実行可能解の中で目的関数
値を最小にするものを準最適解にする．
• 探索回数を無限大まで許せば，確率1で，大域的な最適
解が得られる．
上下限制約のみの最適化問題
• GAは，各変数xiに対する上下限制約のみの最適化問題
minimize f(x1,…, xn)
subject to li  xi  ui , i  1,...,n
に対しての適用は比較的容易．
n次元変数x = (x1,…, xn) の各要素を2進数で表現してGA
を適用．
上下限制約のみのn変数の最適化問題に対する
2進文字列表現
• 変数xiの上下限制約 li  xi  ui , i  1,...,n に対して，解の
精度（有効桁数）に応じて，各変数x1,…, xnに必要なビット
数m1,…, mnを求め，各変数xi のビット数mi, i = 1,…,nに対
応する部分2進も次列を順に並べてつなぎ合わせた総ビ
ット数m = m1+…+ mnの2進文字列表現を行う．
mビット
1 0 … 1 0 …… 1 0 … 0 1
m1ビット
x1
mnビット
xn
De Jongの5種類の関数最小化問題
（着目した特徴）
1.
2.
3.
4.
5.
6.
連続性/非連続性
凸性/非凸性
単峰性/多峰性
2次関数/ 2次でない関数
低次元/高次元
決定的/確率的
De Jongの5種類の関数最小化問題（図5.2）
3
f1 
x
 5.12  xi  5.12
2
i
i 1
f 2  100( xi2  x2 ) 2  1  x1 2
 2.048  xi  2.048
5
f3 
 integer( x )
 5.12  xi  5.12
 ix
 1.28  xi  1.28
i
i 1
30
f4 
4
i
 Gauss(0,1)
i 1
25
f 5  0.002 

j 1
1
2
j

i 1
( xi  aij ) 2
 65.536  xi  65.536
De Jongによる，オンライン・パフォーマンス
•
環境eでの戦略sのオンライン・パフォーマンスxe(s)は，
次式で定義される.
1
xe s  
T
T
 f t 
e
t 1
但し，fe(t)は世代tでの適合度を表す.
•
オンライン・パフォーマンスは，第1世代から第T世代ま
での適合度の平均値となる.
De Jongによる，オフライン・パフォーマンス
•
環境eでの戦略sのオフライン・パフォーマンスxe*(s)は，
次式で定義される.
xe* ( s) 
1
T
T

f e* t 
t 1
但し，fe*(t) = best{fe(1), fe(2), …, fe(t)}
•
オフライン・パフォーマンスは，tまでの最良適合度fe*(t)
の世代平均を表す.
実験結果 (1)
•
•
単峰性の関数：エリートモデルはオンライン, オ
フライン・パフォーマンスの両方を改善させる.
多峰性の関数：エリートモデルはオンライン, オ
フライン・パフォーマンスの両方を改悪させる.
→エリートモデルは，全体的な視野を犠牲にし
て局所的探索を改善する.
実験結果 (2)
•
エリートモデルは，低次元の単峰性関数に関しては，
期待値モデルよりもやや良い結果を与えた. 一方，期
待値モデルは，関数に対して，オンライン, オフライン・
パフォーマンスの両方において， SGAやエリートモデ
ルよりも良い結果を得た.
•
エリート期待値モデルは，単峰性関数に関してはかな
りの改善が見られた. 一方，多峰性関数に対するパフ
ォーマンスは期待値モデルよりも良くなかった.
多峰性対策
•
•
•
前選択：交叉で生じた子の適合度が2つの親のいずれ
かよりも良ければその親と入れ替える.
クラウディング：新しくできた個体を他の個体と入れ替
えるかどうか決めるのに，親との比較ではなく，コードと
して最も似ているものと比較して決める.
シェアリング：多くの点が集中している部分での関数値
には比較的小さい重みを掛け，孤立している点の関数
値には相対的に大きい重みを掛けることにより，関数
値の分布の均一化を図る.
シェアリング関数
• コード化された文字列si, sj間の距離dij = d(si, sj)
を考えることにより
(1) 0  sh(d)  1, d  0,)
(2) sh(0)  1
(3) lim sh(d)  0
d
を満たす関数sh( )をシェアリング関数(sharing
function)と定義する.
シェアリング関数の例
• べき乗のシェアリング関数の例：


1  d 
sh(d)     share 

 0
但し, sshare, は定数.
d   share
others
 > 1,   1,  < 1に対する図示：図5.3
シェアリング関数による適合度の修正
• 個体siの適合度関数をf(si), 個体群サイズをNとし
て, 距離とシェアリング関数が選ばれると, シェア
リングにより次式により適合度を修正する.
f (si )
f (si ) :
mi
N
m i   sh(d(si , sj ))
j 1
シェアリングの適用先
•
•
•
最適化問題における初期収束の防止.
分類システムにおける多様性の維持.
局所解の分布の検出.
制約問題の数値最適化GA
•
線形制約最適化問題を対象として, Michalewiczらは,
制約問題の数値最適化GA (GENOCOP: Genetic
algorithm for Numerical Optimization for Constrained
Problem)を提案.
•
GENOCOPの特徴：
(1) 制約式の集合から等式制約を除去する
(2) 全ての個体が制約集合を満たすように特別な遺伝的
操作を設計する
GENOCOPの評価
•
非線形目的関数として, 実際のオペレーションズ・リサ
ーチ問題に現れる関数(A(x), B(x)), 主として最適化の
教科書に見られる関数(C(x), D(x)), および, 最適化手
法に対する難しいテストケース(E(x), F(x))を用いて
GENOCOPを評価 (図5.4, 表5.3).
•
非線形最適化の代表的な手法の一つとして有名な準
ニュートン法のアルゴリズムに基づく非線形最適化の
汎用プログラムである GAMS/MINOSとの比較 (表5.4)
多目的最適化問題
•
多目的最適化問題(multiobjective optimization
problem: MOP)とは, k個の互いに競合する目的関数
 f1 x1 , x 2 ,...,x n 

:

 f x , x ,...,x 
 k 1 2
n
を, m個の不等式制約条件
 g1 x1 , x2 ,...,xn   0

:

g x , x ,...,x   0
 m 1 2
n
のもとで最小化する問題.
パレート最適解
 
•
x *  X に対して, fi x  fi x* , i  1,...,k で, しかも,
あるjについてfj(x) < fj(x*)となるような x X が存在し
ないとき, x*をパレート最適解と呼ぶ. (図5.5)
•
一方, 単一目的の最適化問題をいかなる現存する最適
化手法で解いても, 凸計画問題以外では局所的な最適
解しか得られないので, MOPに対しても局所的パレート
最適解の概念が提案されている.
局所的パレート最適解
•
x *  X が, X  Nx*,   において, パレート最適解で
あるような実数 > 0 が存在するとき, x*をMOPの局所
的パレート最適解であるという.
但し, N(x*, )はx*の近傍を表し
N x * ,  x Rn | x  x *  
と定義されている.


パレート最適解の求め方
•
•
多目的最適化問題のパレート最適化を求めるための
手法としては, もとの問題を何らかの工夫により単一目
的の問題に変換する, スカラー化手法が知られている.
代表的なスカラー化手法として,以下の手法が知られて
いる.
(1) 重み係数法
(2) 制約法
(3) 重み付けミニマックス法
(4)重み付けlpノルム法
講義内容（第8回目C）
機械学習
1．GA機械学習システムとは
2．ミシガンアプローチ
3．ピッツアプローチ
GA機械学習とは
• 機械学習システムでは，複雑なシステムを学習
対象とするとともに，システムに対する適切な出
力を実現する必要がある．
• 機械学習システムの中で，学習手段としてGAを
用いるものが，GA機械学習である．
機械学習が克服すべき問題
• データはノイズを含む．また，過去に経験していない新し
い状況に対応する必要がある．従って，ロバスト性，適応
能力が要求される．
• リアルタイムの動作が要求される．
• ゴールは間接的，あいまいな場合が多い.
• システムの評価をどのルールにフィードバックするかが
困難.
機械学習システムのルール形式
• システムに外部（環境）からメッセージを入力する
と,内部の多数の
if <条件> then <アクション>
形式のルールが起動して出力を決定.
GA機械学習法の代表例
• ミシガンアプローチ（Holland）
ルール１つを１個体と見なし，ルールの集まりである個体
群に対してGAを適用.
個体： if 条件 then アクション
• ピッツアプローチ（De Jong）
分類子一つ一つを遺伝子と見なし，分類子の集まりを個
体として扱う.
個体： if 条件 then アクション; …; if 条件 then アクション
ミシガンアプローチ
• クラシファイアシステム（CS）とも呼ばれる.
1976年にHollandにより提案される.
• ルールは1セットのみ存在.
個体1： if 条件 then アクション
個体2： if 条件 then アクション
：
個体N： if 条件 then アクション
• ルールの条件部
<条件> = {0, 1, #}n, #: ワイルドカード
CSシステムの構成
メッセージ
検出器
メッセージ分類子リストルール生成
(GA)
リスト
と信頼度
環境
メッセージ
効果器
信頼割り当て
CSシステムの構成
1.
2.
3.
4.
5.
6.
検出器：入力データをCSシステムの中で用いられるコード（メッセ
ージ）に変換.
効果器： CSシステムの出力を外部環境が要求する形のコードに
変換
メッセージリスト：メッセージを一時的に貯めておく記憶領域.
分類子リスト：CSシステムを構成するif～thenルールの候補を貯
めておく記憶領域.
各分類子には信頼度と呼ばれる属性が付属する.
信頼割り当てシステム：有用なルールには信頼度を付加.
逆に，望ましくないルールからは信頼度を減少.
ルールの生成：現在のルールの中の優れたものの組合せを基本
として新しいルールの生成をGAで行う.（バケツリレー方式）
信頼割当のアルゴリズム
手順1：環境から情報が入ってきたら検出器がその情報を0，1系列にコ
ード化してメッセージリストMLにポストする.
手順2：分類子リストCLにある分類子一つ一つについて，条件部が満た
されるメッセージがMLの中にあるかチェックする（条件マッチング）.
該当する分類子を集めて集合Mを構成する.
手順3：マッチした分類子cのbid（賭け）は
R(c)
Bc,k  
p(c,k)
b
とする.p(c,k)は分類子cの信頼度，bは条件部のビット長を表す定数，
R (c)は条件部の中の#でないビット数（特定度）を示す.
信頼割当のアルゴリズム
Mの中の各分類子の bidを計算し，勝者を決める.このとき勝者cは
bidを支払うため信頼度を減らす.
p(c, k) = p(c, k - 1) - B(c, k)
一方、前回cにメッセージを送った分類子sにここで支払ったbidを分
配する. sがcにメッセージを送ったとすると
p(s, k) = p(s, k - 1) + B(c, k)/n
ここでnはcにメッセージを送った個対数である.
手順4：MLをクリアする.
手順5：M’の中の各分類子のbidを支払い，そのbidの値はそれぞれの
分類子の入力とマッチする出力を持つ分類子の中で均等に分類さ
れる. M’の中の分類子は活性化し，後件部に生じる新しいメッセー
ジをMLにポストする.
信頼割当のアルゴリズム
手順6： MLのメッセージを解釈し，競合する場合は矛盾を解決してから
出力インタフェースに出力する.
手順7：環境から利得があればそれを，出力を行った分類子の信頼度に
分配して与える.
手順8： GAを1世代実行する.
a) Mの中の個体の平均強度を計算.ここでのGAでは，各分類子を個
体とし，それのもつ信頼度を適合度として行う.
b) ルーレット選択を行い，交叉を実行.
c) 突然変異.
バケツリレーアルゴリズムの問題点
• 有効なチェーンを育てるのに時間がかかる.
• 壊れやすい.
ピッツアプローチ
• 1つの全体的機能をもつルール群をまとめて1つの個体と
して扱い，内部に多数のルール群を抱え並列的に評価を
行う.
• 個体単位で良いものを競わせることができるため，ミシガ
ンアプローチに比べて， GAをより直接的に適用させるこ
とができる.
• 各個体は「ルール」という遺伝子をもち，ルール単位で遺
伝的操作を行う.
ピッツアプローチの問題点
問題点1：ルールを遺伝子として操作すると交叉はルール組
換えを行うことになり，突然変異は新しいルールへの置
換えを行うことに相当する.従って，ルールが比較的少な
いと初期収束する可能性が高くなる.
問題点2：ルールの個数は固定できないのが普通である.こ
れは，単純GAの適用を困難にする.
問題点の対策
対策1：各ルール自身の中でも交叉可能にし，多様性を持た
せる工夫を行う.
対策2：冗長なルールを付加し，見掛け上同じ長さの個体に
する.
意味のないルール生成排除
方法1：意味を持つ個体しか生成しないように交叉，突然変
異，逆位などの操作自体の方法を工夫する.
方法2：特に工夫しない標準的操作を行っても意味のない個
体が生じないようにコードに制約を加える.
その他の応用
1．ゲーム
2. CG
3. 音楽
囚人のジレンマゲーム
• ２人（p1, p2）の共犯者が別室で取調べを受けている．２人とも黙秘
すれば証拠不十分による軽い刑罰で済み，逆に２人とも白状すればそ
れなりの刑罰に服さなければならないことを２人は知っている．取調
べ官は白状させるために，次のような取引を別々に隔離されている共
犯者に持ちかける．もし，１人が黙秘しているときに他方が相手を裏
切って自白すれば見返りに大きな便宜を図り，自白しなかった他者に
は２人分の重刑を負わすというものである．このときの利得表は以下
のような大小関係を持つ．
表１囚人のジレンマゲーム
p2：黙秘p2：自白
p1：黙秘 (c, c) (a, d)
p1：自白 (d, a) (b, b)
但し，a < b < c < d
CGの応用例
• グロースモデルの世界（河口洋一郎）
例１：人工生命体の未来都市
例２：The Growth Model
例３：シミュレーション画面の例
SBART：模擬育種ベースのCG （畝見）
/
*
abs
-0.33
+
0.12
*
min
abs
cos
cos
min
0.74
XY0
YX0
XY0
YX0
GPを用いて、木構造の数式を進化。その数式に対応したCGが生成。
画面の例
Creatures：K. Sims
進化する仮想生物
（CGアニメーション）
GenJamシステム (John A. Biles)
MIDI sequence
Bass
Piano
Manteca
Drum
Rake
solo
Progression
GenJam
good/bad
phrase
population
measure
population

Download Report