Chương 1. THUẬT GIẢI DI TRUYỀN 1. Tổng quan về thuật giải di truyền [2] 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).
Dựa theo ý kiến của các chuyên gia lĩnh vực (tiếp cận kinh nghiệm). 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com -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. 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.
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. 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. 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com - 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.
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ã LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com - 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 ?