tailieunhanh - Giải thuật di truyền-Genetic Algorithm

Với các số ngẫu nhiên, chúng ta đã có những lời giải thật độc đáo cho một số vấn đề-bài toán khó nhất định – những vấn đề-bài toán hiện chưa có một lời giải chính xác, tổng quát nào. Tuy nhiên, nếu chỉ dừng lại ở đó, ngẫu nhiên cũng chỉ là may rủi và hoàn toàn chưa đủ sức giải quyết các vấn đề-bài toán phức tạp hơn hoặc có không gian tìm kiếm lớn hơn. Một ví dụ rất đơn giản là tìm mật mã để mở khóa với mật mã là một con số thập phân. | Generated by Foxit PDF Creator Foxit Software http For evaluation only. THUẬT GIẢI DI TRUYỀN - GENETIC ALGORITHM - Kỳ 1 1. TỪ NGÃU NHIÊN ĐẾN THUẬT GIẢI DI TRUYỀN Với các số ngẫu nhiên chúng ta đã có những lời giải thật độc đáo cho một số vấn đề-bài toán khó nhất định - những vấn đề-bài toán hiện chưa có một lời giải chính xác tổng quát nào. Tuy nhiên nếu chỉ dừng lại ở đó ngẫu nhiên cũng chỉ là may rủi và hoàn toàn chưa đủ sức giải quyết các vấn đề-bài toán phức tạp hơn hoặc có không gian tìm kiếm lớn hơn. Một ví dụ rất đơn giản là tìm mật mã để mở khóa với mật mã là một con số thập phân có 30 chữ số - giả định rằng ổ khóa này chỉ có thể được mở bằng một mật mã duy nhất. 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. Trước 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 sẽ phát sinh ngẫu nhiên hoặc tuần tự theo một quy tắc duyệt nào đó các mã khóa rồi thử xem mật mã này có thể là mã khóa đú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 ổ khóa là trên 50 ta đã phải phát sinh nhiều hơn 1030 2 mật mã. Bạn có biết con số này lớn khủng khiếp đến mức nào không Trên thực tế nếu dùng siêu máy tính Cray và giả định 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ã 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ã . Dĩ nhiên khi đứng trước những vấn đề-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ư với bài toán mở khóa trên là thông tin cho biết trong hai mật mã được phát sinh ra mật mã nào là tốt hơn nghĩa là có khả năng mở khóa cao hơn . Có thể bạn đọc sẽ thắc mắc bằng cách nào để biết được giữa hai mật mã mật mã nào có khả năng mở khóa cao hơn . Thông thường khi mở khóa người ta thường dựa trên các tác nhân vật lý