基于进化计算的行为模型自动精化和排序学习方法的研究

  本文关键词：基于进化计算的行为模型自动精化和排序学习方法的研究，，由笔耕文化传播整理发布。

《山东大学》 2009年

基于进化计算的行为模型自动精化和排序学习方法的研究

王帅强  

【摘要】： 进化计算是研究仿照生物进化自然选择过程中所表现出来的优化规律和方法,以解决复杂的工程技术领域或其他领域的优化问题的一种计算方法。随着进化计算自身的发展,一些新的进化计算方法在不断的提出,而一些旧的方法也在焕发着新的活力。 近些年,在一些领域中的某些问题的研究中,传统的方法遇到了很大的困难,例如在软件工程领域中的模型精化问题;而在一些领域中,某些问题利用传统的人工智能方法不能得到很理想的结果,例如信息检索领域中的排序学习问题。这些问题都促使我们从进化计算的角度重新审视,以期利用自然进化的思想对他们进一步处理,从而得到理想的结果。 基于以上的应用背景和需求,本文重点研究了利用进化计算相关算法解决传统方法难以处理的某些问题:并以此为基础,开发了一系列的原型系统对研究成果进行了验证。本文主要的研究内容和创新点包括以下方面: 1对软件系统中行为的建模和精化理论的研究。本论文根据自动精化方法必须的条件,提出了一套描述行为模型的形式化符号体系,并据此提出了行为模型的形式化建模方法和行为精化理论。行为建模方法和行为模型的自动精化方法的提出,为推动模型驱动开发理论,尤其是UML和形式化方法集成建模技术的发展和应用,将会起到巨大的推动作用。 在模型驱动开发中,行为的建模和精化是一个关键问题,它需要考虑对象的一系列的动作语义,包括动作在何时触发,系统状态如何变化,以及行为执行结束后最终状态如何描述等等。由于UML在模型语义等方面的缺失,以及形式化方法和UML混合建模研究的广泛开展,使得我们不得不采用以集合论和谓词逻辑为基础的形式化建模方法,对行为进行精确的建模并逐步精化至代码。近几十年中,尽管有很多精化理论和精化工具相继提出,但总体而言,传统的关于精化方面的研究主要考虑的是整个软件系统模型的精化定义和验证问题。随着UML和形式化方法集成建模的研究的广泛开展,形式化建模方法所关注的领域转变为软件系统的对象行为的细节。在这方面,国内外并没有相关的专门用于描述行为精化的思想提出,而传统的基于整个系统的精化显得过于庞大,对于我们的问题并不十分合适。因此,行为精化理论的提出,是一个亟待解决的重要问题。 根据自动精化方法必须的条件,参照前人的工作,我们提出了一套描述行为模型的形式化符号体系,并据此提出了行为模型的形式化建模方法和行为精化理论。本文根据行为精化理论,从问题求解的角度上,提出了一种实现行为精化的一般性的指导思想,即通过搜索状态空间,从而找到一个可以满足特定条件的状态,进而得到精化结果。通过估计状态空间可以证明,遍历式的穷尽搜索办法是不可行的,必须引入启发式的智能搜索机制。 2对基于遗传规划的行为模型自动精化方法的研究。本论文提出了一种基于遗传规划的自动精化方法,它为形式化模型的自动精化方法提供了一个新的思路,同时为UML和形式化方法集成建模方法的推广和应用提供了更加有效的工具支持。 软件开发的模型化和自动化是软件技术的发展趋势,而缺乏自动精化方法是阻碍形式化方法在业界应用的一个重要原因。在本文中我们提出了一种基于遗传规划的自动精化方法。 由于遗传规划算法源自于遗传算法,它也有其自身的弱点,最突出的问题就是它最适合线性结构的问题求解逻辑,而不能有效地处理显式的循环结构和选择结构。为了解决上述问题,我们提出了一种基于谓词逻辑的遗传规划方法。首先,对抽象模型的后置条件进行自下而上的归约精化,以生成显式的循环结构并将问题简化和分解;然后将生成的子问题采用基于遗传规划的精化方法进一步精化,将行为模型的精化看作一个问题求解最终得到实现模型,通过基于遗传规划的方法最终得到一个由若干基本操作组合而成的具体行为。我们还提出了一种在遗传规划中采用组合终止条件的方法,用以生成选择结构;最后,我们提出一种对实现模型的优化方法,以减少实现模型中操作逻辑的冗余。根据我们提出的方法,成功的演化出了冒泡排序算法。 事实上,本方法具有一定的通用性,它适用于任何由若干基本操作组合以完成复杂操作的问题求解过程。 3对基于进化计算的排序学习的研究。本论文提出了基于进化计算的排序函数发现算法的框架;并根据该框架,提出一种基于免疫规划的排序学习方法RankIP,并得到了很好的性能,有力的证明了我们提出的基于排序学习算法框架的有效性。本论文的研究将有力的促进进化计算方法在排序学习问题的应用。 网页排序问题是Web信息检索领域的一个中心问题,一个好的排序算法能够明显的提高检索质量。传统的网页排序算法分为三类:基于链接的方法、基于内容的方法和混合方法。此外,基于机器学习技术的网页排序算法,即“排序学习”,越来越广泛的用来解决信息检索排序问题。这一问题作为信息检索和机器学习的交叉领域,已经成为非常活跃的一个研究热点,并引起广泛关注。目前提出的各种排序学习算法,其结果都不甚理想。 一些学者依据进化计算的思想,提出了基于遗传规划的排序学习方法;而最近包括群智能算法,免疫算法等一系列性能更为优异的进化计算方法的提出,也为基于进化计算的排序学习方法提供了更加有力的工具。在这个基础上,我们介绍了一系列的定义,精确的表达了基于进化计算的排序函数发现算法的一般原理;并且描述了基于进化计算的排序函数发现算法的框架,使得任何的进化计算方法都可以灵活的嵌入算法框架中。算法框架的提出,将有力的促进进化计算方法在信息检索领域,尤其是排序学习问题的应用。 根据我们提出的基于进化计算的排序函数发现的算法框架,在本文中我们还提出一种基于免疫规划的排序学习方法RanklP。我们采用微软亚洲研究院提供的LETOR 2.0数据集合作为训练和验证数据集合,实验证明RankIP较之其他排序学习方法在P@n,MAP和NDCG等评价标准上均优于目前提出的著名的排序学习方法,如RankingSVM和RankBoost等。在实验中我们还对比了免疫规划和遗传规划在排序学习中的应用,结果表明,由于免疫规划在多样性方面优于遗传规划,因此在几乎相同的条件下,基于免疫规划的排序学习算法的性能更为优越。

【关键词】：
【学位授予单位】：山东大学
【学位级别】：博士
【学位授予年份】：2009
【分类号】：TP181
【目录】：

下载全文 更多同类文献

CAJ全文下载

(如何获取全文？ 欢迎：购买知网充值卡、在线充值、在线咨询)

CAJViewer阅读器支持CAJ、PDF文件格式

【相似文献】

中国期刊全文数据库 前10条

1 何加浪;张琨;张宏;;进化计算在软件智能修复中的应用[J];计算机工程;2011年16期

2 张宇山;郝志峰;黄翰;;二元进化策略的收敛性分析[J];计算机科学;2011年07期

3 蔡昭权;罗伟;张宇山;黄翰;罗勇为;;Lévy变异进化规划算法的计算时间分析[J];计算机科学;2011年09期

4 王丽芳;曾建潮;洪毅;;利用Copula函数估计概率模型并采样的分布估计算法[J];控制与决策;2011年09期

5 吴延科;;随机因素对PSO算法的性能影响分析[J];文山学院学报;2011年03期

6 周传华;谢安世;;一种基于动态小生境的自组织学习算法[J];软件学报;2011年08期

7 陈皓;崔杜武;;基于族群进化计算的多项式回归电力负荷预测[J];软件;2011年05期

8 张超群;郑建国;王翔;;蜂群算法研究综述[J];计算机应用研究;2011年09期

9 刘宁;刘雪瑞;;GPS软件接收机精确载波频率捕获算法分析与实现[J];全球定位系统;2011年02期

10 杨治秋;;基于遗传算法的功能可重构数字体系研究[J];微计算机信息;2011年08期

中国重要会议论文全文数据库 前10条

1 黎明;周琳霞;杨小芹;;图像的进化计算分割法[A];中国图象图形学会第十届全国图像图形学术会议（CIG’2001）和第一届全国虚拟现实技术研讨会（CVR’2001）论文集[C];2001年

2 褚德欣;;进化计算及其在智能控制中的应用[A];山西省科学技术情报学会学术年会论文集[C];2004年

3 杨光;林鸿;方锋;;广州市似大地水准面精化及成果应用[A];现代空间定位技术应用研讨交流会论文集（第5卷 第3集）[C];2007年

4 甄登春;;初探重庆主城区的似大地水准面精化[A];重庆市测绘学会第三届优秀论文评选获奖论文暨2005-2006年度学术交流会论文选编[C];2008年

5 赵清杰;杨波;;基于进化计算的BP网权值训练算法及其应用探讨[A];1998年中国智能自动化学术会议论文集（下册）[C];1998年

6 吕岗;赵鹤鸣;;一种优化前向神经网络权值的免疫算法[A];2003年中国智能自动化会议论文集（上册）[C];2003年

7 范新云;;GPS水准法拟合似大地水准面精化的研究[A];第二十一届海洋测绘综合性学术研讨会论文集[C];2009年

8 范新云;;GPS水准法拟合似大地水准面精化的研究[A];中国航海学会航标专业委员会测绘学组学术研讨会学术交流论文集[C];2009年

9 柯益华;胡学姝;;油气田产量预报Г模型参数估计的进化计算[A];2001年中国智能自动化会议论文集（下册）[C];2001年

10 张全德;;精化区域似大地水准面技术方法与设计[A];中国测绘学会2006年学术年会论文集[C];2006年

中国重要报纸全文数据库 前10条

1 ;[N];国际商报;2000年

2 记者 翟敏;[N];上海证券报;2011年

3 记者 翟敏;[N];上海证券报;2011年

4 记者 翟敏;[N];上海证券报;2011年

5 记者 杨勇;“乌龙合同”涉嫌虚假信披 彩虹精化复牌地量跌停[N];第一财经日报;2011年

6 梅雪荣;[N];中国经济时报;2011年

7 记者 施浩;产能释放+毛利提升 天马精化今年业绩或超预期[N];上海证券报;2011年

8 记者 魏梦杰;[N];上海证券报;2011年

9 记者 吴正懿;[N];上海证券报;2011年

10 记者 翟敏;[N];上海证券报;2011年

中国博士学位论文全文数据库 前10条

1 王帅强;基于进化计算的行为模型自动精化和排序学习方法的研究[D];山东大学;2009年

2 尹文君;面向不确定制造过程调度问题的进化计算方法及其应用[D];清华大学;2004年

3 王志春;基于进化计算的复杂分类算法研究及应用[D];天津大学;2010年

4 杨海军;进化计算中的模式理论、涌现及应用研究[D];天津大学;2004年

5 李智欢;无功优化进化计算的局部搜索策略及多目标处理方法[D];华中科技大学;2010年

6 吕岗;免疫算法及其应用研究[D];中国矿业大学（北京）;2003年

7 薛明志;进化计算与小波分析若干问题研究[D];西安电子科技大学;2004年

8 石振国;资源网络的精化学习及应用研究[D];上海大学;2011年

9 杨开兵;基于进化计算的多目标流水车间批组调度问题研究[D];大连理工大学;2011年

10 陈昊;动态环境下进化计算的研究[D];南京航空航天大学;2011年

中国硕士学位论文全文数据库 前10条

1 庞巍;进化计算算法在路径优化问题应用的研究[D];吉林大学;2004年

2 安磊;一种基于遗传算法的数据挖掘技术的研究与应用[D];河海大学;2001年

3 彭轩;遗传算法及其在图像分割中的应用[D];吉林大学;2006年

4 费璐璐;进化计算在作物生长模型优化中的应用研究[D];华东师范大学;2004年

5 华洁;函数聚类及其进化计算知识获取研究[D];西安理工大学;2010年

6 汪晗;基于进化计算的多目标优化与决策方法研究[D];中国人民解放军国防科学技术大学;2002年

7 彭伟民;基于线性变换的适应度函数及机器人进化计算研究[D];广东工业大学;2006年

8 于晓辉;进化计算和人工神经网络在多目标优化问题中的应用[D];山东师范大学;2004年

9 蓝海;CIMS环境下的数据仓库与数据挖掘应用研究[D];清华大学;2002年

10 王丽爱;研究思维进化计算的多峰优化性能及研究算法参数对效率的影响[D];太原理工大学;2004年

  本文关键词：基于进化计算的行为模型自动精化和排序学习方法的研究，由笔耕文化传播整理发布。