臺灣博碩士論文加值系統

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

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.

Index
致謝 i
中文摘要 ii
ABSTRACT iii
INDEX iv
FIGURE INDEX vi
TABLE INDEX vii
CHAPTER 1 INTRODUCTION 1
1.1 INTRODUCTION AND MOTIVATION 1
1.2 THESIS GOALS 2
1.3 THESIS STRUCTURE 3
CHAPTER 2 LITERATURE REVIEW 4
2.1 AN OVERVIEW OF GENETIC ALGORITHM 4
2.1.1 History and Concept 4
2.1.2 Basic Operation of Genetic Algorithm 5
2.2 SCHEMA THEOREM AND BUILDING BLOCKS HYPOTHESIS 8
2.3 EPISTASIS 9
2.4 INHERITANCE CHARACTERISTIC 11
2.5 EVALUATION AND INHERITANCE APPROACHES 13
2.5.1 Chromosome Oriented Approaches 13
2.5.2 Gene Oriented Approaches 13
2.5.3 Schema Oriented Approaches 13
CHAPTER 3 MULTIPLE-EVALUATION GENETIC ALGORITHM 15
3.1 MEGA INTRODUCTION 15
3.2 ALGORITHM DESCRIPTION 16
3.2.1 Coding Mechanism 16
3.2.2 Multiple Evaluation Mechanism 16
3.2.3 Selection Operation 17
3.2.4 Crossover Operation 17
3.2.5 Mutation Operation 19
3.2.6 Replacement Operation and Termination of Evolution 21
3.3 NUMERICAL EXPERIMENTS 21
3.3.1 Test Functions 21
3.3.2 Numerical Implementation of the MEGA 22
3.3.3 Comparison of Optimization Results with the Other Researches 23
3.4 A REPLACEMENT MEGA (RMEGA) 25
3.4.1 A Replacement MEGA (rMEGA) 25
3.4.2 Numerical Implementation of the rMEGA 26
3.5 PERFORMANCE ASSESSMENT OF THE MEGA AND RMEGA 28
3.5.1 Results of the Inheritance Mechanism 28
3.5.2 Results of the Gene-Evaluation Mechanism 29
3.5.3 Results of the Crossover Rate 30
3.5.4 Results of the two-stage mutation 35
3.6 CONCLUDING REMARK 35
CHAPTER 4 MULTIPLE O-D PAIRS ROUTING PROBLEMS 38
4.1 MOTIVATION 38
4.2 PROBLEM DESCRIPTION 38
4.3 ALGORITHM DESCRIPTION 40
4.3.1 Encoding 41
4.3.2 Selection 41
4.3.3 Crossover Operation 42
4.3.4 Mutation Operation 42
4.4 EXPERIMENT AND ANALYSIS 44
4.4.1 Network Topology 44
4.4.2 Performance Metrics 45
4.4.3 Experimental Results for Two Transmit Rates 45
4.4.4 Experimental Results for Multiple O-D Pairs 47
4.4 CONCLUDING REMARK 50
CHAPTER 5 CONCLUSION 51
REFERENCES 52
APPENDIX: BENCHMARK FUNCTIONS 55


Figure Index
Figure 2- 1: A Traditional Genetic Algorithm Flow Chart. 5
Figure 2- 2: Stochastic Universal Sampling 6
Figure 2- 3: One-point Crossover Operation 7
Figure 2- 4: Uniform Mutation Operation 8
Figure 2- 5: Relationships Between Numbers of Mutations and Fitness. 11
Figure 3- 1: An Illustration of the Inheritance Phrase in the Crossover Operation 19
Figure 3- 2: The Pseudo Code of the Evaluation-based Crossover Operation 20
Figure 3- 3: The Pseudo Code of the Evaluation-Based Mutation Operation 21
Figure 3- 4: The Pseudo Code of the rMEGA’s Crossover Operation. 25
Figure 3- 5: The Pseudo Code of the rMEGA’s Mutation Operation. 26
Figure 3- 6: The Experiments for the Efficiency of the Inheritance Mechanism 29
Figure 3- 7: The Experiments for the Efficiency of the Evaluation Mechanism 29
Figure 3- 8: The Results of the rMEGA in Function 2 31
Figure 3- 9: The Variance of the rMEGA in Function 2 31
Figure 3- 10: The Results of the MEGA in Function 2 32
Figure 3- 11: The Variance of the MEGA in Function 2 32
Figure 3- 12: The Results of the rMEGA in Function 10 33
Figure 3- 13: The Variance of the rMEGA in Function 10 33
Figure 3- 14: The Results of the MEGA in Function 10 34
Figure 3- 15: The Variance of the MEGA in Function 10 34
Figure 3- 16: The Converge Curve of Three Mutation Methods in Function 2 36
Figure 3- 17: The Variance of Three Mutation Methods in Function 2 36
Figure 3- 18: The Converge Curve of Three Mutation Methods in Function 10 37
Figure 3- 19: The Variance of Three Mutation Methods in Function 10 37
Fiugre 4- 1: (a) The Chromosome Structure in the MEGA (b) The Gene Structure in Each Chromosome 41
Fiugre 4- 2: One-point Crossover Operation 43
Fiugre 4- 3: Detail Mutation Operation 44
Fiugre 4- 4: NSF Network Topology. 44
Fiugre 4- 5: The Convergence Curve Graph of two Different Transmit Rate 46
Fiugre 4- 6: The Best Routing Path of the MEGA 47
Fiugre 4- 7: The Best Routing Path of the TGA 47
Fiugre 4- 8: The Average Standard Deviation with the Transmit rate b1= 0.25 Mbps 49
Fiugre 4- 9: The Average Standard Deviation with the Transmit rate b2= 0.5 Mbps 50

Table Index
Table 3- 1: The Eleven Test Functions and their Key Properties 22
Table 3- 2: The Results of the MEGA in 11 Benchmark Functions 23
Table 3- 3: The Complexes of the MEGA 24
Table 3- 4: The Comparison of Optimization Results with Existing Algorithm 24
Table 3- 5: The Results of the rMEGA in 11 Benchmark Functions 27
Table 3- 6: The Complexes of the rMEGA 27
Table 3- 7: The Experiment Results Considering the Gene-evaluation and Advantage-inheritance Mechanisms 28
Table 3- 8：The Results of the rMEGA in Function 2 31
Table 3- 9: The Results of the MEGA in Function 2 32
Table 3- 10: The Results of the rMEGA in Function 10 33
Table 3- 11: The Results of the MEGA in Function 10 34
Table 3- 12: The Experiment Results of Three Mutation Methods in Function 2 36
Table 3- 13: The Experiment Results of Three Mutation Methods in Function 10 37
Table 4- 1: The Standard Deviation of the 5 Case with b1=0.25Mbps Transmit rate. 48
Table 4- 2: The Mean Spent Cost of the 5 Case with b1=0.25Mbps Transmit rate. 48
Table 4- 3: The Standard Deviation of the 5 Case with b2=0.5 Mbps Transmit rate. 49
Table 4- 4: The Mean Spent Cost of the 5 Case with b2 = 0.5 Mbps Transmit rate. 49

[1]Holland, J.: Adaptation in Natural and Artificial Systems, The University of Michigan Press, Ann Arbor, MI, 1975.
[2]Beasley, D., Bull, D. R., Martin, R. R.: An overview of genetic algorithms: Part 1, fundamentals, 1993.
[3]Beasley, D., Bull, D. R., Martin, R. R.: An overview of genetic algorithms: Part 2, Research Topics, 1993.
[4]McCall, J.: Genetic algorithms for modelling and optimisation. Journal of Computational and Applied Mathematics, Vol. 184 (2005) 205-222
[5]Kennedy, J. Eberhart, R.: Particle Swarm Optimization. In Proceedings of the IEEE International Conference on Neural Networks (1995) 1942-1948
[6]Vasconcelos, J. A., Ramirez, J. A., Takahashi, R. H. C., Saldanha, R. R.: Improvements in genetic algorithms. IEEE Transactions on magnetics, Vol. 37, No. 5 (Sep. 2001) 3414-3417
[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
[8]Louis, S. J., McDonnell, J.: Learning with case-injected genetic algorithm. IEEE Transactions on Evolutionary Computation, Vol. 8, No. 4 (Aug 2004) 316-328
[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
[11]Ahn, C. W., Ramakrishna, R. S.: Elitism-based compact genetic algorithms. IEEE Transactions on Evolutionary Computation, Vol. 7, No. 4 (Aug 2003) 367-385
[12]Rimcharoen, S., Sutivong, D., Chongstitvatana, P.: Updating strategy in compact genetic algorithm using moving average approach. In Proceedings of IEEE Conference on Cybernetics and Intelligent Systems (CIS ’06) (June 2006) 1-6
[13]Yeh, E. C., Shyu, Y-Y.: A new genetic algorithm with statistical gene evaluation. In Proc. IEEE NAFIPS/IFIS/NASA (1994) 409-410
[14]Kubota, N., Shzmojima, K., Fukuda, T.: The role of virus infection in virus-evolutionary genetic algorithm. In Proceedings of the third IEEE International Conference on Evolutionary Computation (CEC ’96) (1996) 182-187
[15]Yao, X., Liu, Y., Lin, G. M.: Evolutionary programming made faster. IEEE Trans. on Evolutionary Computation, Vol. 3, No. 2 (July 1999) 82-102
[16]Hinterding, R.: Gaussian mutation and self-adaptation for numeric genetic algorithms. In Proc. IEEE International Conference on Evolutionary Computation (April 1997) 87-91
[17]Tu, Z., Lu, Y.: A robust stochastic genetic algorithm (StGA) for global numerical optimization. IEEE Trans. on Evolutionary Computation, Vol. 8, No. 5 (Oct. 2004) 456-470
[18]Vasconcelos, J. A., Ramirez, J. A., Takahashi, R. H. C., Saldanha, R. R.: Improvements in genetic algorithms. IEEE Transactions on magnetics, Vol. 37, No. 5 (Sep. 2001) 3414-3417
[19]Mashhadi, H. R., Shanechi, H. M., Lucas, C.: A new genetic algorithm with Lamarckian individual learning for generation scheduling. IEEE Trans. on Power Systems, Vol. 18, No. 3 (Aug. 2003) 1181-1186
[20]Bäck, T., Hammel, U., Schwefel, H.P.: Evolutionary computation: comments on the history and current state. IEEE Trans. on Evolutionary Computation, Vol. 1, No. 1 (April 1997) 3-17
[21]Ahn, C. W., Ramakrishna, R. S.: Elitism-based compact genetic algorithms. IEEE Trans. on Evolutionary Computation, Vol. 7, No. 4 (Aug. 2003) 367-385
[22]Lin, C. H., He, J. D., A Multiple-Evaluation Genetic Algorithm for Numerical Optimization Problems. Submitted to Computability in Europe 2007: Computation and Logic in the Real World (CiE) (2007)
[23]Sun, T. Y., Liu, C. C., Hsieh, S. T., Lin, C. L., Lee, K. Y.: Cluster-based adaptive mutation mechanism to improve the performance of genetic algorithm. In Proceedings of the 6th International Conference on Intelligent Systems Design and Applications (ISDA '06) (Oct 2006) 461-466
[24]Chen, C., Ma, J., Wu, W., and Zhou, J.: A modeling framework for multipath routing in Ad hoc networks. IEEE GLOBECOM (2005) 2594-2598
[25]Mao, S., Kompella, S., Hou, Y. T., Sherali, H. D., and Midkiff, S. F.: Routing for Concurrent Video Sessions in Ad Hoc Networks. In IEEE Trans on Vehicular Technology, Vol. 55, No. 1 (Jan. 2006)
[26]Mao, S., Hou, Y. T., Cheng, X., Sherali, H. D., Midkiff, S. F., and Zhang, Y.Q.: Routing for concurrent video sessions in ad hoc networks. In IEEE Trans on Multimedia, Vol. 8, No. 5 (Oct 2006)
[27]Fabregat, R., Donoso, Y., Baran, B., Solano, F., and Marzo, J. L.: Multi-objective optimization scheme for multicast flows: a survey, a model and a MOEA solution. In Proc. 3rd international IFIP/ACM. Latin American Conference on Networking (LANC '05) (2005) 73-86
[28]Li, F., Liu, Q. H., Min, F., and Yang, G. W.: A new crossover operator based on the rough set theory for genetic algorithms. In Proc. 4th International Conference on Machine Learning and Cybernetics (2005) 18-21
[29]Homaifar, A., QI, C. X., and Lai, S. H.: Constrained optimization via genetic algorithms. Simulation (1994) 242–254
[30]Hadj-Alouane, A. B., and Bean, 0J. C. Bean.: A genetic algorithm for the 7 multiple-choice integer program. Operations Research (1997) 92–101
[31]Sun, W., and Liu, Z.: Routing multipoint connections in computer networks. In Proc. IEEE International Symposium on Circuits and System, Vo1. 6 (1998)
[32]Djukic, P., and Valaee, S.: Reliable packet transmissions in multipath routed wireless networks. IEEE Trans Mobile Computing, Vol. 5, No. 5 (May 2006)