Giải bài toán tối ưu theo thuật giải di truyền

Nội dung text: Giải bài toán tối ưu theo thuật giải di truyền

1. TẠP CHÍ KHOA HỌC - ĐẠI HỌC ĐỒNG NAI, SỐ 01 - 2016 ISSN 2354-1482 GIẢI BÀI TOÁN TỐI ƯU THEO THUẬT GIẢI DI TRUYỀN ThS. Lê Thị Ngọc Hiếu1 ải di truyề ả ề ải di truyề ả ả -hard. ả ề Thuật giải di truyền (gereric algorithms) là một kỹ thuật của nhằm tìm kiếm giải pháp thích hợp cho các bài toán tối ưu ổ hợp (combinatorial optimization). Thuật giải di truyề ư i iải u ế ề ằ iế ủ ư i ủ i ậ i u u ế iế u i ủ i iều i u ủ i ư ư ủ uật giải di truyề iải ột bài toán ối ưu ột tập hợp của nh ng giải u iến tri e ướng ch n l ng giải pháp tốt dầ i u ủ uật giải di truyề ư i iải ố ối ưu ối ưu 1. Thuật giải di truyền Thuật giải di truyề ũ ư uậ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ó ã ối ưu Qu iến hóa tối ưu chỗ, thế h sau bao gi ũ ố i i ế h ước. Tiến hóa t nhiên ược duy trì nh i u ản: sinh sản và ch n l c t nhiên. Xuyên suốt quá trình tiến hóa t nhiên, các thế h mới u ượ i bổ sung thay thế thế h ũ C nào phát tri ứ ới i ư ng sẽ tồn t i. Cá th nào không thích ứ ược với i ư ng sẽ b ải. S ổi i ư ộng l ẩy quá trình tiế N ược l i, tiế ũ ộng tr l i góp phần ổi i ư ng. Các cá th mới sinh ra trong quá trình tiến hóa nh s lai ghép thế h cha mẹ. Một cá th mới có th mang nh ng tính tr ng của cha mẹ (di truyề ũ mang nh ng tính tr ng hoàn toàn mới ột biến). Di truyề ột biế i ế có vai trò quan tr ư u iến trình tiến hóa, dù rằ ột biến xảy ra với xác su t nh iều so với hi ượng di truyền. Các thuật toán tiến hóa tuy có nh i m khác bi ư ều mô ph ng bố u ả : i ột biến, sinh sản và ch n l c t nhiên. 1.1. Về ứ uậ iải i u ề ượ ộ ộ (xem [1]): 1T ư Đ i h Đồng Nai 85
2. TẠP CHÍ KHOA HỌC - ĐẠI HỌC ĐỒNG NAI, SỐ 01 - 2016 ISSN 2354-1482 GA=(I,  , , s, t, , ) T : (a) I = BI; i uầ (b)  : I R+ i u i i e ộ i ủ ộ (c)  ậ i u ề i ộ iế i i (d) s :I+ I i u i i  + ầu (e) t : I {true, false} i u uẩ (f)  ố ế ẹ (g)  ; ố ế i 1.2. (a) lai) Phép lai là quá trình hình thành nhiễm sắc th mới các nhiễm sắc th cha mẹ, bằng cách ghép một hay nhiều n gen của hai (hay nhiều) nhiễm sắc th cha mẹ với nhau. Phép lai xảy ra với xác su t pc, có th mô ph ư u: - Ch n ngẫu nhiên hai (hay nhiều) cá th b t kỳ trong quần th . Giả sử các nhiễm sắc th của cha mẹ ều có m gen. - T o một số ngẫu nhiên trong khoảng t 1 ến m-1 (ta g i i i Đi m lai chia các chuỗi cha mẹ dài m thành hai nhóm chuỗi con dài m1 và m2. Hai chuỗi nhiễm sắc th con mới sẽ là m11+m22 và m21+m12. - Đư i mới này vào quần th tham gia các quá trình tiến hóa tiếp theo. (b) t bi n) Đột biến là hi ượng các th con mang một số tính tr ng không có trong mã di truyền của cha mẹ P ột biến xảy ra với xác su t pm, nh t nhiều so với xác su t lai pc P ột biến có th mô ph ư u: - Ch n ngẫu nhiên một cá th b t kỳ cha mẹ trong quần th . - T o một số ngẫu nhiên k trong khoảng t 1 ến m, 1 k m. - T ổi gen thứ k và trả cá th này về quần th tham gia quá trình tiến hóa tiếp theo. (c) n (phép tái sinh) P i i u ượ thích nghi củ Độ thích nghi là một hàm gán một giá tr th c cho các cá th trong quần th . Quá trình này có th ược mô ph ư u: - T ộ thích nghi của t ng cá th trong quần th hi n hành, lập bảng cộng dồn các giá tr thích nghi (theo số thứ t gán cho t ng cá th ). Giả sử quần th có n 86
3. TẠP CHÍ KHOA HỌC - ĐẠI HỌC ĐỒNG NAI, SỐ 01 - 2016 ISSN 2354-1482 cá th . G i ộ thích nghi của cá th thứ i là Fi, tổng dồn thứ i là Fti, tổ ộ thích nghi của toàn quần th là Fm. - T o một số ngẫu nhiên F n t 0 ến Fm. - Ch n cá th thứ k ầu tiên th a F Ftk ư uần th của thế h mới. (d) Phép ch n là quá trình lo i b các cá th x u trong quần th ch gi l i trong quần th các cá th tốt. Phép ch n có th ược mô ph ư u: - Sắp xếp quần th theo thứ t ộ thích nghi giảm dần. - Lo i b các cá th cuối ã ch gi l i n cá th tốt nh t. Ở â iả sử quần th ước cố nh n. 1.3. Begin t:=0;  i uầ P(0):={a1(0), a2(0), , a(0)} I T ộ i ủ (a1(0)), (a2(0)), , (a(0)) While (t true) do t:=t+1; T i i P(t) P(t-1); Lai Q(t) P(t-1); Độ iế R(t) P(t-1) ; P(t):= P(t-1)  Q(t)  R(t); T ộ i ủ uầ P(t): (a1(t)), (a2(t)), , (a(t), , (a+(t) ) Sắ ế P(t) e ứ  (ai iả ầ i  uối i i  ố End; End; 1.4. ướ ầu i ủ u i iải ề i uầ i ộ ố ượ ớ u S u ộ ố i i i ộ i i i u ộ ố ủ V ượ i ộ ẫu i ộ ố ủ ộ i iải i ủ ộ ộ uầ 87
4. TẠP CHÍ KHOA HỌC - ĐẠI HỌC ĐỒNG NAI, SỐ 01 - 2016 ISSN 2354-1482 C ã ư ượ ộ iải u ế i e i u e ồi i iế ủ i ộ ậ ề iều ồi u ộ ư i e i ới ư ư e ầ ới ộ ố ư ả ư i e i ẽ ẹ ộ ồi N ư ậ ếu iều ư i e ồi iều i u ả ộ t ố ư i e ế ồi ẽ Đế â ẽ ả i ư : ử iều ế ư i e ồi N ộ ư i e ầu i ư i ều ư ồi ẽ ư i iế e N ư ả ư i e ồi ới i ố e ượ ồi ư i ướ i ộ ổ u : ải i i ư i e ế u Tiế ứ iế ế i ộ ế ộ ư i e ế ồi ế i i T ư ợ ế i i ộ ế ư i e ẽ ượ N ư ậ ải i i ủ uầ ư i uầ ới C i i ế i i ộ ế ộ i ố T : u ẫu ộ ố ế ướ ồi ư ế u ằ i i T ả ả ộ i ủ ế u u u ố ằ ế ướ T : ới ằ i ộ iế T i e ủ i ố ượ ế ướ ẽ ượ ối ợ ới u e ộ ui ắ i ới P ộ iế iế ổi ẫu i ộ iều ầ e ủ ộ ế ướ ộ ới ế u P ộ iế ộ i i ủ ượ 2. ả ậ ả ề Đ iải u ế ộ i e uậ iải i u ề ầ i i u: (a) e ối ượ ầ ủ i ư ả ớ ối ượ ầ e ộ u i u i u iễ i iế ủ i (b) â ư i uầ ầu (c) Đ i ộ i ủ uầ (d) ư ứ iế ủ uậ iải i u ề ư i ộ iế i i (e) ố ầ iế uậ iải ư ướ uầ u i u ộ iế ố ế iế 88
5. TẠP CHÍ KHOA HỌC - ĐẠI HỌC ĐỒNG NAI, SỐ 01 - 2016 ISSN 2354-1482 (f) â uậ iải. ướ : i uầ ầu ướ : ộ i ủ . ướ : T i ư ứ i ộ iế i i i uầ ới ướ : T ộ i ủ ới i i i i ộ ố ố ướ : Nếu ư ượ ố i iải ối ưu ư ế ố ế iế i i u i ướ ướ : T ượ i iải ối ưu i i ã ế ế uậ iải ế uả ượ 3. V ọ 3.1. iả ử ằ ộ ậ c ả 1, F2 n ộ ồ i e S S1, S2 Sm ộ ậ ứ Q Q1, Q2 Qq i ộ â ối ối ưu ủ S (xem [2]). T ối ưu ượ ư ứ ới iều i : - C i : ồ i ưu ỗi ả i i Sj i tin Fi i Sj i ậ ậ i i ả ứ i u ề i u V ế i ố ắ ộ ượ ồ ới i ổ ợ - i u : i iế ượ ã iế i i ứ ối ưu ượ ố i ỗi ậ i ố ả i e : 1 ế u ả i ượ i i e Sj FAM ij 0 ư ợ ượ i V ậ u iế ả 1 ượ i i e S2 S3. SSSS1 2 3 4 F1 0 1 1 0 F2 1 1 0 0 F3 1 1 1 1 F4 0 0 1 1 F5 0 0 0 1 3.2 . - T i ề i u: 89
6. TẠP CHÍ KHOA HỌC - ĐẠI HỌC ĐỒNG NAI, SỐ 01 - 2016 ISSN 2354-1482 ướ ủ ỗi ả e e i u S i ướ ủ ả i . - T i ề i : C ậ i ố ầ u ư u : ậ R x u ộ ả i ố ầ u P ầ ử ij ậ R i ố ầ âu u i i i ả j. ậ U x u ộ ả i ố ầ u ậ ậ P ầ ử uij ậ U i ố ầ âu u i i ậ ậ i ả j. V : R : UM: FFFFF1 2 3 4 5 FFFFF1 2 3 4 5 q 2 3 0 0 0 q 0 0 0 1 2 1 1 q2 2 0 0 1 0 q2 0 3 0 0 0 q 2 1 0 1 0 q3 0 0 3 0 0 3 q 0 0 0 0 3 q4 3 0 2 0 0 4 ậ R iế u 3 i ầ ả 3. ậ U iế u 3 i ậ ậ ầ ả 1 ầ ả 2 ầ ả 4. N i ũ ầ ải ậ R Q x u ộ i e i ầ ố u i ỗi i e P ầ ử FREQ ij i ố ầ âu u i i i i e Sj. V : ậ R Q SSSS1 2 3 4 q1 0 2 3 1 q2 0 3 0 0 q3 2 0 1 0 q4 0 0 4 0 ậ R Q iế u 3 ượ ầ i e S1 ầ site S3. - T i ề : ậ CTR x i i u ề i u P ầ ử CTRij i u ề i u Si ế Sj 90
7. TẠP CHÍ KHOA HỌC - ĐẠI HỌC ĐỒNG NAI, SỐ 01 - 2016 ISSN 2354-1482 SSSS1 2 3 4 S1 0 0.32 0.48 0.16 S2 0.32 0 0.64 0.32 S3 0.48 0.64 0 0.64 S 0.16 0.32 0.64 0 4 3.3 . Đ i e ư ả i e ổ i i u i i : Cost = CCload+CCproc T CCload i i u CCproc i u ề i ử u N ới i ủ i u ề i i u u V ế u â ế i u ề i ử u N ư ậ i i e ư sau (xem [3]): m q Cost CCproc  FREQ ik*() TR i TU i, k ki 11 n T : TRi  r ij j 1 nm TUi, k  u ij ()* FAM jl SIZE F j CTR kl jl 11 3.4 . N ư ã ề ậ i ối ưu ộ ư ả i i e S i C i i S ải iều i : - ỗi i e ải ượ ả - ỗi ả ải ượ i e 3.5. (a) ả - C : ộ ư - C u i u iễ : ậ FAM=[xij] i=1 m, j=1 n (b) 91
8. TẠP CHÍ KHOA HỌC - ĐẠI HỌC ĐỒNG NAI, SỐ 01 - 2016 ISSN 2354-1482 - i uầ : ỗi ượ â ằ ậ FAM ầ ử xij ượ ẫu i ậ iều i ố ầ ử xij= ỗi ớ ố ầ ử xij= ỗi ộ ớ (c) - i  : i i 5.2) - C i ố : ộ ượ i ố ếu i i i u ới uầ (d) ả ề - P ộ iế : (i, j ẫu i ếu i xij u ếu i xij u 0 0 1 0 1 0 V : C FAM i 1 1 0 0 1 0 - P ộ iế ượ i ư u: ẫu i ộ i x32 ượ u 0 0 1 0 0 1 Độ iế ổi 0 1 0 0 1 0 1 1 0 1 0 0 0 1 0 0 1 0 - P : Sắp xế uần th theo thứ t ộ thích nghi giảm dầ i ầ i b các cá th cuối ã ch gi l i 1 cá th tốt nh t. - P i i : Ở ế u i i ố FAM i ế ướ i ẫu i i uầ ư ủ i â uậ iải i u ề i u iế ử ộ uầ : ộ iế i i T i i ố ủ u ướ ẽ ượ i i ế u u ả ả ằ ế uả ượ u u ẽ ố ằ u 92
9. TẠP CHÍ KHOA HỌC - ĐẠI HỌC ĐỒNG NAI, SỐ 01 - 2016 ISSN 2354-1482 ướ T i ộ iế ư ượ ố uậ ũ ủ 4. ế ậ i ã ộ ư iải i ối ưu i ớ ằ uậ iải i u ề i uậ iải i u ề ượ e ư ộ ẽ iải u ế ề i iải ối ưu i ư ậ i i i u iều i i ậ ải ư i i u ả ủ uậ iải i u ề ẫ ượ i iải i i N iều ã i ứu ề u ế ứ iều ủ ế iới , iều ứ i ằ uậ iải i u ề ộ ỹ uậ ẽ iế T I I U TH HẢO N u ễ Đ T c (chủ biên) (2002), Trí tu nhân t o – L p trình ti n hóa, Nxb.Giáo d c, Hà Nội. T e u - P i V u ie T ầ Đứ Qu i ch), (1999), N T ố Nội. 3. Yin-Fu Huang, Jyn-Her Cheng: Fragment Allocation in Distributed Database Design . In: Journal of information science and engineering, 2001. STUDYING NON-LINEAR MODELS IN SOLVING THE OPTIMIZATION PROBLEMS WITH GENETIC ALGORITHMS ABSRACT Using the generic algorithms to generate solutions to the optimization problems in computer science is fascinating as its principles are based on the laws of struggle for existence in nature. This research suggests a method of using genetic algorithms to generate solutions to optimization problems in a vast space. Together illustrative examples, allocation problems in distributed database are considered as an optimization problem of NP-hard. Key words: optimization problems, generic algorithms, allocation problems. 93