pythonで巡回セールマン問題を遺伝的アルゴリズムで解く方法

受付中

回答 1

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 2,482

okazujet

score 9

前提・実現したいこと

巡回セールスマン問題を遺伝的アルゴリズムで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,定義なし]]
のように格納しているファイルを持っています。
地点数は全部で150地点ほどあり、
それぞれ[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と回答しているお店のどこかに行くものとします。
回答数が10店舗であれば10C10+10C9+10C8+・・・・+10C1だけ巡回セールスマンを解いて
かかった時間と順路を1行目からExcelファイルに吐き出せるようにしたいです。

現在巡回セールスマン問題を総当たりで解いており
10店舗であれば2分ぐらいで修了するのですが、
20店舗になると何年もかかる計算になっており困っています。
ご協力お願いします。
不明瞭な点があれば質問をお願いします。

# -*- coding: utf-8 -*- 
import math
import itertools
import queue
import numpy as np
import csv

def compute_travel_time_between2shops(shop1, shop2):
    start_node = ""
    goal_node = ""
    shop1_node_distance = 0
    shop2_node_distance = 0

    #shop1とshop2には,Nodeも許すので,条件分岐する
    if isinstance(shop1, Node) and isinstance(shop2, Node):
        start_node = shop1
        goal_node = shop2
    elif isinstance(shop1, Node):
        start_node = shop1
        goal_node = shop2.node
        shop2_node_distance = math.sqrt((shop2.x - goal_node.x)**2 + (shop2.y - goal_node.y)**2)
    elif isinstance(shop2, Node):
        start_node = shop1.node
        goal_node = shop2
        shop1_node_distance = math.sqrt((shop1.x - start_node.x)**2 + (shop1.y - start_node.y)**2)
    else:
        start_node = shop1.node
        goal_node = shop2.node
        shop1_node_distance = math.sqrt((shop1.x - start_node.x)**2 + (shop1.y - start_node.y)**2)
        shop2_node_distance = math.sqrt((shop2.x - goal_node.x)**2 + (shop2.y - goal_node.y)**2)

    result_time = shop1_node_distance + shop2_node_distance

    if start_node == goal_node:
        return result_time 

    searched_nodes = []
    unsearched_nodes = []

    start_node = Neo_Node(start_node)
    unsearched_nodes.append(start_node)

    while True:
        if len(unsearched_nodes) == 0:
            break

        #確定nodeを一つ決める
        done_node = ""
        temp_cost = 100000
        for un_n in unsearched_nodes:
            if un_n.cost < temp_cost:
                done_node = un_n
                temp_cost = un_n.cost

        #決まったら入れ替え
        searched_nodes.append(done_node)
        unsearched_nodes.remove(done_node)

        #done_nodeに繋がるnodeを未確定に入れる
        for (edge, cost) in zip(done_node.edges_to, done_node.edges_cost):
            new_edge = Neo_Node(edge)
            new_edge.cost = done_node.cost + cost

            #x,y が同じnodeがsearchedに入ってたら入れない
            canInsert = True
            for node in searched_nodes:
                if node.x == edge.x and node.y == edge.y:
                    canInsert = False 

            #x,yが同じnodeがunsearchedに入ってたらcostを比較する
            for node in unsearched_nodes:
                if node.x == edge.x and node.y == edge.y and new_edge.cost < node.cost:
                    unsearched_nodes.remove(node)

            if canInsert and new_edge.floor == done_node.floor:
                unsearched_nodes.append(new_edge) 


    #goal_nodeと同じヤツを出力
    for searched_node in searched_nodes:
        if searched_node.x == goal_node.x and searched_node.y == goal_node.y:
            result_time += searched_node.cost

    return result_time * multiple_value(shop1.floor)

#ノードの階数、x座標、y座標を記録
    #nosが廊下にある分岐点、elsがエレベーターノード
    nos201 = Node(2,253,273)

#Shopの店名、カテゴリ、階数、x座標、y座標、リンクを持つノードを記録,本当は他にもショップの定義があります。
    shop2 = Shop(2, " URBAN RESEARCH DOORS", "レディス・メンズ・キッズ・雑貨",4,263,235,nos403)

# 配列読み込み
    granfront = np.load("a.npy")

     user = [(shop28,1),(shop70,2),(shop71,2),(shop72,2),(shop83,2),(shop86,2),(shop99,1),(shop123,2),(shop133,2),(shop144,2)]

    limit_time = 7200
    tb = 180 # 1
    tw = 600 # 2

    for i in range(len(user)):
        shop_combinations = list(itertools.combinations(user, len(user)-i))
        for shop_comb in shop_combinations:
            shop_permutations = list(itertools.permutations(shop_comb))
            result_time = 100000
            result_root = []
            for shop_perm in shop_permutations:
                temp_time = 0
                temp_shops = []
                for sh, like in shop_perm:
                    temp_shops.append(sh)
                    if like == 1:
                        temp_time += tb
                    else:
                        temp_time += tw

                temp_time += compute_travel_time_between2shops(start_node, temp_shops[0])
                previous_node = temp_shops[0]
                for sh in temp_shops:
                    if previous_node == sh:
                        continue

                    temp_time += granfront[sh.id][previous_node.id]
                    previous_node = sh

                if temp_time < result_time:
                    result_time = temp_time
                    result_root = temp_shops

            # 時間がlimit_timeより少ないなら時間と順番書き込み
            if result_time <= limit_time:
                print("制限時間内にいける店舗の順番と時間:" + str(result_time))
                with open("user1.csv", "a") as f:
                    result = []
                    result.append(result_time)
                    for sh in result_root:
                        result.append(sh.name)

                    writer = csv.writer(f, lineterminator='\n')
                    writer.writerow(result)
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 1

+1

遺伝的アルゴリズムの概要はwikipediaなどを参照すると基本的な考え方が書いてあります。本件でいえば「適当に作った順路の候補をN組作り、ある順路に対する評価関数を決め(ここでは総巡回時間になるでしょうか)、そのN組の順路をすこしずつ変えながらよりスコアの高い個体が遺伝的に生み出されるのを一定回数世代交代を繰り返しながら待つ」という感じになると思います。

残念ながら「このレベルの設問条件ならこういう手順でやればよい」と言えるほど自分には知識がないので具体的な方針をコメントすることはできません。自分の認識ではどんな問題でも効率よく解ける決定版アルゴリズムがあるわけではなく、いまだ色々な観点で研究が続いていると思います。例えば「より評価点の高い個体を生み出すためにどういうふうに子孫を生成するか・残すかの方針」についてバリエーションがあると思います。ご覧のページのコードには「エリート戦略、トーナメント方式」を採用しているようです。

ご覧のページにはコンパクトかつ的確なコメントが添えられたコードが提示されていると思います。これを参考にしてとりあえず作成してみてはいかがでしょうか?そのページの説明以上の回答はもはやコードそのものになってしまう気がしますよ?

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/03/05 22:41

    > 質問を作り直した方がよい?

    ちょっとまよいますが、別途質問を起こし本質問は残しておいてもよいと思います。新たに起こした部分問題の質問の説明上「なぜこの質問をしているかの背景がわかるように」オリジナルの質問へのリンクが提示できたほうが都合がよいことがあるかも知れないからです。

    キャンセル

  • 2017/03/05 23:47

    https://teratail.com/questions/68078
    こちらに質問を作り直したのですがいかがでしょうか?

    キャンセル

  • 2017/03/06 00:01

    残念ながら「小さな部分問題を問う」質問にはなっていません。

    自分の意図を再度申し上げると「ある程度自分で作成すること」およびそれを作る過程で「つまった点だけ(例えば特定の一つの関数や処理の実装についてのみ)質問する」ことです。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.22%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる