The oil drilling model and iterative deepening genetic annealing algorithm for the traveling salesman problem
In this work, we liken the solving of combinatorial optimization problems under a prescribed computational budget as hunting for oil in an unexplored ground. Using this generic model, we instantiate an iterative deepening genetic annealing (IDGA) algorithm, which is a variant of memetic algorithms....
Saved in:
| Main Authors: | , |
|---|---|
| Format: | text |
| Language: | English |
| Published: |
Institutional Knowledge at Singapore Management University
2008
|
| Subjects: | |
| Online Access: | https://ink.library.smu.edu.sg/sis_research/240 https://ink.library.smu.edu.sg/context/sis_research/article/1239/viewcontent/OilDrillingModelTSP_2008_afv.pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Singapore Management University |
| Language: | English |
| Summary: | In this work, we liken the solving of combinatorial optimization problems under a prescribed computational budget as hunting for oil in an unexplored ground. Using this generic model, we instantiate an iterative deepening genetic annealing (IDGA) algorithm, which is a variant of memetic algorithms. Computational results on the traveling salesman problem show that IDGA is more effective than standard genetic algorithms or simulated annealing algorithms or a straightforward hybrid of them. Our model is readily applicable to solve other combinatorial optimization problems. |
|---|