• 検索結果がありません。

九州大学学術情報リポジトリ Kyushu University Institutional Repository 遺伝的アルゴリズム 高木, 英行九州大学大学院芸術工学研究院 出版情報 : バージョン : 権利関係

N/A
N/A
Protected

Academic year: 2022

シェア "九州大学学術情報リポジトリ Kyushu University Institutional Repository 遺伝的アルゴリズム 高木, 英行九州大学大学院芸術工学研究院 出版情報 : バージョン : 権利関係"

Copied!
73
0
0

読み込み中.... (全文を見る)

全文

(1)

九州大学学術情報リポジトリ

Kyushu University Institutional Repository

遺伝的アルゴリズム

高木, 英行

九州大学大学院芸術工学研究院

http://hdl.handle.net/2324/2928255

出版情報:2000-02 バージョン:

権利関係:

(2)

Part III

遺伝的アルゴリズム

高木英行

(3)

1

目 次

1章 遺伝的アルゴリズム入門 3

1.1 最適化問題と探索空間 . . . . 3

1.2 進化的計算 . . . . 5

1.3 探索手法としてのGA . . . . 6

1.4 GA演算 . . . . 7

1.4.1 GA演算:選択 . . . . 8

1.4.2 GA演算:交差 . . . . 9

1.4.3 GA演算:突然変異. . . . 10

1.5 GA演算の具体例 . . . . 11

1.6 簡単な組合せ最適化問題の例. . . . 15

2章 ファジィシステムと遺伝的アルゴリズム 19 2.1 ファジィ理論とファジィシステム . . . . 19

2.2 ファジィシステム . . . . 20

2.2.1 ファジィシステムのアプローチ . . . . 20

2.2.2 数式ベースの制御とルールベースの制御 . . . . 21

2.2.3 IF部(前件部)の設計 . . . . 22

2.2.4 THEN部(後件部)の設計 . . . . 23

2.2.5 ファジィ推論と統合 . . . . 24

2.3 ファジィシステムのための遺伝的アルゴリズム. . . . 26

2.3.1 GAによるFSの設計. . . . 26

2.3.2 GAによるFSの設計の実応用. . . . 28

2.4 遺伝的アルゴリズムのためのファジィシステム. . . . 29

2.4.1 FSによるGAパラメータの最適化 . . . . 29

2.4.2 GA演算のファジィ化 . . . . 30

(4)

2

2.4.3 その他 . . . . 32

3章 ニューラルネットと遺伝的アルゴリズム 33 3.1 生物から学習の仕方を学ぶ . . . . 33

3.2 人工ニューラルネットワークの型 . . . . 34

3.2.1 feed-back型 . . . . 34

3.2.2 feed-forward型 . . . . 35

3.3 学習アルゴリズム . . . . 35

3.3.1 教師なし学習 . . . . 35

3.3.2 教師あり学習 . . . . 37

3.4 非線形関数近似のメカニズム. . . . 39

3.5 ニューラルネットと遺伝的アルゴリズム . . . . 41

3.5.1 GAによるNN学習と設計 . . . . 41

3.5.2 GAによるNN設計の実応用. . . . 43

3.5.3 NNを用いたGAフィットネス関数 . . . . 44

4章 感性と遺伝的アルゴリズム 47 4.1 コンピュータの最適化能力と人間の評価能力 . . . . 47

4.2 インタラクティブ進化アート. . . . 49

4.3 3次元CGライティングデザイン . . . . 51

4.3.1 素人のデザイン技術≠素人の評価能力 . . . . 51

4.3.2 インタラクティブGAライティングシステム. . . . 53

4.3.3 CGライティング:手作業vs. インタラクティブGA . 54 4.4 工業デザイン . . . . 55

4.5 音楽 . . . . 55

4.6 モンタージュ . . . . 56

4.7 実際のインタラクティブ進化計算の世界 . . . . 57

付 録A 演習問題のヒント 61

(5)

3

1 章 遺伝的アルゴリズム入門

1.1 最適化問題と探索空間

実社会では最適化問題が山とある.回路基板をなるべく小さくなるよう素 子配置をする,なるべくパイロットや客室乗務員の手配が楽になるよう人員 配置計画をする,どのバスをどの路線にどの順で回すかのスケジュールをす る,事故の遅れを最も早く回復するための臨時列車ダイヤを組む,最も早く 安定化するようなコントローラを設計する,あるいは,制御する,雑音が最 小になるようなフィルタ係数を求める,投資効率が最大かつリスク最小にな るような投資株式の組合せを考える,などなど.

これらいろいろな分野で使われている最適化問題を,最適解の探索という 観点から眺めてみよう.最適という限り,何か善し悪しの物差しがなければ,

探索ができないので,この物差しをf(x1, x2, ..., xn)としよう.この f()が最 適になるようなxiを求めることが最適化である.このxiは,ある時はフィル タの係数であったり,ある時は銘柄別の投資比率だったり,ある時は列車を発 車させるか運休するかのON/OFFであったりする.

f(x1, x2, ..., xn)が決まると,図1.1のような探索空間を描くことができる.

縦軸が最適化を測る物差しf()で,横軸は探索する変数である.図では,x1x2しか書いていないが,n次元まであるものとして見てもらいたい.最適 化とは,一般的にこのような非線形な探索空間上で最適化の物差しがベスト になる座標(x1, x2, ..., xn)を探し当てることである.

   

では,どのようにして最適な座標を探し出したらよいのであろうか.「そこ のへっこんでいる所」などと言わないでいただきたい.図1.1は実際には見え ずに,(x1, x2, ..., xn)を与えれば,その時のf(x1, x2, ..., xn)の値が1つ求め られるだけなのだから.もちろんいっぱい探し回ればこの探索空間の形状は

(6)

4 第1章 遺伝的アルゴリズム入門

x1 x2

y

図 1.1: 探索空間の例

だんだん見えてくるが,それだけ虱潰しに探すのでは実用的ではない.実用 的には,例えベストではなくとも,よりベターな答を実用的時間内に見つけ だすことが要求される.

よく使われている代表的な方法は,この探索空間の部分的な傾き情報を求 めて,現在の解座標よりf()が大きくなる(あるいは小さくなる)方向へ探索 のコマを進める方法,勾配法である.代表的な勾配法である最急降下法の戦 略は,深い霧に包まれた山中で道に迷った場合に例えると,「先が見えないの だから,足下を見て低くなる(高くなる)方向にとにかく進もう.いつかは,

下界(山頂)に着くだろう」,というものである.時には窪地(小山)にたど り着いて,必ずしも最も低い下界(高い山頂)に着く保証はないが,むやみに 歩き回る(ランダムサーチ)よりは,頼りになる.基本的に探索で歩き回るの は一人(一点)である.

これに対し,グループで連絡を取り合いながら探索するという,異なる戦 略もある.複数の斥候を各地に派遣して連絡を受け,全体の情報を分析しな がら次の探索地点を斥候に指示するような方法である.本章で解説する遺伝 的アルゴリズム(GA)を最適化手法としてとらえると,GAはこのタイプの 探索手法である.

(7)

1.2. 進化的計算 5

1.2 進化的計算

生物の進化にヒントを得た探索や最適化のアルゴリズムを,進化的計算(evo- lutinary computation)とか進化的アルゴリズムという.進化的計算の特徴は その探索や最適化が次のように行われる点にある.

(1) 多数の探索点もしくは多数の解候補に基づいている(個体群を基にした 探索).

(2) 交差や突然変異のような生物進化にヒントを得た演算が使われる.

(3) 確率的探索と確率的演算に基づいている.

(4) 勾配法における探索空間の微分情報のように,探索空間に関する情報を ほとんど用いない.

進化的計算論の代表的なパラダイムには,GA(遺伝的アルゴリズム),ES

(進化的戦略),EP(進化的プログラミング),GP(遺伝的プログラミング)

がある.

GAは,通常ビットコーディング(遺伝子型)した染色体で解を表現し,選 択,交差,および突然変異の遺伝的演算を用いて,この遺伝子型空間上のよ り良い解候補を探索する.交差が最も支配的な演算である.

ESは,実数コーディング(表現型)した染色体で解を表現し,交差,突然 変異のES演算を用いて,この表現型空間上のより良い解を探索する.実数の 突然変異は白色雑音を加えることで行われ,大局的最適解に収束するようガ ウス分布の分散パラメータを制御する.

EPはGAに似ている.主な違いは突然変異が唯一の演算であることであ る.EPでは実数コーディングが行われ,突然変異ではEPコードの構造(長 さ)を変化させることがある.

GPで新しい構造を作り出すために,木構造コーディングが用いられる.交 差は数値に対してではなく,木構造の枝に対して行われる.ニューラルネット (NN)への応用について関係を見てみよう.GAとESはシナプス結合の最適 化,つまりNN学習に用いられ,GPはNNの最適構造を決定する.

最近は,これらのパラダイムの交流が進んでいて,上記のように単純な構 図ではなくなってきている.たとえば,実数コーディングのGAなど普通に

(8)

6 第1章 遺伝的アルゴリズム入門

使われている.本章では,これらの代表としてGAに焦点を絞り,どのよう に解を探索するかを見よう.

1.3 探索手法としての GA

GAを理解するにはGAでよく使われる技術用語をよく理解しておく必要 があるので,これらのいくつかを表1.1に示す.

表 1.1: GAでよく使われる用語

染色体(chromosome タスクの解を表すベクトル

遺伝子(gene 染色体を構成する各解

選択(selection 次世代の親もしくは子供染色体を選ぶこ

個体(individual 各染色体,解ベクトル

個体群(population 全個体

個体数(population size 染色体(個体)の数

フィットネス関数 各解がタスクの解としてどの程度適合し ているかを示す評価関数

表現型(phenotype 解の数値表現 (例)赤,13cm45kg

遺伝子型(genotype 探索空間で用いられる解のビット表現 

(例)“011” “01101.”

GAを探索手法として用いる場合,長所と短所がある.

長所は,(1)最適条件(解)近傍へすばやく収束し,(2)複雑な探索空間で あっても優れた大域的探索能力を示し,(3)勾配情報を用いることのできない 探索空間へも応用が可能,という点にある.

第1と第2の長所は,個体群に基づいた多点探索による.図1.2はこの状況 を示している.勾配法では現在の探索点の勾配情報を用いて次の検索点を決 定する.反対にGAでは現在の多数の探索点における適応度(評価値)を用 いて,多数の次の探索点を決定する.勾配情報のみを用いたとき,次の探索 点は現在の探索点の局所的な幾何学情報に強く影響を受けてしまう.この結 果,時には局所最小解に陥ることもある(図1.2参照).一方,GAでは探索 空間上の至る所に広がった現在の探索点の評価値を用いて次の探索点を決定 する.そして,局所最小解から抜け出すために突然変異演算も用意している.

これが上述の長所の理由である.

(9)

1.4. GA演算 7

勾  

配  

法 G  

A

第  

1  

世  

代  

目 第 

3  

世  

代  

第  

5  

世  

代   第 目

  1  

世  

代  

目 第

  3  

世  

代  

図 1.2: GA探索と勾配探索

GAにおける短所は最適解近傍での収束速度が遅いことである.GA探索は 勾配情報を用いず,GA演算のみを用いることによる.この2つの探索方法を 組み合わせるという提案がいくつかなされている.

1.4 GA 演算

図1.3と図1.4は,それぞれGA処理過程とデータの流れを示している.図 1.4では,6つの解がビットコードで表現されている.これは遺伝子型である.

このビットコードの解表現は,応用タスクで使われる数値に戻される.これ は表現型である.複数の解候補は,タスクに適用されて評価を受ける.この 評価値がフィットネス値である.フィットネス値はGAにフィードバックされ,

その値に基づいて現在の解候補を選択する.選ばれた解候補は次の探索点を 決定する親となる.この考えは,優れた親は,確率的に優れた子供を生むと いう期待に基づいている.次世代の子供は,選択された親が交差や突然変異 のGA演算を受けることによって生成される.この探索過程は,要求探索レ ベルに達するまで繰り返される.

GA演算には,選択,交差,突然変異がある.

(10)

8 第1章 遺伝的アルゴリズム入門

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

   

 

 

 

 

 

 

 

             

 

             

図1.3: GA処理過程

G  

A  

 

 

 

1 1 1

1 1 1 1

1 1

1

1 1

1 1

1 1

1 1 1 1 0 0

0 0

0

0 00

0

0 0

0 0

0 0 0 0 0 1 1

1

1 1 1 1

0

0 0

0 0 0

0 0

1 1 0

0 0 0

1

3   5

4  3 6   2

1   8

1  9

1   4 8 

3 2 

5 6   5 7 

6 6 

4 3  2 4   7 6   9

3  2

3  9

2  8 1 

5

=

G  

A  

 

 

 

 

,  

   

 

 

,  

   

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

   

 

 

 

   

 

 

 

   

 

 

 

 

 

   

 

図1.4: GAデータフロー

1.4.1 GA 演算:選択

選択とは,親となる解(染色体)を選ぶ演算である.次世代の新しい解はこ れら親の解から計算で求められる.より良い親からはより良い子供が得られ ることが期待できるので,高いフィットネス値を持つ親の解ほど高い確率で選 ばれる.

選択にはいくつかの方法がある.ルーレット選択は代表的な選択方法であ る.ルーレットゲームで勝者となる確率は,ルーレット上で選んだ数字の占

(11)

1.4. GA演算 9

める面積に比例する.この類似からルーレット選択はフィットネス値に比例す る選択確率を個体に与える.

フィットネス値の尺度が必ずしも選択確率の尺度にふさわしいわけではな い.たとえば,フィットネス値の非常に高い個体が少数あって,その他は非常 に低い場合を考えてみよう.この場合,フィットネス値が高い親はほとんどい つも選択されることになり,得られる子供は似たり寄ったりになってしまう.

その結果,局所最適解に収束してしまうことが容易に想像できる.順位に基 づく選択では,距離尺度の代わりに順序尺度が用いられる.たとえば,フィッ トネス値(98,84,83,41,36, ...)に対して,選択確率(100,95,90,85,80, ...)が与 えられる.

フィットネスの尺度と選択の尺度は違うので,フィットネス値から選択確率を 計算する際にスケーリングが必要となる.順位に基づく選択は線形スケーリ ングと呼ばれる.スケーリングにもいくつかの方法があり,それがGAの収 束に影響する.

エリート戦略は,上位n個の親をそのまま次世代に残す方法である.子供 のフィットネス値は必ずしも親の値よりも良くなるとは限らない.そこでエ リート戦略では最も良い親を次世代にそのまま残すことによって,次世代の フィットネス値は最悪の場合でも親の世代の最良フィットネス値以下にはなら ないようになるようにしようとするものである.

1.4.2 GA 演算:交差

交差は複数の親を組み合わせて子供を作る演算である.交差はGAにおい て最も基本的な演算である. 親染色体を組み合わせるにはいくつかの方法が ある.最も単純な交差は,一点交差と呼ばれる.親染色体は任意の一点で切 断され,切断された部分を交換する.二点を切断する交差は二点交差と呼ば れる.これを自然に拡張すれば多点交差あるいは一様交差と呼ばれる.図1.5 はこれら標準的な交差のタイプを図示したものである.

交差にはいくつかのバリエーションがある.シンプレックス交差[2]はその ようなユニークな交差の1つである.シンプレックス交差では,2つのより良 い親と1つのできの悪い親を用いて1つの子供の解を作る.2つのより良い親 の同じビット位置が両方とも同じ‘0’もしくは‘1’ならば,子供も良い親を見

(12)

10 第1章 遺伝的アルゴリズム入門

 

 

 

  1  

2

1 0 0 1 0 1 0 1 0 0 1 1

1 0 0

1 0 1 0 1 0

0 1 1

  1  

2

1 0 0 1 0 1 0 1 0 0 1 1

1 0 0

1 0 1 0 1 0

0 1 1

1 0 0 1 0 1 0 1 0 0 1 1

 

 

 

 

 

1 0 0

1 0

1 0

1 0 0

1 1

 

 

 

 

 

 

 

 

1 0 0 1 1 1

 

 

 

1  

 

 

2

1 0 0 1 0 1 0 1 0 0 1 1

 

 

 

 

 

0 1 1 0 0 1

 

1  

2

 

1  

2

 

 

 

 

 

 

 

 

 

 

 

 

1  

2

 

1  

2

● ○ ○ ● ●

図1.5: いろいろな交差

習ってそのビット位置には同じ‘0’もしくは‘1’をコピーする.良い親のビッ トが異なる場合は,子供はどちらを信用してよいか迷ってしまう.そこで,で きの悪い親のビットを反転させた補数を子供にコピーする.つまり,半面教 師にする.図1.5のシンプレックス交差では,左端ビットが前者のケースであ り,左から2番目のビットが後者の例である.

1.4.3 GA 演算:突然変異

親染色体のビットパターンが似かよっていると,遺伝子型空間における親 と交差で得られた子供との距離は近くなる.このことは,個体が局所最適解 近傍に集中していると,交差だけでは局所最適解から抜け出せないことを意 味する.図1.6中の親が●と○だけであるならば,これらの親のビット列を組

(13)

1.5. GA演算の具体例 11

み合わせて得られる子供はその近傍にしか広がらないだろう.

1 0 1 1 0 1

 

 

 

 

 

1 1 1 1 0 1

図1.6: 突然変異の例とその効果

突然変異は染色体のビットを強制的に入れ替えることによって探索が特定 の位置に陥ってしまうことを防ぐ演算である.実数コーディングの場合は,乱 数値を加えることが突然変異演算になる.突然変異によって○の個体が◎の点 にジャンプしたとしよう.すると探索エリアもずっと広がる.図では突然変異 した点が2番目に高いフィットネス値をもっている.もしこの◎と最もフィッ トネス値の高い親が選択されて組み合わされれば,その子供は最適解に近づ く事が期待される.

もし突然変異確率が高すぎれば,GAによる探索はランダムサーチになって しまい,すばやい最適解への収束が困難になる.

1.5 GA 演算の具体例

具体的なGA演算の方法を,関数の最大値を求める数値最適化の例で示そ う.図1.7に示すf(x)の最大値を求める問題で,GAはこの最大値を与える xのみの1次元空間を探索する.ちなみに,この関数は次式で与えられる.

f(x) = 1.5

2πexp(x−50)22000 + 2.5

2πexp(x−150)22000

(14)

12 第1章 遺伝的アルゴリズム入門

f x( )

300 250 200 150 100 50 0.00 0.2 0.4 0.6 0.8 1.0

x

図1.7: GAによる最大値探索の説明に用いる関数

(1) GA コーディングの設計

簡単のために,表1.2のGAコーディングを行うとしよう.探索範囲256に 対して探索精度8ビットを割り振るのでxは整数値になるが,これはGA探 索の本質ではない.交差率100%とは,個体数と同じ8個の親を選択し,8個 の新規の次世代の子供(探索点)を作り,突然変異率1%とは,平均的に100 ビットに1回の確率でビット反転を行うようにすることである.

表1.2: GA演算の例題のGA条件 xの探索範囲 0≤x≤255 遺伝子長(xのビット長) 8ビット

遺伝子表現 2進数のビット表現

個体数 8

選択方法 ルーレット選択

交差方法 二点交差

交差率 100%

突然変異率 1%

(2) 乱数初期化による第 1 世代

8ビットの個体8個すべてを乱数で1/0に初期化する.これを,表1.3に表 す.この2進数表現(ビット表現は2進数コードだけではなく,グレーコー

(15)

1.5. GA演算の具体例 13

ドなど他のコード化も使われる)のxを10進数にデコードし,f(x)を求め る.このf(x)が探索の善し悪しを計るフィットネス関数になる.

表 1.3: 初期乱数で得られた第1世代の例

個体 個体のビット表現 個体の実数表現 f(x) 正規化 正規化f(x) 番号 x2進数表現) x10進数) したf(x) の累積値

1 00110000 48 0.603 0.142 0.1420

2 01010010 82 0.457 0.108 0.2500

3 11011111 223 0.069 0.016 0.2660

4 01111001 121 0.703 0.166 0.4320

5 01000010 66 0.556 0.131 0.5630

6 10101100 172 0.783 0.185 0.7480

7 00011110 30 0.491 0.116 0.8640

8 00111110 62 0.578 0.136 1.0000

(3) 親の選択

この例で採用するルーレット選択では,フィットネス値=親として選ばれる 確率,となる.そこで,フィットネス値合計が1になるよう正規化し,8個の 個体のフィットネス値を丸いルーレット台に並べてみよう(図1.8).ここで0

〜1の乱数値のボールをこの台に転がして止まったところの個体を親に選ぶの である.具体的には,表1.3右端にある正規化したf(x)の累積値を求めてお いて,乱数が正規化f(x)の累積値のどの位置に相当するかを見ることになる.

いま,[0,1]の一様乱数を表1.4のように8個得たとすると,各乱数値が表 1.3から選ぶ個体は表1.4の中央および右になる.この選択された個体が第2 世代の子供を生成する親となる.

(4) 交差

8ビットある染色体(個体)のどの二点で交差するかは,乱数で決める.た とえば,図1.9のようになる.

(16)

14 第1章 遺伝的アルゴリズム入門

0  

.  

1  

4  

2 0  

.  

1  

0  

8 0  

.  

0  

1  

6 0

  .  

1  

6  

6 0

  .  

1  

3  

1 0

  .  

1  

8  

5 0  

.  

1  

1  

6 0  

.  

1  

3  

6

図 1.8: 1.3の正規化フィットネス値をルーレット台に並べた様子

表 1.4: ルーレット選択によって乱数が選ぶ親個体の例 生成乱数値 選択された個体番号 選択された個体

0.890747 8 00111110

0.196014 2 01010010

0.902283 8 00111110

0.770203 7 00011110

0.468292 5 01000010

0.634125 6 10101100

0.904572 8 00111110

0.469818 5 01000010

(5) 突然変異

突然変異率に応じて,ビットを反転させる.たとえば,図1.9で得られた最 初の子個体の左端から2ビット目だけが反転したとしよう.すると表1.5のよ うに変化する.

表1.5: 突然変異による探索点の変化 個体のビット表現 個体の実数表現 f(x)

x2進数表現) x10進数)

00110110 54 0.604

01110110 118 0.657

こうして最終的に得られた第2世代の8個体およびそのxの表現型とその

(17)

1.6. 簡単な組合せ最適化問題の例 15

00110110 01011010

00011110 00111110

01001110 10100000

00000010 01111110 00111110

01010010

00111110 00011110

01000010 10101100

00111110 01000010

図 1.9: 二点交差の例

時のf(x)を,表1.6に示す.この作業を3世代,4世代と,収束が落ち着く まで繰り返すのである.

表1.6: GA演算を通して得られた第2世代の例 個体番号 個体のビット表現 個体の実数表現 f(x)

x2進数表現) x10進数)

1 01110110 118 0.657

2 01011010 90 0.434

3 00011110 30 0.491

4 00111110 62 0.578

5 01001110 78 0.479

6 10100000 160 0.950

7 00000010 2 0.189

8 01111110 126 0.781

1.6 簡単な組合せ最適化問題の例

前節では,パラメータの値を最適にしようとする,数値最適化の例を用い てGA演算の過程を視覚化しようと努めた.数値最適化には勾配法のような 競争相手が多々あるので,与えられた問題に応じて最適な手法を選択すると

(18)

16 第1章 遺伝的アルゴリズム入門

よい1

一方,組合せ最適化とは,性能が最大になる取り合わせの妙を探し出す方法 である.実際のGAの応用ではスケジューリング問題などに代表される.こ こでは,簡単な組合せ最適化問題としてナップサック問題を取り上げ,GA応 用の具体的なイメージをつかもう.

図1.10はナップサック問題とそのGAコーディングを図示したものである.

ナップサック問題とは,品物の総量がナップサックの容量を超えないという条 件下で,できるだけ容量いっぱいになる組合せ,あるいは品物の価値が最大 になる組合せを探す組合せ最適化問題である.ナップサック問題自体は単純 な例題であるが,これと類似した実用的な問題は数多くある.盗みに入った 泥棒がいかに金目のものをナップサックに詰め込むかという実用例は別にし ても,たとえばOSのCPUの負荷を最適化するマルチタスクスケジューリン グ問題がナップサック問題にあたる.

A B

C D

E F

   

   

V

10 0 1 0 1

A B C D E F

6  

0 5  

3 6  

8 2  

6

 

 

 

   

1      

 

 

   

2  

 

 

   

3

 

 

 

 n

 

 

 

 

 

1 1 1 0 0 0 10 0 1 1 1

1 1 1 0

0 0 図1.10: ナップサック問題とGAコーディング例

図1.10では品物が6個あり,問題はどの品物をナップサックに入れるかを 決定することであるから,染色体は1ビットの長さを持つ6つの遺伝子から なる.たとえば,図中の1番目の染色体は,AとDとFをナ ップサックに入 れることを意味する.次にすべての染色体のフィットネス値が計算される.A とDとFの総容量が60,BとEとFの場合が53,AとDとEとFの場合

が68,などである.この場合フィットネス値は総容量自体である必要はない

1 ファジィ理論で有名なザデー教授が戒めるハンマー原理というものがある.ファジィという ハンマーを手に入れると,どの問題もそのハンマーで叩いてみたくなる.ニューラルネットとい うハンマーを手に入れると,どの問題もそのハンマーで叩いてみたくなる.GAというハンマー を手に入れても...

(19)

1.6. 簡単な組合せ最適化問題の例 17

が,フィットネス関数は入れる品の総容量の関数である必要がある.次にGA 演算が染色体に適用され次世代の解候補を作る.最適解が要求仕様を越えた とき,探索は終了する.

演習問題

1. 巨大迷路の抜け道をGAに探させよう.ある迷路には,右に進むか左に 進むかの分岐点が20あるとする.この20個の分岐点での進み方がわ かればそれが解である.さてGAにこの問題を解かせるにはどのように GAコーディングをすればよいか.

2. 図1.10のナップサック容量Vと品物A〜Fに適当な数値を当てはめ,自 分で適当なGA演算を選び,1.5節のように手作業で計算せよ.

3. GAはなぜランダムサーチより早く解収束するのだろうか.交差によっ

て得られた子供個体が親個体よりも良くなる確率と悪くなる確率が等し いと考え,良い親ほど高い確率で選ぶ選択を行うことから説明せよ.

(20)
(21)

19

2 章 ファジィシステムと遺伝的 アルゴリズム

2.1 ファジィ理論とファジィシステム

ファジィ理論の核となる分野にはファジィ集合,ファジィ論理,ファジィ測 度があり,その中でもファジィ集合はファジィ理論の根幹をなす基本的な概念 である.真偽の2値を扱う論理学へファジィ集合を導入して中間値を扱うよ う拡張したものがファジィ論理であり,知識処理にファジィ論理を導入したも のがファジィ推論(または近似推論)である.さらに,制御の分野にファジィ 推論を応用したものをファジィ制御という.

ファジィ理論の応用は,ファジィ制御を中心とする工学に偏っていたが,近 年,医療診断,心理学,教育,経済,経営,社会学などのようなノンエンジニ アリングの分野でも使われるようになってきた.「感性」の分野におけるファ ジィ応用も増えてきた.

本章では,ファジィ理論の中でもファジィルールとファジィ推論によって 特徴づけられるファジィルールベースシステム,簡単には,ファジィシステ ム(FS)を中心に扱う.初めにFSの基礎を説明した後,遺伝的アルゴリズム (GA)とFSとの融合化技術について説明する.

(22)

20 第2章 ファジィシステムと遺伝的アルゴリズム

2.2 ファジィシステム

2.2.1 ファジィシステムのアプローチ

FSの特徴の1つは,比較的簡単で部分的な入出力関係を組み合わせること でFS全体としての複雑な非線形が扱えることである.図1.1の空間が,2入 力と1出力の入出力空間であるとしよう.FSは,入力空間を複数のルール領 域に分割する.分割された個々のルール領域は各々1つずつのIF–THENルー ルに対応し,そのルール領域の形状は,メンバーシップ関数とルールの出力 で決まる.これら個々のルール領域の形状を組み合わせることで複雑な非線 形関係を表現する.

FSの第1の特徴は,複雑な非線形の入出力関係を,多くの簡単な入出力関 係の集まりとして表現することにある.この簡単な入出力関係は各IF–THEN 形式のファジィルールによって記述される.この考え方は,正弦波の組合せで 複雑な波形が構成されているとするフーリエ変換や,シグモイド関数やガウ ス関数の組合せで非線形関係を表すニューラルネット(NN)の考え方に似てい る(図3.7と比べてみよう).

ルール領域の境界線は,はっきりとしていなくて「あいまい」である.この ルールはある程度成り立つが,あのルールもある程度成り立つ,というよう な中間状態がファジィ状態であり,あるルール領域から次のルール領域へかけ て,出力は徐々に変化する.これがFSの本質であり,「ファジィ」という用語 の本来の意味である.

FSのもう1つの特徴は,論理とあいまいさをルールとメンバーシップ関数 に分離する点にある.従来の2値論理システムではこの分離ができないので,

論理かあいまいさのいずれが変化しても,ルールが修正される.FSでは,論 理がおかしいならばファジィルールを修正し,あいまいさがおかしいのであ ればあいまいさを定義するメンバーシップ関数を修正する.

倒立振子の制御器の性能に問題があるとしよう.aを右側に棒がある時の棒 と垂直軸の角度,a˙ をその角速度とする.

IFaが正方向に大きく かつa˙ が速い,THEN 車を右に速く動かす.

IFaが負方向に小さくa˙ が遅い,THEN車を左にゆっくり動かす.

というのは正しい論理であり,ファジィルールそれ自体を変える必要はない.

性能に問題があるのならば,大きい,小さい,速い,遅いなどの,あいまいさ

(23)

2.2. ファジィシステム 21

の定義が修正されるべきである.一方,

IF40≤a≤60 かつ50/s≤a˙ 80/s, THEN車を0.5 m/s動かす.

または

IF−20≤a≤ −10かつ10/s≤a˙20/s, THEN 車を−0.1 m/s 動かす.

のような2値論理ルールでは,角度,角速度,車の速度の量に関する定義や ルールを変える時はいつでも,ルールを修正しなければならない.

2.2.2 数式ベースの制御とルールベースの制御

FSを理解するために,FSの簡単な例としてファジィ制御を取り上げる.制 御の目的は,図2.1の熟練操作者を制御器に置き換えることである.

(a) (b)

 

 

 

 

 

 

図2.1: (a)従来の制御理論ではターゲットシステムの振舞いに注目し,その数学的モ デルを作ろうとする.(b)ルールベースの制御では熟練操作者の振舞いに注目し,そ の人の制御モデルを作ろうとする.

数式ベースの制御方法は昔からの制御理論に基づいていて,ターゲットシ ステムの特徴を観察したり,その数学的モデルを構成したりして,そのモデ ルに基づいた制御器を作る.重要な部分はターゲットシステムであり,操作者 は設計上の要因とはならない(図2.1(a)).

一方,ルールベースの制御はターゲットシステムに着目するのではなくて,

熟練操作者の動作に基づいている(図2.1(b)).ほとんどの熟練操作者はター ゲットシステムの数学的動作を知らないけれども,彼らはシステムを制御で きる.たとえば,熟練したタクシー運転手は,おそらく舗装されていない丘 を右に曲がる時の車の動作の物理モデルを知らないだろうけれど,安全に車 を運転することができる.であるならば,この運転手のモデルができれば車 を安全に制御できるのではないかと考えることは自然であろう.ファジィ制御

(24)

22 第2章 ファジィシステムと遺伝的アルゴリズム

は,ルールベースの制御の1つで,IF–THEN形式のファジィルールで熟練 者の制御動作を記述し,このルールに基づいて制御する.

2.2.3 IF 部(前件部)の設計

IF部の設計をするということは入力空間の分割方法を設計するということ である.ルールベースシステムのほとんどは,すべての入力変数が独立であ るとして,各入力変数軸ごとに入力空間を分割する(図2.2を参照).この前 提は,入力空間の分割が容易であるだけでなく,分割された領域を言語ルー ルで表すことを容易にしている.たとえば,

「IF 温度がA1 かつ 湿度がA2THEN ...」

というルールは理解しやすい.このような変数ごとにあいまいさを記述でき るのも,温度と湿度の変数が分離されているからである.研究者によっては,

入力変数が独立であるという制約を外し,言葉表現の理解しやすさを犠牲に する代わりに,より性能の向上を狙った多次元のメンバーシップ関数を提案 している.

(   b ) ( 

 a )      

1

   

1

    2

     

2

      4       5

     

1      

2       5       4

      3

      3     2

   

1

図2.2: 入力空間のルール分割 (a)クリスプなルール分割,(b)ファジィルール分割 クリスプ(かちっとした)なルールベースシステムとファジィルールベー スシステムの違いは,どのように入力空間を分割するかという点にある(図 2.2の (a) と(b) を比較しよう).論理面で見ると,(a)は「入力がルールn に属するか否か」という2値論理ベースであり,(b)は中間状態を認めている

(25)

2.2. ファジィシステム 23

のでファジィ論理ベースである.FSの考えは,アナログの実世界では不連続 な変化というものはなくて変化は徐々に起きるという考えに基づいている.こ のためFSでは,1つの制御ルールから他の制御ルールへ徐々に遷移するため にルール領域の重複を許している.この重複の度合はメンバーシップ関数で 定義される.徐々に変化するという特徴は,滑らかなファジィ制御を可能にす る.滑らかな制御は省エネや乗り心地に通じ,エアコンや地下鉄へのファジィ 制御ではこれらが売り物になっている[42, 43].

2.2.4 THEN 部(後件部)の設計

入力空間の分割に続く次の段階は,各ルール領域の制御値を決めることで ある.ファジィモデルは,THEN部の表現によって3つのモデルに分類され る.

(1) Mamdaniモデル: y=A

(Aはファジィ数)

(2) TSKモデル: y=a0+

aixi

(aiは定数,xiは入力変数)

(3) 簡略化ファジィモデル y=c

(cは定数)

MamdaniモデルのTHEN部出力は,y=大きいやy=負で小さいのような

ファジィ数であり,メンバーシップ関数で規定される.世界初のファジィ制 御で使われたのがこのモデルである[19].このタイプのFSを解析することは,

THEN部が数式で定義されるFSよりも困難ではあるが,THEN部に先験的 知識を記述しやすい.MamdaniタイプのFSはエキスパートシステム型制御 より,むしろ知識処理を行うエキスパートシステムの記述にふさわしいと思 われる.

TSKモデル(高木–菅野–姜)のTHEN部は,入力変数の重み付き線形結合 によって表現されている[33].入力変数の線形結合を非線形結合に拡張するこ ともでき,一般に関数型ファジィモデルとも言われている.非線形関数の例 として,THEN部をNNで構成するFSがある[34].しかしTHEN部出力を 非線形関数に拡張してシステムの性能を向上させる代わりに,ルールのわか りやすさは犠牲になる.TSKモデルは次に挙げる簡略化ファジィモデルと同 様,ファジィ制御の分野で頻繁に使われる.

(26)

24 第2章 ファジィシステムと遺伝的アルゴリズム

簡略化ファジィモデルのTHEN部は,定数値で表される.このモデルは

MandaniモデルとTSKモデルの両方の特殊な場合に相当する.たとえ各ルー

ル出力が定数であっても,FS全体の出力は非線形である.これは,メンバー シップ関数の特性がシステムの出力に埋め込まれるからである.簡略化ファ ジィモデルの最も大きな特長は,モデルの設計が容易であることである.

2.2.5 ファジィ推論と統合

IF部とTHEN部の設計の次は,多くのファジィルールからシステムの最終 出力を決めることである.最終出力決定には2つの段階があり,ルール強度 を決定して,次に各ルール出力を統合する.

第一段階ではルール強度,すなわち各ルールがどのくらい有効か,あるい は入力データがどの程度各ルールに属しているかという値を決定する.通常,

IF部には次のように複数の入力変数がある.

IFx1∈μ1 かつx2∈μ2 かつ... xk∈μk, THEN ...

この場合,1つのファジィルールにはk個のメンバーシップ値μi(xi) (i= 1, ..., k) がある.まず,k個のメンバーシップ値からルールの有効度,強度を決める必 要がある.この目的に用いられるファジィ演算はt–ノルム演算と呼ばれてい る.t–ノルム演算は多くある.最もよく使われるt–ノルム演算の1つに代数 積があり,それは

ルール強度wi =k

j=1μj(xj)

と表される.Mamdaniらが最初のファジィ制御で使ったmin演算,すなわち,

ルール強度wi =min(μj(xj)),もよくファジィのテキストに紹介されている.

FSの最終出力yは,得られたルール強度wiで各ルール出力を重み付け平 均することで得られる(y=

wiyi/

wi).Mamdaniタイプのファジィ制 御器では統合したシステムの出力から最終的な非ファジィ制御値を決定する.

図2.3は4つのファジィルールからなる簡単なFSの例である.最初のルー ルは

「IFx1が 小さくかつx2 が小さい,THENy= 3x1+ 2x24」

である.入力ベクトルが(x1,x2) = (10, 0.5)であるとしよう.そのときメン

(27)

2.2. ファジィシステム 25

バーシップ値が算出される.第1ルールは入力値に対して0.8と 0.3のメン バーシップ値をもつ.第2ルールは0.8と1.0のメンバーシップ値をもつ.もし

代数積がt–ノルム演算として使われるなら,第1ルールのルール強度は0.8×

0.3 = 0.24となる.第2,第3,第4ルールのルール強度はそれぞれ0.8,1.0,

0.3となる.もしmin演算が使われるならば,第1ルールの強度はmin(0.8, 0.3) = 0.3となる.入力ベクトル(10, 0.5)に対する各ルールの出力は,それ ぞれ27,23.5,−9,−20.5であるから,システムの最終出力yは次式で得ら れる.

y=

wiyi

wi = 0.24×27 + 0.8×23.5 + 1.0×(−9) + 0.3×(−20.5) 0.24 + 0.8 + 1.0 + 0.3 = 4.33

IF and

IF

IF

IF

and

and

and

1

1

1

1

1

1

1

1 0.8

0.3

0.8

0.3

THEN y=3x1+2x24

=27

=23 5.

= −9

= −20 5. y=2x13x2+5 THEN

y= − −x1 4x2+3 THEN

y= −2x1+5x23 THEN

  x1=10

x1

x1 x1

x1

  x2=0.5

x2

x2 x2

x2

図 2.3: TSKモデルのファジィシステムに(10, 0.5)が入力された時の各ルールの出 力例

(28)

26 第2章 ファジィシステムと遺伝的アルゴリズム

2.3 ファジィシステムのための遺伝的アルゴリズム

2.3.1 GA による FS の設計

GAでFSを設計する方法は,C. Karr (1989年)以来[12]いろいろ発表され ている[35]が,最も多く行われている方法は,FSをパラメータ化して,FSの 入出力関係を仕様に合うよう,各パラメータをGAで最適化する方法である.

FSの設計には5つの項目があると考えられる.

(1)入力変数の選択 (2)演算方法の選択 (3) IF部の設計 (4) THEN部の設計 (5)ルール数の決定.

(1)の入力変数選択は,タスクによっては固定されていて選択の余地がない 場合も多い.選択する必要がある場合は,変数減少法やGAなどを用いる.変 数減少法は,1つずつ入力変数を減らしてFSを設計し,その変数を減らした ことでFSの性能が劣化すれば,その変数が重要であり,そうでない場合は性 能にあまり寄与しない変数である,と見なす方法である.要不要の判定をす る入力変数が少ない場合に使われる.入力変数が多い場合は,GAを用いて入 力変数の最適組合せを行うファジィモデリングも考えられる.

(2)の演算方法の選択は,t–ノルム演算子やt–コノルム演算子などのファジィ 演算方法を選択するものである.通常,適当な演算子を使うことが多いが,演 算子によって大きくFSの性格が変わるため,演算子だけを動的に変更するこ とで,FSの動特性を改善する研究もある.パラメトリックなファジィ演算子 を用いて,GAでそのパラメータを変える研究もある.

しかし,FSの設計の中で特に重要な項目は(3)〜(5)であろう.(3)のIF 部の設計とは入力空間をいかに分割するかという問題なので,分割された空 間数,つまり(5)のルール数と直接関係する.これら3項目の設計にGAが 使われる.これら3項目は相互に関係するので,1つずつ最適化するのではな く同時に最適設計する必要がある.以下では,これらをGAで同時に設計す る方法を示そう[15].

まず(3)のIF部設計は,メンバーシップ関数の形状をパラメータ化するこ

(29)

2.3. ファジィシステムのための遺伝的アルゴリズム 27

a b xi

M8(i) M3(i)

M2(i)

M1(i) M4(i)

図 2.4: GAコーディングによるファジィ分割数の決定.[a,b]にかかるメンバーシッ プ関数のみを有効とする

とから始まる.三角形ならば三点,二等辺三角形ならば二点,ガウス形なら ば二点,台形ならば四点で,形状が規定される.各入力変数ごとの最大分割 数を決めれば,GAコーディングするIF部のパラメータ数が決まる.たとえ ば,入力変数が3で,台形メンバーシップ関数を各入力空間ごとに最大8個 まで配置可能だとすれば,3×4×8=96個の形状パラメータを最適化するこ とが,IF部の設計である.

(4)のTHEN部もパラメータ化する.簡易型ファジィ推論では各ルールに 1つの数値を,TSKモデルでは線形式(非線形式に拡張しても同様)の係数 を,Mamdani型のファジィ推論ではIF部設計と同じく,メンバーシップ関 数の形状パラメータを,それぞれGAコーディングする.実際に全部のルー ルが使われなくても最大設計ルール数分のこれらTHEN部パラメータをGA コーディングする.前述の例の場合,最大83=512ルール分のTHEN部パラ メータをGAコーディングする.

(5)のルール数の設計にはちょっと工夫がいる.たとえば,入力変数xiの設 計範囲が[a,b]で,その入力空間のメンバーシップ関数Mj(i)の最大数が8個 であるとしよう.メンバーシップ関数M1(i), M2(i), ..., M8(i)が,aから大きい方 へ順に並ぶように制約を加えてGAで形状を設計する.こうしてbを越えた xiの範囲をカバーするメンバーシップ関数を無視すれば,有効な[a,b]のファ ジィ分割数が確定する.図2.4の場合,5つのメンバーシップ関数を有効と見 なすわけである.これを全入力変数分行えば,入力空間全体の分割数,すなわ ちルール数が確定する.メンバーシップ関数が昇べき順に並ぶような制約の 与え方の一例としては,三角形メンバーシップ関数Mj(i)の三点を,通常(左 端,中央,右端)の座標値にする代わりに,図2.5のように(Mj−1(i) の中央と Mj(i)の中央との差,Mj(i)の中央から左端および右端への距離)の三点をGA コーディングすることが行われている[15].距離は正なので,メンバーシップ

(30)

28 第2章 ファジィシステムと遺伝的アルゴリズム

p

3

p

2

p

1

図 2.5: 昇べき順に並べる制約を課すためのメンバーシップ関数の形状パラメータ化 の例.正数p1のために,メンバーシップ関数は,右へ右へと配置される

関数は,図の右へ右へと順に並ぶ.

以上のGAコーディングで,FSの設計項目(3)〜(5)が同時に設計できる.

なお,実際の設計では,少ないルール数で性能を上げるという二律背反が 求められることも多いので,ルール数に比例するペナルティをGAのフィット ネス関数に導入することも多い.また,性能の良いFSを素早く見つけだすた めに,タスクに先験的知識を組み込み探索空間を狭めることは有用である.た とえば,倒立振子の左右の制御は対象であることを知っていれば探索空間が 半分ですむ.

以上のFSのためのGAに関する研究にご興味ある読者は,解説論文[35]等 を参考にしていただきたい.

2.3.2 GA による FS の設計の実応用

FSのパラメータを決定したり,FSが最適になるようにパラメータを決定 する別な手法として,NN[9]やGA[12]を使用したものが挙げられる.たとえ ば,三角形をしたメンバーシップ関数は左右端と頂点という3つのパラメー タにより定義される.THEN部も同じようにパラメータ化される.

日本ではNNを用いたFSの設計が1991年から商品化に使われ,洗濯機,

炊飯器,掃除機など多くの民生機器に使われている.一方,GAを使った手法 は,1994年以来,韓国の民生機器に取り入れられている.

三星社は,冷蔵庫と洗濯機にGA+FS技術を応用している[13].1994年発 売の冷蔵庫は,庫内の温度にむらがないように,庫内内壁のセンサに応じて

参照

関連したドキュメント

情報理工学研究科 情報・通信工学専攻. 2012/7/12

理工学部・情報理工学部・生命科学部・薬学部 AO 英語基準入学試験【4 月入学】 国際関係学部・グローバル教養学部・情報理工学部 AO

茂手木 公彦 (Kimihiko Motegi) 日本大学 (Nihon U.) 高田 敏恵 (Toshie Takata) 九州大学 (Kyushu U.).. The symplectic derivation Lie algebra of the free

訪日代表団 団長 団長 団長 団長 佳木斯大学外国語学院 佳木斯大学外国語学院 佳木斯大学外国語学院 佳木斯大学外国語学院 院長 院長 院長 院長 張 張 張 張

関谷 直也 東京大学大学院情報学環総合防災情報研究センター准教授 小宮山 庄一 危機管理室⻑. 岩田 直子

[r]

[r]

[r]