遺伝的アルゴリズム・フロイド問題
ノートブックの作成
Google Colaboratory を起動し，新規にノートブックを作成してください． ノートブックのタイトルは AI-10 とします． ノートブックの作成方法は第1回の資料を参照してください．
最初に Simple AI をインストールします． セルで下記のコマンドを実行してください．
!pip install simpleai
フロイド問題
今回は フロイド問題(Floyd Problem) を取り上げましょう．
フロイド問題
1から10までの整数を$A$と$B$の2つのグループに分ける． このとき，各グループの整数の平方根の和を求め，その差の絶対値を目的関数$g(A,B)$とする． この目的関数が最小となるグループ$A$，$B$を求めよ． 例えば，グループ$A$を奇数，グループ$B$を偶数とするとき， 目的関数の値は$1.24$となる． $$ A=\{1, 3, 5, 7, 9\} $$ $$ B=\{2, 4, 6, 8, 10\} $$ $$ f(A) = \sqrt{1} + \sqrt{3} + \sqrt{5} + \sqrt{7} + \sqrt{9} \simeq 10.61 $$ $$ f(B) = \sqrt{2} + \sqrt{4} + \sqrt{6} + \sqrt{8} + \sqrt{10} \simeq 11.85 $$ $$ g(A, B) = |f(A) - f(B)| \simeq 1.24 $$
遺伝的アルゴリズム
フロイド問題を 遺伝的アルゴリズム(Genetic Algorithm) で解きます． 遺伝的アルゴリズムは，進化的アルゴリズムの一つに分類され， 進化の仕組みを参考に開発されたアルゴリズムです． ネーミングがとてもキャッチーなこともあり，とても人気のあるアルゴリズムです． 問題の解は，数値の列で構成される 個体 として表現され，この個体を複数生成し 世代 と呼びます． この世代で，突然変異 と 交叉 と呼ばれるオペレータ（操作）を適用して， 新しい個体を生成し，次の世代とすることを繰り返します．
フロイド問題では，整数がグループAに属するとき$0$， グループBに属するとき$1$とする数値列を個体とします． 例えば，グループ$A$を奇数，グループ$B$を偶数とするとき， 個体$I_1$は下記のように表現されます．
$$ I_1 = (0, 1, 0, 1, 0, 1, 0, 1, 0, 1) $$
この他にも，グループ$A$を1〜5，グループ$B$を6〜10とするとき， 個体$I_2$は下記のように表現されます．
$$ I_2 = (0, 0, 0, 0, 0, 1, 1, 1, 1, 1) $$
突然変異 は個体に含まれる$n$番目の数値をランダムに変化させ， 新しい個体を生成する操作のことです． 例えば，個体$I_1$の5番目の数値を$0$から$1$に変化させます．
$$ (0, 1, 0, 1, 0, 1, 0, 1, 0, 1) \rightarrow (0, 1, 0, 1, 1, 1, 0, 1, 0, 1) $$
交叉 は複数の個体を繋ぎ合わせて，新しい個体を生成する操作のことです． 例えば，個体$I_1$の前半と，個体$I_2$の後半の数値を繋ぎ合わせます．
$$ (0, 1, 0, 1, 0, 1, 0, 1, 0, 1) \times (0, 0, 0, 0, 0, 1, 1, 1, 1, 1) \rightarrow (0, 1, 0, 1, 0, 1, 1, 1, 1, 1) $$
実装
クラスの定義
最初にライブラリをインポートします．
探索問題の型 を表すSearchPrblemと
遺伝的アルゴリズム を表す genetic をインポートします．
この他にも，数値計算のための Numpy と，
オブジェクトのコピーのための copy もインポートします．
import numpy as np
import copy
from simpleai.search import SearchProblem
from simpleai.search.local import genetic
次に 対象とする整数 と，初期状態 を定義します． 初期状態は，全ての整数がグループ$A$に属することとします．
NUMBERS = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
START = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
インポートしたSearchProblemクラスをオーバライドして，
フロイド問題を表す FloydProblem を定義します．
オーバライドするメソッドは，value，generate_random_state，
crossover，mutate の4種類です．
class FloydProblem(SearchProblem):
def value(self, state):
...
def generate_random_state(self):
...
def crossover(self, state1, state2):
...
def mutate(self, state):
...
value(self, state)
状態state の目的関数を算出します．
フロイド問題は目的関数を最小化する必要がありますが，
ここでは目的関数を負の値で表し，最大化を目的とした問題として扱います．
def value(self, state):
value0 = 0
value1 = 0
for n, s in zip(NUMBERS, state):
if s == 0:
value0 += np.sqrt(n)
else:
value1 += np.sqrt(n)
value = -1 * np.abs(value0 - value1) # 負の値
return value
generate_random_state(self)
ランダムに状態を生成します． 生成した乱数が0.5未満であればグループA， 0.5以上であればグループBとします．
def generate_random_state(self):
state = []
for n in NUMBERS:
if np.random.rand() < 0.5:
state.append(0)
else:
state.append(1)
return state
crossover(self, state1, state2)
状態state1と状態state2を交叉し，新しい状態を生成します．
交差する位置は乱数で決定します．
def crossover(self, state1, state2):
child = []
index = np.random.randint(0, len(state1))
for i in range(0, index):
child.append(state1[i])
for i in range(index, len(state2)):
child.append(state2[i])
return child
mutate(self, state)
状態stateを突然変異させ，新しい状態を生成します，
突然変異する位置は乱数で決定します．
def mutate(self, state):
mutated = copy.deepcopy(state)
index = np.random.randint(0, len(mutated))
if mutated[index] == 0:
mutated[index] = 1
else:
mutated[index] = 0
return mutated
解の探索
解を探索する前に，評価が最も高い状態（max_state）と評価値（max_value）を記録する変数を宣言します．
# 評価が最も高い状態と評価値
max_state = START
max_value = 0
探索中に発見した最良解の評価値を出力するため，下記のコードをvalue関数に追加します．
暫定的に評価が高い状態を更新していきます．
def value(self, state):
...
# ここから
global max_state
global max_value
if max_value < value:
max_state = state
max_value = value
print(f"max state: {max_state}({max_value:.3f})")
# ここまで追加
return value
遺伝的アルゴリズムgeneticを用いて解を探索します
ここで，population_sizeは1世代の個体の数，mutation_chanceは突然変異の確率，iterations_limitは世代交代の数です．
problem = FloydProblem(initial_state=START)
# 初期状態の評価
max_state = START
max_value = problem.value(max_state)
print(f"max state: {max_state}({max_value:.3f})")
result = genetic(problem, population_size=100, mutation_chance=0.5, iterations_limit=100)
この結果，目的関数が$-0.015$に収束します． これは，下記のグループに分けられたことを意味しています（AとBが逆の場合も同じ）．
$$ A = \{ 1, 2, 3, 4, 6, 7 \} $$
$$ B = \{ 5, 8, 9, 10 \} $$
max state: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0](-22.468)
max state: [1, 1, 1, 1, 0, 1, 0, 0, 0, 0](-5.277)
max state: [0, 1, 0, 0, 0, 0, 1, 1, 1, 1](-3.633)
max state: [1, 1, 1, 0, 1, 0, 0, 0, 0, 1](-3.379)
max state: [1, 0, 0, 1, 1, 0, 1, 1, 0, 0](-1.048)
max state: [1, 1, 0, 0, 0, 0, 1, 0, 1, 1](-0.024)
max state: [1, 0, 0, 1, 1, 0, 0, 1, 0, 1](-0.015)
max state: [0, 0, 0, 0, 1, 0, 0, 1, 1, 1](-0.015)
課題
1〜20の整数で構成されたフロイド問題を解きなさい．
Google Colaboratoryで作成した AI-10.ipynb を保存し， ノートブック（.ipynb） をダウンロードして提出しなさい． 提出の前に必ず下記の設定を行うこと．
- ノートブックの設定で「セルの出力を除外する」のチェックを外す
- ノートブックの変更内容を保存して固定