以調變式記憶規劃改善機率分佈估計演算法-以TSP問題為例

Adaptive Memory Programming for Improving Estimation of Distribution Algorithm - A Case Study on TSP

吳昕澧(Hsi-Li Wu)

指導教授 ： 尹邦嚴

國立暨南國際大學/管理學院/資訊管理學系/碩士(2012年)

https://doi.org/10.6837/NCNU.2012.00244

摘要

傳統基因演算法在處理變數間連結(Variable Linkage)時，會遇到好的基因砌塊(Building Blocks)被單點交配的交配方式破壞而無法保留，而新興的演化式演算法中的機率分佈估計演算法則利用統計的方式對母體空間內個體分佈建立機率模型，再由此機率模型抽樣產生下一代母體，取代傳統交配、突變的演化機制，以避免好的基因砌塊被破壞。本研究提出多個調變式記憶規劃改善機率分佈估計演算法，並以旅行銷售員問題(Traveling Salesman Problem)來實證分析，實驗結果顯示我們所提出的演算法比傳統的機率分佈估計演算法更有效率及效能。

關鍵字

基因砌塊 ； 機率分佈估計演算法 ； 機率模型 ； 遺傳演算法 ； 調變式記憶規劃

並列摘要

Traditional genetic algorithms are unable to preserve some variable linkage relationships because the performed crossover operation may destroy building blocks. Estimation of Distribution Algorithms (EDAs) are emerging approaches in evolutionary computation. EDA builds probability distributions based on individual instances maintained in current solution population. The next population is generated by sampling a number of instances from the built probability distributions, in contrast to the crossover and mutation mechanisms usually seen in genetic algorithms. This paper proposes several adaptive memory programming to improve EDA . We testify the performance of our algorithms on Traveling Salesman Problem. The experimental result shows that our algorithms are superior to the original EDA in terms of efficiency and effectiveness.

並列關鍵字

Building block ； estimation of distribution algorithm ； probabilistic model ； genetic algorithm ； adaptive memory programming strategy

參考文獻

參考文獻

Baluja, S.,& Davies, S., (1997), Using optimal dependency-trees for combinatorial optimization: Learning the structure of thesearch space., In: Proceedings of the 14th International Conference on Machine Learning.,30-38.

Baluja, S., (1994), Population Based Incremental Learning: A method for integrating genetic search based function optimization and competitive learning, Carnegie Mellon University.

Bonet, J S, Isbell C L, Viola P, (1997),MIMIC: Finding optima by estimating probability densities, Advances in Neural Information Processing Systems, Cambridge: MIT Press, 424-430.

Dorigo, M., & Gambardella, L.M. (1997), Ant colony system: a cooperative learning approach to the traveling salesman problem, IEEE Transactions on Evolutionary Computation, 1(1), 53-66.