M C L C
Ụ
Ụ
L I NÓI Đ U
Ờ
Ầ
iả thu tậ hợp lý để gi iố ưu là những bài toán iả chúng. Trong đó các bài toán t
t ố nh tấ iả pháp t iố ưu hóa t ổ ợ có thể xem như bài toán tìm kiếm gi iả pháp. Khi không gian tìm kiếm nh , ỏ những
t.ệ Thu tậ gi
nh m tìm ki m gi ậ ả ằ ộ ỹ ề là m t k thu t c a ậ ủ khoa h c máy tính h p ( ợ ế ả ộ ề i thu t ti n hóa ậ ế i pháp ả i thu t di ậ ủ ti nế nhiên ộ i thu t di truy n đ ậ ư tin sinh ổ ế ọ ố ư ổ ợ combinatorial optimization). Gi i u t ủ gi ả ế , ch n l c t ọ ọ ự ề ượ , trí tu nhân t o ệ v n d ng các nguyên lý c a ậ ụ , và trao đ i chéo . ổ c dùng ph bi n trong m t s ngành nh ộ ố ạ , tài chính và m t s ngành khác. bài toán cái túi) là m t bài toán i u hóa t ộ ố ộ t ố ư ể ề ọ ừ ừ ấ i h n kh i l ữ ể ộ toán t h p ổ v n đ ch n nh ng gì quan tr ng có th nhét v a vào ọ ng) đ mang theo trong m t chuy n đi. Các ế ế ộ ứ ổ ợ , lý thuy t đ ph c
ế ả ậ i thu t di truy n( GA) và bài toán x p ba lô, v i s Gi ả ụ ủ ộ i thu t di truy n và ng d ng c a gi ậ ứ ớ ự ề chúng i thu t di truy n ề ậ ề i di truy n ả ụ ủ ề
ầ ợ
ạ ọ ệ ớ ộ
Với khả năng hi nệ nay, máy tính đã giúp giải được r tấ nhi uề bài toán khó mà trước đây thường bó tay. M cặ dù v yậ v nẫ có m tộ số lớn các bài toán thú vị mà chưa có gi thường g pặ trong thực ti n.ễ Bài toán t h p trong không gian vô cùng lớn các gi phương pháp cổ đi nể như trên cũng đủ thích hợp, nhưng khi không gian tìm kiếm lớn ph iả dùng kỹ thu tậ trí tuệ nhân t oạ đ cặ bi iả di truyền (GA) là m tộ trong những kỹ thu tậ đó. Gi i thu t di truy n thích h p cho các bài toán t truy n là m t phân ngành c a hóa như di truy nề , đ t bi n Ngày nay, gi ả h cọ , khoa h c máy tính ọ Bài toán x p ba lô (m t s sách ghi là ế ộ ố h pợ . Bài toán đ c đ t tên t ượ ặ trong m t cái túi (v i gi ố ượ ớ ạ ớ ộ ng xu t hi n trong kinh doanh, ng t bài toán t th ệ ự ườ ấ ươ , m t mã h c t p tính toán ụ . ọ và toán ng d ng ậ ứ ạ Chính vì ng d ng l n c a gi ề ậ ớ ủ ụ ứ i thu t di truy n, giáo viên b môn ầ Tr n Thanh Hùng giúp đ c a th y ỡ ủ ầ em ti n hành đi tìm hi u v gi ậ ả ứ ề ể ề ả ế Tìm hi u và ng d ng c a thu t gi trong bài toán x p ba lô v i đ tài “ ớ ề ế trong bài toán x p ba lô”. ế Sinh viên th c hi n: ệ ự Tr n Quang H p. MSSV: 0441060068. L p: KHMT1-K4-Đ i h c công nghi p Hà N i(Haui). Email: hauiquanghop@gmail.com Môn Gi i thu t di truy n và ng d ng. ề ứ ụ ả ậ
CH
NG I
-
T NG QUAN V GI I THU T DI TRUY N
ƯƠ
Ề Ả
Ổ
Ậ
Ề
1. Khái ni mệ Gi nh m tìm ki m gi ọ ả ằ ộ ỹ ề là m t k thu t c a ậ ủ khoa h c máy tính ậ ợ ế ố ư ổ ợ combinatorial optimization). Gi v n d ng các nguyên lý c a ề i ả i thu t ậ ả ủ ti nế h p ( i thu t ti n hóa ậ ế nhiên ộ ậ ụ ổ i u t ả ọ ọ ự i thu t di truy n đ ậ ổ ế ư tin sinh ủ gi ế , ch n l c t ề ượ , trí tu nhân t o ệ ộ ố , và trao đ i chéo . c dùng ph bi n trong m t s ngành nh ộ ố ạ , tài chính và m t s ngành khác.
iả và kh oả sát không gian lời gi iả thích qua thí dụ về sự ti nế hóa c a ủ m tộ
ồ
tố về "nguyên li uệ di truy nề thỏ". M tộ số th ỏ ch mậ ch pạ có
Và trên t ộ tấ cả thiên nhiên l
di truy nề cũng thực hi nệ các bước tương iố ưu , thu t toán iả t ậ
iả c aủ bài toán iả (ý tưởng c aủ m tộ nhiễm s cắ thể cụ thể được người sử dụng xác đ nhị
iả trong không gian lời giải. Tìm kiếm tố nh tấ và kh o ả sát không iả t
iạ bỏ qua vi cệ kh oả sát không gian tìm tố nh tấ hi nệ hành nhưng leo đ iồ l
iả xu tấ s c,ắ nhưng l iả
i thu t di truy n pháp thích h p cho các bài toán t di truy n là m t phân ngành c a ộ hóa như di truy nề , đ t bi n Ngày nay, gi ả h cọ , khoa h c máy tính ọ Tư tưởng c aủ thu tậ toán di truy nề là mô phỏng các hi nệ tượng tự nhiên: K ế thừa và đ uấ tranh sinh t nồ đ cáiể iả khái ni mệ ti nế lời gi kế thừa và đ uấ tranh sinh t nồ được gi qu nầ thể thỏ như sau: Có m tộ qu nầ thể th ,ỏ trong đó có m tộ số con nhanh nh nẹ và thông minh hơn những con khác. Những chú thỏ nhanh nh nẹ và thông minh có xác su tấ bị ch n cáo ăn th tị tố nh tấ có thể : T o ạ thêm nhi uề iạ dể làm những gì t nhỏ hơn, do đó cũng t nồ t thỏ t t.ố Dĩ nhiên, m tộ số thỏ chậm ch pạ đ nầ đ nộ cũng sống sót vì may m n.ắ Qu nầ thể những chú thỏ còn sống sót sẽ b tắ đ uầ sinh s n.ả Vi cệ sinh s nả này sẽ t oạ ra m tộ h nỗ hợp t con với những con thỏ nhanh, m tộ số nhanh nh nẹ có con với th ỏ nhanh nh n,ẹ một số thông minh với thỏ đ nầ đ n… i ạ ném vào m tộ con thỏ "hoang dã" bằng cách làm đ tộ bi nế nguyên li uệ di truy n ề th .ỏ Những chú thỏ con do k tế quả này sẽ nhanh hơn và thông minh hơn những con thỏ trong quần thể g cố vì có nhi uề bố mẹ nhanh nh nẹ và thông minh hơn đã thoát ch tế kh iỏ ch nồ cáo. Khi tìm ki mế lời gi ứng với câu chuy nệ đ uấ tranh sinh t nồ c aủ loài th .ỏ Thu tậ toán di truy nề sử dụng các thu tậ ngữ vay mượn c aủ di truy nề h c.ọ Ta có thể nói về các cá thể (hay ki uể gen, c uấ trúc) trong m tộ qu nầ th ,ể những cá thể này cũng còn được g iọ là chu iỗ hay các nhi mễ s cắ thể. M iỗ ki uể gen (ta g iọ là m tộ nhiễm s cắ th )ể sẽ bi uể di nễ m tộ lời gi đang gi trước), m tộ tiến trình ti nế hóa được thực hi nệ trên m tộ qu n ầ thể các nhiễm s cắ thể tương ứng với m tộ quá trình tìm kiếm lời gi đó cần cân đ iố hai m cụ tiêu: Khai thác những lời gi gian tìm kiếm. Leo đ iồ là m tộ ví dụ về chi nế lược cho phép khai thác và c iả thi nệ iả t lời gi kiếm. Ngược l i,ạ tìm kiếm ngẫu nhiên là m tộ ví dụ đi nể hình c a ủ chi nế lược kh oả sát không gian tìm kiếm mà không chú ý đ nế vi cệ khai thác những vùng đ yầ hứa h nẹ c aủ không gian. Thu tậ toán di truy nề (GA) là phương pháp tìm kiếm (đ cộ lập mi n)ề t oạ được sự cân đ iố đáng kể giữa vi cệ khai thác và kh oả sát không gian tìm kiếm. Thực ra, GA thu cộ lớp các thu tậ gi iạ r tấ khác những thu t ậ gi ng uẫ nhiên vì chúng k tế hợp các ph nầ tử tìm kiếm trực ti pế và ng uẫ nhiên. Khác bi tệ quan trọng giữa tìm kiếm c aủ GA và các phương pháp tìm kiếm khác là GA duy trì và xử lý m tộ tập các lời gi iả (ta g iọ là m tộ qu nầ th )ể
ị
ỗ được ng uẫ nhiên. T pậ các cá th nàyể
được m tộ giá trị có độ thích nghi - Fitness. Giá trị này, đ để ơn gi nả cho đơn t"ố c aủ lời gi iả hay đọ cao trong tìm kiếm theo ki uể leo đ i. ồ Vì t"ố c aủ lời gi iả hay tính thích nghi c aủ cá thể trong ị
m tộ thế hệ khác với độ iạ để t o raạ tố hơn.
ể được ch nọ từ thế h tệ rước, thông thường cũng là những cá thể có ố
iạ được xử lý như thế h tệ rước cho đ nế khi có m tộ cá thể Theo đề xu tấ c aủ giáo sư John Holland, m tộ v nấ đề bài toán đ tặ ra s đẽ ược mã hóa Nói m tộ cách chính xác là các thông số thành các chu iỗ với chi uề dài bit cố đ nh. c aủ bài toán sẽ được chuy nể đ iổ và bi uể di nễ l iạ dưới dạng các chu iỗ nhị phân. Các thông số này có thể là các bi nế c aủ m tộ hàm ho cặ hệ số của m tộ bi uể thức toán h c.ọ Người ta g iọ các chu iỗ bít này là mã genome ứng với m iỗ cá th ,ể các genome đ uề có cùng chi uề dài. Nói ngắn g n,ọ m tộ lời gi iả s đẽ ược bi uể diễn bằng m tộ chu iỗ bít, cũng như m iỗ cá thể đ uề được quy định bằng gen c aủ cá thể đó iả di truy n,ề m tộ cá thể chỉ có m tộ gen duy nh tấ và v y.ậ Như v y,ậ đ iố với thuật gi m tọ gen cũng chỉ ph cụ vụ cho m tộ cá thể duy nhât. Do đó, gen chính là cá thể và cá thể chính là gen. Ban đ u,ầ ta sẽ phát sinh m tộ số lượng lớn, giới h nạ các cá thể có gen ngẫu nhiên - nghĩa là phát sinh m tộ t pậ hợp các chu i bit g iọ là qu nầ thể ban đ uầ (initial population). Sau đó, dựa trên m tộ hàm nào đó, ta sẽ xác đ nhị gi nả chính là độ "t phát sinh ng uẫ nhiên nên độ "t qu nầ thể ban đ uầ là không xác đ nh. Để c iả thi nệ tính thích nghi c aủ qu nầ thể người ta tìm cách t oạ ra qu nầ th ể mới. Có hai cách thao tác thực hi nệ trên thế hệ hi nệ t thích nghi t tố từ thế h trệ ước Thao tác đ uầ tiên là sao chép nguyên m uẫ một nhóm các cá thể t r iồ đưa sang thế hệ sau (selection). Thao tác này đảm b oả độ thích nghi c aủ thế hệ sau luôn được giữ ở m tộ mức độ hợp lý. Các cá thể được ch nọ thông thường là các cá thể có độ thích nghi cao nh t.ấ Thao tác thứ hai là t oạ ra cá thể mới b nằ g cách thực hi nệ các thao tác sinh s nả trên m tộ s cá th độ thích cao. Có hai lo iạ thao tác sinh s n:ả m tộ là thao tác lai t o ạ (crossover), hai là đ tộ bi nế (mutalion). Trong thao tác lai t o,ạ từ gen c aủ hai cá thể được ch nọ trong thế hệ trước sẽ được phối hợp với nhau (theo m tộ quy tác nào đó) đ t oể ạ thành hai gen mới. Thao tác chọn l cọ và lai t oạ giúp t oạ ra thế hệ sau. Tuy nhiên, nhi uề khi do thế hệ khởi t oạ ban đ uầ có đ cặ tính chưa phong phú và chưa phù hợp nên các cá thể không r iả đ uề được không gian c aủ bài toán (tương tự như trường hợp leo đ i,ồ các người iả leo đ iồ t pậ trung d nồ vào m tộ góc trên vùng đ t).ấ Từ đó, khó có thể tìm ra lời gi t iả quy tế được v nấ đề này. Đó là iố ưu cho bài toán. Thao tác đ tộ bi nế sẽ giúp gi sự bi nế đ iổ ng uẫ nhiên m tộ ho cặ nhi uề thành ph nầ gen c a ủ m tộ cá thể ở thế hệ trước t oạ ra m tộ cá thể hoàn toàn mới ở thế hệ sau. Nhưng thao tác này chỉ được phép xảy ra với t nầ su tấ r tấ th pấ (thường dưới 0.01), vì thao tác này có thể gây xáo tr nộ và làm m tấ đi những cá thể ch nọ l cọ và lai t o ạ có tính thích nghi cao, d nẫ đ nế thu tậ toán không còn hi uệ qu .ả Thế h ệ mới được t oạ ra l đ tạ được gi iả pháp mong mu nố ho cặ đ tạ đ nế thời gian giới h nạ
Hình 1. S đ gi i thu t di truy n ơ ồ ả ề ậ iả thu tậ di truy nề như sau:
in structures P(t)
C uấ trúc c aủ gi T=0 Initialize P(t) evaluate While not end do T= t + 1 Select C(t) from P(t - 1) Recombine structures in C(t) forming C'(t) Mutate Evaluate Replace structures in C' (t) forming C'' (t) structures in C''(t) P(t) from C''(t) and/or P (t - 1)
i thu t di truy n c c a gi ề ả ướ ủ ậ ) Kh i t o qu n th (initialize ầ ể ở ạ
2. Các b 2.1. Qu nầ thể đ uầ tiên được khởi t oạ m tộ cách ngẫu nhiên từ t pậ hợp những cá thể .ẻ Kích cỡ c aủ qu nầ thể đ uầ tiên phụ thuộc vào y uế tố tự nhiên c aủ bài toán, iả pháp hợp lý. ề được g iọ là không gian tìm ki mế iả pháp hợp lý cho v n đấ
ắ thể và cá thể cho v nấ đ , ề và thông thường đó sẽ là k tế quả cu iố tố nhất.
riêng l nhưng nhìn chung thì m tộ bài toán có đ nế hàng trăm hay hàng nghìn gi T pậ hợp những gi (search space). Trước m tộ bài toán áp d ng ụ thu tậ toán di truy n,ề ta c nầ ph iả xác đ nhị rõ nhi m s c ễ cùng. Vi cệ phân tích sẽ dựa trên k tế qu cả ơ b nả t Ví d : ụ v1: 1 0 0 0 1 1 1
v2: v3: v4: v5: v6:
ộ 1 1 1 1 0 0 0 1 0 1 0 1 0 1 1 1 0 0 0 1 1 1 1 1 0 0 0 1 0 1 0 1 1 1 0 2.2. Tính toán đ thích nghi(evaluate) Các quá trình ti nế hóa di nễ ra trong vòng l p ặ While, t iạ thế h thệ ứ t, thu tậ toán di
truy nề duy trì m tộ t pậ lời gi }. M iỗ lời gi iả x được t ,…, x n t i
t t x iả P(t) = {x 1, 2, aủ lời gi t" cố i.ả Ch n l c(select) đánh giá "độ thích nghi ", hay độ "t ọ ọ 2.3. Phép ch nọ là quá trình lo iạ bỏ các cá thể x uấ trong qu n thầ ể đ chể ỉ dữ l iạ trong t.ố
i n cá th t l đây ể ố ãy đ ch gi ể ỉ ữ ạ ạ ỏ ể ố t nh t. Gi ấ s ả ử ở ể qu n th có ầ qu nầ thể các cá thể t Phép ch nọ được mô ph ng:ỏ 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 d kích th c c đ nh n
ướ ố ị Có nhi uề phương pháp ch nọ l cọ nhi mễ s cắ thể: Ch nọ l cọ Roulette (Roulett Wheel Selection).
Ch nọ l cọ x pế h ngạ (Rank Selection). Ch nọ l cọ c nhạ tranh (Tournament Selection) Ví d v ụ ề Ch nọ l cọ Roulette (Roulett Wheel Selection).
Hình 2. Roulette Bánh xe
ắ Chia ph n trên bánh xe Roulette tùy thu c vào đ thích nghi c a t ng nhi m s c ộ ễ ầ ộ th . Đ thích nghi càng cao thì ph n c a nhi m s c th đó càng l n. ể ắ ủ ừ ớ ễ ủ ế ừ R i random càng nhi u xác su t r i ch y u vào các ph n l n càng l n. T đó ầ ớ ớ ề c các nhi m s c th t ầ ủ ấ ơ t. ể ộ ơ xác đ nh đ ị ễ ắ ể ố ượ
2.4.
ạ
Quá trình sinh s nả Có hai lo i thao tác sinh s n ả - Phép lai t oạ (Crossover): là quá trình hình thành nhiễm s cắ thể mới trên cơ sở nhi mễ s cắ thể cha mẹ bằng cách ghép một hay nhi uề đo nạ gen c aủ hai hay nhi uề nhi mễ s cắ thể cha mẹ với nhau. Có những phương pháp lai ghép sau:
Based Crossover).
- Lai ghép ánh x tạ ừng ph nầ (PMX Partial Mapped Crossover). - Lai ghép có tr tậ tự (OX order Crossover). - Lai ghép dựa trên v trí (Position ị - Lai ghép dựa trên thứ tự (Order Base Crossover). - Lai ghép có chu trình (CX cycle Crossover). - Lai ghép thứ tự tuy nế tính (LOX Linear order Crossover). Phép lai t oạ x yả ra với xác su tấ p
ả sử các nhi mễ s cắ
, m , được mô ph ngỏ như sau: c Ch nọ ng uẫ nhiên m tộ hay nhi uề cá thể b tấ kỳ trong qu nầ th .ể Gi 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 (được g iọ là đi mể lai). Điểm lai chia các chu iỗ cha mẹ có độ dài m thành hai nhóm chuỗi con với độ dài m 1 2 + m và m + m hai chu iỗ nhi mễ s cắ thể mới là m 11 12 21 22
Đưa hai cá thể mới vào qu nầ thể để tham gia các quá trình tiến hóa ti pế theo. Ví dụ : Hai nhi mễ s cắ thể cha mẹ :
Thì vi cệ trao đ iổ chéo các nhi mễ s cắ thể sau gen thứ năm s t oẽ ạ ra hai con:
ộ Phép đ t bi n (mutalion): ế Phép đ tộ bi nế là hi nệ tượng cá thể con mang m tộ
lỷ ệ đ tộ bi n.ế tố hơn, do đó có m tộ vài
- (ho cặ m tộ s )ố tính trạng có trong mã di truy nề c aủ cha m ,ẹ tức là sự sửa đ iổ m tộ ho cặ m tộ vài gen c aủ một nhiễm s cắ thể ch nọ b ngằ cách thay đ iổ ng uẫ nhiên với xác su tấ là t Không ai có thể đánh giá được phương pháp đ tộ bi nế nào t phương pháp đơn gi n,ả cũng có vài trường hợp khá phức t p.ạ Người ta thường ch nọ m tộ trong những phương pháp sau :
- Đ tộ bi nế đ oả ngược (Inversion Mutation).
- Đ tộ bi nế chèn (Insertion Mutation)
- Đ tộ bi nế thay thế (Displacement Mutation).
- Đ tộ bi nế tương hỗ (Reciprocal Exchange).
(Shift Mutation). - Đ tộ bi nế chuy nể d chị
Phép đ tộ bi nế x yả ra với xác su tấ p nhỏ hơn r tấ nhi uề so với xác su tấ lai p m c.
Phép đ tộ bi nế có thể được mô phỏng:
- Ch nọ ng uẫ nhiên m tộ cá thể b tấ kỳ cha mẹ trong qu nầ th .ể
- T oạ m tộ s nố gẫu nhiên k trong khoảng từ 1 đ nế m với 1≤ k ≤ m.
Thay đ iổ gen thứ k và trả cá thể này về qu nầ thể để tham gia vào
- quá trình ti nế hóa ti pế theo.
iả di truy n,ề gi iả một bài toán được cho ph iả có năm thành ph n:ầ M tộ thu tậ gi - M tộ c uấ trúc dữ li uệ bi uể di nễ không gian lời gi iả c aủ bài toán.
- Phương pháp khởi t oạ qu nầ thể ban đ uầ P(0).
- Hàm đ nhị nghĩa độ thích nghi evaluate đóng vai trò môi trường.
- Các phép toán di truy nề như đã mô ph ngỏ trên.
Và các tham số thu tậ toán di truy nề sử dụng (kích thước, qu nầ th ,ể xác
- su tấ lai, đ tộ bi n…) ế
Đi uề ki nệ k tế thúc Thoát ra quá trình ti nế hóa qu nầ th ,ể dựa vào bài toán mà có các cách k tế thúc v nấ
đề khác nhau, m tộ khi đã đạt đ nế mức yêu c u.ầ M tộ vài trường hợp thông thường như sau:
- K tế thúc theo k tế qu :ả m tộ khi đ tạ đ nế mức giá trị yêu c uầ thì chấm dứt ngay quá trình thực hi n.ệ - K tế thúc dựa vào số thế h :ệ ch nọ số thế h ,ệ quá trình sẽ dừng l iạ đúng ngay s thố ế h ệ đã qui đ nhị trước, không c nầ bi tế k tế quả như thế nào. - Tính theo thời gian: Không c nầ bi tế đã bao nhiêu thế hệ hay k tế quả thế nào, chỉ c nầ dựa vào s ố giờ qui đ nhị mà k tế thúc.
- Tổ hợp: dung nhi uề phương án khác nhau cho v nấ đ ,ề chẳng h nạ như: ch yạ theo số thế hệ xong sau đó đánh giá cho ch yạ theo k tế qu ,ả ho cặ ngược l i.ạ
CH
NG II
-
BÀI TOÁN X P BA LÔ
ƯƠ
Ế
ớ ệ 1. Gi Bài toán x p ba lô t i thi u ế ố ư h p ộ ố c đ t tên t (m t s sách ghi là ừ ấ i h n kh i l ế ữ ể ng t toán t ộ h p ớ ạ ng xu t hi n trong kinh doanh, ấ bài toán cái túi) là m t bài toán i u hóa ộ ừ v n đ ch n nh ng gì quan tr ng có th nhét v a ể ọ ng) đ mang theo trong m t chuy n đi. ổ ợ , lý thuy t đế ộ ứ ạ c gi ộ , tuy ch a có m t ư ờ ử ụ ổ ổ ố ắ , ch ng h n ẳ ố ụ ể ọ ạ ổ ị ươ i đ i gi ậ ờ trên là NP-đ y đầ ủ và ủ
c gi ề ệ ố m t mã hóa khóa công khai ậ ộ ng dùng nhóm thay vì các s nguyên. Merkle-Hellman và m t ườ ng t khác đã b phá, do các bài toán t ng con c th mà h t o ra ự c b ng các thu t toán th i gian đa th c. ứ ả ượ ằ c mô t ả ở ế . 21 bài toán NP-đ y đ c a Karp i b i khá nhi u thu t toán nh thu t toán tham lam, gi ậ ượ ầ ủ ủ ậ là m t trong ộ ể ượ ả ở ả i ư ề ổ ợ . Bài toán đ t ề ọ ượ ặ vào trong m t cái túi (v i gi ố ượ ớ ộ th Các bài toán t ệ ự ườ ươ ụ . ọ và toán ng d ng , m t mã h c ph c t p tính toán ứ ậ ộ thu tậ ả ằ quy ho ch đ ng i b ng Bài toán x p ba lô th ng đ ạ ượ ườ ế ứ cho bài toán t ng quát. C bài x p ba lô t ng quát và bài toán toán th i gian đa th c ả ế ổ NP-khó, và đi u này d n đ n các c g ng s d ng t ng con t ng con đ u là các bài ế ẫ ề ổ làm c s cho các h th ng ạ Merkle-Hellman. ơ ở Các c g ng này th ố ắ s thu t toán t ố ậ th c ra l ạ ự Phiên b n bài toán quy t đ nh c a bài x p ba lô đ ả ế ị trong th c t ự ế Bài toán có th đ thu t di truy n,… ề ậ
2. N i dung bài toán ộ
n m t hàng có tr ng l ộ ộ ẻ ộ ấ ọ ị ậ ư ộ ng và ng t ố i ứ ề ọ ượ ể ạ ng bao nhiêu đ đ t ậ ẻ ộ ữ M t k tr m đ t nh p vào m t c a hi u tìm th y có ộ ử ượ ệ giá tr khác nhau, nh ng h n ch mang theo m t cái túi có s c ch a v tr ng l ỉ ắ đa là M. V y k tr m nên b vào ba lô nh ng món nào và s l ỏ giá tr cao nh t trong kh năng mà h n có th mang đi đ ặ ứ ố ượ ượ . c ể ắ ấ ả ị
Hình 3. Ba lô
3. Bài toán x pế ba lô d ng 0-1 ạ c ch n), còn không đ c cho vào ba ượ ạ ượ ọ ượ ồ ậ ẽ Đ v t nào đ lô s là lo i 0( không đ ạ Bài toán d ng 0-1 s đ ạ c cho vào ba lô s là lo i 1 (đ ẽ c ch n) ọ c phát bi u nh sau: ể ượ ẽ ượ ư
C c đ i hóa: ự ạ
sao cho
ng và giá tr t ng ng. Ch n các đ v t sao cho không ị ươ ứ ồ ậ 4. Ví dụ Cho 8 đ v t có kh i l ố ượ ồ ậ ng t t quá kh i l v ố ượ ố ượ ọ i đa c a túi và giá tr là l n nh t ấ ủ ớ ị
ố Kh i l ng t ố ượ ễ ể i đa c a túi là: 26. ủ ặ ồ ầ ế ướ ạ ẽ
4 1 2 0 i d ng 0-1 ta s có: 6 0 5 1 7 1 8 0
ứ ươ ứ ng ng v i 8 đ v t) ớ ồ ậ ượ c ch n. ọ
ượ ượ N u bi u di n 1 l n nh t đ vào túi v1 d 3 1 1 0 T c là: v1=10011010 (mã nh phân 8 bit t ị c ch n. Đ v t 1 đ ọ Đ v t 3 không đ ượ c ch n. Đ v t 4 đ ọ c ch n. Đ v t 5 đ ọ Đ v t 6 không đ ượ ồ ậ ồ ậ ồ ậ ồ ậ ồ ậ c ch n. ọ
ượ Đ v t 7 đ Đ v t 8 không đ ồ ậ ồ ậ c ch n. ọ c ch n. ọ ượ Áp d ng vào hàm ta s đ c giá tr và kh i l ng c a l n ch n này là: ẽ ượ ố ượ ị ủ ầ ọ ụ - Giá tr :ị 100x1+ 30x0+ 250x0+ 150x1+ 50x1+75x0+ 50x1+ 50x0 = 350 - Kh i l ng: ố ượ 5x1+ 3x0 +10x0 +6x1 +5x1 +5x0 +5x1 +4x1 +4x0 = 25 (th a mãn) ỏ
CH
NG III
-
ƯƠ
Ứ
Ụ
Ả
Ề
BÀI TOÁN X P BA LÔ
NG D NG GI I THU T DI TRUY N TRONG Ậ Ế
ả ậ ề Có 3 m t hàng ti m năng: A, B, C có kh i l 1. Ti p c n gi ế ậ ề ặ ố ượ ị ươ ứ
ng ố ượ
i thu t di truy n trong bài toán ba lô ng và giá tr t B 7 3 A 6 4 ng ng C 8 5 Kh i l Giá trị
ng t ố ượ ể ứ ố Kh i l Hàm tính giá tr l n nh t: i đa ba lô có th ch a là: 13. ị ớ ấ
Đi u ki n th a mãn: ề ệ ỏ
X=0 or X=1, for i= 1, 2, …, n.
c đ a ra ta có 8 tr ng thái c a ba lô nh sau: ừ ủ ạ
T ng kh i l ng ư ổ T ng giá tr ị ổ
T 3 đ v t đ ồ ậ ượ ư A 0 0 0 1 0 1 1 1 B 0 0 1 0 1 0 1 1 C 0 1 0 0 1 1 0 1 ố ượ 0 8 7 6 15 14 13 21 0 5 3 4 8 9 7 12
i pháp t t kê các t p con đáp ng các kh i l ng t i đa ể ượ ả ố t nh t, ta li ấ ệ ố ượ ứ ậ ố
T ng kh i l ng ổ T ng giá tr ị ổ
Đ tìm đ c gi (=13) c a ba lô ủ A 0 0 B 0 0 C 0 1 ố ượ 0 8 0 5
0 1 1 0 0 0 7 6 3 4
1 1 0 13 7
ng h p này, ph ng án t ố ư ể ườ ạ ợ ườ c in nghiêng. L y đ v t 1 và 2 cho vào ba lô, kh i l i u đ ba lô đ t giá tr l n nh t là tr ố ượ ấ ị ớ ng đ t đ ạ ượ ng h p ợ ỏ c là 13( th a ươ ồ ậ c là 7. ấ ị ạ ượ Trong tr đ ượ mãn), giá tr đ t đ V n đ đ t ra: ng ph ế ẽ ấ ề ặ N u bài toán n u ra có 4 đ v t tr lên , thì s l ế Ứ ớ ố ượ ẽ ng án s tăng lên 2 l n. S l ự ỗ ồ ậ ố ượ ề ớ ố ồ ậ ớ ươ ầ ố ượ ệ ẽ ấ ớ ồ ậ ở ng ph ươ ờ ề ng án cũng s nhi u ẽ ng này s ra lên. ng v i m i đ v t s l vô cùng nhi u v i s đ v t l n. Th i gian máy tính th c hi n s r t l n đ đ a ra ể ư k t qu . ả ế ế ạ ộ ậ ể ả ữ i quy t nó theo gi ả i quy t nh ng bài toán lo i này. Trong n i dung ế i thu t di truy n ti n hóa, s đ ề ẽ ượ c ế ả ậ V y đòi h i 1 thu t toán đ gi ậ ỏ bài t p l n này, chúng ta đi gi ậ ớ trình bày ch ở ươ ả ự ụ ở ướ ủ c k t qu đúng nh t, gi ượ ế ế ư các b ể ở ạ ậ ấ ấ ở ế ệ ặ ấ ả ể ể ư ừ ậ ẹ ươ ấ i ả trên đ tìm đ ể ỏ c c a quá trình ti n hóa, ch n 1 kho ng nh ọ trong các t p con tr ng thái(qu n th ) đ đ a ra ầ đây là có giá tr cao nh t. T đó lai ghép ấ ị i thu t di truy n ề t c a c b và m . Gi ả ầ ớ ng án g n đúng v i ng sau. Thay vì tìm ki m r ng rãi nh ví d ộ ế thu t di truy n s d ng trình t ề ử ụ ậ c a các tr ng thái(nhi m s c th ) ễ ắ ạ ủ các c p t t nh t, có đ thích nghi cao nh t, ộ ặ ố đ t o ra các th h con cái mang đ c tính t ể ạ không c g ng tìm ph ố ắ ph ấ ươ ng án đúng nh t, nh ng v n đ m b o v th i gian th c hi n. ả ệ ẫ ố ủ ả ố ng án đúng nh t mà đi tìm các ph ư ả ề ờ ươ ự
i bài toán x p ba lô ậ ả ế i bài toán ba lô nh th nào? Ta ả ể ả ư ế 2. S d ng gi ử ụ Đ hi u vi c áp d ng gi ệ i ví d v bài toán ba lô d i thu t di truy n đ gi ề i đây: ể ể ti n hành gi ề ể ả i thu t di truy n đ gi ậ ướ ụ ụ ề ế ả
2.1. Kh i t o d li u ở ạ ữ ệ Bài toán: Cho b ng các đ v t có kh i l ả
Kh i l ng
ồ ậ 1 7 5 ố ượ 2 8 8 ng và giá tr t 3 4 3 ng ng nh sau: ị ươ ứ 4 10 2 ư 5 4 7 6 6 9 7 4 4 ố ượ Giá trị
ng t i đa c a ba lô có th ch a là 22. ủ ố ượ i theo gi i thu t di truy n nh sau: ể ứ ả ề ậ ả ư
Kh i l ố S đ bài toán x p ba lô gi ơ ồ ế Đi u ki n ch m d t c a s đ là: ề ấ - ứ ủ ơ ồ ệ 90% các NST c a dân s có cùng đ thích nghi. ố ủ ộ
ng dân s ng u nhiên ố ẫ ố
6 1 0 1 0 0 0 7 0 0 1 1 0 0 T. KL 24 19 22 21 16 15 T. GT 19 20 28 11 18 15 2.2. Mã hóa d li u. Kh i t o s l ở ạ ố ượ ữ ệ Ch n dân s là 6 v i các giá tr ng u nhiên. ị ẫ ớ ọ 4 1 0 0 1 0 0 v1 v2 v3 v4 v5 v6 3 0 0 0 0 1 1 1 0 1 0 1 0 1 2 1 1 1 0 1 0 5 0 1 1 0 1 1
2.3. ủ ỗ ế ộ Tính đ thích nghi c a m i NST ủ Cho pop-size =6 Xác su t lai ghép = 0.67 ấ Xác su t đ t bi n = 0.1 ấ ộ Tính đ thích nghi c a m i NST ỗ ộ ủ ộ ợ Chúng ta tính toán đ thích nghi c a m i nhi m s c th b ng cách t ng h p ỗ ể ằ
t quá kh i l ắ ả ằ ủ ồ ậ ố ượ ế ố ượ ơ ng c a nhi m s c th l n h n ắ ượ c ễ ễ ể ủ ổ ng c a ba lô ị ủ ủ ượ ể ớ ng c a ba lô thì m t trong nh ng bit c a nhi m s c th có giá tr là 1 đ ắ ị ộ ơ ồ ủ c ki m tra m t l n n a. Đây là m t s đ c a c và nhi m s c th đ ng cho phép. N u kh i l ữ ể ễ ả ố ượ ủ ộ ầ ữ ộ ể ượ ễ ắ các giá tr c a các đ v t có trong ba lô, trong khi đ m b o r ng kh i l không v kh i l ố ượ đ o ng ượ ả thu t toán tính đ thích nghi. ậ ộ
Hàm tính đ thích nghi: ộ
Ví d :ụ
v1 v2 v3 v4 v5 v6 1 0 1 0 1 0 1 2 1 1 1 0 1 0 3 0 0 0 0 1 1 4 1 0 0 1 0 0 5 0 1 1 0 1 1 6 1 0 1 0 0 0 7 0 0 1 1 0 0 T. KL 24 19 22 21 16 15 T. GT 19 20 28 11 18 15
ng t ả ố ủ i đa c a ba lô có th ch a ể ứ ượ ả c b ng dân s m i( th a mãn ố ớ ỏ ố ượ ụ ủ i đa c a ba lô). ng t ổ ề ủ ố
Trong b ng: v1 có T.KL = 24 > kh i l Đ i 1 bit 1 thành bit 0 trong các m c c a NST v1, ta đ đi u ki n kh i l ệ 1 ố ượ 2 3 4 5 6 7 T. KL T. GT
v1 0 0 0 1 0 1 0 16 16
v2 1 1 0 0 1 0 0 19 20
v3 0 1 0 0 1 1 1 22 28
v4 1 0 0 1 0 0 1 21 11
v5 0 1 1 0 1 0 0 16 18
v6 1 0 1 0 1 0 0 15 15
ộ ủ ừ
Đ thích nghi = T.GT c a t ng NST. Eval(v1)= 16 Eval(v2)= 20 Eval(v3)= 28 Eval(v4)= 11 Eval(v5)= 18 Eval(v6)= 15 Ta th y đ thích nghi c a v3 l n nh t và c a v4 y u nh t. ấ ủ ủ ế ấ ấ ớ
gi ng nhau < 90%. Ta ti p t c b ỉ ệ ố ế ụ ướ ế l a ch n ng u nhiên 2 NST, ự ẫ ọ đây ta có nhi u cách l a ch n. ộ 2.4. Ch n l c ọ ọ T l ệ ự ự ề c ti p theo là ọ vi c l a ch n ọ ở ọ ự ớ - L a ch n v i bánh xe roulette. Bánh xe Roulette là m t ph ươ ng pháp đ n gi n c a vi c th c hi n l a ch n đ ệ ả ủ ự ọ ộ ỗ ươ ứ ơ ầ ủ ộ ượ ầ ệ ự ộ ớ ủ ố i NST nào thì s đ ộ ầ ng ng. M i NST là m t ph n c a bánh xe roulette, đ l n c a ph n ẽ ượ c c quay N l n, trong đó N là s các NST có ạ ừ c th c hi n theo cách sau: ng pháp này có th đ i. Ph thích nghi-t tùy theo đ thích nghi. Các bánh xe đ ộ trong dân s (N = Size). Sau m i vòng xoay, bánh xe d ng t ố ghi l ươ ỗ ể ượ ự ệ ạ
ổ ộ ầ ủ
ỗ ọ ọ
T ng đ thích nghi c a qu n th : ể F = 16+ 20+ 28+ 11+ 18+ 15 = 108 Xác su t ch n l c pi c a m i NST vi (i= 1..6) là: ấ ủ 16*100/(16+20+28+11+18+15) p1= 20*100/(16+20+28+11+18+15) p2= 28*100/(16+20+28+11+18+15) p3= 11*100/(16+20+28+11+18+15) p4= 18*100/(16+20+28+11+18+15) p5= 15*100/(16+20+28+11+18+15) p6= = = = = = = 14,8 % 18,5 % 25,9 % 10,2 % 16,7 % 13,9 %
ị ỗ ấ ủ
ể ớ ầ ọ ư ầ ị ẫ
Các v trí sác xu t qi c a m i NST vi (i=1…6) là: q1= 14.8% = 0.148. q2= 14,8+ 18.5 = 33.3 % = 0.333. q3= 14,8+ 18.5+ 25,9 = 59.2% = 0.592. q4= 14,8+ 18.5+ 25,9+ 10,2 = 69.4 % = 0.694. q5= 14,8+ 18.5+ 25,9+ 10,2+ 16,7 = 86.1 % = 0.861. q6= 14,8+ 18.5+ 25,9+ 10,2+ 16,7+ 13,9 = 100% = 1.000. Gi ả ử đ ượ NST cũ S l n quay bánh xe i thích ạ s quay 6 l n bánh xe Roulette, m i l n ch n 1 NST cho qu n th m i, và đ t ỗ ầ c các giá tr ng u nhiên trong kho ng t ừ ả V trí r i ơ ị [0,1] nh sau: Gi ả NST m iớ ố ầ
0.277 0.148<0.277<0.333 V2 V1
0.521 0.333<0.521<0.592 V3 V2
0.811 0.694<0.811<0.861 V5 V3
0.111 0<0.111<0.148 V1 V4
0.498 0.333<0.498<0.592 V3 V5
0.602 0.592<0.602<0.694 V4 V6 L n 1ầ L n 2ầ L n 3ầ L n 4ầ L n 5ầ L n 6ầ
Nh v y ta s có qu n th m i là: ể ớ ư ậ ẽ ầ
4 5 6 7 1 2 3
0 1 0 0 NST cũ V2 NST m iớ V’1 1 1 0
0 1 1 1 V3 V’2 0 1 0
0 1 0 0 V5 V’3 0 1 1
1 0 0 1 V1 V’4 1 0 0
0 1 1 1 V3 V’5 0 1 0
1 0 0 1 V4 V’6 1 0 0
Lai ghép
ể ớ ữ ầ ấ ề ấ ử ụ ẽ ố ớ ế ố ẫ ộ 2.5. S d ng lai ghép, lai nh ng NST có trong qu n th m i. Vì xác su t lai là pc=0.67 nên s có nhi u nh t là 6*0.67= 4 c p NST tham gia lai ghép. Ta ti n hành theo cách: ế Đ i v i m i NST trong qu n th m i, ta phát sinh ng u nhiên 1 s r thu c [0,1], n u ỗ r <0.67 thì NST đó đ ầ ọ ượ ạ Gi ặ ể ớ c ch n đ lai t o. ể s các s ng u nhiên là: ố ẫ ả ử
NST R ng u nhiên
V’1 ẫ 0.32
V’2 0.95
V’3 0.55
V’4 0.44
V’5 0.32
V’6 0.78
ả ẽ ượ ể ọ c ch n làm các NST đ lai ghép ể ẫ Theo b ng trên thì v’1, v’3, v’4, v’5 s đ Ta g p 2 c p NST 1 cách ng u nhiên (v’1, v’3); (v’4,v’5) đ lai ghép. ế ố ẹ ế ệ ể ạ ặ ặ ộ T 2 c p b m v2 và v3, ta ti n hành lai ghép đ t o ra các th h con cái. ừ V’1:
1 1 0 0 1 0 0
V’3:
0 1 1 0 1 0 0
V’4
1 0 0 1 0 0 1
V’5
0 1 0 0 1 1 1
Ta có r t nhi u ki u lai ghép đ t o ra th h con m i, ví d nh : ụ ư ể ạ ế ệ ề ấ ớ ể ể ơ ệ ề ẫ ố ọ ị - Lai ghép đ n đi m c t ắ . Ch n 1 s pos ng u nhiên( pos) là v trí lai ghép, đi u ki n: pop =[1,6]. Ta ch n pos ọ c a c p 1 là 3, c p 2 là 4 và ti n hành lai ghép ủ ặ ế ặ
V’1:
1 1 0 0 1 0 0
V’3:
0 1 1 0 1 0 0
Con cái:(V’’1,V’’3) pos =3 V’’1
1 1 0 0 1 0 0
V’’3
0 1 0 0 1 0 0
V’4
1 0 0 1 0 0 1
V’5
0 1 0 0 1 1 1
Con cái(V’’4,V’’5) pos=4 V’’4
1 0 0 1 1 1 1
V’’5
0 1 0 0 0 0 1
Còn 1 s ph ố ươ ng pháp n a có th s d ng nh : ư ể ử ụ ữ
- Lai ghép hai đi m c t: ể ắ
V’1:
1 1 0 0 1 0 0
V’3:
0 1 0 0 1 1 1
Con cái:
1 1 0 0 1 1 0
0 1 0 0 1 0 1
- Lai ghép đ ng nh t ấ ồ ặ ạ Có m t m t n sao chép là m t chu i nh phân có chi u dài b ng chi u dài ỗ ề ề ằ ộ ộ ị
ự ị ộ ệ ớ ạ ị i v ị M t n đ Xây d ng NST m i: Duy t qua m t n , bit có giá tr m t thì sao chép gen t ặ ạ NST cha sang con, bit có giá tr 0 thì sao chép t ừ ố ớ ừ c phát sinh ng u nhiên đ i v i t ng c p cha m . ẹ m . ừ ẹ ặ ặ ạ ượ ẫ + NST. + trí đó t + V’1:
1 1 0 0 1 0 0
V’3:
0 1 0 0 1 1 1
v2, bit 0 t ặ ạ ừ ừ
1 0 0 0 M t n ( sao chép bit 1 t 0 1 v3) 1
ệ ặ ạ ế ủ ế
Con ( Duy t các bit c a m t n , n u bit 1 thì sao chép bit c a cha sang con, n u bit 0 thì sao chép bit c a m sang con) ủ 0 ủ ẹ 1 0 1 1 1 1
- Lai ghép s h c ố ọ NST con đ ượ ạ c t o thành b ng cách th c hi n m t phép toán logic nào đó nh ệ ự ộ ư + ằ AND, OR, … v i c p NST b m . ố ẹ ớ ặ
V’1:
1 1 0 0 1 0 0
V’3:
0 1 0 0 1 1 1
Con( Dùng phép or)
0 1 0 0 1 0 0
ử ụ ể ắ ắ ẫ ơ ị c 4 con m i. ẽ ạ ượ ớ Trong bài toán, chúng ta s d ng phép lai ghép đ n đi m c t, v trí c t là ng u nhiên, ta s t o đ V’’1
1 0 0 1 1 1 1
V’’3
0 0 0 1 0 0 1
V’’4
1 0 1 1 1 1 0
V’’5
0 0 0 0 0 1 1
i s là: ế ở ể ệ ạ ẽ ầ
Các NST s đ NST ẽ ượ 1 c thay th b i các con c a chúng.Qu n th hi n t ủ 6 2 3 4 5 7
1 V’1 0 0 1 1 1 1
0 V’2 0 0 1 1 1 1
0 V’3 0 0 1 0 0 1
1 V’4 0 1 1 1 1 0
0 V’5 0 0 0 1 0 1
1 V’6 0 1 0 1 0 0
ự 2.6. Đ t bi n ế ộ c th c hi n trên 1 bit c a NST. Bit đó s đ ế ượ ệ ấ ộ ế c đ i t ẽ ượ ổ ừ ấ ề ẽ ể 0 sang 1 ố ề ẽ ộ ầ ư ơ ộ ộ ế ỗ c đ t bi n. M i bit có c h i đ t bi n là nh nhau nên ta phát sinh ng u nhiên ượ ộ ớ ế ị ế ả ử ượ ộ ị
Phép đ t bi n đ ộ ủ 1 sang 0. Xác su t đ t bi n là pm = 0.1 .S có nhi u nh t 1/10 s bit đ ho c t ượ c ặ ừ đ t bi n. Có t ng công 7*6= 42 bit trong toàn b qu n th nên s có nhi u nh t 4,2 ổ ấ ế ộ bit đ ế ẫ 1 s r v i r thu c [0,1]. N u r < 0.1 thì ch n bit đó làm v trí đ t bi n. Ta Phát sinh ọ ộ ố s xác đ nh đ ng u nhiên 42 s thu c [0,1], gi ị ộ ố ẫ V trí bit ị
ộ c 4 v trí đ t bi n nh sau: ư ế Sô ng u nhiên ẫ 0.04 11
0.07 20
0.09 26
0.02 34
Qu n th sau khi đ t bi n. Nh ng v trí đ t bi n s in đ m ế ẽ ữ ể ế ậ ầ ộ ộ ị
7 3 4 5 NST 1 2 6
1 0 0 1 V’1 1 1 1
1 0 1 1 V’2 0 1 1
0 0 0 1 V’3 0 1 1
1 0 1 0 V’4 1 0 1
1 0 0 0 V’5 0 1 1
1 0 1 0 V’6 1 0 0
ả ậ ả ượ ư ề ế ụ ế ệ ể ặ ế i thu t di truy n. Sau khi k t thúc vòng l p k t ế ệ ủ c 2 t o qu n th và ti p t c ki m tra đi u ki n. N u th a mãn ỏ ể i khi i u, n u không s ti p t c th h ti p theo cho t ớ ẽ ế ụ ế ề ế ệ ế ướ ế ẽ ừ ế
Ta v a hoàn thành 1 th h c a gi ừ c đ a lên b qu đ ạ ầ thì s d ng đ a ra k t qu t ả ố ư ư th a mãn đi u ki n ệ Ki m tra đ thích nghi c a qu n th m i so v i qu n th cũ ầ ủ ể ầ
6 ỏ ể NST ề ộ 1 ể ớ 4 ớ 5 2 3 7 T.KL T.GT
1 1 V’1 1 1 0 0 1 24 33
1 1 V’2 0 1 0 1 1 32 30
1 1 V’3 0 1 0 0 0 18 24
0 1 V’4 1 0 0 1 1 27 20
0 1 V’5 0 1 0 0 1 18 21
0 0 V’6 1 0 0 1 1 21 11
ộ ỏ ẫ ổ ng không th a mãn(<22), đ i ng u nhiên 1 bit 1 thành bit 0 ẫ c bôi đen, ta s có T.GT và ẽ ượ Tính đ thích nghi: V’1, V’2,V’4 có kh i l ổ ố ượ trong m i NST đó. Nh ng v trí đ i là ng u nhiên và đ ị ữ T.KL m i là: ỗ ớ
NST 1 2 3 4 5 6 T.KL T.GT 7
V’1 1 1 0 0 1 1 20 29 0
V’2 0 1 0 0 1 1 22 28 1
V’3 0 1 0 0 1 1 18 24 0
V’4 0 0 0 1 0 1 20 15 1
V’5 0 1 0 0 0 1 18 21 1
V’6 1 0 0 1 0 0 21 11 1
ổ ộ ủ ể ộ T ng đ thích nghi là : F= 29+28+24+15+21+11 = 128 > 108 c a qu n th cũ và đ ầ thích nghi cao nh t 29 > đ thích nghi cao nh t c a qu n th cũ (28). ấ ủ ể ầ ấ ộ
K T LU N
Ậ
Ế
c trong bài t p l n: ậ ớ
i thu t di truy n. ả ề ậ ế ằ ộ Ứ ụ ề ế ạ i thu t di truy n. i quy t m t bài toán b ng gi ừ i quy t bài toán ba lô d ng 0-1. ậ ề ả ả ề ư i quy t đ Nh ng v n đ gi ế ượ ề ả ấ ữ i thu t di truy n. - Hi u v gi ề ả ề ậ ể c đ gi - Tìm hi u v các b ể ề ướ ể ả i thu t di truy n trong t ng bài toán. ng d ng c a gi - ậ ả ủ - Bài toán ba lô và h ng gi ướ i m t bài toán ba lô c th theo gi - Gi ộ Nh ng v n đ ch a gi ả ữ - Tài li u tham kh o ít nên ki n th c v gi i thu t di truy n và bài toán ba lô ả ụ ể i quy t đ ế ượ ế c: ứ ề ả ả ậ ề
ế c ch n l c còn khá nhi u ph ng pháp ch n l c nhóm ch a l y ví ọ ọ ọ ọ ư ấ ươ ề
ủ ả ầ ả ẫ ng d n và bài gi ng c a th y, chúng em đã hoàn thành b n báo ậ ủ ứ ụ ề ề ả
i di truy n trong bài toán x p ế ấ ậ ớ ỡ ể ề ấ ệ còn h n chạ - Trong b ướ c d đ ụ ượ Nh vào s h ự ướ ờ cáo bài t p l n “Tìm hi u và ng d ng c a thu t gi ậ ớ ệ ba lô”. Trong bài t p l n còn nhi u thi u sót, mong th y giúp đ đ hoàn thi n ế báo cáo h n.ơ
TÀI LI U THAM KH O
Ả
Ệ
Ts. Nguy n Đình Thúc, ễ Trí tu nhân t o- L p trình ti n hóa . ậ ế ệ ạ ấ ả Nhà xu t b n
http://vi.wikipedia.org/wiki/Gi%E1%BA%A3i_thu%E1%BA%ADt_di_truy
http://vi.wikipedia.org/wiki/B%C3%A0i_to%C3%A1n_x%E1%BA%BFp_ba_l
PC Chu , JE Beasley. A Genetic Algorithm for the Multidimensional Knapsack [1]. Giáo d c.ụ [2]. %E1%BB%81n [3]. %C3%B4 [4]. Problem
