臺灣博碩士論文加值系統

在現代生活中，利用演化計算解決複雜的最佳化問題已是趨勢，而最佳化問題主要分為數值最佳化問題和組合最佳化問題。雖然最佳化被廣泛用於解最佳化問題，但是在分析解題過程時，往往需要花費很多時間和資源以改善演算法，使演化計算更進步。若是能夠減少在分析時所消耗的時機和資源，將能大幅的提升優化演化計算的速度，而目前，已經有研究者開發出可以協助分析演算計算解數值最佳化問題的工具，讓使用者可以便捷的分析解題過程。然而，目前卻沒有一個有效的工具，可以協助分析演算計算解組合最佳化問題。因此，本研究提出了一種新穎有用的工具，EPanel 2.0。EPanel 2.0是一個可以動態的顯示演算法解各類最佳化問題過程的視覺化界面。EPanel 2.0以視覺化的方式顯示組合最佳化問題編碼長相，詳細畫出解的每個位元，幫助使用者觀察此位元是否為0或為1，並動態呈現演化計算的演算過程，協助使用者比較多個世代解的差異，讓演算法研究者可以簡單的觀察到詳細的解題過程，清楚了解演算法的優缺點，方便改進演算法。針對不同的問題，也都能簡單易懂的方式顯示，降低改良演算法的難度，像是針對擺放的地圖模式。透過使用EPanel 2.0協助分析解題過程，能夠使得演化計算的開發與改良更加得直覺、便利，並且還能夠讓人人都能輕鬆的學習、了解演化計算。

Metaheuristic algorithms are used to solve complex optimization problems, including numerical optimization problems and combinatorial optimization problems. Currently, many applications exist to help users learn how algorithms work on numerical optimization problems, however, there are no applications offering the same tool for combinatorial optimization problems. Combinatorial optimization problems usually have high dimensionality, with only two statuses, making them very difficult to analyze. This study therefore presents a novel and useful tool, EPanel 2.0, to display the process of metaheuristic algorithms solving not only numerical optimization problems but also combinatorial optimization problems. EPanel 2.0 is implemented in JAVA, making it executable in multiple operating systems. EPanel 2.0 has a clear user interface, provides an animated representation of the process, and showing solutions in different ways on different situation. EPanel 2.0 allows users to analyze each step of the algorithm easily. In conclusion, EPanel 2.0 is a useful application in solving optimization problems.

Table of Contents
致謝辭........i
摘要........ii
Abstract........iii
Table of Contents........iv
List of Tables........vi
List of Figures........vii
I. Introduction........1
II. Proposed Application........6
A. Improvement of EPanel........6
B. Epin File for Combinatorial Optimization Problems........8
C. User Interface........9
D. Showing Current Best Solution........12
E. Showing All Solutions........14
F. Display Information........15
G. Display Probability........16
H. Change Generation........17
I. Display Fitness........20
J. Convergence graph........21
K. Map Mode........22
III. Discussion........24
A. GA Solving 0/1 Knapsack Problem........24
B. GNQTS Solving Portfolio Optimization Problem........29
C. QTS solving Sensor Deployment Optimization Problem........35
IV. Conclusion........40
References........41

List of Tables
Table 1: An epin file example of combinatorial optimization problem........9
Table 2: The structure of combinatorial optimization problem epin file........9
Table 3: An example of a map mode epin file........23

List of Figures
Fig. 1: Text log file........5
Fig. 2: EPanel........5
Fig. 3: Compere algorithms in generation........7
Fig. 4: Compere algorithms in evaluation........7
Fig. 5: Record, print screen, read file, and EPanel fans club buttons........11
Fig. 6: Stop, play, accelerate, decelerate and special feature buttons........11
Fig. 7: Show the best solution of each generation........13
Fig. 8: Color adjustment slider........13
Fig. 9: Display solution mode button........14
Fig. 10: Show all solutions........14
Fig. 11: Information button........15
Fig. 12: Probability button........16
Fig. 13: Generation bar........18
Fig. 14: Go to button........18
Fig. 15: Enter generation number........19
Fig. 16: Change Generation........19
Fig. 17: Display the fitness on the top........20
Fig. 18: Convergence graph button........21
Fig. 19: Convergence graph........21
Fig. 20: Map mode........23
Fig. 21 :Solution adjust button........23
Fig. 22: Beginning of GA process........26
Fig. 23: No solution change for many generations in GA process........26
Fig. 24: Best current solution of GA process........27
Fig. 25: Best solution of GA process........27
Fig. 26: Solutions still trying to escape local optima in GA process........28
Fig. 27: Convergence graph of GA process........28
Fig. 28: Beginning of GNQTS process........30
Fig. 29: Best and worst solution comparison, and beta-matrix update by theta........31
Fig. 30: Solution will be better while the marked bit is not chosen........31
Fig. 31: Change in bit choice........32
Fig. 32: GNQTS finds the best solution........32
Fig. 33: The best solution of each generation no longer changes........33
Fig. 34: A different status is chosen from the best solution........33
Fig. 35: All solutions converge at the best solution........34
Fig. 36: Convergence graph of GNQTS process........34
Fig. 37: Beginning of QTS process in map size 20×20........36
Fig. 38: End of QTS process in map size 20×20........37
Fig. 39: A better solution than QTS process in map size 20×20........37
Fig. 40: End of QTS process in map size 50×50........38
Fig. 41: Sensors that can be adjust........38
Fig. 42: Remove three sensors........39
Fig. 43: Replace with one sensors........39

[1] J. G. Digalakis and K. G. Margaritis, “An experimental study of benchmarking functions for genetic algorithms”, Int. J. Comput. Math., vol. 79, no. 4, pp. 403-416, 2002.
[2] J. Kennedy and R. Eberhart, “Particle swarm optimization”, IEEE International Conference on Neural Networks, pp. 1942-1948, 1995.
[3] S. Das and P. N. Suganthan, “Differential evolution: A survey of the state-of-the-art”, IEEE Trans. Evol. Comput., vol. 15, no. 1, pp. 4-31, Feb. 2011.
[4] K.-H. Han and J.-H. Kim, “Quantum-inspired evolutionary algorithm for a class of combinatorial optimization”, IEEE Transactions on Evolutionary Computation, vol. 6, no. 6, pp. 580-593, 2002.
[5] Li, Rongwei, and Dongxue Wang, “Clustering routing protocol for wireless sensor networks based on improved QPSO algorithm”, Advanced Mechatronic Systems, 2017 International Conference on. IEEE, pp. 168-172, 2017.
[6] H.-P. Chiang, Y.-H. Chou, C.-H. Chiu, S.-Y. Kuo, and Y.-M. Huang, “A quantum-inspired Tabu search algorithm for solving combinatorial optimization problems”, Soft Computing, vol. 18, no. 9, pp. 1771-1781, 2014.
[7] S.-Y. Kuo and Y.-H. Chou, “Entanglement-enhanced Quantum-inspired Tabu Search Algorithm for Function Optimization”, IEEE Access, 2017.
[8] Y.-H. Chou, S.-Y. Kuo, C.-Y. Chen, and H.-C. Chao, “A Rule-Based Dynamic Decision-Making Stock Trading System based on Quantum-Inspired Tabu Search Algorithm”, IEEE Access, Volume 2, pp. 883-896, 2014
[9] Y.-H. Chou, S.-Y. Kuo, L.-S. Yang and C.-Y. Yang, “Next Generation Metaheuristic: Jaguar Algorithm”, in IEEE Access, vol. 6, pp. 9975-9990, 2018.
[10] A. R. Syarif and W. Gata, “Intrusion detection system using hybrid binary PSO and K-nearest neighborhood algorithm”, 2017 11th International Conference on Information & Communication Technology and System (ICTS), pp. 181-186, 2017.
[11] G. M. Fan and H. J. Huang, “A novel binary differential evolution algorithm for a class of fuzzy-stochastic resource allocation problems”, 2017 13th IEEE International Conference on Control & Automation (ICCA), pp. 548-553, 2017.
[12] C.-H. Huang and H.-Y. Chen, “A Tool to Support Automated Testing for Web Application Scenario”, IEEE International Conference on Systems, Man and Cybernetics, pp. 2179-2184, 2006.
[13] P.-C. Huang and Y.-H. Kuo “A reliable context model for contextaware applications”, IEEE International Conference on Systems, Man and Cybernetics, pp. 246-250, 2008.
[14] H. Thiruvengada, S. Srinivasan and A. Gacic, “Design and implementation of an automated human activity monitoring application for wearable devices”, IEEE International Conference on Systems, Man and Cybernetics, pp. 2252-2258, 2008.
[15] J. Whipple, W. Arensman and M. S. Boler, “A public safety application of GPS-enabled smartphones and the android operating system”, IEEE International Conference on Systems, Man and Cybernetics, pp. 2059-2061, 2009.
[16] Indratmo, D. Riediger, N. Malloy and S. Bratt, “Design and evaluation of an interactive tabletop application for university open house”, IEEE International Conference on Systems, Man, and Cybernetics, pp. 1793-1796, 2014.
[17] M. Numazawa, K. Ai and M. Noto, “Education and learning support system using proposed note-taking application”, IEEE International Conference on Systems, Man, and Cybernetics, pp. 3617-3622, 2014.
[18] K.-C. Tan, T.-H. Lee, D. Khoo and E.-F. Khor, “A multiobjective evolutionary algorithm toolbox for computeraided multiobjective optimization”, in IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), vol. 31, no. 4, pp. 537-556, 2001.
[19] Y.-H. Chou, S.-Y. Kuo, W. J. Lai, and W.-B. Lai, “A visualization tool for observing metaheuristic algorithm: Epanel”, IEEE International Conference on Systems, Man, and Cybernetics, pp. 2826-2831, 2017.
[20] C. Sachdeva and S. Goel, “An improved approach for solving 0/1 Knapsack Problem in polynomial time using Genetic Algorithms”, International Conference on Recent Advances and Innovations in Engineering (ICRAIE-2014), pp. 1-4, 2014.
[21] Y.-H. Chou, S.-Y. Kuo, Y.-C. Jiang, and C.-Y. Chen, “A Novel Portfolio Optimization Model based on Trend Ratio and Evolutionary Computation”, IEEE Transactions on Emerging Topics in Computational Intelligence, (Under Minor Revision), 2018.
[22] S.-Y. Kuo, Y.-H. Chou, and C.-Y. Chen, “Quantum-inspired algorithm for cyber-physical visual surveillance deployment systems”, Computer Networks, vol. 117, pp. 5-18, 2017.