simulated_annealing_tsp#

simulated_annealing_tsp(G, init_cycle, weight='weight', source=None, temp=100, move='1-1', max_iterations=10, N_inner=100, alpha=0.01, seed=None)[source]#

返回旅行商问题的近似解。

该函数使用模拟退火算法来近似通过所有节点的最小成本循环。从次优解开始，模拟退火算法会扰动该解，偶尔接受使解变得更差的改变，以逃离局部最优解。接受这类改变的概率随着迭代次数的增加而降低，以鼓励得到最优结果。简而言之，该函数返回一个从 source 开始的循环，使得总成本最小化，并返回该成本。

接受提议改变的概率与一个称为温度（temperature）的参数相关（退火过程在物理上有类似于钢铁冷却硬化的类比）。随着温度的降低，增加成本的移动的概率会下降。

Parameters:
GGraph

G 应该是一个完全加权图。 所有节点对之间的距离应该被包含。

init_cycle所有节点的列表或 “greedy”

初始解（一个通过所有节点并返回起点的循环）。 此参数没有默认值，以确保你仔细考虑它。 如果为 “greedy”，则使用 greedy_tsp(G, weight) 。 其他常见的起始循环是 list(G) + [next(iter(G))] 或执行 threshold_accepting_tsp 时的 simulated_annealing_tsp 的最终结果。

weight字符串, 可选 (默认=”weight”)

对应于边权重的边数据键。 如果任何边没有此属性，则权重设置为1。

source节点, 可选 (默认: 列表(G)中的第一个节点)

起始节点。如果为 None，则默认为 next(iter(G))

temp整数, 可选 (默认=100)

算法的温度参数。表示初始温度值。

move“1-1” 或 “1-0” 或 函数, 可选 (默认=”1-1”)

指示在寻找新试验解时使用何种移动的标志。 字符串表示两种特殊的内置移动：

  • “1-1”: 1-1 交换，即交换当前解中两个元素的位置。 调用的函数是 swap_two_nodes() 。 例如，如果在解 A = [3, 2, 1, 4, 3] 上应用 1-1 交换， 可以通过交换第1和第4个元素得到： A' = [3, 2, 4, 1, 3]

  • “1-0”: 1-0 交换，即将解中的一个节点移动到一个新位置。 调用的函数是 move_one_node() 。 例如，如果在解 A = [3, 2, 1, 4, 3] 上应用 1-0 交换， 可以将第4个元素移动到第2个位置： A' = [3, 4, 2, 1, 3]

你可以提供自己的函数来从一个解移动到邻近解。该函数必须以解和用于控制随机数生成的 seed 输入作为参数（参见这里的 seed 输入）。你的函数应保持解为一个循环，首尾节点相同且所有其他节点只出现一次。你的函数应返回新解。

max_iterations整数, 可选 (默认=10)

当外循环连续迭代次数达到此数值且最佳成本解没有任何变化时，算法宣告完成。

N_inner整数, 可选 (默认=100)

内循环的迭代次数。

alpha介于 (0, 1) 之间的浮点数, 可选 (默认=0.01)

外循环每次迭代中温度下降的百分比。

seed整数, random_state, 或 None (默认)

随机数生成状态的指示符。 参见 Randomness 。

Returns:
cycle节点列表

返回一个旅行商可以遵循的循环（节点列表），以最小化旅行的总权重。

Raises:
NetworkXError

如果 G 不是完全图，算法会引发异常。

Notes

模拟退火是一种元启发式局部搜索算法。该算法的主要特点是它接受甚至导致成本增加的解，以逃离低质量的局部最优解。

该算法需要一个初始解。如果没有提供，则由一个简单的贪心算法构造。在每次迭代中，算法会仔细选择一个邻近解。考虑当前解的成本 \(c(x)\) 和邻近解的成本 \(c(x')\)。如果 \(c(x') - c(x) <= 0\)，则邻近解成为下一次迭代的当前解。否则，算法以概率 \(p = exp - ([c(x') - c(x)] / temp)\) 接受邻近解。否则，当前解保持不变。

temp 是算法的参数，代表温度。

时间复杂度： 对于内循环的 \(N_i\) 次迭代和外循环的 \(N_o\) 次迭代，该算法的运行时间为 \(O(N_i * N_o * |V|)\)。

更多信息和算法的灵感来源请参见： http://en.wikipedia.org/wiki/Simulated_annealing

Examples

>>> from networkx.algorithms import approximation as approx
>>> G = nx.DiGraph()
>>> G.add_weighted_edges_from(
...     {
...         ("A", "B", 3),
...         ("A", "C", 17),
...         ("A", "D", 14),
...         ("B", "A", 3),
...         ("B", "C", 12),
...         ("B", "D", 16),
...         ("C", "A", 13),
...         ("C", "B", 12),
...         ("C", "D", 4),
...         ("D", "A", 14),
...         ("D", "B", 15),
...         ("D", "C", 2),
...     }
... )
>>> cycle = approx.simulated_annealing_tsp(G, "greedy", source="D")
>>> cost = sum(G[n][nbr]["weight"] for n, nbr in nx.utils.pairwise(cycle))
>>> cycle
['D', 'C', 'B', 'A', 'D']
>>> cost
31
>>> incycle = ["D", "B", "A", "C", "D"]
>>> cycle = approx.simulated_annealing_tsp(G, incycle, source="D")
>>> cost = sum(G[n][nbr]["weight"] for n, nbr in nx.utils.pairwise(cycle))
>>> cycle
['D', 'C', 'B', 'A', 'D']
>>> cost
31
On this page