Giải thuật gen và một số bài toán về giải thuật gen

Giải thuật gen và một số bài toán về giải thuật gen CHƯƠNG I: KHÁI QUÁT VỀ GIẢI THUẬT GEN CHƯƠNG II: CƠ SỞ TOÁN HỌC CỦA GT GEN CHƯƠNG III: HIỆN THỰC GIẢI THUẬT GEN CHƯƠNG IV: SỰ CẢI TIẾN VÀ ỨNG DỤNG CỦA GIẢI THUẬT GEN CHƯƠNG V: BÀI TOÁN HỘP ĐEN CHƯƠNG VI: BÀI TOÁN TỐI ƯU HOÁ CHƯƠNG VII: BÀI TOÁN NGƯỜI TÙ( Prisoner's Dilemma Problem) CHƯƠNG VIII: BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT(The Traveling Salesman Problem - TSP) CHƯƠNG I KHÁI QUÁT VỀ GIẢI THUẬT GEN ---------*****----------- I-KHÁI NIỆM GIẢI THUẬT GEN ? Giải thuật gen (GAs) là giải thuật tìm kiếm, chọn lựa các giải pháp tối ưu để giải quyết các bài toán khác nhau dựa trên cơ chế chọn lọc tự nhiên của ngành di truyền học. Trong cơ thể cơ thể sinh vật, các gen liên kiết với nhau theo cấu trúc dạng chuỗi gọi là nhiễm sắc thể , nó đặc trưng cho mỗi loài và quyết định sự sống còn của cơ thể đó. Trong tự nhiên một loài muốn tồn tại phải thích nghi với môi trường ,cơ thề sống nào thích nghi với môi trường hơn thì sẽ tồn tại và sinh sản với số lượng ngày càng nhiều hơn , trái lại những loài không thích nghi với môi trường sẽ dần dần bị diệt chủng .Môi trường tự nhiên luôn biến đổi ,nên cấu trúc nhiễm sắc thể cũng thay đổi để thích nghi với môi trường ,và ở thế hệ sau luôn có độ thích nghi cao hơn ở thế hệ trước .Cấu trúc này có được nhờ vào sự trao đổi thông tin ngẫu nhiên với môi trường bên ngoài hay giữa chúng với nhau . Dựa vào đó các nhà khoa học máy tính xây dựng nên một giải thuật tìm kiếm tinh tế dựa trên cơ sở chọn lọc tự nhiên và quy luật tiến hóa, gọi là giải thuật gen (Genetic Algorithms) Mục tiêu nghiên cứu của GAs là : -Trừu tượng hóa và diễn đạt chính xác về các quá trình thích nghi trong hệ thống tự nhiên . -Thiết kế những phần mềm về hệ thống nhân tạo nhằm duy trì các cơ chế quan trọng của hệ thống tự nhiên . Những mục tiêu này đã dẫn đến những khám phá quan trọng trong hệ thống khoa học tự nhiên lẫn nhân tạo . Vấn đề trọng tâm của việc nghiên cứu GAs là tính mạnh mẻ của giải thuật ,sự cân bằng giữa tính hiệu quả và sự cần thiết để có thể tồn tại trong nhiều môi trường khác nhau. GAs ra đời và phát triễn dựa trên quá trình tiến hóa trong tự nhiên và đã được ứng dụng thành công trong nhiều lĩnh vực nhất là tối ưu hóa và máy học . II-GIẢI THUẬT GEN VỚI CÁC PHƯƠNG PHÁP TRUYỀN THỐNG : GAs khác với những sự tối ưu hóa thông thường và những giải thuật tìm kiếm khác bởi 4 điểm sau : 1-GAs làm việc với sự mã hóa môt bộ các thông số , chứ không phải bản thân các thông số . 2-GAs tìm kiếm từ một số điểm dân cư , chứ không phải từ một điểm. 3-GAs sử dụng các thông tin trả giá (payoff) của hàm mục tiêu chứ không phải đạo hàm (derivatives) hay những tri thức phụ khác. 4-GAs sử dụng các luật chuyển đổi theo xác suất ,chứ không phải các luật chuyển đổi xác định. GAs đòi hỏi một tập hợp các thông số tự nhiên của bài toán tối ưu để mã hóa thành các chuỗi có chiều dài hữu hạn , dựa trên một số hữu hạn các ký tự . Để hiểu rõ ta xét bài toán tối ưu đơn giản sau đây : Ví du: tối ưu hóa hàm f(x) = x2 trên khoảng nguyên [0,31]. Chúng ta muốn tìm cực đại của hàm f(x) = x2 trên đoạn số nguyên [0,31] .Bằng phương pháp truyền thống , chúng ta lần lượt tính bình phương của x theo các giá trị từ 0 đến 31 ,cho đến khi chúng ta chọn được giá trị cao nhất của hàm mục tiêu . Với GAs bước đầu tiên của quá trình tối ưu hóa là mã hóa x thành một chuỗi có chiều dài xác định .Có nhiều cách đề mã hóa x , chúng ta hãy xét bài toán tối ưu với cách mã hóa tự nhiên . Giả sử chúng ta có bài toán tắt mở một cái hộp đen ,với một dãy 5 công tắc ở đầu vào . Mỗi tổ hợp các trạng thái của 5 công tắc ứng với một tín hiệu ra ( output ) của hàm f , biễu diễn theo toán học là f = f(s) , trong đó s là một tổ hợp các trạng thái cụ thể của 5 công tắc . Mục tiêu của bài toán là phải đặt các công tắc như thế nào để đạt được giá trị tối đa có thể có của hàm f . Với những phương pháp khác của bài toán tối ưu , chúng ta có thể làm việc trực tiếp với bộ các thông số ( việc đặt các công tắc ) và bậc tắt các công tắc từ một trạng thái này sang trạng thái khác bằng cách dùng những qui tắc chuyển đổi theo phương pháp chuyên biệt . Với GAs ,đầu tiên chúng ta mã hóa dãy các công tắc theo một chuỗi có chiều dài xác định . Cách mã hóa đơn giản như sau : dùng chuỗi dài 5 ký tự gồm các giá trị 0 và 1 , với quy ước tắt = ‘0’ , mở = ’1’.Thí dụ :chuỗi 11110 nghĩa là 4 công tắc đầu mở , công tắc thứ 5 tắt .Bài toán tối ưu hóa hộp đen với 5 công tắc tắt-mở . GAs không yêu cầu bạn biết nguyên tắc làm việc của hộp đen . Trong nhiều phương pháp tối ưu ,chúng ta di chuyển thận trọng từ một điểm trong không gian quyết định đến điểm kế bằng cách dùng vài luật chuyển đổi để xác định điểm kế tiếp . Phương pháp điểm-đến-điểm này khá nguy hiểm , vì chắc chắn sẽ chỉ ra những đỉnh sai trong không gian tìm kiếm đa hình (multimodal) .Trái lại GAs làm việc với một cơ sỡ dữ liệu phong phú gồm có nhiều điểm đồng thời (một dân số các chuỗi ),thực hiện leo nhiều điểm cùng lúc .Do đó , xác xuất gặp đỉnh sai được giảm nhiều so với các phương pháp điểm-đến-điểm .Bài toán hộp đen là một ví dụ .những kỹ thuật khác để giải quyết bài toán này có thể bắt đầu với một bộ các thiết lập các công tắc ,áp dụng vài quy tắc chuyển đổi , và sinh ra một dãy các công tắc thử mới . GAs bắt đầu với một dân số các chuỗi và sau đó sẽ phát sinh thành công những dân số chuỗi khác . Trở lại bài công tắc một sự bắt đầu ngẫu nhiên bằng cách tung đồng tiền ( ngửa =’1’, xấp =’0’ ) có thể sinh ra dân số ban đầu có kích thước n= 4 như sau: 01101 11000 01000 10011 Sau bước khởi đầu này, những dân số thành công sẽ được phát sinh ra bằng cách dùng GAs . Bằng cách làm việc từ một dân số đa dạng , thích nghi cao ,thay vì một điểm đơn , GAs trung thành với những ngạn ngữ cổ cho rằng sẽ có sự an toàn trong một số đông ; chúng ta sẽ sớm hiểu ra cách mà những đặc trưng song song này đóng góp vào sức mạnh của GAs . Nhiều kỹ thuật tìm kiếm yêu cầu nhiều thông tin phụ để làm việc hiệu quả hơn .Thí dụ, kỹ thuật gradient cần đạo hàm ( được tính tóan bằng giải tích hay bằng số) để có thể leo lên đỉnh hiện tại , và những thủ tục tìm kiếm cục bộ khác giống như kỹ thuật greedy của sự tối ưu hóa tổ hợp đòi hỏi truy xuất hầu hết những thông số cho trong bảng .Trái lại GAs không cần tất cả những thông tin phụ này .Để thực hiện một tìm kiếm hiệu quả cho những cấu trúc ngày càng tốt hơn , chúng chỉ yêu cầu các giá trị của hàm mục tiêu liên kết với các nhiễm sắc thể .Những đặc tính này làm cho GAs là một phương pháp chuẩn mực hơn nhiều các phương pháp tìm kiếm khác . III-GIẢI THUẬT GEN ĐƠN GIẢN: GAs là giải thuật tìm kiếm dựa trên cơ chế chọn lọc nhân tạo và sự tiến hoá của các gen . Các gen liên kết nhau tạo thành chuỗi gọi là nhiễm sắc thể , quyết định quá trình hoạt động của cơ thể sống. Các chuỗi nhiễm sắc thể được biểu diễn bằng chuỗi các số nhị phân 0 và 1, mỗi một thành phần trong chuỗi gọi là Allele . Một GAs đơn giản cho những kết quả tốt trong nhiều bài toán thực tế bao gồm 3 thao tác: Sinh sản (hay tái tạo) (Reproduction). Ghép chéo (Crossover) . Đột biến (Mutation) . 1-SINH SẢN: Sinh sản là một quá trình trong đó các chuỗi cá thể được ghép lại tuỳ theo các giá trị của hàm mục tiêu f ( các nhà sinh vật học gọi hàm này là hàm thích nghi ) .Toán tử này được xem là quá trình chọn lọc trong tự nhiên . Hàm mục tiêu f(i) được gán cho mỗi cá thể trong dân số .Thao tác sinh sản ( chọn cha mẹ) được điều khiển bằng cách quay bánh xe roulette , trong đó mỗi chuỗi trong dân số chiếm một khe có kích thước tỉ lệ với độ thích nghi (fitness ) của nó trên bánh xe . Giả sử dân số mẫu của bốn chuỗi trong bài toán hộp đen có các giá trị hàm thích nghi ( hàm mục tiêu ) như trong bảng 1.1. Lấy tổng độ thích nghi của 4 chuỗi , chúng ta được 1170 . Tỷ lệ % của độ thích nghi tổng của dân số được chỉ ra trong bảng 1.1 . BẢNG 1.1 : Các chuỗi của bài toán mẫu và các giá trị thích nghi Số TT Chuỗi Độ thích nghi % trong tổng số 1 01101 169 14.4 2 11000 576 49.2 3 01000 64 5.5 4 10011 361 30.9 Tổng cộng 1170 100.0 Bánh xe roulette được đánh trọng số phù hợp cho sự sinh sản của thế hệ này được thể hiện trên hình 1.1. HÌNH 1.1 : Sự sinh sản đơn giản phân bố các chuỗi con cháu nhờ sử dụng bánh xe roulette với các khe hở tỷ lệ với độ thích nghi . Bánh xe mẫu được xác định dựa trên bảng 1.1 và 1.2 14..4 % 30.9 % 5.5 % 49.2 % ¯ ¯¬ ¬­®¯¬ ¬ ¬¬ ­ ® ¯ Để sinh sản , chúng ta chỉ cần quay bánh xe roulette 4 lần đối với bài toán này , chuỗi 1 có giá trị thích nghi là 169 , đại diện cho 14,4 % so với tổng độ thích nghi . Kết quả là chuỗi 1 chiếm 14.4% bánh xe roulette dốc , và cứ mỗi lần quay 1 chuổi chiếm 0,144 . Mỗi khi chúng ta yêu cầu 1 thê hệ khác , 1 vòng quay đơn giản của bánh xe roulette đánh trọng số sẽ chọn ra được ứng cử viên để sinh sản . Bằng cách này , những chuỗi thích nghi hơn sẽ có 1 số lượng con cháu lớn hơn trong các thế hệ kế tiếp. 2-GHÉP CHÉO: Mỗi khi một chuỗi được chọn để sinh sản , một bản sao chính xác của chuỗi đó sẽ được tạo ra . Các bản sao này được đưa vào bể ghép đôi (mating pool) việc ghép chéo đơn giản có thể được tiến hành theo 2 bước : Đầu tiên các thành viên của các chuỗi đơn giản mới ở trong bể ghép ,được ghép đôi với nhau một cách ngẫu nhiên .Sau đó, mỗi cặp chuỗi sẽ trãi qua việc ghép chéo như sau : một số nguyên chỉ vị trí k dọc theo chuỗi sẽ được chọn lựa qua giá trị ngẫu nhiên nằm trong khoảng từ 1 đến chiều dài chuỗi l trừ 1 [1, l-1 ].Hai chuỗi mới sẽ được tạo ra bằng cách hoán đổi tất cả các ký tự nằm giữa vị trí k +1 và 1 .Thí dụ ,xét 2 chuỗi A1 và A2 từ dân số ban đầu trong ví dụ : A1 = 0110 | 1 A2 = 1100 | 0 Giả sử trong khi chọn một số ngẫu nhiên nằm trong khoảng từ 1 và 4 , chúng ta được k = 4 ( như được chỉ ra bằng dấu ngăn cách | ) .Kết quả của việc ghép chéo làm sinh ra 2 chuỗi mới A’1 và A’2 trong đó dấu ‘ có nghĩa là các chuỗi này là phần tử của thế hệ mới . A’1 = 01100 A’2 = 11001 Cơ chế sinh sản và ghép chéo đơn giản , bao gồm việc sinh số ngẫu nhiên , sao chép chuỗi và trao đổi các chuỗi thành phần .Tuy nhiên , điểm cần nhấn mạnh là việc sinh sản và trao đôi thông tin có cấu trúc (dù là một cách ngẫu nhiên) của quá trình ghép chéo làm cho các giải thuật gen tăng sức mạnh. 3-ĐỘT BIẾN: Nếu sự sinh sản theo độ thích nghi kết hợp với sự ghép chéo làm cho GAs có năng lực xử lý tốt hơn , thì sự đột biến đóng một vai trò quyết định thứ 2 trong hoạt động của GAs .Sự đột biến là cần thiết bởi vì , cho dù sự sinh sản và ghép chéo đã tìm kiếm hiệu quả và tái kết hợp lại các ký hiệu lại với nhau , nhưng thỉnh thoảng chúng có thể trở nên quá sốt sắng và làm mất một vài gen hữu ích nào đó (bit 1 hay bit 0 tại những vị trí đặc biệt nào đó) . Trong các hệ thống gen nhân tạo, toán tử đột biến sẽ chống lại sự mất mát không khôi phục được đó . Trong GAs đơn giản , đột biến là sự thay đổi ngẫu nhiên và không thường xuyên (với xác suất nhỏ) trị số vị trí của một chuỗi. Trong việc mã hóa nhị phân của bài toán hộp đen , cónghĩa là chỉ cần đổi 1 thành 0 và ngược lại . Tự thân no, sự đột biến là một hoạt động ngẫu nhiên trong không gian chuỗi , khi được dùng cùng với sự sinh sản và ghép chéo , nó sẽ là một chính sách bảo hiểm chống lại nguy cơ mất mát những ký hiệu quan trọng . Ba toán hạng sinh sản, ghép chéo và đột biến được áp dụng lặp đi lặp lại để tạo ra nhiễm sắc thể mới, cho đến khi vượt quá kích thước dân số đã định thì dừng lại,coi như một thế hệ mới tương ứng với một quá trình sinh sản đã được tạo xong bao gồm một dân số các chuỗi nhiễm sắc thể, trong GAs có thể sinh ra nhiều thế hệ. 4-SƠ ĐỒ GIẢI THUẬT GEN : Gas bao gồm các bước sau : 1. Khởi tạo 1 dân số (population)ban đầu của các chuổi nhiễm sắc thể . 2. Xác định giá trị mục tiêu cho mỗi một chuỗi nhiễm sắc thể . 3. Tạo các chuổi nhiễm sắc thể mới bằng sinh sản từ các chuổi nhiễm sắc thể hiện tại , có tính vấn đề ghép chéo và đột biến xảy (nếu có) 4. Xác định hàm mục tiêu cho các chuổi nhiễm sắc thể mới và đưa nó vào trong một dân số mới. 5. Nếu điều kiện dừng thỏa thì giải thuật dừng lại và trả về chuỗi nhiễm sắc thể tốt nhất cùng với gía trị mục tiêu của nó , nếu không thì quay lại bước 3. Sơ đồ giải thuật Gen :(hình 1.2) Bước 1: Tạo một dân số ban đầu của các chuổi nhiễm sắc thể . Bước 2: Xác định giá trị Hàm Mục tiêu của các chuổi nhiễm sắc thể. Bước 3: Tạo các chuổi nhiễm sắc thể mới bằng cách sinh sản từ các chuổi nhiễm sắc thể hiện tại (Có xét đến ghép chéo và đột biến xảy ra ). Bước 4: Tính toán các giá trị mục tiêu của các chuổi nhiễm sắc thể mới và đưa nó vào một dân số mới. Bước 5: Nếu điều kiện dừng đã thoã thì dừng lại và trả về yêu cầu của bài toán ,nếu không thì quay lại bước 3 . IV-HIỆN THỰC GIẢI THUẬT GEN Chúng ta hãy áp dụng GAs theo từng bước một , cho một bài toán tối ưu hóa chuyên biệt .Xét bài toán tìm giá trị lớn nhất của hàm f(x)=x2 với x thuộc đoạn [0,31] . Để sử dụng GAs, trước tiên chúng ta phải mã hóa những biến quyết định của bài toán thành một chuỗi có chiều dài xác định nào đó .Ở ví dụ này , chúng ta mã hóa biến x thành một số nguyên nhị phân không dấu có độ dài bằng 5 . Vơí một số nguyên nhị phân không dấu 5 bit , chúng ta diểu diễn được số từ 0 (00000) đến 31(11111) .Bằng hàm mục tiêu đã xác định và phương pháp mã hóa trên , chúng ta sẽ mô phỏng một thế hệ đơn giản qua GAs , với các thao tác : sinh sản ,ghép chéo và đột biến . Đầu tiên chúng ta hãy chọn ngẫu nhiên một dân số ban đầu có kích thước 4 , bằng cách gieo đồng tiền 20 lần (xấp = 0; ngửa = 1) . Chúng ta có thể bỏ qua bước này bằng cách dùng dân số ban đầu của bài toán đặt dãy công tắc cho hộp đen .Hãy xem dân số này biễu diễn ở bên trái bảng 1.2 , chúng ta sẽ thấy giá trị giải mã của x , độ thích nghi (hay chính là giá trị của hàm mục tiêu f(x)) .Để giá trị thích nghi f(x) được tính từ chuỗi như thế nào hãy xem chuỗi thứ 3 của dân số ban đầu , chuỗi 01000 . Giải mã chuỗi này theo số nguyên nhị phân không dấu chúng ta được x = 8. Để tính độ thích nghi hay chính là hàm mục tiêu , chúng ta chỉ việc lấy bình phương của x . Vậy f(x)=64.Các giá trị khác tính tương tự . BẢNG 1.2: GAs tính bằng tay Số Dân số Giá trị x Độ thích pselectI Số đếm tt ban đầu nghi fI fI thật từ bánh xe (chọn ngẫu nhiên) Sf f roulette 1 01101 13 169 0.14 0.58 1 2 11000 24 576 0.49 1.97 2 3 01000 8 64 0.06 0.22 0 4 10011 19 361 0.31 1.23 1 ------------------------------------------------------------------------------------------------- Sum 1170 1.00 4.00 4.0 Average 293 0.25 1.00 1.0 Max 576 0.49 1.97 2.0 Một thế hệ mới bắt đầu bằng sự sinh sản .Chúng ta chọn bể ghép đôi cho các thế hệ kế tiếp bằng cách quay bánh xe roulet 4 lần .Mô phỏng thực tế quá trình này theo cách tung đồng tiền ,kềt quả là chuỗi 1 và chuỗi 4 nhận được một bản sao trong bể ghép đôi, chuỗi 2 nhận được 2 và chuỗi 3 không nhận được gì. So sánh điều này với số lượng các bản sao mong muốn (n * pselecti ), chúng ta nhận tấy: chuỗi tốt nhất nhận được nhiều bản sao, chuỗi trung bình thì giữ nguyên, chuỗi xấu nhất sẽ chết. Bốn bản sao này ( 1 của chuỗi 1, 2 của chuỗi 2, 1 của chuỗi 4 ) sẽ được đưa vào ghép chéo. Quá trình ghép chéo đơn giản gồm 2 bước: -Chọn cặp ghép chéo một cách ngẫu nhiên. -Ghép chéo các cặp chuỗi. Chọn vị trí ghép một cách ngẫu nhiên bằng cách tung đồng tiền. Xem lại bảng 1.2, lựa chọn ngẫu nhiên đã chọn chuỗi 1 và 2, rồi chuỗi 3 và 4 để ghép chéo. Chuỗi 1 và 2 được ghép chéo ở vị trí thứ 4, nghĩa là 2 chuỗi 01101 và 11000 được ghép chéo để tạo ra các chuỗi mới là 01100 và 11001. Chuỗi 3 và 4 được ghép chéo tương tự ở vị trí thứ 2. Kết quả của việc ghép chéo sẽ sinh ra 4 chuỗi như trong bảng 1.2 (tiếp) Bể ghép đôi Cặp ghép đôi vị trí ghép Dân số Trị x f(x)=x2 sau sinh sản với chuỗi (ngẫu nhiên) mới ------------------------------------------------------------------------------------------------------ 0110|1 2 4 01100 12 144 1100|0 1 4 11001 25 625 11|000 4 2 11011 27 729 10|011 3 2 10000 16 256 ------------------------------------------------------------------------------------------------------ Sum 1754 Average 439 Max 729 Thao tác cuối cùng là đột biến, thực hiện trên cơ sở thay đổi giá trị bit ở các vị trí nào đó. Giả sử xác suất đột biến trong lần kiểm tra này là 0.001. Với 20 vị trí bit khả chuyển, chúng ta mong đợi 20 * 0.001 = 0.02 bit chịu đột biến trong một thế hệ đã cho. Với giá trị xác suất đột biến là 0.02, không có bit nào chịu đột biến trong thế hệ này. Kết quả là không có vị trí bit nào chịu sự thay đổi từ 0 thành 1 hay ngược lại. Qua thao tác sinh sản, ghép chéo và đột biến, một dân số mới đã sẵn sàng cho việc thử nghiệm.Để thực hiện điều này, chúng ta lại giải mã các chuỗi dân số mới được tạo bởi giải thuật gen đơn giản, và tính giá trị hàm tối ưu từ giá trị x. Kết quả của một thế hệ dược trình bày bên phải bảng 1.2. Nhìn vào bảng chúng ta thấy các thông số :tổng thích nghi(Sum) ,trị thích nghi trung bình (Average) và trị thích nghi cực đại (Max) đều được cải thiện chỉ qua một thế hệ. Cụ thể Sum tăng từ 1170 lên 1754, Average tăng từ 293 lên 439, Max tăng từ 576 lên 729. Dù rằng quá trình ngẫu nhiên đã giúp đỡ để tạo nên tình huống này, chúng ta thấy rõ ràng sự cải thiện không hề là may mắn. Chuỗi tốt nhất của thế hệ đầu (11000) nhận được 2 bản sao, vì nó có mức độ hoàn thành cao trên trung bình. Khi nó kết hợp ngẫu nhiên với chuỗi có mức độ hoàn thành cao kế tiếp(10011) và ghép chéo tại vị trí thứ 2 (tất nhiên bằng ngẫu nhiên) thì một trong hai chuỗi kết quả là(11011) chứng tỏ rằng đó thật là một lựa chọn tốt. Sự kiện này là một minh hoạ tuyệt vời cho ý tưởng và các ký hiệu được phát triển tương tự trước đó . Trong trường hợp này, kết quả lý tưởng nhất là sự kết hợp của 2 ký hiệu trên trung bình, là hai chuỗi 11--- và ---11 . Mặc dù mọi lý lẽ ở đây vẫn có cái gì đó mang tính nghiệm suy (heuristic), chúng ta bắt đầu thấy được hiệu quả của giải thuật gen là khả năng tìm kiếm hiệu quả và mạnh mẽ. Trong phần sau, chúng ta mở rộng hiểu biết về giải thuật gen qua các giản đồ và các mẫu tương đồng. V-NHỮNG TƯƠNG ĐỒNG: Trong một quá trình tìm kiếm chỉ cho các giá trị trả giá payoff (giá trị thích nghi) (tức cho f(x) mà không cho x) ,thông tin nào được chứa trong các chuỗi và các giá trị hàm mục tiêu sẽ giúp định hướng quá trình tìm kiếm trực tiếp theo huớng cải thiện kết quả ? Để trả lời câu hỏi này hãy xem lại ,các chuỗi và các giá trị thích nghi ban đầu trong bản 1.1 từ phần mô phỏng bài toán hộp đen trước đây , thể hiện như sau : Chuỗi Độ thích nghi 01101 169 11000 576 01000 64 10011 361 Thông tin quan trọng nào chứa trong chuồi dân số hướng dẫn tìm kiếm trực tiếp theo chiều hướng cải thiện ? Nhìn sơ qua,chúng ta chỉ thấy các chuỗi độc lập và độ thích nghi tương ứng ,chẳng có gì đặc biệt. Nhưng nếu nhìn kỹ, chúng ta nhận thấy có những điểm tương đồng nhất định giữa các chuỗi.Khảo sát sâu hơn các điểm tương đồng này ,chúng ta thấy có những mẫu chuỗi nào đó dường như gắn bó mật thiết với chất lượng tốt .Có một lý do hợp lý nào đó để tiến hành trộn và ghép cặp một vài chuỗi con có độ tương quan cao với sự thành công trong quá khứ,ghép với nhau .Ví dụ, trong mẫu dân số này ,những chuỗi bắt đầu bởi 1 dường như là nằm trong số những chuỗi tốt nhất.Có lẽ đây là thành phần quan trọng trong việc tối ưu hoá hàm? Qua hàm số đã cho ( f(x) = x2) và lối mã hoá đã biết (dùng số nguyên không dấu 5 bit) ,chúng ta có thể kiểm nghiệm điều này.Ơ đây có hai điều phân biệt :một là, chúng ta tìm kiếm sự tương đồng giữa các chuỗi dân số; hai là,chúng ta mong đợi mối liên hệ nhân quảgiữa điểm tương đồng này và độ thích nghi cao .Khi thực hiện điều này, chúng ta sử dụng tính phong phú của các thông tin mới trong việc hướng dẫn tìm kiếm. VI-CÁC MẪU SƠ ĐỒ (Schemata): Vì các điểm tương đồng quan trọng trong số các chuỗi thích nghi cao có thể định hướng cho việc tìm kiếm, chúng ta hãy xem xét một chuỗi có thể tương đồng với những chuỗi khác như thế nào. Một chuỗi đại diện cho các lớp chuỗi tương đồng khác tại các vị trí nào đó, theo cách thức nào? Cốt lõi (khung) của các sơ đồ sẽ trả lời những câu hỏi này . Một sơ đồ (Holland, 1968,1975) và một khuôn mẫu tương tự , miêu tả một tập con các chuỗi tương đồng nhau , tại những vị trí nào đó của chuỗi .Một lần nữa chúng ta giới hạn sự thảo luận trên bộ ký tự nhị phân {0,1} mà không làm mất tính tổng quát .Nếu thêm vào bộ ký tự nhị phân một ký hiệu đặc biệt là dấu * ,chúng ta có thể tạo ra các chuỗi (sơ đồ) trên bộ kýtự tam phân {0,1 ,*} về ý nghĩa ,sơ đồ là một thiết bị để so trùng các mẫu : một sơ đồ gọi là trùng khớp với một chuỗi cụ thể ,nếu ở một vị trí của sơ đồ chúng ta có 1 so trùng với 1 của chuỗi , 0 so trùng với 0 , * so trùng với cả 0 và 1 .Thí dụ ,hãy xem xét một chuỗi và một sơ đồ dài 5 ký tự .Sơ đồ 0000 sẽ so trùng với 2 chuỗi {10000, 00000}. Chuỗi *111* mô tả tập con gồm bốn phần tử {01110 , 01111, 11110, 11111} .Sơ đồ 0*1** sẽ so trùng với bất cứ chuỗi nào trong số 8 chuỗi có chiều dài bằng 5 ,bắt đầu bằng ký tự 0 và có ký tự 1 ở vị trí thứ 3 (từ trái sang phải) . Ta thấy , ý tưởng về sơ đồ cho chúng ta một phương thức mạnh mẽ và hữu hiệu để diễn đạt tất cả những sự tương đồng trong số những chuỗi có chiều dài hữu hạn , qua một bộ ký tự hữu hạn . Chúng ta nhấn mạnh rằng chỉ có * là siêu ký hiệu (tức ký hiệu diễn tả cho các ký hiệu khác) , nó không bao giờ được xử lý tường minh bằng GAs .Nó chỉ đơn giản là một phương tiện cho ghi chép cho phép miêu tả tất cả những sự tương đồng có thể có trong số các chuỗi có chiều dài và có bộ ký tự xác định . Việc tính toán số sơ đồ có thể có làm sáng tỏ thêm cho thí dụ .Nếu chuỗi dân số có chiều dài l = 5 ,chúng ta có 3.3.3.3.3 = 35 khuôn mẫu tương đồng khác nhau ,vì một trong số 5 vị trí có thể là 0,1 hay * . một cách tổng quát cho bảng ký tự gồm có k ký tự , xét các sơ đồ có chiều dài l , chúng ta sẽ xây dựng được (k+1) l sơ đồ . Mới xem qua hình như sơ đồ làm cho việc tìm kiếm khó khăn hơn . Một bản ký tự gồm k phần tử chỉ có k1 chuỗi khác nhau có chiều dài bằng l .Vậy tại sao xem xét đến (k +1)1 sơ đồ và làm mở rộng không gian tìm kiếm ? Trở lại ví dụ cũ với l = 5 , k=2 , ta có 25=32 chuỗi khác nhau tại sao lại thêm rắc rối với 35= 243 sơ đồ ? thật ra các lý lẽ đã nêu ra trước đây làm cho mọi việc dễ dàng hơn .Hãy xem lại các khắp lượt danh sách 4 chuỗi cùng với giá trị thích nghi của chúng và cố hình dung thì chúng ta phải làm gì tiếp theo? Chúng ta nhận thấy rằng nếu chỉ xem xét các chuỗi riêng rẽ thì chúng ta chỉ có 4 mẫu thông tin ,nhưng nếu chúng ta xem xét các chuỗi , các giá trị thích nghi và những sự tương đồng của chúng trong số các chuỗi dân số ,chúng ta sẽ có thêm nhiều thông tin mới ,giúp định hướng cho quá trình tìm kiếm .Vậy khi xem xét những sự tương đồng ,chúng ta nhận thêm được bao nhiêu thông tin ? Câu trả lời liên quan đến số các sơ đồ duy nhất chứa trong dân số. Để tính chính xác con số này đòi hỏi có kiến thức về các chuỗi trong trong một dân số đặc thù .Để tính giới hạn trong một dân số cụ thể ,chúng ta phải đếm số lượng các sơ đồ chứa trong một chuỗi riêng biệt , sau đó chúng ta tính đến một giới hạn trên của tổng số sơ đồ trong dân số. Để thấy rõ ,hãy xem xét một chuỗi đơn có chiều dài là 5 :11111 .Chuỗi này là một phần tử của 25 sơ đồ ,bởi vì mỗi vị trí có thể nhận giá trị thật của nó (0 hay 1) hoặc một ký tự thay thế ( * ) .Một cách tổng quát ,một chuỗi riêng biệt sẽ chứa 2l sơ đồ ,dẫn đến kết quả là một dân số kích thước n sẽ chứa một số lượng lớn sơ đồ nằm trong khoảng từ 21 đến n*21 ,tùy thuộc vào tính đa dạng của dân số .Điều này xác minh cho trực giác trước đó của chúng ta .Động cơ thúc đẩy nguyên thủy của sự xem xét những tương đồng quan trọng chính là để thu nhập được nhiều thông tin hơn nhằm hướng dẫn quá trình tìm kiếm .Việc tìm kiếm các đối số chỉ ra rằng một gia tài thông tin về những tương đồng quan trọng thật ra được chứa trong những dân số có kích thước vừa phải .chúng ta sẽ nghiên cứu cách thức khai thác thông tin một cách hiệu quả của GAs .Trong tình hình này ,một số quá trình xử lý song song là cần thiết ,nếu chúng muốn dùng tất cả các thông tin này thật đúng lúc .Có bao nhiêu trong số 21 đến n * 21 sơ đồ sẽ được GAs xử lý thật hữu ích ? Hãy xem xét ảnh hưởng của quá trình sing sản , ghép chéo và đột biến trong việc tăng trưởng hay sút giảm của những sơ đồ quan trọng ,từ thế hệ này sang thế hệ khác .Hiệu quả của sự sinh sản trên một sơ đồ cụ thể dễ dàng xác định ; từ những chuỗi thích nghi cao hơn ,một cách bình quân chúng ta lấy trị số gia tăng từ trước đến giờ đối với những mẫu tương đồng tốt nhất đã quan sát được .Tuy nhiên , sự sinh sản của những mẫu đơn độc không tạo thêm những điểm mới trong không tìm kiếm .Khi bắt đầu ghép chéo, điều gì sẽ xảy ra với một sơ đồ cụ thể ? Sự ghép chéo sẽ để lại một sơ đồ không bị tổn thương nếu sự ghép chéo ấy không cắt sơ đồ ,nhưng nó có thể bị phá vỡ một sơ đồ khi nó cắt .Thí dụ : xét 2 sơ đồ 1***0 và **11* .Sơ đồ thứ nhất gần như sẽ bị phá vỡ khi ghép chéo ,trong khi sơ đồ thứ hai tương đối ít bị phá vỡ hơn .Kết quả là ,các sơ đồ có chiều dài ngắn được để lại đơn độc qua quá trình ghép chéo ,và được sinh sản