遺伝的アノレゴリズムと最適化

西川緯ー，玉置久
川
11附
11111
日川
111111
川
川
11川
11川
11川
11111
削
111
川
川
11川
11川
1111111
川
川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川
11川|川
11 川
11111
川
11川
川
11l川
l川|川
l川
川
11川
11川
11川
11111
川
川|川|川
11 川
11川
11川
11川
11川
11川
11川
11l川
川|川|川|川11 11111川川
11川!川|川|川
11 l川
11川
1刊111
川
川|川|川
11 川|川|川|川
11 川
11l川
川
111111川
川
11川
11川
11川|川|川
11 川
11l川
l川
川
11川
11川
11111
川
川
11川|川|川|川|川
11 川
11川
11l川
川
11川
11川
11l川
l川|川
l川
川
11川|川
11 川
11川
11川
11川
11川
11川
11川|川|川11 川|川|川
11 l川
川
11川
11川
11川
11川!川
11 川
11川
11川
11川|川|川|川
11 川
11川
11川
11川
11川
11川|川|川11 川|川11 1111川
川
11川
11川
11川|川|川|川
11 川
11川
11川
11l川
川
11川
11川
11川|川|川11 川|川11 川111111
川
川
11川
11川
11l川
川
11川
11川
11川
11111
川
川
11川|川
11 川
11l川
l川
川
11川
11111
川|川|川
川
11川
11川
11川
11111
川
川
111
l
1

い近似解法 J ，つまりあまり計算に手数がかからず，しか1. 最適化の考え方も安定的によい(必ずしも厳密な最適でなくとも，それ何らかの意味で望ましい「もの」あるいは「行動」を計画・設計したり実現・実行したりするのが技術の目的に近く現実的に満足できる)近似解を求めうるアルゴリ
ズムが必要とされるのである.

であり，そのための手段や方法を体系化するのが工学の役割であるとすれば，適化する J

r最も望ましくする J

つまり「最とし、う命題が生まれ，その方法を探究するという工学にとって必然的な課題が現われる [IJ.
最適化を数理的に扱う手法は，従来からも，問題の特徴を巧みに利用してよい近似解を求めるために，各種のヒューリステイクスがしばしば用いられてきたが，遺伝的アルゴリズム(GA) はよい近似解を求めるための，比較的一般的な枠組みを与える

OR の分野で普から重1 つの有力なツールである [3 ， 4J.

ここでは，組合せ最適要な研究課題とされてきた.いろいろなタイプの数理計化問題への GA の適用について種々の構成手法を整理し画法がその典型である.数理計画問題では，まずわれわながら解説するとともに，組合せ最適化問題の典型例でれが決定すべき，あるいは決定できる複数個の決定変数あり，実際上も重要なジョブショップ型スケジューリンが定義され，次に最小化あるいは最大化すべき目的関数

グ問題 (Jobshop Scheduling Problem , JSP) を対(これは決定結果の良さ，あるいは望ましさを定量化し象として，た物指)および決定変数が満たすべきいくつかの制約条

2. 組合せ最適化

件が，数式として表現される.すなわち，制約条件を満たす決定変数の組のうちで，目的関数値を最小あるいは最大にするものを求めよ，と L 、う問題である [IJ.

GA の応用を紹介する [5 ， 6， 7J.

組合せ最適化問題とは，組合せ的な制約条件の下である目的関数を最小化(または最大化)する数理計画問題

数理計画問題のうち，変数が連続値(実数値)をとり，であり，一般に次のように記述される [1 ， 2J.

すべての数式が線形で表わされる線形計画問題は比較的minf(x)(1)

subject to xE F(2)z

少ない手数できちんと解ける.しかし，そうでない非線形問題は近傍の連続性にもとづく逐次近似的な方法でしか扱えず，しかも凸性が保証されないと局所最適解が現われたりする厄介さを伴う.また，変数が離散値をとる

ただし ，F は組合せ条件を含むもので，特に F が整数条件を含む場合は整数計画問題と呼ばれる.

組合せ最適化問題では，解候補の組数は可付番有限個でF が組合せ集合である場合には，実数集合を対象とすはあるが，連続値の場合のような近傍の概念が成り立たる場合によく用いられる，連続性や微分の概念にもとづないので，原理的には全数探索(可能な場合の列挙)しく最適化手法は使えない.したがって，一般には可能解か手がない.ところが問題の規模，つまり変数の数が多を列挙する方法によらざるをえないが，先にも述べたよ

くなると組合せ数は爆発的に増える(たとえば変数の数

うに，大型の問題に対しては列挙は事実上不可能である.

に対して指数関数のオーダ)から，超高速計算機をもったとえばてしても現実には全数探索は不可能である [1 ， 2J.

約 2.4x 10 18 となる.そこで，列挙の範囲をいかに限定すしたがって，非線形問題や組合せ問題に対しては，

r賢

n 変数の順列の数 n !はn =20 の場合でもるかが重要になる.

従来の最適化手法を厳密性(得られる解の最適性)のにしかわ

よしかず，たまきひさし

観点から見れば，

京都大学工学部電気工学教室(1) 厳密解法:厳密な最適解を求める方法，

干 606 京都市左京区吉田本町(2)1993 年 7 月号

近似解法:近似最適解を高速に求める方法，© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(23)347遺伝子型。.0"0"'0.0.0.0'"。令。 "'0"0"'0

γ@・@φ0"'0"0"0.0"'0.0・。.。

。ー・-Q...o... 一一ーーーーー、

40 時刻 i

川!?i|;-3 』璽悶

J/--ーー一一一一ーーーーー

表現君主一一一一一、、一ーーーーーーーーー一一ー、ー---ー一ーーー _J

Jl/‑‑、ーー---ーーー一ー ...0...0'"。

I i・"，;':10.0"'0"0"0・@・ 0..0..0・@・@・ 0(a) 列挙的手法

適応度 :82

図 2•

遺伝的アルゴリズムによる最適化の枠組み

スケジューリング問題を例として取り上げ，表現型としてスケジュール(ガントチャート)を示してある.

(b) 発見的手法

3. 遺伝的アルゴリズムによる最適化
図 1

組合せ最適化手法
GA による探索の枠組みを図 2 に示す.の基本的考え方。

、

枠が可能領域(解の全体。

、。、

I戸、、
-v 、槍晶、

̲00

〆，0-r

目的関数 :40、/-、、_/

I・iJ、 d〆、、集合)，丸が 1 つの解候補をそれぞれ表わす.また，

j、，(c) 探索的手法

黒丸は最終的に選ばれる解を表わす.

GA では，まず問題の解候補を個体の表現型と考え，それに対応する個体の遺伝子型(染色体)を 0/1 記号列によって表わす.便宜上，今後は個体の遺伝子型を単に個体と呼ぶ.
次に M個の個体からなる集合 (population) を作り，集合中の個体に対して選択 (selection)および突然変異

交叉 (crossover)(mutation) 演算を繰り返し適用し，適応度 (fitness) の高い個体(すなわち質のよい解候補)に大別される_ (1)には動的計画法(D P) や分校限定法(BAB) などがあるが，いずれも広大な解空間をくまなく探索することが基本になり，膨大な計算量(時間)を要する.それに対して， (のでは問題に関する先験情報を逐次生成していく.この過程では，記号列によって表わされる個体全体のみでなく，その部分列block)も評価され，(building

個体の適応度を高めるのに役立つ部分列が選択によって同時並列的に増加していくことを利用して探索領域を絞り込むのが基本であるが，質の(implicit parallelism) も， GA の大きな特徴である

よい近似解を求めるにはなるべく広い領減の探索が望ま[3 , 4J.

しく，一方，計算量を低減するには先験情報によってでGA における探索過程は，図 S に示すように探索近傍きるだけ狭い領域に限ることが望ましい.これらはトレと探索速度(方向と速さ)によって特徴づけられる.すードオフの関係にあ弘前者を重視するのがランダム探

なわち，索法(モンテカルロ法)であり，後者に重きを置くのが(1)

逐次改善法や欲張り法である.

近傍:表現型から遺伝子型へのコーディングのルー

ル，および交叉演算子と突然変異演算子の実現法によ

また，解の探索と L 、う観点、から見れば，最適化手法は
図 1 に示すように，次の 3 種類に分類される.すなわち(1) 列挙的手法:厳密な列挙あるいは等価的な列挙によって，厳密な最適解を求める.って定まる.

(め速度:適応度の定義，定量化(スケーリング)法および選択演算子の実現法によって定まる.
探索における上記のトレードオフを適切にパランスさせ(の発見的手法:最適解あるいは近似解を生成するためのルールを用いて，ただ 1 つの解を求める.

個体表現
交互，突然変異演舞子

適応度
選択演算子

(の探索的手法:上記 2 法の中間的方法で，解空間の部最適解x分領域を探索することにより近似最適解を求める.

(~')

GA は(3) に属するものといえるが，通常の探索法と異なり，GA では単一の解候補でなくその集団を扱うことによって，先に述べた探索におけるトレードオフに有効な 1 つの解答を提供することになっている.

34
8 (24)

図 3

遺伝的アルゴリズムによる探索© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

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

遺伝アルゴリズム

図 4

最適化問題

コーディング

遺伝的アルゴリズムの標準型構成

解の評価方法(目的関数)などが，問題の環境に含まれると考える.

図 5

遺伝アルゴリズムの問題依存型構成3.
3 アルゴリズムの自己組織型構成法
問題について十分な予備知識がない場合には，問題のるためには，特に探索近傍の設計が重要な役割を担うこ構造を表わすパラメータをも遺伝子型に含めておき，探とになる.

索の過程を通して自己組織的に解に関する知見をアルゴ~、 L 、かえれば，コーディングのルールと遺伝演算子との適合性に考慮を払うことが肝要なポイントでリズムの枠内に取り込む，たとえば探索近傍の設計を自ある.

律的に行なわせるようにすることが必要である.今まで

GA のいくつかの応用事例を検討してみると，対象問のところ，このような考え方にもとづく研究はほとんど題の構造や解の性質の特徴が，遺伝子型へのコーディンなく，構造パラメータの表現法などについても未解明のグおよび演算子の実現に巧みに組み込まれた場合に成功部分が多い.しかし，していることがわかる.つまり，現時点での GA は個々にしアルゴリズムの有効性を明らかにするうえからも，の問題ごとに独自の設計を要求するものである.

図 B のような自己組織型構成法は今後の重要な研究課題

3.1 アルゴリズムの標準型構成法
以上のような状況をふまえて，最適化に対する GA の構成手法を 4 種類に分け，それらの特徴を整理してみよう.標準的な構成手法を図 4 に示した.この過程では，GA と他の探索法との違いを明確である.

3.
4 アルゴリズムの強化学習型構成法
上記の 3 種類の探索型 GA 構成法とは全く異なるもの
として，

GA によって最適解を求めるためのルールベー

個体の遺伝子型へのコーディングが最も重要であり，演スを構築する枠組み，すなわち学習型 GA とも呼ぶべき算子には標準的なもの，たとえば 1 点交叉や 1 ピット反方法がある.これは，強化学習と呼ばれる枠組みに属するもので，探索型 GA と学習型 GA の相違点は次のよう転による突然変異が用いられる.

3.
2 アルゴリズムの問題依存型構成法にまとめられる.

効率的なアルゴリズムの構成，あるいはヒューリステ(1) 探索型:個体を問題の解候補に対応させる.適応度

イクスとの融合を図るには，図 5 のように探索空間を問題の解空間そのものとし，問題固有の遺伝演算子を実現による個体の評価は比較的容易である.

(2) 学習型: {固体を探索のノレーんあるいはルールの集合する方法が有効である.この問題依存型の構成は，問題に対応させる.そのときは，個体と解候補が 1 対 i にや解について十分な知見が得られている場合には有力な対応しないので，個体の評価が困難である.

手段であり，これまでの応用研究はこの手段によるもの

学習型 GA の構成を図 7 に示す.このアルゴリズムでは，各ルールはルール強化(評価)機構によってそのよが多い.

さに応じた報酬を与えられ，各ルールが受け取った報酬の総量に応じてその適応度が算定される[3 J. こ

遺伝的 7)レゴリズム(問題の解候補+問題構逃)をコーデイング

図 S

遺伝的アルゴリズムの自己組織型構成

見かけ上は標準型構成と同じであるが，問題の解候補および問題の構造を遺伝子型としてコーディングしている点が異なる.
図 71993 年 7 月号

遺伝的アルゴリズムの強化学習型構成© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(25)349表 1スケジューリング問題の例

仕事作業{機械，処理時間)J

先行仕事, 0 ,(M"5) 02(M2 , 4)J
203(M" 3) 04(M2 , 4)J
305(M3 , 2)

M1JhJ2

図 S

M2

スケジューリング問題の選択グラフ表現

節点 O および*は，それぞれ開始および終了を表わの枠組みは，ルールベース・システムにおけるルールのすダミー節点である.

自動評価・自動獲得を可能にするものとして注目に値す
るが，ルール強化機構の実現に困難を伴うので，今後の選択グラフ表現した問題では，ある選択弧対から一方研究に待つところも多い.

4. スケジューリング問題への応用
この節では，スケジューリング問題への応用を通して，の弧を除去すること(選択弧対の解消)で 1 つの決定変数が定まり，グラフ中に閉路が生じないようにすべての選択弧対が解消されたときつの実行可能なスケジューんが与えられる.

アルゴリズムの構成例を具体的に紹介しよう.

さて，選択弧対の解消方向を O と l で表わし4.
1 スケジューリング問題

o ある

生産や建設のプロジェクトを完成する工程では，いくいは 1 を選択弧対の数だけ並べた記号列を個体の遺伝子種類かの機械を使って，工程の単位となるいくつかの仕型とする.この遺伝子型によって直接グラフを構成する事(j ob) を順序よく進めて L 、かねばならない.

何らかと(表現型にデコードすると)，高い割合で閉路が生じての基準(たとえばプロジェクトの完了時間)に照らして，しまう.特に GA においては，初期個体集合で閉路を含最も適切に各機械上における各仕事の l順序を決定する問

まないような個体ばかりを選んだとしても，交叉や突然題がスケジューリング問題である.なお通常，変異演算をほどこせば，閉路を含む個体が頻繁に生まれ\，、くつかの仕事の聞には，先行関係(ある仕事を始めるには，こるであろう.そこで，筆者らはデコーディングのルールれだけの仕事が終っていなければならないと L 、う関係)に工夫を加えて閉路が発生しないようにした.そのルー
ルによれば，遺伝子型にはデコーディングの際に参照さが指定されている.

スケジューリング問題のうち，複数台ある機械の機能れない記号(遺伝子)が L 、くつか含まれることになる [5].

がすべて同じ場合を並列機械型，機械の機能が異なる場

つまり，遺伝子型は冗長性をもつことになり興味深い.

合をショップ型という.さらにショップ型のうち，すべなお，この方法によれば，スケジューんとして望ましての住事で使用機械の順序が同じものをフローショップ

いアクティブ・スケジュールの 1 つが得られることが保型，仕事ごとに機械の順序が異なるものをジョブショッ証される.換言すれば，以上の標準型設計法はアクティプ型，どの仕事でも機械の l順序が自由なものをオープン

ブ・スケジューんという解の性質を利用して，ショップ型と呼ぶ.

索領域を限定したことになっている.

GA の探

4.
2 GA の標準型構成の例

4.
3 GA の問題依存型構成の例

筆者らは，ジョブショップ型スケジューリング問題を紙数の都合で詳細は省略するが.スケジューリング問選択グラフによって表現し，それにもとづいて GA を適

題に対する問題依存型 GA 構成法の例として，山田と中用する 1 つの方法を提案した [5 ， 6].

野によるアルゴリズム【 8J を挙げることができる.

グラフによる表現

このは，問題の直感的理解のためにもきわめて有用である.

アルゴリズムの特徴は，問題の表現型であるガントチャ

まず，仕事を節点に対応させ，あらかじめ決められていートをそのまま個体の遺伝子型に対応させる点であり，る仕事聞の先行関係を節点聞の有向弧で表わす.問題のその遺伝子型にもとづくアクティブ・スケジュール生成

決定変数に相当するのは，同一機械上で処理される 2 作

手 11債に交叉および突然変異演算子を組み込むことによっ業聞の先行関係であって，それを選択弧と呼ばれる有向て，探索領域をアクティブ・スケジュール集合に限定し弧の対で表わしておく.一例として，表 1 の例題を選択得ている.さらに，標準型におけるような遺伝子型の冗グラフで表現したのが図 8 である.図中の破線が選択弧長性がないので，探索効率の点ではさらに優れたものに対を表わしている.

なっている.

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

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

店( 1982).

5. おわりに[2J 茨木俊秀:組合せ一最適化分校限定法を中心とし本稿では，組合せ最適化に対する GA の特徴を整理すてー，産業図書(1 983).

るとともに，考えうるアルゴリズムの構成法を分類して[3J D. E. Goldberg

みた.そのうえで，組合せ最適化問題の典型例であるジョブショップ型スケジューリング問題(J SP) を取り上げて，具体的な GA の適用例を紹介した.

JSP の解法として常に GA が最も優れていると主張するつもりは

Genetic AIgorithms in

Search , Optimization , and Machine Learning ,Addison‑W esley(1989).
[4J 西川稀ー:生物の進化と遺伝的アルゴリズム，科学， 63巻

3 号，pp.147-155 岩波書店 (1993).

ないが，問題とその解の性質についての予備知識を適切[5J 西川韓ー，玉置久:ジョブショップ型スケジューに利用し，遺伝子型へのコーディング法や遺伝演算子のリング問題に対する遺伝アルゴリズムのー構成法，計実現法などに工夫を加えれば，有用なツールになりうる

測自動制御学会論文集，ことは確かであり，興味深い.

(1991).

逆にいえば，各種の問題に対して標準的あるいは万能ともいえる手法が確立されていて，誰でもいつでもそれを機械的に適用すれば問題が効率的に解けるわけではな
い.

GA は未だそれほど成熟の段階に達しては L 、ない.

27巻

5 号，

pp.593‑599[6J 西川締ー :GA のスケジューリング問題への応用，計測と制御，

32 巻号，pp.
46‑51 (1993).

[7] 西川稗ー，玉置久:近傍モデルによる遺伝アルゴリズムの並列化手法とそのジョブショップ・スケジュ

GA のポテンシャルを掘り起こし，その利点と欠点につーリング問題への応用，計測自動制御学会論文集， 2
9いて見きわめるには，なお多くの興味ある研究課題が残巻

なお，

5 号，pp.589‑595 (1993).

[8J T. Yamada and R. Nakano

されている.

GA は並列化の比較的容易なアルゴリズムであり [7J ，その点についても言及すべきであるが，ここではAIgorithm Applicablet
oLarge‑Scale Job‑ShopProblems ,Parallel Problem Solving fromNature (PPSN) ,一切割愛した.

A Genetic2,pp. 281-290 ,Elsevier(1992).

参芳文献[1J 西川締ー，三宮信夫，茨木俊秀:最適化，岩波書

4 ・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・a・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・同・・・・・・・・・・・・・岡、

平成 5 年度役員・支部長名簿

'/

1/

1/

1/

務
1/

会計

1/

研究普及

"編

1/

1/

1/

1/

1/

1/

和良(脚日通総合研究所)
治(慶応義塾大学)" 無任所"
国際監
1/

一誠(日本電気紛)

支部長

郁夫(三菱電機紛)

北海道支部

正人(日本アイ・ピー・エム紛)

東北支部
中部支部

進(神戸大学)正剣(東京大学)
勝茂(南山大学)磐郎(日本大学)

事東(中央大学)

晋(早稲田大学)
集1/

1/

1/忠雄(東レ紛)

谷田中木崎本1/

1/

元(近畿大学)

猿幕田茨尾岩"庶"

正夫(中央大学)

井見木橋藤副会長

藤伏津高伊会長

1/

理藤田井口田田戸木山原
伊権忍柳田紀山香森茨森大栗

理事

厚朋(北海道電力側)

圭一(東北電力側)
庸平(中部電力側)

俊秀(京都大学)

関西支部

俊秀(京都大学)

雅夫(東京工業大学)

中国・四国支部俊治(広島大学)

達雄(埼玉大学大学院)

九州支部

誠一(九州大学)

宏文(東燃システム研究所).................................圃................................................................................................圃・・・・・・・・・・・・・・・・・・・・d1993 年 7 月号

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

(27)351