臺灣博碩士論文加值系統

基因演算法是最常用於求解組合性問題的一種演化式演算法，該方法在組合問題中具有不錯的求解。但隨組合性問題的維度變大，該方法易因演化運算後喪失族群多樣性而產生過早收斂或稱過早成熱的問題，使得求得的解落於次佳解(區域最佳解)之中並難以跳脫次佳解。
為了解決此問題，大多數的學者均以改變演化運算子或演化運算子的機率。在本研究中，提出以衡量族群多樣性，當族群多樣性不足時，注入人造染色體以提升族群多樣性使得基因演算法能有機會繼續演化。
該方法以旅行者問題來進行驗證，其結果証明當族群多樣性不足時，注入人造染色體的確能有效的跳脫次佳解並改善求解品質。

The applications of genetic algorithms in solving combinatorial problems are frequently faced with a problem of early convergence and the evolutionary processes are often trapped into a local but not the global optimum. This premature convergence occurs when the population of a genetic algorithm reaches a suboptimal state that the genetic operators can no longer produce offspring with a better performance than their parents. In the literature, plenty of work has been investigated to introduce new methods and operators in order to overcome this essential problem of genetic algorithms.
As these methods and the belonging operators are rather problem specific in general. In this research, we take a different approach by observing the progress of the evolutionary process and when the diversity of the population dropping below a threshold level then artificial chromosomes with high diversity will be introduced to increase the average diversity level thus to ensure the process can jump out the local optimum.
The proposed method is implemented independently of the problem characteristics and can be applied to improve the global convergence behavior of genetic algorithms. The experimental results using TSP instances show that the proposed approach is very effective in preventing the premature convergence when compared with the earlier approaches.

Contents
Contents v
Figure of content vii
Table of content viii
Chapter 1. Introduction 1
1.1 Background 1
1.2 Motivation 1
1.3 Objectives 1
1.4 Framework 2
Chapter 2. Literature Survey 3
2.1 Combinatorial Problems 3
2.2 Travelling Salesman Problem 3
2.3 Application 4
2.4 Genetic algorithms 4
2.5 Diversity mechanism 5
2.6 Relative diversity application research 7
2.7 Individual diversity and population diversity measures 7
2.7.1 Individual diversity measurements: 7
2.7.2 Population diversity measurements: 9
Chapter 3. Problems Definition 10
3.1 Travelling Salesman Problem 10
3.2 Instance 10
Chapter 4. Methodology 14
4.1 Promoting Diversity by Dynamic Diversity Control in Genetic Algorithms 14
4.1.1 Artificial Chromosomes 14
4.1.2 Archive 15
4.1.3 Multiple archives 15
4.1.4 Dominance Matrix 16
4.1.5 Replacement Strategy 18
4.2 DDCGA 18
4.2.1 Encoding 21
4.2.2 Initial population 22
4.2.3 Collecting and removing rules of archive 22
4.2.4 Selection/reproduction operator 23
4.2.5 Crossover 24
4.2.6 Mutation 24
4.2.7 Generating diversified artificial chromosomes 25
4.2.8 Replacement 25
4.2.9 Terminating condition 25
Chapter 5. Experiment 26
5.1 Parameter 26
5.2 Experimental results 26
Chapter 6. Conclusion 31
Future works 31
Appendix 34
A. DOE of SGA in KroA100 instance of TSP 34
B. Lower Threshold Analysis 35
C. Upper Threshold Analysis 38

[1] M.R. Garey, and D.S. Johnson. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman.
[2] F.-C. Yang, and Y.-P. Wang. (2007), Water flow-like algorithm for object grouping problems. Journal of the Chinese Institute of Industrial Engineers ,24, 475~488.
[3] D.R. Sule. (1997), Industrial Scheduling, PWS.
[4] K.R. Baker. (1974), Introduction to Sequencing and Scheduling, John Wiley & Sons Inc, New York.
[5] A. Nagar, S.S. Heragu, and J. Haddock. (1995), A Branch-and-Bound Approach for a Two-Machine Flowshop Scheduling Problem Journal of the Operational Research Society ,46, 721-734.
[6] P. Mellor. (1966), A review of job shop scheduling. Operations Research Quarterly ,17, 161-171.
[7] P.-j. Wang (1995), The Investigation of Dynamic Scheduling Problem Using Genetic Algorithm with Simulation. in "Department of Industrial Engineering", Chung Yuan.
[8] H.H. John. (1992), Adaptation in natural and artificial systems, MIT Press.
[9] E.G. David, and R. Jon. (1987), Genetic algorithms with sharing for multimodal function optimization. in "Proceedings of the Second International Conference on Genetic Algorithms on Genetic algorithms and their application", Lawrence Erlbaum Associates, Inc., Cambridge, Massachusetts, United States.
[10] Michalwics, (1997), Handbook of Evolutionary Computation, IOP Publishing Ltd,.
[11] E.B. James. (1985), Adaptive Selection Methods for Genetic Algorithms. in "Proceedings of the 1st International Conference on Genetic Algorithms", Lawrence Erlbaum Associates, Inc.
[12] L. Yee, G. Yong, and X. Zong-Ben. (1997), Degree of population diversity - a perspective on premature convergence in genetic algorithms and its Markov chain analysis. Neural Networks, IEEE Transactions on ,8, 1165-1176.
[13] K.U. Rasmus. (2002), Diversity-Guided Evolutionary Algorithms. in "Proceedings of the 7th International Conference on Parallel Problem Solving from Nature", Springer-Verlag.
[14] M. Mauldin. (1984), Maintaining Diversity in Genetic Search. in "AAAI".
[15] H. Shimodaira. (1997), DCGA: a diversity control oriented genetic algorithm. in "Tools with Artificial Intelligence, 1997. Proceedings., Ninth IEEE International Conference ".
[16] N. Sangkawelert, and N. Chaiyaratana. (2003), Diversity control in a multi-objective genetic algorithm. in "Evolutionary Computation, 2003. CEC ''03. The 2003 Congress on".
[17] K. Ting, and H. Shu-Yuen. (1997), Using Disruptive Selection to Maintain Diversity in GeneticAlgorithms, Kluwer Academic Publishers.
[18] Y. Tsujimura, and M. Gen. (1998), Entropy-based genetic algorithm for solving TSP Entropy-based genetic algorithm for solving TSP. in "Knowledge-Based Intelligent Electronic Systems, 1998. Proceedings KES ''98. 1998 Second International Conference on" (M. Gen, Ed.
[19] K.Q. Zhu, and Z. Liu. (2004), Empirical Study of Population Diversity in Permutation-Based Genetic Algorithm. in "Genetic and Evolutionary Computation – GECCO 2004".
[20] S. Paul, D.d.J. Edwin, B. Bart de, and W. Franjo. (2006), Multi-objective diversity maintenance. in "Proceedings of the 8th annual conference on Genetic and evolutionary computation %@ 1-59593-186-4", ACM Press, Seattle, Washington, USA.
[21] A. Ekárt, and S.Z. Németh. (2002), Maintaining the Diversity of Genetic Programs. in "Genetic Programming: 5th European Conference, EuroGP 2002, Kinsale, Ireland, April 3-5, 2002. Proceedings".
[22] E.K. Burke, S. Gustafson, and G. Kendall. (2004), Diversity in genetic programming: an analysis of measures and correlation with fitness. Evolutionary Computation, IEEE Transactions on ,8, 47-62.
[23] J.K. Lenstra, A.H.G. RinnooyKan, and P. Brucker. (1977), Complexity of Machine Scheduling Problems. in "Annals of Discrete Mathematics".
[24] R. M''Hallah. (2007), Minimizing total earliness and tardiness on a single machine using a hybrid heuristic. Computers & Operations Research 3126-3142.
[25] J. Bauman, and J. Jozefowska. (2006), Minimizing the earliness-tardiness costs on a single machine. Computers & Operations Research 3219-3230.
[26] W. Bossert, P.K. Pattanaik, and Y. Xu. (2001), The Measurement of Diversity, Universite de Montreal, Departement de sciences economiques.
[27] W. Bossert, P.K. Pattanaik, and Y. Xu. (2002), Similarity of Options and the Measurement of Diversity, Universite de Montreal, Departement de sciences economiques.
[28] T. Murata, T. Murata, and H. Ishibuchi. (1996), "Evolutionary Computation” Proceedings of IEEE International Conference "