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

1.1. ðặt vấn đề Sản xuất phần mềm ngày nay đã trở thành một ngành công nghiệp rộng lớn và năng động, đòi hỏi nhân lực ở trình độ cao. Sản phẩm phần mềm ngày càng trở nên phức tạp, khó dự đoán và khó kiểm soát hơn bao giờ hết. Những thập niên vừa qua đã chứng kiến nhiều công trình nghiên cứu trong lĩnh vực phần mềm nhằm đưa quá trình sản xuất phần mềm vào quy cũ, dễ quản lý hơn và có thể tiên liệu được. ðặc biệt, hướng nghiên cứu về ước lượng công thực hiện phần mềm luôn được quan tâm, với số lượng các công trình nghiên cứu khoa học ngày càng gia tăng trong khoảng thời gian gần đây [14]. Trong quá trình phát triển phần mềm, việc ước lượngchi phí phần mềm trước khi phát triển là rất cần thiết. ðiều này cung cấp một cái nhìn trước về sản phẩm phần mềm, giúp cho việc hoạch định ngân sách, đấu thầu dự án, lên kế hoạch phát triển, phân bổ nhân lực và giảm thiểu những rủi ro. Chi phí phần mềm bao gồm hai loại: chi phí sản xuất và chi phí môi trường. Trong đó, chi phí môi trường có thể chiếm đến hơn 2/3 chi phí phần mềm, nhưng nó phụ thuộc nhiều vào những yếu tố kinh tế khó dự đoán trước như: giá cả, biến động thị trường, kỹ năng đàm phán, ðiều này làm cho việc ước lượng trước chi phí môi trường là điều bất khả. Vì vậy những nghiên cứu về ước lượng phần mềm tập trung vào việcước lượng công thực hiện phần mềm. ðây là một cơ sở quan trọng để tính toán chi phí sản xuất phần mềm. Hiện tại, các phương pháp ước lượng công thực hiện phần mềm có thể được phân vào ba nhóm chính: nhóm ước lượng dựa vào chuyên gia, nhóm ước lượng dựa vào công thức, và nhóm ước lượng dựa vào máy học. Trongsố đó, nhóm phương pháp ước lượng dựa vào công thức hiện được sử dụng rộng rãi với hai mô hình ước lượng nổi tiếng được bán dưới dạng sản phẩm thương mại làCOCOMO và SLIM. Ý tưởng chính của phương pháp ước lượng dựa vào công thức là dùng một phương trình toán học ở dạng hàm nhiều biến để biểu diễn mối liên hệ giữa đại lượng công và các thông số của dự án phần mềm cần ước lượng. Ưuđiểm của phương pháp này là tính khách quan của nó. Với cùng một bộ thông sốđầu vào như nhau, công thức tính công của mô hình ước lượng luôn cho đầu ra kết quả như nhau. Kết quả này không phụ thuộc vào người thực hiện công việc ước lượng và có thể dễ dàng được kiểm chứng. Một ưu điểm nữa của phương pháp ước lượng dựa vào công thức là tốc độ và giá thành. Thời gian đưa ra kết quả ước lượngnhanh chóng và ít tốn kém hơn rất nhiều so với việc thuê chuyên gia. Tuy nhiên, phương pháp ước lượng dựa vào công thức cũng có một vài hạn chế. Hạn chế lớn nhất của nó là những mô hình ước lượng được xây dựng dựa trên một tập dữ liệu lịch sử cục bộ của một đội ngũ phát triển nào đó do tác giả mô hình sưu tầm được. Các công thức tính công của mô hình thường không chính xác khi áp dụng vào thực tế từng công ty với từng loại dự án cụ thể. Trong trường hợp đó, phần lớn các mô hình ước lượng đều cung cấp một cách thức để tinh chỉnh lại công thức tính công cho phù hợp với tập dữ liệu lịch sử của riêng từng công ty. Nhưng trong đa số trường hợp, tập dữ liệu lịch sử sẵn có của công ty không chứa đầy đủ những thông số mô hình quy định, hoặc chứa những thông số mang ý nghĩa hoàn toàn khác. Các công ty phần mềm bấy giờ phải lựa chọn: hoặc điều chỉnh lại những thông số trong tập dữ liệu lịch sử của mình cho phùhợp, hoặc thu thập lại tập dữ liệu lịch sử mới từ đầu thỏa quy định của mô hình. Cả hai lựa chọn này điều tốn rất nhiều thời gian và công sức của công ty muốn áp dụng mô hình. Một hạn chế nữa đối với phương pháp ước lượng dựa vào công thức, đó là bộ thông số tính công của các mô hình ước lượng là cố định, không thay đổi theo thời gian. Bộ thông số này phản ánh những yếu tố liên quan đếncông thực hiện dự án phần mềm cần ước lượng như: kích thước, độ phức tạp, quytrình phát triển, các yếu tố môi trường, Và theo thời gian, với sự phát triển không ngừng của công nghệ, và với sự biến đổi khôn lường của môi trường làm phần mềm, bộ thông số này có khả năng trở nên lạc hậu, không còn phản ánh chính xác những yếu tố của dự án phần mềm nữa. Tóm lại, bên cạnh những ưu điểm vượt trội so với những phương pháp khác, phương pháp ước lượng dựa vào công thức có những hạn chế lớn làm giảm hiệu quả sử dụng của nó. 1.2. Mục tiêu luận văn Với những ưu điểm và hạn chế của phương pháp ước lượng dựa vào công thức nêu trên, mục tiêu của luận văn là đưa ra một phương pháp cải tiến các mô hình ước lượng dựa vào công thức nhằm khắc phục những hạn chế của nó, trong khi vẫn phát huy được những ưu điểm của loại mô hình này. Hướng tiếp cận của luận văn là thay vì sử dụng cáchthức tinh chỉnh riêng của từng mô hình để tinh chỉnh lại mô hình ước lượng dựa vàocông thức cho phù hợp với tập dữ liệu lịch sử trước khi sử dụng, luận vặn đề xuất giải pháp xây dựng mô hình ước lượng hoàn toàn mới dựa trên tập dữ liệu lịch sửcủa người dùng. ðể thực hiện được việc này, luận văn sử dụng công cụ lập trình di truyền, một nhánh nhỏ của giải thuật di truyền, áp dụng vào phân tích hồi quy để tạo ra công thức tính công cho mô hình ước lượng mới. Công cụ lập trình di truyền do luận văn xây dựng có tính linh động cao, cho phép người dùng can thiệp vào quá trình phát sinh công thức, thêm vào những tùy biến để thu được công thức tính công theo những dạng thức hay có những tính chất theo ý muốn chủ quan của mình. 1.3. Cấu trúc luận văn Luận văn được chia làm bốn phần: Phần 1, mở đầu luận văn, gồm chương 1, cung cấp mộtcái nhìn tổng thể về luận văn, tóm tắt những mục tiêu luận văn đề ra. Cấu trúc và cách thức trình bày các chương trong luận văn cũng được đề cập trong phần này. Phần 2, hiện trạng và các nghiên cứu trong lĩnh vựcước lượng công thực hiện phần mềm, bao gồm hai chương 2 và 3. Chương 2, phần đầu giới thiệu những khái niệm cơ bản về ước lượng công thực hiện phần mềm như: ước lượng, chi phí phần mềm, công thực hiện, thông số dự án, đơn vị người-tháng, , phần còn lại mô tả những nhóm phương pháp được sử dụng phổ biến trong việc ước lượng công thực hiện dự án phần mềm. Chương 3 trình bày những nghiên cứu vàkết quả đạt được trong việc á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 trong thời gian gần đây. Phần 3, hướng tiếp cận và giải pháp đề xuất của luận văn, bao gồm bốn chương 4, 5, 6 và 7. Chương 4 trình bày những nhận định của luậnvăn về ước lượng công thực hiện phần mềm, từ đó nêu ra những vẫn đề gặp phải và đề xuất phương hướng giải quyết. Do hướng tiếp cận của luận văn là lập trình di truyền nên chương 5 sẽ đề cập đến giải thuật di truyền, lập trình di truyền và việc áp dụng lập trình di truyền vào phân tích hồi quy. Chương 6 tập trung mô tả về phương pháp do luận văn đề xuất, 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. Cấu trúc bộ thư viện EsLib, phần cốt lõi của bộ phát sinh công thức dùng trong phương pháp đề xuất cũng được trình bày chi tiết. Chương 7 giới thiệu sơ lược các độ đo mô hình ước lượng, trình bày quá trình kiểm nghiệm cũng như những kết quả đạt được trên các tập dữ liệu công cộng thu thập được. Phần 4, kết luận của luận văn, gồm chương 8, trình bày những kết quả đạt được của luận văn, cũng như những mặt hạn chế và hướng phát triển của luận văn trong tương lai.

pdf29 trang | Chia sẻ: tuandn | Ngày: 17/04/2013 | Lượt xem: 1409 | Lượt tải: 0download
Bạn đang xem nội dung tài liệu 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, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trê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”

Các file đính kèm theo tài liệu này:

  • pdf10.pdf
  • pdf1.pdf
  • pdf2.pdf
  • pdf3.pdf
  • pdf4.pdf
  • pdf5.pdf
  • pdf6.pdf
  • pdf7.pdf
  • pdf8.pdf
  • pdf9.pdf
  • pdf11.pdf
  • pdf12.pdf
  • pdf13.pdf
  • pdf14.pdf
Luận văn liên quan