小生境遗传算法综述.pdf-资料库

http://www.paper.edu.cn 小生境遗传算法综述1 李明林 (福州大学机械工程学院福建福州, 350002) （Email：lml_007@163.com）摘要：本文在阅读大量遗传算法小生境技术资料基础上，介绍了遗传算法的特点、物种形成和小生境技术，详细陈述上世纪 80 年代以来的各种小生境实现方法，包括共享函数法、确定性排挤法、可变半径的聚类算法和隔离小生境方法等；最后对小生境遗传算法的工程应用提出了展望。关键词: 小生境，遗传算法，聚类算法，隔离遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。大量的研究表明：简单遗传算法（SGA）在解决单峰值函数优化时是比较有效的，但面对工程中大量存在的多峰值复杂函数优化问题，SGA往往收敛于局部最优解。究其原因，主要是因为大多数选择策略采用繁殖机会同适应度成正比的方法，这很容易导致两个问题[3]： 1）超级数字串或超级个体问题；2）多个相似数字串问题，也称封闭竞争问题。实际上，导致以上两个问题的原因是简单遗传算法的选择策略缺乏多样性保护机制。而对多峰值函数优化问题，群体中个体的多样性可保证优化算法能够搜索出问题的所有最优解，包括局部最优解和全局最优解。为此，将小生境（niche）技术引入遗传算法。 1. 物种形成与小生境技术自然界中，“物以类聚，人以群分”是一种司空见惯的现象。生物总是倾向于与自己特性、形状相类似的生物生活在一起，一般总是与同类交配繁殖后代，这种交配方式在生物进化过程中具有积极作用。生物学上，有共同特性的组织被称为物种（species）。而物种赖以生存的资源环境，我们称之为小生境（niches）[4]。在自然界，小生境技术（niching）表现为：生态环境中分享不同资源的物种的形成。对应于象GA这样的人工系统，小生境技术表现为：在一个固定规模的群体中子群体的形成，每个子群体对应问题的一个子任务（在多峰值优化问题中，每个子任务对应于找出一个山峰）。小生境技术具有相对简单、有效和通用的特性，因此，它可作为 SGA 强有力的组成部分。它可促使群体内个体间协同合作，使算法易于找出优化问题的所有局部最优解和全局最 1 本课题得到福建省教育厅（JB04025）资助 - 1 -

http://www.paper.edu.cn 优解。而 SGA 中，个体间仅仅存在竞争，最好的个体在进化中迅速占据整个群体，即一个物种占据环境的全部资源，或者说算法仅能找出其中的一个最优解（全局最优解或局部最优解）。 2. 小生境技术的研究进展小生境技术最早是由Cavicchio[5]在 1970 年提出的基于预选择机制（Preselection）的小生境实现方法。1975 年DeJong一般化了Cavicchio的预选择机制[6]，在其博士论文提出了基于排挤机制（Crowding）的小生境实现方法[7]。他们声称这两种方法都可在群体中形成小生境的进化环境，并维持了群体的多样性。但在相当长的时间里，对Preselcetion和Crowding 的研究少之又少。直到 1992 年Mahfoud才又进行比较深入的研究，指出在实际应用中，这两种方法并不象其作者所声称的那样能成功地维持多样性。真实情况是这两种方法所采用的随机替代技术将产生大量的基因漂移，而使算法收敛于局部最优解。通过对Crowding方法的修改，Mahfoud提出了一种基于所谓确定性排挤机制（deterministic crowding，简称DC）的小生境实现方法。该方法据说可从根本上消除基因漂移[8，9]。DC的基本思想是：将父代群体随机两两配对，若N为群体规模，则配对后将生成N/2 对父代个体。每对父代个体进行交叉、 1、随机选择两个父代个体P1、P2 ； 2、对P1、P2进行交叉、变异生成子代个体C1、C２； 3、计算P1与C1、P2与C2、P1与C2、P2与C1的距离d1、d2、 d3、d4 ； 4、如果 d1+d2 不大于 d3+d4 ，那么：如果C1的适应度大于P1的适应度，用C1代替P1；如果C2的适应度大于P2的适应度，用C2代替P2；否则：如果C2的适应度大于P1的适应度，用C2代替P1；变异或其他遗传操作，生成两个子代个体。两如果C1的适应度大于P2的适应度，用C1代替P2；子代个体分别与其中一个相似的父代个体进行竞争，适应度高的代替适应度低的进入下一代循环。DC的伪代码如图 1 所示。图 1 DC 的实现步骤 Fig 1 the pseudocode of deterministic crowding DC具有算法简单、收敛速度快和隐含并行性等优点，被用于解决列车轨道混凝土的生产工艺问题，取得了较好的结果[14]。小生境技术中最著名及用得最多的可能是 1987 年Goldberg & Richardson提出的基于共享机制（Fitness Sharing）的小生境实现方法（简称FSGA）[10]。该方法的基本思想是：通过反映个体之间相似程度的共享函数来调整群体中各个个体的适应度，以维护群体的多样性，从而在这以后的群体进化过程中，算法能够依据这个调整后的新适应度来进行选择运算。其中：个体i、j的相似程度可以是基因型的海明距离或表现型的欧氏距离，以dij表示；经调整后个体的适应度为其原适应度值除以小生境数mi，mi为个体i与群体内其他个体之间的共享函数 sh(dij)之和，mi和sh(dij)的表达式如下： - 2 -

http://www.paper.edu.cn m i = n ∑ j 1 = ( dsh ij ) （1） ( dsh ij ) = ⎧ ⎪ 1 ⎨ ⎪ ⎩ − ⎛ ⎜⎜ ⎝ d ij σ sh 0 α ⎞ ⎟⎟ ⎠ if d ij otherwise < σ sh （2） σ sh = k k m 2 ∗ （3）式中：n为群体规模；α为共享程度；бsh为小生境半径，其表达式由Deb和Goldberg[11、12]于 1989 年给出；k为优化问题的维度；m为优化问题最优解的个数。但该方法需要事先知道多峰值函数最优解的个数，并且其复杂度达到O(n2)——n为群体规模。1991 年Oei介绍了几种降低算法复杂度的方法，主要是以在群体中选取几个个体作为样本代替计算所有个体间的相似度，但每个小生境都要限定个体的最大数量[15]。另一个值得关注的小生境实现方法是 1993 年Beasley等提出的Sequential Niching[16]。该方法认为FSGA在求解多峰值函数时，父代群体与子代群体中适应度分布曲线变化不大，只能求得其中最大的一个峰值。因此Beasley提出反复运行 FSGA来搜索所有峰值。其基本思想是：运行 FSGA，找出一个峰值，后将该山峰削平，使得再次运行FSGA时得以搜索其他峰值，如此反复，直到找到所有的峰值。其实现步骤如图 2 所示。 1、计算群体的初始适应度； 2、运行 FSGA 或其他算法，记录最佳个体 S； 3、以 G(S)修正群体的适应度，目的是抑制 S 所在区域的个体参与下一次进化； 4、如果最佳个体超出某一设定的临界值，则该个体作为问题的一个峰值输出； 5、如果所有的峰值都输出，则停止；否则，转步 2；图 2 Sequential Niching 的实现步骤 Fig 2 The pseudocode of Sequential Niching 削平山峰的方法是以上一次 FSGA 所得的最佳个体的函数修改下一次运行 FSGA 时的个体适应度。该函数为一单调递减函数，Beasley 测试了以下两种函数形式： ( SxG , ) = α ⎞ ⎟ ⎠ r ⎧ ⎛ ⎪ ⎜ ⎨ ⎝ ⎪⎩ d xS 1 d xS < r 其他（4） ( SxG , ) = ⎧ ⎛ exp ⎪ ⎜ ⎝ ⎨ 1 ⎪⎩ log ( drm − ) xS ⎞ ⎟ ⎠ r d xS < r 其他（5）上式中：x为群体的某个个体；S为上一次FSGA所得最佳个体；dxS为个体x与S间的距离；r 为小生境半径，其值与式（3）的σsh相同；α、m均为能量因子。第一次运行FSGA时，个体 - 3 -

http://www.paper.edu.cn 适应度为原始适应度；第i次运行FSGA时，个休的适应度由下式确定： ( ) xF i 1 + = ( ) SxGxF , i ( )1 − i （6）同年Yin & Germay[17]将MacQueen’s KMEAN聚类算法引入FSGA。该方法的基本思想是：先将群体分成k组，对应于k个小生境；个体的共享适应度由其原适应度除以小生境数mi，mi 由下式给出： nm = i − n c c d 2d ⎛ ⎜⎜ ⎝ ic max α ⎞ ⎟⎟ ⎠ i Cx ∈ （7） x 其中：dic为个体i与第c组中心的距离；nc为第c组中个体的数量；α的取值同上。另有参数dmax 和dmin分别代表组与组间的最大距离和最小距离。当有两个组的中心距离小于dmin时，这两组将合为一组；当有个体与所有组的距离超过dmax时，将在该个体形成新组。以此实现小生境进化环境。上述几种小生境实现方法都需要计算群体中个体间的距离dij，也就是说群体内所有个体平均分享境内有限的资源，这在群体规模比较大时将影响算法的效率。由此， Pétrowski[13] 于 1996 年提出将群体内有限资源只提供给境内最优个体的基于Clearing机制的小生境实现 void Clearing(double Sigma, int Kappa) { int i , j , nbWinners; SortFitness (P); for (i=0 ; i 0) { nbWinners = 1; for (j = i+1 ; j< n-1 ; j++) { if (Fitness(P[j])>0 && Distance (P[I], P[j])

http://www.paper.edu.cn 技术，使得搜索朝着最优解所在的区域逐步收敛（详细情况请参考文献[19]）。 1999 年Gan和Warwick提出一种类似于GAS的小生境动态聚集方法（Dynamic Niche Clustering，简称DNC）[15、20]。该方法定义一个小生境序列向量Nichset，代表群体中小生境数随着群体的进化而变化。每个小生境i有两个参数：midi和σshi；分别代表小生境的中心点位置和小生境的半径。当群体中的个体与midi的距离小于σshi时，则该个体为小生境i的成员。与GAS不同，DNC中每个个体可以同时分属两个不同的小生境。为防止小生境的无限制增长，将σshi限定在[σmax，σmin]范围内。σshi的初值由群体规模Pop和问题的维度d通过下式确定： σ sh initial = d Pop 3 ∗ d （8）小生境半径的边值σmax=2*σsh、σmax=σsh/4。在初始化群体时，每个个体以自身为中心，以式（8）为半径形成一个小生境。之后进行如下各项操作： 1）、确定当前每个小生境内个体的数量。当个体与所有小生境的距离超出各小生境的半径时，以该个体为中心，以式（8）为半径生成个新小生境。 2 ）、重新计算各小生境的中心位置。计算方法有多种，这里只介绍所谓 Fitness Distribution from Midpoint 方法。小生境 i 的新中心位置由下式确定： mid i = mid i + ∑ n i j 1 = j ( x ∑ − n i j 1 = ) f i j mid f j （9）式中：ni为该小生境内个体数；xi代表个体i；fi为i个体的适应度。 3）、重新计算小生境内的个体。如果某个小生境内无个体存在，则将该小生境从序列中删除。 4）、计算小生境序列中任意两个小生境的距离，并按小生境序列的顺序排列。 5）、如果小生境i与小生境j的距离小于σmin，则将这两小生境合并且取代小生境i。此时要重新计算小生境i的中心位置，并将小生境j从小生境序列中删除。 6）、重新计算各小生境内个体的数量。最后通过共享函数修改所有个体的适应度。个体 i的共享函数中小生境数mi由下式确定： nm = i − n j j α d ⎞ ⎟ ij σ ⎟ 2 ⎠ shj ⎛ ⎜ ⎜ ⎝ （10）式中：nj为小生境j的个体数；dij为个体i与小生境j的距离；σshj为小生境j的半径；α这里取为 1.0 的常数。国内小生境遗传算法的研究主要有 1998 年林焰[3]等提出的基于隔离（Isolation）机制的小生境实现方法。其基本思想是将初始群体分为几个子群体，子群体的规模正比于其平均适应值，但子群体拥有的个数必须满足最大允许规模和最小保护规模的限制，之后在子群体间 - 5 -

http://www.paper.edu.cn 及其内部执行“优胜劣汰，适者生存”，来实现种群的进化。该方法算法简单，且高度模仿生物学中物种的地域隔离进化，隔离机制对于保持种群的多样性和引导种群进化方面具有重要作用，有较高的理论探讨价值和良好的应用前景。但该方法子群体数的选取同样需要事先知道问题最优解的个数。 3. 小生境遗传算法的应用展望小生境遗传算法是在遗传算法的原有结构上引入小生境技术，不但不影响遗传算法的原有特点，而且既维持了群体的多样性，又提高了遗传算法处理多峰值优化问题的能力。因此可以肯定，小生境技术将大大拓宽遗传算法的工程应用范围，特别适用于对所有或大部分局部最优解感兴趣的工程问题。除了文献[1][2]提到的遗传算法的应用领域，文献[21][22]综合概述了遗传算法在机械工程中的应用。参考文献 [1] 专著：周明，孙树栋．遗传算法原理及应用[ M ] ．北京：国防科技出版社，1999． [2] 译著：玄光南[日]，陈润伟著．遗传算法与工程设计［Ｍ］．汪定伟等译．北京：科学出版社，2000． [3] 连续出版物：林焰，郝聚民，纪卓尚，戴寅生．隔离小生境遗传算法研究［Ｊ］．系统工程学报，2000， 15（1）：86~91． [4] 学位论文：Horn, J. The Nature Of Niching: Genetic Algorithms And The Evolution Of Optimal, Cooperative Populations［Ｄ］. Department of Computer Science，University of Illinois at Urbana-Champaign，1997． [5] 学位论文：Cavicchio D J. Adaptive Search Using Simulated Evolution［Ｄ］. University of Michigan, Ann, Arbor， 1970． [6] 专著：陈国良等．遗传算法及其应用［Ｍ］．北京：人民邮电出版社，1996． [7] 学位论文：De Jong, K.A.(1975). An analysis of the behavior of a class of genetic adaptive systems[D]. University of Michigan. Dissertation Abstracts International, 36(10), 5140B. (University Microfilms No.76-9381). [8] Samir W. Mahfoud, Crowding and Preselection Revisited. In Parallel Problem Solving from Nature, 2, North-Holland, pp.27~36, 1992. [9] 学位论文：Samir W. Mahfoud, Niching Methods for Genetic Algorithms. (Doctoral dissertation, University of Illinois at Urbana-Champaign), 1995. [10] 论文集：Goldberg, D.E., & Richardson, J.J. (1987). Genetic algorithms with sharing for multimodal function optimization. Genetic algorithms and their application: Proceedings of the Second International Conference on Genetic Algorithms, 41-49. [11] 学位论文：K. Deb (1989). Genetic Algorithms in Multimodal Function Optimization. (Masters thesis, Dept. Engineering Mathematics, Univ. Alabama). TCGA Report No89002. [12] 论文集：K. Deb & D. Goldberg (1989). An Investigation of Niche and Species Formation in Genetic Optimization. In 3rd International Conference on Genetic Algorithms, 42~50. [13] 论文集：Pétrowski A.(1996). Clearing Procedure As A Niching Method For Genetic Algorithms. In Proc. 1996 IEEE Int. Conf. Evolutionary Computation, Nagoya, Japan(798~805). [14] 技术报告：Pérez-Vázquez, M. E. & Gento-Municio, A.M. & Lourenço, H.R. Solving a Concrete Sleepers - 6 -

http://www.paper.edu.cn Production Scheduling by Genetic Algorithms. (UPF Working Paper Series 2004). [15] 论文集：J. Gan & K. Warwick (2000). A Variable Radius Niching Technique for Speciation in Genetic Algorithms. Proceeding of the Genetic and Evolutionary Computation Conference (GECCO 2000), 96~103. [16] 连续出版物：D. Beasley, D.R. Bull & R.R. Martin (1993). A Sequential Niche Technique for Multimodal Function Optimization [J]. Evolutionary Computation 1(2): 101~125. [17] 论文集：X. Yin & N. Germay (1993). A Fast Genetic Algorithm with Sharing Scheme using Cluster Analysis Methods in Multimodal Function Optimization. In International Conference on Artificial Neural Networks and Genetic Algorithms, 450~457. [18] 连续出版物：S. Tustsui, Y. Fujimoto & A. Ghosh (1997), Forking GAs: GAs with Search Space Division Schemes [J]. In Evolutionary Computation, Vol.5, No.1, 61~80, MIT Press. [19] 连续出版物：M. Jelasity & J. Dombi (1998), GAS, a Concept on Modeling Species in Genetic Algorithms [J]. In Artificial Intelligence, 99(1), 1~19. [20] 论文集：J. Gan & K. Warwick (1999). A Genetic Algorithm with Dynamic Niche Clustering for Multimodal Function Optimisation. In 4th International Conference on Artificial Neural Networks and Genetic Algorithms, 248~255. [21] 连续出版物：杨璐，陈长征，孟杨．遗传算法工程应用进展[J]．沈阳工业大学学报，2002，24（3）： 240~243． [22] 连续出版物：黄洪钟，赵正佳，姚新胜，冯春．遗传算法原理、实现及其在机械工程中的应用研究与展望[J]．机械设计，2000 年 3 月，No.3 ：1~6． Overview of the Niching Genetic Algorithms (College of Mechanical Engineering, Fuzhou University, Fuzhou, Fujian 350002 , China) Li MingLin Abstract: The paper introduces the fundamental principle and characteristic of genetic algorithms. Then the idea of speciation and niche are described, with various niching methods including deterministic crowding, fitness sharing, clearing, sequential niching, variable radius niching technique, and isolation niching. Finally, a prospect is conducted on the niching genetic algorithms’ further application in engineering. Key words: niching methods, genetic algorithms, sharing, crowding, clustering, isolation 作者简介：李明林，男，1977 年生，讲师，研究方向为：机械手控制技术、遗传算法等 - 7 -

资料库

小生境遗传算法综述.pdf

相关推荐

开发技术

热门标签

最新资料