Genetic algorithm to optimize routing problem modelled as the travelling salesman problem
This study presents genetic algorithm (GA) to solve routing problem modelled as the travelling salesman problem (TSP). Genetic algorithm conceptually follows steps inspired by the biological process of evolution. GA is following the ideas of "survival of the fittest" which meant better...
| Main Author: | |
|---|---|
| Format: | Undergraduates Project Papers |
| Language: | English |
| Published: |
2013
|
| Subjects: | |
| Online Access: | http://umpir.ump.edu.my/id/eprint/7666/ http://umpir.ump.edu.my/id/eprint/7666/ http://umpir.ump.edu.my/id/eprint/7666/1/MUHAMMAD_AZRUL_FAIZ_BIN_NOR_ADZMI.PDF |
| Summary: | This study presents genetic algorithm (GA) to solve routing problem modelled as the
travelling salesman problem (TSP). Genetic algorithm conceptually follows steps
inspired by the biological process of evolution. GA is following the ideas of "survival
of the fittest" which meant better and better solution evolves from previous generations
until a near optimal solution is obtained. In TSP, There are cities and distance given
between the cities. The salesman needs to visit all the cities, but does not to travel so
much. This study will use PCB component placement which is modelled as TSP. The
objective is to find the sequence of the routing in order to minimize travelling distance.
The GA with Roulette wheel selection, linear order crossover and inversion mutation
is used in the study. The computational experiment was done using several randomly
generated data with different GA parameter setting. The optimal distance obtains for
40 component placements is 8.9861 mm within 6.751 seconds The results from the
experiments show that GA used in this study is effective to solve PCB component
placement which is modelled as TSP. |
|---|