《分类移民策略遗传算法在优化中的性能研究》由会员分享，可在线阅读，更多相关《分类移民策略遗传算法在优化中的性能研究（7页珍藏版）》请在金锄头文库上搜索。
1、 - 1 - 分类移民策略遗传算法在优化中的性能研究分类移民策略遗传算法在优化中的性能研究1 陈启健，仲元昌，王军强 重庆大学通信工程学院，重庆 (400030) 摘摘 要要： 传统的移民策略在进行移民操作时完全依赖于随机操作， 由于随机个体分布极不均 匀，常常存在很大的盲目性，因而其效果不够理想。针对这一问题，本文按个体编码特性和 问题域对个体分类得到若干种族，而后按种族类别用等量移民替换劣势个体。结果表明，分 类的移民策略具有更强的空间搜索能力和更快的收敛速度。 关键词关键词：分类移民策略；种族；遗传算法；优化；干扰域；空间探索 1. 引言引言 移民策略遗传算法1-4 (Immigrant
2、 Strategy Genetic Algorithm， IGA)中是在新种群的形成 中，引入新的随机个体作为移民(Immigrant)，将一定比例最不适应的个体淘汰，从而引进 新的基因(Chromosome)， 然后再进行交叉等遗传操作。 移民策略改进了传统遗传算法的劣势 个体的淘汰方法。 引入的新基因全在新个体中。 故移民策略在引入了新的基因淘汰低适应值 个体的基因，防止了谬种遗传，有助于减少了低适应值基因的延缓收敛的作用，同时又能 避免了交叉所产生的优秀个体在遴选之前就被变异操作破坏掉， 从而使下一代只继承前一代 个体的全部优秀基因。 然而传统移民策略在进行移民操作时完全依赖于随机个体，
3、 随机个体 常常分布很不均匀， 新移民常常因过分集中而不能有效地覆盖问题域整个空间， 不利于盲区 突破，存在很大的盲目性。因而传统移民策略遗传算法效果有限。 鉴于以上问题，本文在移民策略的基础上按照个体特性将移民分成若干种族(race)，每 一个种族即是问题域的一个子域。 在各种族内产生等量的新的随机移民， 各种族以相同量的 移民淘汰一定量的劣势个体。这样，可以确保新引入移民包含了各种族同样数量的代表。也 就是新引入的移民能同时涵盖问题域的各子域。基于分类移民策略的遗传算法(Classified Immigrant Strategy Genetic Algorithm， CIGA)继承了传统移
4、民策略遗传算法的上述全部优点。 引入种族分类后的分类移民策略还具有以下新的优点： 一、 新分类移民在问题域中分布相对 更均匀，不至于因操作的随机性导致分布过于集中而产生盲区，因而更易于突破盲区，具有 更强的空间探索能力； 二、 优秀个体的保留操作能确保下一代完全继承前一代个体的全部优 秀基因；三、有控制地引入新基因，减少了操作的盲目性，可最大限度地均匀覆盖问题定义 域，有效地排除了个体过于集中在某一狭窄区域的畸形种群的产生，加快了收敛速度；四、 增加的运算量小，代价微乎其微。因而正如实验结果所示，基于分类移民策略的遗传算法不 但提高了收敛速度，还更有效地防止了陷入局部最优，具有更强大的盲区探索
5、能力。 2. 分类移民策略分类移民策略 基于移民策略的遗传算法由的择优、移民汰劣、交叉及变异等过程组成。引入移民的种 族分类后如图 1 所示，移民操作部分变成了种群的初始形成、劣势个体的选择、移民按种族 的形成、劣势个体的淘汰和最优个体的保留等步骤。 1本课题得到国家（973）计划（2002CB410803）和重庆市自然科学基金（CSTC，2006BB2242）的资助。 - 2 - 2.1 种族划分和编码种族划分和编码 种族划分： 这是分类移民策略的至关重要的一步。 结合可求解问题特征及其问题域把种 群个体划分为若干个种族（如图 2）。设问题域为区间,ba，将其分成K个连续子域作为 种族，得到
6、K个种族。则第k个种族为)(),( 1 ab K k aab K k a+ +。随机产生于这个 种族用于淘汰劣势个体的新个体则称为分类移民(Classified Immigrant)。 编码：第k种族内任一成员若用K元素向量, 21N pppL表示，其种族标志标识为 kpN= +1 ，则种群中任一成员的染色体表示为1+N位向量, 121+NN ppppL。则染色 体的值为 = + += N n Pnn ab K k ar 1 2)( 1 ) 1 ( 2.2 新种群的形成新种群的形成 在新种群的形成过程中，我们设置为优秀个体的初步遴选、新移民淘汰劣势个体、最优 个体的继承三大步骤。具体改进如下
7、为了确保优秀基因在随机选择过程中不会因随机性操作被误当劣势个体淘汰， 我们记录 图 1.基于移民策略的遗传算法的流程图 Fig.1 Flow chart of Classified Immigrant GA 分类移民策略 初始种群 N 计算适应度，择优 选择选择 MK+S 个劣势个体个劣势个体 M 族淘汰族淘汰 N*K 个劣势个体个劣势个体 两两随机交叉 变异(可选) 满足收敛否 计算适应度,选择、记录优秀个体 End 轮盘赌法形成子代轮盘赌法形成子代 N 个个体个个体 最优个体淘汰最优个体淘汰 S 个劣势个体个劣势个体 否 是 按种族形成新移民 - 3 - 下历史最优个体和新一代产生的前 1
8、3 个最优个体， 并在新种群形成中强制替代了部分适应 值最小的劣势个体。因而这是基于随机操作的部分地有指导、有计划的过程。 在对劣势个体用分类移民淘汰的改进是本文的重点，设每一代种群中有 N 个个体，保 留前 M 个优秀个体，淘汰余下的 N-M 个个体，其中除 S 个劣势个体用已记录下的最优个体 淘汰外，其余劣势个体用分属各种族的随机个体代替。 归纳起来，新种群的选择方法如下：首先，将问题域划分成 K 个种族，并记录本代适 应值最大的个体若干个(13)，加上历史最优个体，选出其中 S（如 2）个参与劣势个体的淘 汰；然后，运用轮盘赌法(Roulette Wheel Selection )初步选
9、出 N（与种群规模同样大小）个 优秀个体；再根据适应值大小将其中(N-M-S)个适应值最小的个体选出来，替代以随机产生 的分类移民； 最后将余下的 S 个体赋与前面记录下的最优个体， 以确保最为优秀的个体得以 保留继承。程序示意如下： Step K： 将问题域分成K个种族； StepK+1：记录S个最优个体； StepK+2：轮盘赌选择N个优秀个体; StepK+3：据个体pop(i)适应度大小定位M*K+S个适应值最小的劣势个体； StepK+4：将其中M*K个劣势个体赋与全新的随机值； StepK+5：将余下的S个劣势个体赋与最优个体值； 2.3 其它遗传操作其它遗传操作 交叉前，随机地任
10、选出个体两两组合，再进行交叉，以防止乱伦。由于新移民能给现有 个体带来新的基因，所以变异在此显得多余，故本例中取消了这一步骤，节省了不必要的计 图 2.种族划分示意图 Fig.2 Division of Numerical Problem Domain into Races a K ab a )( + )( 1 ab K k a + K abk a )( + K ab b b y x pk,1 pk,2 pk,N-M-s-1 pk,N-M-spk,N-M-s+1pk,N-S pk,N pk,N+1 图 3 新种群分类移民操作示意图 前 N-MK-S 个优秀个体保留 M*K 个劣势个体 换以全新
11、分类移民 S个最优个体 种族标志位 - 4 - 算开销。 2.4 分类移民策略性能分析分类移民策略性能分析 现有有限个个体仅能覆盖有限的问题域， 且分布极不均匀， 完全随机的遗传操作容易陷 入欺骗问题而早熟。例如在求解函数 )03. 0exp()1 . 0sin()07. 0exp()1 . 0sin()07. 0exp()1 . 0cos(5 . 1 1 xxxxxf+=最大值问题时，由其坐 标图（图 4）可见，所求解的最大值所在单调区间-目标域(target domain)-仅占左端极小 部分，称之为劣域(minor domain)，而干扰极值所在问题域-干扰域（deceptive dom
12、ain）则 占总体问题域的绝大部分，相应地称之为优域(major domain)。如果有限个个体等概率覆盖， 则陷入干扰域的概率极大。而变异概率应在 0.1%2%间为宜。这样的变异概率不容易突破 现有的有限问题域范围。 这就容易导致现有的个体在遗传操作时局限于现有有限个个体所覆 盖的问题子域，未能覆盖的子域则成为难以突破的盲区。 分类移民策略继承了传统移民策略遗传算法的全部优点。 例如： 引入了新的基因的同时 又能避免了交叉所产生的优秀个体在遴选之前就被变异操作破坏掉； 用新移民淘汰低适应值 个体的基因，有助于防止低适应值基因的延缓收敛速度等。 引入种族分类后，分类移民策略还具有以下新的优点：
13、一、新分类移民在问题域中分布 相对更均匀，不至于因操作的随机性导致分布过于集中而产生盲区，因而更易于突破盲区； 二、优秀个体的保留能确保下一代完全继承前一代个体的全部优秀基因；三、有控制地引入 新基因，减少了操作的盲目性，可最大限度地均匀覆盖问题定义域，有效地排除了个体过于 集中在某一狭窄区域的畸形种群的产生，加快了收敛速度；四、增加的运算量小，代价微乎 其微。因而正如实验结果所示，基于分类移民策略的遗传算法不但提高了收敛速度，还更有 效地防止了陷入局部最优，具有更强大的盲区探索能力。 优 域（干 扰 域） 劣域?目标域? 图 4 函数问题域分析 Fig.4 Analysis of a Pro
14、blem Domain - 5 - 3. 在优化中的仿真应用在优化中的仿真应用 问题提出：在一定问题域, bax范围内，运用遗传算法寻找某变量 0 x使得函数 )03. 0exp()1 . 0sin()07. 0exp()1 . 0sin()07. 0exp()1 . 0cos(5 . 1 1 xxxxxf+=在整个问题域内取得最大 值 max y(2.0323)。 根据遗传算法个体间的交叉性质， 极值两端的单调递增和递减函数部分自变量经遗传操 作后能且易于收敛于这个极值。在函数 1 f中，由其函数图（图 4）可见，函数有两个极大值 点。在函数问题域右部绝大部分是一个类似钟形幂函数，而最大值
15、max y (2.0323)位于问题 域左端。 我们对分类移民策略遗传算法(CIGA)和经典遗传算法(CGA)、移民策略遗传算法(IGA) 进行了性能比较。三种遗传算法在新种群的形成中均采用轮盘赌法(Roulette Wheel Selection)，其交叉概率为 50%，变异概率为 2%。其编码采用二进制编码。在此基础引入的 分类移民策略将问题域分成四个种族(如图 4中虚线间隔区域)：5,20、10, 5、25,10 和40,25。则第二种族任意个体, 121+NN ppppL的值可表示为： = += N n Pn r 1 25。 结果见图 5 和表 1。 由实验结果可见， 基于分类移民策略的遗传算法比传统遗传算法和移民 策略的遗传算法收敛速度更快， 进入有效域的时间更早， 遗传操作相同代数后陷入干扰空间 的比例更小，这说明其空间探索能力更强。 同时， 在问题域分为四个种族情况下我们还进行了在替换不同比例劣势个体情况下分类 移民策略的性能比较(如图 6)。实验还表明，在种群规模为 40，交叉概率为 50%的情况下， 在替换比由 10%增大到 70%过程中，收敛速度增长迅速，超过 50%后增长缓慢。因此，考 虑到运算复杂度，种族总量在 38 个、替换比例大约在 30%50%间性能代价比最高，引入 图 5 分类移民遗传算法(CIGA)与移民遗传算法 (IGA)、标准遗传算法
