基因演算法中交配與突變交互作用之研究

Study of Interactive Effect of Crossover and Mutation of Genetic Algorithm

范姜智勇(Chih-Yung Fan Chiang)

指導教授 ： 徐巍峰

國立臺北科技大學/電資學院/光電工程系研究所/碩士(2008年)

https://doi.org/10.6841/NTUT.2008.00232

摘要

本論文的主旨是探討以基因演算法設計繞射光學元件時的交配和突變機制的交互影響。傳統的基因演算法通常在同一個世代中，交配與突變機制會一起進行，前人藉由改變交配機制或找尋最佳突變率來優化基因演算法在設計繞射光學元件上的效率提升，經由研究發現在以基因演算法設計最佳繞射光學元件上，同一世代同時啟動交配與突變機制，會對解空間造成一定的擾動，造成收斂較慢的現象。
在本論文的研究中，我們將交配和突變分開，不在同一世代中執行，在模擬像素32×32、像素48×48、像素64×64的繞射光學元件運算中，較大的突變率需要較多的交配世代會表現較好(使用繞射效率，均方根誤差，訊雜比三項評估參數評估)，而在較小的突變率時，需要較多的突變世代會表現較好。模擬結果顯示，在總像素平均隨機突變一點時，有較好的優化速度以及較好的最佳解。
在大部分的交配機制與突變機制交遞作用的情形與傳統基因演算法作比較，在前數百至數千世代數的演化，傳統基因演算法優化的速度較快，爾後優化速度幾乎都會被交配機制與突變機制交互作用的方式所超越，所以在利用基因演算法設計繞射光學元件時，交配機制與突變機制分開在不同世代運行是可行的。

關鍵字

繞射光學元件 ； 基因演算法 ； 交配機制 ； 突變機制

並列摘要

In this thesis, we study the effect of the interactive of the crossover and mutation of the genetic algorithm (GA) for optimization of design of the binary phase diffractive optical elements (DOEs). Both the crossover and mutation usually work in the same generation of the traditional GA. We changed the crossover system and find the optimal mutation rate of GA for optimization DOEs in early study. The crossover and the mutation working simultaneously slowed down the optimization processes because of making some certain disturbance in the solution space.
By way of the research analysis and the result, we find the interactive effect of crossover and mutation of GA in the simulation pixels 32×32, the pixels 48×48, and the pixels 64×64 DOEs. When the mutation rate was higher, the results were better with more crossover generations. When the mutation rate was lower, the results were better with more mutation generations. According to the analysis of the simulation results, the mutation rate to obtain the better results and the higher revolution speed was different. The boundary of the mutation rate to achieve these two goals was about equal to mutate one pixel in an individual.
By comparing with the interactive effect of crossover and mutation of GA and the traditional GA, the later worked better in the first hundreds to thousands generations. The interactive effect of crossover and mutation of GA optimized better than the traditional GA after early generations. Therefore, we can optimize DOEs by the interactive effect of crossover and mutation of GA.

並列關鍵字

diffractive optical elements ； genetic algorithm ； crossover system ； mutation system

參考文獻

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

[4]M. S. Kim and C. C. Guest,“Simulated annealing algorithm for binary phase only filters in pattern classification,”Applied optics,vol.29,no.8,1990.

[5]N. Yoshikawa and T. Yatagai,“Phase optimization of a Kinoform by simulated annealing,”Applied Optics,vol.33,no.5,1994.

[7] G. Zhou, Y. Chen, Z. Wang, and H. Song, “Genetic local search algorithm for optimization design of diffractive optical elements,” Appl. Opt. 38, pp. 4281-4290. (1999)

[8]侯采君，以基因演算法設計繞射光學元件之交配機制研究，碩士論文，國立臺北科技大學光電工程研究所，台北，2007