08-现实世界的应用

5.7　现实世界的应用

不管Skiena写过什么，遗传算法都能频繁有效地应用于大量的问题。它们往往用于解决不需要完美最优解的难题，例如，用传统方法无法解决的大型约束满足问题。复杂的日程安排问题就是其中的一个例子。

遗传算法在计算生物学中找到了很多用武之地，它们已被成功用于蛋白质配体停靠，即在小分子与受体结合时搜索配置方案，在这里被用于药学研究，以便更好地理解自然界的机制。

在第9章中将重温的旅行商问题（Traveling Salesman Problem），是计算机科学中最著名的问题之一。旅行商希望找到地图上的最短路径，每个城市只能恰好经过一次，且要回到起始位置。这看起来像是第4章中的最小生成树，但二者还是有区别的。旅行商问题的解是一个大的环路，目标是要最大限度地降低旅行的开销，而最小生成树则是要最大限度地降低连接每个城市的成本。为了能到达每一个城市，以最小生成树方式在城市间旅行的人可能必须访问同一个城市两次。尽管两种算法看起来很相似，但还是没有算法能在合理的时间内求解出任意城市数量的旅行商问题。遗传算法已经表明，可以在短时间内找到次优但够用的解。旅行商问题广泛应用于货物的有效配送工作。例如，FedEx和UPS的卡车调度员每天都用软件来求解旅行商问题。有助于解决问题的算法可以降低各行各业的成本。

在计算机合成艺术领域，有时会用遗传算法以随机方式模拟生成照片。请想象一下，将50个多边形随机放置在屏幕上，逐渐扭曲、转动、移动、调整大小并改变颜色，直至它们尽可能地与某张照片接近。其结果看起来会像是抽象艺术家的作品，若采用较有棱角的形状，则结果像是彩色玻璃花窗。

遗传算法是演化计算（evolutionary computation）领域的一部分。在演化计算中，与遗传算法密切相关的一个领域是遗传编程（genetic programming），其程序可用选择、交换和变异操作修改自身，以便为编程问题查找不太明显的解。遗传编程不是一种被广泛运用的技术，但不妨想象一下未来程序可以自己编写自己。

遗传算法有一个好处，就是可以轻松实现并行运行。最明显的形式就是，每个种群可以在单独的处理器上进行模拟。粒度最细的形式就是，每个个体都可以发生变异和交换，并在单独的线程中计算其适应度。介于这两者之间的形式还有很多种。