University of Science and Technology Beijing
本文设计并实证研究了一种基于多标签k近邻方法(Multi-Label k-Nearest Neighbor, ML-kNN)推荐元启发式算法的实现框架.应用多标签k近邻分类学习技术,实现了最佳元启发式算法的排名推荐.为了验证效果,以多模式资源约束项目调度问题(MRCPSP)为优化对象,选取不同规模的数百个算例分别提取地标特征和问题基本特征;选用遗传、蚁群、粒子群、蜂群和禁忌搜索5种元启发式算法;使用ML-kNN建立元推荐模型;利用海明损失、单错误率、覆盖率、排位损失和平均准确率5个指标对推荐效果做出分析和评价.实验结果表明基于ML-kNN方法推荐元启发式算法效果突出.其中基于地标特征的单错误率指标为18.4%,平均准确率达到88.9%.相对于kNN方法, ML-kNN取得了更好的推荐结果.此外, ML-kNN方法可实现对所有备选算法的排名推荐.该研究结论有望推广应用到其他组合优化问题的优化算法推荐.
This paper designed and empirically studied 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 was 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) was taken as the optimization object, and hundreds of examples of different scales were selected to extract landmarking features and problem basic features respectively; five meta-heuristic algorithms (genetics, ant colonies, particle swarm, bee colony and tabu search) were selected; the ML-kNN was applied to establish a meta-recommendation model; and the Hamming loss, single error rate, coverage rate, ranking loss and average accuracy rate had been put to use to analyze and evaluate the recommendation effect. The experimental results showed that the meta-heuristic algorithm based on ML-kNN recommendation was effective. Among them, the single error rate of ML-kNN based on landmarking features was 18.4%, and the average precision was 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 was able to achieve the ranking recommendations for all alternative algorithms. The research conclusions were expected to be extended to other combinatorial optimization algorithms.