計抑自動制御学会東北支部 第1占7回研究集会（19卯．5．16） 資料番号16T−1 GAを用いた動的巡回セールスマン問題へのアプローチ Approach to Dynamic Traveling Salesman Problem Using GA 吉田等明，○和賀光悦，恒川佳隆，三浦守 HitoakiYoshida，OKouetsuWaga，YoshitakaTsunekawa，MamoruMiura 岩手大学 Iwate University キ，ワpド：遺伝的アルゴリズム（GeneticAlgorithm），巡回セールスマン問題汀raYelingSalesman Problem），動的巡回セ，ルスマン問題（DynamicTravelingSalesmanProblcm）， 連絡先：〒020 盛岡市上田4−3−5 岩手大学工学部情報工学科 和賀光悦Tel：（019）6ユ3−5491，Fax：（O19）623−549l，E−mail：waga＠cis．iwate−u．aCjp 1．はじめに 遺伝的アルゴリズム（GeneticAlgoritlm：GA） スマン問題に拡張した．巡回セールスマン問 題とは．複数の都市を全て1回ずつ訪問して とは，遺伝子を持つ仮想的な生物の集団巷計 最初の都市に戻ってくる経路のうち，最短距 算機内に設定し，あらかじめ定めた環境に適 応している個体が．子孫を残す確率が高くな 離のものを探索する問題である（囲1）． るように世代交代シミュレーションを実行 し，遺伝子を変化させることにより生物集団 を進化させるものである．これは具休的に， 都市b ①初期集団の生成，②適応度の計算及び③遺 伝的操作（淘汰，交差，突然変異）の各処理 から成る．GAは，最大最小値探索問題や組 み合わせ最適化問題のような，探索に非常に 時間のかかる問題に対して有効なアルゴリ ズムである．本研究では，GAを組み合わせ 最適化間樋の1つである巡回セールスマン 問題に適用し，さらに一般的なアルゴリズム では計算が困難と思われる動的巡回セール 都市d 都市e 園1．巡回セールスマン問題 2．本研究のねらい 布告b 量子力学では，同時に確定できる物理量の 借が時間的・空間的に変化しない状態のこと 都市。、 竺も 都市c O を国有状態と呼ぶ．固有状態では，物理量は ー 都市軸 ノノ ある固有値として観測されるが，この状態は 通常ほとんどない．固有状態でないと幸は， ○一′′ 物理量の観測値はランダムになるのではな く期待値として求められる．図2は，電子線 散乱の様子である． ○ 〔〕 都市d 都市亡 国3．動的巡回セールスマン間規 都市αは，1箇所に固定されておらず，向l2， 】cllユ，lcユl2の確率で恥恥α2のいずれかの 値を取るものとする．また一定時間後には， 都市ロの位置は再び不確定になるものとす る．このような統計的かつ動的な経路を最適 化する問題は，通常のアルゴリズムでは取り 扱いが困難である．本研究では，統計的性格 をもつGAを①通常の巡回セールスマン問 題及び②動的巡回セールスマン問題に適用 図2．電子線散乱 した結果について報告する． 3．GAを通常の巡回セールスマン 多数の電子がスリットを適ってスクリー ン上に達したとき，スクリーン上で観測され 問題に用いた場合 る電子は，ある1点だけに集中するのではな まず，GAの条件を以下のようにして実行 く．また，スクリーン上の全体にランダムに した． 観測されるわけでもない．電子は，図2のよ うにある一定の範囲内で統計的に観測され 方法1 る・観測値をα榊（椚＝0，1，2，■・・）のいず ・佃件数 れかと㌧その出現確率をIcmlユとすると・ ・辻伝手長 月ビット （Ⅲ：都市数） 最大200個 期待値αは（1）式のように表される． 1 ・適応度 云＝lqlユ鴨＋l亡．lα1十】ビュlヱ鴫＋・・・（1） 2 （尺：巡回距離） ・突然変異串10％ ・淘汰方法 ルーレット方式 ・解となる経路 一般の最適化アルゴリズ この不確定性を持つ状態を，巡回セールスマ ムで用いられているような適応度が最も大 ン問題で表現すると図3のようになる．ただ きい個体（エリート〕の経路を解とするので し．今回は簡単化のために，1都市〟だけ はく，集団の中で最大個体数巷持つ生物種に の不確定性状態を扱ってみた． 対応する経路を解とした 2 爪リ −50世代 一■U −−−−1抑世代 ＝・・150世代 一且一 …・川201酒代 ∩‘ 方法2 ーU ［盟称糊拡 しかし，方法1では正解率が悪く，正解率を 上げるため次のような改良貴行った． ▲‖リ ・適応度〔訂（屈：巡回距恥 一総当たり法 4 5 8 丁 8 tl10 1112 都指数 国5．者肺放と誤差率 ・突然変異率 初期世代 20％ 以後1世代につき −0．5％ 最小（39世代以後）0．5％ 図4からは．総当たり法の場合は．都市数 が増えれば解が出るまでの計算時間が極端 に長くなるが，GAでは，都市数が増えても 以上の2つの方法に対する結果を蓑1に 示す．平均誤差率，平均正解率ともに方法1 解が出るまでの計算時間はあまり変わらな よりも方法2の方がよい結果が得られてい いことが分かった．図5から，GAでは，都 る． 市数が多くなれば誤差率も高くなり，世代数 が大きくなれば誤差率は低くなることが分 かるが．100世代以降の誤差率は，あまり変 化していない．また∴総当たり法では．都市 表1．改良前と改良後の比較（5都市） 世代数 平均誤差車 平均正解率 方法1 方法2 数が増えても常に正解となっているのが分 50 3．03！i 3ヰ％ 100 50 2．9了％ 35％ 0．8訓i ￠！摘 100 0．ヰ2！i 85！i かる． 4．GAを動的巡回セールスマン間 題に用いた場合 2で説明した動的状態を表現するために， それぞれ，10世代，5世代，3世代に1回の 次に，通常の巡回セールスマン問題でGA と総当たり法の比較を行った．それぞれ100 割合で都市αの位置巷恥叫，αユの中からラ 回づつシミュレーション杏葉行し，計算時聞 ンダムに再決定し，シミュレーションを行っ 及び誤差率の平均値巷求めた．それらの結果 た・ここで．都市打椚の出現確率hP巷 を図4と図5に示す． 】c。lユ＝l亡．ド＝トユド 1 として 3 3 100回づつ実行し平均値を求めた．都市数は 5で行った（図6）． 2 ［s¶匪皆軸薦 ［盟副型恥 D 0 都市数 図4．者師敬と計算時間 …‥・・1咄軒宅ごと −・…5世代ごと −ヨ世代ごと 50 1（伯 t卯逝 図6．世代放と誤差率 lま1 2側 つJ 虹0 個体数 ■‖凸 図6から．3世代ごとに都市の位置を再決 亡U−A︼ 定した場合も，5世代ごとも，10世代ごと n古 も正解からの誤差率が収束しているのがわ かる．これは，都市の位置を頻繁に再決定し nU た場合もそうでない場合も誤差率が収束す 10 2D 30 誤差率％ （A）都市ロの位置ロ♂（84世代目） 個体の分布の様子である． 即抑亜部0 世代ごとに都市の位置を再決定した場合の L 個体敬 るというGAでの良い点である． 囲7及び図8はそれぞれ10世代ごと，3 ＿＿三且 即組側即0 個体数 楷郎 鮎）肺臓動揺僻目㌢ 20 lO D 罰躍率％ （A）都市αの位置叫侶0世代目） 爪U▲‖∨ 20 3D 誤差率％ の都市αの位置叫（gO世代目） 爪‖V 6．At2 個佐敷 Oロ 10 0 爪じ 爪U ● ♯市㌔のとき正解となる経路書持つ個体 10 0 20 30誤差率 ％ ▲ ホ市d、のと卓正解とな五経鞍を持つ個体 〔B）都市αの位置鞄（90世代目） ■ 朝市㌔のと書正解とな各線路を持つ個体 × モの他の経路せ持つ個体 軋 8仁U4−qム 0 圃8．3世代ごとに新市を再決定Lたときの■体の分布 ＞r ⊥…且＿；可 10 訓 告O誤差率 ％ 国7及び図8の様に，仮想的な生物集団が， （C）都市αの位置勒（100世代目） 動的環境に適応した結見都市叫「呵Zのそ ● 都市㌔申とき正解となる経路を躊つ個体 れぞれの場合の正解となる個体が常に存在 ▲ 相和やと書正解となる経路壷持つ個拝 すること，そして都市の再決定後は，すみや l都市㌔のとき正解となる経路竜神つ個件 かにその正解となる個体が増える傾向があ X モの他の経路善持つ個体 ることが分かる． 園丁．10世代ごとに都市を再決定したときの七休の分布 次に．都市αの位置暮それぞれ3個，5 個，10個の中からランダムに再決定し，シ ミュレーション貴行った（国9，国10及び 囲11）． 4 持 川 ［凸檜岬濾 ．．＼ゝ㌦．一 加 20 ・・…＝1叫豊代ごと 帽 −・＝司軒仁辻 T。 −3世」仁丑 』嘩些準翠聖恕 5 耗5 0 8 郭 0 1〔0 1茄 祉 1郭 H泊 ㈹ （舟斬 郡 加 ほ 柑 10 冨山逼盃 15 ︻芭≠州縫 5 5 巨」転−』鵬山 ＿ 0 知 t∝1 柵 ㈱7都市 抑 ■︼ 帽 ■一 柏 冒］甘刊姓 n− ［芭甘咄雄 ∴′∴ 人V −− −一十−＿㌢ゞ チl′ き 幻 l00 1相 世代駄 （q9都市 図9．都市αの位置を恥叫，穐の3個の中からラ 図10．都市αの位置を恥一叫の5佃の中からラン ンダムに再決定した墳合．すなわち． −1 1 とした場合 ダム に 再決定 し た 1 1 1 α≡α0十αI＋♂コ d＝α0十αl＋α2 1 た墳合 5 1 加 l 抑 一〇 血ロ ︻王叶≠鶉 ウー■U 川 ︻凸檜欄濃 相 ▲．ケー∧U 5 部 1∞ 1助 m I 8 T 世代数 （郎5都市 10 11 中 t0 11 （郎珊七日 一 幻 n■ エE 叩 き ■− 言曝岬輩 ’■ Ⅷ 害掛岬雄 0 モ・｛ナ㌧† 一 ！氾 1甜 l聞 一 世代敵 書 榊 （印1∝世代目 （印7都市 ▲﹁ 節 O 叩 t︼ ［王線欄鈍 ウl 椅 ︻芭甘刊沌 ゴごごご加・−一一−t￣ 8 ■V ノ ■■ 4 ．＿．ごニニニニご＝抽h．−，．一ノ ′ダ 2 50 Ⅹ0 1知 t【氾 5 8 世代蝕 （q9都市 T tI 榊 0 10 （q20ロ世代目 図11．都市αの位置を叫∼叫の10個の中からラン 図12．10世代に1匝lの割合で．都市αの位置暮それ ダム に 再決定 し た場合，すな わ ち ぞれ，3個．5個．10佃の中からランダムに再決定 ＿1 1 1 1 α≡αp＋叫十＝…＋両α8＋両α，とした した場合 場合 都市巷3個の中から再決定した場合より 図9，図10及び国11から都市数が多くな も10個の中から再決定したときの方が誤差 ったり，都市の位置の再決定が頻繁に行われ れば，誤差率が大書くなることが分かる．そ 率が高くなっている．また，都市数が大書く なれば誤差率も高くなるが，それでも高々 して，都市数が多い方が誤差率が収束するま 10％程度である． での世代数が多いが，やはり誤差率は収束し 最後に，10世代ごとに都市αの位置を恥 ている． 叫，叫の3個の中から再決定した場合につ 次に，10世代に1回の割合で，都市α亡D いて誤差率の時間変化巷調べた（図13）． 位置をそれぞれ，3胤 5個，10個の中か らランダムに再決定した場合右横々な都市 数でシミュレーションを行った（囲12）． 6 11 5 まとめ 00 今回は次のこと巷行った．まず，①研究の 御 伽 劇 ［竺称 珊 輔 ・・・・…仙 基礎として通常の巡回セールスマン問題に 一越当たり法 GAを適用した，次に，②不確定性を持つ状 瓢 態を動的巡回セールスン問題で表現しGA 春用いてシミュレーションを行った． m空 m6 也4 m8 1 ①では，都市数が多い場合には，総当たり 法よりもGAが有用であることが分かった． 昭間［s］ （A）7者師 伸 即 劇 ［巴略柵湛 剥 ②では，都市数に関係なく，都市の位置の再 決定が，頻繁に行われる場合もそうでない場 合も，仮想的な生物集団が動的環境に適応し 憩 0 た結果，誤差率が収束するという結果が出た． 皿2 吼4 吼8 吼8 このことは，通常のアルゴリズムでは，解を 1 時間［s］ 求めることが難しい動的巡回セールスマン （扮8都市 わ 幸たことを示すものである． 的 今後は，位置の不確定な都市が多い場合に 劇 ︻芭甘拙雄 00 問題に対し，GAでは成果を上げることがで 抑 適用することにより．一般性について検討す 0 n2 nl q8 吐息 る予定である．また，ゆらぎのある系や非平 衡状態の系への応用も検討している． 1 柵』】 〔q9都市 囲13．10世代ごとに都市αの位置を恥恥勉の 参考文献 3個の中から再決定した墳合での誤差率の時間変化 1）安居院猛，長尾智晴：ジェネティックア ルゴリズム，昭晃堂（1993） 2）米揮保雄：遺伝的アルゴリズムー進化理 図1ヨからわかるように，総当たり法は計 論の情報科学−．森北出版（1993） 算に時間がかからない7都市では常に正解 3）北野宏明（編）：遺伝的アルゴリズム， となっているが，都市の再決定する間隔と同 4ヨ／帆産業図書（1993） 程度の計算時間の8都市では，正解と不正解 4）長倉三郎，中島威（緬）：化学と量子論， l の開巻振動している．そして，それ以上に計 21／諷岩波書店（1979） 算時間がかかる9都市では，常に不正解とな 5）岡部成玄：量子論一連動と方法−，ヱ／ヱも っている．それに対してGAでは，都市数に 近代科学杜（1992） 関係なく正解からの誤差率が常に収束して いる．このことは，通常のアルゴリズムでは， 解巷求めることが難しい動的巡回セールス マン問題に射し，GAでは成果巻上げること がで卓たこと巷示している． 7
© Copyright 2024 ExpyDoc
