自己紹介
皆さんこんにちは。
山中に生息しているプログラマ＆SE、ほげふがーです。
計算量が普通なら爆発してしまうような最適化問題を、量子コンピュータではなく、非力なPCやRaspbe〇〇piで、無理やり解かせるのが大好きです。
気になったら、何かコメントいただけると嬉しいです(^^
(最新版)巡回セールスマン問題(TSP)高速近似アルゴリズム( Maximum Sum Initialize法)
github: https://github.com/TiresiasGit/trunk/tree/master/mmiopt
** 2020/05/04 msinit_shortest1.0.py…計算が実行されない問題を解決しました。**
msinit_longest1.0.py …正しい最適解が計算されない問題を解決しました。
^^^^^^^^^^^^これからは、msinitのファイルのみを保守します。
2020/01/26 msinit ver1.0を公開しました。
今までの自己最速記録に比べ、最大71倍高速化しました！
例：10000x10000のTSPにおいて
計算時間 50.9814秒→0.7162秒！
総距離 10417→10449 (わずかな悪化で済んでいる)
-
randarray4.0.py
ex: python msi_shortest4.0.py filename.npz txt 0.01 single no2-opt- csv_to_npz.py ex: python csv_to_npz.py InFile.csv OutFile.npz ─行列の対角要素は、全て0にして、csvカンマ区切りの表を作成してください。(excelなどで。) 一要素の入力可能な最大値は、9999999です。必要であれば、0~100の正規化をしてください。 csvファイルから、npzに変換して、下記のmsiinitにnpzを入力してください 。
msinit_shortest1.0.py
ex: python msi_longest4.0.py filename.npz txt 0.01 single no2-optmsiinit_longest1.0.py
ex: python randarray4.0.py 10000x10000.npz 10000 uint8
githubにアップしたもの
これです。
git clone https://github.com/TiresiasGit/trunk.git
2020/01/24 ver3.0を公開しました。
2.0をベースにファイル読み込みを、30倍～40倍高速化させました。
- randarray3.0.py
-ex: python randarray3.0.py 10000x10000.npz 100000
- mmiopt_shortest3.0.py
-ex.python mmiopt_shortest3.0.py 10000x10000.npz npz
- mmiopt_longestest3.0.py
-ex.python mmiopt_longest3.0.py 10000x10000.npz npz
- npz_reader.py
-ex: python npz_reader.py ansnode.npz
※savez_compressed()おそるべし.......
2020/01/20 ver2.0を公開しました。
解の質を向上させました。
- mmiopt_shortest2.0.py
- mmiopt_longest2.0.py
※ver1.0に比べ、計算時間は、160～170％ほどになり、長くなっておりますが、10000x10000の1～100の乱数行列ならば、-117ほど短くなります！(付録A参照)
https://github.com/TiresiasGit/trunk/tree/master/mmiopt
mmiopt_shortest1.0.py ←Maximum Mean Initializeの後に2-optを適用
「最短パス」を近似的に求めます。
mmiopt_longest1.0.py ←Minimum Mean Initializeの後に2-opt法を適用
逆に「最長パス」を近似的に求めます。
(クリティカルパスのようなものが求まる？)
Maximum Mean と選択論理のすべてを、
「逆」に設定して作ってあります。
csv_loader.py ←実験用に使ってください。
(mmiopt_longest,mmiopt_shortestのcsv出力を、
別のプログラムに配列で渡したい場合に、
中の関数を切り取って使ってみてください。)
randarray.py ←実験用に使ってください。
(TSPの例題を乱数から作ります。
双方向の正方行列のグラフです。)
行方向：元ノード 列方向：先ノード
要素：元ノード→先ノード のエッジ長
社会貢献したいので、MITライセンスにしています。自由に使って、さらに改良してくださって構いません。
なお、筆者はpythonを仕事で使ったことがありません（笑）
完全に趣味でやってます。
巡回セールスマン問題の概要
各都市がN個あったとする。全都市を担当しているセールスマンには、「それぞれの都市を必ず1回は営業せよ！」という過酷なノルマを課せられている。どこから、どのような順路で回っていけば、このセールスマンは、過労死せず、最短で営業できるでしょうか？という問題です。
この問題が面白いところは、計算量は、総当たり法だと、
N!通り
あること。
考えてみてほしい。N(ノード数)が4桁になる頃には、天文学的な数になっている。
(1000!=402387260077093773543702433923×10^2538>>10の68乗=1無量大数。 無理だろ..これ....)
この総当たり計算を、自宅のPCで解かせるとどうなってしまうか？
おそらく、実行してしまったが最後、1か月ぐらい待てど暮らせど、終わらないだろう。（頑張れば終わるかもしれないが、かかる電気代がやばい
最悪、問題によっては数億年かけても終わらないかもしれない。
このTSP(traveling salesman problem)は組み合わせ最適化問題とも呼ばれています。
※詳しくは、Wikipedia先生を見てね。↓
https://ja.wikipedia.org/wiki/%E5%B7%A1%E5%9B%9E%E3%82%BB%E3%83%BC%E3%83%AB%E3%82%B9%E3%83%9E%E3%83%B3%E5%95%8F%E9%A1%8C
まず、巡回セールスマン問題は、初手の選び方が重要です。
なぜかというと、そこから最小値を選択して、ノードを次々とたどるような方策(常套手段)を取って、さらに2-optなどで最適化をしても、限界があるからです。
そこで、「よい初手の選び方」とは、なんだろうと思い至ったのです。
Maximum Mean Initialize - 2-opt法とは？
平均エッジ長(Mean)が最大(Maximum)の分布を持つノードを、初手に選び(Initializeする)最小値を残ったノードから次々と探索して辿っていきながら、解となったノードを配列に記録し、その求まった解に対して、2-opt法(従来法)を適用する方策です。※筆者が勝手に命名しました。
↓戯言は読み飛ばして構いません（笑）。
2019年11月に、筆者が朝、会社の駐車場を歩いているときのことでした。リラックスしながら歩いていると、アイディアが降ってくるときありますよね？(私だけでしょうか...？)
ふと、いつも通り、巡回セールスマン問題を解くための、いろんなアルゴリズムを脳内で人力シミュレートしているさなか、ふと気づいてしまったのです。
元ノード エッジ 先ノード
〇 －－－> 〇
「距離の長いエッジを多く持つ元ノード(後半で悪さをするノード)を、初手として選び、刈り取ってしまえば、選択可能なエッジ-先ノードのペアが後半絞られていく(1都市1回しか通れない)そのさなかでも、最小値として選ばれたエッジが、期待外れに長いエッジとなってしまう確率を低くすることができるのでは...！？おまけに、その分布は、元ノードの持つエッジの平均長で比較できる！これなら非力なPCでも高速計算が可能だ..!!!」
簡略化のため、2つのノードを切り取って説明します。
A.エッジの平均値の高いノード
エッジ長
Λ
｜ ｜｜｜｜｜｜｜｜｜
｜ ｜｜｜｜｜｜｜｜｜
｜ ｜｜｜｜｜｜｜｜｜
｜ ｜｜｜｜｜｜｜｜｜｜
〇‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾＞先ノードの番号
^最小値の探索で、よい解として選択される可能性のあるエッジ
B.エッジの平均値の低いノード
エッジ長
Λ
｜ ｜｜
｜ ｜｜
｜ ｜｜
｜ ｜｜｜｜｜｜｜｜｜｜
〇‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾＞先ノードの番号
^^^^^^^^^^^最小値探索で、よい解として選択される可能性のあるエッジの集合
↑みなさんなら、どちらを初手に選べばよいか、わかりますか？
B.を初手で選んでしまうと、後半において、Aの分布のようなノードが残ります。A.には、長いエッジが含まれているため、最小値を探索するアルゴリズムを実装している場合、先にどこかのノードが短いノードを取ってしまうかもしれません。そうなると、残るは長いノードだけです。悲しいことに、その長いエッジの中から、最小値を探し、選択せざるを得ません。
逆に、A.を初手に選べば、(それなりによい最小値が1つでも含まれることを期待して)残るは、良解となる可能性を持ったエッジを多量に含むB.が残るわけです。こうなれば、確率的に良解のエッジが残る確率が高くなります。
各ノードのもつエッジ長の平均値の計算量としてはO(n^2)です。(n:ノード数)
そこから、最大値を求める時は最悪O(n)かかります。
あとは、そうして求めた初期ノード(行番号)の中から、最小値を見つける→最小値を持つ列番号のノードがわかる→そのノードから最小値を見つける→最小値を持つ列番号のノードがわかる。……をノード数分繰り返す(最悪O(n^2))
最後にそうして得られた解の順路に対し、従来の2-opt法(最悪、約O(n^2/2))を適用し、解の長さだけ、比較&ノード交換して、改善すれば、完了です。
よって、全体の最悪計算量のオーダーはO(n^2)＋O(n)＋O(n^2)＋約O(n^2/2)= O(kn^2)となります。ある程度高速に解けそうですね。
↓gitに上げてるソースコード、ここにも書いておきます。
#coding: UTF-8
# Maximum Mean Initialize and 2-opt.
# -> MMI-OPT
# this version is approximataly solve "shortest path" from TSP Input.
#
# This argolithm developed for solve TSP approximately fast.
# (TSP=Traveling Salesman Problem. )
#
# Confirmed operating environment.
# CentOS Linux release 7.2.1511 (Core)
# Python 2.7.5
# numpy 1.16.5
#
# How to use this software from command line?
# > python mmiopt_shortest3.0.py filename npz
# ^^^A solution is output as .npz
# ^^^^^^^^int or float valuses square matrix
# of comma delimitered TSP Input file.
# type
# Input:filename int or float
# Output:ansedge.npz or txt int
# ansnode.npz or txt int
# accumulation.npz or txt float
# developer "Ryota Tanaka"
import numpy as np
import csv
import sys
import time
def main():
argv = sys.argv
if len(argv) != 3:
print("File name may not be specified,or may contain extra options.")
exit()
print("start load file!")
data = np.load(argv[1])['array_']
print("end load file!")
start = time.time()
searched = [data.shape[1]]
if data.shape[0] != data.shape[1]:
print("Please check if it is a square matrix.")
#array init
flags = [0] * data.shape[0]
ansnode = np.array([],dtype='int32')
ansedge = np.array([])
accumulation = 0 #累積距離の初期化
print("start max mean initalize.")
index,dataeva = calc_maxevaindex(data)
flags[index] = 1 #訪問済みにする
ansnode=np.append(ansnode,int(index)) #答えとなるノード番号をキューに入れる
num = data.shape[0] - 1
while num > 0:
beforeindex = index #ひとつ前のindexとして保持する
indexes = [i for i, x in enumerate(data[index]) if 0 == flags[i]] #自分と訪問済みを除外したインデックスの集合を得る
indexes = np.array(indexes)#ndarrayに変換
xmin = min(data[index,indexes])
#minindex = np.argmin(data[index,indexes])
minindexes = [i for i,x in enumerate(data[index,indexes]) if x == xmin] #最小値のインデックスの集合を得る
if len(minindexes) > 1:
index = np.argmin(dataeva[indexes[minindexes]])#最小の評価を持つノードを選択する
index = indexes[minindexes[index]] #最小値の行(移動先ノード)の中で評価値が最高のノード(スカラのノード番号)を取り出す
else:
index = indexes[minindexes[0]]
#index = indexes[minindex]
flags[index] = 1 #訪問済みにする
ansnode=np.append(ansnode,int(index)) #答えとなるノード番号をキューに入れる
accumulation += data[beforeindex,index] #累積距離に加算する
num-=1
#print(num)
for i in range(len(ansnode)-1):
ansedge = np.append(ansedge,data[int(ansnode[i]),int(ansnode[i + 1])])
print("end max mean initialize.")
#2-opt法による解のworst除去
print("start 2-opt")
itr = 1
while itr > 0 :
num = data.shape[0] - 1
tempedge0=np.zeros(4)#従来のエッジ長集合
tempedge1=np.zeros(4)#swap後エッジ長集合
templist=np.zeros(6)
while num > 0:
worst_node_i = np.argmax(ansedge)#解の経路から、最長のエッジを出す
#次のループのために、現在見つかった最大値の要素を削除
ansedge = np.delete(ansedge,worst_node_i,axis=0)
worst_minnode=np.argmin(data[int(ansnode[worst_node_i])])
#◆交換なし
#交換元
worst_minnode_i_list=np.where(ansnode-worst_minnode==0)#array[]->intに変換は[0]を参照すればよい
worst_minnode_i=worst_minnode_i_list[0]
#print("worst_minnode_i");#print(worst_minnode_i)
worst_node_i_next = worst_node_i+1
templist[1]=ansnode[worst_minnode_i]
if worst_minnode_i-1 > 0 :
templist[0]=ansnode[worst_minnode_i-1]
tempedge0[0]=data[int(templist[0]),int(templist[1])]
if worst_minnode_i+1 < len(ansnode)-1 :
templist[2]=ansnode[worst_minnode_i+1]
tempedge0[1]=data[int(templist[1]),int(templist[2])]
#交換先
templist[4]=ansnode[worst_node_i_next]
if worst_node_i-1 > 0 :
templist[3]=ansnode[worst_node_i_next-1]
tempedge0[2]=data[int(templist[3]),int(templist[4])]
if worst_node_i+1 < len(ansnode)-1 :
templist[5]=ansnode[worst_node_i_next+1]
tempedge0[3]=data[int(templist[4]),int(templist[5])]
#◆交換した場合
#交換元
templist[1]=ansnode[worst_node_i_next]#swaped
if worst_minnode_i-1 > 0 :
templist[0]=ansnode[worst_minnode_i-1]
tempedge1[0]=data[int(templist[0]),int(templist[1])]
if worst_minnode_i+1 < len(ansnode)-1 :
templist[2]=ansnode[worst_minnode_i+1]
tempedge1[1]=data[int(templist[1]),int(templist[2])]
#交換先
templist[4]=ansnode[worst_minnode_i]#swaped
if worst_node_i-1 > 0 :
templist[3]=ansnode[worst_node_i_next-1]
tempedge1[2]=data[int(templist[3]),int(templist[4])]
if worst_node_i+1 < len(ansnode)-1 :
templist[5]=ansnode[worst_node_i_next+1]
tempedge1[3]=data[int(templist[4]),int(templist[5])]
#print("sum(tempedge0)");#print(np.sum(tempedge0))
#print("sum(tempedge1)");#print(np.sum(tempedge1))
#距離判定
if(np.sum(tempedge1)<np.sum(tempedge0)):
#node swap
tempnode= ansnode[worst_node_i_next]
ansnode[worst_node_i_next]=ansnode[worst_minnode_i]
ansnode[worst_minnode_i]=tempnode
#decrement
num-=1
#while num end
print("end 2-opt")
print("search end ansnode->",ansnode)
ansedge =[]
for i in range(len(ansnode)-1):
ansedge = np.append(ansedge,data[int(ansnode[i]),int(ansnode[i + 1])])
accumulation=np.sum(ansedge)
print("Accumulation Distance = ",accumulation)
print("ansedge = ",ansedge)
itr-=1
if argv[2] == 'txt':
np.savetxt("ansnode.txt", ansnode,fmt ='%d')
np.savetxt("ansedge.txt", ansedge,fmt ='%d')
np.savetxt("accumulation.txt", [accumulation],fmt ='%f')
elif argv[2] == 'npz':
np.savez_compressed("ansnode.npz", array_=ansnode)
np.savez_compressed("ansedge.npz", array_=ansedge)
np.savez_compressed("accumulation.npz", array_=accumulation)
else:
print("!none output files!")
t = time.time() - start
print("calculation elapsed time="+str(t))
#while itr end
def calc_maxevaindex(data):
dataeva = np.mean(data,axis=1)
evamax_i = dataeva.argmax()
return evamax_i,dataeva
if __name__ == "__main__":
try:
start = time.time()
main() #main処理
t = time.time() - start
print("total elapsed time="+str(t))
#errorハンドリング
except IOError as error:
print("Make sure the files are on the same level")
OS：centos7.2 virtual Box上の仮想環境
仮想論理cpuコア数合計:16コア
実行結果：(入力した10000x10000.csvは、エッジ長の平均値に影響しないよう、対角要素をすべて0に初期化しています。)
[root mmiopt]# python mmiopt_shortest3.0.py 10000x10000bin.npz txt
start load file!
end load file!
start max mean initalize.
end max mean initialize.
start 2-opt
end 2-opt
('search end ansnode->', array([2563, 8128, 5845, ..., 7390, 5044, 2855]))
('Accumulation Distance = ', 10405.0)
('ansedge = ', array([ 1., 1., 1., ..., 64., 16., 20.]))
calculation elapsed time=30.0312879086
total elapsed time=32.3572869301
私の環境では、10000ノードx10000ノード(エッジ長は1~100の整数の一様分布乱数)のtspを、演算処理だけなら、30.03秒ほどで解きました。早い方かな？
(この問題を解く速度は、問題の複雑度にかなり依存するようです。)
ファイルの読み込み時間は、
ver2.0だとおよそ97秒
ver3.0にしてから、ファイルをnp.savez_compressed()のnpz拡張子のファイルでバイナリx圧縮にすることにし、そのファイルをnp.load()すると
32.35-30.03=2.32秒！
97秒/2.3秒=およそ42.1倍速 ...
savez_compressed()さん....あなたが神でしたか..!..m(_ _)m
※上記の測定環境は仮想マシンがDIMM上にロードされている状態で実施しました。HDDとファイルをやり取りしたわけではないのでご注意ください。
また、argminの探索を1つでも見つけたら、打ち切る方法にしたところ、なぜか計算の終わる時間が早くなるだけでなく、解が良くなりました...
ノードを後半追っていく中で、無理にMaximum Meanを適用して判断すべきではないのかも...
↑問題の規模や構造によりけりで、どちらが適切かはわかりませんが、途中の場合（複数の最小エッジがかかった場合）の判断はMinimum Meanにすると、よい結果が出るようです。（一番下の付録Aを参照。）
こっちは、最長解を求めるverの計算結果です。(判定論理がすべてshortestと逆にしてます。githubにあります。)
[root mmiopt]# python mmiopt_longest3.0.py 10000x10000bin.npz txt
start load file!
end load file!
start min mean initalize.
end min mean initialize.
start 2-opt
end 2-opt
('search end ansnode->', array([5845, 4865, 669, ..., 7760, 8706, 7255]))
('Accumulation Distance = ', 989456.0)
('ansedge = ', array([99., 99., 99., ..., 75., 83., 70.]))
↑989456.0と、最長な感じになってますね。(^^)b
初手のノードを選ぶのに使われる「元ノードのエッジの平均値を求める」
は、すべてのノードにおいて、ベクトル化処理が可能です。
そこをGPGPUやFPGAなどのように、並列演算に特化したHW用に改造することにより、さらなる高速化が見込めます。
（現状、私の実装では、numpyしか使っていません。)
コーディングのペースは私は速くないので、居てもたっても居られない方が、もしいらっしゃいましたら、先にGPGPU対応版を作ってアップしてもらっても構いません（笑）。ひょっとしたら、一瞬で解けるようなコードができるかもしれませんね。
いずれ並列演算版を作るつもりですが、
2020/01/12追記：
ネットで調べたところ、numpy自体が、CPUコアを並列に使っているとのことでした。すでに並列計算版でした。
蛇足ですが、
from multiprocessing import Pool
:
def multimean(data):
return(np.mean(data))
def calc_maxevaindex(data):
p = Pool(int(2))
dataeva = p.map(multimean,data)
に実験用に改造し、高速化するかどうかも確認しましたが、逆に遅くなりました...
numpy単体でmeanの計算をするのが一番良いようです。
世の中の動き
巡回セールスマン問題という強大な敵を打ち倒す力として、最近できた武器の1つに量子コンピュータ系のアルゴリズムを搭載したハードウェアがあります。
・デジタルアニーラ
https://japan.cnet.com/extra/fujitsu_201803/35115699/
これは基本的には総当たりではなく、確率的に収束しやすくする解法を使用しています。(ざっくりいうとそんな感じ)
最近では日立さんの2部グラフを用いたアルゴリズムもhotなようです。
・MA(モーメンタム・アニーリング)
https://www.itmedia.co.jp/news/articles/1908/30/news130.html
筆者の思い
しかし、そんなハードウェアは、やっぱり個人では入手しづらいんでしょ...
サブスクリプションに参加しないと、使えない。と言って、結局諦めているのが現状じゃないでしょうか？
やっぱり大きな企業しか、使えないんだな.....
いな！(｀・ω・´)
数理最適化は個人で使えてこそ、真価を発揮するものだと思う！
いろんな人が抱えている身近な課題を、自己解決するために、そういた技術はあるんじゃないのか？と。
そんな対抗心から、このアルゴリズムを、githubで公開しようと思い至りました。
気になったら、何かコメントいただけると嬉しいです(^^
良かったら、ついでに私の過去に作ったアプリも見ていってください↓
iOSアプリ
HeartRepo-ハートレポ
https://apps.apple.com/jp/app/heartrepo-%E3%83%8F%E3%83%BC%E3%83%88%E3%83%AC%E3%83%9D/id1459032969
(精神状態からサプリメントをレコメンドしてくれます。)
付録A
◆1000x1000ノード 計算結果
最小が複数あった場合の判断論理なし（先に見つかったノード）
[root python-prog]# python mmiopt_shortest1.0.py 1000x1000.csv
start load file!
end load file!
start max mean initalize.
end max mean initialize.
start 2-opt
end 2-opt
('search end anslist->', array([854, 122, 108, 36, 167, 13, 84, 45, 30, 20, 164, 78, 5,
139, 33, 55, 94, 198, 58, 39, 56, 1, 90, 67, 254, 12,
：
948, 995, 987, 920, 835, 996, 901, 931, 999, 868, 917, 989, 969,
916, 940, 890, 859, 896, 782, 927, 892, 877, 978, 910, 991]))
('Accumulation Distance = ', 1464.0)
('ansedge = ', array([ 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
：
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 2.,
1., 1., 1., 1., 1., 1., 1., 2., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 2., 1., 1., 2., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 2.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 2., 1.,
1., 1., 1., 1., 3., 1., 1., 1., 1., 2., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 2., 1., 1., 1., 1.,
1., 1., 2., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 2., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 3., 2., 1., 1., 2., 1., 1., 1., 1., 1., 2.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 2., 1., 1., 1., 1., 1.,
1., 1., 2., 1., 1., 1., 1., 1., 1., 2., 1., 1., 1.,
2., 1., 1., 1., 1., 1., 1., 1., 3., 1., 1., 1., 1.,
2., 1., 5., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 2., 1., 1., 1., 2., 1., 2., 1., 1., 1., 2.,
1., 1., 1., 1., 2., 1., 1., 2., 1., 3., 2., 1., 2.,
1., 1., 1., 2., 1., 1., 1., 1., 1., 1., 2., 1., 3.,
1., 1., 1., 1., 1., 1., 1., 3., 1., 2., 3., 1., 1.,
1., 1., 1., 1., 2., 1., 2., 2., 1., 1., 2., 1., 1.,
1., 2., 1., 1., 1., 1., 2., 1., 1., 1., 1., 4., 1.,
3., 1., 2., 1., 4., 1., 2., 1., 1., 2., 3., 3., 2.,
4., 3., 2., 3., 1., 9., 1., 1., 2., 1., 7., 1., 2.,
2., 4., 2., 3., 1., 3., 2., 4., 1., 1., 1., 5., 1.,
3., 3., 13., 2., 3., 4., 2., 10., 1., 7., 7., 9., 12.,
2., 9., 5., 3., 16., 3., 2., 1., 5., 16., 3., 12., 4.,
5., 24., 1., 2., 3., 2., 10., 15., 87., 58., 28.]))
calculation elapsed time=0.286923885345
total elapsed time=1.15214395523
[root python-prog]#
・最小エッジが複数あった場合、判断論理をevaが「最小」のノードにした場合
[root python-prog]# python mmiopt_shortest2.0.py 1000x1000.csv
start load file!
end load file!
start max mean initalize.
end max mean initialize.
start 2-opt
end 2-opt
('search end anslist->', array([854, 587, 908, 909, 324, 897, 72, 5, 417, 596, 461, 896, 370,
388, 349, 402, 467, 644, 66, 845, 910, 138, 413, 378, 993, 806,
：
447, 496, 697, 23, 362, 814, 564, 610, 535, 702, 526, 98, 425,
7, 380, 658, 934, 364, 365, 763, 986, 940, 442, 669, 793]))
('Accumulation Distance = ', 1306.0)
('ansedge = ', array([ 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
：
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 2., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 2., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
2., 1., 2., 1., 1., 1., 1., 1., 1., 2., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 2.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 2., 1., 1.,
1., 1., 1., 1., 2., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 2., 1., 2., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 2., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 2., 2., 1., 1., 1., 4., 2., 1., 1.,
2., 1., 1., 1., 1., 1., 1., 1., 2., 1., 1., 2., 1.,
1., 1., 2., 1., 1., 1., 1., 1., 1., 4., 1., 2., 1.,
4., 2., 2., 1., 2., 1., 1., 2., 1., 1., 2., 2., 1.,
2., 3., 2., 1., 2., 3., 1., 1., 1., 1., 1., 1., 1.,
4., 1., 3., 1., 1., 2., 1., 1., 1., 1., 1., 1., 1.,
2., 2., 2., 2., 1., 1., 1., 5., 1., 1., 2., 1., 2.,
1., 1., 1., 1., 3., 2., 3., 2., 4., 1., 1., 6., 2.,
1., 2., 6., 2., 5., 1., 1., 3., 2., 5., 1., 1., 1.,
4., 1., 3., 1., 1., 1., 4., 11., 5., 8., 6., 6., 2.,
1., 5., 3., 4., 4., 2., 6., 1., 2., 1., 2., 1., 4.,
5., 1., 1., 8., 2., 2., 4., 6., 4., 2., 1., 3., 4.,
9., 1., 7., 17., 3., 7., 5., 12., 31., 24., 19.]))
calculation elapsed time=0.406162023544
total elapsed time=1.28471302986
[root python-prog]#
↑最後当たりのエッジの分布がいい感じに、判断なしに比べると、低くなっていますね
・最小エッジが複数あった場合、判断論理をevaが「最大」のノードにした場合
[root python-prog]# python mmiopt_shortest1.6.py 1000x1000.csv
start load file!
end load file!
start max mean initalize.
end max mean initialize.
start 2-opt
end 2-opt
('search end anslist->', array([854, 561, 628, 180, 340, 60, 256, 153, 981, 97, 850, 52, 21,
815, 23, 641, 435, 314, 629, 9, 722, 315, 562, 135, 646, 462,
：
919, 320, 422, 392, 405, 459, 240, 99, 122, 801, 645, 424, 170,
785, 662, 408, 418, 909, 587, 915, 769, 534, 636, 90, 577]))
('Accumulation Distance = ', 1334.0)
('ansedge = ', array([ 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
：
1., 1., 1., 1., 2., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 2., 1., 1., 2.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 2., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 3., 1., 1., 1., 1.,
2., 1., 1., 1., 1., 1., 1., 1., 2., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 2., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 2., 1., 1., 1., 2., 1., 1.,
1., 1., 2., 1., 2., 1., 1., 1., 2., 1., 1., 1., 1.,
1., 1., 1., 1., 2., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
2., 1., 1., 1., 1., 1., 1., 1., 1., 2., 1., 1., 1.,
1., 1., 2., 1., 1., 1., 2., 1., 1., 1., 1., 2., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
1., 2., 1., 2., 1., 1., 1., 1., 4., 1., 1., 2., 2.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 2., 2., 1., 1.,
2., 1., 1., 2., 2., 1., 1., 1., 2., 1., 1., 1., 1.,
1., 1., 1., 1., 1., 1., 1., 1., 1., 3., 1., 1., 1.,
1., 2., 1., 1., 1., 1., 1., 1., 1., 2., 1., 1., 2.,
1., 1., 3., 1., 1., 1., 1., 1., 2., 1., 1., 1., 4.,
1., 2., 1., 1., 1., 1., 1., 4., 2., 1., 1., 1., 1.,
2., 2., 1., 1., 1., 2., 1., 1., 2., 4., 2., 1., 1.,
1., 1., 1., 1., 2., 2., 1., 1., 1., 3., 5., 5., 1.,
2., 1., 4., 1., 1., 3., 2., 1., 3., 2., 1., 2., 2.,
1., 1., 4., 1., 5., 5., 1., 2., 7., 1., 5., 3., 1.,
5., 6., 4., 3., 1., 3., 6., 2., 3., 9., 3., 5., 11.,
7., 5., 4., 2., 12., 7., 44., 43., 10., 38., 21.]))
calculation elapsed time=0.410298109055
total elapsed time=1.24395895004
[root python-prog]#
↑いまいち。
◆10000x1000ノード 計算結果
最小エッジが複数あった場合の判断論理なし（先に見つかったノード）
[root python-prog]# python mmiopt_shortest1.0.py 10000x10000
start load file!
end load file!
start max mean initalize.
end max mean initialize.
start 2-opt
end 2-opt
('search end anslist->', array([ 890, 55, 17, ..., 9789, 9987, 9917]))
('Accumulation Distance = ', 10518.0)
('ansedge = ', array([ 1., 1., 1., ..., 4., 42., 39.]))
calculation elapsed time=18.6911308765
total elapsed time=116.08887291
・最小エッジが複数あった場合、判断論理をevaが「最小」のノードにした場合
[root python-prog]# python mmiopt_shortest2.0.py 10000x10000
start load file!
end load file!
start max mean initalize.
end max mean initialize.
start 2-opt
end 2-opt
('search end anslist->', array([ 890, 4080, 9216, ..., 2573, 1969, 2473]))
('Accumulation Distance = ', 10401.0)
('ansedge = ', array([ 1., 1., 1., ..., 33., 70., 55.]))
calculation elapsed time=30.9934711456
total elapsed time=128.27948904
・最小エッジが複数あった場合、判断論理をevaが「最大」のノードにした場合
[root python-prog]# python mmiopt_shortest1.6.py 10000x10000
start load file!
end load file!
start max mean initalize.
end max mean initialize.
start 2-opt
end 2-opt
('search end anslist->', array([ 890, 321, 5463, ..., 6841, 9386, 9376]))
('Accumulation Distance = ', 10558.0)
('ansedge = ', array([ 1., 1., 1., ..., 53., 48., 21.]))
calculation elapsed time=31.5126929283
total elapsed time=129.637353897
[root python-prog]#