臺灣博碩士論文加值系統

本文提出採用部分因子設計法（Fractional Factorial Design，FFD）可分析出最佳因子組合的能力，分別結合在基因演算法（Genetic Algorithm, GA）的交配運算子和模擬退火法（Simulated Annealing, SA）的擾動運算中，以找出在目前搜尋範圍中具有較佳目標函數值的個體，以增進基因演算法和模擬退火法的搜尋效率。另外本文結合傳統式基因演算法和模擬退火法而成模擬退火-基因演算法(Simulated Annealing-Genetic Algorithm, SAGA)，利用模擬退火法的快速搜尋能力可增進基因演算法的演化效率。進一步地透過結合部分因子設計法於模擬退火-基因演算法而成部分因子設計之模擬退火-基因演算法（Simulated Annealing-Genetic Algorithm by Fractional Factorial Design, FFD-SAGA），以求得更精確之全域最佳解。
本論文一開始以非限制條件的測試函數做實驗，測試結合FFD之演算法與傳統式演算法在高維度時效能之比較，接著比較SAGA與傳統式GA對相同非限制條件之測試函數的效能，然後再比較FFD-SAGA之效能。在對FFD-SAGA的實驗中，一開始我們比較FFD-SAGA與SAGA對非限制條件之測試函數的效能，接著FFD-SAGA與其它方法在有限制條件的測試函數時之演算法求解能力之比較，最後並將其應用於求解四個工程最佳化問題並與其它方法比較其效能。由以上一系列測試的案例可知道結合FFD之演算法是可以有效增進傳統式演算法的效能，另外，利用SA的快速搜尋能力的確可以增進GA的演化效率。同時FFD-SAGA亦可有效地求解限制或非限制條件的測試函數，並且有效地求解四個工程最佳化的應用問題。

This thesis proposes a fractional factorial design (FFD) technique, which can analyze the best individual with the best combination of factors, to incorporate into the crossover operator of a genetic algorithm and the perturbation mechanism of a simulated annealing algorithm for enhancing the search ability of the two algorithms. The aforementioned algorithms are named FFD-GA and FFD-SA, respectively. In addition, the hybrid algorithm with the simulated annealing algorithm and the conventional genetic algorithm, termed simulated annealing-genetic algorithm (SAGA), is introduced by use of the fast search capability of the simulated annealing to improve the evolutionary efficiency of the conventional genetic algorithm Furthermore, the thesis also proposes the FFD-SAGA algorithm, which is the combination of the SAGA and FFD technique, to achieve more accurate solutions of global optimization problems.
First, this study applies the conventional GA and SA algorithms with/without incorporating the FFD technique in solving unconstrained benchmark cases in order to assess the effectiveness of the two algorithms. Moreover, the proposed FFD-SAGA algorithm is compared with other algorithms by solving constrained objective functions. Furthermore, the proposed FFD-SAGA algorithm is applied to four engineering optimization problems to evaluate its algorithmic efficiency in practical engineering design. From the series of benchmarking case testing, the numerical results indicated that both FFD-GA and FFD-SA algorithms are superior to the conventional GA and SA without including the FFD. Also, the FFD-SAGA is relatively effective in solving unconstrained, constrained problems and four engineering optimization problems.

中文摘要………………………………………………………………………… I
英文摘要………………………………………………………………………… II
誌謝……………………………………………………………………………… III
目錄……………………………………………………………………………… IV
表目錄…………………………………………………………………………… VI
圖目錄…………………………………………………………………………… VII
第一章 導論………………………………………………………………………1
1.1 研究背景和動機…………………………………………………………… 1
1.2 研究目的…………………………………………………………………… 2
1.3 論文架構…………………………………………………………………… 2
第二章 文獻探討……………………………………………………………… 3
2.1 部分因子設計法之理論…………………………………………………… 4
2.1.1 部分因子設計法的直交表產生方法…………………………………… 5
2.1.2 因子分析………………………………………………………………… 7
2.2 基因演算法之理論………………………………………………………… 7
2.2.1 基因演算法的流程……………………………………………………… 9
2.2.2 染色體編碼方式………………………………………………………… 10
2.2.3 三個基本運算子………………………………………………………… 11
2.3 模擬退火演算法之理論…………………………………………………… 15
2.3.1 模擬退火演算法的流程………………………………………………… 16
2.3.2 擾動方式………………………………………………………………… 17
2.3.3 機率函數………………………………………………………………… 18
第三章 部分因子設計之模擬退火-基因演算法……………………………… 19
3.1 結合部分因子設計法之演算法的搜尋能力分析………………………… 19
3.1.1 部分因子設計-基因演算法的搜尋能力分析………………………… 19
3.1.2 部分因子設計-模擬退火演算法的搜尋能力分析…………………… 19
3.1.2.1 實例說明部分因子設計-模擬退火演算法的搜尋能力…………… 20
3.2 部分因子設計之模擬退火-基因演算法………………………………… 25
3.2.1 模擬退火-基因演算法………………………………………………… 25
3.2.2 部分因子設計之模擬退火-基因演算法的步驟……………………… 26
3.2.3 實例說明部分因子設計之模擬退火-基因演算法…………………… 28
第四章 實驗結果和討論……………………………………………………… 30
4.1 結合部分因子設計法之演算法…………………………………………… 31
4.1.1 部分因子設計-基因演算法的效能分析……………………………… 32
4.1.2 部分因子設計-模擬退火演算法的效能分析………………………… 33
4.2 模擬退火-基因演算法的效能分析……………………………………… 34
4.3 部分因子設計之模擬退火-基因演算法的效能………………………… 34
4.3.1 FFD-SAGA對非限制條件問題之效能分析…………………………… 34
4.3.2 FFD-SAGA對限制條件問題之效能分析……………………………… 39
4.4 FFD-SAGA對工程最佳化問題之效能分析………………………………… 39
4.4.1 壓力容器最佳化設計…………………………………………………… 39
4.4.2 焊接樑最佳化設計……………………………………………………… 41
4.4.3 拉張/壓縮彈簧重量最佳化設計……………………………………… 42
4.4.4 Himmelblau的非線性最佳化問題…………………………………… 44
第五章 結論和未來展望……………………………………………………… 55
參考文獻……………………………………………………………………… 56
附錄（已發表論文：使用部分因子設計建構直交模擬退火法之效能分析，發表於
第九屆人工智慧與應用研討會，政治大學，93年11月5-6日）…………… 59

[1]Goldberg, D.E., Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, Reading Massachusetts, 1989.

[2]Kirkpatrick, S., Gelatt, C.D., and Vecchi, M.P., “Optimization by Simulated Annealing,” Science, Vol. 220, pp. 671-680, 1983.

[3]Leung, Y.W., and Wang Y., “An Orthogonal Genetic Algorithm with Quantization for Global Numerical Optimization,” IEEE Trans. On Evolutionary Computation, Vol. 5, No. 1, pp. 41-53, 2001.

[4]Michalewicz, Z., Genetic Algorithms + Data Structures = Evolution Programs, Springer-Verlag, Berlin Heidelberg, 1995.

[5]Ingber, L., “Simulated Annealing: Practice Versus Theory,” Math. Comput. Modelling, Vol. 18, No. 11, pp. 29-57, 1993.

[6]Dorigo, M., and Gambardella, L.M., ”Ant Colony System：A Cooperative Learning Approach to the Traveling Salesman Problem, “ IEEE Trans. on Evolutionary Computation, Vol. 1, No.1, pp. 53-66, 1997.

[7]Kennedy, J., and Eberhart, R.C., “Particle Swarm Optimization,” Proc. IEEE Int. Conf. on Neural Networks (Perth, Australia), IEEE Service Center, Piscataway, NJ, Vol. 4, pp. 1942-1948, 1995.

[8]Bhote, K.R., World Class Quality: Using Design of Experiments to make it Happen, American Management Association, New York, 1991.

[9]Montgomery, Design and Analysis of Experiments, 4/e. John Wiley & Sons, Canada, 1997.

[10]URL: http://www.itl.nist.gov/div898/handbook/index.htm

[11]Srinivas, M., and Patnaik, L.M., “Adaptive Probabilities of Crossover and Mutation in Genetic Algorithms,” IEEE Trans. On Systems, Man and Cybernetics, Vol. 24, No. 4, pp. 656-667, 1994.

[12]Adler, D., ”Genetic Algorithms and Simulated Annealing：A Marriage Proposal,” IEEE Int. conf. Neural Networks, San Francisco, pp. 1104-1109, 1993.

[13]Esbensen, H., and Mazumder, P., “SAGA:A Unification of the Genetic Algorithm with Simulated Annealing and its Application to Macro-Cell Placement,” IEEE 7th Int. Conf. on VLSI Design, India, pp. 211-214, 1994.

[14]Lin, F.T., Kao, C.Y., and Hsu, C.C., “Applying the Genetic Approach to Simulated Annealing in Solving Some NP-Hard Problems,” IEEE Trans. On System, Man and Cybernetics, Vol. 23, No. 6, pp. 1752-1767, 1993.

[15]Mahfoud, S.W., and Goldberg, D.E., “Parallel Recombinative Simulated Annealing：A Genetic Algorithm,” Parallel Computing, Vol. 21, pp. 1-28, 1995.

[16]Koakutsu, S., and Kang. M., “Genetic Simulated Annealing and Application to Non-slicing Floorplan Design,” 5th ACM/SIGDA Physical Design workshop, Virginia, USA, Technical Report, 1996.

[17]Zhang, O., and Leung, Y.W., “An Orthogonal Genetic Algorithm for Multimedia Multicast Routing,” IEEE Trans. On Evolutionary Computation, Vol. 3, No. 1, pp.53-62, 1999.

[18]Tsai, J.T., Liu. T.K., and Chou. J.H., “Hybrid Taguchi-Genetic Algorithm for Global Numerical Optimization,” IEEE Trans. On Evolutionary Computation, Vol. 8, No. 4, pp.365-377, 2004.

[19]Ho, S.Y., Shu, L.S., and Chen J.H., “Intelligent Evolutionary Algorithms for Large Parameter Optimization Problems,” IEEE Trans. On Evolutionary Computation, Vol. 8, No. 6, pp. 522-541, 2004.

[20]Ho, S.Y., and Lin, Y.K., “Orthogonal Simulated Annealing for Floorplanning,” 7th Artificial Intelligence and Applications Conference, Taichung, R.O.C, pp 469-474, 2002.

[21]Goldberg D.E., and Richardson, J., “Genetic Algorithms with Sharing for Multimodal Function Optimization,” Genetic Algorithms and their Applications: Proceedings of the Second International Conference on Genetic Algorithms, pp. 41-49, 1987.

[22]Liu, J.L., “New Construction of an Intelligent Genetic Algorithm,” 8th Artificial Intelligence and Applications Conference, Taipei, R.O.C, 2003.

[23]Koziel, S., and Michalewicz, Z., “Evolutionary Algorithms, Homomorphous Mappings, and Constrained Parameter Optimization,” IEEE Trans. On Evolutionary Computation, Vol. 7, No. 1, pp. 19-44, 1999.

[24]Runarsson, P.T., and Yao, X., “Stochastic Ranking for constrained Evolutionary Optimization,” IEEE Trans. On Evolutionary Computation, Vol. 4, No. 3, pp. 284-294, 2000.

[25]Hu, X.H., Eberhart, R.C., and Shi, Y., “Engineering Optimization with Particle Swarm,” Proceedings of the IEEE Swarm Intelligence Symposium 2003 (SIS 2003), Indianapolis, Indiana, USA, pp. 53-57, 2003.

[26]Coello Coello, C.A. “Use of a Self-Adaptive Penalty Approach for Engineering Optimization Problems,” Computers in Industry, Vol. 41, No. 2, pp. 113-127, 2000.

[27]Ray, T. and Liew, K.M., ” Society and Civilization: An optimization algorithm based on the simulation of social behavior,” IEEE Trans. On Evolutionary Computation, Vol. 7, No. 4, pp. 386-396, 2003.

[28]Reklaitis, G.V., Ravindran, A. and Ragsdell, K.M., Engineering Optimization Methods and Applications, New York: John Wiley and Sons, 1983.

[29]Deb, K., “Optimal Design of a Welded Beam via Genetic Algorithms,” AIAA Journal, Vol. 29, No. 8, pp. 2013-2015, 1991.

[30]Homaifar, A.A., Lai, S.H.Y., and Qi, X., “Constrained Optimization via Genetic Algorithms,” Simulation, Vol. 62, No. 4, pp. 242-254, 1994.