Luận văn Thạc sĩ Khoa học máy tính: Cơ sở của thuật toán di truyền và ứng dụng đối với một số bài toàn lớp NP

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:70

Thêm vào BST

Báo xấu

26
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Cấu trúc luận văn gồm 3 chương: Chương 1 - Trình bày các khái niệm cơ bản, mô hình, các tham số cơ bản, các phép toán, cơ chế thực hiện tổng quát của thuật toán di truyền; Chương 2 - Trình bày khái niệm về thuật toán và độ phức tạp của thuật toán, sự phân lớp các bài toán qua độ phức tạp, một số mô hình bài toán lớp NP; Chương 3 - Trình bày kết quả sử dụng GA xây dựng thuật toán giải bài toán lập lịch phân công giảng dạy tại mô hình trường cao đẳng dạy nghề. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Khoa học máy tính: Cơ sở của thuật toán di truyền và ứng dụng đối với một số bài toàn lớp NP

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN THỊ DUYÊN CƠ SỞ CỦA THUẬT TOÁN DI TRUYỀN VÀ ỨNG DỤNG ĐỐI VỚI MỘT SỐ BÀI TOÀN LỚP NP LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Người hướng dẫn khoa học: TS. VŨ VINH QUANG THÁI NGUYÊN, 2020 Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN THỊ DUYÊN CƠ SỞ CỦA THUẬT TOÁN DI TRUYỀN VÀ ỨNG DỤNG ĐỐI VỚI MỘT SỐ BÀI TOÀN LỚP NP Chuyên ngành: Khoa học máy tính Mã số: 8 48 01 01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Người hướng dẫn khoa học: TS. VŨ VINH QUANG THÁI NGUYÊN, 2020 Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn
LỜI CAM ĐOAN Sau quá trình học tập tại Trường Đại học công nghệ thông tin & truyền thông, với những kiến thức lý thuyết và thực hành đã tích lũy được, với việc vận dụng các kiến thức vào thực tế, em đã tự nghiên cứu các tài liệu, các công trình nghiên cứu, đồng thời có sự phân tích, tổng hợp, đúc kết và phát triển để hoàn thành luận văn thạc sĩ của mình. Em xin cam đoan luận văn này là công trình do bản thân em tự tìm hiểu, nghiên cứu và hoàn thành dưới sự hướng dẫn của thầy giáo TS. Vũ Vinh Quang. Thái Nguyên, tháng 7 năm 2020 Sinh viên Nguyễn Thị Duyên Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn
LỜI CẢM ƠN Trong thời gian hai năm của chương trình đào tạo thạc sỹ, trong đó gần một nửa thời gian dành cho các môn học, thời gian còn lại dành cho việc lựa chọn đề tài, giáo viên hướng dẫn, tập trung vào nghiên cứu, viết, chỉnh sửa và hoàn thiện đề tài. Với quỹ thời gian như vậy và với vị trí công việc đang phải đảm nhận, không riêng bản thân em mà hầu hết các sinh viên cao học muốn hoàn thành tốt luận văn của mình trước hết đều phải có sự sắp xếp thời gian hợp lý, có sự tập trung học tập và nghiên cứu với tinh thần nghiêm túc, nỗ lực hết mình; tiếp đến cần có sự ủng hộ về tinh thần, sự giúp đỡ về chuyên môn một trong những điều kiện không thể thiếu quyết định đến việc thành công của đề tài. Để hoàn thành được đề tài này trước tiên em xin gửi lời cảm ơn đến thầy giáo hướng dẫn TS. Vũ Vinh Quang, người đã có những định hướng cho em về nội dung và hướng phát triển của đề tài, người đã có những đóng góp quý báu cho em về những vấn đề chuyên môn của đề tài, giúp em tháo gỡ kịp thời những vướng mắc trong quá trình làm luận văn. Em cũng xin cám ơn các thầy cô giáo Trường Đại học Công nghệ thông tin và Truyền thông cũng như bạn bè cùng lớp đã có những ý kiến đóng góp bổ sung cho đề tài luận văn của em. Xin cảm ơn gia đình, người thân cũng như đồng nghiệp luôn quan tâm, ủng hộ hỗ trợ về mặt tinh thần trong suốt thời gian từ khi nhận đề tài đến khi hoàn thiện đề tài này. Em xin hứa sẽ cố gắng hơn nữa, tự trau dồi bản thân, tích cực nâng cao năng lực chuyên môn của mình để sau khi hoàn thành đề tài này sẽ có hướng tập trung nghiên cứu sâu hơn, không ngừng hoàn thiện hơn nữa đề tài của mình để có những ứng dụng thực tiễn cao trong thực tế. Thái Nguyên, tháng 7 năm 2020 Sinh viên Nguyễn Thị Duyên Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn
MỤC LỤC LỜI CAM ĐOAN .............................................................................................. i LỜI CẢM ƠN ................................................................................................... ii DANH MỤC CÁC BẢNG.............................................................................. vii DANH MỤC CÁC HÌNH .............................................................................. viii LỜI MỞ ĐẦU ................................................................................................... 1 CHƯƠNG 1 GIẢI THUẬT DI TRUYỀN ........................................................ 3 1.1 Giới thiệu về GA ......................................................................................... 3 1.2 Các khái niệm cơ bản .................................................................................. 5 1.2.1 Cá thể, nhiễm sắc thể ............................................................................ 5 1.2.2 Quần thể ................................................................................................ 5 1.2.3 Chọn lọc (Selection) ............................................................................. 5 1.2.4 Lai ghép (Cross-over) .......................................................................... 6 1.2.5 Đột biến (Mutation) ............................................................................. 6 1.3 Mô hình GA ................................................................................................ 6 1.4 Các tham số của GA .................................................................................... 7 1.4.1 Kích thước quần thể .............................................................................. 7 1.4.2 Xác suất lai ghép ................................................................................... 7 1.4.3 Xác suất đột biến .................................................................................. 8 1.5 Cơ chế thực hiện GA ................................................................................... 8 1.5.1 Mã hóa .................................................................................................. 8 1.5.2 Khởi tạo quần thể ban đầu .................................................................... 10 1.5.3 Xác định hàm thích nghi ..................................................................... 10 1.5.4 Cơ chế lựa chọn ................................................................................... 10 1.5.5 Các toán tử di truyền ........................................................................... 10 1.6. Thuật toán di truyền kinh điển ................................................................. 12 1.6.1. Mã hóa ................................................................................................ 12 Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn
1.6.2. Toán tử lai ghép .................................................................................. 13 1.6.3. Toán tử đột biến .................................................................................. 15 1.6.4. Thuật toán di truyền mã hóa số thực (RCGA) ..................................... 15 CHƯƠNG 2 LỚP BÀI TOÁN NP VÀ MỘT SỐ MÔ HÌNH ........................ 22 2.1 Khái niệm về thuật toán và độ phức tạp thuật toán................................... 22 2.1.1 Khái niệm về thuật toán ...................................................................... 22 2.1.2. Các yêu cầu của thuật toán ................................................................ 22 2.2. Độ phức tạp của thuật toán....................................................................... 23 2.2.1. Chi phí phải trả cho một quá trình tính toán ...................................... 23 2.2.2. Độ phức tạp của thuật toán ................................................................ 24 2.2.3. Các qui tắc xác định độ phức tạp thuật toán ...................................... 25 2.3. Vấn đề phân lớp các bài toán dựa trên độ phức tạp thuật toán. ............... 25 2.3.1. Lớp bài toán P .................................................................................... 25 2.3.2. Lớp NP ............................................................................................... 26 2.3.3. Lớp NPC ............................................................................................ 26 2.4 Một số mô hình bài toán lớp NP ............................................................... 27 2.4.1 Mô hình bài toán KNAPSACK .......................................................... 27 2.4.2 Bài toán quân cờ Domino ................................................................... 30 2.4.3 Mô hình bài toán TSP ......................................................................... 33 CHƯƠNG 3: ỨNG DỤNG GIẢI THUẬT DI TRUYỀN GIẢI BÀI TOÁN LẬP LỊCH GIẢNG DẠY THỰC HÀNH....................................................... 35 3.1 Mô hình bài toán thực tế ........................................................................... 35 3.2 Thiết kế giải thuật di truyền GA ............................................................... 37 3.2.1 Xây dựng cấu trúc cá thể, các hàm kiểm tra ....................................... 37 3.2.2 Xây dựng các toán tử trong GA .......................................................... 38 3.3 Các kết quả thực nghiệm ........................................................................... 39 3.3.1 Bộ số liệu Test 1 ................................................................................. 39 3.3.2 Bộ số liệu Test 2 ................................................................................. 42 Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn
KẾT LUẬN ..................................................................................................... 46 TÀI LIỆU THAM KHẢO ............................................................................... 47 PHẦN PHỤ LỤC ............................................................................................ 48 NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN ............................................ 60 Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT GA – Genetic Algorithm: giải thuật di truyền TSP - Travelling Salesman Problems: bài toán người du lịch EC - Evolutionary computation: tính toán tiến hóa EP - Evolutionary Programming: quy hoạch tiến hóa ES - Evolutionary Strategies: các chiến lược tiến hóa GP - Genetic Programming: lập trình di truyền CS - Classifier Systems: các hệ thống phân loại NST – nhiễm sắc thể Selection: chọn lọc Cross-over: lai ghép Mutation: đột biến Reproduction: sinh sản pop-size: kích cỡ quần thể RCGA: thuật toán di truyền mã hóa số thực BLX-α - Blend Crossover: lai ghép BLX-α CMX - Center of Mass Crossover: lai ghép CMX NP-hard: bài toán NP khó NP-complete: bài toán NP đầy đủ Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn
DANH MỤC CÁC BẢNG Bảng 2.1: Bảng giá trị độ phức tạp tính toán của các hàm số ......................... 24 Bảng 3.1: Giáo viên phù hợp chuyên môn với phòng thực hành ................... 40 Bảng 3.2: Giáo viên sẵn sàng nhận buổi hướng dẫn ....................................... 40 Bảng 3.3: Lịch giảng dạy Test 1 ..................................................................... 41 Bảng 3.4: Số buổi giảng dạy đối với các giáo viên Test 1 .............................. 41 Bảng 3.5: Lịch giảng dạy Test 1 ..................................................................... 41 Bảng 3.6: Số buổi giảng dạy đối với các giáo viên......................................... 41 Bảng 3.7 Lịch giảng dạy ................................................................................. 41 Bảng 3.8 Số buổi giảng dạy đối với các giáo viên .......................................... 42 Bảng 3.9: Bảng các giáo viên phù hợp chuyên môn với phòng thực hành .... 42 Bảng 3.10: Bảng các giáo viên sẵn sàng nhận buổi hướng dẫn ...................... 43 Bảng 3.11: Lịch giảng dạy Test 2 ................................................................... 44 Bảng 3.12: Số buổi giảng dạy đối với các giáo viên Test 2............................ 44 Bảng 3.13: Lịch giảng dạy .............................................................................. 44 Bảng 3.14: Số buổi giảng dạy đối với các giáo viên....................................... 45 Bảng 3.15: Lịch giảng dạy .............................................................................. 45 Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn
DANH MỤC CÁC HÌNH Hình 1.1: Sơ đồ mô tả GA................................................................................. 6 Hình 1.2: Lai ghép CMX ............................................................................... 19 Hình 1.3: Phân bố của x cij ............................................................................... 19 Hình 1.4: Toán tử lai ghép SX ........................................................................ 20 Hình 2.1: Các lớp P, NP và NPC .................................................................... 26 Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn
LỜI MỞ ĐẦU Trong thực tế, việc tìm kiếm các phương pháp giải lớp các bài toán tối ưu là một lĩnh vực được các nhà khoa học trên thế giới đặc biệt quan tâm. Đã có rất nhiều các công trình nghiên cứu về lĩnh vực này, chủ yếu được phát triển trong lý thuyết tối ưu hóa đối với mô hình các bài toán quy hoạch và mô hình các bài toán trong công nghệ thông tin để tìm kiếm các thuật toán giải các lớp bài toán NP. Trong thời gian gần đây một hướng nghiên cứu quan trọng được phát triển trong lĩnh vực tính toán tiến hóa, đó chính là nghiên cứu về thuật toán di truyền (Genetic Algorithm - GA). Chính vì vậy, GA đã trở thành một trong những đề tài nghiên cứu thu hút được nhiều sự quan tâm và hiện nay đã và đang đem đến rất nhiều ứng dụng trong thực tiễn. Xuất phát từ thuyết tiến hóa muôn loài của Darwin, các nhà toán học John Holland (1975) và Goldberg (1989) đã đề xuất và phát triển GA. GA là một thuật toán đưa ra lời giải tương đối tối ưu. Tư tưởng chính của thuật toán là tìm kiếm lời giải tối ưu dựa trên cơ chế lai ghép, chọn lọc, sử dụng các nguyên lý về tính di truyền, sự thích nghi và sự sống các cá thể thích nghi nhất trong tự nhiên từ đó tiếp cận đến lời giải tối ưu của bài toán đang xét. Ngày nay, GA được ứng dụng khá nhiều trong các lĩnh vực như khoa học, kinh doanh và giải trí. Đầu tiên phải kể đến là các bài toán tối ưu bao gồm: Tối ưu số và tối ưu tổ hợp đã sử dụng GA để tìm lời giải như là bài toán người du lịch (Travelling Salesman Problems - TSP). Một ứng dụng khác cũng đang được ứng dụng rộng rãi của GA là giải quyết vấn đề bùng nổ về lượng thông tin trên mạng internet bao gồm: Thư viện điện tử, thông tin điện tử... dẫn đến phát sinh một số lượng lớn văn bản với tốc độ tăng chóng mặt. Nội dung chính của luận văn là nghiên cứu thuật toán di truyền và một số ứng dụng với lớp các bài toán NP. Cấu trúc luận văn gồm 3 chương: Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn
Chương 1 trình bày các khái niệm cơ bản, mô hình, các tham số cơ bản, các phép toán, cơ chế thực hiện tổng quát của thuật toán di truyền. Chương 2 trình bày khái niệm về thuật toán và độ phức tạp của thuật toán, sự phân lớp các bài toán qua độ phức tạp, một số mô hình bài toán lớp NP. Chương 3 trình bày kết quả sử dụng GA xây dựng thuật toán giải bài toán lập lịch phân công giảng dạy tại mô hình trường cao đẳng dạy nghề. Các kết quả kiểm tra thuật toán GA giải một số mô hình bài toán NP đã được lập trình trên môi trường Matlab version 7.0. Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn
Chương 1. GIẢI THUẬT DI TRUYỀN Nội dung chính của 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.E. Goldberg đề xuất, sau đó được L. Davis và Z. 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.tnu.edu.vn
(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.tnu.edu.vn
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 . 1.2 Các khái niệm cơ bản 1.2.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. 1.2.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. 1.2.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.tnu.edu.vn
1.2.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. 1.2.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ệ. 1.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.tnu.edu.vn
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. 2. 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). 3. 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ể. 3.2 Kiểm tra điều kiện kết thúc giải thuật. 3.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). 3.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. 3.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. 4. 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. 1.4 Các tham số của GA 1.4.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. 1.4.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.tnu.edu.vn
thường xuyên như thế nào. Nếu xác suất lai ghép là pc, khi đó khả năng để một cá thể được lai ghép là pc. Nếu không thực hiện lai ghép, con sinh ra sẽ giống hoàn toàn bố mẹ. Nếu được lai ghép, con sinh ra sẽ có một phần giống bố và một phần giống mẹ. 1.4.3 Xác suất đột biến Xác suất đột biến cho biết các gen của NST thay đổi thường xuyên như thế nào. Nếu xác suất đột biến là pm, khi đó khả năng để mỗi gen của một NST bất kỳ bị đột biến là pm. Toán tử đột biến có tác dụng ngăn ngừa GA rơi vào tình trạng cực trị địa phương, tuy nhiên nếu thực hiện đột biến với xác suất quá cao sẽ biến GA thành giải thuật tìm kiếm ngẫu nhiên. Nhận xét: Xuất phát từ sơ đồ thực hiện GA, chúng ta có thể có một số nhận xét như sau: + GA lập luận mang tính chất ngẫu nhiên để tìm giải pháp tối ưu cho những vấn đề phức tạp, thay vì xác định như toán học giải tích. Tuy nhiên đây là hình thức ngẫu nhiên có hướng dẫn bởi trị số thích nghi. Chính hàm thích nghi giúp GA tìm giải pháp tối ưu trong rất nhiều giải pháp có thể có. + GA không để ý đến chi tiết vấn đề, trái lại chỉ chú ý đến giải phá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. + GA được sử dụng đặc biệt cho những bài toán yêu cầu tìm kiếm tối ưu toàn cục với không gian tìm kiếm lớn và không thể kiểm soát nhờ khả năng duyệt qua không gian tìm kiếm đại diện mà không thực sự đi qua từng điểm của toàn bộ không gian. 1.5 Cơ chế thực hiện GA 1.5.1 Mã hóa Để có thể thực hiện GA, vấn đề đầu tiên là xuất phát từ bài toán thực tế, ta cần phải mô tả các phương án của bài toán dưới một dạng nào đó (mô hình Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn
toán học, tin học, …). Vấn đề mô tả đó được gọi là các phương pháp mã hóa. Thông thường người ta sử dụng một trong các phương pháp như sau: + Mã hoá nhị phân Mã hoá nhị phân là phương pháp mã hoá NST phổ biến nhất. Trong mã hoá nhị phân, mỗi NST là một chuỗi nhị phân, mỗi bit trong nó có thể biểu diễn một đặc tính của nghiệm. Mã hoá nhị phân thường hay dùng trong các bài toán tối ưu các hàm một biến hay nhiều biến. Khi đó, mỗi chuỗi nhị phân sẽ biểu diễn hàm tại một tập giá trị của các biến. Ngoài ra nó còn được áp dụng trong nhiều loại bài toán khác. Mã hoá nhị phân tuy là phổ biến nhưng nó có một nhược điểm là có thể tạo ra không gian mã hoá lớn hơn so với không gian giá trị của NST. Do đó, với nhiều bài toán thì biểu diễn nhị phân là không hữu hiệu. + Mã hoá hoán vị Trong mã hoá hoán vị, mỗi NST là một chuỗi các số biểu diễn một thứ tự sắp xếp. Mã hoá hoán vị phù hợp cho các bài toán liên quan đến thứ tự. Đối với các bài toán này, việc thao tác trên các NST chính là hoán vị các số trong chuỗi đó làm thay đổi thứ tự của nó. Mã hoá hoán vị có thể được sử dụng trong các bài toán liên quan đến thứ tự như bài toán du lịch hay bài toán lập lịch. + Mã hoá số thực Mã hoá trực tiếp theo giá trị có thể được dùng trong các bài toán sử dụng giá trị phức tạp như trong số thực. Trong đó, mỗi NST là một chuỗi các giá trị. Các giá trị có thể là bất cứ cái gì liên quan đến bài toán, từ số nguyên, số thực, kí tự cho đến các đối tượng phức tạp hơn. Mã hoá số thực thường dùng cho các bài toán đặc biệt. Trong cách mã hoá này ta thường phải phát triển các toán tử đột biến và lai ghép cho phù hợp với từng bài toán. Thông thường mỗi NST được mã hóa là một véc tơ trong không gian. Cách mã hóa này thường sử dụng đối với các bài toán tối ưu số và được phát triển mạnh trong giai đoạn hiện nay. Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn
+ Mã hóa dạng cây Phương pháp này được sử dụng trong các biểu thức toán học. Mỗi NST là một cây của một nhóm đối tượng nào đó. 1.5.2 Khởi tạo quần thể ban đầu Khởi tạo quần thể ban đầu là bước đầu tiên trong GA. Thông thường để khởi tạo quần thể trong bài toán tối ưu, ta tạo ra một cách ngẫu nhiên các lời giải có thể (thường là các lời giải thỏa mãn ràng buộc của bài toán nhưng chưa biết là đại lượng cần tối ưu đã là tối ưu hay chưa). Tuỳ vào từng bài toán cụ thể mà ta có các phương pháp khởi tạo khác nhau. Chất lượng của quần thể ban đầu càng cao thì lời giải mà GA đưa ra càng tốt. 1.5.3 Xác định hàm thích nghi Theo các nghiên cứu và các thử nghiệm của nhiều nhà nghiên cứu về GA thì hàm tính độ thích nghi là một trong hai yếu tố quan trọng nhất quyết định sự thành công hay thất bại của GA. Hàm thích nghi được xây dựng sao cho giá trị thích nghi phải phản ánh được giá trị thực của NST trong việc đáp ứng yêu cầu của bài toán. 1.5.4 Cơ chế lựa chọn Cơ chế lựa chọn được áp dụng khi chọn các cá thể từ quần thể P(t ) để thực hiện việc lai ghép và đột biến, tạo ra quần thể P(t  1) . Có nhiều cách để lựa chọn các cá thể từ một quần thể. Tùy từng mô hình bài toán khác nhau, chúng ta có thể xây dựng các phương pháp lựa chọn khác nhau: thông thường người ta sử dụng một trong 2 phương pháp sau để lựa chọn các cá thể vào quá trình lai ghép + Lựa chọn ngẫu nhiên từ quần thể lấy N cá thể để thực hiện lại ghép + Chọn tất cả các cá thể cùng tham gia lai ghép. 1.5.5 Các toán tử di truyền Các toán tử di truyền của GA là toán tử lai ghép và đột biến. Đây là hai Số hóa bởi Trung tâm Học liệu và Công nghệ thông tin – ĐHTN http://lrc.tnu.edu.vn