chương 1 trình bày một số khái niệm về giải thuật di truyền, mô hình thiết kế giải thuât, các toán tử trong GA. Thuật toán di truyền mã hóa số thực. Các kết quả được tham khảo trong các tài liệu [2, 3, 4, 5, 6, 7, 8] 1.1 Giới thiệu về GA Giải thuật di truyền GA(GENETIC ALGORITHM) do D. Goldberg đề xuất, sau đó được L.
Michalevicz phát triển là kỹ thuật phỏng theo quá trình thích nghi tiến hóa của các quần thể sinh học dựa trên học thuyết Darwin, đây cũng chính là một trong các thuật toán tiến hóa. Thuật toán tiến hóa là các chương trình máy tính có dùng các thuật toán tìm kiếm, tối ưu hóa dựa trên nguyên lý tiến hóa tự nhiên. GA là phương pháp tìm kiếm tối ưu ngẫu nhiên bằng cách mô phỏng theo sự tiến hóa của con người hay của sinh vật. Tư tưởng của thuật toán di truyền là mô phỏng các hiện tượng tự nhiên, là kế thừa và đấu tranh sinh tồn.
GA thuộc lớp các giải thuật xuất sắc nhưng lại rất khác các giải thuật ngẫu nhiên vì chúng kết hợp các phần tử tìm kiếm trực tiếp và ngẫu nhiên. Khác biệt quan trọng giữa tìm kiếm của GA và các phương pháp tìm kiếm khác là GA duy trì và xử lý một tập các lời giải, gọi là một quần thể (population). Trong GA, việc tìm kiếm giả thuyết thích hợp được bắt đầu với một quần thể, hay một tập hợp có chọn lọc ban đầu của các giả thuyết. Các cá thể của quần thể hiện tại khởi nguồn cho quần thể thế hệ kế tiếp bằng các hoạt động lai ghép và đột biến ngẫu nhiên – được lấy mẫu sau các quá trình tiến hóa sinh học.
Ở mỗi bước, các giả thuyết trong quần thể hiện tại được ước lượng liên hệ với đại lượng thích nghi, với các giả thuyết phù hợp nhất được chọn theo xác suất là các hạt giống cho việc sản sinh thế hệ kế tiếp, gọi là cá thể (individual). 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 và ngược lại sẽ bị đào thải. GA có thể dò tìm thế hệ mới có độ thích nghi tốt hơn. GA giải quyết các bài toán quy hoạch toán học thông qua các quá trình cơ bản: lai tạo (crossover), đột biến (mutation) và chọn lọc Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com (selection) cho các cá thể trong quần thể.
Dùng GA đòi hỏi phải xác định được: khởi tạo quần thể ban đầu, hàm đánh giá các lời giải theo mức độ thích nghi – hàm mục tiêu, các toán tử di truyền tạo hàm sinh sản. Trong công nghệ thông tin, GA là một thành phần của Tính toán tiến hóa (Evolutionary computation – EC), một lĩnh vực được coi là có tốc độ phát triển nhanh của trí tuệ nhân tạo. Có thể chia EC thành 5 hướng nghiên cứu như sau : - GA (Genetic Algorithm - GA): Dựa vào quá trình di truyền trong tự nhiên để cải tiến lời giải qua các thế hệ bắt nguồn từ một tập các lời giải ban đầu. - Quy hoạch tiến hoá (Evolutionary Programming - EP): Dựa vào quy luật tiến hoá, tìm phương pháp kết hợp đủ khả năng giải quyết trọn vẹn một bài toán từ một lớp các phương pháp giải quyết được một số phần của bài toán.
- Các chiến lược tiến hoá (Evolutionary Strategies - ES): Dựa trên một số chiến lược ban đầu, tiến hoá để tạo ra những chiến lược mới phù hợp với môi trường thực tế một cách tốt nhất. - Lập trình di truyền (Genetic Programming - GP): Mở rộng GA trong lĩnh vực các chương trình của máy tính. Mục đích của nó là để sinh ra một cách tự động các chương trình máy tính giải quyết một cách tối ưu một vấn đề cụ thể. - Các hệ thống phân loại (Classifier Systems- CS): Các GA đặc biệt được dùng trong việc học máy và việc phát hiện các quy tắc trong các hệ dựa trên các quy tắc.
GA cũng như các thuật toán tiến hoá đều được hình thành dựa trên một quan niệm được coi là một tiên đề phù hợp với thực tế khách quan. Đó là quan niệm "Quá trình tiến hoá 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". 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 thế hệ trước. Sự hình thành và phát triển của GA trên thế giới có thể được điểm qua các mốc thời gian quan trọng như sau: Năm 1960, ý tưởng đầu tiên về Tính toán tiến hoá được Rechenberg giới thiệu trong công trình “Evolution Strategies” (Các chiến lược tiến hoá).
Ý Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com tưởng này sau đó được nhiều nhà nghiên cứu phát triển. Năm 1975, Giải thuật gen do John Holland phát minh và được phát triển bởi ông cùng với các đồng nghiệp và những sinh viên. Cuốn sách "Adaption in Natural and Artificial Systems" (Sự thích nghi trong các hệ tự nhiên và nhân tạo) đã tổng hợp các kết quả của quá trình nghiên cứu và phát triển đó. Năm 1992, John Koza đã dùng GA để xây dựng các chương trình giải quyết một số bài toán và gọi phương pháp này là “lập trình gen”.
Ngày nay GA càng trở nên quan trọng, đặc biệt là trong lĩnh vực tối ưu hoá, một lĩnh vực có nhiều bài toán thú vị, được ứng dụng nhiều trong thực tiễn nhưng thường khó và chưa có giải thuật hiệu quả để giải .2 Các khái niệm cơ bản 1.1 Cá thể, nhiễm sắc thể Trong GA, một cá thể biểu diễn một phương án của bài toán. Trong trường hợp tổng quát, một cá thể có nhiều Nhiễm sắc thể(NST), ở đây ta quan niệm một cá thể chỉ có một NST. Do đó khái niệm cá thể và NST trong GA coi như là tương đương. Một NST được tạo thành từ nhiều gen, mỗi gen có thể có các giá trị khác nhau để quy định một tính trạng nào đó.
Trong GA, một gen được coi như một phần tử trong chuỗi NST.2 Quần thể Quần thể là một tập hợp các cá thể có cùng một số đặc điểm nào đấy. Trong GA ta quan niệm quần thể là một tập các lời giải của một bài toán.3 Chọn lọc (Selection) Trong tự nhiên, quá trình chọn lọc và đấu tranh sinh tồn đã làm thay đổi các cá thể trong quần thể. Những cá thể tốt, thích nghi được với điều kiện sống thì có khả năng đấu tranh lớn hơn, do đó có thể tồn tại và sinh sản. Các cá thể không thích nghi được với điều kiện sống thì dần mất đi.
Dựa vào nguyên lý của quá trình chọn lọc và đấu tranh sinh tồn trong tự nhiên, chọn lựa các cá thể trong GA chính là cách chọn các cá thể có độ thích nghi tốt để đưa vào thế hệ tiếp theo hoặc để cho lai ghép, với mục đích là sinh ra các cá thể mới tốt hơn. Có nhiều cách để lựa chọn nhưng cuối cùng đều nhằm đáp ứng mục tiêu là các cá thể tốt sẽ có khả năng được chọn cao hơn. Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.4 Lai ghép (Cross-over) Lai ghép trong tự nhiên là sự kết hợp các tính trạng của bố mẹ để sinh ra thế hệ con. Trong GA, lai ghép được coi là một sự tổ hợp lại các tính chất (thành phần) trong hai lời giải cha mẹ nào đó để sinh ra một lời giải mới mà có đặc tính mong muốn là tốt hơn thế hệ cha mẹ.
Đây là một quá trình xảy ra chủ yếu trong GA.5 Đột biến (Mutation) Đột biến là một sự biến đổi tại một (hay một số) gen của NST ban đầu để tạo ra một NST mới. Đột biến có xác suất xảy ra thấp hơn lai ghép. Đột biến có thể tạo ra một cá thể mới tốt hơn hoặc xấu hơn cá thể ban đầu. Tuy nhiên trong GA thì ta luôn muốn tạo ra những phép đột biến cho phép cải thiện lời giải qua từng thế hệ.3 Mô hình GA Với các khái niệm được giới thiệu ở trên, GA được mô tả bởi sơ đồ sau đây Bắt đầu Nhận các tham số của bài toán Khởi tạo quần thể ban đầu Tính giá trị thích nghi Điều kiện dừng Sinh sản Lai ghép Lựa chọn giải pháp tốt nhất Đột biến Kết thúc Hình 1.1: Sơ đồ mô tả GA Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Như vậy giải thuật GA được xây dựng qua các bước cơ bản sau đây: 1.
Xác lập các tham số ban đầu của bài toán. Khởi tạo: Sinh ngẫu nhiên một quần thể gồm n cá thể (là n lời giải ban đầu của bài toán). Xác lập quần thể mới: tạo quần thể mới bằng cách lặp lại các bước sau cho đến khi quần thể mới hoàn thành, bao gồm: 3.1 Tính độ thích nghi của mỗi cá thể.2 Kiểm tra điều kiện kết thúc giải thuật.3 Chọn lọc các cá thể bố mẹ từ quần thể cũ theo độ thích nghi của chúng (cá thể có độ thích nghi càng cao thì càng có nhiều khả năng được chọn).4 Tiến hành lai ghép các cặp bố-mẹ với một xác suất lai ghép được chọn để tạo ra một cá thể mới.5 Tiến hành đột biến với xác suất đột biến được chọn xác định cá thể đột biến. Kiểm tra điều kiện dừng: Nếu điều kiện được thỏa mãn thì thuật toán kết thúc và trả về lời giải tốt nhất chính là quần thể hiện tại.4 Các tham số của GA 1.1 Kích thước quần thể Kích thước quần thể cho biết có bao nhiêu cá thể trong một quần thể (trong một thế hệ).
Qua các nghiên cứu cũng như các thử nghiệm đã cho thấy kích thước quần thể không nên quá bé cũng như không quá lớn. Nếu có quá ít cá thể thì ít có khả năng thực hiện lai giống và chỉ một phần nhỏ không gian tìm kiếm được dùng. Như vậy sẽ dễ xảy ra trường hợp bỏ qua các lời giải tốt. Nhưng quá nhiều cá thể cũng không tốt vì GA sẽ chạy chậm đi, ảnh hưởng đến hiệu quả của giải thuật.
Các nghiên cứu cũng đã chỉ ra không có lợi khi tăng kích thước quần thể lên quá một giới hạn cho phép.2 Xác suất lai ghép Xác suất lai ghép cho biết việc lai ghép tạo ra thế hệ mới được thực hiện Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com thường xuyên như thế nào.