連載講座

遺伝的アノレゴリズムの基礎と応用[ 1J
小林重信
l
1
川
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川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11l川|川|川川
11川
11川
11川
11川
11川
11川
11川
11川
11l川l川|川川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11l川川
11川
11川
11川
1111川
川
11川
11川
11111
川川
11川|川
11 川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11111川川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11山
11川
11川
11川
11l川川
11川
11川
11川
11川
11川
11川
11川
11川
111111
川
川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川|川
11 川
11111
川川
11川
11川
1111111
川
川
11川
11川
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川
1111111
川111川
川
11川
11川
11川
11川
11川
11111
附
1111
川
川
11川
11川
11川
11川
11川
11川
11附
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11111
附

1.

はじめに
(branch and boundmethod) の枠組みが提案され，現在，組合せ最適化問

oの有効性は領域知識を利用した枝刈り規則 (pruningrule) の質にいちじるしく依存する.たとえば，平面 TS‑h

っ汎用的な方法として広く利用されている.分岐限定法@40.,

題に対するオベレーションズリサーチ的接近の代表的かh“・

1960年代前半に，分岐限定法

P については，強力な枝刈り規則が知られているが，ジ
図 1ョブショップスケジューリング問題では，良質の枝刈り規則は見いだされておらず，組合せ的爆発 (combina­
本連載は，torial explosion) の問題をかかえている.
1970年代後半に，エキスパートシステム(expertsystem) の枠組みが提案され，現在，組合せ最適化問題に対する人工知能的接近の代表的かっ汎用的な方法として広く利用されている.エキスパートシステムの有効性
は領域専門家から獲得される経験的知識(expertise)

し遺伝的アルゴリズムの概念図r 遺伝的アルゴリズムの基礎と応用」と題

3 回にわたり，GA の基本的な概念，関する理論および GA の応用について，できるだけ平易に解説することを通じて，本学会会員の GA に対する理解と興味を深めることを目的としている.

2. 遺伝的アルゴリズムの基本的概念の質と量にいちじるしく依存する.たとえば，航空機や列車のダイヤ編成を対象としたエキスパートシステムは実用化されているが，ジョブショップスケジューリング

問題では，スケジューリングのための経験則の蓄積が不十分で，知識獲得 (knowledge acquisition) の問題を遺伝的アルゴリズム(Geneticは，ダーウィンの自然淘汰理論Algorithm(NaturalGA)SelectionTheory) に基礎をおく生物の進化過程を模倣した工学的モデルであり，人工生命(Artificial Life)の基盤技術として使われているが，探索手法として頑健な枠組かかえている.

このように，分岐限定法とエキスパートシステムは，領域知識が利用可能で、あることを長所として，見方を変えれば，領域知識に依存せざるをえないことを短所としみをもち，しかも並列処理との親和性が高いことから，最近，組合せ最適化問題に対する新しいパラダイムとして，各界から大きな関心と期待が寄せられている.
GA の枠組みの提案は Holland による口].図 1 は Gて共有している.

1980年代に入り，自然界に存在する物理学的あるいは生物学的な現象を利用して最適化問題を解こうとする研究が盛んになってきた. Hopfield型ニュラルネット [IJ.
シミュレーテッドアニーリング [2J などがそうであり，本連載でとり上げる遺伝的アルゴリズムもそのような流れ

A の挙動を概念的に示したもので，選択・交又・突然変異と呼ばれる 3 つの遺伝的オベレータを順に適生することを繰り返して，環境にもっとも適合する個体群を見いだすように.

GA がふるまうことを示している.

2.
1 GA のデータ構造
はじめに，の 1 つに位置づけられる.

GA で使われる基本的な概念をいくつか紹介する.最小構成要素を遺伝子
こばやし

GA の挙動にしげのぶ東京工業大学総合理工知能科

うる値を対立遺伝子 (allele)(gene) ，遺伝子がとりという.

遺伝子の並び文学専攻

字列干 227 横浜市緑区長津田 4259

遺伝子の位置を遺伝子座(l ocus ).染色体の長さを染色258 (44)(string) を染色体 (chromosome) •© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

染色体上のオベレーションズ・リサーチ

体長 (chromosome length)という.

なお，染色体の表現は，文字列に限定される必然性はない.染色体として，木構造 (treestructure),

グラフ(graph) ，リスト構造(list structure) ，行列 (matrics) など，構造をもっ表現も許される.

GA の特徴の 1 つは構造を，直接，遺伝的操作の対象としうることにある.

染色体によって特徴づけられる個を個体ー〕(indivisual) 個体の集まりを集団 (popula­tion) ，集団の大きさを集団サイズ (populat­ion size)と L 、う.

Simple GA おける 1 点交叉

図 2

最適化問題を GA 上にモデル化する際，一般につの解候補が l つの個体に対応づけられる.各親の個体ベアはそのまま残す.

個体を正の実数に写像する関数を適応!度関数( fitness仏)

function)

各個体について，一定の突然変異率 (mutationという.

最適化問題では，目的関数と制約突然変異 (mutation)rate)

条件を考慮したベナノL ティー関数を適応度関数に対応づに従って，突然変異させるか否かを決定する.突然変異ける必要がある.

させる場合，遺伝子座をランダムに 1 つ指定し，その値染色体によって規定される形質の外部表現形式を表現型 (phenotype) ，染色体による内部表現形式を遺伝子型 (genotype)という.

遺伝子型に対応する表現型が元問題の制約を充足しないとき，その染色体は致死的(fatal) であるという.

クルを l 世代(genetic operations) の 1 サイ(one generartion)という.

simple GA における交叉の様子を図 2 に示す.この2 種 4 個の個体からなる集団を扱っており2通りのベアリングが可能で，異なった染色体をもっ個体

GA の基本形の 1 つとして， Simple GA がある [4J.

Simple GA は以下の手順からなる縫率的過程である，[SimpleGA]

力:ベアとなったとき，交叉率四で交叉が決定され，交叉箇所が 2 ヵ所あることから2 通りの子のベアが生成可能であることを示している.

(1) 初期化 (ini tialization)

Simple GA の実装にあたっては，通常，集団サイズ各遺伝子座の遺伝子に対し，一様分布に従ってo ま

たは l の対立遺伝子を割り当てることにより，ランダムな染色体をもっ個体を集団サイズの数だけ生成し，初期集団とする.
選択(2)-(4) の遺伝的操作

例では

2.
2 SimpleGA(2)を他の対立遺伝子に置き換える.

を数十から数百，交叉率を 0.6 位，突然変異率を 0.01 位に設定寸るのが，経験的に得られたおおよその目安とされていゐ.

Simple GA は，単純で小規模な問題に適用する限り，問題はないが，対象問題が少し複雑・大規模(selection)になるム最適解に到達する前に，すべての個体が同ー

ルーレット選択によって，集団中から個体を復元抽出の染色体をもつか，またはある部分空間に集団全体が陥(samplingwith replacement) することにより，集団る初期収束 (early conversion) をまねく危険性を内包を再編成 (reproduction)している.

する.

再編成された集団から個体を非復元抽出して，個体ベアをランダムに生成する(randompairing).

(3) 交叉 (crossover)に従って，する.交叉させる場合

GA の構成要素および設計問題

GA がもっ潜在的能力をフルに引きだすためには，遺(2) でつくられた各個体ベアに対して，一定の交叉率(crossover rate)

3.

交叉させるか否かを決定伝的オペレータの役割を十分認識した上で，対象問題に対して，オベレータの設計やパラメーターの調整を適切点交叉により，子の個体ベアに行なうことが必要である.

を生成し，親の個体ベアと交換する.交叉させない場合，

3.
1 コード化/交叉問題

1993 年 5 月号

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

(45)251

実行不可能解になるかもしれない.また，実行可能ではGA空間あっても，両親とはまったくかけ離れた子の個体が生成されてしまうかもしれない.不適当な個体が生成される可能性が高いほど，PIGA はランダムサーチより劣る性能を示すことになるであろう.

コード化および交叉の評価規範として次の条件が考えられる [5].

〔コード化評価規範〕1) 完備性(completeness)

問題空間上の解候補はすべて染色体として表現できることが望ましい.

2) 健全性
図 3

問題空間と GA 空間の対応(soundness)

GA 空間上の染色体はすべて問題空間の実行可能な解候補に対応づけられることが望ましい.

表現型 (phenotype) によって規定される解候補の集まりからなる空間を問題空間，

遺伝子型 (genotype)3) 非冗長性(nonredundancy)

染色体 (GA 空間)と解候補(問題空間)は l 対 l にによって規定される空間を GA 空間と呼ぶことにする.

対応づけられることが望ましい.

問題空間と GA 空間の対応関係をコード化 (encoding/〔交叉の評価規範〕

decoding)

4) 形質遺伝性と呼ぶ.

コード化問題とは，

問題空聞からGA 空間への写像 (encoding) および GA 空間から問題空間への逆写像 (decoding)を規定する問題をいう.図

3 は問題空間と GA 空間の対応関係を示している.
図 3 で、は，問題空聞から GA 空間に向かうアークは表現型から遺伝子型へのコード化を，(characterpreservingness)

親の形質は交叉によって生成される子に適切に継承されることが望ましい.

完備性は自然な要求である.致死遺伝子の生成を排除する健全性は，一般に，これを満たすことが困難ではあGA 空聞から問題空るが，交叉に限定を加えることにより，充足できる場合間に向かうアークは遺伝子型から表現型への逆コード化がある.致死遺伝子を許容するコード化は，無駄な探索を表わしている.

を強いられるが，致死遺伝子の生成を抑制するための計

GA 空間上で個体 P 1 と P2 の間での交叉により，子の個体が生成され，これを逆コード化す算コストが節約され，結果的に効率よく最適解を見いだ

ることにより，問題空間上に，親 P 1 と P2 の性質を何すことができる場合もあり得る.

らかの意味で継承した個体 C 1 と C2 が生成されること対応関係が多対多の場合，対応づけのあいまいさを解消を図 3 は示している.

するための規則が必要とされる.

simleGA でも採用されている i 点交叉 (one point

GA 空間と問題空間の図 3 に示すように，コード化と交叉は，不可分の関係crossover) では， 2 つの染色体の聞で，ランダムに選ばにあり，れた交叉箇所の後半部分を交換する.これを複数の交叉で述べた評価規範を満足していても，交叉が不適切であ点に拡張した操作を多点交叉 (multipointcrossover)

GA が動作する空間を定義する.コード化が上れば，好ましい解候補を生成することができず，GA はといい，あらゆる多点交叉が一様に起こるような操作をランダムサーチと同程度またはそれ以下の性能しか示さ一様交又 (uniform crossover)ないであろう.

1 点交叉に対して，という.

GA の性能は遺伝子座の染色体上形質遺伝性は交叉が満たすべき評価規範として妥当とへのコード化に敏感であるが，一様交叉に対しては遺伝思われる.形質の定義は問題領域に依存することから，問子座の位置には無関係なことが知られている.一般に，題領域ごとに形質を定義したうえで，形質遺伝性を満たコード化および交叉の設計は，すコード化と交叉の方法を見いだすことが要求される.

GA の基本的性能を決定

つe ける重要な課題て、ある.

コード化と交叉については，たとえば，巡回セールス

コード化および交叉が不適切であれば，GA 空間で交叉によって生成された個体を問題空間に逆写像したとき258 (46)

マン問題 (Traveling

Salesman Problem:TSP) を対象に，これまで次のような工夫が試みられてきた.

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

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

と呼ばれるコードのある部分文字列に着目して，その順序を反転させるこ

化では，都市名を遺伝子として，起点、とする都市から巡とをいう.染色体上の異なった位置にある 2 つの文字ま回する順に都市名を列挙した文字列を染色体とする.パたは部分文字列の位置を交換することも突然変異の l つス表現された個体ベアに対し点交叉を適用すると，の方法である.

パス表現 (path representation)

多くの場合，致死遺伝子を生じてしまう.

Grefenstette は，突然変異は，染色体上のある遺伝子座の値を他の対立致死遺伝子を抑制するコード化に遺伝子に置き換えることにより，個体の近傍に新しい個representation)体を生成するもので，その意味で突然変異は，局所的なおける工夫として，順序表現 (ordinalと呼ばれるコード化を提案している [6]. 順序表現では，ランダムサーチの一種とみなせる.突然変異は致死遺伝

次に巡回する都市が未訪問都市リストの中で何番目にあ子を生じる危険性を内包している反面，集団として爽失るかを調べ，その番号を遺伝子とし，起点都市から順にした対立遺伝子の回復に寄与することも期待でき，集これを並べた文字列を染色体とする団の多様性を維持するうえで有効な l つの手段ともいえ順序表現された個体ベアに対し点交叉を適用すると，致死遺伝子の生る.

成は抑制されるが，親から子に継承される形質は，いず交叉と突然変異の間には，相補的な側面と競合的な側れも交叉箇所の前半部分だけであり，後半部分に相当す面が存在する.集団全体が探索空間のある超平面に陥っる親の形質は失われてしまうことに問題がある.てしまった場合，突然変異により超平面からの脱却が可Goldberg は，致死遺伝子を抑制する交叉の工夫とし能となることが期待できることおよび突然変異による局

mapped crossover) を所的な探索が有効に働くこともあり得るとういう意味に提案している [7J. 部分写像交叉では，パス表現された個おいて，突然変異は交叉に対して相補的である.しか体ベアに対し点交叉により，染色体の前半と後半をし，交叉によって形成された優れた形質が突然変異によ交換した後，致死遺伝子を生じないように，部分的な入り破壊されてしまうことがあるという意、味において，突れ替え，すなわちパッチを当てることにより，致死遺伝然、変異は交叉に対して競合的である.て，部分写像交叉 (partially3.
3 選択戦略および選択圧力子を抑制する.

致死遺伝子の抑制を重視したこれらの方法は，形質遺選択の目的は，集聞における個体の適応度の分布にも伝性に関しては不完全であるために，ランダムサーチととづいて，交配のための候補を選抜するための確率的決同程度の性能しか示さないことが知られている.

定を行なうことにある.

筆著らは，形質遺伝子を重視した交叉の工夫として，

Simple GA で採用されている代表的な選択戦略であサブツアー交換交叉 (subtour exchangecrossover)

るんーレット選択と呼ばれる方法を提案している [5J. サブツアー交換交叉体が選択される確率は集団の適応度の総和に対するそのは個体の適応度の比によって与えられる.

2 点交叉の特殊なもので，パス表現された個体ベアに対し，サブツアーに含まれる都市集合が一致するときに限って交叉を行なう.サブツアー交換交叉によって生(roulette selection) では，ある個選択によって集団が適応度の高い個体群に収束していく様子を比験的に選択庄力(selection pressure)とL、成される子は L 、ずれも，実行可能解であり，しかも両親う.ルーレット選択は，同じ個体の復元抽出 (samplingの形質すなわちサブツアーをできる限り継承することがwith replacement) を許容していることから，他と比べて適応度が突出した個体が存在するとき，その個体が保証される.
平面 TSP では，交叉経路をもっツアーは最適解にはなりえない.サプツアー交換交叉を実装した GA では，500都市までの問題において .1順序表現や部分写像交叉で繰り返し選ばれる可能性が高く，選択圧力が高くなりがちな方法といえる.
選択庄力を調整する手っ取り早い手段としてスケーリ排除できなかった交叉経路を排除て、きることが報告され

ング (sca 1ì ng) が考えられる.集団内に突出した適応度ている [5].

をもっ個体が存在したり，反対に集団内での適応度のバ

3.
2 突然変異の役割

ラツキが小さいとき，適応、度に対し線形または非線形の突然変異の基本は，ある確率て、選ばれた遺伝子座の値変換を施すことにより，各個体の選択確率が適応度の違を他の対立遺伝子に置き換えることにある.突然変異の変型として，逆位 (inverse) がある.逆位とは，染色体1993 年 5 月号

いに応じて適切に配分されるように調整する.

集団内に同じ染色体をもっ個体が複数個存在すると© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(47)259(バランスの取れた探索}(適応度設計}....一一一一ー(選択/突然変異)・斗(ランダムサーチ}
図 4

図 5

選択圧力制御モデノレ

GA の性能レベルと設計ベルの対応関係

き，ルーレット選択では，その個体の選択確率が複数倍

選択は，集団の中から個体を取捨選択するだけであり，されてしまうため，同じ個体の重複抽出が加速される効

それ自身は新しい個体を生成する能力をもたないが，問果が生じる.同じ個体の行き過ぎた重複抽出を抑制する

題に合った適切な制御戦略を設定し，選択圧力を適切にために，集団内に同じ個体が複数個存在していても，選変化させることにより，大域的探索から局所的探索への択に際しては，同じ個体は l 個しか存在しないものとし円滑な制御を実現する役割をになうことができる.て選択するシェアリング (sharing) が提案されている.
シェアリングは，ルーレット選択に比べて，選択圧力は4.

GA の性能レベルと特徴

GA は確率的かつ並列的なアルゴリズムであり，局所低い方法といえる.

図 4 は，シェアリングとルーレット選択を線形結合し的探索と大域的探索を効果的に組み合せることにより，た選択圧力モデルの一例を示している.図 4 では，個体既存の探索手法と比べて，頑健な挙動を示すことが期待の種類をふ，種類 Si の適応度を f (S;) ，種類 Si の個できる.しかし，体数を n (S色)で，それぞれ表わしている.

選択圧力バ

ためには，ラメータ Pγ は 0-1 の聞の値を取り ，ェアリングに一致し ，Pr=0 のときシPr=1 のときルーレット選択に一致する.

GA の潜在的な能力をフルに引きだす

GA のそれぞれの設計段階において構成要素やパラメータを適切に設計することが必要である.

4.
1 GA の性能レベル [8J
図 5 に GA の設計レベルと性能レベルの関係を示す.

一般に，探索の初期局面では，探索空闘を広く探索す

モンテカルロ法に代表されるランダムサーチでは，あるるために，選択圧力を低く設定することが望ましく，探一定の分布に従って，解候補をサンプリングする探索方

索の終期局面では，収束を加速するために，選択圧力を法であり，近似解法としてはもっとも一般性が高いが，高く設定することが望ましい.図 4 の選択圧力制御モデ

すでに発見された解候補の情報を利用しないことから，

ルを採用する場合，高い性能を期待することは困難である.

選択庄力パラメータ Pr の値を徐々GA は少なくとに上げていく制御則が考えられる.この制御則は，シミもランダムサーチが示す性能レベルをクリアーしていなュレーテッドアニーリングにおける温度パラメータ T をければならない.

徐々に下げていくことに対応づけられる.

交叉を排除した選択と突然変異だけの GA は，シミュ一方，選択が適応度の分布に影響されることを排除す

レーテッドアニーリングの並列バージョンに相当する.

るために，適応度の順位だけにもとづいて選択確率を決

選択圧力を制御することにより，局所解からの脱却はあbased selection) がる程度可能ではあるが，大域的探索能力をもたないこと定するランクベース選択(rankある.に限界がある.

また，確率的選択では，適応度最大の個体であってもGA における大域的探索能力は交叉に求められる.

3.

淘汰されることを許容しているが，最適化問題のタイプ

1 節で議論したように，交叉が有効に機能するためには，によっては，適応、度最大の個体を無条件て、次世代に残す問題に適したコード化が必要である.コード化/交叉設

エリート保存戦略(elitest preserving strategy)併用することも考えられる.

280 (48)を計に失敗すると，ランダムサ一千と同程度の性能しか得られない場合がある.

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

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

コード化/交叉が適切に設計されても，適応度関数の設計に失敗すると，編し問題 (deceptive problem) がGA の高速化は，きわめて近い将来に，実現・普及するものと見込まれる.

生じて，局所解に陥る場合がありうる.
図 5 は，コード化/交叉の設計，適応度の設計が適切

今回は，GA の基本的概念，構成要素および GA の設に行なわれ，さらに実装パラメータの調整が適切に行な計問題を中心に議論した.次回には，組合せ最適化問題，われることにより，大域的探索と局所的探索のバランス特にスケジューリング問題を対象として，のとれた探索が実現されることを示している.

デル化の実際を紹介する.

パランスのとれた探索は，特に組合せ最適化問題に要求されるものであり，

GA によるモ

参芳文献

GA の枠組みはそのような潜在能[1J Hopfield , J.J.and Tank , P. W.

力をもつものと考えられる.

Neural4.
2 GA の特徴 [9JComputation of Decisions in Optimization

探索手法としての GA は，次のような特徴をもっ.

Problems , BiologicalC
ybernetics. Vo1.81(1985)(1)

確率探索法 (Stochastic Search)

141‑152.

GA における選択操作は，確率的であることから，適[2J Kirkpatricks , S. , et a1.
:Optimization by

応度の低い個体であっても，交配の候補として選抜されSimulated Annealing , Seience , Vo1.220 (1983)る可能性を許容している.これは，シミュレーテッドアニ}リングにおける確率的な状態遷移に相当する.選択

圧力を動的に制御することにより，

SA における温度スケジューリングをシミュレートすることが可能である.

(2) 多点探索法(Multi-Point671‑680.

[3J Holland , J.H.:AdaptationinNaturaland
Artificial Systems , TheUniv.Michigan Press ,1975andMITPress , 1992.

[4J Goldberg , D.:GeneticAlgorithms in Seaｭ

Search)GA における集団サイズは，ビームサーチ (beamsearch) におけるビーム幅に相当する.ビームサ}チでは，多点、情報を新しい探索点の生成に利用していないが，rch , Optimization , and Machine Learning.

Addison-Wesley , 1
989.
[5J 山村，小野，小林:形質の遺伝を重視した遺伝的GA では，交叉を通じて新しい探索点の生成に多点、情報アルゴリズムに基づく巡回セールスマン問題の解法，を利用している.

人工知能学会誌，(の直接探索法 (DirectSearch)

7 , 6(1992) , 1049‑
1059.

[6J Grefenstette , J. , Gopal , R. , Rosmaita , B.
J.

GA は，適応度関数の微分値を陽に利用しないことか

andVan Gucht , D.:Genetic AIgorithms forら直接探索法 (Direct Search) の一種である.さらthe Traveling Salesman Problem , Proc. ofに，ランクベース選択を採用すれば，適応度関数の値を序数的にしか利用しないことから，解候補群を人間の評価者が主観によって順序づけることさえすれば，動作可能であるので，

GA はGA は対話型解法としても利用できる.

(4) 並列探索法

6‑168.
ICGil. '85 , 1985 , 1[7J Goldberg , D. and Lingle , R.

Alleles ,loci , and thetravelling salesman problem ,Proι .

ofICGA'85 , 1985 , 1
54‑
159.

[8J 山村，小林:遺伝的アルゴリズムによる組合せ最(para l1 elSearch)

GA における遺伝的操作のうち，交叉と突然変異の操作は逆列処理が可能であり，超並列マシンとの親和性も適化，シミュレーション，

12,

1(1993) , 75‑81.

[9J 小林:遺伝的アルゴリズムの現状と課題，計測と制御，32,1(1993) , 2‑
9.

高いことから，超並列マシンまたは専用マシンを用いた

1993 年 5 月号

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

81(49)2