Các nghiên cứu áp dụng giải thuật di truyền vào ước lượng công thực hiện phần mềm

30 Chương 3: Các nghiên cứu áp dụng giải thuật di truyền vào ước lượng công thực hiện phần mềm 3.1. Tinh chỉnh các hệ số của mô hình COCOMO bằng giải thuật di truyền 3.1.1. Nghiên cứu trên tập dữ liệu của NASA [9] 3.1.1.1. Hướng tiếp cận Mô hình COCOMO nguyên thủy do Barry Boehm phát triển vào năm 1981 dựa trên tập dữ liệu 63 dự án phần mềm của Bộ Quốc phòng Mỹ. Mô hình này xoay quanh công thức 3.1 tính công thực hiện dự án. BSIZEAE ×= Công thức 3.1. Công thức tính công chủ ñạo của mô hình COCOMO 81 [4]. Trong ñó: - E: công thực hiện dự án phần mềm, ñơn vị người-tháng (person-month). - A, B: các hệ số ñiều chỉnh của công thức, phụ thuộc vào môi trường phát triển phần mềm ở mỗi công ty. - SIZE: kích thước phần mềm tính bằng ñơn vị dòng-mã-nguồn. ðể tăng ñộ chính xác của ước lượng, tác giả mô hình COCOMO khuyến cáo nên tinh chỉnh lại các hệ số A, B cho phù hợp với tính chất của từng công ty phần mềm [4]. Trong bài báo của mình, Alaa F. Sheta ñề xuất áp dụng giải thuật di truyền vào việc tinh chỉnh các hệ số A, B của mô hình COCOMO. Một quần thể các cá thể ñược khởi tạo ban ñầu. Mỗi cá thể là một chuỗi bit có kích thước cố ñịnh dùng ñể biểu 31 diễn cặp hệ số A, B ñược phát sinh ngẫu nhiên trong một miền giá trị nào ñó. Hàm thích nghi ñược chọn là Varrianced Account For – VAF. 100 )var( )var(Re 1 × − −= Effort ffortEstimatedEalEffort VAF Công thức 3.2. ðộ thích nghi trong phương pháp của Alaa F. Sheta [9]. Quần thể ñược cho tiến hóa qua các thế hệ theo giải thuật di truyền. Kết quả cuối cùng thu ñược là cá thể có ñộ thích nghi cao nhất. ðó chính là cặp hệ số A, B phù hợp nhất cần tinh chỉnh. 3.1.1.2. Kết quả thực nghiệm Tác giả Alaa F. Sheta tiến hành thực nghiệm hướng tiếp cận của mình trên tập dữ liệu của NASA bao gồm 18 dự án phần mềm. Tham số của giải thuật di truyền ñược cho bởi bảng 3.1. Bảng 3.1. Tham số giải thuật di truyền trong phương pháp của Alaa F. Sheta. STT Tham số Giá trị 1 Cách thức chọn lọc normGeomSelect 2 Loại lai ghép arithXover 3 Loại ñột biến nonUnifMutation 4 Kích thước quần thể 10 5 Số thế hệ tiến hóa 100 6 Miền giá trị hệ số A 0 – 10 7 Miền giá trị hệ số B 0.3 – 2 Kết quả thu ñược sau khi thực hiện giải thuật di truyền là công thức COCOMO với hệ số A = 4.9067, B = 0.7311. 7311.09067.4 SIZEE ×= 32 Áp dụng công thức thu ñược ñể ước lượng lại công thực hiện của 18 dự án phần mềm, kết quả thu ñược như bảng 3.2. Bảng 3.2. Công thực tế và công ước lượng bởi phương pháp của Alaa F. Sheta. STT Công thực tế Công ước lượng 1 115.8000 131.9154 2 96.0000 80.8827 3 79.0000 81.2663 4 90.8000 91.2677 5 39.6000 60.5603 6 98.4000 106.7196 7 18.9000 31.6447 8 10.3000 27.3785 9 28.5000 46.2352 10 7.0000 11.2212 11 9.0000 14.0108 12 7.3000 22.0305 13 5.0000 8.4406 14 8.4000 15.9157 15 98.7000 119.2850 16 15.6000 25.8372 17 23.9000 31.1008 18 138.3000 143.0788 ðồ thị biểu diễn công thực tế và công ước lượng như hình 3.1. 33 Hình 3.1. ðồ thị biểu diễn công thực tế và công ước lượng [9]. 3.1.1.3. Kết luận Kết thúc bài báo của mình, tác giả Alaa F. Sheta kết luận việc áp dụng giải thuật di truyền ñể tinh chỉnh các hệ số A, B của mô hình COCOMO cho ra kết quả tốt. Công thức tính công thu ñược có khả năng ước lượng với ñộ chính xác cao. Hướng tiếp cận này cần ñược kiểm chứng thêm trên các tập dữ liệu khác và cải tiến hơn nữa ñể ñưa ra kết quả tốt hơn. 3.1.2. Nghiên cứu trên tập dữ liệu của công ty phần mềm Việt Nam [1] 3.1.2.1. Hướng tiếp cận Trong luận văn thạc sỹ chuyên ngành Tin học “Nghiên cứu phương pháp ước lượng ñộ lớn, thời gian, và nhân lực cho một dự án phần mềm”, tác giả Trương Quang Bình Long ñề xuất một phương pháp cải tiến hướng tiếp cận của Alaa F. Sheta nêu ở phần trên. Phương pháp này sử dụng giải thuật di truyền ñể tinh chỉnh các hệ số A, B của mô hình COCOMO II. Không như mô hình COCOMO nguyên thủy, mô hình COCOMO II có nhiều tham số hơn và ñược chia làm nhiều phiên bản ñể phù hợp hơn với từng giai ñoạn trong quy trình phát triển phần mềm. 34 Một ñiểm cải tiến ñáng ghi nhận của tác giả là sử dụng phương pháp tinh truyền thống của mô hình COCOMO ñể thu ñược các hệ số A0, B0. Sau ñó, các hệ số A0, B0 này sẽ ñược dùng làm gợi ý cho quá trình thực hiện giải thuật di truyền ñể tìm ra các hệ số A, B sau cùng. 3.1.2.2. Kết quả thực nghiệm Phương pháp của tác giả Trương Quang Bình Long ñược tiến hành thực nghiệm trên tập dữ liệu bao gồm 63 dự án thực tế của một công ty phần mềm ở Việt Nam. Tham số của giải thuật di truyền ñược cho bởi bảng 3.3. Bảng 3.3. Tham số giải thuật di truyền trong phương pháp của Trương Quang Bình Long. STT Tham số Giá trị 1 Cách thức chọn lọc Bàn quay Roulette 2 Tỷ lệ lai ghép 0.85 3 Tỷ lệ ñột biến 0.01 4 Kích thước quần thể 100 5 Số thế hệ tiến hóa 100 6 Miền giá trị hệ số A Từ A0 – e ñến A0 + e 7 Miền giá trị hệ số B Từ B0 – e ñến B0 + e Kết quả thu ñược sau khi thực hiện giải thuật di truyền là công thức COCOMO II với hệ số A = 0.1852, B = 0.8109. ∏ = ××= 17 1 1852.0 i i K EMSizeE ∑ = ×+= 5 1 01.08109.0 j jSFK 35 Khả năng ước lượng của công thức tinh chỉnh bằng giải thuật di truyền ñược tác giả so sánh với công thức tinh chỉnh bằng phương pháp COCOMO truyền thống. Kết quả so sánh hai công thức bằng các ñộ ño MMRE và PRED(30%). 0 2 4 6 8 10 12 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Phiên thử nghiệm T ổ n g s ai s ố MRE COCOMO II MRE GA Hình 3.2. So sánh ñộ chính xác của hai mô hình COCOMO ñã tinh chỉnh [1]. 36 0% 10% 20% 30% 40% 50% 60% 70% 80% 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Phiên thử nghiệm K h ả n ăn g ư ớ c lư ợ n g PRED(30%) COCOMO II PRED(30%) GA Hình 3.3. So sánh ñộ ổn ñịnh của hai mô hình COCOMO ñã tinh chỉnh [1]. 3.1.2.3. Kết luận Như vậy, thông qua những thực nghiệm của mình, tác giả Trương Quang Bình Long ñã kiểm chứng ñược hướng tiếp cận giải thuật di truyền do Alaa F. Sheta ñề xuất là khả quan. Tác giả cũng cải tiến phương pháp ñể áp dụng trên mô hình COCOMO II và thu ñược kết quả rất tốt với tập dữ liệu thực tế từ một công ty phần mềm ở Việt Nam. 3.2. Tìm năng của lập trình di truyền trong ước lượng công thực hiện phần mềm 3.2.1. Nghiên cứu của Colin và Martin [10] 3.2.1.1. Hướng tiếp cận Trong những năm trở lại ñây, một nhánh của giải thuật di truyền là lập trình di truyền ñang ñược quan tâm nghiên cứu và ứng dụng vào lĩnh vực ước lượng công thực hiện phần mềm. Lập trình di truyền dựa trên nền tảng của giải thuật di truyền 37 nhưng các cá thể khác biệt. Các các thể ñược biểu diễn dưới dạng cây thay vì dạng chuỗi cố ñịnh. ðiều này làm gia tăng ñộ ña dạng của các cá thể trong quá trình tiến hóa, một tiêu chí rất quan trọng trong quá trình vận hành hiệu quả giải thuật di truyền. Trong bài báo của mình [10], Colin và Martin ñề xuất phương pháp dùng lập trình di truyền ñể phát sinh công thức tính công dựa trên một tập dữ liệu lịch sử ñược biết từ trước. Quần thể ban ñầu bao gồm các cá thể là các công thức tính công ñược phát sinh ngẫu nhiên. Thông qua giải thuật di truyền, quần thể ñược tiến hóa qua các thế hệ ñể cuối cùng thu ñược các cá thể thích nghi nhất chính là những công thức tính công phù hợp nhất. Hàm thích nghi ñược hai tác giả sử dụng tương tự như hàm thích nghi VAF của Alaa F. Sheta. ðể so sánh với các phương pháp khác, hai tác giả dùng ñộ ño MMRE và PRED. 100 1 × − = ∑ N i i ii Actual ActualEstimated N MMRE Công thức 3.3. ðộ ño MMRE ño ñộ chính xác của mô hình. Trong ñó: - MRRE: ñộ lệch trung bình của các ước lượng ñược thực hiện. - Estimatedi: giá trị ước lượng bởi mô hình trên bộ dữ liệu thứ i. - Actuali: giá trị thực trên bộ dữ liệu thứ i. N KMREP KPRED )( %)( ≤ = Công thức 3.4. ðộ ño PRED ño ñộ ổn ñịnh của mô hình. Trong ñó: - PRED(K%): tỷ lệ ước lượng với ngưỡng K%. - P(MRE<=K): số ước lượng thực hiện bởi mô hình có MRE không quá K%. - N: số bộ dữ liệu trong tập dữ liệu lịch sử. 38 3.2.1.2. Kết quả thực nghiệm Hai tác giả Colin và Martin ñã tiến hành thực nghiệm phương pháp ñề xuất trên tập dữ liệu Dersharnais nổi tiếng. Tập dữ liệu này bao gồm 81 dự án phần mềm do Hiệp hội Tin học Canada thu thập ñược vào cuối thập niên 1980. Các tham số của lập trình di truyền sử dụng trong thực nghiệm cho bởi bảng 3.4. Bảng 3.4. Tham số lập trình di truyền trong hướng tiếp cận của Colin và Martin. STT Tham số Giá trị 1 Kích thước quần thể 1000 2 Số thế hệ tiến hóa 500 3 ðộ sâu cá thể khởi tạo 5 4 Số nút tối ña của cá thể 64 5 Cách thức chọn lọc Tournament 6 Số lượng chọn lọc 5 Kết quả thu ñược sau khi thực hiện lập trình di truyền là công thức tính công. Công thức này ñược tác giả áp dụng lại trên tập dữ liệu lịch sử vào so sánh với phương pháp Mạng Neuron nhân tạo. Bảng 3.5. So sánh kết quả của Colin và Martin với Mạng Neuron nhân tạo [10]. Công thực hiện dự án dự ñoán Mạng Neuron nhân tạo Lập trình tiến hoá Tệ nhất TB Tốt nhất Tệ nhất TB Tốt nhất Correlation 0.588 0.635 0.650 0.612 0.752 0.824 AMSE 6.278 5.477 5.209 14.58 11.13 7.77 Pred(25) 10 10 10 2 4.2 5 Pred(25%) 56 56 56 11.2 23.5 28 MMRE 65.45 60.63 59.23 52.12 44.55 37.95 BMMRE 74 69 66 92.47 74.57 59.23 39 3.2.1.3. Kết luận Với kết quả thực nghiệm ñạt ñược, Colin và Martin kết luận lập trình di truyền có khả năng ñược sử dụng ñể tạo ra công thức tính công cho các mô hình ước lượng. So với Mạng Neuron nhân tạo, công thức phát sinh bởi lập trình di truyền có ñộ chính xác ước lượng MMRE tốt hơn, tuy nhiên ñộ ổn ñịnh ước lượng PRED(25%) còn thấp. Lập trình di truyền có thể trở thành một phương pháp song song dùng ñể kiểm tra chéo kết quả ước lượng của những phương pháp khác. Trong tương lai, cần có thêm nhiều thực nghiệm trên những tập dữ liệu lịch sử khác ñể kiểm chứng hướng tiếp cận này. 3.2.2. Nghiên cứu Y. Shan [11] 3.2.2.1. Hướng tiếp cận Cũng với hướng tiếp cận dùng lập trình di truyền ñể phát sinh công thức tính công cho mô hình ước lượng, Y. Shan và các ñồng sự [11] ñưa ra giải pháp thay thế công cụ lập trình di truyền thông thường bằng công cụ lập trình di truyền cải tiến GGGP (Grammar-Guided-Genetic-Programming). Giải pháp này cho phép người sử dụng can thiệp sâu vào quá trình phát sinh công thức, dạng của công thức phát sinh có thể ñược ñịnh trước. Bên cạnh những tham số ñiều khiển hoạt ñộng của giải thuật di truyền, dạng của công thức phát sinh ñược biểu diễn bằng một cây ngữ pháp BNF như trong hình 3.4. Hàm thích nghi ñược nhóm tác giả lựa chọn tương tự như hàm VAF. 40 Hình 3.4. Cây ngữ pháp BNF sử dụng trong hướng tiếp cận của Y. Shan [11]. 3.2.2.2. Kết quả thực nghiệm Sau khi ñề xuất giải pháp, nhóm tác giả ñã tiến hành thực nghiệm trên tập dữ liệu ISBSG nổi tiếng, bao gồm thông số của 423 dự án phần mềm ñược thu thập trên toàn thế giới. Thông số ñiều khiển lập trình di truyền cho bởi bảng 3.6. Bảng 3.6. Tham số lập trình di truyền trong hướng tiếp cận của Y. Shan. STT Tham số Giá trị 1 Kích thước quần thể 1000 2 Số thế hệ tiến hóa 200 3 ðộ sâu cá thể khởi tạo 9 4 Tỷ lệ lai ghép 0.9 5 Tỷ lệ ñột biến 0.1 6 Cách thức chọn lọc Tournament 7 Số lượng chọn lọc 3 Công thức tính công thu ñược sau khi thực hiện lập trình di truyền ñược nhóm tác giả dùng ñể so sánh với các công thức tính công thu ñược từ phương pháp hồi quy 41 tuyến tính (Linear Regression) và hồi quy logarithm (Logarithm Regression). Kết quả so sánh trên các ñộ ño MMRE, PRED và R2 cho bởi bảng 3.7. Bảng 3.7. So sánh hướng tiếp cận của Y. Shan với phân tích hồi quy [11]. 3.2.2.3. Kết luận Trong công trình của mình, nhóm của Y. Shan ñã khẳng ñịnh lại tính khả thi của hướng tiếp cận lập trình di truyền trong việc ước lượng công thực hiện phần mềm. Những kết quả ñạt ñược tuy chưa cho thấy sự vượt trội nhưng cũng giúp phát triển một phương pháp song song ñược dùng ñể kiểm tra chéo kết quả quả thu ñược từ những phương pháp truyền thống. Việc áp dụng GGGP cho phép ñịnh trước dạng công thức phát sinh còn có thể giúp ích cho việc nghiên cứu ảnh hưởng của từng thông số dự án vào quá trình tính công thực hiện của toàn dự án. ðây là hướng tiếp cận cần nhiều ñóng góp trong tương lai.