遺伝的アルゴリズム（GA）を用いた２人の巡回セールスマン問題（TSP）を解きたいです。

前提・実現したいこと

初期位置の設定
セールスマンが２人（できればそれ以上）のパターン

でアルゴリズムを作成したいのですが、プログラミング初心者で手付かずで困っています。

該当のソースコード

python
1# coding:utf-8
2
3import random as rnd
4import matplotlib.pyplot as plt
5import math
6import copy
7
8
9
10'''
11引数はnumが地点の数。pop_numが個体数です。
12初期に地点をランダムに作成し、keyを地点番号、座標値をvalueとして辞書を作成しています。
13今回は地点番号の並び順を遺伝子配列としてみなし、アルゴリズムを構築していきます。
14はじめの巡回経路はランダムに作成しています。
15'''
16
17def generator(num, pop_num):
18    """ 都市を初期生成 """
19
20    # 範囲指定
21    x_range = 200
22    y_range = 200
23
24    x_coordinate = [rnd.randint(0, x_range) for _ in range(num-1)]  #初期位置を別に作るので"num-1"
25    y_coordinate = [rnd.randint(0, y_range) for _ in range(num-1)]
26
27    coordinate = [[x_coordinate[i], y_coordinate[i]] for i in range(num-1)]
28
29    # 初期位置（トラクタ置き場）生成
30    first_position = [rnd.randint(0, x_range),rnd.randint(0, y_range)]
31
32    # keyが都市の番号、valueが座標値の辞書作成。
33    position_info = {}
34    for i in range(num):
35        position_info[i] = coordinate[i]
36
37    # 初期の巡回順序生成
38    select_num = [i for i in range(num-1)]
39    all_route = [rnd.sample(select_num, num-1) for _ in range(pop_num)]
40
41    # １つ目と２つ目のルートの長さ
42    
43
44    return position_info, all_route
45
46
47'''
48ここでは各座標のユークリッド距離の総和を評価値として評価関数を設計しています。
49show_route()で現世代における最良個体を描画しています。
50'''
51
52def evaluate(position_info, all_route, loop=0):
53    """ ユークリッド距離の総和を計算し評価値とする。 """
54
55    evaluate_value = []
56    for i in range(len(all_route)):
57        temp_evaluate_value = []
58        x_coordinate = [position_info[all_route[i][x]][0] for x in range(len(all_route[i]))]
59        y_coordinate = [position_info[all_route[i][y]][1] for y in range(len(all_route[i]))]
60        for j in range(len(all_route[i])):
61            if j == len(all_route[i]) - 1:
62                distance = math.sqrt(
63                    pow((x_coordinate[j] - x_coordinate[0]), 2) + pow((y_coordinate[j] - y_coordinate[0]), 2))
64            else:
65                distance = math.sqrt(
66                    pow((x_coordinate[j] - x_coordinate[j + 1]), 2) + pow((y_coordinate[j] - y_coordinate[j + 1]), 2))
67            temp_evaluate_value.append(distance)
68        evaluate_value.append(sum(temp_evaluate_value))
69
70    # 一番優秀な個体をmatplotで描画
71    excellent_evaluate_value = min(evaluate_value)
72    draw_pop_index = evaluate_value.index(excellent_evaluate_value)
73
74    show_route(position_info, all_route[draw_pop_index],int(excellent_evaluate_value), loop=loop + 1)
75
76    return evaluate_value
77
78
79'''
80今回は選択として、トーナメント選択、エリート主義を導入しています。
81トーナメント選択は指定したサイズのトーナメントを作成し、その中で指定数の優良個体を選択します。
82エリート主義は指定した上位個体を問答無用で次世代に残す手法です。
83'''
84
85def selection(all_route, evaluate_value, tournament_select_num, tournament_size, elite_select_num, ascending=False):
86    """ トーナメント選択とエリート保存を行う"""
87
88    select_pop = []
89    elite_pop = []
90    # トーナメント選択
91    while True:
92        select = rnd.sample(evaluate_value, tournament_size)
93        select.sort(reverse=ascending)
94        for i in range(tournament_select_num):
95            value = select[i]
96            index = evaluate_value.index(value)
97            select_pop.append(all_route[index])
98
99        # 個体数の半数個選択するまで実行
100        if len(select_pop) >= len(all_route) / 2:
101            break
102
103    # エリート保存
104    sort_evaluate_value = copy.deepcopy(evaluate_value)
105    sort_evaluate_value.sort(reverse=ascending)
106    for i in range(elite_select_num):
107        value = sort_evaluate_value[i]
108        index = evaluate_value.index(value)
109        elite_pop.append(all_route[index])
110
111    return select_pop, elite_pop
112
113'''
114指定した確率によって交叉を実行します。
115ここでは順序交叉と呼ばれる交叉手法を使用しています。
116'''
117def crossover(select_pop, crossover_prob):
118    ''' 確率的に順序交叉を実行する '''
119
120    cross_pop = rnd.sample(select_pop, 2)
121    pop_1 = cross_pop[0]
122    pop_2 = cross_pop[1]
123
124    check_prob = rnd.randint(0, 100)
125    if check_prob <= crossover_prob:
126
127        # 順序交叉
128        new_pop_1 = []
129        cut_index = rnd.randint(1, len(pop_1) - 2)
130        new_pop_1.extend(pop_1[:cut_index])
131        for i in range(len(pop_1)):
132            if pop_2[i] not in new_pop_1:
133                new_pop_1.append(pop_2[i])
134
135        new_pop_2 = []
136        new_pop_2.extend(pop_1[cut_index:])
137        for i in range(len(pop_1)):
138            if pop_2[i] not in new_pop_2:
139                new_pop_2.append(pop_2[i])
140
141        return new_pop_1, new_pop_2
142
143    else:
144        return pop_1, pop_2
145
146'''
147指定した確率で突然変異が起こるようにしています。
148今回は地点番号を入れ替える操作を突然変位としています。
149'''
150def mutation(pop, mutation_prob):
151    """ 循環経路の順番をランダムで入れ替える """
152
153    check_prob = rnd.randint(0, 100)
154
155    if check_prob <= mutation_prob:
156        select_num = [i for i in range(num)]
157        select_index = rnd.sample(select_num, 2)
158
159        a = pop[select_index[0]]
160        b = pop[select_index[1]]
161        pop[select_index[1]] = a
162        pop[select_index[0]] = b
163
164    return pop
165
166'''
167matplotlibを使用して経路を描画する関数です。
168plt.savefig()は描画したグラフをpngとして保存するためのものです。
169'''
170def show_route(position_info, route, excellent_evaluate_value,  loop=0):
171    """ matplotlibで循環経路を描画 """
172
173    x_coordinate = [position_info[route[i]][0] for i in range(len(route))]
174    y_coordinate = [position_info[route[i]][1] for i in range(len(route))]
175    x_coordinate.append(position_info[route[0]][0])
176    y_coordinate.append(position_info[route[0]][1])
177
178    plt.figure() #これ入れたら重ね書きされなくなった。
179
180    plt.scatter(x_coordinate, y_coordinate)
181    plt.plot(x_coordinate, y_coordinate, label=excellent_evaluate_value)
182    plt.title("Generation: {}".format(loop))
183    plt.legend()
184
185    plt.savefig("C:\Users\241k\Documents\img\tsp{}".format(loop))  # pngとして保存。カレントディレクトリにimgフォルダを置く必要あり。
186    # plt.show()
187
188
189# 初期生成時のパラメータ
190num = 50  # 都市の数
191pop_num = 200  # 個体数
192generation_num = 100  # 世代数
193
194# 選択のパラメータ
195tournament_size = 10  # トーナメントサイズ
196tournament_select_num = 2  # トーナメントサイズで選択する個体数
197elite_select_num = 1 # エリート主義で選択する個体数
198
199# 交叉の確率
200crossover_prob = 50
201
202# 突然変異の確率
203mutation_prob = 3
204
205# 初期生成
206position_info, all_route = generator(num, pop_num)
207
208# 評価
209evaluate_value = evaluate(position_info, all_route)
210
211for loop in range(generation_num):
212    # 選択
213    select_pop, elite_pop = selection(
214        all_route, evaluate_value, tournament_select_num, tournament_size, elite_select_num, ascending=False)
215
216    # 選択した個体の中から2個体選択し交叉や突然変異を適用する。
217    next_pop = []
218    while True:
219        # 交叉
220        pop_1, pop_2 = crossover(select_pop, crossover_prob)
221        # 突然変異
222        pop_1 = mutation(pop_1, mutation_prob)
223        pop_2 = mutation(pop_2, mutation_prob)
224
225        next_pop.append(pop_1)
226        next_pop.append(pop_2)
227
228        if len(next_pop) >= pop_num - elite_select_num:
229            break
230
231    # エリート主義。優良個体を次世代へ継承。
232    next_pop.extend(elite_pop)
233
234    # 評価
235    evaluate_value = evaluate(position_info, next_pop, loop=loop + 1)
236
237    # 更新
238    all_route = next_pop
239

Zuishin

2019/10/04 15:39

リンク先にコード載ってますが。初期位置は generator で乱数で x, y を作成しているところです。セールスマンの人数は巡回セールスマン問題に関係ありません。

nandymak

2019/10/05 00:13

やりたい目的は何でしょう？アルゴリズムは思いついたがプログラム化出来ないからでしょうか？プログラムの勉強でしょうか？前者ならプロを雇った方が良いですし、後者ならもっと簡単なお題を選ぶべきと思います。

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

回答1件

コードを走らせて確認したときに、どのようなエラーが出てきたか見ましたか？

エラー対策

" FileNotFoundError: [Errno 2] No such file or directory: 'C:\Users....'
->
plt.savefig("./img/tsp{}".format(loop))

"IndexError: list index out of range"
->
for i in range(num-1):
select_num = [i for i in range(num-1)]

"RuntimeWarning: More than 20 figures have been opened. Figures created through the pyplot interface ('matplotlib.pyplot.figure') are retained until explicitly closed and may consume too much memory."
->
plt.close()

質問の件

セールスマンの人数の件

参照先URLにpop_numが個体数とありますので、pop_num =200 # 個体数を201などに書き換えたら良さそうですね。
――もしくは、巡回先の都市の数ですか？もしそうであれば、
num = 100 # 都市の数
ここの数値が4では3に、それ以下だと動作せず(２つなら経路は触りようなし、１つなら巡回できず)。100では99になりますね。
2. 初期位置の件
position_info, all_route = generator(num, pop_num)
上記numを引数にしてgenerator()で作っていますので、ここのランダム要素をなくして決め打ちすればよさそうですね。
具体的には、既定では200x200のマス目に対してランダムに都市の位置（座標）を数値を割り振って、
いるようですので、x_coordinateとy_coordinateを決め打ちしたら良さそうです。

Python3
1# coding:utf-8
2
3import random as rnd
4import matplotlib.pyplot as plt
5import math
6import copy
7
8
9
10'''
11引数はnumが地点の数。pop_numが個体数です。
12初期に地点をランダムに作成し、keyを地点番号、座標値をvalueとして辞書を作成しています。
13今回は地点番号の並び順を遺伝子配列としてみなし、アルゴリズムを構築していきます。
14はじめの巡回経路はランダムに作成しています。
15'''
16
17def generator(num, pop_num):
18    """ 都市を初期生成 """
19
20    # 範囲指定
21    x_range = 200
22    y_range = 200
23
24    x_coordinate = [rnd.randint(0, x_range) for _ in range(num-1)]  #初期位置を別に作るので"num-1"
25    y_coordinate = [rnd.randint(0, y_range) for _ in range(num-1)]
26
27    print(x_coordinate )
28    print(y_coordinate )
29
30    coordinate = [[x_coordinate[i], y_coordinate[i]] for i in range(num-1)]
31
32    # 初期位置（トラクタ置き場）生成
33    first_position = [rnd.randint(0, x_range),rnd.randint(0, y_range)]
34
35    # keyが都市の番号、valueが座標値の辞書作成。
36    position_info = {}
37
38    # IndexError: list index out of range
39    ######################################
40    # for i in range(num):
41    for i in range(num-1):
42        position_info[i] = coordinate[i]
43
44    # 初期の巡回順序生成
45    select_num = [i for i in range(num-1)]
46    all_route = [rnd.sample(select_num, num-1) for _ in range(pop_num)]
47
48    # １つ目と２つ目のルートの長さ
49
50
51    return position_info, all_route
52
53
54'''
55ここでは各座標のユークリッド距離の総和を評価値として評価関数を設計しています。
56show_route()で現世代における最良個体を描画しています。
57'''
58
59def evaluate(position_info, all_route, loop=0):
60    """ ユークリッド距離の総和を計算し評価値とする。 """
61
62    evaluate_value = []
63    for i in range(len(all_route)):
64        temp_evaluate_value = []
65        x_coordinate = [position_info[all_route[i][x]][0] for x in range(len(all_route[i]))]
66        y_coordinate = [position_info[all_route[i][y]][1] for y in range(len(all_route[i]))]
67        for j in range(len(all_route[i])):
68            if j == len(all_route[i]) - 1:
69                distance = math.sqrt(
70                    pow((x_coordinate[j] - x_coordinate[0]), 2) + pow((y_coordinate[j] - y_coordinate[0]), 2))
71            else:
72                distance = math.sqrt(
73                    pow((x_coordinate[j] - x_coordinate[j + 1]), 2) + pow((y_coordinate[j] - y_coordinate[j + 1]), 2))
74            temp_evaluate_value.append(distance)
75        evaluate_value.append(sum(temp_evaluate_value))
76
77    # 一番優秀な個体をmatplotで描画
78    excellent_evaluate_value = min(evaluate_value)
79    draw_pop_index = evaluate_value.index(excellent_evaluate_value)
80
81    show_route(position_info, all_route[draw_pop_index],int(excellent_evaluate_value), loop=loop + 1)
82
83    return evaluate_value
84
85
86'''
87今回は選択として、トーナメント選択、エリート主義を導入しています。
88トーナメント選択は指定したサイズのトーナメントを作成し、その中で指定数の優良個体を選択します。
89エリート主義は指定した上位個体を問答無用で次世代に残す手法です。
90'''
91
92def selection(all_route, evaluate_value, tournament_select_num, tournament_size, elite_select_num, ascending=False):
93    """ トーナメント選択とエリート保存を行う"""
94
95    select_pop = []
96    elite_pop = []
97    # トーナメント選択
98    while True:
99        select = rnd.sample(evaluate_value, tournament_size)
100        select.sort(reverse=ascending)
101        for i in range(tournament_select_num):
102            value = select[i]
103            index = evaluate_value.index(value)
104            select_pop.append(all_route[index])
105
106        # 個体数の半数個選択するまで実行
107        if len(select_pop) >= len(all_route) / 2:
108            break
109
110    # エリート保存
111    sort_evaluate_value = copy.deepcopy(evaluate_value)
112    sort_evaluate_value.sort(reverse=ascending)
113    for i in range(elite_select_num):
114        value = sort_evaluate_value[i]
115        index = evaluate_value.index(value)
116        elite_pop.append(all_route[index])
117
118    return select_pop, elite_pop
119
120'''
121指定した確率によって交叉を実行します。
122ここでは順序交叉と呼ばれる交叉手法を使用しています。
123'''
124def crossover(select_pop, crossover_prob):
125    ''' 確率的に順序交叉を実行する '''
126
127    cross_pop = rnd.sample(select_pop, 2)
128    pop_1 = cross_pop[0]
129    pop_2 = cross_pop[1]
130
131    check_prob = rnd.randint(0, 100)
132    if check_prob <= crossover_prob:
133
134        # 順序交叉
135        new_pop_1 = []
136        cut_index = rnd.randint(1, len(pop_1) - 2)
137        new_pop_1.extend(pop_1[:cut_index])
138        for i in range(len(pop_1)):
139            if pop_2[i] not in new_pop_1:
140                new_pop_1.append(pop_2[i])
141
142        new_pop_2 = []
143        new_pop_2.extend(pop_1[cut_index:])
144        for i in range(len(pop_1)):
145            if pop_2[i] not in new_pop_2:
146                new_pop_2.append(pop_2[i])
147
148        return new_pop_1, new_pop_2
149
150    else:
151        return pop_1, pop_2
152
153'''
154指定した確率で突然変異が起こるようにしています。
155今回は地点番号を入れ替える操作を突然変位としています。
156'''
157def mutation(pop, mutation_prob):
158    """ 循環経路の順番をランダムで入れ替える """
159
160    check_prob = rnd.randint(0, 100)
161
162    if check_prob <= mutation_prob:
163        # IndexError: list index out of range
164        # select_num = [i for i in range(num)]
165        select_num = [i for i in range(num-1)]
166        select_index = rnd.sample(select_num, 2)
167
168        a = pop[select_index[0]]
169        b = pop[select_index[1]]
170        pop[select_index[1]] = a
171        pop[select_index[0]] = b
172
173    return pop
174
175'''
176matplotlibを使用して経路を描画する関数です。
177plt.savefig()は描画したグラフをpngとして保存するためのものです。
178'''
179def show_route(position_info, route, excellent_evaluate_value,  loop=0):
180    """ matplotlibで循環経路を描画 """
181
182    x_coordinate = [position_info[route[i]][0] for i in range(len(route))]
183    y_coordinate = [position_info[route[i]][1] for i in range(len(route))]
184    x_coordinate.append(position_info[route[0]][0])
185    y_coordinate.append(position_info[route[0]][1])
186
187    plt.figure() #これ入れたら重ね書きされなくなった。
188
189    plt.scatter(x_coordinate, y_coordinate)
190    plt.plot(x_coordinate, y_coordinate, label=excellent_evaluate_value)
191    plt.title("Generation: {}".format(loop))
192    plt.legend()
193
194    # " FileNotFoundError: [Errno 2] No such file or directory: 'C:\Users\....'
195    # plt.savefig("C:\Users\241k\Documents\img\tsp{}".format(loop))  # pngとして保存。カレントディレクトリにimgフォルダを置く必要あり。
196    plt.savefig("./img/tsp{}".format(loop))
197    # plt.show()
198
199    # RuntimeWarning: More than 20 figures have been opened. Figures created through the pyplot interface (`matplotlib.pyplot.figure`) are retained until explicitly closed and may consume too much memory. 
200    plt.close()
201
202# 初期生成時のパラメータ
203num = 100  # 都市の数
204pop_num =200  # 個体数
205generation_num = 100  # 世代数
206
207# 選択のパラメータ
208tournament_size = 10  # トーナメントサイズ
209tournament_select_num = 2  # トーナメントサイズで選択する個体数
210elite_select_num = 1 # エリート主義で選択する個体数
211
212# 交叉の確率
213crossover_prob = 50
214
215# 突然変異の確率
216mutation_prob = 3
217
218# 初期生成
219position_info, all_route = generator(num, pop_num)
220
221# 評価
222evaluate_value = evaluate(position_info, all_route)
223
224for loop in range(generation_num):
225    # 選択
226    select_pop, elite_pop = selection(
227        all_route, evaluate_value, tournament_select_num, tournament_size, elite_select_num, ascending=False)
228
229    # 選択した個体の中から2個体選択し交叉や突然変異を適用する。
230    next_pop = []
231    while True:
232        # 交叉
233        pop_1, pop_2 = crossover(select_pop, crossover_prob)
234        # 突然変異
235        pop_1 = mutation(pop_1, mutation_prob)
236        pop_2 = mutation(pop_2, mutation_prob)
237
238        next_pop.append(pop_1)
239        next_pop.append(pop_2)
240
241        if len(next_pop) >= pop_num - elite_select_num:
242            break
243
244    # エリート主義。優良個体を次世代へ継承。
245    next_pop.extend(elite_pop)
246
247    # 評価
248    evaluate_value = evaluate(position_info, next_pop, loop=loop + 1)
249
250    # 更新
251    all_route = next_pop