コラム / 遺伝的アルゴリズム / 第1章

HOME 研究室概要 コラム 周辺探索 メンバー 掲示板 リンク

第1章 遺伝的アルゴリズムの考え方

 生物は双方の親の遺伝子を交換し、受け継ぐことにより進化していきます。また、生物は進化の中で、環境に適応すると生き残り、適応しないと死滅してゆきます。このような考え方を応用したのが遺伝的アルゴリズムなのです。

 このページの目次

1.1節 染色体・遺伝子の仕組み
1.2節 ダーヴィンの進化論
1.3節 コーディング

 1.1節 染色体・遺伝子の仕組み

 最近、染色体だの、遺伝子などという言葉が、テレビや新聞のニュースでよく流れています。まず、みなさんは、これらの染色体や遺伝子というものを本当に知っていますか?

 遺伝的アルゴリズムについて述べる前に、まず、これらの言葉について説明します。

『染色体』

 細胞内の核の中に存在するDNAは、通常、細い糸状をしていてこのままの状態では顕微鏡では観察できません。しかし、細胞が分裂するときに太い紐状になり、顕微鏡で観察できるようになります。この紐状の構造を「染色体」と呼びます。

『DNA』

 DNAの正式名称はデオキシリボ核酸と言います。構成としましては、塩基・リン酸・糖という3つのパーツから成り立っています。この塩基の並び順(塩基配列)こそが遺伝暗号(遺伝情報)と呼ばれ、3つ並んだ塩基で1つの蛋白質をつくる情報となります。

『遺伝子』

 DNAのところで3つの塩基で1つの蛋白質をつくると言いましたが、 その蛋白質を作り出すために働くDNAの一部分を遺伝子と言います。

 つまり、以下の関係が言えるのです。

染色体の一部がDNAであり、DNAの一部が遺伝子である。

みなさんもごっちゃになっていませんでしたか?

 1.2節 ダーウィンの進化論

 遺伝的アルゴリズムは、ダーウィンの進化論をモチーフにしています。ダーウィンの進化論を非常に乱暴に説明してやれば、だいたいこういうことになります。

「地球には、いろいろな個体がいる。そして環境に応じて、より優秀な個体だけが子孫を残すことができ、劣等な個体は淘汰される。また、残った個体は突然変異を起こす場合があって、前の世代よりも優秀になることも、逆になることもある。こうしたことを繰り返して、我々は進化してきた」

 ここで、優秀な個体というものは、「環境に適応し、 優れた生存能力をもつ者」ということができます。また、優れた者の子は、優れた親の遺伝子を受け継いでいるため、やはり優れた者である可能性が高いの事実です。

 また、遺伝子に突然変異が起こることによってより優れた者になる可能性もあります。こうして集団から、環境に適応できなかった者の遺伝子が消え去り、環境に適応した者の遺伝子が増えていくことで集団全体が進化していくのです。

(a) 環境に適応 (b) 環境に不適応

図.1: ダーウィンの進化論の考え方

 このように、優秀な個体 = 良い解答と見立て、進化の手法を用いて見つけ出そうというのが、遺伝的アルゴリズムなのです。

 1.3節 コーディング

 では、前節の染色体・遺伝子とダーウィンの進化論を、実際に遺伝的アルゴリズムでは、どのようにモデル化しているのでしょうか?

 遺伝的アルゴリズムでは、次のように置き換えて、個体集団(解集団)を進化させることによって、良好な解を探索していきます。

生物 → 個体、染色体 (解)
生存能力 → 適応度 (解の品質)
生殖行動 → 交叉
環境 → 解空間構造および広さ

 このように、遺伝的アルゴリズムでは解を染色体(遺伝子の組)という形で表現します。これは解の持つ特徴を一定のルールに従って記述したもので、このルールを決めて遺伝子を決定することをコーディングといいます。つまり、問題をどう表現をするかということになります。

 また、実際の染色体の様子は、図.2のようになっています。この 0,1,1,0,… と数字が並んでいるのが、解である遺伝子です。この0と1の組み合わせが何を表しているかは、問題によって自由に決められます。また、この遺伝子が入った枠を遺伝子座と呼びます。。

染色体のモデル

図.2: 染色体のモデル

 実際にどうコーディングを行うかは、問題によって異なるため、説明することが難しいです。そこで、第4章でナップサック問題においてのコーディングを説明するとして、次章では、その具体的な遺伝的アルゴリズムの動きを順に追っていこうと思います。

ページの上へ 上のページへ 次の章へ


企画・製作 村上・泉田研究室 HP製作委員会(2001)
ご意見・お問い合わせは、こちら までどうぞ。