遗传算法入门 2：编码卡美洛和书之屋

引言

在本期 G.A. 教程的“这一集”中，我们将对大多数 G.A. 问题解决步骤的第一阶段进行一些深入探讨。与教程的其他部分一样，我们将应用在解决旅行商问题中学习到的知识。由于我将使用 Shark 库，因此本教程及后续教程中使用的解决方案将与 Shark 库最初提出的解决方案相同（如其教程所示）。

背景

本教程引用了上一篇。因此，我强烈建议您先阅读上一篇。您可以在此处找到它。

编码卡美洛

在上一篇教程中，我们讨论了遗传算法的规范视图。我们通过演进的概念解决了一个有趣的例子，这是进化算法家族使用的一种非常强大的技术。在本系列教程的其余部分，我们将深入探讨我们之前概述的每个步骤。

我们概述的第一部分是“社区”，由于我热爱电影和动画，所以我将其命名为卡美洛（您知道亚瑟王的事吗？很酷）。我们的社区，卡美洛，由人组成（哇，多么显而易见！）。这些人，就像亚瑟一样，具有可区分的特征。身高、肤色、脚的大小等身体特征被称为表型。在最根本的层面，我们的基因包含了表型（身体特征/外观）的表示。

我喜欢将人类视为一个非常庞大而复杂的计算机程序（机器）。我们的肤色、发色和体型由我们基因中的一系列指令决定。将基因视为函数（面向对象编程中的方法）。遵循函数/方法的首要原则——模块化，一个基因只包含特定目的的指令。这些基因（方法）然后被关联并捆绑成 DNA（类）。这个 DNA 进一步被打包成染色体（命名空间 :D）。对于 G.A. 的基础知识，我们将重点关注染色体和基因。

对于一个苗条、高挑、金发的女士，我们可以欺骗自己说这些指令在一个染色体中，并这样表示它：

基因_体型	高
基因_发型	金发
基因_性别	女

更多的胡闹

基因_体型	10001010101010111111001010101100101
基因_发型	111111111111111111111111111111110011111101
基因_性别	10

您在其他教程中可能会遇到的另一个词是**等位基因**。等位基因是基因的另一种形式。在上面的表格中，我将性别基因“女”表示为“10”，我可能会，当然是愚蠢地，将男性表示为“01”，将雌雄同体表示为“11”或“00”。基因的这些替代形式称为等位基因。Tamam？（顺便说一句，这是土耳其语的“OK”。）

关于等位基因和染色体的更多信息，假设同一个女士有蓝眼睛、尖鼻子、宽肩膀和迷人的声音！我们可以再次欺骗自己说这些指令在另一个染色体中，并这样表示它：

基因_肩型	宽
基因_眼睛颜色	蓝色
基因_鼻型	尖
基因_声音	性感

如果这些特征是我们唯一的关注点，那么我们可以将我们想象中的个体建模为两个染色体，染色体 1 和染色体 2，分别包含 3 个和 4 个基因。

好的，这个生物学概念与遗传算法有什么关系？在我们第一个教程中获奖的故事中，我们将男性和女性表示为位字符串。换句话说，我们为它们创建了基因型。G.A. 涉及**基因**的重组和突变。这意味着需要表示问题域中的实体（社区中的人）的遗传形式（基因/染色体）。对这些“遗传形式”进行编码的过程称为**编码**。就像“上”有“下”，“前”有“后”一样，编码也有解码。解码是将基因型重新转换为表型表示（ bla bla bla）。

编码没有通用规则；它实际上是特定于问题的。

存在各种编码方案。**二进制编码**，就像我们上面的例子一样，是在二进制形式下对问题域的表示。在上一教程中我们获奖的故事中，我们也看到了这一点，当时我们将男性表示为

int male[SIZE] = {1,0,1,0,1,0,1,0,1};

二进制编码实际上是遗传算法中最常见和最原始的编码形式。

排列编码

众所周知，排列涉及排序。当问题域涉及排序 - 序列、模式等时，它最有效。例如

Chromosome 1: 1R 8P 6S 3T 9U 2G
Chromosome 2: 5 3 8 3 2 7 5 9

单击此处了解更多关于编码方案的信息。

图书之家

大家别激动，我只是用“库”来表达“图书馆”。G.A. 社区创建了 G.A. 库，其中包含常见的 G.A. 操作的类和方法，例如编码、选择、突变、重组、存档等。在本教程的整个过程中，我们将使用 Shark 库的一个组件，称为 EALib（进化算法库）。您可以在此处找到它及其文档。

旅行商问题

一位名叫 Johnny Walker 的推销员，应该在卡美洛拜访 10 个城市。每次旅行连接都有一个成本（即行程时间）。问题是找到一条最便宜的往返路线，该路线恰好访问每个城市一次并返回起点。

图示了本教程中使用的示例。

第一个显而易见的难题是如何编码。我们如何以适合编程的形式表示这张图？

	A	B	C	D	E	F	G	H	我	J
A	0	28	57	72	81	85	80	113	89	80
B	28	0	28	45	54	57	63	85	63	63
C	57	28	0	20	30	28	57	57	40	57
D	72	45	20	0	10	20	72	45	20	45
E	81	54	30	10	0	22	81	14	10	41
F	85	57	28	20	22	0	63	28	28	63
G	80	63	57	72	81	63	0	80	89	113
H	113	85	57	45	41	28	80	0	40	80
我	89	63	40	20	10	28	89	40	0	40
J	80	63	57	45	41	63	113	80	40	0

您可能足够**聪明**尝试二进制编码，但我会偷懒，并与 Shark 库的程序员一起使用整数数组。

const int cities[10][10] =
{
{ 0,   28,  57,  72,  81,  85,  80,  113, 89,  80  },
{ 28,  0,   28,  45,  54,  57,  63,  85,  63,  63  },
{ 57,  28,  0,   20,  30,  28,  57,  57,  40,  57  },
{ 72,  45,  20,  0,   10,  20,  72,  45,  20,  45  },
{ 81,  54,  30,  10,  0,   22,  81,  41,  10,  41  },
{ 85,  57,  28,  20,  22,  0,   63,  28,  28,  63  },
{ 80,  63,  57,  72,  81,  63,  0,   80,  89,  113 },
{ 113, 85,  57,  45,  41,  28,  80,  0,   40,  80  },
{ 89,  63,  40,  20,  10,  28,  89,  40,  0,   40  },
{ 80,  63,  57,  45,  41,  63,  113, 80,  40,  0   }
};

在我们上一篇教程中，我们基本展示了进化策略的概念。我们使用了一个雄性和一个雌性。经典的 G.A. 另一方面，处理的个体不止一个。它处理一个种群。这个种群创建了初始的搜索空间，用于利用/探索进化概念。个体数量（种群大小）没有经验法则，尽管许多 G.A. 人员似乎对 200 的种群大小情有独钟。

所以，让我们将 Johnny 的旅程（城市）表示为拥有 200 个父代和 200 个子代。

PopulationT< unsigned int > parents   ( 200, ChromosomeT< unsigned int >( cities ) );
PopulationT< unsigned int > offsprings( 200, ChromosomeT< unsigned int >( cities ) );

请参阅库的文档以获取语法。它在那里解释得很清楚，相信我！

好了，我们已经了解了编码，学习了一些生物学知识，以及为什么 G.A. 需要它。我们已经开始了一个任务，帮助 Johnny Walker 走过卡美洛的 10 个城市。在下一篇教程中，我们将根据我们在上一篇教程（社区中的问题？）中概述的内容，探讨我们大纲中的下一个概念，即与“适应度”有关的概念。