Luận văn Thạc sĩ Công nghệ thông tin: Ứng dụng thuật toán di truyền giải bài toán đóng thùng

Luận văn "Ứng dụng thuật toán di truyền giải bài toán đóng thùng" tập trung vào xây dựng một thuật toán di truyền để giải bài toán đóng thùng (bin packing problem), một bài toán tối ưu tổ hợp thuộc lớp bài toán NP – khó có nhiều ứng dụng trong thực tế như thiết kế lập lịch tối ưu cho công việc; sắp xếp hàng hóa kho chứa và container tối ưu; cấp phát bộ nhớ hiệu quả; hỗ trợ thiết kế các vi mạch điện tử.
Nội dung trích xuất từ tài liệu:
Luận văn Thạc sĩ Công nghệ thông tin: Ứng dụng thuật toán di truyền giải bài toán đóng thùng bé gi¸o dôc vµ ®µo t¹o trêng ®¹i häc b¸ch khoa hµ néi --------------------------------------- NGUYỄN NGỌC DƯƠNG NGUYỄN NGỌC DƯƠNG ngµnh CNTT ỨNG DỤNG THUẬT TOÁN DI TRUYỀN GIẢI BÀI TOÁN ĐÓNG THÙNG luËn v¨n th¹c sÜ NGµNH C¤NG NGHÖ TH¤NG TINkho¸ 2007-2009 Hµ néi – 2009 bé gi¸o dôc vµ ®µo t¹o trêng ®¹i häc b¸ch khoa hµ néi --------------------------------------- NGUYỄN NGỌC DƯƠNG ỨNG DỤNG THUẬT TOÁN DI TRUYỀN GIẢI BÀI TOÁN ĐÓNG THÙNGluËn v¨n th¹c sÜ C¤NG NGHÖ TH¤NG TIN Ngêi híng dÉn khoa häc : PGS.TS. NGUYÔN §øC NGHÜA Hµ Néi – 2009 Lời cảm ơnĐầu tiên tôi xin bày tỏ sự biết ơn sâu sắc PGS. TS. Nguyễn Đức Nghĩa, thầy đã tận tìnhgiảng dạy chúng tôi các môn học chuyên ngành và nhiệt tình hướng dẫn, giúp đỡ tôi hoànthành luận văn này.Tôi cũng muốn bày tỏ lòng biết ơn các thầy cô khoa Công nghệ Thông tin trườngĐại học Bách khoa Hà Nội đã giảng dạy cho chúng tôi các môn học chuyên đềtrong khóa học.Cuối cùng gia đình, đặc biệt người bạn đời của tôi, là những người rất quan trọng đãmột lòng động viên và tạo điều kiện giúp tôi tập trung hoàn thành luận văn này.Mặc dù đã có nhiều cố gắng, nhưng vì kiến thức và thời gian hạn chế nên chắc chắnluận văn này còn nhiều thiếu sót. Tôi xin chân thành cảm ơn và rất mong nhận đượcnhững ý kiến đóng góp từ các thầy cô và các bạn. Những góp ý xin gửi về địa chỉ: Nguyễn Ngọc Dương Bộ môn Khoa học máy tính, khoa Công nghệ thông tin, trường Đại học Bách Khoa Hà Nội. Email: duongnn@it-hut.edu.vn hoặc nguyenngocduong@gmail.com Hà Nội, ngày 21 tháng 7 năm 2009 Nguyễn Ngọc Dương Học viên cao học Lớp Công nghệ thông tin 2007 – 2009 Trường Đại học Bách Khoa Hà Nội MỤC LỤCDanh mục hình vẽ.....................................................................................................ivDanh mục bảng.........................................................................................................viDanh mục thuật ngữ tiếng Anh............................................................................. viiChương 1. MỞ ĐẦU .................................................................................................1 1.1. Lời mở đầu .......................................................................................................1 1.2. Các khái niệm và thuật ngữ cơ sở ....................................................................3 1.2.1. Bài toán tính toán, thuật toán và độ phức tạp tính toán của thuật toán .3 1.2.2. Các kí hiệu tiệm cận ...............................................................................6 1.2.3. Độ phức tạp tính toán của bài toán ........................................................8 1.2.4. NP- đầy đủ (NP – completeness) .........................................................11 1.3. Một số cách tiếp cận giải các bài toán NP-khó ..............................................18 1.3.1. Phương pháp xấp xỉ .............................................................................18 1.3.2. Phương pháp xác xuất ..........................................................................19 1.3.3. Phương pháp heuristic..........................................................................20 1.4. Bài toán đóng thùng .......................................................................................21 1.4.1. Phát biểu bài toán .................................................................................21 1.4.2. Các biến thể của bài toán đóng thùng ..................................................23 1.4.3. Ứng dụng của bài toán đóng thùng ......................................................25Chương 2 MỘT SỐ PHƯƠNG PHÁP GIẢI BÀI TOÁN ĐÓNG THÙNG ..... 27 2.1. Tổng quan các phương pháp giải bài toán đóng thùng ..................................27 2.2. Các phương pháp heuristic đơn giản .............................................................27 2.2.1. Các thuật toán trực tiếp ........................................................................27 2.2.2. Các phương pháp không trực tiếp ............................................ ...