遗传算法-3

确定问题的编码方案确定适配值函数遗传算子的设计算法参数的选取算法终止准则从算法流程看，GA算法按照以下步骤进行第四节算法关键参数与操作的设计一、编码目的：将问题的解用一种码表示，将问题的状态空间与GA的码空间相对应。码长码制1、问题空间与GA空间遗传算法不能直接处理问题空间的参数，必须把它们转换成遗传空间的、由基因按一定结构组成的染色体或个体。这一转换过程实际上是将问题空间转换为GA空间，它们的对应关系如下图表示。图GA空间与问题空间的对应关系P2P1CP1P2C交叉GA空间问题空间编码译码2、编码评估规范评估编码策略常采用以下3个规范：完备性（Completeness）：问题空间中的所有点（后选解）都能作为GA空间中的点（染色体）表现。问题空间的所有解都能表示为所设计的基因型。健全性（Soundness）：GA空间中的染色体能对应所有问题空间中的解。任何一个基因型都对应于一个可能解。非冗余性（Non-redundancy）：染色体和后选解一一对应。问题空间和表达空间一一对应。3、编码技术遗传算法用到的一般编码技术有：一维染色体编码多参数映射编码可变染色体长度编码二维染色体编码树结构编码多种编码方式二进制编码；浮点数编码；格雷码编码；符号编码；复数编码；DNA编码等。二进制编码与浮点数编码的比较在交叉操作时，二进制编码比浮点数编码产生新个体的可能性多；在变异操作时，二进制编码的种群稳定性比浮点数编码差。二、群体设定1、初始群体的设定一般来讲，初始群体的设定可采取如下的策略：根据问题固有知识，设法把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定初始群体。先随机生成一定数目的个体，然后从中挑出最好的个体加到初始群体中。这个过程不断迭代，直到初始群体中个体个数达到要求。一般情况下，遗传算法在群体初始化阶段采用的是随机数初始化方法。采用生成随机数的方法，对染色体的每一维变量进行初始化赋值。初始化染色体时必须注意染色体是否满足优化问题对有效解的定义。如果在进化开始时保证初始群体已经是一定程度上的优良群体的话，将能够有效提高算法找到全局最优解的能力。2、群体多样性根据模式定理，在二进制编码的前提下，为了满足GA的隐并行性，群体个体数只要设定为即可，其中为染色体长度。2/2LL或称适应度函数。目的：对个体进行评价，是优化过程的依据。三、适配值函数1、目标函数映射成适应度函数2、适应度函数的设计对GA的影响评估函数用于评估各个染色体的适应值，进而区分优劣。影响算法对种群的选择，恰当的评估函数应该能够对染色体的优劣做出合适的区分，保证选择机制的有效性，从而提高群体的进化能力。评估函数的设置同优化问题的求解目标有关。比如在求解函数优化问题时，问题定义的目标函数可以作为评估函数的原型。评估函数应满足较优染色体的适应值较大的规定。因此对于一些求解最大值的数值优化问题，我们可以直接套用问题定义的函数表达式。为了更好地提高选择的效能，可以对评估函数做出一定的修正。目前主要的评估函数修正方法有：线性变换；乘幂变换；指数变换等。适应度函数的重要性适应度函数的选取直接影响遗传算法的收敛速度以及能否找到最优解。一般而言，适应度函数是由目标函数变换而成的，对目标函数值域的某种映射变换称为适应度的尺度变换（fitnessscaling）。几种常见的适应度函数直接转换若目标函数为最大化问题：Fit(f(x))=f(x)若目标函数为最小化问题：Fit(f(x))=-f(x)几种常见的适应度函数界限构造法1若目标函数为最大化问题：若目标函数为最小化问题：的最小估计值。为式中，其他)(,0)(,)())((minminminxfccxfcxfxfFit的最大估计值。为式中，其他)(,0)(),())((maxmaxmaxxfccxfxfcxfFit几种常见的适应度函数界限构造法2若目标函数为最大化问题：若目标函数为最小化问题：c为目标函数的保守估计值。0)(,0)(11))((xfccxfcxfFit0)(,0)(11))((xfccxfcxfFit适应度函数的作用适应度函数设计不当有可能出现欺骗问题：（1）进化初期，个别超常个体控制选择过程；（2）进化末期，个体差异太小导致陷入局部极值。适应度函数的设计单值、连续、非负、最大化合理、一致性计算量小通用性强适应度函数的线性变换法f’=α*f+β系数的确定满足以下条件：①f’avg=favg②f’max=cmultf’avgcmult=1.0~2.0适应度函数的幂函数变换法f’=fkk与所求优化相关0.10.20.30.40.50.60.70.80.900.10.20.30.40.50.60.70.80.91k适应度函数的指数变换法f’=e-afa决定了复制的强制性，其值越小，复制的强制性就越趋向于那些具有最大适应性的个体。1234567891000.10.20.30.40.50.60.70.80.91ff'α理论上还没有完全解决，影响算法的性能！种群数目交叉概率变异概率四、算法参数群体规模N染色体长度L影响算法的搜索能力和运行效率。若N设置较大，一次进化所覆盖的模式较多，可以保证群体的多样性，从而提高算法的搜索能力，但是由于群体中染色体的个数较多，势必增加算法的计算量，降低了算法的运行效率。若N设置较小，虽然降低了计算量，但是同时降低了每次进化中群体包含更多较好染色体的能力。N的设置一般为20~100。影响算法的计算量和交配变异操作的效果。L的设置跟优化问题密切相关，一般由问题定义的解的形式和选择的编码方法决定。对于二进制编码方法，染色体的长度L根据解的取值范围和规定精度要求选择大小。对于浮点数编码方法，染色体的长度L跟问题定义的解的维数D相同。除了染色体长度一定的编码方法，Goldberg等人还提出了一种变长度染色体遗传算法MessyGA，其染色体的长度并不是固定的。参数设计交配概率Pc变异概率Pm决定了进化过程种群参加交配的染色体平均数目。取值一般为0.4至0.99。也可采用自适应方法调整算法运行过程中的交配概率。增加群体进化的多样性，决定了进化过程中群体发生变异的基因平均个数。Pm的值不宜过大。因为变异对已找到的较优解具有一定的破坏作用，如果Pm的值太大，可能会导致算法目前处于的较好的搜索状态倒退回原来较差的情况。Pm的取值一般为0.001至0.1之间。也可采用自适应方法调整算法运行过程中的Pm值。参数设计复制交叉变异为了避免有效基因的损失用于组合新的个体，降低对有效模式的破坏增加种群的有效性五、遗传算子确定性采样排挤模型最佳个体保存模型适应值比例模型排序模型随机锦标赛模型无回放余数随机采样期望值模型选择算子交配算子单性孢子交配算子边重组交配算子循环交配算子顺序交配算子部分匹配交配算子多点交配算子算术交配算子均匀交配算子两点交配算子边集合交配算子变异算子非均匀变异算子高斯变异算子边界变异算子算子选择1、选择算子ffpii/设群体大小为，其中个体的适应度为，则被选择的概率为:niifipi遗传操作（1）适应度比例方法(fitnessproportionmodel)适应度比例方法是目前遗传算法中最基本也是最常用的选择方法。它也叫赌轮或蒙特卡罗（MonteCarlo）选择。在该方法中，各个个体的选择概率和其适应度值成比例。14.4%49.2%30.9%5.5%1234使用赌轮方法的选择30%43%21%6%指针转动方向（2）最佳个体保存方法（elitistmodel）该方法的思想是把群体中适应度最高的个体不进行配对交叉而直接复制到下一代中，此种选择操作又称复制。DeJong对此方法作了如下定义：设到时刻t（第t代）时，群体中a*(t)为最佳个体。又设A(t+1)为新一代群体，若A(t+1)中不存在a*(t)，则把a*(t)作为A(t+1)中的第n+1个个体。选择适应度计算：按比例的适应度函数（proportionalfitnessassignment）基于排序的适应度计算（Rank-basedfitnessassignment）选择算法：轮盘赌选择（roulettewheelselection）选择选择算法：随机遍历抽样（stochasticuniversalselection）局部选择（localselection）截断选择（truncationselection）锦标赛选择（tournamentselection）除了上述选择算子外，还有期望值方法(expectedvaluemodel)排序选择方法(rank-basedmodel)联赛选择方法(tournamentselectionmodel)排挤方法(crowdingmodel)等几个概念选择压力(selectionpressure):最佳个体选中的概率与平均个体选中概率的比值；偏差(bias)：个体正规化适应度与其期望再生概率的绝对差值；个体扩展(spread)：单个个体子代个数的范围；多样化损失(lossofdiversity)：在选择阶段未选中个体数目占种群的比例；几个概念选择强度(selectionintensity):将正规高斯分布应用于选择方法，期望平均适应度；选择方差(selectionvariance):将正规高斯分布应用于选择方法，期望种群适应度的方差。个体选择概率的常用分配方法按比例的适应度分配（proportionalfitnessassignment）某个体i，其适应度为fi，则其被选取的概率Pi为：MiiiiffP1个体ff2P12.56.250.1821.01.000.0333.09.000.2641.21.440.0452.14.410.1360.80.640.0272.56.250.1881.31.690.0590.90.810.02101.83.240.09个体选择概率的常用分配方法基于排序的适应度分配（rank-basedfitnessassignment）线性排序（byBaker）μ为种群大小，i为个体序号，ηmax代表选择压力。maxminmaxminmaxmax2,21],11)([1iPi个体选择概率的常用分配方法基于排序的适应度分配（rank-basedfitnessassignment）非线性排序（byMichalewicz）i为个体序号，c为排序第一的个体的选择概率。1)1(iiccP常用选择方法轮盘赌选择法（roulettewheelselection）个体1234567891011适应度2.01.81.61.41.21.00.80.60.40.20.1选择概率0.180.160.150.130.110.090.070.060.030.020.0累计概率0.180.340.490.620.730.820.890.950.981.001.00常用选择方法随机遍历抽样法（stochasticuniversalsampling）个体1234567891011适应度2.01.81.61.41.21.00.80.60.40.20.1选择概率0.180.160.150.130.110.090.070.060.030.020.0累计概率0.180.340.490.620.730.820.890.950.981.001.00设定n为需要选择的个体数目，等距离选择个体，选择指针的距离为1／n。第一个指针的位置由[0，l／n]区间的均匀随机数决定。如图所示，需要选择6个个体，指针间的距离为l／6＝o.167，第一个指针的随机位置为0.1，按这种选择方法被选中作为交配集个体为：1．2，3．4，6，8。常用选择方法局部选择法（localselection）(1)线形邻集在局部选择法中，每个个体处于一个约束环境中，称为局部邻域(而其他选择方法中视整个种群为