以基因演算法設計繞射光學元件 之交配機制研究

The Study of Crossover Mechanism of Genetic Algorithm for Diffractive Optical Elements

侯采君(Tsai-Chun Hou)

指導教授 ： 徐巍峰

國立臺北科技大學/機電學院/光電工程系所/碩士(2007年)

摘要

基因演算法中，一般認為交配機制比突變機制更為重要，然而目前以基因演算法設計繞射光學元件所得結果卻非如此，模擬結果發現僅以交配機制的演化結果遠低於突變機制，因此我們在基因演算法中完全除去突變機制，純粹以交配機制來進行演化，本論文即深入的探討此一結果，希望能藉由設計新的實驗方法來釐清交配機制(包括交配圖形和交配頻率)在基因演算法中的意義和重要性。主要妨礙本研究的問題為族群純化問題，所以本論文目是為清楚了解族群純化的問題，並找出適當的交配運算方式，。
本研究中，我們發現在固定使用同個交配圖形下加入一種子個體，族群在20世代左右就會完全純化，若能在族群未完全純化時就改變交配圖形，可以促進族群的演化，但經過相當的世代後(約1000世代)，族群的純化也會達相當高的程度而減緩演化的進行，因此，我們採取族群回填方式更新族群個體，以便觀察交配運算對演化的影響。我們共設計了五種交配圖形系列以進行動態式交配運算，在經過十萬世代後，發現圓盤及方形系列有較佳的演化結果，因為圓盤與方形交配圖形能隨著圖形的變換而改變交配像素的多寡，為影響評估函數好壞的主要原因。

關鍵字

繞射光學元件 ； 基因演算法 ； 族群回填 ； 動態變換式交配圖形 ； 交配像素

並列摘要

In the genetic algorithm, it is generally acknowledged the crossover mechanism is even more important than the mutation mechanism. However, the crossover mechanism did not increase the performance of phase-only diffractive optical elements(DOEs) as expected in our early study. In order to identify the effect of the crossover mechanism.
we removed the mutation mechanism and only used only the crossover mechanism to simulate the evolution to design the DOEs. The simulation results of evolution for the crossover mechanism were poor compared with the mutation mechanism, which was different from this algorithm applying to other problems. We believe the main reason of the poor result by only using the crossover mechanism is the population-purity. Therefore, in this thesis, we analyzed the population-purification situation and different crossover mechanism for designing the diffractive optical elements in using the genetic algorithm.
In this research, by using a regular crossover pattern and by adding a seed individual of best performance in the population, we found the populations were completely purified (individuals of the population all become the same) in about 20 generations. By dynamically changing the crossover patterns, the population was purified in hundreds to thousands generations. Therefore, we used a method of the population reload every 1000 generations in order to analyze the effect of different crossover patterns. In the population-reload method, the crossover pattern was changed every 10 generations, the initial population replaced the purified population every 1000 generations, and a total 100,000 generations of the GA revolution. Then, 5 different designs of crossover pattern of random parameters were designed to compare the performance of the binary-phase DOEs. No significant improvement of performance was observed in the simulation results when the number of exchanged pixels was about a half of the total pixels. However, the performance of the DOEs was significantly increased when the number of exchanged pixels decreased, or even increased. Consequently, according to the simulation results obtained in this study, we believe that the spatial location of the exchanged pixels of the crossover mechanism influenced the DOE performance more significantly than the number and pattern of the exchanged pixels.

並列關鍵字

diffractive optical elements (DOEs) ； genetic algorithm(GA) ； population- reload ； population-purification ； movement crossover figure

參考文獻

[1] A. Sommerfeld, Optics, Volume IV of Lectures on Theoretical Physics, New York: Academic Press, 1954.

[3] N. Yoshikawa, M. Iton, and T. Yatagai, “Quantized Phase Optimization of Two-Dimensional Fourier Kinoforms by a Genetic Algorithm,” Isntitute of Applied Physics, University of Tsukuba, 305, Japan,1994.

[4] T. -A. Nguyen, J. -W. An, J. K. Choi, N. Kim, S. H. Jeon, and Y. S. Kwon, “Hybrid Algorithm to Reduce the Computation Time of Genetic Algorithms for Designing Binary Phase Holograms,” Society of Photo-Optical Instrumentation Engineers, 2004.

[7] W. M. Spears, “A Study of Crossover Operators in Genetic Programming,” International Symposium on Methodologies for Intelligent System, pp.409-418, 1993.

[8] M. Mitchell, “An Introduction to Genetic Algorithms,” Third printing, MIT Press.