形質獲得箇所を考慮した改良突然変異手法の効果検証

１．はじめに

遺伝的アルゴリズムにおいての突然変異 は、個体群の多様性維持の役割を担ってい る。本論文では、獲得された形質を考慮し た突然変異を行うことが適切な進化を促す と考えた。そして、形質獲得箇所を考慮し た突然変異手法を提案し、その効果を検証 する。ここで、形質獲得箇所とは、任意の ２つの異なる染色体の同一遺伝子座に同一 遺伝子が存在する場合、その遺伝子座のこ とを指す。この形質獲得箇所は、

２．組合せ最適化問題

組合せ最適化問題とは、「与えられた部 品の要求条件を満たす組合せのうち、与え られた評価尺度で最もよい組合せをみつけ る」という問題の一般名称である。

の配置設計や、物流における車両の配送計 画、工場における作業行程作成など、さま ざまな問題例がある[

３．巡回セールスマン問題（） 本論文で扱う組合せ最適化問題例は、巡 回 セ ー ル ス マ ン 問 題

!" #

の代表的な問題である。

図

#

(!&

# %

#&&

(&

(&# %)!*%

!*%+#&&

#&&

産業情報論集 "(( "#),-!&&."$*/

0 1 1

形質獲得箇所を考慮した改良突然変異手法の効果検証

又 吉 光 邦 當 眞 嗣 貢

図１ ９都市最短経路例

これを現在の計算機の能力でしらみつぶ しに探索するのは不可能なため、いくつか の手法が考え出されている。以下に、簡単 な分類を示す。

)厳密解法

最適解をつ見つける解法で次のような 手法が挙げられる。動的計画法、分岐限定 法、切除平面法、分岐切除法などである。

)近似解法

出力される解の最適解に対する精度が保 証されている解法である。ランダム丸め法 などである。

)発見的解法（近似解法）

出力される解の精度保証はない解法であ るが、探索時間を大幅に縮めることが期待 される。例としては、遺伝的アルゴリズム、

シミュレーティッド・アニーリング、局所 探索法、タブーサーチなどがある。

本研究では、獲得された形質を考慮した 突然変異を行うことが適切な進化を促すと 考え、形質獲得箇所を考慮した突然変異手 法を提案・検証する。従って、発見的解法 の遺伝的アルゴリズムを解法として用いる｡

の現実問題への応用事例

応用事例は、プリント基板などの穴あけ の順番決めなど実際に企業の製品生産コス トと密接にかかわってくる問題がある。図 ２はのベンチマークテストとして有名 な 、図３は実際の回路（基盤）の穿 孔順序の例で、と呼ばれるベンチ マークテストである。

は組合せ最適化問題のよい例題であ り、世界中で多くの研究者がに登 録されている例題の良い解 (巡回路）を短 時間で探索する研究をしている。

３ 遺伝的アルゴリズム()^[] の歴史

は、 とその弟子たち がミシガン大学で行った研究により始まる。

図２ tsp225問題例 表１ 都市数と総経路数

都市数 総経路数

９都市

都市 都市 都市 都市 都市 都市

図３ pr2392問題例（基盤穿孔順序）

歴史はかなり長く、のバイブルともい

う べ き の ｢

｣ が 年に発表されている。 らの研究で は、次の２つを目的としていた。

自然のシステムの適応プロセスを説 明する。

自然の重要なメカニズムを有する人 工的なシステムを設計する。

この中で の弟子である

は、の関数適応化の研究を行い、その 後のの１つの指標となる標準関数を導 入した。

これら らの研究により、その後 の研究は盛んになる｡ ! は理論 から応用に至る幅広い研究を行っている。

最近では、の目指す究極の目標である 人工生命の研究も盛んである。

とは

とは、複数個になる解の候補の表現 文字列を遺伝子"#$%&にみたて、それ を用いて染色体を構成する。そして、染色 体同士の交配により適合度の高い新しい優 良な個体（染色体）を生き残らせるという 適者生存則によって、最適解（最適個体)､

あるいは比較的良好な個体（近似解）を最 終的に得ようとするアルゴリズムである。

遺伝的アルゴリズム（）は、生物の 進化を工学的にモデル化し、また参考にし た学習的アルゴリズムであるが、適応範囲 が非常に広い事でも知られている。基本的 なとして､ ! によって提案され

た単純 '(

があり、これを元に実に種々な 手法が提案されている。

では、ある世代 を形成 している個体 ) の集合を母集団

と呼ぶ。また、では自然 界における生物の進化過程と同様に、環境 への適合度の高い個体が高い確率 で選択される。選ばれた個体に 対して、染色体の交叉)や突然変 異を確率的に発生させることに よって次の世代の個体群が形成される。最 終世代に得られた個体群の中で最も適合度 の高い個体が、最良なシステムとなってい る。

各 個 体 は 、 そ れ ぞ れ 染 色 体 ('"

) によって特徴付けられており、染 色体は遺伝子 の集まりで構成されて いる。また、通常では１染色体で１個 体を表現する。染色体上で各遺伝子のおか れている位置を遺伝子座という。

で扱う情報は遺伝子型： と表現型%'：%の二層構 造からなる。

遺伝子型()…のオペレータの 操作対象。染色体の内部構造にあたる｡

表現(%)…環境に応じて表現型から 適合度が決まる。環境に対する構造を示 すが、の場合、適合度と呼ばれる評 価値で表される。

%によって適合度が決まり、その適 合度が大きいものほど子孫を作りやすく、

小さいものほど死滅しやすい、すなわち淘 汰されるようになっている。これは、次世 代の各個体の適合度は前世代よりも等しい か、あるいは良いことを保障するものとなっ ている。

の手順

のおおよその手順は次のようになっ ている。

まず、初期母集団をランダムに生成す る。母集団とは、では１つの解を個 体として扱う。その個体の集合体のこと をいう。

次に交叉をして、新しい個体を生成す る。交叉は、母集団から親となる個体２ つを任意に選出し、その両親の遺伝子を 受け継いだ新しい個体を生成する。

次に、突然変異を行う。まず、母集団 から１つ個体を選ぶ。その個体の遺伝子 を一部入れ替えし、別の新しい個体とし て生成する。

交叉や突然変異で生成した新しい個体 は、親や元となった個体と比較し適応度 の良いものは次世代へ残り悪いものは淘 汰される。個体の評価とは、個体の持っ てる遺伝子を元に、巡回路の距離を計算 することである。終了条件が満たされる

までを繰り返す。

この選択、交叉、突然変異といった遺伝 子操作には色々な手法があり、その組合せ によって様々なタイプのを作ることが できる。

の 探 索 の 基 本 手順は選択、交叉、突然変異の３つである｡

以下に選択、交叉、突然変異について記す｡

選択

適合度の高い個体が次の世代により多く の子孫を残すという自然淘汰の考えは では選択（）とよばれ、個体の 中で問題での適合度のよいものは増殖し、

逆に悪いものは淘汰される。選択法には、

さまざまな方法が提案されており、その名 前だけをいくつか列挙すると、ルーレット 戦略、ランク戦略、トーナメント戦略、期 待値戦略、そしてエリート戦略がある。

本論文では、エリート戦略をもちいるの で、エリート戦略の簡単な説明を次に記す｡

エリート戦略

集団の中でもっとも適合度の高い個体を そのまま次世代に確実に残す方法である。

この方法を採用すると、その時点でもっと もよい解が交叉や突然変異で破壊されない 利点がある。ただし、エリート個体の遺伝 子が集団中に急速に広がることが知られて おり、エリートによる局所解に陥る危険性 もある。そこで、ある一定世代ごとにエリー ト以外のすべての個体を入れ替えるなどの 操作を伴う場合が多い (アルゴリ ズムなどと呼ばれる手法の一つである)。

図４ 遺伝的アルゴリズムの概略図

交叉

選択された個体間での染色体の組み換え により新しい個体を生成するという交叉 は、で重要な役割のひとつ である。交叉は、個体群の中から任意の２ つの個体（親）をランダムに選び、さらに、

ランダムに選ばれた１点、あるいは多点の 交叉点で遺伝子を組み替えることにより、

新たな個体（子）を生成する操作である｡

交叉の操作は次の３つの重要な点がある｡

・どのようにしてつの個体を選択する のか

・選択した２つの個体をどのように交叉 させるのか

・交叉により生成された新しい個体を以 下にして個体群の中に組み込むか これらは交叉確率や交叉点の数に関係し てくる。つまり、この３つの点の違いによ りいくつかの交叉方法が考えられる。本論 文では、循環交叉を用いるが、参考のため、

順序交叉、部分写像交叉、一様順序交叉を 記す。

順序交叉

まず、交叉点（＊）を決め、この交叉点 を元に引き継ぐ。交叉点から左部分は，個 体のものをそのまま受け継ぐ。

交叉点の右側は、個体の遺伝子の左端 から現れる順番で埋める。

部分写像交叉

まず交叉点（＊）を決め、その右側は個 体をそのまま引き継ぐ。

左側は，まだ引き継がれていない遺伝子 を個体のから引き継ぐ。

既に引き継いだ遺伝子がある遺伝子座は、

の右側部分の関係から決定する。

図５ 交叉点

図６ 未定の遺伝子座の遺伝子を決める

図７ 交叉点と遺伝子の継承

図８ 同一遺伝子の継承

一様順序交叉

まず、染色体長と同じ長さの進数記号 列 を作る。ランダムにとを入れた進 数記号列を元に遺伝子を引き継いでいく｡

子となる個体はの２つ作る。進数記 号列のに当たる遺伝子座にからへ、

に当たる遺伝子座にはからに引き継ぐ。

残りの空白部分は、対となる個体の左か ら順に引き継ぐ。

循環交叉法 本論文の交叉には、この法を用いた｡

法の具体的な手順は以下の通りである｡

まず、親の同一遺伝子を引き継ぎ、

残りは循環的に埋めていく。最初はから で、遺伝子座の都市を引き継ぐ。

の遺伝子座（都市）にある都市を、

の染色体で探す。の遺伝子座にある のでの遺伝子座に引き継ぐ。

図９ 残りの遺伝子の継承

図10 Tを用いた遺伝子の継承

図11 残りの遺伝子の継承

図12 同一遺伝子の継承

図13 残りの遺伝子の継承−1

次に、の遺伝子座５を見ると都市２が ある。都市２は、既に子に引き継いでい るので、今度はの遺伝子座で遺伝子を引 き継ぐことになる。の遺伝子座４にある 都市５を引き継ぐ。

の遺伝子座４を見ると都市４がある。

従って、の都市４がある遺伝子座６で子 は引き継ぐ。

最後は、の遺伝子座６に都市７がある ので、の都市７の遺伝子座で都市を引 き継ぐ。

突然変異

突然変異は、遺伝子をある確率で変化さ せる操作である。突然変異 は 染色体上のある遺伝子座の値を対立遺伝子 に置き換えることにより、交叉だけでは生 成しにくい子個体を生成して個体群の多様 性を維持することができる。

本論文は２点交換を用いた。また突然変 異を施される固体は、ランダムに選ばれる。

以下に、２点交換と共に比較として２点間 逆位、２点間撹拌による突然変異法の概略 を述べる。

２点交換

染色体中のランダムに選ばれた２点を交 換する。

２点間逆位

染色体中のランダムに選ばれた２点間に おいて順序を逆順にする。

２点間撹拌

染色体中のランダムに選ばれた２点間に おいてランダムに撹拌する。

図14 残りの遺伝子の継承−2

図15 残りの遺伝子の継承−3

図16 残りの遺伝子の継承−4

図17 残りの遺伝子の継承−5

図18 ２遺伝子交換

図19 ２遺伝子座間の逆交換

図20 ２遺伝子座間の攪拌交換

本論文では、突然変異を施す遺伝子座に 焦点を当てた研究成果を報告する。

局所探索法

では突然変異と交叉しか行われない ので、解の探索域が広く、そのために解の 質が比較的悪いことが知られている。その ため、解近傍の良解が得られないため、最 適解を見つけられない場合も考えられる。

これを解決するために、に局所探索

を組み込み、で得

た解よりもさらに良い解を得ることのでき る手法が考えられた。個体を評価する際に、

個体が表す解をそのまま評価するのではな く、それを初期値として、その解近傍を探 索する。の方法として、法などが ある。次の図に局所探索による解の移動 範囲（近傍）と初期解から局所最適解まで の解探索による移動図のイメージを示す。

本論文で用いたのは法の即時移動 戦略である。局所探索は初期母集団や交叉、

突然変異などで生成した個体すべてに行っ ている。以下に、本論文で用いた法 の手順を示す。

個体の染色体の内、２都市をランダ ムに選び、入れ替えを行う。

その個体をとし、その評価が個 体より良かった場合、これを個体と しの操作を行う。

その個体をとし、その評価が 個体より悪かった場合、入れ替えた 部分を元に戻し、タブーリストを作り 既に入れ替えを行った部分を除き を行う。

２都市のすべての組合せで、良くなら ない場合終了する。

４ 形質獲得箇所を考慮した突然変異手法 突然変異の難点

突然変異は局所解に陥るのを防ぎ、個体 群の多様性を保つが、染色体上における変 異は無作為に行われるため良い個体が発生 する確率は低い。

形質獲得箇所[]を考慮した突然変異 従来の突然変異は、染色体上のすべての 範囲での遺伝子座において入れ替えを行え る。そのため適応度を改善しない無意味な 入れ替えをすることが多々あると考えてよ い。これは突然変異が、多様性を維持する 半面、探索手法としての不向きさを示して 図21 局所探索のイメージ

図22 ２遺伝子交換

図23 評価が良好であった場合

いる。

そこで、提案する手法ではあらかじめ遺 伝上良いと思われる部分を抽出し、それ以 外の部分を変異させることにする。この

「良いと思われる部分」とは、まず変異さ せる個体とは別にもう１つの個体を個 体群からランダムに選び出し、この２つの 個体の同一遺伝子座に同一遺伝子が存在す る場合、その遺伝子と遺伝子座をいう。

我々は、この同一遺伝部分を形質獲得遺 伝箇所、あるいは単に形質獲得箇所と呼ぶ ことにする。

例えば図の左のような巡回路は、都市 １の次は都市２に巡回する方がよく右図に 示すように変える必要はないと考えられる｡

図のように淘汰され残った個体群には 形質獲得箇所が多く含まれる筈である。す なわちビルディングブロックの形成である。

形質獲得箇所は突然変異等で変更させずに、

それ以外の部分で突然変異をさせることは、

理にかなっていると考えられる。

順序化

形質獲得箇所を考慮した突然変異の機能 をより明確にする為に、比較に利用する個 体の順序化を行う。順序化とは、形質獲得 箇所が最も多くなるように遺伝配列ずらす ことである。

例えば、とには同一遺伝子がひとつ もないが、出発地点が違うだけで同じ経路 である。順序化をしても個体自体に影響は ない。

順序化を行わない場合、同一経路がある にも関わらず染色体としては全く違う個体 として扱われてしまう。例えば、図４の をと比較し順序化すると、のようにな り斜線の部分がと同一遺伝子となること がわかる。

非順序化

非順序化は、形質獲得箇所が最も少ない ようにずらすことである。図４のを、１ 遺伝子分シフトするだけで、形質獲得箇所 は最小となる（図５）。

図24 提案手法（斜線部が形質獲得箇所)

図25 形質獲得箇所を無視した突然変異

図26 形質獲得箇所

図27 順序化なしの場合

図28 順序化

５ 実験

実験環境

実 験 は ､ ､

を用い、プログラム言語 にはを使用。ベンチマークテストは 対称から（最適解、図参照）

と （最適解）を用いた!。選 択法はエリート戦略を用い、交叉法には"

#法を用いた。実験パラメータについては、

交叉率が％、個体群の占める突然変異の 発生率（突然変異率）は％、染色体長の 突然変異が起きる部分（突然変異長率）は ％、個体数は都市数と同じ、つまり の場合は個体。実験の回数は回で、

実験時間は５分。以下の適応度"を最小化 する。

実験は、従来の突然変異を用いた$%従 来&、形質獲得箇所に考慮した突然変異を 用いた$%形質のみ&、順序化し形質獲得

箇所に考慮した突然変異を用いた$%形質 順序化&、非順序化し形質獲得箇所に考慮 した突然変異を用いた$%形質非順序化&

の４つで比較実験を行った。

実験結果と考察

図は、の実験結果、図は の実験結果である。両図とも従来の手法 を黒の太線で記してある。

の場合、従来手法では評価値が 以上の改善は、伸び悩んでいる。それに比 べて、形質のみ、形質非順序化、形質順序 化は良い結果を示している。特に形質順序 化はどの手法よりも良好な結果を示してい ることが分かる。また、意外なことに形質 非順序化が、分を過ぎる頃から従来法よ りも良い結果を示している。これについて 我々は、解の多様性を形質非順序化がもた らしたのではないかと考えているが、更な る調査研究が必要である。

形質のみと比べて形質非順序化が良好で ないのは、形質獲得箇所を考慮した突然変 異が、進化に対して良好な結果を与えてい ることを示すものとして理解してよい。

ここで世代初期の段階では評価が悪い。

その原因として考えられるのは、初期集団 では形質獲得箇所があまりなく、進化が進 んだ中盤以降は形質獲得箇所が増えたため、

適応度" ＝

図29 非順序化

図30 eil51の最適解 図31 eil51 (最適解:426)(100試行平均)

良い結果を出していると思われる。

の場合、従来手法では評価値が 以上の改善は、伸び悩んでいる。それ に比べて、形質のみ、形質非順序化、形質 順序化は良い結果を示している。特に形質 順序化はどの手法よりも良好な結果を示し ていることが分かる。また、と同様、

形質非順序化が、３分を過ぎる頃から従来 法よりも良い結果を示す場合がある。ただ し、ほどの優位性は見られない。

一方、形質のみと比べて形質非順序化が 良好でないのは、形質獲得箇所を考慮した 突然変異が、進化に対して良好な結果を与 えていることを示すものとして理解してよ い。特に、形質順序化を施したものは、世 代を重ねるごとに漸次適応度改善を進めて おり、最適解まであと少しであることが分 かる。このこともまた、形質獲得箇所を考 慮した突然変異が、進化に対して良好な結 果を与えていると解してよい。

６ まとめと課題

本論文では、獲得された形質を考慮した 突然変異を行うことが適切な進化を促すと 考え、形質獲得箇所を考慮した突然変異法 による効果実験を行い、検証した。実験の 結果は、形質獲得箇所を考慮した突然変異 手法は従来の単純な突然変異（２遺伝子交

換）よりも良好だということを示した。特 に形質順序化を施した場合の突然変異に効 果が大きく認められた。

今後の課題としては、今回のベンチマー クテスト以外の複数のユークリッドベ ンチマークテストでの効果検証を行い、定 性的性質を同定していきたい。

付記

本論文は､ ｢當眞嗣貢，又吉光邦，形質 獲得箇所を考慮した突然変異手法の効果検 証，情報処理学会全国大会論文集, ｣ []に加筆したものである。

参考文献

! "#"#$ %&$'$%$(

)' * 山村 他，形質の遺伝を重視した遺伝

的アルゴリズムに基づく巡回セールスマ ン問題の解法，+,)) ．

-伊庭斉志，遺伝的アルゴリズムの基礎―

.,のなぞを解く―，オーム社，/))0． *山本芳嗣，久保幹雄，シリーズ現代人 の数理 巡回セールスマン問題への 招待朝倉書店、/))10．

久保幹雄，サプライ・チェインにおけ る最適化理論の役割と応用事例 −配送 計画を中心として−．

當眞嗣貢，又吉光邦，形質獲得箇所を 考慮した突然変異手法の効果検証，情 報処理学会全国大会論文集， ． 図32 berlin52(最適解:7542)(100試行平均)