基于多分类支持向量机的优化算法智能推荐系统与实证分析
|
摘要
算法智能推荐是超启发式算法研究领域一个重要分支,其目标是从众多"在线"算法中自动选择出最适于当前问题的算法,从而大大提升解决问题的效率。基于此提出并验证了一种优化算法智能推荐系统,理论依据是无免费午餐定理和Rice算法选择框架,并假设问题特征与算法性能表现之间存在潜在关联关系,从而可以把算法推荐问题转换为一个多分类问题。为了验证假设的成立,以多模式资源约束项目调度问题为测试样本数据集,以粒子群、模拟退火、禁忌搜索和人工蜂群等元启发式优化算法为推荐对象,以支持向量机多分类策略实现算法的分类推荐。交叉验证结果表明,推荐准确率均在90%以上,各项评价指标表现优秀。
Intelligent algorithm recommendation is an important branch of the research field of hyperheuristic 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.
Intelligent algorithm recommendation is an important branch of the research field of hyperheuristic 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.
引文
[1]Chen Wang,Shi Yan-jun,Teng Hong-fei,et al.An efficient hybrid algorithm for resource-constrained project scheduling[J].Information Sciences,2010,180(6):1031-1039.
[2]Wolpert D H,Macready W G.No free lunch theorems for optimization[J].IEEE Transactions on Evolutionary Computation,1997,1(1):67-82.
[3]Rice J R.The algorithm selection problem[J].Advances in Computers,1976,15(2):65-118.
[4]Burke E K,Gendreau M,Hyde M,et al.Hyper-heuristics:Asurvey of the state of the art[J].Journal of the Operational Research Society,2013,64(12):1695-1724.
[5]Lindauer M,Hoos H H,Hutter F,et al.AutoFolio:An automatically configured algorithm selector[J].Journal of Artificial Intelligence Research,2015,53(1):745-778.
[6]Cui C,Hu M Q,Weir J D,et al.A recommendation system for meta-modeling:A meta-learning based approach[J].Expert Systems with Applications,2016,46(C):33-44.
[7]Morgan R,Gallagher M.Fitness landscape analysis of circles in a square packing problems[C]∥Proc of the 10th International Conference on Simulated Evolution and Learning,2014:455-466.
[8]Silverthorn B,Miikkulainen R.Latent class models for algorithm portfolio methods[C]∥Proc of the 24th AAAI Conference on Artificial Intelligence,2010:167-172.
[9]Smith-Miles K A.Cross-disciplinary perspectives on metalearning for algorithm selection[J].ACM Computing Surveys,2008,41(1):Article No.6.
[10]Rendell L,Cho H.Empirical learning as a function of concept character[J].Machine Learning,1990,5(3):267-298.
[11]Aha D W.Generalizing from case studies:A case study[C]∥Proc of the 9th International Workshop on Machine Learning,1992:1-10.
[12]Carrier C G,Vilalta R,Brazdil P.Introduction to the special issue on meta-learning[J].Machine Learning,2004,54(3):187-193.
[13]King R D,Feng C,Sutherland A.Statlog:Comparison of classification algorithms on large real-world problems[J].Applied Artificial Intelligence,1995,9(3):289-333.
[14]Cui C,Wu T,Hu M,et al.Short-term building energy model recommendation system:A meta-learning approach[J].Applied Energy,2016,172(15):251-263.
[15]Messelis T,de Causmaecker P.An automatic algorithm selection approach for the multi-mode resource-constrained project scheduling problem[J].European Journal of Operational Research,2014,233(3):511-528.
[16]Miranda P B C,Prudencio R B C,de Carvalho A P L F,et al.A hybrid meta-learning architecture for multi-objective optimization of SVM parameters[J].Neurocomputing,2014,143:27-43.
[17]Smith-Miles K,Lopes L.Measuring instance difficulty for combinatorial optimization problems[J].Computers&Operations Research,2012,39(5):875-889.
[18]Cui Jian-shuang,Liu Xiao-chan,Yang Mei-hua.A metalearning based intelligent recommendation framework for optimization algorithm automatic selection and its empirical study[J].Journal of Computer Applications,2017,37(4):1105-1110.(in Chinese)
[19]Bhatt N,Thakkar A,Ganatra A.A survey¤t research challenges in meta-learning approaches based on dataset characteristics[J].International Journal of Soft Computing and Engineering,2012,2(1):239-247.
[20]Cui Jian-shuang,Yang Jian-hua.Multi-resource constrained project scheduling problems with discrete particle swarm optimization[J].Computer Engineering and Applications,2015,51(14):253-257.(in Chinese)
[21]Chang C C,Lin C J.LIBSVM:A library for support vector machines[J].ACM Transactions on Intelligent Systems and Technology,2011,2(3):Article No.27.
[22]Cortes C,Vapnik V.Support-vector networks[J].Machine Learning,1995,20(7):273-297.
[23]Duan K B,Rajapaks J C,Nguyen M N.One-versus-one and one-versus-all multiclass SVM-RFE for gene selection in cancer classification[M]∥Lecture Notes in Computer Science,Berlin Heidelberg:Springer-Verlag,2007.
[18]崔建双,刘晓婵,杨美华.基于元学习推荐的优化算法自动选择框架与实证分析[J].计算机应用,2017,37(4):1105-1110.
[20]崔建双,杨建华.多资源约束的项目调度问题离散粒子群算法[J].计算机工程与应用,2015,51(14):253-257.
[2]Wolpert D H,Macready W G.No free lunch theorems for optimization[J].IEEE Transactions on Evolutionary Computation,1997,1(1):67-82.
[3]Rice J R.The algorithm selection problem[J].Advances in Computers,1976,15(2):65-118.
[4]Burke E K,Gendreau M,Hyde M,et al.Hyper-heuristics:Asurvey of the state of the art[J].Journal of the Operational Research Society,2013,64(12):1695-1724.
[5]Lindauer M,Hoos H H,Hutter F,et al.AutoFolio:An automatically configured algorithm selector[J].Journal of Artificial Intelligence Research,2015,53(1):745-778.
[6]Cui C,Hu M Q,Weir J D,et al.A recommendation system for meta-modeling:A meta-learning based approach[J].Expert Systems with Applications,2016,46(C):33-44.
[7]Morgan R,Gallagher M.Fitness landscape analysis of circles in a square packing problems[C]∥Proc of the 10th International Conference on Simulated Evolution and Learning,2014:455-466.
[8]Silverthorn B,Miikkulainen R.Latent class models for algorithm portfolio methods[C]∥Proc of the 24th AAAI Conference on Artificial Intelligence,2010:167-172.
[9]Smith-Miles K A.Cross-disciplinary perspectives on metalearning for algorithm selection[J].ACM Computing Surveys,2008,41(1):Article No.6.
[10]Rendell L,Cho H.Empirical learning as a function of concept character[J].Machine Learning,1990,5(3):267-298.
[11]Aha D W.Generalizing from case studies:A case study[C]∥Proc of the 9th International Workshop on Machine Learning,1992:1-10.
[12]Carrier C G,Vilalta R,Brazdil P.Introduction to the special issue on meta-learning[J].Machine Learning,2004,54(3):187-193.
[13]King R D,Feng C,Sutherland A.Statlog:Comparison of classification algorithms on large real-world problems[J].Applied Artificial Intelligence,1995,9(3):289-333.
[14]Cui C,Wu T,Hu M,et al.Short-term building energy model recommendation system:A meta-learning approach[J].Applied Energy,2016,172(15):251-263.
[15]Messelis T,de Causmaecker P.An automatic algorithm selection approach for the multi-mode resource-constrained project scheduling problem[J].European Journal of Operational Research,2014,233(3):511-528.
[16]Miranda P B C,Prudencio R B C,de Carvalho A P L F,et al.A hybrid meta-learning architecture for multi-objective optimization of SVM parameters[J].Neurocomputing,2014,143:27-43.
[17]Smith-Miles K,Lopes L.Measuring instance difficulty for combinatorial optimization problems[J].Computers&Operations Research,2012,39(5):875-889.
[18]Cui Jian-shuang,Liu Xiao-chan,Yang Mei-hua.A metalearning based intelligent recommendation framework for optimization algorithm automatic selection and its empirical study[J].Journal of Computer Applications,2017,37(4):1105-1110.(in Chinese)
[19]Bhatt N,Thakkar A,Ganatra A.A survey¤t research challenges in meta-learning approaches based on dataset characteristics[J].International Journal of Soft Computing and Engineering,2012,2(1):239-247.
[20]Cui Jian-shuang,Yang Jian-hua.Multi-resource constrained project scheduling problems with discrete particle swarm optimization[J].Computer Engineering and Applications,2015,51(14):253-257.(in Chinese)
[21]Chang C C,Lin C J.LIBSVM:A library for support vector machines[J].ACM Transactions on Intelligent Systems and Technology,2011,2(3):Article No.27.
[22]Cortes C,Vapnik V.Support-vector networks[J].Machine Learning,1995,20(7):273-297.
[23]Duan K B,Rajapaks J C,Nguyen M N.One-versus-one and one-versus-all multiclass SVM-RFE for gene selection in cancer classification[M]∥Lecture Notes in Computer Science,Berlin Heidelberg:Springer-Verlag,2007.
[18]崔建双,刘晓婵,杨美华.基于元学习推荐的优化算法自动选择框架与实证分析[J].计算机应用,2017,37(4):1105-1110.
[20]崔建双,杨建华.多资源约束的项目调度问题离散粒子群算法[J].计算机工程与应用,2015,51(14):253-257.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |