ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC BÁCH KHOA NGUYỄN THỊ NGỌC NGÂN NGUYỄN THỊ NGỌC NGÂN * Ư C Ư NG N C PHÁT TRI N PH N SỬ DỤNG THUẬT TOÁN TỐI ƯU D A TRÊN HÀNH VI SĂN ỒI CỦA B Y SĨI KHOA HỌC ÁY TÍNH UẬN VĂN THẠC SĨ KHOA HỌC CHUYÊN NGÀNH KHOA HỌC * KHĨA K32 Đà Nẵng - Năm 2018 ÁY TÍNH ĐẠI HỌC ĐÀ NẴNG TRƢỜNG ĐẠI HỌC BÁCH KHOA NGUYỄN THỊ NGỌC NGÂN Ƣ C Ƣ NG NỖ C PHÁT TRIỂN PH N MỀM SỬ DỤNG THUẬT TOÁN TỐI ƢU D A TRÊN HÀNH VI SĂN MỒI CỦA B Y SĨI Chun ngành: Khoa học máy tính Mã số: 60.48.01 LUẬN VĂN THẠC SĨ Ngƣời hƣớng dẫn khoa học: TS Lê Thị Mỹ Hạnh ĐÀ NẴNG - Năm 2018 i LỜI CAM ĐOAN Tôi cam đoan cơng trình nghiên cứu riêng tơi Các số liệu, kết nêu luận văn trung thực chưa công bố công trình khác Tác giả Nguyễn Thị Ngọc Ngân ii MỤC ỤC MỞ ĐẦU CHƢƠNG TỔNG QUAN VỀ Ƣ C LƢ NG NỖ L C PHÁT TRIỂN PHẦN MỀM THEO M H NH SHETA 1.1 Tổng quan ƣớc lƣợng nỗ lực phát triển phần mềm 1.1.1 Khái niệm 1.1.2 Bốn bƣớc ƣớc lƣợng dự án phần mềm .5 1.3 Mơ hình ƣớc lƣợng nỗ lực phát triển phần mềm 10 1.3.1 Mơ hình COCOMO .11 1.3.2 Mơ hình Sheta 12 CHƢƠNG THUẬT TOÁN TỐI ƢU D A TRÊN HÀNH VI SĂN MỒI CỦA BẦY SÓI 13 2.1 Giới thiệu 13 2.1.1 Bài toán tối ƣu tổng quát phân loại 13 2.1.2 Trí tuệ bầy đàn .15 2.2 Mô tả hành vi săn mồi bầy sói .15 2.3 Chi tiết thuật toán .16 2.3.1 Hệ thống phân cấp xã hội 16 2.3.2 Bao vây mồi 17 2.3.3 Săn bắt mồi 18 2.3.4 Tấn công mồi 19 2.3.5 Tìm kiếm mồi (thăm dị) .20 2.4 Cài đặt thuật toán 21 2.4.1 Biểu diễn mã giả 21 2.4.2 Lƣu đồ thuật toán .22 CHƢƠNG ỨNG DỤNG THUẬT TOÁN VÀO Ƣ C LƢ NG NỖ L C PHÁT TRIỂN PHẦN MỀM .24 3.1 Giới thiệu 24 3.1.1 iểu diễn c thể thuật to n GWO hàm th ch nghi cho to n dự đo n .25 3.1.2 Đo lƣờng chất lƣợng dự đo n 26 3.2 Kết thực nghiệm 27 3.2.1 Tập liệu thực nghiệm 27 3.2.2 Thiết lập thực nghiệm 28 iii 3.2.3 Đ nh gi kết 28 3.3 Đ nh gi hiệu ƣớc lƣợng mơ hình Sheta sử dụng thuật toán tối ƣu dựa hành vi săn mồi bầy sói .33 KẾT LUẬN 34 TÀI LIỆU THAM KHẢO 35 iv Ƣ C Ƣ NG NỖ C PHÁT TRIỂN PH N MỀM SỬ DỤNG THUẬT TOÁN TỐI ƢU D A TRÊN HÀNH VI SĂN MỒI CỦA B Y SÓI Học viên: Nguyễn Thị Ngọc Ngân Chuyên ngành: Khoa học máy tính Mã số: 60.48.01 Khóa: 31 Trƣờng Đại học Bách khoa - ĐHĐN Tóm tắt – Ƣớc lƣợng nỗ lực phát triển phần mềm vấn đề quan trọng hầu hết ngƣời ngành công nghiệp phát triển phần mềm Sự thành công hay thất bại dự án phụ thuộc lớn vào độ xác kết ƣớc lƣợng nỗ lực tiến độ thực Để nâng cao tính xác dự đo n, phƣơng ph p ƣớc lƣợng dựa mơ hình thuật tốn đƣợc sử dụng rộng rãi Tuy nhiên, vấn đề đ nh gi ch nh x c nỗ lực vấn đề đầy thách thức nhà nghiên cứu việc khó khăn hiệu chuẩn tham số Nghiên cứu nhằm mục đ ch đề xuất thuật toán tối ƣu dựa hành vi săn mồi bầy sói (GWO – Grey Wolf Optimizer) để tối ƣu hóa c c thông số công thức đƣợc đề xuất trƣớc dựa nỗ lực thực tế khứ Các kết phƣơng ph p tiếp cận vƣợt trội c c phƣơng ph p c c nghiên cứu khác tính xác kết ƣớc lƣợng Từ khóa - Ƣớc lƣợng nỗ lực phát triển phần mềm; tối ƣu ho bầy đàn; thuật to n hành vi săn mồi bầy sói; thuật tốn tối ƣu hóa; mơ hình ƣớc lƣợng OPTIMIZING PARAMETERS OF SOFTWARE EFFORT ESTIMATION USING GREY WOLF OPTIMIZER Abstract – Software effort estimation has been an important issue for almost everyone in software industry The success or failure of projects depends greatly on the accuracy of effort estimation and schedule results To enhance the accuracy of predictions, estimation approaches based on algorithmic models have been widely used However, the question of accurate estimation of effort has been a challenging issue with regards to researchers, and the most difficult is to calibrate the parameters This study aims to use a Grey Wolf Optimizer (GWO) to optimize the parameters of the previously proposed estimation formula based on past actual effort The results indicated that our proposal outperformed methods in other studies in terms of the accuracy of estimated results Key words - Software effort estimation; particle swarm optimization; Grey Wolf Optimizer algorithm; swarm optimization algorithm; estimation models v DANH MỤC CÁC TỪ VIẾT TẮT Ký hiệu Diễn giải LOC Line Of Code: Ứớc lƣợng kích cỡ phần mềm đƣợc phát triển theo số dịng lệnh EP Function Point: Ƣớc lƣợng kích cỡ phần mềm đƣợc phát triển theo chức năng, độ phức tạp COCOMO Constructive Cost Model: Mơ hình giá cấu thành ME Methodology: Phƣơng ph p luận để nâng cao chất lƣợng mơ hình COCOMO GWO Grey Wolf Optimizer: thuật to n hành vi săn mồi bầy sói MMRE Độ đo Mean Magnitude of Relative Error MdMRE Độ đo Median Magnitude of Relative Error PRED (N) Độ đo Prediction at level N vi DANH MỤC CÁC BẢNG BIỂU Số hiệu Tên bảng Trang bảng 3.1 Dữ liệu dự n phần mềm NASA 27 3.2 Phạm vi tham số mơ hình đề xuất 28 3.3 Gi trị nỗ lực ƣớc lƣợng gi trị MRE mô hình Sheta mơ hình GWO 29 3.4 Gi trị nỗ lực ƣớc lƣợng gi trị MRE mơ hình Sheta mơ hình GWO 31 3.5 Kết mơ hình dựa tiêu chí 33 vii DANH MỤC CÁC HÌNH VẼ Số hiệu hình vẽ Tên hình vẽ Trang 1.1 Đồ thị hội tụ ƣớc lƣợng 1.2 Tiến trình sở ƣớc lƣợng dự án 2.1 Hệ thống phân cấp sói xám 15 2.2 Hành vi săn bắt sói 17 2.3 Các vị tr vectơ 2D, 3D vị trí có sói 18 2.4 Vị tr đƣợc cập nhật GWO 19 2.5 Tấn cơng mồi tìm kiếm mồi 20 2.6 Lƣu đồ thuật toán 22 3.1 Sự hội tụ GWO sử dụng hàm kiểm tra ngẫu nhiên (F1) (F10) 25 3.2 So sánh nỗ lực thực tế với nỗ lực ƣớc lƣợng mơ hình Sheta mơ hình GWO 30 3.3 So sánh MRE mơ hình Sheta mơ hình GWO 30 3.4 So sánh nỗ lực thực tế với nỗ lực ƣớc lƣợng mơ hình Sheta mơ hình GWO 32 3.5 So sánh MRE mơ hình Sheta mơ hình GWO 32 MỞ Đ U Lý chọn đề tài Ƣớc lƣợng nỗ lực phát triển phần mềm hiệu hoạt động quan trọng ƣớc lƣợng dự án phần mềm, đồng thời th ch thức công nghệ phần mềm Ƣớc lƣợng nỗ lực đƣợc sử dụng nhƣ liệu đầu vào cho kế hoạch dự án, phân t ch đầu tƣ, nguồn ngân sách, quy trình định giá dự án nên trở nên quan trọng để có đƣợc ƣớc lƣợng xác Nhiều tổ chức phải chịu tác động tài lên cơng việc họ, bị lợi cạnh tranh, chậm trễ việc hƣởng lợi từ kế hoạch sáng kiến c c ƣớc lƣợng xấu Ở giai đoạn phát triển ban đầu, hạn chế c c mơ hình ƣớc lƣợng nỗ lực dự án phát triển phần mềm độ ch nh x c độ chắn chƣa cao Một số kỹ thuật ƣớc lƣợng sử dụng liệu thu thập từ dự n hoàn thành từ nhiều tổ chức khác với cơng thức tốn học để ƣớc lƣợng chi phí dự án đƣợc giới thiệu nhƣ COCOMO Barry Boehm, SLIM Putnam, mơ hình điểm chức Albrecht… Trong năm gần đây, c c mô hình thuật tốn xử lý khó khăn việc điều chỉnh tham số nhằm cải tiến độ xác ƣớc lƣợng nỗ lực phát triển phần mềm đƣợc phát triển rộng rãi Các mơ hình Sheta hay Uysal sử dụng thuật toán tối ƣu bầy đàn đ p ứng đƣợc tiến độ c c phƣơng ph p công nghệ phần mềm Áp dụng phƣơng ph p ƣớc lƣợng qu trình ph t triển phần mềm nhiệm vụ khó khăn mà cần phải lƣờng trƣớc k ch thƣớc độ phức tạp sản phẩm đƣợc xây dựng để x c định việc cần làm Phát triển phần mềm theo mơ hình Sheta sử dụng thuật to n trở nên phổ biến ngành công nghiệp thay c c phƣơng ph p tiếp cận thông thƣờng phát triển phần mềm Trí thơng minh bầy đàn quy luật đƣợc tích góp từ c c hành vi tƣơng t c độc lập c c c nhân môi trƣờng sống chúng Gần đây, c c nhà ph t triển phần mềm nghiên cứu trí tuệ bầy đàn để tối ƣu hóa c c toán ƣớc lƣợng nỗ lực phát triển phần mềm Đa số c c phƣơng ph p đƣợc lấy cảm hứng từ tƣợng sinh học hành vi xã hội chủ yếu động vật, côn trùng Trong đó, hành vi săn mồi bầy sói cho thấy đƣợc kỹ chiến lƣợc tuyệt vời chúng Ngồi phát triển thuật tốn tối ƣu bầy đàn nhƣ: đàn c , đàn ong nhân tạo, thuật to n đom đóm… thuật tốn bầy sói đƣợc đề xuất để nâng cao hiệu cho ƣớc lƣợng nỗ lực phát triển phần mềm Chính vậy, tơi định chọn đề tài: 30 Nỗ lực thực tế Nỗ lực ƣớc lƣợng mơ hình Sheta Nỗ lực ƣớc lƣợng mơ hình GWO 160 140 Ngƣời - tháng 120 100 80 60 40 20 10 11 12 13 14 15 16 17 18 Dự án Hình 3.2 So sánh nỗ lực thực tế với nỗ lực ƣớc lƣợng mô hình Sheta mơ hình GWO MRE Mơ hình Sheta MRE mơ hình GWO 120% 100% MRE 80% 60% 40% 20% 0% 10 11 12 13 14 15 16 Dự án Hình 3.3 So sánh MRE mơ hình Sheta mơ hình GWO 17 18 31 ảng 3.4 Gi trị nỗ lực ƣớc lƣợng gi trị MRE mơ hình Sheta mơ hình GWO Dự án Nỗ lực thực tế Nỗ lực ƣ c ƣợng mơ hình GWO Nỗ lực ƣ c ƣợng mơ hình Sheta 115.8 106.7778 124.8585 0.0779 0.0782 96 58.8171 74.8467 0.3873 0.2203 79 59.2901 75.4852 0.2495 0.0445 90.8 68.2453 85.4349 0.2484 0.0591 39.6 39.4686 50.5815 0.0033 0.2773 98.4 81.6941 99.0504 0.1698 0.0066 18.9 18.9399 24.148 0.0021 0.2777 10.3 15.0816 18.0105 0.4642 0.7486 28.5 28.7229 37.2724 0.0078 0.3078 10 6.8072 4.5849 0.0275 0.345 11 9.1485 8.9384 0.0165 0.0068 12 7.3 12.1325 13.5926 0.6620 0.862 13 5.2271 1.51 0.0454 0.698 14 8.4 8.8652 8.2544 0.0554 0.0173 15 98.7 93.2846 110.5249 0.0549 0.1198 16 15.6 15.0122 18.2559 0.0377 0.1703 17 23 18.4439 23.369 0.2283 0.0222 18 138.3 117.9142 135.4825 0.1474 0.0204 MRE mơ hình GWO MRE mơ hình Sheta2 32 Nỗ lực ước lượng mơ hình Sheta Nỗ lực thực tế Nỗ lực ước lượng mơ hình GWO 160 140 Ngƣời - tháng 120 100 80 60 40 20 10 11 12 13 14 15 16 17 18 Dự án Hình 3.4 So sánh nỗ lực thực tế với nỗ lực ƣớc lƣợng mô hình Sheta mơ hình GWO MRE Mơ hình Sheta MRE mơ hình GWO 250% 200% 150% 100% 50% 0% 10 11 12 13 14 15 16 17 18 Hình 3.5 So sánh MRE mơ hình Sheta mơ hình GWO Có thể thấy c c dự n sử dụng thuật to n GWO để tối ƣu hóa c c tham số tạo kết ƣớc t nh tốt so với c c dự n sử dụng mơ hình Sheta Điều đƣợc chứng minh thông qua c c gi trị MRE sử dụng mơ hình GWO thấp nhiều so với MRE sử dụng mơ hình Sheta nhƣ thể hình 3.4 33 3.3 Đánh giá hiệu ƣ c ƣợng mô hình Sheta sử dụng thuật tốn tối ƣu dựa hành vi săn mồi b y sói Để kiểm tra hiệu suất mơ hình sử dụng thuật toán GWO, tiêu chuẩn đ nh gi nhƣ MMRE, MdMRE, PRED (25) đƣợc sử dụng Bảng 3.5 cho thấy kết thu đƣợc mô hình ƣớc tính 18 dự án NASA Bảng 3.5 Kết mơ hình dựa tiêu chí Độ đo Mơ hình Sheta GWO Sheta GWO MMRE(%) MdMRE(%) 23.79 14.51 21.66 12.58 63.64 49.27 16.03 6.66 PRED(25) 61.11 77.78 38.89 83.33 Kết cho thấy mơ hình GWO cải thiện MMRE mơ hình Sheta lên 3%, đặc biệt mơ hình GWO nâng cao MMRE mơ hình Sheta lên 47% Sau áp dụng thuật to n GWO Điều có nghĩa hiệu hai mơ hình dự tốn phần mềm đƣợc cải thiện đ ng kể sau sử dụng thuật to n GWO để tối ƣu hóa thơng số Tƣơng tự tiêu chí MdMRE, giá trị MdMRE cho mơ hình với thơng số tối ƣu hóa cách sử dụng thuật tốn GWO thấp so với mơ hình ban đầu Đối với PRED (25), mơ hình GWO mang lại giá trị cao nhất, giá trị thấp thuộc mơ hình Sheta Tiêu chí PRED (25) mơ hình GWO sau áp dụng thuật tốn GWO tối ƣu hóa c c tham số cải thiện đƣợc 45% Cả hai mơ hình đƣợc cải tiến cho giá trị PRED (25) 75% Điều chứng minh mơ hình cải tiến cho hệ thống ƣớc lƣợng nỗ lực tốt Trong đó, c c gi trị PRED (25) hai mơ hình đề xuất Sheta dƣới 75% Những kết mơ hình Sheta khơng đƣợc thích hợp cho việc ƣớc tính nỗ lực Tóm lại, c c mơ hình cải tiến sử dụng thuật to n GWO để tối ƣu hóa c c tham số cho thấy độ ch nh x c dự đo n tốt tốt so với c c mơ hình ban đầu dƣới dạng c c tiêu ch đ nh gi Cũng thấy mơ hình GWO đƣa c c dự đo n ch nh x c 34 KẾT LUẬN Kết đạt đƣợc Qua đề tài ƣớc lƣợng đƣợc chi ph nỗ lực để ph t triển phần mềm gần ch nh x c Giảm thời việc ƣớc lƣợng, đảm bảo thời gian hoàn thành dự n kịp tiến độ, đảm bảo đƣợc chi ph qu trình ph t triển Đầy đủ c c chức mà kh ch hàng yêu cầu Đề xuất đƣợc giải ph p p dụng thuật to n tối ƣu dựa vào hành vi săn mồi bầy sói vào to n ƣớc lƣợng nỗ lực ph t triển phần mềm theo mơ hình Sheta Cài đặt chƣơng trình sở giải ph p đề xuất t ch hợp môi trƣờng Windows Hạn chế Giải ph p đƣa phụ thuộc nhiều vào tham số đầu vào, tham số đầu vào khơng xác dẫn đến kết xa mong muốn Bài toán tối ƣu hóa c c tham số dựa thuật tốn mơ sinh học cịn phụ thuộc vào yếu thực tế nhƣ địa hình, độ nhiễu nên việc phân tích, so sánh kết cịn hạn chế Hƣ ng phát triển Phải làm việc trực tiếp với dự án phần mềm, đúc kết đƣa c c tham số đầu vào xác, dựa thực tế để nắm bắt yếu tố ảnh hƣởng tới tốc độ dự án Áp dụng vào tất mơ hình phát triển phần mềm tƣơng lai Nghiên cứu thêm số thuật toán tối ƣu để cải thiện hiệu ƣớc lƣợng nỗ lực phát triển phần mềm áp dụng vào c c to n ƣớc lƣợng cụ thể 35 TÀI LIỆU THAM KHẢO [1] T T Khuat, M H Le, Optimizing Parameters of Software Effort Estimation Models using DABC algorithm, Journal of Engineering Science and Technology, (Accepted), 2016 [2] Seyedali Mirjalili, Seyed Mohammad Mirjalili, Andrew Lewis, Grey Wolf Optimizer, Advances in Engineering Software 69: 46–61, 2014 [3] Alaa F Sheta, Estimation of the COCOMO Model Parameters Using Genetic Algorithms for NASA Software Projects, Journal of Computer Science (2): 118-123, 2006 [4] McConnell S, Rapid Development, Taming Wild Software Schedules, Microsoft Press (1996), pp.163 – 204 [5] Briand, L.Wieczorek, I., Resource Modeling in Software Engineering, Encyclopedia of Software Engineering, Wiley, 2002 [6] Chen, Z.Menzies, T.Port, D.Boehm, B., Feature subset selection can improve software cost estimation accuracy, In: Proceedings of the 2005 workshop on Predictor models in software engineering, ACM, 2005, pp 1-6 [7] Attarzadeh, I.Ow, S.H., A Novel Algorithmic Cost Estimation Model Based on Soft Computing Technique, Journal of Computer Science, Vol 6, 2010, No 2, pp 117-125 [8] Putnam, L.H., A General Empirical Solution to the Macro Software Sizing and Estimating Problem, IEEE Transactions on Software Engineering, Vol SE-4, 1978, No 4, pp 345-361 [9] Albrecht, A.J.Gaffney, J.E., Software Function, Source Lines of Code, and Development Effort Prediction, A Software Science Validation IEEE Transactions on Software Engineering, Vol SE-9, 1983, No 6, pp 639-648 [10] Muro C, Escobedo R, Spector L, Coppinger R “Wolf-pack (Canis lupus) hunting strategies emerge from simple rules in computational simulations” Behav Process 88:192–7, 2011 [11] Pranjali Diwan, M.R Khan, Energy Efficient Communication for WSNs using Grey-Wolf Optimization Algorithm, 2016 [12] Venu Sangwan, Rajesh Kumar, A K Rathore, Estimation of battery parameters of the equivalent circuit model using Grey Wolf Optimization, 2016 [13] Akash Saxena, Shalini Shekhawat, Ambient Air Quality Classification by Grey Wolf Optimizer Based Support Vector Machine, 2016 36 [14] Esha Gupta, Akash Saxena, Grey wolf optimizer based regulator design for automatic generation control of interconnected power system, 2016 [15] Bailey, J.W., Basili, V.R A meta-model for software development resource expenditures Proceedings of the 5th international conference on Software engineering, pp 107-116, 1981 [16] Olatunji, S.Selamat, A., Type-2 Fuzzy Logic Based Prediction Model of Object Oriented Software Maintainability, In: Fujita, H., Selamat, A (eds.), Springer International Publishing, Intelligent Software Methodologies, Tools and Techniques, Vol 513, 2015, pp 329-342 [17] Valdes, F.Abran, A., Comparing the Estimation Performance of the EPCU Model with the Expert Judgment Estimation Approach Using Data from Industry, In: Lee, R., Ormandjieva, O., Abran, A., Constantinides, C (eds.) Springer Berlin Heidelberg, Software Engineering Research, Management and Applications, Vol 296, 2010, pp 227-240 [18] Conte, S.D.Dunsmore, H.E.Shen, V.Y., Software engineering metrics and models, Benjamin-Cummings Publishing Co., Inc., 1986 ... thuật toán tối ƣu hành vi săn mồi bầy sói - Thu thập, tổng hợp phân t ch kỹ thuật ƣớc lƣợng nỗ lực phát triển phần mềm theo mơ hình Sheta - Áp dụng thuật to n tối ƣu dựa hành vi săn mồi bầy sói. .. ƣớc lƣợng nỗ lực phát triển phần mềm Tiểu kết chƣơng Chƣơng 2: Thuật toán tối ƣu dựa hành vi săn mồi b y sói - Giới thiệu Mơ tả hành vi săn mồi bầy sói Chi tiết thuật tốn Cài đặt thuật toán Tiếu... dụng thuật toán tối ưu dựa hành vi săn mồi bầy sói? ?? Mục đích nghiên cứu - Nghiên cứu thuật to n tối ƣu hành vi săn mồi bầy sói - Nghiên cứu lý thuyết ƣớc lƣợng nỗ lực ph t triển phần mềm theo mơ