模拟退火算法的TSP问题

介绍组合优化是找到对于问题的一大组离散的可能的解决方案的最佳解决方案的过程中。这样的优化可以用来解决在资源管理，运营管理和质量控制的问题，例如路由，调度，填料，生产管理和资源分配。元启发式算法已被证明是良好的求解器用于组合优化问题，在某种程度上，它们提供了在一种有限（通常是短的）时良好最优解。的元启发式的例子有：模拟退火，禁忌搜索，和声搜索，分散搜索，遗传算法，蚁群优化，等等。在本文中，我们将讨论模拟退火及其在解决旅行商问题（TSP）的实现。背景模拟退火给出类似于此名称在热力学的“退火工艺”，特别是与金属的方法是加热，然后逐渐冷却，使其颗粒将达到最小能量状态（退火）。随后，其目的为模拟退火算法随机搜索一个目标函数（即主要特征的组合优化问题）。模拟退火算法的优势超过其他方法来避免陷入局部极小的能力。在这里，我们指的是该算法并不总是拒绝减小目标函数，但也变化，根据其概率函数，增加目标函数的变化： 收起|复制代码P = EXP（-Δf/ T）其中，T是所述控制参数（类似于温度）和Δf是在目标函数中的变化。该概率函数，绝对是波尔兹曼概率分布函数的导数。旅行商问题一位售货员要出差到N个城市（他应该经过每个城市）。我们怎样才能订购的城市，这样的业务员的旅程将是最短的？目标函数，以尽量减少在这里的旅程（所有城市之间的距离在指定顺序的总和）的长度。要开始解决这个问题;我们需要：配置设置：这是从1个城市到N的排列，在所有给定的订单。选择这些排列组合之间的最佳一个是我们的宗旨。重排策略：我们将遵循这里的战略替代路径的部分，并用随机种取代他们重新测试，如果这个修改一是优化与否。目标函数（这是最小化的目的）：这是所有的城市为特定的顺序之间的距离的总和。