（计算机应用技术专业论文）基于遗传算法的汉语基本词汇自动提取研究.pdf

中文摘要 基本词汇是词汇的核心，也是各项语言研究的基础。自从基本词汇这一 概念被提出，国内学者掀起了一股研究基本词汇的热潮。经过半个世纪的 研究，已经取得了相当大的成绩，提出汉语基本词汇的多种鉴定方法，为 我们综合考虑基本词汇的三大特征提供可借鉴的方法。 遗传算法是生命科学与工程科学的相互交叉、相互渗透和相互作用而 成的新的计算方法。它不仅具有自组织、自适应、和自学习性的智能特性， 而且还具有内在的本质并行特性。算法通过适应度来评估个体的优劣。经 过三十多年的研究、应用，遗传算法已成为非线性优化和系统辨识的一个 有效工具。被广泛的应用于函数优化、组合优化、生产调度、自动控制、 机器学习、图象处理、人工生命、机器学习等领域。在自然语言处理方面， 遗传算法也受到重视，应用于信息提取、文本分类、文本聚类、数据挖掘、 自动生成知识库，手写体字符识别等并取得了很好的效果。实践证明，遗 传算法作为现代最优化的手段，它应用于大规模、复杂空间领域离散值情 况下的全局最优化问题是合适的。在求解速度和质量上远超过常规方法， 是一高速近似算法。 汉语基本词汇提取是自学习的过程。首先，利用遗传算法分析语言学 家列举的基本词汇的三大特征，从中学习并总结出这些词语遵循的规律。 然后，根据获得的规律在“工程现代汉语通用词”词表的基础上进行计 算。文中详细的叙述了遗传算法的操作过程。 关键词：遗传算法，汉语基本词汇，自动提取 a b s t r a c t t h eb a s i cw o r di st h ei m p o r t a n tp a r to ft h ev o c a b u l a r ya n dm a n yl a n g u a g e r e s e a r c h e s s i n c et h ec o n c e p to fb a s i cv o c a b u l a r yw a sp r o p o s e d , t h ed o m e s t i c s c h o l a r sh a v er a i s e das t u d yu p s u r g eo f t h eb a s i cv o c a b u l a r y a f t e rh a l f c e n t u r y , r e s e a r c hh a sm a d ec o n s i d e r a b l ea c h i e v e m e n t s v a r i o u si d e n t i f i c a t i o nm e t h o d s o ft h ec h i n e s eb a s i cv o c a b u l a r yw e r ep r o p o s e d t h a tp r o v i d e dt h er e f e r e n c e w h i c hw ec o n s i d e r e dt h r e ec h a r a c t e r i s t i c so ft h eb a s i cv o c a b u l a r y g ai st h en e wc o m p u t a t i o n a lm e t h o dw h i c ht h el i f es c i e n c ea n dt h e e n g i n e e r i n gm u t u a l l yj o i n t l yf o r m i ti sn o to n l ys e l f - o r g a n i z i n g ，a d a p t i v e ，a n d t h ei n t e l l i g e n ts e l f - l e a r n i n gc h a r a c t e r i s t i c s ，b u ta l s ot h ei n h e r e n tn a t u r eo f p a r a l l e lc h a r a c t e r i s t i c s t h ea l g o r i t h me v a l u a t e st h ef i ta n du n f i tq u a l i t yo f t h e i n d i v i d u a lb yf i t n e s s g ah a sb e c o m ea ne f f e c t i v et o o lw h i c ht h en o n l i n e a r o p t i m i z a t i o na n dt h es y s t e mr e c o g n i t i o nb ym o r et h a n3 0y e a r sr e s e a r c ha n d t h ea p p l i c a t i o n i th a sb e e nw i d e l yu s e di nt h ea p p l i c a t i o n ，i n c l u d i n gf u n c t i o n o p d r n i z a t i o n ，c o m b i n a t o r i a lo p t i m i z a t i o n ，p r o d u c t i o ns c h e d u l i n ga n da u t o m a t i c c o n t r o l ，m a c h i n el e a r n i n g ，i m a g ep r o c e s s i n g ，a r t i f i c i a ll i f e ，m a c h i n el e a r n i n g a n do t h e rf i e l d s i nt h en a t u r a ll a n g u a g ep r o c e s s i n ga s p e c t ，g aa l s or e c e i v e d t a k e st o a p p l i c a t i o ni ni n f o r m a t i o n e x t r a c t i o n , t h et e x tc l a s s i f i c a t i o na n d c l u s t e r i n g ，t h ed a t am i n i n g , k n o w l e d g el i b r a r ya u t o m a t i cp r o d u c t i o n ，t h e h a n d w r i t t e nc h a r a c t e rr e c o g n i t i o na n ds o0 1 1a n di th a so b t a i n e dt h ev e r yg o o d e f f e c t t h ep r a c t i c ep r o v e dt h a tg ai sa no p t i m i z e dm e t h o do ft h em o d e m 。i ti s a p p r o p r i a t et o b eu s e di nl a r g e s c a l ea n dc o m p l e xd i s c r e t e s p a c eg l o b a l o p t i m i z a t i o n i ti sb e t t e rt h a nt h ec o n v e n t i o n a lm e t h o di nt h es o l u t i o ns p e e d a n dt h eq u a l i t y , i sah i g l ls p e e da p p r o x i m a t em e t h o d a u t o m a t i ce x t r a c t i o no fc h i n e s eb a s i cv o c a b u l a r yi st h el e a r n i n gp r o c e s s f i r s t ，g aa n a l y z e st h r e ec h a r a c t e r i s t i c so ft h eb a s i cv o c a b u l a r ye n u m e r a t e db y l i n g u i s t sl i s t e d , a n ds t u d i e sa n ds u m m a r i z e st h er u l eo ft h e s ew o r d s t h e n ，g a c o m p u t ei nw o r dt a b l eo f e n g i n e e r i n gd e f i n i t i o no fc o n t e m p o r a r yc h i n e s e c o m m o n - u s i n gw o r d s ”b a s eo nt h a tr u l e t h ep a p e rd e s c r i b e st h eo p e r a t i o n so f t h eg e n e t i ca l g o r i t h mi nd e t a i l k e y w o r d s ：g e n e t i ca l g o r i t h m s ，c h i n e s eb a s i cv o c a b u l a r y ，a u t o m a t i c e x t r a c t i o n 内敛古师范人学颅i 学位论史 1 1 引言 第一章绪论 基本词汇是指一个民族的群众在日常生活的语言交流中要经常使用的、不可 缺少的那部分词汇。基本词汇是一种语言的词汇系统中的核心部分 1 9 5 0 年，斯大林在论语言学中的马克思主义一文中，系统地对基本词 汇进行了论述，文章指出：“语言的词汇中的主要东西就是基本词汇，其中就包括 成为它的基础的全部根词。基本词汇比语言的词汇少得多，可是它的生命却长久 得多它在千百年的长时期中生存着，并且为构成新词提供基础。”“1 斯大林文章的发表对基本词汇的研究产生了重大影响，在上世纪五、六十年 代掀起了一股研究基本词汇的热潮，对基本词汇概念的界定，也是众说纷纭。但 是对基本词汇所具有的“全民常用性、历史稳固性和构词能力强( 或者说能产 性) ”三大特点，语言学界已达成基本共识。 关于基本词汇的最本质特点，至今仍有争论：如，在语言学引论( 1 9 5 8 ) 一书中对基本词汇的特性有这样的描述“一般来说，全民性这个特征是一切基本 词汇的词所共有的”啪。而与之相对应，还有观点认为基本词汇的最本质特点 是构词能力，“这是基本词汇最主要的属性”“1 ，。词的有无构词能力是判断一 个词是否基本的先决条件”o 】。这样就使得一些构句的基本元素，在日常生活 中十分常用，但缺乏构词能力的虚词被排除在了基本词汇之外，这从理论和实际 应用角度都是无法被接受的。 对于基本词汇的稳固性特征也是如此。有些词，几千年来变化不大；有些词， 是过去某个时期的基本词，另外一些词，虽然可能只有上百年的历史甚至更短， 但“它们仍然是现代汉语的基本词汇”“。 鉴于上述的争论。我们研究具有一定限制条件的基本词汇。 1 2 现代汉语工程基本词的定义 本文提取具有一定限制条件的基本词汇，即。现代汉语工程基本词”。其 摹十遗传算法的汉语摧奉词汇的自动提取研究 定义如下： 现代汉语工程基本词( e n g i n e e r i n gd e f i n i t i o no fc o n t e m p o r a r yc h i n e s e b a s i cv o c a b u l a r y ，简称e c b v ) 是现代汉语动态流通语料库词汇系统的核心稳 定部分，是当今汉民族人民在日常交流中普遍使用的、不容易变化，时间上使用 稳定的词汇，它的词语具有较强的构词能力，是汉语言中派生新词的基础。 “现代汉语工程基本词”e c b v 具有如下特征： ( 1 ) 全民常用性； ( 2 ) 时间的使用稳定性： ( 3 ) 构词能力强： 1 3 论文研究的意义 基本词汇是语言的意义基础，是不断变动的词汇系统中相对稳定的部分，是 生成新词语的核心词汇。在中小学语文教学中，抓住了基本词汇，就等于抓住了 词语教学的灵魂。同时，基本词汇集的研制，可以为教学词汇等级大纲的制定， 提供科学的参考依据。 基本词汇包含那些反映人类对世界最主要、最基本、最具体认识的词，而这 些词反映的概念往往是在不同语言中共同存在的，所以基本词汇是第二语言教学 的基础。 研究汉语的基本词汇，还能够推动汉语的本体研究，以词典编纂为例：基本 词汇作为汉语词语的基础，是词典编纂的释义原语。“在释义描述时，希望能以 最基本的概念与浅显易懂的词条将概念明确的表达。也就是说用来描述的词条是 所谓的基本词，且具典型义的以达到典型的写法“。我们知道，朗文词典就是 以2 0 0 0 个常用词汇对所有词条进行释义，简明易懂，这也是其能够成为在世界 范围内英语学习者中广泛流行的重要原因之一 在信息化社会，人机结合实现自然语言理解与处理是我们新世纪信息化发展 的主要目标。在机器翻译、语音识别与合成、文本分类、信息检索、信息过滤等 自然语言处理领域不单需要强有力的技术支持。而且还需要扎实雄厚的语言学基 础研究。例如，基本词汇所具有的全民常用性特征，使得它们具有不同专业领域 所共用的词汇特性所以在进行文本分类时，应该首先排除不具备领域特征的停 2 内蒙古师范人学碗l j 学位论文 用词表。 汉语基本词汇到底包含多少词汇，目前，我们还没有看到一个比较完整的汉 语基本词汇表。我们所看到的汉语基本词汇是在教材中或论文中，作者为说明某 一问题列举的。如果我们能够提供一个汉语基本词汇的提取模型，并实现汉语基 本词汇的自动提取。不仅对其自身的研究有重要的参考价值，并且对其应用也有 重要意义。 1 4 文章的组织结构 文章的组织结构如下： 第一章介绍基本词汇概念的由来，引出现代汉语工程基本词以及汉语基本 词研究的现实意义和文章的组织结构。 第二章介绍现有的汉语基本词汇的研究方法。如，训释频率鉴定法、构词 能力鉴定法、词频统计法等。为本文研究提供参考。 第三章简单的介绍基本词汇的提取过程，即通过机器学习获得现有基本词 汇的规律，在通用词汇集的基础上提取词汇。通用词汇和机器学习的概述。 第四章概述遗传算法的基本术语，遗传算法的操作流程，遗传算法的基础 理论，遗传算法的特点，研究历史和现状。 第五章描述基本词汇提取的过程，设计和实现了一个基于遗传算法的基本 词汇提取实验系统，并对实验结果做出了分析和讨论。 第六章总结本文的工作，并对将来的研究作了展望。 雄十遗传算法的汉语崔奉诃 l 的自动提取研兜 第二章基本词汇研究方法的综述 基本词汇的三大特点虽然被语言学家用来当作鉴定基本词汇的标准。但是由 于界限模糊，因此有的学者为了较为有效地鉴定基本词汇，从理论上提出了一些 具体的可操作的鉴别办法。如，语言学家的经验法贝i l 旧，苏新春先生在如何划 分汉语的基本词汇文中介绍的：“字根分析法、训释频率鉴定法、构词能力 鉴定法、词频统计法”等几种方法。1 ，以及张化瑞提出的“分布差异对比法则” 叫等。 2 1 语言学家的经验法则 该法则建立在主观的概念立论上，没有科学上可验证的客观定义。如，斯瓦 迪士( s w a d e s h ) 提出的基本词汇表，是利用语言学家的经验与基本概念结构的 论证而得出的，但是已经得到比较语言学研究的验证，在使用上己成为学术界的 预设标准，且应用于各种不同的语言。也就是经验法则通过了跨语言可行性的基 本检验。嘲 2 2 字根分析法 “说文解字的5 4 0 个部首字都是独立的字，有自己的形音义。不仅显示 了汉字字形的字根，而且显示了汉字所表示的意义系统中的原始义类。”，“代表 了人们对客观世界的最原始认识”，它们是繁体汉字构字的基础。1 。因为汉语词 衍生自汉字，所醢解读说文解字的5 4 0 个部首，可以了解汉语词中最稳固的 部分。也是最根本的基本词汇。 2 3 训释频率鉴定法 古人在对艰涩难懂的前代语言进行诠释时，总是选择通俗易懂、明白浅显的 训释词。因此最适合担任训释词的莫过于基本词了。充当训释词频率越高的词， 它显示基本词的价值就越大。 “用词的训释频率找出的基本词，使用频率高，流行面广，词义明白浅显。”“1 4 内蒙古师范人学磺i ：学位论文 2 4 构词能力鉴定法 考察词构成其它复合词及语的构词能力“构词能力强的词素往往是那些生 命力长久、曾经独立使用过、所表示的意义原始、稳定的基本词”嗍 2 5 词汇库交集法 。基于斯瓦迪士( s w a d e s h ) 基本词汇表对基本词汇的认识，在不同必要词汇 的定义下，所有词汇库所共有的交集就是基本的词汇。” 这种方法不受限于语言或时代，但基本上还是经验法则的延伸，且它依赖于 专家事先准备好的词汇库资料，无法直接由语料产生 2 6 词汇统计鉴定法 计算语言学主要包括两种方法：一种是人工智能方法。即采用演绎逻辑的方 式把规则形式化，然后处理自然语言，让计算机具有和人相同的广泛的知识和逻 辑推理能力；另一种方法是把庞大的语料库放到计算机里，使用定量分析方法， 对自然语言现象进行概率性的预测。这就是语科库方法或概率的方法“。下面介 绍语料库方法的几种使用： 2 6 1 词频 词语频次( f r e q u e n c e ) 也叫词语频数，是指在一段时间范围内，某一词语在 媒体中的使用频次。它经常被用来衡量词语的常用性特征。 词频大体从必要性的角度体现了词的常用程度，但并不具备充分性，某些情 形下，会产生偏差n 1 1 2 6 2 词流通度 流通度( c i r c u l a t i o n ) 要考察语言在社会交际中的真实使用情况。决定语 言的流通度的主要因素是语料库的选材选材不仅要考虑到静态的分布、散布， 还要考虑这以外的动态因素，即要考察所选文本的发行量、发行周期、发行地区、 崔十遗传算法的汉语幕奉词汇的自动提取研究 阅读率等等。这些与社会语言学有关的因素都决定着文本是否真实流通，我们认 为所谓“真实文本”的最重要核心的问题是文本的“真实流通”。“2 1 目前北京语言大学动态流通语料库主要在进行报纸媒体的语料加工，流通度 系数以c t 代表。主要考虑了发行量、发行周期、发行地区、阅读率等因素。流 通度计算公式是： 媒体的发行量：流通量( t h ev o l u m eo fc i r c u l a t i o n ) 以v c 代表 媒体的发行周期：流通密度( t h ed e n s i t yo fc i r c u l a t i o n ) 以d c 代表 媒体的发行地区：流通空间( t h ea r e ao fc i r c u l a t i o n ) 以a c 代表 媒体的阅读率：流通率( t h ef r e q u e n c yo fc i r c u l a t i o n ) 以f c 代表 计算公式：c t = y c d c a c f c 即：流通度系数= 流通量系数流通密度系数流通空间系数流通率 流通度= 使用度流通度系数 所以流通度是更为客观的词汇使用情况的度量指标。 2 6 j 词汇通用度 词汇通用度( l e x i c a lu s u a l i t y ) 是由北京大学计算语言所在2 0 0 3 年中发 展提出( y u2 0 0 3 ) 。“单一词汇的分布均匀度称之为该词汇通用度，并简称为通 用度”嘲。 分布均匀度( ( d i s t r i b u t i o n a lc o n s i s t e n c y ，英文简称d c ) 是和频率 ( f r e q u e n c e ) 相对的概念。直觉来说，频率求的是在某个范围内数量最多的元 素，而分布均匀度求的是在某个范围内最稳定的元素。这样的叙述，可以帮助我 们更好的理解分布均匀度的意义。 分布均匀度的定义公式如下：( z h a n ge ta 1 2 0 0 4 ) 分布均匀度d e = s m r m e a n s m r 及m e a n 分别定义如下 s m r ：( 窆厄 m e a n = ( f , n ) j l 6 内蒙古师范大学颂卜学位论文 上式中，表示将语料库划分为1 3 等分( 比如，词数相等) f i 是词语在第i 等分出现的次数 分布均匀度用的是均根方( s m r ：s q u a r ei h e a nr o o t ) ，得出的值是语料库等 分切分后，语料均匀分散的程度。其取值范围，可以证明为( o ，1 ) ( 未出现词 不在考虑范围之内) 。分布越均匀，则越接近于1 。 分布均匀度可能的取值说明如下：在整个语料库被分成n 等分的前提下， 若一个词只在其中某一个等分中出现，则其通用度为1 n 。 若一个词在每一个等分中都以相同频次( 非零) 出现，则其通用度为1 。 若一个词在m 个等分( 1 m = n ) 中以不同频次( 非零) 出现，其通用度为m n ”1 我们可以考察词语在一年中十二个月、或若干年的分布均匀度，所以分布均 匀度可以被用来考察词语的稳固性特征。 以上几种方法显然比基本词汇三大特征的定性描述有了更实际操作性。但也 存在一些问题，其中字根分析法和训释频率鉴定法都是以古汉语单字词为对象 的，基本词汇集被完全静态化，所以对于现代汉语基本词汇集的圈定有着很大的 偏差。我们将采用训释频率法，对现代汉语词典中的解释词语进行统计，作 为分析基本词汇提取结果好坏的依据；构词能力鉴定法，即词频、流通度、分布 均匀度等方法，都是较为客观的统计方法，我们可以借鉴使用。但是我们不是只 对基本词汇单一的某一个特性进行考察，而是希望综合考察基本词汇的“常用性、 稳固性和构词能力”三大特征。 7 基十遗传算法的汉语幕奉词汇的白动挺取研究 第三章技术路线 本实验的技术路线是：根据e c b v 所具有的特点，选取e c b v 的特征向量：分 析语言学家列举的基本词汇，根据词汇在常用性、稳固性和构词能力的表现，把 词汇分成几部分，每一部分作为实验的一个训练集；选择合适的算法，在训练集 上经过训练( 学习) 获得每个训练集提取模型的特征向量系数；基本词汇提取 模型的研究基础词表是由北京语言大学动态流通语料库实验室提供的“工程现代 汉语通用词”的词表“1 ，根据获得的特征系数在基础词表上进行计算，得到e c b v 的提取词表；通过人工的校对完善e c b v 的提取。 在基本词汇提取的过程中，训练是一个学习的过程，即获取的知识的过程。 这种从已有的信息中获取新的规律( 规则) 的处理方式属于机器学习的范畴。 下面介绍基本词汇提取实验中用到的基础词表。工程现代汉语通用词” 词表和实验的算法选择。 3 1 通用词汇 通用词汇具有全民通用性特征，我们认为，这主要表现在如下三个方面： ( 1 ) 领域通用性：通用词汇具有在各领域、各行业普遍使用的特性： ( 2 ) 地域通用性：通用词汇具有在使用汉语进行交流的不同缝域的人们所普 遍使用的特性； ( 3 ) 时间通用性：通用词汇具有时间上使用稳定的特性。 基于通用词汇的上述特性，我们用量化的“词汇通用度”指标来表示词汇 通用的程度，用统计的方法考察大众媒体所使用词汇的通用程度，进而实现基于 现代汉语主流报纸媒体语料上的通用词汇自动提取的目标，我们把这类通用词汇 统称为“工程现代汉语通用词”( e n g i n e e r i n gd e f i n i t i o no fc o n t e m p o r a r y c h i n e s ec o 姗o n - u s i n gw o r d s ，英文简称e c c w ) 。工程现代汉语通用词”的词表是基本词汇提取的基础。 b 内盆古卿范人学颈1 - 学位论文 3 2 机器学习 机器学习( m a c h i n el e a r n i n g ) 是研究计算机怎样模拟或实现人类的学习行 为，以获取新的知识或技能，重新组织已有的知识结构使之不断改善自身的性能 机琴学习系统的结构： 图3 一l 学习系统的基本结构 环境向系统的学习部分提供某些信息，学习部分利用这些信息修改知识库， 以增进系统执行部分完成任务的效能，执行部分根据知识库完成任务。同时把获 得的信息反馈给学习部分。 机器学习策略有：经验性归纳学习、分析学习、类比学习、遗传算法、联接 学习、加强学习。 遗传算法是自然遗传学和计算机科学相互结合渗透而成的新的计算方法，它 具有白组织、自适应和自学习的智能特性。算法对问题本身没有过多的要求，是 一种简单适应，鲁棒性强的算法。遗传算法作为模拟自然的一种通用搜索方法， 尤其适用于处理传统搜索方法难以解决的复杂和非线性问题，在复杂空间领域离 散值的搜索上表现出良好的性能，所以我们选择遗传算法作为基本词汇提取的参 数训练模型。 9 基于遗传算法的汉语幕本词汇的自动提取研究 第四章遗传算法概述 遗传算法( g e n e t i ca l g o r i t h m s ，简称g a ) 是一种借鉴生物界自然选择和自然遗 传机制的随机化的搜索算法，是在2 0 世纪6 0 年代末至7 0 年代初期，主要由美 国m i c h i g a n 大学的j o h nh o l l a n d 提出。在随后的近3 0 年的不断发展中，取得 了丰硕的应用成果和理论研究的进展。遗传算法尤其适用于处理传统搜索方法难 以解决的复杂和非线性问题，被广泛应用于组合优化、机器学习、自适应控制、 规划设计和人工生命等领域，是2 l 世纪有关智能计算中的关键技术和研究热点。 4 1 遗传算法的基本术语 遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。 遗传算法是生命科学与工程科学的相互交叉、相互渗透和相互作用而成的新的计 算方法，所以遗传算法中经常使用有关自然进化中的一些基础用语。下面介绍一 些对遗传算法的学习和理解有重要意义的相关术语n 3 m 小6 m “。 染色体( c h r o m o s o m e ) 是遗传物质的主要载体，由多个基因组成。 脱氧核糖核酸( d n a ) 控制并决定着生物遗传性状的染色体中的主要部分。 基因( g e n e ) 是控制生物性状的遗传物质的功能单位和结构单位，复数个基因 组成染色体。 基因座( 1 0 c u s ) 染色体中遗传基因所占的位置。 等位基因( a l l e l e s ) 基因所取的值。 个体( i n d i v i d u a l ) 指染色体带有特征的实体。 种群( p o p u l a t i o n ) 染色体带有特征的个体的集合称为种群。该集合内个体数 称为群体的大小。有时个体的集合也称为集团。 种群规模( p o p u l a t i o ns i z e ) 群体中个体的数目称为种群大小。 适应度( f i t n e s s ) 各个体对环境的适应程度叫做适应度。 表现型( p h e n o t y p e ) 指生物个体所表现出来的性状。 基因型( g e n et y p e ) 指与表现型密切相关的基因组成。 表4 一l 遗传学和遗传算法中基础川话对照表 i o 内莹古师范大学硕一j ：学位论文 自然遗传学人工遗传算法 染色体( c h r o m o s o m e )数组、数据、位串 基因( g e n e ) 特质、个性、探测器、位 等位基因( a l l e l e ) 特性值 基因座( 1 0 c u s )串中的位置 基因型( g e n e t y p e ) 结构 表现型( p h e n o t y p e )参数集、解码结构、候选解 4 2 遗传算法的基本流程 遗传算法模拟生物进化和自然选择的过程，进行全局选优。基本过程是：通 过将具体问题的解空间的可能解进行编码，形成字符串，即生物个体。选取若干 个体形成初始种群，然后将这些生物个体进行生物进化操作，主要有选择、交叉、 变异等，得到新一代的个体，然后在新一代群体的基础上再进行进化操作，经过 若干代的进化，最终得到全局最优解。 下图显示了遗传算法的基本流程。 幕十遗传算j 去的汉语媾奉词汇的自动提取研究 幽4 - 1 遗传算法的基本流栏 遗传算法是循环迭代的过程，它通过个体的适应度值作为选择和淘汰的依 据，个体适应度高则被选择保留的概率高，适应度低的个体被淘汰的概率高。在 算法中适应度的取值是适应度函数，不同的待求问题其适应度函数不同在函数 优化中通常用函数公式本身。 下面分别进行详细的叙述。州州力 4 2 1 基本操作 基本遗传算法分为几个基本步骤：编码、产生初始种群、遗传操作( 选择、 交叉、变异) 、计算适应度、解码并得到结果等。 4 2 1 1 编码 由于遗传算法不能直接处理解空间的数据，因此我们必须通过编码将它们表 示成遗传空间的基因型串结构数据。编码在遗传算法中的含义是指将优化问题的 解空间的备选解转化为用字符串来表示。这样做的目的是便于对备选解进行遗传 操作。 字符串代表携带遗传信息的染色体，串中的每个位置的元素类似于生物的基 因。在遗传算法的实际应用中，根据待解决的实际问题不同，基因的表示方法不 同。较常用的表示方法是二进制编码法。即在字符串中只出现0 和1 。这是一种 最早的编码方法，也是最常用的编码方法。 二进制编码简单，便于进行交叉、变异等遗传操作。但是这种编码也有许多 缺点，例如其编码不便于反应所求问题的特定含义；对于一些连续函数优化问题， 二进制编码的局部搜索能力弱，原因在于欧式空间中临近点的二进制编码在海明 距离下经常是不邻近的：在对连续函数进行二进制编码时如果采用较短的字符 串，则会造成精度降低，而编码长度变长，则算法的搜索空间呈指数级增长。为 了这些问题，人们提出了许多别的编码方法。为了提供局部搜索能力，有人提出 格雷码( g r a yc o d e ) 编码方法，采用这种编码方式，欧式空间中临近点的二进制 编码在海明距离下也是相邻的。为了改善为了克服搜索效率与表示精度间的矛 盾，提出了动态参数编码法。为了提高求解效率、便于求解实际问题，并与其他 算法进行配合又提出了浮点编码( 实数编码) 、符号编码等。此外还有十进制编 1 2 内翟古师范人学硕i j 学位论史 码、多值编码、区间值编码、d n a 编码、d e l t a 编码、对称编码等多种编码方法 4 2 1 2 产生初始种群 产生初始种群是在求解之前，在解的备选空间中选择若干个体组成初始种 群，通常产生初始种群采用的是随机法。 遗传算法的运算对象是由若干个体所组成的集合，称为群体。遗传算法正是 这样一种群体型的操作，任何遗传操作都是从一个由若干个初始个体组成的初始 群体开始的。初始群体的每个个体都是通过随机方法产生的。初始群体也称为进 化的初始代，即第一代。初始群体规模( 即群体中包含个体的数目) 的确定和个 体种类的选择对优化过程有着一定影响：若群体规模太大，则计算量增加，影响 算法性能，还对交叉操作产生负作用，表现在：当群体中个体非常多时，少量适 应度很高的个体会被选择而生存下来，但大多数个体却被淘汰，影响配对库的形 成，若群体规模太小，会使遗传算法的搜索空间中分布范围有限，因而搜索有可 能停止在未成熟阶段，引起早熟现象。 4 2 1 3 进行遗传操作 遗传操作是对种群中的个体的字符串进行选择复制、交叉、变异等处理，目 的在于产生新的个体，构成新的一代。这个过程是对生物界的进化过程的模仿。 产生的种群的总体适应度比其前一代高，经过若干代的迭代，种群得到不断优化， 这个过程类似于自然界生物的进化过程。度量个体的适应度的参数是适应度函 数。 4 2 1 4 适应度函数 在研究自然界中生物的遗传和进化现象时，生物学家使用适应度这个术语来 度量某个物种对于其生存环境的适应程度。对生存环境适应程度较高的物种将有 更多的繁殖机会：而对生存环境适应程度较低的物种，其繁殖机会就相对较少， 甚至会逐渐灭绝。与此相类似，遗传算法中也使用适应度这个概念来度量群体中 各个个体在优化计算中有可能达到或接近于或有助于找到最优解的优良程度。适 应度较高的个体遗传到下一代的概率就较大：而适应度较低的个体遗传到下一代 的概率就相对小一些。度量个体适应度的函数称为适应度函数。遗传算法在进化 搜索中基本上不需要其它外部信息，仅用适应度函数来评估个体的优劣。适应度 函数由分为无约束条件的适应度函数和有约束条件的适应度函数。遗传算法的目 基于遗传算法的汉语皋奉词汇的自动提取研究 标函数不受连续可微的约束，且定义域可以为任意集合。对目标函数的唯一要求 是，针对输入可计算出能加以比较的结果。 4 2 1 5 终止条件 终止条件是指在什么情况下认为算法找到了最优解，从而可以终止算法。由 于通常用遗传算法解决具体问题时，并不知道最优解是什么，也不知道其最优解 的目标函数值，因而需要通过设定终止条件让算法终止，并获得最优解。 常用的终止条件有： ( 1 ) 如果目标函数的最优值已知，那么种群中这个最优值出现或已十分接近 该值，算法终止，输出最优解。 ( 2 ) 规定一定的遗传代数，达到这个规定的遗传代数时，算法终止，认为达 到最优解。 ( 3 ) 群体个体的进化已趋于稳定状态，也就是占群体一定比例的个体己完全 是同一个体，则算法终止。 4 2 1 6 获得最优解 在进行每次遗传操作产生新的种群后，根据终止准则判断是否得到最优解。 如得到最优解，则终止迭代过程，然后对得到的最优个体进行解码，输出求得的 最优解。 4 2 2 遗传算子 在遗传算法中，通过编码组成初始群体后，遗传操作的任务就是对群体的个 体按照它们对环境适应的程度施加一定的操作，从而实现优胜劣汰的进化，最终 逼近最优解。遗传算法操作包括三个基本遗传算子，分别是：选择、交叉、变异。 4 2 2 1 选择 从群体中选择优胜的个体，淘汰劣质个体的操作叫选择( s e l e c t i o n ) 。种群 中的个体在进行交叉之前。要进行选择。选择的目的是把优胜的个体直接遗传到 下一代或通过配对交叉产生新的个体再遗传到下一代。选择的依据是个体的适应 度，适应度值高的个体被选中的可能性大适应度低的个体被选中的概率小。适 应度高的个体可能被多次复制，而适应度低的个体可能一次也未被选中。选择算 子有时也叫复制算子。 1 4 内蒙古师范人学硕士学位论文 常用的选择方法是适应度比例法，也叫轮盘赌法或蒙特卡罗法。它的基本原 则是按照个体的适应度大小比例进行选择。若某代种群有n 个个体，个体i 的适 应度值为f i ，则i 被选中的概率为p 。，即 p i ：# f i i i 除了适应度比例法外，还有最佳个体保存方法、期望值方法、排序选择方法、 排挤方法、联赛选择方法。 4 2 2 2 交叉 所谓的交叉( ( c r o s s o v e r ) 是指将两个父代个体的编码串的部分基因进行交 换，产生新的个体的操作。交叉是模拟生物的繁殖活动。交叉是种群遗传算法中 的重要算子，是种群产生新个体的主要手段。对于二进制编码，具体实施交叉的 方法有单点交叉、两点交叉、多点交叉、一致交叉等。对于实数编码，交叉的方 法有离散重组、中间重组、线性重组等。 以二进制编码方式下的单点交叉为例来说明交叉的操作。有两个个体的编码 分布为( 1 0 0 1 1 1 1 ) ，( 0 0 1 1 0 0 0 ) ，选择的交叉点在第4 和第5 个基因座之间。则交 叉后的两个个体编码为：( 1 0 0 1 0 0 0 ) ，( 0 0 1 1 1 1 1 ) ，下图显示了交叉的操作。 个体a1 0 0 11 1 1 1 0 0 1 0 0 0 新个体a 1 个体b0 0 1 l0 0 0 - - - - 0 0 1 1 1 1 1 新个体b 1 4 2 2 3 变异 变异算子的基本内容是对群体中的个体串的某些基因座上的基因值作变动。 就基于字符集 0 ，1 ) 的二值码串而言，变异操作就是把某些基因座上的基因值取 反，即l 变为0 或0 变为1 。 遗传算法导入变异的目的有两个：一是使遗传算法具有局部的随机搜索能 力当遗传算法通过交叉算子已经接近最优解邻域时，利用变异算子的这种局部 随机搜索能力可以加速向最优解收敛。二是使遗传算法可维持群体多样性，以防 止出现未成熟收敛现象。 4 2 3 参数控制 基本遗传算法( s i m p l eg e n e t i ca l g o r i t h m ，s g a ) ，也称为简单遗传算法。 1 5 基于遗传算法的汉语基奉词扯的白动提取研究 在遗传算法操作过程中，主要参数有； ( 1 ) 交叉概率 交叉概率是种群中个体进行交叉的概率。较大的交叉概率可增强遗传算法开 辟新的搜索领域的能力，但群体中优良的模式遭到破坏的可能性增大；若交叉概 率太低，产生新个体的速度较慢，遗传算法搜索可能陷入迟钝状态。通常取0 5 0 9 之间的数 ( 2 ) 变异率 变异率是种群中个体发生变异的概率。变异概率太小，变异操作产生新个 体的能力和抑制早熟现象的能力就会较差；而过高频度的变异虽然能产生出较多 的新个体，但也有可能破坏很多较好的模式，将使遗传算法趋于纯稗的随机搜索， 一般取为0 0 0 1 - 0 1 。 ( 3 ) 种群规模 种群规模n 是指组成种群的个体数目。通常这个参数从算法开始到结束保持 不变。种群规模到底取多少决定于具体的待求问题，通常取3 0 1 0 0 。 ( 4 ) 染色体长度( 编码长度) 染色体长度是指用多长的字符串表示个体，也称为编码长度m 。编码长度的 大小决定于待求解闯题的变量的取值范围及其精度。取值范围越大。编码长度越 长；求值精度越高，编码长度越长。 ( 5 ) 代沟 代沟控制着每一代群体构成中个体被更新的百分比，即在t 代有m ( 卜g ) 个 个体被选择复制到t + l 代群体中。“代沟”方式的选用为遗传算法利用优化过程 的历史信息提供了条件，加速了遗传算法的收敛过程。 ( 6 ) 算法终止的准则通常是规定一个最大的进化代数，进化代数达到该值算 法即终止。最大进化代数通常取1 0 0 5 0 0 。 以上运行参数的取值只是一般情况下的常用取法，并非固定不变的，在不同 的遗传算法中可以根据具体情况作适当的调整，有时调整后的值可能会与上面的 值有较大差异，但只要能提高算法的运行效率就是可行的。 通常在确定数值之后，在整个算法进行过程中，这些参数就一直不变。但在 有些改进的算法中某些参数可能会变化，变化的目的是为了获得性能上的提高或 1 6 内萤古师范人学顾1 ：学位论文 满足特殊的需要。 4 3 遗传算法的理论基础 模式定理是遗传算法的理论基础，它描述了遗传算法的搜索策略。在进一步 讨论之前，首先了解相关的定义m 1 4 3 1 模式的定义 模式( s c h e m a ) 是一个描述字符串集的模版，该字符串集中的串的某些位置 上存在相似性。 定义4 1 基于三值字符集 0 1 ，) 所产生的能描述具有某些结构相似性的 0 ，l 字符串集的字符串称作模式。其中木为通配符。 以长度为5 的串为例，模式* 0 0 0 1 描述了在位置2 、3 、4 ，5 具有形式“0 0 0 1 ” 的所有字符串，即( 0 0 0 0 1 ，1 0 0 0 1 l 。可以看出，模式的概念为我们提供了一种简 洁的用于描述在某些位置上具有结构相似性的0 、l 字符串集合的方法。这里需 要强调的是，。 ”只是一个描述符，而并非遗传算法中实际的运算符号，它仅仅 是为了描述上的方便而引入的符号而已。 一个串中隐含着多个不同的模式。确切地说，长度为l 的串，隐含着2 个不 同的模式，而不同的模式所匹配的串( 称作模式的样本) 的个数是不同的。比如 模式“1 木料| c ”与模式“0 1 0 , ”相比，后者所匹配的串( r 4 本) 的个数比前者少， 即后者的确定性高。 因此我们引入“阶”的概念来表示模式的确定程度。 定义4 2 一个模式h 的阶就是出现在模式中的。0 ”和“l ”的数目，记为 o ( h ) 。 例如，模式“l 料料”的阶为1 。模式“0 1 0 ”的阶为3 。一个模式的阶数越 高，其样本就越少，因而确定性越高。 但是，模式阶并不能反映模式的所有性质。对于模式“叭料”和“o 料宰1 ” 它们的阶相同，但是，模式“0 料l ”要跨越更长的距离，所以，在进行交叉运 算时，模式。0 料 1 。更容易被破坏，因此，需要引入。长度”的概念。 定义4 3 一个模式h 的长度就是模式中第一个确定位置和最后一个确定位 1 7 苹十遗传算法的汉语苹奉词汇的自动提取研究 置问的距离，记为6 ( h ) 例如。模式。0 1 木料”的长度为1 ，模式“叶料1 ”的长度为4 。 4 3 2 模式定理 定理4 1 ( 模式定理) 在遗传算子选择、交叉和变异的作用下，具有低阶、短 定义距以及平均适应度高于群体平均适应度的模式在子代中得以指数级的增长 模式定理是遗传算法的理论基础，有着深远的意义。对该定理可以这样理解， 下面通过一个实例来观察一下遗传算法对模式的处理情况。采用求f ( x ) = x 2 极值 为实例。假设x 的取值范围为 0 ，3 1 ，则x 可编码为5 位二进制数。给定4 个初 始串，然后施加选择、交叉、变异操作，有关的过程由图4 2 表示。 现考察3 个模式：h l = 1 料 h 2 1 0 $ 和h 3 = l + o 的运行情况。首先来看 h 。在遗传操作下的变化。在选择阶段，各串按照其适应度在群体适应度中所占的 比例进行复制( 比例复制法) 。观察表4 - 1 ，可以看出，由于串2 的适应度大，其 复制概率高，经过选择被复制成2 份，而串3 则丢失了。注意到串2 、4 都是h 的样本，这样通过选择后，h l 的样本增至为3 。由模式定理，理论上应有m f ( h ) f - ，。个样本，其中f ( h ) = ( 5 7 6 + 3 6 1