Tài liệ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

1 .. ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNGLỜI NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG 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, VŨ tổng hợp, đúc kết và phát triển để hoàn thành TRẦN MINH 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. THUẬT TOÁN DI TRUYỀN VÀtháng MỘT SỐ Thái Nguyên, 8 năm 2012 Sinh viên ỨNG DỤNG VỚI LỚP CÁC BÀI TOÁN NP LUẬN VĂN THẠC SỸ CÔNG NGHỆ TrầnTHÔNG Vũ Minh TIN Chuyên ngành: Khoa học máy tính Mã số chuyên ngành: 60.48.01 Ngƣời hƣớng dẫn khoa học: TS. Vũ Vinh Quang Thái Nguyên - 2012 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 2 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 8 năm 2012 Sinh viên Trần Vũ Minh Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 3 MỤC LỤC Lời cam đoan...............................................................................................................i Lời cảm ơn..................................................................................................................ii Mục lục......................................................................................................................iii Danh mục các ký hiệu, các chữ viết tắt .................................................................vi Danh mục các bảng...................................................................................................vii Danh mục các hình..................................................................................................viii LỜI MỞ ĐẦU .............................................................................................................1 CHƢƠNG 1 ................................................................................................................3 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 ............................................................................................4 1.2.1 Cá thể, nhiễm sắc thể ......................................................................................4 1.2.2 Quần thể..........................................................................................................4 1.2.3 Chọn lọc (Selection) .......................................................................................4 1.2.4 Lai ghép (Cross-over) ....................................................................................5 1.2.5 Đột biến (Mutation) .......................................................................................5 1.3 Mô hình GA ..........................................................................................................5 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 ............................................................................................7 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 ................................................................................9 1.5.3 Xác định hàm thích nghi ................................................................................9 1.5.4 Cơ chế lựa chọn .............................................................................................10 1.5.5 Các toán tử di truyền ....................................................................................11 1.6. Thuật toán di truyền kinh điển ...........................................................................13 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 4 1.6.1. Mã hóa ..........................................................................................................13 1.6.2. Toán tử chọn lọc ...........................................................................................13 1.6.3. Toán tử lai ghép ............................................................................................14 1.6.4. Toán tử đột biến ............................................................................................16 1.6.5. Thuật toán di truyền mã hóa số thực (RCGA) ...............................................18 CHƢƠNG 2 ..............................................................................................................25 CƠ SỞ TOÁN HỌC CỦA GIẢI THUẬT DI TRUYỀN..........................................25 2.1. Định lý sơ đồ của Holland..................................................................................25 2.1.1. Một số khái niệm ..........................................................................................25 2.1.2. Định lý sơ đồ (Holland 1975) ........................................................................26 2.2. Mô hình Markov của GA ...................................................................................27 2.2.1. Tính Markov .................................................................................................28 2.2.2. Xích Markov trong GA .................................................................................29 2.2.3. Sự hội tụ của thuật toán di truyền ..................................................................29 CHƢƠNG 3 ..............................................................................................................32 GIẢI THUẬT DI TRUYỀN ĐỐI VỚI MỘT SỐ BÀI TOÁN THUỘC LỚP NP 3.1. Khái niệm về lớp các bài toán NP ......................................................................32 3.2. Thuật toán di truyền với bài toán TSP ...............................................................33 3.2.1 Giới thiệu bài toán ........................................................................................33 3.2.2 Mô tả bài toán ..............................................................................................34 3.2.3 Giải thuật GA đối với bài toán TSP .............................................................36 3.3 Thuật toán GA giải bài toán TSP ........................................................................39 3.3.1 Biểu diễn NST ..............................................................................................39 3.3.2 Khởi tạo quần thể ban đầu ...........................................................................39 3.3.3 Chọn hàm thích nghi ...................................................................................39 3.3.4 Các toán tử di truyền ....................................................................................39 3.3.5 Toán tử đột biến .............................................................................................39 3.4. Thuật toán di truyền với bài toán tách từ trong văn bản ....................................48 3.4.1 Một số thuật toán tách từ tiếng Việt hiện nay.................................................50 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 5 3.4.2 Công cụ tách từ dùng GA ..............................................................................52 3.4.3 Công cụ Opensource tách từ tiếng việt ........................................................59 KẾT LUẬN ...............................................................................................................67 TÀI LIỆU THAM KHẢO .........................................................................................68 NHẬN XÉT CỦA GIÁO VIÊN HƢỚNG DẪN ......................................................69 NHẬN XÉT CỦA GIÁO VIÊN PHẢN BIỆN .........................................................70 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 6 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 đủ WFST - Weighted finit-state Transducer: mô hình mạng chuyển dịch trạng thái hữu hạn có trọng số IGATEC - Internet and Genetics Algorithm-based Text Categorization for Documents in Vietnamese: Phƣơng pháp tách từ tiếng Việt dựa trên thống kê từ Internet và thuật toán di truyền df - document frequency: tần số tài liệu fitness: độ thích nghi Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 7 DANH MỤC CÁC BẢNG Bảng 1: Các tham số điều khiển hoạt động của thuật giải di truyền Bảng 2. Thống kê độ dài từ trong từ điển Bảng 3. Tham số thực hiện GA Bảng 4. Gói vn.hus.mim, tokenizer và các gói con Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 8 DANH MỤC CÁC HÌNH Hình 1: Sơ đồ mô tả GA Hình 2: Lai ghép CMX Hình 3: Phân bố của xjci Hình 4: Toán tử lai ghép SX Hình 5: Sự phân lớp các bài toán Hình 6: Giao diện chương trình TSP Hình 7: Giao diện nhập dữ liệu chương trình TSP Hình 8: Giao diện kết quả chương trình TSP Hình 9. Biểu diễn cá thể bằng các bit 0,1 Hình 10. Thang tỉ lệ phát sinh loại từ Hình 11. Quá trình lai ghép Hình 12. Quá trình đột biến Hình 13. Quá trình sinh sản Hình 14. Quá trình chọn cá thể Hình 15. Giao diện chính vnToolkit 3.0.0 Hình 16. Kết quả tách từ Hình 17. Kết quả thống kê từ Hình 18. Kết quả gỡ rối tách từ Hình 19. Kết quả tách câu Hình 20. Kết quả gán nhãn Hình 21. Bộ dán nhãn được sử dụng Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 9 LỜI MỞ ĐẦU Hiện nay trong ngành khoa học máy tính, việc tìm kiếm lời giải tối ƣu cho các bài toán là vấn đề luôn đƣợc các nhà khoa học đặc biệt quan tâm. Mục đích chính của các thuật toán tìm kiếm lời giải là tìm ra lời giải tối ƣu cho bài toán trong thời gian nhỏ nhất. Các thuật toán nhƣ tìm kiếm không có thông tin, vét cạn (tìm kiếm trên danh sách, trên cây hoặc đồ thị ) hoặc các thuật toán tìm kiếm có thông tin đƣợc sử dụng nhiều trong không gian tìm kiếm nhỏ. Đối với không gian tìm kiếm lớn, việc tìm kiếm các lời giải tối ƣu cho bài toán gặp nhiều khó khăn. Do đó, cần thiết phải có những thuật giải tốt và sử dụng kỹ thuật trí tuệ nhân tạo khi giải quyết các bài toán có không gian tìm kiếm lớn. Thuật giải di truyền (Genetic Algorithm GA) là một trong những kỹ thuật tìm kiếm lời giải tối ƣu đã đáp ứng đƣợc yêu cầu của nhiều bài toán và ứng dụng. Cùng với logic mờ, GA đƣợc ứng dụng rất rộng rãi trong các lĩnh vực phức tạp. Sự kết hợp giữa GA và logic mờ đã chứng tỏ đƣợc hiệu quả trong các vấn đề khó mà trƣớc đây thƣờng đƣợc giải quyết bằng các phƣơng pháp thông thƣờng hay các phƣơng pháp cổ điển, nhất là trong các bài toán cần có sự lƣợng giá, đánh giá sự tối ƣu của kết quả thu đƣợc. 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, GA là một kỹ thuật chung giúp giải quyết vấn đề bài toán bằng cách mô phỏng sự tiến hóa của con ngƣời hay của sinh vật nói chung trong những điều kiện đƣợc qui định sẵn của môi trƣờng. GA là một thuật giải và mục tiêu của GA không nhằm đƣa ra lời giải chính xác tối ƣu mà là đƣa ra lời giải tƣơng đối tối ƣu. John Holland (1975) và Goldberg (1989) đã đề xuất và phát triển GA, là thuật giải tìm kiếm dựa trên cơ chế chọn lọc và di truyền tự nhiên. Thuật giải này sử dụng các nguyên lý di truyền về sự thích nghi và sự sống các cá thể thích nghi nhất trong tự nhiên. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 10 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. Vấn đề làm sao để tổ chức và tìm kiếm một lƣợng thông tin lớn nhƣ vậy một cách có hiệu quả? GA hiện đang đƣợc ứng dụng hiệu quả trong việc phân loại thông tin phục vụ cho việc tìm kiếm văn bản. Với những lý do trên, em chọn đề tài: “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” làm luận văn tốt nghiệp. Nội dung chính của 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, thuật toán di truyền mã hóa số thực. Chương 2 trình bày cơ sở toán học về sự hội tụ của thuật toán di tuyền thông qua mô hình Markov và định lý sơ đồ của Holland. Chương 3 trình bày hai nội dung chính: + Giới thiệu bài toán ngƣời du lịch (Travelling Salesman Problems – TSP) là một trong những bài toán thuộc lớp NP và phƣơng pháp giải bài toán này bằng thuật toán di truyền. + Giới thiệu về bài toán tách từ trong văn bản, ứng dụng của GA đối với bài toán tách từ trong văn bản thông qua bộ công cụ tách từ dùng thuật giải di truyền vnToolkit 3.0. Các kết quả lý thuyết về bài toán TSP và bài toán tách từ trong văn bản đã đƣợc kiểm nghiệm thông qua các chƣơng trình thực nghiệm viết trên nền ngôn ngữ C# và Java. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 11 Chƣơng 1 GIẢI THUẬT DI TRUYỀN 1.1 Giới thiệu về GA 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: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 12 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á). Ý 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 NST (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 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 13 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. 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 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 14 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: Sơ đồ mô tả GA 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. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 15 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 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: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 16 + 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 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. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 17 + 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. + 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 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 18 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ể. Sau đây sẽ giới thiệu một số cơ chế hay áp dụng. Ta sử dụng các kí hiệu nhƣ sau: - Kí hiệu NST thứ i là v i . - Hàm tính độ thích nghi của NST v i là f (vi ) - Kích thƣớc quần thể là pop_size(). - Số NST cần chọn là N. + Cơ chế lựa chọn theo bánh xe Roulette Bƣớc 1: Tính tổng độ thích nghi của cả quần thể: F  pop _ size  f (v ) i 1 Bƣớc 2: Tính xác suất chọn pi cho mỗi NST vi : pi  i f (v i ) F i Bƣớc 3: Tính vị trí xác suất qi của mỗi NST: q i   p i j 1 Bƣớc 4: Sử dụng cơ chế lựa chọn theo bánh xe Roulette đƣợc thực hiện bằng cách quay bánh xe Roulette N lần. Mỗi lần chọn một NST từ quần thể hiện hành vào quần thể mới theo nguyên tắc: - Phát sinh ngẫu nhiên một số r trong khoảng [0,1] . - Nếu r  q1 thì chọn NST v1; ngƣợc lại thì chọn NST thứ i (2  i  pop_size) sao cho qi-1  r  qi. Với cơ chế lựa chọn nhƣ thế này thì có một số nhiếm sắc thể sẽ đƣợc chọn nhiều lần. Điều này phù hợp với lý thuyết lƣợc đồ: các NST tốt nhất thì có nhiều bản sao, NST trung bình thì không đổi , NST kém thì chết đi. + Cơ chế lựa chọn xếp hạng Cơ chế lựa chọn xếp hạng đƣợc mô tả nhƣ sau: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 19 Bƣớc 1: Sắp xếp các NST trong quần thể theo độ thích nghi từ thấp đến cao. Bƣớc 2: Đặt lại độ thích nghi cho quần thể đã sắp xếp theo kiểu: NST thứ nhất có độ thích nghi là 1, NST thứ hai có độ thích nghi là 2, .v.v., NST thứ pop_size có độ thích nghi là pop_size. Theo phƣơng pháp này việc một NST đƣợc chọn nhiều lần nhƣ trong lựa chọn theo kiểu bánh xe Roulette đã giảm đi. Nhƣng nó có thể dẫn đến sự hội tụ chậm và NST có độ thích nghi cao cũng không khác mấy so với các NST khác. + Cơ chế lựa chọn theo lấy mẫu ngẫu nhiên Cơ chế lựa chọn theo mẫu đƣợc thực hiện nhƣ sau: Bƣớc 1: Biểu diễn xác suất chọn các NST lên trên một đƣờng thẳng. Bƣớc 2: Đặt N điểm chọn lên đƣờng thẳng. Các điểm chọn này cách nhau điểm đầu tiên đặt ngẫu nhiên trong khoảng [0, 1 , N 1 ] N Bƣớc 3: Với một điểm chọn, NST gần với nó nhất về bên phải sẽ đƣợc chọn. Phƣơng pháp này có đặc điểm là các điểm chọn đƣợc phân bố đều trên trục số, do đó sẽ gần với điểm xứng đáng đƣợc chọn. 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 toán tử có tác động lớn đến chất lƣợng của giải thuật. Các toán tử này đƣợc xây dựng phụ thuộc vào cách mã hoá các NST. Ở đây chỉ đƣa ra toán tử lai ghép và đột biến trên một số cách mã hoá NST để chỉ ra đƣợc ý tƣởng xây dựng toán tử lai ghép và đột biến trong GA. Còn tuỳ thuộc vào các bài toán cụ thể và cách mã hoá NST mà ta xây dựng hai loại toán tử này. Toán tử lai ghép + Lai ghép đơn điểm: - Một điểm cắt đƣợc chọn tại một vị trí thứ k trên NST. - Từ đầu NST đến vị trí thứ k, NST con sao chép từ cha, phần còn lại sao chép từ mẹ. Với NST cha: X = 11001010, NST mẹ Y = 11101001 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 20 Con sinh ra do lai ghép đơn (điểm cắt k=4): Con : 1100 | 1001 + Lai ghép hai điểm: - Hai điểm cắt đƣợc chọn . - Từ đầu cho đến điểm cắt thứ nhất đƣợc sao chép từ cha, từ điểm cắt thứ nhất đến điểm cắt thứ hai sao chép từ mẹ và phần còn lại sao chép từ cha. Xét Cha : 11| 0010 | 10 Mẹ : 11| 1010 | 01 Con sinh ra do lai ghép hai điểm cắt : Con : 11 | 1010| 10 + Lai ghép mặt nạ : - Xây dựng một mặt nạ là một chuỗi nhị phân có chiều dài bằng chiều dài NST, Mặt nạ đƣợc phát sinh ngẫu nhiên đối với từng cặp cha mẹ. - Xây dựng NST mới: Duyệt qua mặt nạ, bit có giá trị 1 thì sao chép gen tại vị trí đó từ NST cha sang con, bit có giá trị 0 thì sao chép từ mẹ. Ví dụ xét Cha : Mẹ 11001010 : 10101001 Mặt nạ : 10101000 Con sinh ra do lai ghép mặt nạ : Con : 10001001 + Lai ghép số học: NST con đƣợc tạo thành bằng cách thực hiện một phép toán logic nào đó nhƣ AND, OR, … với cặp NST bố mẹ. Ví dụ xét Cha : 11001010 Mẹ : 10101001 Con (AND): 10001000 Toán tử đột biến Phép đảo bit : Bit đƣợc chọn sẽ bị đảo (Bit đƣợc chọn có gạch chân) Nếu trƣớc đột biến : 11011001 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn