Đề tài Giải thuật Gen và bài toán tìm đường đi ngắn nhất

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ị