Q&A
###前提・実現したいこと
巡回セールスマン問題を遺伝的アルゴリズムでpythonを使って解く方法について
質問したいです。
参考URL
http://blog.livedoor.jp/komq/archives/1012592617.html
要は2地点間の移動時間がすべて計算されている上での
遺伝的アルゴリズムを用いた巡回セールスマン問題を解ける方法を知りたいですが、
以下長文でやりたいことを書きます。
現在npyファイルに
地点間の移動時間[秒]を
[[定義なし,2.63,6.52,5.34],
[2.63,定義なし,5.87,4.32],
[6.52,5.87,定義なし,7.87],
[5.34,5.87,7.87,定義なし]]
のように格納しているファイルを持っています。
地点数は全部で１５０地点ほどあり、
それぞれ[shop1,shop2,....,shop150]のように
IDとして取り込んでいます。
やりたいこととしては、
・ユーザごとに移動パターンを作成する
・ユーザごとにアンケート結果をもっており
user = [(shop28,1),(shop70,1),(shop71,2),(shop72,1),(shop83,2),(shop86,2),(shop99,1),(shop123,2),(shop133,2),(shop144,2)]のように各地点に対する興味度合いが格納されており、回答されていない地点は興味がないということで訪問する可能性が0としています。
1と2でその地点に滞在する時間を変えており、それぞれtb = 180,tw = 600のように設定できるようにしています。
・訪問する制限時間をT=7200のように設定しており、その時間内で滞在時間と移動時間を含めて移動パターンを作成します。
・アンケート結果で1,2と回答しているお店のどこかに行くものとします。
回答数が１０店舗であれば10C10+10C9+10C8+・・・・+10C1だけ巡回セールスマンを解いて
かかった時間と順路を１行目からExcelファイルに吐き出せるようにしたいです。
現在巡回セールスマン問題を総当たりで解いており
１０店舗であれば２分ぐらいで修了するのですが、
２０店舗になると何年もかかる計算になっており困っています。
ご協力お願いします。
不明瞭な点があれば質問をお願いします。
python
1# -*- coding: utf-8 -*- 2import math 3import itertools 4import queue 5import numpy as np 6import csv 7 8def compute_travel_time_between2shops(shop1, shop2): 9 start_node = "" 10 goal_node = "" 11 shop1_node_distance = 0 12 shop2_node_distance = 0 13 14 #shop1とshop2には，Nodeも許すので，条件分岐する 15 if isinstance(shop1, Node) and isinstance(shop2, Node): 16 start_node = shop1 17 goal_node = shop2 18 elif isinstance(shop1, Node): 19 start_node = shop1 20 goal_node = shop2.node 21 shop2_node_distance = math.sqrt((shop2.x - goal_node.x)**2 + (shop2.y - goal_node.y)**2) 22 elif isinstance(shop2, Node): 23 start_node = shop1.node 24 goal_node = shop2 25 shop1_node_distance = math.sqrt((shop1.x - start_node.x)**2 + (shop1.y - start_node.y)**2) 26 else: 27 start_node = shop1.node 28 goal_node = shop2.node 29 shop1_node_distance = math.sqrt((shop1.x - start_node.x)**2 + (shop1.y - start_node.y)**2) 30 shop2_node_distance = math.sqrt((shop2.x - goal_node.x)**2 + (shop2.y - goal_node.y)**2) 31 32 result_time = shop1_node_distance + shop2_node_distance 33 34 if start_node == goal_node: 35 return result_time 36 37 searched_nodes = [] 38 unsearched_nodes = [] 39 40 start_node = Neo_Node(start_node) 41 unsearched_nodes.append(start_node) 42 43 while True: 44 if len(unsearched_nodes) == 0: 45 break 46 47 #確定nodeを一つ決める 48 done_node = "" 49 temp_cost = 100000 50 for un_n in unsearched_nodes: 51 if un_n.cost < temp_cost: 52 done_node = un_n 53 temp_cost = un_n.cost 54 55 #決まったら入れ替え 56 searched_nodes.append(done_node) 57 unsearched_nodes.remove(done_node) 58 59 #done_nodeに繋がるnodeを未確定に入れる 60 for (edge, cost) in zip(done_node.edges_to, done_node.edges_cost): 61 new_edge = Neo_Node(edge) 62 new_edge.cost = done_node.cost + cost 63 64 #x,y が同じnodeがsearchedに入ってたら入れない 65 canInsert = True 66 for node in searched_nodes: 67 if node.x == edge.x and node.y == edge.y: 68 canInsert = False 69 70 #x,yが同じnodeがunsearchedに入ってたらcostを比較する 71 for node in unsearched_nodes: 72 if node.x == edge.x and node.y == edge.y and new_edge.cost < node.cost: 73 unsearched_nodes.remove(node) 74 75 if canInsert and new_edge.floor == done_node.floor: 76 unsearched_nodes.append(new_edge) 77 78 79 #goal_nodeと同じヤツを出力 80 for searched_node in searched_nodes: 81 if searched_node.x == goal_node.x and searched_node.y == goal_node.y: 82 result_time += searched_node.cost 83 84 return result_time * multiple_value(shop1.floor) 85 86#ノードの階数、x座標、y座標を記録 87 #nosが廊下にある分岐点、elsがエレベーターノード 88 nos201 = Node(2,253,273) 89 90#Shopの店名、カテゴリ、階数、x座標、y座標、リンクを持つノードを記録,本当は他にもショップの定義があります。 91 shop2 = Shop(2, " URBAN RESEARCH DOORS", "レディス・メンズ・キッズ・雑貨",4,263,235,nos403) 92 93# 配列読み込み 94 granfront = np.load("a.npy") 95 96 user = [(shop28,1),(shop70,2),(shop71,2),(shop72,2),(shop83,2),(shop86,2),(shop99,1),(shop123,2),(shop133,2),(shop144,2)] 97 98 limit_time = 7200 99 tb = 180 # 1 100 tw = 600 # 2 101 102 for i in range(len(user)): 103 shop_combinations = list(itertools.combinations(user, len(user)-i)) 104 for shop_comb in shop_combinations: 105 shop_permutations = list(itertools.permutations(shop_comb)) 106 result_time = 100000 107 result_root = [] 108 for shop_perm in shop_permutations: 109 temp_time = 0 110 temp_shops = [] 111 for sh, like in shop_perm: 112 temp_shops.append(sh) 113 if like == 1: 114 temp_time += tb 115 else: 116 temp_time += tw 117 118 temp_time += compute_travel_time_between2shops(start_node, temp_shops[0]) 119 previous_node = temp_shops[0] 120 for sh in temp_shops: 121 if previous_node == sh: 122 continue 123 124 temp_time += granfront[sh.id][previous_node.id] 125 previous_node = sh 126 127 if temp_time < result_time: 128 result_time = temp_time 129 result_root = temp_shops 130 131 # 時間がlimit_timeより少ないなら時間と順番書き込み 132 if result_time <= limit_time: 133 print("制限時間内にいける店舗の順番と時間：" + str(result_time)) 134 with open("user1.csv", "a") as f: 135 result = [] 136 result.append(result_time) 137 for sh in result_root: 138 result.append(sh.name) 139 140 writer = csv.writer(f, lineterminator='\n') 141 writer.writerow(result) 142
回答1件
0
遺伝的アルゴリズムの概要はwikipediaなどを参照すると基本的な考え方が書いてあります。本件でいえば「適当に作った順路の候補をＮ組作り、ある順路に対する評価関数を決め（ここでは総巡回時間になるでしょうか）、そのＮ組の順路をすこしずつ変えながらよりスコアの高い個体が遺伝的に生み出されるのを一定回数世代交代を繰り返しながら待つ」という感じになると思います。
残念ながら「このレベルの設問条件ならこういう手順でやればよい」と言えるほど自分には知識がないので具体的な方針をコメントすることはできません。自分の認識ではどんな問題でも効率よく解ける決定版アルゴリズムがあるわけではなく、いまだ色々な観点で研究が続いていると思います。例えば「より評価点の高い個体を生み出すためにどういうふうに子孫を生成するか・残すかの方針」についてバリエーションがあると思います。ご覧のページのコードには「エリート戦略、トーナメント方式」を採用しているようです。
ご覧のページにはコンパクトかつ的確なコメントが添えられたコードが提示されていると思います。これを参考にしてとりあえず作成してみてはいかがでしょうか？そのページの説明以上の回答はもはやコードそのものになってしまう気がしますよ？
投稿2017/03/05 08:17
総合スコア18394
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2017/03/05 08:45
2017/03/05 12:41 編集
2017/03/05 11:30
2017/03/05 11:41
2017/03/05 12:08
2017/03/05 12:47
2017/03/05 13:03
2017/03/05 13:41
2017/03/05 14:47
2017/03/05 15:01