臺灣博碩士論文加值系統

遺傳演算法（Genetic Algorithm, GA）是一個非常重要且有效的最佳化工具，由於它具有全域搜尋的能力，且其搜尋結果不易受初始猜測值的影響。遺傳演算法屬多點搜尋的方式，針對多個物種構成的族群進行選種（複製）、交配、突變的運算，以達到適者生存。然而多點搜尋所伴隨而來的代價就是計算量的倍數增加，因此如何增進GA的搜尋效率以節省計算時間，是十分重要的研究課題。 本論文率先提出使用機率分布函數應用於遺傳演算法的交配、突變運算子中，藉以改善傳統遺傳演算法在最佳化過程的效率。這包含避開局部最佳解搜尋全域最佳解的能力，以及最佳化搜尋的速度。在遺傳演算法作最佳化的搜尋過程中，須將所要作最佳化函數的變數予以編碼。編碼之後最左邊的位元，為最大有效位元（MSB，most significant bit），最右邊的位元為最小有效位元（LSB，least significant bit）。對於編碼後的數值而言，愈靠近MSB的各個位元，對於數值本身的正確與否影響愈大，而靠近LSB附近的各個位元，僅影響數值的精確度。且較靠近MSB的位元值的改變，將使該物種在搜尋空間作較大範圍的改變，而LSB附近的位元值的改變，僅使該物種在搜尋空間做小範圍的改變。 在傳統遺傳演算法的交配與突變兩項運算中，並未考慮到各個位元對於物種改變的影響並不相同，也就是說，在交配與突變的過程中，每個位元發生交配或突變的機率是相同的。 本論文特引進非均勻機率密度函數於交配與突變兩項運算中。其目的乃在族群的最佳物種與實際最佳解距離尚遠時，使GA能在MSB附近有較高的交配與突變機率，以進行較大範圍的搜尋以避開局部次佳解。而當搜尋至最佳解附近時，使GA在LSB附近有較高的交配與突變機率，以加速收斂至最佳解。且為建立適當機制，使得機率分布最大值的所在點能適當的移動，本論文提出循環式GA及自適性GA兩種方法並測試其效率，吾人發現，兩者對於各種不同特性的函數，皆能避開局部最佳解，搜尋到全域最佳解，即使對於傳統遺傳演算法能成功收斂的函數，本論文的方法也確實可大幅增加其收斂速度。

Genetic Algorithm is a very important and effective optimizer because of its global searching capability. In this decade, Genetic Algorithms are applied in various problems in many disciplines. In general, the searching result does not depend on the initial guess since GA searches multiple points simultaneously, for which three operators (named as selection, crossover and mutation) are applied on some randomly generated initial population consisting of many individuals to achieve the goal of survival of the fittest. However, the price paid for the multiple-point searching scheme is the increase of computation time. Hence, various techniques are continuously proposed to improve the computational efficiency, which is quite important for GA. In this thesis, the non-uniform probability density functions are first employed in the crossover and mutation operators of GA during the course of searching to improve the computational efficiencies. The capability of escaping from local optima is improved such that the global optimum can be easily achieved. In addition, the convergence speed is also raised. Consider the fact that the parameters are encoded during the course of optimization using GA. After encoding, the most left hand side bit is the most significant bit MSB, while, the most right hand side bit is the least significant bit LSB. It is recognized that the correctness of those bits about the MSB determines the correctness of the parameters. The correctness of those bits about the LSB only determines the precision of the parameters. On the other hand, the changes of those bits near MSB imply a large range searching in parameter space, while, the changes of those bits near LSB imply a small range searching in parameter space. For the crossover and mutation operators of a classical GA, the weighting difference of different bits are not recognized and implemented. That is, the probability of crossover and mutation for each bit is the same in a classical GA. In this thesis, some non-uniform probability density functions are first introduced for the crossover and mutation operators. One objective is to enhance the crossover and mutation probability for the bits near MSB region when the best individual of current generation is still far from the global optimum region. This certainly would increase the escaping capability of GA from the local optimum. The other objective is to enhance the crossover and mutation probability for the bits near LSB region when the best individual of current generation is near the global optimum region. This would increase the convergence speed. In order to achieve the above objectives some mechanisms are required to suitably move the probability density functions. Therefore, two mechanisms are proposed, called Cyclical GA and Adaptive GA, in this thesis, and their efficiency improvements are checked. We found both GAs work for different testing functions, including those that are hard to converge for classical GA.

第一章 簡介................................1
1-1 研究動機與相關研究結果...............1
1-2 本論文的研究結果及貢獻...............2
1-3 論文架構.............................2
第二章 機率密度函數在遺傳演算法之應用......4
2-1 簡介.................................4
2-2 遺傳演算法...........................4
2-3 機率密度函數的介紹及應用.............9
2-4 測試函數簡介.........................12
第三章 機率密度函數循環式遺傳演算法.......30
3-1 機率密度函數之循環...................30
3-2 數值模擬.............................32
3-3 結論.................................35
第四章 適應式遺傳演算法(Adaptive GA).......59
4-1 自我調適R點........................59
4-2 數值模擬.............................61
4-3 結論..................................64
第五章 結論................................81

[1] J. Michael Johnson and Yahya Rahmat-Samii, “Genetic Algorithms in Engineering Electromagnetics,” IEEE Antennas and Propagation Magazine, Vol. 39, No. 4, pp. 7-24, August 1997.
[2] Randy L. Haupt, “An Introduction to Genetic Algorithms for Electromagnetics,” IEEE Antennas and Propagation Magazine, Vol. 37, No. 2, pp. 7-15, April 1995.
[3] Jong-Hwan Kim, Jeong-Yeol Jeon, and Kwangill Koh, “A Novel Evolutionary Algorithms with Fast Convergence,” Evolutionary Computation, IEEE International Conference, Vol. 1, p. 228-233, 1995.
[4] Thomas Bäck, Evolutionary Algorithms in Theory and Practice, Oxford University Press, 1996.
[5] R. L. Haupt, “Thinned arrays using genetic algorithms,” IEEE Transactions on Antennas and Propagation, AP-42, p. 993-99,7, July, 1994.
[6] R. L. Haupt, “Optimization of array antennas using genetic algorithms,” Proceedings of the Progress in Electromagnetics Research Symposium, Noordwijk, The Netherlands, p. 172, 1994.
[7] J. F. Frenzel, “Genetic algorithms a new breed of optimization,” IEEE Potentials, pp. 21-24, October 1993.
[8] J.M. Johnson and Y. Rahmat-Samii, “Genetic Algorithm Optimization and its Application to Antenna Design,” IEEE Antennas and Propagation Society International Symposium Digest, pp. 326-329,June 19-24,1994.
[9] D. E. GoldBerg, Genetic Algorithms in Search, Optimization and Machine Learning, New York, Addison-Wesley, 1989.
[10] G. Sywerda, “Uniform Crossover in Genetic Algorithms,” in J.D. Schaffer (ed.), Proceedings of the Third International Conference on Genetic Algorithms and Their Applications, paper 2-9, June 1989.
[11] D. E. Gold berg, and K. Deb, “A Comparative Analysis of Selection Schemes Used in Genetic Algorithms,” Foundations of Genetic Algorithms, pp. 69-93,1991.