Tài liệu Cơ sở toán học của giải thuật di truyền

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC VŨ THỊ THU HÀ CƠ SỞ TOÁN HỌC CỦA GIẢI THUẬT DI TRUYỀN LUẬN VĂN THẠC SỸ TOÁN HỌC THÁI NGUYÊN - NĂM 2010 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC VŨ THỊ THU HÀ CƠ SỞ TOÁN HỌC CỦA GIẢI THUẬT DI TRUYỀN Chuyên ngành: TOÁN ỨNG DỤNG Mã số: 60.46.36 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học: TS. VŨ MẠNH XUÂN THÁI NGUYÊN - NĂM 2010 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn i Mục lục Mở đầu 1 1 Tổng quan về giải thuật di truyền 1.1 Khái quát chung . . . . . . . . . . . . . . . . . . . . . . 1.2 Các vấn đề cơ bản của giải thuật di truyền . . . . . . . . 1.2.1 Mã hoá - mô tả di truyền cho lời giải của bài toán 1.2.2 Tạo lập lời giải ban đầu (khởi tạo quần thể) . . . 1.2.3 Xây dựng hàm phù hợp . . . . . . . . . . . . . . 1.2.4 Các toán tử di truyền . . . . . . . . . . . . . . . . 1.3 Giải thuật di truyền kinh điển . . . . . . . . . . . . . . . 1.3.1 Mã hoá - Biểu diễn các biến bằng véc tơ nhị phân 1.3.2 Toán tử chọn lọc . . . . . . . . . . . . . . . . . . 1.3.3 Toán tử lai ghép . . . . . . . . . . . . . . . . . . 1.3.4 Toán tử đột biến . . . . . . . . . . . . . . . . . . 1.3.5 Hàm phù hợp . . . . . . . . . . . . . . . . . . . . 1.3.6 Giải thuật di truyền cổ điển . . . . . . . . . . . . 1.4 Giải thuật di truyền mã hóa số thực (RCGA) . . . . . . 1.4.1 Giới thiệu RCGA . . . . . . . . . . . . . . . . . . 1.4.2 Các toán tử của RCGA . . . . . . . . . . . . . . 1.4.3 Một số mô hình tiến hóa. . . . . . . . . . . . . . 3 3 8 8 9 9 9 11 11 12 14 16 16 18 20 20 20 23 2 Cơ sở toán học của giải thuật di truyền 2.1 Định lý sơ đồ của Holland. . . . . . . . . . . . . . . . . . 2.1.1 Một số khái niệm . . . . . . . . . . . . . . . . . . 26 27 27 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ii 2.2 Mô hình Markov của giải thuật di truyền . . . . . . . . . 2.2.1 Tính Markov . . . . . . . . . . . . . . . . . . . . 2.2.2 Một số kết quả . . . . . . . . . . . . . . . . . . . 2.2.3 Xích Markov trong GA . . . . . . . . . . . . . . . 2.3 Một số vấn đề khác . . . . . . . . . . . . . . . . . . . . . 2.3.1 Dạng biểu diễn ma trận của toán tử lai ghép trong RCGA . . . . . . . . . . . . . . . . . . . . . . . . 2.3.2 Điều kiện thành công của toán tử lai ghép . . . . 2.3.3 Toán tử lai ghép SBX . . . . . . . . . . . . . . . Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 31 32 35 36 40 40 44 45 48 49 1 Mở đầu Ngày nay sự phát triển mạnh như vũ bão của máy tính điện tử đã làm thay đổi sâu sắc đến nhiều lĩnh vực của cuộc sống, với tốc độ tính toán nhanh và chính xác, nhiều bài toán tính toán phức tạp trước đây đã được giải quyết trọn vẹn. Hơn thế nữa, nhiều kỹ thuật tính toán dựa trên sự mô phỏng hoạt động tự nhiên hay bắt chước suy nghĩ của con người đã rất phát triển và tạo ra nhiều công cụ tính toán mới có hiệu năng cao. Giải thuật di truyền (GA – Genetic Algorithm) là một trong những công cụ chính trong hệ thống tính toán mềm hay còn gọi là trí tuệ tính toán. GA được đề xuất từ khoảng những năm 70 của thế kỷ trước dựa trên sự mô phỏng quá trình tiến hoá tự nhiên. GA chủ yếu giải quyết vấn đề tìm nghiệm trong lớp các bài toán tối ưu có độ phức tạp tính toán lớn. GA tìm kiếm lời giải của bài toán dựa trên một quần thể được hiểu như một tập những lời giải và tiến hoá quần thể đó dựa trên các toán tử di truyền như chọn lọc, lai ghép, đột biến. Sau khi được giới thiệu, GA đã được các nhà toán học và tin học nghiên cứu và phát triển rất nhanh, nhiều dạng biến thể cũng như vấn đề cải tiến các toán tử được đề xuất và kết quả thử nghiệm cho thấy tính hiệu quả rõ rệt của giải thuật này. Tuy vậy, GA là một giải thuật xác suất, hầu hết nó chỉ đưa ra những lời giải chấp nhận được trong thời gian ngắn mà chưa chắc đã đạt được lời giải tối ưu. Kết quả của quá trình tiến hoá để chọn lời giải tốt nhất phụ thuộc vào nhiều yếu tố ngẫu nhiên: quần thể khởi tạo ngẫu nhiên, chọn cá thể để tiến hoá ngẫu nhiên, việc sinh ra cá thể mới cũng là ngẫu nhiên, . . . Vì vậy việc nghiên cứu cơ sở toán học của giải thuật để đảm Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 2 bảo chắc chắn sẽ đạt được lời giải tối ưu toàn cục của bài toán là việc làm rất khó khăn mặc dù điều này hợp với quy luật tự nhiên và thử nghiệm đều cho kết quả tốt. Cho tới nay người ta mới chỉ đạt được một số kết quả sơ bộ về sự hội tụ của giải thuật chủ yếu dựa trên định lý sơ đồ của Hollan và dựa trên mô hình Markov. Đề tài này nhằm tập trung nghiên cứu cơ sở toán học của GA, tìm hiểu và trình bày một cách có hệ thống một số kết quả nghiên cứu về mô hình toán học của GA cũng như đánh giá sự hội tụ của giải thuật. Do điều kiện nghiên cứu cũng như khả năng lập trình còn hạn chế nên chưa đặt ra việc thử nghiệm trên những bài toán cụ thể. Đề tài gồm những nội dung chính sau: Chương 1 trình bày những vấn đề tổng quan về giải thuật di truyền, nguyên lý chung, giải thuật di truyền kinh điển dựa trên mã hoá nhị phân và giải thuật di truyền mã hoá số thực. Mô tả tường minh giải thuật cũng như một số dạng toán tử di truyền tiêu biểu. Chương 2 trình bày những vấn đề nghiên cứu về cơ sở toán của giải thuật bao gồm định lý sơ đồ của Hollan, mô hình Markov của giải thuật và một số phân tích toán học của các toán tử. Như đã nêu trên, do GA là thuật toán xác suất chứ không tiền định nên việc phân tích mô hình toán học của nó là cực kỳ khó khăn. Luận văn này chỉ đặt ra mục tiêu là tìm hiểu và trình bày lại một cách hệ thống những nội dung cơ bản như đã nêu. Dù rất cố gắng song do còn nhiều hạn chế về thời gian, kiến thức,. . . nên luận văn này không tránh khỏi những thiếu sót. Em rất mong được sự góp ý của các thầy cô cùng các bạn học viên để hoàn thiện hơn nữa hoặc có thể thác triển tiếp đề tài này. Trong suốt quá trình làm đề tài em nhận được sự giúp đỡ của rất nhiều các thầy cô giáo của Đại học Thái Nguyên và các bạn học viên lớp CHTK2, đặc biệt là sự hướng dẫn rất tận tình của thầy giáo TS.Vũ Mạnh Xuân. Em xin chân thành cảm ơn. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 3 Chương 1 Tổng quan về giải thuật di truyền 1.1 Khái quát chung Giải thuật di truyền (Gennetic algorithims - GA) là 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 hoá của con người hay của sinh vật nói chung trong điều kiện quy định sẵn của môi trường. Giải thuật di truyền cũng như các thuật toán tiến hoá nói chung hình thành dựa trên quan niệm cho rằng, quá trình tiến hoá tự nhiên là quá trình hoàn hảo nhất, hợp lý nhất và tự nó đã mang tính tối ưu. Quan niệm này có thể được xem như một tiên đề đúng không chứng minh được nhưng phù hợp với thực tế khách quan. Quá trình tiến hoá thể hiện tính tối ưu ở chỗ, thế hệ sau bao giờ cũng tốt hơn (phát triển hơn, hoàn thiện hơn) thế hệ trước. Tiến hoá tự nhiên được duy trì nhờ 2 quá trình cơ bản: sinh sản và chọn lọc tự nhiên. Xuyên suốt quá trình tiến hoá tự nhiên các thế hệ mới luôn được sinh ra để bổ sung, thay thế thế hệ cũ. Cá thể nào không thích ứng được với môi trường sẽ bị đào thải. Sự thay đổi môi trường cũng là động lực thúc đẩy quá trình tiến hoá. Ngược lại, tiến hoá cũng tác động trở lại góp phần làm thay đổi môi trường. Các cá thể mới sinh ra trong quá trình tiến hoá nhờ sự lai ghép thế hệ cha mẹ. Một cá thể mới có thể mang những tính trạng của cha mẹ (di Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 4 truyền), cũng có thể mang những tính trạng hoàn toàn khác (đột biến). Di truyền và đột biến là 2 cơ chế có vai trò quan trọng như nhau trong quá trình tiến hoá. Dù rằng đột biến xảy ra xác suất nhỏ hơn nhiều so với hiện tượng di truyền. Giải thuật 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ể, các cá thể này cũng còn được gọi là các chuỗi hay các Nhiễm sắc thể (NST). Trong GA, ta chỉ nói về những cá thể có 1 NST; các NST được tạo thành từ các đơn vị - các gen - biểu diễn trong một chuỗi tuyến tính, mỗi gen kiểm soát một (số) đặc trưng. Gen với những đặc trưng nhất định có vị trí nhất định trong NST. Bất cứ đặc trưng nào của mỗi cá thể có thể tự biểu hiện một cách phân biệt, và gen có thể nhận một số giá trị khác nhau (các giá trị về tính năng). Một vấn đề - bài toán đặt ra sẽ được mã hoá thành các chuỗi bit với chiều dài cố định. Nói một cách chính xác là các thông số của bài toán sẽ được chuyển đổi và biểu hiện lại dưới dạng các chuỗi bit. Các thông số này có thể là các biến của một hàm hoặc hệ số của một biểu thức toán học. Người ta gọi các chuỗi bit này là mã genome (gen) ứng với mỗi cá thể, các gen đều có cùng chiều dài. Nói ngắn gọn, một lời giải sẽ được biểu diễn bằng một chuỗi bit cũng giống như mỗi cá thể đều được quy định bằng gen của cá thể đó vậy. Đối với thuật giải di truyền một cá thể chỉ có 1 gen duy nhất và 1 gen cũng chỉ phục vụ cho một cá thể duy nhất. Mỗi kiểu (nhóm) gen (ta gọi là 1NST) sẽ biểu diễn một lời giải của bài toán đang giải (ý nghĩa của 1 NST cụ thể được người sử dụng xác định trước), một tiến trình tiến hoá được thực hiện trên 1 quần thể các NST 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 (có vẻ mâu thuẫn nhau). Khai thác những lời giải tốt nhất và khảo sát không gian tìm kiếm. GA là phương pháp tìm kiếm (độc lập miền) tạo được sự cân đối đáng kể giữa việc khai thác và khảo sát không gian tìm kiếm. Thực ra, GA thuộc lớp các giải thuật xác suất, nhưng lại rất khác Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 5 những giải thuật ngẫu nhiên vì chúng kết hợp các phần tử tìm kiếm trực tiếp và ngẫu nhiên. Khác biệt quan trọng giữa tìm kiếm của GA và các phương pháp tìm kiếm khác là GA duy trì và xử lý một tập các lời giải (ta gọi là một quần thể) - tất cả những phương pháp khác phần lớn xử lý một điểm trong không gian tìm kiếm. Chính vì vậy, GA mạnh hơn các phương pháp tìm kiếm hiện có rất nhiều. GA thực hiện tiến trình tìm kiếm lời giải tối ưu theo nhiều hướng bằng cách duy trì một quần thể các lời giải và thúc đẩy sự thành hình và trao đổi thông tin giữa các hướng này. Quần thể trải qua tiến trình tiến hoá, ở mỗi thế hệ lại tái sinh các lời giải tương đối "tốt"; trong khi các lời giải tương đối "xấu" thì chết đi. Để phân biệt các lời giải khác nhau; hàm mục tiêu được dùng để đóng vai trò môi trường. Các thuật toán, tuy có những điểm khác biệt, nhưng đều mô phỏng các quá trình cơ bản: lai ghép, đột biến, sinh sản và chọn lọc tự nhiên. * Quá trình lai ghép (Crossover): Phép lai là quá trình hình thành nhiễm sắc thể mới trên cơ sở nhiễm sắc thể cha - mẹ, bằng cách ghép một hay nhiều đoạn gen, hai (hay nhiều) nhiễm sắc thể cha - mẹ với nhau. Phép lai xảy ra xác suất Pc có thể mô phỏng như sau: • Chọn ngẫu nhiên hai (hay nhiều) cá thể bất kỳ trong quần thể. Giả sử các nhiễm sắc thể của cha - mẹ đều có m gen. • Tạo một số ngẫu nhiên trong khoảng từ 1 đến m − 1 (ta gọi là điểm lai). Điểm lai chứa các chuỗi cha - mẹ dài m thành hai nhóm chuỗi con dài m1 và m2 . Hai chuỗi nhiễm sắc thể con mới sẽ là m11 + m22 và m21 + m12. • Đưa hai cá thể mới này vào quần thể để tham gia các quá trình tiến hoá tiếp theo. * Quá trình đột biến (Mutation) Đột biến là hiện tượng cá thể con mang một (số) tính trạng không có trong mã di truyền của cha - mẹ. Phép đột biến xảy ra với xác suất Pm , nhỏ hơn rất nhiều so với xác suất lai Pc . Phép đột biến có thể mô phỏng như sau: Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 6 • Chọn ngẫu nhiên một cá thể bất kỳ cha - mẹ trong quần thể. • Tạo một số ngẫu nhiên k trong khoảng từ 1 đến m, 1 ≤ k ≤ m. • Thay đổi gen thứ k và trả cá thể này về quần thể để tham gia quá trình tiến hoá tiếp theo. * Quá trình sinh sản và chọn lọc (Selection) Phép tái sinh là quá trình trong đó, các cá thể được sao chép trên cơ sở độ thích nghi của nó. Độ thích nghi là một hàm gán một giá trị thực cho các cá thể trong quần thể. Quá trình này có thể được mô phỏng như sau: • Tính độ thích nghi của từng cá thể trong quần thể hiện hành, lập bảng cộng dồn các giá trị thích nghi (theo số thứ tự gán cho từng cá thể). Giả sử quần thể có n cá thể. Gọi độ thích nghi của cá thể thứ i là Fi, tổng dồn thứ i là Fti , tổng độ thích nghi của toàn quần thể là Fm. • Tạo một số ngẫu nhiên F trong đoạn từ 0 đến Fm . • Chọn cá thể thứ k đầu tiên thoả mãn F ≥ Ftk đưa vào quần thể của thế hệ mới. Phép chọn là quá trình loại bỏ các cá thể xấu trong quần thể để chỉ giữ lại trong quần thể các cá thể tốt. Phép chọn có thể được mô phỏng như sau: • Sắp xếp quần thể theo thứ tự độ thích nghi giảm dần. • Loại bỏ các cá thể cuối dãy để chỉ giữ lại n cá thể tốt nhất. (Ta giả sử quần thể có kích thước cố định n). Một giải thuật di truyền, giải một bài toán được cho phải có 5 thành phần sau: + Một cấu trúc dữ liệu I biểu diễn không gian lời giải của bài toán. + Phương pháp khởi tạo quần thể ban đầu P (0). + Hàm định nghĩa độ thích nghi eval (.) đóng vai trò môi trường. + Các phép toán di truyền như đã mô phỏng trên. + Và các tham số giải thuật di tryền sử dụng (kích thước quần thể, xác suất lai, đột biến,...). * Cấu trúc giải thuật di truyền tổng quát. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 7 Bắt đầu Khởi tạo quần thể Mã hoá các biến Đánh giá độ thích nghi Chọn lọc Lai ghép Đột biến Thoả điều kiện dừng Không Thoả Kết quả Kết thúc Hình 1.1: Sơ đồ cấu trúc thuật toán di truyền Bắt đầu: t=0 Khởi tạo P (t) Tính độ thích nghi cho các cá thể thuộc P (t). Khi (điều kiện dừng chưa thoả) lặp. t = t + 1; Tái sinh P 0 (t) từ P (t − 1); Lai Q(t) từ P (t − 1); Đột biến R(t) từ P (t − 1); Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 8 Chọn lọc P (t) từ P (t − 1) ∪ Q(t) ∪ R(t) ∪ P (t); Hết lặp Kết thúc. 1.2 Các vấn đề cơ bản của giải thuật di truyền 1.2.1 Mã hoá - mô tả di truyền cho lời giải của bài toán Việc mô tả di truyền cho lời giải cho bài toán gồm hai phần cơ bản: Xây dựng cấu trúc gen cho mỗi lời giải của bài toán để từ mỗi lời giải ta có thể mã hoá thành một NST (chuỗi các gen). Giải mã các NST để nhận được lời giải. Đây là vấn đề cần giải quyết trước khi giải bài toán với GA. Tuỳ thuộc vào nội dung của mỗi bài toán mà ta có cách mã hoá khác nhau. Sau đây là các phương pháp mã hoá hay được sử dụng: Mã hoá dạng chuỗi nhị phân: đây là phương pháp thông dụng và cơ bản nhất được sử dụng ngay từ bước ban đầu khi nghiên cứu GA. Trong phương pháp này mỗi NST là một chuỗi các bit 0 và 1. Mã hoá thứ tự: được sử dụng trong bài toán có sắp xếp thứ tự. Ở đây mỗi NST là một chuỗi các số nguyên thể hiện thứ tự phân bố lời giải của bài toán. Mã hoá theo giá trị: được sử dụng trong các bài toán mà mỗi lời giải là tập các giá trị (ví dụ tập số thực). Trong phương pháp này, mỗi NST là một chuỗi các giá trị có mối quan hệ tương ứng với bài toán. Mã hoá dạng cây: được sử dụng chủ yếu trong các biểu thức toán học, trong phương pháp mã hoá này mỗi NST là một cây của một nhóm đối tượng nào đó. Mã hoá số thực: Mỗi NST được mã hoá là một véc tơ trong không gian Rm chẳng hạn X = (a1 , a2, ..., am) với các ai ∈ R. Cách mã hoá này thường tự nhiên đối với các bài toán tối ưu số và được phát triển rất mạnh trong thời gian gần đây. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 9 1.2.2 Tạo lập lời giải ban đầu (khởi tạo quần thể) Tập lời giải ban đầu thường được khởi tạo ngẫu nhiên từ miền xác định của các lời giải. Cách tạo lập tập lời giải ban đầu phụ thuộc rất nhiều vào cách mã hoá NST. Với phương pháp mã hoá nhị phân: xây dựng NST bằng cách tạo ngẫu nhiên chuỗi các bit 0 hoặc 1. Với phương pháp mã hoá thứ tự: xây dựng NST ban đầu bằng cách hoán vị ngẫu nhiên các thứ tự. Với phương pháp mã hoá theo giá trị: tạo ngẫu nhiên từng giá trị trong miền xác định của lời giải để tạo ra chuỗi NST ban đầu. Với mã hoá số thực: tạo ngẫu nhiên N véc tơ thực trong Rm . 1.2.3 Xây dựng hàm phù hợp Hàm phù hợp đánh giá khả năng phù hợp của tập lời giải theo yêu cầu bài toán. Hàm này được xây dựng cho từng bài toán với yêu cầu cụ thể. Thông thường trong các bài toán tối ưu hàm này chính là hàm mục tiêu của bài toán. 1.2.4 Các toán tử di truyền a. Toán tử chọn lọc Trong quá trình thực hiện của giải thuật di truyền, sau mỗi lần tiến hoá ta chỉ giữ lại các cá thể có độ phù hợp cao còn các cá thể phù hợp thấp bị loại bỏ. Toán tử chọn lọc thường giữ lại 50% các cá thể phù hợp nhất. Tuy nhiên người ta cũng phát triển nhiều sơ đồ chọn khác nhau nhằm là tăng tính đa dạng của quần thể, tránh sự hội tụ sớm. b. Toán tử lai ghép Bước 1: Tạo ra tập NST để tạo sinh từ quần thể bằng cách chọn ngẫu nhiên N NST từ M NST (M là kích cỡ quần thể). Có nhiều cách chọn: Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 10 Chọn ngẫu nhiên theo thứ tự: lặp N lần việc tạo ngẫu nhiên ra một số nguyên i thuộc khoảng [1, M] để chọn NST thứ i. Chọn theo trọng số: tạo trọng số tích luỹ cho M NST theo công thức: pi = i ; M P k (với bài toán tìm min) (1.1) M −i+1 ; (với bài toán tìm max) M P k (1.2) k−1 pi = k−1 Sau khi có trọng số tích luỹ cho NST, ta lần lượt tạo các xác suất ngẫu nhiên r và duyệt từ NST đầu tiên đến khi gặp NST có trọng số tích luỹ lớn hơn r thì chọn nó. Bước 2: Sau khi chọn được N NST, lần lượt lấy ra từng cặp NST để lai ghép tạo ra hai NST mới. Một số dạng toán tử lai ghép hay dùng là : Lai ghép 1 điểm: chọn ngẫu nhiên một vị trí sau đó hoán vị phần đứng sau vị trí vừa chọn giữa hai NST cha và mẹ để nhận được hai NST con. Lai ghép hai điểm: chọn ngẫu nhiên hai vị trí trong một NST, sau đó hoán vị các giá trị đứng giữa hai điểm đã chọn của hai NST cha mẹ để nhận được hai NST con. Lai ghép mặt nạ: tạo một mặt nạ ngẫu nhiên có số bit bằng chiều dài của NST. Ta sẽ hoán vị các giá trị của hai NST cha và mẹ ở những vị trí tương ứng với vị trí bit 1 của mặt nạ. c. Toán tử đột biến: Toán tử đột biến được xây dựng để tránh việc nhận được giá trị tối ưu cục bộ. Đột biến gây ra thay đổi ngẫu nhiên trên từng bit của NST để tạo ra một NST mới. d. Tạo sinh: Chọn các cá thể từ quần thể hiện thời làm quần thể mới cho lần lặp kế tiếp. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 11 1.3 Giải thuật di truyền kinh điển Giải thuật di truyền kinh điển sử dụng mã hóa nhị phân, mỗi cá thể được mã hóa là một chuỗi nhị phân có chiều dài cố định. 1.3.1 Mã hoá - Biểu diễn các biến bằng véc tơ nhị phân Ta sử dụng véc tơ nhị phân có độ dài L như một NST để biểu diễn giá trị thực của biến x ∈ [lx , ux ]. Độ dài L của NST phụ thuộc vào yêu cầu cụ thể của bài toán. Một bit mã hoá x ứng với một giá trị trong khoảng [0, 2L] sẽ được ánh xạ lên giá trị thực thuộc miền [lx , ux ]. Nhờ đó ta có thể kiểm soát miền giá trị của các biến và tính chính xác của chúng. Tỷ lệ co giãn của ánh xạ được tính như sau: g= u x − lx 2L Giá trị x tương ứng với chuỗi NST nhị phân là: x = lx + decimal(N ST ) ∗ g Trong đó, decimal(NST) là giá trị thập phân của chuỗi NST nhị phân. Chẳng hạn ta muốn tìm cực tiểu một hàm k biến f (x1, . . . , xk ) : Rk → R. Giả sử thêm là mỗi biến xi có thể nhận giá trị trong miền Di = [ai , bi] ⊆ R và f (x1, . . . , xk ) > 0 với mọi xi thuộc Di . Ta muốn tối ưu hoá hàm f với độ chính xác cho trước là 6 số lẻ đối với giá trị của các biến. Rõ ràng là để đạt được độ chính xác như vậy mỗi miền Di được phân cắt thành (bi − ai ) ∗ 106 miền con bằng nhau. Gọi mi là số nguyên nhỏ nhất sao cho: (bi − ai ) ∗ 106 ≤ 2mi − 1 Như vậy, mỗi biến xi được biểu diễn bằng một chuỗi nhị phân có chiều dài mi . Biểu diễn như trên, rõ ràng thoả mãn điều kiện về độ chính xác yêu cầu. Công thức sau tính giá trị thập phân của mỗi chuỗi nhị phân biểu diễn biến xi Xi = ai + decimal(1100...012). Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên bi − ai 2 mi − 1 http://www.lrc-tnu.edu.vn 12 trong đó decimal(chuỗi2) cho biết giá trị thập phân của chuỗi nhị phân đó. Bây giờ, mỗi nhiễm sắc thể (là một lời giải) được biểu diễn bằng k P chuỗi nhị phân có chiều dài L = mi i=1 trong đó m1 bit đầu tiên biểu diễn các giá trị trong khoảng [a1 , b1]; ...; mk bit cuối cùng biểu diễn giá trị trong khoảng [ak , bk ]. Để khởi tạo quần thể, chỉ cần đơn giản tạo pop-size (kích cỡ quần thể) nhiễm sắc thể ngẫu nhiên theo từng bit. Phần còn lại của thuật giải di truyền rất đơn giản: trong mỗi thế hệ, ta lượng giá từng nhiễm sắc thể (tính giá trị hàm f trên các chuỗi biến nhị phân đã được giải mã), chọn quần thể mới thoả phân bố xác suất dựa trên độ thích nghi và thực hiện các phép đột biến và lai để tạo các cá thể thế hệ mới. Sau một số thế hệ, khi không còn cải thiện thêm được gì nữa, nhiễm sắc thể tốt nhất sẽ được xem như lời giải của bài toán tối ưu (thường là toàn cục). Thông thường, ta cho dừng thuật giải di truyền sau một số bước lặp cố định tuỳ thuộc vào điều kiện về tốc độ về tài nguyên máy tính. 1.3.2 Toán tử chọn lọc a) Sử dụng bánh xe Roulette Có nhiều cách để thực hiện toán tử chọn lọc, nói chung đều theo tư tưởng cá thể có độ thích nghi cao hơn thì khả năng được chọn nhiều hơn. Nhưng có lẽ đơn giản và hiệu quả nhất là sử dụng bánh xe Roulette (roulette wheel), mỗi cá thể trong quần thể chiếm một khe có độ rộng tỷ lệ thuận với giá trị phù hợp. Độ rộng của khe được tính bằng tỷ lệ % giá trị phù hợp của một cá thể trên tổng giá trị phù hợp toàn quần thể. Gọi fi là độ phù hợp của cá thể thứ i trong quần thể gồm N cá thể fi khi đó cá thể i sẽ được chọn với xác suất pi = N . Trên vòng tròn P fi i=1 Roulette mỗi chuỗi trong quần thể chiếm một khe có độ rộng tỷ lệ với độ phù hợp của chuỗi. Độ rộng của khe được tính theo tỷ lệ phần trăm Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 13 độ phù hợp của chuỗi với tổng độ phù hợp của toàn quần thể là 100%. b. Thủ tục xếp hạng các cá thể. Trong thủ tục này các cá thể được sắp xếp theo giá trị của hàm mục tiêu. Cá thể đầu tiên là cá thể tốt nhất và cá thể cuối cùng là cá thể tồi nhất. Trong thủ tục này cá thể thứ (N − j) trong dãy sẽ có xác suất j chọn lựa là pN −j = N P k k=1 Các bước tiến hành của thủ tục là: - Sắp xếp các chuỗi theo thứ tự giảm dần của hàm mục tiêu (bài toán cực đại) hoặc theo thứ tự tăng dần của hàm mục tiêu (bài toán cực tiểu). - Tính độ phù hợp của chuỗi theo hình Độ phù hợp của chuỗi fi Hình 1.2: Thủ tục xếp hạng tuyến tính c. Thủ tục chọn lọc cạnh tranh Trong thủ tục này chúng ta tiến hành như sau: - Chọn t cá thể từ quần thể hiện tại một cách ngẫu nhiên và chọn cá thể tốt nhất trong t cá thể đó để sao chép sang quần thể tạm thời. - Lặp lại bước trên N lần chúng ta sẽ có quần thể tạm thời. Giá trị t được gọi là kích cỡ của chọn lọc cạnh tranh. Khi t = 2 chúng ta chọn lọc cạnh tranh nhị phân. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 14 1.3.3 Toán tử lai ghép a. Lai ghép một điểm Lai ghép một điểm được thực hiện rất đơn giản. Với hai cá thể cha mẹ đã chọn P1 , P2; toán tử này cần sinh ngẫu nhiên một vị trí k(1 < k < L), sau đó hai cá thể con được tạo thành bằng cách tráo đổi các gen của cặp cha mẹ tính từ điểm cắt. Chẳng hạn P1 = (1 1 1 0 0 0 1 0 1 0) P2 = (0 1 0 1 1 0 0 1 1 1) là hai chuỗi nhị phân độ dài 10, giả sử điểm cắt đã chọn là k = 7, thế thì hai con được sinh ra là : C1 = (1 1 1 0 0 0 1 1 1 1) C2 = (0 1 0 1 1 0 0 0 1 0) Thủ tục lai ghép đơn giản như sau : Procedure lai1diem(k; P1, P2; var C1, C2); Begin For i := 1 to k do Begin C1[i] := P 1[i]; C2[i] := P 2[i]; End; For i := k + 1 to L do Begin C1[i] := P 2[i]; C2[i] := P 1[i]; End; End; b. Lai ghép nhiều điểm Lai ghép nhiều điểm được thực hiện tương tự như lai ghép một điểm. Với hai cá thể cha mẹ đã chọn P1 , P2 ; toán tử này cần sinh ngẫu nhiên k vị trí i1 , ..., ik ; có thể giả thiết thêm i1 < i2 < ... < ik . Các điểm cắt này Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 15 chia các cá thể đã chọn thành các đoạn được đánh số chẵn lẻ; sau đó hai cá thể con được tạo thành bằng cách tráo đổi các gen của cặp cha mẹ tuỳ theo các đoạn chẵn hay lẻ đã nêu. Trong lai ghép nhiều điểm thì lai ghép hai điểm cắt được quan tâm nhiều nhất. Chẳng hạn P1 = (1 1 1 0 0 0 1 0 1 0) P2 = (0 1 0 1 1 0 0 1 1 1) là hai chuỗi nhị phân độ dài 10, giả sử các điểm cắt đã chọn là 2, 5, 8 thế thì hai con được sinh ra là: C1 = (1 1 1 0 0 0 1 1 1 1) C2 = (0 1 0 1 1 0 0 0 1 0) Thủ tục lai ghép được viết tương tự như trên. c. Lai ghép mặt nạ Loại lai ghép này còn gọi là lai ghép đều; với hai cá thể cha mẹ đã chọn P1 , P2 trước hết phát sinh một chuỗi nhị phân ngẫu nhiên cũng có độ dài L gọi là chuỗi mặt nạ. Sau đó các con được tạo ra dựa trên chuỗi mặt nạ này để quyết định lấy thành phần của cá thể cha hay mẹ. Chẳng hạn gen thứ i của cá thể con C1 được lấy là gen thứ i của P1 nếu bit mặt nạ tương ứng là 1 và lấy gen thứ i của P2 nếu bit mặt nạ là 0. Cá thể con C2 được tạo ngược lại. Ví dụ: Với P1 = (1 1 1 0 0 0 1 0 1 0) P2 = (0 1 0 1 1 0 0 1 1 1) là hai chuỗi nhị phân độ dài 10, giả sử chuỗi bít nhị phân (mặt nạ) được khởi tạo ngẫu nhiên là U = (0 1 1 0 0 1 1 0 0 1) thế thì hai con được sinh ra là : C1 = (0 1 1 1 1 0 1 1 1 0) C2 = (0 1 0 0 0 0 0 0 1 1) tục lai ghép như sau : Procedure lai_mat_na(U, P1, P2; var C1, C2); Begin Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 16 For i := 1 to L do Begin If U [i] = 1 then Begin C1[i] := P 1[i]; C2[i] := P 2[i]; End Else Begin C1[i] := P 2[i]; C2[i] := P 1[i]; End; End; End; 1.3.4 Toán tử đột biến Toán tử đột biến làm thay đổi các thông tin của quần thể ở mức bit (gen). Đột biến làm thay đổi giá trị của một bit bất kỳ theo xác suất pm . Mỗi bit đều có cơ hội đột biến như nhau. Thuật toán đột biến thường dùng là: FOR i := 1 TO m DO IF random[0, 1] < pm THEN invert(P arent[i]); trong đó invert(u) là hàm đảo ngược bit u. 1.3.5 Hàm phù hợp Biến đổi hàm mục tiêu thành hàm phù hợp: Do giá trị phù hợp trong giải thuật di truyền là không âm, nên để áp dụng GA cho bài toán tối ưu ta cần phải chuyển giá trị hàm mục tiêu thành hàm phù hợp. Nếu bài toán tối ưu là cực tiểu hàm mục tiêu g(x) thì ta chuyển sang hàm phù hợp như sau:  C max − g(x) g(x) < Cmax f (x) = 0 ngược lại Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn