Tài liệu Ứng dụng thuật giải di truyền giải các bài toán hàm mục tiêu nhiều biến

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KINH TẾ ----------------------------- LÊ CHÍ LUẬN ỨNG DỤNG THUẬT GIẢI DI TRUYỀN CÁC BÀI TOÁN HÀM MỤC TIÊU NHIỀU BIẾN LUẬN VĂN TIẾN SỸ CÔNG NGHỆ THÔNG TIN Mã số:101 10 Người hướng dẫn: PGS.TSKH Hà Nội - 2008 -2 - MỤC LỤC ` LỜI CAM ĐOAN .......................................................................................... 1 MỤC LỤC ..................................................................................................... 2 BẢNG TỪ VIẾT TẮT................................................................................... 4 DANH SÁCH HÌNH VẼ VÀ BẢNG BIỂU .................................................. 6 MỞ ĐẦU ........................................................................................................ 7 Chương 1. THUẬT GIẢI DI TRUYỀN ...................................................... 8 1.1. Tổng quan về thuật giải di truyền [2] ......................................................... 8 1.1.1. Thuật giải di truyền là gì?....................................................................... 8 1.1.2. Lịch sử phát triễn của giải thuật di truyền ............................................... 9 1.1.3. Từ ngẫu nhiên đến thuật giải di truyền ................................................. 10 1.1.4. Một số ứng dụng nổi bật của thuật giải di truyền .................................. 12 1.2. Các nguyên tắc cơ bản của thuật giải di truyền [1] .................................. 14 1.2.1. Những tính chất cơ bản của thuật giải di truyền .................................... 14 1.2.2. Các bước trong việc áp dụng thuật giải di truyền .................................. 18 1.2.3. Các phương pháp mã hoá trong thuật giải di truyền.............................. 19 1.2.4. Một vài ví dụ minh hoạ ........................................................................ 41 1.2.5. Kết Luận .............................................................................................. 52 1.3. Các giai đoạn cần thực hiện để giải quyết bài toán bằng thuật giải di truyền ................................................................................................................ 54 1.3.1. Mối liên hệ giữa thuật giải di truyền và sự tiến hoá .............................. 54 1.3.2. Những tính chất quan trọng của thuật giải di truyền ............................. 56 1.3.3. Một số vấn đề liên quan đến thuật giải di truyền? ................................. 57 Chương 2. ỨNG DỤNG GIẢI THUẬT DI TRUYỀN ĐỂ GIẢI CÁC BÀI TOÁN TỐI ƯU NHIỀU BIẾN.................................................................... 59 2.1. Bài toán tối ưu. ....................................................................................... 59 2.1.1. §Æt vÊn ®Ò. ............................................................................ 59 2.1.2 Một số ví dụ về bài toán tối ưu. ............................................................. 60 2.1.3. Một số ứng dụng nổi bật của bài toán tối ưu ......................................... 62 -3 - 2.2. Ứng dụng giải thuật di truyền để giải các bài toán tối ưu nhiều biến [2]. ............................................................................................................ 65 2.2.1. Đặt vấn đề. ........................................................................................... 65 2.2.2. Biễu diễn các biến bằng véc tơ nhị phân.............................................. 65 2.2.3. Toán tử chọn cá thể (select) .......................................................... 66 2.2.4. Toán tử lai ghép (cross over) ........................................................ 67 2.2.5. Toán tử đột biến (mutation) ........................................................... 67 2.2.7. Bài toán cực tiểu hàm f với n biến liên tục ........................................... 69 Bài toán 1: Bài toán cực tiểu hàm với N biến [2] .................................. 106 2.2.6. Hàm thích nghi (fitness) .................................................................. 68 Bài toán 2: Travelling Salesman Problem(TSP) .................................... 111 KẾT LUẬN ................................................................................................ 120 TÀI LIỆU THAM KHẢO......................................................................... 121 -4 - BẢNG TỪ VIẾT TẮT Từ hoặc cụm từ Từ tiếng Anh Từ tiếng Việt ANN Artificial Network Mạng nơron nhân tạo Chromosome Chromosome Nhiễm sắc thể Computer language Computer language Ngôn ngữ lập trình Cross over Crossover Lai ghép, một hình thức của sự biến hoá trong GA Expert Systems Expert Systems Hệ chuyên gia Neural Fitness Giá trị (trị số) thích nghi Fitness function Fitness function Hàm số thích nghi, hàm số để tính ra giá trị thích nghi cho mỗi giải pháp hay đáp số để xem trường hợp nào là tối ưu hay tốt hơn Fuzzy Logic Fuzzy Logic Lôgic mờ GA Genetic Algorithms Thuật giải di truyền Genotype Genotype Tất cẩ các giải pháp đã được duyệt xét và có hy vọng chọn làm đáp số thích nghi nhất cho vấn đề. Hill-climbing Hill-climbing Tìm kiếm theo kiểu leo núi Initialization Initialization Khởi tạo Model Model Mô hình Mutation Mutation Đột biến, một hình thức của sự biến hoá dùng trong GA Optimization Optimization Tối ưu Population Population Quần thể (toàn bộ các giải pháp cho vấn đề có trị số thích nghi cao cũng -5 - như thấp) Reproduction Reproduction Tạo sinh -6 - DANH SÁCH HÌNH VẼ VÀ BẢNG BIỂU Hình 1. Sơ đồ tổng quát của thuật giải di truyền ................................................................ 16 Hình 3. Mảng byte nén ...................................................................................................... 21 Hình 4. Cấu trúc của một thời khóa biểu ............................................................................. 48 Hình 5. Chọn lọc. X, Y, Z viết tắt của số các cá thể. ........................................................... 50 Hình 6. Ví dụ về lai ghép hai cá thể. Trong trường hợp này lớp số 2 sẽ bị thay đổi ............. 51 Hình 2. Ví dụ về một đột biến trong một cá thể đơn ............................................................ 52 Hình 7. Các bước của Thuật giải di truyền cho bài toán tối ưu hàm .................................... 70 Hình 8. Hàm khởi tạo giá trị ngẫu nhiên ............................................................................. 70 Hình 9. Hàm khởi tạo giá trị ngẫu nhiên (0 hoặc 1) theo xác suất........................................ 71 Hình 10. Hàm tính trị số thích nghi .................................................................................. 73 Hình 11. Hàm chọn cá thể (select) ...................................................................................... 73 Hình 12. Hµm m« pháng toán tử đột biến (mutation) ..................................................... 74 Hình 13. Hàm mô phỏng toán tử lai ghép (cross over) ........................................................ 75 Hình 14. Hàm khởi tạo quần thể. ....................................................................................... 75 Hình 15. Hàm tạo sinh ........................................................................................................ 76 Hình 16. Hàm tái tạo quần thể(rreproduction) .................................................................. 78 Hình 17. Hàm giải mã ...................................................................................................... 79 Hình 18. Hàm thể hiện các bước của Thuật giải di truyền .............................................. 80 Hình 19. Minh hoạ thiết bị thí nghiệm trước khi cân bằng ................................................. 83 Hình 20. Minh họa thiết bị thí nghiệm sau khi cân bằng ..................................................... 83 -7 - MỞ ĐẦU Từ vài thập niên trở lại đây, với những tác động mạnh mẽ của các tiến bộ trong công nghệ phần cứng và truyền thông, các hệ thống dữ liệu phục vụ cho các lĩnh vực kinh tế - xã hội đã phát triển bùng nổ, Vì vậy, tôi chọn hướng nghiên cứu "Ứng dụng của thuật giải di truyền để giải các bài toán tối ưu nhiều biến" làm đề tài nghiên cứu cho luận văn của mình. Ngoài phần mở đầu và kết luận, cấu trúc nội dung của luận văn bao gồm có 3 chương: Chương 1: Trình bày tổng quan về giải thuật di truyền, trả lời câu hỏi “giải thuật di truyền là gì?”. Trình bày những nét chính về lịch sử phát triển của giải thuật di truyền và những ứng dụng nổi bật của giải thuật di truyền trong các lĩnh vực khoa học kỹ thuật và cuộc sống. Bên cạnh đó giới thiệu các nguyên tắc cơ bản của thuật giải di truyền. Tính chất cơ bản của thuật giải di truyền, các bước trong việc áp dụng thuật giải di truyền, các phương pháp hoá của thuật giải di truyền và một số ví dụ cụ thể. Cũng trong chương này sẽ giải thích một số thắc mắc liên quan đến thuật giải di truyền và trình bày mối liên hệ giữa giải thuật di truyền và sự tiến hoá. Chương 2: trình bày những nét tổng quan nhất về bài toán tối ưu. Trả lời câu hỏi “ bài toán tối ưu là gì?” Nêu lên một số ứng dụng nổi bật của bài toán tối ưu, giới thiệu các phương pháp giải các bài toán tối ưu và đưa ra một số ví dụ về bài toán tối ưu. Trình bày về ứng dụng của giải thuật di truyền để giải các bài toán tối ưu nhiều biến. Trình bày cách biểu diễn các biến bằng véc tơ nhị phân, toán tử chọn cá thể, toán tử lai ghép, toán tử đột biến, hàm thích nghi. Trình bày về thuật giải để giải bài toán cực tiểu hàm f với n biến liên tục. Chương 3: Phân tích và cài đặt thử nghiệm . Phần kết luận trình bày tóm tắt về các nội dung thực hiện trong luận văn, đồng thời đưa ra các vấn đề nghiên cứu tiếp cho tương lai. -8 - Chương 1. THUẬT GIẢI DI TRUYỀN 1.1. Tổng quan về thuật giải di truyền [2] 1.1.1. Thuật giải di truyền là gì? Trong sinh hoạt hàng ngày, thường gặp nhiều vấn đề từ đơn giản đến phức tạp. Có những vấn đề liên quan đến sinh hoạt cá nhân như chọn trường cho con em, tìm lộ trình ngắn nhất để đi làm mỗi ngày hoặc những vấn đề liên quan đến công việc tại cơ quan như: hoạch định chương trình chạy máy để tận dụng khả năng các dụng cụ, đảm bảo chất lượng và thoả mãn yêu cầu của khách hàng... Để giải quyết vấn đề, ở nhiều trường hợp, chúng ta có vô số giải pháp nhưng không có giải pháp vạn năng theo nghĩa chúng có thể giải mọi lớp bài toán với hiệu quả cao, có những trường hợp quá phức tạp không có giải pháp nào trước mắt hay không biết phải bắt đầu tìm kiếm từ đâu. Để giải quyết vấn đề thường dựa vào các phương thức sau đây: 1. Dựa trên các công thức toán học hay những định luật khoa học (tiếp cận chính xác). 2. Dựa theo ý kiến của các chuyên gia lĩnh vực (tiếp cận kinh nghiệm). 3. Dựa theo sự tiến hoá, bắt chước các qui trình thích nghi và tiến hoá của sinh giới nói chung. Phương thức dựa trên các công thức toán học hay những định luật khoa học thường cho những đáp số chính xác. Tuy nhiên yếu điểm chính của nó là phải tìm ra công thức hay giả tưỏng những điều kiện hoạt động cho giống với thực tế, điều này không thể thực hiện một cách dễ dàng và nhanh chóng. Trong hơn 20 năm qua, lĩnh vực trí tuệ nhân tạo đã được sử dụng để giúp giải quyết vấn đề. Nguyên tắc cơ bản của phương thức này là kết hợp kiến thức của các chuyên gia với chương trình tin học để dùng máy tính thay con người giải quyết vấn đề một cách khôn ngoan. Nhiều chương trình tin học như Mycin, Prospector v.v… đã thành công trong một số lĩnh vực cụ thể; tuy nhiên đối với những vấn đề chưa hề xảy ra, hệ chuyên gia không thể giúp giải quyết được vấn đề. Nhược điểm quan trọng nhất của hệ chuyên gia là khi thu thập kiến thức của các chuyên gia lĩnh vực, chúng ta không có được những ý kiến trung thực có thể vì các chuyên gia thiếu tinh -9 - thần hợp tác hoặc cũng có thể do kỹ thuật thu nhập không thích nghi. Do đó kể từ những năm 90, thế kỉ 20, hệ chuyên gia không còn là kỹ thuật thích hợp nhất để giải quyết vấn đề. Từ đấy, khuynh hướng trở về với bản thể con người được xem là cứu cánh để giải quyết vấn đề. Trong những năm 70, Mạng nơron nhân tạo, Logic mờ, cùng với Thuật giải di truyền được nghiên cứu và áp dụng thành công trong việc giải quyết các trường hợp phức tạp. Nhìn chung con người và sinh vật đều phải tiến hoá để thích nghi với hoàn cảnh. Vào thời kỳ đồ đá con người phải sống trong hang núi và dùng các dụng cụ thô sơ. Những bộ lạc du mục phải biết sống cho thích nghi với thời tiết và địa phương mà họ tạm cư. Sang thời đại tin học, mọi sinh hoạt đều diễn ra quanh máy vi tính nhiệm màu. Các nhà khảo cổ đã tìm ra những chứng tích của các loài khủng long sống hơn triệu triệu năm trên quả đất này. Vào thời đó nhiệt độ của địa cầu còn khá nóng nên mọi sinh vật phải có da dày, chân cao để chạy nhanh. Tiến hoá cho thích nghi với điều kiện của môi trường chung quanh để tồn tại và phát triển là chứng cớ hiển nhiên mà con người và sinh vậtt đã phải thực hiện. Tiến hoá cho thích nghi không có nghĩa là luôn luôn tìm ra giải pháp tuyệt đối cho vấn đề, nhưng có thể chỉ là tương đối trong điều kiện cho phép. 1.1.2. Lịch sử phát triễn của giải thuật di truyền Y niệm về thuật giải di truyền đã được một số nhà sinh vật học nêu ra từ những năm 50, 60, thế kỉ XX. A.S. Fraser là người đầu tiên đã nêu lên sự tương đồng giữa sự tiến hoá của sinh vật và chương trình tin học giả tưởng về GA. Tuy nhiên chính John Henry Holland, đại học Michigan, mới là ngưòi triển khai ý tưởng và phương thức giải quýêt vấn đề dựa theo sự tiến hoá của con người. Ông bắt đầu bằng những bài giảng và bài báo, sau đó đúc kết các ý tưởng thành sách: Adaptation in Natural and Artificial Systems, xuất bản năm 1975. J.H. Holland được xem là “người khai sinh “ của học thuyết Thuật giải di truyền. Trong giai đoạn đầu, thập niên 70 và 80, thế kỉ XX, phần lớn các nhà nghiên cứu và ứng dụng của GA đều được đào tạo tại đại học Michigan, và dưới sự hướng dẫn của J.H. Holland. J.H. Holland và một số đồng nghiệp như Kenneth De Jong, David E. Goldberg đã dần dần xây dựng nền - 10 - tảng lý thuyết và thực hiện các áp dụng của GA để giải quýêt các vấn đề phức tạp trong thực tế. Tạp chí đầu tiên về lý thuyết và ứng dụng của GA là nguyệt san Evulutionary Computation (1993) do Kenneth De Jong chủ biên, ngoài ra còn có nguyệt san AI Expert, Artificial Intelligent cũng thường có bài đề cập về GA. Tuy chỉ mới được hình thành cách đây chưa đầy 25 năm, GA đã có được cơ sở toán học vững chắc về lý thuyết và số lượng những áp dụng ngày càng gia tăng bao gồm nhiều lĩnh vực khác nhau. GA đã kết hợp với các kỹ thuật thuộc lĩnh vực trí tuệ nhân tạo như Expert Systems (Hệ chuyên gia), Mạng nơron nhân tạo (Artificial Neural Network) và Lôgic mờ (Fuzzy Logic) nhằm tìm giải pháp tối ưu cho những vấn đề phức tạp mà phương thức cổ điển đã không giải quýêt thoả đáng. GA được ứng dụng trong nhiều lĩnh vực khác nhau, từ khoa học tự nhiên đến khoa học nhân văn, từ kỹ thuật sang thương vụ và kinh tế- tài chính. Nhìn chung, những ứng dụng này có thể chia làm ba nhóm chính:  Tìm mô hình tối ưu. Tìm kiếm và tối ưu hoá giải pháp là đề tài thích hợp nhất của GA.  Hoạch định quy trình sản xuất, lộ trình chuyển vận, cách bố trí các bộ phận trong môi trường. Những ứng dụng loại này được dùng trong ngành giao thông, chế tạo sản phẩm, tiếp thị v.v…  Chọn lựa các nhóm hay thành phần trong một tổ chức. Chúng ta cũng có thể sắp xếp các ứng dụng theo lĩnh vực như: quản trị, kinh tế- tài chính, kỹ thuật, nghiên cứu và phát triển. 1.1.3. Từ ngẫu nhiên đến thuật giải di truyền Xét bài toán tìm mật mã để mở khoá với mật mã là một con số thập phân có 30 chữ số với giả sử rằng ổ khoá này chỉ có thể mở bằng một mật mã duy nhất. Đối với bài toán này không gian tìm kiếm là 1030, nghĩa là sẽ có tổng cộng 1030 mật mã khác nhau. Để giải quyết vấn đề này ta thường chỉ nghĩ đến hai phương pháp : Vét cạn toàn bộ hoặc thử ngẫu nhiên các mật mã. Ta phát sinh ( ngẫu nhiên hoặc tuâầntự theo một quy tắc duyệt nào đó) các mã khoá rồi thử xem mật mã này có thể là mã khoá đúng không. Với phương pháp này, để có được một mật mã với khả năng mở được ổ khoá là trên 50%, ta đã phải phát sinh nhiều hơn 1030/2 mật mã. Con số này quá lớn, trên thực tế, nếu dùng siêu máy tính Cray và giả sử rằng cứ mỗi một phần tỷ giây thì máy này có thể phát sinh và thử nghiệm được một mật mã - 11 - (nghĩa là một giây Gray thử được 1 tỷ mật mã) thì nó phải chạy trong một khoảng thời gian tương đương với tuổi của trái đất để thử trên 1030/2 mật mã. Đứng trước mhững bài toán như vậy, người ta thường tìm cách cải thiện thuật toán bằng cách cung cấp thêm một số thông tin khác. Chẳng hạn như thông tin 2 mật mã được phát sinh ra, mật mã nào tốt hơn (nghĩa là có khả năng mở kháo cao hơn). Khi biết được độ tốt của các mật mã, ta sử dụng một phương pháp tìm kiếm thông minh hơn – người ta thường gọi là tìm kiếm theo kiểu leo núi (hill-climbing). Với tìm kiếm leo núi, ta tưởng tượng rằng không gian tìm kiếm của vấn đề bài toán là một vùng đất gập ghềnh(landscape), có nhiều ngọn đồi cao thấp khác nhau. Trong đó, ngọn đồi cao nhất của vùng đất này sẽ là lời giải tốt nhất và vị trí có độ cao càng lớn thì càng gần với lời với lời giải tốt nhất (độ cao đồng nghĩa với độ tốt của lời giải). Tìm kiếm theo kiểu leo núi có nghĩa là chúng ta phải phát sinh các lời giải sao cho càng về sau các lời giải càng tiến gần tới lời giải tốt nhất hơn. Thao tác này cũng giống như thao tác leo núi vậy ( vì càng ngày càng lên cao hơn). Kiểu giải quyết này vẫn còn gặp trở ngại cơ bản là, nếu vùng đất của chúng ta có nhiều núi nhỏ khác bên cạnh ngọn núi cao nhất thì sẽ có khả năng thuật toán bị kẹt ở một ngọn núi nhỏ. Do tư tưởng là càng ngày càng lên cao nên khi lên đến đỉnh một ngọn núi nhỏ thuật toán sẽ không thể đi tiếp được (vì không thể lên cao được nữa, muốn tìm đến ngọn núi cao hơn thì phải xuống núi hiện tại, mà xuống núi thì không đúng tư tưởng càng ngày càng lên cao). Hã tuởng tượng một máy tính giải quyết vấn đề- bài toán theo kiểu leo núi là một nguời leo núi với tư tưởng „càng leo càng cao‟. Nếu chỉ có một người leo núi thì khả năng người đó bị „kẹt‟ trên một đỉnh núi thấp. Nếu có nhiều người leo núi cùng leo ở nhiều điểm khác nhau thì khả năng có người leo đến đỉnh núi cao nhất sẽ cao hơn. Càng nhiều nguời thì khả năng đến đỉnh núi cao nhất sẽ cao hơn. Càng nhiều người thì khả năng đến đỉnh núi cao nhất sẽ cao hơn. Tư tuởng này cũng chưa có gì mới mẻ, đơn giản chỉ là dùng nhiều máy tính để chia việc ra mà thôi. Hơn nữa, với không gian tìm kiếm cỡ 1030 như bài toán mở khoá, chúng ta phải cần bao nhiêu siêu máy tính ? Mà quan trọng hơn nữa, cho dù có nhiều người cùng lêo núi, nhưng số lượng người leo núi quá ít so với số lượng núi thì khả năng tất cả người leo núi đều bị „kẹt‟ cũng vẫn còn cao. Từ đó người ta nảy ra ý nghĩ tạo ra nhiều thế hệ người leo núi ? nghĩa là, nếu toàn bộ người leo núi đầu tiên (giả sử 1000 người chẳng hạn) đều không đạt đến dỉnh núi cao nhất thì sẽ cho 1000 người leo núi khác tiếp tục leo. Tuy nhiên, sẽ nảy sinh một vấn đề, có khả năng là trong nhóm người leo núi mới, có những người lại đi leo lại những ngọn núi mà nhóm truớc đã leo rồi. Ghi nhận lại những ngọn núi đã leo để những nhóm sau còn thừa hưỏng đuợc kết quả của nhóm truớc. Tổng quat hơn : Hãy làm sao để những người giỏi nhất (leo cao nhất) trong số những người leo núi đầu tiên truyền lại „kinh nghiệm leo núi của mình cho 1000 người tiếp nữa để những nguời thế hệ sau để sao cho 1000 người „hậu duệ‟ này sẽ leo cao hơn họ. Và nếu 1000 người sau lại thất bại, những người giỏi nhất trong số họ sẽ lại truyền kinh nghiệm của mình cho 1000 người tiếp nữa để những người thế hệ 3 này leo cao hơn - 12 - nữa. Tiến trình cứ thế tiếp tục cho đến lúc đến 1 thế hệ nào đó, có một người leo đến đỉnh núi cao nhất hoặc hết thoòi gian cho phép. Trong truờng hợp hết thời gian cho phép thì trong toàn bộ các thế hệ, người nào leo cao nhất sẽ được lựa chọn. Trên đây là tư tưởng chính của thuật giải di truyền. Thay vì phát sinh một lời giải, ban đầu ta phát sinh một lúc nhiều (thậm chí rất nhiều) lời giải cùng lúc. Sau đó, trong số lời giải tạo ra, chọn ra những lời giải tốt nhất để làm cơ sở phát sinh ra nhóm các lời giải sau với nguyên tắc „càng về sau‟ càng tốt hơn. Quá trình tiếp diễn cho đến lúc tìm đưwcj một lời giải tối ưu. Đó là tư tưởng ban đầu của thuật giải di truyền. Càng về sau, người ta càng hoàn thiện hơn phương pháp luận của ý tưởng này, dẫn đến sự ra đời của một hệ thống hoàn chỉnh các phương pháp, nguyên lý dùng trong thuật giải di truyền. 1.1.4. Một số ứng dụng nổi bật của thuật giải di truyền 1.1. 3.3. Ứng dụng trong ngành khai thác dầu khí David E. Goldberg là người đầu tiên đã dùng GA trong kỹ thuật. Khi Goldberg đề nghị với J.H. Holland bảo trợ ông thực hiện đề tài Com-puter Aided Gas Pipeline Operation using Genetic Algorithms and Rule learning, người sáng lập ra GA đã phải dè dặt không chắc là Goldberg thành công. Bởi vì vào đầu thập niên 80 thế kỷ XX, GA vẫn còn trong thời kỳ phôi thai, chỉ mới được chứng minh một phần bằng việc làm của J.H.Holland và De Jong, về mặt ứng dụng thực tế thì hoàn toàn chưa có gì đáng kể ngoài việc tối wu hoá một vài hàm số đơn giải. Trước khi đến với tin học, Goldberg là một kỹ sư cơ khí đã chạm trán với nhiều khó khăn trong việc vận chuyển dầu khí trong các mạng lưới phân phối phức tạp. Dọc theo hàng chục cây số đường ống dẫn của mạng lưới phân phối là những bơm, van và áp kế để duy trì lưu lượng và vận tốc tối ưu cho mạng lưới chuyển vận dầu khí. Vì phải điều chỉnh từng đơn vị bơm nên áp suất và lưu lượng tối ưu ở chỗ này thì lại quá thấp hay quá cao tại các nơi khác. Nếu bơm và van không được điều chỉnh một cách hài hoà thì giao động sẽ xảy ra trong mạng lưới đồng thời tạo ra những chỗ hở tại các mối nối, khiến các điều hành viên không dám sử dụng bơm trong điều kiện tối ưu. Tóm lại việc điều hành mạng lưới phân phối dầu khí là rất phức tạp. Năm 1985, David E. Goldberg đã thành công trong việc dùng GA và với máy Apple II ông đã thực hiện được chương trình tin học sử dụng ngôn ngữ Pascal để hiệu chỉnh mạng lưói phân phối dầu khí một cách tốt đẹp. Từ đó GA đã thực sự góp phần vào việc giải quyết những vấn đề phức tạp. 1.1.3.4. Ứng dụng trong lĩnh vực thiết kế - 13 - Genetic Electric Co. (GE) đã dùng GA trong việc yểm trợ chương trìnhtin học vẽ kỹ nghệ để tối ưu hoá việc thiết kế các bộ phận cho máy bay, tuabin nhà máy nhiệt điện và nhiều phụ tùng khác. Động cơ cho máy bay mới nhất của Boeing đã được GA thiết kế với chương trình tin học về GA: Engineous. Sau thành công này, Engineous đã được dùng để tự động hóa việc thiết kế cánh quạt tuabin nhà máy điện nguyên tử. Cơ quan Naval Surface Weapons Center (Bethesda, maryland) đã dùng Engineous để thiết kế cánh quạt các tàu ngầm. 1.1.3.5. Ứng dụng trong ngành khai thác hầm mỏ Chuck Karr đã biến những hiểu biết về lý thuyết GA của mình trong luận án tiến sĩ thành những ứng dụng thực tế để chế tạo dụng cụ đo lường cho kỹ nghệ khai thác khoáng sản. Bằng sự kết hợp GA và Fuzzy Logic, Chuck Karr đã điều chỉnh được độ PH của môi trường thực hiện được bộ kiểm soát để điều khiển trực thăng. Nhiều ứng dụng khác đang được sử dụng trong các lĩnh vực như: - Tìm lộ trình tối ưu cho người chào hàng (Travelling Saleman) - - Tìm vị trí tối ưu để đặt nhiều đài phát thanh để phục vụ cho nhiều thành phố lân cận Tìm địa điểm để khoan dầu trên đại dương. Trên một vùng hàng chục ngàn cây số vuông, việc lựa chọn những điểm khoan dầu khí thích nghi không những giảm chi phí mà còn rút ngắn thời gian dò tìm Thiết kế máy biến thế ( transformer) cho các nhà máy điện. Chọn công thức hoá học thích nghi để tạo sản phẩm thoả mãn yêu cầu của khách hàng. 1.1.3.6. Ứng dụng trong lĩnh vực giao thông. Tìm điều kiện giao thông tối ưu là một trong những ứng dụng quan trọng. Ví dụ như việc hoạch định lộ trình xe chở hàng từ các kho đến các công trường sao cho nhanh và ngắn nhất. Hoạch định chưong trình bảo trì các xa lộ dựa trên các phương tiện hiện hữu và thoả mãn nhịp độ giao thông cũng là đề tài được giải quyết bằng GA. Một số nhà nghiên cứu đang dùng GA để điều hành mạng lưới đèn báo hiệu tại các trục giao thông chính. Hiện nay các đèn báo hiệu này hoạt động trên nguyên tắc: đèn chuyển từ xanh sang vàng và đỏ sau những khoảng thời gian nhất định. Khuyết điểm của giải pháp này là nhiều khi đèn xanh trên một trục giao thông hàng phút nhưng không có xe, trong khi hàng chục chiếc khác đang đợi tại hướng đèn đỏ. Nhiều cuộc thí nghiệm kết hợp GA và chíp điện tử nhận biết dạng hình để điều - 14 - khiển đèn báo hiệu theo nhu cầu (Xem có xe hay không) thay vì thời gian như hiện nay. 1.1.3.7. Ứng dụng trong sản xuất Nhiều ứng dụng của GA tại các trung tâm sản xuất nhằm tăng cường khả năng sản xuất và chuyển giao thành phẩm, tránh việc di chuyển hàng hoá nhiều lần, tồn trữ quá lâu trong kho hay giữ các phưong tiện chuyển vận trong tình trạng chờ đợi. Sau đây là một ví dụ tại công ty cung cấp rượu bia Adolph Coors Company (ACC). ACC sản xuất nhiều loại rượu bia và bao bì dưới nhiều hình thức khác nhau, với tổng số mặt hàng trên dưới 500 loại. Mỗi ngày ban tiếp nhận được hàng trăm đơn đặt hàng như số chỗ giao hàng có giới hạn nên không thoả mãn kịp thời các yêu cầu. Trong nhiều trường hợp xe giao hàng vào được bến nhưng không có đủ hàng . Hãng có 16 dây chuyền sản xuất, nếu sản phẩm không giao kịp thời thì phải giữ trong kho vừa “kẹt” vốn vừa mất nhiều chỗ trong kho hàng. Làm thế nào để phối hợp sản xuất với nhu cầu khách hàng mỗi ngày/ Trước đây, việc này được giửi quyết trên nguyên tắc “ đến trước nhận trước, đến sau phải chờ” ( first come first serve) khiến cho dây chuyền sản xuất phải thay đổi nhiều kần trong ngày và hàng tồn kho ngày một nhiều. Công ty đã sử dụng nhiều phương pháp giải quyết khác nhau nhung đều không thành công. Gần đây, GA đã được dùng và tìm để tìm ra giải pháp tối ưu kết hợp nhu cầu của khách hàng và khả năng sản xuất của công ty. Một ứng dụng khác là lập chương trình chạy máy tại cơ xuởng. Một cơ xưởng thường gồm nhiều máy tiện, máy hàn, máy khoan, máy cắt, máy cán dập, v.v…Những máy này được dùng cho nhiều công tác khác nhau, ví dụ cán dập trước khi hàn, kế đến là khoan và đánh bóng ,v.v.. Làm thế nào để phối hợp yêu cầu của khách hàng với khả năng máy móc hiện có và nhất là với số chuyên viên có mặt trong ngày. GA đã được dùng để kết hợp ba yếu tố trên để tạo sản phẩm tốt và lợi nhuận cao. 1.2. Các nguyên tắc cơ bản của thuật giải di truyền [1] 1.2.1. Những tính chất cơ bản của thuật giải di truyền a. Các thành phần cơ bản của thuật giải di truyền - 15 - Thuật giải 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 quan niện cho rằng, quá trình tiến hóa tự nhiên là quá trình 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 như 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ì nhờ 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, các thế hệ mới luôn được sinh ra để bổ sung 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 được với môi trường sẽ bị đào thải. Sự thay đổi môi trường là động lực thúc đẩy quá trình 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. Các cá thể 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ế có vai trò quan trọng như nhau trong tiến trình tiến hóa, dù rằng đột biến xảy ra với xác suất nhỏ hơn nhiều so với hiện tượng di truyền. Các thuật toán tiến hóa, tuy có những điểm khác biệt, nhưng đề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. b. Giải thuật di truyền. b1. Đầu vào (input): Cho một quần thể các sinh vật (ta có thể xem như là một tập hợp các giải pháp), ta chọn một số hữu hạn (n) các cá thể (giải pháp) trong quần thể (tập hợp) đó (ta có thể gọi đây là một mẫu thử ban đầu, cách chọn mẫu thử này tùy thuộc vào bài toán cụ thể và ta có thể nhờ sự trợ giúp của kỹ thuật xác suất). Tiếp đến ta chọn mô hình (model) để tượng trưng cho các giải pháp. Các mô hình có thể là dãy (String) những số nhị phân : 1 và 0, thập phân và có thể là chữ hay hỗn hợp cả chữ và số. Chọn hàm số thích nghi để dùng làm tiêu chuẩn đánh giá các giải pháp. Các kỹ thuật lai tạo, đột biến, tạo sinh, chọn, và thời gian cho phép. b2. Đầu ra (output): - 16 - Giải pháp tối ưu nhất.  Sơ đồ tổng quát của thuật giải di truyền Xác định độ thích nghi Phát sinh quần thể ban đầu Trình bày lời giải Cá thể nào đạt đến lời giải tối ưu chưa? Chọn lọc Bắt đầu Lai tạo Xây dựng quần thể mới Đột biến Xây dựng thế hệ kế tiếp Hình 1. Sơ đồ tổng quát của thuật giải di truyền b3. Sơ đồ tổng quát của GA Bắt đầu t = 0; Khởi tạo P(t); Tính độ thích nghi cho các cá thể thuộc P(t); Khi (điều kiện dừng chưa thỏa mãn) lặp t = t+1; Tái sinh P‟(t) từ P(t); Lai Q(t) từ P(t-1); Đột biến R(t) từ P(t-1); Chọn lọc P(t) từ P(t-1)  Q(t)  R(t)  P(t); - 17 - Hết lặp Kết thúc. Trong lập trình tiến hóa, khi giải một bài toán đặt ra, cần tận dụng tối đa tri thức về bài toán đó để chương trình tiến hóa đạt được hiệu quả cao nhất có thể. Việc tận dụng tri thức bài tóan có thể được thể hiện (1) qua việc xây dựng một cấu trúc dữ liệu hợp lý sao cho việc xây dựg các phép toán di truyền được tự nhiên và hiệu quả nhất (2) hay qua việc sử dụng phương pháp đã và đang được sử dụng để giải bài toán này và kết hợp chúng với thuật giải di truyền (3) và cách tận dụng hay nhất là tận dụng cả 2 cách trên trong 1 chương trình tiến hóa; đây là cách được nhiều nhà nghiên cứu ứng dụng lập trình tiến hóa sử dụng nhiều nhất. c. Các tính chất đặc thù của thuật giải di truyền 1. GA lập luận mang tính chất ngẫu nhiên (stochastic), thay vì xác định (deterministic) như toán học giải tích. 2. GA duyệt ứng viên theo các nguyên lý thích nghi và tiến hoá, sau đó chọn lấy giải pháp tương đối tốt nhất dựa trên hệ số thích nghi. 3. GA không để ý đến chi tiết vấn đề, trái lại chỉ chú ý đến giải pháp, đặc biệt là dãy số tượng trưng cho giải pháp. 4. GA rất thích hợp cho việc tìm kiếm giải đáp cho vấn đề, hay tìm điều kiện tối ưu cho việc điều hành, và phân nhóm những giải pháp có được. d. Ứng dụng của GA GA được ứng dụng trong nhiều lĩnh vực khác nhau, từ khoa học tự nhiên đến khoa học nhân văn, từ kỹ thuật sang thương vụ và kinh tế tài chính. Nhìn chung, những ứng dụng này có thể chia làm ba nhóm chính: 1. Tìm mô hình tối ưu cho vấn đề. Tìm kiếm và tối ưu hóa giải pháp là đề tài thích hợp nhất của GA. 2. Hoạch định quy trình sản xuất, lộ trình chuyển vận, cách bố trí các bộ phận trong môi trường. Những ứng dụng loại này được dùng trong ngành giao thông, chế tạo sản phẩm, tiếp thị v v…. - 18 - 3. Chọn lựa các nhóm hay thành phần trong một tổ chức. Chúng ta cũng có thể sắp xếp các ứng dụng theo lĩnh vực như: quản trị, kinh tế- tài chính, kỹ thuật, nghiên cứu và phát triển. 1.2.2. Các bước trong việc áp dụng thuật giải di truyền 1.2.2.1. Quá trình lai ghép (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 xảy ra với các 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 (ta 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 m1 và m2. Hai chuỗi nhiểm sắc thể con mới sẽ là m11+m22 và m21+m12. Đưa hai cá thể mới này vào quẩn thể để tham gia các quá trình tiến hóa tiếp theo. 1.2.2.2. Quá trình đột biến (phép đột biến) Độ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ẹ. Phép đột biến xảy ra với xác suất pm, nhỏ hơn rất nhiều so với xác suất phép lai pc. Phép đột biến có thể mô phỏng như sau:  Chọn ngẫu nhiên một cá thể bất kỳ cha mẹ 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 giá quá trình tiến hóa tiếp theo. 1.2.2.3. Quá trình sinh sản và chọn lọc (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ó. Độ thích nghi là một hàm gán một giá trị thực cho các cá thể trong quần thể. Quá trình này có thể được mô phỏng như sau:  Tính độ thích nghi của từng cá thể trong quẩn thể hiện hành, lập bảng cộng dồn các giá trị thích nghi (theo số thứ tự gán cho từng cá thể). Giả sử quần - 19 - thể có n cá thể. Gọi độ thích nghi của cá thể thứ i là Fi, tổng dồn thứ i là Fti, tổng độ thích nghi của toàn quần thể là Fm.  Tạo một số ngẫu nhiên F trong đoạn từ 0 đến Fm.  Chọn cá thể thứ k đầu tiên thỏa mãn F ≥ Ftk đưa vào quần thể của thế hệ mới. 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ự độ thích nghi giảm dần.  Loại bỏ các cá thể cuối dãy để chỉ giữ lại n cá thể tốt nhất. Ở đây, tả giả sử quần thể có kích thước cố định n. Một thuật giải di truyền, giải một bài toán được cho phải có năm 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 như đã mô phỏng ở trên,  Và các tham số thuật giải di truyền sử dụng (kích thước quần thể, xác suất lai, đột biến,….) 1.2.3. Các phương pháp mã hoá trong thuật giải di truyền * Nguyên lý về xác định cấu trúc dữ liệu. Để có thể giải bài toán bằng thuật giải di truyền cần „Gen hoá‟ cấu trúc dữ liệu của bài toán. Đây là thao tác quan trọng nhất (không chỉ riêng với vấn đề bài toán được giải bằng thuật giải di truyền) là phải biết chọn một cấu trúc dữ liệu (CTDL) phù hợp. Để giải vấn đề bài toán bằng thuật giải di truyền ta thường chọn sử dụng một trong 3 loại CTDL sau : Chuỗi nhị phân; chuỗi số thực và cấu trúc cây. Trong đó cấu trúc chuỗi nhị phân và chuỗi số thực thường được sử dụng hơn. 1. 2.4.1. Biễu diễn gen bằng chuỗi nhị phân Mọi cấu trúc dữ liệu trên máy tính về máy tính cuối cùng cũng được chuyển về và thể hiện bởi các chuỗi nhị phân (từ số nguyên, số thực, âm thanh...) Tuy nhiên quá trình đổi sang chuỗi nhị phân được thực hiện ngầm bởi trình biên dịch của máy - 20 - tính. Ở đây, chúng ta sử dụng chuỗi nhị phân một cách tường minh để thể hiện cấu trúc „gen „ của một cá thể và để có thể thực hiện các thao tác lai ghép, đột biến trên cấu trúc này. Thông thường có rất nhiều cách để chuyển đổi dữ liệu của bài toán về chuỗi nhị phân. Tuy nhiên, bạn cần lưu ý chọn cách biễu diễn hiệu quả nhất theo quy tắc sau : * Quy tắc biễu diễn gen qua chuỗi nhị phân : Chọn chuỗi nhị phân ngắn nhất nhưng đủ thể hiện được tất cả kiểu gen. Thực chất, đây chính là một quy tắc cũ mà ta đã biết khi bàn về chọn kiểu biến. Lấy ví dụ, để chuyển biến X nguyên có giá trị trong đoạn [32, 63] về chuỗi nhị phân, có thể bạn sẽ chọn dùng một chuỗi nhị phân dài 6 bit (vì 6 bit đủ để biễu diễn một số trong đoạn [0, 63]). Dĩ nhiên, chọn chiều dài 6 bit là đúng nhưng chưa tối ưu. Thực chất, một con số trong đoạn [32, 63] chỉ cần 5 bit là đủ. Vì với 5 bit, ta có thể biểu diễn được một số Y trong đoạn [0, 31]. Cụ thể Y=X-32. Và thay vì biểu diễn trực tiếp số X, ta biểu diễn thông qua trung gian Y. Khi đã có Y ta sẽ dễ dàng suy ra X thông qua cách tính gián tiếp trên. Để biểu diễn chuỗi nhị phân, ta thuờng dùng các cách sau : Mảng Byte, mảng Bit biểu diễn bằng mảng Integer . 1. 2.4.1.1. Mảng byte Đối với mảng byte, mỗi byte chính là một bit và chỉ nhận 2 giá trị 0 và 1. Nếu byte trong mảng có giá trị khác, chương tình sẽ xem đó là lỗi trầm trọng. Cách biễu diễn này có ưu điểm là truy xuất nhanh hơn, nhưng lượng bộ nhớ sẽ tốn gấp 8 lần so với phương pháp không nén. (Ví 1 byte gồm 8 bit, nhưng ta chỉ dùng 1 bit nên 7 bit còn lại sẽ lãng phí) * Trong PASCAL : TYPE Tgen = ARRAY[0..N-1] OF BYTE * Trong C : typed unsigned char Cgen[N] Với N là chiều dài gen của cá thể. 1. 2.4.1.2. Mảng byte nén : Đối với kiểu biểu diễn này, một byte trong mảng sẽ biểu diễn cho 8 bit của chuỗi nhị phân. Bít 0 đến bít 7 sẽ nằm trong byte thứ 0, bit 8 đến 15 sẽ nằm trong byte thứ nhất,....và cứ thế. Một cách tổng quát, bít thứ n sẽ nằm trong byte thứ (n DIV 8). Trong đó (DIV là toán tử chia lấy phần nguyên).