2004年度卒業論文
分散遺伝的アルゴリズムの
パラメータ変更に伴う解探索能力の変化
─巡回セールスマン問題を例として─
提出日：2005 年 2 月 2 日 指導：山名早人助教授
早稲田大学理工学部情報学科 学籍番号：1G01P104-7
武笠 裕介
概要
本研究では、巡回セールスマン問題に対し、分散遺伝的アルゴリズムのパラメータを変え ることによる解探索能力の変化を探る。単一母体の遺伝的アルゴリズムでは、探索時間に膨 大な時間がかかり、さらに局所的な解に陥る可能性がある。それに対し、分散遺伝的アルゴ リズムでは探索を並列化して行うことで、探索時間の削減、さらには単一母体の遺伝的アル ゴリズムより良質な解が求められると報告されている。そのため分散遺伝的アルゴリズム は重要である。しかし一方で、分散遺伝的アルゴリズムは単一母体の遺伝的アルゴリズムに 比べ、移住に関するパラメータが増えるためパラメータの設定が困難である。従来の研究に おいては、ある一つ、あるいは二つのパラメータを取り上げ、それらについての検証を行っ ている。しかしこのような研究においては、パラメータ同士の関連性を知ることはできな い。そのため、本研究では、最もよく使われている組み合わせ最適化問題のタスクである巡 回セールスマン問題を取りあげた。巡回セールスマン問題に対して、分散遺伝的アルゴリズ ムにおけるパラメータ（個体数、島数、突然変異率、移住率、移住間隔、移住個体の抽出方法、
移住操作の位置）を変化させた場合にどのように解探索能力に違いが出るのかについて考 察する。
その結果、島数、個体数に関しては、島内の個体数が50～350個程度にすると解探索能力が 高く、最適な突然変異率は1/L(Lとは染色体長であり、本研究においては、都市数のこと)で あることが分かった。さらに、移住率に関しては、高い方が解探索能力が高く、移住間隔に関 しては、狭い方が解探索能力が高いことが分かった。移住個体の抽出方法に関しては、適合 度の高い個体から移住個体を選ぶ方法が適合度の低い個体から移住個体を選ぶ方法より、
解探索能力に優れており、移住操作の位置は、解探索能力に影響を与えないことが分かっ た。
目次
はじめに 1
分散遺伝的アルゴリズム 3
遺伝的アルゴリズム 3
遺伝的アルゴリズムの並列化 5
分散遺伝的アルゴリズム 7
母集団サイズ 9
島数 9
評価 9
終了判定 10
交叉手法 10
交叉率 12
突然変異 12
移住方法 12
移住個体の抽出方法 12
移住操作の位置 12
移住間隔 13
移住率 13
問題点 13
関連研究 14
パラメータの調整 14
離散型最適化問題への応用 14
並列化モデル 15
数値実験 17
対象問題 17
実験内容 17
島数による実験 18
パラメータ 18
実験結果 19
突然変異率に関する実験 21
パラメータ 21
実験結果 22
島数、移住間隔、移住率による実験 23
パラメータ 23
実験結果 24
移住率別の最良コスト平均の動向 24 移住間隔別の移住率変化に伴う最良コスト平均の動向 26 移住個体の抽出方法、移住操作の位置による実験 27
パラメータ 27
実験結果 28
考察 31
島数による考察 31
突然変異率による考察 31
島数、移住間隔、移住率による考察 31
移住個体の抽出方法、移住操作の位置による考察 31
結論 32
参考文献 33
はじめに
最適化問題とは、あらかじめ与えられた状態空間上に定義された関数（目的関数）におい て、制約条件を満たす範囲で最大値（あるいは最小値）をとるような設計変数を決定する問 題のことである。複数の局所的最適解を持つような最適化問題に対しては大域的な最適解 が求まるという保証がない。そのため、このような可能性がある場合には、最適化計算の初 期点を変えて何度か計算を行い、得られた局所的最適解から最も適切な解を選ぶことによ り、計算可能な準最適解を求めるということになる。近年、その解法として進化戦略を用い る手法が注目されているが、本研究において述べる遺伝的アルゴリズム（Genetic Algorithms : GA）もその１つである。
遺伝的アルゴリズム(以下GA)は1960年代にJ. H. Hollandによって考案された生物の進化 を工学的に模倣した学習的アルゴリズムである。GAでは、個体（Individual）によって状態空 間の要素を表現する。通常は１つの個体が１つの状態を表し、複数の状態を表すために個体 集団を形成する。この個体集団のことを母集団（population）といい、その中で環境（目的関 数）により適した個体（状態）ほど次世代に選択（selection）されやすく、次世代に残った個体 はさらに交叉（crossover）、突然変異（mutation）することで状態を変化させ広い範囲を効率的 に探索する。このように、GAは、ヒューリスティックな手法とランダム探索法を組み合わせ た多点探索を繰り返し行うことによって段階的に最適解を求める最適化アルゴリズムであ る。
しかしGAには、パラメータの設定が難しいこと、他の最適化手法と比較して計算負荷が 高く膨大な時間とコンピュータ資源を浪費することなどの問題点がある。計算負荷が高い という問題点はGAが多点探索であることに起因している。この問題点の解決法の１つに
GAの並列化がある。GAは、個体の評価や遺伝的操作を同時並行して行うことができるとい
う並列化に適した特性を有しているため、これまでにも多くの並列化モデルが考案されて きた。それらは大きくわけて大域的並列化モデル、粗粒度並列化モデル、細粒度並列化モデ ルの３つに分類される[1]。大域的並列化モデルとは、個体の評価に関してのみ複数のプロ セッサを使用するモデルであり、パラメータは単一母集団GA（Single Population Genetic
Algorithms : SPGA）と同じであり、SPGAと同様、局所解に陥りやすいなどの欠点がある。そ
れに対し、細粒度並列化モデルは1つのプロセッサに極少数の個体を割り当てるモデルであ り、総個体数と相当数のプロセッサが必要になるため、現実的ではない。そのため、本実験で は粗粒度並列化モデルである、DGAを使用した。
DGAとは母集団を複数の分割母集団（Sub-population）に分割し、各分割母集団でGAを行
うというもので、島モデル（Island Model）とも呼ばれる。DGAでは先に述べたように評価や 遺伝的操作は各母集団で独立に行い、各母集団の間では数世代間隔で移住（migration）と呼 ばれる個体の交換操作を行う。このモデルでは、各母集団を各ノードで処理することがで き、移住による個体の交換以外にノード間の通信が必要ない。このため、並列化効率が高く、
大幅な計算時間の短縮が期待できる。またDGAを用いることでSPGAに比べて、初期依存性 の減少と解の品質の向上が報告されている[1]。すなわち、単一プロセッサ上で行う場合で も、DGAはSPGAに比べて解探索の効率が良くなるということである。本研究において、単 一プロセッサ上で仮想的に島モデルを実装することで、パラメータ同士の依存関係を調べ、
傾向を掴むことで、DGAにおけるパラメータ設定の煩雑さを軽減し、さらにはDGAにおけ る解探索能力の向上に繋がると考え、パラメータの設定に関しての考察を行った。
このようにDGAは強力な最適化手法の１つであるが、多くのパラメータ設定が必要とい う欠点が存在する。GAには解探索に大きな影響を与えるパラメータが数多くあり、各パラ メータの最適値は対象問題や、他のパラメータに依存する。そのため、パラメータについて の研究は重要であるといえる。従来の研究においては、第3章で詳しく説明するが、ある一 つ、あるいは二つのパラメータに対して、独立にパラメータを変えた場合についてどうなる のかという検証を行っている。しかし、このような研究では、パラメータ同士の関連性につ いて理解することは不可能である。例えば、SPGAにおいて設定すべき主なパラメータには、
全体の個体数、選択手法、交叉手法、交叉率、突然変異手法、突然変異率があり、これらを独 立したパラメータとしての研究は数多く存在する。一方、DGAでは設定すべきパラメータが さらに増加し、母集団の分割数や各母集団に属する個体数移住操作に関わるパラメータで ある移住率、移住間隔などが加わる。しかし、複数のDGAパラメータについて「同時に」検討 を行った研究は少ない。さらに、同時に検討を行った研究とは、連続最適化問題に関しての 研究であり、本研究で対象問題として選択した、巡回セールスマン問題のような組み合わせ 最適化問題に関して、同時にパラメータについて検証を行った研究はない。従来の研究のよ うに、ある一つのパラメータに関しての検討では、パラメータ同士の関連性を発見すること ができない。しかし、本研究のように、パラメータを「同時」に検討することにより、パラ メータ同士の関連性を発見することが可能となると考えられる。本研究の目的は、一つのパ ラメータを動かすだけではなく、同時に様々なパラメータを動かすことにより、パラメータ 同士の関連を調べ、関連性を考察することである。これにより、DGAにおけるパラメータ設 定の煩雑さの軽減が期待できる。さらに、パラメータ同士の関連性を知ることで、解探索能 力の向上に繋がると考えた。
そこで本研究では、DGAのパラメータを変化させた場合に解探索能力（世代数）にどのよ うな影響があるのかについて検討を行った。今回検討したパラメータは全体の個体数、分割 母集団数、選択手法、交叉法、交叉率、突然変異率、移住間隔、移住率、移住個体の抽出方法で ある。
以降、第2章でDGAの概要と問題点、について述べ、第3章で関連研究について述べ、第4 章でパラメータ変化に関する数値実験を行い、第5章で結果について考察を加えたのち、第 6章で結論を述べる。
分散遺伝的アルゴリズム
遺伝的アルゴリズム
遺伝的アルゴリズムは生物が環境に適応して進化していく過程を工学的に模倣した学習 的アルゴリズムである。GAの研究は1960年代後半から1970年のはじめにMichigan大学のJ . H. Holland [2] らによって始め られた。また、1989年に出版され たGoldbergの 『Genetic Algorithms in Search, Optimization, and Machine Learning』[3]以降、日本でも盛んに研究が行わ れるようになり、現在では多方面に応用されている。
自然界における生物の進化過程においては、ある世代を形成している個体の集合、すなわ ち母集団の中で、環境により適した個体がより高い確率で生き残り、次の世代に子を残す。
このメカニズムをモデル化し、環境に対して最もよく適応した個体、すなわち目的関数に対 して最適値を与えるような解を計算機上で求めようというのがGAの概念である。
GAでは、個体は設計変数の値がコーディングされた染色体（Chromosome）と呼ばれる文 字列上で表現され、この染色体をデコーディングすることにより設計変数を読み出し、目的 関数の値を計算する。このとき、染色体の構造のことを遺伝子型（Geno Type）、これによっ て定まる個体の形質を表現型（Pheno Type）と呼ぶ。また、個体の集団のことを母集団
（Population）と呼ぶ。GAはこの母集団に対して選択、交叉、突然変異などの遺伝的操作を繰 り返し行うことによって解検索を行う。
ここでGAの流れを図2.1に示し、それぞれの操作について簡単に説明する。
Initialization：母集団の初期化
この操作では、あらかじめ設定された数だけランダムに個体を生成するものである。
生成した個体の数のことを母集団サイズ(Population Size)、あるいは単に個体数と呼 び、ここで生成した個体の集団を初期母集団とする。
Evaluation：評価
この操作は、各個体の持つ染色体を問題空間にデコードして解を求めるものである。
ここで求めた解のことを評価値(Evaluation Value)という。
Selection：選択
この操作は、各個体の評価値から次世代への生き残りやすさを求め、生き残りやすさ に基づいて次世代の母集団を形成する。この次世代への生き残りやすさのことを適 合度(Fitness)と呼ぶ。
Crossover：交叉
この操作は、個体間で染色体情報を交換する。個体集団のうち何割の個体が交叉する
かを交叉率(Crossover Rate)というパラメータによって定める。
Mutation：突然変異
染色体は遺伝子(Gene)を格納する複数の遺伝子座(locus)から構成され、遺伝子座に入 りうる遺伝子のことを対立遺伝子という。突然変異とは、染色体上の遺伝子座の遺伝 子を別の対立遺伝子に置き換える操作のことである。染色体のうち何割の遺伝子が 変異するかを突然変異率(Mutation Rate)というパラメータによって定める。
Terminate Check：終了判定
この操作は、あらかじめ定めた終了条件に基づいてGAを終了するためのものであ る。
図2.1 GAのフローチャート
Goldbergによると、GAは従来の最適化手法と比較して次の特徴を持っている[3]。
一点探索でなく、多点探索である。
設計変数を直接操作せずにコード化した状態で扱う。
サンプリングによる探索であり、ブラインドサーチである。
決定論的規則ではなく、確率的オペレータを用いる探索である。
一方でGAに関する研究が進むに従って以下のような問題点が指摘されるようになった。
高い計算負荷
GAでは、評価のために母集団サイズの分だけ目的関数を計算しなければならない。
評価とは毎世代行われるため、評価計算回数の合計は(母集団サイズ)×(終了までに 要した世代数)となる。また、母集団内に同じ染色体を持つ個体が複数存在する場合 もあり、不要な評価計算が多くなり、一点探索の最適化手法と比較して計算にかかる 負荷が大きくなる。
早熟収束による局所解への収束
他の個体に比べ明らかに高い適合度を持つ個体が存在した場合、その個体の遺伝子 情報は急速に母集団内に広がる。この広がりにより母集団内の多様性が減少し、局所 解に収束する可能性が高くなる。
パラメータ設定の複雑さ
GAでは、個体数や交叉率、突然変異率等設定すべきパラメータが多い。また、これら のパラメータは解探索能力に大きく影響する。さらに、対象とする問題によって最適 なパラメータの値が異なる。このため、最適なパラメータの値を知るためには多くの 予備実験が必要となる。
遺伝的アルゴリズムの並列化
遺伝的アルゴリズムは多点探索であるために計算負荷が高い。ここでは、この問題点を解 消するために考案されたGAの並列モデルについて述べる。
GAのアルゴリズムは他の最適化手法と比較して優れた並列化特性を持っており、評価、
選択、交叉、突然変異のすべての遺伝的操作を並列可能である。GAの並列化はその負荷分散 の方法によって大きく3種類に分類できる[1]。
a. 大域的並列化モデル（Global parallelization model）
母集団の分割は行わず、選択と交叉は大域的に行い、個体の評価のみを複数のプロセッ サを使用して処理するモデルである。純粋に計算負荷の分散だけを求めたモデルであ り、並列化することによる母集団の変化がないために解探索に影響を与えないという特 徴がある。
b. 粗粒度並列化モデル（Coarse grained parallel model）
図2.2の様に、母集団を複数の分割母集団に分割し、そのそれぞれの分割母集団を複数の
プロセッサに割り当てるモデルであり、分散GA（Distributed GA）と呼ばれる。DGAで は、分割母集団間で情報交換を行うために移住という操作が新たに必要となる。単一母
集団GAに比べて解の高品質化が計れることが示されており、単一プロセッサでGAを行
う場合にもこのモデルは有効であるといえる。またDGAは島モデルと呼ばれることも あり、このとき分散母集団は島とも呼ばれる。本研究ではこのモデルを用いた。
c. 細粒度並列化モデル（Fine grained parallel model）
１つのプロセッサに１つ、あるいは極少数の個体を割り当てるモデル。このモデルでは プロセッサ間の通信のオーバーヘッドを減らすために近傍のプロセッサに割り当てら れた個体とのみ交叉を行う。このため、個体をどのようにプロセッサに配置するかが解 探索に大きな影響を与える。また、総個体数と相当数のプロセッサが必要になるため、
単純に複数のPCをネットワークで接続して構成された並列計算機システムには不向き なモデルであるといえる。
図2.2 母集団分割図
DGAを用いた理由をここで述べる。大域的並列化モデルに関しては、個体の評価に関して のみ複数のプロセッサを使用するモデルであり、パラメータはSPGAと同じであり、SPGAと 同様、局所解に陥りやすいなどの欠点がある。それに対し、細粒度並列化モデルは1つのプロ セッサに極少数の個体を割り当てるモデルであり、島数と島内の個体数との関連性を調べ ることができない。そのため、本実験では粗粒度並列化モデルである、DGAを使用した。
分散遺伝的アルゴリズム
図2.3にDGAの流れを示す。SPGA(図2.1)との違いは、移住操作が加わる点である。移住は
数世代に一度、各島内で選ばれた１つまたは複数個の個体（移住個体：Migrant）を別の島の 個体と交換することで実現される。このとき、各島内における移住個体の割合を移住率
（Migration Rate）、何世代ごとに移住するかを移住間隔（Migration Interval）と呼ぶ。図2.4に 移住の概念図を示す。
分散遺伝的アルゴリズムでは、それぞれの島で独立に探索が進むため、各島で個体は大き く異なり、母集団全体としての多様性が維持される。ここで、DGAは同じ母集団サイズを持 つSPGAと比較して、1島あたりの個体数が少ないので、島内では早熟収束が起こりやすくな る。しかし、移住によって他の島で成長した遺伝子情報を持つ個体を取り入れることにより 島内での多様性も維持できる。
移住は母集団の多様性を維持するために重要な操作であり、移住を制御する移住率、移住 間隔のパラメータもまた重要なパラメータとなる。移住する個体数が過多な場合には母集 団全体での多様性が十分に保たれず局所解に収束し、過小の場合は効果的な個体の交換が 行われないため、島内での多様性が十分に保たれず、局所解へ収束するといった問題がある と考えられる。
図2.3 DGAのフローチャート
図2.4 移住
母集団サイズ
GAは多点探索であり、その探索点の数のことを母集団サイズ（Population Size）と呼ぶ。探 索点の数が多いと広い範囲を探索することが可能となるために最適解を発見しやすくな る。しかし、多すぎると収束が遅くなるために余計な評価計算回数が増える。逆に探索点が 少ないと収束が速くなるために局所探索性能が向上する。
しかし少なすぎると拾い範囲を探索することができずに最適解ではない局所解に落ち込む 可能性が高くなる。つまり個体数は対象問題の性質や選択手法との関係が深いパラメータ であると考えられる。
島数
DGAでは母集団サイズによって定めた個体を複数の分割母集団に分割する。この分割数
を島数（Number of Islands）と呼ぶ。各島において交叉操作を行うためには島内に少なくとも
２個体存在している必要がある。このため、島数は最大でも（母集団サイズ/2）となる。島数 が多くなると局所解に落ち込む可能性が減少する。島内の個体数は全体の個体数に左右さ れるため、最適な島数は個体数との関係が深いと考えられる。また、島間の情報交換のため の操作である移住操作との関連性が高いと考えられる。
評価
評価とは、個体の持つ染色体をデコーディングして設計変数を読み出し、目的関数の値を 計算する操作である。コーディングには、バイナリコーディングとグレイコーディングの2 つがある。バイナリコーディングは単に整数を2進法によって表現したものであり、グレイ コーディングは、連続する2つの符号間のハミング距離が常に1であるという特徴を持って いる。ハミング距離とは遺伝子の異なる部分の数のことである。これによりグレイコーディ ングはバイナリコーディングに比べて、特に終盤での解探索の効率が良くなるという報告 がなされている[4]。表2.1に0から7までの整数をバイナリコードとグレイコードに変換した 際の対応表を示す。
表2.1 バイナリコードとグレイコードの対応 整数 バイナリコード グレイコード
0 000 000
1 001 001
2 010 011
3 011 010
4 100 110
5 101 111
6 110 101
7 111 100
終了判定
終了判定では、探索の状態に応じて適切にGAを終了させる必要がある。終了判定には 様々なものが考えられるが、主なものを次に示す。
評価値を用いる場合
母集団内の最高評価値や平均評価値からあらかじめ定められた値を超えた場合に終 了する。
世代や評価回数を用いる場合
あらかじめ定められた世代数または評価計算回数だけGAを行うと終了する。
世代と評価値を用いる場合
母集団内の最高表価値や平均評価値が一定世代変化しないと終了する。
本研究では、パラメータを変化させることでの解探索能力の違いを探ることが目的であ るため、確実に収束する世代数と評価値を用いる判定法を使用した。
交叉手法
交叉とは個体間での染色体情報の交換のために行う。交叉の代表的なものとして以下の3 種類がある。本研究では、一点交叉を採用した。
一点交叉 ：
この手法は、ランダムに1つの交叉点(Crossover Point)を定め、その点を境目に染色体 を交換するものである。図2.5に一点交叉の様子を表した図を示す。
図2.5 一点交叉
二点交叉 ：
この手法は、ランダムに2つの交叉点(Crossover Point)を定め、その間にある染色体を 交換するものである。図2.6に二点交叉の様子を表した図を示す。
図2.6 二点交叉
一様交叉 ：
1989年にG. Syswerda [5]によって提案された手法で、交叉操作のたびに交叉点の数が 変化する。交叉の度にランダムにマスクパターンを生成し、それに従って交叉点を作 成するというものである。図2.7に一様交叉の様子を表した図を示す。
図2.7 一様交叉
交叉率
母集団のうち何割の個体が交叉に参加するかを定めるものが交叉率(Crossover Rate)であ る。母集団内に存在する個体が偶数の場合、交叉率1で全ての個体が交叉に参加することに なる。
突然変異
あらかじめ定めた突然変異率に従って全ての遺伝子について突然変異をするか否かの判 定を行い、突然変異する遺伝子を他の遺伝子に置き換える。ここで、連続最適化問題におい て、染色体長をLとした時、最適な突然変異率は1/Lであるという報告がある[6]。図2.8に突然 変異の様子を示す。
図2.8 突然変異 移住方法
移住とは島間で個体を交換する操作である。移住操作を行う際にまず決めなければなら ないのは、どの島からどの島へ移住するか、ということである。本研究では隣の島と個体を 交換する手法をとっている。
移住個体の抽出方法
抽出方法には様々あるが、代表的なものを以下に挙げる。
島内の最も適合度の高い個体から順に選ぶ。
島内の最も適合度の低い個体から順に選ぶ。
移住操作の位置
移住操作の位置には、以下のものがある。
遺伝操作(交叉、突然変異等)の前に個体を移住させる。
遺伝操作の後に個体を移住させる。
移住間隔
移住操作と移住操作の間隔のことを移住間隔(Migration Interval)という。移住間隔が1の場 合、各世代移住を行うことになる。本研究では移住間隔が1,2,3,4,6,10,20世代毎の場合につい て比較した。
移住率
各島内にしめる移住個体の割合のことを移住率(Migration Rate)という。
問題点
母集団を分割することによりGAのもつ問題点のいくつかを解消することができる。しか し、移住という概念を加えたことにより新たな問題点も出てきた。というのは移住を行うた めに移住率と移住間隔という新たなパラメータが必要となることである。これらの移住パ ラメータは他のパラメータと同様に解探索能力に大きな影響を与える。しかし、最適な移住 率、移住間隔の設定は問題によって異なると考えられるため、最適なパラメータを設定する ために多くの予備実験が必要となる。
関連研究
パラメータの調整
DGAの最大の問題点として、本研究のテーマでもある、パラメータの設定に関連する問題 がある。しかし、DGAにおいて、設定すべきパラメータは多岐に渡る。そのため従来の研究 では、交叉法、コーディング法に関するもの[4]、交叉率、突然変異率に関するもの[6]、島数と 個体数との関係に関するもの[7]など、特定の数個のパラメータに関して研究されている。さ らにDGAにおける解探索能力と個体の選択範囲との関連性を調べたものに[8]が挙げられ る。
文献[4]では、DGAの解探索性能に及ぼす交叉法とコーディング法の影響を検討してい る。交叉法として、一点交叉、二点交叉、一様交叉の3通り、コーディング法として、グレイ コーディング、バイナリコーディングの2通りの組み合わせからなる6通りの設定に関して 検証した結果、DGAにおいて最適な交叉法とコーディング法はグレイコーディングと一点 交叉であり、単一母集団GAの場合と同様であると結論付けている。
文献[6]では、DGAにおける最適な交叉率及び突然変異率について数値実験を行ってい る。連続最適化問題において、最適な突然変異率は1/L(L：染色体長)であると結論付けてい た。
離散型最適化問題への応用
離散最適化問題とは，目的関数や制約関数が離散的な関係を持っている場合の最適化問 題のことである．離散的なものの例としては整数の集合, グラフにおけるノードなどが挙げ られる. 以下が離散的最適化問題の例である。
「ナップサック問題」(x 以下という条件の下でより多くのものをナップサックに詰め るためにはどうしたらよいか)
「最短経路問題」(A→B までの最短経路を求める)
「巡回セールスマン問題(Travel Salesman Problem: TSP)」(複数の都市を巡回するための 最短ルートを見出す問題)
離散集合の性質としては，「連続性，微分，積分などの概念を直接適応できない」ことと、
「パターンを数えることができ、総当りでそのパターンを調べれば，必ずその最適解を求め ることができる」ことが挙げられる．しかし、現実世界でそれを行おうとすれば、「組み合わ せ爆発」が起こるため、すべてのパターンを調べられる問題は少ない。
それに対し、連続最適化問題とは、探索する値が連続的に分布している問題である。連続 最適化問題において、DGAはSPGAと比較して高品質な解が得られると報告されている[9]。
しかしながら、種々の離散型最適化問題においてはDGAの性能は明らかになっていない。そ こ で、離散型 最適化問題の 一つである ジョブショ ップスケジュ ーリング問 題(Jobshop Scheduling Problem：JSP)を対象としてDGAの性能を検証した論文に[10]がある。
文献[10]では、JSPを対象としてSPGAとDGAの比較を行い、「DGAでは各サブ母集団で局 所的に発見された部分解が移住によって他の部分解と結合し、より大きな部分解へと成長 することにより最適解を得やすくなる。そのため、SPGAより高品質な解が期待できる。」と 結論付けている。
並列化モデル
DGAに類 似した モデ ルに 、階 層分散 構造 を用 いた 遺伝的 アル ゴリ ズム(Hierarchical Distributed Structure Genetic Algorithm：HDSGA)がある。[11]HDSGAでは、サブ母集団は移住 方法の異なる階層構造に従って配置される。これにより、母集団の多様性と一様性が協調 し、大域的な探索と局所的な探索との両方を行うことが可能である。また、DGAと同じく遺 伝的操作の適用範囲が限定されているモデルに、MGG(Mininal Generation Gap)がある [12]
[13] 。MGGでは、母集団から取り出した2つの個体を元に新しい個体を生成し、その中から
選択した2個体を母集団に戻す、という操作を繰り返す。世代交代の対象を限定することで、
母集団の多様性を維持しながら探索を行うことができる。他にも、各島内の個体数を2つだ けにしたモデルである、2個体分散遺伝的アルゴリズムなどがある[14]。
表3.1にDGAに関しての研究における手法と、文献の分類を行った。
表3.1 DGAに関する研究の手法
手法 概要 利点、欠点 文献
交叉法 交叉手法の違いによる解探索 能力への影響
交叉法以外のパラメータに 関しては触れられていない。
[4][5]
コ ー デ ィン グ法
コーディング法の違いによる 解探索能力への影響
コーディング法以外のパラ メータに関して触れられて いない。
[4]
交叉率、
突然変異率
交叉率、突然変異率に関して、
それぞれの解探索能力への影 響
2つのパラメータに関連性が あるかないか分からない。
[6]
個体数、
島数
個体数と島数の関連性につい て
2つのパラメータの関連性に 関して研究している。
[7]
個 体 の 選択 範囲
次世代生成の際の個体の選択 範囲の違いによる解探索能力 への影響
1つのパラメータに関してし か触れられていない。
[8]
離 散 型 最適 化 問 題 への 応用
離散型最適化問題に応用し、
SPGAとDGAの 比 較を 行 って いる
離散型最適化問題に、DGA が応用できることを示して いる。
[10]
並 列 化 モデ ル
DGA以外の別の並列化モデル について
母集団の多様性を維持しな がら探索を行うことが可能。
[11][12][13]
[14]
数値実験
対象問題
本研究では、対象問題として、「巡回セールスマン問題」を採用した。巡回セールスマン問 題とは、あるセールスマンが幾つかの都市を一度ずつ訪問して出発点に戻ってくるときに、
移動距離が最短になる経路を求める問題である。各都市間には、移動距離(コスト)が存在 し、全ての都市を一度ずつ訪問して出発点に戻るまでの、コストの合計を最小にする問題で ある。組み合わせ最適化問題の代表例として知られていることから対象問題とした。都市数 が少ない場合は総当り探索などでも、容易に解を求められるが、都市数が増えるに従って、
総当りでは組み合わせが多くなり解くことが困難となる。図4.1に都市数4の場合の例を示 す。各都市間には経路が存在し、コストが割り振られている。図4.1では、全ての都市間にコ ストが割り振られており、その中で各都市を一度ずつ訪問する場合にコスト合計が最小と なる経路を示したものである。
図4.1 都市数4の場合
実験内容
本研究では、分散遺伝的アルゴリズムに関するパラメータの検討を行う。全てのパラメー タの比較を同時に行うのは組み合わせが膨大になるために現実的ではない。一方、１つずつ パラメータを比較する実験ではパラメータ間の依存関係を把握することが困難となる。そ
こで今回はDGAの各遺伝子操作に着目し、遺伝的捜査に関連すると考えられるパラメータ ごとにパラメータを分類し、個々の分類毎に実験を行った。
本研究で行った数値実験を以下に示す。
島数による実験
ここでは、島数に関する実験を行った。個体数を統一し、島数を変えることで、DGA 全体としての解探索能力にどのような変化がでるのかについての実験を行った。
突然変異率による実験
ここでは突然変異率を0.01、0.02(都市数50の時の1/L)、0.1、0.2、0.3、0.4、0.5と変化さ せた場合についてDGAの解探索能力についての実験を行った。
島数、移住間隔、移住率による実験
ここでは、移住に関係するパラメータについて実験を行った。移住に影響するパラ メータには、移住率、移住間隔、島数、移住個体の抽出方法、移住方法移住操作の位置 がある。これらの組み合わせは多く、比較が困難となる。そのため移住の頻度が解探 索に与える影響を調べるために、移住率、移住間隔、島数の3つのパラメータについて まず数値実験を行った。
移住個体の抽出方法、移住操作の位置による実験
ここでは移住に関するパラメータのうち、先ほど実験しなかった移住個体の抽出方 法、移住操作の位置の2つのパラメータについて数値実験を行った。
以下、実験結果を示し、パラメータの傾向について述べる。
島数による実験
パラメータ
本実験において比較したパラメータは島数である。終了条件は、「1000世代遺伝的操作を 行う」とし、試行回数は10とした。1000世代とは、数十回の実行により、1000世代以内に収束 することを実験的に調べた結果である。最良コスト平均とは、１回のGA操作によって求め られる最良個体のコストの試行回数平均値(10回の平均値)である。巡回セールスマン問題に おけるコストとは、全ての都市を一度ずつ訪問する際の経路であるため、コストは小さいほ うが良い。そのため、最良コスト平均の値が小さいほうが良い個体であると言える。その他 のパラメータを表4.1に示す。
表4.1 パラメータ ※Lは染色体長(都市数) 個体数 300,500,1000,2000
島数 1,2,3,4,5,10,20
都市数 25,50
交叉 一点交叉
交叉率 1
突然変異率 0.02(1/L)
移住率 0.1
移住間隔 1
個体の選択方法 適応度の上位から
順番に
移住操作の位置 後
実験結果
図4.2及び表4.2に都市数50の場合、図4.3及び表4.3に都市数25の場合の実験結果を示す。
都市数が異なるため、最良コスト平均での比較は妥当ではない。ここで注目すべき点は、い ずれの場合も島数が1から5の範囲で最もコストの小さい点が存在し、その後島数を増やし ていくと、最良コスト平均の値が上昇していく点である。これは、図4.2及び図4.3を比較す れば明らかである。つまり、都市数に関わらず、島数が1から5の間が良いという結論になる。
これを別の視点で見た結果を図4.4、図4.5に示す。
図4.2 都市数50 の場合の島数と最良コスト平均の関係
図4.3 都市数25 の場合の島数と最良コスト平均の関係
表4.2 都市数50 の場合の島数と最良コスト平均の関係 島数 個体数 2000 個体数1000 個数 500 個体数 300
1 6108 5524 5621 5420
2 5628 5477 4985 5986
3 5524 5065 5386.6 6569
4 5042 5443 5673.3 5572
5 5398 5628 6363.3 5478.6
10 4870 7752 7884 9286.6
20 9766 8864 16191.6 15446
表4.3 都市数25 の場合の島数と最良コスト平均の関係 島数 個体数 2000 個体 1000 個体数 500 個体数 300
1 2123 1758 1545 1659
2 1869 1681 1746 1417
3 1541 1398 1678 1512
4 1510 1410 1590 1611
5 1389 1638 1479 1448
10 1531 1601 1685 1837
20 1709 1772 2932 2729
図4.4及び図4.5は、先の図4.2、4.3の島数と最良コスト平均の関係の結果を、各島に所属す る個体の数(以下島内の個体数)で分類し、それをグラフ化したものである。図4.4、4.5におい て注目すべき点は、島内の個体数が約50から500程度の間に、最も、最良コスト平均の小さ い点が存在し、個体数がそれ以上になると、最良コスト平均の値が上昇していく点である。
以上より、「最良コスト平均は、島数が1から10 の間、言い換えると、島内の個体数が50から 500程度の時に小さいため、解探索能力が高い」と言える。
図4.4 都市数50の場合の島内の個体数とコストの関係
図4.5 都市数25の場合の島内の個体数とコストの関係
突然変異率に関する実験 パラメータ
本実験において比較したパラメータは突然変異率である。2.3.7で少し触れたが、連続最適 化問題においては、突然変異率は1/L(L：染色体長)が最適であるという報告[6]はなされてい るが、本研究の対象問題である、巡回セールスマン問題のような組み合わせ最適化問題にお
いて、この報告が適応できるのかについて実験を行った。終了条件は、「1000世代遺伝的操 作を行う」とし、試行回数は10とした。その他のパラメータを表4.4に示す。個体数を500、島 数を2としたのは、4.3の実験の都市数50の場合において最も、最良コスト平均が小さいもの として取り上げた。
表4.4 パラメータ ※Lは染色体長(都市数)
個体数 500
島数 3
都市数 50
交叉 一点交叉
交叉率 1
突然変異率 0.01,0.02(1/L),0.03,0.04, 0.1,0.2,0.3,0.4,0.5
移住率 0.1
移住間隔 1
個体の選択方法 適応度の上位から
順番に
移住操作の位置 後
実験結果
図4.6及び表4.5に実験結果を示す。都市数を50としているため、先の最適な突然変異率
1/Lは1/50(0.02)である。本実験において、突然変異率が0.02の時に最良コスト平均が最も小 さければ、巡回セールスマン問題のような組み合わせ最適化問題に関しても、最適な突然変 異率は1/Lと言える。
図4.6 突然変異率と最良コスト平均の関係 表4.5 突然変異率と最良コスト平均の関係
突然変異率 最良コ スト 平 均
0.01 5511
0.02 5065
0.03 5253
0.04 5596
0.1 5459
0.2 5481
0.3 5754
0.4 5507
0.5 5708
図4.6より、突然変異率が0.02(1/L)の時に最良コスト平均が最も小さいことが分かる。これ
により、最適な突然変異率が1/Lであるという報告[6]は連続最適化問題だけでなく、組み合 わせ最適化問題の代表例である巡回セールスマン問題においても適用することができるこ とが明らかになった。
島数、移住間隔、移住率による実験
パラメータ
本実験では、移住に関係するパラメータについての実験ということで、移住率、移住間隔、
島数の3つのパラメータについて、まず数値実験を行った。終了判定は今までの実験と同様 に「1000世代遺伝的操作を行う」とし、試行回数は10とした。その他のパラメータを表4.6に 示す。
表4.6 パラメータ
個体数 500
島数 2,3,4,5,10
都市数 50
交叉 一点交叉
交叉率 1
突然変異率 0.02(1/L)
移住率 0.1,0.2,0.3 移住間隔 1,2,3,4,5,10
個体の選択方法 適応度の上位から
順番に
移住操作の位置 後
実験結果
移住率別の最良コスト平均の動向
移住率0.1の場合を図4.7に、移住率0.2の場合を図4.8に、移住率0.3の場合を図4.9にそれ
ぞれ示す。全ての場合の詳細な数値は表4.7にまとめて示す。
図4.7 移住率0.1の時の島数と移住間隔、最良コスト平均の関係
図4.8 移住率0.2の時の島数と移住間隔、最良コスト平均の関係
図4.9 移住率0.3の時の島数と移住間隔、最良コスト平均の関係
表4.7 移住率0.1の時の島数と移住間隔、最良コスト平均の関係
島数 移住間隔 移住率 0.1 移住率 0.2 移住率 0.3
2 1 4985 4872 4789
2 2 5185 5086 4913
2 3 5410 5221 5625
2 10 5982 5813 5730
3 1 5386 5237 5161
3 2 5632 5581 5369
3 3 5422 5142 5125
3 10 6181 5588 5404
4 1 5673 5575 5333
4 2 5886 5745 5667
4 3 5635 5617 5536
4 10 5801 5746 5675
5 1 6363 6144 6234
5 2 6504 6257 6308
5 3 6698 6430 6391
5 10 7116 6570 6865
10 1 9884 9050 9143
10 2 10806 10444 10012
10 3 11621 10467 10073
10 10 10785 12317 10381
図4.7、4.8、4.9の全てにおいて、多少の誤差はあるものの、移住率、島数に関わらず、移住 間隔が増えるに従って、最良コスト平均の値が大きくなっている。つまり、移住間隔が広く なるにつれ解探索能力が低くなり、移住間隔が狭くなるにつれ解探索能力が高まると言え る。
移住間隔別の移住率変化に伴う最良コスト平均の動向
次に示す図4.10から図4.13は、表4.7のデータを移住間隔別に移住率を変化させた場合に ついてグラフ化したものである。移住間隔1の場合を図4.10、移住間隔2の場合を図4.11、移
住間隔3の場合を図4.12、移住間隔10の場合を図4.13にそれぞれ示す。
図4.10 移住間隔1の時の移住率変化に伴う最良コスト平均の動向
図4.11 移住間隔2の時の移住率変化に伴う最良コスト平均の動向
図4.12 移住間隔3の時の移住率変化に伴う最良コスト平均の動向
図4.13 移住間隔10の時の移住率変化に伴う最良コスト平均の動向
移住間隔10(図4.13)で島数が10において、移住率0.2のとき最良コスト平均の値が移住率
0.1の場合よりも大きくなってしまっているものの、図4.10から図4.13までを見れば分かる
様に、他の部分では、移住率が上がるにつれて最良コスト平均の値が小さくなっているが分 かる。このことから、移住間隔10で島数が10の場合も誤差であると考えられる。
移住個体の抽出方法、移住操作の位置による実験
パラメータ
本実験では、4.5の実験で取り上げなかった移住に関係するパラメータである移住個体の 抽出方法、移住操作の位置の2つのパラメータについて数値実験を行った。移住個体の抽出 方法では、以下の2つを比較した。
島内の最も適合度の高い個体から順に選ぶ。(以下、「上位」と呼ぶ。) 島内の最も適合度の低い個体から順に選ぶ。(以下、「下位」と呼ぶ。)
移住操作の位置に関しては以下の2つを比較した。
遺伝操作(交叉、突然変異等)の前に個体を移住させる。(以下、「前」と呼ぶ。) 遺伝操作の後に個体を移住させる。(以下、「後」と呼ぶ。)
終了判定は今までの実験と同様に「1000世代遺伝的操作を行う」とし、試行回数は10とし た。その他のパラメータを表4.8に示す。
実験結果
移住操作の位置が前の場合に関して図4.14に、移住操作の位置が後の場合に関して図4.15 にそれぞれ示す。図4.16及び図4.17に、個体の抽出方法別に、移住操作の位置が遺伝操作の 前後での比較を示す。
表4.8 パラメータ
個体数 500
島数 2,3,4,5,10,20
都市数 50
交叉 一点交叉
交叉率 1
突然変異率 0.02(1/L)
移住率 0.3
移住間隔 1
個体の選択方法 適応度の上位から ,
適応度の下位から
移住操作の位置 前,後
図4.15 移住操作の位置が後の場合の移住個体の抽出方法と最良コスト平均の関係
図4.16 個体の抽出方法が上位である場合の移住操作の位置と最良コスト平均の関係
図4.17 個体の抽出方法が下位である場合の移住操作の位置と最良コスト平均の関係
図4.14、図4.15から、ほぼ全ての島数において、適応度上位から移住個体を選んだ方が、下
位から選ぶよりも最良コスト平均の値が小さい。よって、上位から移住個体を選ぶ方が解探 索能力が高いと言える。
図4.16、図4.17から、移住操作の位置の前後による差は小さく、ほぼ同等の解探索能力で あると考えられる。
考察
島数による考察
都市数を25、50とし、島数を2,3,4,5,10,20と変えた場合についての解探索能力の違いについ ての実験であった。都市数がどちらの場合も、島内の個体数が50から500程度の時が最良コ スト平均の値が小さく、解探索能力が高いことから、解探索能力には、島内の個体数が関係 していると考えられる。
突然変異率による考察
連続最適化問題において、最適な突然変異率は1/Ｌであったが、巡回セールスマン問題の 様な組み合わせ最適か問題においても最適な突然変異率が1/Ｌであることが当てはまるの かについて実験を行った。その結果、突然変異率が1/Ｌのときに、最良コスト平均の値が最 も小さくなった。そのため、突然変異率1/Ｌのときが最も解探索能力に優れていると言え る。よって、巡回セールスマン問題においても、最適な突然変異率は1/Ｌであると言える。
島数、移住間隔、移住率による考察
島数を2、3、4、5、10とし、移住率を0.1、0.2、0.3、移住間隔を1、2、3、10とした場合につい て、解探索能力の違いについて探る実験を行った。その結果、島数に関わらず、移住間隔は狭 くなるにつれて解探索能力は向上し、移住率も上がるにつれて解探索能力が向上した。
移住個体の抽出方法、移住操作の位置による考察
移住個体の抽出方法として、適応度の上位から順番に選ぶ方法と、下位から順番に選ぶ方 法、移住操作の位置として、遺伝操作の前に移住操作を行う方法と、遺伝操作の後に移住操 作を行う方法を比較し、解探索能力の違いについて探る実験を行った。その結果、移住操作 の位置を固定した場合に、適応度の上位から順番に選ぶ方法の方が、下位から順番に選ぶ方 法よりも、解探索能力に優れていることが分かった。また、移住個体の抽出方法を固定した 場合には、移住操作の位置の前後による差は見られず、解探索能力に影響はないと考えられ る。
結論
本研究では、分散遺伝的アルゴリズムについて、巡回セールスマン問題を対象にパラメー タの変更に伴う解探索能力の変化について実験を行った。数値実験により、個々のパラメー タに関しては以下のことが言える。
島数に関しては、島内の個体数が50から350程度にすると解探索能力が高い。
巡回セールスマン問題においても、最適な突然変異率は1/Ｌである。
移住間隔は狭い方が解探索能力が高い。
移住率は高い方が解探索能力が高い。
移住個体は適応度の上位から順番に選ぶ方法の方が下位から順番に選ぶ方法よりも解 探索能力が高い
移住操作の位置の違いによる解探索能力の差は見られない。
それに対し、パラメータ同士の関連性については以下のことが言える。
図4.7～図4.13より、移住間隔、移住率の変化に伴う解探索能力の違いは、島数の変化に
伴う解探索能力の違いよりも小さいため、島数の方が、より解探索能力に影響のあるパ ラメータであると言える。
図4.7～図4.13より、島数が多いほど、移住間隔、移住率の変化に伴う解探索能力の違い
が大きい。これは、島数が多いほど島内の個体数が少なくなるため、移住による影響を 受けやすくなるためであると考えられる。
図4.14～図4.17より、移住操作の位置は、解探索能力に直接の影響はないため、移住個
体の抽出方法との関連性はないと考えられる。
今後の課題として、今回実験を行っていない他の対象問題においても本論文で述べた傾 向が当てはまるのかを検証する必要がある。
参考文献
[1] Reiko Tanese, Distributed genetic algorithms. Proc,3rdICGA, pp.434-439, 1989
[2] J.H.Holland. Adaptation In natural and Artificial Systems. University of Michigan Press, 1975.
[3] D.E.Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison- Wasley Publishing Company, 1989
[4] 三木光範,廣安知之,吉田純一, 金子美華,分散遺伝的アルゴリズムの性能に及ぼす交叉法 とコーディング法の影響,情報処理学会第59回全国大会,pp.139-140, 1999
[5] G.Syswarda, Uniform crossover in genetic algorithms. ICGA. 1989
[6] 三木光範,廣安知之,大向一輝,金子美華,分散遺伝的アルゴリズムにおける最適な交叉率 および突然変異率,情報処理学会第59回全国大会,pp.141-142, 1999
[7]飛岡良明,伊庭仁志,並列遺伝的プログラミングに置ける島モデルの実験的解析,情報処理 学会第65回全国大会,pp.373-374, 2005
[8] 三木光範,廣安知之,佐野正樹,MPSシンポジウム論文集ISSN1334-0640情報処理学会シン ポジウムシリーズIPSJ Symposium Series,Vol.2001,No.12,pp.339-342,2001
[9]三木光範,廣安知之,吉田純一,金子美華,分散母集団GAにおける解探索能力,人工知能学会
全国大会,pp.240-241, 1999
[10] 三木光範,廣安知之,花田良子,ジョブショップスケジューリング問題への並列分散遺伝 的アルゴリズムの適用,情報処理学会第64回全国大会,pp.211-212, 2004
[11]謝孟春,馬火玄,藤原正敏,小高知宏,小倉久和,階層分散構造に基づく遺伝的アルゴリズム の一様性と多様性の調和,情報処理学会研究報告(MPS研究会),Vol.1998,No.105,pp.69-74,1998
[12]佐藤浩,小野功,小林重信,遺伝的アルゴリズムにおける世代交代モデルの提案と評価,人
工知能学会誌,Vol.12,No.5,pp.734-744,1997
[13]山村雅幸, 佐藤浩,小林重信,最小騙し問題を用いた世代交代モデルの解析,人工知能学会
誌,Vol.13,No.5,pp.746-756,1998
[14] 廣安知之,三木光範,佐野正樹,谷村勇輔,濱崎,雅弘,2個体分散遺伝的アルゴリズム,計測 自動制御学会論文集,Vol.38, No.11,pp.990 -995,2002
