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

摘要

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

目录

文摘

英文文摘

声明

第1章 绪论

1.1研究背景与意义

1.1.1行为模型的建模和自动精化

1.1.2信息检索中的网页排序

1.2国内外研究现状

1.2.1模型的建模和精化方法

1.2.2网页排序方法

1.3课题的研究内容与意义

1.3.1研究内容

1.3.2研究意义

1.4研究成果

1.5论文的组织结构

第2章 形式化的行为模型建模方法

2.1 UML模型的缺点

2.2行为模型的基础——数据模型

2.2.1数据模型的定义和框架

2.2.2行为模型中形式化语句的基本符号

2.2.3 UML模型到数据模型的转换规则

2.2.4实例研究

2.3模型驱动开发中的行为模型

2.3.1行为模型及其相关定义

2.3.2实例研究

2.4支持递增式建模的复杂行为模型

2.4.1两种重用结构

2.4.2实例研究

2.5本章小结

第3章 行为模型的精化理论研究

3.1行为精化的定义

3.2状态空间分析

3.3本章小结

第4章 基于遗传规划的行为模型的精化方法

4.1程序演化问题中存在的难点

4.2基于谓词逻辑的遗传规划算法

4.2.1行为模型中采用的谓词公式范式

4.2.2基于遗传规划的精化机制

4.2.3实例研究

4.3包含组合终止条件的遗传规划方法

4.3.1组合终止条件

4.3.2实现机制

4.3.3实例研究

4.4本章小结

第5章 基于进化计算的排序学习的研究

5.1进化计算在排序学习领域中的现状

5.2基于进化计算的排序学习

5.2.1形式化定义

5.2.2基于进化计算的排序学习的优点

5.2.3基于进化计算的排序学习的算法框架

5.3本章小结

第6章 RankIP：基于免疫规划的排序学习方法

6.1免疫规划算法

6.1.1生物免疫系统

6.1.2人工免疫系统

6.1.3免疫规划算法

6.1.4免疫规划和遗传规划的区别

6.2 RankIP:基于免疫规划的排序学习算法

6.2.1终止符集合

6.2.2函数集合

6.2.3排序函数的评价

6.2.4亲和度函数

6.2.5高亲和度个体的选择

6.2.6最优个体的选择

6.3实验

6.3.1数据集合：LETOR

6.3.2实验参数

6.3.3 RankIP的测试精度

6.3.4 RankIP对于最优个体选择公式的敏感度

6.3.5 RankIP对几个选择参数的敏感度

6.3.6免疫规划和遗传规划在排序学习中的对比

6.4本章小结

第7章 总结与展望

7.1主要工作总结

7.2未来工作展望

参考文献

致谢

攻读学位期间发表的学术论文

在读期间参与科研项目情况

在读期间获奖情况