個人情報と進化
1 御挨拶
総合情報処理センター 染 奇 博 司
[email protected]‑u.ac.jp
平成 1 3 年 4 月より長崎大学総合情報処理センター助手に着任しました.経歴などのオフィシャル な自己紹介は，下記のスタッフ紹介のページから辿れる筆者のページを御参照願います.
http://w3.cc.nagasaki‑u.ac.jp/center/staff‑jis.html
次章では?筆者の簡単な自己紹介をさせて頂きます .3 葦では，筆者が着任前までに行なってきた研 究分野である遺伝的アルゴリズム ( G e n e t i cA l g o r i t h m ; GA) [ 5 ぅ 6 ] について紹介し， 4 章では
7筆者が 着任前までに行なってきた研究の一部を簡単に紹介させて頂きます.
なお， 3 章からは研究についての内容のため，文体が論文調に変わります…
2 自己紹介
こんな私ですがうよろしくお願い致します.
引越し歴埼玉に生まれ 1 8 年間を過ごし，その後，船橋(千葉県)で 1 年，津田沼(千葉県)で 4 年，横 浜で 5 年間を過ごしヲ現在?長崎に在住.
コンビュータ歴小学生の頃に， I ファミリーベーシック j というゲーム機につなぐコンピュータ(の ようなもの)に触れる.大学 3 年の頃に， EPSON の 3 8 6 マシンを友人より 3 万円で購入?それを 1 年程度使用した後，ショップブランド PC を購入.中身のパーツを入れ替えながら自作 PC とし て現在も利用.最近， SONY の VAIO ノートを(展示品特価で)購入した.
趣味バイク，スキューパ・ダイビング?カクテル作り(最近はストレートやロックで飲むことが多い).
最近実現した夢バイクでの一人旅.横浜から長崎まで.
最近の悩み時々?ウラ声になる.
後悔している(?)こと HappyH a c k i n g Keybord に手を出してしまった.もう他のキーボードは使え ない.
不思議だったこと 7 年ほど前う誰も卒業しないのに卒業旅行に行った. 5 名中 2 名が大学院へ進学， 3 名が留年でした.
爽快だったこと 8 年ほど前，ハワイでハーレーに乗った.スキンヘッドに黒丸サングラスだったので アメリカ人にも結構ウケた.
怖かったこと原チャリを買ったばかりの頃，間違って高速道路に入ってしまった.煽られまくりで した.
過去の幸運運転免許合宿に行ったとき，合宿最終日のボーリング大会で優勝してしまった.この時だ けなぜかいいスコアが出た.普段のスコアはせいぜい 1 0 0
rv1 2 0 程度なのだが…
過去の栄光高校生の頃ヲぶら下がり懸垂が 3 0 回以上できた
つらかったこと高校卒業記念に仲間とやった， 24 時間耐久ボーリング大会.
最近の生き方シミュレーテッド・アニーリング [ 7 ] のように生きる.若い頃の失敗や回り道は将来の 役に立つ(と自分を慰める) •
1 0 1
3 遺 伝 的 ア ル ゴ リ ズ ム に つ い て [ 1 3 ] 3 . 1 概要
遺伝的アルゴリズム (GA) はうダーウイン進化論 [ 2 0 ] に基づく生物の進化の過程を模倣とした工学 的モデルでありう最適化問題における最適化手法としての有効性が報告されている.生物界では?ある 環境下における同一種の生物集団の中で，生殖行動を行うことで子を生成する.しかし?生殖行動を行 うことができる者?すなわち親となることのできる者は，その環境下での生存競争に勝ちうまた，生殖 行動のパートナーを得ることのできた者(有性生殖の場合)だけである.このような者はう 「環境に 適応し，優れた生存能力をもっ者」とされる.優れた者の子はう優れた親の遺伝子を受け継いでいるた めうやはり優れた者である可能性が高い.また，遺伝子に突然変異が起こることによってより優れた者 になる可能性もある.こうして，集団から環境に適応できなかった者の遺伝子が消え去り?環境に適応
した者の遺伝子が増えていくことで集団全体が進化していく.
GA では，
生物界 GA 生物 → 解 生存能力 → 解の品質
生殖行動，突然変異 → 解を生成または変更する演算子 環境 → 解空間(探索空間)
と対応させ，個体集団を進化させることによって良好な解を得る.
3 . 2 G A の特徴
3 . 2 . 1 G A が最適化の対象とする問題領域 GA は，さまざまな分野に応用されているが，
解空間構造が不明であり，また，全探索が不可能と考えられるほど広大な解空間を持ち，現 実的な厳密解法が発見されていない
という特徴を有する問題を対象問題とする.フロアプラン設計問題 ( F l o o r p l a nd e s i g n p r o b l e m ) ，巡 回セールスマン問題(Tr a v e l i n gSalesman Problem : TSP) ，看護婦スケジューリング問題 ( N u r s e S c h e d u l i n g Problem : NSP) などの組合せ最適化問題や非椋形・高次元・多峰性といった特徴を持 つ関数最適化問題が代表的な応用例として挙げられる.これらの問題の解法としてはサンプル点を評 価しながら試行錯誤的に探索する手法である確率的探索手法が一般的に用いられる. GA も確率的探 索手法のひとつである.確率的探索手法には GA の他に?シミユレーテッドアニーリング ( S i m u l a t e d A n n e a l i n g : SA) [ 7 ] やタブーサーチ (TabuS e a r c h ) などが挙げられる.
また，多目的最適化問題や動的に環境(最適化すべき関数)が変化する最適化問題も GA の得意と する領域である.
3 . 2 . 2 G A の長所
確率的探索手法には，探索空間全体を浅く広く探索する大域的探索能力と有力な解候補が発見され る可能性が高い領域を深く集中的に探索する局所的探索能力という相反する 2 つの能力をバランス良 く備えることが要求される. SA やタブーサーチではうこのうちの大域的探索能力の限界が指摘されて いる.一方 GA は大域的探索能力に優れており?他の手法と比較してより優れた性能を示した例が多
く報告されている.またう他の手法とのハイブリッドアルゴリズムの有効性も報告されている.
個体 ( i n d i v i d u a l ) 染色体( chromosome) 染色体長 (chromosomel e n g t h ) 遺伝子 ( g e n e ) 遺伝子座 ( l o c u s ) コード化 ( e n c o d i n g ) コード化法 ( r e p r e s e n t a t i o n ) 遺伝子型 ( g e n o t y p e ) 表現型 ( p h e n o t y p e ) 集団 ( p o p u l a t i o n ) 集団サイズ ( p o p u l a t i o ns i z e ) 交叉 ( c r o s s o v e r ， r e c o m b i n a t i o n ) 交叉確率 ( c r o s s o v e rr a t e ) 親個体 ( p a r e n t ) 子個体 ( c h i l d r e n ， o f f s p r i n g ) 突然変異 ( m u t a t i o n ) 突然変異確率 ( m u t a t i o nr a t e ) 目的関数 ( o b j e c t i v ef u n c t i o n ) 適応度(五t n e s sv a l u e ) 適応度関数 ( f i t n e s sf u n c t i o n ) 選択 ( s e l e c t i o n ) 世代 ( g e n e r a t i o n ) 世代交代モデル
( g e n e r a t i o n a l t e r n a t i o n m o d e l )
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 は次の手順からなる確率的過程である.
( 1 )初 期 化 ( i n i t i a l i z a t i o n ) 集団サイズぶんの個体を生成し?初期集団とする.初期集団となる個体 はうランダムに生成されることが多い.
( 2 )複製選択 (selectionfor reproduction)…集団に存在する一部またはすべての個体から次の 交叉の親となる個体を選択する.
‑103‑
選 択
¥• O O @ @ の ( j ) (複製選択)~ ~ o &y 4 ・ 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 モデル [ 1 8 ]
C
a . ー 、 、 C
¥ ， ・ ー@
/ 1 > .
. ド ー ー ー 、 、
d ー も
FU 4 ' !
一 ︐
︐ .
t
・ ァ L U
¥ ・ 1
e d
! !
9 u
k e C
図 3 :1 点交叉の例
[ 交叉 l
交叉の例として) " 1 点交叉 ( o n e p o i n t c r o s s o v e r ) " を挙げる 1 点交叉とは，両親の染色体を適当な 1 点で切断し，その左右をお E いに交換し合う交叉である 目 親個体 1を a 丸
とした場合，例えば遺伝子座 3 と遺伝子座 4 の問で切断した場合には，子個体 1 は a ， b ， c ， e ， d 子個体 2 は b ρムd ， e となる 1 点交叉の例を図 3 に示す
[ 突然変異]
突然変異の例として"スワ ツプ(い sw 乱 叩 p ) " を挙げる これ 土 l は
3任意の遺伝子座の遺伝子を 2 つ選び'交
f
換失するものである bρA ムd ， e と U い、寸う染色体を持つ個体に遺伝子座 1 と 5 の部分にスワツフ。をかけると ， e 凡
3 . 5 進 化型計算の分類
ここまで
3進化型計算 ( E v o l u t i o n a r yComputationj EC または E v o l u t i o n a r y Algorithm j EA) の ひとつである GA について紹介してきたが，進化型計算と分類されるものには ， 表 2 のようなものがあ る従来までは，これらの分野毎にそれぞれが別々に情報交換を行な ってきたが， GA と ES の中間的な
‑105
ー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 ] の出現や，これらを統合した国際会議である G e n e t i c
α η d E v o l u t i o n α r y Computation C o n f e r e n c e (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 ] および文献 [ 2 1 ] を参照願いたい.
4 . 1 背景と目的
関数最適化は，実問題への応用範囲の広い重要な最適化問題のひとつである.近年，関数最適化問
題への有効な手法として，コード化に実数ベクトルを直接用いた GA である実数値 GA が注目を集め
親 個 体 数 子 個 体 数
サンフサ l
‑ ‑ ‑ +リング ‑ ‑ ‑ +
ー
∞ i 定 義 減 ∞ + 主 主 主』 一 ‑ d ν 定 義 域 ∞ +
( a ) 探索空間が ト ∞汁∞] のときの理想的なサンプリング
親 個 体 数 子 個 体 数
1 1
￨ ‑ 1 f ー+リング i 方 LI ー ‑ .
lAn mj x 主主主 1 「 I A I n m よ x
定 義 域
r定 義 域
( b ) 探索空聞が [ m i n ， ma x ] のときの理想的なサンプリング
親 個 体 数 子 個 体 数
1 1
￨ ‑ 1
与一孟 ム ン リング プ モ ー → 4I 1 1 I ‑
守
￨ d i n r Y 1 4 x ￨ (交叉 ￨
、IA i n mjx
定 義 域 ・ 定 義 域
( c ) 探索空間が [ m i n ， ma x ] のときの ，一般的な交叉オベ レータによるサンプリング
図 5 : 交叉によるサンプリングの例
ている .喜多らは GA を構成する選択・世代交代モデル，交叉などの遺伝演算子の設計に関して「機 能分担仮説 J と呼ばれる考え方を提案している [ 1 2 ] . これは，遺伝演算子それぞれの担うべき機能を 明確にし，その機能を考慮した設計指針に基づいて遺伝演算子を設計するべきであるという考え方で ある.喜多らは交叉に関して「交叉は有限の個体群に対しては新しい子を生成する能力を保有しつつ，
個体群の分布は変化させないように設計すべきである j との設計指針を示している.これに基づき，
親個体集団の平均値ベクトルや分散 ・ 共分散行列といった統計量を子個体集団に遺伝させる交叉が提 案されており ，高い性能を示すことが報告されている [ 1 5 ] .
図 5 ( a ) に，定義域ト∞，+∞]を探索空間とした場合の交叉による子個体生成(サンプリング)の例 を示す.この例では，子個体群は親個体群と同様に探索空間に 一様に分布しており，機能分担仮説の 設計指針を満たした理想的な交叉であるといえる . 次に，図 5 ( b ) および ( c ) に探索空間が [ m i n ， m a x ] の場合の例を示す. ( b ) の例では，子個体群の分布は親個体群から変化しておらず， ( a ) と同様に理想 的な交叉であるといえる. 一方 ， ( c ) の例では，親個体群の中心付近に多数の子個体が生成されてお り，境界付近には少数の子個体しか生成されていない . このようなサンプリングを行うと，最適解が 境界付近に位置するとき，最適解が発見されにくいことが考えられる .
実数値 GA では通常，初期個体集団は探索空間に一様に生成される . このとき，単峰性正規分布交 叉 ( U N D X ) [ 1 6 ] などの多くの実数値 GA の交叉オペレータでは，探索空間の中心付近を探索しやす い一方，境界付近を探索しにくく，探索空間の境界付近に位置する最適解を発見しにくいことが報告 されている [ 1 0 ， 11 ， 1 6 ] . この問題が生じる原因として，交叉によるサンプリングの確率密度に偏りが あることが挙げられる . UNDX などの多くの交叉オペレータを用いたサンプリングでは，図 5 ( c ) の ような偏りのあるサンプリングが行われる.このサンプリングの偏りはサンプリング ・ バイアスと呼
‑1 0 7
ー1 . 4 1 . 2
主 主 ，
トいいい"附山ι川"剛"山"附山… l川川"刷山."川"仰川.削.'山"叫叫.剛..叫叫.除刷叫"刷"叫叩..剛 山 " 叩 " 叩 叩 剛 剛 剖 叫 .E
~ 0 . 8 主 E i 0 6
D‑
0 . 4
0 . 2
。
0 . 1 0 . 2 0 . 3 0 . 4 0 . 5 0 . 6 0 . 7 0 . 8 0 . 9 Domain 0 1 D e f i n i t i o n
図 6 :UNDX によるサンプリング・バイアスの例
ばれる [ 2 ， 1 1 ) . 図 6 に UNDX のサンプリング・バイアスの例を示す.これは，横軸の [ 0 . 0 ， 1 . 0 ) の範 囲に親個体集団を 一様に生成し，ランダムに親個体を選び交叉を行った場合の子個体生成確率の理論 値を縦軸に示したものである.なお，定義域内の一様なサンプリングを行うランダムサーチの子個体 生成確率の理論値を1. 0 としている.中央付近は探索されやすい 一方，境界付近の探索密度は低いこ
とがわかる.近年，実数値 GA は実問題のアプリケーションとしてもその有効性が報告されている.
しかし，実問題では最適解の位置は未知であり，より広く実数値 GA を実問題に応用するためには，
サンプリング・バイアスを考慮した最適解の位置にロバストな手法が望まれる.
本研究の目的は，サンプリング ・ バイアスを考慮した，最適解の位置に対してロバストな実数値 GA を実現する手法を提案することである.
4.2 既存手法の特徴とその問題点
代表的な既存手法に b o u n d a r y e x t e n s i o n b y m i r r o r i n g (BEM) [ 1 0 ) が挙げられる BEM は，探索 空間の外側に拡張領域を設けることで探索空間を拡張し，境界付近を相対的に探索空間の中心に近づ け，サンプリング・バイアスを緩和する手法である .探索空間の拡張程度を調節するパラメータであ
る T e ( 0 < T e < 1 ) に基づき，探索空間の境界面において鏡写しをするように拡張領域は生成される.
個体は，本来の探索空間の境界を超えて，拡張領域に生成されることを許され， x ( 包 ) =(zF ， ， d))
を染色体にもつ個体 Z の評価値は次式に従って計算される .
f ( x ( i ) ) f C f T ( 包 ) ) ， ( 1 ) y ( i ) ( U I ( z ) '
ー， Y~))
i f Xj < m i n j
ん
33 ( z )
2 maxj
ーi f Xj > maxj X~ 3
τ)o t h e r w i s e
ここで， m i n j および maxj はそれぞれ， J 次元の定義域を表す最小値および最大値である.初期個 体集団は，本来の探索杢関内に 一様に生成される . しかし BEM はサンプリング・バイアスを緩和す ることには成功しているものの，探索空間内の領域すべてを同じ探索密度で探索することはできず，
サンプリング ・ バイアスが残存している.ロバスト性の観点からは，サンプリング・バイアスが無で
あることが望ましい.
I K
本来の 探索空間
1/2
r r : i n
室主主盟
盤強探索空間 2 1
max i 々
e ‑ 町 、 ' " e ‑ m a x
図 7 :TSC による探索空間の変換例 ( 1 次元)(左)および TSC によって生成された拡張探索空間での 交叉の例 ( 2 次元)(右) .交叉オペレータは UNDX .
4 . 3 TSC の提案
サンプリング ・ バイアスを無くし，実数値 GA のロバスト性を高める探索空間変換手法である T o r o i d a l S e a r c h S p a c e C o n v e r s i o n (TSC) を提案する. TSC によ って生成される探索空間は ，球面のよ うに中 心や境界の区別のないトーラス状の空間である.また， TSC では，初期個体集団は拡張探索空間に 一様に生成される.従って ， TSC によ って，探索空間内のすべての領域は同等に探索され，サン プリ
ング・バイアスは存在しない . TSC は，次に示す手順で実行される.
s t e p l BEM と同様に，探索空間を r e = 1 . 0 で拡張する.
s t e p 2 拡張された探索空間の両端を， トーラス状に連結する.
変換された探索空間の例を図 7 に示す.直感的には，各境界面に鏡を置き，合わせ鏡にした状態 を想像されるとわかりやすい.本来の探索空間および拡張領域を合わせた探索空間を拡張探索空間 ( e x t e n d e d s e a r c h s p a c e ) と呼び，拡張探索空間の境界を超えた連結された探索空間を仮想探索空間 と呼ぶことにする.初期個体集団は拡張探索空間に 一様に生成され，交叉は次の C千千言語に類似し たコードで表される手順によって行われる .
交叉に必要な k 個の親個体を選ぶ ; / / 一 一 親 o ~親 k-l とする for (int i=l; i <k; i++){
pow(2 ， n) ー 1 個の親 i のクローン個体を作る ; //一‑‑ n は次元数
親 O に最も近い者を親 i 及びクローン個体から選ぶ;
}
親 O 及び for 文中で選ばれた k‑ l 個体で交叉を行う;
親 l のクローン個体とは，図 7 (右)に示すように，仮想、探索空間内の親 1 に対応する点に位置する個 体である .上記の for ループ内のクローン個体の生成及び選択は，次のように行われる.
1 0 9 一
10
1
•
ザ6
8
‑3 .2 ‑1
e ・
10図 8 評価値がすべて等しい関数において全世代を通じて生成された個体の分布(左 :TSC なし，右 : TSC あり)
クローン i 親 i ;
/ / 一 一 親 i のベクトルをコピー for (int j=O; j<n; j++){
}
double dist 阻 ce クローン i [ j ] ‑ 親 o [ j ] ; if (fabs(dist 叩 ce) > l){
//一一 1 は拡張探索空間の幅の半分の大きさ if (dis 七 回 目 > = O){ クローン i[ j ]
ー=21;}
else f クローン i[ j]+=21;}
〉
変換された探索空間はトーラス状なので生成された子個体久 X ( z ) = ( d L ， d))? は，次式に従っ て修正される .
X ( i )
z ( 包 ) z ( i )
=(zf) ， ， d)) ，
( ̲ ( i )
I Xil + 2 1 i f Xj
イ ~ x y ) ‑ 2 1 ぜ Xj> 問 的
l x ; i ) otherwise
( 2 )
ここで e‑mmj ， e‑maxjはそれぞれ，拡張探索空間の j 次元の定義域を表す最小値および最大値であ る.例えば，図 7 の A および B に生成された子個体は拡張探索空間の外側に位置しているため ，A' および B ' に修正される.この修正によって，親個体聞の距離が遠いときは各親個体の近くの境界付近 に子個体が生成されることになる(図 7 ( 右)のグレーの領域).修正された子個体 t の評価値は， BEM と同様に ( 1 ) 式によって計算される .
4.4 サンプリング・バイアスが存在しないことの実験的確認
本節ではサンプリング ・ バイアスが生じていないことを実験的に確認する.評価値がすべて等しい
関数， f ( X ) = 1 ，を目的関数とし， TSC を用いない場合， TSC を用いた場合に生成された全世代の個
体分布について調べる.目的関数の次元数は 2 次元，定義域は [ ‑ 5 . 0 ， 5 . 0 ] である.交叉オベレータに は UNDX をう世代交代モデルには MGG を用いる.突然変異は用いない. MGG は，すべての個体の 評価値が等しい場合ランダムな生存選択になるため，サンプリング・バイアスがなければ探索空間全 体が一様に探索されるはずである.図 8 に実験結果を示す. TSC を用いない場合は探索空間の境界 付近がほとんど探索されていないのに対して， TSC を用いた場合は一様に探索されており，サンプ
リング・バイアスが解消されていることが確認できる.
5 終わりに
本稿では自己紹介および着任前の研究成果の報告を行ないました.今後はう教育活動およびセンター 運営活動と共に?生命情報，広域計算機ネットワークなど，大規模かつ複雑で大量の情報を扱う情報 処理の研究および情報処理に関する教育工学の研究活動を行っていきたいと考えています.
参考文献
[ 1 ] Dav 院 L . : The Handbook o f G e n e t i c Algo 叫 hms ， Van Nostrand Reinhold ， 1 9 9 0 .
[ 2 ] Eshelman ， L . J . ， Mathias ， K. E . and Scha 百 . e r ， J . D . : C r o s s o v e r Operator B i a s e s : Explo 凶 珂 t h eP o p u l a t i o n D i s t r i b u t i o n ， i n P r o c e e d i n g s o f t h e 7 t h I n t e r n a t i o n a l C o n f e r e n c e on G e n e t i c Algo 門 thms ， 1 9 9 7 .
[ 3 ] F o g e l ， D. B . : An I n t r o d u c t i o n t o Simulated E v o l u t i o n a r y Optimization ， IEEE T r ;
日 間.on Neuml Net ω r k s ， Vo l . 5 ( 1 9 9 4 ) ， 3~ 1 4 .
[ 4 ] F o g e l ， L . J . ， Owens ， A. J . and Walsh ， M. J . : Art~βcial I n t e l l i g e n c e t h r o u g h Simul αt e d E v o l u t i o n ， Wiley ， New York ， 1 9 6 6 .
[ 5 ] Holland ， J . H . : Ad α : p t a t i o n i n Natuml and A r t i f i c i a l Systems ， The U n i v e r s i t y o f Michigan P r e s s ， 1 9 7 5 . [ 6 ] Holland ， J . H . : Ad α : p t a t i o n i n Natuml and A r l i f i c iα1 Sy 府 間 The MIT P r e s s ， second e d i t i o n ， 1 9 9 2 .
[ 7 ] K i r k p a t r i c k ， S . ， G e l a t t ， C . and V e c c h i ， M . : O p t i m i z a t i o n by Simulated Annealing ， S c i e n c e ， Vo l . 2 2 0 ( 1 9 8 3 ) ， 671 ‑ ‑ 6 8 0 .
[ 8 ] Koza ， J . R . : Geηe t i c Progmmmi 吋 ， The MIT P r e s s ， 1 9 9 2 .
[ 9 ] Rechenberg ， 1 . : E v o l u t i o n s s t m t e g i e : Optim 附
"UngT e c h n i s c h e r Systeme nach Prinz 明 end e r B ω o g 附 henE
叩l u ‑ t i o n ， F r i e d r i c h Frommann V e r l a g ， S t u t t g a r t ， 1 9 7 3 .
[ 1 0 ] T s u t s u i ， S . : M u l t i ‑ p a r e n t Recombination i n G e n e t i c Algorithms with S e a r c h Space Boundary Extension by M i r r o r i n g ， i n P r o c e e d i n g s o f t h e F i f t h I n t e r n a t i o n a l Coη > J e r e n c e on Pαm l l e l Problem S o l v i n g j ト
"Om Nature ， 1 9 9 8 . [ 1 1 ] Tsuts 肌 S . : Sampling B 副 andS e a r c h Space Boundary Extens
C
巴e 必 d mg ρ so f t 仇 h eG e n e t i c αndE
り仰0 1 ω 叫 u t i ω 0 η 白 r y Compu ω t α ω t i ω 0 η Coη : f e n
陀巴7 η l C αe 2000 ， 2 0 0 0 .
[ 1 2 ] 喜多ー，山村雅幸:機能分担仮説に基づく GA の設計指針，計測と制御， Vo l . 38 ( 1 9 9 9 ) ， 612~617.
[ 1 3 ] 山村雅幸:進化計算論講義プリント，講義資料，東京工業大学大学院総合理工学研究科知能システム科学専攻， 1 9 9 6 . [ 1 4 ] 山村雅幸，小野貴久，小林重信:形質遺伝を重視した遺伝的アルゴリズムに基づく巡回セールスマン問題の解法，人工
知能学会誌， Vo l . 7 ( 1 9 9 2 ) ， 1049~ 1 0 5 9 .
[ 1 5 ] 小野功，山村雅幸，喜多一:実数値 GA とその応用，人工知能学会誌， Vo l . 1 5 ( 2 0 0 0 ) ， 259~266
[ 1 6 ] 小野功，小林重信:単峰性正規分布交叉 UNDX を用いた実数値 GA による関数最適化，人工知能学会誌， Vo l . 1 4 ( 1 9 9 9 ) ，
1146~1155.
[ 1 7 ] 北野宏明(編): J 宣伝的アルゴリズム 1 ~ 4 ，産業図書， 1993~2000.
[ 1 8 ] 佐藤浩，小野功，小林重信:遺伝的アルゴリズムにおける世代交代モデルの提案と評価，人工知能学会誌， Vo l . 1 2 ( 1 9 9 7 ) ，
734~744.
![図 2 ・世代交代モデル MGG モデル [ 1 8 ] C a .ー 、 、 C ¥ ， ・ ー@ / 1 > . .ド ー ー ー 、 、 d ー も FU 4'! 一︐︐.t・ ァLU¥・1ed! ! 9u k e C 図 3 :1 点交叉の例 [ 交叉 l 交叉の例として) " 1 点交叉 ( o n e p o i n t c r o s s o v e r ) " を挙げる 1 点交叉とは，両親の染色体を適当な 1 点で切断し，その左右をお E いに交換し合う交](https://thumb-ap.123doks.com/thumbv2/123deta/10157870.1991711/5.854.211.657.118.786/世代交代モデルMGGモデルーー例として挙げる染色体しその.webp)
