多重評估之基因演算法機制-應用於最佳化問題

本研究提出了一種建構於基因演算法上的新演算法，名為多重評估之基因演算法機制。藉由模擬基因工程，本研究使用染色體內部之基因進行多次的優劣判斷和基因之繼承機制去改良演算法的探索能力。基因多重評估機制可以針對染色體之內部基因進行彼此間的影響評估，之後並運用在交配和突變運作元之上。而另外提出的繼承機制可以使較優良的基因值較穩漸的傳承給後代，而不易被重組的動作而破壞掉。此外為了改善多重評估之基因演算法機制對於數學最佳化問題的效能和穩定度，另外再提出置換式多重評估之基因演算法，藉由運用置換機制去改善在交配運作元中，基因評估的方式。而本研究會利用多個著名的數學最佳化問題去進行解決。此外也於其它學者所提出來的相關研究數據進行比較，以驗證本研究的效能。除了數學最佳化問題之外，本研究也將針對網路最佳化問題進行解決，使用多重評估之基因演算機制之邏輯概念，並搭配重新調整的個體結構，來進行演算法的實際應用。

關鍵字

基因演算法；多重路徑路由；綱要理論；基因評估

並列摘要

This thesis proposes a novel genetic algorithm, named a multiple-evaluation genetic algorithm (MEGA). By mimicking the genetic engineering on biological organisms, the MEGA uses gene-evaluation and inheritance mechanisms to improve both the exploration and exploitation abilities. The proposed gene-evaluation mechanism individually evaluates the influence of each gene and widely applies in the crossover and mutation operators. The proposed inheritance mechanism clones the characteristic of the ancestors and records on inheritance genes. To improve the MEGA the efficient in the numerical problems, we also proposes an replacement multiple-evaluation genetic algorithm (rMEGA). By applying statistic approach, the rMEGA uses replacement mechanism to improve both the efficient and stability abilities. Finally, the MEGA and rMEGA will solve several well-known numerical problems. Experimental results show that the proposed algorithm is more efficient and effective than several existing algorithms. Besides, we also apply for multiple routing problems. We renovate a new chromosome structure and use the proposed MEGA schema in the algorithm operation. And finally we practice the MEGA in multimedia services network routing problems and to fast determine the suitable routing path in some constrains.

並列關鍵字

Schema Theory ； Gene Evaluation ； Genetic Algorithms ； Multiple O-D Pairs Routing

參考文獻

[1] Holland, J.: Adaptation in Natural and Artificial Systems, The University of Michigan Press, Ann Arbor, MI, 1975.

[4] McCall, J.: Genetic algorithms for modelling and optimisation. Journal of Computational and Applied Mathematics, Vol. 184 (2005) 205-222

[7] Bendtsen, C. N., Krink, T.: Dynamic memory model for non-stationary optimization. In Proceedings of the 2002 Congress on Evolutionary Computation (CEC ’02) (2002) 145-150

[9] Yang, S.: Memory-based immigrants for genetic algorithms in dynamic environments. In Proceedings of Genetic and Evolutionary Computation Conference (GECCO ’05) (June 2005) 1115-1122

[10] Harik, G., Lobo, F. G., Goldberg, D. E.: The compact genetic algorithm. IEEE Trans. on Evolutionary Computation, Vol. 3 (Nov. 1999) 287-297

國際替代計量

多重評估之基因演算法機制-應用於最佳化問題

全文下載

主題瀏覽