臺灣博碩士論文加值系統

多目標最佳化方法近年來廣泛的被運用於各種不同的領域，其中進化式演算法(Evolutionary Algorithms, EAs) 模仿自然界進化的原則以逐步搜尋朝向最佳化，與其他傳統搜尋之最佳化方法有很大的不同。在以往多目標最佳化問題的研究中，研究範圍有很大的比例是把焦點放在不具限制條件的演算法設計上，然而在真實環境中，多目標最佳化往往需要考慮到諸多限制條件的因素，而限制式處理機制普遍都採用懲罰函數法(Penalty Function)。但是懲罰函數法的設計需要針對不同的測試問題調整懲罰參數(Penalty Parameter)，在設計上具有困難性與不確定性。本研究將進化式演算法中新發展出的兩個演算法－多目標微粒群最佳化與多目標仿電磁最佳化導入一套不需要因應不同的測試問題而改變參數的限制式處理機制，透過難易不同的測試函數以不同的績效評量指標來分析其結果。

Multi-Objective Optimization (MOO) have been recently used in different kinds of fields. In methods of solving optimal solutions, there are different from classical method and Evolutionary Algorithms (EAs). EAs mimics nature’s evolutionary principles to drive its search towards an optimal solution. The mostly past research of MOO problems often focus on a algorithm of non-constrained problems. However, there are so many constrained MOO problems in the real world, and the constrains mechanism usually adopt a penalty function. But the design of penalty function must introduce penalty parameter to fit different kinds of problems, that’s the most difficult and uncertain factor to handle it. Therefore, this research introduces two famous algorithms- MOPSO and MOEMO with a mechanism without additional parameter to handle constrained problems. We use performance indices for measuring results of different complex problems.

誌謝 I
中文摘要 II
英文摘要 III
目錄 IV
圖目錄 VI
表目錄 VII
第一章 緒 論 1
1.1 研究背景 1
1.2 研究動機與目的 4
1.3 研究方法與流程 7
第二章 文獻探討 9
2.1 多目標最佳化 9
2.1.1 多目標最佳化介紹 9
2.1.2 柏拉圖最佳解 9
2.2 微粒群最佳化 12
2.2.1微粒群演算法之發展背景 12
2.2.2微粒群演算法說明 13
2.2.3 多目標微粒群演算法 16
2.3 仿電磁最佳化 (Electromagnetism-like Optimization, EMO) 19
2.3.1仿電磁演算法發展背景 19
2.3.2仿電磁演算法說明 19
2.3.3 多目標仿電磁演算法 22
2.4 限制式規劃與研究 25
2.4.1忽略法 (Ignoring Infeasible Solutions) 25
2.4.2懲罰函數法(Penalty Function Approach) 25
2.4.3 Jiménez-Verdegay-Goméz-Skarmeta方法 26
2.4.4 限制競賽法 (Constrained Tournament Method) 28
2.4.5 Ray-Tai-Seow方法 29
第三章 具限制式處理機制之多目標進化式演算法 31
3.1共生機制與限制最佳化問題 31
3.2 以不可行度機制處理限制式問題 34
3.3 結合共生機制之多目標進化式演算法 36
3.3.1 結合限制式處理機制之多目標微粒群演算法 36
3.3.2 結合限制式處理機制之多目標仿電磁演算法 41
第四章 研究結果與驗證 49
4.1 互動式多目標進化式演算法之系統建置 49
4.1.1 開發環境簡介 49
4.1.2 測試函數與績效指標 51
4.2 測試函數一 54
4.3 測試函數二 56
4.4 測試函數三 59
4.5 測試函數四 61
4.6 測試函數五 64
4.7 測試函數六 67
4.8 測試結論 71
第五章 結論與建議 72
5.1 研究結論 72
5.2 未來研究與建議 74
參考文獻 75

1.王躍宣、劉連臣、牟盛靜、吳澄，「處理帶約束的多目標優化進化算法」，清華大學學報 (自然科學版) ，pp. 103-106，2005。
2.徐業良，「工程最佳化設計」，台北市，宏明書局，1995。
3.許志義，「多目標決策」，台北市，五南書局，2003。
4.Alvarez-Benitez, J. E., Everson, R. M. and Fieldsend, J. E., A MOPSO Algorithm Based Exclusively on Pareto Dominance Concepts, The Third International Conference on Evolutionary Mutli-Criterion Optimization Mexico, March 8-11, pp. 459-473, 2005.
5.Bäck. T. Evolutionary Algorithms in Theory and Practice. Oxford University Press, New York, 1996.
6.Binh, T. T. and Korn, U.,MOBES: A Multiobjective evolution strategy for constrained optimization problems. In The Third International Conference on Genetic Algorithms(Mendel 97), pp. 176-182, 1997.
7.Bïrbïl, S.I., Stochastic Global Optimization techniques, Department of Industrial engineering, A Dissertation Submitted to the Graduate Faculty of North Carolina State University., 2002.
8.Bïrbïl, S. I., and Fang, S. C., An Electromagnetism-like Mechanism for Global Optimization, Journal of Global Optimization, Vol. 25, pp. 263–282, 2003.
9.Boeringer D. W., Douglas H. Werner, Particle Swarm Optimization Versus Genetic Algorithms for Phased Array Synthesis. IEEE Trans on Antennas and Propagation Vol. 52, No. 3,pp. 771-779, 2004.
10.Boyd, R., and Richerson, P. J., Culture and the Evolutionary Process., Chicago: University of Chicago Press., 1985.
11.Chunlin, J.I., A Revised Particle Swarm Optimization Approach for Multi-objective and Multi-constraint Optimization, In Proceedings of Genetic and Evolutionary Computation Conference (GECCO-2004), 2004.
12.Coello, C. A. C., Lechuga, M. S., MOPSO: A Proposal for Multiple Objective Particle Swarm Optimization., In Proceedings of the 2002 Congress on Evolutionary Computation, IEEE Press., pp. 1051-1056, 2002.
13.Coello, C. A. C. and Christiansen, A. D., MOSES : A Multiobjective optimization tool for engineering design. Engineering Optimization, Vol 31, No. 3, pp. 337-368, 1999.
14.Coello, C. A. C., Pulido G.. T., Lechuga M. S., Handling Multiple Objectives with Particle Swarm Optimization.IEEE Transactions on Evolutionary Computation, Vol 8, No 3, pp. 256-279,2004.
15.Deb, K., An efficient constraint handling method for genetic algorithms. Computer Methods in Applied Mechanics and Engineering Vol. 186, No. 2-4, pp. 311-338, 2000.
16.Deb, K. , Multi-Objective Optimization using Evolutionary Algorithms, 2001
17.Deb, K. and Agrawal, S., Understanding interactions among genetic algorithm parameters. In Foundations of Genetic Algorithms 5 (FOGA-5), pp. 265-286, 1999.
18.Deb, K., Nonlinear goal programming using multi-objective genetic algorithms. Journal of the Operational Research Society, Vol 52, no 3., 291-302., 2001.
19.Debels, D., De Reyck, B., Leus, R. and Vanhoucke, M., A Hybrid Scatter search/electromagnetism Meta-Heuristic for Project Scheduling, European Journal of Operational Research, Vol. 169, pp. 638-653, 2005.
20.Dong, Y., Tang, J.F., Xu B.D. and Wang D.W., An Application of Swarm Optimization to Nonlinear Programming, Computers and Mathematics whit Applications, Vol. 49, pp.1655-1668, 2005.
21.Dorigo, M., Optimization, Learning and Natural Algorithms, Ph.D. thesis, DEI, Politecnico di Milano, Italy. pp. 140, 1992.
22.Feng, C. W., Liu, L., and Burns, S. A., Using genetic algorithms to solve construction time-cost trade-off problems, Journal of Computing in Civil Engineering, ASCE, Vol. 11, No. 3, pp. 184-189, 1997.
23.Jiménez, F., Verdegay, J. L. and Goméz-Skarmeta, A. F., Evolutionary techniques for constrained multiobjective optimization problems. In Proceedings of the Workshop on Multi-Criterion Optimization Using Evolutionary Methods held at Genetic and Evolutionary Computation Conference (GECCO-1999), pp. 115-116, 1999.
24.Jones, D. F., Mirrazavi S. K. and Tamiz, M., Multi-objective meta heuristics: An overview of the current state-of-the-art. Europe an Journal of Operational Research, Vol. 137, No. 1, pp. 1-9, 2002.
25.Kennedy, J., Eberhart, R., Particle swarm optimization, Proceedings of IEEE International Conference on Neural Networks, pp. 1942-1948, 1995.
26.Michalewicz, Z., Dasgupta, D., Le Riche, R.G., and Schoenauer, M., Evolutionary Algorithms for Constrained Engineering Problems, Computers & Industrial Engineering Journal, Vol.30, No.2, pp.851-870, 1996a.
27.Michalewicz, Z., Schoenauer, M., Evolutionary Algorithms for Constrained Parameter Optimization Problems. Evolutionary Computation, Vol. 4, No. 1, pp.1-32, 1996b.
28.Mu, S.J., Su H.Y., Chu J., Wang Y.X., An infeasibility degree selection based genetic algorithms for constrained optimization problems, In proceedings of IEEE international conference on systems man and cybernetics, Vol. 2, pp. 1950-1954, 2003.
29.Okabe T., Jin Y., Sendhoff B., A critical survey of performance indices for multi-objective optimisation, Proceedings of the 2003 congress on evolutionary computation (CEC 2003), Vol. 2, pp.862-869, 2003.
30.Osyczka, A. and Kundu, S., A new method to solve generalized multicriteria optimization problems using the simple genetic algorithm., Structural Optimization, Vol. 10, No. 2, pp. 94-99, 1995.
31.Rao, S., S., Optimization theory and application. New Delhi: Wiley Eastern Limited., 1984.
32.Ray, T., Tai, K. and Seow, K. C., An Evolutionary Algorithm for Multiobjective Optimization. Engineering Optimization., Vol. 33, No. 3, pp. 339-424., 2001.
33.Reynolds, C. W., Flocks, herds and schools: a distributed behavioral model., Computer Graphics, Vol. 21, No. 4, pp. 25-34, 1987.
34.Schaffer, J., D., Multiple objective optimization with vector evaluated genetic algorithms. Proceedings of the First International Conference on Genetic Algorithms. pp. 93-100, 1985.
35.Schott, J. R., Fault Tolerant Design Using Single and Multi-Criteria Genetic Algorithms. Master’s Thesis, Department of Aeronautics and Astronautics, Massachusetts Institute of Technology, Boston, MA, 1995.
36.Shi, Y. H., and Eberhart, R. C., A modified particle swarm optimizer , In IEEE World Congress on Computational Intelligence, IEEE Press, 1998a.
37.Shi, Y. H., and Eberhart, R. C., Empirical study of particle swarm optimization, Proceedings of the Evolutionary Computation 1999 Congress, Vol 3, pp. 1945-1950, 1999.
38.Shi, Y. H., and Eberhart, R. C., Parameter selection in particle swarm optimization, In Evolutionary Programming VII (Berlin, 1998), pp. 591–600, 1998b.
39.Srinivas, N. and Deb, K., Multi-objective function optimization using non-dominated sorting genetic algorithms, Evolutionary Computation Journal Vol. 2, No. 3, pp. 221-248, 1994.
40.Tanaka, M., GA-based decision support system for multi-criteria optimization. In Proceedings of the International Conference on Systems, Man and Cybernetics, Vol. 2, pp. 1556-1561, 1995
41.Tsou, C. S. and Kao, C. H., An Electromagnetism-Like Meta-Heuristic for Multi-Objective Optimization, Proceedings of 2006 IEEE Congress on Evolutionary Computation (CEC 2006)., pp.1172 - 1178, 2006.
42.Von Neumann, J. and O. Morgenstern: Theory of Games and Economic Behavior, Princeton, N. J., 1944.
43.White, D. J., Epsilon dominance and constraint partitioning in multiple objective problems. Journal of Global Optimization, Vol. 12, No.4, pp.435-448, 1998.
44.Wu, P., Yang, K. J. and Hung Y. Y., The Study of Electromagnetism-like Mechanism Based Fuzzy Neural Network for Learning Fuzzy If-Then Rules, Lecture Notes in Computer Science/Artificial Intelligence, Vol. 3684, pp. 382-388, 2005.
45.Xue, F., Multi-objective differential evolution: Theory and applications, Ph.D. dissertation, Rensselaer Polytechnic Institute, 2004.
46.Zavala, A. E. M., Aguirre, A. H. A., Diharce, E. R. V., Constrained optimization via particle evolutionary swarm optimization algorithm (PESO). In Proceedings of Genetic and Evolutionary Computation Conference (GECCO-2005), pp.209-216, 2005
47.Zitzler, E. and Thiele, L., Multi-objective evolutionary algorithms: a comparative case study and strengthen Pareto approach, IEEE Transaction on Evolutionary Computation, Vol. 3 No. 4, pp. 257-271, 1999.