Tài liệu Đề tài Tối ưu hóa theo thuật toán di truyền: Tối ưu hĩa theo thuật tốn di truyền GVHD : PhD Nguyễn Hồng Dũng
1
Lời cảm ơn
Em xin chân thành cảm ơn thầy Nguyễn Hồng Dũng đã giúp em hồn thành đồ án
này. Trong quá trình thực hiện, em đã gặp khơng ít khĩ khăn. Nếu khơng cĩ sự giúp
đỡ tận tình của thầy và các bạn thì cĩ lẽ em khĩ cĩ thể hồn thành tốt đồ án này.
Trên con đường ghĩp nhặt những kiến thức quý báu, các thầy cơ và các bạn lớp thực
phẩm HC03TP là những người đã cùng em sát cánh bên nhau. Em xin chân thành
cảm ơn tất cả.
Tối ưu hĩa theo thuật tốn di truyền GVHD : PhD Nguyễn Hồng Dũng
2
BỘ GIÁO DỤC VÀ ĐÀO TẠO CỘNG HOÀ XÃ HỘI CHỦ NGHĨA VIỆT NAM
TRƯỜNG ĐẠI HỌC BÁCH KHOA ðộc lập –Tự do-Hạnh Phúc
Thành phố Hồ Chí Minh
Khoa: Hoá
Bộ môn :Công nghệ thực phẩm
ĐỒ ÁN
MÔN HỌC :“DAMH CÔNG NGHỆ THỰC PHẨM” MÃ SỐ: 603136
Họ và tên sinh viên: Nguyễn Hữu Chính
MSSV: 60300289
Lớp :HCO3TP01
Ngành:Thực phẩm
1.Đầu đề đồ án :Tổng quan tài li...
41 trang |
Chia sẻ: hunglv | Lượt xem: 2103 | Lượt tải: 0
Bạn đang xem trước 20 trang mẫu tài liệu Đề tài Tối ưu hóa theo thuật toán di truyền, để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
Tối ưu hóa theo thuật toán di truyền GVHD : PhD Nguyễn Hoàng Dũng
1
Lời cảm ơn
Em xin chân thành cảm ơn thầy Nguyễn Hoàng Dũng ñã giúp em hoàn thành ñồ án
này. Trong quá trình thực hiện, em ñã gặp không ít khó khăn. Nếu không có sự giúp
ñỡ tận tình của thầy và các bạn thì có lẽ em khó có thể hoàn thành tốt ñồ án này.
Trên con ñường ghóp nhặt những kiến thức quý báu, các thầy cô và các bạn lớp thực
phẩm HC03TP là những người ñã cùng em sát cánh bên nhau. Em xin chân thành
cảm ơn tất cả.
Tối ưu hóa theo thuật toán di truyền GVHD : PhD Nguyễn Hoàng Dũng
2
BOÄ 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
Các file đính kèm theo tài liệu này:
- DO_AN_THAT.pdf