Đồ án Nghiên cứu tính toán phần mềm và ứng dụng "dò tìm mã DES"

BỘ GIÁO DỤC ĐÀO TẠO TRƯỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG --------o0o-------- iso 9001 : 2000 NGHIÊN CỨU TÍNH TOÁN MỀM VÀ ỨNG DỤNG ĐỒ ÁN TỐT NGHIỆP HỆ ĐẠI HỌC CHÍNH QUY Ngành: Công nghệ thông tin Sinh viên thực hiện : BÙI THỊ OANH Giáo viên hướng dẫn : PGS.TS.TRỊNH NHẬT TIẾN Mã sinh viên : 090112 HẢI PHÒNG 2009 LỜI CẢM ƠN Em xin chân thành cảm ơn sự giúp đỡ của PGS.TS.Trịnh Nhật Tiến, người đã trực tiếp hướng dẫn, tận tình chỉ bảo tạo điều kiện cho em hoàn thành khóa luận đúng thời hạn. Em xin chân thành cảm ơn tất cả các thầy cô giáo trong khoa Công nghệ thông tin - Trường ĐHDL Hải Phòng, những người đã nhiệt tình giảng dạy và truyền đạt những kiến thức cần thiết trong suốt thời gian em học tập tại trường, để em hoàn thành tốt khóa luận. Cuối cùng em xin cảm ơn tất cả các bạn đã góp ý, trao đổi hỗ trợ cho em trong suốt thời gian vừa qua. Em xin chân thành cảm ơn! Hải Phòng, tháng 07 năm 2009 Sinh viên Bùi Thị Oanh MỤC LỤC Danh mục các từ viết tắt NST Nhiễm sắc thể GA Genetics Algorithms DES Data Encryption Standard. Danh mục các thuật ngữ thông dụng trong giải thuật di truyền Trong tự nhiên Trong giải thuật di truyền Gene Đặc tính, ký tự Chromosome (Nhiễm sắc thể) Chuỗi Allele (gene tương ứng) Giá trị của đặc tính Locus (ổ gene) Vị trí chuỗi Genetype (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ã LỜI NÓI ĐẦU Trong thực tế cuộc sống, các bài toán liên quan đến hệ thống nhận thức, tri thức của con người, đều hàm chứa những đại lượng, thông tin, mà bản chất là không chính xác, không chắc chắn, không đầy đủ…. cho các hệ thống ra quyết định. Ví dụ: Sẽ chẳng bao giờ có thông tin, dữ liệu, cũng như các mô hình tính toán đầy đủ và chính xác cho bài toán dự báo thời tiết. Trong lĩnh vực khoa học cũng vậy, các hệ thống phức tạp trên thực tế thường không thể mô tả đầy đủ, và chính xác bởi các phương trình toán học truyền thống. Kết quả là những cách tiếp cận kinh điển dựa trên kỹ thuật phân tích, và các phương trình toán học nhanh chóng không còn phù hợp. Vì thế công nghệ tính toán mềm chính là giải pháp cần thiết trong lĩnh vực này. Công nghệ tính toán mềm bao gồm 3 thành phần chính: Điều khiển mờ (Fuzzy Control) Mạng nơ-ron nhân tạo (Neural Network) Giải thuật di truyền (Genetic Algorithm) Do thời gian không nhiều và khối lượng công việc tìm hiểu khá lớn nên trong khuôn khổ đồ án tốt nghiệp này, để tìm hiểu cho sâu, em tập trung nghiên cứu giải thuật di truyền. Hiện nay, thuật toán di truyền cùng với logic mờ được ứng dụng rộng rãi trong các lĩnh vực phức tạp, các vấn đề khó, sử dụng các kỹ thuật tìm kiếm lời giải, với không gian tìm kiếm rất lớn, nhất là những bài toán cần có sự lượng giá, đánh giá sự tối ưu của kết quả thu được. Chính vì vậy, thuật giải di truyền đã trở thành đề tài nghiên cứu thú vị và đem đến nhiều ứng dụng trong thực tiễn. Xuất phát từ những vấn đề trên, khóa luận đã tìm hiểu, nghiên cứu giải thuật di truyền. Sau đó sử dụng giải thuật di truyền cổ điển kết hợp với phương pháp thống kê ngôn ngữ học giải quyết bài toán “Dò tìm mã DES”. Khóa luận không tránh khỏi những thiếu sót, rất mong được sự giúp đỡ, chỉ bảo của thầy cô và các bạn! Chương 1: TÍNH TOÁN MỀM KHÁI NIỆM TÍNH TOÁN MỀM Tính toán mềm (Soft Computing) khác với tính toán cứng truyền thống (Hard Computing) ở chỗ: không như tính toán cứng, tính toán mềm cho phép sự không chính xác, tính bất định, gần đúng, xấp xỉ trong tính toán. Các mô hình tính toán mềm thường dựa vào kinh nghiệm của con người, sử dụng dung sai cho phép của sự không chính xác, tính bất định, gần đúng, xấp xỉ để tìm lời giải hiệu quả - đơn giản, dễ hiểu, dễ thực hiện, chi phí thấp. Tính toán mềm biểu thị một sự chuyển dịch, biến hoá quan trọng trong các hướng tính toán. Sự chuyển dịch này phản ánh sự kiện trí tuệ con người, không như máy tính, có khả năng đáng kể trong việc lưu trữ và xử lý thông tin không chính xác và bất định, và đây mới là những thông tin thực tế và thường gặp. Các ứng dụng thành công của tính toán mềm cho thấy tính toán mềm ngày càng phát triển mạnh và đóng vai trò đặc biệt trong các lĩnh vực khác nhau của khoa học và kỹ thuật. Tính toán mềm được ứng dụng trong hầu hết các chuyên ngành kỹ thuật như kỹ thuật điện, kỹ thuật điều khiển, kỹ thuật hoá học, kỹ thuật xây dựng,... Kỹ thuật điện là lĩnh vực đầu tiên ứng dụng tính toán mềm trong các lĩnh vực như điều khiển mờ, xử lý ảnh mờ, mạch điện tử dùng logic, người máy,.... Khái niệm “Tính toán mềm” được Zadeh đưa ra lần đầu tiên vào năm 1994 được mô tả như sau: “Một cách cơ bản, tính toán mềm không phải là thể thống nhất các khái niệm và kỹ thuật. Đúng ra, nó là sự kết hợp của các phương pháp riêng biệt theo cách này hay cách khác để thích nghi với nguyên lý của nó. Tại điểm giao đó, mục đích cuối cùng của tính toán mềm là khai thác khả năng thứ lỗi (Tolerance) cho tính không chính xác hay tính bất định để đạt được mục tiêu với chi phí thấp”. Một cách đơn giản hơn, “Tất cả các tính toán có bao gồm tính không chính xác một cách có chủ đích trong tính toán ở một hay nhiều mức và cho phép tính không chính xác này làm thay đổi (làm giảm) độ chính xác của bài toán, hay “làm mềm” mục tiêu tối ưu ở một số bước, đều bị coi là thuộc lĩnh vực tính toán mềm”. PHÂN BIỆT TÍNH TOÁN MỀM VÀ TÍNH TOÁN CỨNG Tính toán truyền thống, hay còn gọi là tính toán cứng, là phương pháp sử dụng các kỹ thuật tính toán, dựa trên dữ liệu đầu vào để đưa ra kết quả cuối cùng một cách chính xác theo yêu cầu của bài toán. Bảng dưới đây đưa ra một số điểm khác biệt giữa tính toán mềm và tính toán cứng, để chúng ta có được một hình dung cụ thể hơn về tính toán mềm. Điểm so sánh Tính toán cứng Tính toán mềm Dữ liệu xử lý Xử lý bài toán dựa trên số liệu chính xác. Ví dụ: Giá trị của A phải là 0 hoặc 1: {0,1} Không đòi hỏi dữ liệu phải chính xác. Ví dụ: Giá trị của A có thể nằm trong khoảng từ 0 đến 1: [0,1] Kết quả đầu ra - Yêu cầu đưa ra kết quả tối ưu (kết quả chính xác hoàn toàn) Yêu cầu đưa ra kết quả gần tối ưu (cho phép sự sai lệch nhất định trong kết quả tìm được) Kỹ thuật tính toán - Sử dụng kỹ thuật tính toán truyền thống Kỹ thuật tính toán dựa trên Heuristic được sử dụng phổ biến Thời gian tính toán - Thời gian tính toán thường chậm hơn. Trong một số trường hợp, không thể đưa ra kết quả trong thời gian chấp nhận được - Thời gian tính toán nhanh hơn với chi phí thấp hơn Lĩnh vực áp dụng Các bài toán yêu cầu lời giải chính xác, không cho phép sự sai lệch. Các bài toán không yêu cầu lời giải chính xác, song phải đưa ra kết quả trong một khoảng thời gian nhất định với chi phí nhất định Bảng 1: So sánh tính toán cứng và tính toán mềm TẠI SAO CẦN PHẢI CÓ TÍNH TOÁN MỀM Trong thực tế cuộc sống, các bài toán liên quan đến hệ thống nhận thức, trí tuệ của con người đều hàm chứa những đại lượng, thông tin không chính xác, không chắc chắn, không đầy đủ. Ví dụ: sẽ chẳng bao giờ có các thông tin, dữ liệu cũng như các mô hình tính toán đầy đủ, và chính xác cho bài toán dự báo thời tiết. Nhìn chung con người luôn ở trong bối cảnh không có thông tin chính xác, và đầy đủ cho các hệ thống ra quyết định. Trong lĩnh vực khoa học kỹ thuật cũng vậy, các hệ thống phức tạp trên thực tế thường không thể mô tả một cách đầy đủ, và chính xác bởi các phương trình toán học truyền thống. Kết quả là những cách tiếp cận kinh điển dựa trên kỹ thuật phân tích, và các phương trình toán học nhanh chóng tỏ ra không còn phù hợp. Vì thế, công nghệ tính toán mềm chính là giải pháp trong lĩnh vực này. Một số đặc điểm của công nghệ tính toán mềm: Tính toán mềm căn cứ trên các đặc điểm, hành vi của con người, và tự nhiên để đưa ra quyết định hợp lý trong điều kiện không chính xác, không chắc chắn. Các thành phần của tính toán mềm có sự bổ sung, hỗ trợ nhau. Tính toán mềm là một hướng nghiên cứu mở, bất kỳ một kỹ thuật mới nào được tạo ra từ việc bắt chước trí thông minh của con người, đều có thể trở thành một thành phần mới của tính toán mềm. Chính nhờ những đặc điểm đó mà tính toán mềm đang được nghiên cứu và ứng dụng rộng rãi trong nhiều lĩnh vực, đặc biệt là: trí tuệ nhân tạo, khoa học máy tính và học máy. Cụ thể: Không phải bài toán nào cũng có thuật toán có thể giải quyết được bằng tính toán cứng. Không phải bài toán nào có thuật toán có thể giải quyết được bằng tính toán cứng, cũng có thể thực hiện với chi phí và thời gian chấp nhận được. Khi bản thân dữ liệu là không chính xác thì không thể giải quyết được bằng phương pháp chính xác. Với những ưu thế đó, tính toán mềm đang dần thể hiện vai trò của mình nhất là trong việc giải quyết vấn đề mới. CÁC KỸ THUẬT TRONG TÍNH TOÁN MỀM Công nghệ tính toán mềm bao gồm 3 thành phần chính: Điều khiển mờ (Fuzzy Control) Mạng nơ-ron nhân tạo (Neural Network) Giải thuật di truyền (Genetic Algorithm) Logic mờ (Fuzzy Logic – FL) Khái niệm tập mờ (Fuzzy set) được Zadeh đưa ra vào năm 1965 với mục đích cho phép các phần tử thuộc về một tập liên tục thay cho rời rạc. Kể từ đó, các ứng dụng và phát triển dựa trên khái niệm tưởng chừng rất đơn giản này, đã mang lại những kết quả khó có thể tin được, thậm chí khó có thể chỉ ra các ứng dụng, phát triển hay sản phẩm nào không có liên quan đến khái niệm tập mờ. Ví dụ: chúng ta thường nghe đến nhiều thuật ngữ như: máy giặt fuzzy, quạt fuzzy, xe máy fuzzy... Khái niệm tập mờ có vai trò rất quan trọng trong việc giải quyết các bài toán tối ưu, đưa ra các bài toán có tính thực tế, giải quyết bài toán với chi phí thấp và trong thời gian nhanh hơn (mặc dầu chấp nhận việc có thể có sai số). Trong lĩnh vực an toàn thông tin, tập mờ cũng được sử dụng rất rộng rãi. Tất cả các thuật toán, giải thuật, kỹ thuật được giới thiệu dưới đây đều được xuất phát từ tập mờ. Mạng Nơron (Neural Network – NN). NN là mô hình tính toán dựa trên bộ não. Mô hình NN bao gồm các bộ xử lý _ các Nơron _ có mối liên kết chặt chẽ với nhau, tương tự như họat động của các Nơron trong não người. Các Nơron được kết nối bởi các đường liên kết có đánh trọng số, truyền tín hiệu từ nơron này đến nơron khác. Mỗi nơron nhận các tín hiệu đầu vào (có trọng số) thông qua các đường kết nối và tạo một tín hiệu đầu ra. Hình vẽ sau đây mô tả mô hình của mạng nơron điển hình: W1 W2 W3 Y Neuron X1 X2 X3 y y y Input Signals Weights Output Signals Hình 1. Mô hình mạng Nơron điển hình Chương trình tiến hóa (Evolutionary Computation – EC) Kĩ thuật EC bao gồm rất nhiều các giải thuật khác nhau, ở đây, tiểu luận trình bày một trong những giải thuật tiến hóa phổ biến nhất – giải thuật di truyền (Genetic Allgothm –GA). Hình vẽ bên dưới mô tả hoạt động của một giải thuật di truyền điển hình. Population New Population Mutation Mating Selection Hình 2 – Mô hình hoạt động của giải thuật di truyền. Bài này sẽ trình bày các khái niệm cơ bản về giải thuật di truyền và áp dụng trong bài toán cụ thể. Chương 2: GIẢI THUẬT DI TRUYỀN KHÁI NIỆM GIẢI THUẬT DI TRUYỀN Thuật toán di truyền (Genetic Algorithm_GA) là kỹ thuật chung giúp giải quyết 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 vào lý thuyết tiến hóa muôn loài của Darwin) trong điều kiện quy định sẵn của môi trường. GA là một thuật giải và 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. Đặc trưng của thuật toán di truyền kinh điển Thuật toán di truyền lập luận ngẫu nhiên thay vì xác định. Thuật toán di truyền duyệt toàn bộ các giải pháp, sau đó chọn lấy giải pháp tương đối tốt dựa trên hệ số thích nghi. Thuật toán di truyền không để ý chi tiết vấn đề, mà chỉ chú ý đến giải pháp, đặc biệt là dãy số tượng trưng cho giải pháp. Goldberg và Zbiniev Michalewicz nêu ra đặc trưng của GA như sau: Thuật toán di truyền làm việc với một mã hóa của tập hợp tham số, chứ không phải là một tham số. Thuật toán di truyền tìm kiếm từ một quần thể các điểm, chứ không phải là một điểm hoặc một vài điểm như phương pháp tìm kiếm leo đồi (Hill Climbing). Thuật toán di truyền đánh giá thông tin với hàm mục tiêu, mà không dựa vào đạo hàm hay thông tin bổ sung khác. Thuật toán di truyền sử dụng các luật biến đổi theo xác suất, mà không sử dụng luật quyết định. Cơ sở sinh học của giải thuật di truyền Trong cơ thể sinh vật, các gene liên kết với nhau theo cơ chế dạng chuỗi gọi là nhiễm sắc thể (NST), 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 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 bị tuyệt chủng. Môi trường tự nhiên luô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ờ 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 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 di truyền (Genetic Algorithms). Tư tưởng của giải thuật di truyền Có một số lớn các bài toán người ta chưa tìm thuật toán tương đối nhanh để giải quyết chúng. Nhiều bài toán trong lớp này là các bài toán quy hoạch thường nảy sinh trong các ứng dụng. Với bài toán quy hoạch thuộc loại khó, có thể tìm được thuật toán “nhanh”, cho kết quả gần tối ưu. Đối với một số bài toán quy hoạch khó, ta cũng có thể tìm thuật toán xác suất, thuật toán này không đảm bảo cho kết quả tối ưu, nhưng bằng cách chọn ngẫu nhiên đủ nhiều “bằng chứng”, có thể giảm tùy ý xác suất sai của kết quả. Nói một cách trừu tượng, việc giải bài toán có thể xem như tìm kiếm trong không gian với lời giải có thể. Vì cái đích của chúng ta là “lời giải tốt nhất”, ta có thể xem phương pháp giải bài toán là quá trình tối ưu hóa. Đối với không gian nhỏ, phương pháp “vét cạn” cổ điển là đủ dùng. Đối với các không gian lớn hơn, đòi hỏi những phương pháp trí tuệ nhân tạo đặc biệt. Thuật toán di truyền (GA) nằm trong các phương pháp đặc biệt đó. Tư tưởng của thuật toán di truyền là xem xét, đánh giá các gene thế nào là tốt cho mục tiêu, sử dụng nó tiếp cho thế hệ sau. Nói theo ngôn ngữ di truyền là giữ lại các gene trội, loại bỏ các gene không tốt, hay là đào thải những thế hệ không tốt. Hoạt động của giải thuật di truyền Thuật toán di truyền dùng nhiều ngôn ngữ của ngành di truyền học. Chúng ta sẽ nói về các “cá thể” trong một quần thể. Thường thì các cá thể này được gọi là xâu, hoặc nhiễm sắc thể. Mỗi loài có một số lượng nhiễm sắc thể nhất định (Ví dụ: cơ thể người có 46 nhiễm sắc thể). Tuy nhiên, trong bài này, ta chỉ nói về các cá thể có đúng một nhiễm sắc thể. Mỗi nhiễm sắc thể bao gồm các đơn vị - gene – xếp liên tiếp; mỗi gene điều khiển sự thừa kế của một hoặc vài tính trạng bất kỳ (thí dụ màu mắt) có thể được thể hiện dưới nhiều mức độ khác nhau. Ta nói gene đó có nhiều trạng thái (gọi là state). Mỗi nhiễm sắc thể (cá thể) sẽ biểu thị một lời giải có thể của một bài toán (ý nghĩa của mỗi nhiễm sắc thể, nghĩa là kiểu gene của nó được quy định bởi người lập trình). Một quá trình tiến hóa được thực hiện trên một quần thể nhiễm sắc thể, là tương đương với sự tìm kiếm trong một không gian các lời giải có thể. Sự tìm kiếm này đòi hỏi sự cân bằng giữa hai mục đích: Khai thác lời giải tốt nhất, và khám phá không gian tìm kiếm. Phương pháp “leo núi” là một ví dụ về chiến lược khai thác lời giải tốt nhất theo các hướng cải tiến. Tìm kiếm ngẫu nhiên là một ví dụ điển hình của sự khám phá không gian tìm kiếm, không chú trọng khai thác các miền hứa hẹn trong không gian tìm kiếm. Thuật toán di truyền là lớp các phương pháp tìm kiếm tổng quát với sự cân bằng đáng kể giữa khai thác và khám phá không gian tìm kiếm. Thuật toán di truyền cũng như các thuật toán tiến hóa nói chung, hình thành dựa trên khái niệm cho rằng quá trình tiến hóa tự nhiên là hoàn hảo nhất, hợp lý nhất và tự nó đã mang tính tối ưu. Quan niệm này có thể được xem là một tiên đề đúng, không chứng minh được nhưng phù hợp với thực tế khách quan. Quá trình tiến hóa 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 hóa tự nhiên được duy trì bằng hai quá trình cơ bản: sinh sản và chọn lọc tự nhiên. Xuyên suốt quá trình tiến hóa tự nhiên, là thế hệ mới luôn được sinh ra để bổ sung và thay thế thế hệ cũ.  Cá thể nào phát triển hơn, thích ứng hơn với môi trường sẽ tồn tại, cá thể nào không thích ứng với môi trường sẽ bị đào thải. Sự thay đổi môi trường là động lực tiến hóa. Ngược lại tiến hóa cũng tác động trở lại, góp phần làm thay đổi môi trường. 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 hóa 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ế quan trọng như nhau trong tiến hóa, dù đột biến xảy ra với xác suất nhỏ hơn nhiều so với di truyền. Các thuật toán tiến hóa, tuy có những đặc điểm khác biệt, nhưng đều mô phỏng các quá trình cơ bản: lai ghép, đột biến, sinh sản và chọn lọc tự nhiên. Như vậy, quá trình tiến hóa càng lâu thì càng có điều kiện cho các cá thể tốt được sinh ra, và chất lượng của cá thể càng được nâng lên. CẤU TRÚC GIẢI THUẬT DI TRUYỀN ĐƠN GIẢN Trong thuật toán di truyền đơn giản, các cá thể hay còn gọi là NST (Nhiễm sắc thể) được mã hóa thành một chuỗi nhị phân gồm giá trị 0 và 1. Một NST trong GA cổ điển có dạng sau: 0 0 1 1 0 0 1 1 1 Mỗi NST biểu diễn một lời giải có thể có của bài toán. Một quá trình tiến hóa được thực hiện trên một quần thể (một tập hợp NST) tương đương với sự tìm kiếm trong không gian lời giải có thể. Sự tìm kiếm này đòi hỏi sự cân bằng giữa hai mục đích: tìm lời giải tốt nhất và khám phá không gian tìm kiếm mới. GA cổ điển thực hiện tìm kiếm theo nhiều hướng bằng cách duy trì một tập lời giải có thể, khuyến khích sự hình thành và trao đổi thông tin giữa các hướng. Tập lời giải trải qua quá trình tiến hóa và cuối cùng cho ta một lời giải đủ tốt được chọn để tái sinh, các lời giải tồi bị loại bỏ. Để phân biệt mức độ tốt xấu giữa các lời giải khác nhau người ta dùng một hàm gọi là “hàm mục tiêu” hay “hàm thích nghi” vì hàm này tương đương với môi trường sống hay thuyết tiến hóa. Thuật toán di truyền đơn giản bao gồm ba toán tử sau: Tái tạo (Reproduction) Lai ghép (Crossover) Đột biến (Mutation) Tái tạo Tái tạo là một quá trình trong đó các chuỗi biểu diễn cá thể được sao chép lại tùy theo giá trị 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ố. Việc sao chép lại các chuỗi tùy theo giá trị thích nghi của chúng, có nghĩa là: Những chuỗi có giá trị thích nghi cao hơn sẽ có nhiều cơ hội đóng góp các chuỗi con cho thế hệ tiếp theo. 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ử các chuỗi của quần thể ban đầu đã khởi tạo trong bài toán hộp đen có các giá trị hàm thích nghi như trong bảng sau. Lấy tổng độ thích nghi của 4 chuỗi, chúng ta được 1170. Ta có tỉ lệ % độ thích nghi của từng chuỗi trong quần thể: STT 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 10001 361 30.9 Tổng cộng 1170 100.0 Các chuỗi của bài toán mẫu và các giá trị thích nghi Bánh xe roulette được đánh trọng số phù hợp cho sự tái tạo của thế hệ này được thể hiện trên hình sau: 49.2% 2 5.5% 3 30.9% 4 14.4% 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. Với bài toán hộp đen, để sinh sản chúng ta chỉ cần quay bánh xe Roulette 4 lần. Đối với bài toán cụ thể thì: Chuỗi 1 có giá trị thích nghi là 169 đại diện cho 0.144. Tương tự với các chuỗi còn lại, bằng cách này chuỗi thích nghi hơn sẽ có