本节书摘来异步社区《Java遗传算法编程》一书中的第1章，第1.7节，作者： 【英】Lee Jacobson（雅各布森） , 【美】Burak Kanber（坎贝尔），更多章节内容可以访问云栖社区“异步社区”公众号查看。
在计算机科学中，如果处理优化问题时有许多候选解需要搜索，我们就称解的集合是“搜索空间”。搜索空间内每个特定的点就是给定问题的一个候选解。在这个搜索空间中有距离的概念，相比位置远离的解，位置彼此靠近的解更可能表现出相似的特征。为了理解这些距离在搜索空间中如何组织，请考虑下面使用二进制遗传表示的例子：
“101”与“111”只差1。这是因为只要有1个变化（0翻转到1），就能从“101”变成“111”。这意味着这些解在搜索空间中的空间距离仅为1。
另一方面，“000”与“111”是有3处不同。这就是说距离为3，在搜索空间“000”与“111”相距为3。
因为变化较少的一些解彼此较近，所以搜索空间中解的距离可以用来提供一种相似性，说明另一个解的特征相似。许多搜索算法经常将这种理解作为一种策略，以改善搜索结果。
如果搜索空间内发现的候选解标上其个体的适应度水平，我们就可以将搜索空间看成“适应度景观”。图1-1提供了一个例子，说明二维适应度景观看起来如何。
适应度景观的横轴是我们要优化的值，竖轴是对应的适应度值。需要指出，这通常是对实际情况的过度简化。大多数真实世界的应用程序都有多个值需要优化，会生成多维适应度景观。
在上面的例子中，可以看到搜索空间中的每个候选解的适应度值。这很容易看到最适应解的位置，但是，要在现实中做到这一点，搜索空间中每个候选解都需要求出适应度函数的值。对于复杂的问题，搜索空间呈指数式增长，计算每个解的适应度值是不合理的。在这种情况下，搜索算法负责找到最佳解的可能位置，同时又受到限制，仅看到搜索空间的一小部分。图1-2所示是搜索算法通常会看到什么的一个例子。
请考虑一种算法，它要搜索十亿个（1 000 000 000）可能解构成的搜索空间。即使每个解只需要1秒来对适应度求值和赋值，它仍然需要超过30年，才能搜索每个可能的解！如果我们不知道搜索空间中每个解的适应度值，我们就无法确切地知道最佳解在哪里。在这种情况下，唯一合理的方法是采用一种搜索算法，它能在可用的时间内发现足够好的解。在这些条件下，一般来说，遗传算法和进化算法能够非常有效地发现可行的、接近最佳的解。
在搜索空间进行搜索时，遗传算法使用种群的方法。作为其搜索策略的一部分，遗传算法假设两个评分不错的解可以组合，形成一个更适应的后代。这个过程可以在适应度景观（图1-3）中看出来。
遗传算法中的变异算子让我们搜索特定候选解的近邻。变异应用于一个基因时，其值随机地改变。这可以表示成在搜索空间（见图1-4）中跨出一步。
在这两个交叉和变异的例子中，得到的解都有可能比原来亲代的适应度更差（见图1-5）。
在这种情况下，如果解的表现足够差，它最终会在选择过程中从基因库删除。个体候选解小的负面变化是可以接受的，只要种群平均趋势指向更适应的解。
实现优化算法时，必须考虑一个障碍，即该算法能否很好地逃离搜索空间的局部最优位置。为了更好地表现什么是局部最优，请参考图1-6。
在这里，我们可以看到适应度景观中的两座小山，它们峰值略微不同。正如前面提到的，优化算法不能够看到整个适应度景观，相反，它能做得最好的是找一些解，它认为这些解很可能处于搜索空间的最佳位置。正是因为这种特点，优化算法通常能在不知不觉中专注于查找搜索空间的次优部分。
如果实现使用一个简单的登山算法来解决任何足够复杂的问题，这个问题很快就会引起注意。一个简单登山算法没有任何内建的方法来处理局部最优，因此往往会在搜索空间的局部最优区域中终止其搜索。一个简单的随机登山算法相当于没有种群和交叉的遗传算法。该算法相当容易理解，它从搜索空间中的随机点开始，然后评估相邻的解，尝试找到更好的解。如果登山算法在相邻位置找到了更好的解，它会移动到新位置，并再次重新启动搜索过程。通过在搜索空间中找到的任何一座山向上爬，这个过程会逐渐找到更好的解，它因而得名“登山算法”。如果登山算法再也找不到更好的解，它就假设是在山顶，并停止搜索。
图1-7展示了登山算法的典型搜索过程。
图1-7表明，简单登山算法在搜索空间的局部最优区域开始搜索时，如何很容易返回一个局部最优解。
虽然目前还无法实现在不首先求值整个搜索空间的情况下，确保避免局部最优，但该算法有许多变种，可以帮助避免局部最优。其中一个最基本而有效的方法，称为“随机重启登山”，就是从随机起始位置多次运行登山算法，然后返回它在不同运行中找到的最佳解。这种优化方法比较容易实现，而且有效性令人惊讶。其他方法诸如模拟退火方法［参见Kirkpatrick，Gelatt，and Vecchi （1983）］和禁忌搜索［参见Glover（1989）和Glover（1990）］，它们对登山算法进行了微小改变，都有助于减少局部最优。
在避免局部最优和取得接近最优的解方面，遗传算法的有效性令人惊讶。做到这一点的一种办法，是让种群能够从搜索空间的大片区域取样，定位最佳的区域，继续搜索。图1-8展示了种群在初始化时可能如何分布。
经过几代后，种群就开始一致走向前几代发现的最优解。这是因为不太适合的解会在选择过程中移除，让位给交叉和变异（见图1-9）产生的新解。
变异算子也起到了逃离局部最优的作用。变异允许一个解从当前位置跳到搜索空间的另一个位置。这个过程往往会导致在搜索空间的较优区域中发现更适合的解。
相关资源：java 遗传算法 编程