进化计算技术的优化应用

在计算机科学领域，进化计算是人工智能，进一步说是智能计算中涉及组合优化问题的一个子域。其算法是受生物进化过程中“优胜劣汰”的自然选择机制和遗传信息的传递规律的影响，通过程序迭代模拟这一过程，把要解决的问题看作环境，在一些可能的解组成的种群中，通过自然演化寻求最优解。

运用达尔文理论解决问题的思想起源于20世纪50年代。20世纪60年代，这一想法在3个地方分别发展起来。美国的Lawrence J.Fogel提出了进化编程（evolutionary programming），而来自美国Michigan大学的John Henry Holland则借鉴了达尔文的生物进化论和孟德尔的遗传定律的基本思想，并将其进行提取、简化与抽象提出了遗传算法（genetic algorithms）。在德国，Ingo Reichenberg和Hans-Paul Schwoebel提出了进化策略（evolution strategies）。比起人类设计的软件，进化算法可以更有效地解决多维的问题，优化系统的设计。

进化算法正是借用以上生物进化的规律，通过繁殖、竞争、再繁殖、再竞争，实现优胜劣汰，一步步逼近复杂工程技术问题的最优解。进化计算的主要分支有遗传算法（GA）、遗传编程（GP）、进化策略（ES）和进化编程（EP）。

1）遗传算法

遗传算法（genetic algorithms，GA）是一类通过模拟生物界自然选择和自然遗传机制的随机化搜索算法，由美国John Henry Holland教授于1975年在他的专著Adaptation in Natural and Artificial Systems中首次提出。它是利用某种编码技术作用于称为染色体的二进制数串，其基本思想是模拟由这些串组成的种群的进化过程，通过有组织的然而是随机的信息交换来重新组合那些适应性好的串。遗传算法对求解问题的本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并根据适应性来选择染色体，使适应性好的染色体比适应性差的染色体有更多的繁殖机会。

2）遗传编程

遗传编程（genetic programming，GP）的思想是Stanford大学的John Kloza在1992年出版专著Genetic Programming中提出的。自计算机出现以来，计算机科学的一个重要目标即是让计算机自动进行程序设计，即只要明确地告诉计算机要解决的问题，而不需要告诉它如何去做，遗传编程便是该领域的一种尝试。它采用遗传算法的基本思想，但使用一种更为灵活的表示方式——分层结构来表示解空间。这些分层结构的叶节点是问题的原始变量，中间节点则是组合这些原始变量的函数，这样的每一个分层结构对应问题的一个解，也可以理解为求解该问题的一个计算机程序。遗传编程即是使用一些遗传操作动态的改变这些结构以获得解决该问题的一个计算机程序。(www.xing528.com)

3）进化策略

1964年，由德国柏林工业大学的Ingo Reichenberg等提出。在求解流体动力学柔性弯曲管的形状优化问题时，用传统的方法很难优化设计中描述物体形状的参数，而利用生物变异的思想来随机地改变参数值获得了较好的结果。随后，他们便对这一方法进行了深入的研究，形成了进化计算的另一个分支——进化策略（evolution strategies，ES）。

进化策略与遗传算法的不同之处在于：进化策略直接在解空间上进行操作，强调进化过程中从父体到后代行为的自适应性和多样性，强调进化过程中搜索步长的自适应性调节，主要用于求解数值优化问题；而遗传算法是将原问题的解空间映射到位串空间之中，然后再施行遗传操作，它强调个体基因结构的变化对其适应度的影响。

4）进化编程

进化编程是（evolutionary programming，EP）由美国Lawrence J.Fogel等在20世纪60年代提出。他们在研究人工智能时发现，智能行为要具有能预测其所处环境的状态，并且具有按照给定的目标做出适当的响应的能力。在研究中，他们将模拟环境描述成是由有限字符集中符号组成的序列。

进化计算有着极为广泛的应用，在模式识别、图像处理、人工智能、经济管理、机械工程、电气工程、通信、生物学等众多领域都获得了较为成功的应用。如利用进化算法研究小生境理论和生物物种的形成、通信网络的优化设计、超大规模集成电路的布线、飞机外形的设计和人类行为规范进化过程的模拟。