Luận văn Một số phương pháp xây dựng mô hình ước lượng công thực hiện phần mềm bằng lập trình di truyền

64 Chương 6: Phương pháp xây dựng mô hình ước lượng dựa trên công thức bằng Lập trình di truyền 6.1. Phương pháp ñề xuất 6.1.1. Kiến trúc Như ñã trình bày ở chương 4, mô hình ước lượng dựa trên công thức có những hạn chế làm giảm hiệu quả sử dụng của nó, ñó là: - Hạn chế về tính sẵn sàng. - Hạn chế về khả năng áp dụng thực tế. - Hạn chế về tính linh ñộng. Trong chương này, chúng tôi ñề xuất một phương pháp nhằm khắc phục những hạn chế của mô hình ước lượng dựa trên công thức, trong khi vẫn phát huy những ưu ñiểm của nó. Phương pháp ñề xuất cũng sẽ làm thay ñổi căn bản quy trình áp dụng mô hình ước lượng dựa trên công thức vào thực tế. Ở cách tiếp cận truyền thống, các mô hình ước lượng dựa trên công thức cần phải ñược tinh chỉnh lại cho phù hợp trước khi áp dụng vào từng ñội ngũ phát triển phần mềm cụ thể. Trong khi ñó, luận văn ñề xuất một phương pháp có cách tiếp cận là xây dựng hẳn một mô hình ước lượng mới cho từng ñội ngũ phát triển. Mô hình mới ñược xây dựng hoàn toàn tự ñộng dựa trên tập dữ liệu lịch sử của người dùng (người dùng ở ñây có thể là một cá nhân, một ñội ngũ phát triển phần mềm, hay một công ty phần mềm muốn triển khai mô hình ước lượng công thực hiện phần mềm vào môi trường làm việc của mình). Cách tiếp cận của luận văn có hai ñặc ñiểm cần ghi nhận: 65 - Mô hình mới ñược xây dựng có thể ñược áp dụng trực tiếp vào thực tế mà không cần thông qua tinh chỉnh. Có ñược ñiều này là do mô hình mới ñược xây dựng ngay trên chính tập dữ liệu lịch sử của người dùng. - Công thức của mô hình mới ñược phát sinh một cách tự ñộng và nhanh chóng, ngay khi cần, người dùng có thể mở rộng tập dữ liệu lịch sử (mở rộng thông số dự án lẫn số lượng số dự án) và phát sinh lại mô hình mới. Hình 6.1 trình bày kiến trúc của phương pháp ñược ñề xuất. Hình 6.1. Kiến trúc của phương pháp luận văn ñề xuất. Kiến trúc của phương pháp luận văn ñề xuất gồm ba phần: - ðầu vào: tập dữ liệu lịch sử và thông tin cấu hình, tùy biến công thức của mô hình cần xây dựng. - ðầu ra: mô hình ước lượng dựa trên công thức, với công thức của mô hình ñược tự ñộng phát sinh. - Phần lõi: bộ phát sinh công thức ñược xây dựng bằng lập trình di truyền. 66 6.1.1.1. Tập dữ liệu lịch sử ðầu vào ñầu tiên và quan trọng nhất của phương pháp là tập dữ liệu lịch sử của người dùng. ðây là tập hợp bộ dữ liệu về các dự án phần mềm ñã hoàn thành có dạng như bảng 6.1. Dự án phần mềm Công thật sự Thông số tính công 1 Thông số tính công 2 … 1 Real Effort 1 Cost Driver 11 Cost Driver 12 … 2 Real Effort 2 Cost Driver 21 Cost Driver 22 … … … … … … N Real Effort N Cost Driver N1 Cost Driver N2 … Bảng 6.1. Tập dữ liệu lịch sử của N dự án phần mềm. Mỗi dòng dữ liệu trong bảng chứa thông tin về một dự án phần mềm ñã hoàn thành trong quá khứ bao gồm: công thật sự thực hiện và các thông số liên quan ñến việc tính công. Không như ở quá trình tinh chỉnh của mô hình ước lượng dựa trên công thức truyền thống, tập dữ liệu lịch sử ở ñây không chịu sự ràng buộc mỗi cột thông số tính công phải tương ứng về mặt ý nghĩa với mỗi thông số của mô hình. Ngược lại, mô hình mới ñược xây dựng ở ñầu ra sẽ có bộ thông số lấy từ các cột của tập dữ liệu lịch sử ở ñầu vào. 6.1.1.2. Thông tin cấu hình, tùy biến Một ñầu vào khác của phương pháp là thông tin cấu hình, tùy biến. Những thông tin này cho phép can thiệp vào quá trình phát sinh công thức tính công cho mô hình mới. ðiều này nhằm mục ñích tăng tính tiện dụng và khả năng tùy biến cho phương pháp. 67 Bảng 6.2 liệt kê những thông tin cấu hình, tùy biến ñược dùng làm ñầu vào cho bộ phát sinh công thức. Bảng 6.2. Thông tin tùy biến của bộ phát sinh công thức. STT Cấu hình Ý nghĩa 1 Bộ thông số của mô hình Cho phép lựa chọn những thông số tính công nào ở tập dữ liệu lịch sử ñể làm thông số của mô hình ñược xây dựng. 2 Dạng công thức tính công Cho phép quy ñịnh dạng của công thưc tính công ñược phát sinh ở mô hình mới. 3 ðộ sâu công thức Công thức tính công ñược biểu diễn bằng cây biểu thức, cấu hình này cho phép quy ñịnh ñộ sâu của cây biểu thức. 4 Các phép toán trong công thức Cho phép lựa chọn những phép toán sử dụng trong công thức tính công, chỉ những phép toán này mới có khả năng xuất hiện trong công thức. 5 Nhóm thông số lập trình di truyền Những thông số vận hành lập trình di truyền ñể phát sinh công thức như: kích thước quần thể, số thế hệ tiến hóa, tỷ lệ lai ghép, ñột biến, … 6.1.1.3. Mô hình ước lượng ñược xây dựng ðầu ra của phương pháp là một mô hình ước lượng dựa trên công thức. Mô hình này gồm hai thành phần: - Công thức tính công ñược phát sinh từ tập dữ liệu lịch sử. - Bộ thông số của mô hình lấy từ các thông số tính công của tập dữ liệu lịch sử. 68 Như ñã nhận ñịnh ở chương 4, tập dữ liệu lịch sử có tính chất “cục bộ”, gắn liền với một ñội ngũ phát triển phần mềm. Vì vậy, ở ñầu vào, tập dữ liệu lịch sử của ñội ngũ phát triển nào ñược sử dụng, thì ở ñầu ra, mô hình ước lượng ñược xây dựng cũng sẽ gắn liền với ñội ngũ phát triển ñó. Có thể nói mô hình ước lượng này là ñặc trưng riêng của ñội ngũ phát triển, nên có thể ñược sử dụng trực tiếp mà không cần tinh chỉnh như ở mô hình ước lượng dựa truyền thống. 6.1.1.4. Bộ phát sinh công thức Phần cốt lõi của phương pháp là bộ phát sinh công thức. Nó có nhiệm vụ phát sinh ra công thức tính công cho mô hình ước lượng cần xây dựng. Công thức này ñược rút trích từ tập dữ liệu lịch sử và có thể tùy biến nhờ vào thông tin cấu hình tùy biến ở ñầu vào. ðể có thể phát sinh công thức theo một tập dữ liệu cho trước, một phương pháp toán học ñược sử dụng, ñó là phương pháp phân tích hồi quy. Như ñã trình bày ở chương 5, công cụ phân tích hồi quy tự ñộng có kết quả tốt hiện nay là lập trình di truyền. Bên cạnh ñó, lập trình di truyền còn cho phép người sử dụng cấu hình, tùy biến những tham số của nó ñể cho ra kết quả phù hợp. Vì những ñiều này, lập trình di truyền ñã ñược lựa chọn ñể xây dựng bộ phát sinh công thức. Nền tảng của bộ phát sinh công thức là là bộ thư viện lập trình di truyền EsLib. Bộ thư viên này sẽ ñược mô tả chi tiết ở những phần sau. 6.1.2. Quy trình cải tiến áp dụng mô hình ước lượng vào thực tế Trong thực tế, khi áp dụng mô hình ước lượng dựa trên công thức vào một công ty hay một ñội ngũ phát triển phần mềm, ñể ñạt ñược hiệu quả cao nhất, một quy trình áp dụng mô hình gồm ba bước ñược tiến hành như mô tả trong hình 6.2. Quy trình này ñòi hỏi người dùng mô hình phải tinh chỉnh lại mô hình theo tập dữ liệu lịch sử trước khi sử dụng. ðây chính là ñiều tạo nên hạn chế về tính sẵn sàng của mô hình ước lượng dựa trên công thức. 69 Hình 6.2. Quy trình áp dụng mô hình ước lượng dựa trên công thức vào thực tế. Với phương pháp luận văn ñề xuất, những hạn chế của mô hình truyền thống ñược khắc phục, khi ñó nảy sinh hai dạng cải tiến của quy trình áp dụng mô hình vào thực tế. Dạng cải tiến thứ nhất ñược mô tả trong hình 6.3. Hình 6.3. Quy trình cải tiến dạng một của phương pháp ñề xuất. Ý tưởng ở dạng cải tiến thứ nhất rất ñơn giản, bước “Lựa chọn mô hình” và “Tinh chỉnh mô hình” ở quy trình truyền thống ñược thay thế bằng bước “Xây dựng mô hình” ở quy trình cải tiến. ðiều này tạo nên sự khác biệt lớn: mỗi ñội ngũ phát triển phần mềm ñược xây dựng riêng một mô hình ước lượng phù hợp với tập dữ liệu lịch sử của họ, mô hình này có thể ñược áp dụng trực tiếp mà không cần tinh chỉnh, và việc xây dựng mô hình ñược thực hiện nhanh chóng và hoàn toàn tự ñộng. Dạng cải tiến thứ hai ñược mô tả trong hình 6.4. 70 Hình 6.4. Quy trình cải tiến dạng hai của phương pháp ñề xuất.. Không như dạng cải tiến thứ nhất, ở dạng thứ hai, quy trình áp dụng mô hình gồm ba bước giống với quy trình khi chưa cải tiến. ðiểm khác biệt nằm ở bước “Tinh chỉnh mô hình”. Ở dạng cải tiến thứ hai, bước “Tinh chỉnh mô hình” ñược thay thế bằng bước “Tinh chỉnh cải tiến”. ðiều này có nghĩa là: việc ñiều chỉnh công thức tính công của mô hình sẽ không ñược thực hiện theo cách thức truyền thống gắn liền với mô hình, thay vào ñó, bộ phát sinh công thức của phương pháp ñề xuất sẽ ñược sử dụng. Công thức cũ của mô hình sẽ là một thành phần của thông tin cấu hình, tùy biến làm ñầu vào cho bộ phát sinh công thức. Nhờ ñó, công thức tính công ñược phát sinh sẽ giữ nguyện ñược dạng của công thức cũ. 6.2. Bộ thư viện EsLib 6.2.1. Giới thiệu EsLib Như ñã trình bày trong phần phương pháp ở trên, phần cốt lõi của phương pháp ñề xuất nằm ở bộ phát sinh công thức, có nhiệm vụ phát sinh công thức tính công dựa trên tập dữ liệu lịch sử cho mô hình ước lượng cần xây dựng. Và ñể thực hiện ñược ñiều này, bộ phát sinh công thức sử dụng công cụ lập trình di truyền. Phần tiếp theo này ñi sâu vào trình bày việc hiện thực hóa bộ phát sinh công thức thông qua việc xây dựng bộ thư viện hỗ trợ lập trình di truyền EsLib. ðây là ñược xem là nền tảng của bộ phát sinh công thức. Bộ thư viên EsLib hỗ trợ ñầy ñủ những chức năng cần thiết ñể bộ phát sinh công thức hoạt ñộng ñược. Hai chức năng chính của EsLib là: sử dụng lập trình di truyền phát sinh công thức từ tập dữ liệu lịch sử và xây dựng mô hình ước lượng với công 71 thức tính công ñã ñược phát sinh. Ngoài ra, EsLib còn cho phép ñánh giá khả năng ước lượng của mô hình ñược xây dựng thông qua những ñộ ño. Bảng 6.3. Những chức năng chính của bộ thư viện EsLib. STT Chức năng Mô tả 1 Biểu diễn cây biểu thức và thực hiện những thao tác trên cây ðược dùng ñể biểu diễn các cá thể trong lập trình di truyền, mỗi cá thể là một công thức tính công tiến hóa qua từng thế hệ với các phép toán chọn lọc, lai ghép, ñột biến có thể xảy ra trên cá thể. 2 Vận hành giải thuật di truyền trên một quần thể các cá thể Lập trình di truyền sử dụng giải thuật di truyền ñể thực hiện quá trình tiến hóa quần thể qua các thế hệ, các cá thể trong quần thể ở thế hệ sau có ñộ thích nghi cao hơn so với các thế hệ trước ñó. 3 Tùy biến các thông số lập trình di truyền Cho phép tùy biến các thông số về kích thước quần thể, số thế hệ tiến hóa, cách thức thực hiện chọn lọc, lai ghép, ñột biến, … Chức năng này làm tăng khả năng mở rộng và tái sử dụng của bộ thư viện. 4 Biểu diễn tập dữ liệu lịch sử và các thao tác trên tập dữ liệu Biểu diễn tập dữ liệu lịch sử dùng ñể phát sinh công thức tính công, cho phép ñọc và duyệt các bộ thông số trong tập dữ liệu. 5 Tạo mô hình ước lượng dựa trên công thức Thực hiện việc xây dựng mô hình ước lượng từ công thức tính công và bộ thông số mô hình rút trích từ tập dữ liệu lịch sử. 6 Mô phỏng các ñộ ño khả năng ước lượng của mô hình ðo khả năng ước lượng của mô hình thông qua các ñộ ño MMRE, PRED, R2, … Cho phép lựa chọn và mở rộng ñộ ño sau này. 72 6.2.2. Giải pháp cài ñặt EsLib Phần chính yếu của bộ thư viện EsLib là công cụ lập trình di truyền, cho phép phát sinh công thức tính công của mô hình ước lượng. Ban ñầu, khi bắt tay vào xây dựng bộ thư viện, hai giải pháp sau ñã ñược xem xét: - Giải pháp 1: sử dụng công cụ lập trình di truyền hiện có trên thị trường. Giải pháp này nhanh gọn và ñơn giản, chỉ cần tốn công lựa chọn những công cụ phù hợp hiện có, tìm hiểu cấu trúc và cách hoạt ñộng của nó, rồi tiến hành việc tích hợp vào bộ thư viện EsLib. - Giải pháp 2: xây dựng từ ñầu công cụ lập trình di truyền cho bộ thư viện EsLib. Giải pháp này tốn nhiều thời gian và công sức ñể xây dựng nền tảng giải thuật di truyền, cách biểu diễn cá thể dạng cây, thực hiện những phép toán di truyền, … Nhưng bù lại, với việc xây dựng từ ñầu, công cụ lập trình di truyền thu ñược sẽ hoàn toàn phù hợp với những yêu cầu của bộ thư viện EsLib. Với giải pháp 1 sử dụng công cụ lập trình di truyền hiện có, những công cụ ñược lựa chọn cần thỏa một số ñặc ñiểm sau ñây: - Miễn phí và có mã nguồn mở ñể thuận tiện cho việc chỉnh sửa, mở rộng các chức năng. - Có kiến trúc hướng ñối tượng, tái sử dụng và mở rộng các lớp dễ dàng. - Hỗ trợ biểu diễn cá thể dưới dạng cây biểu thức. - Cho phép ñiều chỉnh hàm thích nghi theo nhu cầu. - Cho phép lựa chọn và mở rộng các phép toán di truyền: chọn lọc, lai ghép, ñột biến. - Cho phép can thiệp sâu vào quá trình tiến hóa ở từng thế hệ. Sau khi thực hiện khảo sát (trong khoảng thời gian cho phép của luận văn), không có công cụ lập trình di truyền nào hiện có trên thị trường thỏa ñược tất cả các ñặc ñiểm cần thiết như ñề ra ở trên. Những công cụ hỗ trợ ñầy ñủ tính năng thì lại là sản 73 phẩm kinh doanh, không miễn phí và không mã nguồn mở. Còn những công cụ mã nguồn mở thì một số không ñủ mạnh ñể có thể tùy biến, can thiệp sâu vào quá trình hoạt ñộng của giải thuật di truyền, số khác có kiến trúc không tốt, khó tái sử dụng và mở rộng ñể thực hiện việc tích hợp vào bộ thư viện EsLib. Chính vì lý do này mà giải pháp 2 xây dựng từ ñầu công cụ lập trình di truyền cho bộ thư viện EsLib ñã ñược lựa chọn. Môi trường phát triển của bộ thư viện EsLib ñược lựa chọn là: - Nền tảng phát triển: .NET Framework 3.0. - Ngôn ngữ lập trình: ngôn ngữ C#. 6.2.3. Kiến trúc EsLib Hình 6.5 mô tả kiến trúc bộ thư viện EsLib Hình 6.5. Kiến trúc bộ thư viện EsLib. Bảng 6.4 giải thích ý nghĩa các gói (package) trong EsLib. Chi tiết về từng gói của bộ thư viện EsLib ñược trình bày trong phần kế tiếp. 74 Bảng 6.4. Chức năng các gói trong bộ thư viện EsLib. STT Tên gói Ý nghĩa 1 exp Bao gồm những thành phần dùng ñể biểu diễn cây biểu thức (các hằng số, biến số, các toán tử, …). Những thao tác trên cây như duyệt cây, tìm kiếm phần tử, thêm bớt nhánh, … và ñặc biệt là tạo lập cây cũng ñược hỗ trợ trong gói này. 2 ga Bao gồm những thành phần chính yếu của một công cụ lập trình di truyền, cho phép khởi tạo quần thể, xác ñịnh hàm thích nghi, vận hành giải thuật di truyền, thực hiện các phép toán chọn lọc, lai ghép, ñột biến qua từng thế hệ. Tất cả ñều ñược xây dựng trên nền tảng mở, cho phép dễ dàng tùy biến, tái sử dụng và mở rộng khi cần. 3 Es chứa những thành phần liên quan ñến việc xây dựng mô hình ước lượng, biểu diễn tập dữ liệu lịch sử. Những ñộ ño khả năng ước lượng của mô hình cũng ñược cài ñặt trong gói này. 6.2.4. Gói exp 6.2.4.1. Kiến trúc gói exp Gói exp ñảm trách những vấn ñề liên quan ñến cây biểu thức, một thành phần dùng ñể biểu diễn cá thể trong lập trình di truyền. Những gói con của gói exp: - tree - tree.init - terminal - operator - init Kiến trúc gói exp ñược mô tả thông qua sơ ñồ lớp ở hình 6.6. 75 H ìn h 6. 6. S ơ ñồ lớ p ki ến tr úc g ói e xp c ủa b ộ th ư vi ện E sL ib . 76 6.2.4.2. Các chức năng chính của gói exp 6.2.4.2.1. Biểu diễn cây biểu thức Như ñã trình bày ở phần trên, biểu diễn cây biểu thức là chức năng chính của gói exp. Cây biểu thức có tính chất phân cấp nên ở ñây, mẫu Composite (một trong 23 mẫu thiết kế của Gang of Four) ñược sử dụng. Các lớp ñối tượng chính yếu và ý nghĩa của chúng trong việc biểu diễn cây biểu thức ñược mô tả ở bảng 6.5. Bảng 6.5. Chức năng các lớp dùng biểu diễn cây biểu thức trong gói exp. STT Tên lớp Ý nghĩa 1 expExpression ðại diện cho biểu thức tổng quát, chứa những thành phần chung nhất của biểu thức như: tính giá trị, rút gọn biểu thức, kết buộc giá trị cho tham số biểu thức, ... Lớp expExpression là lớp cơ sở, ñóng vai trò Component trong mẫu Composite. Mỗi loại biểu thức cụ thể sẽ kế thừa từ lớp này và hiện thực hóa những thành phần chung theo cách riêng. 2 expTerminal ðại diện cho các biểu thức ñơn không chứa biểu thức con là hằng số và biến số trong biểu thức. Lớp expTerminal kế thừa expExpression, ñóng vai trò lá trong mẫu Composite, có lớp kết thừa là expNumber và expSymbol ñại diện từng biểu thức ñơn cụ thể. 3 expOperator ðại diện cho các biểu thức phức hợp như các phép toán và hàm số học. ðặc ñiểm của expOperator là có thể chứa các biểu thức con bên trong nó. Mỗi biểu thức con là một biểu thức tổng quát, có thể là ñơn hay phức hợp. expOperator kế thừa expExpression, ñóng vai trò phức hợp trong mẫu Composite. Mỗi phép toán cụ thể kế thừa expOperator ñể cài ñặt cách thức tính toán riêng. 77 6.2.4.2.2. Khởi tạo cây biểu thức Một chức năng khác không kém phần quan trọng của gói exp là khởi tạo cây biểu thức. Bảng 6.6. Chức năng các lớp dùng khởi tạo cây biểu thức trong gói exp. STT Tên lớp Ý nghĩa 1 expTreeNodeInitScheme Lớp cơ sở, ñại diện cho cách thức khởi tạo cây tổng quát, chứa những thành phần chung nhất trong việc khởi tạo cây như: lựa chọn nút lá hay nút phức hợp, tạo nút, … Mỗi cách thức khởi tạo cụ thể sẽ kế thừa từ lớp expTreeNodeInitScheme và hiện thực hóa cách thức thức khởi tạo riêng. 2 expTreeNodeInitFullScheme ðại diện cho cách thức khởi tạo cá thể dạng Full trong lập trình di truyền (xem thêm chương 5), kế thừa expTreeNodeInitScheme. 3 expTreeNodeInitGrowScheme ðại diện cho cách thức khởi tạo cá thể dạng Grow trong lập trình di truyền (xem thêm chương 5), kế thừa expTreeNodeInitScheme. 4 expTreeNodeSet ðại diện cho tập các loại nút có thể ñược lựa chọn trong quá trình khởi tạo cây. Mỗi bước trong quá trình khởi tạo cây, một loại nút sẽ ñược lựa chọn ñể thêm vào các nhánh cây. expTreeNodeSet quản lý tập những loại nút này. Nó ñược thiết lập trước khi khởi tạo, cho phép tùy biến cây ñược khởi tạo. 78 Việc khởi tạo ñược thực hiện bằng hai cách: - Cách 1: khởi tạo cây biểu thức từ chuỗi biểu thức cho trước. ðây là cách khởi tạo thông thường và quen thuộc với người sử dụng gói exp ñể làm việc với biểu thức. Lớp expExpression cung cấp phương thức tĩnh expExpression.parse(string) ñể thực hiện việc khởi tạo này. - Cách 2: khởi tạo cây biểu thức ngẫu nhiên và tự ñộng. Cách khởi tạo này ñược dùng trong quá trình khởi tạo quần thể khi vận hành giải thuật di truyền. Khởi tạo theo cách này ñòi hỏi cho phép lựa chọn nhiều dạng khởi tạo khác nhau. Gói exp cung cấp những lớp ñối tượng dùng cho cách khởi tạo này như mô tả ở bảng 6.6. 6.2.5. Gói ga 6.2.5.1. Kiến trúc gói ga Gói ga ñảm trách những vấn ñề liên quan giải thuật di truyền và lập trình di truyền. Những gói con của gói ga: - ga.selcheme - ga.gp Kiến trúc gói ga ñược mô tả thông qua sơ ñồ lớp ở hình 6.7. 79 H ìn h 6. 7. S ơ ñồ lớ p ki ến tr úc g ói g a củ a bộ th ư vi ện E sL ib . 80 6.2.5.2. Các chức năng chính của gói ga 6.2.5.2.1. Khởi tạo cá thể ðể vận hành giải thuật di truyền, trước hết phải tạo các cá thể trong quần thể. Việc tạo cá thể ñược thực hiện thông qua những lớp ñối tượng mô tả ở bảng 6.7. Bảng 6.7. Chức năng các lớp dùng khởi tạo cá thể trong gói ga. STT Tên lớp Ý nghĩa 1 gaIndividual ðại diện cho cá thể tổng quát trong quẩn thể của giải thuật di truyền, là lớp cơ sở, chứa những ñặc tính chung nhất mà một cá thể phải có. Những loại cá thể cụ thể kế thừa từ lớp này ñể hiện thực hóa những ñặc tính này theo cách riêng. 2 gaExpIndividual ðại diện cho cá thể cây biểu thức ñược dùng trong lập trình di truyền. Lớp gaExpIndividual kế thừa từ gaIndividual và chứa dữ liệu là cây biểu thức ñược cài ñặt ở gói exp. 3 gaIndividualParameters Chứa những thông số cần thiết cho quá trình khởi tạo cá thể cây biểu thức (ñối tượng gaExpIndividual). Những thông số này bao gồm: - Cây biểu thức cơ sở: cá thể dù biến ñổi thế nào trong quá trình tiến hóa vẫn giữ nguyên dạng cơ sở. - Hàm thích nghi: hàm quy ñịnh cách thích nghi của cá thể dùng trong quá trình tiến hóa. - Dạng khởi tạo: khởi tạo cá thể Full hay Grow. - ðộ sâu khởi tạo: ñộ sâu tối ña cá thể khi khởi tạo. - ðộ sâu tối ña: ñộ sâu tối ña cá thể khi tiến hóa. 81 6.2.5.2.2. Khởi tạo quần thể Quần thể trong giải thuật di truyền ñược khởi tạo từ một cá thể ban ñầu làm “hạt giống”. Các cá thể còn lại ñược tạo ra bằng sao chép từ “hạt giống” này. Những lớp ñối tượng liên quan ñến quần thể ñược mô tả ở bảng 6.8. Bảng 6.8. Chức năng các lớp dùng khởi tạo quần thể trong gói ga. STT Tên lớp Ý nghĩa 1 gaPopulation ðại diện cho quẩn thể của giải thuật di truyền, chứa ñầy ñủ những thành phần cần thiết của một quần thể các cá thể có khả năng tiến hóa qua các thế hệ. 2 gaPopulationParameters Chứa những thông số cần thiết cho quá trình khởi tạo quần thể. Những thông số này bao gồm: - Kích thước quần thể: số lượng các cá thể trong quần thể. - Cá thể “virus”: ngoài cá thể “hạt giống” ñược dùng ñể khởi tạo quần thể ban ñầu, một cá thể khác là “virus” có thể ñược tiêm vào quần thể ñể tăng ñộ ña dạng cũng như ñịnh hướng cho quần thể trong quá trình tiến hóa. - Tỷ lệ tiêm: tỷ lệ cá thể “virus” vào quần thể. 6.2.5.2.3. Khởi tạo và vận hành giải thuật di truyền Thuật giải di truyền mô tả cách thức tiến hành quá trình tiến hóa trên các cá thể trong một quần thể. Các cá thể ñược chọn lọc, lai ghép và ñột biến theo cách thức nào ñó ñể dần dần thích nghi với mức ñộ do một hàm thích nghi quy ñịnh. Ở ñây, hai mẫu Template Method và Stratergy (trong 23 mẫu thiết kế của Gang of Four) ñược sử dụng ñể cài ñặt các lớp liên quan. 82 Bảng 6.9. Chức năng các lớp dùng vận hành giải thuật di truyền trong gói ga. STT Tên lớp Ý nghĩa 1 gaAlgorithm ðại diện cho giải thuật di truyền tổng quát, chứa những thành phần chung nhất khi vận hành giải thuật di truyền như: chọn lọc, lai ghép, ñột biến, tạo quần thể thế hệ kế tiếp, … Là lớp cớ sở, chứa phương thức template trong mẫu Template Method. Cách thức vận hành giải thuật di truyền theo một trình tự khung cố ñịnh. Những giải thuật cụ thể kế thừa từ lớp này ñể hiện thực hóa một cách cụ thể các bước trong giải thuật. 2 gaAlgorithmParameters Chứa những thông số cần thiết cho quá trình khởi tạo giải thuật di truyền, bao gồm: - Số thế hệ: số thế hệ tiến hóa của quần thể. - Cách chọn lọc: cách thức thực hiện việc chọn lọc các cá thể trong quá trình tiến hóa (xem thêm mô tả lớp gaSelectionScheme bên dưới). - Tỷ lệ lai ghép: xác suất thực hiện lai ghép các cá thể trong quần thể. - Tỷ lệ ñột biến: xác suất thực hiện ñột biến trên các cá thể trong quần thể. 3 gaSelectionScheme Lớp cở sở, ñại diện cho cách thức chọn lọc tổng quát, chứa phương thức chung dùng ñể thực hiện việc chọn lọc cá thể trong quần thể. Từng cách thức chọn lọc cụ thể kế thừa từ lớp này ñể hiện thực hóa phương thức chọn lọc riêng. 83 Như vậy, sau khi ñã khởi tạo quần thể, giải thuật di truyền sẽ ñược áp dụng lên trên quần thể, ñiều khiển quá trình tiến hóa của quần thể qua các thế hệ. Bảng 6.9 mô tả các lớp ñối tượng chính ñược dùng trong giải thuật di truyền 6.2.6. Gói es 6.2.6.1. Kiến trúc gói es Gói es ñảm trách những vấn ñề liên quan ñến việc xây dựng và ñánh giá mô hình ước lượng. Gói es bao gồm những gói con sau: - es.function - es.metric Hình 6.8 mô tả kiến trúc của gói es thông qua sơ ñồ lớp. 84 H ìn h 6. 8. S ơ ñồ lớ p ki ến tr úc g ói e s củ a bộ th ư vi ện E sL ib . 85 6.2.6.2. Các chức năng chính của gói es 6.2.6.2.1. Tạo mô hình ước lượng từ tập dữ liệu lịch sử Chức năng chính của gói es là tạo mô hình ước lượng dựa trên tập dữ liệu lịch sử. ðây cũng là chức năng chính của bộ thư viện EsLib. Bảng 6.10. Chức năng các lớp dùng tạo mô hình ước lượng trong gói es. STT Tên lớp Ý nghĩa 1 esDataSet ðại diên cho tập dữ liệu lịch sử, là một bảng dữ liệu với mỗi dòng chứa thông tin lịch sử của một dự án phần mềm. 2 esModel ðại diện cho mô hình ước lượng cần xây dựng, mỗi mô hình ước lượng bao gồm bộ các thông số mô hình (esCostDriver) và công thức tính công (esFunction). 3 esCostDriver ðại diện cho thông số tính công của mô hình ước lượng. 4 esFunction Lớp cơ sở, ñại diện cho công thức tính công tổng quát của mô hình ước lượng. Mỗi loại công thức cụ thể kế thừa từ esFunction ñể hiện thực hóa công thức tính công riêng. 5 esExpFunction ðại diện cho công thức tính công dạng cây biểu thức, kế thừa từ esFunction và hiện thực hóa công thức tính công bằng cây biểu thức ñược phát sinh từ công cụ lập trình di truyền. 86 ðể thực hiện ñược chức năng này, gói es cung cấp những lớp ñối tượng cần thiết ñể biểu diễn tập dữ liệu lịch sử và mô hình ước lượng. Công thức tính công của mô hình ñã ñược công cụ lập trình di truyền ở gói ga và exp thực hiện. Bảng 6.10 mô tả những lớp ñối tượng chính dùng trong quá trình tạo mô hình ước lượng 6.2.6.2.2. ðánh giá khả năng ước lượng của mô hình Khả năng ước lượng của mô hình là một vấn ñề ñược quan tâm hàng ñầu trong quá trình xem xét triển khai mô hình vào thực tế. Vì vậy, bên cạnh chức năng tạo mô hình, gói es còn cài ñặt một nền tảng cho phép mô phỏng các ñộ ño dùng trong việc ñánh giá khả năng ước lượng của mô hình. Mỗi ñộ ño cho phép ñánh giá một khía cạnh của mô hình dựa trên một tập dữ liệu lịch sử ñược dùng làm thang ño. Bảng 6.11 mô tả những lớp ñối tượng chính trong việc mô phỏng các ñộ ño. Bảng 6.11. Chức năng các lớp dùng ñánh giá mô hình ước lượng trong gói es. STT Tên lớp Ý nghĩa 1 esMetric Lớp cơ sở, ñại diên cho ñộ ño mô hình tổng quát, chứa những thành phần chung nhất của các ñộ ño. Mỗi ñộ ño cụ thể kế thừa esMetric ñể hiện thực hóa cách thức ño riêng. Hiện tại có 3 lớp kế thừa từ esMetric tương ứng với 3 ñộ ño ñược hiện thức hóa là: MMRE, PRED và R2. 2 esMMREMetric ðại diện cho ñộ ño MMRE dùng ñánh giá ñộ chính xác của mô hình, kế thừa từ esMetric. 3 esPREDMectric ðại diện cho ñộ ño PRED dùng ñánh giá ñộ ổn ñịnh của mô hình, kế thừa từ esMetric. 4 esR2Metric ðại diện cho ñộ ño R2 dùng ñánh giá ñộ tin cậy của mô hình, kế thừa từ esMetric. 87 6.3. Ứng dụng Estimator 6.3.1. Mô tả Estimator Như ñã trình bày trong phần quy trình ước lượng cải tiến, với mô hình ước lượng truyền thống, quy trình ước lượng trải qua ba bước: - Lựa chọn mô hình. - Tinh chỉnh mô hình - Ước lượng bằng mô hình ñã tinh chỉnh. Khi áp dụng phương pháp ñề xuất, quy trình ước lượng ñược cải tiến bao gồm hai bước: - Xây dựng mô hình. - Ước lượng bằng mô hình ñã xây dựng. Ứng dụng Estimator ñược xây dựng nhằm hỗ trợ các bước trong quy trình ước lượng cải tiến. Nền tảng của ứng dụng chính là bộ thư viện EsLib ñược mô tả ở phần trên. Bảng 6.12 mô tả các chức năng của ứng dụng Estimator. Môi trường phát triển của ứng dụng Estimator: - Nền tảng phát triển: .NET Framework 3.0. - Ngôn ngữ lập trình: ngôn ngữ C#. - Cơ sở dữ liệu: các tập tin XML. 88 Bảng 6.12. Những chức năng chính của ứng dụng Estimator. STT Chức năng Mô tả 1 Xây dựng mô hình từ tập dữ liệu lịch sử Cho phép tạo mô hình ước lượng dựa trên tập dữ liệu lịch sử của người dùng. Tập dữ liệu lịch sử này không chịu ràng buộc như ở quá trình tinh chỉnh mô hình truyền thống. Mô hình mới có công thức tính công và bộ thông số ñược rút trích từ tập dữ liệu lịch sử. 2 Xây dựng mô hình từ ñầu Cho phép tạo mô hình ước lượng một cách thủ công. Người dùng tự ñịnh nghĩa công thức tính công và bộ thông số của mô hình. Chức năng này nhằm tạo ra sự linh ñộng và tự do cho người dùng. 3 Tinh chỉ mô hình Cho phép tinh chỉnh lại công thức tính công của mô hình sẵn có theo tập dữ liệu lịch sử. Lúc này, tập dữ liệu lịch sử bị ràng buộc phải bao gồm ñầy ñủ những thông số của mô hình. 4 Ước lượng công thực hiện bằng mô hình ñã xây dựng Cho phép lựa chọn mô hình ước lượng trong số những mô hình ñã xây dựng ñể thực hiện việc ước lượng công thực hiện dự án phần mềm. 5 Tùy biến thông số bộ phát sinh công thức Cho phép ñiều chỉnh những thông số cần thiết trong quá trình xây dựng mô hình từ tập dữ liệu lịch sử, nhằm thu ñược công thức tính công của mô hình như mong muốn. 89 6.3.2. Kiến trúc Estimator Ứng dụng Estimator ñược xây dựng theo kiến trúc ba tầng với mục ñích tạo ra tính linh ñộng, dễ dàng mở rộng về sau. Hình 6.9 mô tả kiến trúc của ứng dụng Estimator. Hình 6.9. Kiến trúc ứng dụng Estimator. Các tầng trong kiến trúc ứng dụng Estimator: - Tầng giao diện (Presentation Layer): bao gồm các màn hình của ứng dụng, các ñối tượng làm nhiệm vụ hiển thị và thu thập thông tin từ người dùng. Tầng giao diện chỉ có thể tương tác trực tiếp với tầng xử lý nghiệp vụ. Có thể 90 xem tầng giao diện là cầu nối giữa người dùng và các chức năng ñược hỗ trợ bởi tầng xử lý nghiệp vụ bên dưới. - Tầng xử lý nghiệp vụ (Business Layer): bao gồm các ñối tượng làm nhiệm vụ xử lý nghiệp vụ. Tầng nghiệp vụ cung cấp những chức năng của ứng dụng và thể hiện chúng bên ngoài cho người dùng thông qua tầng giao diện. Khi cần lưu trữ hay truy xuất dữ liệu, tầng nghiệp vụ tương tác trực tiếp với tầng dữ liệu bên dưới. - Tầng dữ liệu (Data Access Layer): bao gồm các ñơn vị dữ liệu của ứng dụng, các ñối tượng chịu trách nhiệm lưu trữ và truy xuất dữ liệu. Khi có yêu cầu về dữ liệu từ tầng xử lý nghiệp vụ, tầng dữ liệu thực hiện việc tìm kiếm, ñóng gói dữ liệu, sau ñó chuyển những gói này cho tầng xử lý nghiệp vụ. 6.3.3. Một vài màn hình của ứng dụng Estimator 6.3.3.1. Màn hình Ước lượng công thực hiện dự án phần mềm Hình 6.10. Màn hình ước lượng công thực hiện dự án phần mềm. 91 6.3.3.2. Màn hình Quản lý mô hình ước lượng Hình 6.11. Màn hình quản lý các mô hình ước lượng. 92 6.3.3.3. Màn hình Tùy biến thông số bộ phát sinh công thức Hình 6.12. Màn hình tùy biến thông số phát sinh công thức tính công.