Tài liệu Tính toán tiến hoá và ứng dụng lập thời khoá biểu trường trung học phổ thông

ĐẠI HỌC QUỐC GIA HÀ NỘI KHOA CễNG NGHỆ TRẦN QUỐC HƯNG TÍNH TOÁN TIẾN HÓA VÀ ỨNG DỤNG LẬP THỜI KHÓA BIỂU TRƯỜNG TRUNG HỌC PHỔ THÔNG Chuyên ngành: CÔNG NGHỆ THÔNG TIN Mã số: 1.01.1 LUẬN VĂN THẠC SĨ Hà Nội – Năm 2004 ĐẠI HỌC QUỐC GIA HÀ NỘI KHOA CÔNG NGHỆ TRẦN QUỐC HƯNG TÍNH TOÁN TIẾN HÓA VÀ ỨNG DỤNG LẬP THỜI KHÓA BIỂU TRƯỜNG TRUNG HỌC PHỔ THÔNG Chuyên ngành: CÔNG NGHỆ THÔNG TIN Mã số: 1.01.1 LUẬN VĂN THẠC SĨ NGƯỜI HƯỚNG DẪN KHOA HỌC: Tiến Sĩ HOÀNG XUÂN HUẤN Hà Nội – Năm 2004 1 MỤC LỤC Mở đầu ......................................................................................................... 4 Cấu trúc của luận văn ..................................................................................... 6 Chƣơng I: Giải thuật di truyền và Tính toán tiến hóa .............................. 8 1.1. Giải thuật di truyền .............................................................................. 8 1.1.1. Lược sử ............................................................................................... 8 1.1.2. í tưởng ................................................................................................ 10 1.1.3. Đặc thù của GA cổ điển ...................................................................... 10 1.1.4. Cấu trúc của GA cổ điển ..................................................................... 11 1.1.4.1. Cấu trỳc nhiễm sắc thể và kiểu gene ................................................ 12 1.1.4.2. Thủ tục GA ...................................................................................... 13 1.1.4.3. Phương pháp mó húa và giải mó ...................................................... 15 1.1.4.4 Thủ tục chọn lọc (Selection) ............................................................. 17 1.1.4.5. Quỏ trỡnh tỏi tạo .............................................................................. 18 1.1.4.5.1. Cỏc toỏn tử di truyền .................................................................... 18 1.1.4.5.2. Quỏ trỡnh tỏi tạo ........................................................................... 20 1.1.4.6. Điều kiện kết thỳc ............................................................................ 20 1.1.5. Sự hội tụ của GA ................................................................................ 20 1.1.6. Biểu diễn bằng vector số thực ............................................................. 25 1.2. Tớnh toỏn tiến húa .............................................................................. 26 1.2.1 Các chiến lược tiến hóa (Evolution Strategies – ES) ............................ 28 1.2.1.1 Chiến lược tiến hóa hai thành viên .................................................... 28 1.2.1.2 Chiến lược tiến hóa đa thành viờn: ký hiệu ( +1) ES ...................... 30 1.2.1.3 Chiến lược tiến hóa đa thành viên cải tiến ........................................ 31 1.2.2 Lập trỡnh tiến húa (Evolutionary Programming EP) ......................... 32 1.2.2.1. í tưởng ............................................................................................. 32 Phương pháp Tính toán tiến hóa Và ỏp dụng lập Thời khúa biểu Trung học Phổ thụng 2 1.2.2.2. Biểu diễn nhiễm sắc thể ................................................................... 32 1.2.3 Lập trỡnh di truyền (Genetic Programming – GP) ............................... 34 1.2.3.1. í tưởng của GP ................................................................................. 34 1.2.3.2. Biểu diễn nhiễm sắc thể ................................................................... 34 1.2.4 Chương trỡnh tiến húa (Evolution Programmes – EPs) ....................... 36 1.2.4.1. í tưởng .............................................................................................. 36 1.2.4.2. So sánh GA cổ điển và các chương trỡnh tiến húa ............................ 36 1.2.5. Các bước xây dựng một chương trỡnh tiến húa ................................... 39 Chƣơng II: Tổng quan bài toán thời khóa biểu và các phương pháp tiếp cận ...................................................................................................................... 41 2.1 Tổng quan: ............................................................................................. 41 2.2. Cỏc bài toỏn thời khúa biểu ................................................................... 43 2.2.1. Thời khúa biểu Tiểu học ..................................................................... 43 2.2.2. Thời khóa biểu Trung học cơ sở, Trung học phổ thông ....................... 43 2.2.3. Thời khóa biểu Cao đẳng-Đại học ...................................................... 45 2.3. Các phương pháp tiếp cận hiện nay ....................................................... 48 Chƣơng III: Mô hỡnh tiến húa cho bài toỏn thời khúa biểu THPT ......... 51 3.1. Biểu diễn nhiễm sắc thể và kiểu gene .................................................... 51 3.2. Khởi tạo quần thể ban đầu ..................................................................... 53 3.2.1. Phõn bố số tiết học trong mỗi ngày cho từng khối lớp ......................... 53 3.2.2. Thủ tục tạo ngẫu nhiờn 1 nhiễm sắc thể ............................................... 53 3.3. Xác định hàm thích nghi ........................................................................ 56 3.4. Cỏc toỏn tử di truyền .............................................................................. 57 3.4.1 Cỏc toỏn tử biến dị ............................................................................... 57 3.4.1.1 Toán tử đổi chỗ tiết học trong một lớp (khử tiết cụm) ........................ 57 Phương pháp Tính toán tiến hóa Và ỏp dụng lập Thời khúa biểu Trung học Phổ thụng 3 3.4.1.2 Toán tử đổi chỗ giỏo viờn trong một lớp (khử tiết trựng) ................... 58 3.4.1.3 Toỏn tử chuyển dịch mụn học trong một ngày (khử tiết cỏch) ........... 59 3.4.1.4 Toỏn tử dồn tiết của một mụn học của một lớp (khử tiết phõn tỏn) ... 59 3.4.1.5 Toán tử thay đổi toàn bộ lớp .............................................................. 60 3.4.2. Cỏc toỏn tử lai ghộp ............................................................................ 60 3.5. Quỏ trỡnh chọn lọc ................................................................................. 61 3.6 Thủ tục tiến húa ....................................................................................... 62 Chƣơng IV: Xây dựng phần mềm .............................................................. 64 4.1 Tổ chức dữ liệu ....................................................................................... 64 4.2. Sơ đồ phân ró chức năng ........................................................................ 65 4.3. Một số chức năng và giao diện của phần mềm ........................................ 67 4.3.1. Chức năng “Nhập dữ liệu” ................................................................... 67 4.3.1.1. Chức năng “Bảng phõn cụng Giảng dạy” ......................................... 67 4.3.1.2 Chức năng “Bảng đăng ký tiết dạy bằng tay” ..................................... 68 4.3.2. Chức năng Hiển thị TKB ..................................................................... 69 4.3.2.1 Chức năng “Xem/In Thời khóa biểu Giáo viên” ................................ 69 4.3.2.2 Chức năng “In Thời khóa biểu Giáo viên” ......................................... 70 4.3.2.3 Chức năng “Xem/In thời khóa biểu Lớp” .......................................... 73 4.3.2.4 Chức năng “In thời khóa biểu các lớp” .............................................. 74 4.4. Thử nghiệm phần mềm ........................................................................... 75 4.4.1. Kết quả đạt được của phần mềm .......................................................... 75 4.4.2. Bảng kết quả thử nghiệm ..................................................................... 76 Kết luận ......................................................................................................... 77 Tài liệu tham khảo ......................................................................................... 78 Phương pháp Tính toán tiến hóa Và ỏp dụng lập Thời khúa biểu Trung học Phổ thụng 4 MỞ ĐẦU Thời khóa biểu của trường học là kế hoạch giảng dạy của giỏo viờn và học tập của học sinh. Một bảng thời khúa biểu hợp lý giỳp giỏo viờn thuận lợi, thoải mỏi khi lờn lớp và giỳp học sinh thoải mỏi khi học tập. Đó từ lõu, việc lập thời khúa biểu là vấn đề quan trọng của nhà trường và phải luôn luôn hoàn thành trước khi triển khai giảng dạy. Lập thời khóa biểu bằng phương pháp thủ công là công việc rất nặng nề, tốn nhiều thời gian và dễ vị phạm các ràng buộc về nghiệp vụ. Do vậy, khi áp dụng phải trải qua điều chỉnh vài lần mới có thể đạt được yêu cầu cơ bản. Lập thời khóa biểu là vấn đề của tất cả các hệ thống trường học từ bậc phổ thông đến cao đẳng đại học phải thường xuyên đối mặt trong việc tỡm ra một giải phỏp tối ưu hoặc chấp nhận được. Các bài toán thời khóa biểu rất phong phú và đa dạng bởi những ràng buộc và yêu cầu đặc trưng của từng hệ đào tạo, thậm chí từng trường học. Bài toỏn thời khúa biểu thuộc lớp bài toỏn NP khú [12] nên các giải thuật truyền thống khó giải quyết được trọn vẹn các yêu cầu nghiệp vụ và yêu cầu về thời gian thực hiện. Trong gần ba thập niên qua, giải thuật di truyền và các cải tiến-phát triển của nó gọi chung là tính toán tiến hóa [7] đó thực sự tạo ra cỏc kết quả rất khả quan khi ỏp dụng giải quyết cỏc bài toỏn tối ưu. Giải thuật di truyền và tính toán tiến hóa mô phỏng sự tiến hóa của tự nhiên của sinh học và gần đây nhất là phương pháp tối ưu hóa đàn kiến do Dorigo đề xuất là hướng tiếp cận hiện đại nhất. Cả hai loại giải thuật trên đó tỏ ra rất hiệu quả trong việc ỏp dụng Phương pháp Tính toán tiến hóa Và ỏp dụng lập Thời khúa biểu Trung học Phổ thụng 5 giải quyết cỏc bài toỏn tối ưu trong thực tế, tiêu biểu là bài toán lập thời khóa biểu trường học, là một bài toán thú vị và có tính thực tiễn cao. Ở Việt Nam đó cú một vài phần mềm lập thời khúa biểu khỏ tốt, nhưng chưa đáp ứng hết các yêu cầu thực tế cũng như cách tổ chức giảng dạy của từng trường. Ở Đăk Lăk, chưa có phần mềm lập thời khóa biểu riêng đáp ứng các điều kiện cụ thể của miền núi. Xuất phát từ những vấn đề trên, đề tài “Tính toán tiến hóa và áp dụng lập thời khóa biểu trường Trung học phổ thông”, khúa luận tập trung nghiờn cứu giải thuật di truyền và phương pháp tính toán tiến hóa đồng thời giải quyết bài toán thời khóa biểu về mặt lý thuyết lẫn xõy dựng phần mềm, xem như một thử nghiệm đầu tiên ở vùng Tây Nguyên xa xôi. Do khả năng và thời gian hạn chế, tác giả chỉ mới hoàn thành phần mềm ở mức cơ bản nhất, chỉ tạm sử dụng nội bộ trong trường nơi tác giả công tác. Hy vọng trong thời gian tới, tác giả sẽ bổ sung thêm chức năng cho phần mềm và hoàn chỉnh thành sản phẩm sử dụng được trong ngành giáo dục Đăk Lăk. Phương pháp Tính toán tiến hóa Và ỏp dụng lập Thời khúa biểu Trung học Phổ thụng 6 Cấu trúc của luận văn như sau: Chƣơng I: Giải thuật di truyền và Tính toán tiến hóa Giới thiệu tóm lược về lịch sử, sự phát triển và các kết quả đạt được của giải thuật di truyền cổ điển trong việc giải quyết bài toán tối ưu hàm số nhiều biến. Các phần tiếp theo trỡnh bày cỏc khỏi niệm, các đặc trưng, cấu trúc và cơ chế hoạt động của giải thuật di truyền. Minh họa việc tỡm giỏ trị cực đại hàm số nhiều biến bằng giải thuật di truyền cổ điển. Giới thiệu sự phỏt triển và cỏc cải tiến của giải thuật di truyền với tờn gọi chung là tớnh toỏn tiến hóa. Nêu đặc trưng trong việc thay đổi cách biểu diễn nhiễm sắc thể và các toán tử di truyền cho phù hợp với từng bài toán cụ thể. Các hướng tiếp cận chính của phương pháp tính toán tiến hóa. Nêu cấu trúc và các bước cơ bản để xây dựng một chương trỡnh tiến húa. Chƣơng II: Tổng quan các bài toán thời khóa biểu Phát biểu sơ bộ các loại thời khóa biểu, chủ yếu là bài toán thời khóa biểu trường Trung Học Phổ Thông. Nêu các đặc trưng nghiệp vụ, các ràng buộc của từng loại thời khóa biểu. Chƣơng III: Mô hỡnh tiến húa cho bài toỏn cho bài toỏn thời khúa biểu Trung Học Phổ Thụng Đây là nội dung chính của luận văn. Các vấn đề được trỡnh bày là phỏt biểu đầy đủ các ràng buộc của bài toán thời khóa biểu Trung học phổ thông, giới thiệu cách biểu diễn nhiễm sắc thể và các toán tử di truyền để giải quyết bài toán bằng phương pháp tính toán tiến hóa. Chƣơng IV: Xây dựng phần mềm lập thời khóa biểu THPT Giới thiệu các chức năng cơ bản của phần mềm minh họa bài toán lập thời khóa biểu Trung Học Phổ Thông theo phương pháp tính toán tiến hóa, Phương pháp Tính toán tiến hóa Và ỏp dụng lập Thời khúa biểu Trung học Phổ thụng 7 một số giao diện của phần mềm. Phần mềm được xây dựng bằng Access 2000. Kết quả thử nghiệm của phần mềm trên bộ dữ liệu thực của trường Trung Học Phổ Thông Buôn Ma Thuột. Đánh giá hiệu quả và tính khả dụng của phần mềm. Phương pháp Tính toán tiến hóa Và ỏp dụng lập Thời khúa biểu Trung học Phổ thụng 8 Chƣơng I GIẢI THUẬT DI TRUYỀN VÀ TÍNH TOÁN TIẾN HểA (Genetic Algorithm and Evolutionary Computation) 1.1. GIẢI THUẬT DI TRUYỀN: 1.1.1. Lƣợc sử í tưởng giải thuật di truyền được nêu ra từ những năm 1950-1960 bởi các nhà sinh học nhằm giải quyết các bài toán di truyền trong sinh học. Khi đó, giải thuật di truyền chưa trở thành một phương pháp luận mà chỉ ở mức độ giải quyết các bài toán sinh học riêng lẻ. A.S Fraser là người tiên phong nêu lên sự tương đồng giữa sự tiến hóa của sinh vật trong tự nhiên và chương trỡnh tin học giả tưởng về giải thuật di truyền cổ điển (GA-Genetic Algorithm). Thực tế, John Henry Holland mới là người đầu tiên triển khai ý tưởng và phương thức giải quyết các bài toán tối ưu dựa theo sự tiến hóa tự nhiên của sinh vật. Năm 1975, John Henry Holland và các đồng nghiệp của ông ở trường Đại học Michigan – Hoa Kỳ công bố Giải thuật di truyền và ông được xem là người đề xướng giải thuật này. Ông đó đúc kết các bài giảng và các bài báo thành sách với tựa đề Adaptation in Nature and Artificial Systems – Sự mụ phỏng theo tự nhiờn và cỏc hệ thống nhõn tạo. Trong sách, J.H. Holland đó trỡnh bày rất hệ thống phương pháp giải quyết các bài toán tối ưu hàm nhiều biến nhờ một kiểu gene nhị phân và nhiều công trỡnh nghiờn cứu về giải thuật di truyền, gọi tắt là GA. Phương pháp Tính toán tiến hóa Và ỏp dụng lập Thời khúa biểu Trung học Phổ thụng 9 Sau Holland, nhiều đồng nghiệp của ông như Kenneth De Jong, David E. Goldberg đó dần tạo nờn nền tảng lý thuyết vững chắc cho GA và thực hiện cỏc ỏp dụng của GA để giải quyết các bài toán phức tạp trong thực tế. Kể từ đó, nhiều công trỡnh nghiờn cứu về GA đó được công bố ở nhiều nơi trên thế giới. Hai đồng nghiệp xuất sắc của ông là Kenneth De Jong và David E. Goldberg đó cú nhiều cụng trỡnh nghiờn cứu về GA cổ điển và những phát triển của nó trong nhiều lĩnh vực khác nhau. Đặc biệt, David E. Golberg đưa ra “Thuật toán di truyền hỗn hợp” vào năm 1993, được xem là một cải tiến quan trọng trong GA cổ điển. Các nhà nghiên cứu về GA cổ điển lại tiếp tục đưa ra nhiều cải tiến vô cùng phong phú cho GA cổ điển và được gọi chung là Tính toán tiến hóa – Evolutionary Computation [7]. GA đó kết hợp với cỏc kỹ thuật thuộc lĩnh vực trớ tuệ nhõn tạo như Hệ chuyên gia (Expert System), Mạng Neuron nhân tạo (Artificial Neural Network), Logic mờ (Fuzzy Logic) nhằm tỡm giải phỏp tối ưu cho những vấn đề phức tạp mà các giải thuật cổ điển truyền thống đó khụng giải quyết được thỏa đáng [3]. GA ứng dụng được nhiều trong các lĩnh vực khác nhau, từ khoa học tự nhiên đến khoa học nhân văn, từ kỹ thuật sang thương vụ và kinh tế tài chớnh. Những ứng dụng này cú thể chia làm ba nhúm chớnh: Tỡm mụ hỡnh tối ưu cho vấn đề. Tỡm kiếm và tối ưu hóa giải pháp là đề tài thích hợp nhất của GA Hoạch định quy trỡnh sản xuất, lộ trỡnh vận chuyển, cỏch bố trớ cỏc bộ phận trong mụi trường. Chọn lựa cỏc nhúm hay thành phần trong một tổ chức Phương pháp Tính toán tiến hóa Và ỏp dụng lập Thời khúa biểu Trung học Phổ thụng 10 1.1.2. í tƣởng í tưởng của GA là mô phỏng theo quá trỡnh tiến húa tự nhiờn của sinh vật theo thuyết Darwin. Trong quỏ trỡnh tiến húa, mỗi cỏ thể đều phải tự tỡm cỏch thớch nghi tốt nhất với mụi trường sống rất phức tạp và luôn luôn thay đổi. Cá thể nào có khả năng thích nghi với môi trường cao hơn thỡ sẽ cú khả năng tồn tại, phát triển và sinh sản cao hơn, ngược lại cá thể nào có khả năng thích nghi thấp sẽ có nhiều nguy cơ bị tiêu vong hoặc phát triển chậm. Sự thích nghi đó được đúc kết và ghi lại trong cấu trỳc của nhiễm sắc thể của chỳng. Việc giải bài toỏn thực tế cú thể xem là việc tỡm kiếm trong một khụng gian cỏc lời giải tiềm năng nhằm tỡm ra lời giải tốt nhất hoặc chấp nhận được mà ta có thể gọi là quá trỡnh tối ưu hóa. Đối với không gian tỡm kiếm nhỏ, đơn giản nhất là dùng kỹ thuật “vét cạn”, nghĩa là liệt kê toàn bộ lời giải tiềm năng, sau đó chọn ra lời giải. Đối với không gian tỡm kiếm khỏ lớn thỡ kỹ thuật vột cạn cú độ phức tạp rất lớn, khó chấp nhận được. Khi đó, giải thuật di truyền tỏ ra rất thớch hợp cho việc giải quyết bài toỏn tỡm kiếm lời giải tối ưu. GA không chú trọng đến giải pháp duy nhất và chính xác như các phương thức cổ điển, trái lại GA xét đến toàn bộ các giải pháp và chọn lấy giải pháp tương đối tốt nhất. GA dựa trờn tớnh ngẫu nhiên như trong thế giới tự nhiên của sinh vật, nhưng được hướng dẫn bởi hàm thích nghi (Fitness Function), hơn nữa GA cũn cú nền tảng lý thuyết vững chắc là lý thuyết sơ đồ (Schema theorem) [20]. 1.1.3. Đặc thù của GA cổ điển Phương pháp Tính toán tiến hóa Và ỏp dụng lập Thời khúa biểu Trung học Phổ thụng 11 GA lập luận ngẫu nhiờn thay vỡ xỏc định. GA duyệt toàn bộ các giải pháp, sau đó chọn lấy giải pháp tương đối tốt nhất dựa trên hệ số thích nghi. GA không để ý đến chi tiết vấn đề mà chỉ chỳ ý đến giải pháp, đặc biệt là dóy số tượng trưng cho giải pháp. Goldberg và Zbiniev Michalewicz nêu ra đặc trưng của GA như sau: GA làm việc với một mó húa của tập hợp tham số mà khụng phải một tham số. GA tỡm kiếm từ một quần thể cỏc điểm chứ không phải một điểm hoặc một vài điểm như phương pháp tỡm kiếm leo đồi (Hill Climbing). GA đánh giá thông tin với hàm mục tiêu mà không đưa vào đạo hàm hay thông tin bổ sung khác. GA sử dụng các luật biến đổi theo xác suất mà không sử dụng luật quyết định. 1.1.4. Cấu trúc của giải thuật di truyền cổ điển GA cổ điển sử dụng ý tưởng và các thuật ngữ trong di truyền học như được trỡnh bày sau đây. Trong tự nhiên, mỗi cá thể có một tập hợp các tính chất và đặc điểm riêng biệt được thể hiện ra ngoài môi trường gọi là kiểu hỡnh (phenotype). Kiểu hỡnh này được quyết định bởi cấu trúc gene trong cơ thể, gọi là kiểu gene (genotype). Các gene tạo thành các nhiễm sắc thể, mỗi tế bào có tập hợp các nhiễm sắc thể như nhau. Các nhiễm sắc thể là các chuỗi DNA (DeoxyriboNucleotic Acid) hoạt động như một mô hỡnh cho toàn bộ cơ thể. Sự đa dạng về kiểu gene của các cá thể dẫn đến sự đa dạng về kiểu hỡnh của Phương pháp Tính toán tiến hóa Và ỏp dụng lập Thời khúa biểu Trung học Phổ thụng 12 một quần thể sinh học. Quỏ trỡnh phỏt triển của mỗi quần thể tuõn theo quy luật chọn lọc của tự nhiờn mà tiến húa qua cỏc thế hệ nối tiếp nhau. Trong đó, các hậu duệ được sinh ra từ thế hệ trước thông qua quá trỡnh sinh sản (di truyền và biến dị) cạnh tranh tự nhiờn với nhau, cỏ thể nào cú kiểu hỡnh (và do đó là kiểu gene) thích nghi cao hơn trong môi trường phát triển thỡ sẽ cú khả năng cao hơn trong tồn tại và sinh sản con cháu. Do đó, kiểu gene này sẽ tiến hóa và hoàn thiện. Quỏ trỡnh tiến húa này được lặp đi lặp lại, các cá thể có kiểu gene phù hợp sẽ sống sót và phát triển, các cá thể yếu sẽ bị loại bỏ dần. GA là kỹ thuật tối ưu dựa trên khái niệm chọn lọc tự nhiên và di truyền. Do vậy, lời giải của bài toán được trỡnh bày như các gene trong nhiễm sắc thể. GA mô tả một nhóm các lời giải tiềm năng được đề cử, qua tiến hóa và chọn lọc tự nhiên các nhiễm sắc thể với độ thích nghi tốt hơn sẽ xuất hiện. Chọn lọc tự nhiên đảm bảo cho cá thể có độ thích nghi tốt nhất sẽ được truyền lại cho các thế hệ con cháu (các quần thể tương lai). Phép lai ghép (Crossover) kết hợp các gene từ hai cá thể bố mẹ để tạo thành hai cá thể con mới (Offspring) với độ thích nghi có chiều hướng cao hơn bố mẹ. Phép biến dị (Mutation) cho phép tạo ra chất liệu di truyền mới, tạo ra những đột phá trong tỡm kiếm. GA cung cấp sự cải tiến thế hệ về độ thích nghi của các cá thể và sau nhiều thế hệ sẽ tạo ra các cá thể chứa những thiết lập biến đổi đó được tối ưu. Mỗi cá thể (Individual) trong GA thường chỉ gồm một nhiễm sắc thể. Do vậy thuật ngữ cá thể và nhiễm sắc thể được dùng không phân biệt ngữ nghĩa. 1.1.4.1. Cấu trỳc nhiễm sắc thể và kiểu gene Trong GA cổ điển, mỗi cá thể (hay nhiễm sắc thể) được mó húa bởi cỏc chuỗi nhị phõn. Phương pháp Tính toán tiến hóa Và ỏp dụng lập Thời khúa biểu Trung học Phổ thụng 13 Vớ dụ: một nhiễm sắc thể gồm 8 gene như sau: 1 0 0 1 0 1 1 0 Mỗi kiểu gene (một nhiễm sắc thể cụ thể) biểu thị một lời giải tiềm năng của bài toán. Một quá trỡnh tiến húa được thực hiện trên một quần thể (một tập hợp các cá thể) tương đương với sự tỡm kiếm trong một khụng gian cỏc lời giải tiềm năng (Potential solution). Sự tỡm kiếm này đũi hỏi sự cõn bằng giữa hai mục tiờu: tỡm lời giải tốt nhất và khỏm phỏ khụng gian tỡm kiếm. GA cổ điển thực hiện việc tỡm kiếm theo nhiều hướng bằng cách duy trỡ một tập lời giải tiềm năng, khuyến khích sự hỡnh thành và trao đổi thông tin giữa các hướng. Tập lời giải trải qua quá trỡnh tiến húa và cuối cựng cho ta một lời giải đủ tốt theo yêu cầu. Tại mỗi thế hệ, các lời giải tương đối tốt được tái sinh, và các lời giải tương đối xấu bị loại bỏ dần. Để đánh giá mức độ tốt xấu của từng lời giải, người ta xây dựng hàm thích nghi (Fitness Function), hàm này đóng vai trũ như môi trường sống trong thuyết tiến hóa của Darwin. 1.1.4.2. Thủ tục GA GA cổ điển do J.H Holland đề xướng [16], [20] nhằm giải bài toỏn tối ưu sau đây: Max{(f(x) / x M Rn} Trong đó M là hỡnh hộp trong khụng gian số thực n-chiều Rn, f(x) > 0 với x M Phương pháp Tính toán tiến hóa Và ỏp dụng lập Thời khúa biểu Trung học Phổ thụng 14 Mỗi x trong M, được mó húa bởi một chuỗi nhị phõn z = (x1, x2, … xm), với m là độ dài của chuỗi. Chuỗi này gọi là nhiễm sắc thể hay cá thể, mỗi x i gọi là một gene. Người ta xây dựng các thủ tục mó húa và giải mó tương ứng. Xây dựng hàm eval trên tập nhiễm sắc thể để đánh giá độ thích nghi của mỗi cá thể: eval(z) = f(x), trong đó x là vector tương ứng với z. Tương ứng với t = 0, là điểm xuất phát thủ tục GA hay thế hệ ban đầu, ta khởi tạo ngẫu nhiên quần thể ban đầu P(0) gồm N cá thể. Sau đó tiến hành đánh giá độ thích nghi của quần thể. Quá trỡnh tiến húa được diễn ra thông qua quá trỡnh chọn lọc cỏc cỏ thể tốt, biến đổi các cá thể bởi các toán tử di truyền, rồi lại đánh giá độ tốt của quần thể cho đến khi chọn được các cá thể đủ tốt. Cấu trúc của GA cổ điển như sau: Procedure GA Begin t  0; Khởi tạo P(t); Đánh giá P(t); Repeat t  t + 1; Chọn Q(t) từ P(t-1); // bởi bỏnh xe xổ số Tỏi tạoP(t) từ Q(t); // bởi cỏc toỏn tử di truyền Đánh giá P(t) và chọn cá thể tốt nhất Until điều_kiện_kết_thúc; Biểu diễn lời giải; End; Phương pháp Tính toán tiến hóa Và ỏp dụng lập Thời khúa biểu Trung học Phổ thụng 15 Trong đó P(t) là quần thể tại thế hệ thứ t Quỏ trỡnh tiến húa được diễn ra trong vũng lặp While, tại thế hệ thứ t, t t t giải thuật duy trỡ một tập lời giải P(t ) {x1 , x2 , ..., xn } . Mỗi lời giải xit được đánh giá độ thích nghi. Một tập lời giải mới được xây dựng (vũng lặp t+1) bằng cỏch chọn lọc cỏc cỏ thể cú độ thích nghi cao hơn, ta được tập lời giải trung gian. Tiếp theo, một số cá thể trong tập lời giải đó được chọn này được biến đổi bằng các toán tử di truyền là “lai ghép” và “biến dị” để tạo thành một lời giải mới cho thế hệ thứ t+1. 1.1.4.3. Phương pháp mó húa và giải mó Biểu diễn mó nhị phõn và giải mó của mỗi lời giải tiềm năng thực hiện như sau: Mó húa: Giả sử ta cần tỡm cực đại của hàm số n biến f(x1, x2, … xn) với sai số mỗi biến xi là 10-p (sai số đến p chữ số thập phân). Ta chia mỗi đoạn [ai, bi] thành (bi ai) x 10p đoạn bằng nhau. Ký hiệu mi là số tự nhiờn nhỏ nhất thỏa món: (bi ai ).10 p 2 mi 1 Khi đó, nếu x = (x1, x2, …xn) và xi thuộc đoạn thứ k thỡ xi được mó húa bởi chuỗi nhị phõn cú độ dài mi cú dạng (bmi 1 ,...,b0 ) sao cho k mi 1 b j .2 j j 0 sẽ thỏa món yờu cầu về độ chính xác và x được biểu diễn bởi chuỗi nhị phân n có độ dài m mj j Phương pháp Tính toán tiến hóa Và ỏp dụng lập Thời khúa biểu Trung học Phổ thụng 16 m1 bits đầu tiên của chuỗi ứng với một giá trị x1 theo ứng với một giỏ trị x2 một giỏ trị xk [a1, b1], m2 bits tiếp [a2, b2], …, mk bits cuối cựng của chuỗi ứng với [ak, bk] Vớ dụ: Tỡm giỏ trị cực đại của hàm số hai biến: f(x1, x2) = 10 + x1sinx1 + x2sinx2 trờn miền –1 x1 3; 3 x2 5 với sai số cỏc biến là 10-2 Vỡ b1 – a1 = 3 – (-1) = 4; 4x102 = 400 và 28 < 400 < 29 nên cần 9 gene để biểu diễn x1 Tương tự, b2 – a2 = 5 – 3 = 2; 2x102 = 200 và 27 < 200 < 28 nên cần 8 gene để biểu diễn x2 Do vậy, m = 17 là độ dài của chuỗi. Giải mó: Chuyển đổi các chuỗi nhị phân về dạng số thập phân. Với mỗi đoạn gene (bmi 1 ,...,b0 ) ta xác định ki theo cơ số 10: mi 1 (b j .2 j )10 ki j 0 và cú: xi a i ki . bi ai 2 mi 1 hay là: mi 1 (b j .2 j )10 . xi a i j 0 (bi ai ) 2 mi 1 Phương pháp Tính toán tiến hóa Và ỏp dụng lập Thời khúa biểu Trung học Phổ thụng 17 1.1.4.4 Thủ tục chọn lọc (Selection) Các cá thể được chọn lọc theo độ thích nghi của chúng để tham gia vào pha tiếp theo của quá trỡnh tiến húa. Cỏ thể cú độ thích nghi cao hơn có cơ hội được chọn nhiều hơn, nghĩa là có nhiều con cháu trong các thế hệ tiếp theo. Phép chọn lọc các cá thể trong mỗi quần thể được thực hiện nhờ bánh xe xổ số (Roulette Wheel tờn một trũ đánh bạc của Châu Âu). Với mỗi quần thể P(t –1) gồm N nhiễm sắc thể: P(t – 1) = {v1, v2, …, vn} ta xây dựng bánh xe xổ số như sau: Bỏnh xe xổ số Đánh giá độ phù hợp toàn phần, cũn gọi là tổng độ thích nghi của quần thể. N F eval(vi ) i 1 Tớnh xỏc suất chọn lọc pi của mỗi cỏ thể vi : pi eval (vi ) F Tớnh xỏc suất tớch lũy qi cho mỗi cỏ thể vi: i p j , i = 1, 2, … N qi j 1 Quỏ trỡnh chọn lọc Quỏ trỡnh chọn lọc quần thể Q(t) từ P(t – 1) dựa vào bỏnh xe xổ số được thực hiện như sau: Phương pháp Tính toán tiến hóa Và ỏp dụng lập Thời khúa biểu Trung học Phổ thụng 18 Đối với mỗi số tự nhiên k = 1, 2,.., N, phát sinh một số thực ngẫu nhiên rk [0, 1] Nếu rk qi , 2 i q1 thỡ chọn cỏ thể v1, ngược lại, chọn cá thể vi sao cho qi-1 < rk N Với cách thực hiện như thế, một số cá thể có thể được chọn nhiều lần và Q(t) vẫn được xem là có N phần tử. Các cá thể tốt được chọn nhiều lần, các cá thể trung bỡnh thỡ bỡnh ổn và cỏc cỏ thể xấu bị giảm dần. Minh hoạ bỏnh xe xổ số với quần thể cú 5 cỏ thể: 30% 20% 1 5 2 4 15% 3 25% 10% Cá thể 1 có xác suất chọn lọc là 20%, nghĩa là mỗi lần quay bánh xe xổ số, nó có khả năng được chọn là 0.2. Tương tự như vậy cho các các thể thứ 2, 3, 4, 5. 1.1.4.5. Quỏ trỡnh tỏi tạo Quỏ trỡnh tỏi tạo dựa trờn cỏc toỏn tử di truyền là phộp lai và biến dị. 1.1.4.5.1. Cỏc toỏn tử di truyền a. Phép lai hay trao đổi chéo (Crossover Operator): Kết hợp các đặc tính trên nhiễm sắc thể của bố và mẹ để tạo thành hai cá thể con mới, bằng cách hoán đổi các đoạn gene tương ứng trên các nhiễm sắc thể của bố và Phương pháp Tính toán tiến hóa Và ỏp dụng lập Thời khúa biểu Trung học Phổ thụng