臺灣博碩士論文加值系統

最佳化問題可以區分為數值最佳化問題與組合最佳化問題，基因演算法(Genetic algorithms, GAs)已經被廣泛的應用在解最佳化問題上面，基因演算法搭配多親代交叉方法(multi-parent crossover)常被用來解數值最佳化問題。然而，在解組合最佳化問題方面，還沒有一個有效的多親代交叉方法。Partially mapped crossover (PMX)演算法是解組合最佳化問題方面最常用的交叉方法。在本篇論文中，我們提出了multi-parent partially mapped crossover (MPPMX)。大量的實驗結果顯示出MPPMX改進PMX的比率最高到達38.63 %。而t-test的 p-value在PMX與MPPMX的差異上的值是介於10-6 到10-14之間，也指出MPPMX針對PMX有顯著性的改進。

Optimization problems are divided into numerical optimization problems and combinatorial optimization problems. Genetic algorithms (GAs) are applied to solve optimization problems widely. GAs with multi-parent crossover are often used to solve numerical optimization problems. However, no effective multi-parent crossover is used for combinatorial optimization problems. Partially mapped crossover (PMX) is the most popular crossover for combinatorial optimization problems. In this thesis, we propose multi-parent partially mapped crossover (MPPMX). A large amount of experimental results show that the improvement ratio of MPPMX reaches 38.63 % over PMX. The p-values of t-test on the difference between MPPMX and PMX range from 10-6 to 10-14, which indicates the significant improvement of MPPMX over PMX.

1.INTRODUCTION
1.1 GENETIC ALGORITHMS
1.2 MULTI-PARENT CROSSOVERS
1.3 COMBINATORIAL OPTIMIZATION PROBLEMS
1.3.1 Traveling Salesman Problem
1.3.2 Job Shop Scheduling Problem
1.4 ORGANIZATION
2.GENETIC ALGORITHMS FOR COMBINATORIAL OPTIMIZATION PROBLEMS
2.1 REPRESENTATION
2.1.1 Permutation Representation for the TSP
2.1.2 Representations for the JSP
2.2 SELECTION
2.3 CROSSOVER
2.3.1 Two-Parent Crossover
Partially Mapped Crossover (PMX)
2.3.2 Multi-Parent Crossover
Diagonal Crossover
Uniform Scanning Crossover (U-Scan)
Occurrence Based Adjacency Based Crossover (OB-ABC)
2.4 MUTATION
2.4.1 Insertion Mutation
2.4.2 Reciprocal Exchange Mutation
3.THE PROPOSED METHOD - MPPMX
3.1 MULTI-PARENT PARTIALLY MAPPED CROSSOVER (MPPMX)
3.1.1 Algorithm
3.1.2 Substrings Selection
3.1.3 Substrings Exchange
3.1.4 Mapping List Determination
3.1.5 Offspring Legalization
3.1.6 Complexity analysis of MPPMX
3.2 MPPMX FOR COMBINATORIAL OPTIMIZATION PROBLEMS
3.2.1 MPPMX for the TSP
3.2.2 MPPMX for the JSP
4.PERFORMANCE EVALUATION
4.1 EMPIRICAL ANALYSIS
4.2 EXPERIMENTAL RESULTS ON THE TSP
4.3 EXPERIMENTAL RESULTS ON THE JSP
5.CONCLUSIONS AND FUTURE WORK
APPENDIX A.SETTING AND DATA OF THE EXPERIMENTAL RESULTS
A.1 DATA ON THE TSP
A.1.1 The solution quality
A.1.2 The convergence
A.1.3 The data
A.2 DATA ON THE JSP
A.2.1 The solution quality
A.2.2 The data
REFERENCES

[1]H. J. Bremermann, M. Rogson, and S. Salaff, “Global properties of evolution processes,” In H.H. Pattee, E.A. Edlsack, L. Fein, and A.B. Callahan, editors, Natural Automata and Useful Simulations, pp. 3-41, Spartan Books, Washington DC, 1966.
[2]L. J. Fogel, A. J. Owens, and M. J. Walsh, Artificial Intelligence through Simulated Evolution, John Wiley, 1966.
[3]H. Kaufman, “An Experimental Investigation of Process Identification by Competitive Evolution,” IEEE Transactions on Systems Science and Cybernetics, vol. 3, No. 1, pp. 11-16, 1967.
[4]S. Tsutusi, “Multi-Parent Recombination in Genetic Algorithm with Search Space Boundary Extension by Mirroring,” Proceedings of the 5th International Conference on Parallel Problem Solving from Nature, pp. 428-437, 1998.
[5]A. E. Eiben, “Multiparent Recombination in Evolutionary Computing,” In A. Ghosh and S. Tsutsui, editors, Advances in Evolutionary Computing, Natural Computing Series, Springer, pp. 175-192, 2002.
[6]J. H. Holland, Adaptation in Natural and Artificial System, University of Michigan Press, 1975.
[7]C. Darwin, The Origin of Species, John Murray, London, 1859.
[8]C. K. Ting, “Design and Analysis of Multi-Parent Genetic Algorithms,” Dissertation of University of Paderborn, Germany, 2005.
[9]C. K. Ting and H. K. Büning, “A Mating Strategy for Multi-Parent Genetic Algorithms by Integrating Tabu Search,” Proceedings of the 2003 Congress on Evolutionary Computation CEC2003, Canberra, Australia, IEEE Press, pp. 1259-1266, 2003.
[10]A. E. Eiben, P-E. Raué, and Zs. Ruttkay, “Genetic Algorithms with Multi-Parent Recombination,” Proceedings of the 3rd Conference on Parallel Problem Solving from Nature, vol. 866 of LNCS, pp. 78-87, 1994.
[11]A. E. Eiben, C. H. M. van Kemenade, and J. N. Kok, “Orgy in the Computer: Multi-Parent Reproduction in Genetic Algorithms,” Proceedings of the 3rd European Conference on Artificial Life, vol. 929, pp. 934-945, 1995.
[12]A. E. Eiben, C. H. M. van Kemenade, and J. N. Kolk, “Diagonal Crossover in Genetic Algorithms for Numerical Optimization,” Journal of Control and Cybernetics, vol. 26, No. 3, pp. 447-465, 1997.
[13]H.-M. Voigt, and H. Mühlenbein, “Gene Pool Recombination and Utilization of Covariances for the Breeder Genetic Algorithm,” Proceedings of the 2nd IEEE International Conference on Evolutionary Computation, pp. 172-177, 1995.
[14]H. Mühlenbein and H.-M. Voigt, “Gene Pool Recombination in Genetic Algorithms,” Proceedings of the 6th International Conference on Genetic Algorithms, pp. 104-113, 1995.
[15]I. Ono and S. Kobayashi, “A Real-coded Genetic Algorithm for Function Optimization Using Unimodal Normal Distribution Crossover,” Proceedings of the Seventh International Conference on Genetic Algorithms, pp. 246-253, 1997.
[16]S. Tsutusi and A. Ghosh, “A Study on the Effect of Multi-Parent Recombination in Real Coded Genetic Algorithms,” Proceedings of the 1998 IEEE International Conference on Evolutionary Computation, pp. 828-833, 1998.
[17]S. Tsutsui, M. Yamamura, and T. Higuchi, “Multi-Parent Recombination with Simplex Crossover in Real Coded Genetic Algorithms,” Proceedings of the 1999 Genetic and Evolutionary Computation Conference, pp. 657-664, 1999.
[18]D. Gong and X. Ruan, “A New Multi-Parent Recombination Genetic Algorithm,” Proceedings of the 5th World Congress on Intelligent Control and Automation, vol. 3, pp. 2099-2103, 2004.
[19]C. K. Ting, “An Analysis of the Effectiveness of Multi-parent Crossover,” In Parallel Problem Solving from Nature VIII, vol. 3242 of LNCS, pp 131-140, Springer-Verlag, 2004.
[20]J.P. Caldeira, F. Melicio, and A. Rosa, “Using a Hybrid Evolutionary-Taboo Algorithm to Solve Job Shop Problem,” Proceedings of the 2004 ACM Symposium on Applied Computing, pp. 1446-1451, 2004.
[21]M. Garey, D. Johnson, and R. Sethi, “The Complexity of Flowshop and Jobshop Scheduling,” Mathematics of Operations Research, vol. 1, pp. 117-129, 1976.
[22]M. Gen and R. Cheng, Genetic Algorithms and Engineering Design, John Wiley and Sons, New York, 1997.
[23]M. Gen, Y. Tsujimura, and E. Kubota, “Solving Job-Shop Scheduling Problem Using Genetic Algorithms,” Proceedings of the 16th International Conference on Computers and Industrial Engineering, pp. 576-579, 1994.
[24]L. Davis, “Job Shop Scheduling with Genetic Algorithms,” Proceedings of the First International Conference on Genetic Algorithms, pp. 136-140, 1985.
[25]F. Croce, R. Tadei, and G. Vlota, “A Genetic Algorithm for the Job Shop Problem,” Computers and Operations Research, vol. 22, pp. 15-24, 1995.
[26]U. Dorndorf and E. Pesch, “Evolution Based Learning in A Job Shop Scheduling Environment,” Computers and Operations Research, vol. 22, pp. 25-40, 1995.
[27]D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, New York, 1989.
[28]D. Goldberg and R. Lingle, “Alleles, Loci and the Traveling Salesman Problem,” Proceedings of the First International Conference on Genetic Algorithms, pp. 154-159, 1985.
[29]C. H. M. van Kemenade, J. N. Kok, and A. E. Eiben, “Raising GA Performance by Simultaneous Tuning of Selective Pressure and Recombination Disruptiveness,” Proceedings of the 1995 IEEE International Conference on Evolutionary Computation, pp. 346-351, 1995.