概要
↑の最後で記述したやってみたい仕様を取り入れた。
- 親候補を選別時に同一個体が重複して親配列に格納されないようにする
- エリート個体が新世代を上書きしないようにする
- 品物の重さが重複しないようにする
(最初の遺伝子配列設定では品物のインデックスも重複しないようにした。結果には大きく響かないと思われるが)
実装
- ソースコード
import random
# ===== 設定 =====
# 全品物数
ITEM_MAX = 15
# 個体の遺伝子長（選ぶ品物の数）
GENE_LENGTH = 10
# 全個体数(人口)
POPULATION_SIZE = 100
# 親として選別する個体数
PARENTS_SIZE = 80
# 何世代先まで子孫を残すか
GENERATIONS = 200
# リュックサックの耐久力の最大値[kg]
WEIGHT_MAX = 300
# 荷物の重さの最大値[kg]
ITEM_WEIGHT_MAX = 30
# 交配率
CROSS_RATE = 0.95
# 突然変異が発生する確率
MUTA_RATE = 0.05
##### 関数の定義 #####
# ===== (f-1) 初期個体群を生成 =====
def createIndividual():
# ランダムに品物番号を選ぶ
# 遺伝子配列に格納するのは品物の番号(配列のindex)であり品物自体の重さではない
return random.sample(range(0, ITEM_MAX), GENE_LENGTH)
# ===== (f-2) 評価関数 =====
# 配列"individual"の要素番号g番目の数値のインデックスの重さを抽出して足していく
def fitness(individual):
total = sum(weights[g] for g in individual)
return total if total <= WEIGHT_MAX else 0
# ===== (f-3) ルーレット選択 =====
def selectPopulation(pop):
# 各個体の評価点を要素とした配列を生成する
fits = [fitness(ind) for ind in pop]
# 配列の合計を計算する
total_fit = sum(fits)
# 全個体の評価点が0ならば完全にランダムでPARENTS_SIZE個の個体を選ぶ(重複なし)
if total_fit == 0:
selected_parents = [random.sample(pop, PARENTS_SIZE)]
return selected_parents
# 適応度比例選択
# pop(population)からfit(各個体の評価点)に応じてPARENTS_SIZE個の個体を選びそれらを親とする
# 評価点が高いほど選ばれやすい
# 同じ個体が複数回2次元配列selected_parentsに格納されるのを防ぐ
selected_parents = []
while len(selected_parents) < PARENTS_SIZE:
chosen = random.choices(pop, weights=fits, k=1)[0]
if chosen not in selected_parents:
selected_parents.append(chosen)
return selected_parents
# ===== (f-4) 一点交叉 =====
# 親2人の遺伝子を掛け合わせて子を生成
def crossover(parent1, parent2):
point = random.randint(1, GENE_LENGTH-1)
child1 = parent1[:point] + parent2[point:]
child2 = parent2[:point] + parent1[point:]
return child1, child2
# ===== (f-5) 突然変異 =====
# 個体の遺伝子配列indのどれかの要素を低確率で変異させる
def mutate(ind):
for i in range(GENE_LENGTH):
if random.random() < MUTA_RATE:
ind[i] = random.randint(0, ITEM_MAX - 1)
##### 関数の定義ここまで #####
# (0)
# ITEM_MAX個の品物の重さを乱数で設定する
# 重さに関して重複しないように選ぶ
# (rangeは終了値を含まないためITEM_WEIGHT_MAX+1を指定)
weights = random.sample(range(1, ITEM_WEIGHT_MAX+1), ITEM_MAX)
print("weight of items:", weights)
# (1)
# POPULATION_SIZE個の遺伝子配列を格納する配列(2次元配列)を作成する
# (f-1)を呼び出す
population = [createIndividual() for _ in range(POPULATION_SIZE)]
# 初代の遺伝子配列を一部表示する
for i, ind in enumerate(population):
if i+1 == 1 or (i+1)%10 == 0:
print(f"No{i+1}, items: {ind}")
# ===== GA ループ =====
for gen in range(GENERATIONS):
# (2)
# 子孫を残す個体をPARENTS_SIZE個選別する
# (f-3)を呼び出す
selected = selectPopulation(population)
# (4)
# 選別された個体をランダムにシャッフルする
# この後の交配では配列のインデックス0から2個ずつ親として交叉させるため結果的にペアがランダムとなる
random.shuffle(selected)
# 交配
# next_generationの最後にエリート個体を格納するために(POPULATION_SIZE-1)個の子を生成する
next_generation = []
while len(next_generation) < POPULATION_SIZE-1:
# i番目と(i+1)番目の親との間に子を作る
# PARENTS_SIZE=80ならばi = 1, 3, 5, ..., 75, 77, 79, 1, 3, 5, ...となる
i = len(next_generation)%PARENTS_SIZE
if random.random() < CROSS_RATE:
# あと何人子を残すかを計算する
remaining = POPULATION_SIZE - len(next_generation)
# 作り出したい子供が残り1人のとき
if remaining == 1:
child1, child2 = crossover(selected[-1], selected[0])
next_generation.append(child1) # 1人だけ追加
# iがselectedの最後のインデックスのときselected(親配列)の先頭と末尾を代入
elif i >= PARENTS_SIZE-1:
child1, child2 = crossover(selected[-1], selected[0])
next_generation.extend([child1, child2]) # # 2人追加
# 上記2つの条件がなければ親配列を順番に交叉させる
else:
child1, child2 = crossover(selected[i], selected[i+1])
next_generation.extend([child1, child2]) # 2人追加
# (5)
# 突然変異
# (f-5)を呼び出す
for ind in next_generation:
mutate(ind)
# (3)
# エリート保存（最良個体を次世代にコピー）
best_ind = max(population, key=fitness)
next_generation[-1] = best_ind[:]
# (6)
# 世代更新
population = next_generation
# 10世代ごとに表示
if gen % 10 == 0:
best_ind = max(population, key=fitness)
best_fit = fitness(best_ind)
print(f"Generation {gen+1}, best score: {best_fit}, best items: {best_ind}")
# 最終結果を表示
best_ind = max(population, key=fitness)
best_fit = fitness(best_ind)
print(f"Generation {GENERATIONS}, best score: {best_fit}, best items: {best_ind}")
結果
- 結果自体は前回と特に大きく変わらない
weight of items: [28, 9, 12, 14, 30, 20, 5, 24, 11, 2, 22, 17, 8, 1, 23]
- 初代の遺伝子配列の一部
No1, items: [10, 13, 4, 2, 9, 14, 5, 7, 3, 8]
No10, items: [2, 14, 8, 7, 1, 4, 11, 13, 10, 3]
No20, items: [12, 9, 14, 5, 13, 10, 2, 3, 6, 11]
No30, items: [13, 5, 6, 0, 4, 9, 12, 14, 3, 8]
No40, items: [10, 1, 9, 4, 13, 0, 8, 3, 12, 7]
No50, items: [9, 8, 14, 5, 1, 4, 10, 6, 11, 13]
No60, items: [0, 6, 11, 9, 5, 13, 7, 8, 1, 12]
No70, items: [3, 8, 9, 13, 2, 1, 10, 0, 4, 11]
No80, items: [10, 2, 9, 1, 0, 11, 12, 6, 8, 3]
No90, items: [14, 9, 2, 0, 8, 3, 1, 10, 12, 11]
No100, items: [0, 7, 12, 1, 8, 3, 11, 13, 14, 4]
Generation 1, best score: 219, best items: [0, 6, 10, 5, 1, 4, 4, 0, 7, 14]
Generation 11, best score: 253, best items: [10, 0, 7, 7, 4, 4, 7, 14, 5, 0]
Generation 21, best score: 266, best items: [10, 0, 4, 4, 0, 4, 4, 14, 11, 0]
Generation 31, best score: 272, best items: [10, 0, 4, 4, 0, 4, 4, 14, 0, 14]
Generation 41, best score: 283, best items: [0, 0, 4, 4, 0, 4, 0, 14, 4, 0]
Generation 51, best score: 283, best items: [0, 0, 4, 4, 0, 4, 0, 14, 4, 0]
Generation 61, best score: 283, best items: [0, 0, 4, 4, 0, 4, 0, 14, 4, 0]
Generation 71, best score: 287, best items: [14, 0, 4, 4, 0, 4, 0, 4, 4, 4]
Generation 81, best score: 287, best items: [14, 0, 4, 4, 0, 4, 0, 4, 4, 4]
Generation 91, best score: 287, best items: [14, 0, 4, 4, 0, 4, 0, 4, 4, 4]
Generation 101, best score: 287, best items: [14, 0, 4, 4, 0, 4, 0, 4, 4, 4]
Generation 111, best score: 288, best items: [7, 0, 4, 4, 0, 4, 0, 4, 4, 4]
Generation 121, best score: 288, best items: [7, 0, 4, 4, 0, 4, 0, 4, 4, 4]
Generation 131, best score: 288, best items: [7, 0, 4, 4, 0, 4, 0, 4, 4, 4]
Generation 141, best score: 289, best items: [14, 4, 4, 4, 0, 4, 0, 4, 4, 4]
Generation 151, best score: 290, best items: [7, 4, 4, 4, 0, 4, 0, 4, 4, 4]
Generation 161, best score: 290, best items: [4, 4, 7, 4, 0, 4, 0, 4, 4, 4]
Generation 171, best score: 290, best items: [4, 4, 7, 4, 0, 4, 0, 4, 4, 4]
Generation 181, best score: 290, best items: [4, 4, 7, 4, 0, 4, 0, 4, 4, 4]
Generation 191, best score: 290, best items: [4, 4, 7, 4, 0, 4, 0, 4, 4, 4]
Generation 200, best score: 290, best items: [4, 4, 7, 4, 0, 4, 0, 4, 4, 4]