基于蚁群算法的TSP求解：蚂蚁走遍全国旅游景点问题

Question

我正在寻找解决旅行商问题的和谐搜索算法的改编版本。我必须实现它并描述结果。我发现了一些解决方案，例如：http://www.academia.edu/6709329/Adaptation_of_the_Harmony_Search_Algorithm_to_solve_the_travelling_salesman_problem和http://www.jtacs.org/archive/2013/1/4/JTACS_2013_01_04.pdf，但这些解决方案效果不佳。我不能使用任何与其他算法的组合，它必须是清晰的和谐搜索（但修改当然是允许的）。我还在《音乐启发的和谐搜索算法：理论和应用》一书中寻找它，并在这里找到了描述，但这还不够。我想我已经尝试了所有可能性。如果有任何源/想法/示例可以展示如何做到这一点，我将非常感激。

- Łukasz Gil

---

鉴于负面的研究结果，您认为如何才能使用和谐搜索算法来解决旅行商问题并获得良好的结果呢？ - RBarryYoung

我第二个链接的PDF文件比较了几种TSP算法，其中HS算法的结果非常不错。 - Łukasz Gil

但是以你自己的话来说：“这些解决方案并不好，并且结果很差”。请解释一下，真正的问题是什么？ - RBarryYoung

我认为这些描述不够完整，非常简略，而且关键点没有被描述清楚。我已经根据上述链接实现了算法，但是我的结果很差，而出版物的作者却有好的结果。 - Łukasz Gil

Answer 1

我是一名计算机科学领域的研究员。自从我在会议演讲中第一次看到和谐搜索算法以来，我就对其产生了怀疑。事实证明，和谐搜索是进化策略的一个特例，这种方法是在60年代提出的。而且，尤其是该方法的“发明者”所报告的数字是不可信的。对我来说，和谐搜索是一种骗局方法，该方法的“发明者”很可能进行了学术欺诈。

简而言之：如果算法对您不起作用，很可能不是您的错。

来源：

1) 和谐搜索算法-我个人对这种“新型”元启发式方法的经验 2) 和谐搜索算法的严格分析：如何被“新颖”方法误导的研究社区（2010年发表的期刊文章）

3) 和谐搜索算法的批判性分析-如何不解决数独问题（2015年发表的期刊文章）

4) 整洁算法 - 和谐搜索

- Dennis Weyland

Answer 2

我已经实现了基于Harmony Search算法的复合Web服务选择，因此我将尝试创建整个模型。

步骤：

1）初始化问题和算法参数。

目标函数带有决策变量。对于 TSP ，决策变量应该是最短路径的 weight 。根据性能，可以设置其他 Harmony Search 的变量。

• 和声记忆大小（HMS），（样本解的数量）
• 考虑到和声记忆的比率（HMCR）
• 音高调整率（PAR）
• 终止准则（最大搜索次数）

这些变量必须实际测试，通过运行算法并使用不同值获取结果，以获得最佳性能。

2）初始化和声记忆。

在这一步中，您需要通过创建和声（随机解决方案）并存储它们来填充内存，以便稍后进行处理。

3）即兴创作新的和声。

创建新的和谐（解决方案）有两种选择。一种是从已经创建的和谐中选择一个，另一种是随机创建一个新的。这取决于和谐记忆考虑率（HMCR）。这是一个概率，你可以用它来选择上述任何一种方式。

4) 更新和谐记忆。

新创建的和谐（解决方案）必须与已经存在的进行比较。如果新的和谐（解决方案）更好，则将其保存在最差的和谐（解决方案）的位置（在这里比较了这些解决方案的路径总重量）。

5) 重复步骤3和4，直到满足终止条件。

检查是否满足终止条件。这个终止条件可以是迭代次数，或者达到一定的精度。

---

希望这个解决方案能够帮到你。

- Haris

---

嗨，哈里斯，我知道谐和搜索的工作原理，我已经实现了一个，但是经典的HS返回的结果不尽如人意。谐波改进非常缓慢。必须有更好的方法来选择新谐波的城市，我尝试过获取最近的邻居，但这导致算法得到了贫乏结果的局部最优解。必须有另一种方法来获得更好的谐波。针对其他问题的适应性是经典HS的修改形式，必须是TSP的良好形式。抱歉我的英语。 - Łukasz Gil