Download miễn phí Đồ án Nghiên cứu về giải thuật di truyền và ứng dụng dò tìm khóa mật
- 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.
http://s1.liketly.com/flash/edoc/web-viewer.html?file=jh2i1fkjb33wa7b577g9lou48iyvfkz6-demo-2016-01-14-do_an_nghien_cuu_ve_giai_thuat_di_truyen_va_ung_dung_do_tim_3UEbvUQIAG.png /tai-lieu/do-an-nghien-cuu-ve-giai-thuat-di-truyen-va-ung-dung-do-tim-khoa-mat-87373/ Để tải tài liệu này, vui lòng Trả lời bài viết, Mods sẽ gửi Link download cho bạn ngay qua hòm tin nhắn. Ket-noi - Kho tài liệu miễn phí lớn nhất của bạn
Ai cần tài liệu gì mà không tìm thấy ở Ket-noi, đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
Bé gi¸o dôc vµ ®µo t¹o Trê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 thay mặt 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 hay 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
– DF + ∑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...
