进化规划（Evolutionary Programming）是20世纪60年代由美国的J.Fogel等为了求解预测问题而提出的一种有限机进化模型。Fogel等在人工智能的研究中发现，智能行为是一种具有能预测其所处环境的状态，并按照给定的目标作出适当响应的能力。他们将模拟环境描述为由有限字符集中的符号组成的序列，于是问题转化为：如何根据当前观察到的符号序列作出响应以获得最大的收益，收益的计算是按照环境中将要出现的下一个符号及预先定义好的效益目标来确定的。进化规划中常用有限状态自动机（Finite State Machine，FSM）来表示这样的策略，Fogel等借用进化的思想对一群FSM进行进化以获得较好的FSM。他们将这一方法应用于模式识别、控制系统的设计等问题中，取得了较好的结果。90年代，Fogel又将进化规划思想拓展到实数空间，使其能够用来求解实数空间中的优化计算问题，并在其变异运算中引入正态分布的技术，这样，进化规划就演变成为一种优化搜索算法，并在很多实际领域中得到了应用。90年代以来，国内从事进化规划方面的研究已渐趋成熟。为改进进化规划的实际计算性能，很多学者提出了多种变形的进化计算。例如，海军工程大学的张民等提出了一种改进的多群进化规划算法，在该算法中，进化在多个不同的子群间并行进行，通过使用不同的变异策略，实现种群在解空间具有尽可能分散探索能力的同时，在局部具有尽可能细致的搜索能力。尽管进化规划已成功地应用于多个领域，但其在人工智能方面的应用研究仍有待进行。
进化规划算法进化规划的基本思想也是源于对自然界中生物进化过程的一种模仿，主要构成如下：
（1）个体的表示方法 在进化规划中，搜索空间是一个n维空间，与此相对应，搜索点就是一个n维向量x∈Rn。算法中，组成进化群体的每一个个体X就直接用这个n维向量来表示，即
X=x∈Rn （2-52）
（2）适应度评价 在进化规划中，个体适应度F（X）是由它所对应的目标函数f（x）通过某种比例变换而得到的，这种比例变换是为了既保证各个个体的适应度总取正值，又维持各个个体之间的竞争关系，即个体的适应度由下式来确定：
F（X）=δ[f（x）] （2-53）
式中，δ为某种比例变换函数。
（3）变异算子 遗传算法和进化策略对生物进化过程的模拟着眼于单个个体在其生存环境中的进化，强调的是“个体的进化过程”。与遗传算法和进化策略的出发点不同，进化规划是从整体的角度出发来模拟生物的进化过程的，它着眼于整个群体的进化，强调的是“物种的进化过程”。所以在进化规划中不使用交叉运算之类的个体重组算子，因为这些算子的生物基础是强调个体的进化机制。这样，在进化规划中，个体的变异操作是唯一的一种最优个体搜索方法，这是进化规划的独特之处。
在标准的进化规划中，变异操作使用的是高斯变异算子，后来又发展了柯西变异算子、Levy变异算子以及单点变异算子。变异算子是区别不同变异算法的主要特征。
（4）选择算子 可采用轮赌选择、无回放随机选择、回放余数随机选择、排序选择、竞争选择等策略。竞争选择的基本过程如下：(www.xing528.com)
1）将μ个父代个体P（t）和经过一次变异运算后所产生的μ个子代个体P´（t）合并在一起，组成一个共含有2μ个个体的个体集合{P（t）∪P´（t）}；
2）对这个个体集合中的每一个个体Xk∈P（t）∪P´（t）再从这个个体集合中随机选取其他q个个体（其中μ是选择运算的参数），比较这q个个体和个体Xk之间的适应度大小，以其中适应度比Xk的适应度还要高的个体的数目作为个体Xk的得分Wk（k=1，2，…，2μ）；
3）按个体集合{P（t）∪P´（t）}中每个个体得分Wk（k=1，2，…，2μ）的大小对全部2μ个个体作降序排列，选择前μ个个体作为进化过程中的下一代群体P（t+1）。
从上面的选择操作过程中可以知道，在进化过程中，每代群体中最好的个体在比较适应度大小时总被赋予最大的得分，从而这个最好的个体总能够确保被保留到下一代群体中。与遗传算法和进化策略相比，进化规划主要具有下面几个特点：
1）进化规划对生物进化过程的模拟主要着眼于物种的进化过程，所以它不使用个体重组方面的操作算子，如交叉算子。
2）进化规划中的选择运算着重于群体中各个个体之间的竞争选择，但当竞争数目较大时，这种选择也就类似于进化策略中的确定选择过程。
3）进化规划直接以问题的可行解作为个体的表现形式，无需再对个体进行编码处理，也无需再考虑随机扰动因素对个体的影响，这样就更便于其应用。
4）进化规划以n维实数空间上的优化问题为主要处理对象。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
