改進針對基於模型之基因演算法的指數族群方法

Improving the Exponential Population Scheme for Model-Based Genetic Algorithms

林遠任(Yuen-Jen Lin)

指導教授 ： 于天立

國立臺灣大學/電機資訊學院/電機工程學研究所/碩士(2018年)

https://doi.org/10.6342/NTU201802888

摘要

在早期發展的基因演算法中有一些參數需要事先調整，這對無經驗的使用者來說是困難的。在最近的基於模型之基因演算法當中，大部分的參數均已被決定，因此近來有關無參數基因演算法的研究皆著重在族群大小上。本研究根基於指數族群方法，此方法每次皆將族群大小增為兩倍直到解令人滿意為止，另外此方法能夠適用在基於模型之基因演算法之上而不調整當中機制。本論文提出了三點對指數族群方法的修改，其中包括為了避免基於模型之基因演算法冗長探索的新終結族群規則、經過優化可以使族群大小成長更有效率的族群乘數、以及一個使用之前族群資訊的方法。在本論文中亦給出關於新終結族群規則以及族群乘數優化的理論分析。當使用在數種基於模型之基因演算法上時，實驗顯示這些修改在大部分情形下可以減少指數族群方法所需之適應分數評估次數。

關鍵字

無參數基因演算法 ； 調整族群大小 ； 指數族群方法 ； 族群乘數

並列摘要

There are some parameters required to be tuned in early development of genetic algorithms. The tuning process is difficult for inexperienced users. In modern model-based genetic algorithms (MBGAs), most of these parameters are pre-determined, and therefore recent research concerning parameterless genetic algorithms targets at population size. This work is based on the exponential population scheme (EPS), which doubles the population until the solutions are satisfactory and is applicable to MBGAs without modifying their internal processes. In the thesis, three modifications to EPS are proposed. They are a new population termination criterion to prevent MBGAs from long exploration, an optimized population multiplier to grow the population size more efficiently and a method that reuses the information from the previous population respectively. Theoretical analyses of the new termination criterion and the optimized population multiplier are given. These modifications empirically reduce required number of function evaluations of EPS on several MBGAs in most cases.

並列關鍵字

parameterless genetic algorithm ； population sizing ； exponential population scheme ； population multiplier

參考文獻

[1] C.-H. Chang and T.-L. Yu. Investigation on parameterless schemes for DSMGA-II. In Proceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion, GECCO ’16 Companion, pages 85–86, New York, NY, USA, 2016. ACM.

[2] P.-L. Chen, C.-J. Peng, C.-Y. Lu, and T.-L. Yu. Two-edge graphical linkage model for DSMGA-II. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO ’17, pages 745–752, New York, NY, USA, 2017. ACM.

[3] D. M. Chickering, D. Heckerman, and C. Meek. A bayesian approach to learning bayesian networks with local structure. In Proceedings of the Thirteenth Conference on Uncertainty in Artificial Intelligence, UAI’97, pages 80–89, San Francisco, CA, USA, 1997. Morgan Kaufmann Publishers Inc.

[4] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Dynamic tables. Introduction to Algorithms (3nd ed.), pages 463–471, 2009.

[5] D. E. Goldberg, K. Sastry, and T. Latoza. On the supply of building blocks. In Proceedings of the 3rd Annual Conference on Genetic and Evolutionary Computation, GECCO ’01, pages 336–342, San Francisco, CA, USA, 2001. Morgan Kaufmann Publishers Inc.