- Huỳnh Thị Thanh Bình Hà Nội – Năm 2014 Giải thuật di truyền giải bài toán lập kế hoạch học tập 2 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 MỤC LỤC MỤC LỤC. - GIẢI THUẬT DI TRUYỀN. - Lịch sử giải thuật di truyền. - 23 Giải thuật di truyền giải bài toán lập kế hoạch học tập 3 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 2.2. - ỨNG DỤNG GIẢI THUẬT DI TRUYỀN. - Các bài toán tối ƣu. - THAM SỐ CỦA GIẢI THUẬT. - 58 Giải thuật di truyền giải bài toán lập kế hoạch học tập 4 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 4.3. - 77 Giải thuật di truyền giải bài toán lập kế hoạch học tập 5 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 LỜI CAM ĐOAN Luận văn Thạc sĩ ―Giải thuật di truyền giải bài toán lập kế hoạch học tập‖, chuyên ngành Công nghệ thông tin là công trình của cá nhân tôi. - Ngày 25 tháng 3 năm 2014 Tác giả luận văn Đỗ Ngọc Phục Giải thuật di truyền giải bài toán lập kế hoạch học tập 6 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 DANH MỤC THUẬT NGỮ - VIẾT TẮT STT Viết tắt Nguyên gốc Chú thích 1. - GA Genetic Algorithm Giải thuật di truyền 5. - Xuất Xuất danh sách bản ghi ra excel Giải thuật di truyền giải bài toán lập kế hoạch học tập 7 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 DANH MỤC HÌNH VẼ, ĐỒ THỊ Hình 1. - Mô hình giải thuật. - 70 Giải thuật di truyền giải bài toán lập kế hoạch học tập 8 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 Hình 26. - 73 Giải thuật di truyền giải bài toán lập kế hoạch học tập 9 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 DANH MỤC BẢNG Bảng 1. - 64 Giải thuật di truyền giải bài toán lập kế hoạch học tập 10 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 Bảng 27. - 69 Giải thuật di truyền giải bài toán lập kế hoạch học tập 11 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 MỞ ĐẦU 1. - Bài toán lập kế hoạch học tập thuộc lớp các bài toán NP-đầy đủ vì vậy có thể không tìm ra lời giải tối ƣu. - Vì vậy việc nghiên cứu và ứng dụng giải thuật di truyền (Genetic Giải thuật di truyền giải bài toán lập kế hoạch học tập 12 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 Algorithm - GA) để giải quyết hiệu quả bài toán lập kế hoạch học tập là việc làm cần thiết. - Mục tiêu của đề tài Đề tài tập trung nghiên cứu và ứng dụng giải thuật di truyền vào bài toán lập kế hoạch học tập cho Trƣờng Sĩ quan Tăng Thiết Giáp (TSQTTG). - Tìm hiểu giải thuật di truyền và ứng dụng của nó trong việc giải quyết các bài toán tối ƣu. - Ứng dụng giải thuật di truyền vào bài toán lập kế hoạch học tập cho trƣờng. - Ứng dụng giải thuật di truyền vào bài toán lập kế hoạch học tập tại một trƣờng cấp Đại học trong ngành Quân đội theo học niên chế với những ràng buộc và những yêu cầu cơ bản. - Biểu diễn bài toán lập kế hoạch học tập trong trƣờng bằng mô hình giải thuật di truyền. - Giải thuật di truyền giải bài toán lập kế hoạch học tập 13 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 b. - Xây dựng hệ thống lập kế hoạch học tập sử dụng giải thuật di truyền. - Đề ra đƣợc giải pháp và ứng dụng các vấn đề của giải thuật di truyền vào việc giải quyết bài toán lập kế hoạch học tập cho trƣờng SQTTG. - Giải thuật di truyền giải bài toán lập kế hoạch học tập 15 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 CHƢƠNG 1. - Tính đến nay có rất nhiều các đề xuất sử dụng giải thuật di truyền cho bài toán lập lịch. - Phát biểu bài toán. - Ứng dụng của bài toán. - Giải thuật di truyền giải bài toán lập kế hoạch học tập 16 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 lịch thi, hoặc một vài sự kiện trong trƣờng đại học. - Từ đó, luận văn đề xuất một giải thuật GA giải bài toán lập kế hoạch học tập. - Do đặc thù của trƣờng quân đội, giảng Giải thuật di truyền giải bài toán lập kế hoạch học tập 17 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 viên thƣờng xuyên có lịch công tác đột xuất do nhiệm vụ nên trong tháng lập lịch cho tháng tiếp giảng viên phải đăng ký thời gian bận trong tháng tiếp. - Ràng buộc cứng là những ràng buộc bắt buộc kết quả phải thoả mã các ràng Giải thuật di truyền giải bài toán lập kế hoạch học tập 18 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 buộc đó. - Giải thuật di truyền giải bài toán lập kế hoạch học tập 19 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 1.4. - Giải thuật di truyền giải bài toán lập kế hoạch học tập 20 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 H(n,g. - với mọi l Tối thiểu thời gian trống của giảng viên: Giải thuật di truyền giải bài toán lập kế hoạch học tập 21 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 - Fit2 = Min ( với mọi g Tối thiểu số phòng sử dụng - Fit3 = Min ( với mọi n 1.4.5. - Giải thuật di truyền giải bài toán lập kế hoạch học tập 22 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 CHƢƠNG 2. - GIẢI THUẬT DI TRUYỀN 2.1. - Tham số của giải thuật di truyền. - Ứng dụng của giải thuật di truyền. - Giải thuật di truyền giải bài toán lập kế hoạch học tập 23 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 lại sẽ bị đào thải. - Ví dụ: Bài toán ngƣời du lịch. - Các giá trị có thể là các thông tin Giải thuật di truyền giải bài toán lập kế hoạch học tập 25 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 liên quan đến bài toán, từ số nguyên, số thực, kí tự cho đến các đối tƣợng phức tạp hơn. - Trong giải thuật di truyền ta quan niệm quần thể là một tập các lời giải của một bài toán. - Dựa vào giá trị hàm thích nghi của Giải thuật di truyền giải bài toán lập kế hoạch học tập 26 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 mỗi cá thể, giải thuật di truyền mới có thể chọn lựa đƣợc các cá thể tốt cho các thế hệ sau. - Xác xuất của mỗi NST theo kiểu lựa chọn Roulet Giải thuật di truyền giải bài toán lập kế hoạch học tập 27 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 Cơ chế lựa chọn theo bánh xe Roulet đƣợc thực hiện bằng cách quay bánh xe Roulet N lần. - Giải thuật di truyền giải bài toán lập kế hoạch học tập 28 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 (a) Trạng thái quần thể trƣớc khi (b) Trạng thái quần thể sau sắp xếp khi sắp xếp Theo phƣơng pháp này việc một NST đƣợc chọn nhiều lần nhƣ trong lựa chọn theo kiểu bánh xe Roulet đã giảm đi. - Điểm cắt là một gen vị trí ngẫu nhiên k trên NST Hình 2: Lựa chọn xếp hạng Giải thuật di truyền giải bài toán lập kế hoạch học tập 29 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 - Cá thể con có phần đầu đến gen thứ k giống hệt mẹ, phần còn lại giống hệt cha. - Giải thuật di truyền giải bài toán lập kế hoạch học tập 30 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 Hình 5: Lai ghép đồng nhất mã hóa nhị phân Cụ thể hơn ta có bảng sau: Hình 6. - Giải thuật di truyền giải bài toán lập kế hoạch học tập 31 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 Hình 8. - Phép đảo bit mã hóa nhị phân 2.1.2.6.2 Đột biến theo mã hóa hoán vị Hoán đổi thứ tự: Thứ tự các gen đƣợc hoán đổi đƣợc lựa chọn ngẫu nhiên Giải thuật di truyền giải bài toán lập kế hoạch học tập 32 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 Hình 10. - Giải thuật di truyền giải bài toán lập kế hoạch học tập 33 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 Thế hệ n-1: p cá thểThế hệ n: p cá thểThế hệ con: p cá thểLai ghépNạp lại hoàn toàn Hình 12. - Chiến lược nạp lại theo mô hình cá thể ưu tú Tạo ra số NST mới ít hơn kích thƣớc quần thể và thay thế chúng cho các bố mẹ có độ thích nghi thấp: Giải thuật di truyền giải bài toán lập kế hoạch học tập 34 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 Thế hệ n-1: p cá thểThế hệ con: m cá thểLai ghépNạp m con Hình 14. - Mô hình giải thuật BeginKhởi tạo quần thể ban đầuTính độ thích nghi của các cá thể trong quần thểThoả mãn điều kiện dừng?- Lựa chọn cá thểChọn lời giải tốt nhất từ cá thể có độ thích nghi cao nhấtEndĐúngSaiLai ghépĐột biến Giải thuật di truyền giải bài toán lập kế hoạch học tập 35 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 Hình 15. - Mô hình giải thuật 2.1.2.9. - ỨNG DỤNG GIẢI THUẬT DI TRUYỀN Để ứng dụng giải thuật di truyền vào việc giải quyết một bài toán nào đó cần phải thực hiện một số công việc quan trọng sau: Giải thuật di truyền giải bài toán lập kế hoạch học tập 36 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 1. - Giải thuật di truyền giải bài toán lập kế hoạch học tập 37 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 O(f(n. - Một số bài toán quyết định. - Bởi vậy Cook, Karp, và một số nhà khoa học khác định nghia ra lớp bài Giải thuật di truyền giải bài toán lập kế hoạch học tập 38 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 toán NP-khó, mà phần lớn mọi nguời đều tin rằng chúng không thể đƣợc giải quyết trong thời gian đa thức. - Giải thuật di truyền giải bài toán lập kế hoạch học tập 39 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 - P: là lớp bài toán quyết định có thể đƣợc giải quyết trong thời gian đa thức. - Giải thuật di truyền giải bài toán lập kế hoạch học tập 40 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 Hình 17: Các lớp bài toán P, NP và co-NP 2.4.2.2. - Giải thuật di truyền giải bài toán lập kế hoạch học tập 41 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 Hình 18: Phân lớp tạm thời các bài toán Bài toán ―Hỗ trợ xếp thời khóa biểu‖ thuộc vào lớp NP-khó, vì vậy không thể giải nó một cách chính xác khi kích thuớc dữ liệu đầu vào lớn. - Giải thuật di truyền giải bài toán lập kế hoạch học tập 42 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 CHƢƠNG 3. - Tham số của giải thuật. - Giải thuật di truyền giải bài toán lập kế hoạch học tập 43 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 - Schedule: Là đối tƣợng cá thể, thể hiện cho một phƣơng án lập lịch. - Giải thuật di truyền giải bài toán lập kế hoạch học tập 44 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 CrossoverProbability = crossoverProbability. - Giải thuật di truyền giải bài toán lập kế hoạch học tập 45 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 int nr = GA.Config.Instance.GetNumberOfRooms. - Giải thuật di truyền giải bài toán lập kế hoạch học tập 46 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 } Bảng 8. - Giải thuật di truyền giải bài toán lập kế hoạch học tập 47 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 void RoomOverlap. - Giải thuật di truyền giải bài toán lập kế hoạch học tập 48 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2. - Giải thuật di truyền giải bài toán lập kế hoạch học tập 50 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 int room = rand.Next. - Giải thuật di truyền giải bài toán lập kế hoạch học tập 51 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 break. - Giải thuật di truyền giải bài toán lập kế hoạch học tập 52 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 } Bảng 17. - Giải thuật di truyền giải bài toán lập kế hoạch học tập 53 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 int daySize = GA.Config.DAY_HOURS * numberOfRooms. - Giải thuật di truyền giải bài toán lập kế hoạch học tập 54 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 CHƢƠNG 4. - Giải thuật di truyền giải bài toán lập kế hoạch học tập 55 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 - Dữ liệu phi cấu trúc (dạng văn bản, ảnh. - Mặc dù vậy, để thuận tiện Giải thuật di truyền giải bài toán lập kế hoạch học tập 56 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 hơn trong việc quản lý, sẽ thực hiện phân cấp CSDL theo nhóm sử dụng. - Đây là phƣơng pháp tiết kiệm thiết bị lƣu trữ và thời gian nhất nhƣng khi phục hồi dữ liệu Giải thuật di truyền giải bài toán lập kế hoạch học tập 57 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 phức tạp và tốn thời gian nhất. - Giải thuật di truyền giải bài toán lập kế hoạch học tập 58 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 - Thiết bị mạng: Dùng để kết nối mạng. - Giải thuật di truyền giải bài toán lập kế hoạch học tập 59 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 ApplicationApplicationPhần mềmứng dụngClientServerApplicationApplicationPhần mềmứng dụngClientApplicationApplicationPhần mềmứng dụngClientDatabase Hình 21. - Giải thuật di truyền giải bài toán lập kế hoạch học tập 60 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 Các module quản lý, cập nhậtCác module quản trịCác module nghiệp vụCác module tổng hợpCác module khácDatabaseLớp ứng dụngLớp dữ liệuUser-definedAssembliesLớp thư viện (trung gian)Data ProviderNetwork Assemblies Hình 22. - Code Nvarchar(50) Phiên hiệu đơn vị Giải thuật di truyền giải bài toán lập kế hoạch học tập 61 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 TT Tên Kiểu dữ liệu Mô tả 5. - Cấu trúc bảng dữ liệu nhƣ sau: Giải thuật di truyền giải bài toán lập kế hoạch học tập 62 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 TT Tên Kiểu dữ liệu Mô tả 1. - UserName Varchar(30) Khóa chính, Tên tài khoản Giải thuật di truyền giải bài toán lập kế hoạch học tập 63 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 TT Tên Kiểu dữ liệu Mô tả 2. - Cấu trúc bảng dữ liệu nhƣ sau: Giải thuật di truyền giải bài toán lập kế hoạch học tập 64 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 TT Tên Kiểu dữ liệu Mô tả 1. - ID Int (Autonumber) Khoá chính Giải thuật di truyền giải bài toán lập kế hoạch học tập 65 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 TT Tên Kiểu dữ liệu Mô tả 2. - STT Int Số thứ tự của đề mục Giải thuật di truyền giải bài toán lập kế hoạch học tập 66 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 Bảng 29. - Cấu trúc bảng dữ liệu nhƣ sau: TT Tên Kiểu dữ liệu Mô tả Giải thuật di truyền giải bài toán lập kế hoạch học tập 67 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 TT Tên Kiểu dữ liệu Mô tả 1. - Kịch bản 1: Bộ dữ liệu đơn giản gồm các thông số sau: Nội dung Số lƣợng Giảng viên 13 Môn học 8 Lớp học 4 Phòng học 5 Giải thuật di truyền giải bài toán lập kế hoạch học tập 68 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 Số cặp tiết phải xếp (CourseClass) 26 Bảng 33. - Kết quả thử nghiệm với bộ dữ liệu theo kịch bản 1: Số thế hệ Giá trị hàm mục tiêu Thời gian (phút Giải thuật di truyền giải bài toán lập kế hoạch học tập 69 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 Bảng 36. - Giao diện quản lý danh mục Giải thuật di truyền giải bài toán lập kế hoạch học tập 70 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 Hình 25. - Giao diện dữ liệu chuẩn bị trước khi giải thuật thực hiện Giải thuật di truyền giải bài toán lập kế hoạch học tập 71 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 Hình 27. - Giao diện cập nhật chương trình đào tạo Giải thuật di truyền giải bài toán lập kế hoạch học tập 72 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 Hình 29. - Thiết lập lớp thuộc chương trình đào tạo Giải thuật di truyền giải bài toán lập kế hoạch học tập 73 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 Hình 30. - Giải thuật di truyền giải bài toán lập kế hoạch học tập 75 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 CHƢƠNG 5. - Xây dựng giải thuật di truyền giải bài toán lập kế hoạch học tập cho trƣờng Sĩ quan Tăng Thiết giáp. - Giải thuật di truyền giải bài toán lập kế hoạch học tập 76 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 5.3. - Giải thuật di truyền giải bài toán lập kế hoạch học tập 77 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 TÀI LIỆU THAM KHẢO [1]. - Giải thuật di truyền giải bài toán lập kế hoạch học tập 78 Học viên thực hiện: Đỗ Ngọc Phục - CB120105 - 12BCNTT2 [11]
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt