臺灣博碩士論文加值系統

本論文提出一個以細菌演化為基礎的多階段遺傳演算法，並將其應用來探討數值最佳化、銷售員旅行問題與模糊系統設計問題。多階段遺傳演算法是擷取細菌演化的特性所架構的一個多階段演化的最佳演算法，其主要有五項特色：(1)採用多個「複製→變異→淘汰」演化的多階段架構。(2)採用可變長度的多階層編碼方式對參數進行編碼。 (3)採用可變的染色體族群數量。(4)採用多種不同的變異運算子來產生新染色體。(5)採用適應運算子來扮演區域最佳化的功能。在探討數值最佳化與旅行銷售員問題上，從與傳統遺傳演算法的比較中可知所提的多階段遺傳演算法不但具有快速的搜尋能力，而且具有提高解之精確度的能力。此外，在多重遺傳演算法的應用方面，本論文以數值最佳化、旅行銷售員與模糊系統設計等問題來驗證所提方法對解決多樣化問題的適應性以及其在各類問題上搜尋最佳解的效能。經由在各種問題的實現與模擬結果可看出多階段遺傳演算法中的編碼方法以及多樣化的變異運算確實可以有效的應用來處理各種不同類型的最佳化問題。最後，在模糊系統設計的應用上，除了將所設計出來的模糊系統應用來解決函數逼近問題及倒車入庫問題的探討與模擬之外，我們還將對倒車入庫問題所設計的模糊系統實現在一個以Nios軟核心嵌入式處理器為主控的FPGA晶片上，並以模型車來實現自動倒車功能，以驗證應用所提方法設計的系統確實可以有效地將車子自動倒車入庫。

A novel optimization algorithm called multiple-stage genetic algorithm (msGA) is proposed in this thesis, and it is applied to deal with numerical optimization, traveling salesman problem and fuzzy system design issues. The proposed msGA with a multiple-stage structure is inspired from the concept of the rapid reproduction and adaptation properties in the bacterial evolution process. The main properties of msGA are: (1) A multiple-stage structure with several “reproduction→variation→elimination” processes is proposed. (2) A parameter structure with variable-length and multiple-level is proposed. (3) Population size is not fixed. (4) Different variation operations for generating new chromosomes are proposed in different ways. (5) Adaptation operation for performing local optimization is proposed. In the applications of numerical optimization problems and traveling salesman problems, we can see that the proposed msGA is better than traditional genetic algorithms in the searching speed and high quality solutions. Besides, the proposed msGA is applied in fuzzy system design issues for dealing with the function approximation problem and the truck backing-up problem. In these applications, we can find that the proposed msGA with the proposed parameter structure and optional variation operations is very flexible for many kinds of optimization issues, and the multiple-stage structure can greatly improve the searching speed to obtain optimal solutions. Finally, the designed fuzzy system for the truck backing-up problem is implemented in a Nios embedded system and a hardware experiment of the truck backing-up problem is implemented to illustrate the effectiveness of the proposed method.

第一章 緒論
1.1 研究背景
1.2 論文內容
1.2.1 多階段遺傳演算法的介紹
1.2.2 多階段遺傳演算法的應用
1.2.3 模糊系統之嵌入式設計與硬體實現
1.3 論文架構
第二章 多階段遺傳演算法
2.1 細菌的演化行為
2.2 參數編碼
2.3 演算法架構
2.4 運算子
2.4.1 複製運算子
2.4.2 突變運算子
2.4.3 轉換運算子
2.4.4 交配運算子
2.4.5 適應運算子
2.4.6 求值運算子
2.4.7 淘汰運算子
2.5應用於數值最佳化問題之探討與比較
2.5.1 極值問題
2.5.2 多項式問題
2.5.3 與傳統遺傳演算法的比較
2.6 總結
第三章 多階段遺傳演算法於銷售員旅行問題之探討
3.1 問題描述及常見的解決方案
3.1.1 最近鄰居法
3.1.2 插入法
3.1.3 模擬退火法
3.1.4 遺傳演算法
3.2 以多階段遺傳演算法來探討TSP
3.2.1 變異運算
3.2.2 突變運算
3.3模擬結果與比較
3.4 總結
第四章 多階段遺傳演算法於模糊系統設計之應用
4.1 模糊系統設計簡介
4.2多階段遺傳演算法應用於模糊系統設計
4.2.1 所採用之模糊模型
4.2.2 參數編碼
4.2.3 變異運算子
4.3 應用於函數逼近問題的探討
4.4 應用於倒車入庫問題的探討
4.5 總結
第五章 倒車入庫系統之設計與實現
5.1倒車入庫系統描述
5.2 倒車入庫系統之設計
5.3 倒車入庫系統之實現
5.4 實驗結果
5.5 總結
第六章 結論
參考文獻
研究著作

[1] J.H. Holland, Adaptation in Natural and Artificial Systems, University of Michigan Press, 1975.
[2] D.E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, Reading, 1989.
[3] L. Davis, Handbook of Genetic Algorithms, Van Nostrand Reinhold, 1991.
[4] Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs, Springer, 1992.
[5] I. Lee, R. Sikora, and M.J. Shaw, “A genetic algorithm-based approach to flexible flow-line scheduling with variable lot sizes,” IEEE Transactions on Systems, Man and Cybernetics, Part B, vol. 27, no. 1, 1997, pp. 36-54.
[6] H.D. Jin, K.S. Leung, M.L. Wong, and Z.B. Xu, “An efficient self-organizing map designed by genetic algorithms for the traveling salesman problem,” IEEE Transactions on Systems, Man and Cybernetics, Part B, vol. 33, no. 6, 2003, pp. 877-888.
[7] A. Homaifar, S. Guan, and G.E. Liepins, “A new approach on the traveling salesman problem by genetic algorithms,” International Conference on Genetic Algorithms, 1993, pp. 460-466.
[8] C.C. Chen and C.C. Wong, “Self-generating rule-mapping fuzzy controller design using a genetic algorithm,” IEE Proceedings of Control Theory and Applications, vol. 149, no. 2, 2002, pp. 143-148.
[9] J.S. Jang, C.T. Sun, and E. Mizutani, Neuro-Fuzzy and Soft Computing─A Computational Approach to Learning and Machine Intelligence, Prentice-Hall, 1997.
[10] M. Syrjakow and H. Szczerbicka, “Combination of direct global and local optimization methods,” IEEE International Conference on Evolutionary Computation, vol. 1, 1995, pp. 321-333.
[11] C.H. Chou and J.N. Chen, “Genetic algorithms: Initialization schemes and genes extraction,” IEEE International Conference on Fuzzy Systems, vol. 2, 2000, pp. 965-968.
[12] G. Magyar, M. Johnsson, and O. Nevalainen, “An adaptive hybrid genetic algorithm for the three-matching problem,” IEEE Transactions on Evolutionary Computation, vol. 4, no. 2, 2000, pp.135-146.
[13] J.B. Park, Y.M. Park, J.R. W, and K.Y. Lee, “An improved genetic algorithm for generation expansion planning,” IEEE Transactions on Power Systems, vol. 15, no. 3, 2000, pp. 916-922.
[14] Y. Zhou and N. Sannomiya, “A method for solving large-scale flowshop problems by reducing search space of genetic algorithms,” IEEE International Conference on Systems, Man, and Cybernetics, vol. 3, 2000, pp. 1776-1781.
[15] J.A. Vasconcelos, J.A. Ramirez, R.H.C. Takahashi, and R.H.C. Saldanha, “Improvements in genetic algorithms,” IEEE Transactions on Magnetics, vol. 37, no. 5, 2001, pp.3414-3417.
[16] T. Yoshikawa, T. Furuhashi, and Y. Uchikawa, “DNA coding method and a mechanism of development for acquisition of fuzzy control rules,” IEEE International Conference on Fuzzy Systems, vol. 3, 1996, pp.2194-2200.
[17] T. Yoshikawa, T. Furuhashi, and Y. Uchikawa, “The effects of combination of DNA encoding method with pseudo-bacterial GA,” IEEE International Conference on Evolutionary Computation, 1997, pp. 285-290.
[18] J. Valente de Oliveira, “On the optimization of fuzzy systems using bio-inspired strategies,” IEEE International Conference on Fuzzy Systems, vol. 2, 1998, pp. 1229-1234.
[19] L. Jiao and L. Wang, “A novel genetic algorithm based on immunity,” IEEE Transactions on Systems, Man, and Cybernetics, Part A, vol. 30, no. 5, 2000, pp. 552-561.
[20] I. Molnar and S. Hardhienata, “Comparison of optimization strategies for combined simulation,” Proceedings of the European Simulation Multiconference, 1990, pp. 198-203.
[21] R.R. Yager and D.P. Filev, Essentials of Fuzzy Modeling and Control, John Wiley, 1994.
[22] M. Sugeno and G.T. Kang, “Structure identification of fuzzy model,” Fuzzy Sets and Systems, vol. 28, no. 1, 1988, pp. 15-33.
[23] R.R. Yager and D.P. Filev, “Unified structure and parameter identification of fuzzy models,” IEEE Transactions on Systems, Man and Cybernetics, vol. 23, no. 4, 1993, pp. 1198-1205.
[24] C.T. Lin and C.S.G. Lee, Neural Fuzzy Systems: A Neuro-Fuzzy Synergism to Intelligent Systems, Prentice Hall, 1996.
[25] L.X. Wang, A Course in Fuzzy Systems and Control, Prentice Hall, 1997.
[26] L. Margulis and D. Saga, MICROCOSMOS─Four Billion Years of Evolution from Our Microbial Ancestors, Brockman, 1995.
[27] K.A. Drlica, Understanding DNA and Gene Cloning: A Guide for the Curious, John Wiley & Sons, 1997.
[28] J.H. Holland, Adaptation in Natural and Artificial Systems, University of Michigan Press, 1975.
[29] T. Back, Evolutionary Algorithms in Theory and Practice, Oxford Press, 1996.
[30] A.J. Hoffman and P. Wolfe, "History" in the Traveling Salesman Problem, Wiley, 1985.
[31] E.L. Lawler, J.K. Lenstra, A.H.G.R. Kan, and D.B. Shmoys, The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, John Wiley & Sons, 1985.
[32] D.S. Johnson and L.A. McGeoch, Local Search in Combinatorial Optimization, The Traveling Salesman Problem: A Case Study in Local Optimization, Wiley, 1996.
[33] G. Gutin and A.P. Punnen, Traveling Salesman Problem and Its Variations, Kluwer, 2002.
[34] http://www.math.princeton.edu/tsp/index.html
[35] http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95
[36] http://www2.nkfust.edu.tw/~smguo/research/TSP/TSP.htm
[37] S.A. Cook, “The complexity of theorem-proving procedure,” Proceedings of the 3rd ACM Symposium on Theory of Computing, 1971, pp. 151-158.
[38] D.J. Rosenkrantz, R.E. Steams, and P.M. Lewis, “An analysis of several heuristics for the traveling salesman problem,” SIAM Journal of Computerization, vol. 6, 1977, pp. 563-581.
[39] S. Jung and B.R. Moon, “Toward minimal restriction of genetic encoding and crossovers for the two-dimensional Euclidean TSP,” IEEE Transactions on Evolutionary Computation, vol. 6, no. 6, 2002, pp. 557-565.
[40] S. Kirkpatrick, C.D. Gelatt, and M.P. Vecchi, “Optimization by simulated annealing,” Science, vol. 220, 1983, pp. 671-680.
[41] S.T. Choy and W.C. Siu, “New approach for solving the traveling salesman problem using self-organizing learning,” IEEE International Conference on Neural Networks, vol. 5, 1995, pp. 2632-2635.
[42] N. Vishwanathan and D.C. Wunsch, “ART/SOFM: A hybrid approach to the TSP,” International Joint Conference on Neural Networks, vol. 4, 2001, pp. 2554-2557.
[43] R. Yang, “Solving large traveling salesman problems with small populations,” International Conference on Genetic Algorithms in Engineering Systems: Innovations and Applications, 1997, pp. 157-162.
[44] R.H.J.M. Otten and L.P.P.P. van Ginneken, The Annealing Algorithm, Kluwer Academic, 1989.
[45] H. Tamaki, H. Kita, N. Shimizu, K. Maekawa, and Y. Nishikawa, “A comparison study of genetic codings for the traveling salesman problem,” IEEE International Conference on Evolutionary Computation, vol. 1, 1994, pp. 27-29.
[46] K. Tagawa, Y. Kanzaki, D. Okada, K. Inoue, and H. Haneda, “A new metric function and harmonic crossover for symmetric and asymmetric traveling salesman problems,” IEEE International Conference on Evolutionary Computation, 1998, pp. 822-827.
[47] Y. Nagata and S. Kobayashi, “An analysis of edge assembly crossover for the traveling salesman problem,” IEEE International Conference on Systems, Man, and Cybernetics, vol. 3, 1999, pp. 12-15.
[48] H.S. Yoon and B.R. Moon, “An empirical study on the synergy of multiple crossover operators,” IEEE Transactions on Evolutionary Computation, vol. 6, no. 2, 2002, pp. 212-223.
[49] L.A. Zadeh, “Fuzzy sets,” Information of Control, vol. 8, 1965, pp. 338-353.
[50] E.H. Mamdani, “Application of fuzzy algorithms for control of simple dynamic plant,” Proceedings of the Institution of Electrical Engineers, vol. 121, no. 12, 1974, pp. 1585-1588.
[51] E.H. Mamdani and S. Assilian, “Experiment in linguistic synthesis with a fuzzy logic controller,” International Journal of Man-Machine Studies, vol. 7, no. 1, 1975, pp. 1-13.
[52] T. Takagi and M. Sugeno, “Fuzzy identification of systems and its applications to modeling and control,” IEEE Transaction on Systems, Man, and Cybernetics, vol. 15, no. 1, 1985, pp.116-132.
[53] M. Sugeno and K. Tanaka, “Successive identification of a fuzzy model and its applications to prediction of a complex system,” Fuzzy Sets and Systems, vol. 42, no. 3, 1991, pp. 315-334.
[54] C.C. Wong and C.C. Chen, “A GA-based method for constructing fuzzy systems directly from numerical data,” IEEE Transactions on Systems, Man and Cybernetics, Part B, vol. 30, no. 6, 2000, pp. 904-911.
[55] W. Pedrycz and M. Reformat, “Evolutionary fuzzy modeling,” IEEE Transactions on Fuzzy Systems, vol. 11, no. 5, 2003, pp. 652-665.
[56] R.R. Yager and D.P. Filve, “Generation of fuzzy rules by mountain clustering,” Journal of Intelligent Fuzzy Systems, vol. 2, 1994, pp. 209-219.
[57] C.C. Wong and C.C. Chen, “A hybrid clustering and gradient descent approach for fuzzy modeling,” IEEE Transactions on Systems, Man and Cybernetics, Part B, vol. 29, no. 6, 1999, pp. 686-693.
[58] C.C. Wong and H.R. Lai, “A grey-based clustering algorithm and its application on fuzzy system design,” International Journal of Systems Science, vol. 34, no. 4, 2003, pp. 269-281.
[59] Q. Gan and C.J. Harris, “Fuzzy local linearization and local basis function expansion in nonlinear system modeling,” IEEE Transactions on Systems, Man and Cybernetics, Part B, vol. 29, no. 4, 1999, pp. 559-565.
[60] C.C. Wong and C.C. Chen, “An SVD-QR-based approach to fuzzy modeling,” IEEE International Conference on Systems, Man and Cybernetics, vol. 4, 2000, pp. 2381-2385.
[61] H. Nomura, I. Hayashi, and N. Wakami, “A learning method of fuzzy inference rules by descent method,” IEEE International Conference on Fuzzy Systems, 1992, pp. 203-210.
[62] B. Kosko, Fuzzy Engineer, Prentice Hall, 1997.
[63] L.X. Wang and J.M. Mendel, “Generating fuzzy rules by learning from examples,” IEEE Transactions on Systems, Man and Cybernetics, vol. 22, no. 6, 1992, pp. 1414-1427.
[64] S.G. Kong and B. Kosko, “Adaptive fuzzy system for backing up a truck-and-trailer,” IEEE Transactions on Neural Networks, vol. 3, no. 2, 1992, pp. 211-223.
[65] G. Chen and D. Zhang, “Back-driving a truck with suboptimal distance trajectories: A fuzzy logic control approach,” IEEE Transactions on Fuzzy Systems, vol. 5, no. 3, 1997, pp. 369-380.
[66] W. Zhong, J. Liu, M. Xue, and L. Jiao, “A multiagent genetic algorithm for global numerical optimization,” IEEE Transactions on Systems, Man and Cybernetics, Part B, vol. 34, no. 2, 2004, pp. 1128-1141.