遺伝的アルゴリズムと人工知能
伊庭斉志l
川111111
川
111
川
川
11川
11川
11山
11111
川
川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
1111111
川
川
11川
11川
11川
11川
11川
11川
11川
111111
川
111
川
川
11川
11川
11川
11川
11川
111111
川
川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11111
川
川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11111
川
川
11111
川
川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川|川
11 l川
l川
川
11川
11川
11川
11川
11川
11川
11山
11川
11川
11川
11川
111111
川
川
11川
11川
11川|川
11 川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川|川
11 川
11川
11川
11川
11川
11川
11川
11川
11川
111111
川
l川
川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11111
川
川
111111
川
川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
111

1.

従来の研究では，グラフを l 次元文字列の遺伝子コードはじめにに写像し，通常の GA の枠内で最適化を行なつていた.

本稿では，人工知能における記号的な表現を扱えるように遺伝的アルゴリズム(GA) の手法を拡張する.本たとえば [Kit旬ano
凶91口]で1 次元配列に写像する手法と，L システムにもとづくグ

章の目的は，従来の GA を次のように補うことを試みる

ラフ生成ルールを文字列として扱う手法が提案されていものである.

る.これらの手法は各領域で一定の成果をあげているが，1.探索のための的確な部分構造の把握

グラフなどの構造的表現をそのままの形式で遺伝子とし2. 問題の表現形式にもとづいた効果的な探索の実現て扱ってはおらず，その結果グラフのもつ構造的特性が3. より高次の知識の適応的な学習システムの構築

適応評価に十分には反映されない場合も多いと考えられ

以下では，構造的な表現としてグラフ構造(特に木構る.

造)を扱う.木はサイクルをもたないグラフのことであ

このような問題を解決するため，本章では構造的表現を直接遺伝子コードとして扱えるように GA を拡張す

り，る.

A/1

これは Genetic Programming と呼ばれ，により提唱された手法である [Koza90J.

B C

理論的研究としては，

Dる [Ehrig87J.

Koza

また関連する

L システムやグラフ変形文法があ以下では Koza の手法をもとにして， GAのような構造を言う.これは人工知能における多くの知を用いた構造的表現の適応学習を説明し，関数合成や知識表現で用いられる構造である(たとえば概念形成の決識獲得への応用について述べる [Iba92b ， 93J [伊庭90 ， 91

定木や意味ネットワークなど).木構造は LISP の S 式でa, bJ.
本章では，便宜上 GA で扱う情報として， PTYPE と記述でき，たとえば上の木は，GTYPE の 2層構造からなる表現形式を採用する [Lang­(A(B)

ton89]. GTYPE は遺伝(子)型のアナロジーであり，(C(D)))GA のオベレータの操作対象となる.

もしくは簡略化して，であり，(AB(CD))

PTYPE は表現型

GTYPE の環境内での発達に伴う大域的な行動や構造の発現を表わす.次世代を生成する際の選択はとなる.したがって以下では木構造と LISP の S 式を同PTYPE をもとにして計算された適合度に依存する.すなわち，適合度の高いものほど生き残りやすく，より多一視する.

構造的表現を GA で扱う試みはさまざまな分野で研究されている.たとえば [Kitano90J で、は，ニューラルネットの結合状態を示すグラフを GA を用いて設計した.

産なように GA は進行する.

2. 構造的表現への GA の拡張

GA を用いてグラフの採色問題(一木に対する GA のオベレータとして，以下を導入する

定の色数でグラフのノードを採色し同色となる隣接ノー(図 1 ) これらはピット列を対象とする従来の GA オベドの数を最小にする問題)の近似解を求めた.こうしたレータの自然な拡張である.

また [Davis91J は，

いばひとし

Gmutation ノードのラベルの変更
Ginv
erion 兄弟の並べ換え

電子技術総合研究所知能情報部推論研究室

GC l'個師'ver〒 305 つくば市梅園 1-1-4

これらのオベレータを LISP の表現木に適用した例を1993 年 7 月号

部分木の取り換え© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(17)3
4
1

gmutation

図 2 に示す.この適用を LISP の S 式で記述す
ると表 1 のようになる.ただしオベレータの適用部位には下線を付した.
構造的表現に対する遺伝アルゴリズムは次の一一一一一ーシようになる.

Step1

ランダムに木構造 GTYPE {gt (i)} を構成する

Step2 各 GTYPEgt (i) の表現型ぁ (i) に対し

gmver
slOnて適合度 ft (i) を求める.

Step3 適合度の大きな GTYPE に対して一定数のベアーを取り出す

Step4 取り出したベアーに対して Ger個師ver

一一一今を適用し，適合度の小さな GTYPE と置き換える

Step5 各 GTYPE に関してランダムに Ginver­
r且T

VAev
oa

八/UAf一kuh

E を次の世代の {gけ.( i)} として，

σbC

Step6 以上によって求められた新しい GTYP

田TO

sion, Gmutation を適用する
STEP2

‘‘、.
‘lhへ戻る
こうして拡張した GA の枠組みは，‘‘‘」.GTYPE から PTYPE への変換
.適合度の計算

T1を適切に設計することでさまざまな問題に適用可能である.

T1~

GA による構造的表現の探索能力については，グラフの獲得やランダム木の収束

T1・

図1などの実験において，その有効性を確認した.

Gcrossov
erprogn

詳しくは [Iba92b] を参照されたい.以下では，
関数合成，知識獲得なとe への本手法の応用につ

dill‑xG
mutation~ーヤ/l¥¥/¥yx

1 ハxxiX

Ginv
ersionprint

¥¥

XXy/
¥1/ペぺ\lx(その 1 )

図 2342(18)mc〆f/、X

図 2pr
匤t(その 2 )© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ

表 1GmutiltioD

S 式の変換採用する.したがって適合度が1. 0 となる PTYPEが， Fibonacci 関数と入出力が一致する関数であ(+xy)

る.ただし必ずしも定義としては一致しない.さ品(+x 圭)
G加ersiODGcrossover

らに ，V N と V T からランダムに生成された関数(prog叫 (incf x)(setqx2)(printx))(2 節のアルゴリズムの初期生成部分， STEP1)

品(prog叫( setq x2)(灼cf x)(
printx))は一般に無限ノL ープを含み得るので，

eval‑hook等の機能によりループの過度の巡回を回避する必(
progn(incfx)(setqx2)(setq 型 x))(
progn(decfx)(setqx(*(sqrtx)x)(
printx))要がある.その場合の出力値は正解とは一致しないものとする.

品(progn(incfx)(sqrtx)(setqyx))(progn(decfx)(setqx(*(setqx2)x)(printx))

ここでは GA のパラメータとして，集団数200，GerωωIver の確率 0.6， Gmutation の確率 0.0333とする.簡単のため Ginversion は省略した.この場合，第 7 世代において，いて説明する.

(defunfib(j‑index)

3. 関数の合成問題(my+(fib (my‑j‑index1))(fib(my‑j‑index2))))

再帰的定義を含む Fibonacci 関数を GA を用いて自1 ， 1 を初めの 2 項としというような関数を獲得した.これは Fibonacci関数のて，前の 2 項をつぎつぎに足して得られる数列(1， 1 ， 2 ，定義と一致する.ただし簡単のため j-index が 1 と 2 の3, 5, 8, 13, ...)である.

場合の値(1)は既知としている.図 3 はこの実験における動合成する. Fibonacci数列とは，Fibonacci 関数 (fib n) は，こ関数生成のトレース(第 5 から 7 世代まで)を示す.図の数列の第 n 項を与える関数である.
GA にもとづく学習の実現のために， GTYPE を V N

からわかるように第 7 世代において115 番目)適合度と V T から生成される木構造 ， PTYPE を GTYPE の0.0714)と 130番目(適合度 0.050)の親の Ger欄over表現を評価した結果とする.ここで V N は，非終端記号，によって上の GTYPE が得られた.

Gcr個80ver の適用

一般には関数記号で、ある.木構造において V N に属する部位が r~ において Dewey

ノードの子の数は関数としての引数の数 (arity) に一致th67]) で示されている.この場合は， 115番目の GTYPEし，一定のものと不定のものがある .

V T は終端記号でたとえば ， VN={f.+，一}， VT={O , 1 ， 2 ， x} のときを+，ーの arity は 1 ， 2 ， 2 である.こ130

ド (0_ 2. 1)との交叉である.この時までに適用されたオベレータの数はGmutation が 251 回， Gcr個師，ver が438 回である.図中の s-fitness は適合度をスケーリングのとき，GTYPE=(f(f(ー(ー(+0 x)1)1)))に対応する表現型は，通常のセマンティックスで、は，PTYPE=(f(f(‑x2)))

した値を示す [Goldberg89].

これは適合度の差異を際立たせるために用いられる.
筆者は同様の手法を用いて，l 、くつかの関数の合成実

験や構造的クラシファイアによる補食行動の進化的学習となる.の実験を行な L 、，その有効性を確認した [Iba92c]. また

以下では，Koza らはこの手法をもとにしてさまざまの関数合成のVN={fib , mn+ , my- },実験を行ない成功を収めている.

VT={1 , 2, j‑index}とする.ここで my+ と my ーは 2 引数をとる通常の加算と減算を示し ，る.の 1 番目の子ノードの 1 番目の子ノード (0. 1. 1 )と，番目の GTYPE の 2 番目の子ノードの 1 番目の子ノーあり，変数や定数を表現する.

考える.ここで f.

DecimalNotation([Knuｭfib は再帰定義に用いる関数名であj-index は Fibonacci 関数の引数となる変数を示

詳しくは文献 [Koza90] を参照されたい.

4.

構造的 GA にもとづく GMDHす.適合度としては， j-index にさまざまな値( 1からシステム同定問題は，未知のシステムのふるまいを入20) を代入したときの PTYPE が表わす関数が返す値出力の観測値から予測するものである.この問題の難しと，実際に Fibonacci 関数が返すべき値との合致率をさは，吸うべき変数，データ，制約などによる組合せ論

1993 年 7 月号

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(19)343khnenko7lJ.

Populationreportこれは，変数群から選択された適当な 2 変数の 2 次式を重回帰分析により構成し，Generation5fitness s‑fitness

それを新たな変数とみなして変数群に加え，目標4)(11B(11ト 2 J‑INDEX))

0.
0
7
140.
0708の近似精度を得るまでこの変数の選択と生成をく

128)
(
11B2)

0.
0
7
140.
0708

選択にヒューリスティックが必要であることや，

1(1)(HY+10.
07
140.
0708

書string(町+りかえすとし寸手法である .GMDH については，探索が極値に陥りやすいことなどの欠点が指摘されている [Tenoiro90].

(FI
B(HY‑J‑INDEX1))(FIB1)))

筆者らは，構造的 GA を用いてシステム同定問
題の解決、ンステムを構築した.

150)‑INDEX)))(FI
B(FI
B(町ー J-INDEX J0.
07
14O.0708

GMDH で構成される変数の関係が 2 分木であることに注意されたい.たとえば，入力変数が {X }， X2 , X g , x，} で出Generation6

力変数が y である関数の GMDH の結果が，fitness s‑fitness(D唱wey DecimalNotation)115) (128 , 150)
0.
1 &0.1.1.
2 0.
0714 0.
0720(FI
B(FI
B(MY‑J‑INDEX2)))
韓関rentsxsite130) (4, 1(1)0 &0.
2
(限+ (FI
B(MY‑J‑INDEX1))(FI
B(KY+1J‑INDEX)))

0.
00
50%1=G副 ，.x2 (x }, %2) ,0.
00
41(1)

%2=G .x 2, .1 (x. , %1) ,(2)ﾝ =G"""Z2 (X' , %2) ,(3)のときを考える.ここで %1 と %2 は中間変数 ，は推論結果である.各関数 G は重回帰分析で求めNote:max=0.0833 min=0.
0010 avg=0.
047217ncros
s= 369nedi
t= 366nmu
tation= 2maxn=0.
0791 minn=0.
0009 avgn=0.
0328(Last50)

た 2 次式である.このとき y は，入力変数を終端ノードとする木，(NODEl(NODE2(a) 第 5. 6 世代

(NODE3(x!
l (X2))(x.
)

Populationreport
書stringGeneration6(ぬ)))‑fitnessfitness s115)

0.
07140.
07201(町30)+((FFIIBB((HHEY+‑Jl‑JIN‑DIEEDXUl))))0.
00500.
0041(FI
B(FIB (HY明 J- INDEX2)))で表現される.ここで NODEl ，NODE2 , N O

DE3 は各々宮， %2 ， Zl に対応する.各ノードは Gについての情報を保持する.
以上のように考えると2 節で述べた構造的 G

A の手法が GMDH による探索にそのまま応用できる.さらに GA の選択に際しては MDL にもとづく適応度計算を採用した.これは木の記述長とGeneration7xsitefitness s‑fitness(DeweyDecimalNotation)
0.
1.
1 &0.
2.
1 1.
0000 0.
1156129) (115, 130)
(KY+(11B(HY‑J‑INDEX1))(FIB (i町ー J-INDEX 2)))
韓関rents

当てはめ誤差のトレードオフを評価するためである.

MDL の GA への応用については決定木の学習実験などでその有効性を確認している [Higu­chi
93J.
Note:max=1.00∞ min =0.0010 avg=0.0578
51ncross= 438nedi
t= 432nmutation= 2maxn=0.2106 皿 inn =0.0∞9 av
gn=0.
0364(Last50)

程式と呼ばれ，(b) 第 6. 7 世代

dx(t)̲ ax(t-~)
10(t‑d一 bx(t)dt 1+x

一一一一一

図 3
的爆発にある.古典的な手法としてGMDH(GroupMethodofDataHandling) が開発されている口 va344 (20)

図 4 は時系列予測の結果を示す. (a)は予測すべきデータである.これは Mackey-Glass 微分方を満たす.ただし ，仏)

a=O.2 , b=O.I ， τ=17 である.この式は 3.5 フラクタル次元のストレンジ・アトラクター© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オベレーションズ・リサーチ

を有する [Tenorio90J. 時系列予測問題とは，現在値をx(t)chaos.ans5

過去のデータの関数，x(t}=f(x(t‑I), x(t-2) , …, x(t-M)).

(5)として求めることである(この実験ではM= 1O とする).
以下では x(l)- x(100} を訓練デ}タ， x(IOI}‑x(500)をテストデータとした.用いたパラメータは，集団数 60 ，Ger輔overの確率 0.6 ， Gmutation の確率0.0333 である.

0.
2(t -i) を表わす.

図 4(b) と(巴)は GA による 233 と 1740世

TEm陪 t‑

また終端ノードは ((1)， (2)，…，刷}である.ただし (i) は z200100

代での予測結果である.世代 1740 で獲得された構造表現

図 4とそのノードに記録されている係数の一例を表 2 に示す

x(tI(ただし G. I> .
2(zl>Z2)=ao+ 向的 +a2Z2+ a S Zl Z2+ 向Z12+l.2300400500ーー

テストデータ

訓練データ(8.
)

GMDH/last2.temp

a5Z22). (c) においてはテストデータにおいて完全な一致が見られることに注意されたい(平均誤差 5.06x 10‑6).

0.
8

この他にパターン認識の実験などにより，構造的 GA が0.
6

GMDH の探索において有効なことを確認した.なお本0.
4

節の実験の詳細や結果の議論については [Iba93J を参照

0.
2

されたい.

Timet1005. おわりに

200
図 4

本稿では， GA を構造的表現に拡張した適応的手法に300

ムーー一一一」ー

400500(ゆlast6.tempx(tl

もとづく知識の獲得と生成のための枠組みを示し，有効性を試すための実験について説明した.

GA の枠組みの利点は， PTYPE/GTYPE の表現を通して構造をオベレータで直接操作し，適応選択による結果を構造的表現として得られることである.この点が分散表現を重視するコネクショユスト・アプローチとは0.
2異なり，記号レベルの学習との統合をはかる上で有利でTimet.
.
L100ある.特に高次の知識表現の変換手法( representational

表 2200図 4300400500(c)

獲得された木構造(NODE95239(7)(NODE95240(NODE95241(NODE95242(NODE95243(NODE95244(8)(NODE95245(8)(NODE95130(2)(3))))(NODE95173(10)(NODE95174(NODE95175(4)(1))(5)))
)
(5))

(6)
)
(NODE95178(NODE95179(8)(3))(10))))

1993 年 7 月号

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(21)345change) としての可能性を示唆し， 機械学習におけるrepresentation , ETL-TR92・ 12 ， InProc. of2nd「発見的論理 J [Lakatos76J 手法として重要であると考PacificRimInternational Conferenceon Artiｭ
ficialIntelligence (PRICAI92) , 1
992える.

[Ibeetal.
92c
J Iba , H. , andHiguchi , T.
:Evoluｭ
参考文献

tionaryLearningo
fPredatoryBehaviorsBasｭ

[伊庭90J 伊庭斉志，情報の進化と創造的学習について，
人工知能学会基礎論研究会，

SIG-F/H/K・ 9001 ・ 10 ，

ed on Structured Classifiers ,ETL-TR92・ 34，

In Proc. of2nd International Conference onSimulation of Adaptive Behavior (SAB92) ,1990[伊庭91aJ 伊庭斉志，構造的表現の適応的学習とその応用，情報処理学会人工知能研究会，

AI-76・ 2 ，1991[伊庭91bJ 伊庭斉志，適応的学習に基づく知識の獲得と生成，第 5 回人工知能学会全国大会，

1991[Davis91J Davis , L̲
:Order‑based genetic algoｭ

1992[Ibaetal.
93] Iba , H. , Kurita , T. deGaris , H.
and Sato , T.
:System identification based onstructuredgenetic algorithms ,ETL-TR93・ 1 ，submitted to ICGA93 , 1
993rithms and the graph coloring problem , in[Ivakhnenko71] Ivakhnenko , A.G.
:Polynomial ,Handbookofg
eneti
calgorithms , (ed̲ Davis ,theoryofcomplex systems , IEEE Tr. SMC ,L.), VanNostrand Reinhold , 1
991

vol.SMC-I , nO.4 , 1
97
1[Ehrig87J Ehrig , H. , Nagl , M. , Rozenberg , G.

[Kitano90] Kitano , H.: Designing neural netｭandRosenfeld , A.:Graph‑grammarsandtheirworks using genetic algorithms with graphapplicationt
ocomputerscience , Lecturenotes

generation system , Complex systems, vol.4 ,incomputerscience , vol.291 , Springer‑Verlag

1990[Knuth67] Knuth , D. E.
: The ar
tof computer1
987[Fantana90JFontana , W.:AlgorithmicchemistryinA
rtificialLife11, Addison Wesley , 1
990

programming , vol.
l. Reading , M. A:Addison-Wesley , 1
967[Goldberg89JGoldberg , D.E. , :Genetic algorithms[Koza90J Koza , J.Geneticprogramming:A paｭ

insearch , optimizationandmachine learning ,radigm forgenetically breeding populations

Wesley , 1
989o
fcomputerprogramst
osolv
e problems , Reｭ[Higuchietal.
93J Higuchi , T. , Iba , H. , deGaris ,H.Niwa , T_ , Tanaka , T̲andFuruya , T.
:EvolｭvableHardware

genetic‑based generation ofelectroniccircuitryatgateandhardware desｭcriptionlanguage levels , submitted to ICGAport No. STAN-CS・ 90・ 1314 ， Dept. of Compuｭ
ter Science , Stanford Univ. , 1
990[Langton89] Langton , C. G.
:Artificia
1 life , In
Artificial Life , Addison-Wesley , 1
989.
:Proofs and refutation[Lakatos76J Lakatos , I
thelogicofmathematical discovery , Cambriｭ

93 , 1993[Ibaetal.
92aJ Iba , H. , Akiba , S. , Higuchi , T.
andSato , T.
: BUGS:A bug‑baseds
earchstraｭ

976 (邦訳:数学的発見のdgeUniversityPress , 1
論理証明と論駁，佐々木力訳，共立出版，

1980)

tegyusingg
eneti
calgorithms , InProc.of2nd[Tenorioetal.
90
J Tenorio , M.F.and Lee , W.:

ParallelProblem SolvingfromNature(PPSN

Selforganizingnetworkforoptimum superviｭ92) , North-Holland , 1
992

sed learning , IEEE Tr. Neural Netwarks ,[Ibaetal.
92bJ Iba , H.and Sato , T.
: Meta‑levelvol.1, no.1 , 1
990strateg
ylearningforG A based an structured348(22)© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オベレーションズ・りサーチ