Loading...
Please wait, while we are loading the content...
Similar Documents
A Genetic Algorithm for a Hamiltonian Path Problem
| Content Provider | Scilit |
|---|---|
| Author | de León, Eunice Ponce Ochoa, Alberto Santana, Roberto |
| Copyright Year | 2020 |
| Description | The genetic algorithm (GA) is one of the stochastic search techniques with application to a wide variety of combinatorial optimization problems. A conjecture of I. Hàvel, also attributed to P. Erdös, asserts that the simple graph G(k+1) (k>0), whose vertices are the subsets of cardinalities k and k+1 of the set {0,…,2k} and whose adjacency is given by subset inclusion, is Hamiltonian. The search of a Hamiltonian cycle in this graph is reduced to find a Hamiltonian path in the multi-level graph. In this paper we describe a GA approach to this conjecture. We present theoretical and computational results which show that this GA approach finds the optimal solutions when we search path for each level of the graph. We introduce an evolutive fitness function, and discuss the impact of using non standard crossover operators. Seeding and adaptive mutation rate are used. Hamiltonian cycles in G(6) and G(7) are constructed. Book Name: Industrial and Engineering Applications of Artificial Intelligence and Expert Systems |
| Related Links | https://api.taylorfrancis.com/content/chapters/edit/download?identifierName=doi&identifierValue=10.1201/9780429332197-3&type=chapterpdf |
| Ending Page | 19 |
| Page Count | 7 |
| Starting Page | 13 |
| DOI | 10.1201/9780429332197-3 |
| Language | English |
| Publisher | Informa UK Limited |
| Publisher Date | 2020-01-08 |
| Access Restriction | Open |
| Subject Keyword | Book Name: Industrial and Engineering Applications of Artificial Intelligence and Expert Systems Obstetrics and Gynecology Optimal Adaptive Hamiltonian Algorithm Evolutive Function Conjecture |
| Content Type | Text |
| Resource Type | Chapter |
