自己紹介 - センターレポート

こんな私ですがうよろしくお願い致します.

引越し歴埼玉に生まれ18年間を過ごし，その後，船橋(千葉県)で1年，津田沼(千葉県)で4年，横浜で5年間を過ごしヲ現在?長崎に在住.

コンビュータ歴小学生の頃に，

I

ファミリーベーシックjというゲーム機につなぐコンピュータ(のようなもの)に触れる.大学3年の頃に， EPSONの386マシンを友人より 3万円で購入?それを 1年程度使用した後，ショップブランドPCを購入.中身のパーツを入れ替えながら自作PCとして現在も利用.最近， SONYのVAIOノートを(展示品特価で)購入した.

趣味バイク，スキューパ・ダイビング?カクテル作り(最近はストレートやロックで飲むことが多い).

最近実現した夢バイクでの一人旅.横浜から長崎まで.

最近の悩み時々?ウラ声になる.

後悔している(?)こと HappyHacking Keybordに手を出してしまった.もう他のキーボードは使えない.

不思議だったこと 7年ほど前う誰も卒業しないのに卒業旅行に行った.5名中2名が大学院へ進学， 3 名が留年でした.

爽快だったこと 8年ほど前，ハワイでハーレーに乗った.スキンヘッドに黒丸サングラスだったのでアメリカ人にも結構ウケた.

怖かったこと原チャリを買ったばかりの頃，間違って高速道路に入ってしまった.煽られまくりでした.

過去の幸運運転免許合宿に行ったとき，合宿最終日のボーリング大会で優勝してしまった.この時だけなぜかいいスコアが出た.普段のスコアはせいぜい

1 0 0

1 2 0

程度なのだが…

過去の栄光高校生の頃ヲぶら下がり懸垂が

3 0

回以上できた

3

遺伝的アルゴリズムについて

[ 1 3 ] 3 . 1

概要

遺伝的アルゴリズム

(GA)

はうダーウイン進化論

[ 2 0 ]

に基づく生物の進化の過程を模倣とした工学的モデルでありう最適化問題における最適化手法としての有効性が報告されている.生物界では?ある環境下における同一種の生物集団の中で，生殖行動を行うことで子を生成する.しかし?生殖行動を行うことができる者?すなわち親となることのできる者は，その環境下での生存競争に勝ちうまた，生殖行動のパートナーを得ることのできた者(有性生殖の場合)だけである.このような者はう「環境に適応し，優れた生存能力をもっ者」とされる.優れた者の子はう優れた親の遺伝子を受け継いでいるためうやはり優れた者である可能性が高い.また，遺伝子に突然変異が起こることによってより優れた者になる可能性もある.こうして，集団から環境に適応できなかった者の遺伝子が消え去り?環境に適応

した者の遺伝子が増えていくことで集団全体が進化していく.

GA

では，

生物界

GA

生物 → 解生存能力 → 解の品質

生殖行動，突然変異 → 解を生成または変更する演算子環境 → 解空間(探索空間)

と対応させ，個体集団を進化させることによって良好な解を得る.

3 . 2 G A

の特徴

3 . 2 . 1 G A

が最適化の対象とする問題領域

GA

は，さまざまな分野に応用されているが，

解空間構造が不明であり，また，全探索が不可能と考えられるほど広大な解空間を持ち，現実的な厳密解法が発見されていない

という特徴を有する問題を対象問題とする.フロアプラン設計問題 (Floorplandesign problem) ，巡回セールスマン問題(TravelingSalesman Problem : TSP) ，看護婦スケジューリング問題 (Nurse Scheduling Problem : NSP)などの組合せ最適化問題や非椋形・高次元・多峰性といった特徴を持つ関数最適化問題が代表的な応用例として挙げられる.これらの問題の解法としてはサンプル点を評価しながら試行錯誤的に探索する手法である確率的探索手法が一般的に用いられる.

GA

も確率的探索手法のひとつである.確率的探索手法には GAの他に?シミユレーテッドアニーリング (Simulated Annealing : SA) [7]やタブーサーチ (TabuSearch)などが挙げられる.

また，多目的最適化問題や動的に環境(最適化すべき関数)が変化する最適化問題も GAの得意とする領域である.

3 . 2 . 2 G A

の長所

確率的探索手法には，探索空間全体を浅く広く探索する大域的探索能力と有力な解候補が発見される可能性が高い領域を深く集中的に探索する局所的探索能力という相反する 2つの能力をバランス良く備えることが要求される.SAやタブーサーチではうこのうちの大域的探索能力の限界が指摘されている.一方

GA

は大域的探索能力に優れており?他の手法と比較してより優れた性能を示した例が多

く報告されている.またう他の手法とのハイブリッドアルゴリズムの有効性も報告されている.

個体 (individual) 染色体(chromosome) 染色体長 (chromosomelength) 遺伝子 (gene) 遺伝子座 (locus) コード化 (encoding) コード化法 (representation) 遺伝子型 (genotype) 表現型 (phenotype) 集団 (population) 集団サイズ (populationsize) 交叉 (crossover

，

recombination) 交叉確率 (crossoverrate) 親個体 (parent) 子個体 (children，offspring) 突然変異 (mutation) 突然変異確率 (mutationrate) 目的関数 (objectivefunction) 適応度(五tnessvalue) 適応度関数 (fitnessfunction) 選択 (selection) 世代 (generation) 世代交代モデル

(generation alternation model)

3 . 2 . 3 G A

の短所

表

1 :

主な

GA

用語の一覧解に対応するもの

個体を記号列や文字列などで表現したもの染色体の長さ

染色体を構成する最小単位染色体上の遺伝子の位置解を染色体で表現すること

コード化の方法

個体の染色体による内部表現形式

染色体から対応する解へデコードされた外部表現形式個体の集まり

集団に含まれる個体の数

複数の個体の遺伝子情報を基に新たな個体を生成する遺伝的演算子

交叉を行う確率

交叉において遺伝子情報を提供する個体交叉によって生成される個体

ひとつの個体をもとに新たな個体を生成する遺伝的演算子突然変異を行う確率

最小化または最大化すべき関数個体の良好きを示す値?

適応度を決める関数

複数の個体からいくつかの個体を選ぶこと

GA

では，ある決まった手順を繰り返すことによって探索を進めるが，その繰り返しの1単位

世代交代の枠組み

GA

の枠組みは非常に柔軟であり?その設計に関する多くの部分が設計者に委ねられている.前述のGAの長所を生かすためには，適切にGAを設計する必要が有り?また?適切なパラメータを設定する必要がある.これらが不適切な場合には，ランダムサーチ以下の性能になってしまうこともある.

一般に，他の確率的探索手法と比較して，

GA

は多くの計算時間を必要とする.この点の改善策として， GAが並列計算を行う特長を活かしてう複数のCPUによる計算の並列化が提案されている.

確率的探索手法全般に言えることであるが，最終的に得られた解に対して最適解の保証がない.またう最終的に得られる解が試行のたびに異なることがある.

3 . 3 G A

の枠組み

ここでは， GAの大まかな枠組みについて簡単に説明する.ただし7前述のようにGAの枠組みは非常に柔軟で、あるため?あくまでも一例として理解していただきたい.

GA

では，生物のしくみに対応した独特の用語が使われる.GAで用いられる用語を表1に示す.アルゴリズムの概念図を図1に示す.

GA

は次の手順からなる確率的過程である.

選択 ^¥

• ^O ^O

^@^@

^の ⁽ ^j ⁾

^{(複製選択)}^~

^~ o ^&y ⁴ ^・ ^C

A

次世代へ

生存選択) _可_F交叉

キゆで・

⁽ ^j ⁾

^.^司司^.^.^.^.^.^.^t^突^然^変^異

1¥ 今

図

1 :

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

[ 1 8

，

1 9 ]

( 3 )

交叉…交叉確率に従いヲ交叉を行なうかどうかを決定する.交叉を行なう場合?親個体の遺伝子情報を用いてひとつまたは複数の子個体を生成する.

( 4 )

突然変異…子個体に突然変異を加える.突然変異確率はう子個体ひとつひとつに対して突然変異を行なうかどうかを決定するのに用いられる場合および子個体の遺伝子座毎に対して用いられる場合がある.

( 5 )

生存選択

( s e l e c t i o nf o r s u r v i v a l )

…生成された子個体集固またはそれに親個体集団を加えた集団から?次世代集団とする個体を選択する.

(6) (2)に戻る.

(2) ^{r v}(5)を1世代とし?終了条件を満たすまでこれを繰り返し?生成されたすべての個体の中で最

も良好な個体を最適化問題の解とする.

3.4 TSPへの応用例

GAの応用例としてヲ TSPへの応用について説明する.5都市(各都市の名前を a，b， c， d， eとする) のTSPを想定する.

[コード化]

コード化の例としてう"パス表現

( p a t hr e p r e s e n t a t i o n ) "

を挙げる.パス表現とは巡回する都市の順番どおりにコード化する方法であり， b，c，a，e，dの順番で巡回するとした場合にはう b，c，a，e，d と染色体

にコード化される.

[世代交代モデル]

世代交代モデルの例として，

" M i n i m a l G e n e r a t i o n Gap (MGG)"

を挙げる

[ 1 8 ] .MGG

はう次の手順を 1世代として探索を進める.

( a )

複製選択…集団からランダムに2個体を親個体として選択する.

( b )

交叉…選ばれた親個体を用いて交叉を行いう複数の子個体を生成する.

( c )

生存選択…親個体および子個体の中で最良の個体と?残りの個体から適応度に基づいたルーレツト選択によって選ばれた個体の2個体を次世代に生き残る個体として選択する.

MGG

では突然変異は一般的には用いられないがう用いる場合には生存選択の後で用いる.

終了条件は集団が収束するまでとすることが一般的であるが?他の手法との比較実験の場合にはう世代数?評価個体数?計算時間

(CPU

タイム) ，などを用いることもある.

MGG

の例を図

2

に示す.

図 2・世代交代モデル MGGモデル [18]

a . ー、

_、 _C

¥，・ー@

/ 1 > .

. ドーーー

、、

d ーも

FU 4'!

一︐

︐

. t

・ァ

L U

¥・1

e d

! !

k e C

図3:1点交叉の例

[交叉

l

交叉の例として)"1点交叉 (onepoint crossover)"を挙げる 1点交叉とは，両親の染色体を適当な 1点で切断し，その左右をおEいに交換し合う交叉である目親個体 1をa丸

とした場合，例えば遺伝子座3と遺伝子座4の問で切断した場合には，子個体1は a，b，c，e，d子個体2 はbρムd，eとなる 1点交叉の例を図3に示す

[突然変異]

突然変異の例として"スワツプ(いsw乱叩p)"を挙げるこれ土lは³任意の遺伝子座の遺伝子を 2つ選び'交

f

換失するものである bρAムd，eとUい、寸う染色体を持つ個体に遺伝子座 1と5の部分にスワツフ。をかけると， e凡

a a

c G

e e

図 4:スワップによる突然変異の例

表 2:進化型計算のおおまかな分類

通称正式名文献主探索オベレータ主なコード化法

GA G e n e t i c A I g o r o t h 叫 H o l l a n d

， J

. H .

[5，6] 交叉文字列(特にバイナリ)

EP E v o l u t i o n a r y P r o g r a m m i n g F o g e l

， L.J. [4] ^突然変異テーブル構造

ES E v o l u t i o n S t r a t e g y R e c h e n b e r g

， 1. [9] ^突然変異実数値

GP G e n e t i c P r o g r a m m i n g K o z a

， J.R. [8] 交叉木構造

EC E v o l u

七

i o n a r yC o m p u t a t i o n F o g e l

，

D . B .

[3] 上記のものすべての総称

性質を持つ実数値

GA( R e a l ‑ c o d e d GA) [ 1

，

1 5 ]

の出現や，これらを統合した国際会議である Genetic

αηd Evolutionαry Computation Conference (GECCO)の開催などに見られるようにう近年は境界がなくなりつつある.

3.6 G Aの解説文献

本章では

GA

について簡単に紹介してきたがうより詳しい解説が必要な場合には?次に示す文献が参考になる.なお，ここでは日本語の文献のみを紹介する.

まず，

GA

一般については?文献

[ 1 9 ]

および文献

[ 1 7 ]

が参考になる.今回

GA

の応用例として挙げた

TSP

については，文献

[ 2 3 ]

が詳しく，

GA

による

TSP

の解法は

[ 1 4

，

2 4 ]

が参考になる.実数値

GA

については文献

[ 1 5 ]

を，

GA

の設計論については文献

[ 1 2

，

2 1 ]

を参照されたい.

4

着任前の研究紹介研究内容は?大きく

l.探索オベレータの機能分担を考慮した

GA

2.フロアプラン設計問題への接近 3.関数最適化問題への接近

4.サンプリング・バイアスを考慮した

GA

に分けられるが?紙面の都合上本稿では「サンプリング・バイアスを考慮した

GAJ

についてのみ簡単に紹介する.本章にて紹介する内容の詳細については，文献

[ 2 2 ]