（电路与系统专业论文）人工鱼群算法在聚类问题中的应用研究.pdf

安徽人学硕二l 学位论文 摘要 摘要 yliii1 1 2 l q 12l ll 6 l l l1 l i l t 3 f i l l 3 1 1 1 4 1 1 1 1y 2 2 6 13 3 4 聚类在数据挖掘、统计学、机器学习等很多领域都有广泛应用。聚类问题实 质是一个全局优化问题。遗传算法是一种基于生物自然选择与遗传机理的随机搜 索与优化方法。人工鱼群算法( a f s a ) 是一种新提出的新型仿生优化算法。它采用 自下而上的设计方法，对寻优空问的形式和性质没有特殊要求。算法具有良好自 适应能力，克服局部极值、取得全局最优值的能力和较快的收敛速度，可用于许 多优化模型的求解。人工鱼群算法为求解优化问题提供一种新思路，新方法。 本文在深入研究人工鱼群算法和遗传算法的基础上，将遗传算法中的选择、 变异交叉融合到人工鱼群算法，提出一种人工鱼群算法与遗传算法融合算法，并 应用于求解聚类问题。本文的主要研究内容和研究成果如下： 1 在深入研究人工鱼群算法和聚类问题的基础上，提出了求解分类数目已知 的聚类问题的人工鱼群算法。首先构造人工鱼个体模型，确定人工鱼个体和聚类 问题的联系，确定算法的目标函数，然后编程求得最优解。 2 在深入研究求解聚类问题的人工鱼群算法的基础上，为了克服算法初期收 敛速度快，后期收敛速度慢的缺陷，本文提出了一种改进人工鱼群算法。在最优 值连续无变化或变化不明显时采用变异或交叉操作，消除人工鱼漫无目的随机游 动或大量聚集在非全局极值点附近的局限，提高算法的求解速度和求解精度，改 善求解质量。 关键词：人工鱼群算法；遗传算法；聚类；优化。 安徽大学硕i j 学位论文a b s t r a c t a b s t r a c t c l u s t e r i n gh a sb e e na p p l i e dt om a n ya r e a s ，i n c l u d i n gd a t am i n i n g ，s t a t i s t i c s ，a n d m a c h i n el e a r n i n ga n dc a nb er e g a r d e da sa g l o b a lo p t i m i z a t i o np r o b l e m t h eg e n e t i c a l g o r i t h mi sar a n d o ms e a r c ha n do p t i m i z e ds o l u t i o nt h a tm i m i c st h ep r o c e s so f n a t u r a le v o l u t i o na n dg e n e t i c s a r t i f i c i a lf i s hs w a r ma l g o r i t h m ( a f s a ) i sa n o v e l b i o i n s p i r e do p t i m i z i n gm e t h o d i ti sa l s oas u p e r i n c u m b e n td e s i g nm e t h o d ，a n dh a s n op a r t i c u l a rd e m a n d so nt h ef o r ma n dp r o p e r t yo ft h eo p t i m i z a t i o ns p a c e t h e a l g o r i t h mh a ss t r o n gs e l f - a d j u s t m e n ta b i l i t ya n dr a p i dc o n v e r g e n c es p e e d ，a l s oc a n o v e r c o m et h el o c a lt h r e s h o l da n da c q u i r et h eg l o b a lb e s t o p t i m i z e dv a l u e ，a n d t h e r e f o r ec o u l db ea p p l i e di n t ot h ec a l c u l a t i o nf o rm a n ym o d e lo p t i m i z a t i o n s t h e a r t i f i c i a lf i s hs w a r ma l g o r i t h m p r o v i d e s ak i n do fn o v e lm e t h o dt os o l v et h e o p t i m i z a t i o np r o b l e m s o nt h eb a s i so fa d v a n c e dr e s e a r c ho nt h ea r t i f i c i a lf i s hs w a r ma l g o r i t h ma n dt h e g e n e t i ca l g o r i t h m ，t h i sp a p e rp r e s e n t sa na l g o r i t h m sc o m b i n a t i o no ft h ea r t i f i c i a lf i s h s w a m i a l g o r i t h ma n dt h eg e n e t i ca l g o r i t h mb ym e a n so fc o m b i n i n gt h es e l e c t i o na n d m u t a t i o nf r o mt h eg e n e t i ca l g o r i t h mw i t ht h ea r t i f i c i a lf i s hs w a r m a l g o r i t h m t h er e s e a r c hc o n t e n ta n dr e s u l t sa r eb r i e f l yd e s c r i b e da sb e l o w ， 1 o nt h eb a s i so fa d v a n c e dr e s e a r c ho nt h ea r t i f i c i a lf i s hs w a r ma l g o r i t h ma n d c l u s t e r i n gp r o b l e m s ，t h i sp a p e rp r o v i d e st h ea r t i f i c i a lf i s hs w a l t da l g o r i t h mo n s o l v i n gc l u s t e r i n gp r o b l e m sw h i c hn u m b e r so fs o l u t i o nc a t e g o r i e sa r ek n o w n t h e r o u g hp r o c e s si s ；f i r s t l y , t os t r u c t u r et h ei n d i v i d u a la r t i f i c i a lf i s hm o d e l ，a n dt h e n m a k ep r o p e rc o n n e c t i o n sb e t w e e nt h ei n d i v i d u a la r t i f i c i a l f i s ha n dt h ec l u s t e r i n g p r o b l e m ，t h e nc o n f i r mt h eo b j e c t i v ef u n c t i o nt ot h ea l g o r i t h m ，l a s t l y , t op r o g r a m m e f o rt h eb e s ts o l u t i o n 2 o nt h eb a s i so fa d v a n c e dr e s e a r c ho nt h es o l u t i o n so ft h ec l u s t e r i n gp r o b l e m s a n dt h ea r t i f i c i a lf i s hs w a r ma l g o r i t h m ，t h i sp a p e r p r e s e n t st h ei m p r o v e da r t i f i c i a l f i s hs w a r ma l g o r i t h m ，w h i c hc a na v o i do v e rr a p i dc o n v e r g e n c es p e e da t a ne a r l i e r t i m ea n do v e rs l o wc o n v e r g e n c es p e e da tal a t e rt i m e i i 安徽人学颂一i j 学位论文a b s t r a c f 一一 w h e nt h eb e s to p t i m i z e dv a l u eh a sn oc o n t i n u o u s c h a n g eo rn oo b v i o u s c h a n g e ，t h ei m p r o v e da r t i f i c i a lf i s hs w a r ma l g o r i t h mi n v o l v e di n t h i sp a p e ra p p l i e s v a r i a n c ea n dc r o s s o v e ro p e r a t i o n si no r d e rt oe l i m i n a t et h ea r t i f i c i a lf i s h sa i m l e s s l y r a n d o mm o v e m e n to rt h em a s s i v ec o n v e r g e n c e sa r o u n dt h en o n g l o b a lt h r e s h o l d ， a n dc o n s e q u e n t l yg a i nt h eh i g h e rs p e e d ，b e t t e ra c c u r a c ya n di m p r o v e dq u a l i t yi n c a l c u l a t i o n t h ee x p e r i m e n tr e s u l ti se f f e c t i v eb yc h o s e nu c id a t aa st h ec l u s t e r i n g d a t aa n dh a sb e e ne m u l a t e db yt h ej a v ap r o g r a m k e yw o r d s ：a r t i f i c i a lf i s hs w a r ma l g o r i t h m ，g e n e t i c a l g o r i t h m ，c l u s t e r i n g ， o p t i m i z a t i o n i l l 安徽大学硕二| 二学位论文 插图清单 插图清单 图卜l 数据挖掘分类示意图4 图卜2 聚类算法分类示意图7 图3 1 遗传算法流程图2 7 图4 1i r i s 数据i a f s a 聚类过程，1 3 1 代以后目标函数值稳定在9 7 2 2 3 6 图4 2w i n e 数据i a f s a 聚类过程，1 4 2 代以后目标函数值稳定在1 6 5 3 0 5 3 3 7 图4 3i r i s 数据集聚类过程，1 2 1 代以后 目标函数值稳定在9 7 2 2 3 7 图4 4 连续1 0 次运行平均进化代数比较3 8 安徽入学坝：i j 学位论文i l l u s t r a t i o nl i s t i1lu st r a tio nlist f i g 1 1c l a s sd i a g r a mo fd a t am i n i n g 4 f i g 1 2c l a s sd i a g r a mo fp o l yc l a s s i f i c a t i o na l g o r i t h m 7 f i g 3 一lg e n e t i ca l g o r i t h mf l o w c h a r t 2 7 f i g 4 一li r i sd a t ai a f s ac l u s t e r i n gp r o c e s s 1 3 1o nb e h a l fo ft h eo b j e c t i v ef u n c t i o n v a l u ea f t e rt h es t a b i l i z a t i o n9 7 2 2 3 6 f i g 4 - 2w i n e d a t ai a f s ac l u s t e r i n gp r o c e s s ，1 4 2o n b e h a l fo ft h eo b j e c t i v ef u n c t i o nv a l u ea f t e r t h es t a b i l i z a t i o n1 6 ，5 3 0 5 3 3 7 f i g 4 - 3i r i sd a t ac l u s t e r i n gp r o c e s s ，1 2 1o n b e h a l fo ft h eo b j e c t i v ef u n c t i o nv a l u e a f t e rt h es t a b i l i z a t i o n9 7 2 2 3 7 f i g 4 4r u nf o r1 0t i m e st h ea v e r a g ee v o l u t i o n g e n e r a t i o nc o m p a r e d 3 8 v i i 安徽大学硕士学位论文 第一章绪论 第一章绪论 计算机技术和通信技术的蓬勃发展，为数据库广泛应用于商业管理、工程丌 发、政府办公和科学研究等场合奠定了基础，而且数据库的应用范围也在逐步扩 大，信息量不断增大。信息爆炸的时代已经到来，信息过量已经成为人们急需面 对和解决的问题。由此人们提出了一系列的问题，例如如何从大量的历史数据中 及时发现有用的信息，从而提高信息得利用效率? 真正让数据成为一个单位的资 源，充分利用现有的大量数据信息，帮助单位业务决策和战略发展? 在这个历史 背景下，产生了数据挖掘( d a t am i n i n g ) 和知识发现( d m k d ) 技术n 1 ，而且该技术 得到了蓬勃发展，并表现出强大的生命力。 1 1 数据挖掘技术 所谓数据挖掘( d a t am i n i n g ) 3 就是从大量的不完全的有噪声的模糊的随 机的数据中，挖掘隐含在其中的人们事先不知道的、而又是潜在有用的信息和知 识的过程。 1 1 1 数据挖掘技术的应用领域及研究现状 在1 9 8 9 年举行的第十一届国际联合人工智能学术会议上，首次出现了从数据 库中发现知识( k d d ) 心1 一词。截至目前，美国人工智能协会主办的k d d 国际研讨 会已经多次召开，由原来的专题讨论会逐步发展到国际学术大会，也逐渐从发现 方法为研究重点转向系统应用为研究重点，更加注重多种发现策略和技术的集成 和多种学科相互渗透。亚太地区1 9 9 9 年在北京召开了第三届p a k d d 会议，会议共 收到论文1 5 8 篇，人们研究的热情空前高涨。在1 9 9 3 年i e e e 的k n o w l e d g ea n dd a t a e n g i n e e r i n g 会刊率先出版专刊讨论k d d 技术。其他的很多领域的国际学会、学刊 ( 例如：并行计算、计算机网络和信息工程等) 也专题或专刊讨论数据挖掘和知 识发现问题。 此外，互联网上也有很多电子出版物关于k d d 技术，最为权威的是k n o w e d g e 安徽人学硕士学位论文人工鱼群算法在聚类问题中的应用研究 d i s c o v e r yn u g g e t s ( h t t p ：w w w k d n u g g e t s c o m s u b s c r i b e h t m l ) 半月刊。d m e m a i1c 】u b 等许多自由论坛也在讨论d m 技术。典型数据挖掘系统在世界上目前主 要有：e n t e r p r i s em i n e r ( s a s 公司的) 、i n t e li g e n tm i n e r ( i b m 公司的) 、 s e t m i n e r ( s g i 公司的) 、c l e m e n t i r e ( s p s s 公司的) 、w a r e h o u s es t u d i 0 ( s y b a s e 公司的) 、s e e 5 ( r u l e q u e s tr e s e a r c h 公司的) 等等。还有专业网站( 如： h t t p ：w w w d a t a m i n i n g l a b c o m ) 提供许多数据挖掘系统和工具的性能测试报 告。 国内研究d m k d 与国外相比要晚，还没有形成整体实力。国家自然科学基金9 3 年开始支持该领域的研究项目。当前，国内的科研机构和高等院校正积极展开知 识发现的相关基础理论研究及其应用研究。主要科研单位有以研究模糊方法在知 识发现中应用的北京系统工程研究所、以主要研究数据立方体代数问题北京大 学、还有主要研究对关联规则开采算法的优化和改造的华中理工大学、复旦大学、 浙江大学、中国科学技术大学、中国科学院数学研究所、吉林大学等研究机构； 以主要探讨研究非结构化数据的知识发现以及w e b 数据挖掘方向的南京大学、四 川联合大学和上海交通大学等高校。 随着d m k d 研究的深入，数据库、人工智能和数理统计已经成为数据挖掘和知 识发现的三根强大的技术支柱。目前d m k d 的主要研究内容包括基础理论研究、发 现算法研究、数据仓库研究、可视化技术研究、定性定量互换模型研究、知识表 示方法研究、发现知识的维护和再利用研究、半结构化和非结构化数据中的知识 发现研究以及网上数据挖掘研究等。 1 1 2 数据挖掘技术概述 所谓数据挖掘( d a t am i n i n g ) 就是从大量的不完全的有噪声的模糊的随机的 数据中，挖掘隐含在其中的人们事先不知道的、而又是潜在有用的信息和知识的 过程。相似的描述还有很多，例如从数据库中发现知识( k d d ) 、数据分析、数据 融合( d a t af u s i o n ) 以及决策支持等。 人们认为形成知识的源泉是原始数据，它可以是结构化的数据( 如：关系数 据库中的数据) ，可以是半结构化的数据( 如：文本、图形、图像数据) ，也可 以是异构型数据( 如：分布在网络上的数据) 。发现知识的方法很多，有数学的 安徽大学坝一i j 学位论文第一章绪论 方法和非数学的方法；有演绎的方法和归纳的方法。发现的知识可应用于众多领 域：像信息管理领域、查询优化领域、决策支持领域、过程控制领域以及数据本 身的维护领域等。因此，数据挖掘技术汇聚了众多领域的科研人员，尤其是数据 库领域、人工智能领域、数理统计领域、并行计算领域等方面的科研人员。可以 说数据挖掘是一门广义上的交叉学科。 从数据挖掘技术的产生背景就决定了它是一种面向应用的技术。不但广泛应 用于面向特定数据库的检索查询调用，而且可以对数掘进行微观、中观乃至宏观 的统计、分析、综合、推理，从而指导求解实际问题，发现事件间的关联和利用 已有的数据对未来进行预测。知识发现的目标不是去发现真理、不是去发现崭新 的自然科学定理以及纯数学公式，更不是去证明机器定理的，而是去发现面向特 定应用领域，特定的前提条件和约束条件，具有相对性的知识。因此可以说d m k d 的研究成果是讲求实际的应用的。 数据挖掘技术能够发现的知识类型主要有：广义型、特征型、差异型、关联 型、预测型和偏离型知识。 表达同类事物共同性质的广义型知识； 描述事物各方面的具体特征的特征型知识； 描述事物之间依赖或关联的关联型知识： 按照历史的和当前的数据对未来数据推测的预测型知识； 描述事物偏离常规的现象的偏离型知识。 上述知识可以在不同的概念层次上发现，从微观到中观然后到宏观，随着概 念树由下向上攀升，可以为不同层次不同用户提供决策需求。知识发现的主要工 具和方法有很多，诸如分类、聚类、模式识别、减维、可视化、决策树、遗传算 法、不确定性处理等都是。 很多学科领域都与数据挖掘有关，数据挖掘的方法也有很多，按照不同的分 类标准可以划分为不同的类型，图卜1 列出了主要分类方法。 安徽大学坝士学位论文人：l i 鱼群算法在聚类问题中的应用研究 数 据 挖 掘 分 类 分类或预测模型发现 数据总结 聚类 关联规则发现 序列模式发现 依赖关系或依赖模型发现 异常和趋势发现 有关系数据库 面向对象数据库 空间数据库 时态数据库 文本数据源 多媒体数据库 异质数据库 遗产数据库以及环球网w e b r 归纳学习方法( 决策树、规 机器学习方法 基于范例学习 则归纳等 l 遗传算法 厂回归分析( 多元回归、自回归等) l 判别分析( 贝叶斯判别、费歇尔 笋0 另0 、非参数笋0 另0 等) j 聚类分析( 系统聚类、动态聚类 统计方法等) l 探索性分析( 主元分析法、相关 1分析法等) ( f 前向神经网络( b p 算法等) j 自组织神经网络( 自组织特 神经网络方法1征映射、竞争学习等) ( 厂多维数据分析或联机分析处 数据库方法 t 面向属性的归( o 纳l a 方p 法) 方法 图卜1 数据挖掘分类示意图 f i g 1 一】c l a s sd i a g r a mo fd a t am i n i n g 从挖掘任务和挖掘方法的角度，下面主要讨论数掘抽取、分类发现、聚类和 厂l，i，、ii一厂， y 。( 在求极大问题中y ； y 。，若尝试 t r y n u m b e r 次后仍不满足前进条件，就随机移动一步执行随机行为。 ( 2 ) 聚群行为 设向量x ；表示人工鱼当前状态，计算当d v i s u a l 时，即当前邻域内的r l ，( 伙 伴数目) 及x 。( 中心位置) ，如果满足y 。n ， 8y 。，则表明伙伴的中心有较多的食 物并且不太拥挤，那么就朝x 。( 伙伴的中心位置) 方向前进一步，否则进行觅食 行为。 ( 3 ) 追尾行为 设向量x 。表示人工鱼当前状态，寻找当前邻域内( 即满足d v i s u m ) 的伙 伴中的伙f l ；x 使得y 。为最优，若满足y 。n ， 8y 。晚明伙伴x 。的：状念周围不太捌挤 且有较高食物浓度，那么就朝伙伴x 。的方向前进一步，否则，执行觅食行为。 ( 4 ) 随机行为 人工鱼的随机行为就是向感知范围内随机选择的一个状态方向移动的行为， 是人工鱼觅食行为的一个缺省行为。 安徽火学硕：l 学位论文 第二章人工鱼群算法 2 1 3 行为选择 依据待解决问题的性质，评价人工鱼当前所处的环境，然后选择某种行为。 最常用的评价方法就是选择各行为中使得向最优方向进步最大的行为，即选择各 行为中，让人工鱼的下一个状态最优的行为，若没有能使人工鱼下一状态优于当 前状态的行为，那么就进行随机行为。 2 2 组合优化问题的人工鱼群算法 组合优化问题涉及到各个领域，例如交通运输、经济管理和通信网络等领域， 是运筹学中的一个经典且重要的分支，主要是寻找离散事件的最优编排、分组、 次序或筛选等。 2 2 1 组合优化问题 组合优化问题的数学模型1 8 1 描述为： m i n f ( x ) 3 t g ( x ) 0 ( 2 1 ) x d 式( 2 1 ) 中，函蝴x ) 、g ( x ) 分别表示目标函数和约束函数，变量x 表示决 策变量，d 代表有限个元素组成的集合。一般情况下，用三参数( d ，f ，厂) 来表示 一个组合优化问题，其中，集合d 表示决策变量的定义域，参数f 表示可行解域， 定义f = x l x d ，g ( x ) o ) ，参嫉示目标函数。如果x + 满足尺x + ) = m i n a x ) i x f ) 。则称x + 为问题的最优解。 2 2 2 人工鱼群算法中的距离和领域 解决组合优化问题时，经常涉及距离、邻域和中一t l , 等概念，给出这些概念在 人工鱼群算法中的定义。 ( 1 ) 距离 安徽大学硕：i ? 学位论文 人工鱼群算法在聚类同题中的应用研究 在组合优化问题( d ，f ，) 中，定义式( 2 2 ) 表示决策变量x l 和x 2 之间的距 离。 d i s t a n c e ( x l ，x 2 ) = lx l x 2l + lx 2 。x l i( 2 2 ) 在聚类1 9 题中，表示不i 司时属于x l 和x 2 的元素的个数。 ( 2 ) k 距离邻域 对于组合优化问题p ，f ，f ) ，定义式( 2 3 ) 表示x 的k 一距离邻域。 n ( x ，k ) = ( x ld i s t a n c e ( x ，x ) y 。( 在求极大问题中y ， y ，若 尝试t r y n u m b e r 次后仍不满足前进条件，则执行其他行为( 如随机移动行为) 。 聚群行为：设向量x j 表示人工鱼当前状态，计算当d 6 ，( o 6 1 ) ，则表明伙伴中心不太拥 挤并且有较多的食物，并且y 。 6 ，则表明伙伴x 。的附近不太拥挤并且有较多的食物，就朝伙伴k ；。的方 向前进一步，否则，执行觅食行为。 约束行为：组合优化问题求解过程中，因为在人工鱼的聚群行为、随机行为 等操作的作用下，人工鱼的状态容易变得不可行，此时，为了让人工鱼重新转变 成可行的状态，需呀利用相应的约束对人工鱼的状态进行规整化。 公告板：设置公告板的目的是记录最优人工鱼的状态。在寻优过程中，各人 工鱼个体每次行为结束都检验公告板的状态与自身状态，如果自身状态优于公告 板状态，就把自身状态保存到公告板上，最终历史最优的状态记录在公告板上。 移动策略：它是基本人工鱼群算法中行为评价的一种延伸，可以采用基本人 工鱼群算法中的行为评价模式，也可以采取特定的行动策略，如让人工鱼先进行 追尾行为，若无进步再执行觅食行为，若任无进步则执行聚群行为，若任然没有 进步就执行随机行为。 2 2 4 人工鱼群算法求解聚类问题 聚类问题的实质是一个优化问题，使得聚类的结果对应的目标函数得到最 优解。基本人工鱼群算法的整体描述如下： 步骤l ：算法初始化。设定人工鱼的数量m ，视野范n v i s u a l ，拥挤因子6 安徽大学硕士学位论文 一 ：生鱼鲎篁：鲨垄鍪鲞塑望! 箜些里婴壅 _ - _ _ h - _ ，- - _ - _ - _ _ _ - _ _ _ - _ _ _ - 一 ( d e l t a ) ，每次试探的最大次数t r y n u m b e r ，最大进化代数m a x g e n 等参数；初始 化m 条鱼的初始状态a m ，计算其目标函数值y m ，登记公告板。 步骤2 ：每条鱼先进行追尾行为，若其状态优于公告板，则更新公告板后转 步骤3 ，否则执行群聚行为：若其状态优于公告牌，则更新公告牌后转步骤3 ， 否则，执行觅食行为；若其状态优于公告牌，则更新公告牌。 步骤3 ：若m 条鱼都执行了步骤2 ，则转步骤4 ，否则转步骤2 。 步骤4 ：若公告板没有更新，随机选择一条人工鱼使其状态改变为公告板上 的状态。 使用u c i 数据集进行聚类实验，结果如表2 - i 、表2 - 2 所示。从实验数据表2 1 可以看出，a f s a 在求解分类数目已知的聚类问题时，求解结果不是特别稳定， 人工鱼进化代数也较多，运算时间较长；表2 2 d p a f s a 求解的最优值优于原数据 集提供的分类结果求得的目标函数值。但是，求解结果还有改进的空间，算法 还可以进一步优化。 表2 一la f s a j 对i r i s 、w i n e 平1 g l a s s ：数据集实验数据 数据集 i r i sw i n eg 1 3 s s 项目值代数值代数值代数 第1 次 9 7 4 32 0 41 6 9 7 8 2 62 5 22 2 0 6 72 5 3 第2 次 9 7 5 l 3 0 01 6 7 7 6 6 12 1 62 2 5 8 92 1 3 第3 次 9 7 2 32 5 61 6 5 7 8 7 62 4 02 2 0 2 62 8 1 第4 次 1 2 9 22 7 91 6 5 3 0 5 32 3 02 5 1 6 82 7 3 第5 次 1 3 3 72 0 41 7 0 6 9 1 52 9 62 2 5 8 82 0 4 第6 次 9 7 7 4l3 91 6 9 8 5 8 32 6 l2 1 9 2 92 1 0 第7 次 1 3 5 5 l4 4 91 7 2 2 2 8 2 2 1l2 2 2 1 42 5 3 第8 次 9 7 7 32 4 6 1 6 9 5 2 9 91 9 32 1 8 2 32 4 7 第9 次9 7 2 21 6 91 6 5 3 6 1 92 6 l2 1 3 2 22 4 3 第1 0 次 1 2 6 92 7 61 6 5 4 8 9 12 9 72 2 2 3 l2 2 9 安徽人学坝j 卜学位论文笫二章人工鱼群算法 表2 2a f s a 算法的统计结果比较 数据集提供的分类结果 数据最优值平均值最差值最优解次数 求得的目标函数值 i r is9 7 2 2 1 1 5 2 2 14 2 0 01 4 1 0 0 5 1 w i f i e1 6 5 3 0 5 31 7 0 0 7 5 02 0 8 2 7 5 03 2 3 9 6 9 0 7 g 1 a s s 2 1 3 2 22 2 3 1 32 5 7 1 903 3 4 7 8 2 3 人工鱼群算法研究现状及发展趋势 鱼群算法( a f a ) u 5 。1 7 1 是2 0 0 2 年由李晓磊等提出的群集智能优化算法的又一 具体实现模型。鱼群算法采用了自下而上的寻优模式，模仿自然界鱼群的各种 行为，通过构造人工鱼个体，利用各个体的行为进行局部寻优，最终收敛到全 局最优，鱼群算法为解决优化问题提供了一种新思路，其主要特点1 7 1 如下： 具有并行性的特点，多条人工鱼可以并行搜索最优解： 具有简单性的特点，算法中仅仅使用了目标问题的函数值； 具有全局性的特点，跳出局部极值，收敛到全局极值的能力很强； 具有快速性的特点，虽有随机因素，但总体上是逐步向最优解搜索的； 具有跟踪性的特点，可以跟踪工作状况或其他因素的变更造成的极值点 的漂移，能够快速跟踪变化。 人工鱼群算法尽管有很多优点，但由于刚刚诞生且是建立在仿真基础上， 因此其性能以及理论基础还有待于进一步研究。目前对这种算法的研究主要有 三个方向： 理论基础的研究：目前，群集智能算法均是停留在仿真阶段，尚未能提 出一个完善的理论分析，因此进行理论研究可进一步完善发展各算法的性能。 算法适用范围的研究：n f l 定理表明不存在适用于任何问题的优化算法， 因此研究各群集智能算法的适用范围成为一件必要的研究工作。 系统框架的构建：人工鱼群算法是基于仿生机理，与遗传算法、蚁群算 法等群集智能算法具有许多相似的特征，因此建立系统的算法框架有利于取长 补短，发展混合型算法，提高算法的性能。 安徽火学硕上学位论文 人：【鱼群算法在聚类问题中的应用研究 2 4 小结 本章主要介绍了基本人工鱼群算法的基本思想、行为描述和行为选择。组 合优化问题涉及到各个领域，例如交通运输、经济管理和通信网络等领域，是 运筹学中的一个经典且重要的分支，主要是寻找离散事件的最优编排、分组、 次序或筛选等。求解组合优化问题的人工鱼群算法的原理与基本鱼群算法一样， 在描述和实现过程中对行为描述和移动策略进行了调整。并使用人工鱼群算法 求解分类数目已知的聚类问题。最后分析了人工鱼群算法研究的主要有三个方 向：理论基础的研究。适用范围的研究。系统框架的构建。 安徽大学硕二l ：学位论文 笫三章遗传算法 第三章遗传算法 遗传算法是模拟生物进化过程来求解问题的一种自适应人工智能技术，是 一种自适应、自组织的全局优化算法。 3 1 遗传算法的产生和发展 遗传算法简称g a ( g e n e t i ca l g o r i t h m s ) 【l 纠是1 9 6 2 年由美国m i c h i g a n 大学 的h o l l a n d 教授提出的模拟自然界遗传机制和生物进化论而成的一种并行随机 搜索最优化方法，是模拟生物进化过程来求解问题的一种自适应人工智能技术， 是一种自适应、自组织的全局优化算法。 早期关于遗传算法的研究主要集中在自然遗传系统的计算机模拟。这一时期 的发展没有明确目标，也缺乏具有指导意义的理论和相关计算工具。直到7 0 年代 中期，h o l l a n d 署d d e j o n g 发表了具有创造性研究成果口9 咖这一现状才得到改观。遗 传算法( g e n e t i ca l g o r i t h m ) 这一术语在1 9 6 7 年由b a g l e y 发表的论文中提出，而且 研究了遗传算法在自动博弈中的应用比。c a v i c c h i o 在1 9 7 0 年利用遗传算法来解决 模式识别问题心引。h o l l s t i e n 首次把遗传算法应用于函数优化问题乜3 | ，1 9 7 1 年， h o l l s t i e n 详细阐述了遗传算法用于数字反馈控制的方法。1 9 7 5 年对遗传算法研究 而言是很重要的一年，h o l l a n d 的著名专著自然系统和人工系统的适配n 叫出 版了，专著中不仅系统的阐述了遗传算法的基本理论和基本方法，而且提出了模 式理论( s c h e m at h e o r y ) 。同一年，d e j o n g 把h o l l a n d 的模式理论与其计算实验有 机结合起来了，成为遗传算法发展的重要里程碑。8 0 年代是遗传算法的兴盛发展 时期，无论是理论研究还是应用研究都很热门。因为遗传算法能够求解复杂函数 优化问题和组合优化问题，所以很多学科都广泛重视遗传算法。当人们发现不可 能找到复杂问题最优解时，退而求复杂问题的满意解，求解复杂问题的最佳工具 之一就是遗传算法。遗传算法不断汲取生物遗传学、进化论和分子生物学最新成 果，同时，算法也得到了实验证明和证伪，其本身也在不断进化1 j 。 3 2 遗传算法 安徽火学硕二l 学位论文人工鱼群算法在聚类问题中的应用研究 遗传算法的基本思想是基于m e n d e l 的遗传学说和d 删m 的进化论的比。基因 遗传原理是m e n d e l 遗传学说中最重要的原理。它认为，染色体内的基因代表了物 种的遗传特性。之所以每个基因产生的个体对环境具有某种适应性，是因为每个 基因有其特殊的位置并且控制某种特殊的性质。基因突变或基因杂交而产生的后 代相比原始基因更能适应环境的变化。经过自然淘汰，存优去劣，那些适应性强 的基因结构得以保留。适者生存原理是进化论中最重要的原理之一。它认为，在 发展进化过程中各个物种越来越适应外界环境，后代在继承父代基本特征的同 时，又会产生一些相异于父代的变化。只有能够适应新环境的个体特征在环境改 变时才能保留下来。 3 2 1 基本概念 遗传算法中涉及到很多概念与进化论和遗传学有关，主要有：串( s t r i n g ) 、 种群( p o p u l a t i o n ) 、种群大小( p o p u l a t i o ns i z e ) 、基因( g e n e ) 、基因位置( g e n e p o s i t i o n ) 、基因特征值( g e n ef e a t u r e ) 、串结构空间s 8 、参数空间s 9 和适应度 ( f i t n e s s ) 等。 ( 1 ) 串( s t r i n g ) 串是个体的表现形式，和遗传学中的染色体( c h r o m o s o m e ) 相对应。串用 二进制表示，串的一位对应于染色体中的一个基因，串的总位数表示了染色体的 长度。在遗传算法中，串或染色体表示实际问题的解。 ( 2 ) 种群( p o p u l a t i o n ) 每代所产生的染色体的集合称为种群。一个种群代表了实际问题在这一代的 部分解的集合。 ( 3 ) 种群大小 种群大小是指在种群中个体的数量，表示实际问题在这一代的部分解的个 数。 ( 4 ) 基因( g e n e ) 串中的元素称为基因，主要用于描述个体的特征。 ( 5 ) 基因位置( g e n ep o s i t i o n ) 一个基因在染色体中的位置称为基因位置( 简称基因位) 。 安徽火学预二i j 学位论文 第三章遗传算法 ( 6 ) 基因特征值( g e n ef e a t u r e ) 如果串表示整数，那么基因的特征值就是对应二进制数的权。 ( 7 ) 串结构空问s 5 串结构空间就是基因任意组合所构成的串的集合。 ( 8 ) 参数空间s 9 串空间在物理系统中的映射称为参数空间。 ( 9 ) 适应度( f i t n e s s ) 适应度用于评价某个个体对环境的适应程度。在遗传算法中，每一个体表示 实际问题的一个解，每个解对应某一函数值。这一函数是实际问题的目标函数， 称为适应函数，是用来衡量一个染色体的指标。 3 2 2 遗传算法的基本原理 遗传算法将“优胜劣汰，适者生存”的生物进化原理引入优化参数形成的编 码串联群体中，按所选择的适应度函数并通过遗传中的选择、交叉及变异对个体 进行筛选，使适应度高的个体被保留下来，组成新的群体，新的群体既继承了上 一代的信息，又优于上一代。这样周而复始，群体中个体适应度不断提高，直到 满足一定的条件。遗传算法的算法简单，可并行处理，并能得到全局最优解。 遗传算法的基本操作有选择、交叉和变异三种。 ( 1 ) 选择( s e l e c t ) 从一个旧种群中选择生命力强的个体位串产生新种群的过程称为选择操作。 具有高适应度的位串更有可能保留到下一代。选择操作可以通过随机方法来实 现。 ( 2 ) 交叉( c r o s s o v e r ) 交叉主要模拟生物进化过程中的繁殖现象，通过两个染色体的交换组合，来 产生新的优良品种。 交叉的过程为：首先任选两个染色体，然后随机选择一点或多点交换点位置： 交换双亲染色体交换点右边的数字串，从而可得到两个新的染色体数字串。 交叉体现了自然界中信息交换的思想。交叉有一点交叉、多点交叉、还有一 致交叉、顺序交叉和周期交叉。其中，一点交叉是最基本的方法，应用较广。 安徽火学硕二l 学位论文 人： 鱼群算法柏! 聚类问题中的应用研究 两个染色体x 、y ，以x 、y 为双亲进行交叉操作，产生两个后代x 、y ， 比如：个体x = 1 1 0 0 0 1 0 1 ，y = 0 0 1 0 1 1 1 1 ，选择其左边4 位进行单点交叉操作，则 有后代x 一0 0 1 0 0 1 0 l ，y = 1 1 0 0 1 1 1 1 ；若选择它们的第3 位到第5 位进行双点交 叉操作，则后代x = 1 1 1 0 1 1 1 1 ，y = 0 0 0 0 0 1 1 i 。 ( 3 ) 变异( m u t a t i o n ) 变异运算用来模拟生物在自然的遗传环境中由于各种偶然因素引起的基因 突变，它以很小的概率随机地改变遗传基因的值。在以二进制编码表示染色体的 系统中，它随机地将染色体的某一个基因取反，从而得到新的个体( 染色体) 。 例如有个体x = 1 1 0 0 1 0 1 1 ，对第2 ，第5 位的基因进行变异，则有x 一1 0 0 0 0 0 1 1 。 3 2 3 遗传算法的应用步骤 对于一个实际的优化问题，构造遗传算法可按下述步骤进行： 第1 步：确定出个体的表现型x 和问题的解空间，即确定决策变量及各种约 束条件； 第2 步：确定目标函数的类型及数学描述形式或量化方法，即建立优化模型； 第3 步：确定