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 开始的环路，其总成本最小化。它也返回该成本。

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

参数:
G图

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

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

初始解（一个经过所有节点并返回起点的环路）。此参数没有默认值，旨在提醒您考虑它。如果为“greedy”，则使用 greedy_tsp(G, weight)。其他常见的起始环路包括 list(G) + [next(iter(G))] 或执行 threshold_accepting_tsp 时 simulated_annealing_tsp 的最终结果。

weight字符串，可选 (默认为 “weight”)

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

source节点，可选 (默认为 list(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 交换，我们可以将第四个元素移动到第二个位置：A' = [3, 4, 2, 1, 3]

您也可以提供自己的函数来实现从一个解到邻居解的移动。该函数必须以当前解作为输入，并包含一个 seed 输入来控制随机数生成（参见此处的 seed 输入）。您的函数应保持解为一个环路，其中第一个节点和最后一个节点相同，并且所有其他节点出现一次。您的函数应返回新的解。

max_iterations整数，可选 (默认为 10)

当外部循环连续迭代此次数而最佳成本解没有发生任何变化时，声明完成。

N_inner整数，可选 (默认为 100)

内部循环的迭代次数。

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

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

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

随机数生成状态的指示器。参见随机性。

返回:
cycle节点列表

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

抛出:
NetworkXError

如果 G 不是完全图，算法会抛出异常。

注意

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

此算法需要一个初始解。如果未提供，则通过一个简单的贪婪算法构建。在每次迭代中，算法会审慎地选择一个邻居解。考虑当前解的成本 \(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

示例

>>> 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
在此页面上