Tài liệu Giải thuật di truyền và ứng dụng vào bài toán lập thời khóa biểu

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CNTT VÀ TRUYỀN THÔNG NGUYỄN THỊ HỒNG GIẢI THUẬT DI TRUYỀN VÀ ỨNG DỤNG VÀO BÀI TOÁN LẬP THỜI KHÓA BIỂU LUẬN VĂN THẠC SỸ KHOA HỌC MÁY TÍNH Thái Nguyên – 2013 Số hóa bởi Trung tâm Học liệu 1 http://lrc.tnu.edu.vn MỤC LỤC DANH MỤC CÁC KÝ HIỆU, CÁC TỪ VIẾT TẮT .................................................4 DANH MỤC CÁC BẢNG..........................................................................................5 DANH MỤC CÁC HÌNH ...........................................................................................6 LỜI MỞ ĐẦU .............................................................................................................7 CHƢƠNG 1. GIẢI THUẬT DI TRUYỀN TRONG KHAI PHÁ DỮ LIỆU ............9 1.1 Quá trình khai phá dữ liệu và giải thuật di truyền (GA) .......................................9 1.1.1 Quá trình khai phá dữ liệu .............................................................................9 1.1.2 Giải thuật di truyền .......................................................................................12 1.2 Các khái niệm cơ bản về GA ..............................................................................13 1.2.1 Nhiễm sắc thể ...............................................................................................13 1.2.2 Quần thể, thế hệ, toán tử di truyền, tiến hóa ................................................15 1.2.3 Hàm thích nghi .............................................................................................15 1.2.4 Chọn lọc........................................................................................................15 1.2.5 Lai ghép ........................................................................................................18 1.2.6 Đột biến ........................................................................................................20 1.2.7 Chiến lƣợc nạp lại quần thể ..........................................................................21 1.3 Mô hình GA ........................................................................................................23 1.4 Không gian tìm kiếm và điều kiện dừng của GA ...............................................24 1.4.1 Không gian tìm kiếm ....................................................................................24 1.4.2 Điều kiện dừng của GA ................................................................................25 1.5 Đặc điểm và ứng dụng của GA ...........................................................................25 1.5.1 Đặc điểm của GA .........................................................................................25 1.5.2 Ứng dụng của GA .........................................................................................26 CHƢƠNG 2. BÀI TOÁN THUỘC LỚP NP ..............................................................27 VÀ BÀI TOÁN LẬP THỜI KHÓA BIỂU .................................................................27 Số hóa bởi Trung tâm Học liệu 2 http://lrc.tnu.edu.vn 2.1 Lớp các bài toán NP ............................................................................................27 2.1.1 Một số khái niệm: .........................................................................................27 2.1.2 NP-khó và NP-đầy đủ...................................................................................27 2.1.3 Tối ƣu hóa đa mục tiêu .................................................................................28 2.2. Bài toán lập thời khóa biểu ................................................................................29 2.2.1 Một số khái niệm cơ sở ................................................................................33 2.2.2 Mô hình bài toán...........................................................................................34 CHƢƠNG 3. XÂY DỰNG BÀI TOÁN THỜI KHOÁ BIỂU DỰA TRÊN GIẢI THUẬT DI TRUYỀN ..............................................................................................37 3.1 Bài toán lập thời khóa biểu ở trƣờng Cao đẳng Công nghệ và Kinh tế Hà Nội .37 3.1.1 Giới thiệu ......................................................................................................37 3.1.2 Nội dung hoạt động nghiệp vụ .....................................................................37 3.2 Áp dụng giải thuật di truyền vào bài toán lập thời khóa biểu .............................38 3.2.1 Các toán tử di truyền đối với bài toán hỗ trợ xếp thời khóa biểu .................38 3.2.2 Thiết kế cơ sở dữ liệu ...................................................................................43 3.3. Cài đặt chƣơng trình ...........................................................................................50 3.4. Đánh giá kết quả thử nghiệm .............................................................................50 KẾT LUẬN ...............................................................................................................53 TÀI LIỆU THAM KHẢO .........................................................................................54 Số hóa bởi Trung tâm Học liệu 3 http://lrc.tnu.edu.vn DANH MỤC CÁC KÝ HIỆU, CÁC TỪ VIẾT TẮT 1 Từ Tiếng Anh viết tắt GA Genetic Algorithm giải thuật di truyền 2 EC Evolutionary computation tính toán tiến hóa 3 EP Evolutionary Programming quy hoạch tiến hóa 4 ES Evolutionary Strategies các chiến lƣợc tiến hóa 5 GP Genetic Programming lập trình di truyền 6 CS Classifier Systems các hệ thống phân loại 7 MOOP Multi-objective Optimization Problem Tối ƣu hóa đa mục tiêu 8 NST TT Nghĩa Tiếng Việt nhiễm sắc thể 9 Selection chọn lọc 10 Cross-over lai ghép 11 Mutation đột biến 12 Reproduction sinh sản 13 pop-size kích cỡ quần thể 14 NP-hard bài toán NP khó 15 NP-complete bài toán NP đầy đủ 16 Fitness độ thích nghi Số hóa bởi Trung tâm Học liệu 4 http://lrc.tnu.edu.vn DANH MỤC CÁC BẢNG Bảng1: Mã hóa nhị phân độ dài 20 bit ...........................................................13 Bảng2: Mã hóa hoán vị 2 NST A&B .............................................................14 Bảng3: Mã hóa giá trị các NST A, B, C ........................................................14 Bảng4: Mặt nạ lai ghép đồng nhất .................................................................19 Bảng 5: Lai ghép một điểm cắt mã hóa hoán vị ............................................20 Bảng 6: Phép đảo bit mã hóa nhị phân ..........................................................20 Bảng 7: Hoán vị thứ tự mã hóa hoán vị .........................................................21 Bảng 8: Thay đổi giá trị trong mã hóa giá trị .................................................21 Bảng 9: Bảng chỉ số .......................................................................................34 Bảng 10: Bảng kiểm tra ràng buộc về phòng .................................................40 Bảng 11: Bảng kiểm tra ràng buộc về giảng viên ..........................................40 Bảng 12: Bảng kiểm tra ràng buộc về lớp sinh viên ......................................41 Số hóa bởi Trung tâm Học liệu 5 http://lrc.tnu.edu.vn DANH MỤC CÁC HÌNH Hình 1: Xác suất của mỗi NST theo kiểu lựa chọn Roulet ............................16 Hình 2: Lựa chọn xếp hạng ............................................................................17 Hình 3: Lai ghép một điểm cắt mã hóa nhị phân ...........................................18 Hình 4: Lai ghép hai điểm cắt mã hóa nhị phân ..........................................18 Hình 5: Lai ghép đồng nhất mã hóa nhị phân ................................................19 Hình 6: Lai ghép số học mã hóa nhị phân .....................................................19 Hình 7: Chiến lƣợc nạp lại hoàn toàn ............................................................21 Hình 8: Chiến lƣợc nạp lại ngẫu nhiên ..........................................................22 Hình 9: Chiến lƣợc nạp lại theo mô hình cá thể ƣu tú ...................................22 Hình 10: Sơ đồ mô tả GA ..............................................................................23 Hình 11: Phân lớp tạm thời các bài toán ........................................................28 Hình 12: Ma trận cá thể..................................................................................39 Hình 13: Lai ghép 1 điểm cắt .........................................................................42 Hình 14: Sơ đồ giải thuật di truyền đề xuất ...................................................43 Hình 15: Nhập danh mục quản lý hình thức bài học .....................................46 Hình 16: Quản lý danh mục loại phòng học ..................................................46 Hình 17: Quản lý danh mục lớp học ..............................................................47 Hình 18: Quản lý danh mục môn học ............................................................47 Hình 19: Quản lý danh mục phòng học .........................................................48 Hình 20: Quản lý danh mục tòa nhà ..............................................................48 Hình 21: Quản lý chƣơng trình đào tạo .........................................................49 Hình 22: Cập nhật chƣơng trình đào tạo khung .............................................49 Hình 23: Cửa sổ xếp Thời khóa biểu .............................................................50 Số hóa bởi Trung tâm Học liệu 6 http://lrc.tnu.edu.vn LỜI MỞ ĐẦU Hiện nay trong ngành khoa học máy tính, việc tìm kiếm lời giải tối ƣu cho các bài toán là vấn đề luôn đƣợc các nhà khoa học đặc biệt quan tâm. Mục đích chính của các thuật toán tìm kiếm lời giải là tìm ra lời giải tối ƣu cho bài toán trong thời gian nhỏ nhất. Các thuật toán nhƣ tìm kiếm không có thông tin, vét cạn (tìm kiếm trên danh sách, trên cây hoặc đồ thị ) hoặc các thuật toán tìm kiếm có thông tin đƣợc sử dụng nhiều trong không gian tìm kiếm nhỏ. Đối với không gian tìm kiếm lớn, việc tìm kiếm các lời giải tối ƣu cho bài toán gặp nhiều khó khăn. Do đó, cần thiết phải có những thuật giải tốt và sử dụng kỹ thuật trí tuệ nhân tạo khi giải quyết các bài toán có không gian tìm kiếm lớn. Thuật giải di truyền (Genetic Algorithm GA) là một trong những kỹ thuật tìm kiếm lời giải tối ƣu đã đáp ứng đƣợc yêu cầu của nhiều bài toán và ứng dụng. Cùng với logic mờ, GA đƣợc ứng dụng rất rộng rãi trong các lĩnh vực phức tạp. Sự kết hợp giữa GA và logic mờ đã chứng tỏ đƣợc hiệu quả trong các vấn đề khó mà trƣớc đây thƣờng đƣợc giải quyết bằng các phƣơng pháp thông thƣờng hay các phƣơng pháp cổ điển, nhất là trong các bài toán cần có sự lƣợng giá, đánh giá sự tối ƣu của kết quả thu đƣợc. Chính vì vậy, GA đã trở thành một trong những đề tài nghiên cứu thu hút đƣợc nhiều sự quan tâm và hiện nay đã và đang đem đến rất nhiều ứng dụng trong thực tiễn. Xuất phát từ thuyết tiến hóa muôn loài của Darwin, GA là một kỹ thuật chung giúp giải quyết vấn đề bài toán bằng cách mô phỏng sự tiến hóa của con ngƣời hay của sinh vật nói chung trong những điều kiện đƣợc qui định sẵn của môi trƣờng. GA là một thuật giải và mục tiêu của GA không nhằm đƣa ra lời giải chính xác tối ƣu mà là đƣa ra lời giải tƣơng đối tối ƣu. John Holland (1975) và Goldberg (1989) đã đề xuất và phát triển GA, là thuật giải tìm kiếm dựa trên cơ chế chọn lọc và di truyền tự nhiên. Thuật giải này sử dụng các nguyên lý di truyền về sự thích nghi và sự sống các cá thể thích nghi nhất trong tự nhiên. Do tính hấp dẫn và tính thời sự của khai phá dữ liệu, đặc biệt là giải thuật di truyền, tôi đã chọn đề tài “Giải thuật di truyền và ứng dụng vào bài toán lập thời Số hóa bởi Trung tâm Học liệu 7 http://lrc.tnu.edu.vn khóa biểu” làm luận văn cao học của mình. Trong đó tập trung nghiên cứu các kỹ thuật lập lịch và chọn ra một kỹ thuật tiêu biểu đề thực hiện bài toán thời khóa biểu phục vụ công tác giảng dạy của trƣờng, nơi tôi đang công tác. Số hóa bởi Trung tâm Học liệu 8 http://lrc.tnu.edu.vn Chương 1. GIẢI THUẬT DI TRUYỀN TRONG KHAI PHÁ DỮ LIỆU 1.1 Quá trình khai phá dữ liệu và giải thuật di truyền (GA) 1.1.1 Quá trình khai phá dữ liệu Theo Bách khoa toàn thƣ Việt Nam, tri thức là “kết quả của quá trình nhận thức của con người về đối tượng được nhận thức, làm tái hiện trong tư tưởng của con người những thuộc tính, những mối quan hệ, những quy luật vận động, phát triển của đối tượng và diễn đạt bằng ngôn ngữ tự nhiên hay hệ thống ký hiệu khác”. Phát hiện tri thức là một quá trình bao gồm một dãy các bƣớc lặp sau: 1. Làm sạch dữ liệu 2. Tích hợp dữ liệu 3. Chọn lựa dữ liệu 4. Chuyển đổi dữ liệu 5. Khai phá dữ liệu 6. Đánh giá các mẫu 7. Trình diễn tri thức Trong đó, khai phá dữ liệu là bƣớc quan trọng nhất trong tiến trình phát hiện tri thức. Dữ liệu là những mô tả về sự vật, con ngƣời và sự kiện trong thế giới thực. Dữ liệu bao gồm số, ký tự, văn bản, hình ảnh, đồ họa,…có một giá trị nào đó đối với ngƣời sử dụng và chúng đƣợc lƣu trữ, xử lý trong máy tính. Theo liệu bách khoa toàn thƣ, “khai phá dữ liệu ” là khâu chủ yếu trong quá trình phát hiện tri thức từ dữ liệu để trợ giúp cho việc làm quyết định trong quản lý. Số hóa bởi Trung tâm Học liệu 9 http://lrc.tnu.edu.vn Khai phá dữ liệu (Data Mining-DM) là một khái niệm ra đời vào những năm cuối của thập kỷ 80. Nó bao hàm một loạt các kỹ thuật nhằm phát hiện ra các thông tin có giá trị tiềm ẩn trong các tập dữ liệu lớn (các kho dữ liệu). Về bản chất, khai phá dữ liệu liên quan đến việc phân tích các dữ liệu và sử dụng các kỹ thuật để tìm ra các mẫu hình có tính chính quy (regularities) trong tập dữ liệu. Năm 1989, Fayyad, Piatestsky-Shapiro và Smyth đã dùng khái niệm Phát hiện tri thức trong cơ sở dữ liệu (Knowledge Discovery in Database – KDD) để chỉ toàn bộ quá trình phát hiện các tri thức có ích từ các tập dữ liệu lớn. Trong đó, khai phá dữ liệu là một bƣớc đặc biệt trong toàn bộ quá trình, sử dụng các giải thuật đặc biệt để chiết xuất ra các mẫu (pattern) (hay các mô hình) từ dữ liệu. Có nhiều kỹ thuật khác nhau đƣợc sử dụng để khai phá dữ liệu nhằm thực hiện hai chức năng mô tả và dự đoán. Với mỗi chức năng thì có các kỹ thuật DM tƣơng ứng với nó. Không có kỹ thuật nào tốt để áp dụng chung cho mọi trƣờng hợp. Kỹ thuật khai phá dữ liệu mô tả có nhiệm vụ mô tả các tính chất hoặc các đặc tính chung của dữ liệu trong CSDL hiện có. Một số kỹ thuật khai phá trong nhóm này là: phân cụm dữ liệu, tổng hợp, trực quan hoá, phân tích sự phát triển và độ lệch,… Kỹ thuật khai phá dữ liệu dự đoán có nhiệm vụ đƣa ra các dự đoán dựa vào việc suy diễn trên CSDL hiện thời. Một số kỹ thuật khai phá trong nhóm này là: phân lớp, hồi quy, cây quyết định, thống kê, mạng nơron, luật kết hợp,…. Một số kỹ thuật phổ biến thƣờng đƣợc sử dụng để khai phá dữ liệu hiện nay bao gồm: 1.Cây quyết định Kỹ thuật cây quyết định là một công cụ mạnh và hiệu quả trong việc phân lớp và dự báo. Các đối tƣợng dữ liệu đƣợc phân thành các lớp. Các giá trị của đối tƣợng Số hóa bởi Trung tâm Học liệu 10 http://lrc.tnu.edu.vn dữ liệu chƣa biết sẽ đƣợc dự đoán, dự báo. Tri thức đƣợc rút ra trong kỹ thuật này thƣờng đƣợc mô tả dƣới dạng tƣờng minh, đơn giản, trực quan, dễ hiểu đối với NSD. 2.Phân lớp dữ liệu và hồi quy Mục tiêu của phân lớp dữ liệu là dự đoán nhãn lớp cho các mẫu dữ liệu. Quá trình gồm hai bƣớc: xây dựng mô hình, sử dụng mô hình để phân lớp dữ liệu. Mô hình đƣợc sử dụng để dự đoán nhãn lớp khi mà độ chính xác của mô hình chấp nhận đƣợc. Phƣơng pháp hồi quy tƣơng tự nhƣ phân lớp dữ liệu. Nhƣng khác ở chỗ nó dùng để dự đoán các giá trị liên tục còn phân lớp dữ liệu dùng để dự đoán các giá trị rời rạc. 3.Phân cụm dữ liệu Mục tiêu của phân cụm dữ liệu là nhóm các đối tƣợng tƣơng tự nhau trong tập dữ liệu vào các cụm, sao cho những đối tƣợng thuộc cùng một lớp là tƣơng đồng nhau. 4.Khai phá luật kết hợp Mục tiêu của phƣơng pháp này là phát hiện và đƣa ra mối liên hệ giữa các giá trị dữ liệu trong CSDL. Đầu ra của giải thuật luật kết hợp là tập luật kết hợp tìm đƣợc. Phƣơng pháp khai phá luật kết hợp gồm có hai bƣớc: Bƣớc 1: Tìm ra tất cả các tập mục phổ biến. Một tập mục phổ biến đƣợc xác định thông qua việc tính độ hỗ trợ và thoả mãn độ hỗ trợ cực tiểu. Bƣớc 2: Sinh ra các luật kết hợp mạnh từ tập mục phổ biến, luật phải thoả mãn độ hỗ trợ và độ tin cậy cực tiểu. 5. Mạng nơron Đây là một trong những kỹ thuật DM đƣợc ứng dụng phổ biến hiện nay. Số hóa bởi Trung tâm Học liệu 11 http://lrc.tnu.edu.vn Kỹ thuật này phát triển dựa trên một nền tảng toán học vững vàng, khả năng huấn luyện trong kỹ thuật này dựa trên mô hình thần kinh trung ƣơng của con ngƣời. Kết quả mà mạng nơron học đƣợc có khả năng tạo ra các mô hình dự báo, dự đoán với độ chính xác và độ tin cậy cao. Nó có khả năng phát hiện ra đƣợc các xu hƣớng phức tạp mà kỹ thuật thông thƣờng khác khó có thể phát hiện ra đƣợc. Tuy nhiên phƣơng pháp mạng nơ ron rất phức tạp và quá trình tiến hành nó gặp rất nhiều khó khăn: đòi hỏi mất nhiều thời gian, nhiều dữ liệu, nhiều lần kiểm tra thử nghiệm. 6.Giải thuật di truyền Giải thuật di truyền là quá trình mô phỏng theo tiến hoá của tự nhiên. Ý tƣởng chính của giải thuật là dựa vào quy luật di truyền trong biến đổi, chọn lọc tự nhiên và tiến hoá trong sinh học. Giải thuật di truyền tuy không phải là kỹ thuật khai phá dữ liệu đƣợc triển khai mạnh nhất trong kinh tế - xã hội, nhƣng nó có những lợi thế riêng, đặc biệt là trong ứng dụng trong ngành giáo dục với các bài toán lập lịch nhƣ sắp xếp thời khóa biểu. Đây cũng là lý do mà đề tài tập trung nghiên cứu vào đó. 1.1.2 Giải thuật di truyền Lịch sử phát triển giải thuật di truyền: Tính toán tiến hóa (Evolutionary computing) là các kỹ thuật tìm kiếm theo xác suất có ý tƣởng xuất phát từ nguyên lý “chọn lọc tự nhiên” trong học thuyết về sự tiến hóa của Darwin, và các kỹ thuật về gen. Các kỹ thuật này đƣợc áp dụng cho một quần thể bao gồm các cá thể nhân tạo, chúng chiến đấu trong cuộc đấu tranh sinh tồn trong đó các cá thể thích nghi nhất sẽ sống sót và cho phép sản sinh ra các cá thể mới. Giải thuật di truyền (Genetic Algorithm) do John Holland phát minh và đƣợc ông phát triển cùng với các đồng nghiệp và sinh viên vào những năm 1970. Cuốn sách " Sự thích nghi trong các hệ tự nhiên và nhân tạo” (Adaption in Natural and Số hóa bởi Trung tâm Học liệu 12 http://lrc.tnu.edu.vn Artificial Systems) xuất bản năm 1975 đã tổng hợp các kết quả của quá trình nghiên cứu và phát triển đó. Năm 1992, John Koza đã dùng GA để xây dựng các chƣơng trình giải quyết một số bài toán và gọi phƣơng pháp này là "Lập trình di truyền" (Genetic Programming). Năm 1996, thƣ viện các hàm C++ cho GA (GALib) đã đƣợc Mathew Wall, trƣờng Đại học Massachussets (Massachusetts Institute of Technology) đƣa ra.Đây là các công cụ sử dụng giải thuật di truyền cho tối ƣu hoá các chƣơng trình có sử dụng sự biểu diễn hay các toán tử di truyền. 1.2 Các khái niệm cơ bản về GA 1.2.1 Nhiễm sắc thể Nhiễm sắc thể (NST) hay còn gọi là cá thể. Các sinh vật sống đều cấu tạo từ các tế bào, và tất cả các tế bào này đều bao gồm một tập hợp các nhiếm sắc thể giống nhau. Các NST này là một chuỗi các ADN, quy định đặc tính của cả cá thể. Mỗi NST bao gồm rất nhiều GEN, mỗi gen quy định một trạng thái nào đó. Trong bài toán tối ƣu, cá thể tƣơng ứng với một lời giải tiềm tàng. Việc mã hóa và giải mã gen, biến đổi giữa kiểu gen và kiểu hình đƣợc quyết định bởi tính chất của bài toán. Nhƣng thông thƣờng có một số phƣơng pháp mã hóa NST thƣờng gặp sau: 1.2.1.1 Mã hóa nhị phân Đây là cách mã hóa nhị phân phổ biến nhất.Mỗi một nhiễm sắc thể là một chuỗi bit nhị phân 0 & 1. Mỗi một bit có thể biểu diễn một đặc tính nào đó của lời giải, và số bit cần để mã hóa đƣợc tính toán hợp lý để chuỗi nhị phân không quá dài, mà chỉ vừa đủ cho biểu diễn thông tin cần thiết cho lời giải. Chronosome A Chronosome B 00110101000010111010 10111100110010001011 Bảng1: Mã hóa nhị phân độ dài 20 bit Số hóa bởi Trung tâm Học liệu 13 http://lrc.tnu.edu.vn Mã hoá nhị phân thƣờng hay dùng trong các bài toán tối ƣu các hàm một biến hay nhiều biến. Khi đó, mỗi chuỗi nhị phân sẽ biểu diễn hàm tại một (tập) giá trị của (các) biến hoặc mỗi bộ chuỗi nhị phân sẽ biểu diễn một bộ nghiệm của hàm. Mã hoá nhị phân tuy là phổ biến nhƣng nó có một nhƣợc điểm là có thể tạo ra không gian mã hoá lớn hơn so với không gian giá trị của NST. Do đó, với nhiều bài toán thì biểu diễn nhị phân là không hữu hiệu. 1.2.1.2 Mã hóa hoán vị Mỗi NST là một chuỗi hoán vị của các số (thƣờng là số tự nhiên) để biểu diễn một trình tự nào đó. Chronosome A Chronosome B 479321865 965143278 Bảng2: Mã hóa hoán vị 2 NST A&B Mã hoá hoán vị phù hợp cho các bài toán liên quan đến thứ tự. Đối với các bài toán này, việc thao tác trên các nhiễm sắc thể chính là hoán vị các số trong chuỗi đó làm thay đổi trình tự của nó. Mã hóa hoán vị rất hữu ích với các bài toán sắp xếp. 1.2.1.3 Mã hóa giá trị Mã hóa giá trị trực tiếp có thể đƣợc sử dụng trong các bài toán mà giá trị của nó là các giá trị phức tạp nhất là số thực. Sử dụng mã hóa nhị phân sẽ trở nên khó khăn. Trong đó, mỗi NST là một chuỗi các giá trị. Các giá trị có thể là các thông tin 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. Chronosome A Chronosome B Chronosome C 1.4765 6.2324 3.8653 9.2134 ABDJEIFJDHDIERJFDLDFLFEGT (black) (black) (blue) (red) (white) Bảng3: Mã hóa giá trị các NST A, B, C Mã hoá theo giá trị thƣờng dùng cho các bài toán đặc biệt. Trong cách mã hoá này ta thƣờng phải phát triển các toán tử đột biến và lai ghép cho phù hợp với từng bài toán. Số hóa bởi Trung tâm Học liệu 14 http://lrc.tnu.edu.vn 1.2.2 Quần thể, thế hệ, toán tử di truyền, tiến hóa Quần thể (population) trong tự nhiên là một tập hợp các cá thể có cùng một số đặc điểm nào đấy. 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 tiềm tàng của một bài toán. Khái niệm thế hệ (generation) gắn chặt với khái niệm quần thể. Mỗi thế hệ đƣợc xác định bởi một quần thể chƣa tham gia vào quá trình tiến hóa tiếp theo. Các toán tử di truyền (GA operator) là các toán tử thao tác đối với các cá thể nhằm tạo ra các cá thể mới. Quá trình tiến hóa (evolution) là việc áp dụng các toán tử di truyền đối với các cá thể, chuyển quần thể từ thế hệ này sang thế hệ tiếp theo, với một bộ phận cá thể hoặc toàn bộ quần thể đã đƣợc biến đổi. 1.2.3 Hàm thích nghi Trong tự nhiên, chỉ có những cá thể nào thích nghi đƣợc với môi trƣờng thì mới tồn tại, không nó sẽ bị diệt vong. GA đƣa ra khái niệm hàm thích nghi, hay hàm sức khỏe để đánh giá một cá thể so với quần thể. Dựa vào giá trị hàm thích nghi của mỗi cá thể, thuật toán di truyền mới có thể chọn lựa đƣợc các cá thể tốt cho các thế hệ sau. Hàm thích nghi cũng là một tiêu chí đánh giá mức độ tiến hóa của quần thể. 1.2.4 Chọn lọc Dựa vào nguyên lý của quá trình chọn lọc và đấu tranh sinh tồn trong tự nhiên, chọn lựa các cá thể trong GA chính là cách chọn các cá thể có độ thích nghi tốt để đƣa vào thế hệ tiếp theo hoặc để cho lai ghép, với mục đích là sinh ra các cá thể mới tốt hơn. Tuy nhiên, quá trình chọn lọc mang rất nhiều yếu tố ngẫu nhiên. Có nhiều cách để lựa chọn nhƣng cuối cùng đều nhằm đáp ứng mục tiêu là các cá thể tốt sẽ có khả năng đƣợc chọn cao hơn. Có nhiều cách để lựa chọn các cá thể từ một quần thể. Sau đây sẽ giới thiệu một số cơ chế hay áp dụng. Để tiện mô tả các cơ chế lựa chọn luận văn đƣa ra một số kí hiệu sau: Số hóa bởi Trung tâm Học liệu 15 http://lrc.tnu.edu.vn - Cách biểu diễn các NST thứ i là vi . - Hàm tính độ thích nghi của NST vi là f(vi ). - Kích thƣớc quần thể là pop_size. - Số NST cần chọn là N. 1.2.4.1 Lựa chọn theo bánh xe Roulet Trƣớc khi lựa chọn thì tính các giá trị sau: - Tính tổng độ thích nghi của cả quần thể: F = i) - Tính xác suất chọn pi cho mỗi NST vi : pi = f(vi) / F - Tính vị trí xác suất qi của mỗi NST: qi = j Hình 1: Xác suất của mỗi NST theo kiểu lựa chọn Roulet 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. Mỗi lần chọn một NST từ quần thể hiện hành vào quần thể mới bằng cách sau: - Phát sinh ngẫu nhiên một số r trong khoảng [0, 1]. - Nếu r < q1 thì chọn NST v1; ngƣợc lại thì chọn NST thứ i (2 ≤ i ≤pop_size) sao cho qi-1≤ r ≤ qi. Với cơ chế lựa chọn nhƣ thế này thì có một số nhiễm sắc thể sẽ đƣợc chọn nhiều lần. Điều này phù hợp với lý thuyết lƣợc đồ: Các NST tốt nhất thì có nhiều bản sao, NST trung bình thì không đổi, NST kém thì chết đi. Hoặc lựa chọn kiểu bánh xe Roulet có thể mô tả theo thuật toán sau: Số hóa bởi Trung tâm Học liệu 16 http://lrc.tnu.edu.vn (1) [SUM] Tính tổng giá trị thích nghi S của tất cả các cá thể hay nhiễm sắc thể trong toàn quần thể. (2) [SELECT] sinh một số ngẫu nhiên trên đoạn (0...S) ta đƣợc r. (3) [LOOP] duyệt lại toàn bộ quần thể, tính tổng hàm thích nghi từ 0, ta gọi là s. Khi nào s > r thì ta dừng lại với nhiễm sắc thể hiện tại. 1.2.4.2 Lựa chọn xếp hạng Theo cơ chế lựa chọn trên khi sự khác biệt giữa các hàm thích nghi lớn,các NST có độ thích nghi kém sẽ rất ít có cơ hội đƣợc lựa chọn, nhất là khi có các NST tốt có độ thích nghi trên 90%. Cơ chế lựa chọn xếp hạng đƣợc mô tả nhƣ sau: - Sắp xếp các NST trong quần thể theo độ thích nghi từ thấp đến cao. - Đặt lại độ thích nghi cho quần thể đã sắp xếp theo kiểu: NST thứ nhất có độ thích nghi là 1, nhiễm săc thể thứ hai có độ thích nghi là 2, v.v…, NST thứ pop_size có độ thích nghi là pop_size. (a) Trạng thái quần thể trƣớc khi sắp xếp (b) Trạng thái quần thể sau khi sắp xếp Hình 2: Lựa chọn xếp hạng 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. Nhƣng nó có thể dẫn đến sự hội tụ chậm và NST có độ thích nghi cao cũng không khác mấy so với các NST khác. 1.2.4.3 Lựa chọn trận đấu Hay còn đƣợc gọi là lựa chọn theo trạng thái ổn định. Cơ chế lựa chọn: Số hóa bởi Trung tâm Học liệu 17 http://lrc.tnu.edu.vn - Lấy một số NST trong quần thể ra để chọn, NST có độ thích nghi cao nhất đƣợc chọn. - Lặp lại thao tác trên N lần 1.2.5 Lai ghép Lai ghép trong tự nhiên là sự kết hợp các tính trạng của bố mẹ để sinh ra thế hệ con. Trong giải thuật di truyền, lai ghép đƣợc coi là một sự tổ hợp lại các tính chất (thành phần) trong hai hoặc nhiều cá thể cha mẹ nào đó để sinh ra một cá thể mới mà có đặc tính mong muốn là tốt hơn cá thể cha mẹ. Đây là một quá trình xảy ra chủ yếu trong giải thuật di truyền. Tùy theo cách mã hóa NST mà có các những cách lai ghép khác nhau: 1.2.5.1 Lai ghép theo mã hóa nhị phân - Lai ghép một điểm cắt (One Points Crossover) + Điểm cắt là một gen vị trí ngẫu nhiên k trên NST + Cá thể con có phần đầu đến gen thứ k giống hệt cha, phần còn lại giống hệt mẹ. Hình 3: Lai ghép một điểm cắt mã hóa nhị phân - Lai ghép 2 điểm cắt + Hai điểm cắt sẽ đƣợc chọn ngẫu nhiên. Hình 4: Lai ghép hai điểm cắt mã hóa nhị phân - Lai ghép đồng nhất Số hóa bởi Trung tâm Học liệu 18 http://lrc.tnu.edu.vn + Chuỗi nhị phân của con sẽ đƣợc lai ghép ngẫu nhiên hoặc từ mẹ hoặc từ cha. Hay nói cách khác, ta sẽ xây dựng một mặt nạ lai ghép. Nó cũng là một chuỗi nhị phân các bit 0&1. + Duyệt mặt nạ: ở vị trí bit mặt nạ = 1 thì gen ở vị trí tƣơng ứng của mẹ đƣợc lai ghép cho con, nếu bit mặt nạ = 0 thì gen ở vị trí tƣơng ứng của cha đƣợc lai ghép cho con. Hình 5: Lai ghép đồng nhất mã hóa nhị phân Cụ thể hơn ta có bảng sau: Bảng4: Mặt nạ lai ghép đồng nhất - Lai ghép số học: Cá thể con đƣợc sinh ra bằng một phép toán logic nào đó (AND,OR,…) với cặp NST bố mẹ. Hình 6: Lai ghép số học mã hóa nhị phân 1.2.5.2 Lai ghép theo mã hóa hoán vị Lai ghép một điểm cắt: Số hóa bởi Trung tâm Học liệu 19 http://lrc.tnu.edu.vn - Vị trí cắt đƣợc chọn một cách ngẫu nhiên - Con mới đƣợc sinh ra sẽ có phần gen đầu cho đến vị trí cắt giống mẹ. - Duyệt NST cha từ đầu, gen nào chƣa có trong NST của con thì đƣa vào. Bảng 5: Lai ghép một điểm cắt mã hóa hoán vị 1.2.5.3 Lai ghép theo mã hóa giá trị Mã hoá theo giá trị có thể áp dụng tất cả các toán tử lai ghép có trong mã hoá nhị phân. 1.2.6 Đột biến Đột biến là một sự biến đổi tại một (hay một số) gen của cá thể ban đầu để tạo ra một cá thể mới. Đột biến có thể tạo ra một cá thể mới tốt hơn hoặc xấu hơn cá thể ban đầu. Tuy nhiên, trong giải thuật di truyền thì ta luôn muốn tạo ra những phép đột biến cho phép cải thiện lời giải qua từng thế hệ. Đột biến cũng mang tính chất ngẫu nhiên. Tƣơng tự lai ghép, mỗi cách mã hóa NST khác nhau sẽ có những phép đột biến khác nhau. 1.2.6.1 Đột biến theo mã hóa nhị phân Phép đảo bit: Bit đƣợc chọn sẽ đƣợc đảo. Bảng 6: Phép đảo bit mã hóa nhị phân 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 Số hóa bởi Trung tâm Học liệu 20 http://lrc.tnu.edu.vn