《Java遗传算法编程》—— 1.7 搜索空间

本节书摘来异步社区《Java遗传算法编程》一书中的第1章，第1.7节，作者： 【英】Lee Jacobson（雅各布森） , 【美】Burak Kanber（坎贝尔），更多章节内容可以访问云栖社区“异步社区”公众号查看。

1.7 搜索空间

在计算机科学中，如果处理优化问题时有许多候选解需要搜索，我们就称解的集合是“搜索空间”。搜索空间内每个特定的点就是给定问题的一个候选解。在这个搜索空间中有距离的概念，相比位置远离的解，位置彼此靠近的解更可能表现出相似的特征。为了理解这些距离在搜索空间中如何组织，请考虑下面使用二进制遗传表示的例子：

“101”与“111”只差1。这是因为只要有1个变化（0翻转到1），就能从“101”变成“111”。这意味着这些解在搜索空间中的空间距离仅为1。

另一方面，“000”与“111”是有3处不同。这就是说距离为3，在搜索空间“000”与“111”相距为3。

因为变化较少的一些解彼此较近，所以搜索空间中解的距离可以用来提供一种相似性，说明另一个解的特征相似。许多搜索算法经常将这种理解作为一种策略，以改善搜索结果。

1.7.1 适应度景观

如果搜索空间内发现的候选解标上其个体的适应度水平，我们就可以将搜索空间看成“适应度景观”。图1-1提供了一个例子，说明二维适应度景观看起来如何。

适应度景观的横轴是我们要优化的值，竖轴是对应的适应度值。需要指出，这通常是对实际情况的过度简化。大多数真实世界的应用程序都有多个值需要优化，会生成多维适应度景观。

在上面的例子中，可以看到搜索空间中的每个候选解的适应度值。这很容易看到最适应解的位置，但是，要在现实中做到这一点，搜索空间中每个候选解都需要求出适应度函数的值。对于复杂的问题，搜索空间呈指数式增长，计算每个解的适应度值是不合理的。在这种情况下，搜索算法负责找到最佳解的可能位置，同时又受到限制，仅看到搜索空间的一小部分。图1-2所示是搜索算法通常会看到什么的一个例子。

请考虑一种算法，它要搜索十亿个（1 000 000 000）可能解构成的搜索空间。即使每个解只需要1秒来对适应度求值和赋值，它仍然需要超过30年，才能搜索每个可能的解！如果我们不知道搜索空间中每个解的适应度值，我们就无法确切地知道最佳解在哪里。在这种情况下，唯一合理的方法是采用一种搜索算法，它能在可用的时间内发现足够好的解。在这些条件下，一般来说，遗传算法和进化算法能够非常有效地发现可行的、接近最佳的解。

在搜索空间进行搜索时，遗传算法使用种群的方法。作为其搜索策略的一部分，遗传算法假设两个评分不错的解可以组合，形成一个更适应的后代。这个过程可以在适应度景观（图1-3）中看出来。

遗传算法中的变异算子让我们搜索特定候选解的近邻。变异应用于一个基因时，其值随机地改变。这可以表示成在搜索空间（见图1-4）中跨出一步。

在这两个交叉和变异的例子中，得到的解都有可能比原来亲代的适应度更差（见图1-5）。

在这种情况下，如果解的表现足够差，它最终会在选择过程中从基因库删除。个体候选解小的负面变化是可以接受的，只要种群平均趋势指向更适应的解。

1.7.2 局部最优

实现优化算法时，必须考虑一个障碍，即该算法能否很好地逃离搜索空间的局部最优位置。为了更好地表现什么是局部最优，请参考图1-6。

在这里，我们可以看到适应度景观中的两座小山，它们峰值略微不同。正如前面提到的，优化算法不能够看到整个适应度景观，相反，它能做得最好的是找一些解，它认为这些解很可能处于搜索空间的最佳位置。正是因为这种特点，优化算法通常能在不知不觉中专注于查找搜索空间的次优部分。

如果实现使用一个简单的登山算法来解决任何足够复杂的问题，这个问题很快就会引起注意。一个简单登山算法没有任何内建的方法来处理局部最优，因此往往会在搜索空间的局部最优区域中终止其搜索。一个简单的随机登山算法相当于没有种群和交叉的遗传算法。该算法相当容易理解，它从搜索空间中的随机点开始，然后评估相邻的解，尝试找到更好的解。如果登山算法在相邻位置找到了更好的解，它会移动到新位置，并再次重新启动搜索过程。通过在搜索空间中找到的任何一座山向上爬，这个过程会逐渐找到更好的解，它因而得名“登山算法”。如果登山算法再也找不到更好的解，它就假设是在山顶，并停止搜索。

图1-7展示了登山算法的典型搜索过程。

图1-7表明，简单登山算法在搜索空间的局部最优区域开始搜索时，如何很容易返回一个局部最优解。

虽然目前还无法实现在不首先求值整个搜索空间的情况下，确保避免局部最优，但该算法有许多变种，可以帮助避免局部最优。其中一个最基本而有效的方法，称为“随机重启登山”，就是从随机起始位置多次运行登山算法，然后返回它在不同运行中找到的最佳解。这种优化方法比较容易实现，而且有效性令人惊讶。其他方法诸如模拟退火方法［参见Kirkpatrick，Gelatt，and Vecchi （1983）］和禁忌搜索［参见Glover（1989）和Glover（1990）］，它们对登山算法进行了微小改变，都有助于减少局部最优。

在避免局部最优和取得接近最优的解方面，遗传算法的有效性令人惊讶。做到这一点的一种办法，是让种群能够从搜索空间的大片区域取样，定位最佳的区域，继续搜索。图1-8展示了种群在初始化时可能如何分布。

经过几代后，种群就开始一致走向前几代发现的最优解。这是因为不太适合的解会在选择过程中移除，让位给交叉和变异（见图1-9）产生的新解。

变异算子也起到了逃离局部最优的作用。变异允许一个解从当前位置跳到搜索空间的另一个位置。这个过程往往会导致在搜索空间的较优区域中发现更适合的解。

《Java遗传算法编程》—— 2.10 练习 1．运行遗传算法几次，观察进化过程的随机性。它通常需要多少代来找到这个问题的一个解？ 2．扩大和减小种群规模。减小种群规模如何影响算法的速度？它是否也影响找到一个解需要的世代数？扩大种群规模如何影响算法的速度？它如何影响找到一个解需要的世代数？
《Java遗传算法编程》—— 2.9 小结 在本章中，你已经学会了实现遗传算法的基本知识。本章开头的伪代码提供了一个通用的概念模型，针对本书其余部分所有要实现的遗传算法：每个遗传算法将初始化并评估种群，然后进入一个循环，进行交叉、变异和再评估。仅当终止条件满足时，才退出循环。
《Java遗传算法编程》—— 2.8 交叉实现 为了实现轮盘赌选择，在GeneticAlgorithm类的任意位置增加一个selectParent( )方法。selectParent( )方法基本上是反着玩轮盘赌。在赌场，轮盘上已经有标记，然后旋转的轮盘，等待球落入位置。
《Java遗传算法编程》—— 2.6 交叉方法 在交叉过程中，除了用不同的选择方法，还有可用不同的方法在两个个体之间交换遗传信息。不同的问题具有不太一样的特点，采用特定的交叉方法更好。例如，“全一”问题只要求完全由1构成的字符串。字符串“00111”与字符串“10101”具有相同的适应度值，因为它们都包含3个1。
《Java遗传算法编程》—— 2.5 轮盘赌选择 轮盘赌选择（也称为适应度比例选择）是用轮盘赌为类比，从种群中选择个体的方法。这种想法是根据种群中个体的适应值，将它们放置在一个假想的轮盘上。个体的适应度越高，在轮盘上占据的空间就越多。图2-1展示了在这个过程中，个体通常如何放置。
《Java遗传算法编程》—— 2.4 基本实现 为了消除所有不必要的细节，保持最初的实现容易尝试，本书中介绍的第一个遗传算法将是简单的二进制遗传算法。 二进制遗传算法比较容易实现，对于解决许多种优化问题，它可能是非常有效的工具。你可能还记得第1章提到，二进制遗传算法是由Holland（1975）提出的原创的遗传算法。
《Java遗传算法编程》—— 2.3 关于本书的代码示例 本书中的每一章都作为一个包，放在附带的Eclipse项目中。每个包都至少有4个类。 GeneticAlgorithm类，它抽象了遗传算法本身，为接口方法提供了针对问题的实现，如交叉、变异、适应度评估和终止条件检查。
异步社区 异步社区(www.epubit.com)是人民邮电出版社旗下IT专业图书旗舰社区，也是国内领先的IT专业图书社区，致力于优质学习内容的出版和分享，实现了纸书电子书的同步上架，于2015年8月上线运营。公众号【异步图书】，每日赠送异步新书。