Tsai Chun-Wei, Tseng Shih-Pang, Chiang Ming-Chao, Yang Chu-Sing, Hong Tzung-Pei
Department of Computer Science and Engineering, National Sun Yat-sen University, Kaohsiung 80424, Taiwan ; Department of Applied Informatics and Multimedia, Chia Nan University of Pharmacy & Science, Tainan 71710, Taiwan.
Department of Computer Science and Engineering, National Sun Yat-sen University, Kaohsiung 80424, Taiwan.
ScientificWorldJournal. 2014;2014:178621. doi: 10.1155/2014/178621. Epub 2014 May 5.
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.
本文提出了一种简单而高效的算法，用于减少遗传算法（GA）及其变体的计算时间。该算法的灵感来源于这样一个观察结果：GA中所有个体共有的基因在进化过程中具有很高的存活概率，并最终成为最终解决方案的一部分；因此，可以将这些基因保存起来，以消除GA后续世代中的冗余计算。为了评估所提出算法的性能，我们不仅用它来解决旅行商问题，还对其可能对最终结果质量产生的影响进行了广泛分析。我们的实验结果表明，与传统GA相比，所提出的算法可以显著减少GA和基于GA的算法的计算时间，同时将最终结果质量的下降限制在非常小的百分比范围内。
