Đề tài 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 theo một tỷ lệ lấy mẫu tốt qua quá trình sinh sản .Thông thường sự đột biến có tỷ lệ thấp sẽ không làm phá vỡ một sơ đồ cụ thể một cách thường xuyên .Sau nhiều quan sát ,chúng ta đi đến kết luận: các sơ đồ có chiều dài xác định ngắn ,độ thích nghi cao (chúng ta gọi là những khối gạch xây) sẽ được nhân giống từ thế hệ này sang thế hệ khác bởi các mẫu gia tăng theo hàm mũ ,cho đến kết quả tốt nhất quan sát được .Tất cả chúng sẽ được xử lý song song mà không cần tốn thêm vùng nhớ đặc biệt so với dân số của n chuỗi . VII-CÁC THUẬT NGỮ: Các GAs đã bắt rễ sâu trong cả ngành di truyền học tự nhiên lẫn nghành khoa học máy tính ,nên những thuật ngữ được sử dụng trong các tài liệu về GAs là sự pha trộn thuật ngữ giữa các ngành tự nhiên và nhân tạo . Mãi đến gần đây ,chúng ta mới tập trung nghiên cứu khía cạnh nhân tạo của các dòng lai của GAs ,và bàn về các chuỗi , bảng ký tự ,vị trí chuỗi …Chúng ta hãy duyệt lại sự tương ứng giữa các thuật ngữ và tên tương ứng trong giới tự nhiên , liên hệ với sự phát triển của các tài liệu về GAs và cũng để tránh các sơ suất trong phát biểu . Chuỗi (strings) trong hệ gen tương tự như nhiễm sắc thể (chromosomes ) trong hệ thống sinh học .Trong tự nhiên ,một hay nhiều nhiễm sắc thể sẽ liên kết lại để tạo ra một chỉ thị di truyền chung để xây dựng và điều khiển một cơ thể sống nào đó .Trong tự nhiên , gói di truyền chung ( total genetic package) được gọi là kiểu gen ( genotype) .Trong hệ thống nhân tạo , một gói các chuỗi được gọi là một cấu trúc (structure) (trong những chương đầu , cấu trúc chỉ chứa một chuỗi đơn mà thôi,do đó chữ cấu trúc và chuỗi có thể thay đổi cho nhau, cho đến khi nào cần phân biệt chúng ) .Trong tự nhiên gen nhân tạo ,các cấu trúc được giải mã để tạo nên một tập thông số cụ thể ,sự luân phiên của giải pháp hay điểm (trong không gian lời giải). Nhà thiết kế hệ thống gen nhân tạo tạo sự luân phiên để để mã hóa cả các thông số bằng số lẫn không phải bằng số. Theo thuật ngữ sinh học , chúng ta nói nhiễm sắc thể bao gồm các gen .các gen này chiếm một giá trị nào đó gọi là gen tương ứng (alleles) .Trong di truyền học , vị trí của một gen (ổ gen của nó-locus) được chỉ riêng ra từ chức năng của gen đó .Thí dụ : gen màu mắt ở vị trí thứ 10 (tức giá trị ổ gen ) của động vật ứng với mắt xanh. Trong việc tìm kiếm gen nhân tạo , chúng ta nói rằng các chuỗi được cấu tạo từ những đặc tính (features hay detector) ,chúng có những giá trị khác nhau .Đặc tính có thể được đặt ở những vị trí (position) khác nhau của chuỗi .Sự tương quan giữa các thuật ngữ tự nhiên và nhân tạo được chỉ ra trong bảng 1.3 . Từ trước đến nay ,chúng ta không phải phân biệt giữa một gen (một ký tự cụ thể ) và một ổ gen của nó (vị trí của nó) ; vị trí của một bit trong một chuỗi xác định ý nghĩa của nó (cách giải mã) một cách đồng nhất trong toàn bộ dân số và trong mọi thời điểm .Thí dụ , chuỗi 10000 được giải mã theo số nhị phân không dấu ,ứng với số 16 (hệ 10) ,bởi vì bit 1 được ngầm hiểu là 16. BẢNG 1.3: Đối chiếu các thuật ngữ TRONG TỰ NHIÊN TRONG GIẢI THUẬT GEN Chromosome (nhiễm sắc thể) Chuỗi Gene Đặc tính , ký tự Allele (gen tương ứng) Giá trị của đặc tính Locus (ổ gen) Vị trí chuỗi Genotype (kiểu gen) Cấu trúc Phenotype (kiểu hình) Tập thông số, giải pháp luân phiên , cấu trúc được giải mã Epistasis (tính lấn áp gen) Tính không tuyến tính ---------------***------------------ CHƯƠNG II CƠ SỞ TOÁN HỌC CỦA GT GEN I-ĐỊNH LÝ CƠ BẢN CỦA GIẢI THUẬT GEN: Các thao tác của GAs bắt đầu với một dân số ngẫu nhiên có n chuỗi , rồi sao chép các chuỗi theo khuynh hướng đến cái tốt , ghép cặp và đổi các chuỗi con thành phần , thỉnh thoảng làm đột biến giá trị bit để có số đo tốt . Mặc dù các GAs đã xử lý trực tiếp dân số của các chuỗi theo cách không phức tạp , qua chương 1 chúng ta đã bắt đầu nhận ra rằng quá trình xử lý các chuỗi một cách tường minh gây nên sự xử lý ngầm nhiều sơ đồ trong mỗi thế hệ .Để phân tích sự tăng trưởng và suy giảm của nhiều sơ đồ chứa trong một dân số , chúng ta cần vài ký hiệu bổ sung.Hãy xem xét các thao tác sinh sản , ghép chéo và đột biến trên sơ đồ chứa trong một dân số. Không làm mất tính tổng quát , chúng ta xét một chuỗi được tạo từ bộ ký tự nhị phân V ={0,1} .Theo quy ước , chúng ta ký hiệu chuỗi bằng ký tự in hoa , các ký tự riêng biệt bằng chữ thường có đánh chỉ số vị trí . Ví dụ , chuỗi A gồm 7 bit : A =0111000 , được biểu diễn dưới dạng sau : A = a1 a2 a3 a4 a5 a6 a7 Ơ đây , ai chỉ đặc tính nhị phân đơn (còn gọi là gen ai), mỗi đặc tính có thể nhận giá trị 1 hoặc 0 (đôi khi chúng ta còn gọi giá trị ai là gen tương ứng) .Trong chuỗi cụ thể , a1 = 0 ,a2 =1 ,a3 =1,a4 =1,a5 = 0… Cũng có thể có các chuỗi mà đặc tính không được sắp thứ tự như chuỗi A , thí dụ :A’ = a2 a6 a4 a3 a7 a1 a5. Chương sau sẽ khai thác hiệu quả của sự mở rộng việc biễu diễn chuỗi để cho phép các đặc tính bố trí độc lập với nhiệm vụ của chúng . Hiện thời ,giả thiết nhiệm vụ của đặc tính có thể được xác định bằng vị trí của nó . Giải thuật gen đúng nghĩa yêu cầu một dân số các chuỗi , chúng ta xét dân số của các chuỗi riêng lẻ Aj , j=1,2,3,… ,n, chứa trong dân số A(t) ở thời điểm (hay thế hệ) t,chữ in đậm để chỉ dân số .Bên cạnh các ký hiệu mô tả các dân số , các chuỗi ,các vị trí bit , và các gen tương ứng , chúng ta cần các ký hiệu quy ước để mô tả sơ đồ được chứa trong các chuỗi cá thể và các dân số .Xét một sơ đồ H tạo nên từ bộ 3 ký tự V+={0,1,*} , trong đó * được so trùng với cả ký tự 0 và 1 .Thí dụ ,xét sơ đồ 7 ký tự H = *11*0* * , chúng ta thấy chuỗi A = 0111000 nói ở trên là một ví dụ của sơ đồ H . Từ kết quả của chương trước, ta biết có 31sơ đồ (hay sự tương đồng) được xác định từ một chuỗi nhị phân có chiều dài l. Tổng quát, nếu bộ ký tự có k ký tự thì ta có (k+1)1sơ đồ. Hơn nữa, trong một chuỗi dân số có n phần tử thì sẽ có nhiều nhất là n*21 sơ đồ được chứa trong dân số đó, vì bản thân mỗi chuỗi là biểu diễn của 21sơ đồ.Những tính toán này cho chúng ta một cảm nhận nào đó về độ lớn của thông tin được xử lý bởi GAs .Tuy nhiên, để hiểu rõ tầm quan trọng của những khối gạch xây đối với những giải pháp trong tương lai, chúng ta cần phân biệt sự khác nhau giữa các loại sơ đồ. Tất cả các sơ đồ không được tạo nên một cách đồng đều, có một số sơ đồ đặc biệt hơn những cái khác . Ví dụ,sơ đồ 011*1* * là một thể hiện xác định hơn về sự tương đồng quan trọng so vớisơ đồ 0* * * * * * . Hơn nữa , một sơ đồ nào đó có thể trải rộng với chiều dài chuỗi nhiều hơn các sơ đồ khác. Ví dụ, sơ đồ 1* * * *1* sẽ trải một phần của chuỗi rộng hơn sơ đồ 1*1* * * *. Để đánh giá những ý tưởng này, chúng ta cần giới thiệu về hai đặc trưng của sơ đồ: bậc (other) của sơ đồ và chiều dài định nghĩa (defining length) của sơ đồ. Bậc của sơ đồ H , ký hiệu là o(H), là số các vị trí xác định (trong bộ ký tự nhị phân, chính là tổng số các bit 1 và 0) có trong mẫu. Ví dụ: bậc của sơ đồ 011*1* * là 4 (ký hiệu o(011*1**) = 4) còn bậc của sơ đồ 0* * * * * * là 1. Chiều dài định nghĩa của sơ đồ H ,ký hiệu d(H) là khoảng cách giữa vị trí có giá trị xác định đầu tiên với vị trí có giá trị xác định sau cùng của sơ đồ .Thí dụ , sơ đồ 011*1* * có chiều dài định nghĩa d = 4 , vì vị trí xác định cuối cùng là 5 và vị trí xác định đầu tiên là 1 .do đó khoảng cách giữa chúng là d(H) = 5-1 = 4 . Sơ đồ 0* * * * * * chỉ có một vị trí xác định ,do đó vị trí đầu và cuối trùng nhau , nên chiều dài định nghĩa d = 0 Sơ đồ và những đặc trưng của nó là những công cụ ký hiệu thích hợp để thảo luận và phân loại chính xác các sự tương đồng của chuỗi .Hơn thế nữa chúng cung cấp các phương tiện cơ sở để phân tích hiệu quả ròng của việc sinh sản và các thao tác di truyền trên các khối gạch xây được chứa bên trong dân số .Chúng ta hãy xem xét hiệu quả riêng và hiệu quả phối hợp của việc sinh sản ,ghép chéo và đột biến ,trên sơ đồ được chứa trong dân số của các chuỗi . Dễ dàng xác định hiệu quả của việc sinh sản trên một số lượng mong muốn của các sơ đồ trong một dân số .Giả sử tại bước thời gian (thế hệ) đã biết thứ t có m ví dụ của một sơ đồ cụ thể H, chứa trong dân số A(t) .Chúng ta viết m = m(H,t) (có thể có những số lượng khác nhau của các sơ đồ khác nhau tại những thế hệ t khác nhau). Khi sinh sản , một chuỗi sẽ được sao chép theo giá trị thích nghi của nó , hay chính xác hơn là chuỗi AI sẽ được tuyển chọn với xác xuất pI=fi / S fj . Sau khi chọn một dân số không phủ lắp (trùng lớp một phần ) có kích thước n với sự thay thế từ dân số A(t) ,chúng ta mong muốn có m(H,t+1) đại diện cho sơ đồ H trong dân số , tại thế hệ thứ t+1 , được xác định qua phương trình : m(H,t+1) = m(H,t) * n * f (H)/ S fj trong đó f(H) là dộ thích nghi trung bình của các chuỗi đại diện cho sơ đồ H ở thế hệ thứ t . Nếu chúng ta nhận thấy được độ thích nghi trung bình của toàn bộ chuỗi có thể được tính theo f = S fj / n ,chúng ta có thể viết lại phương trình tăng trưởng của sơ đồ sinh như sau: m(H,t +1) = m(H,t) *f(H) / f Qua đẳng thức trên chúng ta nhận thấy ,một sơ đồ cụ thể sẽ tăng trưởng tỉ lệ với độ thích nghi trung bình của nó chia cho độ thích nghi trung bình của toàn bộ dân số .Nói cách khác , các sơ đồ có giá trị thích nghi hơn độ thích nghi trung bình của dân số sẽ gia tăng số lượng các mẫu trong thế hệ kế , và ngược laị. Nghĩa là , mọi sơ đồ trong dân số sẽ tăng trưởng hay suy giảm tùy thuộc vào giá trị thích nghi trung bình của dân số , dưới tác động riêng rẽ của việc sinh sản . Cần nhớ rằng tại một thế hệ , có nhiều việc diễn ra song song với các thao tác đơn giản trên n chuỗi trong dân số . Anh hưởng của việc sinh sản trên sơ đồ là rõ ràng về mặt định tính :Các sơ đồ trên trung bình sẽ tăng trưởng và các sơ đồ dưới trung bình sẽ phải chết . Chúng ta có thể học thêm được điều gì khác nữa về dạng toán học của sự tăng trưởng (hoặc suy giảm ) từ phương trình sai phân của sơ đồ ? Giả thiết sơ đồ đặc thù H vượt quá độ thích nghi trung bình một lượng với c là hằng số .Với giả thiết này , chúng ta có thể viết lại phương trình sai phân cuả sơ đồ như sau : m(H,t+1) = m(H,t) ( f + cf ) / f = ( 1+c ) m(H,t) Bắt đầu với t = 0 và giả thiết một giá trị c không , chúng ta được phương trình : m(H,t) = m(H,0)(1+c) t Ta nhận thấy phương trình này giống như phương trình tiền lãi phức hợp , các về toán học sẽ nhận thấy phương trình này giống như cấp số nhân hay phép tương tự rời rạc dạng hàm mũ . Hiệu quả của việc sinh sản rõ ràng là định tính được việc sinh sản cấp phát sự gia tăng (hay giảm) theo hàm mũ của số lượng các phép thử đối với sơ đồ có độ thích nghi trên (hoặc dưới) trung bình . Bây giờ ta xét ảnh hưởng của ghép chéo và đột biến : Sự ghép chéo là sự trao đổi thông tin một cách ngẫu nhiên nhưng có cấu trúc giữa các chuỗi .Việc ghép chéo tạo ra những cấu trúc mới , với sự phá vỡ tổi thiểu đối với chiến lược cấp phát chỉ do sự sinh sản gây ra .Kết quả là các phần gia tăng(hay giảm) theo hàm mũ của sơ đồ trong một dân số trên nhiều sơ đồ , được chứa trong một thế hệ . Để thấy sơ đồ nào bị ảnh hưởng bởi sự ghép chéo và sơ đồ nào không bị ảnh hưởng , hãy xét một chuỗi A có chiều dài l = 7 và hai sơ đồ đại diện H1,H2 của nó : A = 0111000 H1 = *1* * * * 0 H2 = * * * 1 0 * * Rõ ràng hai sơ đồ H1 và H2 đại diện cho chuỗi A , nhưng để thấy ảnh hưởng của việc ghép chéo trên sơ đồ , trước tiên hãy nhớ lại rằng việc ghép chéo đơn giản tiến hành với sự lựa chọn ngẫu nhiên một cặp chuỗi sau đó chọn ngẫu nhiên vị trí ghép và trao đổi các chuỗi con từ đầu chuỗi đến vị trí ghép , với chuỗi con tương ứng . Giả sử chuỗi A được chọn để cặp đôi và ghép chéo , chiều dài của A là 7 . Quay xúc xắc để chọn chỗ ghép (có 6 chỗ có thể ghép trong một chuỗi có chiều dài là 7), giả sử xúc xắc ngửa mặt 3 nghĩa là chúng ta cắt cả 2 chuỗi ban đầu tại giữa vị trí bit thứ 3 và bit thứ 4 . Điểm ghép được đánh dấu bởi dấu |. A = 011 | 1000 H1 = *1* * | * * * 0 H2 = * * * | 10 * * Sơ đồ H1 sẽ bị phá hủy vì 1 ở vị trí 2 và 0 ở vị trí 7 sẽ được đặt vào các con cháu khác nhau (chúng ở hai phía của điểm ghép hay điểm cắt). Rõ ràng là cũng ở cùng một điểm cắt như vậy sơ đồ H2 sẽ sống sót , bởi vì ở 1 vị trí 4 và 0 ở vị trí 5 sẽ được mang trọn vào 1 thế hệ con cháu nào đó . Dù rằng chúng ta đã thấy khá rõ là H1 dường như ít khả năng sống sót hơn H2 bởi vì theo trung bình thì điểm cắt rơi vào giữa những vị trí xác định xa nhất . Để định lượng sự quan sát này , chúng ta nhận thấy H1 chiều dài định nghĩa là 5 . Nếu điểm ghép được chọn gống nhau 1 cách ngẫu nhiên trong số l – 1 = 7 –1 = 6 vị trí có thể có , rõ ràng là H1 sẽ bị phá hủy với xác xuất Pd = d(H1)/(l-1) =5/6 (nó tồn tại với xác suất Ps = 1 - Pd = 1/6). Tổng quát , chúng ta thấy giới hạn dưới của xác suất sống sót Ps có thể đuợc tính theo 1 sơ đồ bất kỳ . Bởi vì , 1 sơ đồsống sót khi điểm cắt rơi bên ngoài chiều dài định nghĩa , xác suất sống sót của sự ghép chéo đơn giản là Ps = 1 - d(H) /(l-1) , từ đó sơ đồ nhường như bị phá hủy bất cứ lúc nào tại 1 vị trí nằm trong chiều dài định nghiã ,được chon từ l-1 vị trí có thể có . Nếu việc ghép chéo tự thân nó thực hiện bằng sự lựa chọn ngẫu nhiên , chúng ta nói rằng với xác suất Pc ở một cặp ghép cụ thể , xác suất sống sót có thể được cho bằng biểu thức : Ps ³ 1 – Pc * d(H) /(l-1) Hiệu qủa phức hợp của sự sinh sản và ghép chéo giờ đây có thể được xem xét . khi xét riêng việc sinh sản chúng ta quan tâm đến việc tính toán số lượng của 1 sơ đố H cụ thể được mong đợi trong thế hệ kế tiếp . Giả sử hai thao tác sinh sản và ghép chéo là độc lập với nhau chúng ta có thể ước lượng sau : m(H,t+1) ³ m(H,t) * f(H) * [1 - Pe * d(H) /(l-1)] `f So sánh đẵng thức này với các biểu thứ c trước đây cho việc sinh sản riêng lẻ , hiệu quả của ghép chéo và sinh sản đạt được bằng cánh nhân với số lượng sơ đồ mong muốn cho việc sinh sản riêng lẻ bởi xác suất sống sót Ps dưới tác dụng của việc ghép chéo . Sơ đồ H sẽ tăng trưởng hay bị phá hủy tùy thuộc vào thừa số nhân .Đối với cả hai việc ghép chéo lẫn sinh sản , thừ số nhân phụ thuộc vào 2 yếu tố : Sơ đồ đó là trên hay dưới trung bình dân số , và sơ đồ đó có chiều dài định nghĩa tương ứng là ngắn hay dài . Rõ ràng với những sơ đồ hội đủ 2 yếu tố trên (trên trung bình và chiều dài định nghĩa ngắn ) sẽ được chọn làm mẫu với tỉ lệ gia tăng theo hàm mũ . Thao tác cuối cùng cần xem xét là sự đột biến . Theo định nghĩa trước đây , sự đột biến là sự thay thế ngẫu nhiên một vị trí đơn với xác suất Pm .Để một sơ đồ H sống sót được , tất cả những vị trí có giá trị xác định của nó phải được sống sót . Do đó, từ một gen tương ứng (allene) sống sót với xác suất (1-Pm) và từ mỗi đột biến độc lập theo thống kê , một sơ đồ cụ thể sẽ sống sót khi từng vị trí cố định o(H) bên trong sơ đồ đó sống sót . Nhân xác suất sống sót ( 1 - Pm) với chính nó o(H) lần , chúng ta được xác xuất của biến dị sống sót là (1-Pm)o(H) .Đối với giá trị Pm nhỏ (Pm << 1 ) , xác suất sống sót của sơ đồ có thể tính xấp xỉ bởi biểu thức 1 – o(H)*Pm . Vì thế chúng ta kết luận rằng 1 sơ đồ H cụ thể nhận một số lượng mong muốn các bản sao trong thế hệ kế tiếp dưới tác dụng của sự sinh sản , ghép chéo , và đột biến theo đẳng thức sau (bỏ qua các đại lượng quá bé) : m( H,t +1 ) ³ m (H,t).f(H) /`f .{1-Pc .d(H) /(l-1) – o(H)Pm} Sự đột biến thêm vào làm thay đổi một chút các kết luận trước đó . Những sơ đồ trên trung bình , bậc thấp , ngắn sẽ nhận số lần thử tăng theo hàm mũ trong nhũng thế hệ tiếp theo . Kết luận này quan trọng , rất quan trọng đến nỗi chúng ta đặt cho no một tên gọi là Định lí sơ đồ hay là Lý thuyết nền tảng của giải thuật gen . II-XỬ LÝ SƠ ĐỒ : Chương 1 đã trình bày cơ chế của giải thuật GEN đơn giản thông qua sự tính toán bằng tay cho một thế hệ . Chúng ta trở lại ví dụ này , nhưng lần này là để quan sát cách GAs xử lý sơ đồ – chứ không phải các chuỗi cá thể - bên trong một dân số . Sự tính toán bằng tay ở chương 1 được ghi lại trong bảng 2.1. Bảng 2.1:Xử lý GAs đơn giản ---------------------------------------------------------------------------------------------------- Xử lý chuỗi ---------------------------------------------------------------------------------------------------- Số tt Dân số Giá trị x Độ thích Pselecti fi Số đếm từ ban đầu nghi f(x)=x2 fi /Sf `f bánh xe 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.0 4.00 4.0 Average 293 0.25 1.00 1.0 Max 576 1.49 1.97 2.0 ---------------------------------------------------------------------------------------------------- Trước khi sinh sản. ---------------------------------------------------------------------------------------------------- Đại diện chuỗi Độ thích nghi trung bình của sơ đồ f(H) ---------------------------------------------------------------------------------------------------- H1 1**** 2,4 469 H2 *10** 2,3 320 H3 1***0 2 576 ---------------------------------------------------------------------------------------------------- Sau khi sinh sản ---------------------------------------------------------------------------------------------------- Xử lý chuỗi ---------------------------------------------------------------------------------------------------- Bể ghép đôi ghép đôi Vị trí ghép Dân số Trị x f(x) = x2 sau sinh sản với chuỗi 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 ---------------------------------------------------------------------------------------------------- Sau sinh sản Sau mọi thao tác ---------------------------------------------------------------------------------------------------- Số đếm Số đếm Đại diện Số đếm Số đếm Đại diện mong muốn thật chuỗi mong muốn thật chuỗi ---------------------------------------------------------------------------------------------------- 3.20 3 2,3,4 3.20 3 2,3,4 2.18 2 2,3 1.64 2 2,3 1.97 2 2,3 0.0 1 4 ---------------------------------------------------------------------------------------------------- Cùng với các thông tin đã trình bày , chúng ta đếm được bao nhiêu lần chạy của 3 sơ đồ H1, H2 ,H3 với: H1 = 1**** H2 = *10* * H3 = 1***0 Quan sát hiệu quả của sự sinh sản , ghép chéo và đột biến trên sơ đồ H . Trong suốt giai đoạn sinh sản các chuỗi được sao chép một cách xác suất tùy theo giá trị thích nghi của chúng . Hãy xem cột thứ 1 trong bảng chúng ta thấy 2 chuỗi 2 và 4 cùng đại diện cho sơ đồ 1**** . Sau khi sinh sản , chúng ta thấy 3 bản sao của sơ đồ được tạo ra (chuỗi 2 , 3, 4 trong cột ghép cặp). Số lượng này có phù hợp với giá trị được tiên đoán trong định lí sơ đồ ? Từ định lí sơ đồ , chúng ta mong muốn có m * f(H) /`f bản sao . Tính trung bình của sơ đồ f(H1) , chúng ta được (576 + 361)/2 = 468.5 . Chia cho trung bình dân số f = 293 và nhân với số lượng sơ đồ H1 có ở thế hệ t , m (H,t) = 2 , chúng ta được số lượng mong muốn của sơ đồ H1 tại thế hệ t+1 là m ( H,t+1 ) = 2 * 468.5 / 293=3.2 . So sánh với số lượng sơ đồ thực sự (là 3) chúng ta thấy rằng đã có đúng số lượng các bản sao như mong muốn . Thực hiện thêm một bước nữa , chúng ta thấy việc ghép chéo không có thêm bất kỳ một tác dụng nào , bởi vì chiều dài định nghĩa d(H1)=0 đã ngăn cản sự phá vỡ một bit đơn . Thêm nữa , với Pm=0.001 chúng ta muốn có m* Pm=3* 0.001= 0.003 hoặc không có bit nào bị thay đổi bên trong 3 bản sao của sơ đồ trong 3 chuỗi . Kết quả quan sát cho thấy đối với sơ đồ H1, chúng ta nhận được số sơ đồ tăng theo tỉ lệ với hàm mũ đúng như định lí sơ đồ đã tiên đoán . Đến giờ mọi việc đều tốt đẹp ; nhưng sơ đồ H1 chỉ có một bit xác định , dường như chỉ là một trường hợp đặc biệt . Hãy xét sự nhân giống của sơ đồ H2= *10** và H3= 1***0 . Sự sinh sản trước khi ghép chéo các bản sao sơ đồ là đúng .Trường hợp H2 bắt đầu với 2 ví dụ trong dân số ban đầu và kết thúc với 2 bản sao qua sự sinh sản . Điều này tương đồng với số lượng các bản sao mong muốn , m (H2)= 2*320/293=2.18, trong đó 320 là độ thích nghi trung bình của sơ đồ và 293 là độ thích nghi trung bình của dân số . Trường hợp H3 bắt đầu với một ví dụ đơn (chuỗi 2) và kết thúc với 2 bản sao qua sự sinh sản (chuỗi 2 và 3 trong cột các bản sao của chuỗi ). Điều này tương đồng với số lượng các bản sao mong muốn m(H3) = 1* 576 /293= 1.97 , trong đó 576 là độ thích nghi trung bình của sơ đồ và 293 là độ thích nghi trung bình của dân số .Tình huống ghép chéo sau đây phức tạp hơn một chút .Để ý rằng đối với sơ đồ ngắn như sơ đồ H2 , hai bản sao vẫn được duy trì mặc dù sự ghép chéo đã xảy ra . Bởi vì chiều dài định nghĩa ngắn , chúng ta mong đợi sự ghép chéo để làm gián đoạn quá trình chỉ một lần trong bốn lần (l- 1= 5-1=4).Kết quả là , sơ đồ H2 sống sót với xác suất cao . Số lượng mong muốn thực tế của sơ đồ H2 sau đó là : m(H2,t+1)=2.18*0.75=1.64, hoàn tòan tương ứng với số lượng thực là 2 sơ đồ . Còn H3 thì lại mang màu sắc khác .Vì chiều dài định nghĩa lớn (d(H3)=4) , do đó sự ghép chéo thường phá hủy sơ đồ này . III-BÀI TOÁN 2-Armed Bandit và K-Armed Bandit: Hiệu quả của sự sinh sản ghép chéo và đột biến đã rõ ràng cả về mặt định tính lẫn định lượng . Những sơ đồ có chiều dài định nghĩa ngắn , bậc thấp , độ thích nghi trên trung bình ( những khối gạch xây ) sẽ tăng trưởng tỉ lệ với hàm mũ trong các thế hệ tương lai .Nhưng mặc dù đã chứng minh kỹ lưỡng về điều này , vẫn còn một câu hỏi tồn tại :Tại sao đây là một việc tốt để làm ? Tại sao phải chọn hàm mũ ? Những câu hỏi này dẫn đến một bài toán quan trọng của lí thuyết quyết định theo thống kê , bài toán máy đánh bạc 2 – cần và dạng mở rộng của nó là bài toán máy đánh bạc k- cần . Giả sử chúng ta có một máy đánh bạc 2 cần với 2 cần có tên là Trái và Phải. Giả thuyết chúng ta biết rằng một cần sẽ trả phần thưởng m1 với độ biến thiên d12 và cần kia là trả thưởng m2 với d22, trong đó m1³ m2 .Chúng ta nên chơi cần nào? Hiển nhiên là chúng ta muốn chơi với cần trả thưởng thường xuyên hơn (cần có tiền thưởng là m1), nhưng chúng ta không biết trước cần nào sẽ trả thưởng cao hơn (Trái hay Phải ) , chúng ta đang đối mặc với tình huống khó xử . Không những chúng ta phải ra một quyết định về việc chơi cần nào , mà cùng lúc ấy chúng ta còn phải thu thập thông tin xem cần nào tốt hơn . Sự trao đổi giữa việc khảo sát cho tri thức và việc khai thác cho các tri thức ấy là một chủ đề nền tảng quan trọng trong lí thuyết và các hệ thống đáp ứng . Cách thức xác định tình thế khó xử này sẽ nói lên nhiều điều về thành công cuối cùng của một phương pháp . Một cách để tiếp cận sự trao đổi này là tách sự khảo sát ra khỏi sự khai thác , bằng cách thực hiện trước một thí nghiệm đơn và sau đó ra một quyết định đơn tất yếu (không thể đảo ngược được) dựa trên kết quả của thí nghiệm đó .Đó là cách tiếp cận của lí thuyết quyết định truyền thống (cổ điển) mà chúng ta có thể miêu tả chính xác như sau : Giả sử chúng ta có tổng số lần thử là N cho cả 2 cần .Đầu tiên ,chúng ta đặt một số lượng các phép thử bằng nhau n cho mỗi một trong hai cần (2n < N) trong suốt giai đoạn thí nghiệm . Sau khi thí nghiệm xong , chúng ta đặt N-2n phép thử còn lại cho cần nào cho số trả thưởng tốt nhất mà ta quan sát được .Giả sử , chúng ta biết rằng từ N, m1, m 2, d1, d2 chúng ta có thể tính được sự mất mát theo mong muốn (De Jong , 1975) : L(N,n) = | m1 - m 2 | . | ( N- n ) q (n) + n ( 1 – q(n) ) | trong đó : q(n) là xác suất mà cần xấu được quan sát là tốt , sau n phép thử trên mỗi máy .Xác suất này sẽ được xấp xỉ chính xác bởi phần đuôi của phân bố chuẩn : ; với Từ đẳng thức này ,chúng ta có thể thấy hai nguyên nhân mất mát liên quan đến thủ tục . Sự mất mát thứ nhất là kết quả của việc thực hiện n phép thử trên cần sai (muốn thử trên cần tốt nhưng lại thử nhầm trên cần xấu) trong suốt thời gian thử nghiệm . Sự mất mát thứ hai là kết quả của việc chọn phải cần có phần thưởng thấp (m 2) ngay cả sau khi hoàn thành việc thử nghiệm .Chúng ta không thể nào khẳng định là vào cuối cuộc thí nghiệm chúng ta sẽ chọn được đúng cần như mong muốn hay không , vì thế chúng ta hy vọng rằng sẽ ít chọn phải cần xấu và chịu thêm một sự mất mát trong N – 2n phép thử còn lại trong giai đoạn khai thác .Chúng ta có thể giải quyết cho kích thước thí nghiệm tối ưu là n* bằng cách lấy đạo hàm của phương trình mất mát và đặt nó bằng 0. Holland (1975) đã tính toán và chỉ ra cách phân phối các phép thử vào 2 cần như thế nào để tối thiểu hóa sự mất mát theo như mong đợi .Điều này dẫn đến kết quả là đặt n* phép thử vào cần xấu nhất và N – n* phép thử cho cần được thấy là tốt hơn , với n* được tính bằng phương trình sau đây : trong đó b = s1/( m1-m2 ) Xoay quanh phương trình này, chúng ta nhận thấy rằng số lần thử cho bởi cần tốt hơn quan sát được ,thì tuân theo phương trình: Nói cách khác , để đặt các phép thử một cách tốt ưu (theo nghĩa mất mát ít nhất như mong muốn ) , chúng ta nên tăng thêm một chút số lượng phép thử gia tăng theo hàm mũ cho cần được quan sát là tốt hơn . Nhưng không may là chiến lược này không hiện thực , vì có yêu cầu biết kết quả trước khi có kết quả . Tuy nhiên , điều này tạo nên một giới hạn quan trọng trong việc thực hiện , đó là một chiến lược hiện thực nên cố gắng để đạt đến .Chắc chắn có nhiều chiến lược có thể đạt đến sự lý tưởng này .Tiếp cận bằng thực nghiệm được phân tích ở trên cho thấy bằng cách nào mà số lượng lần thử ít hơn (theo hàm mũ) được đặt vào cần xấu , với tư cách là số lượng các phép thử được gia tăng .Một phương pháp khác thậm chí đã dẫn đến gần với việc bố trí các phép thử lý tưởng , đó là GAs đã được thảo luận . Định lý sơ đồ bảo đảm cung cấp ít ra là một số lượng gia tăng theo hàm mũ của các phép thử , cho những khối gạch xây được quan sát thấy là tốt nhất. Bằng cách này, GAs là một thủ tục hiện thực nhưng lại gần tối ưu ( Holland, 1973, 1975) để tìm kiếm những giải pháp lựa chọn. Với GAs, chúng ta sẽ giải quyết máy đánh bạc 2-cần đơn giản một cách nhanh chóng; trong GAs thông thường, chúng ta xem xét giải pháp đồng thời của nhiều máy đánh bạc nhiều cần. Để làm việc này một cách mạnh mẽ, trước tiên chúng ta xét dạng giải pháp đối với máy k-cần đơn và sau đó chứng minh rằng GAs thông thường có thể được xem là sự hợp thành của nhiều máy có k-cần như thế. Dạng của giải pháp bài toán k-cần giới hạn được Holland khám phá ra năm 1973 . Giải pháp mất mát tối thiểu theo mong muốn để bố trí các phép thử vaò k-cần cạnh tranh nhau thì tương tự như giải pháp cho 2 cần: một số lượng lớn hơn (tăng theo hàm mũ) của số các phép thử sẽ được đưa cho những cần được nhận thấy là tốt nhất . Kết quả này không làm ngạc nhiên, nhưng nó luôn liên hệ chặt chẽ với những nhận xét của chúng ta về việc xử lí sơ đồ, nếu như chúng ta xem một tập các sơ đồ đang cạnh tranh nhau như là một máy đánh bạc k-cần chuyên biệt. Để thấy sự liên hệ này , chúng ta xác định các yếu tố của một tập hợp các sơ đồ đang cạnh tranh , và sau đó đếm số lượng và kích thước của các bài toán máy đánh bạc k-cần đang được giải quyết bên trong một GAs của chiều dài chuỗi đã cho. Hai sơ đồ A và B với các vị trí riêng biệt a1 và b1 là đang cạnh tranh nếu ở tại mọi vị trí i = 1,2,…,l, chúng ta có hoặc là ai = bi =* hoặc là ai ¹ *, bi ¹ *, ai ¹ bi tại ít nhất một giá trị i. Thí dụ, xét tập hợp 8 sơ đồ cạnh tranh tại các vị trí 2,3,5, trong các chuỗi có chiều dài 7 dưới đây: * 0 0 * 0 * * * 0 0 * 1 * * * 0 1 * 0 * * * 0 1 * 1 * * * 1 0 * 0 * * * 1 0 * 1 * * * 1 1 * 0 * * * 1 1 * 1 * * Có 8 sơ đồ cạnh tranh trên 3 vị trí 2, 3 và 5, bởi vì bất kì vị trí nào trong số 3 vị trí này đều có thể chiếm hoặc là giá trị 1 hoặc là giá trị 0 (23 = 8). Chúng ta có thể bắt đầu thấy sự liên hệ với bài toán k-cần trong danh sách 8 sơ đồ cạnh tranh ở trên .Từ những sơ đồ được xác định trên các vị trí giống nhau này, chúng cạnh tranh với cái khác để chiếm những khe hở dân số quí giá.Để đặt các khe dân số một cách thích hợp, chúng ta cần đặt các số tăng theo hàm mũ cho những sơ đồ được thấy là tốt nhất, chỉ khi chúng ta cho các phép thử gia tăng tỉ lệ với hàm mũ cho cần được thấy là tốt nhất trong số k-cần. Một trong những khác biệt giữa tình thế của chúng ta trong một GAs và bài toán k-cần là chúng ta có một số các bài toán tiến hành song song. Thí dụ, với 3 vị trí cố định trên một chuỗi chiều dài 7, có [ 73]= 35 của ( 23 = 8) các bài toán 8 cần. Tổng quát, cho sơ đồ bậc j trên các chuỗi có chiều dài l , chúng ta có {l j } bài toán kj cần khác nhau, trong đó kj = 2j. Không phải tất cả S{lj }= 21 bài toán đều được giải quyết tốt như nhau, vì sự ghép chéo có khuynh hướng phá vỡ những máy nào có các chiều dài định nghĩa lớn như đã nói trước đây. Trong phần kế, chúng ta đếm số sơ đồ xử lí hiệu quả bằng Gas. IV-SỐ SƠ ĐỒ ĐƯỢC XỬ LÝ HIỆU QUẢ : Các đối số đếm được từ trước đến nay đã chỉ rằng chúng ta có từ 21 cho tới n * 21 sơ đồ đang xử lý trong một dân số chuỗi với chiều dài l và kích thước n . Như đã biết , không phải tất cả đều được xử lý với xác suất cao , bởi vì sự ghép chéo đã phá vỡ những sơ đồ với chiều dài định nghĩa tương đối lớn . Trong phần này chúng ta sẽ tính toán một giới hạn thấp nhất của những sơ đồ được xử lý hữu ích – đó chính là mẫu cho tỷ lệ gia tăng theo hàm mũ . Mặc dù bài toán chỉ n cấu trúc cho mỗi thế hệ , nhưng một GT GEN có vẻ như phải xử lý đến n3 sơ đồ . Kết quả này rất quan trọng và Holland đã cho nó một tên gọi đặc biệt là sự song song ngầm .Mặc dầu ở mỗi thế hệ chúng ta thực hiện sự tính toán tỷ lệ với độ lớn của dân số , chúng ta đạt đến sự xử lý hữu ích một số lượng dường như là n3 sơ đồ theo cách song song , mà không cần tốn thêm vùng nhớ đặc biệt nào hơn chính bản thân dân số .Chúng ta hãy nhận lại sự ước lượng này để hiểu những giả thuyết nền tảng của nó và khảo sát nguồn gốc của đòn bẫy tính toán này . Xét một dân số gồm n chuỗi nhị phân có chiều dài l .Chúng ta chỉ xét các sơ đồ sống sót với một xác suất lớn hơn hằng số Ps . Giả thiết thao tác ghép chéo là đơn giản và tỷ lệ lỗi e < 1 - Ps .Điều này dẫn chúng ta đi đến việc chỉ quan sát những sơ đồ có chiều dài ls < e (l -1) +1 . Với một chiều dài sơ đồ cụ thể , chúng ta có thể ước tính một giới hạn thấp nhất của số các sơ đồ duy nhất được xử lý bởi một dân số ngẫu nhiên ban đầu của các chuỗi .Để làm điều này , đầu tiên chúng ta đếm số lượng các sơ đồ có chiều dài ls hay ngắn hơn .Sau đó nhân với một độ lớn dân số thích ứng , được chọn theo ý chúng ta muốn , theo trung bình thì không lớn hơn 1 đối với mỗi sơ đồ có chiều dài ls /2 .Giả sử chúng ta muốn đếm được số sơ đồ có chiều dài l = 10 như sau: 1 0 1 1 1 0 0 0 1 0 Để làm điều này , chúng ta tính số lượng sơ đồ trong ô nhớ thứ nhất gồm 5 vị trí : 1 0 1 1 1 0 0 0 1 0 sao cho bit cuối cùng của ô là cố định .Điều này có nhgĩa là chúng ta muốn mọi sơ đồ có dạng : %%%%1 * * * * * trong đó các dấu * là giá trị nào đó và các dấu % sẽ lấy hoặc là giá trị cố định (1 hay không ở vị trí đó ) hoặc là giá trị nào đó . Rõ ràng có 2(ls –1) sơ đồ ,bởi vì ls –1 = 4 vị trí có thể được cố định hay nhận giá trị nào đó . Để đếm số lượng tổng cộng của những sơ đồ này , đơn giản là chúng ta chỉ ta cần trượt khung mẫu gồm 5 vị trí dọc theo sơ đồ : 1 0 1 1 1 0 0 0 1 0 Chúng ta thực hiện việc này tổng cộng là l - ls + 1 lần và chúng ta có thể ước lượng tổng số các sơ đồ có chiều dài ls hay nhỏ hơn là 2 (ls-1) * (l - ls + 1). Đó là số lượng các sơ đồ trong chuỗi cụ thể đã cho . Để phỏng định toàn thể số lượng các sơ đồ như thế trong toàn bộ dân số , đơn giản là chúng ta có thể nhân với độ lớn n của dân số và có được n * 2(ls - 1 ) * (l - ls + 1 ). Số này hiển nhiên là phỏng định cho con số chính xác , bởi vì chắc chắn là sẽ có những sự lặp lại của các sơ đồ bậc thấp trong các dân số lớn . Để tinh chế lại sự phỏng định này , chúng ta lấy ra một độ lớn dân số n = 2 ls/2 . Bằng cách chọn lựa theo phương thức này chúng ta muốn có toàn bộ (hay là một số ít hơn ) số các sơ đồ có bậc ls /2 hoặc lớn hơn . Nhận thấy rằng số lượng sơ đồ được phân bố thành 2 thành phần (nhị thức , binomially) , chúng ta kết luận là một nửa có bậc cao hơn ls/2 và một nửa bậc thấp hơn ls/2 . Nếu chúng ta chỉ đếm nhũng sơ đồ có bậc cao hơn , chúng ta ước chừng một giới hạn thấp cho các sơ đồ như sau : ns ³ n( l – ls + 1 )2(ls-2) Điều này khác với sự phỏng định trước đó bởi thừa số l/2 .Hơn nữa , nếu giới hạn độ lớn trong giá trị cụ thể 2ls/2,cho kết quả là biểu thức sau : ns = Từ ns = C n3 ,chúng ta kết luận là số lượng sơ d0ồ tỉ lệ với lũy thừa bậc 3 của độ lớn dân số , và do có bậc n3,tức (o(n3)) Vì thế , chúng ta thấy rằng mặc dầu có sự phá hủy những sơ đồ bậc cao ,dài bởi sự ghép chéo và đột biến ,các GT GEN vốn dĩ xử lí một số lượng lớn các sơ đồ ,trong khi xử lí một số lượng tương d0ối nhỏ các chuổi. V-CÁC GIẢ THUYẾT KHỐI GẠCH XÂY : Bức tranh của việc thực hiện GT GEN sẽ rõ ràng hơn với viễn cảnh được cung cấp bởi các sơ đồ . Những sơ đồ thấp bậc thấp và thích nghi cao sẽ được lấy mẫu liên kết lại và lấy mẫu lại để tạo nên các chuỗi có tiềm lực thích nghi cao hơn . Theo lối này bằng làm việc với những sơ đồ cụ thể này (những khối gạch xây) , chúng ta có thể giảm độ phức tạp của bài toán thay vì xây dựng các chuỗi hoàn thành cao bằng cách thử mọi tổ hợp có thể tưởng tượng được ,chúng ta xây dựng các chuỗi ngày càng tốt hơn từ những giải pháp riêng phần tốt nhất của các mẫu trong quá khứ . Bởi vì những sơ đồ thích nghi cao của các chuỗi có chiều dài định nghĩa ngắn và bậc thấp đóng vai trò quan trọng trong hành vi của các GAs ,chúng ta đã đặt cho chúng một tên gọi đặc biệt là khối gạch xây .Giống như trẻ con tạo các pháo đài nguy nga bằng cách ghép các mẫu gỗ đơn giản , các GAs sẽ tìm sự hoàn thành gần tối ưu thông qua việc đặt cạnh nhau các sơ đồ hoàn thành cao ,bậc thấp và ngắn ,hay đó chính là các khối gạch xây. Chương 1 đã nhấn mạnh nhiều lần rằng các ký hiệu sẽ liên kết lại để tạo nên những ý tưởng tốt hơn .Đến giờ chúng ta nhìn nhận rằng chính những khối gạch xây sẽ liên kết để tạo nên những chuỗi tốt hơn .Hiển nhiên là sự tăng lên của các bằng chứng theo kinh nghiệm đã cung cấp những yêu cầu trong một lớp rộng các bài toán .Bắt đầu từ 2 thập niên trước với các luận văn của hai nhà tiên phong (Babley , 1967 và Rosenberg ,1967 ) và được tiếp tục thông qua nhiều ứng dụng của GAs được nêu lên ở các hội nghị gần đây về GAs ,giả thuyết khối gạch xây được nêu ra trong nhiều bài toán khác nhau .Các bài toán đơn hình ,trơn , các bài toán đa hình có nhiễu , và các bài toán tối ưu hóa phức hợp, đều được giải quyết thành công nhờ GAs .Trong khi các bằng chứng theo kinh nghiệm có giới hạn thì không có lý thuyết chứng minh ,có gợi ý là GAs thích hợp cho nhiều dạng của bài toán mà chúng ta thường gặp . Mới đây , Bethke (1981) đã làm rõ thêm vấn đề này .Sử dụng các hàm Walsh và chuyển đổi khéo léo các sơ đồ , ông đã phát minh ra phương pháp phân tích hiệu quả các giá trị thích nghi trung bình nhờ dùng các hệ số Walsh .Điều này cho phép chúng ta xác định các hàm và mã đặc biệt đã cho ,các khối gạch xây phối hợp lại để tạo nên lời giải tối ưu hay gần tối ưu .Holland (1987) đã mở rộng các tính toán của Benthke để phân tích độ thích nghi trung bình của sơ đồ khi dân số không được phân bố đồng nhất . Việc chuyển đổi sơ đồ của Bethke và Holland vượt quá phạm vi nguyên cứu của chúng ta .Với người đọc quen thuộc với chuỗi Fourier ,tính tuần hoàn của các sơ đồ khác nhau được đặt ra .Thật ra ,chính sự tuần hoàn này cho phép phân tích hàm Walsh .Trong khi sự phân tích điều hòa xác định các đặc trưng vật lý thông qua sự kiểm tra độ lớn tương đối của các hệ số Fourier thì sự phân tích hàm Walsh sẽ xác định sự hiệu xuất tĩnh như mong muốn của GAs thông qua sự phân tích các độ lớn tương đối của những hệ số Walsh . Mặc dù những phương pháp chuyển đổi này là các công cụ toán học mạnh để phân tích GAs trong những trường hợp xác định ,nhưng sự tổng quát hóa những kết quả này cho việc mã hóa và các hàm tùy ý đã được chứng minh là rất khó khăn .Bethke đã tạo ra một số trường hợp thí nghiệm có thể dẫn đến sai lạc cho GT GEN 3 thao tác (chúng ta gọi tổ hợp các hàm –mã hóa này GAs –lầm lẫn ) .Những kết quả này nói lên rằng các hàm và việc mã hóa mà là GAs lầm lẫn ,có khuynh hướng chứa đỉnh tối đa cô lập : những điểm tốt nhất có khuynh hướng bị vây quanh bởi những điểm xấu nhất .Thực tế nhiều hàm chúng ta gặp phải trong thế giới thực không có các đặc trưng hi hữu này ; có một số tính đều đặn thông thường trong tổ hợp mã hóa hàm –giống như tính đều đặn của một hay nhiều sơ đồ –có thể được khai thác bởi sự tái liên kết những khối gạch xây .Tóm lại ,chúng ta có thể nói rằng việc tìm ra những hàm xấu loại này là khó khăn ,bất chấp kỹ thuật tìm kiếm .Tuy nhiên ,điều quan trọng phải ghi nhớ là GAs đơn giản phụ thuộc vào sự tái liên kết của các khối gạch xây để dò tìm những điểm tốt nhất .Nếu các khối gạch xây dẫn dắt kém hiệu quả ,vì sự mã hóa đã dùng hay do bản thân hàm ,bài toán có thể yêu cầu một thời gian chờ đợi lâu hơn để đi đến những giải pháp gần tối ưu . -------------***--------------- CHƯƠNG III HIỆN THỰC GIẢI THUẬT GEN --------------***** --------------- I- CẤU TRÚC DỮ LIỆU GAs xử lý các dân số của các chuỗi . do đó không có gì ngạc nhiên khi cấu trúc dữ liệu nguyên thủy cho GAs là một chuỗi dân số . Có nhiều cách để hiện thực dân số. Với GAs , chúng ta chọn cách đơn giản nhất . Chúng ta xây dựng dân số là một mảng các cá thể , trong đó mỗi cá thể chứa kiểu hình ( phenotype) (thông số hay các thông số đã giải mã), kiểu gen (genotype)(nhiễm sắc thể nhân tạo hay chuỗi bit) , và giá trị thích nghi (hàm mục tiêu ) cùng với các thông tin phụ khác .Sơ đồ dân số được trình bày trên hình 3.1 .Đoạn chương trình trên hình 3.2 khai báo kiểu dân số tương ứng với mô hình này . HÌNH 3.1 :Sơ đồ của một dân số chuỗi trong giải thuật gen INDIVIDALNUMBER INDIVIDUALS STRING X f (x) []THER 1 01111 15 225 2 01001 9 81 3 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : n 00111 7 49 Các khai báo kiểu dữ liệu theo Pascal const maxpop = 10; maxstring = 30; type allele = boolean ; (allele = vị trí bit) chromsome = array [1 .. maxstring] of allele ;(chuỗi bit) individual = record chrom:chromosome; (genotype = chuỗi bit) x: real; (phenotype = số nguyên không dấu ) fitness : real ; (gía trị hàm mục tiêu ) parent1, parent2 ,xsite : integer; (parent và cross pt) end; population = array [ 1.. maxpop] of individual; Tham khảo đoạn chương trình trên , các hằng được khai báo gồm kích dân số tối đa maxpop, chiều dài tối đa maxstring . Đây chính là giới hạn trên của kích thước dân số và chiều dài chuỗi .Phần khai báo dữ liệu individual là record gồm chrom thuộc kiểu chromosome đại diện cho nhiễm sắc thể nhân tạo ,fitness là biến đại diện cho giá trị thích nghi của chuỗi, và x là biến thực tương ứng với gía trị thông số đã giải mã .Bản thân kiểu chromosome là mảng của kiểu allene (đánh chỉ số từ 1 đến maxstring). Trong GAs , chúng ta áp dụng các toán tử gen trên toàn bộ dân số ở từng thế hệ . Để thực hiện trên các thao tác này , chúng ta sử dụng 2 dân số không phủ lấp nhau , qua đó đơn giản hóa viện sinh sản của các con cháu và sự thay thế của các bố mẹ .Khai báo hai dân số là oldpop và newpop cùng các biến toàn cục của chương trình .Với các dân số này, ta có thể dễ dàng tạo ra các con cháu mới từ các thành viên của oldpop nhờ các toán tử gen , và thay oldpop thành newpop để chuyển sang thế hệ mới Có các phương pháp lưu trữ hiệu qủa hơn để xử lí các dân số . Chúng ta có thể duy trì dân số đơn , không phủ lấp nhau .Không có lý do đặc biệt náo để kích thước dân số cố định . Các dân số tự nhiên chắc chắn thay đổi kích thước , và có thể là động cơ của suốt quá trình tìm kiếm bằng gen nhân tạo để cho phép kích thưóc dân số thay đổ từ thế hệ này sang thế hệ khác . Tuy nhiên , có một động cơ mạnh mẽ trong công việc hiện tại của chúng ta để giữ cho mọi việc đều đơn giản , và hướng dẫn lựa chọn các dân số không phủ lấp có kích thước cố định . Hình 3.3:Khai báo biến toàn cục của GAs theo Pascal var oldpop,newpop,: population;(2 dân số không phủ lấp) popsize , 1chrom ,gen, maxgen :integer ;(các biến tòan cục) pcross , pmutation , sumfitness: real; nmutation, ncross : (các thống kê nguyên) avg, max, min :real; (các thống kê thực) Trước khi tìm hiểu 3 thao tác thiết yếu của GAs , chúng ta cần định nghĩa một số biến toàn cục quan trọng , có ảnh hưởng đến tòan bộ chương trình , biến popsize tương ứng với kích thước dân số (n),biến lchrom ứng với chiều dài chuỗi (l)biến gen ứng với bộ đếm số thế hệ (t).Biến maxgen là giới hạn trên của số các thế hệ.Các biến pcross, pmulation là các xác suất ghép chéo và đột biến, ứng với pc và pm . Biến sumfitness là tổng các độ thích nghi dân số Sf . Các biến này quan trọng trong suốt phép chọn của bánh xe roulette. II-SINH SẢN, GHÉP CHÉO VÀ ĐỘT BIẾN : Trước khi tìm hiểu từng thủ tục kể trên chúng ta cần nhớ sợi dây chung xuyên suốt 3 thao tác sinh sản ,ghép chéo và đột biến là các phép chọn ngẫu nhiên .Trong các đoạn chương trình dưới đây , chúng ta giả thiết đã có 3 thủ tục ngẫu nhiên : Random : trả về số thực nhẫu nhiên , nằm giữa 0 và 1 . Flip: trả về giá trị boolean là true cùng với xác suất đặc tả ( giá trị ngẫu nhiên bernoully) Rnd: trả về giá trị nguyên nằm giữa các giới hạn dưới và trên đã chỉ ra (biến ngẫu nhiên đồng nhất trên tập con các số nguyên kề nhau ). Trong giải thuật gen đơn giản , việc sinh sản được hiện thực trong thủ tục select , như việc tìm kiếm tuyến tính thông qua bánh xe roulete với các khe hở trọng số tỉ lệ với giá trị thích nghi của chuẩn . Trong đoạn chương trình trên hình 3.4 , chúng ta thấy select trả về giá trị chỉ số dân số tương ứng với cá thể đã chọn . Để làm điều này , tổng riêng phần của các giá trị thích nghi được cộng dồn vào biến thực partsum . Biến thực rand chứa vị trí nơi bánh xe chiếm sau khi quay , theo tính toán sau : Rand: = randdom* sumfitness Ơ đây , tổng các độ thích nghi của dân số (được tính trong thủ tục statistics) được nhân với số ngẫu nhiên giả lặp tạo bởi thủ tục random . Cuối cùng , cấu trúc repeat- untill tìm kiếm thông qua bánh xe roulet có trọng số , cho đến khi tổng riêng phần lớn hơn hoặc bằng điểm dừng rand .Hàm trả về với giá trị chỉ số dân số hiện tại j được gán cho select . Hình 3.4 hàm select hiện thực phép chọn của bánh xe roulet . function select(popize : integer; sumfitness :real; var pop: integer) :integer; {một cá thể qua phép chọn củ bánh xe roulette} var rand, partsum :real;{điểm ngẫu niên trên bánh xe roulette} j :integer;{chỉ số dân số} begin partsum := 0.0; j:= 0; {gán 0 cho bộ đếm và bộ tích luỹ} rand := random*sumfitness; {tínt toán điểm trên bánh xe roulette, sử dụng số ngẫu nhiên[0,1]} repeat j := j+1; partsum := partsum + pop[j].fitness; until (partsum >= rand) or (j =popsize); {trả về số cá thể} select := j; end; Đây có lẽ là cách đơn giản nhất để hiện thực việc chọn lựa . Đoạn chương trình select cho chúng ta cách chọn trực tiếp con cháu cho thế hệ kế . Bước kế tiếp là ghép chéo , thực hiện bằng thủ tục crossover trên hình 3.5 : Hình 3.5: thủ tục crossover hiện thực sự ghép chéo đơn giản Procedure crossover(var parent1,parent2,child1,child2 : chromosome; var lchrom,ncross,pmutation,jcross :integer; var pcross,pmutation:real); {ghép chéo 2 chuỗi bố mẹ đặt vào 2chuỗi con} var j :integer; begin if flip(pcross) then begin {ghép chéo với (pcross)} jcross := rnd(1,lchrom-1); {ghép giữa 1 và lchrom –1} ncross := ncross + 1; {tăng bộ đếm lần ghép chéo} end else jcross := lchrom; { trao đổi lần 1, giữa 1 với 1 và 2 với 2} for j := 1 to jcross do begin child1[j] := mutation(parent1[j],pmutation,nmutation); child2[j] := mutation(parent2[j],pmutation,nmutation); end; { trao đổi lần 1, giữa 1 với 2 và 2 với 1} if jcross lchrom then {bỏ qua nếu mặt ghép là lchrom –không ghép} for j := 1 to jcross do begin child1[j] := mutation(parent2[j],pmutation,nmutation); child2[j] := mutation(parent1[j],pmutation,nmutation); end; end; Thủ tục crossover nhận 2 chuỗi bố mẹ là parent 1 và parent 2 và sinh ra 2 chuỗi con child1 và child2. Các xác suất ghép chéo và đột biến pcross và pmutation được chuyển cho crossover , cùng với chiều dài chuỗi lchrom , bộ đếm tích lũy số lần đột biến nmutation . Trong crossover , các thao tác phản ảnh các mô tả của chúng ta trong chương 1 . Đầu thủ tục , chúng ta xác định khi nào sẽ thực hiện ghép chéo trên cặp nhiễm sắc thể bố mẹ hiện tại . Chúng ta búng đồng tiền , để đạt được mặt ngửa với xác suất pcross .Mô phỏng việc búng đồng tiền qua thủ tục boolean là flip , trong đó flip gọi thủ tục random giả lập số ngẫu nhiên .Nếu cần ghép chéo , vị trí ghép chéo được chọn giữa 1 và vị trí ghép cuối cùng .Chỗ ghép chéo được chọn qua hàm rnd , hàm này trả về một số nguyên ngẫu nhiên nằm giữa các giới hạn dưới và trên (giữa 1 và lchrom-1 ) .Nếu không có sự ghép nào được chọn , chỗ ghép chéo được lấy là lchrom (chuỗi đầy đủ dài 1) , qua đó sự đột biến theo từng bit được tiến hành cho dù thiếu mặt sự ghép chéo .Cuối cùng , sự trao đổi các phần trong ghép chéo được thực hiện qua 2 cấu trúc for-do ở cuối đoạn chương trình .Đoạn for-do đảm nhận chuyển từng bit nằm giữa parent1 và child1 , và giữa parent2 và child2 .Đoạn for –do thứ 2 đảm nhận chuyển và trao đổi từng phần chất liệu giữa parent1 và child2 , và giữa parent2 và child1 .Trong trường hợp này , đột biến theo từng bit được tiến hành bởi hàm boolean mutation . Đột biến tại 1 điểm được thực hiện bằng thủ tục mutation trên hình 3.6. Hình 3.6: Thủ tục Mutation thực hiện ghép chéo điểm, bit đơn: function mutation(alleleval :allele; pmutation :real; var nmutation :integer) :allele; var mutate :boolean; Begin mutate := flip(pmutation); {búng đồng tiền} if mutate begin nmutation := nmutation + 1; mutation := not alleleval; {đổi giá trị bit} end else mutation := alleleval; {không đổi} end; Thủ tục này dùng hàm flip (tung đồng tiền 2 mặt ) để xác định khi nào thay đổi từ true sang false và ngược lại .Thủ tục flip chỉ đưa ra tỉ lệ phần trăm mặt ngửa pmutation theo thời gian , như kết quả bộ tạo số tự nhiên random nằm bên trong bản thân thủ tục flip .Hàm này cũng giữ các mốc trên số các đột biến bằng cách tăng biến pmutation .Như vậy , với sự sinh sản có nhiều cách để cải thiện biến dị đơn. Ví dụ , có thể tránh việc sinh ra quá nhiều số ngẫu nhiên nếu chúng ta quyết định khi nào thế hệ kế phải có mặt hơn là gọi hàm flip mỗi lần . III-GIAI ĐOẠN SINH SẢN VÀ GHÉP CHÉO: Thủ tục tạo thế hệ mới từ thế hệ cũ , bắt đầu với chỉ số ban đầu j = 1 và tiếp tục cho tới khi vượt quá kích thước dân số popsize, ta chọn 2 cặp mate1 và mate2 bằng cách gọi hàm select . Việc lai ghép và đôy biến chuỗi nhờ thủ tục crossover , giải mã cặp chromosomes , tính các giá trị hàm mục tiêu và tăng dân số lên 2 đơn vị. Hình 3.7 : Thủ tục generation tạo thế hệ mới từ thế hệ cũ. procedure generation; {tạo thế hệ mới thông qua chọn lựa ghép chéo và đột biến} var j,mate1,mate2,jcross :integer; Begin j := 1; repeat {chọn đột biến và ghép chéo cho đến khi newpop được lấp đâỳ} mate1:= select(popsize,sumfitness,olpop); {chọn cặp ghép đôi} mate2:= select(popsize,sumfitness,olpop); {ghép chéo và đột biến –đột biến bên trong quá trình ghép chéo} crossover(oldpop[mate1].chrom, oldpop[mate2].chrom, newpop[j].chrom,newpop[j+1].chrom,lchrom,ncross, nmutation,jcross,pcross,pmutation); {giải mã chuỗi, tính fitness } with newpop[j] do begin x := decode(chrom,lchrom); fitness := objfunc(x); parent1 := mate1; parent2 := mate2; xsite := jcross; end; with newpop[j+1] do begin x := decode(chrom,lchrom); fitness := objfunc(x); parent1 := mate1; parent2 := mate2; xsite := jcross; end; {tăng chỉ số dân số} j := j + 2; until j > popsize; end; Với bài toá bất kỳ chúng ta phải tạo thủ tục giải mã các chuỗi, để tạo thông số hoặc bộ thông số phù hợp với bài toán . chúng ta cũng tạo thủ tục nhận thông số hay bộ các thông số đã cho. Các thủ tục này được đặt tên là decode và objfunc. với các bài toán phức tạp ,chúng ta cần các thủ tục giải mã khác nhau ,các thủ tục tính hàm thích nghi khác nhau .Để thống nhất với phần dã trình bày,chúng ta tiếp tục dùng cách mã hoá số nguyên nhị phân không dấu, và dùng hàm luỹ thừa đơn giản biểu diễn hàm thích nghi :f(x) = x10 . Sau đây chúng ta xây dựng tủ tục decode. Trong thủ tục này, chromosome đơn được giải mã bắt đầu từ bit thấp nhất và map từ phả sang trái bằng cách trích lũy vào lũy thừa cơ số 2 hiện tại ,được cất vào biến poweroftwo .Khi bit tương ứng được thiết lập .giá trị tích lũy này được cất vào biến accum ,cuối cùng được trả về cho hàm decode. Hình 3.8 : thủ tục decode giãi mã chuỗi nhị phân là số nguyên khop6ng dấu. function decode(chrom :chromosome; lbits :integer) :real; {giải mã chuỗi thành số nguyên không dấu} var j : integer; accum, powerof2 : real; Begin accum := 0.0powerof2 :=1; for j:= 1 to lbits do begin if chrom[j] then accum := accum + powerof2; powerof2 := powerof2 * 2; end; decode := accum; end; Hàm mục tiêu ta dùng ở đây là hàm lũy thừa đơn giản :f(x) = (x/coeff)10 .Giá trị coeff được chọn để chuẩn hóa thông số x khi chuỗi bit có chiều dài lchrom = 30 được chọn : coeff = 230 –1 = 1073741823.0 Từ đó giá trị x được chuẩn hóa , giá trị tối đa của hàm là f(x) = 1.0 ,khi x = 230 –1 cho trường hợp lchrom = 30 Hình 3.9: Thủ tục objfunc tính hàm thích nghi f(x) = cx10 từ thông số giải mã x. function objfunc (x :real) :real; const coeff = 1073741823.0; {hệ số chuẩn hóa vùng} n = 10; Begin objfunc := power(x/coeff,n) end; IV-CHƯƠNG TRÌNH CHÍNH : Dưới đây là chương trình chính của GAs đơn giản: Hình 3.10 : Chương trình chính GAS : Begin gen := 0; repeat {vòng lặp chính} gen := gen +1 ; generation; statictics(popsize, max, avg, min, sumfitness, newpop} report(gen} oldpop := newpop ; {hướng đến thế hệ mới} until (gen >= maxgen) ; end; Bắt đầu chương trình chính, chúng ta đặt bộ đếm thế hệ gen := 0. Sau đó chúng ta nhập dữ liệu vào chương trình , khởi tạo dân số ngẫu nhiên ban đầu, tính toán thống kê dân số ban đầu, và in ra báo cáo ban đầu bằng thủ tục initialize. Ở đây không đào sâu vào đoạn chương trình khởi động . Kế tiếp vòng lặp chính của chương trình chứa trong cấu trúc repeat-until gồm : tăng bộ đếm thế hệ, sinh ra một dân số mới trong thủ tục generation, tính toán các thống kê sinh sản mới bằng thủ tục statictics , in bản báo cáo ban đầu nhờ thủ tục report ,rồi gán dân số mới vào dân số cũ cho thế hệ kế tiếp : oldpop := newpop ; Kiểmtra điều kiện ,nếu bộ đếm thế hệ còn nhỏ hơn số thế hệ tối đa maxgen thì quay trở lên làm lại các lệnh trong vònglặp này cho đến khi điều kiện được thỏa. Thủ tục statictics sẽ tính toán các giá trị trung bình ,lớn nhất và nhỏ nhất của độ thích nghi; nó cũng tính tổng thích nghi sumfitness mà bánh xe roulette yêu cầu: Hình 3.11 : Thủ tục statictics tính các thống kê dân số quan trọng: procedure statictics(popsize :integer; var max, avg ,min ,sumfitness :real; var pop :opulation) ; var j :integer; Begin {khởi tạo} sumfitness := pop[1].fitness ; min := pop[1].fitness ; max := pop[1].fitness ; {vòng lặp tìm max ,min ,sumfitness} for j := 2 to popsize do begin sumfitness := sumfitness + fitness; if fitness > max then max := fitness ; if fitness < min then min := fitness ; end; avg := sumfitness / popsize ; end ; Thủ tục report sẽ tình bày một bản báo cáo dân số đầy đủ bao gồm các chuỗi ,các độ thích nghi và các giá trị thông số .Một danh sách của report và chương trình con writechrom . Hình 3.12 Thủ tục writechrom: procedure writechrom(var out : text ; chrom :chromosome; lchrom :integer) ; var j :integer; begin for j := lchrom downto 1 do if chrom[j] then writeln(out,’1’) else write(out,’0’) ; end; V-PHÂN TÍCH CHƯƠNG TRÌNH : Chúng ta xác định một phép thử đơn giản .Chuỗi bit như là số nguyên không dấu 30 bit. Hàm thích nghi (x /c)n , trong đó c được chọn để chuẩn hóa x, và n được chọn là 10. Ở đây ta chọn số mũ lớn hơn là vì với số mũ lớn hơn ,giá trị trung bình của hàm sẽ thấp hơn ,và một phần nhỏ hơn của vùng sẽ ánh xạ đến các giá trị trên một vài số lượng đã chỉ ra .Kết quả là dân số bắt đầu ngẫu nhiên sẽ không chứa nhiều điểm tốt để bắt đầu dò tìm, đây là phép thử tốt hơn cho việc thực hiện GAs. Để xác định các mô phỏng một cách chính xác hơn ,hãy chọn một tập hợp các thông số tử cho GAs .Trong nghiên cứu của De Jong (1975) về GAs để tối ưu hóa hàm ,một loạt các thông số nghiên cứu bằng 5 hàm phù hợp với các bài toán ,đã khuyên cáo rằng sự thực hiện tốt đẹp của GAs đòi hỏi chọn lựa một xác suất ghép chéo lớn ,xác suất đột biến nhỏ (tỉ lệ nghịch với dân số) và một độ lớn dân số vừa phải .Theo khuyến cáo này , chúng ta chọn các thông số sau cho các mô phỏng tính toán đầu tiên : pmutation = 0.0333 (xác suất đột biến) pcross = 0.6 (xác suất ghép chéo) popsize = 30 (độ lớn dân số) Trong sự mô phỏng bằng tay ở chương 1 ,chiều dài chuỗi là ngắn (l=5) .vậy không gian tìm kiếm nhỏ , chỉ gồm 25 = 32 điểm .Miền này nhỏ quá, phép thử không có sức thuyết phục cao ,vì bất kỳ một phương pháp tìm kiếm kiểu liệt kê hay ngẫu nhiên nao cũng có thể tìm ra kết quả nhanh chóng với không gian tìm kiếm nhỏ như vậy .Giờ đây ,chúng ta muốn thấy phép thử khắc nghiệt hơn đối với GAs ,chiều dài chuỗi được tăng lên và số mũ đem thử của hàm cũng được tăng lên ,với chiều dài chuỗi lchrom = 30 ,không gian tìm kiếm sẽ rộng hơn và cách làm việc kiểu ngẫu nhiên hay liệt kê sẽ không tích hợp .Với lchrom = 30 sẽ có 230 điểm,phương pháp liệt kê mỗi điễm một lần hoàn toàn không thể làm nhanh được .Hơn nữa với sự gia tăng hàm số mũ của hàm thích nghi vừa mới điều chỉnh thì chỉ có 1.05% số điểm của không gian tìm kiếm là có giá trị lớn hơn 0.9 ,hai sự sửa đổi này rõ ràng đã làm cho phép thử GAs thuyết phục hơn . Chúng ta bắt đầu với GAs đơn giả và cho nó chạy qua 7 thế hệ .Bảng thống kê chỉ ra như sau : Các thông số của GAs đơn giản : Độ lớn dân số (popsize) = 30 Chiều dài nhiễm sắc thể (lchrom) = 30 Số thế hệ tối đa(maxgen) = 10 Xác suất ghép chéo (pcross) = 0.6 Xác suất đột biến (pmutation) =0.0333 Các thống kê dân số ban đầu : Độ thích nghi cực đại dân số ban đầu = 2.8241322532E-0.1 Độ thích nghi trung bình dân số ban đầu = 3.4715832788E-0.2 Độ thích nghi cực tiểu dân số ban đầu = 1.1406151375E-10 Tổng độ thích nghi dân số ban đầu = 1.0414749837+0.0 Dân số khởi động có độ thích nghi trung bình là 0.0347 .Thích nghi trung bình của hàm trong khoảng đã cho có thể tính được bằng 0.0909 .Trong một chừng mực nào đó chúng ta đã không gặp may ,khi lựa chọn ngẫu nhiên dân số ban đầu .Lướt qua các độ tích nghi thành phần tốt nhất trong dân số khởi động chúng ta thấy fmax = 0.2824 ,chúng ta muốn có 30.(1-0.2824 0.1) = 3.56 hay là xấp xỉ 4 chuỗi trong một dân số ngẫu nhiên 30 phần tử có độ thích nghi tốt hơn 0.2824 .Không những chúng ta gặp xui với giá trị trung bình ,mà chúng ta lại không gặp may với giá trị max .Măc dù có sự giảm không mong muốn dân số ban đầu ,mỗi khi GAs khởi đông nó sẽ nhanh chóng tìm ra cách thực hiện tốt ,sau vòng sinh sản ,ghép chéo và đột biến đầu tiên .Trong thế hệ thứ nhất ,một chuỗi rất tốt với độ thích nghi là 0.8715 đã được tìm ra .Nếu chạy tiếp nữa sự cải thiện xa hơn được tìm thấy trên cả độ thích nghi dân số trung bình lẫn độ thích nghi dân số cực đại .Càng về cuối quá trình ,sự hội tụ quan sát được càng cao .Trong thế hệ thứ 7 ,Chúng ta nhận thấy rằng có sự hợp lý ở hầu hết các vị trí bit .Điều này đã xảy ra ,mặc dù chúng ta chưa đạt đến điểm tốt nhất trong không gian ,tuy nhiên chúng ta đã đến gần điểm đó .Ở thế hệ thứ 6 ,một cá thể đã xuất hiện với độ thích nghi là f =0.9807 .Điểm này gần điểm tối ưư nhưng chưa phải điểm tối ưu .Hành vi hội tụ mà không bảo đảm tối ưu đã làm phiền lòng những ai tiếp cậ GAs từ cơ sở tối ưu tuyền thống khác.Có nhiều cách làm giảm sự hội tụ sớm này ,chúng ta sẽ nghiên cứu vài cách.Tuy nhiên sự thật của vấn đề là các GAs không đảm bảo hội tụ trong bài toán tùy ý .Dù chúng ta rút ra được các miền đáng quan tâm của không gian tìm kiếm một cách nhanh chóng ,nhưng chúng là những phương pháp yếu ,không đảm bảo có những thủ tục hội tụ hơn.Điều nàynkhông làm giảm giá trị tiện ích của chúng .Hoàn toàn ngược lại có nhiều phương pháp hội tụ hơn lại phải hy sinh tính toàn cục và tính linh hoạt cho sự hội tụ .Thêm nữa ,nhiều phương pháp bị hạn chế bởi một lớp hẹp các bài toán .Kết quả là các GAs có thể được dùng ở những nơi mà các kỹ thuật hội tụ hơn không giám giải quyết .Hơn nữa,nếu chúng ta đang giải quyết bài toán được biết là cục bộ nhưng hội tụ , thì các phương pháp hiện có ,các ý tưởng về phương pháp lai là hoàn toàn tự nhiên .Hãy bắt đầu sự tìm kiếm bằng GAs để chọn ra những ngọn đồi đáng qua tâm trong bài toán .Một khi GAs tìm được ra những miền tốt nhất ,kế đó hãy chọn các sơ đồ hội tụ cục bộ và leo lên những dỉnh cục bộ .Bằng các này ta có thể kết hợp tính toàn cục và tính song song của GAs ,với hành vi hội tụ hơn của kỹ thuật cục bộ . VI-BIẾN ĐỔI CÁC HÀM MỤC TIÊU SANG HÀM THÍCH NGHI: Trong nhiều bài toán ,mục tiêu được đưa ra một cách tự nhiên ,chẳn hạn là cực tiểu hóa một số hàm g(x) nào đó ,hay là cực đại hóa hàm lợi ích hay hàm lợi nhuận n(x) .Ngay khi bài toán được đưa ra một cách tự nhiên dưới dạng tối ưu hóa ,thì điều này không bảo đảm hàm tiện ích sẽ không âm với mọi x mà chúng ta yêu cầu trong hàm thích nghi (hàm thích nghi phải có giá trị không âm) .Như vậy cần thiết phải chuyển những hàm mục tiêu thông thường sang một dạng hàm thích nghi ,thông qua một hay nhiều phép biến đổi . Tính đối ngẫu của cực tiể hóa giá thành và cực đại quá lợi nhuậnđược tìm hiểu rất rõ .Thông thường để chuyển một bài toán cực tiểu hoá sang bài toán cực đại hóa ,chúng ta chỉ cần nhân hàm giá với một số âm .Trong GAs thao tác này là chưa đủ ,bởi vì đại lượng đạt được sau đó sẽ không có gì bảo đảm là không âm trong mọi trường hợp .Với GAs ,sự chuyển đổi từ giá sang giá trị thích nghi thường làm như sau : f(x) = Cmax – g(x) khi g(x) < Cmax ,f(x) = 0 và ngược lại. Có nhiều cách khác nhau để chọn hệ số Cmax . Cmax có thể được lấy như là hệ số nhập ,theo giá trị g lớn nhất quan sát được tính đến lúc ấy ,theo giá trị g lớn nhất trong dân số hiện thời ,hay theo giá trị lớn nhất của k thế hệ sau cùng .Để thích hợp hơn , Cmax nên biến đổi theo sự biến động dân số . Khi phát biểu hàm mục tiêu như là hàm lợi nhuận hay hàm tiện ích , chúng ta dễ dàng định hướng hàm : lợi nhuận hay ích lợi tối đa sẽ dẫn đến sự thực hiện như mong muốn .Có thể chúng ta vẫn còn một vấn đề với giá trị âm cuả hàm tiện ích u(x) .Để khắc phục điều này ,chúng ta chỉ cần biến đổi độ thích nghi theo phương trình sau : f(x) = u(x) + Cmin khi u(x) + Cmin > 0, f(x) = 0 vá ngược lại. Chúng ta có thể chọn Cmax như là hệ số nhập ,như là giá trị tuyệt đối của giá trị xấu nhất trong thế hệ hiên tại hay k thế hệ sau cùng ,hay theo một hàm biến động dân số . Mọi sự bắt chước với các hàm mục tiêu này gây ra sự nghi ngờ về mối liên hệ giữa hàm mục tiêu và hàm thích nghi .Trong tự nhiên ,sự thích nghi (một số con cháu sống sót để sinh sản) là phép lặp thừa .Một số lượng con cháu sẽ sống sót bởi vì chúng thích nghi ,và chúng thích nghi bởi vì một số lượng con cháu sẽ sống sót .Sự sinh tồn trong dân số tự nhiên là một nhiệm vụ tối hậu và duy nhất của bất kỳ sự du nhập nào .Ngược lại trong công việc của GAs ,chúng ta có cơ hội điều chỉnh mức độ cạnh tranh giữa các thành viên của dân số đr63 đạt đến sự thực hiện quá độ và chủ yếu mà chúng ta mong muốn .Đây là cái mà chúng ta phải làm ,khi chúng ta thực hiện việc co độ thích nghi. VII-ĐỘ CO THÍCH NGHI : Điều chỉnh số lượng các bản sao là đặt biệt quan trọng đối với GAs dân số nhỏ .Trong lúc bắt đầu chạy GAs ,chúng ta thường có một số ít cá thể đặc biệt trong dân số .Nếu các cá thể đặc biệt lại cho luật chọn lọc bình thường (pselect = fi / Sf) ,chúng có thể chiếm tỉ lệ đáng kể của dân số trong một thế hệ , và điều này sẽ gây ra sự hội tụ sớm .Sau đó chỉ sau một lần chạy ta có bài toán rất khác với bài toán đầu .Cuối lần chạy có thể có sự biến đổi đáng kể bên trong dân số ,tuy nhiên độ thích nghi trung bình dân số cá thể đạt gần đến độ thích nghi dân số tốt nhất .Nếu điều này xảy ra ,các thành viên trung bình và các thành viên tốt nhất gần như lấy cùng số lượng bản sao trong những thế hệ tương lai ,và sự sống sót của cá thể thích nghi nhất cần thiết cho sự cải thiện sẽ trở thành ngẫu nhiên trong dân số những cá thể bình thường .Trong cả hai trường hợp ,khi bắt đầu chạy cũng như khi bắt đầu chạy ổn định ,phép co độ thích nghi là một lối thoát. Một thủ tục có ích là phép co tuyến tính .Gọ f là độ thích nghi thô và f’ là độ thích nghi được co .Co tuyến tính yêu cầu một quan hệ tuyến tính giữa f và f’ như sau : f’ = af + b Các hệ số a và b có thể được chọn theo nhiều cách ,tuy nhiên trong tất cả mọi trường hợp chúng ta muốn có độ co thích nghi trung bình f’avg bằng với độ thích nghi thô favg ,bởi vì việc dùng thủ tục chọn lọc sau đó sẽ bảo đảm rằng mọi thành viên dân số trung bình sẽ đóng góp vào thế hệ con cháu kỳ vọng trong thế hệ kế tiếp .Để điều khiển số lượng dân số đã cho đối với thành viên dân số có độ thích nghi thô tố đa ,chúng ta chọn quan hệ co kiểu khác để đạt được độ thích nghi co tối đa f’max = Cmult * favg trong đó Cmult là số lượng các bản sao mong muốn cho thành viên dân số tốt nhất .Đối với các dân số nhỏ (n = 50 .. 100) , = 1.2 đến 2 được sử dụng thành công. Thủ tục co đơn giản thông qua 3 chương trình con prescale ,scale , scalepop. procedure prescale(umax,uavg,umin :real; var a,b :real); {tính các hệ số co cho phép co tuyến tính} const fmultiple = {bội số của phép co là 2} var delta :real; {ước số} Begin if umin > (fmultiple * uavg – umax) / (fmultiple –1.0) {kiểm tra không âm} then begin {phép co thông thường} delta := umax –uavg; a := (fmutiple – 1.0) * uavg / delta ; b := uavg * (uavg – fmultiple * uavg) / delta ; end else begin {co thật nhiều nếu có thể được} a:= uavg / delta ; b:= -umin * uavg / delta ; end; end; function scale(u,a,b :real) :real; {co một giá trị của hàm mục tiêu} Begin scale := a * u + b; end; procedure scalepop (popsize :integer ;var max ,avg ,min ,sumfitness :real ; var pop :poulation) ; {co toàn bộ dân số} var j :integer ; a ,b :real ; {độ dốc và phần bị chắn cho phương trình tuyến tính} Begin prescale(max ,avg ,min ,a ,b) ; {nhận độ dốc và phần bị chắn cho hàm} sumfitness := 0.0 ; for j:= 1to popsize do begin fitness :=scale(objective ,a ,b) ; sumfitness := sumfitness + fitness ; end; end; Thủ tục prescale nhận các giá trị thích nghi thô trung bình ,tối đa và tối thiểu ,là uavg ,umax ,umin và tính toán các hệ số co tuyến tính a và b dựa trên logic .Nếu có thể thì co đến bội sô 1mong muốn Cmult (trong chương trình là fmultiple) ,sau đó thực hiện tính toán .Mặt khác việc thực hiện co bằng cách chốt quanh giá trị trung bình và kéo giãn độ thích nghi cho đến khi giá trị cực tiểu dần đến 0 .Thủ tục scale sẽ được gọi sau thủ tục prescale để co tất cả các giá trị thô của các cá thể bằng cách dùng hàm scale đơn giản .Ở đây chúng ta giả thiết rằng các giá trị thích nghi thô được lưu trữ trong record indivadual trong một giá trị thực được gọi là objective(pop[j].objective) .Các độ thích nghi đã co được đặt vào thông số thực fitness ,và tổng thích nghi sumfitness sẽ được tính lại . Bằng cách này ,phép co đơn giản sẽ giúp ta ngăn chặn những chi phối sớm của những cá thể đặc biệt ,để khuyến khích sự cạnh tranh lành mạnh giữa những cá thể gần bằng nhau .Tuy nhiên ,điều này không phải là toàn bộ những nghiên cứu của chúng ta về các biến đổi hàm mục tiêu có thể có . VIII-Mà HOÁ : Để biến đổi chuỗi có chiều dài hữu hạn thành các thông số của bài toán tối ưu hoá .chúng ta đã giới thiệu một mã nhị phân đơn giản để giải bài toán bậc công tắc nhị phân đơn giản .Trong phép mã hoá này chúng ta cho phép nối dài các bit 0 ,1 ,trong đó giá trị 0(hay 1) thứ I chỉ rằng công tắc thứ I là tắt (hay mở) .Chúng ta cũng đã giải mã chuỗi nhị phân này thành số nguyên không dấu. Mặt dù ,cách mã hóa này cho chúng ta một sự linh hoạt nào đó ,nó không cung cấp đủ các chọn lựa mà chúng ta cần để giải quyết các bài toán mà chúng ta gặp trong khoa học ,kinh doanh và kỹ thuật .Trong phần này chúng ta giải quyết 2 nguyên lý cơ bản của sự mã hóa trong GAs để giúp thiết kế mã cho các bài toán khác nhau .Sau đó ,chúng ta sẽ nghiên cứu cách mã hóa chuỗi nhị phân ,đã biến đổi và đa thông số ,mà cách này đã chứng tỏ có ích lợi tropng nhiều bài toán khác nhau . Về một phương diện nào đó mã hóa một bài toán cho việc tìm kiếm trong GAs không phải là vấn đề lớn ,vì các lập trình viên GAs bị hạn chế nhiều bởi sự hình dung của họ .Chúng ta đã thấy trong chương trứớc ,các GAs khai thác những sự tương đồng trong các mã tùy ý ,cũng như là những viên gạch xâydẫn đến điểm gần tối ưu . Chúng ta dựa trên 2 nguyên lý cơ bản để mã hóa GAs : Nguyên lý khối gạch xây có nghĩa và nguyên lý bộ ký tự tối thiểu . Nguyên lý khối gạch xây có nghiã : Ngưòi sử dụng nên chọn cách mã hóa sau cho các sơ đồ bậc thấp ,ngắn sẽ thích hợp với bài toán đã cho và không có liên hệ tương đối với sơ đồ trên các vị trí khác. Nguyên lý bộ ký tự tối thiểu :Người sử dụng nên chọn bộ ký tự nhỏ nhất cho phép diễn tả bài toán một cách tự nhiên . Bảng sau sẽ thấy các chuỗi nhị phân với độ thích nghi của chúng : có được bằng cách giải mã một chuỗi nhị phân thành một số nguyên không dấu và sau đó đánh giá độ thích nghi bằng hàm f(x) = x2 . Chuỗi nhị phân Trị x Chuỗi không nhị phân Độ thích nghi 01101 13 N 169 11000 24 Y 576 01000 8 I 64 10011 19 T 361 Sự tương quan giữa mã nhị phân và mã không nhị phân Nhị phân Không nhị phân 00000 A 00001 B 00010 C … … 11001 Z 11010 1 11011 2 … … 11111 6 Trong trường hợp nhị phân vi65c tìm kiếm những tương đồng quan trọng có thể thực hiện bằng một số lượng nhỏ ký tự của bảng chữ cái .Trong trường hợp không nhị phân ,chúng ta chỉ có 4 chuỗi ký tự đơnvà các giá trị thích nghi của chúng ;không có sự tương đồng về mặt mã để khai thác . Để hiểu điều này một cách toán học hơn ,chúng ta so sánh số lượng sơ đồ có sẳn trong mã nhị phân với một sơ đồ có sẳn trong mã không nhị phân .Trong cả hai trưòng hợp mã nhị phân và không nhị phân phải mã hóa một số lượng như nhau các giải pháp ,tuy nhiên những phần chính của bộ ký tự khác nhau yêu cầu những chiều dài chuỗi khác nhau .Để cân bằng số điểm trong mỗi không gian ,chúng ta cần 2l = kl’ ,trong đó l là chiều dài chuỗi theo mã nhị phân ,l’ là chiều dài chuỗi theo mã không nhị phân .Số lượng sơ đồ theo mỗi cách mã hóa có thể được tính toán bằng cách sử dụng chiều dài chuỗi tương ứng : 3l cho trường hợp nhị phân va(k+1)l’ cho trường hợp không nhị phân.Dể dà chỉ ra rằng bộ ký tự nhị phân cung cấp một số sơ đồ tối đa trên một bit thông tin trên bộ mã bất kỳ .Từ đó, những tương đồng này là điều thiết yếu cho sự tìm kiếm,khi chúng ta thiết kế một bộ mã chúng ta nên cực đại hóa số lượng khả dụng của chúng cho GAs khai thác . IX-CÁC RÀNG BUỘC : Chúng ta chỉ mới thảo luận GAs để tìm kiếm những hàm mục tiêu không ràng buộc .Nhiều bài toán thực tế chưá một hay nhiều ràng buộc .Trong phần này chúng ta xét sự hợpnthành trong tìm kiếm theo GAs. Các ràng buộc thường được phân lớp thành các quan hệ bằng nhau hay khác nhau .Từ đó,các ràng buộc “bằng nhau” có thể được xếp vào một mô hình hệ thống – hay hộp đen ,chúng ta chỉ quan tâm đến những ràng buộc “khác nhau”.Đầu tiên ,có thể xuất hiện những ràng buộc “khác nhau” mà có thể không tạo ra bài toán riêng .Một GAs sinh ra một trình tự các thông số được kiểm tra nhờ mô hình hệ thống ,hàm mục tiêu và các ràng buộc .Đơn giản là chúng ta chỉ cần chạy mô hinh ,đánh giá hàm mục tiêu ,và kiểm tra để phát hiện các ràng buộc bị vi phạm.Nếu không tập thông số sẽ được gắn giá trị thích nghi phù hợp với sự đánh giá hàm mục tiêu .Nếu ràng buộc bị vi phạm ,giải pháp sẽ là không khả thi và do đó không thích nghi .Thủ tục này là tốt ,ngoại trừ các bài toán ứng dụng bị ràng buộc cao ;việc tìm thấy một điểm khả thi cũng khó khăn như tìm ra điểm tốt nhất .Kết quả là ,chúng ta thường muốn rút ra một số thông tinnào đó về giải pháp không khả thi ,có thể bằng cách giảm tầm quan trọng của thích nghi trong mối quan hệ với mức độ vi phạmcủa ràng buộc .Đó chính là phương pháp chụi phạt. Trong phương pháp chụi phạt ,một bài toán ràng buộc trong tối ưu hóa được biến đổi thành bài toán kông ràng buộc bằng cách kết hợp với phí tổn hay phạt với tất cả phạm vi ràng buộc .Phí tổn này được bao hàm trong sự đánh giá hàm mục tiêu .Thí dụ ,bài toán ràng buộc ban đầu với dạng tối thiểu hóa: tối thiểu hóa g(x) phụ thuộc vào hi(x) >= 0 ,I = 1,2,…,n trong đó x là một m-vectơ Chúng ta dổi sang dạng không ràng buộc : tối thiểu hóa g(x) + r. Trong đó F : hàm phạt r : hệ số chụi phạt Có một số giải pháp thực hiện hàm phạt F .Ở đây, chúng ta lấy bình phương của vi phạm ràng buộc , F|hi(x)| = hi2(x) cho tất cả mọi ràng buộc i bị vi phạm .Dưới điều kiện xác định ,giải pháp không ràng buộc sẽ hội tụ đến giải pháp ràng buộc ,khi hệ số phạt r dần đến vô cực.Trong thực tiễn ,các giá trị r trong các GAs thưởng được xáx dịnh độc lập cho mỗi ràng buộc ,vì thế những vi phạm vừa phải cuả các ràng buộc sẽ sinh ra các phần phạt ,đó là một số phần trăm đáng kể của chi phí hoạt động theo danh nghiã . --------------- ***------------------ CHƯƠNG IV SỰ CẢI TIẾN VÀ ỨNG DỤNG CỦA GIẢI THUẬT GEN I-SỰ CẢI TIẾN CỦA GIẢI THUẬT GEN: 1.Sự tiến hóa của giải thuật gen: Qua các chương , những khái niệm cơ bản của GAs đã được đề cập ,tuy nhiên để GAs thực thi có hiệu quả hơn ,người ta đã thực hiên một số cải tiến GAs chuẩn này.Trước tiêncải tiến dựa trên chọn lọc các sơ đồ và sau đó là một số cải tiến trên toan tử gen. a/Cải tiến trong việc chọn lựa các sơ đồ: Việc chọn lọc các sơ đồ được sử dụng trong GAs chuẩn đó là lựa chọn trên bánh xe roulette .Những sơ đồ này là những thành viên tốt nhất nhưng có thể thất bại trong các lần sinh kế tiếp và có thể dẫn đến những lỗi ngẫu nhiên .Để cải thiện điều này , một vài phương pháp cải tiếnđược liên kết cùng với việc chọn lựa trên bánh xe roulette đã được tiến hành. Chọn lọc ưu tú (elitist): Chiến thuật này nhằm sao chép lại thành viên tốt nhất trong một thế hệ và đưa nó vào trong thế hệ kế tiếp .Chiến thuật này có thể gia tăng tốc độ tôí ưu của một dân số bởinhững cá thể tốt và do đó không những cải thiện được việc tìm kiếmcục bộ mà còn làm cho GAs được thực hiện hoàn chỉnh hơn . Chọn lọc khi lấy mẫu (Deterministic Sampling): Trong một sơ đồ ,xác suất chọn lọc thường được tính như sau : pselecti = fi /S fj .Sau đó số con cái ei trong một chuỗi Ai được tính bởi ei = n * pselecti .Mỗi chuỗi sẽ cấp phát một số con cái tùy thuộc vào giá trị ei .Những chuỗi còn lại cần phải điền cho đầy một dân số thì sẽ được lấy ra theo thứ tự từ đầu dân số đã được sắp xếp trước . Lấy phần mẫu còn lại ngẫu nhiên có thay thế (Remainder Stochatic Sampling With Replacement) :Sau khi đã tính số con cái ei trong một sơ đồ đã được chọn lọc để lấy mẫu trong giai đoạn trên , thì phần nguyên của ei sẽ gán cho những cá thể có trong dân số đó ,còn phần lẻ của ei sẽ được sử dụng để tính trọng số trong việc chọn lựa trên vòng tròn bánh xe để sinh ra các cá thể còn lại. Lấy mẫu còn lại ngẫu nhiên và không thay thế ( Remainder Stochatic Sampling Without Replacement ) :Cũng tương tự như trên nhưng phần lẻ của giá trị ei bây giờ được xem như là xác suất. Hay nói cách khác ,số lần tham gia vào trong quá trình sinh sản của một chuổi bằng với giá trị phần nguyên của ei .Sau đó ,để đảm bảo đủ kích thước dân số , ta chọn những con cái khác của những chuỗi với xác suất tương đương với phần lẻ của số cá thể mong đợi cho đến khi đạt được kích thước dân số n .Ví dụ 1 chuỗi với số bản copy mong đợi là 1.5 ,chắc chắn sẽ nhận được một bản copy và một bản copy khác với xác suất 0.5 Ranking Procedure : Theo phuơng pháp này ,một dân số được sắp xếp tùy thuộc vào giá trị fitness .Sau đó ta gán các cá thể này cho mỗi một con cháu mà có hàm gần giống với Rank .Một hàm Rank do BanKer đề ra (1985) : Count Rank Khi đó : Trong đó lmax là giá trị do user đưa vào ,1 < lmax <=2 với n là kích thước dân số .Miền ei sau đó sẽ là[2 - lmax , lmax].Phương trình trên là một trường hợp đặc biệt. 2-Cải tiến trên các toán tử tối ưu : GAs là sự kết hợp của 3 toán tử :tái tạo ,ghép chéo và đột biến .Chúng tác động ở cấp độ trên toàn bộ dân số ,ta có một số cải tiến trên các toán tử này như sau: Ghép chéo nhiều điểm: Toán tử ghép chéo mà ta sử dụng từ trước đến giờ là ghép chéo chỉ trên 1 bit đơn tại 1 vị trí được. Quá trình ghép chéo này có thể tiến hóa thành ghép chéo nhiều điểm mà trong đó số điểmghép chéo sẽ được cho trước Nc .Khi Nc = 1 thì trở thành ghép chéo đơn ,với Nc chẳn chuỗi được xem như là một chuỗi không có sự bắt đầu và kết thúc ,và số điểm ghép chéo Nc được chọn xung quanh một vòng tròn đồng nhất một cách ngẫu nhiên. Quá trình ghép chéo nhiều điểm có thể giải quyết 1 tổ hợp cụ thể các đặt tính đã được mã hóa trên một chuỗi nhiễm sắc thể mà sự ghép chéo một điểm không giải quyết được. Giả sử ta có hai chuỗi : Chuỗi 1 : 10110001100 Chuỗi 2 : 00101101001 Trong đó các bits gạch dưới biểu diễn cho những sơ đồ có tính hoàn thiện cao .Giả sử một trong hai sơ đồ này hoán chuyển thì sẽ mất đi thuận lợi trong quá trình ghép chéo .Rõ ràng ghép chéo một điểm không thể tránh được điều này ,sơ đồ 1 sẽ bị phá vỡ và không được truyền đi .Vấn đề này có thể giải quyết bằng ghép chéo hai điểm như sau : Chuỗi 1 : 1 0 1 1 | 0 0 0 1 | 1 0 0 Chuỗi 2 : 0 0 1 0 | 1 1 0 1 | 0 0 1 Chuỗi con 1 : 1 0 1 1 1 1 0 1 1 0 0 Chuỗi con 2 : 0 0 1 0 0 0 0 1 0 0 1 Một cách khác thể hiện sự ghép chéo nhiều điểm là ghép chéo đồng nhất đã được giới thiệu bởi Syswerda(1989) .Theo cách này ,hai chuỗi parents được chọn và hai chuỗi children sẽ được tạo ra .Với mỗi vị trí trên hai chuỗi con ,chúng ta quyết địng ngẫu nhiên chuỗi cha nào đó đóng góp giá trị bit vào chuỗi con này tùy thuộc vào khuôn mẫu (template) đã được chọn ngẫu nhiên .Quá trình được mô tả như sau : parent 1 : 01100111 parent 2 : 11010001 template: 01101001 Tương ứng với 0 thì lấy chuỗi 1 còn 1 thì lấy chuỗi 2 và ngược lại.Kết quả : child 1 : 11110001 child 2 : 01000111 Mặc dù ghép chéo nhiều điểm có ưu điểm trên ,nhưng đôi khi nó dẫn đến cấu trúc phức tạp . Các toán tử tái lập lại bậc : Không giống như toán tử từ trước chỉ tìm kiếm trên tập allele tốt ,các toán tử này còn tìm kiếm trên những cách mã hóa cũng như tập các giá trị allele tốt hơn .Những toán tử này thích hợp cho bài toán mà giá trị fitness phụ thuộc vào sự sắp xếp chuỗi ,chẵn hạn như trị fitness phụ thuộc vào tổ hợp của các giá trị allele v và bậc o , f = f(v,o) ,một chuỗi kết hợp các giá trị allele và các thônh tin có thể biểu diễn như sau : 12345678 10010001 Tron