遗传算法和旅行商问题

• 下载源代码 - 119 Kb
• 下载演示可执行文件 - 159 Kb

目录

1. 遗传算法
   • 理论
   • 遗传算法与旅行商问题
2. 基础实现，模板类 GA<> 和 GA 选择类
3. 旅行的基因组
4. 旅行商问题应用程序
   • GA 线程
   • 用户界面
5. 环境
6. 参考

免责声明

我不是遗传算法的专家，也没有遗传算法的学位，所以本文不能用作遗传算法的书籍或教程。这里没有涉及任何关于遗传算法的数学、逻辑或代数。这只是一个程序员对遗传算法的看法，以及一个遗传算法编码的例子。请谨慎使用！任何评论和批评都将不胜感激。

遗传算法，理论

关于遗传算法的书籍和网络资源非常多。我所能做的最好的就是引用我最喜欢的网站上的一些精彩描述。

来自 Marek Obitko 网站 的定义

“遗传算法是进化计算的一部分，而进化计算是人工智能的一个快速发展的领域。正如你所猜测的，遗传算法的灵感来源于达尔文的进化论。简单地说，通过遗传算法解决问题的解是通过进化的。”

来自 Generation5.org 的解释

“遗传算法并不难编程或理解，因为它们是基于生物学的。从现实生活中的进化来思考可能会帮助你理解。下面是一个通用遗传算法的步骤：

创建随机初始状态

初始种群由随机选择的解（相当于染色体）创建。这与符号人工智能系统不同，后者的初始状态已经在问题中给出。

评估适应度

为每个解（染色体）分配适应度值，取决于它离解决问题（从而得到期望问题的答案）有多近。（这些“解”不应与问题的“答案”混淆，可以将其视为系统为达到答案可能采用的特征。）

繁殖（& 子代变异）

具有较高适应度值的染色体更有可能繁殖后代（后代在繁殖后可能会发生变异）。后代是父代和母代的产物，其构成是父代和母代基因的组合（这个过程称为“交叉”。

下一代

如果新一代包含一个产生接近或等于期望答案的输出的解，则问题已解决。如果不是这种情况，则新一代将经历与其父代相同的过程。这将持续到找到一个解。”

在我看来，遗传算法易于理解，并且使用 C++ 很容易实现。遗传算法同时的优点和缺点是鲁棒性。即使你的一些功能实现不正确，遗传算法也会继续运行，并或早或晚地解决问题（或找到任何局部最优解）。这种特性无疑会在调试和调优过程中造成一些麻烦。另一个有趣的问题是如何从现有的交叉、变异、基因表示等算法中选择最佳算法。

有关遗传算法理论的一些有用链接，请参阅参考文献主题。

遗传算法与旅行商问题

关于旅行商问题

再次引用来自 http://www.math.princeton.edu/tsp/

“旅行商问题，简称 TSP，是这样的：给定有限数量的“城市”以及每对城市之间的旅行成本，找出访问所有城市并返回起点的最便宜的路线。”

基因组与算法

我们不能对旅行商问题使用传统的表示和算法，因为每个城市在基因中都必须是唯一的，不能重复。

对于基因表示，我使用顺序表示，其中城市按访问顺序排列。这是旅行商问题基因组的常用方法。

Example: [9 3 4 0 1 2 5 7 6 8]

经过多次测试和研究，我选择了 J. Grefenstette 的贪婪交叉算法。

引自 Sushil J. Louis

“贪婪交叉选择一个父代的第一个城市，比较两个父代离开该城市的城市，并选择较近的城市来延长行程。如果一个城市已经出现在行程中，则选择另一个城市。如果两个城市都已出现，则随机选择一个未选择的城市。”

根据我的经验，这是一种非常有效的方法。

变异

我们不能像传统的变异那样改变基因的位。相反，我们必须交换路径中城市的顺序。

Example:
  Before mutation   [0 1 2 3 4 5 6]
  After mutation    [0 1 3 2 4 5 6]

有很多方法可以进行这种交换操作。最简单的方法是使用随机交换。不幸的是，这种策略无法快速达到最优解，但可以防止收敛到局部最优解。此外，我还使用了贪婪交换变异。

再次引自 Sushil J. Louis

“贪婪交换的基本思想是随机选择一个染色体的两个城市，如果新的（交换后的）行程长度比旧的短，则交换它们。”

在浏览网页时，我发现了关于遗传算法的研究，由 Hiroaki Sengoku 和 Ikuo Yoshihara 撰写的 《使用遗传算法的快速旅行商问题求解器》。这是我见过的最快的算法。不幸的是，它是 Java 实现的，没有任何源代码。我只找到了一份 PDF 文档描述了该算法：arob98.pdf 阅读和研究之后，我在代码中使用了“2-opt 变异”的思想。这种方法与贪婪交换变异的想法相同，但更广泛，更有效。将其添加到代码后，我极大地提高了程序在小规模和中等规模数据集（最多 200 个城市）上的速度。然而，对于大型数据集（1000 个城市及以上），这种启发式方法是一个非常慢的方法。

选择

我实现了三种选择方法：轮盘排名、轮盘成本和锦标赛。当然，我也使用了精英主义。

轮盘赌选择

来自 Marek Obitko 网站 的定义

“成本选择：根据适应度选择父代。染色体越好，被选中的机会就越大。想象一个轮盘赌，其中包含种群中的所有染色体，每个染色体的位置大小与其适应度函数成正比。
排名选择：当适应度差异很大时，之前的选择会出现问题。例如，如果最佳染色体的适应度占轮盘赌的 90%，那么其他染色体被选中的机会将非常渺茫。排名选择首先对种群进行排名，然后每个染色体根据其排名获得适应度。最差的适应度为 1，次差的为 2，依此类推，最好的适应度为 N（种群中的染色体数量）。”

锦标赛选择与精英主义

来自 W. B. Langdon, 伦敦大学学院 的定义

“一种从种群中选择个体的机制。从种群中随机选择一组（通常在 2 到 7 个个体之间）并选择最佳的（通常只有一个，但可能更多）。精英遗传算法是这样一种算法：它始终在种群中保留迄今为止找到的最佳个体。锦标赛选择自然具有精英主义。”

在我看来，经过测试，轮盘排名和锦标赛选择在旅行商问题的情况下速度稍快。对于其他问题，其他选择算法可能更好。

协同进化。迁移

我在网上没有找到太多关于这些方法的文档。基本思想是：允许同时进化多个种群。描述来自 Generation5.org 网站

“遗传算法很棒，但它们也有自己的问题。一个大问题是遗传算法倾向于陷入局部最优解。换句话说，它们会找到一个合理的解决方案，但不是最佳解决方案。已经设计出了几种方法来解决这个问题，我们将要研究的方法是协同进化。”

同时，协同进化的思想允许利用 WinNT\2k 机器的多 CPU SMP 能力。我们可以轻松地在单独的线程中运行多个遗传算法，而不会受到任何影响。为了在不同的遗传算法之间交换数据，我们可以迁移种群中的最佳基因。

基础实现
模板类 GA<> 和 GA 选择类

GA<> 类实现了遗传算法的基础逻辑：重组、变异。用户可以通过 GA<> 类的方法管理基因种群。它维护基因种群和基因上下文、选择方法以及随机化方法。用户可以通过模板参数指定此类的行为。

template <typename Traits, typename Selection> class GA {…}

模板参数 Traits 必须为 Gene 类、Random 类、Population 容器类和线程同步类定义 typedef。

模板参数 Selection 必须提供遗传算法的选择算法。现在有三个此类：selection_tournament<>、selection_roulette_cost<> 和 selection_roulette_rank<>。

GA<> 接口

• init - 初始化种群
• update - 计算适应度值并返回最佳基因或 end()
• find_best - 查找适应度最佳的基因
• epoch - 生成下一代种群（选择、交叉、变异等）
• recombine - 进行选择，生成新基因，移除非精英父代并移除重复基因
• mutate - 尝试变异基因
• migration - 在种群之间交换最佳基因
• sort - 根据适应度值对种群中的基因进行排序（将最佳基因移到种群开头）
• begin - 返回指向种群第一个（最佳）基因的迭代器
• end - 返回指向种群末尾之后的迭代器
• size - 返回种群的大小

使用 GA<> 类的示例

typedef ga_traits<RandomCRT> traits;
typedef GA<traits, selection_tournament<traits> > tGA;
traits::Gene::Context context;
tGA ga(50, &context);		
tGA::iterator it = ga.update();
while(it == ga.end())
{
	ga.epoch(); 
	it = ga.update(); 
}
traits::Gene* gnp = (*it); 

旅行的基因组

class TSPData

旅行上下文保存旅行数据、辅助数据以及用于交叉操作的方法。

struct TSPBase

基本基因类具有特定于线程的内存池，用于内存优化。在计算过程中，遗传算法会创建和销毁大量动态基因对象。使用默认内存分配例程非常低效。取而代之的是，我使用了一个特殊的内存池类，该类从进程堆中预分配了一大块内存，然后缓存释放的块。

class TSPGene<> : TSPBase

基因实现
每个基因保存销售员的路径（行程）以及该行程的适应度值。当然，行程成本越低，基因的适应度越好。它包含一些构造函数和用于变异和启发式计算的方法。默认构造函数创建带有随机行程的基因，并为交叉操作使用另一个构造函数。

TSPGene* gnp = new TSPGene(parent1, parent2).

它根据父代基因的遗传物质生成后代。

TSP 应用程序，GA 线程

对于每一次协同进化，_Main 类都会创建一个单独的线程，其中包含 GA<> 类的实例。根据用户的设置，它会创建一个具有三种选择方法之一的遗传算法，并设置种群大小、精英大小、迁移大小、启发式值、变异和交叉概率。

然后，在每个回合（或 AI 术语“epoch”）中，它会调用重组、变异和启发式方法，并用最佳基因的结果更新应用程序的面板。它还试图防止收敛到局部最优解，并在适应度一段时间内保持不变时终止 50% 的种群。

TSP 应用程序，用户界面

用户可以更改遗传算法的设置，以便根据点集的尺寸和形状对其进行调整。

• 协同进化字段：协同进化的数量（单独的线程）从 1 到 16。默认值为 CPU 数量 * 2。
• 种群字段：每个协同进化的种群大小，从 10 到 1000。
• 精英字段：种群中的精英大小，从 0 到种群大小。
• 迁移字段：迁移基因的大小，从 0 到种群大小。
• 启发式字段：每个 epoch 中通过启发式方法改进的最佳基因的大小。注意：在大种群中，计算解决方案可能会非常缓慢。
• 交叉字段：交叉概率，从 0 到 100。
• 变异字段：变异概率。从 0 到 100。
• 选择组合框：选择方法（轮盘排名、轮盘成本和锦标赛）。
• 删除重复项复选框：使用自然选择算法进行设置。它消除相似的基因以避免过早收敛。

环境

我使用了 VC++ 6.0。SP5，Win2k SP2，MS Platform SDK 2001 年 4 月。

并在 Win2k SP2 IE 6.0、Win2k SP1 IE 5.0、Win ME IE 5.5、Win 98 SE IE 5.0 上进行了测试。

参考文献

1. S.Hsiung 和 J.Matthews，Generation 5 - 遗传算法与遗传编程
   
   
2. Marek Obitko，遗传算法导论
   
   
3. Hiroaki Sengoku 和 Ikuo Yoshihara，使用遗传算法的快速旅行商问题求解器
   
   
4. Sushil J. Louis 和 Rilun Tang，
   
   • 用于旅行商问题的交互式遗传算法,
   • 具有记忆的遗传算法用于旅行商问题,
   • 增强具有记忆的遗传算法以解决旅行商问题
     
     
5. Sergey Isaev，遗传算法
   
   
6. W. B. Langdon，遗传编程与数据结构
   
   
7. 求解旅行商问题