应用蚁群优化算法解决旅行商问题

• 下载源代码 - 3.61 MB
• 下载演示 - 1.28 MB

目录

• 引言
• 致谢
• 准备工作
• 旅行商问题
• 蚁群优化算法
• 蚁群系统
• 构建解
• 信息素更新
• 蒸发
• 精英蚁算法
• 基于排名的蚁群系统
• 最佳-最差蚁算法
• 最小-最大蚁群系统
• 蚁群系统
• 解的构建
• 蒸发和信息素更新
• 信息素重置（重启）
• 变异
• 旅行统计
• 旅行统计：距离
• 旅行统计：分支因子
• 统计数据的呈现
• 用户手册（差不多）
• 选择算法
• 设置城市范围、城市数量、最大迭代次数、α、β 和 ρ
• 选择城市生成方法
• 手动设置城市
• 设置任意城市配置和距离（提交城市地图）
• 设置其他算法参数
• 启用或禁用变异和/或重置并设置其参数
• 设置或重置对称选项
• 选择要收集的统计数据
• 运行测试
• 监控测试
• 将结果保存为XML文件
• 幕后花絮，或感兴趣的点
• 模型
• 类
• 工作原理
• 算法类
• 算法工厂
• 使用TypeList进行算法注册
• 统计
• Lambda表达式、STL算法和此应用程序
• 引入您自己的蚁群优化算法
• 引入您自己的统计
• 运行算法
• 工作线程和主线程的同步
• 使用GDI+绘图
• 在文档/视图模型之外创建
• 创建自定义打印对话框
• 源代码和演示项目
• 历史

简介

我一直对人工智能问题很感兴趣。所以当我看到Peter Kohout的文章《遗传算法和蚁群优化算法》时，我立刻下载了它。这篇文章是关于旅行商问题的解决方案。在阅读文章及其代码时，我突然想到数学图可能是解决这个问题的自然数学模型。出于纯粹的好奇，我决定使用Boost Graph Library重写代码。在编写代码的过程中，我了解到其他人工智能蚁算法。我决定将它们添加到代码中。我想深入了解算法的行为，所以我添加了几项统计数据来计算。我添加了通过图表呈现这些统计数据的方法。我还添加了查看运行时所需图快照的方法。我添加了将配置和行程结果序列化到XML文件的功能，以及加载和运行外部蚁群配置及其图快照的可能性。我添加了例程，将图快照打印成表格，并为最佳到目前为止的解决方案生成报告。最后，我得到了一个用户界面和代码都大不相同的应用程序。

该应用程序具有开放式架构。您可以非常轻松地为应用程序添加新算法和统计数据，而无需更改大部分应用程序代码。

人工智能爱好者将在此找到玩转人工智能蚁群优化算法及其参数的可能性。他们将能够查看整个过程的每一步。

实现的算法有

• 蚁群系统
• 精英蚁算法
• 基于排名的蚁群系统
• 最佳-最差蚁算法
• 最小-最大蚁群系统
• 蚁群

下面将讨论这些算法。

我希望那些对人工智能完全不感兴趣的人也能在应用程序代码中找到适合自己的东西。它可能是

• 对象工厂设计模式的使用
• 使用TypeList模板将对象注册到工厂
• C++ lambda表达式在STL算法中的使用
• 通过事件进行线程同步
• MFC CPrintDialog类的定制
• 实现一个相当复杂的UI

以及其他内容。

总之，祝您阅读愉快。

致谢

蚁群优化算法的定义可以在Marco Dorigo和Thomas Stützle的书《蚁群优化》中找到。这本书的大部分内容可以通过Google Preview在本书的网页上访问。Thomas Hammerl的维也纳大学硕士论文《用于树和超树分解的蚁群优化》也很有用。

我还使用了Thomas Stützle的ACOTSP软件。该软件是用C语言在Unix操作系统下编写的。我用它作为蚁群优化算法的参考。

我想感谢Igor Tandetnik，感谢他在MSDN开发者论坛上对我询问的非常有用的建议。

准备工作

为了编译和链接代码，我使用了MS Visual Studio 2012 Ultimate Update 3。由于我在代码中使用了我的ChartCtrlLib库，因此项目需要在项目属性中添加预处理器指令_VARIABDIC_MAX=10。该库的调试版本和发布版本位于解决方案目录的Debug和Release文件夹中。

所有代码都可以在MS Visual Studio 2010下编译，但您需要启动一个新的解决方案并手动从VS 2012解决方案导入项目属性。源代码不应被更改。

在此应用程序中，我使用了静态MFC库ChartCtrlLib.lib和专有滑块控件CSliderGdiCtrlT。您可以从我的文章《具有增强用户界面的MFC图表控件》以及关于滑块的文章《SliderGdiCtrl：另一个滑块控件——接受（几乎）所有POD类型并使用GDI+》中获得关于该库的详细信息。该项目zip文件中包含两个控件的头文件和编译好的库。关于TypeList使用方法的信息在我的文章《对象工厂设计模式：使用TypeList和模板元编程注册创建者函数》中。静态库和滑块的代码可以在Visual Studio 2012下无缝编译。

您需要Boost Graph Library。我使用的是Boost v. 1_51.0。您可以从Boost网站下载，或使用BoostPro 1.51.0.0安装程序。

所有自定义控件均使用GDI+构建。

如果您要在此应用程序中添加自己的算法，则需要所有这些信息。

旅行商问题

《蚁群优化》中的引述：“旅行商问题是这样的一个问题：一位销售员从家乡出发，想要找到一条最短的路线，让他能够访问给定的一组客户城市，然后回到家。每个客户城市只能访问一次。”每个城市都可以从所有其他城市到达。

蚁群优化算法

在所有蚁群优化算法中，每只蚂蚁都会得到一个起始城市。从这个城市开始，蚂蚁根据算法规则选择下一个城市。在一次访问所有客户城市之后，蚂蚁会返回起始城市。蚂蚁可以同时旅行或依次旅行。每只蚂蚁都会在自己的路线上沉积一定量的信息素。信息素的量取决于蚂蚁路线的质量：较短的路线通常会产生更多的信息素。沉积的信息素会蒸发。

算法使用不同的规则来选择下一个要移动的城市、蒸发和信息素的沉积。

每个优化算法的噩梦都是永远陷入某个局部最优循环。

针对不同的蚁群优化算法，已经开发出不同的技术来摆脱这种循环。

该应用程序目前实现了六种已知算法。

• 蚁群系统
• 精英蚁算法
• 基于排名的蚁群系统
• 最佳-最差蚁算法
• 最小-最大蚁群系统
• 蚁群

每种算法都可以启用或禁用变异和/或重置选项进行运行。

我并没有发明这些算法。我使用了本文“致谢”部分列出的来源，并进行了少量修改。下面算法方程中的符号与“致谢”部分列出的来源中的符号相同。

蚁群系统

蚁群系统优化算法是Marco Dorigo提出的第一个算法，并进行了分析。

构建解

最初，城市之间的每条路径都有一定的初始信息素量。每只蚂蚁从随机分配的城市开始，从一个城市移动到下一个城市，直到所有城市都被访问过一次。从最后一个访问的城市，蚂蚁返回起始城市。

城市i中的蚂蚁通过计算概率来选择下一个要访问的城市

这里

• s^p - 部分解 #p
• N - 从城市i到所有尚未被蚂蚁访问过的邻近城市的路径集合
• c_ij - 从城市i到城市j的路径
• p - 概率
• t_ij - 路径c_ij上的信息素量
• h_ij - 某个启发式因子，通常是 ，其中d_ij是城市i和j之间的距离，Q是一个常数
• α和β - 算法参数。

蚂蚁将与要前往的每个j进行比较，直到一个随机数。如果 ，蚂蚁立即移动到城市j。这意味着蚂蚁并不总是选择信息素最多的路径，从而降低了陷入局部循环的可能性。

永远不会满足条件的概率非常非常小。因此，在此应用程序中，我采用了《蚁群优化》中提出的修改。对于给定的城市i，我仍然生成一个随机数，但将其与移动总和进行比较。在计算每个新的时，总和会更新。第一个使成立的j是下一个要移动的城市的索引。实际上，这种修改只在第一次试验的步骤中才会有区别，此时沉积在旅行路径上的信息素非常接近。

蚂蚁并行旅行。这意味着在所有蚂蚁返回其起始城市之前，不会进行信息素校正。

信息素更新

蚂蚁根据公式更新连接城市的信息素

其中

• m - 蚂蚁数量，
• 如果蚂蚁k经过了城市i和j之间的路径 ；Q是一个常数，而L_k是第k只蚂蚁的旅行长度。
• 否则为0。

在此应用程序中，Q是城市的范围，即包含所有城市的最小正方形的边长。由于Q仅作为分数的分子出现，而分母是距离，因此结果与城市坐标的比例无关。

关于α、β、ρ、信息素的初始值以及蚂蚁数量（ρ是蒸发因子，见下文）的值，有各种不同的建议。一篇文章建议α = 1, β=2, ρ=0.5, 以及初始信息素 t=1/m，其中m是城市数量。无论如何，您都可以在此应用程序中进行调整。

似乎蚂蚁的数量并不重要，如果试验次数足够多的话，那么每只蚂蚁的起始城市集合可以包含所有客户城市。在此应用程序中，我们只雇用了十只蚂蚁。

蒸发

在所有蚂蚁完成第n次旅行后，蒸发会应用于城市之间的所有路径。

(3)

这里 是蒸发因子。

全局蒸发何时应用存在一个问题：是所有蚂蚁完成旅行后立即应用，还是在图边（城市之间的路径）上的所有信息素都更新后应用？蒸发在更新之前，本质上是增加更新的信息素。

在文献中，一些作者将(1 - ρ)乘数应用于所有信息素，而另一些作者则不应用。

我发现更新后的蒸发有时可以防止出现局部非最优循环，因此在此应用程序中，全局蒸发在信息素更新之后，最后应用于图的边。

精英蚁算法

解的构建和蒸发按照蚁群系统算法中的方程（1）和（2）进行定义。

信息素更新略有不同：在每次迭代中，迄今为止最佳的蚂蚁会沉积额外的​​信息素到它旅行过的路径上。

请注意，此算法会持续沉积额外的​​信息素到相同的路径上，直到最佳到目前为止的解决方案发生变化。您可能需要尝试使用变异和/或重置来配合此算法。

基于排名的蚁群系统

不同之处在于信息素更新。

对于每次迭代，都会选择迄今为止最佳的蚂蚁以及本迭代中额外的w-1只最佳蚂蚁。迄今为止最佳的蚂蚁和每只选定的排名蚂蚁都会在其旅行路径上沉积信息素。

Q是一个常数，L^r是第r只蚂蚁旅行的长度，e是附加乘数。同样，最佳结果在。

成员类似于精英蚁算法中用于迄今为止最佳蚂蚁的参数。

最佳-最差蚁算法

我使用了Oscar Cordon等人的《最佳-最差蚁系统分析》。解的构建由（1）定义，蒸发规则如（3）所示。

只有迄今为止最佳的蚂蚁会更新信息素。

这里  如果路径 是来自T^bs，T^bs是迄今为止最佳的往返行程，C^bs-是行程的长度。

此外，当前迭代中最差蚂蚁的往返行程中不包含在迄今为止最佳解决方案中的路径会受到额外蒸发的影响。

通常，此算法包括对所选路径上信息素的变异，并且算法在我们似乎陷入困境时会重置所有信息素到初始值并重新开始搜索最佳解决方案。

在此应用程序中，变异和重置是选项。您可以将它们添加到任何算法中。

最小-最大蚁群系统

解的构建根据方程(1)进行。

在允许更新信息素的蚂蚁选择方面存在变体：迄今为止最佳的蚂蚁、当前迭代中的最佳蚂蚁、最近一次重置后的最佳蚂蚁、偶数迭代的迄今为止最佳蚂蚁、奇数迭代中的最佳蚂蚁。

城市之间的路径上的信息素量有最小和最大限制，即τ_min和τ_max。据信这可以防止局部循环。因此，蒸发是

更新是

这里  如果路径  是选定蚂蚁的往返行程，C^sel - 是行程的长度。

一些作者将信息素初始化为τ_max，但在本应用程序中，我使用的是τ₀= 1/n_cities。

蚁群系统

在所有先前的算法中，信息素仅在所有蚂蚁完成给定迭代的旅行后才更新。蚁群系统有所不同。蚂蚁从一个城市移动到下一个城市后，所经过路径上的信息素会减少一定量。解的构建也不同。

解的构建

该算法有一个参数。该参数设定了选择下一个城市的两条规则之间的边界。在每一步，算法都会生成一个随机数。如果，则按照(1)选择下一个要移动的城市；否则，下一个要移动的城市索引j为

其中

• i是当前城市的索引，
• j是要移动到的下一个城市的索引，
•  是与当前城市i在第k步相邻的城市集合，
• τ_il是路径c_il上的信息素量，
• _,  Q是一个常数（在此应用程序中，它是城市的范围），d_il是城市i和l之间的距离，
• β - 算法参数

在蚂蚁从城市i移动到城市j后，路径c_ij上的信息素根据以下公式蒸发和更新：

其中

• ξ -局部蒸发因子，
• τ₀ - 附加信息素（算法参数）。

在第一只蚂蚁完成第k步并修改了信息素后，它不会开始下一步。它会等待所有其他蚂蚁完成它们的第k步并修改它们在第k步旅行过的路径上的信息素。在此过程中，第n+1只蚂蚁等待蚂蚁n的更新，依此类推。

蒸发和信息素更新

在所有蚂蚁完成一次迭代后，信息素更新和全局蒸发会应用于路径。

在《用于树和超树分解的蚁群优化》中，只有迄今为止最佳的蚂蚁才被允许更新信息素。蒸发也只允许在为此蚂蚁访问过的路径上进行。

在此应用程序中，您可以选择：当前迭代的最佳蚂蚁、迄今为止最佳的蚂蚁、重置后的最佳蚂蚁，或所有蚂蚁。

该应用程序使用蒸发的方程(3)和全局信息素更新的方程(2)或(4)。

这些方程仅应用于所选蚂蚁（们）访问过的路径。

信息素重置（重启）

如果蚂蚁陷入了局部循环，可以选择重置所有信息素到初始值并继续运行。此选项可以为所有已实现的算法启用或禁用。

选择阈值是一个重置参数。如果

所有城市之间路径上的信息素都被重置为，并且开始寻找最短路径。尽管如此，之前的历史记录并没有被销毁。新的迄今为止最佳行程会更新重置后的最佳值；如果它小于全局迄今为止最佳行程，它也会替换旧的迄今为止最佳值。

在(12)中

• 是重置参数，
• m是蚂蚁往返行程中的路径数，
• - 当前迭代中，在迄今为止最佳和当前迭代中最差蚂蚁的轨迹之间存在不同边的数量。
• - 连续事件的数量，当  时，
• 是一个阈值，重置参数。

本质上，当迄今为止最佳和当前迭代中最差的轨迹非常接近时，会发生重置。用户可以选择重置后的操作：结束运行或继续运行。

如果运行要继续，连续事件的数量将从零开始计数。

变异

蚂蚁路径上的信息素变异用于防止解决方案陷入某些局部循环。这在Oscar Cordon等人的《最佳-最差蚁系统分析》一文中得到了解释。

似乎它仅为最佳-最差蚁算法提出。

在此应用程序中，全局变异选项可以为每个已实现的算法启用或禁用。

这个想法很简单：您随机选择蚂蚁路径（图边），然后根据一组规则增加或减少每条路径上的信息素量。蒸发或增加信息素的规则是

其中

• 是边上的信息素， 是随机选择的城市之间的路径子集，
•  是为每条路径 生成的随机值，
• - 加减阈值，参数
• - 路径上信息素的最小和最大限制
•  
• - 变异强度，变异参数，
• - 迄今为止最佳往返行程路径的平均信息素，
•   - 当前迭代次数，
•  - 自上次信息素重置以来的迭代次数（见下文），
•  - 最大迭代次数（运行参数）

中的路径数量计算如下：

其中

•  - 变异率，参数，
• m- 城市数量

用户设置变异之间的周期（间隔）。此外，用户可以设置重置次数来延迟变异周期的开始。例如，如果重置次数设置为三，变异周期设置为30，则应用程序将等待连续发生三次重置，然后才开始计算变异的迭代次数。如果重置次数设置为零，则每30次迭代将执行一次变异。

如果重置次数设置为零，则每30次迭代将执行一次变异。之后，应用程序将等待另外三次重置以重复计数。如果在计数过程中发生新的重置，迭代计数器将被重置。如果重置次数设置为零，则每30次迭代将执行一次变异。

请注意，在测试结束时，信息素校正的程度会增加。

旅行统计

您可以收集以下统计数据：

• 每次迭代中，每轮最佳和迄今为止最佳的旅行长度值（始终开启）
• 每次迭代中，每轮最差和迄今为止最差的旅行长度值
• 每次迭代中，蚂蚁旅行长度的平均值及其标准差
• 距离——每次迭代中，蚂蚁往返行程中与迄今为止最佳解决方案中的路径不同的路径数量的平均值和标准差
• 分支因子——信息素量大于某个阈值的路径数量的平均值和标准差
• 蚂蚁起始城市分布
• 每次迭代中，重置后的最佳往返行程值

随机变量ν的平均值和标准差计算如下：

其中

•  是n个变量的平均值，
•  是它们的标准差。

距离和分支因子需要一些额外的解释。

旅行统计：距离

对于给定迭代中的每只蚂蚁，将其往返行程与迄今为止最佳的蚂蚁的行程进行比较。计算蚂蚁行程中独有的路径。然后，计算蚂蚁数量的平均值和标准差。这些统计数据是衡量行程质量的指标：低距离意味着找到了解决方案，或者我们陷入了局部循环。

但是，如何在对称图上计算唯一路径？对称图具有路径A->B等于路径B->A。我们决定方向无关紧要：如果迄今为止最佳的蚂蚁是顺时针旅行，而另一只蚂蚁以相同的轨迹逆时针旅行，那么这些蚂蚁旅行的是相同的轨迹。请注意这一点。

旅行统计：分支因子

假设我们有n个城市需要蚂蚁访问。那么每个城市都有n-1个邻近城市可供选择作为下一步。每个城市到邻近城市的路径都有一定量的信息素沉积。

对于每个城市，分支因子统计会计算沉积信息素量大于某个阈值的路径数量。计数越少，选择越确定，解决方案越好。

对于每个城市，分支阈值单独计算为

其中

• - 城市k的出站路径上的最大和最小信息素，
•  - 用户设置的参数。

请注意，分支因子考虑了所有邻近边，无论它们是否被访问过。

统计数据的呈现

除起始城市外，所有统计数据都以线性图表呈现。起始城市显示为条形图。

前两个图表（每轮最佳和迄今为止最佳）以及起始城市显示在应用程序主对话框的只读窗口中。用户可以调用一个单独的窗口来分析、保存或打印所有线性图表。

用户手册（差不多）

这是一个相当长的章节，但用户界面并不那么简单。

要运行某个算法，应执行以下一系列操作：

1. 按名称选择算法
2. 选择城市生成方法
3. 设置城市范围，它定义了城市坐标的范围
4. 设置城市数量
5. 设置最大迭代次数
6. 设置参数α、β和ρ（方程(1)和(3)）。
7. 如果适用，设置其他算法参数
8. 启用或禁用变异和重置，并设置其参数
9. 如果适用，设置或重置蚂蚁路径的对称选项
10. 选择要收集的统计数据
11. 设置一个触发器以在需要时获取旅行图快照

步骤 1-10 可以按任何顺序执行多次：选择将在点击“应用”按钮后提交。即使选择已提交，如果您还没有开始运行算法，您仍然可以更改它们。

点击“应用”后，您可以逐步或连续运行算法，随时停止和恢复运行，或取消运行。算法参数在您开始运行时被锁定。

当算法运行时，它会每100个周期、每次停止和在运行结束时显示蚂蚁旅行的状态。

当算法运行时或在停止时，您可以查看收集到的统计数据的图表，并在单独的对话框中处理这些图表。当满足触发条件时，应用程序将在单独的窗口中显示一个图快照。

您可以将城市配置和/或城市图结构（及其顶点和边）保存到XML文件。

对于您选择的迭代，您还可以将蚂蚁状态、解决方案的底层图、统计图表和图快照保存为XML文件。

您还可以随时打印报告——迄今为止记录的最佳行程数据。

在算法运行时提交的所有用户操作和请求都会在当前迭代结束时执行。请求被处理后，算法将继续运行。

要更改算法或其参数，您必须取消运行（“取消”按钮）或等到运行结束。

让我们深入了解细节。

选择算法

这很简单：只需在“算法”组合框中选择一个项目。

设置城市范围、城市数量、最大迭代次数、α、β和ρ

使用相应的滑块。要粗略设置值，请使用鼠标；要进行精细调整，请使用Home、End、Page Up、Page Down、和键。

选择城市生成方法

该应用程序提供五种城市生成方法：

• “自动放置”：城市放置在一个圆上。圆的直径等于城市范围。
• “随机”：城市的X和Y坐标是随机生成的；采取了特殊的预防措施，以防止在同一坐标生成两个城市。坐标值的分布在、上是均匀的，其中Q是城市的范围。
• “手动放置”：您生成自动或随机放置，或使用现有放置并按需移动城市。移动城市的坐标显示在状态栏中。
• “从文件加载城市”：从外部XML文件加载一组城市的坐标。您无需点击“应用”即可开始：直接进入“运行”。
• “从文件加载配置”：此选项加载所有城市及其坐标和城市之间的距离作为图。生成的图将从应用程序主对话框窗口中的用户选择中获取α、β、蒸发因子ρ、算法类型和算法参数。信息素的初始值设置为Q/cities数量，其中Q是城市的范围。同样，您无需点击“应用”即可开始：直接进入“运行”。
• “从文件加载图”：它导入算法图在某个先前周期或许多天前保存时的快照：城市、它们之间的距离、沉积的信息素，所有内容。如果图与图表和起始城市条形图一起保存（这是此应用程序中保存图的默认选项），则图表和条形图也会加载。您可以从保存图的迭代（周期）继续。要仅使用配置，您需要选择“使用现有配置”并重新应用它。同样，您无需点击“应用”。
• “使用现有地图”：它使用最后一个生成或加载的城市配置。

选项从文件加载配置和从文件加载图使用的是相应XML文件中保存的城市之间的距离。所有其他选项会自动计算生成或加载的城市之间的距离作为欧几里得距离。

手动设置城市

如上所述，您可以使用手动放置手动设置您想要的任何城市配置。唯一的限制是所有X和Y都必须是非负的。建议在开始手动放置之前设置所有其他算法参数，因为您设置的配置将自动提交。当然，在用使用现有地图完成放置后，您可以设置任何参数。

进行手动放置：

• 将“城市范围”和“城市数量”滑块设置为所需值。
• 在“城市/生成方法”组合框中选择“手动放置”。将显示一个对话框以选择城市生成方法。选择“自动”、“随机”或“使用现有地图”，然后点击“确定”。
• 生成的城市配置将在主应用程序对话框的图片控件中显示。用鼠标左键单击选择城市，然后拖动城市到所需位置，或使用箭头键。城市名称和坐标显示在对话框状态栏的第一个窗格（窗格0）中。您还可以通过右键单击城市来调用城市标签。
• 完成后，在图片控件中的“确定”按钮上双击鼠标左键。配置将被提交，您可以开始运行。

请记住，城市之间的距离将自动计算为欧几里得距离。如果您的距离应该不同，请参阅下一段。

设置任意城市配置和距离（提交城市地图）

城市之间的距离仅用于计算，因此您可以设置任何方便您的距离值。要现实，请记住城市之间可能的最短距离是欧几里得距离。

假设您有一张您需要访问的地点地图，它们之间有单向街道。这意味着有时从A到B的距离不等于从B到A的距离。尽管如此，您仍然可以使用XML配置文件在此应用程序中处理您的地图，以设置地图并将其加载到应用程序中。

要设置任意城市配置，您必须生成一个初始配置，将其保存到XML文件中，然后修改该文件并将其加载回来。

首先，您必须为您的城市范围和城市数量生成一个城市配置。任何生成方法（“规则”、“随机”或“手动”）都可以。通过点击应用提交配置。之后，转到选项/保存/保存配置子菜单项，点击它，并将配置保存为配置图XML文件。

现在用任何XML编辑器打开文件（我推荐Microsoft XML Notepad 2007，它是免费且好用的，但您也可以使用MS Visual Studio或任何可以工作的工具）。您会看到类似这样的内容：

<Config_Graph>
<Graph_Prop CitiesNum="10" SymMut="true" SymDist="false" StartPher="0.1" CitiesExtent="25"/>
<Vertex ID="0" Name="City_0" X="8.536407" Y="3.749408">
<Edges>
  <Target ID="1" Name="City_1" X="2.025207" Y="9.906549" Dist="8.9613676071167"/>
  <Target ID="2" Name="City_2" X="0.2259159" Y="0.8545399" Dist="8.80025672912598"/>
  <Target ID="3" Name="City_3" X="11.42984" Y="5.034723" Dist="3.16607141494751"/>
  <Target ID="4" Name="City_4" X="11.51926" Y="7.236289" Dist="4.58865690231323"/>
  <Target ID="5" Name="City_5" X="6.953999" Y="7.392624" Dist="3.97203135490417"/>
  ....................................................................................................
                                                 
</Edges>
</Vertex>
<Vertex ID="1" Name="City_1" X="2.025207" Y="9.906549">
<Edges>
................................................................................................................

根据您的地图修改城市名称、坐标和城市之间的距离。如果对于某些城市对距离(A, B) ≠距离(B, A)，则将SymMut和SymDist更改为false（我稍后会解释）。对于对称图，距离(A, B) ≠ 距离(B, A)对于所有城市，SymMut必须为true。保存文件，返回或启动应用程序，然后加载配置。

默认情况下，城市名称为“City_0”、“City_1”等。对城市或配置XML文件执行相同的过程来更改城市名称。

设置其他算法参数

点击“编辑蚂蚁选项”。如果存在其他算法参数，将显示相应的对话框。选择参数并点击确定。如果您调用此对话框且不想更改先前设置，请点击取消。例如，这是用于设置排名蚂蚁数量及其蒸发因子（用于排名蚁算法）的对话框。

启用或禁用变异和/或重置并设置其参数

点击选项菜单按钮，然后点击变异或重置菜单项。在显示的对话框中设置参数并点击确定。如果对话框中的复选框“允许”未选中，则该框中的所有其他控件都将被禁用，请不要尝试更改它们的状态。这是变异参数对话框。

一些参数需要解释（参见方程（13））。

• “MUT PERIOD”- 变异周期，可能设置为1到100个周期。
• “SEL THRESHOLD”- 减少和增加变异之间的阈值。
• “MUT RATE”- 受变异影响的图边的比例。
• “WAIT FOR RST”- 变异开始前的重置次数；可以为零；如果未启用重置，则滑块将禁用。
• “MUT STRENGTH”- 应用于边的计算出的完整变异的比例。

对于重置，只有两个参数：最差蚂蚁当前迭代中与迄今为止最佳行程不同的图边比例，以触发重置，以及此事件连续重复的次数以重置旅行。还有一个列表框可选择重置后的操作。操作是：

• 无信息素重置：此操作与变异一起使用：如果启用了变异且Wait for Rst不为零，则应用程序将不会将所有图边重置为初始信息素，而是在发生指定次数的重置后变异信息素。
• 重置：重置后，所有信息素都重置为初始值。
• 结束运行：信息素被重置，测试结束。用户可以继续此测试或开始新的测试。

设置或重置对称选项

如果城市A和B之间的距离不等于城市B和A之间的距离，则城市图是对称的。您必须单独计算图中每条边的信息素。

如果d(A, B) == d(B, A)，则有两种选择。您可以假设A到B的路线有两条独立的单向车道，并分别计算每条车道的信息素，或者假设有一条双向车道，并将B到A的边上的信息素设置为等于A到B边上的信息素。对于对称图，您可以选择以下选项之一：点击选项菜单按钮，然后点击对称路径菜单项。

设置不同距离的唯一方法是通过配置XML（参见上面的设置任意城市配置）。

选择要收集的统计数据

有一些统计数据您可以收集：

• 每次迭代中，每轮旅行和迄今为止最佳的旅行值（始终开启）
• 每次迭代中，每轮最差和迄今为止最差的旅行值
• 每次迭代中，蚂蚁旅行长度的平均值及其标准差
• 每次迭代中，蚂蚁往返行程中与迄今为止最佳解决方案中的路径不同的路径数量的平均值和标准差
• 分支因子的平均值和标准差：信息素量大于某个阈值的路径数量
• 蚂蚁的起始城市分布
• 每次迭代中，重置后的最佳往返行程值

要启用或禁用统计数据，请点击选项菜单按钮，点击设置统计数据与结果菜单项，然后选择所需的统计数据。使用滑块设置分支因子阈值。

对于所有统计数据（“起始城市”除外），收集的数据都表示为线性图表。

运行测试

要提交所有参数，请点击“应用”按钮。之后，“运行”和“单步”按钮将被启用。

您可以逐步进行，或连续运行测试，并随时停止运行。要从运行切换到单步，您必须先停止运行。在停止后恢复运行，您需要再次点击“停止”按钮（捕获文本会更改为“恢复”）。

当测试运行时，所有允许更改算法、算法和测试参数的控件都将被禁用。您必须等待测试完成，或随时通过点击“取消运行”按钮中断它。此操作仅取消模式；所有参数均未更改或删除。您可以从取消测试的点继续测试，或者更改算法和/或参数，然后点击“应用”以清除旧参数和数据，并使用新参数集开始。在提交新设置之前，所有先前的测试数据都可访问。您可以随时监控测试进度，直到新的算法和/或算法参数被提交。

监控测试

每100次迭代和每次停止时，应用程序都会更新其数据，并显示当前周期的旅行长度及其轨迹。它还提供当前迭代的最佳和最差蚂蚁的行程长度、重置后最佳行程以及迄今为止最佳和最差的结果。您从组合框中选择蚂蚁，并在框左侧的控件中查看周期、蚂蚁ID和行程长度。行程轨迹显示在框下方。

统计数据也在第100次迭代、每次停止、完成或取消运行时更新。

主对话框中显示了每轮最佳和迄今为止最佳行程长度的统计图表。此图表控件是只读的；这意味着不允许任何用户输入。要查看所有图表并与之交互（例如，隐藏、平移、缩放、保存等），您必须从“选项”中选择“查看图表”。此操作将显示图表控件。

要完全掌握图表控件的功能，最好阅读我的文章《具有增强用户界面的MFC图表控件》，但这里是其用户手册的简要版本。

• 要查看图表值，请通过鼠标中键单击启用跟踪（光标会变成十字形）。之后，选择X坐标并单击图表以查看所选X的数据图例。
• 要水平缩放，请使用SHIFT + 左键单击选择缩放边界。
• 要垂直缩放，请使用SHIFT + 左键双击选择第一个缩放边界，然后使用SHIFT + 左键单击选择第二个边界。
• 要水平平移，请使用左右箭头键或SHIFT + 鼠标滚轮。
• 要垂直平移，请使用向上和向下箭头键。
• 要更改所选图表的Y轴刻度，首先使用CTRL + 左键单击选择它，然后使用CTRL + 鼠标滚轮或向上/向下键更改Y轴刻度。
• 所有其他图表操作，如隐藏/显示、保存、打印，都可以从在图表控件上右键单击时显示的弹出菜单中执行。

该图表控件窗口的大小可以由用户更改。

如果用户未停止，算法将继续运行。要在此控件中更新图表，您必须再次点击“查看图表”。

您可以随时通过从“选项”菜单按钮选择“打印报告”来打印本周期最佳到目前为止的旅行数据。您将看到MFC打印对话框，用于选择打印机、打印机设置和打印选项。报告由几页组成。第一页显示迄今为止最佳的行程数据（旅行长度、周期等）、算法信息以及上面显示的行程轨迹图。其他页面以表格形式显示迄今为止最佳的轨迹。表格的一页显示约40行。

如果您在打印对话框中选择“选择”，则只打印第一页。否则，将打印完整报告。为了获得更大的灵活性，您可以安装一个转换器将报告打印到PDF文件（例如doPdf，它是免费且非常好的），或打印到MS XPS文件。

最后，也许也是最重要的应用程序功能（我在其他蚁群应用程序中没有看到它）是设置一个触发点并在该点获取系统快照的可能性。触发器可以在算法提交后的任何时间设置。从“选项”中，选择“图快照设置”。您将看到“图快照触发器”对话框。

这是不言自明的；只有两个复选框需要额外说明。第一个是继续运行。默认情况下，触发器会中断测试运行，用户必须点击“恢复”按钮才能继续测试。如果选中此框，运行将继续。

第二个是“续订......”。默认情况下，触发器在触发事件发生后被清除。当选中此框时，触发器将重置。例如，如果触发器设置为“迄今为止最佳更改”，您将持续收到快照，每次迄今为止最佳旅行距离发生变化时。触发器只能在测试参数提交后设置，因为点击“应用”按钮会将它们重置为无触发模式。

触发事件发生时，将显示边对话框。它显示了从某个源顶点（城市）开始的图边。您可以通过用鼠标左键单击城市来更改源城市。您可以通过CTRL + 左键单击选择此源城市的下一个顶点（目标城市）。在城市上右键单击将调用带有城市名称的工具提示窗口。在同一城市上第二次右键单击将隐藏名称。在空白处右键单击将隐藏所有工具提示。

边缘图片控件右侧的文本框显示主要算法参数、选定蚂蚁的数据以及源城市和目标城市以及连接它们的边的数据。边颜色图例位于边图片控件下方。

点击“查看蚂蚁图”将显示快照的边视图。它有很多页面。第一页是选定（在前一个对话框中）蚂蚁的旅行轨迹。其他页面显示所有源城市的边；每个源城市都有一个单独的页面。表格显示目标、源的距离、蚂蚁选择下一条边进行旅行之前的信息素、选择的概率以及行程结束时更新后的信息素。

要在此页面之间导航，请使用页面底部的按钮。您也可以通过在第一页上左键单击城市来选择源城市。您也可以通过选择第一页上的起始城市，然后在后续页面上点击目标城市圆圈来跟踪蚂蚁的行程。

 如果页面无法显示给定源城市的所有边，则可以在页面具有焦点时（单击页面以设置焦点）使用UP/DOWN键滚动页面。

您可以将所有源城市的所有表格保存到XML文件中。您也可以打印所有表格、选定源城市的表格或任意数量的源城市。请记住，打印所有十个城市的源将占用11页纸；对于100个城市，将占用301页纸。

将结果保存为XML文件

有五种将数据保存到XML文件的选项：

• 保存城市：保存生成城市的ID、名称和坐标。
• 保存配置：此外，还保存了城市之间的距离。
• 保存（蚁群）图：保存整个系统图，包括城市ID、名称、坐标；城市之间的距离以及数据所在的周期的边上的信息素量。还保存了算法参数、变异和重置参数、收集的统计数据的类型。还保存了当前周期的蚂蚁行程轨迹。此外，还为每轮最佳、迄今为止最佳、重置后最佳、当前轮最差和迄今为止最差的蚂蚁保存了周期、边信息素和旅行状态。图表和起始城市分布会自动保存在单独的文件中。
• 保存蚁群蚂蚁：保存所有蚂蚁的行程轨迹。
• 保存图表：保存统计图表。

所有选项都可以从“选项/保存”访问。

此外，您可以从“边视图”对话框保存选定的蚂蚁图，并从图表控件的弹出菜单保存图表。

城市和配置可以通过“生成方法”组合框加载回应用程序，以运行任何已注册的算法。城市XML文件允许在将文件加载回之前修改城市坐标和城市名称。城市之间的距离将由应用程序计算为欧几里得距离。

配置文件的城市坐标和名称之外，还可以更改其城市之间的距离。

殖民地图 XML 文件封装了用户请求保存操作时的完整系统快照。实际上，它可能包含三个 XML 文件：图本身，包含算法、其参数和请求的统计数据；如果图表有数据（保存图时的时期大于零），则包含一个图表 XML 文件；以及如果请求并收集了起始城市统计数据，则包含一个城市条形图。这就是为什么我建议将它们组织在一个公共文件夹中来存放这三个文件。您只需设置图表文件的名称；图表和城市文件会自动命名。例如，如果图表文件命名为“TestB.xml”，则图表文件将命名为“TestB_Charts.xml”，城市文件为“TestB_CitiesChart.xml”。

如果您选择加载殖民地图 XML 文件，图表和城市文件将在存在时自动加载。加载文件后，您可以从保存殖民地图的时期开始运行测试。如果您丢失了图表文件，应用程序将从加载的时期开始收集和计算统计数据。起始城市分布也是如此。

收到保存到 XML 文件的请求后，应用程序会显示 MFC CFileDialog 对话框。您可以自由选择保存文件的位置。为了在此过程中引入一些秩序，我在 AntCol 工作目录中为每种类型的数据设置了默认子文件夹来存放文件，因此如果您设置了这些子文件夹，CFileDialog 会在保存数据的每种类型的默认子文件夹中打开。子文件夹包括：

• Cities
• ConfigGraphs
• Graphs
• Ants
• Charts
• AntGraphs

工作原理如下：

• 应用程序获取 AntCol.exe 的完整模块名，例如“C:\...\AntCol.exe”。
• 它从模块名中剥离文件名（AntCol.exe）。
• 它在模块路径中搜索名为“AntCol”的子目录。
• 它会删除“AntCol”之后的所有字符，在“Col”后添加反斜杠，并根据用户想要保存的内容，从列表中添加文件夹名称。
• 它将生成路径传递给 CFileDialog 作为默认路径，因此对话框将从此路径开始。
• 如果未找到 AntCol 文件夹，CFileDialog 将在 MyDocument 目录中启动。

您需要将工作目录设置为“.....\AntCol”并将可执行文件 AntCol.exe 复制到其中。之后，您需要在工作目录 AntCol 中创建这些子文件夹。

当然，您可以不用这些东西，并将 XML 文件保存在您计算机或网络的任何位置。

幕后技术，或值得关注的点

此应用程序是一个基于对话框的 MFC 应用程序，大量使用了 Boost Graph Library 和 GDI+。

其主类 CAntColApp 继承自 MFC 扩展类 CWinAppEx。

如果您想仔细研究应用程序代码，有四个函数可以作为起点：

• void CAntColDlg::OnBnClickedBtnapply() 处理并提交用户输入，为运行准备算法
• void CAntColDlg::OnBnClickedBtnrun() 启动一个工作线程来执行算法
• static unsigned _stdcall CAntColDlg::RunASTravel(void* colDataPtr) - 工作函数
• LRESULT CAntColDlg::OnTravelOnce(WPARAM wParam, LPARAM lParam) - 处理工作线程发送给应用程序主线程的消息

所有这些函数都在 AntColDlg.h、AntColDlg.cpp 文件中。

从那里您可以跳转到内部调用的其他函数，以及这些二次函数调用的函数，以此类推。

模型

旅行商问题 (TSP) 的自然数学模型是图：顶点是城市，边是城市之间的路线。每个顶点都连接到所有其他城市。在 Boost Graph Library 中，该模型最好用有向邻接表图来描述。为了将算法参数、城市以及城市之间的路线连接到图中，我为图本身、其顶点和边提供了绑定的属性。这些属性在 Colony.h 文件中定义。

图属性是

struct AntColProp
{
    ..............................................................
    bool m_bSymMut;       // Enabled or disabled ability to change m_bSym
    bool m_bSym;          // If true for edges ij and ji have equal  //distances
    int m_grID;           // Actually index of the associated ant
    int m_startIdx;       // Start point; idx is embedded in vertex  //property
    double m_startPher;   // Start pheromone; used for reinitialization //only
    double m_alpha;       // Power of the pheromone
    double m_beta;        // Power of the distance (edge weight)
    double m_evap;        // Global Evaporation factor; pheromone // attenuation is 1 - m_evap
    float m_citiesExtent; // Cities placement dimension
    string_t m_szAlgName; // Name of the algorithm
};

这里 string_t 代表 std::basic_string<TCHAR>。

在有向邻接表中，连接顶点 i 和 j 的边不等于连接 j 和 i 的边。然而，在大多数情况下，连接任意两个城市的路线是双向的。属性成员 m_bSymMut 和 m_bSym 是标志，用于指示应额外注意对称边 ij 和 ji，以使边长和信息素相等。对于非对称图，m_bSymMut 始终为 false，而 m_bSym 的值无关紧要。对于对称图，m_bSymMut = true，并且双向路线的 m_bSym 必须为 true。您可以尝试将对称图中的边视为非对称边，方法是将 m_bSym 设置为 false。

该结构还包括一个构造函数和一个函数 string_t GetAntColPropStr(int citiesNum)，用于将成员值转换为字符串。

之前已报告了一个关于访问邻接图绑定属性的问题。解决方案是调用 boost::get_property(graph&, graph name)，这与处理其他绑定属性不同。

顶点属性是

struct City 
{
  ......................
  int m_idx;
  // City index
  string_t m_szName;
  bool m_bVisited;
  Gdiplus::PointF m_pntLocationF;
};

默认情况下，在放置城市时，城市会被命名为“City_0”、“City_1”等。城市名称可以在应用程序外部更改，并且可以重新加载整个配置。用户可以设置包含城市的正方形的范围，从 1.0 到 100.0。

边属性是

struct Path
{
  ..............................
  bool m_bTraveled;
  double m_dist;
  double m_pher;
};

默认情况下，边长（城市之间的距离）m_dist 计算如下：

同样，也可以在应用程序外部更改边长。因为 m_dist 仅用于计算，所以它可以是任何值。

这是旅行商图的定义

typedef adjacency_list<vecS, vecS, directedS, City, Path,
           property<graph_name_t, AntColProp> > GRAPH;

有关此类的更多信息，请参阅 Boost::adjacency_list 网页。

我知道 STL 列表不是搜索的最佳结构，但在 Release 配置下，即使有一百个城市，应用程序的性能也还可以。

类

此应用程序中有三个主要角色：CAnt 类、CColony 类以及算法类层次结构。

CAnt (Colony.h) 只是一个存储，用于保存蚂蚁在图导航所需的所有内容。

class CAnt
{
  ..............................................
  public:
    int m_antID;
    GRAPH m_antCitiesGraph;
    std::list<City> m_lstAntPath;
    double m_travelLength;
    vertex_descriptor m_currVertex;
    vertex_descriptor m_startVertex;
    int m_epoch;
};

CColony (Colony.h) 负责处理和保存蚂蚁行程的结果，以及处理一组蚂蚁的某些任务。

class CColony
{
................................................................
public:
  static std::mt19937 m_rndGenAnts; // Mercer generator for cities
  static std::mt19937 m_rndColony;  // To select start cities
  
  static const int m_antNmb; // Ten ants for now
  MAP_ANTS m_mapAnts; 
                             // We keep ants in map antIdx/ant 
  GRAPH m_colGraph;          // Colony Graph; passed to the 
                             // every ant before tripitEpoch;
                             // Initial epoch; zero or loaded from graph
  int m_startRstEpoch;  // Epoch of last reset
  int m_rstNmb;         // Number of resets so far
  int m_maxRun;
};

主对话框有一个成员 m_antColony。在每次行程之前，殖民地会将殖民地图传递给它的蚂蚁。蚂蚁的轨迹保存在每个蚂蚁的 m_lstAntPath 中，并且根据行程轨迹更新殖民地图。所有蚂蚁都保存在一个名为 m_mapAnts 的映射中。

稍后我们将讨论算法类。

工作原理

用户选择一个算法、其参数、城市数量和行程数量，以及城市生成方法。他还/她还可以选择要收集的统计数据。之后，用户通过单击 **Apply** 按钮来提交选择。

应用程序调用算法工厂实例化选定的算法，调用统计工厂编译统计数据映射。它还会启用/禁用相应的 UI 控件。

之后，用户单击 **Run** 或 **Step**，应用程序将启动工作线程来运行算法。

应用程序使用四个事件句柄（文件 AntColDlg.h 和 AntColDlg.cpp）来控制主线程和工作线程之间的交互。

HANDLE m_hEvAbortRun;
HANDLE m_hEvStopReq;
HANDLE m_hEvInfoReq;
HANDLE m_hEvContRun;

句柄名称不言自明（更多细节如下）。事件控制着工作线程中的等待函数。在工作线程退出或被这些事件中断后，用户可以恢复运行，或者更改算法和/或算法和测试的参数。

算法类

所有算法类（文件 TravelAlg.h 和 TravelAlg.cpp）都继承自基类 CASTravelBase。所有新算法类都必须继承自这个基类。该类定义了算法接口。

class CASTravelBase
{
public:
  CASTravelBase(); 
  virtual ~CASTravelBase();
  virtual unsigned int TravelGraphOnce(CColony& antColony) = 0;
  virtual void UpdateASGraphOnce(CColony& antColony) = 0;
  virtual string_t GetAlgName(void)const  = 0;
  virtual void GetAlgParams(V_ALGPARAMS& vAlgParams) = 0;
  virtual string_t GetAlgParamStrT(void) = 0;
  virtual void SetAlgParams(V_ALGPARAMS& vAlgParams) = 0;
  static void GetMutParams(V_ALGPARAMS& vAlgParams);
  static string_t GetMutParamStrT(bool bShort = true);
  static void GetRstParams(V_ALGPARAMS& vAlgParams);
  static string_t GetRstParamStrT(bool bShort = true);
  static void SetMutParams(V_ALGPARAMS& vAlgParams);
  static void SetRstParams(V_ALGPARAMS& vAlgParams);
// From WrapBase
  virtual string_t GetParamString(void) {return string_t(_T(""));}
// Reinitialize the edges' pheromones to the start pheromone
  RST_ACTIONS RestartAlgorithm(CColony& antColony);
  void MutatePheromones(CColony& antColony);
protected:
// Evaporate pheromones on all edges
  void EvaporateEgdePheromones(CColony& antColony, double evapFactor);
    void TravelGraphOnce(CAnt& ant);
  void UpdateAntPathPher(GRAPH& colGraph, CAnt& ant);
  void UpdateAntPathPher(GRAPH& colGraph, CAnt& ant, double multiplier);
public:
  static CDlgMut* GetMutDlg(bool bDelete = false);
  static CDlgRst* GetRstDlg(bool bDelete = false);
  virtual INT_PTR RunDlg(void) 
  {  
    AfxMessageBox(_T("There are no additional alg params"));
    return IDCANCEL;
  }
  static void DeleteParamsDlgs(void);
public:
  static double m_mutMinPher;         // for mutation, to prevent -INV and 
  static double m_mutMaxPher;         // For MMAS and just in case
  static bool m_bMutAllowed;
  static bool m_bRstAllowed;
  static int m_mutPeriod;
  static double m_mutRndTrsh;
  static double m_mutRate;
  static double m_mutStrength;
  static int m_mutRstTrsh;  // Nmb of resets before mut period starts
  static int m_mutRstCnt;   // Count of resets
  static int m_rstTrsh;
  static int m_rstCntTrsh; // Repetition of the distance between worst and    
                           // best to date below threshold
  static RST_ACTIONS m_rstAction;    // What to do after that: restart or 
                                     // finish
// Names of parameters
  static string_t m_strMutAllowed;
  static string_t m_strMutMinPher;
  static string_t m_strMutMaxPher;
  static string_t m_strRstAllowed;
  static string_t m_strMutPeriod;
  static string_t m_strMutRndTrsh;
  static string_t m_strMutRate;
  static string_t m_strMutStrength;
  static string_t m_strMutRstTrsh;
  static string_t m_strMutRstCnt;
  static string_t m_strRstTrsh;
  static string_t m_strRstCntTrsh;
  static string_t m_strRstAction;
  static string_t m_strActions[];
};

严格来说，只有 TravelGraphOnce 和 UpdateASGraphOnce 实现算法本身。所有其他虚函数定义了应用程序、用户和算法之间的交互。

通常，所有算法需要知道的是其参数 α、β 和蒸发因子 ρ（参见公式 1 和 3）。它需要它们来计算到下一个城市的转移概率并蒸发信息素。算法从殖民地实例接收这些参数，因为它们是殖民地图的属性。

其他参数（如果有的话，例如，排名蚂蚁算法中的排名蚂蚁数量，或蚁群算法中的局部蒸发因子）算法应该从外部获取。在此应用程序中，用户从相应的对话框设置这些附加参数。对话框是独立的类，但算法（用户）可以通过虚函数 INT_PTR RunDlg(void) 调用它们。此函数只是调用相应对话框类的 DoModal。

对话框没有自己的数据成员；它们使用相应算法的数据成员。所有算法的附加参数都声明为静态的，因此可以随时访问。在单击 OK 时，对话框会读取其控件的状态并设置相应的算法静态数据成员。

每个附加算法参数都有一个对应项，即其名称，一个静态字符串。我们需要这些名称来促进 XML 文件和算法参数之间的交换。我们引入了虚函数 GetAlgParams(V_ALGPARAMS & vAlgParams) 和 SetAlgParams(V_ALGPARAMS& vAlgParams)。向量 V_ALGPARAMS 是一个由 std::pair(bstr_t (parameter name) ,variant_t (parameter value)) 组成的向量。使用 bstr_t 和 variant_t 可以使不同类型的值（例如，float、int、bool 等）具有相同类型的向量元素。

最后，为了以易于理解的形式呈现算法状态，有虚函数 GetAlgName、GetAlgParamStrT、GetParamString。最后一个函数用于设置主应用程序对话框静态控件中的文本。

类 CASTravelBase 还包括用于设置和获取变异和重置模式参数的静态函数。我们之前提到过，用户可以为任何算法设置变异和重置模式，因此函数 RST_ACTIONS RestartAlgorithm(CColony& antColony) 和 void MutatePheromones(CColony& antColony) 被设为基类的成员。

为了展示一个具体算法的算法接口是如何定义的，我将展示精英蚁算法的类。

有一个类用于精英蚁群算法，它继承自 CASTravelBase。

class CASETravel:public CASTravelBase
{
public:
  CASETravel(void);
  virtual ~CASETravel(void);
  static CASTravelBase* CreateASETravelAlg() { return new CASETravel;}
  virtual unsigned int TravelGraphOnce(CColony& antColony);
  virtual void UpdateASGraphOnce(CColony& antColony);
  virtual string_t GetAlgName(void) const {return AlgName();}
  virtual void GetAlgParams(V_ALGPARAMS& vAlgParams);
  virtual string_t GetAlgParamStrT(void);
  virtual void SetAlgParams(V_ALGPARAMS& vAlgParams);
  static bool RegisterWithFactory(void);
public:
  virtual CString GetParamString(void);
private:
  unsigned int TravelASEGraphOnce(CColony& antColony);
  void UpdateASEPheromone(CColony& antColony);
  string_t AlgName(void) const {return m_szAlgName;}
public:
  static CDlgEAS* GetMnDlg(bool bDelete = false);
  virtual INT_PTR RunDlg(void) {return GetMnDlg()->DoModal();}
  static void DeleteParamsDlgs(void);
// Members
public:
  static double m_easFactor;
  static string_t m_strEasFactor;
public:
  static const string_t m_szAlgName;
...................................................................
};

您可以在 TravelAlg.cpp 文件中看到该类的实现。

算法工厂

为了获取算法实例，我使用了算法工厂。它实现为 Scott Meyers 单例模式。

CTravelAlgFactory& CTravelAlgFactory::Instance()
{
  static CTravelAlgFactory factory;
  return factory;
}

我知道单例在多线程应用程序中存在问题。在此应用程序中，工作线程从未尝试实例化算法。相反，它从主线程接收算法实例的指针。

为了将算法注册到工厂，我使用了一个 std::map，以算法名称作为键，算法创建函数作为值。这意味着算法必须在此应用程序中拥有唯一的名称。

每个算法都有一个静态创建者成员函数，例如：

static CASTravelBase* CreateACSTravelAlg() { return new CACSTravel;}

为了向工厂注册算法，算法工厂有一个函数：

bool RegisterCreatorAlgFn(const string_t& algName, TravelAlgCreator creatorFn)
{
    bool bResAlg  = m_algMap.insert(MAP_TRAVELALG::value_type(algName, creatorFn)).second;
    if (bResAlg)
      m_vAlgNames.push_back(algName);
    return bResAlg;
}

向量 m_vAlgNames 用于初始化算法名称的组合框（稍后讨论）。

每个算法都调用此函数来注册自己。例如：

bool CACSTravel::RegisterWithFactory(void)
{
  return travelAlgFactory.RegisterCreatorAlgFn(m_szAlgName, CreateACSTravelAlg);
}

如果同一名称下注册了其他算法，则插入函数将失败，并且注册函数将返回 false。

为了在给定应用程序中注册所有算法，并能够轻松地向应用程序添加新算法，我使用 TypeList 来枚举并向工厂注册所有算法类。

使用 TypeLists 进行算法注册

TypeList 模板的代码在 TypeLists.h 文件中。

Andrei Alexandrescu 在他的书“Modern C++ Design”中定义了 TypeList 作为一个模板。

template <class T, class U>
struct TypeList
{
  typedef T Head;
  typedef U Tail;
};

它是一个非常简单的模板，但它能让你完成的事情非常令人惊叹。

在书中和 Loki 库（Loki\MSVC\1300\Typelist.h）中，有用于定义类集合的 TypeList 的宏。

#define TYPELIST_1(T1) TypeList<T1, NullType>
#define TYPELIST_2(T1, T2) TypeList<T1, TYPELIST_1(T2)>
#define TYPELIST_3(T1, T2, T3) TypeList<T1, TYPELIST_2(T2, T3)>
#define TYPELIST_4(T1, T2, T3, T4) TypeList<T1, TYPELIST_3(T2, T3, T4)>
#define TYPELIST_5(T1, T2, T3, T4, T5) TypeList<T1, TYPELIST_4(T2, T3, T4, T5)>
#define TYPELIST_6(T1, T2, T3, T4, T5, T6) TypeList<T1, TYPELIST_5(T2, T3, T4, T5, T6)>
..........................................................................................

Loki 库定义了最多 50 个类的宏，但您可以从中获得一些想法。在 Loki 库中，有一个名为 MakeTypeList 的模板，可以自动生成最多 18 个数据类型的 TypeList。

为了自动化算法的注册，我们使用了一个名为 RegFactoryClasses 的模板（文件 TypeLists.h）。

template <class TList, int idx>
struct RegFactoryClasses;
template <class Head, class Tail>
struct RegFactoryClasses<TypeList<Head, Tail>, 0>
{
        typedef Head Result;
  static inline void Fn(void)
  {
    Result::RegisterWithFactory();
  }
};
template <class Head, class Tail, int idx>
struct RegFactoryClasses<TypeList<Head, Tail>, idx>
{
  typedef typename RegFactoryClasses<Tail, idx - 1>::Result Result;
  static inline void Fn(void)
  {
    Result::RegisterWithFactory();
    RegFactoryClasses<TypeList<Head, Tail>, idx - 1>::Fn();
  }
};

编译器在编译时开始展开模板，每次调用静态函数 Head::RegisterWithFactory()，其中 Head 是 TypeList 中的某个类。编译器在索引零处停止。

因此，我们现在需要在应用程序中为六个算法定义我们的 TypeList。

typedef TYPELIST_6(CASTravel, CASETravel, CRASTravel, CBWASTravel, CMMASTravel, CACSTravel) AlgTypeList;

我们还为结构 RegFactoryClasses 定义了类型别名。

typedef RegFactoryClasses<AlgTypeList, TypeListLength<AlgTypeList>::value - 1 > RegAlgStruct;

这里 TypeListLength 是 Andrei Alexandrescu 定义的一个元函数。

template <class TList> 
struct TypeListLength;
template <>
struct TypeListLength<NullType>
{
  enum {value = 0};
};
template < class T, class U >
struct TypeListLength<TypeList<T, U> >
{
  enum { value = 1 + TypeListLength<U>::value};
};

现在很简单：在主对话框的 OnInitDialog() 中，您调用：

RegAlgStruct::Fn();

它开始调用算法的 RegisterWithFactory 函数，从 TypeList 中的最后一个类型 CACSTravel 开始。在注册过程中，算法的创建函数作为键被添加到已注册算法的映射中。因为映射是一个有序的容器，所以映射中键的顺序并不立即清楚。

我们在主对话框的组合框中为用户呈现算法类型，并且我们希望组合框以它们在注册时出现在 TypeList 中的顺序显示它们。因此，在注册时，我们将算法名称添加到字符串向量中。该向量是算法工厂的一个数据成员。稍后，我们使用此向量初始化组合框，而不必担心算法的数量和名称。因为 TypeList 中的第一个类是最后注册的，所以我们从向量的末尾开始。

V_ALGNAMES::reverse_iterator rIt =  CTravelAlgFactory::m_vAlgNames.rbegin();
V_ALGNAMES::reverse_iterator rItE = CTravelAlgFactory::m_vAlgNames.rend();
for (int idx = 0; rIt != rItE; ++rIt, ++idx)
{
  m_comboAlg.InsertString(idx, rIt->c_str());
}

我之前提到过，附加算法参数是通过对话框设置的。对话框是在堆上创建的。为了在算法销毁时释放内存，我们再次使用了 TypeList。它是一个模板（文件 TypeLists.h）。

template <class Head, class Tail, int idx>
struct DestroyParamsDlgs<TypeList<Head, Tail>, idx>

统计

同样，有一个统计数据的层次结构，所有统计数据都继承自一个基类（文件 TStat.h）。

class CTStatBase
{
public:
  CTStatBase(void);
  virtual ~CTStatBase(void);
public:
  void UpdateDataCapacity(size_t maxRun);
  virtual int TravelStatID(void) const = 0;
  virtual V_CHARTNAMES* ChartNames(void) = 0;
  virtual void InitStatParams(void) {};
  virtual void CalculateDataSample(const CColony& antColony) = 0;
  virtual size_t ExportData(CChartContainer& chartContainer, int initEpoch) = 0;
public:
  V_STATDATA m_vData1;   // Data time series
  V_STATDATA m_vData2;
};

所有统计数据都存储在两个 std::vector<double> 数据成员 m_vData1 和 m_vData2 中。具体存储什么取决于统计数据的类型。例如，对于“最佳到目前为止”和“每次迭代最佳”统计数据，它们是最佳到目前为止和每次迭代最佳蚂蚁的行程长度。

为了优化内存使用，我们使用了函数 UpdateDataCapacity(size_t maxRun)。它为向量预留了正好 maxRum 个元素的内存。

这里的关键函数是 CalculateDataSample。在一次行程完成后调用它。

统计数据以数字和图表的形式呈现给用户。每个统计数据的图表数量各不相同。例如，距离统计数据有三个图表：平均距离，以及平均值 ± 标准差图表。图表的名称存储在图表名称向量中，该向量是具体统计数据的一个数据成员。

在用户或应用程序的请求下，函数 ExportData 获取累积的数据块，计算图表的数据，并附加图表。这每 100 次行程发生一次，或者在每次停止时，以及在测试完成后发生。

统计类是：

• CTStatBest：收集最佳到目前为止和每次迭代最佳蚂蚁的行程长度。
• CTStatWorst：最差到目前为止和每次迭代最差蚂蚁的行程长度。
• CTStatLength：当前迭代蚂蚁行程长度的平均值和标准差。
• CTStatDist：当前迭代距离的平均值和标准差（参见上面的行程统计）。
• CTStatBranch：分支的相同值（参见行程统计）。
• CTStatCities：起始城市分布。
• CTStatRst：连续重置之间的间隔（如果启用了重置）。

这是一个具体统计类的示例。

class CTStatBest : public CTStatBase
{
public:
  CTStatBest(void);
  virtual ~CTStatBest(void);
public:
  static CTStatBase* CreateTStatBest() { return new CTStatBest;}
  virtual int TravelStatID() const {return m_statID;}
  virtual V_CHARTNAMES* ChartNames() {return &m_vChartNames;}
  virtual void CalculateDataSample(const CColony& antColony);
  virtual size_t ExportData(CChartContainer& chartContainer, 
                                                 int initEpoch);
  static bool RegisterWithFactory(void);
public:
  static const int m_statID;
  V_CHARTNAMES m_vChartNames;
};

您可以在 TStat.cpp 文件中看到实现。

同样，我们使用类工厂和 TypeList 来向工厂注册统计数据。

typedef TYPELIST_7(CTStatBest, CTStatWorst, CTStatLength, CTStatDist,
                 CTStatBranch, CTStatCities, CTStatRst) TStatList;
typedef RegFactoryClasses<TStatList, 
                 TypeListLength<TStatList>::value -1> RegTStatStruct;

可以看出，有七种统计数据，并且 RegFactoryClasses 使用 TStatList 而不是 AlgTypeList。

诀窍在于，统计类也有名为 RegisterWithFactory 的静态函数，因此无需重写 RegFactoryClasses 的定义。

此外，我们使用 TypeList 来初始化统计类的一个静态数据成员 m_statID。例如：

const int CTStatBest::m_statID = IndexOf<TStatList, CTStatBest>::value;

IndexOf 是 Andrei Alexandrescu 定义的结构。

template <typename T> 
struct IndexOf<NullType, T>
{
  enum { value = -1};
};
template <class Tail, typename T>
struct IndexOf<TypeList<T, Tail>, T>
{
  enum {value = 0};
};
template <class Head, class Tail, typename T>
struct IndexOf<TypeList<Head, Tail>, T>
{
private:
  enum {temp = IndexOf<Tail, T>::value};
public:
  enum {value = temp == -1 ? -1 : 1 +temp};
};

TypeList 和 IndexOf 一起替换了枚举值。

Lambda 表达式、STL 算法和此应用程序

在此应用程序中，我们经常使用 STL 算法，如 std::transform、std::minmax_element、std::for_each 等。通常，我们将这些算法应用于存储某些结构的容器。为了处理数据，STL 算法需要提供谓词或函数，因为像 less_than 或 greater_than 这样的操作通常未为这些结构定义。C++ lambda 表达式在这里派上了用场。

例如，下面的代码片段计算城市坐标的最大值，以获得城市范围，即包围所有城市的正方形（文件 AntColDlg.cpp）。

float CAntColDlg::GetCitiesExtent(const MAP_CITIES& mapCities)
{
  float maxCoord = 0.0f;
  for_each(mapCities.begin(), mapCities.end(), 
     [&maxCoord](const PAIR_CITY& pair_city) ->void
     {PointF pntF = pair_city.second.m_pntLocationF; 
      float locM = max(pntF.X, pntF.Y); 
      if (maxCoord < locM) maxCoord = locM;});
....................................................
}

这是一个带有捕获子句的 lambda 表达式的示例。

首先，我们定义要操作的迭代器范围（它是城市地图的全部内容）。

其次，我们定义一个局部变量 maxCoord = 0.0f。

接下来，我们调用 for_each 算法作用于迭代器范围。lambda 表达式定义了我们将要执行的计算。

方括号中的变量是捕获的变量。VS 2012 帮助文件说：“Lambda 表达式可以访问在封闭作用域中可访问的任何具有自动存储持续时间的变量。”这是 lambda 表达式的一个非常强大的特性。

如果 lambda 表达式要更改捕获的局部变量的值，您必须通过引用传递它。

接下来是参数列表。与 STL 算法一样，它会解引用容器迭代器。

->void 是表达式的返回类型。这种声明函数返回类型的方法在 C++ 11 标准中引入。

最后是表达式的主体。

我们访问 City 的成员 m_pntLocationF，选择其 X 或 Y 坐标的最大值，并在需要时更新捕获的局部变量 maxCoord。

在代码中，您会发现 lambda 表达式与 std::transform 和其他 STL 算法一起使用。

引入您自己的蚁群优化算法

您可以看到，将您自己的算法包含在此应用程序中很简单。

• 首先，编写您的算法类，继承自 CASTravelBase。将文件 TravelAlg.h 和 TravelAlg.cpp 追加到其中。这将使您不必费心查找和包含正确的头文件，如果您使用单独的算法文件的话。
• 如果您的算法有参数，请将它们声明为类的静态数据成员。提供一个对话框或其他方式来设置这些参数。请记住，您必须为每个参数提供一对静态数据成员，即值和值名称字符串，以确保应用程序可以保存/加载参数到/从 XML 文件。
• 将您的类类型添加到 AlgTypeList 的 TypeList 定义中。不要忘记更改 TypeList 宏中的数字；例如，如果您正在添加一个类，请将 TYPELIST_6 更改为 TYPELIST_7，依此类推。
• 编译、构建并运行。

引入您自己的统计数据

这类似，但更复杂。除了您自己的统计类和统计类型列表的更正之外，您还需要向统计选择对话框添加一个按钮，并将您的图表（如果有）添加到 AntColDlg.cpp 文件中的 CAntColDlg::ResetStChartData 函数。

运行算法

选择一个算法、其参数以及相应的统计数据。选择后，通过单击 **Apply** 按钮（函数 CAntColDlg::OnBnClickedBtnapply()）来提交算法及其参数和选定的统计数据。这将启用 **Run** 或 **Step** 按钮。单击其中一个按钮将启动一个工作线程。该线程接收函数

unsigned _stdcall CAntColDlg::RunASTravel(void* colDataPtr) 

将 CAntColDlg 的指针作为参数。

m_hWorkThread = (HANDLE)_beginthreadex(NULL, 0, CAntColDlg::RunASTravel, this, CREATE_SUSPENDED , NULL);

算法的执行由此函数和函数控制：

CAntColDlg::OnTravelOnce(WPARAM wParam, LPARAM lParam)

在 C++ 11 中有一个新的类 std::thread，它可以接受带多个参数的工作函数。我没有使用它，因为它只包含在 VS 2012 中。

这是工作函数 CAntColDlg::RunASTravel 的伪代码：

• 准备一个事件对象数组来同步工作线程和主线程。
• 获取最大试次数并进入循环以执行行程。
• 重置蚂蚁殖民地。
• 为选定算法在殖民地图中为所有殖民地蚂蚁进行行程。
• 在每次行程结束时，分析图形快照的请求，如果信号触发器被发出，则设置快照标志。
• 计算并保存行程的统计数据。
• 检查重置和变异条件，如果需要，则执行重置或变异。
• 更新蚂蚁殖民地图信息素。
• 检查是否是时候将数据发送到主线程以进行行程状态的定期显示（每 100 次行程）或允许拍摄快照，并设置相应的控件事件。
• 进入等待函数并等待事件。
• 退出等待函数（如果合适）并返回到行程循环的开头。

让我们讨论工作线程和主线程的同步。

工作线程和主线程的同步

我们使用四个 Windows 事件对象来同步工作线程和主线程。

事件句柄是 CAntColDlg 的成员，并在 CAntColDlg::OnInitDialog 中创建。

m_hEvAbortRun = CreateEvent(NULL, FALSE, FALSE, NULL);// Auto reset,  // nonsignaled
m_hEvStopReq  = CreateEvent(NULL, FALSE, FALSE, NULL);// The same 
m_hEvInfoReq  = CreateEvent(NULL, FALSE, FALSE, NULL);// The same
m_hEvContRun  = CreateEvent(NULL, TRUE,  TRUE, NULL); // Manual Reset,    // signaled

事件在工作线程开始时在两个数组中排序。

HANDLE syncEvArr[] = 
{ 
  antColDlgPtr->m_hEvAbortRun, antColDlgPtr->m_hEvStopReq, 
    antColDlgPtr->m_hEvInfoReq,  antColDlgPtr->m_hEvContRun 
};
HANDLE waitEvArr[] = 
{ 
  antColDlgPtr->m_hEvAbortRun, 
  antColDlgPtr-m_hEvContRun
};

事件被初始化。

ResetEvent(syncEvArr[0]);
ResetEvent(syncEvArr[1]);
ResetEvent(syncEvArr[2]);
SetEvent(syncEvArr[3]);

继续运行的事件是两个数组中的最后一个。开始时，只有继续运行的事件被发出信号。

工作线程在处理完行程后，进入等待函数。

DWORD dwWait = WaitForMultipleObjects(4, syncEvArr, FALSE, INFINITE);
switch (dwWait)
{
case WAIT_OBJECT_0:       // Terminated by user
  antColDlgPtr->PostMessage(UWM_ONCETRAVELED, MODE_FAIL, runCnt);
  return MODE_FAIL;;
case WAIT_OBJECT_0 + 1:   // Stop initiated
  if (antColDlgPtr->m_citiesMode == MODE_STEP)
    antColDlgPtr->PostMessage(UWM_ONCETRAVELED, MODE_STEP, runCnt);
    else
    antColDlgPtr->PostMessage(UWM_ONCETRAVELED, MODE_STOP, runCnt);
  dwWait = WaitForMultipleObjects(2, waitEvArr, FALSE, INFINITE);
  switch (dwWait)
  {
  case WAIT_OBJECT_0:     // Terminated by user
    antColDlgPtr->PostMessage(UWM_ONCETRAVELED, MODE_FAIL, runCnt);
    return MODE_FAIL;
  case WAIT_OBJECT_0 + 1: // Continue; mode is to set by caller
    break;
  }
  break;
case WAIT_OBJECT_0 + 2:   // Interrupted to display the state; needs to
                                                    // set cont. event
  antColDlgPtr->PostMessage(UWM_ONCETRAVELED, MODE_RUN, runCnt);
  dwWait = WaitForMultipleObjects(2, waitEvArr, FALSE, INFINITE);
  switch (dwWait)
  {
  case WAIT_OBJECT_0:     // Terminated by user
    antColDlgPtr->PostMessage(UWM_ONCETRAVELED, MODE_FAIL, runCnt);
    return MODE_FAIL;
  case WAIT_OBJECT_0 + 1: // Continue; mode is to be set by caller
    break;
  }
  break;
case WAIT_OBJECT_0 + 3:   // Normal continuation
  break;
}

如果主线程（用户）想要停止或中断测试执行，它应该重置 *continue* 事件并设置其他事件之一，如下所示：

if (m_citiesMode == MODE_RUN)
{
  ResetEvent(m_hEvContRun);
  SetEvent(m_hEvInfoReq);
}

第一个操作是重置 m_hEvContRun。因为所有其他事件通常是非信号状态，所以工作线程将进入等待状态。它会等待直到用户将任何其他事件设置为信号状态。这将释放工作线程，工作函数将转到 switch 语句来处理从第一个等待函数返回的结果。

首先，工作线程向主线程发送一条消息：

antColDlgPtr->PostMessage(UWM_ONCETRAVELED, MODE_RUN, runCnt);

工作线程将适当的值传递给消息的 WPARAM 和 LPARAM。

如果用户请求中断测试（已设置事件 m_hEvStopReq 或 m_hEvInfoReq），以启动单步执行或停止执行，或者应用程序请求关于行程状态的信息，工作线程将进入第二个等待函数，等待用户选择继续或中止运行。这次工作线程只等待两个事件。

工作线程发送给主线程的消息在函数 CAntColDlg::OnTravelOnce(WPARAM wParam, LPARAM lParam)（文件 AntColDlg.cpp）中处理。

此函数在完成所有处理后，如果用户希望继续运行，则设置事件 m_hEvContRun。如果工作线程正在等待，这将释放它。

在完成运行后，工作线程向主线程发送消息：

antColDlgPtr->PostMessage(UWM_ONCETRAVELED, MODE_APPLY, runCnt);

然后退出。

使用 GDI+ 绘图

所有绘图都在 GDI+ 中渲染。为了实现无闪烁的渲染，我将绘制到内存位图，并且只在绘图结束时将位图传输到屏幕表面（这通常称为双缓冲）。这是一个例子：

void CStCities::OnPaint()
{
  CPaintDC dc(this);                 // Device context for painting
  Graphics gr(dc.m_hDC);             // Graphics to paint
  Rect rGdi;
  gr.GetVisibleClipBounds(&rGdi);   // The same as the clip rect
  rGdi.Width -= 1;                  // Important: right and bottom
  rGdi.Height -= 1;                 // borders are outside the rectangle          
  Bitmap clBmp(rGdi.Width, rGdi.Height);          // Memory bitmap
  Graphics* grPtr = Graphics::FromImage(&clBmp);  // As memDC
  .................................................
        // Drawing routines
  .................................................
 
  gr.DrawImage(&clBmp, rGdi);
  delete grPtr;
}

其次，为了显示起始城市作为条形图，我使用了一个**透明**的图片控件 CCitiesChart。

我将其叠加在主对话框图表控件上。代码在 CAntColDlg::OnInitDialog() 中。

WINDOWPLACEMENT contPlacement;
m_chartContainer.GetWindowPlacement(&contPlacement);
m_stCitiesChart.SetWindowPlacement(&contPlacement);

在文档/视图模型之外打印

在文章 KB133275 中，Microsoft 解释了如何从 MFC CView 之外的类进行打印。此外，互联网上还有一个关于 GDI 打印、GDI+ 打印的教程。该教程过于复杂，Microsoft 没有提及 GDI+。

尽管如此，我还是遵循了 Microsoft 示例代码的框架。

例如，这是我打印测试结果报告的方式。

首先，您使用 CPrintDialog 选择打印机并获取打印机 DC（AntColDlg.cpp）。

void CAntColDlg::PrintReport(void)
{
  CPrintDialog printDlg(FALSE,PD_USEDEVMODECOPIES|PD_HIDEPRINTTOFILE|PD_NOPAGENUMS|
                   PD_NOSELECTION|PD_RETURNDC);
  printDlg.m_pd.Flags &= ~PD_SHOWHELP;
  printDlg.m_pd.Flags &= ~PD_NOSELECTION;
  if (IDOK == printDlg.DoModal())
  {
// Get screen dpi to scale all literals like pen width, offsets, etc. e  
    CPaintDC containerDC(this);
    int scrDpiX = containerDC.GetDeviceCaps(LOGPIXELSX);
// Init and run prn report
    CPrnReport prnReport;     // Instantiate the print report class     
    prnReport.InitRepData(this);
// If true, print the first page only
    bool bPrintSel = printDlg.PrintSelection() == TRUE ? true : false;
    prnReport.PrintReport(scrDpiX, bPrintSel, printDlg.GetPrinterDC());
  }
}

所有工作都在函数（文件 PrnReport.cpp）中完成。

void CPrnReport::PrintReport(int scrDpiX, bool bPrintSel, HDC printDC)
{
  if (printDC != NULL)
  {
    CDC* pDC = new CDC;
    pDC->Attach(printDC); 
    Graphics* grPtr = Graphics::FromHDC(printDC);  // Graphics to paint
    grPtr->SetPageUnit(UnitDocument);
    grPtr->SetSmoothingMode(SmoothingModeAntiAlias);
// Get dpiRatio
    float dpiRatioX = 300.0f/scrDpiX;
    RectF rGdiF;
        grPtr->GetVisibleClipBounds(&rGdiF);     // The same as the clip rect
// Begin Printing
    pDC->StartDoc(m_algName.c_str());       // MFC functions
    pDC->StartPage();
..........................................  // Drawing functions 
    pDC->EndPage();
// Now print the best to date ant's path as a table
    if (!bPrintSel)
    {
      ...........................................
      while (true)
      {
        pDC->StartPage();
        ................................. // Drawing functions 
        pDC->EndPage();
        if (firstRow == rowsTotal)
          break;
      }
    }
    pDC->EndDoc();
    delete(pDC);
  }
}

请注意 MFC 函数 StartDoc、StartPage、EndPage 和 EndDoc 的使用。

创建自定义打印对话框

该方法是众所周知的：在 MFC 中找到 CPrintDialog 资源模板，复制它，扩展它，并编写您自己的派生自 CPrintDialog 的类，包含您喜欢的所有功能。

我花了很长时间试图找到合适的资源，并最终找到了。您可以从本应用程序复制 IDD_DLGEDGEPRINT 来节省一些时间。

您需要像这样初始化 CFileDialog 的 m_pd 结构成员（文件 DlgEdgePrint.cpp）。

CDlgEdgePrint::
  CDlgEdgePrint(BOOL bPrintSetupOnly, DWORD dwFlags, CWnd* pParentWnd)
               : CPrintDialog(bPrintSetupOnly, dwFlags, pParentWnd)
{
  m_pd.lpPrintTemplateName = (LPTSTR) MAKEINTRESOURCE(IDD_DLGEDGEPRINT); 
      m_pd.Flags |= PD_ENABLEPRINTTEMPLATE;  
  m_pd.Flags &= ~PD_SHOWHELP;
      m_pd.hInstance = AfxGetInstanceHandle(); 
}

您还必须为添加到对话框模板的控件编写处理程序。

在我的自定义打印对话框中，我只添加了一个 CStatic 控件来显示一个警告，该警告在打印对话框实例化之前就已知。

sstream_t stream_t;
stream_t << _T("Selected screen page takes ") << paperPagesPerScrPage 
   << _T(" paper pages,\n") << _T("All pages need ") 
         << totalPaperPages << _T(" paper pages.\n") 
   << _T("Screen page #1 shows ant's path,\nfor other pages") 
   << _T(" source vertex's ID = page nmb -2") << endl;
string_t str = stream_t.str();
const _TCHAR* buf = str.data();

我像这样初始化了 m_pd 成员：

CDlgEdgePrint printDlg(FALSE, PD_SELECTION|PD_USEDEVMODECOPIES|PD_HIDEPRINTTOFILE||PD_RETURNDC);
printDlg.m_pd.Flags    &= ~PD_SHOWHELP;
printDlg.m_pd.Flags    |= PD_ENABLEPRINTHOOK;
printDlg.m_pd.lpfnPrintHook = PrintHookProc;
printDlg.m_pd.nFromPage = WORD(selPage + 2);
printDlg.m_pd.nToPage   = WORD(selPage + 2);
printDlg.m_pd.nMinPage  = 1; 
printDlg.m_pd.nMaxPage  = WORD(pagesNum);
printDlg.m_pd.lCustData = (LPARAM)buf;

我在对话框初始化时，通过调用回调函数 PrintHookProc，在静态控件中写入了这段文字。

UINT_PTR CALLBACK PrintHookProc(HWND hdlg, UINT uiMsg, WPARAM wParam, LPARAM lParam)
{
  UNREFERENCED_PARAMETER(wParam);
  switch(uiMsg)
  {
  case WM_INITDIALOG:
    {
      PRINTDLG* pd = (PRINTDLG*)lParam;
      const _TCHAR* buf = (_TCHAR*)pd->lCustData;
      HWND tbHWND = (HWND)GetDlgItem(hdlg, IDC_EDGEPRN_STWARN);
      SetWindowText(tbHWND, buf);
    }    break;
  }
  return FALSE;
}

源代码和演示项目

本文档附带了应用程序源代码和 AntCol.exe 文件。

源代码中包含了它使用的库：ChartCtrlLibD.lib（Debug 版本 1.2.1）和 ChartCtrlLib.lib（Release 版本 1.2.1）。您将能够使用您自己的算法重新编译和构建 AntCol.exe。

代码是在 MS Visual Studio 2012 (VC++ 11) 和 Windows & Pro 上构建的。

如果您没有 VS 2012，您仍然可以在 MS VS 2010 中使用源代码。我在源代码 zip 文件中的 2010Project 文件夹中包含了解决方案和项目文件。源代码文件是相同的，唯一的区别是对于 VC++ 11，项目属性包含预处理器指令 _VARIADIC_MAX=10，因为在 VC++ 11 中，Microsoft 对具有许多参数的模板使用可变参数模板，并且默认的最大元素数量是五个。在 VC++ 10 中，他们使用我们为 TypeList 使用的递归定义。

要在 VS 2010 中工作，您需要 ChartCtrlLib.lib 的 VC++ 10 版本。您可以从我的文章下载它们： An MFC Chart Control with Enhanced User Interface。

历史记录

• 2013 年 8 月 22 日：初始版本，1.0.0。