質問をすることでしか得られない、回答やアドバイスがある。

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

ただいまの
回答率

90.52%

  • Python

    7929questions

    Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

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

受付中

回答 1

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 1,294

okazujet

score 3

前提・実現したいこと

巡回セールスマン問題を遺伝的アルゴリズムで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 17:45

    ご回答ありがとうございます。
    長文を読んでくださりありがとうございます。
    やりたいことは
    「適当に作った順路の候補をN組作り、ある順路に対する評価関数を決め(ここでは総巡回時間になるでしょうか)、そのN組の順路をすこしずつ変えながらよりスコアの高い個体が遺伝的に生み出されるのを一定回数世代交代を繰り返しながら待つ」でおっしゃる通りで
    考え方も参考URLや遺伝的アルゴリズムについて調べたらやり方自体は把握していますが、
    実装力がなくコードとして読み込むことができません。
    全ての地点を座標化し、それをダイクストラ法を用いてそれらの移動時間をすべて算出できたのですが、
    遺伝的アルゴリズムを用いて巡回セールスマン問題を解くコードを実装できなくて困っています。
    入力に全地点のうち数地点の地点名と突然変異させる回数を入力すれば
    出力でそう移動時間と巡回経路を算出プログラムをいただけないでしょうか?

    ご迷惑をおかけしてしまい申し訳ございません
    色々調べたのですが、pythonで今回の事例にあって改変すればできそうなソースコードを見つけることができませんでした。
    shop17,-999,80.25991779,-999,102.6312653,38.85243401,90.38458331,95.96488901,64.29904977,90.13840462,169.2105062,100.8549304,81.1001744,-999,129.2528464,70.01976573,79.12109002,-999,59.54952577,42.89306815,110.2578754,72.58839286,42.14606695,69.15961034,80.36088935,-999,86.59051634,117.1357507,89.79788987,47.25822572,37.80504901,107.2621976,65.51107772,93.41204033,88.02187531,107.8455901,89.09396394,58.91324991,61.35604599,174.8561111,179.3337755,208.189624,72.59666839,116.7631609,95.83544898,33.90504901,143.6118272,71.95948506,109.6254799,116.1701086,102.1972885,85.52439506,97.99480664,177.7553448,75.20473419,117.1357507,94.82737996,97.14282549,106.0026035,109.692019,133.3339339,73.18281811,11.27302945,143.6118272,93.08610402,91.31618042,61.8555755,116.9041275,105.4912831,-999,84.87977427,108.0478082,103.691561,109.4896892,82.4633531,112.8688618,79.38566535,95.39176162,-999,198.2178752,189.9557005,-999,92.71503182,75.44273092,127.112207,-999,73.13584563,158.1807651,208.0733379,86.66678231,108.9669302,34.80273552,192.9648701,-999,10.3385264,45.48305185,72.23075118,105.008329,108.9226273,30.83519602,-999,105.3797964,46.9459517,30.30458959,77.91912071,135.3088376,105.4104545,-999,101.6567447,112.7110348,57.7081276,201.1092368,-999,73.37767136,76.80635101,-999,-999,83.2149378,86.78735277,-999,98.18618616,-999,132.7741854,133.3721241,70.80443473,-999,-999,95.33517294,73.82161244,88.27771008,84.33052141,60.75769615,73.96051447,73.37220649,-999,-999,92.17771008,201.1592995,111.9864345,87.39042384,24.44674866,86.81649406,33.64485341,86.16661417,73.67502834,122.4544955,-999,-999,-999,83.13574494,-999,196.2458269,77.55813647,141.0074767,80.56804304,-999,84.13626638,-999,-999
    全ての地点についてほかの地点との移動時間をこのように格納しています。
    -999となっているのは定義はしているが、行く必要がない地点との移動時間を仮に設定しています。

    キャンセル

  • 2017/03/05 19:05 編集

    自分の場合は興味があるのでできたらもう少し具体的アドバイスもしたいのですが、如何せん30分やそこらでは充分な回答は無理なので、残念ながらコードによるアドバイスはできそうもありません。

    同じ問題を共有していたり興味をお持ちの方がいらっしゃればコードそのものの回答がつく可能性はあると思います。おわかりと思いますが本サイトは無償の助け合いサイトです。よって難易度・複雑さが大きくなるほど具体的なコードによる回答を得られる可能性は低くなると思います。回答に必要な手間が大きくなりますから。

    ただ、ある程度まで完成に近づいたコードを提示できるなら、アドバイスが得られる可能性はずっと高くなると思います。

    なお、長大なデータ・コードはコメント欄には書かずに質問欄に見やすい形で書きましょう。閲覧者が見やすくなりそれだけ回答の手間が減るからです。

    キャンセル

  • 2017/03/05 20:30

    サービスの使い方からご教示いただきありがとうございます。
    初めてこのサービスを利用したのでありがたいです。

    もう少し次回から抽象的な質問にします。

    一応コードを最低限にして質問覧に載せました。
    できればご回答いただけると幸いです。

    キャンセル

  • 2017/03/05 20:41

    パッと見てナップサック問題にも見えますね。
    店舗内の滞留時間を考慮(単純加算)した巡回セールスマン問題としても解けそうですが。

    キャンセル

  • 2017/03/05 21:08

    >can110さん
    そうだと思います。
    解き方に困っているのですが、
    何か簡単な解き方はないでしょうか?

    キャンセル

  • 2017/03/05 21:47

    > もう少し次回から抽象的な質問にします。

    むしろ具体的な質問が歓迎されます。ただし大きなプログラムの全体を質問するのではなく、プログラムの中で自分が悩んでいる特定の部分のみに着目した小さくて具体的な質問にするのです。本件であれば、最初にN組の個体(=巡回ルート)を生成する必要がありますが、「これこれの構造にしたいのだが、乱数を使ってどうやってその構造を生成すればいいだろう?」と悩んだら、まずはそのことだけを質問します。プログラム全体となると回答しにくくても小さな部分問題なら回答がつく可能性は非常に大きくなると思いますよ。

    キャンセル

  • 2017/03/05 22:03

    >KSwordOfHasteさん

    ありがとうございます。
    では質問を作り直したほうがよろしいでしょうか?

    キャンセル

  • 2017/03/05 22:41

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

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

    キャンセル

  • 2017/03/05 23:47

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

    キャンセル

  • 2017/03/06 00:01

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

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

    キャンセル

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

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

関連した質問

同じタグがついた質問を見る

  • Python

    7929questions

    Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。