threshold_accepting_tsp#

threshold_accepting_tsp(G, init_cycle, weight='weight', source=None, threshold=1, move='1-1', max_iterations=10, N_inner=100, alpha=0.1, 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))

threshold整型，可选 (默认值=1)

算法的阈值参数。它表示初始阈值的值。

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.1)

当至少有一个相邻解被接受时，阈值的降低百分比。如果内层循环没有接受任何移动，则阈值保持不变。

seed整型、random_state 或 None (默认值)

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

返回值：
cycle节点列表

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

抛出：
NetworkXError

如果 G 不完整，算法将抛出异常。

另请参阅

simulated_annealing_tsp

说明

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

该算法需要一个初始解。这个解可以通过一个简单的贪婪算法构建。在每次迭代中，它精心选择一个相邻解。考虑当前解的成本 \(c(x)\) 和相邻解的成本 \(c(x')\)。如果 \(c(x') - c(x) <= threshold\)，则相邻解成为下一迭代的当前解，其中 threshold 被称为阈值。

与模拟退火算法相比，阈值接受算法不接受质量非常低的解（由于存在阈值）。在模拟退火算法中，即使质量非常低的解也可以以概率 \(p\) 被接受。

时间复杂度：其运行时间为 \(O(m * n * |V|)\)，其中 \(m\) 和 \(n\) 分别是外层循环和内层循环的运行次数。

有关更多信息以及算法的灵感来源，请参阅：https://doi.org/10.1016/0021-9991(90)90201-B

示例

>>> 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.threshold_accepting_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.threshold_accepting_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
在本页