基于多标签k近邻方法实现元启发式算法的排名推荐

设计并研究一种基于多标签k近邻方法(multi-label k-nearest neighbor, ML-k NN)推荐元启发式算法的实现框架.应用多标签k近邻分类学习技术,实现最佳元启发式算法的排名推荐.为了验证效果,以多模式资源约束项目调度问题(MRCPSP)为优化对象,选取不同规模的数百个算例分别提取问题基本特征和地标特征;选用遗传、粒子群、禁忌搜索、蜂群和蚁群5种元启发式算法,使用ML-k NN建立元推荐模型;利用海明损失、单错误率、覆盖率、排位损失和平均准确率5个指标对推荐效果做出分析和评价.实验结果表明,基于ML-k NN方法推荐元启发式算法效果突出,其中基于地标特征的单错误率指标为18.4%,平均准确率达到88.9%.相对于k NN方法, MLk NN取得了更好的推荐结果.此外, ML-k NN方法可以实现对所有备选算法的排名推荐,该研究结论有望推广应用于其他组合优化问题的优化算法推荐.

Ranking recommendation to implement meta-heuristic algorithm based on multi-label k-nearest neighbor method

This paper designs and studies the implementation framework of a recommendation meta-heuristic algorithm based on the multi-label k-nearest neighbor(ML-kNN). The multi-label k-nearest neighbor classification learning technology is applied to implement the best meta-heuristic algorithm ranking recommendation. In order to verify the effect, the multi-modal resource-constrained project scheduling problem(MRCPSP) is taken as the optimization object, and hundreds of examples of different scales are selected to extract landmarking features and problem basic features respectively; five meta-heuristic algorithms(genetics, particle swarm, tabu search, bee colony and ant colonies) are selected; the ML-kNN is applied to establish a meta-recommendation model; and the Hamming loss, single error rate, coverage rate, ranking loss and average accuracy rate are used to analyze and evaluate the recommendation effect. The experimental results show that the meta-heuristic algorithm based on ML-kNN recommendation is effective, among which, the single error rate of the ML-kNN based on landmarking features is 18.4%, and the average precision is 88.9%. The ML-kNN had been acquired the better recommendation effect in relative with the single label kNN. In addition, the ML-kNN method is able to achieve the ranking recommendations for all alternative algorithms. The research conclusions are expected to be extended to other combinatorial optimization algorithms.