面向实例的群体智能优化算法及其应用研究

以蚁群和粒子群为代表的群体智能优化算法近年得到了广泛研究和应用。为保障对不同问题的适应能力，这类算法一般提供一些可选算子和可调参数。由于数学描述的复杂性，当前主要基于简单实验配置这些算子和参数，无法反映待解决问题实例的具体特征，而有关算法性能预测方面的研究更为少见。本项目拟将机器学习的思想引入群体智能领域，在元学习框架下，通过对大量历史实例求解数据进行离线地分类和回归学习，挖掘群体智能算法与问题属性、运行时间的内在关系，并据此提出一种面向实例的算法在线配置和性能预测方法，解决其中的关键理论和技术问题。在应用方面，拟将取得的理论成果应用于卫星测控资源调度问题，实现一种支持在线配置和性能预测的群体智能调度算法。本项目的实施有助于充实群体智能的理论基础，促进群体智能与机器学习的学科交叉，同时有望为卫星测控资源调度问题提供一套切实可行的解决方案。

本项目采用机器学习的思想和方法，通过系统分析群体智能优化算法在求解历史实例时所积累的大量数据，获取算法性能与算法配置、问题属性之间的关系，用以指导新实例的求解，并对求解性能进行评价。.以MKP问题为例，研究分析了问题属性的抽取方法，确定了影响问题难易程度和算法适应度的关键属性；通过在属性空间进行聚类分析，构建了MKP的元实例集。在采用蚁群算法求解MMKP问题时，根据MMKP问题中对象的组间可分性，提出了一种面向单组的状态转移算子；根据MMKP问题的约束特征，提出了一种不可行性指标和修复算子。仿真实验表明，由此形成的AL-MMKP算法具有很强的竞争力。在采用粒子群算法求解连续优化问题时，根据问题的多模特征，提出了一种新型的学习规则，该规则综合利用“学习标本”的适应度和分布信息，提高了搜索效率；对影响算法性能的关键参数进行了理论研究，给出了一种鲁棒且简单的参数设置规则。统计分析表明，由此形成的SLPSOA算法优于已有的PSO算法。基于序优化理论，提出了一种群体智能算法解性能评价方法。该方法首先通过聚类分析，将采样样本均匀化分区；然后通过核密度估计获得分区后各子区域的适应度分布，在此基础上计算出可以用来评价解性能的对准概率。通过对比分析该方法的理论计算结果与实际统计结果，验证了该方法的有效性。针对实际的卫星测控资源调度问题，以可见弧段为调度对象，建立了该问题的复合独立集模型；分别在单目标和多目标框架下，提出了两种蚁群求解算法；并在多目标框架下，利用目标向量之间的间距概念，提出了一种解集分布度量方法，进而实现了对解性能的评价。.在项目执行期间，发表论文10篇，协助培养博士生2名，独立培养硕士生1名，实现了预期目标。