Pythonでは、遷移確率に従ってTSPのランダムパスを生成します

Question

移動販売員問題（TSP）については、Pythonでランダムツアーを生成したいと思います（nセットの各ノードは1回だけ訪れます） M [i、j]は、最短グローバルパスがノードiをノードjに接続する確率を含む状態遷移行列M（nxn）から導かれる。

誰でも、Pythonでそれを行う方法を知っていますか？ここでは一般的な方法やそれを行うモジュールについて尋ねています。

例：j =（i + 1）％nの場合はM [i、j] = 1、他の場合は0とします。生成される（常に0から始まる）すべてのパスは、（0,1,2、...、n）です。この行列を少し変更して、1.0を0.9に置き換え、M [i、i + 2]に0.1を代入すると、可能なパスは（0,2,3、..、n、1）です。いくつかの確率が0であるこの特定の例では、最後の移動が（ノードnからノード1へ）不可能であることを知っているので、確率は常に0より大きいと仮定することができる。

Answer 1

あなたが少しのコードを提供した場合にはるかに良い質問、特に質問が多くのステップを前にしているステップをターゲットにしているため）

セットアップはちょっと迷惑になるかもしれない（cvxpyといくつかのMIPソルバーは悪くありません;私はここでCBCを使用しています、cvxpyの代替案やsetup-docsのドキュメントを参照してください）。それは実際にテストされていません。この考え方は、ProbabilisticグラフィカルモデルのMAP計算にある程度基づいていますが、転送は数学的に間違っている可能性があります（保証はありません）。私たちの場合のオプト問題は制約に縛られているので、もっと難しくなります！

アイデア

有効溶液（有効なパス）を生成しながら、（これは大きな偏差がより重く罰せさ=正方形）の溶液パスの=一部使用先験的-確率を最大化する最適化問題を定式。

問題は非凸（私はわかりません）なので、全体的に最適な方法で解くのは実行不可能ですが、の相違点のヒューリスティックはです。

備考：このアプローチは、グローバル最適（非コンベックス最適化アルゴリズムを使用しているため完全に真ではない）を設計することによって設計されています。つまり、異なる手法を用いた複数のサンプリングは、この手法では自然ではありません（しかし、異なる開始点を持つDCCPルーチンを呼び出すと、高い確率で異なる解が得られます）。

備考2：非理論的アプローチ（非商用ソルバーの場合）ではパフォーマンスが非常に悪く、より理論的なアプローチになります。ここ実装

は、Python 3、numpyの、scipyのダウンロード（最短経路）、cvxpy（OPT-問題の定式化）とDCCP（cvxpy用凸関数の最適化拡張の差）

コード

を使用して、いくつかの実装であります

import numpy as np 
from scipy.sparse.csgraph import csgraph_from_dense, shortest_path 
from scipy.spatial import distance 
from cvxpy import * 
import dccp 
np.random.seed(1) 

""" Create random problem """ 
N = 10 
distances = np.random.rand(N, N)     # assymetric 

""" Calculate shortest paths """ 
csparse_distances = csgraph_from_dense(distances) 
shortest = shortest_path(csparse_distances)   # directed 

""" Calculate a-prori probabilities based on global shortest paths """ 
shortest_global = np.copy(shortest) 
for row in range(shortest_global.shape[0]): 
    # normalize sum to 1 
    row_sum = np.sum(shortest_global[row, :]) 
    shortest_global[row, :] /= row_sum 

""" Formulate MIQP problem """ 
# Based on: https://en.wikipedia.org/wiki/Travelling_salesman_problem 
#  and my example here: https://github.com/cvxgrp/cvxpy/blob/master/examples/tsp_mip.py#L16 

# Variables 
x = Bool(N, N)          # edge x,y in PATH 
u = Int(N)           # aux-var 

# Constraints 
constraints = [] 

for j in range(N):          # ingoing: exactly 1 
    indices = list(range(0, j)) + list(range(j + 1, N)) 
    constraints.append(sum_entries(x[indices, j]) == 1) 
for i in range(N): 
    indices = list(range(0, i)) + list(range(i + 1, N)) # outgoing: exactly 1 
    constraints.append(sum_entries(x[i, indices]) == 1) 

for i in range(1, N):        # subtour-elimination 
    for j in range(1, N): 
     if i != j: 
      constraints.append(u[i] - u[j] + N*x[i, j] <= N-1) 

# Objective 
obj = Maximize(sum_entries(square(mul_elemwise(shortest_global, x)))) 

# Solve 
prob = Problem(obj, constraints) 
print("problem is DCP: ", prob.is_dcp()) 
prob.solve(method='dccp', solver=CBC, ccp_times=10) # do not use default solver! 
# Remark: formulation above not accepted by CVX-ruleset 
#   -> need "difference of convex function"-extension 
#   -> heuristic (which is well-known for good behaviour)! 


""" Print solution """ 
print('Solution path matrix') 
print(np.round(x.value).astype('int')) 
print('A-priori probability matrix') 
print(np.round(shortest_global, 2)) 

出力

... 
... 
iteration= 1 cost value = 0.34508891154470694 tau = 0.005 
iteration= 2 cost value = 0.5092119781611304 tau = 0.006 
iteration= 3 cost value = 0.5092119781611304 tau = 0.0072 
Solution path matrix 
[[0 0 0 0 0 0 0 0 1 0] 
[1 0 0 0 0 0 0 0 0 0] 
[0 0 0 1 0 0 0 0 0 0] 
[0 0 0 0 1 0 0 0 0 0] 
[0 0 0 0 0 1 0 0 0 0] 
[0 0 0 0 0 0 0 0 0 1] 
[0 0 1 0 0 0 0 0 0 0] 
[0 0 0 0 0 0 1 0 0 0] 
[0 0 0 0 0 0 0 1 0 0] 
[0 1 0 0 0 0 0 0 0 0]] 
A-priori probability matrix 
[[ 0. 0.14 0. 0.24 0.11 0.07 0.07 0.03 0.13 0.21] 
[ 0.12 0. 0.09 0.22 0.01 0.17 0.13 0.11 0.06 0.07] 
[ 0.11 0.1 0. 0.27 0.08 0.12 0.05 0.02 0.1 0.15] 
[ 0.06 0.17 0.06 0. 0.15 0.12 0.11 0.09 0.01 0.23] 
[ 0.09 0.16 0.09 0.18 0. 0.13 0.13 0.11 0.05 0.05] 
[ 0.01 0.15 0.02 0.21 0.12 0. 0.08 0.05 0.15 0.22] 
[ 0.06 0.17 0.06 0.25 0.03 0.12 0. 0.09 0.11 0.11] 
[ 0.09 0.07 0.07 0.21 0.08 0.08 0.11 0. 0.14 0.15] 
[ 0.11 0.16 0.11 0.09 0.07 0.14 0.11 0.12 0. 0.1 ] 
[ 0.07 0.17 0.07 0.21 0.15 0.12 0.12 0.09 0. 0. ]] 

編集：

• 痛いが、何とかECOS_BBはまだ良いソルバー・セットアップをはるかに可能性があるを教えてくれるものを使用しているようです。