Đồ án Nghiên cứu về giải thuật di truyền và ứng dụng dò tìm khóa mật

Bé gi¸o dôc vµ ®µo t¹oTr­êng ®¹i häc d©n lËp h¶i phßngĐề tài: NGHIÊN CỨU VỀ GIẢI THUẬT DI TRUYỀN VÀ ỨNG DỤNG DÒ TÌM KHÓA MẬT Giáo viên hướng dẫn : PGS.TS.Trịnh Nhật Tiến Sinh viên thực hiện : Nguyễn Thanh Phương H¶i phßng 20081Nội dung báo cáoI. Tæng quan vÒ gi¶i thuËt di truyÒnII. Chương trình tiến hóaIII. øng dông gi¶i thuËt di truyÒn dß t×m khãa m· thay thÕ ®¬n 2“Giải thuật di truyền” là một kỹ thuật của khoa học máy tính nhằm tìm kiếm giải pháp thích hợp cho các bài toán tối ưu tổ hợp (combinatorial optimization) “Giải thuật di truyền” là một dạng của “giải thuật tiến hóa” vận dụng các nguyên lý của tiến hóa như di truyền, đột biến, chọn lọc tự nhiên, và trao đổi chéo. Kh¸i niÖm vÒ gi¶i thuËt di truyÒn3 Giải thuật di truyền thường được ứng dụng nhằm sử dụng ngôn ngữ máy tính để mô phỏng quá trình tiến hoá của một tập hợp những đại diện trừu tượng của các giải pháp có thể cho bài toán tối ưu hóa vấn đề. Quá trình tiến hóa xảy ra từ một tập hợp những cá thể hoàn toàn ngẫu nhiên ở tất cả các thế hệ. Trong từng thế hệ, tính thích nghi của tập hợp này được ước lượng, nhiều cá thể được chọn lọc (dựa vào thể trạng), được sửa đổi (bằng đột biến hoặc tổ hợp lại) để hình thành một tập hợp mới. Tập hợp này sẽ tiếp tục được chọn lọc lặp đi lặp lại trong các thế hệ kế tiếp của giải thuật.4 SƠ ĐỒ TỔNG QUÁT CỦA THUẬT GIẢI DI TRUYỀN 5a/. Phép lai Phép lai là quá trình hình thành nhiễm sắc thể mới trên cơ sở các nhiễm sắc thể cha-mẹ, bằng cách ghép một hay nhiều đoạn gen của hai (hay nhiều) nhiễm sắc thể cha-mẹ với nhau.Phép lai với xác suất Pc có thể mô phỏng như sau: - Chọn ngẫu nhiên hai (hay nhiều) cá thể bất kì trong quần thể. Giả sử các nhiễm sắc thể của cha-mẹ đều có m gen. - Tạo một số ngẫu nhiên trong khoảng từ 1 đến m - 1 ( gọi là điểm lai) - Điểm lai chia các chuỗi cha-mẹ dài m thành hai nhóm chuỗi con dài dài m1 và m2. - Đưa hai cá thể mới này vào quần thể để tham gia các quá trình tiến hoá tiếp theo.1/. C¸c phÐp to¸n di truyÒn6 Đột biến là hiện tượng cá thể con mang một (số) tính trạng không có trong mã di truyền của cha-mẹ.Một phép đột biến có thể mô phỏng như sau: -Chọn ngẫu nhiên một cá thể cha-mẹ bất kì trong quần thể.-Tạo một số ngẫu nhiên k trong khoảng từ 1 đến m (1≤ k ≤ m)-Thay đổi gen thứ k và trả cá thể này về quần thể để tham gia quá trình tiến hoá tiếp theo.b/. Phép đột biến7c/. Phép tái sinh và phép chọn - Phép tái sinh là quá trình trong đó các cá thể được sao chép trên cơ sở độ thích nghi của nó. - Phép chọn là quá trình loại bỏ các cá thể xấu trong quần thể để chỉ giữ lại trong quần thể các cá thể tốt. - Phép chọn có thể được mô phỏng như sau:  + Sắp xếp quần thể theo thứ tự độ tốt giảm dần. + Loại bỏ các cá thể cuối dãy để chỉ giữ lại m cá thể tốt nhất, ở đây ta giả sử quần thể có kích thước cố định m.8 Một thuật giải di truyền giải bài toán, phải có 5 thành phần sau: - Một cấu trúc dữ liệu I biểu diễn không gian lời giải của bài toán. - Phương pháp khởi tạo quần thể ban đầu P(0). - Hàm định nghĩa độ thích nghi Eval(.) đóng vai trò môi trường. - Các phép toán di truyền: + Phép lai ghép + Phép đột biến + Phép tái sinh và phép chọn lọc - Các tham số dùng trong giải thuật di truyền: kích thước quần thể, xác suất lai, đột biến ... 2/. Các thành phần trong “Giải thuật di truyền”9C¸c b­íc cña thuËt gi¶i di truyÒn B­íc 1 : Gen hoá vấn đề của bài toán + Xác định cá thể + Biểu diễn cá thể B­íc 2 : Xác định hàm thích nghi B­íc 3: Xác định các toán tử di truyền (lai ghép, đột biến, chọn lọc) cùng với các thông số ngẫu nhiên của nó. + Toán tử lai ghép (Crossover): + Toán tử đột biến (Mutation): + Toán tử chọn lọc (Selection): + Một số vấn đề về chọn tập tái sinh B­íc 4: Tạo quần thể ban đầu, kích thước tối đa của quần thể và tiến hoá quần thể : Ở những bước trên, ta xác định các yếu tố đặc trưng của quần thể tương đối cố định bao gồm : các cá thể, các toán tử di truyền (lai ghép, đột biến, chọn lọc, tái sinh). Tại bước này, ta sẽ kết hợp những cái đó lại thành một giải thuật di truyền cụ thể.10 Là khái niệm dùng để chỉ các chương trình máy tính có sử dụng các thuật toán tìm kiếm và tối ưu hoá dựa trên nguyên lý tiến hoá tự nhiên. Quá trình tiến hoá thể hiện tính tối ưu ở chỗ, thế hệ sau bao giờ cũng tốt hơn, phát triển hơn, hoàn thiện hơn thế hệ trước. Tiến hoá tự nhiên được duy trì nhờ hai quá trình cơ bản: sinh sản và chọn lọc tự nhiên. II. Ch­¬ng tr×nh tiÕn hãa11 Trong thuật giải di truyền, các cá thể mới liên tục được sinh ra trong quá trình tiến hoá nhờ sự lai ghép ở thế hệ cha-mẹ. Một cá thể mới có thể mang những tính trạng của cha-mẹ (di truyền), cũng có thể mang những tính trạng hoàn toàn mới(đột biến). Di truyền và đột biến là hai cơ chế có vai trò quan trọng như nhau trong tiến trình tiến hoá, dù rằng đột biến xảy ra với xác xuất nhỏ hơn rất nhiều so với hiện tượng di truyền. Các thuật toán tiến hoá đều mô phỏng bốn quá trình cơ bản: Lai ghép, đột biến, sinh sản và chọn lọc tự nhiên. 12Bài toán dò tìm khoá mật trong mã thay thế đơn.*Bµi to¸nCho mét b¶n tin ®­îc m· hãa b»ng khãa m· thay thÕ ®¬n nh­ sau: MTVSFDECRXBUQJYGKLWHANIOZP víi ®é phï hîp: 0.9421675Yªu cÇu: B»ng giải thuật di truyền dß tìm khãa mËt trªn.III. øng dông GA dß t×m khãa m· thay thÕ ®¬n13* Thùc hiÖn thuËt to¸n di truyÒn ®Ó t×m khãa 1/. Biểu diễn khóa . - Khóa mã thay thế đơn có thể được biểu diễn như một danh sách (chuỗi, xâu) các chữ cái trong bảng Alphabet. Trât tự đó thể hiện tần số xuất hiện từng chữ cái trong bản mã , còn thể hiện ngầm cả sự thay thế. - Ví dụ một khóa có dạng: CDEFGEIJKLMNOPQRSTUVWYZAB Trong tiếng Anh, thứ tự tần xuất xuất hiện các chữ cái trong bản rõ là: ETAOINHSRDLUMWCGFYPBKVJXQZ Ở đây E có tần số xuất hiện nhiều nhất, chữ Z có tần số xuất hiện ít nhất. Theo qui tắc mã hóa thay thế đơn, chữ E trong bản rõ sẽ được thay thế bởi chữ C trong bản mã.142/. Hàm đánh giá. Hàm đánh giá dùng để quyết định khóa nào tốt hơn, được chọn dựa trên phân tích tần số xuất hiện chữ cái đơn lẻ và bộ hai chữ cái. Quá trình đánh giá như sau:a/. Chọn khóa ban đầu để giải mã một bản mã, sẽ được bản rõ. b/. Văn bản rõ sẽ được phân tích tần số xuất hiện của các chữ cái đơn và bộ đôi (2 chữ cái liền nhau).c/. Kết quả phân tích tần số được so sánh với tần số tiếng Anh chuẩn để xác định độ sai lệch Độ sai lệch của chữ I =Tần số xuất hiện chữ I trong tiếng Anh chuẩn-Tần số xuất hiện chữ I trong bản giải mã.15Tổng / Độ sai lệch / của 26 chữ cái là : 26 26 Dif= ∑i=1 { |SF[i] – DF [i] + ∑j=1 |SDF[I,j] – DDF [i,j] |}d/. Độ phù hợp là F =1-Dif . Độ sai lệch càng nhỏ, thì độ phù hợp càng cao.e/. Tổng các độ sai lệch được chia cho 4 để giảm sự nhạy cảm trong trường hợp có độ sai lệch càng lớn và tránh được việc tổng các độ sai lệch lớn hơn 1.f/. Độ phù hợp được tăng lên bội của 8 để làm tăng lên sự khác nhau nhỏ giữa các giá trị giữa chúng 8 F =(1 –Dif /4) 16Qui trình trao đổi chéo như sau : Giải thuật chọn ngẫu nhiên 2 khóa (bố mẹ) và trao đổi chéo. Việc lựa chọn này là ngẫu nhiên, nhưng vẫn có trọng số theo hướng : các khóa có độ phù hợp cao thì sác xuất được chọn sẽ cao.Hai khóa bố mẹ sinh ra 2 khóa con thông qua việc trao đổi chéo sau : + Duyệt từng cặp phần tử (cặp chữ cái) tương ứng của 2 khóa bố mẹ (duyệt từ đầu phải để sinh ra con 1, duyệt từ đầu trái để sinh ra con 2) . +Với mỗi cặp phần tử như vậy ,chọn ra chữ cái có tần số xuất hịên nhiều hơn trong bản mã , để đưa vào khóa con.3/. Qui trình trao đổi chéo17Thực hiện qui trình trao đổi chéo với hai bố mẹ Bố  : CDEFGHIJKLMNOPQRSTUVWXYZAB Mẹ : FGHIJKLMNOPQRSTUVWXYZABCDE * Duyệt từ đầu phải của khóa bố mẹ , để sinh ra khóa con 1 : Con 1 : FDEIJHLMKOPQRSTUVWXYZABCDE Kí tự đầu tiên của con1 là F vì nó xuất hiện nhiều hơn trong bản mã so với C.+ Nếu trong cặp kí tự đang xét, một chữ cái có tần số xuất hiện nhiều hơn chữ kia, nhưng nó đã có mặt trong khóa con, thì chữ cái còn lại trong cặp sẽ được chọn cho khoá con. + Nếu trong cặp kí tự đang xét, cả hai chữ cái đều có mặt trong khóa con, nhưng nó đã có mặt trong khóa con, thì chữ cái cho khóa con sẽ được chọn ngẫu nhiên trong các chữ cái chưa xuất hiện trong khóa con.* Duyệt từ đầu trái của khóa bố và mẹ, để sinh ra khóa con 2, như sinh con 1 : Con 2 : CDVFGHIJKLMNOPQRSTUYWXBZAE18Qui trình đột biến như sau :+ Khi một kí tự trong khóa được chọn đột biến, nó sẽ chuyển đổi vị trí với một chữ cái được chọn ngẫu nhiên trong khóa, nếu độ phù hợp của khóa thuộc nửa dưới của thế hệ khóa đang xét. + Nếu độ phù hợp của khóa thuộc nửa trên của thế hệ khóa, thì chữ cái được chọn để đột biến, sẽ ®­îc đổi vị trí với chữ cái bên phải nó .4/. Qui trình đột biến19Giải thuật gồm các bước sau: 1). Một tập các khóa (thế hệ khóa) ban đầu được sinh ra ngẫu nhiên. 2). Xác định độ phù hợp của từng khóa. 3). Từng cặp khóa cha mẹ được chọn ngẫu nhiên có định hướng dựa trên độ phù hợp của các khóa. 4). Qui trình trao đổi chéo được áp dụng đối với từng cặp khóa cha mẹ đã chọn. 5). Qui trình đột biến với tần số thấp được áp dụng với các khóa con đã sinh ra. 6). Thế hệ dân số mới của các khóa được duyệt để cập nhật một danh sách 10 khóa tốt nhất trong toàn bộ các thế hệ. 7). Thuật toán dừng sau một số lương nhất định các thế hệ và các khóa tốt nhất được sử dụng để giải mã văn bản.5/.Giải thuật hoàn chỉnh20*Kết quả thực nghiệmBản tin được mã hóa bằng khóa mật : MTVSFDECRXBUQJYGKLWHANIOZP với độ phù hợp 0.9421675 Theo giải thuật di truyền, khóa mật được hình thành dần bắt đầu từ thế hệ khóa dự tuyển đầu tiên (được sinh ngẫu nhiên).Sau nhiều làn phát triển qua ‘sinh sản’ và ‘đột biến’ tập khóa dự tuyển ‘trưởng thành’, để hội tụ tới khóa mật ‘chính hiệu’.1/. Kết quả cài đặt giải thuật di truyền21* Mô tả quá trình ‘trưởng thành’ của khóa mật từ thế hệ khóa dự tuyểna). Thế hệ khóa dự tuyển đầu tiên:Gồm 10 khóa, được sinh ngẫu nhiên có độ phù hợp tương ứng bên cạnh:1. PSYEIUXDWBNJZKCQMVHOLTGAFR 0. 3433762. BRPAQONHXIFJWDZTGLEMUKSVYC 0. 2767393. GIXCOWMZFPVTNUHYJKRQDSELAB 0. 347094. FYWURETDXVOSHICKPBQLMGJZNA 0. 4485365. GFLITACYVXWPQZRDNOEJUKSHMB 0. 3478186. YAWNUIJBLXDFMSOZVGQKHEVPTC 0. 2928877. QRUZIVEXCJPGBOHMNSTAYDLWFA 0. 3329248. BZTRPJIODCNXYGMQHEUAWKFVSL 0. 3416379. WDJQRVLENAIGHCYZBMPFOTXSKU 0. 32107410. HIACSLYQPOKVJTGNEWBDFRXZUM 0. 301443Thế hệ khóa đầu tiên có độ phù hợp trung bình là 0. 33535322b). Thế hệ khóa thứ nhất: Được tính bằng giải thuật di truyền,có độ phù hợp tương ứng bên cạnh: 1. GFXCTWMYVPSAQURDJKELBOZHNI 0. 483116 2. FYWURETDXVOSHICKPBQLMGJZNA 0. 448536 3. SGDJTIMLVXWPFCZYNORQUKEHAB 0. 439237 4. GFLITACYWXVPQRZDNOEUKSHMBJ 0. 347818 5. GIXCOWMZFPVTNUHYJKRQDSELAB 0. 34709 6. PSXYEIUXDWBNJZKCQMVHOLTGAF 0. 34337 7. BZTRPJIODCNXYGMQHEUAWKFVSL 0. 341637 8. QRUZIVEXCJPKGBOHMNSTAYDLWF 0. 332924 9. WDJQRVLENAIGHCYZUBMPFOTXSK 0. 321074 10. HIACSLYQPOKVJTGNEWBDFRXZUM 0. 301443Thế hệ khóa thứ nhất có độ phù hợp trung bình là 0.370625Độ phù hợp của quần thể tăng theo hướng ngày càng phù hợp hơn.23d) Thế hệ khóa thứ 250 : 1. MVTSFDECRXBYQULGKJHWANOZIP 0. 879804 2. MVTSFDECRXBYQULGKJHWANOZIP 0. 876283 3. MVTSFDECRXBUQLAGJKHWPYNZIO 0. 875058 4. MVTSFDECRXBUQLAGJKHWPNYZOI 0. 874911 5. MVTSFDECRXBUQLAGJKHWPNOZIP 0. 874024 6. MVTSFDECRXBJQULGWKHOANYZIP 0. 857039 7. MVTSFDECRXBJQULGWKHOANPZIY 0. 855014 8. MVTSFDECRXBJQULGWKHOANPZIY 0. 840219 9. MVTSFDECRXBJQULGWKHYANPZOI 0. 83318610. MVTSFDECRYBJQULGWKHOANPZXI 0. 820659Thế hệ khóa thứ 250 có độ phù hợp trung bình là 0.85862Ta nhận thấy rằng các khóa trong toàn bộ thế hệ khóa đã có phần đầu là: MVTSFDECRXBNhư vậy thì các chữ cái có tần số cao trong tiếng Anh chuẩn đã được nhận ra. Đến đây thì ta đã có thể đọc đuợc bản giải mã, hoặc có thể đoán đuợc các chữ cái bị sai.24e). Thế hệ khóa thứ 1000 : 1. MVTSFDECRXBUQJYGKLWHANIOZP 0.942167 2. MVTSFDECRXBUQJAGJKHWPYNOPZ 0.941364 3. MVTSFDECRXBUQLAGJKHWPYNOIZP 0.94066 4. MVTSFDECRXBUQLAGJKHWPYNIZOP 0.940408 5. MVTSFDECRXBUQLAGJKHWPYNIPOZ 0.940364 6. MVTSFDECRXBUQLAGJKWHPYNIPOZ 0.939856 7. MVTSFDECRXBUQLAGJKHWYNIPOZP 0.934928 8. MVTSFDECRXBUQLAGJKHWPYNIOPZ 0.9348999. MVTSFDECRXBUQLAGJKHWPYNIOPZ 0.93412410. MVTSFDECRXBUQLAGJKHWPYNIPOZ 0.934096Thế hệ khóa thứ 1000 có độ phù hợp trung bình là 0.938287Cá thể thứ nhất có độ phù hợp là cao nhất (0.942167) và hoàn toàn trùng với khóa mà ta đang cần tìm25IV. KẾT LUẬN Trong thời gian thực tập em đã cố gắng tìm hiểu nghiên cứu các tài liệu liên quan . Và đã đưa ra được cơ sở lý thuyết của đề tài để từ đó tiếp tục xây dựng và hoàn chỉnh đề tài. Tuy nhiên bài báo cáo của em vẫn còn những chỗ thiếu sót. Mong các thầy cô giáo và các bạn góp ý để em hoàn thành đề tài của mình.Thuật giải di truyền (GA) là kỹ thuật chung giúp giải quyết vấn đề-bài toán bằng cách mô phỏng sự tiến hóa của con người hay của sinh vật nói chung (dựa trên thuyết tiến hóa muôn loài của Darwin) trong điều kiện qui định sẵn của môi trường. GA là một thuật giải, nghĩa là mục tiêu của GA không nhằm đưa ra lời giải chính xác tối ưu mà là đưa ra lời giải tương đối tối ưu.26