七种改进的遗传算法： 1、 分层遗传算法（Hierarchic Genetic Algorithm） 2、 CHC算法 3、 Messy算法 4、 自适应遗传算法（Adaption Genetic Algorithm） 5、 基于小生境技术的遗传算法（Niched Genetic Algorithm，简称NGA） 6、 并行遗传算法（Parallel Genetic Algorithm） 7、 混合遗传算法：遗传算法与最速下降法相结合；遗传算法与模拟退火法（Simulated Annealing）相结合

改进的遗传算法（一） 经证明，简单遗传算法在任何情况下（交叉概率Pc,变异概率Pm，任意初始化，任意交叉算子，任意适应度函数）都是不收敛的，且不能搜索到全局最优解。（充分证明一点：便宜没好货，好算法不简单阿）。通过改进遗传算法，即在选择作用前（或后）保留当前最优解，则能保证收敛到全局最优解。 传说中危害极大的早熟现象具体表现如下： 1、群体中所有的个体都陷于同一极值而停止变化。 2、接近最优解的个体总是被淘汰，进化过程不收敛。 消除早熟现象的方法： 1、动态确定变异概率，既可防止优良基因因变异而遭到破坏，又可在陷入最优解时为种群引入新的基因。 2、改进选择方式，放弃赌轮选择，以避免早期的高适应度个体迅速占据种群和后期的种群中因个体的适应度相差不大而导致种群停止进化。（赌轮选择方式会使每一个个体都获得复制一份的机会，体现不出好的个体的竞争力，无法实现遗传算法优胜劣汰的原则）。于是，采取一种基于种群的按个体适应度大小排序的选择算法来代替赌轮选择方法。 first() {将种群众的个体按适应度大小进行排序} while 种群还没有扫描完 do {排在前面的个体复制两份；中间的复制一份；后面的不复制；}

下面将改进的遗传算法具体描述如下： 1、在初始种群中，对所有的个体按其适应度大小进行排序，然后计算个体的支持度和置信度。 2、按一定的比例复制（即将当前种群中适应度最高的两个个体结构完整地复制到待配种群中）。 3、按个体所处的位置确定其变异概率并变异；按优良个体复制4份，劣质个体不复制的原则。 4、从复制组中孙继选择两个个体，对这两个个体进行多次交叉，从所得的结果中选择一个最优个体存入新种群 5、弱满足结束条件，则停止；不然，转到第一步，直至找到所有符合条件的规则。 本算法的优点：在各代的每一次演化过程中，子代总是保留了父代中最好的个体，以在“高适应度模式为祖先的家族方向”搜索出更好的样本，从而保证最终可以搜索到全局最优解。

遗传算法求解多目标优化问题 解决含多目标和多约束的优化问题称为多目标优化问题（Multi-objective Opimization）。 本项目为多目标优化问题 Pareto最优解：不存在比其更优的解。常用方法： 1、 权重系数变换法：给每个目标函数赋予权重，其线性加权和为总的目标函数。 2、 并列选择法：先将群体中的全部个体按子目标函数的数目均等地划分为一些子群体，对每个子群体分配一个子目标函数，各个子目标函数在相应的子群体中独立地进行选择运算，各自选择出一些适应度高的个体组成一个新的子群体，然后再将所有这些新生成的子群体合并成一个完整的群体，在这个群体中进行交叉和变异操作，从而生成下一代的完整群体，如此不断地进行“分割—并列选择—合并”操作，最终可求出多目标优化问题的Pareto最优解。 3、 排列选择法：基于Pareto最优个体（Pareto最优个体是指群体中的这样一个或一些个体，群体中的其他个体都不比它或它们更优越），对群体中的各个个体进行排序，依据这个排列次序来进行进化过程中的选择运算，从而使得排在前面的Pareto最优个体将有更多的机会遗传到下一代群体中。如此这样经过一定代数的循环之后，最终就可求出多目标最优化问题的Pareto最优解。 4、 共享函数法：利用小生境遗传算法，将相同个体或类似个体的数量加以限制，以便能够产生出种类较多的不同的最优解。对于一个个体X，在它的附近还存在有多少种、多大程度相似的个体，是可以度量的，这种度量值称为小生镜数。 5、 混合法：选择算子的主体使用并列选择法，然后通过引入保留最佳个体和共享函数的思想来弥补只使用并列选择法的不足之处。（1）并列选择过程；（2）保留Pareto最优个体过程，对于子群体中的Pareto最优个体，不让其参与个体的交叉运算和变异运算，而是将这个或这些Pareto最优个体直接保留到下一代子群体中；（3）共享函数处理过程。 遗传算法有效性的理论依据为模式定理和积木块假设。模式定理保证了较优的模式（遗传算法的较优解）的样本呈指数级增长。积木块假设提出，遗传算法具备寻找到全局最优解的能力，即具有低阶、短距、高平均适应度的模式（积木块）在遗传算子作用下，相互结合，能生成高阶、长距、高平均适应度的模式，最终生成全局最优解。 基于三值字符集{0，1，*}所产生的能描述具有某些结构相似性的0、1字符串集的字符串称作模式。模式H中确定位置的个数称作该模式的阶数。一个模式的阶数越高，其样本数就越少，因而确定性越高。模式H中第一个确定位置和最后一个确定位置之间的距离称作该模式的定义距。

模式定理：在遗传算子选择、交叉和变异的作用下，具有阶数低、长度短、平均适应度高于群体平均适应度的模式在子代中将以指数级增长。

积木块假设（Building Block Hypothesis）：阶数低、长度短、适应度高的模式（积木块）在遗传算子作用下，相互结合，能生成阶数高、长度长、适应度高的模式，可最终生成全局最优解。

在遗传算法中，将所有妨碍适应度高的个体的生成从而影响算法正常工作的问题统称为欺骗问题（Deceptive Problem）。

竞争模式：若模式H和H’中*的位置完全一致，但任一确定位的编码均不同，则称H和H’互为竞争模式。

欺骗性：假设f(X)的最大值对应的X的集合为X*，H为一包含X*的m阶模式，H的竞争模式为H’，而且f(H)>f(H’)，则f为m阶欺骗。

最小欺骗性：在欺骗问题中，为了造成骗局所需设置的最小的问题规模（即阶数）成为最小欺骗性。

早熟（Premature Convergence，简称PC）：未成熟收敛，即群体中个体的多样性过早地丢失，从而使算法陷入局部最优点。主要表现在两个方面： 1、 群体中所有的个体都陷入同一极值而停止进化。 2、 接近最优解的个体总是被淘汰，进化过程不收敛。

未成熟收敛的主要原因： 1、 理论上考虑的选择、交叉、变异操作都是绝对精确的，它们之间相互协调，能搜索到整个解空间，但是在具体实现时很难达到这个要求。 2、 所求解的问题是遗传算法欺骗问题。当解决的问题对于标准遗传算法来说比较困难时，遗传算法就会偏离寻优方向，这种问题被称为遗传算法欺骗问题。 3、 遗传算法处理的群体是有限的，因而存在随机误差，它主要包括取样误差和选择误差。取样误差是指所选择的有限群体不能代表整个群体所产生的误差。选择误差是指不能按期望的概率进行个体选择。

遗传算法早熟的具体表现： 1、 在进化初始阶段，生成了具有很高适应度的个体X。 2、 在基于适应度比例的选择下，其他个体被淘汰，大部分个体与X一致。 3、 相同的两个个体交叉，从而未能生成新个体。 4、 通过变异所生成的个体适应度高但数量少，所以被淘汰的概率很大。 5、 群体中的大部分个体都处于与X一致的状态。

防止未成熟收敛的方法： 1、 重新启动法：碰到未成熟问题而不能继续时，随即选择一组初始值重新进行遗传算法操作。 2、 配对策略（Mating Strategies）：为了维持群体的多样性，有目的的选择配对个体，以防止根本不相似的个体进行配对。Eshelman提出了一种可以更直接的防止相似个体交配的方法—防止乱伦机制（Incest Prevention Mechanism）：参与交配的个体是随机配对的，但只有当参与配对的个体间的海明距离超过一定阈值时，才允许他们进行交配。 3、 重组策略（Recombination Strategies）：就是使用交叉算子。主要是从使用频率和交叉点两方面考虑，来维持群体的多样性。 4、 替代策略（Replacement Strategies）：确定在选择、交叉产生的个体中，选择哪一个个体进入新一代群体。

性能评估： 目前，遗传算法的评估指标大多采用适应度值。 1、 在线性能（On-line Performance）评估准则：可用从第一代到当前的优化进程的平均值来表示。 2、 离线性能（Off-line Performance）评估准则：是在特定时刻或特定值的最佳性能的累积平均。即在进化过程中，每进化一代，就统计目前为止的各代中的最佳适应度或最佳平均适应度，并计算对进化代数的平均值。 离线性能用于测试算法的收敛性，在应用时，优化问题的求解可以得到模拟，在一定的优化进程停止准则下，当前最好的解可以被保存和利用；而在线性能优于测量算法的动态性，在应用时，优化问题的求解必须通过真实的实验在线实现，可以迅速得到较好的优化结果。

一个好的优化算法为：当xi能稳定地接近于全局极小点（或极大点）的邻域时，迅速收敛于x*，当满足给定的收敛准则时，迭代中止。

小生境技术：排挤机制—-在一个有限的生存空间中，各种不同的生物为了延续生存，必须相互竞争各种有限的生存资源。差别较大的个体由于生活习性不同而很少竞争，处于平衡状态的大小固定的种群，新生个体将代替与之相似的旧个体。排挤机制用海明距离来度量个体之间的相似性。

共享函数：用来度量两个个体的相邻关系和程度。给定个体g，它的共享函数由它与种群中的其他个体的相似程度决定。将g与种群中其他个体逐个比较，若很相似，则对g的共享函数加一个较大值；否则，就加一个较小值。个体共享度为该个体与群体内其他个体共享函数之和。