A Novel, Evolutionary, Simulated Annealing inspired Algorithm for the Multi-Objective Optimization of Combinatorial Problems

详细信息	查看全文 | 推荐本文 |

• 作者：Elias D. Nino^a ; ^b ; ^enino@vt.edu ; ^{enino@uninorte.edu.co} ; Carlos J. Ardila^b ; ^{cardila@uninorte.edu.co} ; Anangelica Chinchilla^c
• 关键词：Combinatorial Optimization ; Genetic Algorithms ; Simulated Annealing ; Multi-objective Optimization
• 刊名：Procedia Computer Science
• 出版年：2012
• 期刊代码：pc74_18770509
• 类别：cp
• 出版时间：2012
• 卷：9
• 期：Complete
• 页码：1992-1998
• 文件大小：422 K

摘要

This paper states a novel hybrid-metaheuristic based on deterministic swapping, evolutionary algorithms and simulated annealing inspired algorithms for the multi-objective optimization of combinatorial problems. The proposed algorithm is named EMSA. It is an improvement of MODS algorithm. Unlike MODS, EMSA works using a search direction given by the assignation of weights to each objective function of the combinatorial problem to optimize. Lastly, EMSA is tested using well know instances of the Bi-Objective Traveling Salesman Problem (BTSP) from TSPLIB. Its results were compared with MODS metaheuristic (its predecessor). The comparison was made using metrics from the specialized literature such as Spacing, Generational Distance, Inverse Generational Distance and Non-Dominated Generation Vectors. In every case, the EMSA results on the metrics were always better and in some of those cases, the superiority was 100%.