臺灣博碩士論文加值系統

調和搜尋演算法(Harmony Search; HS)是將樂團演奏表現調整至最協調且美妙的現象引用到最佳化演算系統當中，而發展出一套全新的啟發式演算法。然而在最佳化問題的求解過程中，如何有效率的搜尋到目標函數的全域最佳解並不是一件容易的事，而調和搜尋演算法有不錯的搜尋精確度，但調和搜尋演算法由於微調方向依賴隨機化的方式求得，使得搜尋速度較慢，求解時間上消耗多，這對於決策者而言，是求解過程中的最大問題。
本研究提出直交調和搜尋演算法(Orthogonal Harmony Search; OHS)，主要透過結構上重新修正並應用直交表實驗設計(Orthogonal Experimental Design; OED)之技術以改良調和搜尋演算法。直交調和搜尋演算法主要以三項機制運作搜尋：(1)以直交交配來做全域搜尋(exploration)，(2)以直交微調來做區域搜尋(exploitation)，(3)以隨機方式尋找其他可行解。因此，直交調和搜尋演算法承襲調和搜尋演算法的搜尋精確度，結合直交表實驗設計具有優良經驗的推理能力與主效果分析，促使演算法在廣大的搜尋空間中，能夠為子代判斷正確的搜尋區域與方向，更快速向最佳解逼近以達到收斂並強化搜尋最佳解的能力。
本研究於直交表改良演算法的測試函數中，選出八個函數做實驗，實驗函數包含單一區域解與多重區域解問題。實驗結果除了與調和搜尋演算法比較之外，並與直交基因演算法(Orthogonal Genetic Algorithm; OGA)、直交模擬退火演算法(Orthogonal Simulated Annealing Algorithm; OSA)比較，整體結果直交調和搜尋演算法優於其他演算法，並證實本研究所提出之演算法在各種測試函數中能迅速且穩定向最佳解逼近。

Harmony search is a new heuristic algorithm, and it is conceptualized using the musical process of searching for a perfect state of harmony. How to search the global optimization solution efficiently in object function is difficult in the process of solving optimization problems. Harmony search have ability to find solutions closer to the optima but it consumes a lot of time. And it’s a big problem of HS for decision makers.
This paper brings up an Orthogonal Harmony Search (OHS). The main focal point of OHS is to revise harmony search and apply method of orthogonal experimental design to enhance it. OHS has three operators: (1) orthogonal clossover for global search, (2) orthogonal pitch adjustment for local search, (3) random search for feasible space. OHS use the systematic reasoning methods, ODE and factor analysis, to find the right direction to approach the optimal solution and speed the search ability.
We execute the proposed algorithm to solve eight test functions include of unimodal and multi-modal. Comparing with HS, OGA and OHS, we can find that OHS can quicker slove problems than them and more stable find optimal or close-to-optimal solutions.

摘要 I
ABSTRACT II
誌謝 III
目錄 IV
表目錄 V
圖目錄 VI
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 1
1.3 研究架構 2
1.4 研究工具 3
第二章 文獻探討 4
2.1 啟發式演算法相關文獻 4
2.1.1 基因演算法 4
2.2.2 演化策略 5
2.2.3 演化規劃 5
2.2.4 蟻拓尋優法 6
2.2.5 禁忌搜尋演算法 6
2.2.6 模擬退火演算法 7
2.2 調和搜尋演算法相關文獻 7
2.2.1 調和搜尋演算法介紹 7
2.2.2 調和搜尋演算法與基因演算法之比較 12
2.2.3 調和搜尋演算法之相關文獻 13
2.3 直交表結合搜尋演算法之相關文獻 14
第三章 研究方法 16
3.1 直交表實驗設計方法 17
3.1.1 直交表 17
3.1.2 建立直交表 19
3.1.3 主效果分析 21
3.1.4 最陡路徑法 22
3.2 直交調和搜尋演算法 22
3.2.1 初始解 22
3.2.2 演算法搜尋 23
第四章 數值實驗與分析 31
4.1 實驗測試函數 31
4.2 參數實驗設計及說明 35
4.3 OHS與其他演算法實驗結果之比較 38
4.4 OHS與OGA初始解之特徵探討 48
4.5 實驗結論 51
第五章 結論與未來建議 54

參考文獻
[1]吳子逢，何信瑩。使用直交實驗設計的高效率演化策略及其應用，逢甲大學碩士論文，2003。
[2]林宏穗，何信瑩。設計一種新型的直交粒子群最佳化演算法，逢甲大學碩士論文，2004。
[3]Arabas, J., Mulawka, J. and Pokrasniewicz, J., “A new class of the crossover operators for the numerical optimization,” Proceedings of the 6th International Conference on Genetic Algorithms, Morgan Kaufmann, San Mateo, CA, pp. 42-48, 1995.
[4]Bäck, T., Evolutionary Algorithms in Theory and Practice. New York: Oxford Univ. Press, 1996.
[5]Cantù-Paz, E ., A summary of research on parallel genetic algorithms. IlliGAL Report No. 95007, University of Illinois at Urbana-Champaign, July, 1995.
[6]Carlos Andrés Peña-Reyes, Moshe Sipper, “Evolutionary Computation in Medicine: an overview,” Artificial Intelligence in Medicine, 19, pp. 1-23, 2000.
[7]Colorni, A., Dorigo, M. and Maniezzo, V., “An investigation of some properties of an ant algorithm,” Proceedings of the Parallel Problem Solving from Nature Conference, R. Manner and B. Manderick Eds. Brussels, Belgium: Elsevier, pp.509-520, 1992.
[8]Colorni, A., Dorigo, M. and Maniezzo, V., “Distributed optimization by ant colnies,” Proceedings of the First European Conference Artificial Life, F. Varela and P. Bourgine, Eds. Paris, France: Elsevier, pp.134-142, 1991.
[9]Darrell Whitley, L. and Kauth, J., GENITOR: a different genetic algorithm, Proceedings of the 1988 Rocky Mountain Conference on Artifical Intelligence, 1988.
[10]Darrell Whitley, L. and Starkweather, T., “GENITOR II: a distributed genetic algorithm,” Journal of Experimental and Theoretical Artifical Intelligence 2, pp. 189-214, 1990.
[11]Darrell Whitley, L., The GENITOR algorithm and selective pressure: why rank based allocation of reproductive trials is best, in: J. D. Schaffer (Ed.), Proceedings of the Third International Conference on GAs, Morgan Kaufmann, Los Atlos, CA, pp. 116-121., 1989
[12]Dorigo, M., Bonabeau, E. and Theraulaz, G., “Ant algorithm and stigmergy,” Future Generation Computer Systems, 16, pp. 851-871, 2000.
[13]Dorigo, M., Caro, G.D. and Gambarsella, L.M., “Ant algorithms for discrete optimization,” Artificial Life, 5, pp. 137-172, 1999.
[14]Dorigo, M., Maniezzo, V. and Colorni, A., “Positive feedback as a research strategy,” Technology Report 91-016, Politecnico di Milano, 1991.
[15]Eshelman, L. J. and Schaffer, D., Preventing premature convergence in genetic algorithms by preventing incest, in: L. Booker, R. Belew (Eds.), Proceedings of the Fourth International Conference on GAs, Morgan Kaufmann, Los Atlos, CA, 1991.
[16]Eshelman, L. J. and Schaffer, J. D., Real-coded genetic algorithms and intervalschemata. In Foundations of Genetic Algorithms 2 (FOGA-2), pp.187-202, 1993.
[17]Fogel, L. J., “Autonomous automata,” Ind. Res., vol. 4, pp. 14–19, 1962.
[18]Fogel, L. J., “On the organization of intellect,” Ph.D. dissertation, University of California, Los Angeles, 1964.
[19]Fogel, L. J., Owens, A. J., & Walsh, M. J., Artificial intelligence through simulated evolution. New York: Wiley, 1966.
[20]Geem Z.W., Kim J.-H., Loganathan GV, “A new heuristic optimization algorithm: harmony search,” Simulation 76(2), pp. 60-68, 2001.
[21]Geem Z.W., Kim J.-H., Loganathan GV, “Harmony search optimization: Application to pipe network design,” Int J Modell Simulat 22(2), pp. 125-133, 2002.
[22]Geem Z.W., Lee S.-K., “A new structural optimization method based on the harmony search algorithm,” Computers and Structures 82, 781-798, 2004.
[23]Geem Z.W., Lee S.-K., “A new meta-heuristic algorithm for continuous engineering optimization: harmony search theory and practice,” Comput. Methods Appl. Mech. Engrg. 194, pp. 3902-3933, 2005.
[24]Glover F., “Heuristic for integer programming using surrogate constraints,” Decision Sci. 8(1), pp. 156-166, 1977.
[25]Goldberg, D. E., Genetic Algorithms in Search, Optimazation and Machine Learning, Addison-Wesley, Reading, MA, 1989.
[26]Goldberg, D. E., Deb, K. and Korb, B.,Messy genetic algorithms revisited: Nonuniform size and scale. Complex Systems 4(4), pp. 415-444, 1990.
[27]Goldberg, D. E. and Deb, K., A comparison of selection schemes used in genetic algorithms. In Foundations of Genetic Algorithms 1 (FOGA-1), pp. 69-93, 1991.
[28]Goldberg, D. E., Korb, B. and Deb, K., Messy genetic algorithms: Motivation, analysis and first results. Complex Systems 3(5), pp. 493-530, 1989.
[29]Ho S.-Y. and Chen J.-H., “A GA-based systematic reasoning approach for solving traveling salesman problems using an orthogonal array crossover,” High Performance Computing in the Asia-Pacific Region, 2000. Proceedings. The Fourth International Conference/Exhibition on, vol.2, no.pp.659-663 vol.2, 2000.
[30]Ho S.-J., Ho S.-Y, and Shu L.-S., “A Novel Orthogonal Simulated Annealing Algorithm for Optimization of Electromagnetic Problems,” IEEE TRANSACTIONS ON MAGNETICS 40(4), 2004.
[31]Ho S.-Y., Ho S.-J., and Lin Y.-K., “An orthogonal simulated annealing for floorplanning problems,” IEEE Trans. VLSI Syst. 12, 2004.
[32]Holland, J. H., “Outline for a logical theory of adaptive systems,” J. Assoc. Comput. Mach., vol. 3, pp. 297–314, 1962.
[33]Holland, J. H., Adaptation in Natural and Artificial Systems. Ann Arbor, MI: Univ. of Michigan Press, 1975.
[34]Holland, J. H. and Reitman, J. S., “Cognitive systems based on adaptive algorithms,” in Pattern-Directed Inference Systems, D. A. Waterman and F. Hayes-Roth, Eds. New York: Academic, 1978.
[35]J. Yen, J. C. Liao, B. Lee and D. Randolph, A hybrid approach to modeling metabolic systems using a genetic algorithm and simplex method, IEEE Transactions on System, Man, and Cybernetics-Part B: Cybernetics, 28(2), pp. 173-191, 1998.
[36]Kirkpatrick S., Gelatt C. and Vecchi M., “Optimization by simulated annealing,” Science 220(4598), pp. 671-680, 1983.
[37]Koza, JR., Genetic programming: a paradigm for genetically breeding populations of computer programs to solve problems. Technical Report STANCS-90-1314, Department of Computer Science, Stanford University, June 1990.
[38]Koza, JR., Genetic Programming. Cambridge, MA: MIT Press, 1992.
[39]Leung Y.-W. and Wang Y., “An orthogonal genetic algorithm with quantization for global numerical optimization,” IEEE Trans. Evol. Comput. 5, pp. 41–53, 2001.
[40]Mitsuo Gen, Runwei Cheng, Genetic Algorithms and Engineering Design, Wiley, New York, 1997.
[41]Pierreval, H., Caux, C., Paris J.L. and Viguier, F., “Evolutionary Approaches to the Design and Organization of Manufacturing Systems,” Computers & Industrial Engineering, 44, pp. 339-364, 2003.
[42]Rechenberg, I., Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Stuttgart, Germany: Frommann-Holzboog, 1973.
[43]Rechenberg, I., Evolutionstrategie ’94. Frommann-Holzboog, Stuttgart, 1994.
[44]Renders, J.-M. and H. Bersini, “Hybridizing genetic algorithms with hill-climbing methods for global optimization: Two possible ways, ” In Z. Michalewicz, J. D. Scha_er, H.-P. Schwefel, D. B. Fogel, and H. Kitano (Eds.), Proceedings of the First IEEE International Conference on Evolutionary Computation, pp. 312-317, IEEE Press, 1994.
[45]Schwefel, H.-P., Numerical Optimization of Computer Models. Chichester: Wiley, 1981.
[46]Schwefel, H.-P., Evolution and Optimum Seeking. New York: Wiley, 1995 (Sixth-Generation Computer Technology Series).
[47]Schwefel, H.-P., Evolution and Optimum Seeking, Wiley , New York, 1995.
[48]Schwefel, H.-P.,and Rudolph, G., “Contemporary evolution strategies,” in Advances in Artificial Life. 3rd Int. Conf. on Artificial Life (Lecture Notes in Artificial Intelligence, vol. 929), F. Mor´an, A. Moreno, J. J. Merelo, and P. Chac´on, Eds. Berlin, Germany: Springer, pp. 893–907, 1995.
[49]Shu L.-S., Ho S.-Y., and Ho S.-J., “OSA: Orthogonal Simulated Annealing Algorithm and Its Application to Designing Mixed H2/H Optimal Controllers,” IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS 34(5), 2004.
[50]Syswerda, G., “Uniform crossover in genetic algorithms,” Proceedings of the 3rd International Conference on Genetic Algorithms, pp.2-9, 1989.
[51]Wang T.-Y., Wu K.-B., A parameter set design procedure for the simulated annealing algorithm under the computational time constraint. Computer & Operations Research (26), pp. 665-678, 1999.
[52]Yao X., Liu Y., “Fast evolution strategies,” in Evolutionary Programming VI, P. J. Angeline, R. Reynolds, J. McDonnell, and R. Eberhart, Eds. Berlin, Germany: Springer-Verlag, pp. 151-161, 1997. (Available at ftp://www.cs.adfa.edu.au/pub/xin/yao_liu_ep97.ps.gz).