基于高阶逻辑的交叉算子的形式化研究

摘要

随着计算机系统规模的迅速增大，系统设计实现的正确性问题越来越严峻。形式化方法的出现，成为了解决该问题的一个重要手段。它运用数学方法的特点相比于传统的模拟和测试具有更高的可靠性和良好的完备性。其中，定理证明的方法因其既能验证系统规范又不受系统规模的限制而备受关注。遗传算法被越来越多的应用在安全性要求较高的领域，然而定理证明器中还未有形式化的遗传算法，这就限制了形式化方法在相关领域的应用。因此，将遗传算法形式化在HOL4系统中对扩展定理证明方法的应用领域具有重要的研究意义和实用价值。
　　众所周知，遗传算法的求解能力取决于最关键的操作——交叉算子。因此，本文对应用最多的单点交叉和多点交叉进行了形式化。首先，本文采用高阶逻辑的方法对交叉算子进行了形式化分析，从而定义交叉算子生成子代的过程为交叉操作。通过对交叉操作的形式化抽象，提取了交叉操作的基本组成元素。这些基本元素组成了交叉操作的一般化模型，并使用高阶逻辑表示基本组成元素。基于一般化结构模型，使用双递归的方法提出了交叉操作的形式化模型，并用数学的方法描述了此模型。然后，使用形式化的交叉操作分别完成了单点交叉算子和多点交叉算子的形式化，并使用支持高级证明步骤、重写对策和自动推理证明了交叉算子的性质。同时，交叉算子性质的证明充分保证了本文形式化的交叉算子的正确性。最后，为了说明形式化的交叉算子的实用性，用形式化的交叉算子设计了一个遗传算法，用来求解机器人在运动空间的最优避碰路径。此应用为HOL4中设计遗传算法程序提供了一个有效的实例。
　　将交叉操作函数引入HOL4系统，丰富和完善了系统中的理论库，增强了其推理能力，并扩展了应用领域。此外，本文形式化的交叉算子可以被直接应用在遗传算法的形式化模型中，从而有利于遗传算法的形式化研究。通过使用形式化的交叉算子完成了机器人路径规划中遗传算法的实现，挖掘了形式化的交叉算子的应用潜力。

目录

声明

摘要

第一章 绪论

1．1 研究背景和意义

1．2 国内外研究现状

1．2．1 定理证明的研究现状

1．2．2 遗传算法形式化的研究现状

1．3 本文的主要研究内容及贡献

1．4 本文的组织结构

第二章 形式化方法概述

2．1 形式化方法简介

2．2 交互式定理证明器

2．3 HOL系统简介

2．4 本章小结

第三章 交叉操作的形式化

3．2 交叉操作的定义及预备工作

3．3 交叉操作的一般化结构模型

3．4 一般化模型的高阶逻辑表示

3．4．1 染色体的高阶逻辑描述

3．4．2 交叉项的高阶逻辑描述

3．4．3 基本操作的高阶逻辑描述

3．5 交叉操作的形式化建模

3．6 交叉操作的高阶逻辑描述

3．7 交叉操作中基本操作性质的形式化证明

3．7．1 基本操作性质的高阶逻辑描述

3．7．2 基本操作性质的形式化证明

3．7 难点及解决方案

3．8 本章小结

第四章 交叉算子在HOL4系统中的形式化

4．1 研究动机

4．2 单点交叉算子的形式化

4．2．1 单点交叉算子的形式化实现

4．2．2 单点交叉算子性质的证明

4．3 多点交叉算子的形式化

4．3．1 多点交叉算子的形式化实现

4．3．2 多点交叉算子性质的证明

4．4 难点及解决方案

4．5 本章小结

第五章 形式化的交叉算子的应用

5．1 形式化的交叉算子的应用

5．2 本章小结

第六章 总结与展望

6．1 总结

6．2 展望

参考文献

致谢

研究成果及发表的论文

作者与导师简介