本記事の読者対象は
・人工知能っていうのはアバウトに知ってるけどよくわからない
・そもそも人工知能ってそこまで価値なくね？
・やろうと思ったが数式を見て萎えて辞めた
・人工知能をやりたいがどうすればいいかわからない
・人工知能系のソースはムズすぎて読めない
みたいな人を対象にしています。
遺伝的アルゴリズムは人工知能の一部として定義されていますが、
私からすると感覚的に二分探索のアルゴリズムを書いてる感覚です。
遺伝的アルゴリズムもアルゴリズムなので概念を理解すれば実装は簡単です。
本記事は実践的なので、そもそも遺伝的アルゴリズムを知らない人は対象外です。
ですが、安心してください。下記の神スライドを全部読んでアバウトに理解すればOKです。
(このスライドは神レベルで超効率的に遺伝的アルゴリズムを学べます。本にして売ってください)
遺伝的アルゴリズム（Genetic Algorithm）を始めよう！
どれぐらい理解できればいいかはは下記をざっくり理解できればOKです
また、わからない単語は基本的にスライドに書いてあります。
本プログラムの大まかな流れ(少し違う部分あり)
1 解を表現する符号を決定する
2 N個のランダムな現行遺伝子個体を作成
3 次世代遺伝子個体集団を格納する変数生成
4 評価関数を用いて現行遺伝子を評価計算
5 現行世代から二つの遺伝子を選択
6 選択遺伝子を交叉させ子孫を生成
7 生成した子孫に対して突然変異を行う
8 次世代個体数をN個まで5-6を繰り返す
9 次世代集団を現行世代に移行、収束するまで繰り返す
10 もっとも評価が高い遺伝子を出力する
では早速入ります
概要
本記事では遺伝的アルゴリズム(以下GA)を用いてOneMax問題を解いていきます。
また、今回はGAに関して外部のライブラリは使用しません。二分探索をする時もライブラリなんて使いませんよね？
使用するimportは下記に表します
・計算の誤差なるべくなくすためにDecimal
・ランダムな値を取得するためにRandom
・計算しやすいように、遺伝子情報とその遺伝子の評価値を格納するClass。GeneticAlgorithm(一番最初に自分で作ります)
GeneticAlgorithmは本記事筆頭者がJavaチックなコーディングが好きなので作ります。（別のやり方でもOK)
OneMax問題とは
list = [0,1,0,0,0,1,0,0,0,1,0,1,1,0,1]
のようにランダムに配置された配列を進化的計算(GA)で
list = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
のように全ての配列値を1に近づける問題です。
本記事達成目標
下記と同様の結果が得られることが目標です。
1が最適解です。各種世代での評価値の最小値最大値平均値を出力してます。
-----第1世代の結果-----
Min:0.36
Max:0.63
Avg:0.4999
-----第2世代の結果-----
Min:0.46
Max:0.65
Avg:0.5653
-----第3世代の結果-----
Min:0.54
Max:0.67
Avg:0.6098
-----第4世代の結果-----
...
...
-----第39世代の結果-----
Min:0.84
Max:0.93
Avg:0.9247
-----第40世代の結果-----
Min:0.85
Max:0.94
Avg:0.9256
最も優れた個体は[1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
符号 選択 交叉 突然変異 世代交代 各種定義
それぞれのアルゴリズムの詳細です
符号:バイナリエンコーディング
0と1で遺伝子を表現する
選択:エリート主義
もっとも適用度の高い個体を選択する
交叉:二点交叉
遺伝子の一部にランダムな二点を選択し、
その間にある遺伝子を入れ替える
変異:置換
遺伝子を対立する数値に置き換える
0.1%~1% 高くても数%
低すぎると局所収束。高すぎると収束しない。
世代:定常状態モデル
生成した子孫を適用度の低い個体と入れ替える。
数値的設定
遺伝子の長さ:100
遺伝子を持つ個体の集団:100
その時点で最適解にエリート数:20
エリートを交叉させて出す子孫数:40
世代交代時内訳:エリート遺伝子20。子孫遺伝子40。エリート以外の現行遺伝子40。計100
個体突然変異率:1%
遺伝子突然変異:1%(遺伝子一つの対しての突然変異率)
世代交代数:40
コーディング
途中抽象化の仕方がカバガバだったり、一貫性のないコードであったりします。ご了承ください。
GeneticAlgorithm.py
まずはじめにGeneticAlgorithm.pyを作成し、genomClassを作成します。
class genom:
genom_list = None
evaluation = None
def __init__(self, genom_list, evaluation):
self.genom_list = genom_list
self.evaluation = evaluation
def getGenom(self):
return self.genom_list
def getEvaluation(self):
return self.evaluation
def setGenom(self, genom_list):
self.genom_list = genom_list
def setEvaluation(self, evaluation):
self.evaluation = evaluation
このClassをインスタンス変数として遺伝子情報と評価値を記憶させます。
setで値を代入し、getで値をもらいます。
main.py
定数
各種定数です
# 遺伝子情報の長さ
GENOM_LENGTH = 100
# 遺伝子集団の大きさ
MAX_GENOM_LIST = 100
# 遺伝子選択数
SELECT_GENOM = 20
# 個体突然変異確率 @GitHubに上げたコードでは0.1の10%になってます
INDIVIDUAL_MUTATION = 0.01
# 遺伝子突然変異確率 @GitHubに上げたコードでは0.1の10%になってます
GENOM_MUTATION = 0.01
# 繰り返す世代数
MAX_GENERATION = 40
各種関数
関数内部での詳しい説明はコメントアウトにて記述しています。
create_genom
引数で指定された数だけ遺伝子をランダムに生成し、genomClassで返します
evaluation
個体から遺伝子情報を取り出して、評価します
select
個体集団から引数で指定された一定の数だけのエリート集団を返します
crossover
引数から二つの個体を取得し、それから生成した子孫二つを配列に入れて返します
next_generation_gene_create
世代交代をします。現在の集団、エリート集団、子孫集団から作成します
mutation
引数から得られた確率をもとに突然変異処理をします。
def create_genom(length):
def create_genom(length):
"""
引数で指定された桁のランダムな遺伝子情報を生成、格納したgenomClassで返します。
:param length: 遺伝子情報の長さ
:return: 生成した個体集団genomClass
"""
genome_list = []
for i in range(length):
genome_list.append(random.randint(0, 1))
return ga.genom(genome_list, 0)
def evaluation(ga):
def evaluation(ga):
"""評価関数です。今回は全ての遺伝子が1となれば最適解となるので、
合計して遺伝子と同じ長さの数となった場合を1として0.00~1.00で評価します
:param ga: 評価を行うgenomClass
:return: 評価処理をしたgenomClassを返す
"""
genom_total = sum(ga.getGenom())
return Decimal(genom_total) / Decimal(len(ga.getGenom()))
def select(ga, elite):
def select(ga, elite_length):
"""選択関数です。エリート選択を行います
評価が高い順番にソートを行った後、一定以上
:param ga: 選択を行うgenomClassの配列
:param elite_length: 選択するエリートの数
:return: 選択処理をした一定のエリート、genomClassを返す
"""
# 現行世代個体集団の評価を高い順番にソートする
sort_result = sorted(ga, reverse=True, key=lambda u: u.evaluation)
# 一定の上位を抽出する
result = [sort_result.pop(0) for i in range(elite_length)]
return result
def crossover(ga_one, ga_second):
def crossover(ga_one, ga_second):
"""交叉関数です。二点交叉を行います。
:param ga: 交叉させるgenomClassの配列
:param ga_one: 一つ目の個体
:param ga_second: 二つ目の個体
:return: 二つの子孫genomClassを格納したリスト返す
"""
# 子孫を格納するリストを生成します
genom_list = []
# 入れ替える二点の点を設定します→[10:25]→10から25まで
cross_one = random.randint(0, GENOM_LENGTH)
cross_second = random.randint(cross_one, GENOM_LENGTH)
# 遺伝子を取り出します
one = ga_one.getGenom()
second = ga_second.getGenom()
# 交叉させます
progeny_one = one[:cross_one] + second[cross_one:cross_second] + one[cross_second:]
progeny_second = second[:cross_one] + one[cross_one:cross_second] + second[cross_second:]
# genomClassインスタンスを生成して子孫をリストに格納する
genom_list.append(ga.genom(progeny_one, 0))
genom_list.append(ga.genom(progeny_second, 0))
return genom_list
def next_generation_gene_create(ga, ga_elite, ga_progeny):
def next_generation_gene_create(ga, ga_elite, ga_progeny):
"""
世代交代処理を行います
:param ga: 現行世代個体集団
:param ga_elite: 現行世代エリート集団
:param ga_progeny: 現行世代子孫集団
:return: 次世代個体集団
"""
# 現行世代個体集団の評価を低い順番にソートする
next_generation_geno = sorted(ga, reverse=False, key=lambda u: u.evaluation)
# 追加するエリート集団と子孫集団の合計ぶんを取り除く
for i in range(0, len(ga_elite) + len(ga_progeny)):
next_generation_geno.pop(0)
# エリート集団と子孫集団を次世代集団を次世代へ追加します
next_generation_geno.extend(ga_elite)
next_generation_geno.extend(ga_progeny)
return next_generation_geno
def mutation(ga, individual_mutation, genom_mutation):
def mutation(ga, individual_mutation, genom_mutation):
"""突然変異関数です。
:param ga: 突然変異をさせるgenomClass
:param individual_mutation: 固定に対する突然変異確率
:param genom_mutation: 遺伝子一つ一つに対する突然変異確率
:return: 突然変異処理をしたgenomClassを返す"""
ga_list = []
for i in ga:
# 個体に対して一定の確率で突然変異が起きる
if individual_mutation > (random.randint(0, 100) / Decimal(100)):
genom_list = []
for i_ in i.getGenom():
# 個体の遺伝子情報一つ一つに対して突然変異がおこる
if genom_mutation > (random.randint(0, 100) / Decimal(100)):
genom_list.append(random.randint(0, 1))
else:
genom_list.append(i_)
i.setGenom(genom_list)
ga_list.append(i)
else:
ga_list.append(i)
return ga_list
if name == 'main':
if __name__ == '__main__':
# 一番最初の現行世代個体集団を生成します。
current_generation_individual_group = []
for i in range(MAX_GENOM_LIST):
current_generation_individual_group.append(create_genom(GENOM_LENGTH))
for count_ in range(1, MAX_GENERATION + 1):
# 現行世代個体集団の遺伝子を評価し、genomClassに代入します
for i in range(MAX_GENOM_LIST):
evaluation_result = evaluation(current_generation_individual_group[i])
current_generation_individual_group[i].setEvaluation(evaluation_result)
# エリート個体を選択します
elite_genes = select(current_generation_individual_group,SELECT_GENOM)
# エリート遺伝子を交叉させ、リストに格納します
progeny_gene = []
for i in range(0, SELECT_GENOM):
progeny_gene.extend(crossover(elite_genes[i - 1], elite_genes[i]))
# 次世代個体集団を現行世代、エリート集団、子孫集団から作成します
next_generation_individual_group = next_generation_gene_create(current_generation_individual_group,
elite_genes, progeny_gene)
# 次世代個体集団全ての個体に突然変異を施します。
next_generation_individual_group = mutation(next_generation_individual_group,INDIVIDUAL_MUTATION,GENOM_MUTATION)
# 1世代の進化的計算終了。評価に移ります
# 各個体適用度を配列化します。
fits = [i.getEvaluation() for i in current_generation_individual_group]
# 進化結果を評価します
min_ = min(fits)
max_ = max(fits)
avg_ = sum(fits) / Decimal(len(fits))
# 現行世代の進化結果を出力します
print "-----第{}世代の結果-----".format(count_)
print " Min:{}".format(min_)
print " Max:{}".format(max_)
print " Avg:{}".format(avg_)
# 現行世代と次世代を入れ替えます
current_generation_individual_group = next_generation_individual_group
# 最終結果出力
print "最も優れた個体は{}".format(elite_genes[0].getGenom())
実行結果
-----第1世代の結果-----
Min:0.36
Max:0.63
Avg:0.4999
-----第2世代の結果-----
Min:0.46
Max:0.65
Avg:0.5653
-----第3世代の結果-----
Min:0.54
Max:0.67
Avg:0.6098
-----第4世代の結果-----
...
...
-----第39世代の結果-----
Min:0.84
Max:0.93
Avg:0.9247
-----第40世代の結果-----
Min:0.85
Max:0.94
Avg:0.9256
最も優れた個体は[1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
最初の個体の最大適用度は0.63でありますが、最後は0.94にまで解を近づけることができてます
要するに1の数が最初は63/100だったのを94/100にまで持って行けました。
何回か実行してると100に行くかもしれません
実際にやってみよう
上記をコピペしても実行できますが面倒なのでGitからもってきましょう
GitHubからCloneしてとりま実行してみましょう
$ git clone https://github.com/Azunyan1111/OneMax.git
>>Cloning into 'OneMax'...
>>remote: Counting objects: 5, done.
>>remote: Compressing objects: 100% (4/4), done.
>>remote: Total 5 (delta 0), reused 5 (delta 0), pack-reused 0
>>Unpacking objects: 100% (5/5), done.
$ pwd
>>/Users/admin/Desktop
$ cd OneMax/
$ pwd
>>/Users/admin/Desktop/OneMax
$ ls
>>GeneticAlgorithm.py README.md main.py
$ python main.py
main.pyを実行することで処理が始まります
こちらもどうぞ
Python Webスクレイピング 実践入門
Python Webスクレイピング テクニック集「取得できない値は無い」JavaScript対応
【毎秒1万リクエスト!?】Go言語で始める爆速Webスクレイピング【Golang】