Page 153 - 大数据技术及安全研究

第四章 大数据时代演化算法与进化算法的有关分析

设计便是在该领域的一种尝试。它采用遗传算法的基本思想，但使用一种更为灵
活的表示方式——分层结构来表示解空间。这些分层结构的叶结点是问题的原始
变量，个间结点则是组合这些原始变量的函数。它们很类似于 LISP 语言中的 S-
表达式。这样的每一个分层结构对应问题的一个解，也可以理解为求解该问题的

一个计算机程序。遗传程序设计即是使用一些遗传操作动态地改变这些结构以获
得解决该问题的可行的计算机程序。遗传程序设计的思想是 Stanford 大学的 J. R.
Koza 在 20 世纪 90 年代初提出的。
（三）特点

1. 智能性
演化计算的智能性包括自组织、自适应和自学习性等。采用演化计算求解问
题时，在确定了编码方案、适应值函数及遗传算子以后，算法将利用演化过程中
获得的信息自行组织搜索。由于基于自然的选择策略为：适者生存、不适应者淘

汰，故而适应值大的个体具有较高生存概率。通常适应值大的个体具有与环境更
适应的基因结构，再通过杂交和基因突变等遗传操作就可能产生与环境更适应的
后代。演化算法的这种自组织、自适应特征同时也赋予了它具有能根据环境的变
化自动发现环境的特性和规律的能力。自然选择消除了算法设计过程中的一个最

大障碍：即需要事先描述问题的全部特点，并说明针对问题的不同特点算法应采
取的措施。于是，利用演化计算的方法我们可以解决那些结构尚无人能理解的复
杂问题。
2. 本质并行性

演化计算的本质并行性表现在两个方面：
一是演化计算是内在并行的，即演化算法本身非常适合大规模并行。最简
单的并行方式是让几百甚至数千台计算机各自进行独立种群的演化计算，运行过
程中甚至不进行任何通信（独立的种群之间若有少量的通信一般会带来更好的结

果），等到运算结束时才通信比较，选取最佳个体，这种并行处理方式对并行系
统结构也没有什么限制和要求。可以说，演化计算适合在目前所有的并行机或分
布式系统上进行并行处理，而且对其并行效率没有太大的影响。
二是演化计算的内合并行性。由于演化计算采用种群的方式组织搜索，从而

它可以同时搜索解空间内的多个区域，并相互交流信息，这种搜索方式使得它虽
然每次只执行与种群规模成比例的计算，而实质上已进行了大约 O（N3）次有

·141·