基于问题模式挖掘的自适应蚁群算法及其应用研究

项目名称： 基于问题模式挖掘的自适应蚁群算法及其应用研究

项目编号： No.60875043

项目类型： 面上项目

立项/批准年度： 2009

项目学科： 金属学与金属工艺

项目作者： 冯祖仁

作者单位： 西安交通大学

项目金额： 30万元

中文摘要： 蚁群算法是一类应用广泛的智能优化算法。但是，蚁群算法的参数设置还没有成熟的理论指导，启发信息的获取和利用以及解质量的定量评价尚缺乏理论依据和方法，从而在一定程度上限制了蚁群算法在实际中的应用。本项目将数据挖掘的思想与蚁群算法相结合，拟研究一种基于问题模式挖掘的自适应蚁群算法，其基本思想是从大量解记录中发现问题模式，利用目标函数值与解差异之间的关联关系，建立参数自适应机制；利用目标函数值变化与各解元素属性之间的关联关系，揭示解元素之间的组合对解质量的贡献，实现启发信息的获取和利用；在序优化理论的基础上，统计分析解空间的分布，得出解质量评价的理论依据和方法，并分析计算邻域搜索对解质量的贡献。针对典型的资源调度问题（以较大规模的卫星测控资源调度问题为例），实验分析自适应蚁群算法的寻优能力，以及解质量定量评价方法的有效性。本项目将有助于促进蚁群算法理论发展，并使之更好地满足工程实际应用需求。

中文关键词： 蚁群算法；自适应；问题模式；数据挖掘；资源调度

英文摘要： Ant colony optimization (ACO) is a popular intelligent optimization algorithm. However, there is still no mature theoretical guideline on parameter settings in the literature. Moreover, few theoretical method is available for exploring and utilizing heuristic information, and assessing solution quality. These problems have restricted the practical applications of ACO to some extent. This project aims at studying an adaptive ACO algorithm, which integrates the idea of data mining into ACO by mining corresponding problem patterns. The basic idea of this algorithm is threefold. First, it digs problem patterns from plenty of solutions, then establishes the adaptive mechanism of parameters by exploiting the relationship between objective function values and the differences among solutions. Second, it utilizes the relationship between the variation of objective function values and the attributes of each solution component, and discloses the contribution of solution component combinations to the solution quality, so as to obtain and utilize heuristic information. In addition, on the basis of the ordinal optimization theory, it statistically analyzes the distribution of solutions, such that theoretical base and assessment method can be obtained, and the contribution of local search to solution quality can be analyzed. Finally, we apply the proposed algorithm to representative resource scheduling problems with the satellite resource scheduling problem as an example, and empirically analyze the search ability of the proposed algorithm and the validity of the solution quality assessment method. It can be expected that our project would help to promote the theoretical progress of ACO and make ACO meet real-world requirements in a better manner.

英文关键词： Ant colony algorithm; adaptivity; problem pattern; data mining; resource scheduling