Báo cáo tóm tắt đề tài khoa học và công nghệ: Nghiên cứu một số thuật toán lấy cảm hứng từ tự nhiên và ứng dụng vào bài toán tối ưu nỗ lực, chi phí phát triển phần mềm

ĐẠI HỌC ĐÀ NẴNG<br /> TRƯỜNG ĐẠI HỌC BÁCH KHOA<br /> <br /> BÁO CÁO TÓM TẮT<br /> ĐỀ TÀI KHOA HỌC VÀ CÔNG NGHỆ CẤP ĐẠI HỌC ĐÀ NẴNG<br /> <br /> NGHIÊN CỨU MỘT SỐ THUẬT TOÁN LẤY CẢM HỨNG<br /> TỪ TỰ NHIÊN VÀ ỨNG DỤNG VÀO BÀI TOÁN<br /> TỐI ƯU NỖ LỰC, CHI PHÍ PHÁT TRIỂN PHẦN MỀM<br /> Mã số: B2016-ĐN02-06<br /> <br /> Chủ nhiệm đề tài: TS. Lê Thị Mỹ Hạnh<br /> Thành viên : KS. Khuất Thanh Tùng<br /> KS. Ngô Thành Phát<br /> <br /> Đà nẵng, 5/2018<br /> <br /> Mục lục<br /> <br /> ii<br /> <br /> MỤC LỤC<br /> MỤC LỤC .................................................................................................................................. I<br /> DANH SÁCH HÌNH VẼ ........................................................................................................ IV<br /> DANH SÁCH BẢNG ............................................................................................................. IV<br /> CHƯƠNG 1. CÁC THUẬT TOÁN TỐI ƯU LẤY CẢM HỨNG TỪ TỰ NHIÊN ............... 1<br /> 1.1. Giới thiệu vấn đề ....................................................................................................... 1<br /> 1.2. Tính phức tạp của bài toán tối ưu .............................................................................. 1<br /> 1.3. Phân lớp các nguồn cảm hứng từ tự nhiên để xây dựng thuật toán tối ưu ................ 1<br /> 1.4. Tổng quan về các thuật toán tối ưu từ tự nhiên ......................................................... 1<br /> 1.5. Giới thiệu chung về các thuật toán được sử dụng trong đề tài .................................. 1<br /> 1.6. Thuật toán đàn ong nhân tạo ..................................................................................... 2<br /> 1.7. Thuật toán dạy-học .................................................................................................... 2<br /> 1.8. Thuật toán đàn ong nhân tạo kết hợp dạy học ........................................................... 2<br /> 1.9. Thuật toán tối ưu bầy đàn .......................................................................................... 2<br /> 1.10. Thuật toán lai giữa đàn ong nhân tạo và tối ưu bầy đàn (ABC-PSO) ....................... 2<br /> CHƯƠNG 2. BÀI TOÁN ƯỚC LƯỢNG NỖ LỰC PHÁT TRIỂN PHẦN MỀM .................. 3<br /> 2.1. Giới thiệu bài toán ..................................................................................................... 3<br /> 2.2. Tổng quan về các kỹ thuật ước lượng nỗ lực phần mềm .......................................... 3<br /> 2.3. Các phương pháp ước lượng nỗ lực dựa trên phương tình toán học ......................... 4<br /> 2.3.1.<br /> Mô hình ước lượng giá cấu thành COCOMO ............................................... 4<br /> 2.3.1.1. Các phương thức phát triển phần mềm trong mô hình COCOMO ......... 4<br /> 2.3.1.2. Mô hình COCOMO cơ sở ........................................................................ 4<br /> 2.3.1.3. Mô hình COCOMO trung cấp ................................................................. 4<br /> 2.3.1.4. Mô hình COCOMO nâng cao .................................................................. 4<br /> 2.3.1.5. Mô hình COCOMO II .............................................................................. 4<br /> 2.3.2.<br /> Phương pháp điểm chức năng ....................................................................... 8<br /> 2.3.3.<br /> Kết hợp COCOMO II và điểm chức năng để ước lượng nỗ lực ................... 8<br /> 2.4. Phương pháp ước lượng nỗ lực cho quy trình phần mềm Agile ............................... 8<br /> 2.4.1.<br /> Quy trình phát triển phần mềm Agile............................................................ 8<br /> 2.4.1.1. Các nguyên tắc của quy trình Agile......................................................... 8<br /> 2.4.1.2. Các đặc trưng của quy trình Agile .......................................................... 8<br /> 2.4.2.<br /> Phương pháp ước lượng nỗ lực phát triển phần mềm sử dụng quy trình Agile8<br /> 2.4.2.1. Các yếu tố đầu vào của mô hình ước lượng ............................................ 9<br /> 2.4.2.2. Xác định story point cho dự án .............................................................. 10<br /> 2.4.2.3. Xác định vận tốc của nhóm phát triển ................................................... 11<br /> 2.4.2.4. Xác định thời gian và chi phí dự án ...................................................... 11<br /> CHƯƠNG 3. CÀI ĐẶT, THỬ NGHIỆM VÀ ĐÁNH GIÁ KẾT QUẢ ................................. 12<br /> 3.1. Đặt vấn đề................................................................................................................ 12<br /> 3.2. Các tiêu chuẩn đánh giá kết quả ước lượng nỗ lực ................................................. 13<br /> 3.3. Tối ưu tham số mô hình COCOMO bằng thuật toán TLABC ................................ 13<br /> 3.3.1.<br /> Hàm thích nghi ............................................................................................ 13<br /> 3.3.2.<br /> Kết quả thực nghiệm ................................................................................... 14<br /> 3.4. Phương trình toán học mới cho bài toán ước lượng nỗ lực phát triển cho các phần mềm<br /> sử dụng quy trình Agile ...................................................................................................... 14<br /> 3.4.1.<br /> Phương trình toán học đề xuất .................................................................... 14<br /> <br /> Mục lục<br /> iii<br /> 3.4.2.<br /> Tìm tham số tối ưu cho công thức ước lượng Agile sử dụng thuật toán ABCPSO<br /> ..................................................................................................................... 14<br /> 3.4.2.1. Biểu diễn cá thể của thuật toán và hàm thích nghi ............................... 15<br /> 3.4.2.2. Kết quả thực nghiệm .............................................................................. 15<br /> 3.5. Phân tích chức năng của chương trình .................................................................... 15<br /> 3.6. Thiết kế chương trình .............................................................................................. 15<br /> 3.6.1.<br /> Biểu đồ ca sử dụng (Use case) .................................................................... 16<br /> 3.6.2.<br /> Biểu đồ tuần tự và hoạt động ...................................................................... 17<br /> 3.6.3.<br /> Biểu đồ lớp .................................................................................................. 18<br /> 3.7. Một số hình ảnh của hệ thống ước lượng nỗ lực ..................................................... 19<br /> KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN .............................................................................. 21<br /> <br /> Danh sách hình vẽ và bảng<br /> <br /> iv<br /> <br /> DANH SÁCH HÌNH VẼ<br /> Hình 1.<br /> Hình 2.<br /> Hình 3.<br /> Hình 4.<br /> Hình 5.<br /> Hình 6.<br /> Hình 7.<br /> Hình 8.<br /> Hình 9.<br /> Hình 10.<br /> Hình 11.<br /> <br /> Phân loại các nguồn cảm hứng từ tự nhiên ....................................................... 1<br /> Phân loại các kỹ thuật ước lượng nỗ lực phát triển phần mềm ......................... 3<br /> Biểu đồ Ca sử dụng (Use case) ....................................................................... 16<br /> Biểu đồ phân rã chức năng xem dự án ............................................................ 17<br /> Biểu đồ tuần tự của chức năng ước lượng dự án ............................................. 17<br /> Biểu đồ hoạt động của chức năng thiết lập tham số mô hình ước lượng ........ 18<br /> Biểu đồ lớp của hệ thống ước lượng nỗ lực .................................................... 18<br /> Giao diện chức năng chính của phần mềm ước lượng nỗ lực ......................... 19<br /> Giao diện khi một dự án đã kết thúc ............................................................... 19<br /> Giao diện chức năng tạo mới một dự án COCOMO ....................................... 20<br /> Giao diện chức năng thiết lập cấu hình tham số.............................................. 20<br /> <br /> DANH SÁCH BẢNG<br /> Bảng 1.<br /> Bảng 2.<br /> Bảng 3.<br /> Bảng 4.<br /> Bảng 5.<br /> Bảng 6.<br /> Bảng 7.<br /> <br /> Các yếu tố hiệu chính chi phí của mô hình COCOMO II ................................. 4<br /> Thang điểm các yếu tố hiệu chỉnh chi phí mô hình COCOMO II .................... 6<br /> Các nhân tố ảnh hưởng đến quy mô dự án ........................................................ 7<br /> Thang điểm các nhân tố ảnh hưởng đến quy mô dự án..................................... 7<br /> Điểm quy mô cho các user story ..................................................................... 10<br /> Kết quả ước lượng nỗ lực sử dụng thuật toán ABC, TLABC, COCOMO II .. 14<br /> Kết quả ước lượng của các thuật toán tối ưu trên các tiêu chí đánh giá.......... 15<br /> <br /> Danh sách từ viết tắt<br /> <br /> v<br /> <br /> DANH SÁCH TỪ VIẾT TẮT<br /> Từ viết tắt<br /> ABC<br /> ABC-PSO<br /> CCNN<br /> CoBRA<br /> COCOMO<br /> D<br /> DF<br /> EAF<br /> Eff<br /> ES<br /> FP<br /> FR<br /> GMDHPNN<br /> GRNN<br /> KLOC<br /> MAR<br /> MdMRE<br /> ME<br /> MMRE<br /> MRE<br /> NE<br /> NP<br /> PNN<br /> PSO<br /> PRED(N)<br /> SF<br /> SP<br /> TCF<br /> TLBO<br /> TLABC<br /> UFP<br /> Vi<br /> V<br /> <br /> Ý nghĩa<br /> Artificial Bee Colony – Thuật toán đàn ong nhân tạo<br /> Hybrid Artificial Bee Colony and Particle Swarm Optimization – Thuật toán<br /> lai giữa đàn ong nhân tạo và tối ưu bầy đàn<br /> Cascade-Correlation Neural Networks – Mạng nơ-ron tương quan xếp tầng<br /> Phương pháp ước lượng chi phí, chuẩn hóa và phân tích rủi ro<br /> COnstructive COst MOdel – Mô hình ước lượng giá cấu thành<br /> Số chiều của bài toán<br /> Hệ số giảm tốc của các yếu tố hay biến động trong dự án Agile<br /> Effort adjustment factor – Yếu tố hiệu chỉnh nỗ lực<br /> Effort – Nỗ lực<br /> Điểm cho mỗi user story<br /> Function Point – Điểm chức năng<br /> Hệ số giảm vận tốc thường xuyên trong dự án Agile<br /> Group Method of Data Handling Polynomial Neural Network – Mạng nơ-ron<br /> với phương pháp nhóm xử lý dữ liệu tuyến tính<br /> General Regression Neural Networks – Mạng nơ-ron hồi quy tổng quát<br /> Ngàn dòng lệnh<br /> Mean Absolute Residual – số dư tuyệt đối trung bình<br /> Median Magnitude of Relative Error – Độ lớn trung vị của lỗi tương đối<br /> Methodology – Nhân tố phương pháp luận trong mô hình Sheta-Uysal<br /> Mean Magnitude of Relative Error – Độ lớn trung bình của lỗi tương đối<br /> Magnitude of Relative Error – Độ lớn của lỗi tương đối<br /> Số ong thợ trong thuật toán ABC<br /> Số cá thể trong thuật toán tối ưu bầy đàn<br /> Probabilistic Neural Networks – Mạng nơ-ron xác suất<br /> Particle Swarm Optimization – Thuật toán tối ưu bầy đàn<br /> Precision at level N – Độ chính xác ở mức lỗi dưới N%<br /> Nhân tố ảnh hưởng đến quy mô dự án<br /> Tổng điểm Story point của một dự án Agile<br /> Độ phức tạp kỹ thuật của thệ thống sử dụng phân tích điểm chức năng<br /> Teaching-learning-based Optimization – Thuật toán tối ưu dạy học<br /> Teaching-learining based Artificial Bee Colony – Thuật toán đàn ong nhân<br /> tạo cải tiến sử dụng cơ chế dạy học<br /> Điểm chức năng thô<br /> Vận tốc cơ sở của nhóm phát triển<br /> Vận tốc sau hiệu chỉnh của nhóm phát triển<br /> <br />