进化计算

进化计算是一种模拟自然界生物进化过程与机制，进行问题求解的自组织、自适应的随机搜索技术。它以达尔文进化论的“物竟天择、适者生存”作为算法的进化规则，并结合孟德尔的遗传变异理论，将生物进化过程中的繁殖、变异、竞争和选择引入到了算法中，是一种对人类智能的演化模拟方法。进化计算有着遗传算法、进化策略、进化规划和遗传规划四大分支。其中，遗传算法是进化计算中最初形成的一种具有普遍影响的模拟进化优化算法。

详细…

基本过程

进化计算尽管有多个重要分支，但它们却有着共同的进化框架。

   若假设P为种群(Population，或称为群体)，t为进化代数， P(t)为第t代种群 , 则进化计算的基本结构可粗略描述如下：
   {  确定编码形式并生成搜索空间；
      初始化各个进化参数，并设置进化代数t=0；
      初始化种群P(0);
      对初始种群进行评价（即适应度计算）；
      while（不满足终止条件）do
          {
          t=t+1;
          利用选择操作从P(t-1)代中选出P(t)代群体；
          对P(t)代种群执行进化操作；
          对执行完进化操作后的种群进行评价（即适应度计算）；
          }
   }
   可以看出，上述基本结构包含了生物进化中所必需的选择操作、进化操作和适应度评价等过程。

特点

进化计算的思想主要来源于自然界的生物进化，因此它具有极强的自适应性和很好的环境自适应能力。与传统算法相比，进化计算具有以下优良特征。

自组织性：在应用进化计算进行问题求解时，一旦确定了编码方案、适应值函数及遗传算子，算法就会利用进化过程中所获得的信息自行组织搜索。这些信息主要是每个种群个体的适应度值，搜索过程将在这些适应度值的指导下，使个体随着进化代数的增加而逐步逼近目标。
自适应性：进化计算主要依据的是自然界“优胜劣汰，适者生存”的选择策略。一般来说，那些适应度值大的个体会具有较高的生存概率，或者说具有与环境更加适应的基因结构。这些个体再经过选择、交叉、变异等进化操作，就有可能产生出与环境更加适应的后代。这样，就可以不断改进种群的性能，使算法具有自适应环境的能力。
并行性：从进化计算的基本结构可以看出，进化计算是从由多个个体组成的初始种群开始搜索的，并且其搜索过程的每一步都是对种群中的所有个体同时进行操作，因此它应该是一种多点并行搜索方法。
多解性：进化计算的多点并行搜索方式，不仅能够使算法从多点出发，而且还能够进行多目标搜索和实现多目标求解。
全局优化性：进化计算的多点并行搜索过程是在整个搜索空间的各个部分同时进行的。这种方式不仅可以提高搜索效率，同时，更大程度地避免了搜索陷入局部最优解的可能，使得其搜索结果为全局最优，或者至少是全局最近最优。
内在学习性：学习是整个进化过程自身具有的不可分割的一种行为。进化计算的内在学习主要包括宗亲学习(phylogenetic learning)、社团学习(sociogenetic learning)和个体学习(ontogenetic learning)三种方式宗亲学习是指父代通过遗传，将其优异特性传递给子代，使子代能够通过其家庭成员的“血缘”继承方式学到先辈的优异特性。社团学习是指在一个独立群体内部所进行的知识和结构的共享。个体学习是指生物体通过不断实践来积累知识和经验，以增强自身的自适应能力。在这些学习方法中，个体学习是生物体为了自身生存的一种必然行为，也是自然界中发生最为频繁的一种学习方式。
统计性:进化计算实际上是一种利用概率转移规则指导的随机搜索技术，其选择、交叉、变异等操作都是以概率的方式进行的。
稳健性:稳健性是指在不同条件和环境下算法的适应性和有效性。当用进化计算求解不同问题时，只需要修改相应的适应度函数，而无须改变算法的其他部分，因此它具有较好的适应性。同时，由于进化计算具有自然系统的自适应特征，因此通过对算法在效率和效益之间的权衡，不仅能够使它适应不同的环境，而且能够取得较好的效果。

应用领域

在应用方面，进化计算主要适应于较少依赖于目标函数值，且缺乏搜索所需要的辅助信息的一类问题。而对于那些目标比较明确，且有较多辅助信息可用的问题，进化计算不具有优势。目前，进化计算较为成功的应用领域包括机器学习、模糊系统、人工神经网络训练、程序自动生成、专家系统的知识库维护、数据挖掘、多目标规划等。

遗传算法

遗传算法的基本思想(美国密执安大学霍兰德教授1962提出)是使用模拟生物和人类进化的方法来求解复杂问题。它从初始种群出发，采用优胜略汰、适者生存的自然法则选择个体，并通过杂交、变异产生新一代种群，如此逐代进化，直到满足目标为止。

详细…