遺伝的アルゴリズムとMGGモデルでナップサック問題を解く

遺伝的アルゴリズムとは

生物の進化のように、遺伝子の交叉・突然変異を通して世代を重ね、環境（解きたい問題）に適合した遺伝子（解）を得る手法。

ナップサック問題とは

泥棒が店に盗みに来たとする。
そこには、重さ・価値が様々な商品が一つずつある。
泥棒に持てる重さには限りがあるが、その条件下で盗める最大価値を求める。
という問題である。

この問題は解を単純に求めようとすると、O(2^n)の総当たりで取り組むことになる。
そのため、遺伝的アルゴリズムを用いて近似解を比較的早く求めようということである。

遺伝的アルゴリズムの流れ

問題設定

今回は30個の商品があるとする。
タプルの第一要素が重さ、第二要素が価値である。

production = [(2, 21), (3, 4), (2, 28), (4, 21), (8, 7),
              (10, 22), (10, 22), (10, 22), (7, 2), (5, 40),
              (7, 28), (9, 36), (7, 14), (8, 25), (7, 14),
              (2, 21), (8, 2), (9, 36), (5, 28), (5, 4),
              (4, 12), (8, 7), (7, 28), (2, 28), (7, 28),
              (9, 24), (5, 40), (2, 21), (3, 4), (3, 40),
              (10, 15), (7, 14), (10, 18), (10, 22), (9, 33),
              (7, 2), (3, 40), (4, 12), (9, 36), (7, 35),
              (8, 25), (9, 33), (9, 24), (7, 31), (7, 21),
              (5, 28), (7, 21), (10, 15), (8, 2), (9 ,20),]

第一世代の生成

遺伝子は各商品を持つ(=1)、持たない(=0)の2値、商品の数だけ桁を用意する。
また、遺伝子は世代ごとにn個用意する。
第一世代はランダムで値をふり、世代を重ねるごとに洗練されるようになる。

geen = [[random.randint(0, 1) for i in range(dim)] for l in range(n)]

評価

遺伝子の評価は問題ごとに変わり、うまく設定することがキモである。
例えば、今回の問題に対して、

• 持つ商品の価値の合計 （持つ商品の重さが許容以下の場合）
• 1（許容以上の場合）

と評価をする場合、持つ商品の重さの制限が厳しいとき、
いつまでも重さ以上の遺伝子から進化せず、解が得にくい

今回は、

• 持つ商品の価値の合計 （持つ商品の重さが許容以下の場合）
• 持つ商品の重さの合計 （許容以上の場合）

として、全ての遺伝子が許容以上の場合、持つ商品の軽い順で考えることにする。

def f(g):
    weight = sum([production[j][0] * g[j] for j in range(dim)])
    if weight <= w_max:
        return sum([production[j][1] * g[j] for j in range(dim)]), weight
    else:
        return 1, weight

選択

どの遺伝子を交叉させるか選択する。
今回はルーレット選択を用いる。
各遺伝子の評価結果の比を重み付き確率として、乱数による選択を行う。

def select(score):
    total = sum(score)
    threshold = random.random() * total
    sum_s = 0
    for i, s in enumerate(score):
        sum_s += s
        if sum_s > threshold:
            return i

また、エリート選択をルーレット選択と並行して取り入れる。
一番良い遺伝子をそのまま次世代に引き継がせる。
評価で取り入れた重さの合計はここで考慮に入れる。

def find_elite(score, weight=None):
    if not weight is None and len(list(set(score))) == 1:
        min_weight = 1e+6
        min_index = None
        for i, w in enumerate(weight):
            if min_weight > w:
                min_weight = w
                min_index = i
        return min_index
    else:
        max_score = -1
        max_index = None
        for i, val in enumerate(score):
            if max_score < val:
                max_score = val
                max_index = i
        return max_index

交叉

2つの遺伝子を組み合わせて、新しい遺伝子を作る。
今回は2点交叉を用いる。
2点をランダムに指定し、2点間の間を入れ替える方法。
「000|101|111」 <- 「000|010|111」<交叉> 「001|101|110」

def cross(parent1, parent2):
    length = len(parent1)
    r1 = int(math.floor(random.random() * length))
    r2 = r1 + int(math.floor(random.random() * (length - r1)))

    child = copy.deepcopy(parent1)
    child[r1:r2] = parent2[r1:r2]

    return child

突然変異

交叉だけで世代を重ねると、解は良くなるが局所的最適解に陥ることになりかねない。
そこで、低い確率で遺伝子を書き換える突然変異を導入する。

def mutate(geen):
    for i in range(n):
        for l in range(dim):
            if random.random() > cross_rate:
                geen[i][l] = 1 - geen[i][l]

    return geen

実行

以上を組み合わせて、実行する。

n = 10
w_max = 50
dim = len(production)
cross_rate = 0.99
g_num = 10000

geen = [[random.randint(0, 1) for i in range(dim)] for l in range(n)]

for stage in range(g_num):
    # 評価
    score = []
    weight = []
    for g in geen:
        s, w = f(g)
        score.append(s)
        weight.append(w)

    # 選択
    elite_index = find_elite(score, weight)
    if stage % 100 == 0:
        print("Generation: {}".format(stage))
        print(f(geen[elite_index]), geen[elite_index])

    # 交叉
    next_geen = [geen[elite_index]]
    while len(next_geen) < n:
        selected_index1 = select(score)
        selected_index2 = select(score)
        while selected_index1 == selected_index2:
            selected_index2 = select(score)
        next_geen.append(cross(geen[selected_index1], geen[selected_index2]))

    # 突然変異
    geen = mutate(next_geen)

実行結果は以下である。
見方は、
(一番良い遺伝子の評価結果(価値), 同重さ) [遺伝子]

実行結果

Generation: 0
(1, 102) [0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0]
Generation: 100
(243, 50) [1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1]
Generation: 200
(358, 47) [1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Generation: 300
(319, 50) [0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Generation: 400
(247, 50) [0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Generation: 500
(349, 48) [0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0]
Generation: 600
(394, 50) [1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0]
Generation: 700
(382, 49) [1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0]
Generation: 800
(328, 47) [0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0]
Generation: 900
(315, 48) [1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0]
Generation: 1000
(333, 49) [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0]

MGGモデル

遺伝的アルゴリズムの派生モデルであり、世代交代を局所的にすることで遺伝子の多様性を保つ手法。

実行

n = 10
w_max = 50
dim = len(production)
cross_rate = 0.99
g_num = 10000

geen = [[random.randint(0, 1) for i in range(dim)] for l in range(n)]

for stage in range(g_num):
    # ランダムに2つ選択
    selected_index1, selected_index2 = random.sample(range(n), 2)
    parent1 = geen[selected_index1]
    parent2 = geen[selected_index2]

    # 選択した2つから交叉・突然変異で複数生成
    children = [cross(parent1, parent2) for i in range(n)]
    children = mutate(children)

    # 子のスコアを計算
    score = []
    weight = []
    for c in children:
        s, w = f(c)
        score.append(s)
        weight.append(w)

    # 子のエリート
    elite_index = find_elite(score, weight=weight)
    if stage % 100 == 0:
        print("Generation: {}".format(stage))
        print(f(geen[elite_index]), geen[elite_index])

    # 子のルーレット選択
    score[elite_index] = 0
    selected_index = select(score)

    # 選択された子を親に戻す
    geen[selected_index1] = children[elite_index]
    geen[selected_index2] = children[selected_index]

実行結果

Generation: 0
(1, 131) [0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1]
Generation: 100
(164, 50) [1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1]
Generation: 200
(303, 48) [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
Generation: 300
(334, 47) [1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Generation: 400
(369, 50) [0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1]
Generation: 500
(369, 50) [1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1]
Generation: 600
(375, 49) [1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
Generation: 700
(366, 50) [1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
Generation: 800
(328, 48) [0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Generation: 900
(382, 49) [0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0]
Generation: 1000
(395, 50) [1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0]

あとがき

どちらも世代を重ねるごとに、結果が良くなっていることがわかる。
また、遺伝的アルゴリズムは世代ごとに結果に波があるように見えるが、MGGモデルはその波が比較的小さいように見える。