Đề tài: Tìm hiều và ứng dụng của thuật giải di truyền trong bài toán xếp ba lô

Với khả năng hiện nay, máy tính đã giúp giải được rất nhiều bài toán khó mà trướcđây thường bó tay. Mặc dù vậy vẫn có một số lớn các bài toán thú vị mà chưa cógiải thuật hợp lý để giải chúng. Trong đó các bài toán tối ưu là những bài toánthường gặp trong thực tiễn.Bài toán tối ưu hóa tổ hợp có thể xem như bài toán tìm kiếm giải pháp tốt nhấttrong không gian vô cùng lớn các giải pháp. Khi không gian tìm kiếm nhỏ, nhữngphương pháp cổ điển như trên cũng đủ thích hợp,...
Nội dung trích xuất từ tài liệu:
Đề tài: Tìm hiều và ứng dụng của thuật giải di truyền trong bài toán xếp ba lôMỤC LỤC LỜI NÓI ĐẦUVới khả năng hiện nay, máy tính đã giúp giải được rất nhiều bài toán khó mà trướcđây thường bó tay. Mặc dù vậy vẫn có một số lớn các bài toán thú vị mà chưa cógiải thuật hợp lý để giải chúng. Trong đó các bài toán tối ưu là những bài toánthường gặp trong thực tiễn.Bài toán tối ưu hóa tổ hợp có thể xem như bài toán tìm kiếm giải pháp tốt nhấttrong không gian vô cùng lớn các giải pháp. Khi không gian tìm kiếm nhỏ, nhữngphương pháp cổ điển như trên cũng đủ thích hợp, nhưng khi không gian tìm kiếmlớn phải dùng kỹ thuật trí tuệ nhân tạo đặc biệt. Thuật giải di truyền (GA) là mộttrong những kỹ thuật đó.Giải thuật di truyền là một kỹ thuật của khoa học máy tính nhằm tìm kiếm giải phápthích hợp cho các bài toán tối ưu tổ hợp (combinatorial optimization). Giải thuật ditruyền là một phân ngành của giải thuật tiến hóa vận dụng các nguyên lý của tiếnhóa như di truyền, đột biến, chọn lọc tự nhiên, và trao đổi chéo.Ngày nay, giải thuật di truyền được dùng phổ biến trong một số ngành như tin sinhhọc, khoa học máy tính, trí tuệ nhân tạo, tài chính và một số ngành khác.Bài toán xếp ba lô (một số sách ghi là bài toán cái túi) là một bài toán tối ưu hóa tổhợp. Bài toán được đặt tên từ vấn đề chọn những gì quan trọng có thể nhét vừa vàotrong một cái túi (với giới hạn khối lượng) để mang theo trong một chuyến đi. Cácbài toán tương tự thường xuất hiện trong kinh doanh, toán tổ hợp, lý thuyết độ phứctạp tính toán, mật mã học và toán ứng dụng.Chính vì ứng dụng lớn của giải thuật di truyền( GA) và bài toán xếp ba lô, với sựgiúp đỡ của thầy Trần Thanh Hùng giáo viên bộ môn Giải thuật di truyền, chúngem tiến hành đi tìm hiểu về giải thuật di truyền và ứng dụng của giải thuật di truyềntrong bài toán xếp ba lô với đề tài “Tìm hiều và ứng dụng của thuật giải di truyềntrong bài toán xếp ba lô”.Sinh viên thực hiện:Trần Quang Hợp.MSSV: 0441060068.Lớp: KHMT1-K4-Đại học công nghiệp Hà Nội(Haui).Email: hauiquanghop@gmail.comMôn Giải thuật di truyền và ứng dụng. CHƯƠNG I - TỔNG QUAN VỀ GIẢI THUẬT DI TRUYỀN 1. Khái niệm Giải thuật di truyền là một kỹ thuật của khoa học máy tính nhằm tìm kiếm giảipháp thích hợp cho các bài toán tối ưu tổ hợp (combinatorial optimization). Giải thuậtdi truyền là một phân ngành của giải thuật tiến hóa vận dụng các nguyên lý của tiếnhóa như di truyền, đột biến, chọn lọc tự nhiên, và trao đổi chéo.Ngày nay, giải thuật di truyền được dùng phổ biến trong một số ngành như tin sinhhọc, khoa học máy tính, trí tuệ nhân tạo, tài chính và một số ngành khác.Tư tưởng của thuật toán di truyền là mô phỏng các hiện tượng tự nhiên: Kế thừavà đấu tranh sinh tồn để cái tiến lời giải và khảo sát không gian lời giải khái niệmkế thừa và đấu tranh sinh tồn được giải thích qua thí dụ về sự tiến hóa của mộtquần thể thỏ như sau:Có một quần thể thỏ, trong đó có một số con nhanh nhẹn và thông minh hơn nhữngcon khác. Những chú thỏ nhanh nhẹn và thông minh có xác suất bị chồn cáo ăn thịtnhỏ hơn, do đó cũng tồn tại dể làm những gì tốt nhất có thể : Tạo thêm nhiềuthỏ tốt. Dĩ nhiên, một số thỏ chậm chạp đần độn cũng sống sót vì may mắn.Quần thể những chú thỏ còn sống sót sẽ bắt đầu sinh sản. Việc sinh sản này sẽtạo ra một hỗn hợp tốt về nguyên liệu di truyền thỏ. Một số thỏ chậm chạp cócon với những con thỏ nhanh, một số nhanh nhẹn có con với thỏ nhanh nhẹn, mộtsố thông minh với thỏ đần độn… Và trên tất cả thiên nhiên lại ném vào một con thỏhoang dã bằng cách làm đột biến nguyên liệu di truyền thỏ. Những chú thỏ con dokết quả này sẽ nhanh hơn và thông minh hơn những con thỏ trong quần thể gốc vìcó nhiều bố mẹ nhanh nhẹn và thông minh hơn đã thoát chết khỏi chồn cáo.Khi tìm kiếm lời giải tối ưu , thuật toán di truyền cũng thực hiện các bước tươngứng với câu chuyện đấu tranh sinh tồn của loài thỏ.Thuật toán di truyền sử dụng các thuật ngữ vay mượn của di truyền học. Ta có thểnói về các cá thể (hay kiểu gen, cấu trúc) trong một quần thể, những cá thể nàycũng còn được gọi là chuỗi hay các nhiễm sắc thể.Mỗi kiểu gen (ta gọi là một nhiễm sắc thể) sẽ biểu diễn một lời giải của bài toánđang giải (ý tưởng của một nhiễm sắc thể cụ thể được người sử dụng xác địnhtrước), một tiến trình tiến hóa được thực hiện trên một quần thể các nhiễm sắc thểtương ứng với một quá trình tìm kiếm lời giải trong không gian lời giải. Tìm kiếmđó cần cân đối hai mục tiêu: Khai thác những lời giải tốt nhất và khảo sát khônggian tìm kiếm. Leo đồi là một ví dụ về chiến lược cho phép khai thác và cải thiệnlời giải tốt nhất hiện hành nhưng leo đồi lại bỏ qua việc khảo sát không gian tìmkiếm. Ngược lại, tìm kiếm ngẫu nhiên là một ví dụ điển hình của chiến lược khảosát không gian tìm kiếm mà không chú ý đến việc khai thác những vùng đầy hứahẹn của không gian. Thuật toán di truyền (GA) là phương pháp tìm kiếm (độc lậpmiền) tạ ...