• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

计算机工程与科学

• 人工智能与数据挖掘 • 上一篇    下一篇

基于多分类支持向量机的优化算法智能推荐系统与实证分析

崔建双,车梦然   

  1. (北京科技大学东凌经济管理学院,北京 100083)
  • 收稿日期:2018-04-23 修回日期:2018-06-07 出版日期:2019-01-25 发布日期:2019-01-25
  • 基金资助:

    国家自然科学基金(71472013);中央高校基本科研业务费专项资金(06106175)

An intelligent recommendation system for
optimization algorithms based on multi-classification
support vector machine and its empirical analysis

CUI Jianshuang,CHE Mengran   

  1. (Dolinks School of Economics and Management,University of Science and Technology Beijing,Beijing 100083,China)
  • Received:2018-04-23 Revised:2018-06-07 Online:2019-01-25 Published:2019-01-25

摘要:

算法智能推荐是超启发式算法研究领域一个重要分支,其目标是从众多“在线”算法中自动选择出最适于当前问题的算法,从而大大提升解决问题的效率。基于此提出并验证了一种优化算法智能推荐系统,理论依据是无免费午餐定理和Rice算法选择框架,并假设问题特征与算法性能表现之间存在潜在关联关系,从而可以把算法推荐问题转换为一个多分类问题。为了验证假设的成立,以多模式资源约束项目调度问题为测试样本数据集,以粒子群、模拟退火、禁忌搜索和人工蜂群等元启发式优化算法为推荐对象,以支持向量机多分类策略实现算法的分类推荐。交叉验证结果表明,推荐准确率均在90%以上,各项评价指标表现优秀。

关键词: 算法推荐, 问题特征, 多分类支持向量机, 多模式资源约束项目调度问题

Abstract:

Intelligent algorithm recommendation is an important branch of the research field of hyperheuristic algorithms. Its goal is to automatically select the most suitable algorithm for the problem to be solved from many "online" algorithms, thereby greatly improving the efficiency of problem solving. We propose and validate an intelligent optimization algorithm recommendation system, whose theoretical basis is the No Free Lunch theorem and Rice’s algorithm selection framework. It assumes that there is a potential correlation between problem features and algorithm performance, thus the algorithm recommendation problem can be converted into a multiclassification problem. In order to verify the assumption, the multimode resource constrained project scheduling problem is chosen as the test sample data, a number of metaheuristic optimization algorithms such as the particle swarm optimization, simulated annealing, tabu search, and artificial bee swarm, are used as the recommended algorithms, and the multiclassification strategy of support vector machine is applied to achieve algorithm classification recommendation. Crossvalidation results show that the recommendation accuracy exceeds 90% and the evaluation indicators perform well.
 

Key words: algorithm recommendation, problem feature, multiclassification support vector machine, multimode resource constrained project scheduling problem