The IRMA Community
Newsletters
Research IRM
Click a keyword to search titles using our InfoSci-OnDemand powered search:
|
Optimization of the Vertex Separation Problem with Genetic Algorithms
|
|
Author(s): Héctor J. Fraire Huacuja (Tecnológico Nacional de México, Instituto Tecnológico de Ciudad Madero, Mexico)and Norberto Castillo-García (Tecnológico Nacional de México, Instituto Tecnológico de Ciudad Madero, Mexico)
Copyright: 2016
Pages: 19
Source title:
Handbook of Research on Military, Aeronautical, and Maritime Logistics and Operations
Source Author(s)/Editor(s): Alberto Ochoa-Zezzatti (Juarez City University, Mexico), Jöns Sánchez (Consejo Nacional De Ciencie Y Tecnologia (CONACYT), Mexico), Miguel Gastón Cedillo-Campos (Transportation Systems and Logistics National Laboratory, Mexican Institute of Transportation, Mexico)and Margain de Lourdes (Polytechnic University of Aguascalientes, Mexico)
DOI: 10.4018/978-1-4666-9779-9.ch002
Purchase
|
Abstract
The Vertex Separation Problem (VSP) is an NP-hard combinatorial optimization problem in the context of graph theory. The importance of studying VSP lies in its close relation with other problems. Thus, VSP has important practical applications in the contexts of very large scale integration design, computer language compiler design, natural language processing, order processing of manufactured products and bioinformatics. Up to our knowledge, there are only two trajectory-based metaheuristic algorithms for VSP documented in the literature. The main contribution of this chapter is that we extend the available heuristics to solve VSP by proposing a genetic algorithm (GA). It is of particular interest to study the impact of four different crossover operators in the algorithm performance. The experimental results showed that the order-based crossover is the best. Moreover, the best GA variant was compared with the best algorithm for VSP: GVNS. The results of this comparison showed that GVNS outperforms our best GA variant by approximately 1.54 times in solution quality.
Related Content
|
Sonal Linda.
© 2024.
24 pages.
|
|
Yasmin Yousaf Mossa, Peter Smith, Kathleen Ann Bland.
© 2024.
40 pages.
|
|
Ugochukwu Okwudili Matthew, Jazuli Sanusi Kazaure, Charles Chukwuebuka Ndukwu, Godwin Nse Ebong, Andrew Chinonso Nwanakwaugwu, Ubochi Chibueze Nwamouh.
© 2024.
29 pages.
|
|
Shruti Jose, Priyakrushna Mohanty.
© 2024.
20 pages.
|
|
Richa Srishti.
© 2024.
15 pages.
|
|
Aleksei Alipichev, Liudmila Nazarova, Yana Chistova.
© 2024.
21 pages.
|
|
Mustafa Öztürk Akcaoğlu, Burcu Karabulut Coşkun.
© 2024.
18 pages.
|
|
|