Responsive image
博碩士論文 etd-0723107-140832 詳細資訊
Title page for etd-0723107-140832
論文名稱
Title
利用粒子群優化演化法自動化產生測試資料
Automatic test data generation by particle swarm optimization
系所名稱
Department
畢業學年期
Year, semester
語文別
Language
學位類別
Degree
頁數
Number of pages
80
研究生
Author
指導教授
Advisor
召集委員
Convenor
口試委員
Advisory Committee
口試日期
Date of Exam
2007-06-27
繳交日期
Date of Submission
2007-07-23
關鍵字
Keywords
軟體測試、粒子群優化演算法、結構測試
none
統計
Statistics
本論文已被瀏覽 5849 次,被下載 28
The thesis/dissertation has been browsed 5849 times, has been downloaded 28 times.
中文摘要
自動產生軟體測試資料近年來成為一個熱門的研究領域,而針對結構測試(Structural Testing)乃是最常見的應用。許多方法也被提出用來解決這個問題,其中又以基因演算法(Genetic Algorithm)最為盛行。然而它是否為最好的方法還不得而之。本論文嘗試導入粒子群優化演算法(Particle Swarm Optimization)來解決這個問題,並改良原本的粒子群優化演算法來提升其效能。

在本論文中,我們把這改良的新方法稱為h-PSO。本論文提出此方法的動機在於,從許多文獻中得知,粒子群優化演算法在連續解空間以及在多維度的解空間上,表現出的效能比基因演算法好,所以正適合用在結構測試的領域上。而在本論文的實驗中,我們可以發現h-PSO比起結合區域搜尋和基因演算法的MA,方法較為簡單,效能也較佳。
Abstract
none
目次 Table of Contents
1. 序論 1
1.1. 研究背景 1
1.2. 研究動機與目標 4
1.3. 論文架構 5
2. 相關文獻 6
2.1. 軟體測試(Software testing) 6
2.2. 結構化測試(Structural testing) 8
2.2.1. 基本概念 8
2.2.2. 動態產生結構化測試資料 12
2.3. 演化式測試(Evolutionary Testing) 13
2.3.1. 基本概念 13
2.3.2. 基因演算法(Genetic Algorithm) 19
2.3.3. 基因演算法的缺點(The Weakness of Genetic Algorithm) 22
2.4. 粒子群優化演算法(Particle Swarm Optimization) 23
2.4.1. 粒子群優化演算法基本概念 23
2.4.2. 粒子群優化演算法粒子速度的更新策略 27
3. 研究方法與架構 29
3.1. 適合度公式(Fitness Function) 29
3.2. h-PSO方法整體架構 33
4. 實驗結果與討論 41
4.1. 標竿程式(Benchmark Programs) 41
4.2. 實驗結果(Experimental Results) 42
4.3. 結果討論(Result Discussion) 44
5. 結論與未來發展 56
6. 參考文獻 57
附錄 A:Source code of Trangle1 and the corresponding CFG 60
附錄B:Source code of Trangle3 and the corresponding CFG 63
附錄C:Source code of Trangle4 and the corresponding CFG 66
附錄D:Source code of Remainder and the corresponding CFG 69
附錄E:Source code of ComplexBranch and the corresponding CFG 71
參考文獻 References
1. Rees, K., et al., Managing the uncertainties of software testing: a Bayesian approach. Quality and Reliability Engineering International, 2001. 17(3): p. 191-203.
2. McMinn, P., Search-based software test data generation: a survey. 2004. p. 105-156.
3. Coward, P.D. and B. Polytech, Symbolic execution systems-a review. 1988. p. 229-239.
4. Korel, B., Dynamic Method of Software Test Data Generation. Software Testing, Verification & Reliability, 1992. 2(4): p. 203-213.
5. Miller, W. and D.L. Spooner, Automatic Generation of Floating-Point Test Data. TSE, 1976. 2(3): p. 223-226.
6. Korel, B., Automated software test data generation. 1990. p. 870-879.
7. Ferguson, R. and B. Korel, The chaining approach for software test data generation. ACM Transactions on Software Engineering and Methodology (TOSEM), 1996. 5(1): p. 63-86.
8. Wegener, J., A. Baresel, and H. Sthamer, Evolutionary test environment for automatic structural testing. 2001. p. 841-854.
9. Deb, K., Multi-objective Genetic Algorithms: Problem Difficulties and Construction of Test Problems. Evolutionary Computation, 1999. 7(3): p. 205-230.
10. Wang, H.C., A hybrid genetic algorithm for automatic test data generation. 2006.
11. Kennedy, J. and R. Eberhart, Particle swarm optimization. 1995.
12. Blum, C. and A. Roli, Metaheuristics in combinatorial optimization: Overview and conceptual comparison. 2003, ACM Press New York, NY, USA. p. 268-308.
13. Hassan, R., et al., A COMPARISON OF PARTICLE SWARM OPTIMIZATION AND THE GENETIC ALGORITHM. 46 th AIAA/ASME/ASCE/AHS/ASC Structures, Structural Dynamics, and Materials Conference, 2005: p. 1-13.
14. Sagarna, R. and J.A. Lozano, Scatter Search in software testing, comparison and collaboration with Estimation of Distribution Algorithms. 2006, Elsevier. p. 392-412.
15. Clarke, L.A., A System to Generate Test Data and Symbolically Execute Programs. TSE, 1976. 2(3): p. 215-222.
16. Beizer, B., Software system testing and quality assurance. 1984: Van Nostrand Reinhold Co. New York, NY, USA.
17. Beizer, B., Software testing techniques. 1990: Van Nostrand Reinhold Co. New York, NY, USA.
18. Myers, G.J., et al., The Art of Software Testing. 2004: John Wiley and Sons.
19. Sternberg, R.J. and E.L. Grigorenko, Dynamic Testing: The Nature and Measurement of Learning Potential. 2001: Cambridge University Press.
20. Alba, E. and J.F. Chicano, Software Testing with Evolutionary Strategies.
21. Mantere, T. and J.T. Alander, Evolutionary software engineering, a review. 2005. p. 315-331.
22. Tracey, N., et al., An automated framework for structural test-data generation. 1998. p. 285-288.
23. Holland, J.H., Adaptation in natural and artificial systems. 1992: MIT Press Cambridge, MA, USA.
24. Haupt, R.L., et al., Practical Genetic Algorithms. 2004: Wiley-Interscience.
25. Goldberg, D.E., Genetic Algorithm in Search, Optimization and Machine Learning. 1989, MA: Addison Wesley.
26. Whitley, D., A genetic algorithm tutorial. 1994, Springer. p. 65-85.
27. Sagarna, R. and J.A. Lozano, ON THE PERFORMANCE OF ESTIMATION OF DISTRIBUTION ALGORITHMS APPLIED TO SOFTWARE TESTING. 2005, Taylor & Francis. p. 457-489.
28. Shi, Y. and R. Eberhart, A modified particle swarm optimizer. 1998. p. 69-73.
29. Eberhart, R.C. and Y. Shi, Particle swarm optimization: developments, applications and resources. 2001, Piscataway, NJ, USA: IEEE. p. 81-86.
30. Clerc, M., The swarm and the queen: towards a deterministic and adaptiveparticle swarm optimization. 1999.
31. Eberhart, R.C. and Y. Shi, Comparing inertia weights and constriction factors in particleswarm optimization. 2000.
32. Carlisle, A. and G. Dozier, An off-the-shelf PSO. 2001. p. 1–6.
33. McMinn, P., D. Binkley, and M. Harman, Testability transformation for efficient automated test data search in the presence of nesting. Proc. UK Software Testing Workshop (UKTest 2005): p. 165–182.
34. Tracey, N.J., A Search-based Automated Test-data Generation Framework for Safety-critical Software. 2000: University of York.
35. Pargas, R.P., M.J. Harrold, and R. Peck, Test-Data Generation Using Genetic Algorithms. 1999. p. 263-282.
36. McMinn, P. and M. Holcombe, Evolutionary testing of state-based programs. 2005, ACM Press New York, NY, USA. p. 1013-1020.
37. McMinn, P. and M. Holcombe, Evolutionary Testing Using an Extended Chaining Approach. Evolutionary Computation, 2006. 14(1): p. 41-64.
38. Shi, Y. and R.C. Eberhart, Parameter selection in particle swarm optimization. 1998. p. 611–616.
39. Shi, Y., et al., Empirical study of particle swarm optimization. 1999.
40. Jones, B.F., H.H. Sthamer, and D.E. Eyres, Automatic structural testing using genetic algorithms. 1996. p. 299-306.
41. Michael, C.C., G. McGraw, and M.A. Schatz, Generating software test data by evolution. 2001. p. 1085-1110.
電子全文 Fulltext
本電子全文僅授權使用者為學術研究之目的,進行個人非營利性質之檢索、閱讀、列印。請遵守中華民國著作權法之相關規定,切勿任意重製、散佈、改作、轉貼、播送,以免觸法。
論文使用權限 Thesis access permission:校內一年後公開,校外永不公開 campus withheld
開放時間 Available:
校內 Campus: 已公開 available
校外 Off-campus:永不公開 not available

您的 IP(校外) 位址是 44.210.235.247
論文開放下載的時間是 校外不公開

Your IP address is 44.210.235.247
This thesis will be available to you on Indicate off-campus access is not available.

紙本論文 Printed copies
紙本論文的公開資訊在102學年度以後相對較為完整。如果需要查詢101學年度以前的紙本論文公開資訊,請聯繫圖資處紙本論文服務櫃台。如有不便之處敬請見諒。
開放時間 available 已公開 available

QR Code