Evolutionary operators for the Hamiltonian completion problem
- PDF / 394,446 Bytes
- 16 Pages / 595.276 x 790.866 pts Page_size
- 80 Downloads / 211 Views
(0123456789().,-volV)(0123456789(). ,- volV)
METHODOLOGIES AND APPLICATION
Evolutionary operators for the Hamiltonian completion problem Krunoslav Puljic´1 • Robert Manger2
Ó Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract This paper deals with evolutionary algorithms for solving the Hamiltonian completion problem. More precisely, the paper is concerned with a collection of crossover and mutation operators, which mostly originate from the traveling salesman problem, but have further on been modified or customized for Hamiltonian completion. The considered crossovers and mutations are tested on a set of randomly generated problem instances. The obtained experimental results clearly show that the behavior and relative ranking of the operators within the Hamiltonian completion environment are different than within the traveling salesman environment. Moreover, it is shown that our modified or custom-designed operator variants accomplish much better results for Hamiltonian completion than the standard variants. Keywords Hamiltonian completion Evolutionary algorithm Evolutionary operator Crossover Mutation Traveling salesman
1 Introduction In order to allow simpler presentation, we will restrict to directed graphs, although the whole material can very easily be adapted to undirected graphs. So let G be a directed graph with n vertices (Jungnickel 2013). We say that G is Hamiltonian if it contains a Hamiltonian cycle, i.e., a directed circular path that passes through each vertex exactly once. Suppose now that G is not necessarily Hamiltonian. Then the Hamiltonian completion problem (HCP) consists of finding the minimal number of arcs, which are not originally present in G but have to be added in order to make G Hamiltonian. The required minimal number of extra arcs is called the Hamiltonian completion number (HCN). The HCP is clearly NP-hard (Garey and Johnson 1979; Papadimitrou and Steiglitz 1998), since it allows solving Communicated by V. Loia. & Robert Manger [email protected] Krunoslav Puljic´ [email protected] 1
Faculty of Economics and Business, University of Zagreb, Trg J.F. Kennedyja 6, 10000 Zagreb, Croatia
2
Department of Mathematics, Faculty of Science, University of Zagreb, Bijenicˇka cesta 30, 10000 Zagreb, Croatia
the NP-complete problem of determining whether a given graph is Hamiltonian or not. Namely, a graph is Hamiltonian if and only if its HCN is equal to 0. Also, the HCP is closely related to the well-known traveling salesman problem (TSP) (Cook 2012; Gutin and Punnen 2007), where a complete graph is given with arc costs assigned, and a Hamiltonian cycle is sought whose total cost (sum of arc costs) is minimal. Indeed, the HCP can easily be reduced to the TSP in the following way. We add to the given graph G all missing arcs to make it complete. We assign costs so that the original arcs have cost 0 and the added arcs cost 1. We solve the TSP in the obtained complete graph. Then the optimal cycle for the TSP determines a solution for the HCP, i.e., the arcs within th
Data Loading...
