IV. 遺伝的アルゴリズム(Genetic Algorithm)

基本的記述(Basic Description)

進化に関するダーウィンの理論によって起こされました。 遺伝的アルゴリズムによって解かれる問題の解は進化します。

Genetic algorithms are inspired by Darwin's theory about evolution. Solution to a problem solved by genetic algorithms is evolved.

アルゴリズムは、個体群と呼ばれる解(染色体によって表現される)の集団で始まります。 １つの個体群から解が抜き取られ、新しい個体群を形成するために使われます。 これは、新しい個体群は古いものよりも良いという期待に動機付けられます。 新しく形成された解(子孫(offspring))に選ばれる解は、彼ら(解)の適合度によって選ばれます。 より適合しているものは、より再生されるチャンスがあります。

Algorithm is started with a set of solutions (represented by chromosomes) called population. Solutions from one population are taken and used to form a new population. This is motivated by a hope, that the new population will be better than the old one. Solutions which are selected to form new solutions (offspring) are selected according to their fitness - the more suitable they are the more chances they have to reproduce.

これがある状態（例えば個体群の数、最も良い解が改善される）が満足されるまで続けられます。

This is repeated until some condition (for example number of populations or improvement of the best solution) is satisfied.

サンプル(Example)
探索空間の章からすでにご存知のように、問題解決の方法は、しばしば関数の極値を探すことによって表わされます。 ここにちょうど問題が示されています。 いくつかの関数が与えられて、ＧＡは関数の最小値を探そうとします。 As you already know from the chapter about search space, problem solving can be often expressed as looking for extreme of a function. This is exactly what the problem shown here is. Some function is given and GA tries to find minimum of the function.
You can try to run genetic algorithm at the following applet by pressing button Start. Graph represents some search space and vertical lines represent solutions (points in search space). The red line is the best solution, green lines are the other ones.
Button Start starts the algorithm, Step performs one step (i.e. forming one new generation), Stop stops the algorithm and Reset resets the population.

Here is applet, but your browser does not support Java. If you want to see applets, please check browser requirements.





基本的な遺伝的アルゴリズムの概要

  1. [スタート] Generate random population of n 染色体 (suitable solutions for the problem)
  2. [適合度] 個体群内のすべての染色体xの適合度f(x) を評価する
  3. [新しい個体群] 新しい個体群が完成するまで、次のステップを繰り返すことにより新しい個体群を創り出す
    1. [選択] 適合度により個体群の中から両親となる２つの染色体を選び出す(良い適合度になるにつれ、選ばれるチャンスは広がります)
    2. [交叉] 交叉確率に従って、新しい子孫（子供）を作り出す親を交叉させます。 もし交叉が行われない場合には、親がそっくりコピーされます。
    3. [突然変異] 突然変異確率に従って、新しい子孫のすべての位置（染色体上の位置）にたいして、突然変異を行います
    4. [Accepting] 新しい子孫を新しい個体群にいれる
  4. [置き換え] アルゴリズムの次の実行のために、新しく生成された個体群を使います
  5. [テスト] 最終条件が満足したら、終了(stop)します、そして現在の個体群の最良の解を返します。
  6. [ループ] 2へ戻る

  1. [Start] Generate random population of n chromosomes (suitable solutions for the problem)
  2. [Fitness] Evaluate the fitness f(x) of each chromosome x in the population
  3. [New population] Create a new population by repeating following steps until the new population is complete
    1. [Selection] Select two parent chromosomes from a population according to their fitness (the better fitness, the bigger chance to be selected)
    2. [Crossover] With a crossover probability cross over the parents to form a new offspring (children). If no crossover was performed, offspring is an exact copy of parents.
    3. [Mutation] With a mutation probability mutate new offspring at each locus (position in chromosome).
    4. [Accepting] Place new offspring in a new population
  4. [Replace] Use new generated population for a further run of algorithm
  5. [Test] If the end condition is satisfied, stop, and return the best solution in current population
  6. [Loop] Go to step 2




Some Comments

見てわかるように、基本的なＧＡの概要は非常に一般的です。 様々な問題について違った改良

As you can see, the outline of Basic GA is very general. There are many things that can be implemented differently in various problems.

はじめの疑問は、どんなタイプのエンコードを選んで、染色体を作ればいいかということです。 これは、交叉、突然変異という、GAの２つの基本的なオペレータにも関係してきます。 交叉と突然変異については次の章で紹介します。

First question is how to create chromosomes, what type of encoding choose. With this is connected crossover and mutation, the two basic operators of GA. Encoding, crossover and mutation are introduced in next chapter.

次の疑問は、どのように交叉のための親を選択するかということです。 これはいろいろな方法で行うことができますが、主な考え方は他のに比べて良い両親を選ぶということです（他のより良い両親は、良い子孫を残すという希望がこめられています）。 また、あなたは新しい子孫だけで新しい個体群を作ると、現在の個体群のもっともよい染色体が失われてしまうと思うかもしれません。 これは本当です、エリート主義と呼ばれるものがしばしば使われます。 これは、少なくとも１つの最も良い解は、なんの変更もなしに新しい個体群にコピーされます。 ですから、見つかったもっともよい解は実行の最後まで生き残ります。

Next questions is how to select parents for crossover. This can be done in many ways, but the main idea is to select the better parents (in hope that the better parents will produce better offspring). Also you may think, that making new population only by new offspring can cause lost of the best chromosome from the last population. This is true, so so called elitism is often used. This means, that at least one best solution is copied without changes to a new population, so the best solution found can survive to end of run.

いくつかの関係した疑問は、後で議論します

Some of the concerning questions will be discussed later.

ひょっとしたら、あなたは何故遺伝的アルゴリズムが機能するのか不思議におもうかもしれません。 それは、部分的にはスキーマ理論(Holland)によって説明することができます、 しかしながらこの定理は、最近非難にさらされています。 もしもっと知りたいのであればother resources.を見てください。

Maybe you are wandering, why genetic algorithms do work. It can be partially explained by Schema Theorem (Holland), however, this theorem has been criticised in recent time. If you want to know more, check other resources.


prev             next

(c) Marek Obitko, 1998
Japanese translation (c) Ishii Manabu, 1999 - Terms of use