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ả.

CHỦ NHIỆM BỘ MÔN Ngày tháng năm
(Ký và ghi rõ họ tên ) (Ký và ghi rõ họ tên)

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

GVHD : PhD Nguyễn Hồng Dũng

3 NHẬN XÉT ĐỒ ÁN

Cán bộ hướng dẫn .Nhận xét: ________________________________________
________________ ________________________________________________
________________ ________________________________________________
________________ ________________________________________________
________________ ________________________________________________

Điểm: __________ Chữ ký: ___________________

Cán bộ chấm hay Hội đồng bảo vệ.Nhận xét : __________________________
________________ ________________________________________________
________________ ________________________________________________
________________ ________________________________________________
________________ ________________________________________________

Điểm : __________ Chữ ký: ___________________

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


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
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

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

Xem xét bài toán sau:




 












(1)


  

 


  

  ;   
Cực đại toàn cục 

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

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(x
1
,x
2
,x
3
,.,x
n
),trong đó mỗi biến xi thụộc miền D=[a
i
,b
i
] 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 x
i
. Để đạt được độ chính xác như vậy miền [ a
i
,b
i

] được phân cắt
thành (b

,b
i

] được biểu diễn bằng một chuỗi nhị phân có
chiều dài m
i
. Phép ánh xạ biến nhị phân thành biến thực x
i

được tính theo công thức:

x
i
= a
i
+ decimal(string
2
)*
12 −
−
i
m
ii
abtrong đó decimal (string
2
) biểu diễn giá trị thập phân của chuỗi nhị phân string
2

] .
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 truyTrong đó 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.

ủa ngôn ngữ chương trình.
Chromosome B ( do_until step wall )
Mã dạng cây
ng trong các bài toán trình tự (ordering problems) như trong
travelling salesman problem), trong đó mỗi nhi
nhiên.
Chromosome A 1 5 3 2 6 4 7 9 8
Chromosome B 8 5 6 7 2 3 1 4 9
Hình 7:Mã hoán vị
n Hoàng Dũng
16

ạo cụ thể cho bài
ến hóa hoặc các biểu
ờng hợp bản thân cấu trúc dữ liệu của
ợc thực hiện khá dễ dàng.
ợng , chẳng hạn
(ordering problems) như trong
i nhiễm sắc thể