計測自動制御学会東北支部 第164回研究集会（1996．11．22）
資料番号164−1

遭伝的アルゴリズムにおける人為淘汰の提案とその適用
IGentetic11gorith usinglrtifitialSelection○永見広次＊，坂野 進■轟○圧irotsuguⅣagami＋，Susumu Sakano＝

書目本大学，−書目本大学■Nihon University，埠＋Ⅳihon tJniversity
キーワード：遺伝的アルゴリズム（Genetic Algorithm），最適化〔Optimization），活性化（Activation），人為淘汰〔ArtifitialSelection〕
連絡先：〒963−10郡山市田村町 徳定 手中河原1日本大学工学部 機械工学科
メカトロニクス研究室 永見広次，Tel∴（0249〕568774，Fax．：〔0249）56−8860

1． まえが善ののみを選んで次世代の個体を決定すると、局

近年、遺伝的アルゴリズム（GA）はその最所的な解にとらわれ解の収束性が著しく悪くな適イヒあるいは探索能力を利用して、組み合わせる。これを避けるために適応度の低い個体も確問題、最適化問題‖〜5）などの数理科学の分野の率的に残す、あるいは交叉、突然変異の方法をみならず位置決め、制御など工学分野の問題り工夫するなど経験的な処理を行っている。これ叫巨）にも適用されつつあり、新しい解法として注ら人の手を加える方法は自然淘汰という考え方目されている。遺伝的アルゴリズムは鮎11andに反するものである。そこで、本研究では、こによる提案以来、種々検討され改良されて卓てれまで経験的に行われてきた、計算時間を短くいるが、未だ発展途上の研究分野であり、系統するための種々の方法をも含めて、活性化手法だった、信頼性の高い手法としての確立が期待による多様化の考え方を提案する。GAにおいされている。GAは従来の探索手法では解決のて、自然淘汰と人為淘汰巷併用することにより困難な問題に対して、短時間の処理時間で解を解の収束性が良くなり、計算時間を短縮で喜る見出しうるが、局所解が多々存在するような問ことを示す。

題においては、余り有効ではないとも言われて本稿では、活性化の手法を巡回セールスマンいる。GAは自然淘汰による個体の進化という、問題（TS P）に適用し、その有効性を示す。

適者生存と遺伝情報の継承の考え方をアルゴリ

次に、ロボットの逆運動解析に適用し、その有ズムとして採用し、問題の解法として用いる。

効性、および具体的な傾向を調べる。

実際の解析においては、適応度の高い優勢なも2． 人為淘汰と活性化

然変異により遺伝子がより優秀になる可能性は2．1 従来のGAの間痛点低くなる。GAではそのような場合が多く、あGAの持つ問題点を整理し、以下のような二る段階から収束速度を鈍らせている〔図1）。

このような状態から脱出するためには、ある世るが、数世代で収束する場合もあれば、数十万代での優秀な個体の増殖を妨げ、個体群として世代でもなお最適解に到達できない場合もある。

は不安定で多様な状態にすることが有効である。

この間題の解決には二つの課題がある。収束速不安定な状態におく作業が人為淘汰の付加であ度を速める課題と収束速度のばらつきを少なくる。人為淘汰の手法として、活性化、遺伝子操する課題である。後者の課題はGAが乱数を多作、遺伝子融合等が考えられるが、以下には活用しており、その基本操作を変更しない限り現性化の手法を取りあげる。活性化の手法の導入

状では解決困難であろう。本研究では前者の問により、個体集団全体の画一化が避けられ、常題に対して、系統だった解決方法の可能性を示に最適解を求めて世代が進んでいくこととなる。

す新たな方法として人為淘汰を付加したGAのここに活性化とは 異種混合による活性化 ●提案を行う。

で、部分的初期化のことである。この手法は個体群全体を破壊することなく活性化へと導くた

2．2 人為淘汰の概雇
GAは大局的な収束は速いが、局所解から抜めに、確率的に発生箇所を定めるのではなく、け出すのはきわめて違い。ある世代で優秀な個が人為的と呼ぶ所以である。

体がしばらくその優位を保ったときに、その個確定的に発生箇所を指定することとなる。これ
活性イヒは一部の個体群を完全に初期化するた体の遺伝子パターンを持つ子孫が増殖する。こめに、その数、位置に注意を払わねばならない。の状態では、その個体を越える優秀な遺伝子をGAのメインアプローチは交叉であり、活性化持つ個体が現れる可能性は善わめて低い。このも交叉を支援するような形を取る。全体に対しような状態でのGAは善わめて安定しており、てさほど多くない数の個体を初期化する。位置突然変異による他の個体の登場を待つより方法については、優秀な個体を初期化しないように、はなくなる。突然変異はある個体のほんの一部適合度の低い個体を初期化する。図2に活性化分を変化させるだけであり、染色体の一部分がの手法の概念を示す。

その個体の適合度を支配している場合など、突堰

lウリhJ4■b■b7︻b9Tlllll■1111川1222胡犯4749糾82

ワ■︻J■▲・﹁コ一口7Q山一封︼几Undとである。構造上、取りうる値は必ず見いだせ

n．1111■1111111111111上−ltal

つU解の収束する時点が予測不可能であるというこ■Ud﹁−d．一．．4．■1．一■

fig．1交叉の効果が得られない状態︼日一▲

第2は工学的側面で、GAを用いた解析では血■﹁必要である。

▲1

多様化を図るためには、何らかの異種の混入が▲︼．■−▲▲．1．．4

個体を発生させる仕組みがなく、系の活性化、﹂．．4■を持つものではない。この種にGAはより良い4．4■体を活性化多様化できるほど強力なインパクト

ュ

れ、同一種の氾濫を招いている。突然変異は全山

汰の手法である。交叉は同じ系の中でのみ行わ

古でのわずかな変化を頼りに進化していく自然淘

ロ1r【W6【■【ell111111川1】111Lll111珊M肌（ID朋q11111111川111111111110（lM肌仙川耶
1111111110111】11111110別冊叩000O
l】l111111011111111111（IDO耶Ⅲ0川O
lllLlll11（11111）lLllllDMmⅢMOO
llllllll川11111111111DO8Ⅲ0馴川00
111111‖101111111111川肌帖0馴）川田
llllllllllIl】111111111川M伽仙川M
l1111111川11111111111m山肌仙川Ⅲ
1111】11110111Llll11HmODqDMO川11111111】机1111111111叩0㈹00MM11‖1】111111111111111日Ⅲ001削削削
11Llll‖川I111111川110【lM肌仙川別Il‖11ユ耶肌l‖」11】‖川叩00仙川珊
1111111111】1111111111（l帥00m州側1‖111111【11111111川肌仙川叫肌1（l叩1】11】111川111111川○Ⅲ川q叩DqDl叩
111111111（Ill11111【lM胴M叩朋M朋111111111肌11111剛小川剛l川剛仙川耶
1111101】川1】111100（相川ql叩州別朋

由5151515151515151515151朝粥罰¶l柑帽m朋鵬k

第1は生物学的側面で、GAは一つの系の中間つの側面から考える。l相月al＄a18Sm∈±n：90
SGA
P「OPO60dGA

初期化された個体
2000
G申n即aljon

10ロ0

fi富．Z ＝活性化の方法

fig．4 活性化を付加したGAと単純GAとの

8． 巡回セールスマン開場の解析枯果

比較

50100
lnitlalSa匝Smen

flg．5 初期条件による効果（2000世代後の影響）

fi已．3 TSP問題モデル国

図4は、世代毎の最適値の平均的変化を表した
巡回セールスマン問題に、従来のGA（SGものであるが、これを見るとPGAもSGAとA）と提案したGA（PGA）を適用した場合同じく、初期段階での激しい収束を見せ、次第の比較を行った結果が図4、図5である。にその収束速度が低下していくのが見られる。

また、解法の為の各パラメータを去1に示す。

また、その収束速度がS GAと比較して1，5倍の速度で収束しているのが判る。特に、収束

TabJelTSP解法の為の条件「「（）POSed GAly王eS亡t亡Ction st「al亡占yCrゥs帥Ver rat亡Mutatil）n r且t亡
At：tivation rate

試用

ヱU

10．
・・・100Hyb「 d：；e0．
0．1atl￠ 丘 亡n亡rations
0．1atモVe「yE亡nerationが安定しだした時点というのは、S GA、PG
Aでその差が最も見いだしにくい段階であると予想されるにも関わらず、常にPGAがS GAよりも高い適合度を示しているのが判る。

図5は個体群の大書さによるPGAとS GAの比較を行った結果を表したものである。これを見ると、PGA、S GAともに個体数が増える

に従って、2000世代後の最適解がより小さな値を取っていくのが判る。これは、探索点が増えるに従って、正しい解を見いだす機会が増えていくということを表している。また、PG
AはSGAと比較して、各点において3〜5％の経路短縮を見せている。このことば、先の解

4．1 活性化手法の効果
図7に活性化の手法を付加したGAと代表的なGAであるSGAをロボットの逆運動解析に適用した結果を示す。活性化の手法を付加したGAの最適解に至る世代数はSGAの約1／2となっており、前述したTS P解法と同様に、活性化による収束速度の上昇がみられる。GAが析でも裏付けされている。

目標値へ高速に収束するための条件ば ある世
4．

ロボットの逆運勤解析への適用

代における最良な個体の持つ遺伝子の適応度がどれだけ目標値に近いか ではなく、 最適解となりうる個体の遺伝子がどの位多く存在するが である。活性化の手法は個体集団の中に多様性をもたらし、多様化により最適解となりうる個体を多数存在させる役割を果たしている。
玉石▲l

亡
t＝l

亨．1

2．1

flg．6逆運動解析モデル図t．1
l

ロボット逆運動解析へ提案する活性化の手法○王ヰ8

砧帽r■tl州江tXl∝pt血頑を適用し、従来の単純GA（SGA）と比較した結果を述べる。なお、ロボットの逆運動学は

fig．7 活性化GAと単純GA
図8に活性化の演算処理を行う世代について調エンド・エフェクタの位置と姿勢との目標に対べた結果を示す。

してロボットの関節角を求めていくことであるが、以下では、手法の比較に重点を置き、位置のみを目標値として与えた場合について述べる。
なお、本研究において使用した、解析のための各パラメータを次に示す。

Table2 逆運動解析のための条件
Proposed GA SGA
Numbers ロf city
populaいon siヱ巳
Selection strate已yCr〔ISSOVer rate

Mutati（】n rate
Activ∈ltion rate

Zロ

100
Hybrid selection
0．10．1atlO已巳n巳ratlons
0．1atev巳ry
已eneraいon

ktj一員tion perioJ（ti憮古1

fig．8 活性化の効果

本解析の場合には、10世代前後に1回の活烏性化の処理が有効であることを示している。活注意すればよく、中位の個体との入れ替えの方性イヒはある周期で適用した方が効果があること

がより個体集団の多様性が増し、より高速に収を示している。周期が短いと多様化が進み過ぎ、束することが考えられる。

周期が長くなると活性化による変化の効果が少なくなると考えられる。

6． まとめ以上に述べて幸たように、人為淘汰としての

5． SGAとの比較
以上の結果は、PGAが遺伝的アルゴリズム

活性化の手法は交叉を中心としたこれまでのGAの枠組みを崩すことなく、計算処理の効率化の概念を継承している事を示す一例である。こを図るものであり、GAの汎用性もそのまま継れらのことば、GAがこれまで様々な問題解決承している。このことは、GAがこれまで適用のために適用されてきた分野に対して、PGAされて喜た種々の分野の問題解決に本報告の手も適用可能であることを示すものである。

法が適用可能であることを示している。

さらに同一条件下のもとでは、PGAはSG人為淘汰という枠組みの提案と、具体的な方Aより収束効率が良いことが示された。活性化法としての活性化の手法はGAの有する特色をの手法がSGAに比べて高速に収束するのは、損なうことなく、その収束効率、探索効率を高より常に新たな個体を加えることにより、個体めていると結論づける。

群の遺伝子の分布の多様性を国り、局所解にと遺伝的アルゴリズムはきわめて汎用性が高く、どまることなく最適解により速く到達可能であ

比較的自由に広い範囲の問題に対して適用で善る為である。この多様性の維持によって、PGる。しかし、最近のGAは個々の問題への適用AがS GAに対してその収束効率の優位性を保において、応用を急ぐあまりに特殊化しすぎ、ちつつ、GAの特徴を継承していることが判る。

GAの本質を見失いかねない状況にある。

これらの結果、我々の提案した活性化手法は、本報告では、従来のGAの基である自然淘汰GAの特色を損なうことなく、その収束効率、の考え方に加えて、人為淘汰の考え方を併用す探索効率を高めていることが結論づけられる。

ることを提案した。具体的には、交叉を中JL、と活性化の手法は個体群の多様性を維持するたしたこれまでのGAの枠組みを崩すことなく、めの手段で、集団の遺伝子分布において、希少人為淘汰の一つの手法である活性化手法を導入な個体を発生させ、これを集団内に定着させるすることにより局所解にとどまることなく、収手段となっている。

束速度の向上を図ることが可能であることを示

活性化の手法は一部の個体群を完全に初期化した。

するために、その数及び入れ替えの位置について注意が必要である。発生する個体の数につい卓考文献ては、GAの主役はあくまでも交叉であり、活1〕波多野寿昭；GAによる最適化，計測自動制御学性化も突然変異も交叉を支援するような形でな

会論文集．32−1，52（1g93）

ければならない。活性化の数を多くすることは、

2＝．［．nolland：Adaptationin Naturaland

ランダムに探索することに近づき、どの位の数

ArtificialSyste皿S．Unv．of A4ichigan

が適当なのか、問題により異なってくるのか、

Press〔1975）

今後の検討課題である。入れ替えの位置につい3）D．E．GoldBerg：GeT）etic Algorithzninては、本報告では下位の個体との入れ替えを行

Search，OptimizatiDn，and Hachine Learning，ったが、優秀な個体を初期化しないことのみを

Addison＝胃esly（1989）

4）E．G．David：Genetic Algorithms，AddisoT卜Yse 237〔1994）
ly（1980）17）西原，石原，松久，佐藤；遺伝的アルゴリズムに5〕山村，小林：遺伝的アルゴリズムの工学的応用．

よる受動形ジャイロ制振機構の最適設計，日本機

人工知能学会誌，94，506〔1994）

械学会論文集．C62−595，19／26（19g6）6）山村，小野，小林；形質の遺伝を重視した遺伝的

18）立先，辻村：遺伝的アルゴリズムによる平面多アルゴリズムに基づく巡回セールスマン問題の節機構の鍵合，日本機械学会論文集，C605銅，38

解法，人工知能学会誌，7−6，1049／1059（1992）

6／a93（1994）

7〕前川，玉置，喜多，西川：遺伝的アルゴリズムに

19）田島，中野，市川，前田：遺伝的アルゴリズムをよる巡回セールスマン問題の一解法，計測自動制用いた経路プランニング，人工知能学会誌，10−1，細学会論文集，315，598／605（1995）

84／104（1995）

8）辻岡，梶原，長粒：遺伝的アルゴリズムを用いた

20）長谷川，松本，塩野谷：GAによる肘屈折運動構造系とH瑚J御系の統合最適設計，日本機械学

時の筋力特性の同定．日本機械学会論文集，C62−

会論文集．C6卜587，62／69（1995）

596，180／186（1996）

9）稲川．荒川，山川：遺伝的アルゴリズムを用いた

21）竹田，大松：遺伝的アルゴリズムを用いたニュ

2次元構造物の最適トポロジーに関する研究，日ーロ紙幣識別技術，日本機械学会論文集，C62−59

本機械学会論文集，C6卜587，259／266〔1995）

3，135／140（1996）

10）梶原，佐々木，長船：遺伝的アルゴリズムによ22）飯間，三宮：遺伝的アルゴリズムの動作に対する構造物の位相形状最適化，日本機械学会論文集，

る致死遺伝子の影響，計測自動制御学会論文集，

C62−597，83／90〔1996）31T5，569／575（1995）

11）飯間，三宮：ある製品投入順序問題における遺23）久保臥伊達，福田：遺伝的アルゴリズムにお伝的アルゴリズムの交差規制のロバスト性．電気ける年齢構造の導入とその収束性，計測自動制御

学会論文集，115−C−10，1208／1214〔1995）

学会論文集，31−5，560／568〔19g5）

12）飯間，三宮：遺伝的アルゴリズムを用いた変形

24）市川，石井：遺伝子分布に基づく遺伝的アルゴ

フローショップ問題の解法，システム制御学会論

リズムの多様性維持，計測自動制御学会論文集，

文誌，61仇1／9（1993）

3ロー10．1242／1250〔1994）

13）梶原，大崎，香川：品質、納期、コストを考慮したGAによるスケジューリング手法に関する研究，日本機械学会論文集，C62−597，4al／436（1996）
14）古川，渡辺，玉山，嘉数：一方向走行クレーンをもつF舶Sエ場における複数AG†の運行スケジュー
リング．日本機械学会論文集．C62−595，407／412〔1996）15）藤本，逢坂：遺伝的アルゴリズムを用いたロボットマニピュレータのモデル化誤差推定，日本機械学会論文集，C61−587，417／425（1995）
16）Liu，小島：遺伝的アルゴリズムによる倒立振り子の非線形フィードバック安定化システムの最適設計法．日本機械学会論文集，C60−57了，232／