A High-Performance Genetic Algorithm: Using Traveling Salesman Problem as a Case
This paper presents a simple but efficient algorithm for reducing the computation time of genetic algorithm (GA) and its variants. The proposed algorithm is motivated by the observation that genes common to all the individuals of a GA have a high probability of surviving the evolution and ending up...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2014-01-01
|
| Series: | The Scientific World Journal |
| Online Access: | http://dx.doi.org/10.1155/2014/178621 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832555384985878528 |
|---|---|
| author | Chun-Wei Tsai Shih-Pang Tseng Ming-Chao Chiang Chu-Sing Yang Tzung-Pei Hong |
| author_facet | Chun-Wei Tsai Shih-Pang Tseng Ming-Chao Chiang Chu-Sing Yang Tzung-Pei Hong |
| author_sort | Chun-Wei Tsai |
| collection | DOAJ |
| description | This paper presents a simple but efficient algorithm for reducing the computation time of genetic algorithm (GA) and its variants. The proposed algorithm is motivated by the observation that genes common to all the individuals of a GA have a high probability of surviving the evolution and ending up being part of the final solution; as such, they can be saved away to eliminate the redundant computations at the later generations of a GA. To evaluate the performance of the proposed algorithm, we use it not only to solve the traveling salesman problem but also to provide an extensive analysis on the impact it may have on the quality of the end result. Our experimental results indicate that the proposed algorithm can significantly reduce the computation time of GA and GA-based algorithms while limiting the degradation of the quality of the end result to a very small percentage compared to traditional GA. |
| format | Article |
| id | doaj-art-8ab01e916a124287bd3b1e45735278c6 |
| institution | Kabale University |
| issn | 2356-6140 1537-744X |
| language | English |
| publishDate | 2014-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | The Scientific World Journal |
| spelling | doaj-art-8ab01e916a124287bd3b1e45735278c62025-02-03T05:48:21ZengWileyThe Scientific World Journal2356-61401537-744X2014-01-01201410.1155/2014/178621178621A High-Performance Genetic Algorithm: Using Traveling Salesman Problem as a CaseChun-Wei Tsai0Shih-Pang Tseng1Ming-Chao Chiang2Chu-Sing Yang3Tzung-Pei Hong4Department of Computer Science and Engineering, National Sun Yat-sen University, Kaohsiung 80424, TaiwanDepartment of Computer Science and Engineering, National Sun Yat-sen University, Kaohsiung 80424, TaiwanDepartment of Computer Science and Engineering, National Sun Yat-sen University, Kaohsiung 80424, TaiwanDepartment of Electrical Engineering, National Cheng Kung University, Tainan 70101, TaiwanDepartment of Computer Science and Engineering, National Sun Yat-sen University, Kaohsiung 80424, TaiwanThis paper presents a simple but efficient algorithm for reducing the computation time of genetic algorithm (GA) and its variants. The proposed algorithm is motivated by the observation that genes common to all the individuals of a GA have a high probability of surviving the evolution and ending up being part of the final solution; as such, they can be saved away to eliminate the redundant computations at the later generations of a GA. To evaluate the performance of the proposed algorithm, we use it not only to solve the traveling salesman problem but also to provide an extensive analysis on the impact it may have on the quality of the end result. Our experimental results indicate that the proposed algorithm can significantly reduce the computation time of GA and GA-based algorithms while limiting the degradation of the quality of the end result to a very small percentage compared to traditional GA.http://dx.doi.org/10.1155/2014/178621 |
| spellingShingle | Chun-Wei Tsai Shih-Pang Tseng Ming-Chao Chiang Chu-Sing Yang Tzung-Pei Hong A High-Performance Genetic Algorithm: Using Traveling Salesman Problem as a Case The Scientific World Journal |
| title | A High-Performance Genetic Algorithm: Using Traveling Salesman Problem as a Case |
| title_full | A High-Performance Genetic Algorithm: Using Traveling Salesman Problem as a Case |
| title_fullStr | A High-Performance Genetic Algorithm: Using Traveling Salesman Problem as a Case |
| title_full_unstemmed | A High-Performance Genetic Algorithm: Using Traveling Salesman Problem as a Case |
| title_short | A High-Performance Genetic Algorithm: Using Traveling Salesman Problem as a Case |
| title_sort | high performance genetic algorithm using traveling salesman problem as a case |
| url | http://dx.doi.org/10.1155/2014/178621 |
| work_keys_str_mv | AT chunweitsai ahighperformancegeneticalgorithmusingtravelingsalesmanproblemasacase AT shihpangtseng ahighperformancegeneticalgorithmusingtravelingsalesmanproblemasacase AT mingchaochiang ahighperformancegeneticalgorithmusingtravelingsalesmanproblemasacase AT chusingyang ahighperformancegeneticalgorithmusingtravelingsalesmanproblemasacase AT tzungpeihong ahighperformancegeneticalgorithmusingtravelingsalesmanproblemasacase AT chunweitsai highperformancegeneticalgorithmusingtravelingsalesmanproblemasacase AT shihpangtseng highperformancegeneticalgorithmusingtravelingsalesmanproblemasacase AT mingchaochiang highperformancegeneticalgorithmusingtravelingsalesmanproblemasacase AT chusingyang highperformancegeneticalgorithmusingtravelingsalesmanproblemasacase AT tzungpeihong highperformancegeneticalgorithmusingtravelingsalesmanproblemasacase |