遺伝的アルゴリズムで処理が終了しません．

実現したいこと

遺伝的アルゴリズムにて5つの制約条件を必ず守るスケジュールの自動作成を行いたい．

▲▲機能を動作するようにする

前提

作成するシフトは14人のスタッフ10日分です．
割り当てられるシフトは以下の通りです．
SHIFTS = ['N', 'NS', 'NB', 'D', 'I', 'G', 'Z', 'FN']

発生している問題・エラーメッセージ

満たすべき制約条件5つを必ず守るようにすると計算時間が多いせいかなかなか実行が終了しません．
交叉と突然変異の箇所がおかしいのでしょうか．

該当のソースコード

python
1import random
2
3# スケジュールの制約条件を定義
4REQUIRED_STAFF_COUNT = 7
5FN_STAFF_COUNT_MIN = 1
6FN_STAFF_COUNT_MAX = 2
7NS_STAFF_COUNT_MIN = 1
8NS_STAFF_COUNT_MAX = 2
9
10# シフトの候補
11SHIFTS = ['N', 'NS', 'NB', 'D', 'I', 'G', 'Z', 'FN']
12
13# 遺伝的アルゴリズムのパラメータ
14POPULATION_SIZE = 100
15GENERATIONS = 10000
16MUTATION_RATE = 0.2
17
18
19class Schedule:
20    def __init__(self, genes=None):
21        if genes is None:
22            self.genes = [random.choice(SHIFTS) for _ in range(10 * 14)]
23
24        else:
25            self.genes = genes
26
27    def calculate_fitness(self):
28        # 適応度関数を定義する
29        # 制約条件を元にスケジュールの優れた程度を評価する
30        fitness = 0
31
32        # 1. 制約条件1: 毎日，z以外のシフトが割り当てられるスタッフが7名以上いるか
33        staff_counts = {shift: 0 for shift in SHIFTS}
34        for i in range(14):
35            staff_shifts = self.genes[i * 10: (i + 1) * 10]
36            for shift in staff_shifts:
37                staff_counts[shift] += 1
38
39        if staff_counts['Z'] >= REQUIRED_STAFF_COUNT:
40            print("ok_1")
41            fitness += 1
42            print("fitness" + str(fitness))
43        else:
44          fitness = 0
45
46        # 2. 制約条件2: 7の倍数の日にちから連続して3日間FNが割り当てられるスタッフが1人以上2人以下か
47        fn_days = [i for i in range(6, 10 * 14, 7)]  # 7の倍数の日にち
48        fn_staff_count = sum(1 for i in fn_days if self.genes[i:i + 3] == ['FN', 'FN', 'FN'])
49        if FN_STAFF_COUNT_MIN <= fn_staff_count <= FN_STAFF_COUNT_MAX:
50            print("ok_2")
51            fitness += 1
52            print("fitness_2" + str(fitness))
53        else:
54            fitness = 0
55            print("fitness_2" + str(fitness))
56
57        # 5. 制約条件5: Nは6の倍数の日にちに割り当てられなければならない
58        n_days = [i for i in range(0, 10 * 14, 6)]  # 6の倍数の日にち
59        for i in n_days:
60            if self.genes[i] != 'N':
61                break
62        else:
63            
64            print("ok_5")
65            fitness += 1
66
67
68
69
70
71        # 3. 制約条件3: 7の倍数の日にちから連続して2日間NSが割り当てられるスタッフが1人以上2人以下か
72        ns_days = [i for i in range(6, 10 * 14, 7)]  # 7の倍数の日にち
73        ns_staff_count = sum(1 for i in ns_days if self.genes[i:i + 2] == ['NS', 'NS'])
74        if NS_STAFF_COUNT_MIN <= ns_staff_count <= NS_STAFF_COUNT_MAX:
75            print("ok_3")
76            fitness += 1
77
78        # 4. 制約条件4: Nが割り当てられたシフトの次の日は必ずzでなければならない
79        for i in range(len(self.genes) - 1):
80            if self.genes[i] == 'N' and self.genes[i + 1] != 'Z':
81                break
82        else:
83            print("ok_4")
84            fitness += 1
85
86
87        return fitness
88
89
90    def crossover(self, other):
91        # 交叉の実装
92        # 2つのスケジュールを組み合わせて新しいスケジュールを生成する
93        crossover_point = random.randint(1, len(self.genes) - 1)
94        child1_genes = self.genes[:crossover_point] + other.genes[crossover_point:]
95        child2_genes = other.genes[:crossover_point] + self.genes[crossover_point:]
96        print(child1_genes)
97        return child1_genes, child2_genes
98
99
100    def mutate(self):
101        # 突然変異の実装
102        # スケジュールの一部を変更する
103        for i in range(len(self.genes)):
104            if random.random() < MUTATION_RATE:
105                self.genes[i] = random.choice(SHIFTS)
106
107
108
109if __name__ == "__main__":
110    # 初期のランダムなスケジュールを生成
111    best_schedule = Schedule()
112    best_fitness = best_schedule.calculate_fitness()
113    print("Initial Best Fitness:", best_fitness)
114
115    generation = 0
116    while best_fitness < 5:
117        generation += 1
118
119        # 新しい世代のスケジュールを生成
120        new_schedule = Schedule()
121        
122        # 交叉を行う別のスケジュールを生成
123        other_schedule = Schedule()
124        
125        # 交叉を実行して新しい子スケジュールを取得
126        child1_genes, child2_genes = new_schedule.crossover(other_schedule)
127        child1 = Schedule(child1_genes)
128        child2 = Schedule(child2_genes)
129        
130        # 突然変異を実行
131        child1.mutate()
132        child2.mutate()
133
134        # 新しいスケジュールの適応度を計算
135        fitness_child1 = child1.calculate_fitness()
136        fitness_child2 = child2.calculate_fitness()
137
138        # 子スケジュールのうち適応度の高い方を選択
139        if fitness_child1 > fitness_child2:
140            new_fitness = fitness_child1
141            new_schedule = child1
142        else:
143            new_fitness = fitness_child2
144            new_schedule = child2
145
146        # 新しいスケジュールがより優れていれば更新
147        if new_fitness > best_fitness:
148            best_schedule = new_schedule
149            best_fitness = new_fitness
150            print(f"Generation {generation}, Best Fitness: {best_fitness}")
151
152    # 最良のスケジュールを表示
153    print("\nFinal Best Schedule:")
154    for i in range(14):
155        staff_shifts = best_schedule.genes[i * 10: (i + 1) * 10]
156        print(f"Staff {i + 1} shifts: {' '.join(staff_shifts)}")
157

補足情報（FW/ツールのバージョンなど）

google colabで作成しています．

can110

2023/07/27 01:17

コードを見る限りPOPULATION_SIZEが利用されておらず全体的に遺伝的アルゴリズムの流れにのっとっていないと思うのですがいかがお考えでしょうか？

行動規範の内容に同意します

回答3件

結論から言うと、ご提示のコードは遺伝的アルゴリズム (GA) を実装していません。

あるスケジュールの適当な日の前と後を他のスケジュールのものと入れ替える操作を「交叉」、適当な日のシフトをランダムに変更する操作を「突然変異」と呼んでいるようです。しかしこれらはGAで言うところの交叉や突然変異ではないです。

他の方からも指摘があるように、世代毎の個体数が1ではGAとして成立しません。
スケジュールの内容が日の粒度で変化させられるため、遺伝子にあたるような情報単位が存在しません。

全体としてみると、スケジュールをランダムに発生させては制約を満たすかどうかを調べるということを繰り返す乱択アルゴリズムです。

あと、余計なお世話ですが……週内の労働時間・労働日数には法的な規制があります。それが制約条件に盛り込まれていないようです。例えば、休日 (おそらくzだと思います) を月末に8日まとめて取らせるような働かせ方は許されないはずですが、ご提示のコードではそんなことも起こるかもしれません。

投稿2023/09/27 03:04

ikedas

総合スコア4343

ikedas

2023/10/10 04:22

ご質問のコードは、こちらをもとに改造したコードなのかと思います。 https://gist.github.com/siu-issiki/842520926fddcdfe93f6d1166f790c0d これが遺伝的アルゴリズムの例として適切かというと疑問です (あらかじめ決めてあった解に到達するまで置き換えを繰り返しているだけでは……)。世代毎の個体数が十分な大きさを持つことが必要であるという点は一応、考慮されているようです。遺伝的アルゴリズムについては参考書も豊富です。そういうものを読んできちんとした理解を持ってから実装に取り組んだほうがいいとおもいます。

行動規範の内容に同意します

ベストアンサー

収束に時間がかかっている場合に途中で打ち切る方法としては，下記の変更が考えられます。

    # while best_fitness < 5:
    while best_fitness < 5 and generation < GENERATIONS:

一方，収束し難い理由として以下の点が気になりました。

世代間の引き継ぎのために，下記の変更が必要と思われます。

        # new_schedule = Schedule()
        new_schedule = Schedule(best_schedule.genes)

制約条件4 が厳しいので，スケジュールの生成時に条件を満たすように設定するのもひとつの方法と思われます。

上記を踏まえた御参考として，numpy モジュールの配列を用いた記述例を下記に示します。なお，試行した感触で突然変異率を下げ（0.2 -> 0.01）ました。

Python
1import numpy as np
2
3rng = np.random.default_rng(42)
4
5D = 10  # number of days
6S = 14  # number of staff members
7SHIFTS = np.array(['N', 'NS', 'NB', 'D', 'I', 'G', 'Z', 'FN'])
8
9REQUIRED_STAFF_COUNT = 7
10FN_STAFF_COUNT_MIN = 1
11FN_STAFF_COUNT_MAX = 2
12NS_STAFF_COUNT_MIN = 1
13NS_STAFF_COUNT_MAX = 2
14
15# POPULATION_SIZE = 100
16GENERATIONS = 1000
17MUTATION_RATE = 0.01
18
19
20class Schedule:
21    def __init__(self, genes=None):
22        if genes is None:
23            self.genes = rng.choice(SHIFTS, (S, D))
24        else:
25            self.genes = genes
26        for s, d in zip(*np.where(self.genes == 'N')):
27            if d in range(D - 1):
28                self.genes[s, d + 1] = 'Z'
29
30    def calculate_fitness(self):
31        g = self.genes
32        fitness = 0
33
34        if np.all(np.sum(g != 'Z', axis=0) >= REQUIRED_STAFF_COUNT):
35            fitness += 1
36
37        fn_staff = np.full(S, False)
38        for s, d in zip(*np.where(g)):
39            if d in range(6, D - 2, 7) and np.all(g[s, d:d + 3] == 'FN'):
40                fn_staff[s] = True
41        if FN_STAFF_COUNT_MIN <= np.sum(fn_staff) <= FN_STAFF_COUNT_MAX:
42            fitness += 1
43
44        ns_staff = np.full(S, False)
45        for s, d in zip(*np.where(g)):
46            if d in range(6, D - 1, 7) and np.all(g[s, d:d + 2] == 'NS'):
47                ns_staff[s] = True
48        if NS_STAFF_COUNT_MIN <= np.sum(ns_staff) <= NS_STAFF_COUNT_MAX:
49            fitness += 1
50
51        fit = True
52        for s, d in zip(*np.where(g == 'N')):
53            if d in range(D - 1) and g[s, d + 1] != 'Z':
54                fit = False
55                break
56        if fit: fitness += 1
57
58        if np.all(np.sum(g[:, 5:D:6] == 'N', axis=0) > 1):
59            fitness += 1
60
61        return fitness
62
63    def crossover(self, other):
64        g = self.genes.reshape(S * D,)
65        o = other.genes.reshape(S * D,)
66        cross_point = rng.integers(1, S * D - 1)
67        ch1 = np.concatenate([g[:cross_point], o[cross_point:]])
68        ch2 = np.concatenate([o[:cross_point], g[cross_point:]])
69
70        return Schedule(ch1.reshape(S, D)), Schedule(ch2.reshape(S, D))
71
72    def mutate(self):
73        g = self.genes.reshape(S * D,)
74        for k, _ in enumerate(g):
75            if rng.random() < MUTATION_RATE:
76                g[k] = rng.choice(SHIFTS)
77
78
79if __name__ == "__main__":
80    best_schedule = Schedule()
81    best_fitness = best_schedule.calculate_fitness()
82    print("Initial Best Fitness:", best_fitness)
83
84    generation = 0
85    while best_fitness < 5 and generation < GENERATIONS:
86        generation += 1
87
88        new_schedule = Schedule(best_schedule.genes)
89        other_schedule = Schedule()
90        child1, child2 = new_schedule.crossover(other_schedule)
91
92        child1.mutate()
93        child2.mutate()
94
95        child1_fitness = child1.calculate_fitness()
96        child2_fitness = child2.calculate_fitness()
97
98        if child1_fitness > child2_fitness:
99            new_schedule = child1
100            new_fitness = child1_fitness
101        else:
102            new_schedule = child2
103            new_fitness = child2_fitness
104
105        if new_fitness > best_fitness:
106            best_schedule = new_schedule
107            best_fitness = new_fitness
108            print(f"Generation {generation:4d}, Best Fitness: {best_fitness}")
109
110    print("\nFinal Best Schedule:")
111    add_space = np.vectorize(lambda s: s + ' ' if len(s) < 2 else s)
112    print(add_space(best_schedule.genes))
113# Initial Best Fitness: 3
114# Generation    4, Best Fitness: 4
115# Generation   37, Best Fitness: 5
116# 
117# Final Best Schedule:
118# [['G ' 'G ' 'Z ' 'FN' 'FN' 'NS' 'NS' 'NS' 'G ' 'I ']
119#  ['Z ' 'Z ' 'Z ' 'N ' 'Z ' 'Z ' 'FN' 'NB' 'Z ' 'D ']
120#  ['NS' 'NB' 'NB' 'FN' 'NS' 'NS' 'I ' 'I ' 'I ' 'NS']
121#  ['D ' 'FN' 'N ' 'Z ' 'NS' 'NS' 'FN' 'NB' 'I ' 'D ']
122#  ['I ' 'D ' 'D ' 'Z ' 'I ' 'I ' 'Z ' 'D ' 'Z ' 'G ']
123#  ['FN' 'D ' 'I ' 'NS' 'N ' 'Z ' 'Z ' 'NB' 'NB' 'I ']
124#  ['D ' 'NS' 'I ' 'I ' 'NS' 'NB' 'NS' 'G ' 'NS' 'N ']
125#  ['NB' 'D ' 'Z ' 'N ' 'Z ' 'NB' 'NB' 'N ' 'Z ' 'D ']
126#  ['NB' 'Z ' 'I ' 'N ' 'Z ' 'G ' 'G ' 'I ' 'I ' 'I ']
127#  ['FN' 'I ' 'I ' 'NB' 'D ' 'G ' 'Z ' 'Z ' 'G ' 'Z ']
128#  ['N ' 'Z ' 'NS' 'G ' 'Z ' 'NS' 'NS' 'D ' 'FN' 'N ']
129#  ['FN' 'NS' 'NB' 'G ' 'G ' 'N ' 'Z ' 'I ' 'NS' 'NS']
130#  ['N ' 'Z ' 'N ' 'Z ' 'G ' 'N ' 'Z ' 'NS' 'FN' 'G ']
131#  ['NS' 'D ' 'FN' 'D ' 'NS' 'FN' 'FN' 'FN' 'FN' 'Z ']]

投稿2023/07/30 04:00

little_street

総合スコア319

ChatGPT3.5
遺伝的アルゴリズムを使って、5つの制約条件を満たすスケジュールを自動的に作成しようとしているようですね。ただし、アルゴリズムの実行に時間がかかりすぎていてうまく終了しないようです。交叉と突然変異の部分に問題があるのかもしれません。

パフォーマンスと終了条件の問題を解決するために、以下の点に注意してみてください：

ポピュレーションサイズ：現在のポピュレーションサイズが100に設定されていますが、これでは効率的に探索空間を調べるのに十分ではないかもしれません。ポピュレーションサイズを増やして、より早く良い解を見つける可能性を高めてみてください。
終了条件：現在の終了条件は、最良の適応度が5以上になることに基づいています。これではアルゴリズムが終了せずに長時間実行される可能性があります。代わりに、一定の世代数や最大計算時間など、より適切な終了条件を使ってみてください。
突然変異率：現在の突然変異率は0.2で、各イテレーションで20％の遺伝子が突然変異することを意味します。これは高すぎるか低すぎるかもしれません。異なる突然変異率を試して、アルゴリズムのパフォーマンスにどのような影響を与えるかを確認してください。
選択方法：遺伝的アルゴリズムにおいて選択プロセスは重要です。適切な選択方法（トーナメント選択やルーレットホイール選択など）を使用して、探索と活用をバランス良く行えるようにしてください。
交叉ポイント：ランダムに交叉ポイントを選ぶ方法では常に良い結果が得られるとは限りません。単一点または二点交叉などのより洗練された交叉方法を使用して、多様性を高め、探索空間をより効果的に探索してみてください。
デバッグ：アルゴリズムがどこで立ち往生しているのか、問題に直面しているのかを理解するために、さらに多くのプリント文を追加して、変数や適応度スコアの値を異なるタイミングで確認してみてください。