臺灣博碩士論文加值系統

啟發式演算法近年來常被應用於解決實際生活中的各種複雜問題，其也相當容易使用且得出較好的解。在過去許多各式各樣不同類型的啟發式演算法被提出及應用，而一些學者也提出使用多個族群的啟發式演算法來縮短得到更好近似解所需的代數。因此在本論文中，我們首先回顧多族群基因演算法中的處理機制，並且針對其設計數個階層式執行架構。我們的貢獻分為三個主要部分，在第一部分中，我們首先探討多族群計算的特性，從而設計出不同階層式之多族群基因演算架構。在第二部分中，我們結合遷徙機制於上述多族群階層式架構中，並且比較遷徙機制所帶來的效能。而在第三部分中，我們將進一步考慮對階層式架構的多族群加入外來個體以增加搜尋多樣性並保有菁英個體。最後我們也藉由實驗驗證上述所提方法之有效性及執行效率。從實驗結果中可發現所提的階層式多族群架構可避免陷入區域最佳解，遷徙機制可以改善解的品質，及加入外來個體能增加整體搜尋最佳解的可變性。

Metaheuristics have recently been commonly used to solve complex problems in real applications. They are easy to use and usually get good solutions for the problems. There were many approaches proposed in improving the performance of the metaheuristics. Some scholars also used multiple populations in meta-heuristic approaches to shorten the generation number needed to find nearly optimal solutions. In this thesis, we revisit the multi-population mechanisms and design several hierarchical execution architectures of GA. We make three main parts of contribution in this thesis. In the first part, we review the properties of sub-population execution for GA, and design a hierarchical sub-population architecture. In the second part, we embed different migration mechanisms in the above hierarchical sub-population architecture and compare their performance. In the third part of the thesis, we further consider adding aliens to merged sub-populations to increase diversity and reserve elitists. Experiments are also made for verifying the effectiveness and efficiency of the proposed approaches. From the experimental results, it is found that the hierarchical sub-population architecture could easily avoid solutions trapped in local optima, the migration mechanism could make solution quality of sub-populations better, and adding aliens could increase search variety.

Contents
論文審定書 i
致謝 ii
摘要 iii
Abstract iv
List of Figures vii
List of Tables x
CHAPTER 1 Introduction 1
1.1 Motivation 1
1.2 Organization of Thesis 4
CHAPTER 2 Related Works 5
2.1 Genetic Algorithms 5
2.2 Multi-population Genetic algorithms 8
2.3 Migration Strategy 10
2.4 Hierarchical Structure 12
CHAPTER 3 Multi-population Genetic Algorithm with Hierarchical Execution 15
3.1 Main Idea 15
3.2 The Proposed Algorithm 18
3.3 An Example of the Proposed HMGA 20
3.4 A different hierarchical architectures example of the Proposed HMGA 28
CHAPTER 4 Hierarchical Multi-population Genetic Algorithm with Migration Mechanism……… 31
4.1 Main Idea 31
4.2 The Proposed Hierarchical Multi-population Genetic Algorithm with Migration Strategy 34
4.3 An Example of MHMGA Algorithm 36
CHAPTER 5 Hierarchical Multi-population Genetic Algorithm with Aliens 41
5.1 Main Idea 41
5.2 The Proposed Hierarchical Multi-population Genetic Algorithm with Alien Mechanism 43
5.3 An Example of the AHMGA Algorithm 45
CHAPTER 6 Experimental Evaluation 50
6.1 Benchmark Functions 50
6.2 Parameter Settings 52
6.3 Experimental Results of HMGA 53
6.4 Experimental Results of MHMGA 57
6.5 Experimental Results of AHMGA 69
CHAPTER 7 Conclusion and Future Work 73
References 74

References
[1]E. Cantú-Paz, "A survey of parallel genetic algorithms," Calculateurs Paralleles, Rreseaux et Systems Repartis, " Vol. 10, No. 2, pp. 141-171, 1998.
[2]D. X. Chang, X. D. Zhang and C. W. Zheng, "A robust dynamic niching genetic algorithm with niche migration for automatic clustering problem," Pattern Recognition, Vol. 43, Issue 4, pp. 1346-1360, 2010.
[3]J. K. Cochran, S. M. Horng and J. W. Fowler, "A multi-population genetic algorithm to solve multi-objective scheduling problems for parallel machines." Computers & Operations Research, Vol. 30, Issue 7, pp. 1087-1102, 2003.
[4]K. Deb, "An efficient constraint handling method for genetic algorithms." Computer Methods in Applied Mechanics and Engineering, Vol. 186, Issue 2, pp. 311-338, 2000.
[5]K. Deb, A. Pratap, S. Agarwal and T. Meyarivan, "A fast and elitist multiobjective genetic algorithm: NSGA-II," IEEE Transactions on Evolutionary Computation, Vol. 6, No. 2, pp. 182-197, 2002.
[6]M. Dorigo, M. Birattari and T. Stützle, "Ant colony optimization," IEEE Computational Intelligence Magazine, Vol. 1, Issue 4, pp. 28-39, 2006.
[7]R. Esmat, H. Nezamabadi-Pour and S. Saryazdi, "GSA: a gravitational search algorithm," Information Sciences, Vol. 179, Issue 13, pp. 2232-2248, 2009.
[8]D. E. Goldberg, and J. H. Holland, "Genetic algorithms and machine learning," Machine Learning, Vol. 3, Issue 2, pp. 95-99, 1988.
[9]J. J. Grefenstette, Parallel Adaptive Algorithms for Function Optimization, Technical Report, Vanderbilt University, Nashville, pp. 18-81, 1981.
[10]J. H. Holland, Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence, University of Michigan Press, 1975.
[11]T. P. Hong, J. C. Chen and W. Y. Lin, Particle Swarm Optimization with Hierarchical Execution, Technical Report, 2014.
[12]T. P. Hong, L. I. Huang and W. Y. Lin, "Comparison of some migration policies in sub-ant-colony scheme,” The Taiwan Academic Network Conference, pp. 1557-1561, 2014.
[13]M. Jamil and X. S. Yang, “A literature survey of benchmark functions for global optimisation problems,” International Journal of Mathematical Modelling and Numerical Optimisation, Vol. 4, No. 2, pp. 150-194, 2013.
[14]J. Kennedy and R. Eberhart, “Particle swarm optimization,” The 1995 IEEE International Conference on Neural Networks, Vol. 4, pp. 1942 -1948, 1995.
[15]X. Lai and G. Tan, “Studies on migration strategies of multiple population parallel particle swarm optimization,” The Eighth International Conference on Natural Computation, pp. 29-31, 2012.
[16]J. J. Liang, A. K. Qin, P. N. Suganthan and S. Baskar. "Comprehensive learning particle swarm optimizer for global optimization of multimodal functions." IEEE Transactions on Evolutionary Computation, Vol. 10, No. 3, pp. 281-295, 2006.
[17]W. Y. Lin, T. P. Hong, S. M. Liu and J. H. Lin, "Revisiting the design of adaptive migration schemes for multipopulation genetic algorithms," The 2012 Conference on Technologies and Applications of Artificial Intelligence, pp. 338 – 343, 2012.
[18]M. Mitchell, An Introduction to Genetic Algorithms, The MIT press, 1998.
[19]K. NARA, H. Univ and A. Shiose, "Implementation of genetic algorithm for distribution systems loss minimum re-configuration," IEEE Transactions on Power Systems, Vol. 7, No. 3, pp. 1044-1051, 1992.
[20]C. B. Pettey, M. R. Leuze and J. J. Grefenstette, "A parallel genetic algorithm," The Second International Conference on Genetic Algorithms, pp. 155-161, 1987.
[21]A. Ratnaweera, S. K. Halgamuge and H. C. Watson, "Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients," IEEE Transactions on Evolutionary Computation, Vol. 8, No. 3, pp. 240–255, 2004.
[22]Y. R. Samii and E. Michielssen, "Electromagnetic optimization by genetic algorithms," Microwave Journal, Vol. 42, No .11, pp. 232-232, 1999.
[23]M. Sefrioui and J. Périaux, "A hierarchical genetic algorithm using multiple models for optimization,"The Sixth International Conference on Parallel Problem Solving from Nature, pp. 879-888, 2000.
[24]M. Seyedali, S. M. Mirjalili, and A. Lewis, "Grey wolf optimizer," Advances in Engineering Software, Vol. 69, pp. 46-61, 2014.
[25]P. S. Shelokar, P. Siarry, V. K. Jayaraman and B. D. Kulkarni, "Particle swarm and ant colony algorithms hybridized for improved continuous optimization," Applied Mathematics and Computation, Vol. 188, Issue 1, pp. 129-142, 2007.
[26]D. Simon, "Biogeography-based optimization," IEEE Transactions on Evolutionary Computation, Vol. 12, No. 6, pp. 702–13, 2008.
[27]M. B. Wall, A Genetic Algorithm for Resource-Constrained Scheduling, PhD Disseration, Massachusetts Institute of Technology, 1996.
[28]W. W. Wasserman and A. Sandelin, "Applied bioinformatics for the identification of regulatory elements," Nature Reviews Genetics, Vol. 5, No. 4, pp. 276-287, 2004.
[29]Wikipedia, https://en.wikipedia.org/wiki/Charles_Darwin
[30]Wikipedia, https://en.wikipedia.org/wiki/Genetic_algorithm
[31]Wikipedia, https://en.wikipedia.org/wiki/Introduced_species
[32]Wikipedia, https://en.wikipedia.org/wiki/Marco_Polo
[33]Wikipedia, https://en.wikipedia.org/wiki/Christopher_Columbus
[34]S. H. Zegordi and M. A. B. Nia, "A multi-population genetic algorithm for transportation scheduling" Transportation Research Part E: Logistics and Transportation Review, Vol. 45, Issue 6, pp. 946-959, 2009.