Quantum inspired evolutionary algorithm for ordering problems

详细信息    查看全文

• 作者：Luciano Reis da Silveira ^{lucianoreisdasilveira@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Ricardo Tanscheit ^{ricardo@ele.puc-rio.br" class="auth_mail" title="E-mail the corresponding author} ; Marley M.B.R. Vellasco ; ^{marley@ele.puc-rio.br" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Quantum inspired evolutionary algorithm ; Ordering optimization problem ; Quantum bit ; Vehicle routing problem
• 刊名：Expert Systems with Applications
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：67
• 期：Complete
• 页码：71-83
• 全文大小：851 K

文摘

This paper proposes a new quantum-inspired evolutionary algorithm for solving ordering problems. Quantum-inspired evolutionary algorithms based on binary and real representations have been previously developed to solve combinatorial and numerical optimization problems, providing better results than classical genetic algorithms with less computational effort. However, for ordering problems, order-based genetic algorithms are more suitable than those with binary and real representations. This is because specialized crossover and mutation processes are employed to always generate feasible solutions. Therefore, this work proposes a new quantum-inspired evolutionary algorithm especially devised for ordering problems (QIEA-O). Two versions of the algorithm have been proposed. The so-called pure version generates solutions by using the proposed procedure alone. The hybrid approach, on the other hand, combines the pure version with a traditional order-based genetic algorithm. The proposed quantum-inspired order-based evolutionary algorithms have been evaluated for two well-known benchmark applications – the traveling salesman problem (TSP) and the vehicle routing problem (VRP) – as well as in a real problem of line scheduling. Numerical results were obtained for ten cases (7 VRP and 3 TSP) with sizes ranging from 33 to 101 stops and 1 to 10 vehicles, where the proposed quantum-inspired order-based genetic algorithm has outperformed a traditional order-based genetic algorithm in most experiments.