Đề tài Tối ưu hóa theo thuật toán di truyền

OÄ GIAÙO DUÏC VAØ ÑAØO TAÏO COÄNG HOAØ XAÕ HOÄI CHUÛ NGHÓA VIEÄT NAM TRÖÔØNG ÑAÏI HOÏC BAÙCH KHOA ðoäc laäp –Töï do-Haïnh Phuùc Thaønh phoá Hoà Chí Minh Khoa: Hoaù Boä moân :Coâng ngheä thöïc phaåm ÑOÀ AÙN MOÂN HOÏC :“DAMH COÂNG NGHEÄ THÖÏC PHAÅM” MAÕ SOÁ: 603136 Hoï vaø teân sinh vieân: Nguyễn Hữu Chính MSSV: 60300289 Lôùp :HCO3TP01 Ngaønh:Thöïc phaåm 1.Ñaàu ñeà ñoà aùn :Tổng quan tài liệu về tối ưu hóa theo thuật toán di truyền 2.Nhieäm vuï : • Tổng quan về lý thuyết • Phần mềm sử dụng • Thiết kế thực nghiệm 3.Ngaøy giao ñoà aùn :6/2/2007 4.Ngaøy hoaøn thaønh ñoà aùn : 27/6/2007 5.Ngaøy baûo veä hay chaám: 28/6/2007 CHUÛ NHIEÄM BOÄ MOÂN Ngaøy thaùng naêm (Kyù vaø ghi roõ hoï teân ) (Kyù vaø ghi roõ hoï teân) Tối ưu hóa theo thuật toán di truyền GVHD : PhD Nguyễn Hoàng Dũng 3 NHAÄN XEÙT ÑOÀ AÙN Caùn boä höôùng daãn .Nhaän xeùt: ________________________________________ ________________ ________________________________________________ ________________ ________________________________________________ ________________ ________________________________________________ ________________ ________________________________________________ Ñieåm: __________ Chöõ kyù: ___________________ Caùn boä chaám hay Hoäi ñoàng baûo veä.Nhaän xeùt : __________________________ ________________ ________________________________________________ ________________ ________________________________________________ ________________ ________________________________________________ ________________ ________________________________________________ Ñieåm : __________ Chöõ kyù: ___________________ Tối ưu hóa theo thuật toán di truyền GVHD : PhD Nguyễn Hoàng Dũng 4 Danh mục các hình Hình 1 : Nguyên lý của phương pháp leo ñồi……………………………………….10 Hình 2 : ðồ thị của hàm (1)…………………………………………………………11 Hình 3: Thuật toán di truyền………………………………………………………...13 Hình 4 : Mã nhị phân………………………………………………………………..14 Hình 5: Mã số thực………………………………………………………………….15 Hình 6: Mã dạng cây………………………………………….…………………….16 Hình 7:Mã hoán vị ………………………………………………………………….16 Hình 8 : Roulette wheel……………………………………………………………..17 Hình 9: Situation before ranking (graph of fitnesses) ………………………………18 Hình 10: Situation after ranking (graph of order numbers) ………………………...18 Hình 11 : Lai một vị trí ñối với mã nhị phân………………………………………..20 Hình 12: Lai một vị trí ñối với mã số thực………………………………………….20 Hình 13 : Lai một vị trí ñối với mã dạng cây………………………………………..21 Hình 14: Lai hai vị trí……………………………………………………………….21 . Hình 15: Lai hai vị trí ñối với mã số thực…………………………………………...21 Hình 16: Lai ñều…………………………………………………………………….22 Hình 17: Lai số học…………………………………………………………………22 Hình 18: ðột biến …………………………………………………………………..23 Hình 19: ðột biến nhẹ………………………………………………………………23 Hình 20: Phần mềm Matlab…………………………………………………………26 Hình 21 : Gatool…………………………………………………………………….27 Hình 22: Phần mềm Design-Expert 7.1.2 ………………………………………….30 Hình 23:Kết quả thu ñược lần 1 khi chạy mục tiêu 1 ………………………………34 Hình 24: Kết quả thu ñược lần 1 khi chạy mục tiêu 2………………………………35 Hình 25: Kết quả thu ñược lần 1 khi chạy mục tiêu 3 ……………………………...35 Tối ưu hóa theo thuật toán di truyền GVHD : PhD Nguyễn Hoàng Dũng 5 Hình 26: Pareto front………………………………………………………………. 37 Mục lục 1.TỔNG QUAN VỀ TỐI ƯU HÓA………………………………………………..7 1.1.KHÁI QUÁT……………………………………………………………………..7 1.2.PHÂN LOẠI……………………………………………………………………...7 1.3. TỐI ƯU HÓA CỤC BỘ VÀ TỐI ƯU HÓA TOÀN CỤC………………………8 1.3.1 Phương pháp truyền thống……………………………………………………...8 1.3.2 Phương pháp leo ñồi……………………………………………………………9 2.THUẬT TOÁN DI TRUYỀN……………………………………………..…….12 2.1.LÝ THUYẾT……………………………………………………………...……12 2.1.1KHỞI TẠO QUẦN THỂ BAN ðẦU …………………………..……………13 2.1.2.MÃ HÓA……………………………………………………………………...14 2.1.2.1.Mã nhị phân ………………………………………………………………...14 2.1.2.2 .Mã số thực………………………………………………………………….15 2.1.2.3.Mã dạng cây ………………………………………………………………...16 2.1.3.LỰA CHỌN ………………………………………………………………16 2.1.3.1.Roulette selection……………………………………………………………17 2.1.3.2.Rank selection……………………………………………………………….18 2.1.3.3Elitism………………………………………………………………………..19 2.1.4.PHÉP LAI ……………………………...…………………………………….19 Tối ưu hóa theo thuật toán di truyền GVHD : PhD Nguyễn Hoàng Dũng 6 2.1.4.1.Lai một vị trí………………………………………………………………...19 2.1.4.2.Lai hai vị trí …………………………………………………………………20 2.1.4.3. Lai ñều ……………………………………………………………………..21 2.1.4.4.Lai số học …………………………………………………………………...22 2.1.5.ðỘT BIẾN ……………………...……………………………………………22 2.1.5.1.ðột biến nhẹ………………………………………………………………... 23 2.1.5.2.ðột biến biên ………………………………………………………………..24 2.1.5.3.ðột biến ñồng dạng …………………………………………………………24 2.2PHẦN MỀM ÁP DỤNG………………………………………………………..24 2.3.ỨNG DỤNG……………………………………………………………………27 3.THIẾT KẾ THỰC NGHIỆM…………………………………………………...28 3.1.BÀI TOÁN……………………………………………………………………...28 3.2.CHẠY CHƯƠNG TRÌNH………………………………………………………35 4..KẾT LUẬN………………………………………………………………………37 5.TÀI LIỆU THAM KHẢO……………………………………………………….37 PHỤ LỤC Tối ưu hóa theo thuật toán di truyền GVHD : PhD Nguyễn Hoàng Dũng 7 1.TỔNG QUAN VỀ TỐI ƯU HÓA. 1.1.KHÁI QUÁT Tối ưu hóa (optimization) là quá trình tìm cực trị một ñại lượng nào ñó của ñối tượng thiết kế dưới dạng hàm số và phải thỏa mãn các ràng buộc của bài toán. Cho nên người ta hiểu lời giải tối ưu hay một bản thiết kế tối ưu là lời giải tốt nhất hay bản thiêt kế hay nhất. Trong kỹ thuật, người ta dùng nhiều phương pháp tối ưu hóa khác nhau ñể tìm lời giải hay nhất. Theo cách nhìn hiện ñại, lý thuyết tối ưu hóa bao gồm tập hợp các kết quả của toán học cơ sở kết hợp với các phương pháp số dùng ñể tìm phương án tốt nhất từ tập hợp phương án theo một thuật giải nhất ñịnh. Hầu hết các bài toán kỹ thuật ñều có nhiều biến cho nên việc tính toán ñể tối ưu hóa rất phức tạp ñòi hỏi rất nhiều thời gian và trong nhiều trường hợp không thể giải ñược bằng phương pháp số thông thường mà thiếu ñi sự hỗ trợ của máy tính. Lý thuyết tối ưu hóa ñược phát triển mạnh do sự xuất hiện của máy tính với tốc ñộ xử lý nhanh, ñảm bảo thực hiện các phương pháp số khác nhau ñể tối ưu hóa. Hầu hết các phương pháp tối ưu thực chất là bất biến và có thể giải nhiều thiết kế khác nhau. Hiện nay ñã có hàng chục phương pháp số tối ưu hóa, thể hiện dưới dạng thuật toán tiêu chuẩn ñược xây dựng và ngày càng hoàn thiện. Cho nên nhiệm vụ của người thiết kế là chọn phương pháp và tập hợp chương trình sao cho ñúng và hợp lý. 1.2.PHÂN LOẠI Các phương pháp tối ưu hóa ñược phân ra thành nhiều nhóm mà mỗi nhóm lại có phương pháp khác nhau. Chúng có thể ñược chia thành các nhóm sau ñây: • Phương pháp tối ưu hóa bằng thống kê • Phương pháp tối ưu bằng quy hoạch toán học • Phương pháp tối ưu hóa liên tục • Phương pháp tối ưu hóa gián ñoạn • Phương pháp tối ưu hóa không có ràng buộc
Phương pháp tối ưu hóa thống kê ñược kể ñến là phương pháp lý thuyết trò chơi và phương pháp qui hoạch thực nghiệm.
Phương pháp tối ưu hóa bằng quy hoạch toán học ñược chia thành hai nhóm nhỏ. Phương pháp thứ nhất là phương pháp phân tích bao gồm những phương pháp phân tích vi phân, phương pháp phân tích biến phân, nguyên tắc max min..nhóm thứ hai là những phương pháp phân tích số bao gồm phương pháp qui hoạch tuyến tính, phương pháp qui hoạch phi tuyến, phương pháp qui hoạch ñộng, phương pháp qui hoạch ngẫu nhiên… Tối ưu hóa theo thuật toán di truyền GVHD : PhD Nguyễn Hoàng Dũng 8 Trong quy hoạch tuyến tính thông dụng nhất là phương pháp ñơn hình và phương pháp ñơn hình cải biên. Trong quy hoạch phi tuyến có thể kể tới là phương pháp quy hoạch lồi, phương pháp quy hoạch bình phương….
Các phương pháp tối ưu hóa liên tục ñược phân lọa theo dấu hiệu như: sự tồn tại của ràng buộc kỹ thuật, dạng cực trị, ñặc tính của phương pháp giải o Theo dạng của hàm mục tiêu, phương pháp tối ưu hóa liên tục ñược chia ra: phương pháp tuyến tính, phương pháp lồi, phương pháp bậc hai và phương pháp phi tuyến. o Theo sự tồn tại của ràng buộc kỹ thuật phương pháp tối ưu hóa liên tục ñược chia ra: không có ràng buộc kỹ thuật và có ràng buộc kỹ thuật. Lọai không có ràng buộc kỹ thuật có thể giải bằng phương pháp bậc không, bậc nhất và bậc hai. Loại có ràng buộc kỹ thuật có thể giải bằng phương pháp hàm phạt và hàm chắn. o Theo dạng cực trị các phương pháp tối ưu hóa chia hai loại : tối ưu hóa cục bộ và tối ưu hóa toàn bộ. o Theo phương pháp xác ñịnh ñạo hàm thì có hai phương pháp : phương pháp phân tích và phương pháp số. Nếu theo ñạo hàm thì chia làm ba loại : bậc không, bậc nhất và bậc hai.
Phương pháp tối ưu hóa gián ñoạn dùng trong trường hợp biên số và hàm mục tiêu thay ñổi một cách gián ñoạn. Các phương pháp này áp dụng rất hiệu quả ñể giải các bài toán ñặc trưng như bài toán vận tải, bài toán tối ưu hóa số nguyên hoặc bài toán dạng tổ hợp.
Phương pháp tối ưu hóa gián ñoạn có thể kể ñến như : phương pháp cắt ñứt, phương pháp nhánh cây, phương pháp cộng ñược, phân tích quy hoạch ñộng và phương pháp tìm kiếm ngẫu nhiên.
Các phương pháp tối ưu hóa cục bộ không có ràng buộc kỹ thuật tùy theo bậc ñạo hàm sẽ ñược phân ra bậc không, bậc nhất và bậc hai. • Phương pháp bậc hai nổi tiếng là phương pháp Newton. • Phương pháp bậc nhất có mấy phương pháp chính như phương pháp gradient, phương pháp dốc ñứng, phương pháp metric thay ñổi. Loại bậc không một biến bao gồm: phương pháp chia ñôi, phương pháp mặt cắt vàng, phương pháp Phibônasi, phương pháp nội suy bậc hai…. Tối ưu hóa theo thuật toán di truyền GVHD : PhD Nguyễn Hoàng Dũng 9  Còn loại bậc không nhiều biến có thể kể ñến phương pháp tọa ñộ, phương pháp Rosenbrock, phương pháp Hook-Jeeves, phương pháp tìm kiếm ngẫu nhiên, phương pháp ñơn hình Neld- Mead, phương pháp Powell… nhất có mấy phương pháp chính như phương pháp gradien,ược, phân tích quy hoạch ñộng và phương pháp tìm kiếm ngẫu nhiên. 1.3. TỐI ƯU HÓA CỤC BỘ VÀ TỐI ƯU HÓA TOÀN CỤC 1.3.1 Phương pháp truyền thống Phương pháp truyền thống hay còn gọi là phương pháp tối ưu hóa tiêu chuẩn (standard algorithms). ða số là các phương pháp tối ưu hóa cục bộ. Xem xét sơ qua một vài phương pháp:
Phương pháp liệt kê: Duyệt tất cả các ñiểm nằm trong vùng khảo sát ñể tìm ra ñiểm cực trị của nó. Phương pháp này không thích hợp khi dữ liệu ñầu quá lớn lớn tức là không gian tìm kiếm quá lớn.
Phương pháp giải tích: Một số phương pháp dạng này như phương pháp steepest descent, phương pháp Quasi-Newton, phương pháp Gauss-Newton, phương pháp Levenberg-Marquardt … Tìm ñiểm cực trị bằng cách giải tập các phương trình khi cho Gradient bằng 0. ðể xét ñược Gradient phải tính ñạo hàm của hàm số. ðiều này không giải quyết ñược trong trường hợp hàm số không liên tục hoặc không có ñạo hàm. ðối với bài toán có ñiểm yên ngựa thì phương pháp này không còn hiệu quả nữa. 1.3.2 Phương pháp leo ñồi ðây là phương pháp nổi tiếng, mở ñầu cho việc giải bài toán tối ưu hóa toàn cục. Hầu hết các phương pháp và các thuật toán ñể giả bài toán tối ưu hóa toàn cục sau này ñều dựa trên phương pháp này. Ta tưởng tượng rằng không gian tìm kiếm là một vùng ñất gập ghềnh (landscape) với nhiều ngọn ñồi cao thấp khác nhau. Trong ñó, ngọn ñồi cao nhất sẽ có lời giải tốt nhất và vị trí có ngọn ñồi cao nhất sẽ càng gần với lời giải tốt nhất. Tìm kiếm leo ñồi có nghĩa là chúng ta phải phát sinh lời giải sao cho càng về sau các lời giải càng tiến ñến gần lời giải tốt nhất. Thao tác này cũng giống như thao tác leo ñồi vậy. Tối ưu hóa theo thuật toán di truyền GVHD : PhD Nguyễn Hoàng Dũng 10 Hình 1 : Nguyên lý của phương pháp leo ñồi Tìm kiếm leo ñồi bắt ñầu bằng cách chọn vị trí bắt ñầu trong không gian tìm kiếm ( hình 1). Sau ñó quyết ñịnh xem hướng leo lên nhanh nhất, ñánh giá lại hướng leo lên (xem thử chỗ nào ít dốc hơn ñể leo lên nhanh hơn). Tiếp tục cho ñến khi tìm ñược một vị trí trong không gian lời giải mà tất cả những ñiểm xung quanh ñều nằm ở dưới. Tối ưu hóa theo thuật toán di truyền GVHD : PhD Nguyễn Hoàng Dũng 11 Kiểu giải quyết này gặp vấn ñề cơ bản là vùng ñất chúng ta có nhiều ngọn ñồi nhỏ bên cạnh thì có khả năng chúng ta bị kẹt ở những ngọn ñồi nhỏ. Và như vậy, chúng ta chỉ tìm ñược cực ñại cục bộ mà thôi. Hầu hết các phương pháp tối ưu khác ñều hoạt ñộng dựa theo cách này và chỉ khác nhau ñơn giản ở chỗ anh ta quyết ñịnh hướng leo lên như thế nào, chọn một bước ñể tiến lên tiếp tục là bao nhiêu và có nên sử dụng những thông tin ñã ñược tích lũy trước ñó không. Xem xét bài toán sau:
         (1)                ;   ! " # Cực ñại toàn cục
  = 1 khi   = (0.5, 0.5) Thật không may, cuộc sống không may mắn như vậy. chúng ta hãy xem hình 2. Hình 2 : ðồ thị của hàm (1) ðiểm cực ñại là một ñỉnh trung tâm nhỏ ñược chỉ bởi mũi tên, xung quanh nó là những vòng tròn ñồng tâm cực ñại thứ hai. Cách duy nhất mà người leo ñồi có thể tìm thấy cực ñại thực sự nếu như anh lính nhảy dù rớt xuống một nơi nào ñó trên vùng dốc của cực ñại trung tâm mà thôi. Việc leo ñồi từ các vùng khác chỉ dẫn anh ta tới những cực ñại thứ hai của những vòng tròn ñồng tâm khác. ðiểm trung tân này chỉ chiếm khoảng 1% trong toàn bộ không gian tìm kiếm ( 0$   $ ). Tối ưu hóa theo thuật toán di truyền GVHD : PhD Nguyễn Hoàng Dũng 12 Với khả năng xảy ra cực ñại toàn cục là 1%, bạn phải chạy chương trình tìm liếm leo ñồi trung bình là 100 lần trước khi tìm ra cực ñại trung tâm. Khi phải ñối mặt với bài toán tối ưu hóa với không gian tìm kiếm lớn hoặc ñiểm cực ñại nằm ở một phần rất nhỏ của không gian tìm kiếm thì giải thuật leo ñồi gặp nhiều khó khăn. Và rõ ràng thuật toàn leo ñồi là chiến lược tối ưu hóa cục bộ trong khi hình 2 bắt ta phải tìm một cực ñại toàn cục. Vậy chúng ta giải quyết như thế nào ñây? ðể giải bài toán như hình 2 thì thuật toán leo ñồi lặp lại (iterated hill climing). Nghĩa là bạn có thể chạy thuật toán leo ñồi lặp lại nhiều lần, mỗi lần bắt ñầu từ một ñiểm ngẫu nhiên trong không gian tìm kiếm. Mỗi lần như vậy bạn hãy ghi nhớ các cực ñại tìm ñược. Cứ tiếp tục như vậy cho ñến khi bạn tìm thấy cái lớn nhất trong trong tất cả các cực ñại mà bạn tìm ñược. Lúc này thì bạn ñã giải ñược bài toán tối ưu hóa toàn cục. ðây là tư tưởng sơ khởi ban ñầu của thuật toán di truyền. Càng về sau, người ta càng hoàn thiện hơn ý tưởng của phương pháp này dẫn ñến sự ra ñời hoàn chỉnh các phương pháp, nguyên lý dùng trong thuật toán di truyền. Thuật toán di truyền có thể giải mọi bài toán tối ưu hóa không cần biết ñạo hàm có xác ñịnh hay không, hàm số có liên tục hay không và trong không gian tìm kiếm vô cùng lớn. 2.THUẬT TOÁN DI TRUYỀN 2.1.LÝ THUYẾT Thuật giải di truyền-theo như nhà bác học Charles Darwin trong cuốn sách Natural Selection and Survival of the Fittest-cũng như các thuật toán tiến hóa nói chung, hình thành dựa trên quan niệm cho rằng, quá trình tiến hóa 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 hóa thể hiện tính tối ưu ở chỗ: thế hệ sau bao giờ cũng tốt hơn thế hệ trước. Tiến hóa tự nhiên ñược duy trì nhờ hai quá trình cơ bản: sinh sản và chọn lọc tự nhiên. Cá thể nào phát triển hơn, thích nghi hơn với môi trường sẽ tồn tại, ngược lại, cá thể ñó sẽ bị ñào thải. Các thuật toán tiến hóa, tuy có những ñiểm khác biệt, nhưng ñều mô phỏng bốn quá trình cơ bản: lai ghép, ñột biến, sinh sản và chọn lọc tự nhiên. Thuật toán di truyền lần ñầu ñược ñưa ra bởi John Holland, thuộc trường ñại học Michigan vào những năm 1970. Ông ta ñặc biệt quan tâm tới việc ứng dụng chọn lọc tự nhiên vào nghiên cứu máy móc và phát triển kỹ thuật cho phép chương trình máy tính có thể mô phỏng quy trình tiến hóa. Ban ñầu nó ñược gọi là dự án tái sản xuất (reproductive plans), nhưng sau ñó ñược biết ñến phổ biến với cái tên thuật toán di truyền (genetic algorithms). Trong hơn 30 năm qua, ñã có nhiều nghiên cứu trong giải thuật cũng như ứng dụng ñược công bố. Tối ưu hóa theo thuật toán di truyền GVHD : PhD Nguyễn Hoàng Dũng 13 Hình 3: Thuật toán di truyền 2.1.1KHỞI TẠO QUẦN THỂ BAN ðẦU Tối ưu hóa theo thuật toán di truyền GVHD : PhD Nguyễn Hoàng Dũng 14 Chọn kích thước quần thể thích hợp cho thuật giải di truyền luôn luôn cần thiết nhưng lại là một nhiệm vụ khó khăn ñối với người sử dụng. Một mặt, nếu kích thước quần thể quá nhỏ, thuật giải di truyền sẽ hội tụ rất nhanh và do ñó lời giải tối ưu sẽ là không tối ưu. Mặt khác, nếu kích thước quần thể quá lớn thì tốn nhiều tài nguyên máy tính và thậm chí bị ngăn cản. Theo một cuộc ñiều tra lý thuyết về xác ñịnh kích thước quần thể tối ưu, Goldberg cho rằng kích thước quần thể ñược xác ñịnh theo công thức pop=1.65 x 20.21*length và ñề nghị rằng kích thước này nên là 130, 557, 10244 cho chuỗi dài 30, 40, 50, 60 . Smith ñề nghị một thuật giải ñể xác ñịnh kích thước quần thể ban ñầu từ quần thể thích nghi……. Tóm lại, việc xác ñịnh kích thước quần thể ban ñầu là hoàn toàn ngẫu nhiên và phụ thuộc vào từng bài toán cụ thể. 2.1.2.MÃ HÓA GAs bắt ñầu với quần thể, tập của nhiều cá thể (nhiễm sắc thể). Sự mã hóa các biến phụ thuộc vào từng bài toán. Thông thường có các dạng mã sau: mã nhị phân, mã Gray, mã số thực và mã dạng cây. 2.1.2.1.Mã nhị phân Mã nhị phân ñược biểu diễn bằng các chuỗi 0 và 1. Quy tắc biểu diễn gen qua chuỗi nhị phân : Chọn chuỗi nhị phân ngắn nhất nhưng ñủ thể hiện ñược tất cả kiểu gen. chromozome A 10001010001111101010111 chromozome B 00000001000000011110000 Hình 4 : Mã nhị phân Giả sử muốn tối ưu hàm n biến f(x1,x2,x3,.,xn),trong ñó mỗi biến xi thụộc miền D=[ai ,bi] là tập con của tập số thực R và yêu cầu chính xác là k chữ số thập phân cho mỗi giá trị của biến xi. ðể ñạt ñược ñộ chính xác như vậy miền [ ai,bi ] ñược phân cắt thành (bi- ai)*10k miền con bằng nhau. Gọi mi là số nguyên nhỏ nhất sao cho: Tối ưu hóa theo thuật toán di truyền GVHD : PhD Nguyễn Hoàng Dũng 15 (bi- ai)*10 k ≤ 2 mi - 1. Như vậy mỗi biến xi thuộc [ ai,bi ] ñược biểu diễn bằng một chuỗi nhị phân có chiều dài mi. Phép ánh xạ biến nhị phân thành biến thực xi ñược tính theo công thức: xi = ai + decimal(string2)* 12 − − im ii ab trong ñó decimal (string2) biểu diễn giá trị thập phân của chuỗi nhị phân string2 . Bây giờ mỗi nhiễm sắc thể (là một lời giải) ñược biểu diễn bằng chuỗi nhị phân có chiều dài m = ∑ = n i i m 1 .Với m1 là bit ñầu tiên biểu diễn các giá trị trong khoảng [a1,b1], m2 là bit kế tiếp biểu diễn giá trị trong khoảng [a2,b2] và nhóm mn bit cuối cùng biểu diễn trong khoảng [an,bn] . Biểu diễn bằng chuỗi nhị phân có thể tạo ra nhiều nhiễm sắc thể thậm chí với số alen ít. Nói cách khác, việc mã hóa này không tự nhiên ñối với vài bài toán và kết quả ñúng ñạt ñược sau khi mã hóa hoặc ñột biến. 2.1.2.2 .Mã số thực ðối với những bài toán có nhiều tham số, việc biểu diễn gen bằng chuỗi số nhị phân ñôi lúc sẽ làm cho kiểu gen của cá thể trở nên quá phức tạp. Dẫn ñến việc thi hành cách thao tác trên gen trở nên kém hiệu quả. Khi ñó, người ta sẽ chọn biểu diễn kiểu gen dưới dạng một chuỗi số thực. Tuy nhiên, chọn biểu diễn kiển gen bằng chuỗi số thực, bạn cần lưu ý quy tắc sau : Quy tắc biểu diễn kiểu gen bằng chuỗi số thực : Biểu diễn kiểu gen bằng số thực phải ñảm bảo tiết kiệm không gian ñối với từng thành phần gen. Mục ñích chính là ñể mở rộng không gian tìm kiếm của GA gần với không gian thực của bài toán hơn. Trong mã số thực, mỗi nhiễm sắc thể là một chuỗi các các giá trị. Các giá trị có thể là bất cứ thứ gì liên quan ñến vấn ñề ñang xét, bao gồm số thực, kí tự và thậm chí là các ñối tượng. Chromosome A 1.2324 5.3243 0.4556 2.3293 2.4545 Chromosome B ABDJEIFJDHDIERJFDLDFLFEGT Chromosome C (back), (back), (right), (forward), (left) Tối ưu hóa theo thuật toán di truy Trong ñó A ñại diện cho tác vụ ri Việc mã hóa này rất cần thiết trong việc tạo ra các ñột biến v toán. 2.1.2.3.Mã dạng cây Mã dạng cây ñược sử dụng chủ yếu cho các ch thức. Cấu trúc cây thường ñư bài toán cũng có dạng cây và do ñó vi Trong mã dạng cây, mỗi nhiễm sắc thể l như hàm hoặc lệnh của ngôn ngữ ch Chromosome A ( + x ( / 5 y ) ) Hình 6: 2.1.2.4.Mã hoán vị Mã hoán vị ñược sử dụng trong các bài toán trình t bài toán “Người du lịch” (travelling salesman problem), trong ñó m là một chuỗi các số tự nhiên. Chromosome A Chromosome B Hình 2.1.3.LỰA CHỌN ền GVHD : PhD Nguyễn Hình 5: Mã số thực êng, B ñại diện cho một cái khác …… à lai tạo cụ thể cho b ương trình tiến hóa hoặc các biểu ợc dụng trong trường hợp bản thân cấu trúc dữ liệu của ệc ñột biến và lai ñược thực hiện khá dễ d à một cây của nhiều ñối tượng , chẳng hạn ương trình. Chromosome B ( do_until step wall ) Mã dạng cây ự (ordering problems) như trong ỗi nhi 1 5 3 2 6 4 7 9 8 8 5 6 7 2 3 1 4 9 7:Mã hoán vị Hoàng Dũng 16 ài àng. ễm sắc thể Tối ưu hóa theo thuật toán di truy Nhiễm sắc thể ñược lựa chọn t tạo và ñột biến. Vấn ñề ở ñây là l hóa của Darwin thì những cha m nhiều phương pháp ñể lựa ch xe rulet (Roulette wheel selection), l chọn theo vòng (Tournament selection), l selection), lựa chọn xếp hạng (Rank selection) và m (Elitism). Sau ñây là một số 2.1.3.1.Roulette selection Hình 8 : R Tính ñộ thích nghi eval(vi) là kích thước của quần thể eval(vi) = ∑ − = sizepop i i i vf vf 1 )( )( Tìm tổng giá trị thích nghi F cho toàn qu F = ∑ − = sizepop i ivf 1 )( Tìm xác suất chọn pi cho m pi = ∑ − = sizepop i i i veval veval 1 )( )( Tìm xác suất tích lũy qi cho m ền GVHD : PhD Nguyễn ừ quần thể ñể trở thành cha mẹ cho các phép toán lai ựa chọn nhiễm sắc thể như thế nào. Theo thuy ẹ tốt nhất sẽ sống sót và tạo ra những con m ọn nhiễm sắc thể tốt nhất, ví dụ như lựa chọ ựa chọn theo Boltzman (Boltzman selection), l ựa chọn trạng thái bền (Steady state ột vài phương pháp khác phương pháp thông dụng. oulette wheel của mỗi nhiễm sắc thể vi (i=1..pop-size), : với )( ivf là hàm mục tiêu ần thể: ỗi nhiễm sắc thể vi: ỗi sắc thể vi: Hoàng Dũng 17 ết tiến ới. Có n theo bánh ựa với pop-size Tối ưu hóa theo thuật toán di truy qi = ∑ − = sizepop i ip 1 Tiến trình chọn lọc ñược th lần chọn ra một nhiễm sắc th sau: • Phát sinh 1 số ngẫu nhiên • Nếu r< q1 thì chọn nh vi sao qi-1< r ≤ qi Hiển nhiên sẽ có một số niễm s lý bởi vì các nhiễm sắc thể t bình không thay ñổi và các nhi 2.1.3.2.Rank selection Cách tính ñộ thích nghi như trên ch tốt tương ñối ñồng ñều giữa các cá th hàm mục tiêu không tốt - có m còn lại thì các cá thể của thế làm giảm khả năng di truyền ñ truyền cục bộ, từ ñó có thể làm gi biệt ñó chưa chắc ñã dẫn ñến l Phương pháp xác ñịnh ñộ thích nghi x này. Phương pháp này không làm vi function) mà chỉ làm việc dự xếp các thể theo giá trị hàm m nhiễm sắc thể sẽ nhận ñược ñ cá thể xấu nhất có hạng là 1, cá th thích nghi là N( số lượng nhi hạng. Hình 9: Situation before ranking (graph of fitnesses) ền GVHD : PhD Nguyễn ực hiện bằng cách quay bánh xe rulét pop- ể từ quần thể hiện hành vào quần thể mới r trong khoảng [0,1 ] iễm sắc thể ñầu tiên v1, ngược lại chọn nhi ắc thể ñược chọn nhiều lần. ðiều này không có gì vô ốt nhất có nhiều bản sao hơn, các nhiễm sắc th ễm sắc thể kém nhất thì chết ñi. ỉ thực sự hiệu quả ñối với những quầ ể. Nếu, vì một lý do nào ñó – có thể ột cá thể có ñộ tốt quá cao, tách biệt hẳn các cá th hệ sau sẽ bị “hút” về phía cá thể ñặc biệt ñó. Do ñó, s ến thế sau của các cá thể xấu, tạo nên hiện tư ảm khả năng dẫn ñến lời giải tốt nhất (vì cá th ời giải tốt nhất). ếp hạng sẽ loại bỏ hiện tượng di truy ệc trên giá trị ñộ lớn của hàm mục tiêu (object a trên thứ tự của các cá thể trên quần thể sau khi ñ ục tiêu. Phương pháp này sẽ xếp hạng quầ ộ thích nghi tương ứng với thứ hạng của mình. Ví d ể tiếp theo xếp hạng 2,….và cá thể tốt nh ễm sắc thể). Chính vì vậy mà ta gọi là ñộ thích nghi x Hoàng Dũng 18 size lần. Mỗi theo cách ễm sắc thể ể trung n thể có ñộ do chọn ể ẽ ợng di ể ñặc ền cục bộ ã sắp n thể và mỗi ụ : ất có ñộ ếp Tối ưu hóa theo thuật toán di truy Hình 10: Situation after ranking (graph of order numbers) Phương pháp này sẽ cho ta linh ñ ñộ thích nghi lên các cá thể có ñ thể có ñộ thích nghi càng cao thì xác su Phương pháp này giúp cho t nhau. Tuy nhiên, phương pháp này d thể tốt nhất không khác biệt là bao so v 2.1.3.3Elitism Phương pháp này là một phương pháp m và ñột biến, chúng ta sẽ mất ñi nh là phương pháp mà ñầu tiên chúng ta s kế tiếp, những cái còn lại sẽ Phương pháp này gia tăng kế nhiễm sắc thể tốt nhất. 2.1.4.PHÉP LAI Các cặp cha mẹ ñược chọn lai một vị trí, lai nhiều vị trí cá thể tạo ra do lai ghép vẫn kiểm soát tần số lai tạo mà ở cá thể tạo ra nhanh, nếu quá nhanh có th ñi ý nghĩa của việc lựa chọn ban ñ kiếm do mất ñi khả năng thăm d 2.1.4.1.Lai một vị trí Với mỗi nhiễm sắc thể trong  Phát sinh 1 số ngẫu nhiên sắc thể ñó ñể lai ghép.  Sau ñó ghép các nhiễ mỗi cặp nhiễm sắc th ền GVHD : PhD Nguyễn ộng ñặt một trọng số ñể xác ñịnh sự tập trung c ộ tốt cao, mà vẫn luôn ñảm bảo ñược quy lu ất ñược tồn tại và di truyền càng cao. ất cả các nhiễm sắc thể có cơ hội ñược lựa ch ẫn ñến việc hội tụ chậm hơn bởi vì nhi ới các nhiễm sắc thể khác. ới. Khi tạo ra một quần thể mới b ững nhiễm sắc thể tốt nhất dù ít hay nhi ẽ sao chép lại những cá thể tốt nhấ ñược thực hiện theo các cách cũ. t quả tốt ưu bởi vì chúng ta ñã giữ lại ñược nh lựa lai ghép với xác suất pc. Có 3 dạng lai , lai ñều và lai theo thuật toán . Với 4 loại trên, là hằng số. Số cá thể lai tạo sẽ là pc * popsize. ñó toán tử lai ñược thực hiện. Nếu tốc ñộ lai nhanh thì s ể những cá thể trội hơn bị ñào th ầu. Tuy nhiên, tốc ñộ quá chậm sẽ ñình tr ò. quần thể: r trong khoảng [0,1 ]. Nếu r < pc thì ch m sắc thể ñã ñược chọn một cách ngẫu nhiên. ể ñược ghép ñôi, lại phát sinh ngẫu nhiên Hoàng Dũng 19 ủa ật : cá ọn như ễm sắc ằng lai tạo ều. Elitism t vào thế hệ ững ghép cơ bản: xác suất Tốc ñộ lai ố ải và làm mất ệ việc tìm ọn nhiễm ðối với một số Tối ưu hóa theo thuật toán di truyền GVHD : PhD Nguyễn Hoàng Dũng 20 nguyên pos trong khoảng [ 0, m ] (m là tổng số bit trong một nhiễm sắc thể). Số pos cho vị trí ñiểm lai. Hai nhiễm sắc thể (b1b2..bpos bpos+1..bm) và (c1c2..cposcpos+1..cm) ñược thay bằng cặp con của chúng (b1b2..bposcpos+1..cm) và (c1c2..cposbpos+1..bm). Mã nhị phân Hình 11 : Lai một vị trí ñối với mã nhị phân Mã số thực Hình 12: Lai một vị trí ñối với mã số thực Mã hoán vị (1 2 3 4 5 6 7 8 9) + (4 5 3 6 8 9 7 2 1) = (1 2 3 4 5 6 8 9 7) Mã dạng cây Chromosome 1 A B C D E F G H I J Chromosome 2 0 1 2 3 4 5 6 7 8 9 Offspring 1 A B C 3 4 5 6 7 8 9 Offspring 2 0 1 2 D E F G H I J Tối ưu hóa theo thuật toán di truy Hình 13 2.1.4.2.Lai hai vị trí Hình 1 Và : Hình 15: Lai hai v 2.1.4.3. Lai ñều Trường hợp lai ñều thì mỗ gen tương ứng với cá thể b sau:  Tạo một chuỗi lai gi bít ñược tạo ngẫu nhiên  Chuỗi con ñược tạo Chromosome 1 Chromosome 2 Offspring 1 Offspring 2 ền GVHD : PhD Nguyễn : Lai một vị trí ñối với mã dạng cây 11001011 + 11011111 = 11011111 4: Lai hai vị trí ị trí ñối với mã số thực i gen của cá thể con ñược chọn một cách ố hoặc mẹ. Cách tiến hành lai ñều ñược tiế ả M có chiều dài bằng chiều dài chuỗi b ra bằng cách lấy từng gen từ cá thể cha, m A B C D E F G H I J 0 1 2 3 4 5 6 7 8 9 A B 2 3 4 5 6 7 8 J 0 1 C D E F G H I 9 Hoàng Dũng 21 ngẫu nhiên n hành như ố, mẹ. Các ẹ. Nếu bít Tối ưu hóa theo thuật toán di truyền GVHD : PhD Nguyễn Hoàng Dũng 22 thứ I trong chuỗi lai giả M là 0 thì lấy gen tương ứng của cá thể P1, ngược lại lấy gen tương ứng cá thể P2 Hình 16: Lai ñều 2.1.4.4.Lai số học Một vài phếp toán số học ñược thực hiện ñể tạo ra con mới , thường là phép AND. Hình 17: Lai số học 2.1.5.ðỘT BIẾN ðột biến là một toán tử duy trì sự ña dạng của quần thể. ðột biến nhằm tạo ra những thông tin mới trong quần thể lai tạo tại các vị trí bit nào ñó trong mỗi nhiễm sắc thể. Với xác suất ñột biến trong quần thể là pm thì số lượng nhiễm sắc thể bị ñột biến sẽ là pm*pop-size. Mỗi bít trong nhiễm sắc thể có cơ hội ñột biến như nhau và ñược thay ñổi từ 0 thành 1 hay ngược lại. ðối với các mã khác thì cũng tương tự, các giá trị sẽ ñột biến ngẫu nhiên thành một giá trị khác. ðối với mỗi nhiễm sắc thể trong quần thể và với mỗi bit trong nhiễm sắc thể: Chromosome 1 1 0 1 1 1 0 1 1 1 0 1 Chromosome 2 1 1 0 0 1 0 0 0 1 1 1 Offspring 1 1 0 0 0 1 0 0 0 1 0 1 Tối ưu hóa theo thuật toán di truy • Phát sinh một số ngẫ biến bit ñó • Trong GAs, ñột biến 0.001 ñến 0.01. ðột ðột biến phụ thuộc vào vi ra tại một vị trí hay nhi Binary Encoding Chromosome 1 1 0 0 1 0 0 0 1 1 1 Offspring 1 0 0 0 1 0 0 0 1 1 1 ðể quá trình ñột biến có hi nghịch với kích thước gen. (N là kích thước gen). Hơn quần thể. Nghĩa là số lư hưởng ñến khả năng ñột biế 2.1.5.1.ðột biến nhẹ ðột biến này chỉ áp dụng cho mã nh Hình ền GVHD : PhD Nguyễn u nhiên r trong khoảng [0,1]. Nếu r< pm, ti xảy ra với xác suất rất nhỏ, thường nằm trong biến nhằm loại trừ sự nhầm lẫn do các tối ệc mã hóa cũng như phép lai. ðột biế ều vị trí. Permutation Encoding Chromosome 9 4 6 2 3 1 0 5 7 8 Offspring 9 6 4 2 3 1 0 5 7 8 Hình 18: ðột biến ệu quả thì xác suất ñột biến thường ñượ Một xác suất ñột biến thường ñược sử d nữa xác suất ñột biến nên ñộc lập với ợng cá thể trong quần thể tăng hay giảm n cá thể trong quần thể. ị phân 19: ðột biến nhẹ Hoàng Dũng 23 ến hành ñột khoảng ưu cục bộ. n có thể xảy c chọn tỉ lệ ụng là 1/N kích thước không ảnh Tối ưu hóa theo thuật toán di truyền GVHD : PhD Nguyễn Hoàng Dũng 24 2.1.5.2.ðột biến biên ðột biến này thay thế gen ñược chọn với gen ở biên trên hoặc dưới một cách nhẫu nhiên. Toán tử này ñược xây dựng cho các bài toán tối ưu mà lời giải tối ưu nằm trên hoặc gần biên của không gian tìm kiếm khả thi. Do ñó, nếu tập ràng buộc C rỗng và biên thật lớn thì lời giải có ñược thật khó khăn. Nhưng nó lại có ích vô cùng khi có các rang buộc. 2.1.5.3.ðột biến ñồng dạng ðột biến này thay thế các giá trị của gen ñược chọn với giá trị ngẫu nhiên ñồng dạng ñược chọn nằm giữa biên trên và biên dưới .Nghĩa là toán tử này chọn một thành phần ngẫu nhiên k = (1,….,q) của vectơ x = (x1,..,xk,….xq) và sản sinh ra x’ = (x1,…,xk’,..,xq), trong ñó xk’ là giá trị ngẫu nhiên (phân bố xác suất ñều) trong khoảng . Toán tử này ñóng vai trò quan tọng trong những giai ñoạn ñầu của quá trình tiến hóa khi các lời giải ñược phép di chuyển tự do trong không gian tìm kiếm. ðặc biệt, toán tử cần thiết này cần thiết trong trường hợp quần thể ban ñầu gồm nhiều bản sao của cùng một ñiểm. Tình trạng như thế thường xảy ra trong những bài toán tối ưu có ràng buộc mà người sử dụng ñặc tả ñiểm khởi ñầu của tiến trình. Hơn nữa, ñiểm khởi ñầu duy nhất này có một thuận lợi to lớn: nó cho phép phát triển một tiến trình lặp mà lần lặp ké tiếp bắt ñầu tại ñiểm tốt nhất của lần lặp trước. Chính kỹ thuật này ñã ñược dùng trong việc phát triển một hệ thống xử lý các ràng buộc phi tuyến trong những không gian không nhất là lồi sau này. Và do ñó, trong những giai ñoạn sau của quá trình tiến hóa,toán tử này cho phép thoát khỏi tối ưu cục bộ ñể tìm một ñiểm tốt hơn. 2.2PHẦN MỀM ÁP DỤNG GENOCOP III–Genetic Algorithm for Constrained Problems in C (by ZbigniewMichalewicz) DE–Differential Evolution Genetic Algorithm in C and Matlab(by Rainer Storn). DE has won the third place at the 1st International Contest on Evolutionary Computationon a real-valued function testsuite PGAPack–Parallel Genetic Algorithm in Fortran and C (from Argonne National Laboratory) PIKAIA–Genetic algorithm in Fortran 77/90 (by Charbonneau, Knapp and Miller) GAGA–Genetic Algorithm for General Application in C (by Ian Poole) Tối ưu hóa theo thuật toán di truyền GVHD : PhD Nguyễn Hoàng Dũng 25 GAS–Genetic Algorithm in C++ (by Jelasityand Dombi) GAlib–C++ Genetic Algorithm Library(by Matthew Wall) Genetic Algorithm in Matlab(by Michael B. Gordy) GADS–Genetic Algorithm and Direct Search Toolbox in Matlab(from MathWorks) GEATbx–Genetic and Evolutionary Algorithm Toolbox for Matlab (by HartmutPohlheim) GAOT–Genetic Algorithms Optimization Toolboxin Matlab(by Jeffrey Joines) Một số phần mềm trên chúng ta phải lập trình ñể giải bài toán. ðây không phải là vấn ñề ñơn giản vì thuật toán di truyền rất dài và phức tạp. ðối với những người không chuyên thì lập trình không dế tí nào. Ngày nay có nhiều phần mềm cung cấp giao diện ñồ họa (GUI) rất dễ sử dụng, thiết lập các thông số và chạy phần mềm là xong. Tuy nhiên phần mềm mạnh nhất và có thể nói là hoàn thiện nhất hiện nay là Gatool nằm trong phần mềm Matlab của tập ñoàn Mathworks. Matlab có thể nói là phần mềm vạn năng dùng cho các ngành kỹ thuật và kinh tế. Ta có thể dùng dòng lệnh (command line) hoặc giao diện ñồ họa ñể tính toán, rất dễ sử dụng. Giao diện ñồ họa rất trực quan và dễ sử dụng. Chúng ta chỉ cần nhập hàm, thiết lập các thông số theo yêu cầu của vấn ñề và cho nó chạy. Tối ưu hóa theo thuật toán di truyền GVHD : PhD Nguyễn Hoàng Dũng 26 Hình 20: Phần mềm Matlab Tối ưu hóa theo thuật toán di truyền GVHD : PhD Nguyễn Hoàng Dũng 27 Hình 21 : Gatool Giá thành : 200$ -700$ “The Genetic Algorithm and Direct Search Toolbox requires MATLAB and the Optimization Toolbox and is available immediately for Windows, UNIX/Linux, and Macintosh systems. Pricing starts at $700 U.S.” 2.3.ỨNG DỤNG • Scheduling: Facility, Production, Job, and Transportation Scheduling • Design: Circuit board layout, Communication Network design, Tối ưu hóa theo thuật toán di truyền GVHD : PhD Nguyễn Hoàng Dũng 28 keyboard layout, Parametric design in aircraft • Control: Missile evasion, Gas pipeline control, Pole balancing • Machine Learning: Designing Neural Networks, Classifier Systems, Learning rules • Robotics: Trajectory Planning, Path planning • Combinatorial Optimization: TSP, Bin Packing, Set Covering, Graph Bisection, Routing, • Signal Processing: Filter Design Image Processing: Pattern recognition • Business: Economic Forecasting; Evaluating credit risks Detecting stolen credit cards before customer reports it is stolen • Medical: Studying health risks for a population exposed to toxins • Chemical Engineering Heat transfer processing; Define molecular structure.. 3.THIẾT KẾ THỰC NGHIỆM 3.1.BÀI TOÁN. Nhóm nghiên cứu- M.-J. CHEN, K.-N. CHEN, AND C.-W. LIN-thuộc các trường ñại học công nghệ ở ðài Loan nghiên cứu khả năng sống sót (viabilities) của probiotics khi thêm vào các chất kích thích sinh trưởng. Calcium gluconate, sodium gluconate và N-acetylglucosamine ñược thêm vào sữa gầy ñể duy trì khả năng sống sót của Lactobacilus acidophilus và Bifidobacterium longum. ðể quyết ñịnh khả năng sống sót của probiotics, quần thể B.longum và L.acidophilus ñược ño bằng colony forming units (CFU) và bằng lượng β-galactosidase mà chúng tạo ra. Hoạt tính β-galactosidase ñược ño bằng cách xác ñịnh tốc ñộ thủy phân o- nitrophenol-β- galatopyranoside (Yu và cộng sự-1987). Sự thủy phân chất này tạo ra o-nỉtophenol-một hợp chất sinh màu cao có thể ñược xác ñịnh bằng phương pháp quang phổ. Một ñơn vị hoạt tính enzyme là 1 µmol/L of o-nitrophenol/mL. Dựa theo nghiên cứu của họ và những người trước ñó-Mitsuoka và cộng sự(1987)- khả năng sống sót của probiotics bị ảnh hưởng bởi 3 biến ñộc lập : calcium gluconate (0.0 to 0.5%), sodium gluconate (0.0 to 1.0%) và N-acetylglucosamine (0.0 to 1.0%). Việc xác ñịnh giới hạn nồng ñộ trên ñã ñược khảo sát trước. Sữa bắt ñầu ñông tụ và Tối ưu hóa theo thuật toán di truyền GVHD : PhD Nguyễn Hoàng Dũng 29 hơi tạo ra vị lạ khi nồng ñộ calcium gluconate ñược thêm vào cao hơn 0.5%. Do ñó, giới hạn trên cho calcium gluconate trong thí nghiệm này là 0.5%. Kết quả thực nghiệm ñược cho ở bảng 1. Bảng 1-Dữ liệu thực nghiệm Phương trình ñại số tổng quát từ bâc 1 tới bậc 3 ñược ñưa ra: Yi = ƒi(X1, X2, X3) + εi i = 1,2,3 Trong ñó Y1,Y2, Y3 là số L.acidophilus, B.longum và β-galactosidase quan sát ñược, X1, X2, X3 là nồng ñộ của Ca-gluconate, Na-gluconate và N-acetylglucosamine, εi là các sai số. Phương pháp hồi quy ñược thực hiện dựa trên kết quả thực nghiệm ñể xây dựng mô hình toán học phù hợp. Các mô hình này sau ñó ñược tính toán như những hàm mục Variables Responses Treatment number Calcium Sodium N-acetyl- gluconate gluconate glucosamine (%) (%) (%) Lactobacillus Bifidobacterium β- galactosid- Acidophilus longum ase activity (log CFU/ml) (log CFU/ml) (units/ml) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 0.00 0.50 0.00 0.50 0.00 0.50 0.00 0.50 0.25 0.25 0.25 0.25 0.25 0.25 0.25 0.25 0.25 0.00 0.00 1.00 1.00 0.50 0.50 0.50 0.50 0.00 1.00 0.00 1.00 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.50 0.00 0.00 1.00 1.00 0.00 0.00 1.00 1.00 0.50 0.50 0.50 0.50 0.50 7.47 7.56 7.34 7.35 7.56 7.55 7.34 7.45 7.48 7.35 7.41 7.32 7.38 7.41 7.40 7.42 7.42 7.44 7.79 7.56 7.56 7.83 7.80 7.71 7.76 7.91 7.81 7.77 7.70 7.71 7.77 7.73 7.79 7.80 257.5 282.5 252.5 250.0 270.0 280.0 246.7 251.7 285.0 236.7 241.7 232.5 275.0 275.0 275.0 277.5 275.0 Tối ưu hóa theo thuật toán di truyền GVHD : PhD Nguyễn Hoàng Dũng 30 tiêu trong bài toán tối ưu hóa bằng thuật toán di truyền ñể thu ñược khả năng sông sót cực ñại của probiotics. Các ñáp ứng- ở ñây là các hàm tuyến tính, bình phương và bậc ba- ñược kiểm tra ñể ñánh giá sự phù hợp sử dụng phân tích phương sai ANOVA. Bảng 3a kiểm tra xác suất (Prob > F), xem xét liệu chúng có nhỏ hơn 0.5 hay không. Phân tích ANOVA ñược thực hiện bằng Design-Expert® software (Stat- Ease, Inc., Minneapolis, Minn., U.S.A., 2000) Hình 22: Phần mềm Design-Expert 7.1.2 Kết quả phân tich ANOVA cho 3 trương hợp : bậc1 , bậc 2, bậc 3. Tối ưu hóa theo thuật toán di truyền GVHD : PhD Nguyễn Hoàng Dũng 31 Model Source Sum of Squares p-value Prob > F Lactobacillus acidophilus (log CFU/ml) Linear 0.066 0.0016 Quadratic 0.022 0.0068 Cubic 7.850x10^-3 0.0280 Bifidobacterium longum (log CFU/ml) Linear 0.048 0.3305 Quadratic 0.014 0.0085 Cubic 0.015 0.0367 b-galactosidase (units/ml) Linear Quadratic Cubic 2531.51 2168.73 59.130 0.0170 0.0001 0.0111 Significant at 5% level Bảng 2: Kết quả phân tích ANOVA cho mẫu Kết quả phân tích ANOVA cho thấy rằng mô hình tuyến tính phù hợp cho ñáp ứng một (p-value :0.0016), mô hình bình phương phù hợp cho hai mô hình còn lại (p- value: 0.0074 và 0.0001). Phương trình ñại số bậc 2 phù hợp với dữ liệu thực nghiệm thu ñược từ Design- Expert có dạng:
%  &' (&) * )+, -) ((&). * . */. ) -)-. (&)) * )+, -) Với k,i = 1, 2, 3 ; và β0, βi, βii, βij là các hệ số hồi quy. Sum of Mean F Source Square df Square Value Prob > F Model 0.066 3 0.022 9.1 0.0016 A-A 5.000E-003 1 5.000E-003 2.07 0.1736 B-B 0.039 1 0.039 16.25 0.0014 C-C 0.022 1 0.022 9.14 0.0098 Bảng 3:Phân tích ANOVA cho mô hình tuyến tính của Lactobacillus acidophilus Tối ưu hóa theo thuật toán di truyền GVHD : PhD Nguyễn Hoàng Dũng 32 Source Sum of Squares df Mean Square F Value p-value Prob > F Model 0.19 9 0.021 7.10 0.0085 A-A B-B C-C AB AC BC A^2 B^2 C^2 0.061 0.024 0.059 0.031 1.600E-003 2.250E-004 0.040 0.024 0.053 1 1 1 1 1 1 1 1 1 0.061 0.024 0.059 0.031 1.600E-003 2.250E-004 0.040 0.024 0.053 20.10 8.02 19.46 10.17 0.53 0.075 13.29 7.87 17.70 0.0029 0.0253 0.0031 0.0153 0.4897 0.7925 0.0082 0.0263 0.0040 Bảng 4:Phân tich ANOVA cho mô hình bậc hai của Bifidobacterium longum Bảng 5: Phân tich ANOVA cho mô hình bậc hai của β-galactosidase Các hệ số hồi quy cho mô hình phân tích như sau: Source Sum of Squares df Mean Square F Value p-value Prob > F Model 4700.24 9 522.25 57.00 < 0.0001 A-A B-B C-C AB AC BC A^2 B^2 C^2 134.65 111.05 10.87 189.06 6.25 382.20 3.22 825.26 660.53 1 1 1 1 1 1 1 1 1 134.65 111.05 10.87 189.06 6.25 382.20 3.22 825.26 660.53 14.70 12.12 1.19 20.64 0.68 41.72 0.35 90.08 72.10 0.0064 0.0102 0.3121 0.0027 0.4361 0.0003 0.5717 < 0.0001 < 0.0001 Tối ưu hóa theo thuật toán di truyền GVHD : PhD Nguyễn Hoàng Dũng 33 Regression coefficient Lactobacillus acidophilus Bifidobacterium longum β-galactosidase β 0 +7.5200 +7.68000 +269.32500 β 1 Not Significant +1.23500 +58.25000 β 2 -0.1400 +0.39000 +26.45000 β 3 -0.1050 -0.60750 Not Significant β 12 -0.70000 -55.00000 β 13 Not Significant Not Significant β 23 Not Significant +39.10000 β 11 -1.56000 Not Significant β 22 -0.30000 -56.00000 β 33 +0.45000 -50.10000 β0 represents intercept and β1, β2 and β3 represent the 3 factors of calcium gluconate, sodium gluconate, and N-acetylglucosamine, respectively. β11,β22, and β33 represent the respective square terms. β12, β23, and β13 are the interaction terms. Bảng 6: Hệ số hồi quy Ta có các phương trình tương ứng:
, = 7.52000 - 0.14000*x(2) - 0.10500*x(3)
 = 7.68000 + 1.23500*x(1) + 0.39000*x(2) - 0.60750*x(3) - 0.70000*x(1)*x(2) - 1.56000*x(1)^2 - 0.30000*x(2)^2 + 0.45000*x(3)^2
0 = 269.32500 + 58.25000* x(1) + 26.45000* x(2) - 55.00000* x(1)* x(2) + 39.10000* x(2 )* x(3) - 56.00000* x(2)^2 - 50.10000* x(3)^2 Mục tiêu của chúng ta là tìm cực ñại các hàm mục tiêu:
%  &' (&) * )+, -) ((&). * . */. ) -)-. (&)) * )+, -) Với các ràng buộc biên ñối với các biến ban ñầu: 0$ -, $ ; 0$ - $ ; 0$ -0 $ ; Trong trường hợp này có nhiều hướng tiếp cận ñể giải bài toán tối ưu ña mục tiêu. Ở ñây ta dùng phương pháp tiếp cận tổng trọng số (weighting objective). ðây là hướng tiếp cận cổ ñiển và ñơn giản, tuy nhiên nó cũng mang lại hiệu quả cao. Tối ưu hóa theo thuật toán di truyền GVHD : PhD Nguyễn Hoàng Dũng 34 Hàm mục tiêu tổng: 1  (23
% 0 )+,  Với 23 là các trọng số, ñược lựa chọn tùy theo mức ñộ quan trọng của từng mục tiêu. 23 4  (23 0 5+,  Chọn 23 dựa vào kết quả thu ñược khi chạy từng mục tiêu như hình dưới. 23 
%6
%0, 2   78;27  7; 29   1  78
,  7
  
0 Kết quả ñạt ñược khi thuật toán hội tụ về tối ưu toàn cục sau 51 thế hệ: Hình 23:Kết quả thu ñược lần 1 khi chạy mục tiêu 1 Tối ưu hóa theo thuật toán di truyền GVHD : PhD Nguyễn Hoàng Dũng 35 Hình 24: Kết quả thu ñược lần 1 khi chạy mục tiêu 2. Hình 25: Kết quả thu ñược lần 1 khi chạy mục tiêu 3 3.2.CHẠY CHƯƠNG TRÌNH Thông số ñiều khiển Tối ưu hóa theo thuật toán di truyền GVHD : PhD Nguyễn Hoàng Dũng 36 Parameter GAs Population size 20 Fitness scaling rank Selection roulette Crossover fraction 0.8 Mutation 0.01 Max generation 100 Bảng 7 : Thông số ñiều khiển cho GAs Kết quả khi chạy cho cả 3 mục tiêu Bảng 8:Kết quả thu ñược sau 9 lần chạy Các ñiểm tối ưu ñược tạo ra sẽ nằm trên miền tối ưu Pareto. Ojb Runs
,

0 1 7.5161 7.9184 289.6279 2 7.5013 7.8829 290.3122 3 7.5127 7.8988 292.9167 4 7.5178 7.8981 286.2441 5 7.5126 7.9097 288.8895 6 7.5004 7.8831 290.3798 7 7.4996 7.8897 291.0070 8 7.4950 7.8760 291.4077 9 7.4941 7.8992 289.5172 Tối ưu hóa theo thuật toán di truyền GVHD : PhD Nguyễn Hoàng Dũng 37 Hình 26:Pareto front 4..KẾT LUẬN. Việc áp dụng thuật tóan di truyền ñể giải các bài toàn kỹ thuật mang lại hiệu quả cao, cho kết quả tin cậy hơn, tránh ñược vấn ñề cục bộ. Nó có thể giải ñược các bài toán phi tuyến, không có ñạo hàm, hàm số không liên tục… 5.TÀI LIỆU THAM KHẢO [1] Nguyễn ðình Thúc. Lập trình tiến hóa. Nhà xuất bản giáo dục, 2001. [2] ðặng Văn Nghìn. Tối ưu hóa. Trường ñại học Bách Khoa thành phố Hồ Chí Minh, 2002. [3] Stephen Boyd, Lieven Vandenberghe. Convex Optimization. Cambridge University Press,2004. [4] Ronald John, Van Iwaarden. An Improved Unconstrained Global Optimization Algorithms. University of Colorado at Denver Press, 1996. [5] Carlos A. Coello Coello & Alan D. Christiansen. Two New GA-based Methods for Multiobjective Optimization. USA [6] Roger L. Wainwright. Introduction to Genetic Algorithms Theory and Applications. The Seventh Oklahoma Symposium on Artificial Intelligence,1993. Tối ưu hóa theo thuật toán di truyền GVHD : PhD Nguyễn Hoàng Dũng 38 [7] J. Pérez, M. Santamarina, J. Vallés, A. Peña, D. Valera, and A. Carreño. Optimal LayoutDesign for Milk Goats Livestock Farms Using Genetic Algorithms. Agricultural Engineering International: the CIGR Journal of Scientific Research and Development. Manuscript BC 03 019 . Vol.VI. December, 2004. [8] Arnold Neumaier. Complete search in continuous global optimization and constraint satisfaction. Cambridge Univ. Press 2004. [9] Q.T. Pham. Effext of Numerical Errors on the Performance of Optimization Methhods. Paper 601, Proc. Chemeca 2005, Brisbane, Australia, September 25 - 28, 2005. [10] Paul Charbonneau. An Introduction to Genetic Algorithms for Numerical Optimization. National Center for Atmospheric Research, Boulder, Colorado, 2002. [11] Scheilla V.C. de Souza, Roberto G. Junqueira. A procedure to assess linearity by ordinary least squares method. Analytica Chimica Acta 552 (2005) 25–35. [12] M. Kadkhodaei, M. Salimi, M. Poursina. Analysis of asymmetrical sheet rolling by a genetic algorithm. International Journal of Mechanical Sciences 49 (2007) 622– 634. [13] Ramin B. Boozarjomehry, Mohammad Masoori. Which method is better for the kinetic modeling:Decimal encoded or Binary Genetic Algorithm?. Chemical Engineering Journal 130 (2007) 29–37. [14]Kusum Deep, Manoj Thakur. A new crossover operator for real coded genetic algorithms. Applied Mathematics and Computation 188 (2007) 895–911. [15] Shiu Yin Yuen , Chi Ho Ma. Genetic algorithm with competitive image labeling and least square. Pattern Recognition 33 (2000) 1949}1966. [16] C. L. Karr, B. Weck, D. L. Massart, P. Vankeerberghen. Least Median Squares Curve Fitting Using a Genetic Algorithm. Elsevier Science Ltd. Printed in Great Britain,1995. [17] A.M. Crowe , C.J. McClean a, M.S. Cresser. An application of genetic algorithms to the robust estimation of soil organic and mineral fraction densities. Environmental Modelling & Software 21 (2006) 1503e1507. [18] G.R. Liu, X. Han, K.Y. Lam. A combined genetic algorithm and nonlinear least squares method for material characterization using elastic waves. Comput. Methods Appl. Mech. Engrg. 191 (2002) 1909–1921. [19] T. Morimoto , W. Purwanto, J. Suzuki, Y. Hashimoto. Optimization of heat treatment for fruit during storage using neural networks and genetic Algorithms. Computers and Electronics in Agriculture 19 (1997) 87–101. Tối ưu hóa theo thuật toán di truyền GVHD : PhD Nguyễn Hoàng Dũng 39 [20] M.-J. Chen, K.-N. Chen,C.-W. Lin. Optimization of the Viability of Probiotics in a New Fermented Milk Drink by the Genetic Algorithms for Response Surface Modeling. Journal of Food Science—Vol. 68, Nr. 2, 2003. [21] S.J.Mardle, S.Pascoe, M. Tamiz. An Investigation of Genetic Algorithms for the Optimization of Multi –Ojbective Fisheres Bioeconomic Models. Intl.Trans. in Op. Res. 7 (2000) 33-49. [22] The MathWorks, Genetic Algorithm and Direct Search Toolbox, [24] The MathWorks, Optimization Toolbox, [25] Stat-Ease, Inc, Design-Expert 7.1 Trial Program PHỤ LỤC Miền tối ưu Pareto 1.Giới thiệu Trong bài toán tối ưu ña mục tiêu, ta mong muốn tìm ñược một tập giá trị các biến quyết ñịnh nhằm tối ưu các hàm mục tiêu. Tập các biến quyết ñịnh cho ta một kết quả tối ưu ñược gọi là một tập tối ưu và ñược ký hiệu là x*. Miền tối ưu Pareto là một tập hợp chứa các tập tối ưu mà từ ñó ta có thể chọn ra các giá trị mong muốn. 2.Tối ưu Pareto f2 Miền khả thi A C1 C B f1 Tối ưu hóa theo thuật toán di truyền GVHD : PhD Nguyễn Hoàng Dũng 40 Hình 1 - Miền tối ưu Pareto. Như hình trên miền tối ưu Pareto (ñường tô ñậm) là một tập hợp các ñiểm nếu di chuyển từ ñiểm này (ví dụ ñiểm A) ñến ñiểm kia (ví dụ ñiểm B) trong tập hợp làm cho một mục tiêu bị giảm thì phải có ít nhất một mục tiêu khác tăng lên và ngược lại. Nói cách khác một vector xv = f(xv)=(v1,v2,…,vn) thuộc một tập P ñược gọi là thuộc miền tối ưu Pareto khi và chỉ khi không tồn tại một vector quyết ñịnh xu = f(xu) = (u1,u2,…un) nào thống trị xv ,nghĩa là ∀ i ∈ {1,…,n}, ui ≤ xi và ∃ i ∈ {1,…,n}, ui<xi Như ở hình trên thì A,B,C1 thuộc miền tối ưu Pareto nhưng C thì không, vì C bị thống trị bởi C1. Một phương án x* không bị thống trị bởi một phương án nào cả sẽ thuộc về miền tối ưu Pareto. Do vậy việc giải bài tóan tối ưu hóa ña mục tiêu là chọn ra từ miền Pareto của bài toán một hay một số các phương án tốt nhất theo một nghĩa nào ñó dựa trên cơ cấu ưu tiên của người ra quyết ñịnh. Tối Ưu Hóa Theo Thuật Toán Di Truyền GVHD : PhD Nguyễn Hoàng Dũng Trang 41