臺灣博碩士論文加值系統

以往在不同的領域中，通常將群體視為均勻混合的狀態，而過分忽略了不同群體結構的差異。但不管是在最佳化的演算法，或是演化賽局理論的概念中，群體結構往往占了很重要的角色。
近來在最佳化的研究發現，高連接性的群體結構較適用於單一最佳點的目標函數，但低連接性的群體結構則更適用於處理多個最佳點的最佳化問題。而在演化賽局理論相關的文章中指出，高連接性的群體網路會使個體傾向採用背叛的策略，但低連接性的群體網路則可能促進個體之間的合作或是產生合作者與背叛者共存等複雜的結果。
本研究中將賽局理論中混合策略的概念應用於差分演算法，試圖改善差分演算法處理多峰函數最佳化的能力，其中使用低連接性的方格狀群體結構，讓演算法更適用於處理多個最佳點的最佳化問題，並藉由模擬演化賽局的DB更新規則維持一定比例的混合策略，討論在不同目標函數與不同比例的混合策略下，使用混合策略的演算法與使用純粹策略的演算法效能上的差異，以及解釋混合策略較適用於某些目標函數的原因。最後藉著函數產生機構的最佳化例子證實所發展的演算法搜尋多個最佳點的效能與處理實際問題的能力。

In the field of science and technology, we often take it for granted that population is composed of well-mixed individuals. But how individuals are connected to each other can lead to different outcomes, and population structure do matter.
According to recent researches on optimization, population topology proved to have a huge impact on the performance of algorithm. While population with higher connectivity like well-mixed population is more suitable for unimodal optimization, population with lower connectivity can deal with more complicated one such as multimodal optimization. But not only in optimization but also in the field of evolutionary game theory does population structure make difference. In Prisoner’s dilemma, highly-connected population will favor defect than cooperate. On the contrary, when individuals are loosely-connected, cooperators can form small clusters to resist defectors, resulting in much more complicated consequences.
Inspired from the concept of mixed-strategy in game theory, we attempted to improve the performance of differential evolution algorithm(DE) on unconstrained multimodal problems. On the one hand, we adopted cellular population in order to locate multiple optima. On the other hand, by DB updating process we were able to control specific proportion of each strategy in population. In order to distinguish the performance between mixed-strategy and pure strategy, discussion and comparison had been made with other algorithms in various benchmark functions. Last but not least, the proposed algorithm is applied to an example of function generation optimization to show its ability to handle real-world engineering problems.

誌謝.................................................................................................................................... i
摘要................................................................................................................................... ii
Abstract ............................................................................................................................ iii
目錄.................................................................................................................................. iv
圖次.................................................................................................................................. vi
表次................................................................................................................................ viii
第一章 緒論..................................................................................................................... 1
1-1研究背景 ............................................................................................................ 1
1-2動機與目的 ........................................................................................................ 2
1-3論文架構 ............................................................................................................ 2
第二章 差分演算法......................................................................................................... 3
2-1最佳化方法 ........................................................................................................ 3
2-1.1簡單形法 ................................................................................................. 3
2-1.2基因演算法 ............................................................................................. 5
2-1.3粒子群演算法 ......................................................................................... 7
2-2差分演算法 ........................................................................................................ 8
2-3多峰函數之最佳化 .......................................................................................... 12
2-4群體結構的影響 .............................................................................................. 14
2-4.1群體結構與粒子群演算法 ................................................................... 14
2-4.2群體結構與差分演算法 ....................................................................... 15
2-5測試函數與測試方法 ...................................................................................... 17
第三章 演化賽局理論................................................................................................... 27
3-1賽局理論 .......................................................................................................... 27
3-2演化動態 .......................................................................................................... 29
3-3群體結構的影響 .............................................................................................. 33
第四章 研究方法........................................................................................................... 37
4-1演化動態模擬 .................................................................................................. 37
4-1.1模擬方法 ............................................................................................... 37
4-1.2模擬結果 ............................................................................................... 39
4-2混合策略之格狀差分演算法 .......................................................................... 42
4-2.1演算法架構 ........................................................................................... 42
4-2.2演算法流程 ........................................................................................... 43
4-3混合策略之選擇與比較 .................................................................................. 46
第五章 結果與討論....................................................................................................... 52
5-1測試結果與比較 .............................................................................................. 52
5-2函數產生機構之最佳化 .................................................................................. 58
5-2.1目標函數推導 ....................................................................................... 58
5-2.2函數產生機構最佳化例子 ................................................................... 63
5-2.3函數產生機構最佳化例子討論 ........................................................... 69
第六章 結論與未來展望............................................................................................... 70
參考文獻......................................................................................................................... 71

[1] Spendley, W. G. R. F. R., Hext, G. R., &; Himsworth, F. R. (1962). Sequential application of simplex designs in optimisation and evolutionary operation. Technometrics, 4(4), 441-461.
[2] Nelder, J. A., &; Mead, R. (1965). A simplex method for function minimization. The computer journal, 7(4), 308-313.
[3] Box, M. J. (1965). A new method of constrained optimization and a comparison with other methods. The Computer Journal, 8(1), 42-52.
[4] 林豐澤. (2005). 演化式計算上篇: 演化式演算法的三種理論 模式 Evolutionary Computation Part 1: Three Theoretic Models of Evolutionary Algorithms. 智慧科技與應用統計學報, 3(1), 1-28.
[5] Eberhart, R., &; Kennedy, J. (1995, October). A new optimizer using particle swarm theory. In Micro Machine and Human Science, 1995. MHS''95., Proceedings of the Sixth International Symposium on (pp. 39-43). IEEE.
[6] Price, K. V. (1996, June). Differential evolution: a fast and simple numerical optimizer. In Fuzzy Information Processing Society, 1996. NAFIPS. 1996 Biennial Conference of the North American (pp. 524-527). IEEE.
[7] Storn, R., &; Price, K. (1997). Differential evolution–a simple and efficient heuristic for global optimization over continuous spaces. Journal of global optimization, 11(4), 341-359.
[8] Mezura-Montes, E., Velázquez-Reyes, J., &; Coello Coello, C. A. (2006, July). A comparative study of differential evolution variants for global optimization. In Proceedings of the 8th annual conference on Genetic and evolutionary computation (pp. 485-492). ACM.
[9] Epitropakis, M. G., Plagianakos, V. P., &; Vrahatis, M. N. (2011, April). Finding multiple global optima exploiting differential evolution''s niching capability. In Differential Evolution (SDE), 2011 IEEE Symposium on (pp. 1-8). IEEE.
[10] Li, X. (2010). Niching without niching parameters: particle swarm optimization using a ring topology. Evolutionary Computation, IEEE Transactions on, 14(1), 150-169.
[11] Thomsen, R. (2004, June). Multimodal optimization using crowding-based differential evolution. In Evolutionary Computation, 2004. CEC2004. Congress on (Vol. 2, pp. 1382-1389). IEEE.
[12] Kennedy, J., &; Mendes, R. (2002). Population structure and particle swarm performance. In Evolutionary Computation, 2002. CEC''02. Proceedings of the 2002 Congress on (Vol. 2, pp. 1671-1676). IEEE.
[13] Dorronsoro, B., &; Bouvry, P. (2010). Differential evolution algorithms with cellular populations. In Parallel Problem Solving from Nature, PPSN XI (pp. 320-330). Springer Berlin Heidelberg.
[14] Epitropakis, M. G., Plagianakos, V. P., &; Vrahatis, M. N. (2012, June). Multimodal optimization using niching differential evolution with index-based neighborhoods. In Evolutionary Computation (CEC), 2012 IEEE Congress on (pp. 1-8). IEEE.
[15] Hofbauer, J., &; Sigmund, K. (1998). Evolutionary games and population dynamics. Cambridge University Press.
[16] Nowak, M. A., Tarnita, C. E., &; Antal, T. (2010). Evolutionary dynamics in structured populations. Philosophical Transactions of the Royal Society B: Biological Sciences, 365(1537), 19-30.
[17] Ohtsuki, H., &; Nowak, M. A. (2006). The replicator equation on graphs. Journal 72
of theoretical biology, 243(1), 86-97.
[18] Ohtsuki, H., &; Nowak, M. A. (2006). Evolutionary games on cycles. Proceedings of the Royal Society B: Biological Sciences, 273(1598), 2249-2256.
[19] Matsuda, H., Ogita, N., Sasaki, A., &; Satō, K. (1992). Statistical Mechanics of Population The Lattice Lotka-Volterra Model. Progress of theoretical Physics, 88(6), 1035-1049.
[20] 藍兆杰、徐偉傑、陳怡君譯、Dixit,A and Skeath,S著（2002），策略的賽局，台北，弘智文化事業有限公司。