（计算机软件与理论专业论文）hopfield网络、遗传算法的数据挖掘中的应用.pdf

山东师范大学硕士学位论文 摘要 近年来，数据挖掘引起了信息产业界的极大关注，主要原因是存在大量数据，可以 广泛使用，并且迫切需要将这些数据转换成有用的信息和知识。获取的信息和知识可以 用于多种领域，包括商务管理、生产控制、市场分析、工程设计和科学探索等。在过去 的3 0 多年中，计算机硬件稳令人吃惊的进步导致了计算机、数据收集设备和存储介质 的飞速发展。这些技术大大推动了数据库和相关信息产业的发展，使得大量数据库和信 息用于事务管理、信息检索和数据分析。为了从海量数据中获取重要信息、作出重大决 策，数据挖掘应运而生。关联规则挖掘作为数据挖掘的一个重要方面，能够发现大量数 据中项集之间的相关联系。随着大量数据的收集和存储，许多业界人士对于从他们的数 据库中挖掘关联规则越来越感兴趣。目前有多种挖掘关联规则的方法，如a p r i o r i 方法 以及由此衍生出来的多种方法，频繁模式增长方法( f r e q u e n t p a t t e r ng r o w t h ) 等等。然而 每种方法都有其自身局限性，人们仍在改进已有的关联规则挖掘方法并不断探索新方 法。 人工神经网络是在现代科学研究成果的基础上提出的模拟人脑结构和机制的一门 新兴科学。它不是人脑真实的全面的描述，而是对这类生物神经网络的抽象、模拟和简 化，其目的在于探索人脑的信息j j u q - 、存储和搜索机制，为人工智能和信息处理等学科 的研究开辟新途径。人工神经网络是采用物理可实现的方法来模拟人脑神经细胞的结构 和功能的系统，它模拟了人类神经元活动的原理，具有自学习、联想、对比、推理和概 括能力，为很好地解决关联规则挖掘这样一个复杂问题提供了新的途径。近来，h o p f i e l d 网络作为神经网络的一种，被尝试用于关联规则挖掘，并取得了一定成果。但是，已有 的直接、机械的将h o p f i e l d 网络用于关联规则挖掘的方法具有缺陷，这些缺陷主要源于 h o p f i e l d 网络自身的不足。 遗传算法于1 9 7 5 年由m i c h g a n 大学的j o h nh o l l a n d 首先提出。它是一种自适应的 搜索策略，因其操作类似于自然界的优胜劣汰机制而得名。遗传算法因其自适应性、领 域知识无关性、并行性等特性，且能较好的处理大规模数据，特别适合于解决多目标优 化问题，因而在诸多领域有广泛的应用。作为一个趋势，遗传算法被越来越多的应用于 训练神经网络，改进神经网络的拓扑结构和权值。实践中，遗传算法进化b p 网络的应 用越来越成熟，并已经取得了丰硕的成果。与之相比，遗传算法和h o p f i e l d 网络的结合 虽然也取得了一些成果，但还有待繁荣。 山东师范大学硕士学位论文 本文致力于h o p f i e l d 网络、遗传算法和关联规则挖掘三者的结合，引入遗传算法局 部进化h o p f i e l d 网络的思想，提出了一种新的基于遗传算法的h o p f i e l d 网络，并将此 h o p f i e l d 网络用于关联规则挖掘。 关键词：h o p f i e l d 网络，能量函数，遗传算法，关联规则挖掘 中图分类号：t p 3 9 1 山东师范大学硕士学位论文 a b s t r a c t r e c e n t l y , d a t am i n i n ga r o u s e st t e m e n d o u sa t t e n t i o n ，f o rt h em a i nr e a s o nt h a ta1 0 to fd a t a c a nb e u s e da n dn e e dt ob et r a n s f o r m e di n t ou s e f u li n f o r m a t i o na n dk n o w l e d g e t h e i n f o r m a t i o na n dk n o w l e d g eo b t a i n e dc a nb e u s e di n m a n yf i e l d s ，i n c l u d i n g b u s i n e s s m a n a g e m e n t ，p r o c e s sc o n t r o l ，m a r k e ta n a l y s i s ，e n g i n e e r i n gd e s i g na n ds c i e n c ee x p l o r a t i o na n d s oo n i nt h ep a s t3 0y e a r s ，s t e a d ya n da m a z i n gp r o g r e s si nc o m p u t e rh a r d w a r eh a si n d u c e d p l e n t i f u ls u p p l yo fp o w e r f u lc o m p u t e r , d a t ac o l l e c t i o nd e v i c ea n da c c e s sm e d i a t e c h n o l o g y g r e a t l yp r o m o t e st h ed e v e l o p m e n to fd a t a b a s ea n di n f o r m a t i o ni n d u s t r y m o r ea n dm o r e d a t a b a s e sa n di n f o r m a t i o na r eu s e dt ot r a n s a c t i o nm a n a g e m e n t ，i n f o r m a t i o ns e a r c ha n dd a t a a n a l y s i s t oo b t a i ni m p o r t a n ti n f o r m a t i o nf r o mh u g ed a t at om a k ed e c i s i o n ，d a t am i n i n g e m e r g e sa st h et i m e sr e q u i r e b e i n ga ni m p o r t a n tb r a n c ho fd a t am i n i n g ，a s s o c i a t i o nr u l e s m i n i n gc a nf i n di n t e r r e l a t i o no fi t e m s a sal o to fd a t aa r ec o l l e c t e da n ds t o r e d ，p e o p l ea r e m o r em a dm o r ei n t e r e s t e di nm i n i n ga s s o c i a t i o nr u l e sf r o mt h e i rd a t a b a s e s t h e r ea r es e v e r a l m e t h o d sf o ra s s o c i a t i o nr u l e sm i n i n g ，a p r i o r ia l g o r i t h ma n ds o m ea l g o r i t h m sd e r i v i n gf r o m i t ，f r e q u e n tp a t t e r ng r o w t hm e t h o da n ds oo n h o w e v e r , e v e r ym e t h o dh a si t so w nf l a w , p e o p l e n o w t r yt oi m p r o v ee x i s t i n g sa n de x p l o r en e wa p p r o a c h e s a r t i f i c i a ln e u r a ln e t w o r ki sa j u m p e d u ps c i e n c es i m u l a t i n gs t r u c t u r ea n dm e c h a n i s mo f h u m a nb e i n g s b r a i n i ti sn o tc o m p r e h e n s i v ed e s c r i ! c i t i o no fo u rb r a i nb u ta b s t r a c ts i m u l a t i o n a n dp r e d i g e s t i o n ，a i m i n gt oe x p l o r et h ew a yo fp r o c e s s ，a c c e s sa n ds e a r c hi n f o r m a t i o nt of i n da n e wa p p r o a c ht od e v e l o pa r t i f i c i a li n t e l l i g e n c ea n do t h e rs c i e n c e s a r t i f i c i a ln e u r a ln e t w o r k s i m u l a t e sp r i n c i p l eo fn e r v ec e l l ，h a sa b i l i t yo fs e l f - s t u d y , a s s o c i a t i o n ，c o n t r a s t ，r a t i o c i n a t i o n a n dr e c a p i t u l a t i o ni t s u p p l i e san e ww a yt os o l v ea s s o c i a t i o nr u l e sm i n i n g ，r e c e n t l y , a so n e k i n do fa r t i f i c i a ln e u r a ln e t w o r k ，h o p f l e l dn e t w o r ki su s e df o ra s s o c i a t i o nr u l e sm i n i n ga n d a c q u i r e s r e m a r k a b l e r e s u l t s h o w e v e r , e x i s t i n gm e t h o d sh a v e s o m ef l a w sf o rc o h e r e n t d i s a d v a n t a g eo f h o p f i e l dn e t w o r k g e n e t i ca l g o r i t h mw a sf i r s tb r o u g h tf o r w a r db yj 0 h nh o l l a n di n1 9 7 5 g e n e t i ca l g o r i t h m i sak i n do fa d a p t i v es e a r c hs t r a t e g y b e c a u s eg e n e t i ca l g o r i t h mi sa d a p t i o n ，p a r a l l e l i s m ，a n d g o o da td e a l i n gw i t hh u g ed a t a ，i ti sw i d e l yu s e di nm a n yf i e l d s t h e r e f o r e ，g e n e t i ca l g o r i t h mi s u s e dt ot r a i na r t i f i c i a ln e u r a ln e t w o r k ，t oi m p r o v et o p o l o g ya n dw e i g h to f n e t w o r k i np r a c t i c e ， 山东师范大学硕士学位论文 a p p l i c a t i o no fg e n e t i ca l g o r i t h mt oe v o l v eb pn e t w o r ki sm o r ea n dm o r em a t u r ea n dg e t sg o o d r e s u l t s i nc o n t r a s t ，t h o u 【g hs o m ea c h i e v e m e n t sa p p e a r , c o m b i n a t i o no fg e n e t i ca n dh o p f i e l d n e t w o r kn e e dt ob ep r o s p e r e d t h i sp a p e rd e d i c a t e st oc o m b i n eh o p f i e l dn e t w o r k ，g e n e t i ca l g o r i t h ma n da s s o c i a t i o nr u l e s m i n i n gt o g e t h e r , i n t r o d u c ean e wi d e at h a tu s eg e n e t i ca l g o r i t h ml o c a l l yt oe v o l v eh o p f i e l d n e t w o r ka n dt h e nr i s et h en e t w o r kt om i n ea s s o c i a t i o nr u l e s k e y w o r d s ：h o p f i e l dn e t w o r k ，e n e r g yf u n c t i o n ，g e n e t i ca l g o r i t h m ，a s s o c i a t i o nr u l e sm i n i n g c l a s s i f i e a t i o n ：t p 3 9 1 独创声明 本人声明所呈交的学位论文是本人在导师指导f 进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，沦文审不包含其 他人已经发表或撰写过的研究成果，也不包含为获得( 注：如 没有其他需要特别声明的，本栏可空) 或其他教育机构的学位或证书使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示i 身十意。 学位论文作者签名：冰饿 ， ，l ， 导师签字c 宁：2 聋艺象； 7j 学位论文版权使用授权书 本学位论文作者完全了解堂蕉有关保留、使用学位沦文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。 本人授权堂撞可以将学位论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在 解密后适用本授权书) 学位论文作者签名：缸聪 导师签字 签字日期：2 0 0 辟年月z 。| 三|签字日期：2 0 06 年c 朗如日 山东师范大学硕士学位论文 1 1 研究背景 1 1 1 关联规则挖掘 第一章绪论 在过去的数十年中，我们生成、收集和存储数据的能力已经大大提高。产生这些变 化的因素包括条码在大部分商业产品中的应用，许多商务、科学和行政事务的计算机化， 以及由文本和图像扫描平台到卫星遥感系统的数据收集工具的进步。此外，作为全球信 息系统的万维网的流行，已经将我们淹没在数据和信息的汪洋大海中。存储数据的爆炸 性增长业已激起对新技术和自动工具的需求，以便帮助我们将海量数据转换成信息和知 识。由此诞生了一门新兴的前沿学科数据挖掘。数据挖掘出现于2 0 世纪8 0 年代后期， 9 0 年代有了突飞猛进的发展，并在新千年继续繁荣。 关联规则展示“属性一值”频繁的一起出现在给定数据集中的条件。发现这些规则 即关联规则挖掘是数据挖掘的三大主要功能( 关联规则挖掘、聚类、分类) 之一。随着 大量数据不停的收集和存储，众多人士对于从他们的数据库中挖掘关联规则越来越感兴 趣。如何有效地挖掘关联规则备受关注。 a g r a w a l 等在1 9 9 3 年提出了a 叫o r i 算法，当前挖掘关联规则的方法主要也都是基 于此算法提出的。a p r i o r i 算法缺点包括：f 1 1 由频繁k 1 项集进行自连接生成的候选频繁 k 项集数量巨大。( 2 ) 在验证候选频繁k 项集的时候需要对整个数据库进行扫描，对于大 规模数据i o 负担非常巨大【“。还有一种重要的挖掘算法f p g r o w t h 算法改进了a p r i o r i 的不足之处，但也存在一些不足：效率低，不利用背景知识，要考察很多不可能频繁的 项目等。针对现有算法的不足之处，本文提出了基于h o p f i e l d 网络的关联规则挖掘算法， 使用h o p f i e l d 网络挖掘关联规则。 1 1 2h o p fi e i d 网络 典型的人工神经网络模型主要分3 大类：以感知机、b p 反向传播模型、函数型网 络为代表的，用于分类、预测和模式识别的前馈式人工神经网络模型；以h o p f i e l d 的离 散模型和连续模型为代表的，分别用于联想记忆和优化计算的反馈式人工神经网络模 山东师范大学硕士学位论文 型；以a r t 模型、k o h o l o n 模型为代表的，用于聚类的自组织映射人工神经网络模型。 1 9 8 2 年，j h o p f i e l d 提出了可用作联想存储器的h o p f i e l d 网络模型。h o p f i e l d 网 络是一种循环神经网络，从输出到输入有反馈连接。h o p f i e l d 网络是近年来人工神经网 络的一个前沿研究领域，应用日趋广泛，在模式识别、图像处理、联想记忆和问题优化 等领域颇有成效。h o p f i e l d 网络由于本身良好的鲁棒性、自组织自适应性、并行处理性、 分布存储和高度容错性等特点，比较适合解决数据挖掘的问题，因此越来越受到人们的 关注。但是h o p f i e l d 网络存在不稳定性，容易陷入局部最优值口”。针对这些缺陷，本 文使用遗传算法进化h o p f i e l d 网络，并将此基于遗传算法的h o p f i e l d 网络应用于关联规 则挖掘。 1 2 本文的主要工作和组织结构 本文综合分析了h o p f i e l d 网络、遗传算法和关联规则挖掘的特性，使用遗传算法训 练h o p f i e l d 网络，提出了一个基于遗传算法的h o p f i e l d 网络，在此基础上，使用该h o p f i e l d 网络挖掘关联规则。具体组织如下： 第一章绪论。介绍了本文的研究背景，主要涉及关联规则挖掘和h o p f i e l d 网络；本 文得主要工作和组织结构。 第二章介绍了h o p f i e l d 网络和遗传算法的基础知识。包括h o p f i e l d 网络的基本结构、 电路模型和动态方程、能量函数和网络稳定性：遗传算法的特点和操作，重点介绍了并 行遗传算法的相关知识。 第三章介绍了现有使用遗传算法进化h o p f i e l d 网络的方法的特点以及局限性。在详 细分析基于全局进化的h o p f i e l d 网络优化算法的基础上，提出了一种新的基于局部进化 的训练方法。并分析了使用局部进化方法得到的h o p f i e l d 网络的能量函数及其稳定性等 性能指标。 第四章介绍了关联规则的基本概念、关联规则挖掘的种类。分析了现有关联规则挖 掘方法的利弊。 第五章使用第三章提出的基于遗传算法的h o p f i e l d 网络进行关联规则的挖掘。主要 内容包括设计了使用h o p f i e l d 网络发现频繁项集的过程，提出了一个新的能量函数，把 挖掘关联规则问题涉及的几个约束映射到此能量函数，并根据此能量函数确定网络的初 始参数。 山东师范大学硕士学位论文 最后总结了本文的主要工作和进一步的研究方向。 山东师范大学硕士学位论文 第二章h o p f i e l d 网络、遗传算法理论基础 2 1 h o p f i e i d 网络 2 1 1 人工神经网络综述 一人工神经网络原理 人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k s ，a n n ) 简称神经网络，是模拟人类大脑 处理信息的模型，是一种与传统模式识别完全不同的分布式并行信息处理系统。 人工神经网络由多个简单的处理单元( 神经元) 按某种方式相互连接而成，依靠其 状态对外部输入的动态响应来处理信息【4 】。每个神经元可以记忆( 存储) 、处理一定的信 息，并与其它神经元并行工作。不同的神经网络模型具有不同的学习规则，学习是基于 一系列训练方法调整神经元的连接权值来实现的。换句话说，神经网络从实例中学习。 好的学习算法会使它不断积累知识，根据不同的问题自动调整一组连接权值，使其具有 良好的自适应性。此外，自学习过程只需要一部分结点参与工作。当某个或某些结点出 现故障时，就让功能相近的其它结点代替故障结点参与学习，使系统不致中断，所以人 工神经有很强的容错能力。 4 图2 1 人工神经元网络模型 山东师范大学硕士学位论文 二人工神经网络的用途 由于人工神经网络自身的结构特点，其具备有别于其他工具的优点，从而具有一系 列不同的用途，这些用途可大致分为以下六种： 1 模式联想。模式联想是与大脑相似地依靠联想学习的分布式记忆。网络存储一 系列的模式，并将已存模式的部分描述或畸变呈现给网络，网络的任务就是回忆存储的 该特定模式。 2 模式识别。模式识别被定义为一个过程，由这个过程将接收的模式或信号确定 为一些指定类中的一个类。 3 函数逼近。考虑由函数关系d = f ( x ) 描述的非线性输入输出映射，其中向量z 是输入，向量d 为输出，向量值函数厂( 町假定为未知。函数逼近的功能是设计一个神经 网络来逼近未知函数。 4 控制。这里控制指的是对设备进行控制操作。所谓“设备”是指一个过程或者 可以在被控状态下维持运转的系统的一个关键部分。 5 滤波。从一个带有噪声的数据集中抽取一定数量的符合要求的信息。 6 波束形成。波束形成是滤波的空间形式，利用它区分目标信号和背景噪声的空 间性质。 2 1 2h o o f i e i d 网络的基本结构 1 9 8 2 年，j h o p f i e l d 提出可用作联想存储器的互连网络h o p f i e l d 网络模型。h o p f i e l d 网络模型是一种循环神经网络，从输出到输入有反馈连接。反馈神经网络由于输出端又 反馈到输入端，所以h o p f i e l d 网络在输入的激励下，状态会不断变化。当有输入之后， 可以求得h o p 矗e l d 网络的输出，这个输出反馈到输入从而产生新的输出，反馈过程一直 进行下去，直至网络达到某种状态。如果h o p f i e l d 网络是一个收敛的稳定网络，则这个 反馈与迭代的计算过程所产生的变化越来越小，一旦了稳定平衡状态，那么h o p f i e l d 网 络就会输出一个稳定的恒值。对于一个h o p f i e l d 网络来说，关键在于确定它在稳定条件 下的权值系数。 h o p f i e l d 最早提出的网络是二值神经网络，神经元的输出只取1 和0 两个值，也称 为离散h o p f i e l d 网络。在离散h o p f i e l d 网络中，采用的神经元是二值神经元，输出的离 山东师范大学硕士学位论文 散值1 和0 分别表示神经元处于激活和抑制状态。 图2 2 所示的是一个由三个神经元组成的离散h o p f i e l d 网络。在图中，第0 层仅仅 是作为网络的输人，它不是实际神经元，所以无计算功能。第一层是实际神经元，执行 对输入信息和权值系数乘积的累加和，并由非线性函数， 处理输出信息。厂是一个 简单的阈值函效，如果神经元的输出大于阂值0 ，那么，神经元的输出为1 ，否则为0 。 图2 2 ：三个神经元组成的h o p f i e l d 网络 图2 , 3 ：简化的h o p f i e l d 网络 对于二值神经元，它的计算公式如下 u j = 巧e + x j 其中：置为外部输入。并且有 第0 层 第1 层 山东师范大学硕士学位论文 誓= 1 ，当u i e 时 r = o ，当q o ，且神经元的转移函数f 为连续单调递增函数，则有警o ，且等号成立的条件为：对一切i 1 , 2 , - - - , n 有 盟堕：o 。 d t 定理表明：若连续h o p f i e l d 网络是对称的，则网络的状态演变总是朝着能量减小的 方向运动，而且网络的稳定平衡点就是能量函数的极小点。 上述定理只是提出了网络稳定性的充分条件，但并非必要条件，而且能量函数也不 是唯一的。 山东师范大学硕士学位论文 2 1 5h o p f i e l d 网络与优化计算 h o p f i e l d 网络有两种主要功能：联想记忆与优化计算，这两种功能是对偶的。当用 于联想记忆时，是通过样本模式的输入确定网络的稳定状态，经过学习求得网络的连接 权值。当用于优化计算时，则是以优化问题的目标函数与约束条件建立网络的连接权值， 网络运行时从初始状态演变到稳定状态，即可得到优化问题的最优解。在实际应用中， 任何一个系统，如果其优化问题可以用能量函数e ( f ) 作为目标函数，那么，总可以用连 续h o p f i e l d 网络对其求解。由于引入能量函数e ( t ) ，h o p f i e l d 使神经网络和问题优化直 接对应，这种工作是开拓性的。利用h o p f i e l d 网络进行优化计算，就是用神经网络这一 动力系统给出初始的估计点，即初始条件，然后随网络的运动传递而找到相应极小点。 这样，大量的优化问题都可以用连续的h o p f i e l d 网络来求解。这也是h o p f i e l d 网络用于 优化计算的根本原因。 2 2 遗传算法的基本思想 遗传算法于1 9 7 5 年由m i c h g a n 大学的j o h nh o l l a n d 首先提出。它是一种自适应的 搜索策略，因其操作类似于自然界的优胜劣汰机制而得名【5 1 。遗传算法因其自适应性、 领域知识无关性、并行性等特性，且能较好的处理大规模数据，特别适合于解决多目标 优化问题，因而在诸多领域有广泛的应用。 遗传算法是从代表问题可能潜在解集的一个种群开始的，一个种群由经过基因编码 的一定数目的个体组成。每个个体实际上是带有特征的实体。由于仿照基因编码的工作 很复杂，所以往往进行简化，如使用二进制编码。初代种群产生之后，按照适者生存和 优胜劣汰的原理，逐代演化产生越来越好的近似解。在每一代，根据问题域中个体的适 应度大小挑选个体，并借助于个体遗传学的遗传算子进行组合交叉和变异，产生出代表 新的解集的种群。 2 2 1 遗传算法的特点 传统优化方法主要有三种：枚举法、启发式算法和搜索算法。遗传算法不同于这些 方法的主要区别在于： 山东师范大学硕士学位论文 i 自组织、自适应和智能性。应用遗传算法求解问题时，在编码方案、适应度函数 及遗传算子确定后，算法将利用进化过程中获得的信息白行搜索。 2 遗传算法的本质并行性。遗传算法按并行方式搜索整个种群内所有的点，而不是 单个点。 3 遗传算法不需要求导或其他辅助知识，而只需要使用影响搜索方向的目标函数和 相应的适应度函数。 4 遗传算法强调概率转换规则，而不是确定的转换规则。 5 遗传算法可以更加直接的应用。 6 遗传算法对给定问题，可以产生许多潜在的解，最终选那个解择可以由使用者自 己确定。 2 2 2 遗传算法的操作 2 2 2 1 遗传个体的表示 遗传个体的表示，即编码问题的关键就是要使编码能够代表所给特征集的所有可能 子集的解空间。编码方法主要有两种： 一二进制编码 假设种群中个体数目为聆，表示第f 代的第f 个个体，i 1 ，2 ， 。每个个体用， 位表示。这样每个个体 1 8 ，1 b o ，1 ) ，个体的基因位数目l = m l 。个体爿可以表 示为，维的行向量，即 t i = “。1 _ i 2 n “一1 m x ；”o 。 第f 代种群墨可以表示为一个n m l 的矩阵五= 爿，# ，r 。个体的第k 个长度为， 的二进制码串转化为实数的解码函数为 州，耻”谱( 豁“吣2 1 ) 其中峨和u 分别为第k 个实数的下限和上限。 二浮点数编码。 山东师范大学硕士学位论文 假定种群中个体数目为n ，表示第f 代的第i 个个体，i 1 ，2 ，n ) 。每个个体的基 因位数l = m ，由m 个实数构成，个体e r ”，可以表示m 维的行向量，即 x ：_ ( ”，i ”，爿1 ) 。这样第f 代的种群置可以表示为一个n x m 的矩阵 置= ( f ，# ，f ) 7 。初始种群矩阵五= ( 矗，端) 7 中没有相同的两行，而且每列中 没有相同的元素，即初始种群中所有个体互异，对任意i j ( i ，_ ， 1 2 ，h ) ) 有吲， 个体中没有两个个体的同一基因位是相同的。 常用的编码方法还有很多。例如，为了提高遗传算法局部搜索能力，提出了格雷码 编码；为了改善遗传算法的计算复杂性，提出了符号编码等等。 2 2 2 2 适应度函数 遗传算法在进化搜索中基本不利用外部信息，仅以适应度函数为依据，利用种群中 每个个体的适应度函数值进行搜索。因此适应度函数的选取至关重要，直接影响到遗传 算法的收敛速度以及能否找到最优解。 常见的适应度函数 适应度函数主要有以下三种： 1 直接以待求解的目标函数转化为适应度函数。 2 若目标函数为最小问题，则 j 可f ( 厂( x ) ) = 器“一，“1姜箍k c “ 若目标函数为最大问题，则 f i t ( f ( x ) ) = 协f 曲1 姜矿n 3 若目标函数为最小问题，则 f j ( ，( 。) ) 2 i i i 而。2 o ，。+ ，( 。) 2o 若目标函数为最大问题，则 肋( 似) ) = i 士而 二适应度函数的设计 山东师范大学硕士学位论文 适应度函数的设计主要满足以下条件 1 单值、连续、非负、最大化 2 合理、一致性 3 计算量小 4 通用性强 2 2 2 3 遗传算子 选择 选择过程的第一步是计算适应度。在被选集中每个个体具有一个选择概率，这个选 择概率取决于种群中个体的适应度及其分布。 常用的选择算法有： 1 轮盘赌选择法( r o u l e t t ew h e e ls e l e c t i o n ) 。该方法中，每个个体的选择概率与其 适应度成比例，其选择概率公式如下： ， 只； 乃 z 一一， j = l 上式中，只为选择概率，i 为染色体序号，z 为个体i 的适应度值，为染色体个数。 显然，概率p 反映了个体i 的适应度在整个群体的个体适应度总和中所占的比例。 个体适应度越大，被选中的概率越高，反之越低。按上式计算出群体中每个个体的选择 概率后，就可以决定哪些个体被选出。但是，这种方法可能引起过早收敛，同时由于该 方法是基于概率的选择，所以存在统计误差。 2 联赛选择法( t o u r n a m e n ts e l e c t i o nm o d e l ) 。联赛选择法的基本思想是每次选取几个 个体中适应度最高的一个个体遗传到下一代群体中。在联赛选择操作中，只有个体适应 度之间的大小比较关系运算，而无个体适应度之间的算术运算，所以它对个体适应度取 值的正负无特别要求。 联赛选择的具体操作过程是： ( 1 ) 从群体中随机选取个个体进行适应度大小的比较，将其中适应度最高的个体 遗传到下一代群体中。 ( 2 ) 上述过程重复m 次，就可得到下一代群体中的m 个个体。 山东师范大学硕士学位诒文 3 最佳个体保存法( e l i t i s tm o d e l ) 。最佳个体保存法的思想是群体中适应度值最高的 个体不进行交叉而直接复制到下一代中，这种选择方法又称复制。其优点是，进化过程 中某一代的最优解可免遭交叉和变异操作的破坏。但是，这也隐含了一种危机，即局部 最优个体的遗传基因会急速增加而使进化可能再次陷入局部解。也就是说，该方法的全 局搜索能力差，更适合单峰性质的搜索空间，而不适合多峰性质的搜索空间，此方法一 般要与其它选择方法结合使用。 4 竞争选择法。以上几种方法都没有顾及染色体群体的特点，这势必造成选择压力 不足或波动，引起遗传的延迟或振荡。在自然界中，当种群中的个体大量繁殖生存时， 为争夺有限的资源，群体中个体之间的竞争压力必然d hj 1 0 ，个体的寿命和出生率也因此 降低。基于这种竞争机制，并结合上述几种选择方法，提出了竞争选择法，即先用适应 度比例法进行选择，经配对交叉后产生下一代，再利用最佳保存法将上一代的最佳个体 复制下来，为了保持群体规模不变，需要从新群体中淘汰1 个个体( 被淘汰的个体与最 佳个体的欧氏距离最短) 。显然，这种方法可以适当地加大竞争压力，较好的体现了自 然界优胜劣汰的规律，并且能够避免适应度高的个体被淘汰。 二交叉 交叉是把两个父个体的部分结构加以替换重组而生成新个体的操作。交叉的目的是 为了能够在下一代种群中产生新的个体。通过交叉操作，遗传算法的搜索能力得以飞速 提高。交叉是遗传算法获取新优良个体的最重要的手段。 在遗传算法中执行交叉操作时，首先定义参数以作为交叉操作的概率，这个概率说 明种群中进行交叉操作的染色体数量的期望值为p 。 由于遗传算法编码主要分为实值编码和二进制编码，交叉操作也分为实值交叉和二 进制交叉。 1 实值交叉 ( 1 ) 离散交叉。离散交叉在个体之问交换变量的值。考虑如下含有三个变量的个体： 父个体11 22 55 父个体2 1 2 343 4 子个体的每个变量可以按等概率随机的挑选父个体，例如交叉之后得到的两个子个体 为： 子个体11 2 345 1 4 些堕燮丝苎 子个体21 24 5 ( 2 ) 中间交叉。子个体的产生按下列公式：子个体= 父个体l + a 。( 父个体1 父个体 2 ) q 这里口是一个比例因子，可由卜d ，1 + 明上均匀分布随机数产生，d 般选择0 2 5o 2 二进制交叉 ( 1 ) 单点交叉。单点交叉中，交叉点七的范围为 i ，n v a 卜1 】，n v a r 是个体数目，在该 点分界相互交换。 ( 2 ) 多点交叉。对于多点交叉，m 个交叉位置丘可无重复随机的选择，相互交换交叉 点之间的变量。 ( 3 ) 均匀交叉。均匀交叉将每个点都作为潜在的交叉点，随机的产生与个体等长的o l 掩码，掩码中的片段表明了哪个父个体向子个体提供变量。 除上述交叉算法外，还有部分匹配交叉、顺序交叉、循环交叉、洗牌交叉、缩小代 理交叉等等。 三变异 变异是子个体的变量以很小的概率或步长发生转变。变异本身是种局部搜索，使 遗传算法具有局部搜索能力。同时保持种群的多样性，防止出现非成熟收敛。 1 实值变异。实值变异采用以下变异算子：x = x o 5 三。上式中；兰掣，a ( i ) 以概率击取值1 ，以l 古取值o ，通常m 取2 0 ，l 为变量的取值范围，x 为变异前的变量 取值，x 为变异后的变量取值。 2 二进制变异a 对于二进制编码的个体，变异意味着变量的翻转。每个个体变量值 2 2 3 遗传算法的一般实现 1 随机生成初始化种群x ( 0 ) = 瓴，乇，) 。 2 计算当前种群x ( f ) 中每一个个体薯的适应度函数r “x ，) 。 3 使用交叉算子产生种群丘( f ) 。 4 使用其他算子对种群进行操作。 山东师范大学硕士学位论文 5 f = f + 1 ，i f n o t ( e n t _ t e s t ) g o t o2 。 2 2 4 并行遗传算法 自从1 9 7 5 年h o l l a n d 系统地提出遗传算法的完整结构和理论以来，众多学者一直致 力于遗传算法的发展，对编码方式、控制参数、选择方式和交叉机理等问题进行了深入 的探究，引入了动态策略和自适应策略以改善遗传算法的性能，提出了各种变形的遗传 算法。其基本途径概括起来有以下几个方面： ( 1 ) 改变遗传算法的组成成分 ( 2 ) 采用混合遗传算法 ( 3 ) 采用动态自适应技术 ( 4 ) 采用非标准的遗传操作算子 ( 5 ) 采用并行遗传算法 这里重点介绍一下并行遗传算法。 一并行遗传算法的分类 遗传算法的自然特性，决定了它很适合并行化晡l 。并行遗传算法主要有三种实现方 案： 1 主从式模型。并行系统分为一个主处理器和若干个从处理器。主处理器监控整个 染色体种群，并基于全局统计执行选择操作。各个从处理器接受来自主处理器的个体进 行重组交叉和变异，产生新一代个体，并计算适应度，再把计算结果传给主处理器。主 从式方法的通信时间往往超过计算时间，以致降低了算法的执行速度，而且这种方法要 求同步机制，容易造成主进程繁忙而子进程空闲或相反情况出现，引起内在不平衡，效 率不高。 2 粗粒度模型。又称孤岛模型，将种群分成若干个子种群并分配给各自对应的处理 器，每个处理器独立计算适应度，进行选择、交叉和变异操作。粗粒度模型对遗传模式 积木块的搜索次数的上限可用指数函数描述，它对系统平台要求不高，特别适合基于 t r a n s p u t e r 的m i m d 系统。 3 细粒度模型。为种群中的每一个体分配一个处理器，每个处理器计算自己所属个 体的适应度，而选择、交叉和变异操作仅在与之相邻的个处理器之间互相传递的个体 中进行。 山东师范大学顾士学位论文 二迁移策略 迁移是并行遗传算法引入的一个新的算子，它是指在进化过程中群体间交换个体的 过程。迁移策略可分为以下两种： 1 一传多。每个处理器对应有若干个相邻处理器，每个处理器产生新个体后都将自 己最好的一个个体传送给其所有相邻的处理器，并且接受来自相邻处理器的最优个体， 将这些个体与自己的个体同时考虑，淘汰适应度差的个体。 2 一传一。每个处理器仅将自己最好的个体传给一个相邻的处理器。 图2 4 所示为独立并行遗传算法示意图，其中左图为一传多，右图为一传一。 山东师范大学硕士学位论文 图2 4 独立并行遗传算法 山东师范大学硕士学位论文 3 1 综述 第三章基于遗传算法的h o p f i e l d 网络 h o p f i e l d 网络是近年来人工神经网络的一个前沿研究领域，应用日趋广泛，在模式 识别、图像处理、联想记忆和问题优化等领域颇有成效。但是h o p f i e l d 网络存在不稳定 性口j ，这主要是由于能量函数在能量下降时可能陷入局部极小值。当h o p f i e l d 网络规模 变大、能量函数变复杂时，这个问题变得尤为严峻。影响能量函数陷入局部极小值的因 素主要有：神经元初值、能量函数的控制参数、神经元的输入输出激活函数。 将h o p f i e l d 网络与遗传算法相结合是提高h o p f i e l d 网络的全局收敛的一个途径。遗 传算法是基于自然进化原理的一种自适应寻优方法，遗传群体中每一个体是搜索空间的 一个可能解，它被编码为基因形式。初始群体通常随机产生，也可根据特定问题的先验 知识确定。每个个体的适应度反映其优劣程度，并决定其进入下一代种群的概率。进化 过程中的基因交叉、基因变异和个体选择使得遗传群体的全局适应度逐渐提高，直至收 敛。因此采用遗传算法进行优化计算时需要决定：编码方法、初始群体产生方法、适应 度函数定义、遗传算子选择、遗传群体规模、交叉变异概率等。 3 2 现有遗传算法训练h o p f i e l d 网络的方法 3 2 1 遗传算法训练h o p f i e l d 网络的局限 有效的确定神经网络的参数和结构一直是人工神经网络研究的一个难点。要想得到 满意的参数和结构往往需要经过反复的试验。传统方法在这方面还存在一些缺陷，如训 练速度慢，网络容易陷入局部极小值以及全局搜索能力弱等 g l 。遗传算法是一种全局并 行的随机搜索方法，有较强的鲁棒性，并有收敛到全局最优的能力，对目标函数既不要 求连续也不要求可微【9 。但遗传算法不适用于解的微调，难以确定它们的精确位置。因 此将两者结合起来，为解决大规模、复杂、并行问题提供了可能。纵观以前学者进行的 研究工作，有的研究成果说明两者结合起来对于复杂问题求解表现出很强的能力。而另 外的研究却证明它们结合的前景并不令人乐观f l0 | 。主要原因有两点，一是遗传算法有可 能出现早期收敛和基因缺失问题，所以不能完全保证缩短训练时间和在全局范围内进行 山东师范大学硕士学位论文 搜索：二是神经网络结构影响它的泛化能力，实验证明小的神经网络通常具有较强的泛 化能力。 较之传统训练方法，使用遗传算法训练神经网络可以在搜索空间内获得更好的搜索 能力以避免陷入局部极小。目前，大多数使用遗传算法训练人工神经网络的方法是针对 网络的权值，少数方法针对网络的拓扑结构【1 1 】，只有很少一部分方法既训练网络权值， 又改进网络结构。 3 2 2 几种基于遗传算法的h o p f i e i d 网络进化方法 提高h o p f i e l d 网络在优化计算时的稳定性的方法，目前主要有4 类旧： 1 选择合适的能量函数简化优化计算的复杂性【1 4 】。但这种方法一般只对特定的 优化问题有效，仅适用于求解小规模的h o p f i e l d 网络优化问题。 2 为h o p f i e l d 网络加入陷阱逃脱