造成上述欺骗问题的主要原因有两个：
编码不当或适应度函数选择不当。
如果它们均是单调关系，则不会存在欺骗性问题，但是对于一个非线性问题，难于实现其单调性。
1.欺骗函数的类型
Goldberg曾研究用适应度函数的非单调性来研究欺骗性问题。
考虑一个2位二进制最大化问题，假定“11”对应最优解，若H（0*）>H（1*），则欺骗性存在。
该条件可化为：
下面以前一种为例进行讨论，设
则有：
r<1+c-c’
c>1：
称为Ⅰ类欺骗问题，见图1，求最优化时较难
c<=1:
称为Ⅱ类欺骗问题，见图2，此问题求最优化更难
图1
图2
这两类欺骗性问题应该称为非单调问题，在非单调问题中同时存在欺骗性和非欺骗性问题。
过去，将适应度函数的非单调问题与欺骗问题同等看待，认为遗传算法只有在单调问题里有效。
但是，如果单调问题不使用遗传算法或者不使用概率搜索，一般的搜索法可能是适用的，没有遗传算法存在的必要。
即使是单调的，只有存在需要高机能交叉操作（非单调且非欺骗问题），才能使遗传算法存在有意义，这不外乎使交叉操作成为遗传算法本质作用的一个证明。
2.欺骗性化解
可以采用Grey编码或纠正适应度函数
3.遗传算法的困难问题
容易问题：
采用基本的遗传算法，易于得到最优解的场合或问题
困难问题;与上相反
遗传算法的欺骗性与遗传算法的困难性不存在对等或等价关系，这是由于遗传算法的欺骗性是从静态超平面分析给出的，并且假设个体数无偏差，而遗传算法的困难性来源于不适当的问题表示、交叉和变异的扰动作用、有限的种群大小、复杂的多模型状态图等。
3.5遗传算法动态分析
从随机过程和数理统计角度讨论遗传算法较为一般的规律，有助于较好地把握遗传算法的特性，以提高求解效率和改善求解效果。
铃木（1995年）从Markov链的角度分析了基本遗传算法（SGA）的统计规律，并得到了一些有意义的结论。
SGA的当前种群只与前一代种群有关，因此SGA可以用一个Markov链来描述。
第四章遗传算法的改进
自从1975年J.H.Holland系统地提出遗传算法的完整结构和理论以来，总多学者一直致力于推动遗传算法的发展，对编码方式、控制参数的确定、选择方式和交叉机理等进行了深入的探究，引入了动态策略和自适应策略以改善遗传算法的性能，提出了各种变形的遗传算法（VariantsofCanonicalGeneticAlgorithm,简称VCGA）.其基本途径概括起来有以下几个方面：
（1）改变遗传算法的组成成分或使用技术，如选用优化控制参数、适合问题特性的编码技术等。
（2）采用混合遗传算法
（3）采用动态自适应技术，在进化过程中调整算法控制参数和编码力度
（4）采用非标准的遗传操作算子
（5）采用并行遗传算法
本章将介绍这些方面的典型思路和集中改进的遗传算法。
4.1分层遗传算法
对于一个问题，首先随机生成N*n各样本（n>=2,N>=2）,然后将它们分成N个子种群，每个子种群包括n各样本，对每个子种群独立的运行各自的遗传算法，记它们为GAi（i=1,2,….N）。
这N个遗传算法最好在设置特性上有较大差异，这样就可以为将来的高层遗传算法产生更多种类的优良模式。
在每个子种群的遗传算法运行到一定代数后，将N个遗传算法的结果种群记录到二维数组R[1….N,1…n]中，则R[i,j]（i=1…N,j=1…n）表示GAi的结果种群的第j个个体。
同时将N各结果种群的平均适应度值记录到数组A[1….N]中，A[i]表示GAi的结果种群平均适应度。
高层遗传算法与普通遗传算法的操作相类似，也可以分为以下三个步骤：
1.选择（种群之内选择）
基于数组A[1….N]，即N个遗传算法的平均适应度值，对数组R代表结果种群进行选择操作，一些结果种群由于它们的平均适应度值高而被复制，甚至复制多次；另一些结果种群由于它们的种群平均适应度值低而被淘汰。
2.交叉（种群之间交叉）
如果R[i,1….n]和R[j,1…..n]被随机地匹配到一起，而且从位置x进行交叉（）则R[i,x+1….n]和R[j,x+1…..n]相互交换相应的部分。
这一步骤相当于交换GAi和GAj中结果种群的n-x个个体。
3.变异
以很小的概率将少量随机生成的新个体替换R[1…N,1…n]中随机抽取的个体。
至此，高层遗传算法的第一轮运行结束，N各遗传算法GAi（i=1…N）可以从相应于新的R[1….N,1…n]种群继续各自的操作。
分层遗传算法的流程图如下：
4.2CHC算法
CHC算法是Ｅshelman于1991年提出的遗传算法的缩写，第一个C代表（Crossgenerationalelitistselection）策略，H代表异物种重组（Heterogeneousrecombination），第二个C代表大变异（Cataclysmicmutation）。
CHC算法与基本遗传算法SGA不同点在于：
SGA的遗传操作比较单纯，简单地实行并行处理；而CHC算法牺牲这种单纯性，换取遗传操作的较好效果，并强调优良个体的保留。
下面分别介绍其遗传操作的改进之处。
1.选择
通常遗传算法是依据个体的适应度复制个体完成选择操作的，
而在CHC算法中，上世代种群于通过新的交叉方法产生的个体种群混合起来，从中按一定概率选择较优的个体。
这一策略成为跨世代精英选择。
其明显特征表现在：
（1）健壮性
由于这一选择策略，即使当交叉操作产生较劣个体偏多时，由于原种群多数个体残留，不会引起个体的评价值降低。
（2）遗传多样性保持
由于大个体群操作，可以更好的保持遗传过程中的遗传多样性。
（3）排序方法
克服了比例适应度计算的尺度计算
2.交叉
CHC算法使用的重组操作是对均匀交叉的一种改进。
均匀交叉对父个体位值的各位位置以相同概率实行交叉操作，这里改进之处是：
当两个父个体的位置相异的位数为m时，从中随机选取m/2个位置，实行父个体位置的互换。
显然，这样的操作对模式具有很强的破坏性，因此，确定一阈值，当个体间的海明距离低于该阈值时，不进行交叉操作。
并且，与种群进化收敛的同时，逐渐地减小该阈值。
3.变异
CHC算法在进化前期不采取变异操作，当种群进化到一定的收敛时期，从优秀个体中选择一部分个体进行初始化。
初始化的方法是选择一定比例的基因座，随机的决定它们的位置。
这个比例值称为扩散率，一般取0.35。
4.3messyGA
根据积木块假设，SGA中，定义距长的模式容易受到破坏，只有从小积木块的模式中才能最终构成最优解，这对进化模拟而言是十分不利的。
为克服这一缺点，Goldberg等在1989年提出了一种变长度染色体遗传算法，该算法在不影响模式定义距的情况下，是优良的模式得以增殖。
在生物进化过程中，其染色体长度比不是固定不变的，而是随着进化过程也在慢慢的变化。
另一方面，在遗传算法的实际应用中，有时为了简化描述问题的解，也需要使用不同长度的编码串。
例如，用遗传算法对模糊控制器规则库进行优化设计时，事先一般不知道规则数目，这样一个规则库对应一个个体，个体的染色体长度可以描述为变化的。
用染色体算法对人工神经网络结构进行优化设计时，如果各层的节点数是未知的，同样，个体染色体长度也可以描述为变化的。
变长染色体的编码采用二元编制，同时用一个二元数组表示，二元数组的第一位为固定座序号，第二位是基因座上的数值。
变长度染色体中可能在交叉操作中出现缺失位（缺失位上的值用0表示）和重复位（重复位用左边的值表示）。
例.X1（1,0）（2,1）（3,1）（4,0）（5,1）
X2（1,1）（2,1）（3,0）
X’1（1,0）（2,1）（3,1）（4,0）（2,1）（3,0）
X’2（1,1）（5,1）
X’1染色体为0110X’2染色体为10001（位码已变）
X1染色体为01101X2染色体为110
其交叉操作是切断和拼接两部分完成的。
4.4自适应遗传算法
遗传算法的参数中交配概率Pc和变异概率Pm的选择是影响遗传算法行为和性能的关键所在，直接影响算法的收敛性，Pc越大，新个体产生速率就越快。
然而，Pc过大时遗传模式被破坏的可能也越大，使得具有高适应度的个体结构很快就会被破坏，但是如果Pc过小，就不易产生新的个体结构；若Pm取值过大，那么遗传算法就变成了纯粹的随机搜索算法，Pc和Pm的确定在实际应用中是个繁琐和困难的事情。
Srinvivas等提出的自适应遗传算法（AdaptiveGA）,Pc和Pm能够随适应度自动改变：
1.当种群个体适应度趋于一致或趋于局部最优时，使Pc,Pm增大，反之减小。
2.对于适应度高于种群平均适应度的个体，使Pc，Pm减小，反之增大。
即好的个体尽量保持，差的个体尽量被替代而淘汰
当Pc，Pm恰当时，AGA算法能够在保持群体多样性的同时保证遗传算法的收敛性。
Pc，Pm可按如下简单公式计算：
（多有）
K：
是要选定的
上式虽然简单但存在问题，当f’或f趋于fmax时，Pc，Pm趋于0，f越小则Pc,Pm大。
这种调整方法对于种群处于进化后期比较合适，但在进化初期是不当的，这会使初期较优的个体处于几乎不变的状态，从而以使进化走向局部最优解。
为此对前式假如作如下修改便使f’或f趋于fmax时，Pc，Pm不会为0。
4.5基于小生境技术的遗传算法
生物学上，小生境（niche）是指特定环境中的一种组织功能。
在自然界中，往往特征、性状相似的物种相聚在一起，并在同类中交配繁殖后代。
在SGA中，交配完全是随机的，虽然这种随机化的交配形式在寻优的初级阶段保持了解的多样性，但在进化的后期，大量个体集中于某一极值点上，它们的后代造成近亲繁殖。
在用遗传算法求解多峰值函数的优化计算时，经常是只能找到个别的几个最优解，甚至往往的得到的是局部最优解。
我们希望优化算法能够找出全部最优解，引进小生境的概念，有助于实现这样的目的。
小生境技术就是将每一类个体划分为若干类，每个类中选出若干适应度较大的个体作为一个类的优秀代表组成一个种群，再在种群中以及不同种群之间通过杂交、变异产生新一代个体群。
小生境技术特别适合于复杂多峰函数的优化问题。
小生境的模拟方法主要建立在常规选择操作的改进基础上。
1.1970年，Cavichio：
当新产生的子代个体的适应度越过其父代个体的适应度时，所产生的子代个体才能替代父代个体而遗传到下一代个体中，否则父代个体仍保留在下一代种群中。
——预选择机制的选择策略。
2.1975年，DoJong:
排列机制的选择策略—一个有限的生存空间中，各种不同的生物为了能够延续生存，它们之间必须相互竞争有限的资源——设计一个排挤因子CF（一般取2或3），由种群中随机选择的1/CF个个体组成排挤成员，然后依据新产生的个体与排挤成员的相似性来排挤一些与排挤成员相类似的个体，个体之间的类似性是由海明距离来度量。
随着排挤过程的进行，群体中的个体逐渐被分类，从而形成一个个小的生成环境，并维持群体的多样性。
3共享法的选择策略（暂略，较难）
4.6混合遗传算法
众所周知，梯度法、模拟退火法等一些优化算法具有很强的局部搜索能力，而另一些含有问题相关的启发知识的启发式算法的运行效率也比较高。
如果融合这些优化方法的思想，构成一个新的混合遗传算法（hybridgeneticalgorithm）,是提高遗传算法运行效率和求解质量的一个有效手段。
目前，混合遗传算法体现在两个方面：
一是引入局部搜索过程，二是增加编码变换操作过程。
在构成混合遗传算法时，DeJong提出下面三个基本原则；
1.尽量采用原有算法的编码（这个原有指遗传原有）
2.利用原有算法全局搜索的优点
3.改进遗传算子
第五章进化计算初步
进化计算有三个分支：
（1）遗传算法（GA）
（2）进化规划（EvolutionaryPrograming）（3）进化策略（EvolutionaryStrategy）
本章将讨论进化计算的理论框架及分支的构成技术，主要介绍遗传程序设计技术。
5.1进化计算理论的基本框架
进化计算是指以进化原理为仿真依据，在计算机上实现的具有进化机制的算法和程序。
目前进化计算侧重于算法的研究，因此有时称为进化算法（EvolutionaryAlgorithm）若有性质来区分，现有的进化算法可细分为：
（1）具有代表性的、最基本的遗传算法（geneticalgorithm）（第二章）
（2）侧重于数值分析的进化策略（evolutionarystrategy）（5.2节）
（3）介于数值分析和人工智能间的进化规划（evolutionarystrategy）（5.3节）
（4）偏向进化自组织和系统动力学特性的进化动力学（evolutionarydynamics）
（5）偏向以程式表现人工智能行为的遗传程序设计（geneticprogramming）（5.4节）
（6）适应动态环境学习的分类系统（classifiersystem）（第8章）
（7）用以观察复杂系统交互的各种生态模拟系统（echosystemandetc）
（8）研究人工生命（artificallife）的元胞自动机（cellualarautomata）
（9）模拟蚂蚁群体行为的蚁元系统（antsystem）（10.3节）
基因型与表现型之间的关系是进化计算中的一个基本关系，在其复杂的非线性关系中“一因多果”和“一果多因”是突出的两个特点。
表现型的变化是对对象遗传结构和当时环境条件交互作用所致的结果，非线性效果很明显，甚至相差很大的遗传结构可能会导致类似的行为。
这样在研究基因型—表现型相互关系及其在进化过程中的规律时就必须充分利用非线性系统工具和随机过程的统计测度理论，动力学机制也是必须加以研究的动态属性。
适应度状态图描述了适应度和基因型间的关系，自适应状态图则勾画了适应度与表现型之间的联系状况。
在进化计算中算子占有重要的地位，相应的操作也应反映动态的机制。
因此，进化机制体系可归纳为：
进化计算=进化算子+进化操作+进化策略+进化计算理论
这里进化算子可以有多种形式，进化策略可容纳较为复杂的非线性动力学机制。
进化计算作为完整的体系，应包括最优性、统计分析、选择策略和相应判据等内容。
5.2进化策略
20世纪60年代初，柏林工业大学的学生I..Rechenberg和H.P.Schwefel等在进行风洞实验时，由于设计中描述物体形状的参数难以用传统方法优化，因此利用生物变异的思想来随即改变参数值，获得了较好的效果。
随后，他们对这种方法进行了深入的研究和发展，形成了进化计算的另一个分支—进化策略（EvolutionaryStrategy,EA）.
1.（1+1）-ES
早期进化策略的种群只含有一个个体，而且只使用变异操作。
在每一进化代，变异后的个体与其父个体进行比较，选择两者之优。
这种进化策略称为（1+1）-ES或二元ES。
设初期个体为，它可以代表问题解空间的一个向量。
第k代（k=1,2…..）的个体可以作为其父个体即为k-1代的子个体：
其中为独立正态随机变量。
子个体与亲代个体进行比较选择最优者作为当代个体，对于最小化问题，有：
（1+1）-ES存在很多弊端，如有时收敛不到最优解、效率较低等。
它的改进即增加种群内个体的数量，从而演化为。
2.，
1997年由Schwefel提出，其基本做法是：
种群内含有个个体，随即选取一个个体进行变异，然后取代种群中最差的个体。
与（1+1）-ES的相似之处是，每次只产生一个后代。
为了进一步提高效率，又发展成为和，并引进了交叉操作。
3.进化策略的主要特点（与GA比较）
（1）GA需要将原问题的解空间映射到位串空间中，强调个体基因的变化对其适应度的影响；
升级会员 