👾
[python] 遺伝的アルゴリズムを実装してみた
pythonで遺伝的アルゴリズムを実装してみました。
遺伝的アルゴリズムとは？
アルゴリズムの概要
生物の遺伝を模して作られたアルゴリズム。
現世代で評価の高い個体が次世代に残りやすくし、世代を進めると賢い個体ができる。
- 現世代として、複数の性質をもつ個体を複数用意する。（たとえば、「010」「111」「000」）
- 個体を評価し、点数をつける（「010」1点、「111」3点、「000」0点）
- ある確率で３つのどれかを行い、次世代とする。評価の高いものが選ばれやすくする。
a. 【SELECTION】個体をひとつ選択してそのままコピーする。
b. 【CROSSOVER】個体を２つ選択し、交叉する。(「010」「111」から「011」が生まれる等)
c. 【MUTATION】個体をひとつ選択して突然変異を起こす。（「010」が「110」になる） - このやりとりを数回繰り返し、最も評価点の高いものを採用する。
コード
やっていること
1. 初期値や繰り返しの世代数、次世代個体の作り方の確立等を指定する
2. 現世代を評価する
各個体は[0,1]からなるリストで成り立っていて、リストの1の数を評価点としています。
3. 次世代を生成する
評価の高い個体が選ばれやすくした確率分布で、
現世代から、SELECTION（選択）, CROSSOVER（交叉）, MUTATION（突然変異）のいずれかを行う。
4. 世代交代し、2,3を繰り返す。
5. 最終世代と、その最高評価の個体を出力
出力
試行回数を50回にすると、最高の解を得ることができました。（[1,1,1,1,1]が最高）
$ python3 main.py
...
Selected operation: MUTATION
Selected operation: CROSSOVER
Selected operation: SELECTION
Selected operation: SELECTION
Selected operation: SELECTION
Individual: [0, 1, 1, 1, 1] Evaluation: 4
Individual: [1, 1, 1, 1, 1] Evaluation: 5
Individual: [1, 1, 1, 1, 1] Evaluation: 5
Individual: [1, 0, 1, 1, 1] Evaluation: 4
Individual: [1, 1, 1, 1, 1] Evaluation: 5
Selected operation: MUTATION
Selected operation: SELECTION
Selected operation: SELECTION
Selected operation: SELECTION
Selected operation: CROSSOVER
Individual: [1, 0, 1, 1, 0] Evaluation: 3
Individual: [1, 1, 1, 1, 1] Evaluation: 5
Individual: [1, 1, 1, 1, 1] Evaluation: 5
Individual: [0, 1, 1, 1, 1] Evaluation: 4
Individual: [1, 1, 1, 1, 1] Evaluation: 5
Selected operation: SELECTION
Selected operation: CROSSOVER
Selected operation: CROSSOVER
Selected operation: MUTATION
Selected operation: CROSSOVER
Individual: [1, 1, 0, 1, 1] Evaluation: 4
Individual: [1, 1, 1, 1, 1] Evaluation: 5
Individual: [1, 1, 1, 1, 1] Evaluation: 5
Individual: [1, 1, 0, 1, 1] Evaluation: 4
Individual: [0, 1, 1, 1, 1] Evaluation: 4
Strongest individual:
Individual: [1, 1, 1, 1, 1] Evaluation: 5
Discussion