Title

考量多重目標最佳化之開放原始碼軟體釋放時機與管理

Translated Titles

Open Source Software Release Time and Management Considering Multi-objective Optimization

Authors

游鎮洋

Key Words

開放原始碼軟體 ; 多重釋放規畫 ; 軟體可靠度模型 ; 多重目標最佳化 ; 多重目標演化演算法 ; Open source software ; multi release planning ; software reliability growth model ; multi-objective optimization ; multi-objective evolutionary algorithm

PublicationName

清華大學資訊系統與應用研究所學位論文

Volume or Term/Year and Month of Publication

2013年

Academic Degree Category

碩士

Advisor

黃慶育

Content Language

英文

Chinese Abstract

對於開放原始碼軟體系統開發者來說,首要的工作便是掌握開發時程和資源分配,由於隨著程式規模的增加以及資源的限制性,這項工作困難度隨著重要性一起提高。開放原始碼軟體的特性使得開發者在進行評估以及維護程式時是更加困難的,在此提出的模型便是為了這種漸進式開發以及多重版本的軟體而設計的。在這種開發方式下的軟體,其開發方式可以分為不同的階段,用這種開發方式最能夠符合開發者在現實中的開發案例。在此用來檢驗我們提出模型的錯誤追蹤資料均是由數個最有名的開放原始碼軟體得來,最後的結果顯示出模型是否有反應錯誤回報的能力。 傳統的釋出最佳化問題是將測試資源對應到目標函式(可靠度或是成本),在限制式之下決定一個最佳解。這些方法將複數的選擇空間縮減成為單一目標的最佳化問題,雖然簡化了問題也降低了複雜度,但是不能確保得到的解同時將所有的目標最佳化。追求可靠度最大化以及成本最小化應該要同時考慮到,因此我們使用多重目標演化演算法來解決最佳化釋出問題。為了符合現實中的案例,我們將兩個最為重要的因素:測試成本和系統可靠度當作目標,測試時所耗費的資源當作第三個目標 。 基因演算法發展的歷史悠久,在解決多重目標方面有許多選擇,我們從眾多知名且實用的演算法中選用非優勢排序基因演算法-II當作主要的解決方法。然而,非優勢排序基因演算法-II並不能保證在所有情形下都可以得到最佳解。在此研究中我們提出這些特殊的情形以及我們改進的方式,進一步呈現完整的演算法和相關實驗。為了證明實驗的實用性符合現實需求,我們使用開放原始碼的錯誤資料來評估釋放時間,實驗的結果顯示出改善的方法比非優勢排序基因演算法-II還要好,我們也提供數值範例來說明他的實用性。

English Abstract

How to manage the schedule and allocate resources for the Open Source Software (OSS) product is an important process for software system developers. With both an increase in the size of the program and the limitation of resources, this process has become more important and difficult. The property of OSS makes it more difficult for developers to assess and maintain the product. Our model is designed for the development process that is an iterative process and multi-release. In such a condition, the software development is split into phases, which best describes the situation that developers meet in a real case. The bug tracking data would be collected from a few popular open source products and used for examining the model we propose. The result would show whether the model has the ability to describe the time pattern related to bug reporting or not. The Traditional Optimal Release Time Planning Problem is about deciding on an optimal solution with constraints on the amount of testing resources with respect to some objective functions (e.g., reliability, or cost). These methods reduce the multi-decision space into a single-objective optimization problem. Although these formulations simplify the problem and reduce the complexity involved, the solutions do not take care of every objective involved. To maximize reliability and to minimize cost should be done at the same time. As a result, we suggest solving the Optimal Release Time Planning Problem with the Multi-objectives Evolutionary Algorithms (MOEAs). To qualify conditions in a realistic situation, we consider the testing cost and system reliability, two of the most important dimensions generally considered, as two objectives. The testing resource consumed is adapted into the third objective. Since the genetic algorithm has been developed for years, there are many choices to solve MOEAs. We choose the Non-dominated Sorting Genetic Algorithm II (NSGA-II), one of the most famous and useful approaches, as our main method. However, NSGA-II does not guarantee the optimal solution under every condition. The special scenario and the way we improve it is set out in the paper. Also, an improved method is proposed and the experiments are mentioned. To prove that the proposed method is practical and conforms to a realistic case, open source data is used to assess the release time and shows that the proposed method is better than NSGA-II. The Numerical examples are provided to illustrate the practicality.

Topic Category 基礎與應用科學 > 資訊科學
電機資訊學院 > 資訊系統與應用研究所
Reference
  1. [1] I. Samoladas, I. Stamelos, L. Angelis, and A. Oikonomou, “Open Source Software Development Should Strive for Even Greater Code Maintainability,” Communications of the ACM, Vol. 47, No. 10, pp. 83-87, Oct. 2004.
    連結:
  2. [5] D. E. Goldberg, Genetic Algorithms in Search of Optimization and Machine Learning, Addison-Wesley, Oct. 1989
    連結:
  3. [6] H. Ohtera and S. Yamada, “Optimal Allocation and Control Problems for Software-Testing Resource,” IEEE Trans. on Reliability, Vol. 39, No. 2, pp. 171-176, Jun. 1990.
    連結:
  4. [7] B. Beizer, Software Testing Techniques, Boston, International Thomson Computer Press, 1990.
    連結:
  5. [8] A. L. Goel and K. Okumoto, “Time-dependent Error-detection Rate Model for Software Reliability and Other Performance Measures,” IEEE Trans. on Reliability, Vol. 28, No. 3, pp. 206-211, Aug. 1979.
    連結:
  6. [10] Y. P. Chang, “Estimation of Parameters for Nonhomogeneous Poisson Process: Software Reliability with Change-point Model,” Communications in Statistics-Simulation and Computation, Vol. 30, No. 3, pp. 623-635, 2001.
    連結:
  7. [11] K. Okumoto and A. L. Goel, “Optimum Release Time for Software Systems, Based on Reliability and Cost Criteria,” Journal of Systems and Software, Vol. 1, pp. 315-318, 1980.
    連結:
  8. [12] S. Yamada and S. Osaki, “Cost-reliability Optimal Release Policies for Software Systems,” IEEE Trans. on Reliability, Vol. 34, No. 5, pp. 422-424, Dec. 1985.
    連結:
  9. [14] Y. Nishio and T. Dohi, “Determination of The Optimal Software Release Time Based on Proportional Hazards Software Reliability Growth Models,” Journal of Quality in Maintenance Engineering, Vol. 9, No. 1, pp. 48-65, 2003.
    連結:
  10. [15] C. Y. Huang and M. R. Lyu, “Optimal Release Time for Software Systems Considering Cost, Testing-effort, and Test Efficiency,” IEEE Trans. on Reliability, Vol. 54, No. 4, pp. 583-591, Dec. 2005.
    連結:
  11. [16] P. J. Boland, and N. Ní Chuív, “Optimal Times for Software Release when Repair is Imperfect,” Statistics & Probability Letters, Vol. 77, No. 12, pp. 1176-1184, July. 2007.
    連結:
  12. [17] J. W. Ho, C. C. Fang, and Y. S. Huang, “The Determination of Optimal Software Release Times at Different Confidence Levels with Consideration of Learning Effects,” Software Testing, Verification and Reliability, Vol. 18, No. 4, pp. 221-249, Jun. 2008.
    連結:
  13. [18] K. C. Chiu, J. W. Ho, and Y. S. Huang, “Bayesian Updating of Optimal Release Time for Software Systems,” Software Quality Journal, Vol. 17, No. 1, pp. 99-120, Mar. 2009.
    連結:
  14. [19] X. Li, M. Xie, and S. H. Ng, “Sensitivity Analysis of Release Time of Software Reliability Models Incorporating Testing Effort with Multiple Change-points,” Applied Mathematical Modelling, Vol. 34, No. 11, pp. 3560-3570, Nov. 2010.
    連結:
  15. [20] Y. F. Li, M. Xie, and T. N. Goh, “Adaptive Ridge Regression System for Software Cost Estimating on Multi-collinear Datasets,” Journal of Systems and Software, Vol. 83, No. 11, pp. 2332-2343, Nov. 2010.
    連結:
  16. [21] X. Li, Y. F. Li, M. Xie, and S. H. Ng, “Reliability Analysis and Optimal Version-updating for Open Source Software,” Information and Software Technology, Vol. 53, No. 9, pp. 929-936, Sep. 2011.
    連結:
  17. [23] T. L. Graves, A. F. Karr, J. S. Marron, and H. Siy, “Predicting Fault Incidence Using Software Change History,” IEEE Trans. on Software Engineering, Vol. 26, No. 7, pp. 653-661, Jul. 2000.
    連結:
  18. [25] M. Zaki, A. El-Ramsisi, and R. Omran, “A Soft Computing Approach for Recognition of Occluded Shapes,” Journal of System and Software, Vol. 51, No. 1, pp. 73-83, Apr. 2000.
    連結:
  19. [26] O. Berman and N. Ashrafi, “Optimization Models for Reliability of Modular Software Systems,” IEEE Trans. on Software Engineering, Vol. 19, No. 11, pp. 1119-1123, Nov. 1993.
    連結:
  20. [27] C. A. C. Coello, “Evolutionary Multi-objective Optimization: An Historical View of The Field,” IEEE Computational Intelligence Magazine, No. 1, pp. 28-36, Feb. 2006.
    連結:
  21. [30] J. D. Knowles and D. W. Corne, “Approximating The Non-dominated Front Using The Pareto Archived Evolution Strategy,” Evolutionary Computation, Vol. 8, No. 2, pp. 149-172, 2000.
    連結:
  22. [31] N. Srinivas and K. Deb, “Multi-objective Optimization Using Non-dominated Sorting in Genetic Algorithms,” Evolutionary Computation, Vol. 2, No. 3, pp. 221-248, 1994.
    連結:
  23. [33] E. Zitzler and L. Thiele, “Multi-objective Evolutionary Algorithms: A Comparative Case Study and The Strength Pareto Approach,” IEEE Trans. on Evolutionary Computation, Vol. 3, No. 4, pp. 257-271, Nov. 1999.
    連結:
  24. [36] E. Zitzler and L. Thiele, “Comparison of Multi-objective Evolutionary Algorithms: Empirical Results,” Evolutionary Computation, Vol. 8, No. 2, pp. 173-195, 2000.
    連結:
  25. [37] R. C. Purshouse and P. J. Fleming, “On The Evolutionary Optimization of Many Conflicting Objectives,” IEEE Trans. on Evolutionary Computation, Vol. 11, No. 6, pp. 770-784, Dec. 2007.
    連結:
  26. [38] K. Deb, “Multi-objective Genetic Algorithms: Problem Difficulties and Construction of Test Functions,” Evolutionary Computation, Vol. 7, No. 3, pp. 205-230, 1999.
    連結:
  27. [39] Z. Wang, K. Tang, and X. Yao, “Multi-objective Approaches to Optimal Testing Resource Allocation in Modular Software Systems,” IEEE Trans. on Reliability, Vol. 59, No. 3, pp. 563-575, Sep. 2010.
    連結:
  28. [40] J.R. Schott, “Fault Tolerant Design Using Single and Multi-criteria Genetic Algorithm Optimization,” Master's thesis, Department of Aeronautics and Astronautics, Massachusetts Institute of Technology, Cambridge, Massachusetts, 1995.
    連結:
  29. [45] E. Zitzler and L. Thiele, “Multi-objective Evolutionary Algorithms: A Comparative Case Study and The Strength Pareto Approach,” IEEE Trans. on Evolutionary Computation, Vol. 3, No. 4, pp. 257-271, Nov. 1999.
    連結:
  30. [46] M. R. Lyu, Handbook of Software Reliability Engineering, IEEE computer society press, 1996.
    連結:
  31. [2] D. Bosio, B. Littlewood, L. Strigini, and M. J. Newby, “Advantages of Open Source Processes for Reliability: Clarifying the Issues,” Proceedings of the 25th-26th Open Source Software Development Workshop, pp. 30-46, Newcastle upon Tyne, U.K., Feb. 2002.
  32. [3] J. Feller, and B. Fitzgerald, Understanding Open Source Software Development, Addison Wesley, London, 2002.
  33. [4] K. Crowston, H. Annabi, and J. Howison, “Defining Open Source Software Project Success,” Proceedings of the 24th International Conference on Information Systems, pp. 327-340, Seattle, Washington, U.S.A., Dec. 2003.
  34. [9] The Mozilla Organization. Bugzilla Bug Tracking System, 1998-2013. http://www.bugzilla.org, Accessed on 16 May, 2013.
  35. [13] T. Dohi, Y. Nishio, and S. Osaki, “Optimal Software Release Scheduling Based on Artificial Neural Networks,” Annals of Software Engineering, Vol. 8, No. 1-4, pp. 167-185, Feb. 1999.
  36. [22] Q. P. Hu, R. Peng, M. Xie, S. H. Ng, and G. Levitin, “Software Reliability Modelling and Optimization for Multi-release Software Development Processes,” 2011 IEEE International Conference on Industrial Engineering and Engineering Management, pp. 1534-1538, Singapore, Singapore, Dec. 2011.
  37. [24] Y. Zhang, M. Harman, and S. A. Mansouri, “The Multi-objective Next Release Problem,” Proceedings of the 9th annual conference on Genetic and Evolutionary Computation, pp. 1129-1137, London, England U.K., 2007.
  38. [28] A. Konak, D. W. Coit, and A. E. Smit, “Multi-objective Optimization Using Genetic Algorithms: A Tutorial,” Reliability Engineering and System Safety, Vol. 91, No. 9, pp. 992-1007, Sep. 2006.
  39. [29] J. D. Schaffer, “Multiple Objective Optimization with Vector Evaluated Genetic Algorithms,” Proceedings of the First International Conference on Genetic Algorithms, pp. 93-100, Pittsburgh, PA, U.S.A., 1985.
  40. [32] J. Horn, N. Nafpliotis, and D. E. Goldberg, “A Niched Pareto Genetic Algorithm for Multi-objective Optimization,” Proceedings of the First IEEE Conference on Evolutionary Computation, Vol. 1, pp. 82-87, Orlando, Florida, U.S.A., 1994.
  41. [34] E. Zitzler, M. Laumanns, and L. Thiele, “SPEA2: Improving The Strength Pareto Evolutionary Algorithm for Multi-objective Optimization,” Evolutionary Methods for Design, Optimization and Control with Application to Industrial Problems, pp. 95-100, 2001.
  42. [35] K. Deb, A. Pratap, S. Agarwal, and T. A. M. T. Meyarivan, “A Fast and Elitist Multi-objective Genetic Algorithm: NSGA-II,” IEEE Trans. on Evolutionary Computation, Vol. 6, No. 2, pp. 182-197, 2002.
  43. [41] B. Luo, J. Zheng, J. Xie, and J. Wu, “Dynamic Crowding Distance? A New Diversity Maintenance Strategy for MOEAs,” 2008. ICNC'08. Fourth International Conference on Natural Computation, Vol. 1, pp. 580-585, Oct. 2008.
  44. [42] https://bugzilla.mozilla.org/, Accessed on 16 May, 2013.
  45. [43] https://issues.apache.org/bugzilla/, Accessed on 16 May, 2013.
  46. [44] https://bugs.eclipse.org/bugs/, Accessed on 16 May, 2013.
  47. [47] J. D. Musa, A. Iannino, and K. Okumoto, Software Reliability, Measurement, Prediction, and Application, PWS Publishing Co, 1987.