遗传算法和蚁群优化算法
4.78/5 (102投票s)
遗传算法和蚁群优化算法
引言
我最近对遗传算法和蚁群优化技术产生了浓厚的兴趣。我决心编写一个完整的程序来演示这两种技术。特别是，我想比较这两种方法在解决旅行商问题（TSP）方面的效率。
旅行商问题
Buckland (2002, pp. 118) 简洁地总结了这个问题：“给定一系列城市，旅行商必须确定一条最短的路线，以便他能且仅能一次性访问每个城市，然后返回起点。”
他接着解释说，这是数学家称为NP-Complete问题的一个例子。随着城市数量的增加，解决问题所需的计算能力呈指数级增长。一台计算机上解决五十个城市TSP的算法，为了增加额外的十个城市，需要千倍的计算机能力。下表展示了这个问题
显然，对于大量的城市，“蛮力”方法是不可行的，如果想找到这个问题的解决方案，就需要采用其他算法。
背景
算法详解
遗传算法
该算法包含以下基本步骤：
- 初始化：随机创建染色体。此时，种群多样化非常重要。否则，算法可能无法产生好的解决方案。
- 评估：对每个染色体在解决手头问题方面的表现进行评分。为每个染色体分配一个适应度值。
- 选择：根据适应度，选择最适应的染色体进行繁殖到下一代。
- 重组：将单个染色体和染色体对进行重组、修改，然后放回种群。
我将不详细讨论遗传算法的细节，因为这些内容在其他地方有更好的解释，但我将讨论用于生成有效交叉算子和轮盘赌选择的机制。每个染色体都编码为一个可能的路径。例如，一个包含五个城市的路径可能编码为3,4,0,1,2。TSP的一个难点是简单的交叉操作无法奏效。考虑以下情况，交叉发生在位置3。
| 父代 1 | 1 2 3 4 5 |
| 父代 2 | 3 5 2 1 4 |
| 子代 1 | 1 2 3 1 4 |
| 子代 2 | 3 5 2 4 5 |
这里出现的问题是，子代1两次访问了城市1，这是不允许的，而子代2根本没有访问城市1。必须使用一种编码方式来确保只生成有效的路径。一个众所周知且可能是最容易理解的交叉算子称为部分匹配交叉。Buckland (2002, pp. 130-132) 解释了这项技术如下：
选择一个交叉区域。
Parent 1: 12x34x5 Parent 2: 35x21x4建立以下映射关系。
3 -> 2 4 -> 1现在我们逐个遍历每个父代基因，并在遇到在上述映射中出现的基因时进行交换。
第一次迭代（映射3与2）
Child 1: 13245 Child 2: 25314第二次迭代（映射4与1）
Child 1: 43215 Child 2: 25341最终交叉的基因是有效的排列，没有重复。
轮盘赌选择是一种根据适应度比例从染色体种群中选择成员的技术。Buckland 形象地描述道：“想象一下，种群的总适应度得分被表示为一个饼图或轮盘。现在，您为种群中的每个成员分配一个轮盘的切片。切片的大小与该染色体的适应度得分成正比：成员越适应，得到的饼图切片就越大。然后，要选择一个染色体，您只需旋转轮盘，投入小球，然后抓住小球停止的那个染色体。” Buckland (2002, pp. 100)
蚁群算法
该算法的灵感来源于对真实蚂蚁的观察。单独来看，每只蚂蚁都是盲目的、脆弱的，几乎微不足道。然而，通过相互协作，蚁群表现出复杂的行为。其中一项能力是找到通往食物源或其他有趣地标的最短路径。这是通过释放一种称为“信息素”的特殊化学物质来实现的。随着越来越多的蚂蚁使用某条特定的路径，该路径上的信息素浓度会增加，从而吸引更多的蚂蚁。在我们的例子中，一只人工蚂蚁被随机放置在每个城市，并在每次迭代中选择下一个要去的城市。这个选择由以下公式决定，正如 Dorigo (1997) 所述：
位于城市i的每只蚂蚁会根据以下概率跳到尚未访问过的城市j之一：
其中
表示蚂蚁k在城市i前往城市j的概率。
表示蚂蚁k在城市i尚未访问的城市集合。
是信息素轨迹的相对重要性。
是城市之间距离的相对重要性。
因此，选择某个城市的概率取决于该城市有多近以及该路径上已存在多少信息素。通过调整 和 参数，可以确定其中哪个具有更大的权重。一旦完成一条路径（即蚂蚁一次性访问了所有城市），就会计算边上的信息素蒸发。然后，每只蚂蚁根据以下公式（Dorigo 1991）计算出的数量，在完成的路径上沉积信息素：
如果
，其中
将城市i和j之间的边的信息素浓度乘以p(
), 称为“蒸发常数”。该值可以在0到1之间设置。蒸发常数越低，信息素蒸发越快。 RHO 是蚂蚁k在边上沉积的信息素量，由
定义，它是该蚂蚁创建的路径长度。直观地说，短路径会在边上产生更高水平的信息素。
快速用户手册
该应用程序的核心是用于解决旅行商问题的两种算法。通过从主框架的工具栏中选择，可以将每种算法引入视图。视图是呈现给用户的窗口。遗传算法视图如下所示：
每个视图分为两个水平部分。
- 上半部分显示了每种算法当前性能的图形视图。
- 下半部分显示了当前解决方案与已知最佳解决方案的图表。在大多数TSP演示中，城市是随机放置的。我选择以圆形分布城市。这使得计算城市间最短路径变得容易，并且可以直观地评估算法与最优解的差距。
模拟由控制按钮控制
每个按钮都是不言自明的。Start 按钮用于启动应用程序，Stop 按钮用于停止模拟。Reset 按钮用于重置模拟，Step 按钮用于单步执行模拟。文本信息显示以下信息：
- Epoch 代表模拟运行到当前周期的次数。
- Best So Far 是迄今为止最短的路径。
- Best Possible 代表当前路径的最优解。
- Elapsed Time 是算法内部花费的时间。这不包括“绘制”解决方案到屏幕上花费的时间。有关更多信息，请参见下文。
上述信息的图表
蓝色线是Epoch与算法迄今找到的最短距离的图。绿色线代表最短可能路径（最优解）。当两条线收敛时，就找到了解决方案。
设计与实现
我选择 C++ 作为编程语言来开发此应用程序。编译后的程序总是比解释型程序快。这两种算法以及可视化过程在计算上都相当昂贵。C 语言可能会更快，但通过选择 C++ 语言，就失去了面向对象的优点。其他可能的语言有 Delphi、Visual Basic 和 C#，但我在这些语言上没有足够的经验来尝试如此大规模的项目。我选择使用 Microsoft Foundation Classes (MFC) 应用程序框架。使用它的好处是：
- 应用程序框架的应用程序小巧且速度快
- Visual C++ 工具减少了编程的繁琐工作
- 框架功能丰富
主要缺点之一是需要很长时间才能理解底层模型的复杂性。此外，一旦开发人员尝试脱离向导生成的代码，就很容易在调试器中迷失方向。该项目使用 Visual Studio .NET Academic Version 7.1.3088 开发和编译。用于实现遗传算法的代码基于 Mat Buckland (2002) 的著作《AI Techniques for Game Programming》。ACO 算法的代码部分基于 M Jones (2003) 的著作《AI Application Programming》。还使用了其他几个代码源。
- CMemDC 是一个用于双缓冲的类。这是计算机动画中避免屏幕闪烁的技术，由于屏幕每秒更新（重绘）几次，闪烁是一个主要问题。这里使用的技术是创建一个离屏缓冲区，然后将图像绘制到缓冲区上。最后将图像复制到屏幕上。
- CAutoFont 是一个用于字体操作的类。
- CChart 是一个用于图表绘制的类。
- CPerfTimer 用于计时。
CSideBannerWnd用于在窗口左侧显示面板。
起初，我认为文档应该包含两种算法的通用信息，包括城市数量、城市位置和最短可能路径。然而，随着项目的进展，我意识到每种算法的差异足够大，需要自己独立的数据结构。需要的是一种在不同视图（继承自共同的基类）之间切换的方式。
“有时，文档的显示方式需要进行重大更改。例如，在 PowerPoint 中，您可以以所见即所得（WYSIWYG）的形式查看幻灯片，或在文本编辑窗口中仅查看文本。在 MFC 世界中，可以找到数量惊人的程序来实现这种行为，定义一个 CView 的派生类并使其负责所有可视化更改。这种方法有几个缺点：
- 类定义文件庞大，难以管理。
- 重用性降低：您可以重用一个庞大的
CView派生类，或者什么都无法重用。 - 难以维护（如果您想修改或添加新的“外观”到文档中怎么办？）
- 内存浪费：某些变量（对象）将存在于内存中但不会被使用。” (Lodos,1999)
作者接着解释了这是如何实现的，并举例说明了定义不同视图以及如何切换它们的代码。
以下序列图显示了 CACOView 和 CAntSystem 类之间的基本交互。
以下序列图显示了 CGAView 和 CGASystem 类之间的基本交互。
性能
接下来，我将注意力转向 ACO，并研究了算法中的某些参数如何影响性能。
这里使用的参数是：城市数量：40，alpha：1，beta：1，rho：0.6。这些发现表明，可能可以编写一个遗传算法来优化参数。这可能是一个有趣的项目。
结论
这是一个既有回报又困难的项目。我之前对 MFC 编程了解甚少，认为它很容易掌握。事实证明我错了，我花了很长时间才让程序运行起来。尽管学习曲线陡峭，但我很高兴能实际制作出一个可用的程序，并且在此过程中学到了很多关于遗传算法和蚁群优化算法的知识。我非常感谢所有为这个精彩的网站做出贡献的人。我发现其中许多文章对本项目非常有帮助。继续保持你们出色的工作，伙计们。
参考文献
- Buckland, M., 2002, AI Techniques for Game Developers, Premier Press, United States of America.
- Dorigo ,M., & Gambardella, L. M (1997) Ant colonies for the traveling salesman problem. BioSystems, 43 ,73-81
- Jearakul, C.,1999 2D and 3D Watefall Chart Control, [Online], Available: http:/www.codeguru.com.controls/Waterfall.shtml [Accessed 3/9/2003]
- Jones, M., 2003, AI Application Programming, Publisher: David Pallali.
- Lodos, J, 1999 Replacing a view in a doc-view application, [Online], Available: http:/www.codeguru.com/doc_view/ReplacingView.shtml [Accessed 2/9/2003]
- Nordmeyer, J., Automatic Font Handling Class, [Online], Available: https://codeproject.org.cn/gdi/autofont.asp [Accessed 28/10/2003]
- Prosise, J, 1999,Programming Windows with MFC, 2nd Edition, Microsoft Press, Redmond Washington
- Rule,K..1999 Flicker Free Drawing in MFC, [Online], Available: http:/www.codeproject.com/gdi/flickerfree.asp [Accessed 24/9/2003]
- Wyant,D., 2002, CPerfTimer timer class, [Online], Available: http:/www.codeproject.com/datetime/perftimer.asp [Accessed 24/9/2003]