Tài liệu Tự chỉnh thông số bộ điều khiển mờ dùng các thuật toán tối ưu hóa phỏng sinh học

ðại Học Quốc Gia Tp. Hồ Chí Minh TRƯỜNG ðẠI HỌC BÁCH KHOA ---------------------------------- NGUYỄN ðỨC HOÀNG TỰ CHỈNH THÔNG SỐ BỘ ðIỀU KHIỂN MỜ DÙNG CÁC THUẬT TOÁN TỐI ƯU HÓA PHỎNG SINH HỌC Chuyên ngành: TỰ ðỘNG HÓA LUẬN VĂN THẠC SĨ TP. HỒ CHÍ MINH, tháng 7, năm 2009 CÔNG TRÌNH ðƯỢC HOÀN THÀNH TẠI TRƯỜNG ðẠI HỌC BÁCH KHOA ðẠI HỌC QUỐC GIA TP HỒ CHÍ MINH Cán bộ hướng dẫn khoa học : TS. Huỳnh Thái Hoàng ...................................... (Ghi rõ họ, tên, học hàm, học vị và chữ ký) Cán bộ chấm nhận xét 1 : TS. Nguyễn Thiện Thành ......................................... (Ghi rõ họ, tên, học hàm, học vị và chữ ký) Cán bộ chấm nhận xét 2 : PGS.TS. Nguyễn Tấn Tiến...................................... (Ghi rõ họ, tên, học hàm, học vị và chữ ký) Luận văn thạc sĩ ñược bảo vệ tại HỘI ðỒNG CHẤM BẢO VỆ LUẬN VĂN THẠC SĨ. TRƯỜNG ðẠI HỌC BÁCH KHOA, ngày . .31 . . tháng . 7 . năm . 2009 . i ðẠI HỌC QUỐC GIA TP. HCM TRƯỜNG ðẠI HỌC BÁCH KHOA ---------------- CỘNG HOÀ XÃ HỘI CHỦ NGHIÃ VIỆT NAM ðộc Lập - Tự Do - Hạnh Phúc ---oOo--Tp. HCM, ngày . 31 . tháng . 7 . . năm .2009 . NHIỆM VỤ LUẬN VĂN THẠC SĨ Họ và tên học viên: .Nguyễn ðức Hoàng . . . . . . . . . . . . . . . . . . . . . Giới tính : Nam Ngày, tháng, năm sinh : . 10/01/1984. . . . . . . . . . . . . . . . . . Nơi sinh : Bình Thuận. . . . . Chuyên ngành : . . . . .Tự ñộng hóa. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Khoá (Năm trúng tuyển) : . .2007. . . 1- TÊN ðỀ TÀI: TỰ CHỈNH THÔNG SỐ BỘ ðIỀU KHIỂN MỜ DÙNG CÁC THUẬT TOÁN TỐI ƯU HÓA PHỎNG SINH HỌC 2- NHIỆM VỤ LUẬN VĂN: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .......................................................................... .+ Nghiên cứu các thuật toán tối ưu hóa phỏng sinh học, so sánh ưu khuyết ñiểm của các thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .......................................................................... .+ ðề xuất thuật toán tối ưu phỏng sinh học lai, cải thiện chất lượng lời giải, tốc ñộ hội tụ . . . .......................................................................... .+ Áp dụng chỉnh ñịnh thông số bộ ñiều khiển mờ giữ cân bằng hệ con lắc ngược quay . . . . .......................................................................... .......................................................................... .......................................................................... .......................................................................... .......................................................................... .......................................................................... .......................................................................... ................................................................... 3- NGÀY GIAO NHIỆM VỤ : . . . . . . . . . . . . . . . . . . . . . 4- NGÀY HOÀN THÀNH NHIỆM VỤ : . . . . . . . . . . . . . . . . . . . . . 5- HỌ VÀ TÊN CÁN BỘ HƯỚNG DẪN (Ghi ñầy ñủ học hàm, học vị ): . . . . . . . . . . . . . . . . . TS. Huỳnh Thái Hoàng. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Nội dung và ñề cương Luận văn thạc sĩ ñã ñược Hội ðồng Chuyên Ngành thông qua. CÁN BỘ HƯỚNG DẪN (Họ tên và chữ ký) CHỦ NHIỆM BỘ MÔN QUẢN LÝ CHUYÊN NGÀNH (Họ tên và chữ ký) TS. Nguyễn ðức Thành TS. Huỳnh Thái Hoàng ii Lời cảm ơn Trước hết tôi muốn gửi lời cảm ơn ñến thầy Huỳnh Thái Hoàng, tiến sĩ giảng viên trường ðại học Bách khoa thành phố Hồ Chí Minh, Khoa ðiện – ðiện tử, Bộ môn ðiều khiển Tự ñộng, người ñã hướng dẫn trực tiếp ñể tôi có thể hoàn thành luận văn này. Em xin chân thành cảm ơn những ý kiến ñóng góp, những nhận xét của thầy. Tôi cũng muốn cảm ơn các thầy cô trong Bộ môn ðiều khiển Tự ñộng ñã trang bị cho tôi những kiến thức cần thiết ñể tôi có thể tiếp tục vững bước trên con ñường học vấn. Cuối cùng tôi muốn gửi lời cảm ơn ñến ba mẹ tôi, người ñã chăm lo, nuôi dưỡng và tạo mọi ñiều kiện ñể tôi có thể yên tâm hoàn thành luận văn. Một lần nữa tôi chân thành cảm ơn tất cả mọi người. Tp Hồ Chí Minh, 7/2009 Nguyễn ðức Hoàng iii Tóm tắt Thiết kế bộ ñiều khiển mờ liên quan ñến việc chọn các tham số của hàm thuộc, các hệ số tiền và hậu xử lý, hệ cơ sở luật mờ. Tối ưu các tham số này là ñiều kiện quan trọng ñể ñạt ñược chất lượng ñiều khiển. Khi số biến ngõ vào ít thì phương pháp thử sai trở nên tiện lợi, tuy nhiên khi số biến ngõ vào lớn thì phải yêu cầu các phương pháp khác. Một trong các phương pháp ñó là các thuật toán tối ưu hóa phỏng sinh học. Chúng là những phương pháp tìm kiếm ngẫu nhiên nhưng có tính ñịnh hướng, phỏng theo sự tiến hóa của sinh vật trong tự nhiên hoặc hành vi xã hội của các bầy ñàn. Các phương pháp này ñã ñược ứng dụng thành công trong nhiều lĩnh vực, ñặc biệt là tối ưu hóa các hàm phi tuyến. Trong luận văn này, các thuật toán tối ưu hóa phỏng sinh học ñược sử dụng ñể chỉnh ñịnh tối ưu các tham số bộ ñiều khiển mờ ổn ñịnh hệ con lắc ngược xoay. Các kết quả mô phỏng ñược sử dụng ñể so sánh giữa các thuật toán, từ ñó rút ra kết luận về khả năng ứng dụng của từng thuật toán trong việc chỉnh ñịnh tham số. Ngoài ra, luận văn cũng tập trung vào phân tích và so sánh giữa các thuật toán ñể tìm ra mối liên hệ giữa chúng, ñồng thời có thể kết hợp các ưu ñiểm của chúng lại với nhau ñể tạo ra các thuật toán lai tốt hơn. iv Mục Lục Chương 1 Giới thiệu 1 1.1 ðặt vấn ñề ....................................................................................................................... 1 1.2 Công trình liên quan ....................................................................................................... 2 1.3 Phạm vi nghiên cứu ........................................................................................................ 2 1.4 Tóm lược nội dung luận văn ........................................................................................... 3 Chương 2 Các thuật toán tối ưu hóa phỏng sinh học 4 2.1 Giới thiệu ........................................................................................................................ 4 2.2 Các thuật toán tối ưu hóa phỏng theo sự tiến hóa ........................................................... 5 2.2.1 Thuật toán di truyền (GA) ..................................................................................... 7 2.2.2 Thuật toán tiến hóa sai phân (DE) ......................................................................... 10 2.3 Các thuật toán tối ưu hóa phỏng theo trí tuệ bầy ñàn ..................................................... 13 2.3.1 Thuật toán tối ưu bầy ñàn (PSO) ........................................................................... 13 2.3.2 Thuật toán ếch nhảy (SFLA) ................................................................................. 17 2.3.3 Thuật toán con ong (BA) ....................................................................................... 19 Chương 3 Các thuật toán tối ưu hóa phỏng sinh học lai 22 3.1 Giới thiệu ........................................................................................................................ 22 3.2 So sánh các thuật toán tối ưu hóa phỏng sinh học .......................................................... 22 3.2.1 Giống nhau ............................................................................................................ 22 3.2.2 Khác nhau .............................................................................................................. 23 3.2.3 Nhận xét................................................................................................................. 25 3.3 Các thuật toán tối ưu hóa phỏng sinh học lai .................................................................. 26 3.3.1 Ý tưởng .................................................................................................................. 26 3.3.2 Thuật toán lai HSFL-BA........................................................................................ 26 3.3.3 Kết quả mô phỏng .................................................................................................. 27 3.3.4 Nhận xét ................................................................................................................. 31 3.4 Tóm tắt ............................................................................................................................ 31 Chương 4 Tự chỉnh tham số bộ ñiều khiển mờ ổn ñịnh hệ con lắc ngược xoay 32 4.1 Giới thiệu ........................................................................................................................ 32 4.2 Hệ con lắc ngược xoay.................................................................................................... 32 4.2.1 Mô tả toán học ....................................................................................................... 32 v 4.3 Thiết kế bộ ñiều khiển mờ giữ cân bằng hệ con lắc ngược xoay .................................... 34 4.3.1 Tự chỉnh các tham số bộ ñiều khiển mờ ................................................................ 34 4.3.2 Kết quả mô phỏng.................................................................................................. 36 4.3.3 So sánh và nhận xét ............................................................................................... 49 Chương 5 Kết luận và hướng phát triển 52 5.1 Kết luận ........................................................................................................................... 52 5.1.1 Kết quả ñạt ñược .................................................................................................... 52 5.1.2 Hạn chế .................................................................................................................. 52 5.2 Hướng phát triển ............................................................................................................. 53 Tài liệu tham khảo Phụ Lục A1. Thuật toán di truyền (GA).............................................................................................. pl 1 A2. Thuật toán tiến hóa sai phân (DE) ................................................................................. pl 3 A3. Thuật toán tối ưu bầy ñàn (PSO) ................................................................................... pl 6 A4. Thuật toán ếch nhảy (SFLA).......................................................................................... pl 8 A5. Thuật toán con ong (BA) ............................................................................................... pl 10 A6. Thuật toán lai HSFL-BA ................................................................................................ pl 12 B. Bài báo vi Luận văn cao học Chương 1 Giới thiệu 1.1. ðặt vấn ñề Các bài toán tối ưu hóa rất quan trọng trong thực tiễn, ñặc biệt trong các lĩnh vực kỹ thuật thiết kế, thực nghiệm khoa học và quyết ñịnh trong kinh doanh. Do sự phức tạp của các bài toán ngày càng tăng (tính phi tuyến, số biến cần tối ưu lớn,…) không thể giải quyết ñược bằng các phương pháp tối ưu toán học truyền thống như gradient, toàn phương tuyến tính, quy hoạch ñộng…, ñã thúc ñẩy sự phát triển của các phương pháp khác dựa vào các nguyên lý tự nhiên và trực giác. Một trong những phương pháp ñó là các thuật toán tối ưu hóa phỏng sinh học. ðây là những phương pháp tìm kiếm ngẫu nhiên, bắt chước sự tiến hóa sinh học trong tự nhiên và/hoặc các hành vi xã hội bầy ñàn. Các thuật toán này ñã ñược ứng dụng thành công trong nhiều lĩnh vực, ñặc biệt là lĩnh vực ñiều khiển. Trong ñề tài này, tác giả sử dụng một số thuật tóan tối ưu hóa phỏng sinh học ñể chỉnh ñịnh tối ưu tham số bộ ñiều khiển mờ. Trên cơ sở những kết quả thu ñược, tác giả sẽ chỉ ra khả năng ứng dụng của từng thuật toán trong chỉnh ñịnh tham số. Ngoài ra, ñề tài cũng tập trung vào phân tích và so sánh giữa các thuật toán ñể tìm ra mối liên hệ giữa chúng, ñồng thời có thể kết hợp các ưu ñiểm của chúng lại với nhau ñể tạo ra các thuật toán lai tốt hơn. ðó chính là mục ñích của ñề tài này. Vì ñây là một lĩnh vực khá rộng nên trong ñề tài này tác giả chỉ tập trung vào 5 thuật toán là: GA (Genetic Algorithm), DE (Differential Evolution), PSO (Particle Swarm Optimization), SFLA (Shuffled Frog Leaping Algorithm), BA (Bees Algorithm). Trang |1 Luận văn cao học 1.2. Công trình liên quan Lĩnh vực tối ưu hóa phỏng sinh học ñã phát triển rất nhanh chóng trong thời gian qua và ñã ñược ứng dụng thành công trong nhiều lĩnh vực. Có rất nhiều sách cũng như các bài báo viết về vấn ñề này. Hằng năm có rất nhiều hội nghị thảo luận về sự phát triển cũng như những ứng dụng mới của các thuật toán phỏng sinh học. Hầu hết các bài viết ñều tập trung vào các vấn ñề so sánh chất lượng giữa các thuật toán ( tốc ñộ hội tụ, thời gian thực thi,…) ([P7], [P16]. [P17], [P22], [P29]), ứng dụng của các thuật toán vào những trường hợp cụ thể như thiết kế bộ ñiều khiển mờ (chỉnh ñịnh tối ưu tham số, chỉnh ñịnh hệ luật,…) ([P4], [P6], [P8], [P9], [P10], [P11], [P12]), nhận dạng mờ ([P26], [P27]), phân bố tài nguyên (tối ưu mạng phân bố nước sử dụng các thuật toán ACO, SFLA) ([P19], [P24], [P28]), hoạch ñịnh ñường ñi cho robot trong môi trường ñộng sử dụng thuật toán ACO lai ([P14]),… Việc áp dụng thuật toán di truyền vào thiết kế bộ ñiều khiển mờ ñã phát triển rất mạnh trong hơn 10 năm qua. Hình 1.1 và hình 1.2 cho thấy xu hướng phát triển này ([P8], [P25]). Hình 1.1. Số lượng xuất bản mỗi năm Hình 1.2. Số trích dẫn mỗi năm Ngoài ra, gần ñây cũng có một số thuật toán ñược sử dụng ñể chỉnh ñịnh bộ ñiều khiển mờ như thuật toán PSO ([P12]), thuật toán BA ([P6]). 1.3. Phạm vi nghiên cứu Trang |2 Luận văn cao học Như ñã trình bày trong phần 1.2, việc nghiên cứu một cách có hệ thống về các thuật toán tối ưu hóa phỏng sinh học là chưa có. Vì vậy, trong ñề tài này tác giả sẽ tổng hợp, nghiên cứu, phân tích những ñiểm giống nhau và khác nhau của các thuật toán tối ưu phỏng sinh học ñể có cái nhìn một cách tổng quát về các thuật toán này. Phân tích khả năng của từng thuật toán ñến việc tìm kiếm lời giải tối ưu cả về tốc ñộ hội tụ và chất lượng nghiệm. Trên cơ sở phân tích khả năng của từng thuật toán ñến việc tìm kiếm lời giải tối ưu, tác giả ñề xuất cải tiến nâng cao chất lượng các thuật toán tối ưu phỏng sinh học bằng cách lai các thuật toán quen thuộc nhằm phát huy ưu ñiểm của các thuật toán riêng lẽ ñể ñược các thuật toán mới tốt hơn. ðể chứng minh cho những nhận ñịnh, các thuật toán này sẽ ñược ứng dụng vào chỉnh ñịnh tối ưu tham số bộ ñiều khiển mờ ổn ñịnh con lắc ngược xoay tại vị trí cân bằng. ðây là một ñối tượng khá phức tạp trong ñiều khiển mà việc chỉnh ñịnh các tham số bằng phương pháp thử sai rất khó ñể ñạt ñược yêu cầu về ổn ñịnh hay chất lượng ñáp ứng quá ñộ. 1.4. Tóm lược nội dung luận văn Luận văn bao gồm 5 chương với nội dung như sau: Chương 1 khái quát về sự phát triển của các thuật toán tối ưu hóa phỏng sinh học, mục ñích cũng như phạm vi nghiên cứu của luận văn. Chương 2 trình bày lý thuyết của một số thuật toán tối ưu hóa phỏng sinh học bao gồm các thuật toán phỏng theo sự tiến hóa như GA, DE và các thuật toán phỏng theo trí tuệ bầy ñàn như PSO, SFLA và BA. Chương 3 phân tích những ñiểm giống nhau và khác nhau giữa các thuật toán, ñề xuất lai ghép giữa các thuật toán ñể ñược thuật mới tốt hơn. Chương 4 trình bày các kết quả ñạt ñược khi ứng dụng các thuật toán này vào chỉnh ñịnh tối ưu tham số bộ ñiều khiển mờ ổn ñịnh con lắc ngược xoay tại vị trí cân bằng. Chương 5 tóm tắt các kết quả ñạt ñược, chưa ñạt ñược và hướng phát triển của luận văn. Trang |3 Luận văn cao học Chương 2 Các Thuật Toán Tối Ưu Hóa Phỏng Sinh Học 2.1. Giới thiệu Các thuật toán tối ưu hóa phỏng sinh học là những phương pháp tìm kiếm ngẫu nhiên bắt chước sự tiến hóa sinh học trong tự nhiên và/hoặc hành vi xã hội của các loài vật. Hành vi của các loài vật này ñược hướng dẫn bởi quá trình học, thích nghi và tiến hóa. ðể phỏng theo hành vi của các loài vật này, những nhà nghiên cứu ñã phát triển các hệ thống tính toán ñể tìm kiếm lời giải nhanh hơn, ổn ñịnh hơn cho các bài toán tối ưu hóa phức tạp. Có thể chia các thuật toán tối ưu hóa phỏng sinh học thành hai nhóm: nhóm các thuật toán phỏng theo sự tiến hóa như GA, DE,… và nhóm các thuật toán phỏng theo trí tuệ bầy ñàn như PSO, SFLA, BA,… Chi tiết các thuật toán này ñược trình bày trong phần 2.2. ðể thuận tiện cho việc theo dõi các thuật toán, luận văn chỉ xét bài toán tìm cực tiểu của hàm mục tiêu f(x) với x ∈ Rd, d là số nghiệm cần tối ưu. Các ký hiệu ñược sử dụng xuyên suốt luận văn ñược tóm tắt như sau: X ik : vị trí của cá thể i tại vòng lặp thứ k. X ik +1 : vị trí của cá thể i tại vòng lặp thứ k+1. X : vị trí tốt nhất của cá thể thứ i. : vị trí tốt nhất của cá thể trong quần thể. X pi g Trang |4 Luận văn cao học X ik ( j) : Vi k : vận tốc của cá thể i tại vòng lặp thứ k. c : hệ số gia tốc. Dmax : w : vector j của cá thể i tại vòng lặp thứ k. kích thước tìm kiếm cục bộ theo mỗi chiều trong SFLA hoặc BA. trọng số quán tính. rand(.) : số ngẫu nhiên phân bố ñồng nhất giữa 0 và 1. pc : xác suất lai ghép. pm : xác suất ñột biến. G : số thế hệ. N : số cá thể trong quần thể. d : chiều của bài toán (số nghiệm cần tối ưu). m : số memeplexe trong SFLA hay số vị trí ñược chọn trong BA. e : số vị trí tốt nhất trong m vị trị ñược chọn. n2 : số lần cập nhật quanh e vị trí. n1 : số lần cập nhật quanh m-e vị trí. ||D|| : chuẩn của vector D. 2.2. Các thuật toán tối ưu hóa phỏng theo sự tiến hóa Các thuật toán tối ưu hóa phỏng theo sự tiến hóa (EA: Evolutionary Algorithms) là các phương pháp tìm kiếm phỏng theo sự chọn lọc tự nhiên và sự tồn tại của cá thể tốt nhất trong thế giới sinh học. EA khác với các kỹ thuật tối ưu hóa truyền thống ở chỗ chúng chỉ liên quan ñến việc tìm kiếm từ một quần thể các nghiệm chứ không phải là một ñiểm. Hình 2.1 cho thấy sơ ñồ khối cơ bản của một EA. Như có thể thấy, về cơ bản EA không sử dụng bất kỳ thông tin nào về hàm tối ưu, chẳng hạn sự liên tục, khả vi,…mà chỉ sử dụng giá trị của hàm ñể ñịnh hướng cho quá trình tìm lời giải tối ưu.([P18]). Trang |5 Luận văn cao học Hình 2.1 Sơ ñồ thuật toán phỏng theo sự tiến hóa EA là một thuật ngữ chung ñược sử dụng cho các thuật toán phỏng theo sự tiến hóa. Nhiều loại thuật toán này ñã ñược phát triển một cách ñộc lập. Bao gồm: • Thuật toán di truyền (GA: Genetic Algorithm) cơ bản ñược sử dụng ñể tìm kiếm trong không gian rời rạc. Trong thuật toán này, chọn lọc ñược thực hiện ngẫu nhiên dựa trên giá trị thích nghi; lai ghép ñược coi là quan trọng; ñột biến ñược thực hiện ngẫu nhiên và ñồng nhất trong mỗi nhiễm sắc thể. • Chiến lược tiến hóa (ES: Evolutionary Strategy) cơ bản ñược sử dụng ñể tìm kiếm trong không gian giá trị thực nhiều chiều. Trong thuật toán này, chọn lọc ñược thực hiện xác ñịnh dựa trên hạng của các cá thể theo giá trị thích nghi; chỉ có ñột biến ñược sử dụng và dựa trên phân bố chuẩn. • Lập trình tiến hóa (EP: Evolutionary Programming) cơ bản ñược sử dụng ñể tìm kiếm trong không gian giá trị thực nhiều chiều. Mặc dù thuật toán này giống với ES nhưng nó khác ở chỗ chọn lọc ñược thực hiện ngẫu nhiên; quá trình tiến hóa khác với ES. • Lập trình di truyền (GP: Genetic Programming) có thể ñược xem như sự mở rộng của GA, và cơ bản nó ñược sử dụng ñể tạo ra chương trình tự ñộng. Trong thuật toán này, nhiễm sắc thể ñược biểu diễn bởi cấu trúc cây tương ứng với chương trình giống LISP, mỗi giá trị thích nghi ñược ñánh giá bởi hành vi của chương trình tương ứng, ñột biến và lai ghép ñược ñịnh nghĩa thích hợp với nhiễm sắc thể cấu trúc cây. Trang |6 Luận văn cao học • Tiến hóa sai phân (DE: Differential Evolution) ñược sử dụng ñể tìm nghiệm tối ưu toàn cục trong không gian giá trị thực nhiều chiều. Ý tưởng quan trọng của DE là tạo ra vector thử. EA thường ñược xem là phương pháp tối ưu toàn cục mặc dù sự hội tụ ñến tối ưu toàn cục chỉ ñược bảo ñảm theo ý nghĩa thống kê. Tuy nhiên, một trong những sức mạnh của EA là chúng có thể thực hiện tốt ñối với các hàm có nhiều nghiệm tối ưu cục bộ. EA có khuynh hướng không bị mắc kẹt trong tối ưu cục bộ và có thể tìm ra nghiệm tối ưu toàn cục. EA thích hợp với nhiều bài toán tối ưu liên tục và tổ hợp, mặc dù mỗi thuật toán có một lĩnh vực ứng dụng, cụ thể: • GPs rất phù hợp với các bài toán yêu cầu xác ñịnh một hàm có thể biểu diễn dưới dạng hàm số. • ES, EPs và DE rất phù hợp ñể tối ưu hóa các hàm liên tục. • GAs rất phù hợp với các bài toán tối ưu tổ hợp (mặc dù ñôi khi có thể áp dụng cho bài toán tối ưu liên tục). EA ñã ñược áp dụng thành công trong nhiều bài toán tối ưu hóa như nối dây, lên kế hoạch, người bán hàng, xử lý ảnh/tín hiệu, thiết kế kỹ thuật, tối ưu tham số,… Trong luận văn này, tác giả chỉ giới hạn trình bày hai thuật toán EA là GA và DE. 2.2.1. Thuật toán di truyền (GA) 2.2.1.1. Giới thiệu Thuật toán di tryền ñược Holland giới thiệu lần ñầu tiên vào năm 1975, là giải thuật tìm kiếm lời giải tối ưu ngẫu nhiên phỏng theo sự tiến hóa của sinh vật trong tự nhiên. GA có một số ñiểm khác với các thuật toán tối ưu thông thường. Thứ nhất, GA tìm kiếm nhiều ñiểm cực trị cùng một lúc nên hạn chế bị mắc kẹt tại các cực trị cục bộ. Thứ hai, GA chỉ cần ñánh giá hàm mục tiêu ñể ñịnh hướng quá trình tìm kiếm lời giải tối ưu mà không cần bất kỳ thông tin nào của hàm như tính liên tục, khả vi,… Do ñó, GA có khả năng giải quyết tốt các bài toán tìm cực trị hàm phi tuyến, không khả vi, không liên tục,… Trang |7 Luận văn cao học GA ñược ứng dụng nhiều trong các lĩnh vực như: kỹ thuật thiết kế, hoạch ñịnh ñường ñi cho robot, hệ thống phân loại, hệ thống học, nhận dạng mẫu, huấn luyện mạng thần kinh, chỉnh ñịnh hệ mờ,… 2.2.1.2. Thuật toán GA là thuật toán dựa vào quần thể có 3 toán tử chính là: chọn lọc, lai ghép và ñột biến. ðể áp dụng GA giải bài toán tối ưu, trước hết phải mã hóa lời giải của bài toán thành chuỗi nhiễm sắc thể. Tùy theo cách mã hóa mà chuỗi nhiễm sắc thể có thể là chuỗi nhị phân, chuỗi số thập phân, chuỗi số thực. Cách mã hóa nhị phân cơ bản có khuyết ñiểm là không phù hợp ñể giải các bài toán tối ưu trong không gian liên tục, nhiều chiều và yêu cầu ñộ chính xác cao. Trong luận văn này, tác giả sử dụng mã hóa số thực ñể tiện so sánh với các thuật toán còn lại. Sau ñây là những ñặc ñiểm chính của 3 toán tử GA. Nguyên tắc cơ bản của chọn lọc là cá thể nào có ñộ thích nghi cao thì khả năng ñược chọn là lớn. Có nhiều phương pháp chọn lọc như: chọn lọc tỉ lệ, chọn lọc ñấu vòng, chọn lọc cắt, chọn lọc sắp hạng tuyến tính, chọn lọc sắp hạng lũy thừa,…([E2], [E11], [P20]). Lai ghép là phương thức trao ñổi thông tin giữa các cá thể (hay nhiễm sắc thể). Phép toán này kết hợp ñặc ñiểm của hai cá thể bố mẹ ñể tạo ra hai cá thể con với kỳ vọng cha mẹ tốt sẽ sinh ra con tốt hơn. Phép lai ghép không tác ñộng ñến tất cả các cá thể trong quần thể mà chỉ xảy ra giữa hai cá thể bố mẹ ñược chọn ngẫu nhiên với xác suất pc, gọi là xác suất lai ghép. Có nhiều phép lai ghép tùy thuộc vào cách mã hóa như lai ghép một ñiểm, lai ghép nhiều ñiểm, lai ghép ñều, lai ghép số học, lai ghép BLXα,…([E2], [E10], [E11]). Hai phương trình (2.1) và (2.2) miêu tả cách tạo ra các gen của cá thể con tương ứng với hai cách lai ghép số học và lai ghép BLX-α. Hình 2.2 mô tả cách tạo ra gen của các cá thể ứng với phép lai BLX-α. ðột biến có vai trò tăng sự ña dạng về cấu trúc trong quần thể, ngăn cho GA không hội tụ sớm vào lời giải tối ưu cục bộ. Nguyên tắc cơ bản của ñột biến là thay ñổi ngẫu nhiên chuỗi nhiễm sắc thể với xác suất ñột biến pm. Có nhiều phương pháp ñột biến Trang |8 Luận văn cao học như: ñột biến một ñiểm, ñột biến nhiều ñiểm, ñột biến ngẫu nhiên, ñột biến không ñồng nhất,… ([E2], [E10], [E11]). Với, X ck ( j ) = X pk 2 + c ( X pk1 ( j ) − X pk 2 ( j ) ) (2.1) X ck ( j ) = random ( X ck ( j ) , X ck ( j ) ) (2.2) X ck ( j ) = min ( X pk1 ( j ) , X pk 2 ( j ) ) − α X pk1 ( j ) − X pk 2 ( j ) X ck ( j ) = max ( X pk1 ( j ) , X pk 2 ( j ) ) + α X pk1 ( j ) − X pk 2 ( j ) Trong ñó, X ck ( j ) : gen thứ j của cá thể con thứ k. X pk 1 ( j ) , X pk 2 ( j ) : gen thứ j của cá thể cha, mẹ thứ k. random ( X ck ( j ) , X ck ( j ) ) : hàm tạo số ngẫu nhiên trong  X ck ( j ) , X ck ( j )  . α : hệ số gia tốc (giống hệ số c trong SFLA). Lưu ñồ giải thuật của GA ñược cho ở Hình 2.3, mã giả và chương trình xem ở phụ lục A1. X k c ( j) X pk 2 ( j ) X k c ( j) X pk1 ( j ) X ck ( j ) Hình 2.2 Sơ ñồ lai ghép BLX-α trong GA Trang |9 Luận văn cao học Bắt ñầu Khởi tạo: - Kích thước quần thể (N) - Xác suất lai ghép (pc) - Xác suất ñột biến (pm) Khởi tạo ngẫu nhiên quần thể có N cá thể ðánh giá ñộ thích nghi của từng cá thể Chọn N cá thể dựa vào ñộ thích nghi Tạo ra cá thể con từ cá thể cha mẹ bằng toán tử lai ghép ðột biến cá thể con bằng toán tử ñột biến Tiêu chuẩn hội tụ thỏa mãn ? Chưa Thỏa Xác ñịnh nghiệm tốt nhất Kết thúc Hình 2.3 Lưu ñồ giải thuật GA 2.2.2. Thuật toán tiến hóa sai phân (DE) 2.2.2.1. Giới thiệu Thuật toán tiến hóa sai phân (DE) lần ñầu tiên ñược giới thiệu bởi Price và Storn vào năm 1995. ðây là thuật toán tối ưu dựa vào quần thể với mã hóa số thực ñể tìm nghiệm tối ưu toàn cục. Ưu ñiểm của thuật toán DE là cấu trúc ñơn giản, bền vững và dễ sử dụng. Thuật toán DE ñược ứng dụng thành công trong nhiều lĩnh vực như tối ưu các hàm phi tuyến, thiết kế bộ lọc số, quá trình lên men…([E7], [P23]). 2.2.2.2. Thuật toán Giống như GA, DE có 3 toán tử chính là: chọn lọc, lai ghép và ñột biến. Tuy nhiên, sự khác nhau ở chỗ DE sử dụng thông tin về khoảng cách và hướng ñể tìm kiếm lời giải tối ưu trong khi GA sử dụng thông tin về giá trị hàm mục tiêu ñể ñịnh hướng quá trình T r a n g | 10 Luận văn cao học tìm kiếm. Phép ñột biến ñược thực hiện trước ñể tạo ra vector ñột biến bằng cách: tính hiệu hai vector ñược chọn ngẫu nhiên từ quần thể rồi nhân với một trọng số c, sau ñó cộng với một vector thứ ba ñược chọn ngẫu nhiên từ quần thể khác với hai vector ñã chọn như phương trình (2.3). Vi k = X rk0 + c ( X rk1 − X rk2 ) (2.3) Trong ñó, X rk0 , X rk1 , X rk2 : các vector ñược chọn ngẫu nhiên khác nhau ñôi một. : vector ñột biến i ở thế hệ thứ k. Vi k Sau khi ñột biến, toán tử lai ghép ñược áp dụng giữa vector ñích X và vector ñột biến V sử dụng phương trình (2.4) ñể có ñược vector thử U. U = U k i k i ( j) Trong ñó, U ik  Vi k ( j ) = k  X i ( j ) nếu j c hoặc j = rnbr ( i ) (2.4) ngược lại : vector thử i tại vòng lặp thứ k. U ik ( j ) , Vi k ( j ) , X ik ( j ) pc ( rand ( 0,1) ≤ p ) : phần tử thứ j của các vector Ui ,Vi , Xi. : xác suất lai ghép có giá trị trong khoảng [0,1]. randj(0,1): hàm ngẫu nhiên phân bố ñều trong khoảng [0,1]. rnbr(i) : hàm tạo ra các chỉ số ngẫu nhiên từ 1 ñến d. Cuối cùng phép chọn lọc ñược sử dụng ñể chọn ra vector tốt nhất giữa vector ñích X và vector thử U cho thế hệ tiếp theo như Hình (2.4). X k +1 i U ik = k  X i nếu f (U ik ) ≤ f ( X ik ) (2.5) ngược lại Trong ñó, f(.) : là hàm mục tiêu cần tìm nghiệm cực tiểu. T r a n g | 11 Luận văn cao học Lưu ñồ giải thuật của DE ñược cho ở Hình 2.5, mã giả và chương trình xem ở phụ lục A2. X rk1 − X rk2 X rk2 X k r1 X F . ( X rk1 − X rk2 ) k r0 Vi k X ik +1 X ik Hình 2.4 Quá trình cập nhật vector mới Bắt ñầu Khởi tạo: - Kích thước quần thể (N) - Xác suất lai ghép (pc) - Hệ số gia tốc (c) Khởi tạo ngẫu nhiên quần thể có N cá thể ðánh giá ñộ thích nghi của từng cá thể Chọn 3 vector khác nhau từng ñôi một Tạo vector thử V (2.3) Lai ghép X và V → U (2.4) Nếu f(U) > f(X) → X = U Tiêu chuẩn hội tụ thỏa mãn ? Chưa Thỏa Xác ñịnh nghiệm tốt nhất Kết thúc Hình 2.5 Lưu ñồ giải thuật DE T r a n g | 12 Luận văn cao học 2.3. Các thuật toán tối ưu hóa phỏng theo trí tuệ bầy ñàn Trí tuệ bầy ñàn (SI: Swarm Intelligence) là một kỹ thuật trí tuệ nhân tạo tập trung vào nghiên cứu hành vi tập hợp của một hệ thống phân bố tạo bởi một quần thể các cá thể tương tác cục bộ với nhau và với môi trường. Mặc dù không có một tiêu chuẩn ñiển hình nào chỉ ra hành vi của các cá thể nhưng sự tương tác cục bộ giữa các cá thể dẫn ñến xuất hiện một mô hình toàn cục. Ví dụ về các hệ thống kiểu này có thể ñược tìm thấy rất nhiều trong tự nhiên bao gồm ñàn kiến, bầy chim, ong mật, vi khuẩn,…Các thuật toán giống bầy ñàn, chẳng hạn thuật toán tối ưu bầy kiến (ACO: Ant Colony Optimization), tối ưu bầy ñàn (PSO: Particle Swarm Optimization), thuật toán ếch nhảy (SFLA: Shuffled Frog Leaping Algorithm), thuật toán con ong (Bees Algorithm),... ñã ñược áp dụng thành công ñể giải các bài toán tối ưu hóa trong kỹ thuật và viễn thông. Các mô hình SI có nhiều ñặc ñiểm giống với EA. Giống EA, các mô hình SI dựa vào quần thể. Hệ thống ñược khởi tạo bởi một quần thể các cá thể (nghĩa là các nghiệm tiềm ẩn). Các cá thể này sau ñó ñược xử lý qua nhiều thế hệ bằng cách bắt chước hành vi xã hội của các loài côn trùng hoặc loài vật trong nổ lực tìm ra lời giải tối ưu. Không giống như EA, các mô hình SI không sử dụng các toán tử tiến hóa như lai ghép và ñột biến. Nghiệm tiềm ẩn chỉ ‘bay’ qua không gian tìm kiếm bằng cách tự chỉnh sửa theo mối quan hệ của nó với các cá thể khác trong quần thể và môi trường. ([E3], [E6]). Trong luận văn này, tác giả chỉ giới hạn trình bày ba thuật toán SI là PSO, SFLA và BA. 2.3.1. Thuật toán tối ưu bầy ñàn (PSO) 2.3.1.1. Giới thiệu PSO là một kỹ thuật tối ưu hóa ngẫu nhiên dựa vào quần thể ñược phát triển bởi Dr. Eberhart và Dr. Kennedy vào năm 1995, phỏng theo hành vi xã hội của bầy chim hay ñàn cá. PSO có nhiều ñiểm tương ñồng so với các kỹ thuật phỏng theo sự tiến hóa như GA. T r a n g | 13