基于语义的web服务动态组合

《基于语义的web服务动态组合》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

学校代号10536学号0810802547分类号TP18密级公开硕士学位论文基于本体的webservices合成方案及应用学位申请人姓名赵海涛培养单位长沙理工大学导师姓名及职称龙鹏飞教授学科专业计算机软件与理论研究方向软件工程论文提交日期2011年4月 学校代号：10536学号：0810802547密级：公开长沙理工大学硕士学位论文基于本体的webservices合成方案及应用学位申请人姓名赵海涛导师姓名及职称龙鹏飞教授培养单位长沙理工大学专业名称计算机软件与理论论文提交日期2011年4月论文答辩日期2011年5月答辩委员会主席施荣华教授 ResearchonClusteringBasedonImmuneGeneticAlgorithmandParticleSwarmOptimizationbySunYangB.E.(ChangshaUniversityofScience&Technology)2007AthesissubmittedinpartialsatisfactionoftheRequirementsforthedegreeofMasterofEngineeringinComputerApplicationTechnologyinChangshaUniversityofScience&TechnologySupervisorProfessorLuoKeMarch,2010 长沙理工大学学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名：日期：年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。本学位论文属于1、保密□，在______年解密后适用本授权书。2、不保密√。（请在以上相应方框内打“√”）作者签名：日期：年月日导师签名：日期：年月日 摘要WebServices定义了应用程序如何在Web上实现互操作性的一套标准，它可以在网络中进行跨平台跨语言的描述、发布、查找以及调用。因此WebServices给应用程序的集成带来了方便，但是单个WebService提供的功能毕竟有限，要想仅仅通过单一的、功能简单的WebServices交互来实现真正跨企业边界的应用集成是显然不够的，因此需要对已有的单个WebServices进行合成，从而形成新的WebServices以提供更多功能。本文的主要研究工作如下：一、提出了一种基于本体的WebServices动态语义合成的建模方法。该建模方法是把WebServices转化为本体的形式，在合成中利用WebServices的语义，从而实现动态语义合成。WebServices的语义分为两部分：输入输出参数语义和功能语义。因此把本体建模分为两个步骤来实现：输入输出参数建模和WebServices功能建模。首先提出WebServices的输入输出参数，将其表示为本体中类的形式，然后把WebServices的功能对应于本体中的属性，因为在本体中属性定义类之间的关系，因此通过属性可以判断产生这种属性的WebServices之间的关系，并且根据这些关系来确定WebServices能否合成。本体是WebServices建模的基础，如何构建本体直接关系到模块的质量。本文利用现在广泛使用的英语词库WordNet来构建本体。这样就可以避免进行重复的无意义的定义概念的工作，另外可以最大限度的消除各个领域间的语义冲突。首先将WordNet中同义词集合对应到本体中的类，然后定义这些类之间的关系来完成本体的构建。二、提出了WebServices最佳路径合成算法。在WebServices的合成中，可能会有几个服务同时满足某一个要求，我们需要选择最合适的一个来合成。这类似于最短路径算法（Dijkstra算法）中遇到的问题，但也有明显的区别。Dijkstra算法智能处理有向无环图中两点之间的单条最短路径问题，而WebServices合成中可能会涉及多条路径同时存在的问题，也就是某个服务需要多个服务的输出才能执行，我们称之为多个服务问题。另外每个输入输出节点的元素个数可能不是唯一的，这样就会产生一系列的问题，我们称之为多个输入问题。因为我们从Dijkstra算法出发，加入对这两个问题的处理形成在WebServices合成领域中的最佳路径合成算法。另外该算法可以根据多种选择策略来选择WebServices，比如价格，执行时间等。实验表明与没有选择策略的合成算法相比，此算法能显著提高WebIV Services的合成质量，并且在某些情况下，响应时间要比没有选择策略的合成算法要好。一、实现了WebServices动态自动合成原型系统。在现有技术Protégé、Tomcat等基础上实现了WebServices动态自动合成原型系统DASO，设计开发了WebServices建模引擎、合成引擎以及执行引擎等组件，并对上面提出的建模方法和合成算法进行了实现。实践证明该系统具有良好的效果。关键词：WebServices，语义建模，本体，最佳路径，合成算法，选择策略，DASO。IV ABSTRACTWiththedevelopmentofinformationscienceandtechnology,peoplehaveinclinedtocollectingandorganizingallkindsofdatabycomputers,thenthesizeofdatahasexpendedaswell.Whenpeoplehaveaccumulatedmassiveamountofbusinessdata,howtofindthevaluableinformationinthevastocean-likedatahavebecomeanurgentneedtobesolved.Forthisdataminingtechniqueshaveemerged，whichisoneofthemostcutting-edgeresearchofthedatabaseandinformationdecision-making.Clusteranalysisasanimportantbranchofdataminingistheanalysisofdata’ssimilarity,anddividedthelargedatasetsintogroups,inwhichthedatainsidethesamegroupwasmostsimilartoeachotherandthedataindifferentgroupswasdifferfromeachother.Clusteringisaneffectivemeansoffindingusefulinformation.Atpresent,Clusteranalysishasbeenwidelyusedinpatternrecognition,dataanalysis,imageprocessing,marketresearchandmanyotherfields.Thereisalargenumberofclusteringalgorithmsintheliterature.Thechoiceofalgorithmdependsonthetypeofdata,thepurposeandapplicationsofclustering.ThispaperdiscussedC-meansclusteringmethodwhichbasedontheimmunegeneticalgorithmandparticleswarmoptimizationalgorithmseparately.Followingisthemainworkhasbeendone:1.Complementedclusteringalgorithmwithimmunegeneticalgorithm.First,analyzedthestrengthsandweaknessesoftheexistinggeneticalgorithm,theimmunemechanismwasintroducedintothestandardgeneticalgorithmtoovercometheprematurephenomenon;Second,theC-meansalgorithmandtheimmunegeneticalgorithmwerecombinedtoformahybridalgorithm;Finally,basedontheactualsituationoftheclusteringproblemdesignedthegeneticselection,crossoverandmutationoperators,madethehybridalgorithmconvergetotheglobaloptimalsolutionmuchfasterandmoreefficiently.2.Clusteringwiththeimprovedparticleswarmalgorithm.First,theadvantagesanddisadvantagesoftheexistingparticleswarmoptimizationwereanalyzed;second,theIV C-meansalgorithmwhichhasstronglocalsearchabilityandthegeneticalgorithm-basedcrossoverandmutationoperationsweremixedintotheparticleswarmalgorithm;finally,themhaveplayedtheiradvantagesrespectivelythroughappropriateregulation.NotonlythePSOalgorithm’sabilityoflocalsearchisimproved,butalsothediversityofthepopulationwasincreased,atlastachievedthepurposeofpreventprematureproblemofthealgorithm.3.SelectedsomedatasetsandtheclusteringexperimentswereimplementedthroughMATLABprogrammingbytheimprovedalgorithms,andresultswerecomparedwithotheralgorithms,andanalyzedtheresultoftheexperiment.Keywords:clusteringalgorithms;Cmeancluster;immunegeneticalgorithm;immunegeneticCmeanclusteralgorithm;particleswarmoptimalalgorithmIV 目录摘要IABSTRACTII第一章绪论1.1研究的背景和意义11.2国内外研究现状21.2.1数据挖掘的研究现状21.2.2聚类的研究现状41.3本文所做的工作41.4本文的内容组织5第二章聚类2.1聚类概述62.1.1聚类的概念62.1.2聚类的步骤62.2聚类的相似度度量72.2.1聚类分析中的数据类型72.2.2样本间距离的计算82.3评价标准92.4常用的聚类算法102.4.1常见的聚类算法间的关系112.4.2几种常用的聚类算法的比较112.4.3聚类算法中的划分方法122.5聚类的应用142.6本章小结15第三章基于人工免疫机制的遗传算法的改进研究3.1基本遗传算法163.1.1遗传算法背景及研究现状163.1.2遗传算法的求解过程173.1.3遗传算法的优点203.1.4遗传算法的不足之处213.2生物免疫系统213.2.1人工免疫系统概述213.2.2生物免疫系统的结构和组成233.2.3免疫细胞24 3.2.4抗原与抗体253.2.5免疫系统机制253.3免疫遗传算法263.4基于免疫遗传算法的模糊C均值聚类算法设计283.4.1模糊C—均值算法简介283.4.2模糊C—均值算法步骤283.4.3算法设计293.4.4仿真实验313.5本章小结32第四章改进的粒子群算法的聚类方法4.1粒子群算法的研究背景334.2粒子群算法原理334.3基本粒子群算法344.3.1算法描述344.3.2参数设定354.4改进的粒子群聚类算法364.4.1粒子群算法的优缺点364.4.2改进的粒子群聚类算法364.5仿真实验384.6本章小结39第五章结论与展望5.1结论405.2展望40参考文献41致谢46附录（攻读硕士学位期间发表录用论文）4752 第一章绪论1.1研究的背景和意义随着互联网技术的进步以及商业企业对互联网以来的增强，软件越来越需要集成到Internet上来，需要和Internet上的其他软件（而不光是人）进行交互。Web服务是基于网络的软件开发模式，通过规范性的设计、发布和发现，以及调用，可以由多个Web服务构建一个完整的企业应用。WebService是一项新技术，能使得运行在不同机器上的不同应用无须借助附加的、专门的第三方软件或硬件，就可以相互交换数据或集成。依据WebService规范实施的应用之间，无论他们所使用的语言、平台或内部协议时什么，都可以相互交换数据。WebService是自描述、自包含的可用网络模块，可以执行具体的业务功能。WebService也很容易部署，因为它们基于一些常规的产业标准以及已有的一些技术，诸如XML和HTTP。WebService减少了应用接口的花费。WebService为整个企业甚至多个组织之间的业务流程的集成提供了一个通用机制。WebServices技术为异构、自治和松散耦合的分布式应用提供了一个集成和交互机制。但是单一的WebService功能毕竟简单、有限，难以满足某些实际应用的需求，因此有必要对现有的单个WebServices进行合成，以生成功能更复杂、更强大的WebServices来支持各种应用需求。随着WebServices应用的不断深入，另一项技术——WebServices合成技术已经得到了业界和学术界的广泛关注。WebServices的合成方法从技术角度大体可以分为静态合成和动态合成两种。静态合成是在开发设计过程中就决定WebServices之间的控制流和数据流如何进行；而动态合成是在系统运行过程中进行的，它们之间的控制流和数据流是自动产生的。采用静态合成还是动态合成可根据WebServices的特点和用户需求决定，如果合成的WebServices之间的内在关系比较固定，则采用静态合成；如果合成的WebServices需要经常根据环境进行动态调整，则采用动态合成技术。现在的WebServices合成技术有两个研究方向：l把重点放在合成的WebServices如何执行上比如SELP-SERV，主要讨论合成后的WebServices如何有效的分布式执行，对WebServices的如何合成则涉及的较少。52 l重点在WebServices的合成如OWL-S。这种技术借助于描述言语来表示WebServices的语义，从而实现合成。但缺点是需要修改现有的WebServices的WSDL描述形式，这对于大量的WebServices来说是不可接受的，另外从WSDL转化到OWL-S与限制了OWL-S的能力。因此，针对上述两种研究的不足，本文将现有的WebServices建模，并且利用本体来表示其语义，从而消除了需要改写的WSDL描述的不足，另外，由于我们能够用本体来表示WebServices的语义，因此我们可以把注意力集中在WebServices的合成上。1.2国内外研究现状针对于WebServices合成这个热门的问题，不少研究单位都提出了自己的解决方法，相关的业界标准也正在扩充和完善中，比如：lWebServices合成的业界标准包括WSFL（IBM），BPML（BPMI），XLANG（Microsoft），BPEL4WS（BEA，IBM，Microsoft），WSCI（BEL，SAP，Sun）等。注意到很多大公司都已经介入WebServices合成及其相关技术的研究标准的提出。但这些标准大多是把注意力放在了合成的WebServices如何执行上。比如BPEL4WS是一种基于工作流的WebServices合成规范，它定义了各个WebServices之间的调用顺序以及如何协作等，而并没有说明如何合成已有的WebServices。l基于工作流的WebServices合成技术，通过定义WebServices的执行流程，并且在流程中详细说明WebServices之间的控制流和数据流来完成合成，比如上述的BPEL4WS。它将WebServices的合成表示成流程图的形式，因此只关注于WebServices的执行，并没有考虑WebServices之间如何合成及这些WebServices的语义。lOWL-S（DAML-S）是从语义Web上发展出来的一种基于语义的WebServices合成技术，它取代WSDL利用OWL-S对WebServices进行规范、精确的语义描述，从而解决了WSDL文件描述不一致、不清晰、不规范的问题。它利用对象间的联系来定义WebServices之间的关系，解决了合成中自动化的问题。但使用OWL-S来描述WebServices，需要对现有的WebServices进行改造，工作量是巨大的，并且从WSDL转化到OWL-S也限制了OWL-S的语义表述能力。52 lSELF-SERV提出了一种基于工作流的WebServices合成方法。它将WebServices组织成服务社区的形式以表述服务的语义。一个服务社区描述了属于这个社区的服务共有的功能和能力，而不考虑服务的具体实现和调用方法。与其他工作流合成方法一样，SELF-SERV关注于合成服务的执行。事实上服务的合成大多由手工来完成。服务提供者在将其提供给服务注册到UDDI时，也要将其服务注册到某个社区以说明服务的功能。因此服务合成严重依赖于服务提供者的工作，这对服务提供者是个负担。lSWORD为WebServices合成提供了一种基于规则的专家系统。它根据输入数参数及其限定条件产生合成方案。输入输出参数是操作实际需要的数据，而限定条件表示输入输出参数所在领域或范围。比如某个操作的限定条件是Person（X），输入参数是firstname（X），则表明操作的实际输入数据是firstname（X），而输入数据所在的领域是Person（X）。SWORD并没有考虑输入输出参数不能完全匹配的情况。比如某个操作的输入数据时firstname（X），而提供的数据是fullname（X）的情况，这种情况下，这个操作也应该能够执行。l针对合成服务的质量，[35]提出了一个质量驱动的WebServices合成模型，主要包括price，duration，reputation，reliability和availability等5个方面的衡量标准，在这些QoS模型的基础上，该文章提出了一个全局服务选择方法，并使用线性编程技术来选择一个最优的WebServices合成方案，但是文章没有给出WebServices合成的方法。1.3本文所做的工作本文主要从以下三个方面来完成基于免疫遗传算法和粒子群算法的聚类研究工作：（1）用免疫遗传算法完成聚类设计首先，分析现有遗传算法的优缺点，在充分学习人工免疫机制的基础上将其引入遗传算法，用来克服了标准遗传算法的早熟现象；其次，将C—均值算法和免疫遗传算法有机结合，形成一种混合算法；最后，根据聚类问题的实际情况设计遗传选择、交叉和变异算子，使得混合算法更快、更有效地收敛到全局最优解。（2）用改进后的粒子群算法完成聚类设计52 首先，分析现有粒子群算法的优缺点；其次，将局部搜索能力强的C-均值算法和基于遗传算法的交叉、变异操作同时结合到粒子群算法中；最后，通过适当调节，发挥各自的优点。既提高了PSO算法的局部搜索能力，又因为加入了交叉、变异操作达到了增加种群的多样性，防止了算法早熟的目的。（3）完成聚类算法的实现在该部分主要是将改进后的算法选择一些数据集用MATLAB编程来实现，并与其他论文中提出的算法结果进行对比，并分析实验结果，评价所做的工作。1.4本文的内容组织本文主要对基于免疫遗传算法和基于粒子群算法的两类聚类算法分别进行了研究，其组成如下：第一章主要介绍了本课题的研究背景及意义，以及数据挖掘和数据挖掘中聚类的国内外研究现状。第二章主要介绍了与聚类相关的一些知识，包括聚类的概念、评价标准、常见的聚类算法，以及这些方法的比较，最后阐述了聚类的作用和意义。第三章首先介绍了遗传算法的概念，包括遗传算法的基本概念、操作步骤等，并分析了遗传算法的优缺点，紧接着介绍了人工免疫系统的概念、结构及应用，最后提出了一种用人工免疫机制改进的遗传算法——免疫遗传算法，用该算法实现聚类，并且用实验证明了算法的可行性。第四章介绍了粒子群算法的基本概念、操作步骤以及研究现状等，提出了一种改进的粒子群算法。最后分析并评价所作的算法结果。第五章主要总结并且客观的评价了本文所作的工作，并且展望了在本文基础可以进行的下一步工作。52 第二章WebServices及其合成概述本章将简要介绍WebServices，主要包括两个部分的内容：首先是WebServices概述，包括其概念和涉及的技术标注，然后介绍了WebServices合成基本知识与相关背景，并指出了这方面所存在的问题和不足，从而进一步明确本文的研究目标和内容。2.1WebServices概述近年来，随着信息技术的发展和互联网的出现，计算机已经在社会生活的各个领域得到了广泛的应用。但随着网络的逐渐普及，网络异构的影响也逐渐显现。由于各类计算机软硬件体系机构、网络协议、具体应用的局限性，目前在互联网上无法有效的进行软件的互操作。因此如何使软件能够进行跨平台、与编程语言无关的互操作成为互联网的一大问题。WebServices的出现解决了这个问题，它是使应用程序可以以与平台和编程语言无关的方式进行相互通信的一项技术。WebServices是一个软件接口，它描述了一组可以在网络上通过标准化的XML消息传递访问的操作。它使用基于XML语言的协议来描述要执行的操作或者要与另一个WebServices交换的数据。一组以这种方式交互的Web服务构成了面向服务的体系结构（Service-OrientedArchitecture，SOA）。WebServices是一项极具发展潜力的重要技术，它作为一套标准，定义了应用程序如何在Web上实现互操作性，是建立可互操作的分布式应用的新平台。本节从两个方面来介绍WebServices：①WebServices概念；②WebServices的技术标准。2.1.1webServices概念Web服务是松散耦合的、可复用的软件模块，从语义上看，它封装了离散的功能，在Internet上发布后能够通过标准的Internet协议在程序中访问。下面对这个定义做一些更加详细的解释，以增强对它的理解。l首先，Web服务是可以复用的软件模块。Web服务是对软件开发中的面向对象设计的发展和升华。基于组件的模型允许开发者复用其他人创建的代码模块，组成和扩展它们形成新的软件。l52 其次，这些软件模块是松散耦合的。传统的应用软件设计模式要求各个单元之间紧密连接，这种连接形成的复杂性要求开发者必须对连接的两端元素有完全的了解和控制能力，而且，这种连接一旦建立后，很难从中把一个元素取出，用另一个元素代替。相反，松散耦合的系统，只需要很简单的协调，并允许更加自由的配置。l第三，从语义上看，Web服务封装了离散的功能。一个Web服务就是一个自包含的“小程序”，完成单个的任务。Web服务的模块使用其他软件可以理解的方式描述输入和输出，其他软件知道它能做什么，如何调用它的功能以及会返回什么样的结果。l第四，Web服务可以在程序中访问。和Web网站或桌面程序不同，Web服务不是为直接于人交互设计的，它们不需要有图像化的用户界面。Web服务是在代码级工作的，它们被其他软件调用，并与其他软件交换数据。不过Web服务最终的目的还是形成一个能够与用户交互的应用软件。l最后，Web服务是在Internet上发布的。Web服务使用现有的并广泛使用的传输协议，比如HTTP。使用与传输Web内容相同的、并广泛使用的协议，不需要调整现有的Internet架构，Web服务就可以通过防火墙进行通信。WebService技术使得应用程序间可以基于标准的因特网协议进行协作，而无须人的直接干预。借此，可将许多业务操作自动化，创建新的功能效率及新的更有效的业务开展方式。WebService范式对基础架构的要求并不高，其目的就是确保在任何平台上使用任何技术和标称语言都可以实现和访问WebService。实际上，WebService的实现方式并不是唯一的，而是代表了几类相关的技术。WebService一个普遍接受的定义基于如图2.1所示的一套具体的补充标准。开发被普遍接受的开放标准是WebService基础架构开发联盟的一个重头戏。同时，如图2.1所示，这些工作也导致了大量的新标准、新术语的诞生。为了简化问题，我们对WebService技术架构的一些重要标准进行了分类，并在下面进行了简要介绍。图2.1l使能技术标准：虽然WebService并没有限定采用任一特定的传输协议，然而WebService使用互联网连接和基础架构进行构建，从而确保几乎无障碍的连接，并能得到广泛的支持。例如，WebService在传输层利用了HTTP协议，也即Web服务器和浏览器所使用的连接协议。WebService的另一个使能技术是可扩展的标记语言（XML）。XML是一个被广泛采用的格式，用于交换数据及相应的语义。对于WebService技术架构中的其他任何层，Web52 Service基本都是用XML作为基础构造块。l核心服务标准：WebService的核心标准包括基本标准SOAP、WSDL和UDDI：简单对象访问协议：SOAP是一个基于XML的简单的消息协议，WebService依靠该协议进行相互间的信息交换。SOAP协议基于HTTP，并使用诸如HTTP这样的常规的因特网传输协议来传送数据。为了进行WebService间的相互通信，SOAP实现了一个请求/响应模型，并使用HTTP来穿透防火墙，将防火墙配置为接受HTTP和FTP服务请求服务描述：当WebService和它的客户之间在完成一些任务时，诸如指定数据和操作、表示WebService契约，或者了解WebService的功能，若使用一些标准的方法则会更为有效。为了实现这一点，首先需要使用WebService描述语言（WSDL）来描述WebService的功能特性。WSDL定义了XML语法，将服务描述为能够交换信息的通信端点的集合。服务发布：使用UDDI可进行WebService的发布。UDDI是一个公开目录，可提供在线服务的发布，并有助于WebService的最终发现。公司可以发布它们所能提供的服务的WSDL规范，其他公司根据这个WSDL描述来访问那些服务。这样，独立的应用程序将能公布应用流程或任务，以便其他远程的应用程序或系统可以使用这些流程或任务。在企业的注册机构中，企业简介中通常提供了这些WSDL规范的连接。2.1.2WebService技术标准为了实现应用程序之间的互操作性，WebServices提供了一套标准的类型系统，以用于沟通不同平台、编程语言和组件模型中的不同类型系统。另外在WebServices平台中也提供了一种标准来描述这些WebServices，使得客户可以得到足够的信息来调用这些WebServices，这种描述语言就是WSDL（WebServicesDescriptionLanguage）；同时还提供了一种方法来对这些WebServices进行远程调用，这种方法实际上是一种远程过程调用协议（RPC），为了达到互操作性，这种RPC协议所使用的数据传输格式必须与平台和编程语言无关，这种数据格式就是基于XML的SOAP（SimpleObjectAccessProtocol）；另外为了使得企业能将自身的WebServices注册并是其它企业能否发现和访问这些Web52 Services，需要一套基于Web的、分布式的注册中心的实现标准和规范，就是通常所说的UDDI。本节将对WSDL和UDDI技术进行简单的介绍。2.1.2.1WSDL介绍WSDL文档的跟元素为，其中包括多个子元素。这些子元素总体上可以分为两类，一类位于文档的前半部分，它们构成了Web服务的“抽象定义”，另一类位于文档的后半部分，它们构成了Web服务的“具体说明”。抽象部分以独立于平台和程序语言的方式来描述Web服务，比如Web方法的参数类型：后一部分指定Web服务的具体内容，比如传输协议。抽象部分包括一下3个元素：lTypes，独立于机器和程序语言的类型定义。lMessages，包含方法参数（输入和输出分开）或消息文档说明。lPortTypes，使用Messages部分的消息定义来描述方法的签名（操作名称、输入参数和输出参数）。具体说明部分包括其他两个元素：lBindings，指定PortTypes部分中每个操作的绑定信息。lServices，指定每个绑定的port地址。抽象定义和具体说明二者之间既具有一定的独立性，又具有很强的关联性。独立性表现在抽象定义不包含任何与机器、平台或程序语言相关的信息，它只是对Web服务最通用的描述，同一个抽象定义部分可以被不同的具体说明使用。关联性表现在具体说明部分必须使用抽象定义中的内容，在指定绑定和地址信息时，所针对的操作都应该是抽象定义部分已经声明过的。即使在抽象定义和具体声明内部，元素之间也有紧密的关系。为了更好地说明两个部分及其元素之间的关系，可以用如图2.2所示的结构图来表示。图2.2WSDL文档的结构图2.1.2.2UDDI介绍为了实现真正意义上的电子商务，需要给这些现有的和潜在的B2B商务角色提供一个完全开放的贸易环境，需要企业能互相发现，也就是使他们互相了解各自的需求和能力，并在各个商业实体使用自身首选地技术、服务与商务流程的前提下，进行应用服务的集成。针对这一需求，一个由技术领域和商业领域的领导者组成的开发小组开发了统一描述、发现与集成（UniversalDescription，DiscoveryandIntegration—UDDI）标准。这是一个彻底的新计划，意图简历一个全球化的、与平台无关的、开放式的架构，使得企业能：⑴发现彼此；⑵定义如何通过Internet交互；⑶使用一个全球性的商务注册中心，以共享信息，并加速全球B2B的电子商务应用。UDDI计划能使得企业使用它们现有的、首选的应用来方便、快速、动态地互相发现并完成彼此间的交易。参与到UDDI计划中来，可以使一个已创建B2B电子商务的商家拓展新的市场与服务，也能使所有刚上网的公司能快速地参与到全球商务环境中来。UDDI与其他一些工业联盟所提出的，并以此为技术核心来实现其核心业务为主要目的的标准不同，它能真正为所有类型的企业、交易市场和技术提供者解决现有的问题。作为这项承诺的体现，发起UDDI计划的公司在Web上发布了一个可操作的UDDI商业注册中心。UDDI商业注册中心是UDDI标准的具体实现，能使所有企业在电子商务的活动中利用它而获得利益。52 通过使用诸如HTTP、XML、SOAP和其他一些规范，UDDI体现了其跨平台和开放性的承诺。这使得任何在UDDI商业注册中心注册过的企业都能得到一个全球为唯一的标识，以标识该商业实体。通过UDDI注册，使得公司能够公开发布自身的描述、服务描述以及服务访问方式等信息。已注册的企业能够被潜在的交易市场或采购商搜索到，同时，对于合作伙伴之间的集成也能更为动态和方便地实施。目前参与到UDDI组织的企业来自很多行业，它们同时也是这些行业的核心力量。UDDI工作原理如图2.3所示。UDDI工作原理图第一步，在软件公司和标准组织定义关于在UDDI中注册的行业或企业的规范时，开始向注册中心发布有用的信息。这些规范叫做技术模型或者更常见的说法是tModel。第二步，公司还会注册关于其业务及其提供的服务的描述。第三步，UDDI注册中心会给每个实体指定一个在程序中唯一的标识符，叫做唯一通用标识符（UniqueUniversalIdentifier，UUID）键，从而能随时了解所有这些实体的情况。UUID键必须是唯一的，并且在一个UDDI注册中心中从来都不会变化。这些键看上去象格式化好的十六进制随机字符串。可以利用这些键来引用与之相关联的实体。在一个注册中心中创建的UUID键只在该注册中心的上下文中有效。第四步，诸如电子交易场所（e-Marketplace）和搜索引擎等其它类型的客户机与商业应用程序（例如，基于工作流聚合起来的Web服务）使用UDDI注册中心来发现它们感兴趣的服务。第五步，另外的企业就可以调用这些服务，简便的进行动态集成。2.2聚类的相似度度量随着聚类技术的发展和应用越来越广泛，人们越来越发现，评价数据对象间的相似性和评价数据集合聚类结果的好坏成为聚类中的关键问题52 。正是根据这两个关键问题，现在出现了各种各样的聚类算法。这一小节主要讨论聚类的相似度的度量方法，2.3节中讨论聚类算法好坏的评价准则，在2.4节中将讨论常用的聚类算法。2.2.1聚类分析中的数据类型在讨论聚类分析相似度的度量方法之前，我们先了解下在聚类分析中通常所选择的数据结构类型。1．数据矩阵（DataMatrix，或称为对象—变量结构）假设有m个数据对象，每个数据对象又有n个属性，那么要表示这m个数据对象的话就可以用一个m×n矩阵来表示，即数据矩阵。这个矩阵的每一列可以表示数据对象的一个属性，而每一行可以表示一个具体的数据对象。例如，人脸识别的数据可以由鼻子、眼睛、耳朵、眉毛、嘴巴等组成。其中表示第i个对象的第j个属性的值。2．相异度矩阵（DissimilarityMatrix，或称为对象—对象结构）假设要计算两个均有n个属性的数据对象之间的相似性，这个问题同样可以用矩阵理论来解决，即用一个n×n的三角矩阵表示其相似性，如下：数据对象和的相似性可以用表示，通常为非负数，其值越小，则表明数据对象和越相似，反之，其值越大，则表明数据对象和越相异。且容易得到：=,=0。相异度矩阵中的具体值通常可以用距离公式计算得到。具体计算方法见下节的介绍。52 2.2.2样本间距离的计算假设有两个数据对象和，它们分别都有n个属性。和可以用数学语言表示为：=｛,…,｝和=｛,…,｝，那么，这两个数据对象间的距离可以用多种方法计算得到，具体选哪种都是随意的，但是现在最常用的距离度量是欧氏距离(即欧几里德距离)和曼哈顿距离。本文也列举出了一些其它的常用度量方法[5]，其具体计算公式如下：（1）曼哈顿距离（r=1，2，3……n）（2.1）其中r表示样本的第r个属性，下面的公式中r具有相同的意思和取值。（2）欧几里得距离（2.2）（3）马氏距离（2.3）其中V-1为样本协方差的逆矩阵，T表示求矩阵的转置。（4）切氏距离（2.4）（5）斜交距离（2.5）在数据标准化处理后，Rri为与之间的相关系数。（6）兰氏距离（2.6）52 2.3评价标准随着聚类分析的应用越来越广泛，在不同领域的人们也对聚类提出了各种各样的要求，因此也就有了各种各样的评价标准。这也使得聚类分析成为数据挖掘技术中一个富有挑战性的研究领域。根据目前存在的各项潜在应用，对聚类的典型要求（即评价准则）主要有以下9个方面[1]：(1)可解释性和可用性首先，所有的工程应用都是为人类服务的，聚类也不例外，它的结果最终还是要面向用户的，因此所有的聚类结果应该是人类可理解和可应用的。(2)能够处理噪声数据现实世界的数据库当中的数据并不是我们想象的那样完整和一致，而是常常包含了一些未知的、空缺的或者错误的数据，这样的数据我们称之为噪声数据。因此一个好的聚类算法应该能够处理噪声数据对它的影响。(3)能够处理不同的数据类型随着聚类分析的应用扩大到各种不同的领域，因此来自不同领域的不同数据对象类型需要被处理，这就对聚类算法提出了一种新的要求。(4)能处理高维数据假设气象局要对一年中的天气情况进行聚类分析，而影响天气的包含许多因素，比如温度、湿度、紫外线强度、风速、可见度等等，这就对聚类算法提出了一种新的要求——处理高维数据的能力。虽然上面的例子可能不是很恰当，但是类似的这样的应用随处可见，因此对于不同应用领域的聚类算法而言，不能只要求其能聚类低维的数据对象，而且要能够处理高维的数据对象。(5)能够发现任意形状的簇正如前面相似度度量一节中介绍的一样，在目前的算法中绝大部分是采用基于欧氏距离和曼哈顿距离的度量方法来进行相似性判断的。这种度量方法的一个明显缺陷就是适合于发现球状簇，而在现实中有些类型可能具有规则的形状，如正方形、椭圆或者球形，而更一般地情况是类型的形状可能是任意的。因此我们需要设计出能够发现任意形状簇的聚类算法。(6)可伸缩性52 假如一个聚类算法对于较小的数据对象集合有较好的聚类效果，而当遇到稍微大点的数据对象集合时要么计算时间变的非常长，要么聚类的结果很不理想，那么我们称这个聚类算法具有不好的伸缩性。因此，伸缩性是指算法的效果不会随着数据对象集合的大小而有太大的浮动，一般来说，如果算法的计算时间随着数据库的大小呈线性变化的话，我们称其具有较好的伸缩性。(7)输入的参数越少越好在许多聚类算法执行之前会要求用户输入一些参数，比如期望聚类能够得到的簇数目或者一些控制参数。毫无疑问，这些参数对聚类结果是有极大影响的，一旦用户输入了错误的参数将会导致不可预料的聚类结果，这也就加重了用户的负担，因此，一个较好的聚类算法应该是具有较少或者没有输入参数。(8)记录的输入顺序与结果无关在有些聚类算法中，如果将同一个数据对象的集合以不同的顺序输入将会得到不同的聚类结果，对于这样的算法我们称之为对输入数据的顺序是敏感的。但是在实际的应用当中，谁也无法保证每次聚类之前的数据都以最好的顺序输入，这也就不能保证得到最好的聚类结果，因此，我们需要设计出对输入数据的顺序没要求的聚类算法。(9)基于约束的聚类在实际应用中，许多聚类是需要在人的指导下进行的，而不同人会有不同的要求，从而就有了不同的约束条件。因此一个好的聚类算法应该能够满足不同的约束条件，并且在这些约束条件下都要有较好的聚类效果。2.4常用的聚类算法随着聚类分析的广泛使用，目前的文献中存在着大量的聚类算法。因为这些方法可能互相重叠，使得一个算法同时具有几种特征，所以很难对它们进行一个明确的划分。不过用现在大家比较认同的一种划分方法[1]可以将聚类算法大致分为：划分的方法(PartitioningMethods)、层次的方法(HierarchicalMethods)、密度的方法(Density-basedMethods)、模型的方法(Model-basedMethods)、网格的方法(Grid-basedMethods)这么五种。本节除了介绍这几种算法之间的关系和对比之外，将重点介绍与本课题相关的基于划分的方法。2.4.1常见的聚类算法间的关系常见的聚类算法之间的关系[6]，可以用下图表示：52 聚类方法划分方法层次方法基于模型方法基于密度方法K中心K均值STING自下而上自下而上DBSCAN统计方法神经网络PAMCLARACLARANSSOMCOBWEBBIRCHCLIQUEWaveClusterDENCLUECURESTING+MOSAIC基于网络DENCLUE图2.2常见聚类算法间的关系2.4.2几种常用的聚类算法的比较基于上述分析，本节主要对传统的常用的聚类算法按照2.3节提到的聚类算法评价标准中的六个方面（算法的效率、对噪声的敏感性、对数据输入顺序的敏感性、发现聚类的形状、高维性和可伸缩性）进行比较[7]，结果如表2.1所示。表2.1常用聚类算法的比较算法的效率对噪声的敏感性对数据输入顺序的敏感性发现聚类的形状高维性可伸缩性C-means较高敏感不太敏感球形好较好CLARANS较低不敏感非常敏感凸形或球形一般好BIRCH高一般不太敏感凸形或球形好较差CURE较高不敏感敏感任意形状好较差DBSCAN一般不敏感敏感任意形状一般较好COBWEB较低一般敏感任意形状好较好52 STING高不敏感不敏感任意形状好好SOM一般敏感敏感任意形状好较好由表2.1可以看出，传统的这些聚类算法中的大多算法都只是在某些方面能够接近或者达到聚类算法的评价标准，却没有哪一种算法在各个方面都表现良好。但是聚类算法的评价标准是针对不同的应用领域提出的，所以我们完全可以根据具体领域的要求选择恰当的聚类算法，而较少的考虑对该领域的应用影响不大的标准，或者我们还可以结合多种聚类算法，使它们互补自己的缺点，来达到我们的要求。另外，通过大量的应用实践表明如果数据对象集合的数据量规模中等或者中等以下，数据分布又比较匀称的话，基于划分的方法就能很好的解决问题。而且划分方法具有通用、容易理解和容易实施的优点。下一小节中我们将重点介绍基于划分的方法。2.4.3聚类算法中的划分方法对于空间中的基于划分的聚类问题可以用具体的数学语言描述为：对于中给定的N个点,,…,,按照相似性将它们分成k个(k事先给定)集合,,…,,且这k各集合满足：(1)≠Φ，i=1,2,…,k；(2)=Φ，i,j=1,2,…,k；i≠j；(3)。基于划分的聚类方法的通俗描述为：对于给定的含有n个数据对象的数据集合，要求将其分为k(k<=n)个小集合，每个小集合就代表着一个簇，这些簇之间满足以下关系：（1）每个小集合至少包含一个数据对象；（2）每个数据对象仅且只能属于一个集合。在该方法中最常用也是最著名的算法是K均值算法和K中心点算法（也称C均值和C中心点算法）,下面对其进行分别介绍。1.K均值算法K均值算法在满足划分方法的基础上，还要将K作为输入参数，52 以确定需要聚类的具体簇数目，然后按照以下的步骤来进行聚类：首先，在待聚类的数据对象集合中随机的选取K个数据对象作为这K个簇的初始化均值或中心。然后根据每个对象与这个K个簇中心的距离，将剩下的每个对象分别指派到相似度最高的簇中，最后计算每个簇的新均值。这个过程不断重复迭代，直到准则函数收敛或者类中心不再变化为止。平方误差准则就是其中的一个较常用的准则函数，具体的定义见(2.7)式。（2.7）(2.7)式中p代表数据对象集合中的具体的数据对象，而是簇的均值（和p都是多维的），E则代表数据对象集合中所有数据对象的平方误差和，这个式子的意思就是，对于簇中每个数据对象，求数据对象到其所在簇中心的距离的平方和。这样便达到了聚类的最初定义——簇中数据尽可能的紧凑（即相似）簇间数据对象尽可能的独立（即相异）。若用具体的算法描述K均值聚类算法，具体的操作步骤如下：(1)任选k个初始簇中心；(2)将数据对象集合中的所有的数据对象按最小距离原则分配给某个簇中心;(3)用公式=,计算新的簇中心(i=1,2,…k)，其中为第i个聚类域包含的数据对象个数；(4)若≠(i=1,2,…k)或者（为任意给定的一个很小的值），转步骤(2)；否则算法收敛，计算结束。1.K中心点算法假设有在一个数据对象集合中的一个数据对象的值与其它所有的数据对象的值相差非常的大（称为离群点或者孤立点），那么K均值算法的结果将很大的会被该点影响，因为K均值算法是以数据对象的均值作为簇中心的，这也是K均值算法的一个致命缺点。如果再使用平方误差函数作为收敛准则那么更是使聚类结果雪上加霜。为了降低K均值算法对初值的敏感性，又提出了K中心点算法——52 用每个簇中的某个实际数据对象来代表该簇的中心而不是用该簇的均值。其余算法操作步骤和K均值算法类似。当然准则函数也需要修改一下，这里我们用绝对误差作为度量准则，其定义见(2.8)式：（2.8）(2.8)式中,p代表簇中的任意的一个数据对象,代表了簇中的簇中心，即代表对象。E则是数据对象集合中所有数据对象与所在簇中心间的绝对误差之和。2.5聚类的应用聚类分析作为数据挖掘的一项功能也可以作为其他算法的预处理步骤，比如分类、特征化以及属性子集选择等。首先将待处理的数据作一次聚类，然后再用后续的算法对检测到的簇、特征或者选择的属性进行进一步的处理。在有的算法中，这样的预处理对后续的计算具有极大的好处。聚类分析还可以作为独立的工具使用。比如首先用聚类分析获得数据的分布情况，接着通过观察每个簇的特征最后可以决定对哪些特定的数据需要做进一步的分析和处理。聚类分析还可以用于离群点检测(outlierdetection)。离群点又称孤立点，是指那些貌似不属于任何一个簇的点。虽然在一般的聚类中总是希望能够去掉这些离群点，因为它们一般都会对聚类效果有影响，但是在实际应用当中，正是这些离群点比其他簇内点可能存在着更高的实用价值。虽然目前离群点检测的主要应用于各种诈骗行为的监控和检测，但是同样也适用与其他领域或学科。比如按照我们以前的认识——所有的哺乳动物都是胎生的，并且开始是用乳汁喂养的，而卵生的动物一定是非哺乳动物——将一些动物进行哺乳动物和非哺乳动物的聚类分析，鸭嘴兽将是一个离群点，因为虽然它是卵生动物，但同时又是哺乳长大的，所以貌似不输于任何一个分类。在这里如果我们把它作为离群点删掉的话我们就得不到这样一个新的认知：有的哺乳动物不是胎生的。目前，聚类分析在实际的生活应用中也是非常的广泛。比如：在生物学中，聚类分析能够根据植物的生长特性及体态特征等信息来推导出其所属科目，从而更容易获得对该物种的本质认识。在商业中，聚类分析能够帮助市场销售人员根据购买信息从产品中发现有销售前途的产品或者发现不同的顾客群体，52 为以后的生产和销售给出指导性的意见。在电子商务上，聚类分析可以帮助店主对浏览相似网页的客户进行聚类，分别分析这些网站和客户的共同特征，从而为店主提高销售业绩和为客户提供更好的服务带来帮助。在Internet应用上，聚类分析可以通过搜集相似内容的文档来对缺少的信息进行修复。我们相信，随着信息技术的高速发展，数据的价值会越来越高，聚类分析作为获取数据价值的有效手段，也会随之发展的越来越好，应用的范围也越来越广。2.6本章小结本章主要介绍了与聚类相关的一些知识，为后续章节的工作做好准备。这些知识包括聚类的基本概念、步骤、聚类分析中的常见数据类型、样本间距离的计算方法、聚类的评价标准、常见的聚类算法，以及这些算法的比较等，最后阐述了聚类的作用和意义。52 第三章本体与webservices遗传算法（GeneticAlgorithm，简称GA）起源于对生物系统所进行的计算机模拟研究。是在20世纪70年代由美国Michigan大学的J.H.Holland教授首次提出的[8]。经过10多年的发展，到90年代已经达到了高潮阶段。因为遗传算法是借鉴生物的进化理论，并且具有简单通用、鲁棒性强的特点，所以其应用范围非常广泛，并且被公认为是21世纪智能计算的重要技术之一。虽然基于遗传算法的聚类方法能够解决模糊C均值对初值敏感性问题，并有更多的机会获得全局最优解[9-15]，但是由于遗传算法内在的缺点，用其解决聚类时仍会出现未成熟收敛现象，不能保证每次运行都得到全局最优解。因此本课题将免疫机制引入遗传算法，有效地克服了标准遗传算法的早熟现象，并将C-均值算法和免疫遗传算法有机结合，形成一种混合算法。根据聚类问题的实际情况设计遗传选择、交叉和变异算子，使得混合算法更快、更有效地收敛到全局最优解。3.1基本遗传算法3.1.1遗传算法背景及研究现状遗传算法是在生物界自然选择、适者生存以及遗传变异机理的启发下提出的一种随机搜索算法，是对达尔文的生物进化理论的计算模拟。虽然遗传算法的最早雏形由Fraser提出，但是最终的具体算法思想却由大家所熟知的美国Michigan大学的J.Holland教授在1975年给出的[8]。遗传算法被提出之后，因为受到了各国学者的广泛关注，所以也不断涌现出有关遗传算法的研究成果。直到近年，遗传算法的发展仍在继续，仍然有许多人员将它应用到越来越广泛的研究领域，例如机器学习、图像处理、神经网络、模式识别、社会科学和工业优化控制等各个方面[16]。尤其在解决旅行商问题、铁路运输计划优化、煤气管道的最优控制以及键盘排列优化等问题上遗传算法都取得了很大成功。随着人们对遗传算法的研究越来越深入，其应用领域也越来越广泛，遗传算法的缺点也逐渐暴露了出来。例如遗传算法容易产生早熟的问题，并且在进化的后期52 其搜索效率会比较低。其中部分原因可能是由于评价函数没有选择好造成的，比如评价函数具有欺骗性或者不能满足模块假说等；而另外一些原因可能是由于算法设计的不恰当造成的。为此，人们针对遗传算法存在的各种缺点提出各种各样的改进策略。范围涉及编码、初始种群的产生、遗传算子设计，以及参数设置等各个方面。例如：在编码方面，针对二进制编码方案提出了实数编码方式；针对定长编码方案提出了动态编码方案[17-18]；在初始种群产生上，针对初始种群的随机生成，提出了小区间生成法[19]；在遗传算子设计上，针对“轮盘赌”的选择算子，提出了连续挑选和竞争选择的改进方法[17]；针对常见的单点交叉算子，提出了多点交叉或者两点交叉以及均匀交叉的各种交叉算子[17]；在参数设置方面，针对各参数在遗传算法中始终不变的情况提出了类似于自学习和自适应的遗传算法[20-21]。此外，有人还提出了多种群遗传算法、遗传粒子群算法和模拟退火遗传算法等各种混合算法来提高遗传算法的搜索效率[22-25]。另外还针对一些特定的问题提出了并行遗传算法和分布式遗传算法等等[26-30]。3.1.2遗传算法的求解过程遗传算法是通过对个体的评估和对个体基因的作用，有效地利用已有信息来指导搜索并改善解的质量。所以遗传算法并不是一种简单的随机搜索比较算法，它自有自己的独特之处。一般来说，标准遗传算法由六个部分组成：编码、初始化最原始种群、计算适应度值并评价个体的优劣、设计遗传算子（包括选择、交叉、变异共三个）、确定运行参数，以及确定终止条件。其具体的执行流程可参照下页的图3.1。（1）编码：在进行遗传操作之前，首先要对待解决的问题进行转换，将其转换成能够用遗传算法操作的染色体（即数据串），而编码就是要完成的这样的转换工作。目前人们已经尝试了多种不同的编码方式，其中最常用的有二进制编码、符号编码和浮点数编码等。这些现存的编码方式都有各自的优缺点，比如二进制编码具有原理清晰，操作简单的优点，但是同时可能会存在码串太长或者数据转换误差的缺点等，因此对于不同的问题应该选择不同的编码方式。（2）初始化最原始种群：在这一步首先需要面临着应该随机产生多少初始个体的问题。当种群规模太小时虽然可以提高算法的运算速度，但同时也降低了群体的多样性，可能会引起算法的早熟现象；而当种群规模太52 大时，又会使得算法的运行效率降低。因此，一般建议视具体的问题选取20到100间的个体数目。假设初始种群为，迭代器t=0；最大进化代数为T。图3.1基本遗传算法框图（1）计算适应度值并评价个体的优劣：个体（即解）的优劣性是通过适应度函数来进行评价的。并且对于不同的问题，显然其定义的适应度函数也会随之不同。所以这一步要完成的工作是：根据具体的问题设计出恰当的适应度函数，并用该函数计算种群中每个个体的适应度值，从而评价每个个体的优劣。（2）选择操作：用选择算子作用于种群中的每个个体。常见的也是最简单的一种选择算子就是基于“轮盘赌”的方法，即根据个体被选择的概率与其适应度成正比，具体操作方法如图3.2所示。AC1/6=17%3/6=50%B2/6=33%fitness(A)=3fitness(B)=1fitness(C)=252 图3.2基于轮盘赌的选择方法（1）交叉操作：用交叉算子作用于种群中的每个个体。常见的交叉方法有基于单点的交叉方法和基于多点的交叉方法，以及一致交叉方法等。下面以两个二进制编码的基因串用图分别演示说明这三种交叉方法。为了便于演示，假设这两个父本基因串一个全是由1组成的，另外一个全是由0组成的。①单点交叉：在两个父本基因串上按照交叉概率随机选取一个点，然后在这个交叉点处分别断开两个父本染色体，紧接着互相交换两个父本染色体的剩余部分，从而生成两个子代。具体做法见图3.3。图3.3单点交叉图3.4多点交叉②多点交叉：类似于单点交叉，不同之处在于交叉点是多个，所以当在各个交叉点断开染色体后，两个父本染色体就交错的交换交叉点之间的基因串，最后形成两个子代。具体做法见图3.4。③一致交叉：随机选取一个父本染色体为“头”，剩下的一个“尾”，第一个子代的每个基因由“抛硬币”确定其相反的拷贝作为第二个子代，具体做法见图3.5。图3.5一致交叉（2）变异操作：用变异算子作用于种群中的每个个体。变异的实质就是用一个被称为变异概率的值来控制新个体的产生，其具体做法就是选择一个恰当的变异概率，然后对染色体上的每个基因值以该概率进行变异，下面仍然以二进制编码的一个全是由1组成的基因的变异进行说明。具体做法见图3.6所示：图3.6变异算子52 （1）经过选择、交叉和变异运算之后，种群从进化到了下一代。（2）终止条件判断：若，则将选择进化过程中产生的具有最大适应度值的个体作为最优解输出，计算结束。否则，，并且转到步骤（2）执行；假设第t代种群用变量表示，初始种群是随机设计的，则简单遗传算法的伪代码描述如下：ProcedureGABegin;initialize;evaluatewhilenotfinisheddobegin;selectfrom;reproducepairsin;evaluate;endend3.1.3遗传算法的优点遗传算法与大多数传统优化算法最显著的不同在于：遗传算法是借鉴生物界的自然选择和适者生存的遗传机制形成的一种随机搜索算法。它是通过一群拥有类似于生物界染色体的个体来模拟自然界生物的进化过程的，从而最终达到寻找最优解的目的。因此它不依赖于传统优化算法所依赖的评估函数的梯度信息。因此遗传算法与其他优化算法相比还具有以下的优点[31]：（1）能够表示各种各样的解结构：包括集合、矩阵、序列、树、图、链、表等各种一维或二维甚至多维的数据结构，这使得遗传算法的可以求解各种复杂的问题。（2）群体搜索特性：因为遗传算法是模拟的生物进化过程，所以它是同时从多个个体的进化过程中挑选最优解，这就相当于搜索算法重的“多点搜索”，使得遗传算法具有较好的全局和局部搜索能力，这也明显优于许多传统的“单点搜索”算法。52 （3）不需要额外的辅助信息：遗传算法中个体好坏的评价仅仅都是通过适应度函数计算得到的适应度值来确定的，并且因为遗传算法不依赖适应度函数的梯度信息，因此在这里适应度函数不仅可以不连续可微，而且可以任意设置定义域。（4）可并行性和可扩展性：因为遗传算法是同时对种群中的多个个体进行处理的，因此其具有较好的可并行性，且容易与其他算法或者技术相融合。3.1.4遗传算法的不足之处凡事都有两面，遗传算法也不例外。虽然它已经拥有很多优点，但还是不可避免的存在着一些自身的缺陷，比如，算法的可信度问题、效率问题、精度问题，以及编码可能存在表示的不准确性问题等。这些不足可能有的是由于具体的应用造成的，而有一些问题是由于遗传算法内在的原因造成的，对于这种应用上的问题容易被解决，而对于遗传算法自身的缺陷是不容易克服的，比如遗传算法容易出现早熟收敛的现象就是一个明显的例子。遗传算法是一种基于多点的启发式随机搜索的算法，与传统的算法相比，虽然具有很多优点，但是，在具体的实施应用当中遗传算法往往会面临一些自相矛盾的问题：比如算法在迭代的后期，种群中适应值大的个体在数量上占据了绝对优势，使得大部分个体几乎趋于一致，失去了种群的多样性，因此容易出现早熟现象，从而陷入局部最优解；虽然这点可以通过加大交叉率和变异率来增加种群的多样性，但是过大的交叉率和变异率又将降低在最优解附近的搜索效率，甚至错过最优解。鉴于遗传算法存在以上缺陷，有人将基于生物原理的免疫系统[29]引入到了遗传算法中，形成一种免疫遗传算法。生物的免疫系统是一个高度进化并且极其复杂的系统，它通过自适应地识别和排除侵入机体的病毒，来维护机体内环境的稳定。人们将生物学上的免疫系统的机理结合到遗传算法中，所形成的免疫遗传算法在各个工程领域进行了崭新的研究。有关该算法的具体介绍在本章的后续几节中。3.2生物免疫系统3.2.1人工免疫系统概述免疫是指机体对感染具有抵抗能力，而能够不患疫病或传染病。人工免疫系统(ArtificialImmuneSystem,简称AIS)是由免疫器官、免疫组织、52 免疫活性分子和免疫细胞组成的复杂系统。免疫系统具有识别机制，能够将外界的入侵病毒等病原体与生物的自体分子或者细胞相区分开来，然后采取一定的措施将它们消除，而且免疫系统具有“记忆”每一种感染源的能力，以防止同一种感染源的再次入侵。免疫学是研究免疫系统的功能与结构，研究免疫系统识别并消除有害生物及其成分的应答过程及机制，理解其对机体有益的防卫功能和有害的病理作用及其机制的医学科学[33]。首先将免疫学引入实际工程应用的是由美国免疫学家、诺贝尔奖获得者、医学家、生物学家Jerne，他是在1974年提出了免疫网络理论。之后，在20世纪80年后期到90年代初期，Perelson、Farmer、Varela、Bemini等免疫理论学者纷纷发表了将免疫系统用于实际工程应用方面的论文，为该理论奠定坚实的基础。在90年代初期将人工免疫系统应用到实际工程当中的还有日本学者Ishida、美国学者Bemisi和Forrest，他们分别利用人工免疫系统解决故障诊断问题、自适应的问题以及计算机安全和病毒检测的问题。随着人工免疫系统的应用越来越广泛，越来越多的人开始注意到早期的免疫学家在20世纪80年后期到90年代初期所做工作的重要性[34]。关于人工免疫系统的新技术、新方法也不断涌现。目前，入侵检测、故障诊断、阀值优化、路由选择、模式识别以及数据聚类等许多不同领域的工程问题都用人工免疫方法解决了其中的一些问题。随着人工免疫系统应用的发展，也出现了许多对其改进的算法以及与其他算法相融合的混合算法。国外对人工免疫的研究成果颇多：例如文献[35]~[37]分别提出了与遗传算法相结合形成的免疫遗传算法，基于信息熵的免疫算法，以及免疫agent算法等。此外，识别和检测二维动态物体的问题在文献[38]中用基于人工免疫系统的三维模式识别系统所解决。故障诊断的问题在文献[39]中用免疫系统的三种模式(B、T、D)所解决。人工免疫网络的自适应性、多样性、分布性、动态性和鲁棒性被DasguPta应用到计算机网络的安全领域，并结合否定选择算法进行计算机网络的入侵检测。还有模式识别[40，41]、机器人[42]、负荷预测[43]以及数据分析[44]等工程领域也用人工免疫系统解决了一定的问题。国内人工免疫系统的应用相对国外的来说应用范围还没有那么广泛，目前主要还集中在网络安全、故障诊断和控制器设计等方面，网络安全方面的应用与其他领域相比还算较多，代表性的参考文献有文献[45]~[47]。数据挖掘领域的问题用人工免疫系统解决的还相对较少，目前还主要集中在聚类、分类和数据浓缩等方面的数据挖掘任务中。例如一种新型的自适应人工免疫网络算法由华南理工大学的李春华等提出来，用于解决离散型数据的聚类分析。此外，52 将人工免疫算法与其他进化算法(如遗传算法)相结合是提高算法执行效率的一种非常有效手段。3.2.2生物免疫系统的结构和组成1.生物免疫系统的结构免疫系统的结构大致如图3.7所示，它是由分布在各个层次的防御系统组成的多层次结构。图3.7生物免疫系统的体系结构[33](1)物理屏障：也就是起到物理层面的防护作用。包括皮肤、指甲等组织。(2)生理屏障：是指人体的一定腺体分泌出来的诸如汗液、唾液、眼泪、鼻涕等之类的体液，这些体液中要么含有丰富的生物酶，要么含有抑菌或杀菌的化学物质，它们起到破坏和分化微生物的作用，而胃酸是因为PH酸度所以能够杀死多数消化道中的微生物，体温也在一定程度上阻碍了入侵微生物的生存。(3)免疫系统：分为自适应免疫系统和固有免疫系统两种，两者均由噬食细胞、淋巴细胞和细胞因子等组成，这些细胞能够有效地识别入侵的微生物，并采取相应的措施将其清除。2.生物免疫系统的组成生物免疫系统中最重要的就是补体系统和淋巴系统，它们均由免疫器官、免疫组织和免疫细胞组成。下面主要介绍免疫系统中的这两大系统。(1)淋巴系统淋巴细胞和淋巴组织组成了分布在人体各处的免疫系统的组织和器官，使得人体各处都具有免疫防卫功能。按照功能可以将淋巴器官分为：外周淋巴器官和中枢淋巴器官。外周淋巴器官主要是指52 组成淋巴循环的细胞、组织和器官，比如脾、扁桃体、淋巴结等。它们担负着机体的保卫功能，而中枢淋巴器官主要是由骨髓和胸腺组成，主要完成生产免疫细胞的任务，大家都熟知的多功能造血干细胞就是在这类器官中产生的。(2)补体系统补体系统是一个蛋白质组成的复杂联合体，这个联合体是由一组能够互补抗体功能的调节浆细胞组成。补体是一组经活化后具有酶活性的蛋白质，而不是单一的分子，它们主要存在于人和脊椎动物的组织液和血清中。补体在免疫系统中主要起免疫粘附、溶菌和杀菌、调理、炎症介质以及中和及溶解病毒等作用。3.2.3免疫细胞单核吞噬细胞、造血的干细胞和淋巴细胞系组成了人体的免疫细胞，它们随着血液和淋巴液在人体中不断的循环以完成时刻的防卫工作。免疫系统所产生的免疫细胞和分泌物的结构划分如图3.8所示。在这里我们主要介绍免疫系统中起关键作用的淋巴细胞系。图3.8免疫系统产生的细胞和分泌物的结构划分[33]从上图可用看到，由B细胞和T细胞以及自然杀伤细胞三种细胞组成了淋巴细胞系。其中B细胞主要具有提呈抗原、产生抗体和分泌细胞因子参与免疫调节三个功能；T细胞一般具有活化期和静止期两种状态，按其功能来分又可将T细胞分为调节T细胞和毒性T细胞两类，调节T细胞又可以分为抑制性T细胞和辅助性T细胞。辅助性T细胞的作用是就是激活B细胞而毒性T细胞是清除微生物的入侵者、病毒或癌细胞。虽然只有B细胞才能产生抗体，但是B细胞发挥作用必须要有一定的条件：首先必须要B细胞识别到了抗原并且与抗原的匹配程度超过一定的阈值；其次，还要有T细胞的刺激。只有这两个条件都达到了B细胞才有可能分化成为浆细胞，制造大量的抗体，否则缺任何一个条件B细胞都会凋亡。52 3.2.4抗原与抗体1.抗原通俗的讲，抗原就是入侵到生物体内的微生物的入侵者、病毒或癌细胞等，但这些入侵者都有一个共同点，那就是它们都能够使得免疫系统做出反映（免疫学上称为免疫应答），并能与免疫系统所产生的抗体或效应细胞发生反应。这里还有个抗原决定基的概念，它是指抗原表面能被抗体识别的部分。根据现代免疫学中抗原的概念，抗原必须具备免疫原性和抗原性这两种特性。2.抗体通俗的讲，抗体就是免疫系统为了保卫人的机体不受到外部入侵者的伤害所产生的一些对付抗原的物质。从前面小节中关于免疫细胞的介绍中我们可以知道，这些物质是由B细胞产生的。3.亲和力亲和力的实质就是抗体和抗原之间的匹配程度。这种匹配程度越高，亲和力也就越大，匹配程度越低，亲和力就越小。引入亲和力的概念是为了说明免疫系统会针对不同的抗原选择与其亲和力高的抗体来进行处理。3.2.5免疫系统机制在免疫系统中存在的主要机制有：克隆选择与克隆扩增机制、免疫应答与抗原记忆机制、阴性选择与自体耐受机制、以及抗体的多样性等。这里主要讲其中的两个——免疫系统中抗体的多样性机制和克隆选择与克隆扩增机制。1.生物免疫系统中抗体的多样性生物体能够随机生成新抗体并且伴有体细胞的高频变异和基因重组发生，这使得免疫系统中的抗体保持高度的多样性。基因重组(也称受体编辑)：基因重组的任务主要是由B细胞来完成的。当B细胞进入克隆选择与克隆扩增阶段后，它的抗原受体上的基因将发生重组，即受体编辑。这个过程类似与遗传算法中介绍的个体交叉过程，只是比那个过程更为复杂些。因此在这个过程中是极易产生新抗体的。体细胞的高频变异：与基因重组类似，体细胞的高频变异还是由在克隆选择与克隆扩增阶段的B细胞来完成的[48-50]，因为52 在此阶段的B细胞具有极高的变异概率，这就有可能产生新的具有更高抗原亲和力的抗体。这个过程又与遗传算法中的变异操作很类似。体细胞的高频变异在保持生物免疫系统的多样性中起着非常重要的作用。从上面的介绍中我们可以推出：在解决优化问题的过程中，生物免疫系统中的受体编辑和体细胞的高频变异的作用分别与遗传算法中的交叉、变异算子的作用相类似，即体细胞的高频变异使得算法具有在局部区域内进行良好搜索的能力，而受体编辑可以使算法避免在亲和力域内过度的进行局部搜索，这点也被最近的研究成果所证明[51]。随机生成新抗体：根据最近的研究成果表明，一般情况下自然界拥有大概种不同的外部蛋白质或模式（即抗原决定基），而生物的免疫系统只能同时存在种不同的蛋白质。虽然体细胞的高频变异和受体编辑能够使免疫系统在一定程度上保持多样性，但是按照这个数目对比，免疫系统中的抗体显然还是远远不够去结合每一种可能的抗原决定基的。因此，免疫系统中生产抗体的器官——骨髓，会每天随机产生大量的新抗体，去替代没用的或者老化的抗体，以应对那些可能从未碰到过病原体。2.克隆选择与克隆扩增克隆选择：即当生物体受到某种外部入侵者的伤害并需要大量某种抗体时，免疫系统就会选择与该抗原具有最高亲和力的抗体，对其进行克隆扩增。这个选择高亲和力抗体的过程就被称为克隆选择。可见，免疫系统之所以能够这么有效的保护机体的关键原因在于其对抗体分子时刻保持着高度的多样性，使得绝大部分的外部入侵生物都能够被识别并消除。克隆扩增：即将克隆选择的抗体进行大量复制的过程。因为这些抗体是被复制的，所以它们与入侵的抗原都具有相同的亲和力，因此也只有它们才能最快的将病原体消除。我们在医院检查身体时，正是利用了这点，即通过检查体内是否存在大量的某种抗体来判断是否得了某种疾病，。3.3免疫遗传算法免疫遗传算法（ImmuneGeneticAlgorithm简称IGA）是基于生物免疫机制提出的一种改进的遗传算法，一般由抗原的识别、初始抗体产生、适应度计算、记忆细胞分化、抗体的促进和抑制以及抗体产生共六个模块组成。此外，我们称免疫遗传算法中的个体为抗体。模块1：其主要功能是抗原识别，即判断这里出现的抗原是不是在记忆库中有记录52 的抗原。这里的“抗原”相当于GA中待解决的问题。模块2：其主要功能是产生初始种群。如果在第一步中判断出抗原是以前没有出现过的，记忆库中不存在的新抗原，则随机产生初始种群，否则，初始群体由从记忆细胞中取出的相应抗体组成。模块3：其主要功能是计算适应度。用具体的目标函数计算每个个体(相当于这里的抗体)的适应度值。模块4：其主要功能是分化记忆细胞，如果在第一步中判断出抗原是以前没有出现过的新抗原，则将当前群体中适应度最高的个体加入记忆库中，否则，用当前群体中适应度高的抗体替换掉记忆库中的适应度低的抗体。模块5：其主要功能是促进或者抑制抗体，根据当前群体中个体浓度(即用种群中适应度值相近的个体数目比种群中个体的总数目所得到的百分比)，来决定是增加还是减少个体被选择的概率，如果浓度低则增加，即促进，反之则减少，即抑制。模块6：其主要功能是产生抗体，即用交叉、变异算子作用于种群。由以上六个模块构成了免疫遗传算法，具体流程图如下所示。图3.9免疫遗传算法流程图52 3.4基于免疫遗传算法的模糊C均值聚类算法设计3.4.1模糊C—均值算法简介在传统的分类或聚类算法中每个对象被严格地划分到某个类中，因为每个对象具有非此即彼的特性，所以在这种聚类分析中的类的界限是明显的，因此大家形象的将这种分类或聚类方法被称为“硬划分”方法。但是在现实生活中，任何事物都是有着千丝万缕的联系，不可能完全孤立，因此也就与其他对象不可能有那么明确的划分界限，所以更适合用“软划分”来对现实中的事物进行聚类。模糊C均值算法(FCM，Fuzzy-means)就是相对与传统的聚类算法来说的，它是由硬C均值算法发展而来。模糊集理论的提出给软划分提供了强有力的理论支持，人们开始用模糊的概念处理聚类和分类的问题了。首先由Ruspini[52]提出最早的模糊划分的概念，接着由Dulm给出了真正有效的FCM算法，最终由Bezdeklls[53]在前人工作的基础上建立起了模糊聚类理论，即用模糊的方法来处理聚类问题。随后人们利用这一理论，提出了许多模糊聚类方法，其中比较有代表性的有:基于模糊等价关系的传递闭包方法，基于相似性关系和模糊关系的方法(包括凝聚法和分裂法)，基于数据集的凸分解方法，难以辨识关系和动态规划方法，以及基于模糊图论最大树方法等。但是由于这些方法对处理的数据量有限制所以后来的研究和应用就逐渐减少了。目前比较受欢迎的是基于目标函数的方法，因为该方法设计简单应用范围又不受限制，并且能够借助数学方法进行求解，因此该方法逐渐已经成为聚类分析研究的焦点和主流[54]。作为现在相当流行和应用广泛的模糊C均值(FCM)聚类算法，由于该算法是从硬C均值(HCM，Hard-means)聚类算法发展而来，因此也具有C均值算法的特点：算法设计简单、收敛速度快且局部搜索能力强，但它对初始条件较为敏感，对不同的初始值有不同的聚类结果，并且由于该算法是基于梯度下降的算法，因此，常常不可避免地使目标函数陷入局部极值，甚至会出现退化解和无解的情况。由此，本文提出了一种基于免疫遗传算法的FCM算法和基于改进的粒子群算法的聚类方法，用来改进该算法的不足。3.4.2模糊C—均值算法步骤FCM算法是把n个数据xi(i=1，2，…，n)分成c个模糊族，并求得每个族的类中心，使目标函数达到最小。FCM算法目标函数为：52 (3.1)这里=1，。其中：X={…,}为数据集，m为模糊加权指数，且，c为聚类的类别数，且cU={}表示隶属度矩阵，是第j类中的样本xi的隶属度，V={}表示类中心矩阵。为使目标函数达到最小，类中心和隶属度的更新如下：(3.2)其中，j=1,2,…,c。(3.3)当=0时，则=1,=0,k≠j,i=1,2,…,n。算法具体描述如下：Step1:设定模糊指数b，任选c个初始聚类中心；Step2:用公式(3.2)计算样本集中每个样本对各聚类中心的隶属度；Step3:按照最大隶属度原则将各个样本分配给c个聚类中心的某个；Step4:用(3.2)式计算新聚类中心(i=1,2,…c)；Step5:按照(3.1)式计算，若（为给定的一个很小的值）或者≠(i=1,2,…c)，转步骤(2)；否则算法收敛，计算结束。3.4.3算法设计（1）编码和适应度函数算法中的个体采用基于聚类中心的浮点数编码方式，每个抗体S由c个聚类中心组成，它可表示为长度为c×l的浮点码串。个体的适应度函数可定义为：52 (3.4)其中:也就是式（3.1）中的。（2）基于免疫原理的选择操作抗体浓度的定义：=(3.5)抗体的适应度概率的定义：(3.6)抗体的选择概率：p=(3.7)其中>0是常数。这种选择策略的优点：抗体被选择的概率不仅依赖于抗体适应度的大小，还要依赖于个体在种群中的规模，这样充分体现了免疫系统的特性，保证了种群的多样性。（3）交叉和变异在本课题中采用一致交叉的方法，即在两个配对抗体的每个基因座上的基因都以相同的交叉概率进行交换，从而形成两个新的个体。变异采用均匀变异的方法，即分别用符合某一范围内均匀分布的随机数，以某一较小的变异概率来替换个体编码串中各个基因座上的原有基因值。算法流程如下：Step1：初始种群产生初始化，确定较小正常数（）、交叉概率、变异概率以及每代中C-值算法的迭代次数L。置遗传代数t=1，随即生成n个抗体，形成初始种群P；Step2：适应度计算用公式（3.2）、（3.3）对种群中的每个抗体迭代L次，然后得到新种群P1，对P1中的每个抗体分别运用公式（3.1）和（3.4）计算和f值。Step3：终止条件判断52 计算，若，指定最好的个体为算法的结果，否则转Step4；Step4：记忆细胞分化将种群P1按f值降序排列，选取适应度最大的N个构成抗体子集M（即选择记忆细胞，其规模是抗体总数的20%），当新的记忆细胞产生时抗体子集是满的时，就用高亲和力的抗体代替低亲和力的抗体；Step5：抗体的促进或抑制分别运用公式（3.5）、（3.6）、（3.7）计算、和p，并以p为选择概率复制（M+P1）中的抗体，最后得到种群P2；Step6：抗体产生以交叉概率为的一致交叉法和变异概率为的均匀变异法作用于种群P2得到种群P3，置t=t+1，转Step2。3.4.4仿真实验采用C-均值算法、GA算法、KGA算法和本文算法分别进行仿真计算。遗传算法的交叉概率取为0.70，变异概率取为0.008，群体规模为100，L=5，q=1，α=0.8，ε=10-4。实验采用文献[15]中的数据，共有两个数据集：第一个是著名的Iris数据集，这个数据集是通过测3种植物花的四个不同部位所得的150个4维向量的数据所组成，用上述4种算法分别做了3次实验，每次实验迭代50次，结果见表3.1。表3.1Iris数据实验结果次数C—均值算法GAKGA本文算法197.08707397.00010397.00010397.000103297.11854797.00010397.00010397.000103397.08707197.00010397.00010397.000103第二个实验数据是300个随机分布的4维随机向量，聚类数目是8，这个数据集合的规模不仅大于Iris数据，而且因为数据是完全是随机分布的，所以没有明显的类别分界线，且存在大量的局部极优点，因此是个很困难的优化问题。采用4种方法分别做3次实验，每次实验迭代100次，结果见表3.2。52 表3.2随机分布数据实验结果次数C—均值算法GAKGA本文算法1101.455101.343101.572101.2782101.572101.298101.507101.2783101.818101.309101.583101.278从表3.1和表3.2中，不难看出本文所给出的混合算法的局部收敛速度和全局收敛速度都优于GA和KGA算法。特别是对大规模、完全随机分布的数据聚类问题，其优越性更加明显。3.5本章小结本章首先介绍了遗传算法的研究现状和背景意义，紧接着介绍了遗传算法的基本概念、求解过程、应用步骤等，并分析了现有遗传算法的优缺点以及常用的改进策略。其次，介绍了人工免疫系统的相关的概念，包括人工免疫系统的结构和组成，人工免疫系统中的免疫细胞，抗体和抗原，以及最重要的克隆选择和克隆扩张原理，最后，提出了一种用人工免疫机制改进的遗传算法——免疫遗传算法，用该算法实现聚类，并且分析算法的实验结果。52 第四章基于本体的webservices合成建模4.1粒子群算法的研究背景粒子群优化算法(ParticleSwarmOptimization，PSO)是由Kennedy和Eberhart在1995年提出的，该算法是在鸟群、鱼群和人类社会行为规律的启发下提出的一种基于群智能的演化计算技术[55]。近年来演化计算和优化等领域的学者们都广泛注意到了粒子群算法的易实现、快收敛速度和较少设置和调整参数等优点。目前，在函数优化、模式分类、神经网络训练、模糊系统控制以及其它工程领域粒子群算法都得到了广泛的应用。并且在动态目标寻优、多维空间函数寻优等方面，根据近几年的研究和实践，粒子群算法有着收敛速度快、解质量高和鲁棒性好等优点，因此尤其适合于工程应用[56]。但是PSO算法也有缺点，其最主要的问题是容易产生早熟收敛、局部寻优能力差等[57]。针对这一点，近年来也出现了一些改进的PSO算法，如文献[58]~[62]提出的模糊PSO算法、智能PSO算法、小生境PSO算法、混合PSO算法以及保证局部收敛的GCPSO算法等。纵观各种与PSO算法相关的混合算法，大多数基本上采用一种策略对其改进，要么与其他算法结合，要么加入变异操作，同时采用两种策略的混合算法较少[57]。PSO算法的研究尚还处在初期阶段，相对来说是一种较新的基于群智能的进化计算技术，它的理论基础研究还比较贫乏，远未像遗传算法那样形成系统的分析方法和坚实的数学基础。比如算法的收敛性问题，如何在解空间内提高算法的搜索效率问题，以及在理论上深入的研究算法模型本身的问题等。此外，PSO算法中参数的选择依赖于具体的问题，一般情况下，要想设计出合适的参数需要多次的经验进行选择。研究如何选择和设计参数，使其减少对具体问题的依赖，也将大大促进PSO算法的发展和应用。4.2粒子群算法原理虽然粒子群算法最初是在鸟群和鱼群寻找食物的基础上提出来的，但同样适合于大多数生物的活动习惯，比如像这样的情景就很多见：在一个区域内有一只野兔子，一群狼都在四处寻找它，开始所有的狼都不知道这只兔子在哪里，但当有一只狼发现了那只兔子之后，它就开始估算自己与兔子之间的距离然后根据自身的条件调整奔跑速度。其他狼要想找到兔子的最简单方法就是跟着那只找到兔子的狼，通过52 估算自己与那只狼之间的距离来估算自己与兔子之间的距离，然后再调整自己的位置和速度。在这个过程中有可能出现开始发现兔子的狼后来把兔子跟丢了，但是后来又被其他的狼发现的情况，所以只有整个狼群的合作才能以最快的速度抓到那只兔子。粒子群算法就从生物种群的这种行为特性中得到启发并用于求解优化问题的[63]。若我们把一个优化问题看作是一群饥饿的“狼”，优化问题的最优解看作“兔子”，那么在粒子群算法中，“狼”就是在解空间中进行搜索的“粒子”。这里的“粒子(Particle)”是没有质量和体积，只有调整本身状态的速度和加速度的一个折衷概念。而“群(Swarm)”是来自于人工生命的概念[64,65]。因此粒子群算法也可被看作是对简化了的人类社会或者动物群体活动的计算机模拟，信息共享机制是推动算法运行的主要机制，也是算法中最重要的部分。在搜索空间中每个粒子都以一定的速度移动，并且这个速度是用同伴的移动经验和自己的移动经验来动态调整的。粒子的“好坏”程度是通过目标函数计算得到的适应值(fitnessvalue)来评价的。每个粒子不仅知道自己的当前位置和到目前为止自己所发现的最好位置pbest(particlebest)，而且还知道到目前为止整个群体所发现的最好位置gbest(globalbest)。如果pbest可以看作是粒子本身的移动经验，也就是每个粒子本身找到的最优解，那么gbest则是pbest中的最好值，即全局最优解，是整个种群的经验。每个粒子使用下列信息更新自己的当前位置：(1)自身位置；(2)自身速度；(3)自身位置与pbest之间的距离；(4)自身位置与gbest之间的距离。然后算法就是这样以一个随机初始化形成的粒子群，迭代着开始进行搜索了。4.3基本粒子群算法4.3.1算法描述在PSO中，每只鸟被称之为一个粒子，每个粒子用其几何位置和速度向量表示，在问题求解中，每个粒子参考自己既定方向、所经历的最优方向和整个鸟群的最优方向确定自己的飞行[66]。现在一般采用下面公式对每个粒子进行操作：52 (4.2)其中是粒子的速度向量，是粒子当前位置。pbest是粒子本身所找到的最好解得位置，gbest是整个种群目前找到的最优解的位置。其他参数的介绍见第3部分。4.3.2参数设定PSO算法中需要调节的参数主要包括：惯性权重系数w、学习因子和、最大速度vmax以及种群规模m，在本课题算法中还加入了最大位置xmax。(1)惯性权重系数惯性权重系数w是用前面的速度来控制当前速度的影响，较大的w可以加强PSO的全局搜索能力，而较小的w能加强PSO的局部搜索能力。目前普遍采用的是将w设置为从0.9到0.1线性下降的方法[67]，这种方法可使得PSO在开始时在较大的区域内探索，较快地定位最优解的大致位置，随着w逐渐减小，粒子速度减慢，开始进行精细的局部搜索。(2)学习因子学习因子(也称加速度系数)和分别调节粒子向全局最优粒子和个体最优粒子方向飞行的最大步长。若太小，则粒子可能远离目标区域；若太大则可能导致粒子忽然向目标区域飞去或飞过目标区域[68]。合适的c1和c2可以加快收敛且不易陷入局部最优，目前大多数文献均采用c1=c2=2。但文献[55]分析指出，令c1=1.5，c2=2.5能使算法具有更好的收敛性能。(3)最大速度引入最大速度vmax的实际上是对粒子的全局搜索能力和局部搜索能力的一种平衡。vmax越大，则粒子的飞行速度越高，从而可以对整个空间进行有效的搜索；vmax越小，则粒子的飞行速度越低，从而可以对局部区域进行更加有效的搜索，确保获得较高的搜索精度。一般来说，对于基本PSO算法，若将搜索空间第d维的变化范围定义为[-xdmax,xdmax]，令vdmax=k*xdmax(d=1,2,…,D),并且在k∈[0.1,0.2][10]的范围内能够获得较好性能。(4)种群规模52 PSO算法种群规模较小，一般令m=20～40。其实对于大部分问题10个粒子就能取得很好结果，但对于较难或者特定类别的问题，粒子数可能取到100或200。(5)最大位置最大位置xmax的引入是为了防止在迭代后期，粒子位置超过取值区间。经试实验得出，xmax=q*xmax(d=1,2,…,D)，并且在q∈[0.5,0.9]的范围内能够获得较好的性能。4.4改进的粒子群聚类算法4.4.1粒子群算法的优缺点由于粒子群算法收敛速度快，需要设置、调整的参数少，实现简洁，近年来受到学术界的广泛重视。现在，PSO算法在函数优化、神经网络训练、模糊系统控制以及其它工程领域都得到了广泛应用[69]。但是PSO算法也有缺点，其最主要的问题是它容易产生早熟收敛、局部寻优能力较差等[57]。纵观各种与PSO算法相关的混合算法，大多数基本上采用一种策略对其改进，要么与其他算法结合，要么加入变异操作，同时采用两种策略的混合算法较少[57]。因此，本文提出了一种新的改进策略：将局部搜索能力强的K-均值算法和基于遗传算法的交叉、变异操作同时结合到PSO算法中。通过适当调节，发挥各自的优点，既提高了PSO算法的局部搜索能力，又因为加入了交叉、变异操作增加了种群的多样性，防止了算法早熟。通过与文献[70]中提出的方法对比，这种改进的粒子群聚类算法的收敛效果更好一些。4.4.2改进的粒子群聚类算法(1)编码和适应度函数算法中的个体采用基于聚类中心的浮点数编码方式，每个粒子由K个聚类中心组成，它可表示为长度为K×l的浮点码串。个体的适应度函数定义为：(4.3)其中，为各样本到各自聚类中心的欧氏距离的和。(2)基于遗传算法的交叉、变异操作首先，采用基于轮盘赌的52 选择策略选择适应度较高、与种群规模一样大小的个体进行交叉、变异，然后将完成上述操作的部分粒子按目标值的大小重新插入到原种群中，取代原种群中目标值较大的个体。具体的交叉、变异操作采用由菲尔德大学开发的遗传算法工具箱中提供的离散重组的交叉方法和实种群变异方法。(3)解聚类问题的基本粒子群算法步骤如下：Step1:设定粒子数m，规定迭代次数Max_DT，随机产生m个初始解X0；Step2:根据当前位置，以式(4.3)计算适应值f。设置当前适应值为个体极值pbest，当前位置为个体极值位置pxbest，根据各个粒子的个体极值pbest，找出全局极值gbest和全局极值位置gxbest；While(迭代次数<规定迭代次数)doFori=1:mStep3:按式(4.1)，更新自己的速度，并限制在vmax内；Step4:按式(4.2)，更新当前的位置；Step5:根据当前位置，各个样本按最小距离原则分配给K个聚类中心；Step6:按(4.3)式计算适应度f；Step7:更新pbest,pxbest；End；Step8:根据各个粒子的个体极值pbest，找出全局极值gbest和全局极值位置gxbest；Step9:X0=X1；End；Step10:最后输出全局极值gbest和全局极值位gxbest。本课题算法是在文献[69]的基础上作的改进。首先在第4步，更新位置时将其限制在xmax内，其他的改进如下：改进方法1：先用K-均值算法作一快速分类，其结果作为其中一个粒子结果，并在第(8)步后面对粒子进行交叉、变异操作，其他步骤同上，此方法称为Kmean+PSO+GA。改进方法2：采用K-均值算法的思想，在第(5)步后面，在新的分类基础上重新计算新的聚类中心，如果重新计算得到的聚类中心的适应度比原来的差，则舍弃，否则更新为当前的位置，且在第(8)步后面对粒子进行交叉、变异操作，此方法称为PSO+Kmean+GA。改进方法3：综合改进方法1和方法2，此方法称为Kmean+PSO+Kmean+GA。52 4.5仿真实验在以WindowsXP为操作系统的PC(AMDSempron(2200+)，1.5GHz主频，1GB内存)机上用Matlab7.0.1分别对C-均值算法、GA算法、PSO算法、Cmean+PSO算法、PSO+Cmean算法、Cmean+PSO+Cmean算法、PSO+GA算法、Cmean+PSO+GA算法、PSO+Cmean+GA算法、Cmean+PSO+C+GA算法进行仿真实验。实验参数设置如下：交叉概率Pc=0.68，变异概率Pm=0.001，种群规模为m=30，迭代次数Max_DT=50，c1=1.5，c2=2.5，w=0.8(1+t)*0.2/Max_DT(t为当前迭代次数)，k=0.14，q=0.85。实验采用Fisher的Iris植物样本数据，该数据集由分别属于三种植物的150个样本组成，每个样本均为4维模式向量，代表植物的4种特征数据。每种算法作了20次实验，结果见表4.1。表4.1对Iris植物样本数据聚类的实验结果算法最好解平均值最差解最好解次数C-均值算法97.325997.3360597.346210GA算法97.235597.9344899.07521PSO97.295097.4750397.51971PSO+GA97.309897.4462997.51671Cmean+PSO97.325997.3558197.634412Cmean+PSO+GA97.190197.3264397.34621PSO+Cmean97.041697.0829497.12332PSO+Cmean+GA97.040697.0755297.11651Cmean+PSO+Cmean97.041697.0876697.12331Cmean+PSO+Cmean+GA96.946197.0736597.10131从表4.1可以看出，用改进后的粒子群算法作的聚类，其结果比用简单粒子群算法或简单遗传算法或者C均值算法作的聚类的结果都要好，而其用粒子群算法和C-均值算法以及遗传算法的三种算法所结合形成的混合算法的聚类结果又比用粒子群算法和C-均值两种算法所结合形成的混合算法做的聚类结果要好，特别值得注意的是如果各种算法结合的顺序不同最终得到的聚类结果也是不同的。并且可以由表中结果看出，用改进后的最后一种算法所作的聚类其结果相对于其他算法或者改进策略来说是最好的。52 4.6本章小结本章在简单介绍了粒子群算法的研究现状之后，紧接着介绍了粒子群算法原理、算法的基本操作步骤和其参数的设定等问题，然后在着重分析了现有粒子群算法的优缺点，并结合前面章节所介绍的C-均值聚类算法和遗传算法中的内容，提出了一种改进的粒子群算法。最后用改进后的算法作实验并分析运行结果。52 第六章结论与展望5.1结论C均值聚类算法简单、收敛速度快且局部搜索能力强，但它对初始条件较为敏感，对不同的初始值有不同的聚类结果。由于该算法是基于梯度下降的算法，因此，常常不可避免地使目标函数陷入局部极值，甚至会出现退化解和无解的情况[72]。为此，本文为了克服FCM算法和C均值算法对初值的敏感性，提出了一种基于免疫遗传算法的FCM算法和基于改进的粒子群算法的聚类方法。其主要完成以下两部分工作：（1）提出了一种基于免疫遗传算法的FCM算法。一方面，将FCM算法作为一个搜索算子，使得该算法具有局部搜索能力强，运算量小的特点，从而能加快算法的局部寻优速度。另一方面，结合了免疫算法的优点，使得该算法具有免疫系统的记忆功能和抗体的促进和抑制功能，加快了搜索速度，保证的个体的多样性，克服了GA未成熟收敛的现象。因此，本文算法具有较快的收敛速度和较高的收敛精度。实验结果也表明，本文算法能够有效地收敛于全局最优解。（2）提出了一种基于改进的PSO算法的新聚类算法。该算法一方面结合了C-均值，使得该算法具有局部搜索能力强，运算量小的特点，从而能加快算法的局部寻优速度；另一方面，加入了基于遗传算法中的交叉、变异操作，保证了种群的多样性，克服了PSO未成熟收敛的现象。因此，本文算法具有较快的收敛速度和较高的收敛精度。实验结果也表明，本文算法能够有效地收敛于全局最优解。5.2展望由于本人的能力限制加之时间紧迫，本论文只是在一定程度上改善了粒子群算法和遗传算法的早熟现象，但是并没有显著的提高这两种算法的寻优能力，因此可以说只有量的变化没有质的提高。并且改进后的算法是否因为在遗传算法中加入了免疫操作和在粒子群算法中加入交叉和变异操作，使得算法的复杂性增加，并且较明显的延长了算法的计算时间，这些等问题都有待做进一步的研究。最后，本文基本还停留在理论研究和实验验证的阶段，这些理论和方法在实际应用中还有待进一步验证。52 参考文献[1]JiaweiHan,MichelineKamber数据挖掘.概念与技术[M].范明.北京:机械工业出版社,2007,3.[2]数据挖掘讨论组.数据挖掘资料汇编[DB/OL].http://www.dmgroup.org.cn,2008.5.[3]陈栋.Knight.一个通用知识挖掘工具[J].计算机研究与发展,1998,35(4):338-343.[4]中国人民大学统计系数数据挖掘中心.数据挖掘中的聚类分析[J].统计与信息论坛,2002,17(3):28-33.[5]马仲来.系统聚类分析中应注意的两类问题.数理统计与管理[J],1994,12(6):55-56.[6]马飞.数据挖掘中的聚类算法研究:[南京理工大学硕士学位论文].南京:南京理工大学,2008,1,5.[7]王鑫,王洪国,王瑶等.数据挖掘中聚类方法比较研究[J].计算机技术与发展,2006,16(10):20-25.[8]HollandJ.H.Adaptioninnaturalandartificialsystem[M].Michigan:TheUniversityofMichiganPress.1975.[9]HallLO,OzyurtIB,BezdekJC.Clusteringwithageneticallyoptimizedapproach[J].IEEETransactionsonEvolutionaryComputation,1999,3(2):103-112.[10]刘健庄,谢维信.聚类分析的遗传算法方法[J].电子学报,1995,23(11):81-83.[11]刘静,钟伟才.免疫进化聚类算法[J].电子学报,2001,29(12):1868-1872.[12]ShengW,TuckerA,LiuX.ClusteringwithNichinggeneticK-meansalgorithm[A].ProceedingsofGeneticandEvolutionaryComputationConference[C].Berlin:Springer-Verlag,2004.162-173.[13]KrishnaK,MurtyMN.GeneticK-meansalgorithm[J].IEEETransactionsonSystems,ManandCybernetics,PartB:Cybernetics,1999,29(3):433-439.[14]MaulikU,BandyopadhyayS.Geneticalgorithm-basedclusteringtechnique[J].PatternRecognition,1997,30(7):1109-1119.[15]高坚.基于C—均值和免疫遗传算法的聚类.[J].计算机工程,2003,29(12):65-66.[16]周春光,梁艳春.计算智能[M].长春:吉林大学出版社,2001,1.52 [1]田小梅,龚静.实数编码遗传算法的评述[J].湖南环境生物职业技术学院学报,2005,11(1):25-31.[2]李鹏,董聪.基于实数编码的广义遗传算法及其在优化问题中的应用[J].控制与决策,2002,17(4):487-490.[3]张志顺,胡勇刚,赵宏伟等.基于改进形式的遗传算法研究[J].微电子学,2002,32(4):273-275.[4]田小梅,郑金华,李合军.基于父个体相似度的自适应遗传算法[J].计算机工程与应用,2005,31(18):61-63.[5]聂冲,王维平,赵雯等.基于学习算子的自学习遗传算法设计[J].计算机仿真,2006,23(9):168-171.[6]吴养会,王乃信,刘瀛洲.多种群竞争遗传算法及其性能分析[J].西北农业科技大学学报,2005,33(4):154-156.[7]蔡良伟,李霞.一种带融合操作的实数多种群遗传算法[J].计算机工程与应用,2005,31(13):61-63.[8]王文义,任刚.多种群退火贪婪混合遗传算法[J].计算机工程与应用,2005,31(23):60-62.[9]SureshChandraSatapathy,VenkateshKatari,RohitParimietal.ANewApproachofIntegratingPSO&ImprovedGAforClusteringwithParallelandTransitionalTechnique[C].IEEE,ThirdInternationalConferenceonNaturalComputation,2007.[10]周远晖,陆玉昌,石纯一.基于克服过早收敛的自适应并行遗传算法[J].清华大学学报,1998,38(3):93-95.[11]吴佳英,李平,胡宁静等.一种改进多亲遗传算法的并行模型研究[J].计算机工程,2007,33(5):190-192.[12]李同强,周天弋,吴斌.基于改进遗传算法的加权模糊C均值聚类算法[J].计算机应用,2009,29(B12):260-262.[13]曹志宇,张忠林,李元韬.快速查找初始聚类中心的K-means算法[J].兰州交通大学学报,2009,28(6):15-18.[14]司徒莹.新型免疫遗传算法研究[J].计算机应用与软件,2009,26(11):266-268.[15]雷英杰,张善文,李续武等.MATLAB遗传算法工具箱及应用[M].西安:西安电子科技大学出版社,2005,4.52 [1]初级电气化验收规程中华人民共和国国家标准GB/T15659-95.[2]陈慰峰.医学免疫学[M].北京:人民卫生出版社,2001:1-18.[3]黎竹娟.免疫遗传算法WEB使用挖掘中的研究:[广西大学硕士学位论文].南宁:广西大学,2007.5.[4]NasarouiO,GonzalezF,DasguptaD.Thefuzzyimmunesystem:motivations,basicconcepts,andapplicationtoclusteringanddWebprofiling,FuzzySystems[C].In:FUZZ-IEEE’02,Proceedingsofthe2002IEEEInternationalConference,Vol12002-05:711-716.[5]DDasgupta.Immune-basedintrusiondetectionsystem:ageneralframework[C].In:Proceedingsofthe22ndnationalinformationsystemssecurityconference,1999.[6]IshidaY.FullyDistributedDiagnosisbyPDPLearningAlgorithm:TowardsImmuneNetworkPDPModel[C].In:ProcofIJCNN90,SanDiego.1990.[7]Cserey,G.,Falus,A.,Pored,W.,Roska,T.AnartificialimmunesystemforvisualapplicationswithCNN-UM[A].CircuitsandSystems,2004,ISCAS04,Proceedingsofthe2004InternationalSymposium[C].2004,17-20.[8]P.J.CostaBranco,J.A.Dente,andR.VilelaMendes.UsingImmunologyPrinciplesforFaultDetection[J].IEEETransactionsonIndustrialElectronics,2003,50(2):362-373.[9]ATarakanov.DDasgupta.Animmunechiparchitectureanditsemulation[q].In:2002NASAConferenceonEvolvableHardware,2002.[10]ForrestS,PerelsonA,CherukuriR.Self-nonselfdiscriminationinacomputer[C].In:Proceedingsof1994IEEEComputerSocietySymposiumonResearchinSecurityandPrivacy,LosAlmitos,CA,USA:IEEEComputerSociety,1994:202-212.[11]Moshref,H.,VanLandingham,H.,Immunenetworksimulationofreactivecontrolofarobotarmmanipulator[A].SoftComputinginIndustrialApplications,2001,SMCia/01,Proceedingsofthe2001IEEEMountainWorkshopon[C].2001,81-85.[12]YouYong,WangSunhn,hengWanxing.Short-termloadforecastingusingartificialimmunenetwork[A].PowerSystemTechnology,2002Proceedings.PowerCon2002,InternationalConference[C].2002,322-325.[13]JHunt,JTimmis.DCookeetal.TheDevelopmentofanArtificialImmunesystemforRealWorldApplication[J].ArtificialImmunesystemandtheirApplications.1999.52 [1]王磊,潘进,焦李成.免疫规划[J].计算机学报,2000,23(8):806-812.[2]焦李成,杜海峰.人工免疫系统进展与展望[J].电子学报,2003,31(l0):1540-1548.[3]谈英姿,沈炯,吕震中.免疫PID控制器在气温控制系统中的应用研究[J].中国电机工程学报,2002,22(10):148-152.[4]陈慰峰.医学免疫学[M].北京:人民卫生出版社,2001,8.[5]王磊,潘进,焦李成.免疫算法[J].电子学报,2000,28(7):74-78.[6]BurnetFM.TheClonalSelectionTheoryofAcquiredImmunity[M].Cambridge:CambridgeUniversityPress,1959,2.[7]KeplerTB,PerelsonAS,SomaticHypermutationinBcells:AnOptionalontrolTreatment[J],JournaloftheoreticalBiology,1993,(164):37-64.[8]高新波,谢维信.模糊聚类理论发展及应用研究进展[J].科学通报,1999,44(21):2241-2251.[9]BezdekJC.MumericaltaxonomywithFuzzysets[J].JournalMathematicalBiology,1974,(14):57-71.[10]BerekC,Ziegner.TheMaturationoftheimmuneresponsetoday[J].1993,14(8)400-402.[11]BezdekJC.PatternRecognitionwithFuzzyObjectiveFunctionAlgorithms[M].NewYork:PlenumPress,1981.[12]KennedyJ,EberhertR.Particleswarmoptimization[C]//IEEEInternationalConferenceonNeuralNetworks,1995:1942-1948.8.[13]ShiY,EberhartRC.ParticleSwarmOptimization:developments,applicationsandresources[C].In:ProcCongressonEvolutionaryComputation2001NJ:Piscataway,IEEEPress,2001:81-86,101-106.[14]海风吹.蚁群算法,PSO算法以及两种算法可以融合的几种方法[DB/OL].(2008-5-20).http://www.cnblogs.com/hetonghai/archive/2008/04/09/1144145.html.[15]ShiY,EberhartRC.FuzzyAdaptiveParticleSwarmOptimization[C].In:ProcCongressonEvolutionaryComputation,2001:101-106.[16]LovbjergM,RasmussenTk,KrinkT.hybridParticleSwarmOptimizerwithBreedingandSubpopulation[C].In:ProcCongressonEvolutionaryComputation,2001.[17]CiuprinaG,InanD,MunteanuI.UseofIntelligent-ParticleSwarmOptimizationin52 Electromagnetics[J].IEEETransonMagnetics,2002:38(2):1037-1040.[1]BritsR,EngelbrechtAP,vandenBerghF.ANichingParticleSwarmOptimizer[C]In:4thAsia-PacificConferenceonSimulatedEvolutionandLearning,2002.[2]李峻金,向阳,芦英明.粒子群聚类算法综述[J].计算机应用与软件,2009,26(11)：266-268.[3]vandenBerthF,EngelberchtAP.ANewLocallyConvergentParticleSwarmOptimizer[C].In:IEEEConferenceonSystems,Man,andCyber-netics,2002.[4]MillonasM,SwarmsM.Phasetransitionandcollectiveintelligence.In:C.G.Langton,(Eds.),ArtificiallifeIII.Addison–Wesley,MA,1994.[5]高岳林,任子晖.带有变异算子的自适应粒子群优化算法[J].计算机工程与应用,2007,43(25):43-47.[6]吕振肃,侯志荣.自适应变异的粒子群优化算法[J].电子学报,2004,32(3):416-420.[7]寇保华,杨涛,张晓今等.基于交叉变异的混合粒子群优化算法[J].计算机工程与应用,2007,43(17):85-88.[8]刘向东,沙秋夫,刘勇奎等.基于粒子群算法的聚类分析[J]计算机工程,2006,32(6):201-202.[9]高尚,杨静宇.一种新的基于粒子群算法的聚类方法[J].南京航空航天大学学报,2006,38(6):62-64.52 致谢首先要感谢我的导师罗可教授，感谢他在我读研期间对我工作的细心指导，以及在学习、生活上的鼓励和关心。在这三年中，他不仅传授我专业知识，指引我跟踪学科前沿，而且教导我务实上进，正直为人，这些将激励我在平时的学习和工作中不断前进。正是在他的指导使我对数据挖掘产生了浓厚的兴趣，并有了进一步的学习和运用。也由于他的帮助，使我更好的完成了毕业设计，达到了检验自己的知识与能力的目的，再次感谢罗老师能在忙碌的工作中抽出时间对我进行细致的指导。同时还要感谢计算机与通信工程学院、研究生部及计算机工程与应用杂志社在我们读研期间所给予的各种支持和帮助，是他们为我们创造了十分完善的学习条件。也要感谢以前教导过我的各位老师，正是由于他们对我的基础知识的教授，我才有能力完成这一工作。并且要感谢那些帮助过我的同学们，正是他们无私的帮助，才使得我在遇到问题时能够及时地找到思路。52 附录（攻读硕士学位期间发表录用论文）[1]孙洋,罗可.基于免疫遗传算法模糊C均值算法[J].计算机工程与应用,2009,45(23)：152-153.[2]孙洋,罗可.基于改进粒子群算法的聚类方法[J].计算机工程与应用,2009,45(33)：134-136.52