遺伝的アルゴリズムによる川渡し問題の解法

概要

論文の詳細を見る
遺伝的アルゴリズム(Gentic Algorithm:以下GA)は、生物進化の鍵である遺伝子の挙動にヒントを得た多点探索型の最適化アルゴリズムであり、様々な組み合わせ問題において比較的良好な(近似)解を短時間に見つけることで知られている。しかしながら、一般的な組み合わせ問題を解くためのGAは、遺伝子長の決まった問題に対してよりよい近似解を求めるための手法なので、遺伝子長の確定した種が環境への適応度を世代ごとに増していくのと似た方法である。ところが、「川渡し問題」は解の大きさが分からない、つまり遺伝子長が分からない問題であるため、遺伝子長一定のGAでは解けない。そこで本稿では、新種の発現にヒントを得て遺伝子長の分からない問題を解く簡単な手法を提案する。この方法は実世界において、種がある世代で突然、遺伝子長に変化を来たし、新種の発現となることで環境に適応する能力を獲得することにヒントを得ている。実際に、それを従来のGAに組み込むことで「川渡し問題」を解くことが出来ることを示す。
一般社団法人情報処理学会の論文
1995-09-20