Tài liệu Giải thuật di truyền + cấu trúc dữ liệu = chương trình tiến hoá

ĐẠI H Ọ C Q U Ố C GIA H À NỘI TRƯỜNG ĐẠI H Ọ C KHOA H Ọ C T i ; NHIÊN ..................................... - GIẢI THUẬT DI TRUYỀN CẨU TRÚC DỮ LIỆU = CHVOMG TRÌNH TICN HÓfl <,// d u -l i HỔ SĨ ĐÀM, TRẦN MINH CHÂU, PHẠM VIỆT THẮNG HÀ NÔI -1999 Z B I G N I E W IVIICHALEV. I E Z GENETIC ALGORITHMS + DATA STRUCTURES EVOLUTION PROGRAMS S p r i n g e r 1992 u. Chư«mg mữ duu Trong vòng 3 0 nãm trò lại đ iy , có một sự quan lim r.gày càng cao ;ới các chuơng irình giãi quyết các bài loán dựa ưôn các nguyồn lý vố tiến hoá và d ì truyén; các hệ này duv trì mỌL tạp hợp các lừi giài có ihi, và ihực hiỊrv chọn Lọc dựa irdn dộ ihích nghi cùa lừns cá ih>i. rổi áp dụng các Dhép biín d ổi gicn. M ội trong các dạng của các hệ trốn là lóp J-c Chiến lược T iín hoá, lớp này g6m các Ihuật toán bấl chuức c i c nsuyẻn lý liín hoá irona lự nhiỗn để giàĩ cáo bài toán lối lAj hoá có ibam số [3 1 9 ,3 4 8 ]. l-orgel là m ội phưưng pháp t'im kiốm ưong không gian "Lập Irình Tlõ'n h oá” cúa các m áy hữu hạn nhò. Kỹ ihuỊl ■‘lìm kiii'fn rải rác” cùa G lovcr duy trì m ội lộp các điểm ư a cứu và sinh ra cá thể con bảng các lổ hợp luyiin lính có irọny số. M ộl loại h Ị ú ín hoá k h á i là các Thuậl ỉoán Di ư u y in Hà Ian(lS8Ị . Năm 1990. K oiu [231] dã đtí xual m ộl loại hộ liín lioá, L4p trình Di L'uyón. lím kicm chương innh mdy lính tồi n h íl cho viủc gidi một bài lodn nào dó. ♦ Ta dùng m ột ihuẠi naữ chung, Chương irình Ticn hoá (E P), ch o m ọi hỏ tiín hoá k é cà các hệ LỈã ùược liột kẻ ở trân ). N ội riung cùa EP dược irình bny irong hình O.I. EP ỉ i một ihuẠl loán xác suủì duy ưi một q u ìn ihể cd ihể, P(t)... lại vòng lặp liiữ ĩ. M ỗi cá ihò Jiú diỌn m ỏl lừi giài c ó iliO’ cũ:i bài loán dã cho. T ron g EP, cá ihể dược biẩu ihị bảiiíi mộ: cấu irúc dữ !iỏu (cõ Ihô phứo lạp) s. M ỗi lời ciải x \ được Jár.h giá '.heo độ :hích nahi lỉiòi irưOrng cùa lừi £Ìài đó. Sau Jó, n;ội quán ih i m ứi (vò n g lập i + l) được xáv dựna Dằng cách chạn các cá thể có độ thích nghi cao (bước chọn lọ c). M ột sồ’ cá của quán ỉhii mứi bị biốn đôi (bước biến J ôi) bầng cách áp dung các phéo biến d ổi gien đỏ tạo ra các lòi iiâ i mói. Có nhiổu phép biến đổi; m, íđột biến) tao ra m ột cá thể mới bầng m ộl sửa đổi r.hỏ irèn mỌl cấ Ihổ (m, ; s -> S), vù phiíp bii'n cJdi bậc uao hưn Cj (íja o JÒi ch iu ) lậO ra >;ác cá ihể mới bang cách k íl hợp các phán cùa nhi>íu cá Ihô (lừ hai irờ lốn) (c^: Sx..xS —* S). Sau mộl sđ Ih.ồ' hộ, chương Irình sè hội lụ - với hy vọng rằng cá ihể lốt n h ít sẽ đại dtện cho một lời 2 Ìài gán lối ưu. p ro ced u re cvolution_proeram begin t< -0 khời lạo P(ỉ) dánh ciá P(t) •• w h ile (.noi dícu_kiiỊn_dừnc ) do bcyiri I » - 1+1 chọn p(0 í ừ P ( t - l) , ihay dổi P(0 đánh giá P(t) end H ìn h 0 .] . C ẩ u in ic chươiiỊỉ iriiilt tiế n h o á X ét VÍ dụ sau. Giả sừ la cần tìm m ộl đổ ihị ihoà mãn m ột số' điổu kiện (.chảng hạn tìm mộ: topo lối ưu cho m ội m ạng truyổr ihỗnc ihco các tiôu ch í vổ chi phí truvổn tin, cíộ ùn cặy.v.v..). M ỏi cá thổ irong EP này biổu thị m ột lời giải có ih ể của bài toán, nghía là. mỏi cá thổ đại diộn cho m ột đổ Ihị. Tạp hạp ban đáu F(Q) cữa các đổ thị (được khời lạo ncảu nhiôn hoặc Ih k iì quà cùa mội quá irình hcurisiic: nảo dó) là diẩm xuú’i phá; (/= 0 / của EH. Hàm đánh giá ihườnc dược cho săn - nổ k íl hợp các yôu cáu cùa bài loán. Hàm đánh ciá trà vé độ thích nchi cùa m ỗi dổ ihị d ỉ phăn biột giữa các cá Ihể tôì và xấu. M ội số phép (iộ: biỂn cổn được ihiÊi k ế đổ b iín đổi m ội đổ Ihị. Các phép irao cỉổi chéo cũna cẩn thiối cho việc kết hợp cấu irúc cùa hai (hoặc nhiổu hơn) đổ thị Ihinh m ộl đ ổ thị. Các phép biên dối này Ihườns phài phù hợp vái lừna bài loán cụ thể. V í dụ, nếu la cán lìin các đíi ihị livi: thỏng và khỏnc có chu irình (dố Ihị dạnc cay), một phcp đột bicn cổ ihc xoá m ỏi cạnii của đổ ihị và Ihỗm một cạnh m ói đc nối hai dổ thị con ròi nhau. Ta c ó Ihể dùnc m ội cách k h ij là ihiết k ế m ộl phép đột biến khốnc phụ Ihuộc bài loán và đưa các điổu kiện cùa bài loáii vào Irons hàm dánh iiìá đò ino hàm dánh giá irà về £Ìá Irị ihẩp ch o các dổ ihị khỏn c phiìi cây. Ta tháy, có thể xây dựng nhiốu EP cho một bài loán. Các EP đó c ó Ihể khác nhíiu vé nhici: mật: cấu trúc dữ liệu để biểu d iỉn m ột cá thổ, các phép biến đổi gien, cách khừi lạo quấi. ihé ban dẩu. và các Iham sô' (kích thước quẩn Ihể, xác suâì áp dụnp các phcp bicn dối v.v..). Tuv nhiẾn, ch ú n s cổ mộ’. nguyÊn lý chunc: quần Ihổ trải qua một sô' bicn đổi. \iư on e quá irinh liốn hoá đổ, các cá (hổ đấu iranh đi' sinh lổn. Nlìư clã nói ữ uủii. EP kliOiiỊi phài lù ý lưõiií: m ới mil nó tỉũ dược tiùn*; dốn troni; vùnc nãm nav. Tịonu khoàiis lliòi uian đó, nliiồu lìiỊ licn hoá khúc nhnii đã được phá: b'iwi:. Nhưnc ironc cuởn sách n jy , la chi bàn Vií sự tươnc ii6iic giũu các khuỏn mfiu Ja óạni: cú; các EP. Ta s c t à n Vii cách xáy dựni; m ội EP ch o m ội lớp các bài loíin cụ Ihố. các cấu Irt.v dữ liộu ihích hợp (có lỉii plìứ: lạp) dùnc dc bicu d iĩn n h iỉm sác Uk (NST), và mội lập m j rộna các loán lữ cicn, ưong khi các GA c ổ óicii cJiinc các xảu nhị phân có dộ dji khùnc đổi (làm NST, cấu ưúc dữ liộu S.I cho các c í ihể và hai plicp bicn đổi: đội biốn nhị phãri vìi ưao c5ổi chéo nhị phùn. N ói cácn kiiác. c i’u irúc c ù u m ộ l GA cũng giônu cấu U'úc của mộ! EP (hình 0.1), các dicm khác biột ẩn dưứi láng ihấp bon. Trong các EP, NST khỏii!: nluVi ihiốl piiài dược b iiu d iỉn hòi x£iu nhi piiiin, và quá Iiình bicn dổi liicn ban t:6m c;j ưác lojii lừ gicn khác pliù hợp với cấu irúc và bài toán dà clio. Đ ó cũng khônc hoàn loàn lù mftl hướ.ic m ới. Nàm 1985, Di; Jong v iíi [84j: • “...Ta phài làm gì ncu biẩu'3iỉn lự nhiòn nhấi của các phán lử irone không gian « lìm k iím lại là các c íu u ú c dữ liiỊu phức tạp hơn như màng, cây, dổ ihị có hướng, v.v...T a có nỗn “ ỉu y ín lính hoá” chúng thành m ột biổu diỗn xâu, hay có những cách định nghĩa lại irao đổi chéo và dột biốn m ột cách sáng tạo để có Ihii dùng trực tiiip các cấu trúc dó. Tôi chưa ih íy m ột tiến bộ nào U'ong lĩnh vực n ày...” Có lẽ b iiu diỏn lự n h iin của mộl lời giùi cộng vứi mộl họ các loán lừ gicn khá hữu dụng trong việc ước lượng các lời giài cùa nhiiỉu bài loán. Cách úếp cận dùng khuôn mả'j lự nhiồn này ( E P ) , nhìn chung, là mộl hướng giãi toán hứa hẹn. Bên cạn[\ các khuồn mảu úốn hoá khác (chiốn lược tiín hoá, EP. lạp trình gicn ), các nhà nghitìn cứu vẻ G A dã líiTi hiiiu các bìiiu diỏn gicn khác, chánn hạn danh sách Ihứ lự (clio bãi xếp ba lô), em bedded lisl (ch o bùi xếp lịch sàn xuấi). vajiablc-olem enl lisl (bài Ihiết k ế mạch bán uán). Mưừi nãm UV iại đ ay dã ghi nhận i;hiổu biốn dạng ciia GA tuỳ Iheo dạng ứng đụng. Các biến dạns g ô m có: các dãy d ọ dài không cổ' dịnh (các phán lừ của dãy ià diổu kiỌn nhân ouã), các cấu trúc phức tạp hơn XÃU nhị phản (v í dụ ma ưủn), và cúc loán tử gien đuợc ihay đ ổ i phù liijp với diổu kitỊn bài icán. Trong [285] c ó miỏu ù m ội GA dùng b a c k - D r o p a g a t i o n (một kỳ thuậi huả’n luvồii mạng nơ-ron) làm toán lừ c ù n s vói hai phương pháp ưao đổi chéo và dôt b iín dã dược cài liốii CỈIO phù hợp với m ạng nơ-ix>n. Davis và Ccom bs [65,761 c'il giói iliiiỊu m ội G A dàm nhiửm niỏl giai đoạn trong quá irình ihiốt k ỉ mạng ch u yin mạch (packet-sw itching network); biểu diễn nhị phân khôna được dùng, GA r.ày dùng 5 loán tử gien (số, ihống kẻ, cơ sỏ ư i thức). Các loán tử này khác xa trao đổi chéo và đột biế:i nhị phân. Phan lớn các nhà nghiỏn cứu d i cài Uốn G A bàng cách dùng các bi«ỉu điỗn khững lliuộc dạng x iu . huv lliiốl k í các loũn lử gicn dục biỌ[ dá pliù hợp với bili loán cần giãi. N hiéu ihử ngiùỌm da đạna đã dược x i y dựng cho các bài loán cụ thể, đơn giản là vì khó áp dụng irực ìiốp G A chuán cho m ột bài toán và một s6 Ihay dổi ư on s cẩu Lnic NST là c£r. ihiỏì. Trong cuỏn sách này, lác sià dã cố ý lách ra khòi G A chuẩn dùng xáu nhị phàn: cấc lấc giả dã tìm kiếm các cấu trúc dữ liệu tốt hơn và các loán từ gien thích hợp vói các cấu trúc nàv đ ể áp d ụ n s ch o nhiổu dạng bìii. Bằnc cách thừ nehiộm các c íu Uiíc và các phóp b iín dổi đó, chúng lôi đã Ihành lỊp được các hệ ờ mức cao hơn G A kinh điển. M ội cảu hòi dược dặt ra: m ội chiến !ược tiến hoá có phải là mỌi Ihuật loán eien hay không. Đ ể iránn viộc phàn loại các hộ liến hoíi, la gọì chúne m ội cáclì dơn eìàn là các “chương trình Liín hoá" (EP). Tai sao c h ú n t u lại rời bó G A d ì hưóna lới các chưone irình lìín hoá ir.ểm dèo hơn? Cho dù dă được dưa vào lý ihuvởi một cách đẹp đc. G A khôns đem lại ứng dụng ihànli côna trong nỶiiểu ỉĩnh vực. Có lẽ sự ih íl bại và thành côn g của G A có cùng một nguyỏn nhủn chính: G A khỏnj; phụ Ihuộo vào bài loán. M ột irong những hộu quiì cùa sự ngăn nắp cùa G A (lính khôna phụ ihuộc) Ih sự bả't lực củ:i G A khi xử lý các ràng buộc không tẩm thường. Như dã nói ờ trồn, N ST irong hẩu hốt các G A dểu là các xủu nhị phan. M ột v ín để qưan trọng cán dược xét khi ih iíi k ế biổu d iẻn lC;i siả i của m ội bài loán dó lù cách xừ lý các rar.s buộc cùa bài toán dởi vái các lời giải. Như dược trình bày irong [74]: "Các diòu ki-Ịn ràng buộc có ihể dược xử lý bảng cách phạt diếm nặng cúc cá thỏ không Ihoà mãn, phạl điổm vừa phải, hoặc xây dựng cách giài mã biẩi' d iễn £Ìen sao cho Iiánh dưực vi(Ịc sinh ra các cá ihổ khône hợp liỊ. M ỏi cách đổu có ưu diCm và nhược d iìm . N íu tích hợp viộc Dhạt diểm vào ihủ lục đánh aiá tronc khi miiin xác dịiih có nhiéu khà nânc sinh ra cá thò khống họp !Ọ. rùi ro cùa ta l i G A r ít c ó thii dùne píián lứn Ihời cian cho viộc dánh eìá các lời ciài khống hơp lộ. Hơn nữa. oòn c ó thè xdv ra trưừne hợp khi m ội cá Ihì hợp lò được ùm th ív , nó sẽ đẩy các cá Ihì khác ra khòi quan the và cuẩn th i sẽ hội lụ lai J<5 x à khònu liếp tục tìm cdc lời iidi lốt hcrr.. Bởi vì dườns dỉr. d ín các lài giãi hợp lộ khác cán sinh ra cdc cá Iliõ k hôn s kợp lệ để làm các cấu ưúc chuyen tiốp. Sự phại diiỉm vì vi pliam các đidu kiện làm cho các cấu ỉrúc iruna ciun khó c ó i!iỏ lái sình. Nếu phại di(ỉm nỉiẹ, hộ có the phái iriìn ciíc cá ihể khủri: ihcù mãn các ràng buộc nhưng lại úuợc cỉánh 2 iá cao hơn các cá Lhể ihoà màn. Nếu dùiig m ội bộ aìài m i ciio ihù lực dánh s!Ìá đồ irính tạo ra các cá i\\á k iiõ n i iìCTp iộ lừ các N ST m ội cách tUỏnii minh. Ihuội [oán ihườns đòí iiòi khối lượng lính loáa I'ũ't lứn. Hưn nữa. piùi mọi ran i buộc CỈKI đổ bài J>iu Jỏ ih i ,\ừ 'iV úó JÙI1;Ị Uico cácli Iiiiy." (M ục 4 .5 sẽ i;iứi ilii^Li ví c!ụ Vi5 các brt uiài mã. các Uián sử;i v.'i nu't vài Ii.'iiT. phạt đ iểm áp clụnc cho bài loón xốp ba lô). IVone lẠp uììih tiín iioá. ván xiá íhũà x ã n c ic r jn c buộc oó m ỏt sào :iú i ;<;úw. D ó khõr. phài viộc lựa chọn một hàm dánh cid vói mội sỏ' cách phại Jien:. mà l i vice ,*pon bicu uiồ: NST lố l n h ít cúa các lời íiiài cúa bài loán cù n s vái các lodn íứ cicn ilìoù mãii m ọi ràiK buộc. M ội kián lử cicn iliườns: iruvổn cau liTÌc đặc irưnc nào đó lừ ohu ir.j sa n s con.. Do vậy. biổii dicn cấu UTÌC dóne vai irò quan :rọnc Irant: việc định nchla các loán lữ EÌcn. Hiíỉ nữa, cá c cấu irúc biiiu di3n khác nhau thi'ch hợp vói biếu di-ỉn riinc buộc :hco các hướ:u khác nhau. Đic-U nùy iìini vj'ii J(í pl-.úv lạp him n.ữa- B iiu diứr. NST và tOvin lử liicn ànl. hưỏne iản nliau; có iõ mọi bài loán dcu cùn dược phủn lích kỳ ũùnc (ici có ;hừ’ lìm r.i bic'. di>5n thích hợ]> và các toán tử liicn phù h(ip vói cách biiíu diỗn đó. G lover, trone niỉhiiỉn cứu vé mẠt bài toán phức tạp v é cấu h\nh bàn phím [ l - l l] . dã viối; # "M ặc Jù iiwh luCu quà cùa gíùi Uiuậl đi Uuvéiì r íl Ììú á ) hỢỊ) cho hùi luân cau lùiỉi^ bùn phím , biéu cliỗn xiiu nhị phiin vỉi cdc loán ỉù U*uv6n Ihrtng kh^ni: phù hiTp Vi*?; các diẻu kiện của bùi loán. V ỉ dụ, n i u bỉéu dí6n m ỏi thành phíin của m ội bàn phím 4 0 phím bầng 3 bii, dẻ ihấv chĩ c ó m ột ư on g sổ ĨTÌỎÌ bộ cấu in íc 1 2 0 b il bấl kỳ là biSu d iỉn m ội cấu irúc hợp lộ.” T rong [8 8 ], D e Jong dă vi6i v é bài loán nsười đưa ihư như sau: '*Nốu (lùuị; các \kú \ ì lử iìíio dổi chciỉ vò dột biCỉỉ kiiih ỏ\6i\. GA SC ù m kiòỉ)^ ir&ii m ọ i lổ hựp cùa củt: llùn h phố, iroíìg khi dó, la chi củn quun lủm i là m ôl "ìài ilỉuậl Ji truviín? D uy irì quán llvJ các lời i:iỳi c ó thò? Bicu d iỉn nhị phùn c ja cdc lừi aiãi? Qud 'jình chọn ỉọ c dựa vào J ộ iliícli nchi? Cúc iv^án lử '.úi k íl h(Tp? Sự tồn lại cùa Định Iv Mủu ? G ià ihuvốt Viỉ các kl'o’i sỏ ? H jy lấi cá r.liữim Jitiu ircn'’ C lìươns líìíah liốn hoá cho bài loán naưòi đưa Ihix với b iju didn vcclor sỏ’ tự tiiiiủn và ioún lừ P M X icliư ơ n s 10) có phài ỉà m ội eiài iliuật di iruycn h av khỏnu'.’ C hươnc trình licn hoá ch o b ii loán 2 Ìao ihôna vứi biiìu dicn ma irận và phép trao đ ổi ch éo s ố h ọc c ó phái là m ội aiài thuậi J i iruyổn hay không? T ronc cuốn sách này chúnt; lô i khồna đưa ra CaU ưà tời cho cảu hỏi ircn mà chúnc lôi sò ciứi ihiộu m ỏ r s ố kếi quà ihú vị ihu được khi áp òụ n Ị các kỹ ihuâl lẠp tiình ú ín hi;á ch o nhicu d ạn c bài. N h ư đà nổi ờ irón. m ỏi sủ' nhù n c h iin wứu đã nhận ru licm nãniỉ cùa nhicu hư ớnc sửa đô,. Trong [78] D avis vii'i; “ K hi ỉhảo luân với nsười dùna. tôi aiài Ihích rầna k ế hoạch cùa tôi là lai ghép giưa giải ihuại gien và ưiuỊt loái'. hiửn dùng bằng cách áp. dụng các nguyỏn tắc sau: • D ù n ^ C âch M ã H oá H iện Hành', dùng cách m í h o á của ihuẠt toán hiện hành ch o Ihuạt toán lai. • L a i G hép K hi Có Thể'. Kết hợp các ưu điểm cùa thuật toán hiện hành vào thuật toán lai. • T h ic k ì^glii H o á C á c T o á n T ừ C ie n : xây dụng các phép trao đổi ch éo và đột biến cho kiểu mà hoá mối tương ứng với các phép trao đẩi cháo và d ộ t biến nhị phàn. Tích hợp các heurisúc phụ ihuộc bài toán vào các toán tử. {...] Tữi dùng thuỊt ngữ th uật toán gien la i ch o các thuật toán được xây dựng theo ba nguyốn tấc trôn." Dường như thuẠt toán g isa lai và các chương trình iiến hoá cố cùng một ý tường: sự tách khỏi GA idnh diển nhị phản d i hướng tới các hậ phức tạp hơn với các c íu UTlc dữ ỉiệu phù hợp (D ùng Cách Mã Hoá Hiện Hành), và các toán từ gíen íhích hợp (Thích'K ghi Hũá Các Toán Từ G icn), D avis eiả Ihiết sự có mật cùa m ộl hoặc nhiểu thuật toán hiộn hành và dựa ưèn các ihuậỉ lodn đó đổ bàn vé sự xay dựng thuỊt toán gicn h ir Tror.c hướng tiếp cận lâp t ìn h liến hoá cứa chúng ta, ta khồng dưa ra giả thiết nào thuộc clặng trỉr, m ọi chưcmg ứinh liến hoá sẽ á'~ạc g iớ i thiệu ưong cuốn sách này dểu được xây dựng từ đáu. ' -■fv. LỊip irình tiến hoá có những thế mạnh và yếu điểm gì? Có ìẽ'ưu''điổm chính của lâp trình tiến h o i là khá nãng ứng dụng rộng rãi. Trong cuốn sách nàv,' chúng tôi c i'g a n g m ô là nhiầu bài toán da dạng và cách xây dựng chương ii'inh ũến ỉìoá‘ cho m ỗi bài Uong số Jó. K íl quà ihưừric r ít k h i quan: nhiéu hộ có hiộu quà cao hơii nhiiSu so với các phẩn m ỉm Ihươiig mại có Iron thị ỉrường. M ột thế mạnh khác c ó ỉiên quan đ ín EP là bản chấi song song của ihuậl toán. Như đã được viết Irong [154.]: “Trong m ột thẩ giúi mà các thuật toán chuỗi được làm cho song song bàng vô số xảo ihuật và những sự bóp m éo, Ihật nực cười khi cá c giải thuẠt di ưuyổn (tính song so n c cao) bị biến ihành thuẠl toán chuỗi bằng cá c xào thuật trái tự nhiẻn khững kcm." T íl nhiẻn, diéu nàv dúng với m ọi EP.dùng quẩn :h ì dân số. Thồm văo dó, ta củng phài thừa nhận nén m ón e lý thuyết nghèo nàn cùa EP. Thực nghiộrr; vói các cấu trúc dữ liỊu và các biến thể của trao đ ổi ch«ỉo và đột biến đồi hỏi m ột sự phân tích kỹ càng đẩ c6 ihiì đàm bào hiệu q u i luơng đối lốt cho ihuàt toán. Điổu này cho dốn nay vẫn chưa dược thực h íín . • Nhln chung, các kỹ Ihuật s i i i toán ưong AI được chia thành hai loại ‘'m ạnh” và '‘y íu ”. ‘ Một phương pháp vếu dưa ra lì s i i thiít vổ miổn xác dịnh củu bài toán và d o dó nó cú thể được áp dụng rộng rãi. Miil ,wiác, phương pháp này c6 th(S phài chịu Jụng sự bùng IIà lổ hợp khi dem áp dụn e ch o các bài loán c ổ kích thưóc lớn han (90). Vấn đổn này có Ihá iránh được bằnc cách đưa ra các già th iít mạnh vé m iển xác định cCia btii toán rổi ;Ịn dụtig IritỊt dể các aià lliiíl này irona quá u ìiili giãi. N hưns các phương pháp mạnh này có mộl nhược diỏm là khả nãng áp dụng có hạn của chúng: chúng Ihưừng phải được Ihiốt k í lại n gav cd khi áp dụng ch o các bìii loán.gán siốn g. Các chương irình liín hoá nằm ờ dâu đó ờ giữa các phưong pháp Vii'u và các phươns pháp m ạnh. MỘI s ố EF (như các G A ) khá yếu và không cíưa ra g ià Ihiếi gì VC m iổn xác định cùa bài toán. M ột số chương trình khác (ví dụ GEis'OCOP hay G EN ETIC -2) phụ thuộc đ i bji Iihiiíu hơn và phụ Ihuộc với mức dỌi da dim e. V í dụ, C E N O C O P (chuơng 7), như mọi chic’n lưực ũốn hoú (chưưnu ổ), dược thiốl kõ’ dủ’ giãi các bùi lủp irlnii Uìum sỏ’. Hộ có ihổ xữ lý m ọi hàm m ục tiủu vứi m ọi uìp tíuộc luvO'n lính. Hò G ENTIC-2 (chươiit: 9) Jùni: c h o cá c bài loún yiao Ihônu. Các h<Ị khác ^xcm chương 10 và 11) thích hơD vói các bài quỵ hoạch lổ hợp (như các bài lũp lịch, người đưa diư, các bài Vii đó ihị). C iư ơ n a 12 giOi chiộu m ột ứng dụng ihú vị cùa m ội EF ch o iiiJucilve learning o f d ecision rules. Có m ột chút chflm biếm ờ đay: các G A dược co i là các phương pháp yếu nhưng chúnc ahanh clión a cliuycn ihùnh các pliương pliáp mạnh với sự có mậi cùa cúc ràng buộc khỏnt; lám thưừng. C ho dù la .xcl dốn hùin phạl diiìm, bô giải mà, hay thuệl loán sừa ch.ữa, ch ú n ỉ dổu phdi dược Ilúoi kố dặc biộ: dò phù lìợp vói bài loán cụ thẩ. Trona khi dó, các EP ^đươl: COI là các phươna pháp phụ iliuộc bài loán và là các phượng pháp mạnh hơn fihiỏu) bỏns' ư ờ nổn c ó VC yốu hơn nhiéu (.la SC bàn vé v ín d ẻ này kỷ han irong chương 14). Dicu này chi ra mỌl úiim Iiãiie lớn cùa hướng tiốp cộn dùng lạo tiình liiin hoá. Cúc quan sút IrOii Jũ ihúc ilãv lỏi niiliiổii cửu các lúih c iiíl cùu các loáii lừ uicn kli.ic Iili.ui x ác định iriin các cấu irúc dữ líỌu ciàu ihông ũn hơn xủu nhị phdn - xa ỉiơn nữa. nchicn cứu này c ó ỉh i dẫn lới sự hình ilùnii của m ội phương pháp iập irình m ới ^ironiỉ [277] eọi lũ E V A - v icl tấi của “E V olu ùon progrA m m ina’').' N ói m ội cách gần đúna. ư o n s m ỏi Irơvini: lập irình kicu mới J ó , m ộl lặp idnh viiỉa không những SC iựa chọn các cấu irúc dữ liệu Viíi các toán lử gien llu'ch hợp cho m ột bài loán cự lliẻ mà còn chọn hàm đánh §iá va khởi Lạo q u á a ihc ban dâu \CÚC lliam s ố k l ú c d ư ợ c d ic u fh iiih b ô i m ột quá in n h di iruyổn khãc). T u y nhiiỉn, m ộl khối iưựnỉi lứn nglúiin cứu phài dượa,hoàn thành irưức khi la c ó ihii dõ xu iì cá c nén m ón e x i y dựiig cho niộl mOi Ii'ưừng lập trình kiiiu m ới đó. Cuón sách này clii aikh thiỊu nhữag bước đáu úiiii hưóng lới m ục díciì này bầna cách nahiOn cửu các cau Irúc iiử liỊu khác nhau v i các loán :ử iiicn xũv dựni: các EP ch o nhiéu bài loán. C h ú n g í a s ẽ q u a y l ạ i V('ri ỹ l ư õ n g VC mi ii l r ư ( m g l:ìp í r i n h m<)ì n á y à cuiii s ã c h ( c h i i rm g 14) 8 1. T h u ậ t ío á n di truyOn iù gì? Có m ột lớp lổn các bài toán hay mà người la chua tìm ihuật loán iươne lối nhanh đ i giải chúng. Nhiiìu bài toán trong Ik'ap này là các bài loán quy hoạch mà ihưìmg này sinh trong các ứne dụn e. Cho m ộl bài toán quy hoạch ihuôc loại khó này. ta thườnỉ có ihể tìm ra một Ihuài loán chạy nhanh và cho kốt quà gán tối ưu. Đ ối với m ột số bài loán quy hoạch khó, la củng có thể dùng các thuỊt toán xác suấi - những ihuật toán này khỏng đàm bào cho ra kct quà lối ưu. nhưng bằng cách chọn ngầu nhiồn đù nhiéu “bang chứng", ta có thố giàm tuỳ thích xác su it sai cùa kếi q u i Các ihuẠl loan hi^u quà cao dũ Jược lìm ra cho rít nhiiíu bài loán quy hoạch. Thí dụ, ta có thử áp dụn e ■'mỏ phòng !uy<Ịn il-.Jp” cho bài toán thiốl k ỉ VLSI hoặc cho bài toán r.gười dưa ihu. Hơn nữa. nhiiiu bài loán quy hoạch tổ hợp ihuộc aui m ô lớn (nhiéu bài trong số dđ dã được chứng m inh thuộc vaò lớp NP-hard) có thể được giãi eản đúng trẻn máy tính hiện dại bẳng phương pháp M ontc Carlo. N'ói một cách ưừu íượne, viộc giài m ộ[ bài loán có ihể xem như việc lìm kiếm ư ong một khỏng gian cá c lời giải có thẩ. V ì cái dích cùa chúng ta là “lời 2 Íài tổt nhấi”, ta có thế coi cỏng việc này là một quá uìna tối ưu hũá. Đ ối với những không gian nhỏ, phương pháp "vét cạn” cổ di-in là tiù dùng: còn những không gian lớn hơn dòi hỏi các phưcmg pháp trí tuỏ nhan tạo đặc biệt.'Các ihuât toán di iruyền (G A ) nầm irone số các phương pháp đặc biệi dó. ThuẠt toán di tiuyiin là các Ihuậl loán ngầu nhiỏn mà phươns thức tìm k iím dựa irCn mộl số hi«Ịn iưựng ihiủn nhiCn: sự Ihừa kố gien và thuyết đấu ti'anh sinh tổn cùa Darwin.[74] có đoạn: các thuật loán gicn v ì sự liến hoá tự nhiẽn c ó cùng m ột nguyên lý, Trong sự liín hoá lự nhiỏn. mỗi loài sinh vỊt đểu phài tìm cách thích nghi tốt với m ội n;ỏi trưừna sốnc phức tạp và luôn Ihav đổi. “ Kiến thức” m à m ỗi loàỉ đức kết được chi lại irong c íu trúc nhiỉm sắc Ihổ của các ihành viỏn...” Tư iưòng dằnc sau ihuật loán di lcuvén là iàm ihco lự nhiõn. Ta hàv lấy ihỏ n làm mộỉ v{ dụ: XÓI m ột đàn ih ỏ tại một Iliừi Jidm nào d ó. M ộ i s ố c o n th ò nhanh nhẹn và linh khôn hơn các con kháo U'ong dàn. Nhữnt: con Ihò nhanh hơn và klíôn hơn nàv ít khả nãnc bị cáo ãn hơn, do đó ciiúne sống SỔI nliiòu.liơn tlò đò Ihiim Ihỏ con. T íl nhiiln, mỏt phđn ti-onc s ố lliò chỊm ch ạ tịh cn và niiừ ncỌch hưn cũng mav mán SỐIIC SÓI. N liihig con ihò sonti sót bắi dáu sinh <ỉõ. kối qud là m ội iự kci hợp thú vị cùa gien thỏ: m ội sò' Ihò chặm k ít hợp với thò nhanh, nhanh với nhanh, khũn với ngu, V.V.. Trong đó, Ihinh thoàng lại này ra niỏí con “ihỏ rừng” do sự đột b iín gicn . N hững con Ihỏ non được sinh ra (lính UTjng bình) s ẽ chạv nhanh hờn và linh khổn hưn Uiil’ hộ thỏ ban đáu vì ihỏ cliạy nhanh và liiìh khôn số n c sổt nhiổu hơn. (M ay mắn là nhữne con cáo cũng dang trài qua m ột quá ưình tương tự - nếu k h ôn g ih ỏ s ẽ ư ò nỏn quá khôn và quá nhanh đển nỗi khổng con cáo nào đuổi kịp). Thuật toán di truyén bảc chước câu chuvện nhũng con thò. N hư được v iếl trong [380]: "Lý ih u yếi ch o rằng chọn lọ c tự nhiẻn là nguyẽn lý cơ bàn cùa sự tiến hoá dã được Darw in đề ra rấi lầu trước khi cơ -ehế di truyển dưọc tìm ra. Chưa biếc đến các nguyổn lý di ưuyổn c ơ b in , Darwin đưa ra e iả ihiiìl v é sự thừa k ế hoà trốn, ôn c c h o rung các lính ch;Vi cùa cha mọ hoã [ủn vùo nhau như các chất iòn e trons cơ chd co n ...“ T huậi loán di íTuyổn dùn e nhiều ihuật rgữ cùa ngành di iruycn học. Chúng ta sẽ nói v é các ■*cd ihé" ( hoặc genotype, structure) ư-ong m ội quán liiiỉ': ihưòn® thì các cá íhể này còn dược g ọi l i xảu (siring) hơặc nhicm sắc ihể (NST). M ỏi tẽ bùo irong c ơ th i của m ột lo-i nào đ ó chứa m ột s ố r.híl địr.h N S T ( v í dụ người c ó 4 6 NST); tuy nhiôn, iron? cu ốn sá c i này ta ch i nổi vé cá c cá ihc chi chúa dúne m ội NST. M ỗi N S T bao gổm các đơn vị • aicn , hav lính trạng, mã ) - xốo liố.T liỏp; mỏi gien điểu khiển sự Ihừa k í của m ột hoặc vài lím trạng (hoặc đặc Irưng). G ien cùa các tính irạng nhấl định có vị trí x ác định trẻn NST, vị ỉn' iló được g ọ i là !o ci (vị [n trCin xảu). M ội lính ưạng b ít kỳ (ih í dụ máu tóc) c ó thổ được ibd hiôn vứi nhiéu m ức độ khdc nhau; la nóL rằng gien đ ó Ci5 nhiéu trạng chái (g ọ i là allete). M ỗi kiíìu g ìcn (gcn oiyp c) (iic'nti cuũn sách này là m ội N ST ) sẽ b iìu Ihị m ội lời ciải c ó lie cùa m ột bài loáu (ý nuhTa cùa m ỗi NST cụ lh>5 . nghia là kitìu gicn của nó. dược quy ưi’c bừi người lộp Iiìiìh); m ội quá u ìn h tiốn hoá dưực ihực hiiỊn irCn m ộl quiui Ih i NST líi tirui i; Jưưng vứi sự lìm kio'm u-oni: nu)i khỏng iiian cáo iừi giủi c ó ihể. Sự •.ìm kiếm này đ òi h')i sự cdii bàng giữa hai m ục đíoh; khai ihác Idi giải íôì nhất và khám phá khủng gian lìn kiếm [4 6 ]. Phương phúp “Ico núi" là một ví dụ vổ chiến lược khai ihác lùi EÌùi tỐL nhất ilico các hướnq cãi tiốn. Tìm k iím ngáu nhiẻn là m ộl v í dụ diẩn hình của sự kr4cn phá klìỏrg gian lìm kiốm . khồng chú irọne khai iháo các rniồn hứa hẹn Irong k hôn s sian lìm kiốn. Thuủl toán di iruyổn là lớp các phương pháp lìm kiốm [ổng quái (không phụ ih u ộc v;o m icn xác dịnh) với sự oiiii bui:i: dúim kõ uiữa khai*fclúc và khám phá không ':;ian ùm kicrr. G A đã được áp dụng khá ihành c ô n c cho m ột s ố bài toán quy hoạch như routing. Lip lỊi.h. diồu khien độniì, irò chơi, co íin iiivc m odcllinq, các bài toán giao Ihông, bài toán ngưùi dra Ihư, c á c bài toiln diiìu k h i í n tứi ưu, lối ưu hoá Cilu h ỏi c o s ỡ d ử liỊu. V.V.. ( x c m ihLHi [1 5 .3 4 ...]). Tuy nhiòn. Jong khuyửh cáo về vi.Ịc c o i G A như là công cụ tối ưu hoá; ” ... d o Nự q uan Iflm lứii vài) chức nâng lổi ưu hoá ứng dụng, la d ỉ đi đốn ch ỗ coi G A là các ihuại toán lồi ưu hoá và sẽ ngạc nhitin và/lioặc thất v ọ n g khi chúng k h ôn g tìm dược kết quà lối ưu hiổn nhiủn trong m ột không gian tìm kiếm nào đ ó . T ôi ch o rằng la chl nOn xom C A là m ộl sự g ià iạp (khá lý tường) của quá u ìn h phát iricin lự nhiửn và GA chứa dựng d ích và chủ dịnh (nốu có) cùa quá trình cự nhiòn đó. Tôi không rỗ có ai m uốn dịnh n ghĩa đích và ùhù định của các hệ tiến hoá hay không. Nhưng Ifti cho rằng, c ô n g bàng mà nói, các hệ đ ó nói chung k h ôn g dược xem là cổng cụ lối ưu hoá chức n án g.” M ăi khác, lối ưu hoá lai là ứna Jụna chính của G A. Tror.a ^ 4 8 1 Schw efel v iít: Trong Ihập kỹ irưút, lim quuiỉ Iiọni: của lối iru hoá dã dược niìín mạnh hơn - nhiổu bài toún quy hoạch tổ hợp quv mổ lớn. oác bai loán ứnư d ụ n g với rinj- biiộc cao ohi có tlid dược ciâi gán dúng irữii m av ;ínii lìiộn dại. O A nhâm vao cá c bài ioán phúc tạp Jó. GA nàm iron a !ớo các tlìuỊt to^n xác .ỉuẩtniiưnc lại Nhác cá c ihuật loán níiủu nhiồn ỡ chỏ G A kò't h(jp cú c iliành phiỉn cồ hư.7ns vdri tìm ki^m n g ẫ u nhiiri. M ộl ;ính vhất quan irạrE khác c ủ a c i c p h ư ơ n c phan ti:n k i í m dựa vào 2 Ìcn này là chúnu duy ;rì một ựip hvTp cac lừi giãi c ó ihii - m ọi phươnỉ p lú p i;h;ic đốu .‘hi xử iý Jiom đưn Uoni: khỏn e iii.n ù r . ícicm. PhưưnịỊ pháp Ico núi sứ dụn c kỹ ihuậl náiỉii cấp lập ( iio ra ú v e im p ro v em en t); kv thuại r.ày áp dụns: c h o míM Jicm Jơn ( diiỉm r.iộa :ại ) iror.i khôn i: siiin lìm k ij;n. Trvìns một lẩn nânc c íp , m ột diòm m ới dược chọn iror;: số các Jicm làn củn cãa cJiom hiiin ha:ih i Jo đó kỹ ilíu Ịi uày uòn Jưựt i;v* I'” * lũii cẠii lu y Um kiò':n cục bi' ;. Nửu đic;n :nứi oh 0. Trong u-ường hiTp sau, xác xuất ;r.á'p nhận p !à m ột hàm phụ ihuộc giá ;rị il hìim m ục liCu (ại dicm hiỊn hành vã lại ciícm mới, và m 6i Iham s>! Jiiỉu khicn “ nhiựl đ v ’ TT càng nhỏ ihì xác s u ii chap nrtộn dijH', m ới càng ihấp. Trong irinn chạy Ihuậi loáii. n h iệi đ ộ T của hệ giĩim dãn lừng bưóc, ihuỊii loán k ii ih ú t khi T Jại lứi m ội g iá trị nho nào đó. N h ư đã n ói ờ ư ên , C A ihực hiện lìm kiii'm ih co nhiéu hướng bang cách duy u ì m ộj táp hợp các lờ i giài có ih ể và khuyến khích sự hình Ihành vã irao đ ổi thõn|: lin giữa các hướng. Tập hợp lời giải irài qua sự liến hoá: lọi m òi ih ế hệ, các lời ^iài iươnc đối "tốV' được lái sinn, ư o n g khi cá c lời giài iươnc dối 'lổ i" bị loại bò. Đ ổ phíin biộl giữa các Itì giài khúc nhau, la dùng m ột hum m ục liốu (dánh ^iá ) dóng vai irò của m ội m ôi ưường sốr.a. Cấu Irúc cùa m ộ i G A dơn giàn cũ n g giốn g như cấu irúc cùa m ội chuơnp ưìrih liốn hoá bit k ỳ (xem hình 0 .1 , chương M ờ dáu). Trong vòng lặp ĩ, m ột G A duy irì m ột lộp lời giùi (N ST , vecior) H ự ) = Ia-*!,... ^v'„j. M ỏi lờ; ciài -\^ được đánh giá '*độ ihích nghi”. Sau đó. mội lâp hợp m ới (vò n g lặp dược x â y dựiig bang cách chọn các cá thể thích nghi hơn. Mội sô’ cá Ihể ư o n g lập hợp này bị biến đòi bảng phương pháp lai và đột biến để ụ o Ihành các lời giả i m ới. Phương pháp ư ao đổi ch éo kốì hợp các dặc lính ưõn N ST cùa bõ' và m ẹ đ ể tạo Lhành hai cá ll>c m ới bằng cách iráo c3ổi các doạn iương ứng ưôr. N ST cùa bố và m ẹ. Thí dụ, nốu b ố m ẹ được bidu d iỉn bằng các vcrior 5-ch iổu {a .,b i,C ị,á .C ) và trao d ổi ch ỏo các NST sau gicii thứ haỉ iO lạo ra hai con ihì và '• Trực giá c d ằnc sau sự áp dụiìtt phép Irao dổi chóo dó là sự irao đổi Ihfinc lin ciữa các lòi giải khúc nhau. Phứp đ ộ l biến sưa dổi luỳ ý m ộl vài ỄÌcn cũii m ộl NST dược ch ọn, nầnc cách ihav' dổi ngủu nhi6n với xá c suấi là lý lứ dội biốn. Trực c ia t dàng sau phép dội blốn lìi sự bổ x u n c sự dj dạiìg ch o lẠp lời G A { như m ọi chưong trinh licn h o j ) ch o m ộl bài toán cụ ihd phiii có 5 thành phần sau đảy: • M ột cúch bicu diỗn tiico gicri các lời piài c ó Ihẩ cùa bùi toán. • M ộl cách xfiy dựng ựip hợp ban đáu ciiu các lừi giài. • M ộl hàm dánn giá dóng vui Irò m ỏi irưừng sốn g, xốp han^j tá c lùi giài Ihcc) d ỏ “ Uỉích nghi m ồi ư ư ò n g ” cùa chúnc. •• • Các phép biến đổi gicn đổ Ihay đ ổi cấu irúc cùa các cá Ihể con. • G iá irị c h o cá c tham s6 được ciùng ( kích ihưóc cùa tẠp lời giãi, xác suất áp dụng biín d ổ i gicn , v.v ..). Ta sè bàn vổ các đậc đ iim chính cùa các C A với ba v í dụ dưói dây. Trong ví dụ ỉXx), với m ọi -t s [-1 ..2 Ị. ỉ Tinh ! l Đ ồ Ihị hàm số./ĩ.v)** X - sir.(lC;u:) - I.o H im / iưưim J ối dỗ kháo sái. Các khỏii” tiiòm của diỊO hàm bủc nhũt f Jược xác dinh như sau: / ’(.V) = MIÌI lOxvi - U);lv < oủim ihức Iiủn tưưníĩ dươim vứi Ỉ0~VJ = 0 lan(107Lt) = -ỈŨTtr. R õ ràn e, phưong trình trôn oó vô s ố nghiệm , x = ( 2 i - l ) / 2 0 + f ,.v ớ i í = I .2 .... •to = 0, .r, = (2 / + l ) / 2 0 - £•„ với i = - 1 . - 2 .... trong đ ó . các s, biửu ihị các dily số Ihực 2,iãm dẩn ( với i = l , 2 ,.... và i' = - 1 . - 2 ,...; tiến dán đốn k h ôn g. C ũ n g ndn lưu ý rẳng h à m /d ạ t d ín cdc cực đại lại .V, nếu i lẻ, và đạl cực lí - 5 7 /2 0 T £■,9- I.S 5 -r £•„. irong đóyt.Ti,) hơi lớn h ơ n /(l.S 5 ) = 1.85 X sin(18;: + z /2 ) f 1.0 = 2 .S 5 . G iả sừ ta m uốn xây dựng m ộl G.A đẻ giải bài toán ư-én. Ta hãy Iđn lượt bàn v é c á c thànii phán chm h cùa G A đó. 1 .1 .ỉ lỉic u dicn T a d ù n g N S T dưới dạng m ột vector nhị phân để biểu diễn các giá irị thực của b iến X. Đ ộ d à i c ù a v c c to r phụ th u ộ c vào đ ộ ch ín h xác m à la cần , ừ o n g irường hợp n à v là 6 c h ữ s ố Siiu clđu phảy. M ién x á c định cùa X c ó dộ ilùi 3; yCu cáu vổ độ chính x ác đ òi hỏi đoan [—1..2] đư ợ c chí.i ihìlnh ít nhííl 3* 1 0 0 0 0 0 0 đoạn con dộ dài bằng nhau. N ghĩa là m ỗi vcclor nhị phi'^n (N.ST) oán 2 2 bii: 2 0 9 7 1 5 2 = 2 " < 3000 0 0 0 < 2” = 4194 3 0 4 . C ách brốn đ ổi xủu nhị phin ihành m ột sỏ’ ihực X irong đoạn [ - 1 ..2 ] 2 ốm 2 bưức; • b iến d ổ i xau nhị phán lừ hộ cơ (); = • lìm ^ )|Ũ “ sang hệ Ihộp phản: ' ihực X iư ơn e ứnc: x = - 1 . 0 + x ’ x 3 /(2 " -l). trong đó, - 1 . 0 là biỏn ưái của m iền và 3 là độ dài của mi(Sn. , T n íd ụ , m ộl NST (loooioiiioiioioioooii:) b iiu dicỉi số 0 .6 3 7 1 9 7 . vì x ’ = (lO O O lO lllO llO lO lO O O lU j; = 22S8967 VD X = - 1 . 0 ^ 2 2 8 8 9 6 7 x 3 /4 1 9 4 3 0 ? = ũ .6 ? 7 1 97. liiố n nhiSr., các NST (OOOOOOOOOŨOỮOOOOOOOOO) và.( 1 n u 1 ] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ) lần lượt biểu dìỗn các biên cùa m iẻn xác định: - 1 và 2. 1.1.2 T ập họp ban (lau Quá ưii.ỉi khò; 1;,K1 rui dan íỊÌàr.. lu xủy dune một lộp N ÍT , U'Oiig dó m ỏi N ST lã m ội vcclor nhị phần eồm 2 2 bii. Tấi cà 22 bii cùa mỗi NST đầu dược k hòi lạo n cẫu nhièn. 1.1.3 H àm d án h giá ỉiù n i dánlì giá cval ciành cho các vector nhị phân V iương dương với hàm f; cvul(vj - ríx). Iron!: đó. N ST V dcii diộn cho aiú irị Ihực X. Như dã nói dóV. ờ ;icn. hiim dúnh giá dóng vai irò cùa m ói irưònt;, n ó phán lo ạ i'cá c lời giài có ihc dựa vào dộ ihích nghi cùa chún". V í dụ, ba NST; Vi = ( i o o o i o i n ũ i i o i o i o o o i i u V, = (00000011 lOOOOCOOOlOOOO), V, = { 1 n 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 ] 01). lull lưín iưưiìj^ ứiii; vứi các ui;j irị X = 0 .6 3 7 1 9 7 , X- = - 0 . 9 5 8 9 7 3 . và Xj = 1 .6 2 7 8 8 b . Hàm dánh ẹiá s ệ lính diổm chúnc nhu sau: cval(V |) = = 1.586345. eval(vj) = f(x ,) = 0.07 8 8 7 8 , ev a l(v j) = f( x ,) = 2 .2 5 0 6 5 0 . R õ ràng, trong ba XST. Vj là tối nhất vì hùm d in h giá trả VC giá irỊ cao nh íl. 1.1.4 C á c p h c p biốn d oi gicn Trong pha bic'n dổi cùa G A, ìa sẽ dùng hai phép biến đ ổi cổ điển: đột biến và ưao đổi chco. N hư dã nói dốn ờ trồn, phóp dội biốn Ihay dổi m ội vài gicn ( vị in' irèa N ST ) vcri x ác su it bang ti lộ dột bicn. Giả sử ihứ năm uồn N ST Vj dược chọn đột biốn. G icn 5 của N ST này là 0. do dó nó SC bị sữa ihành 1. Sãũ dột biến. N ST V, irờ thành: Vj- = ( 1 1 iOlCCHXOl n i l 1000101). N S T này biiiu d icn giá irị X]' = 1 .7 2 1 6 3 8 và ù x / ) = - 0 . 0 8 2 2 5 7 . T a :hà'y đ ộ i bicn n ì v Jã aiàm đária kẩ của N S T V.. M ậi k l ú c , ncu 2 Ìen s ố 10 c ù a N S T V, dược ch ọn d i d ột b iến Ihi Vj” = ( 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 1 0 1 ) . Ta c ó c iá trị iưane ứna Xj” = Ì.6 3 0 8 ỊS và fix j”) = 2 .3 4 3 5 5 5 . kẻì quà này tốt hơn 2 Ìá Irị ban đẩu fiXj) = 2 .2 5 0 6 5 0 . Ta hãy m inh hoạ phép trao đổi ch éo ư>Jn các N ST V. và Vj. C ià sừ điòm cắl được chọa ự i g i u nhiỏn; UII VỊ Iri sau cicn s ố 5: vj-= (ooonnioi 1 ĩnnonnooninonnì. v ' = u ! lOOlOOOOOl 1! 111000101). Hai cá ih í mứi là: V;‘ = Ì.OCOOOI00000111 ỉ I ỉ o o o i o n , Vj' = (11 lo o io i 1 in o o o o o o o 10000). C h úns đươc dúnh 2 Ìá như sau: •• f ( v ,‘) = f(^ 0 .9 9 8 1 13) = 0.94Ũ S 6,\ f(v3‘) = f(!.6 6 6 0 2 8 ) ==2.^592^5. Lưu V rằng cá Ihỏ con Ihứ hai dưạc đánh aiứ cao hơn cả hai cá Lhi bố mẹ. 1.1.5 C á c tham .sô' Đ ố i vớ i bài toán cụ liiiì Iiày, ta dã sử dụng các tham số sau ; p op _size = 50. xác suấí trao đổi chóo kích íhước tạp lừi giài = 0 ,2 5 , xác suất đột biến p„ = 0,01. Các m ục tiếp theo sẽ g iớ i ihiửu m ột số k íl quả ihực nghiệm hệ di truyền này. 1 .1 .6 K ế t q u â th ự c nghiệm Bàng l . 1 gh i lại các Ih í hộ có sự nâng c íp của hàm đánh giá. NST tốt nhít sau 150 ih ế hệ là v .„ . = (1111001 l o i o o o i o o o o o i o i ) . g iá u ị lư ơn g ứnu là * 1.Ổ50773. N hư dã m ong dại, = 1.85 -i- e, và f ( x „ J hơi lớn hơn 2.85. TlìC’ hd 1 1.441942 6 2.250003 8 1 2.250283 9 2 .2 5 0 2 8 4 10 2.2503Ó3 12 1 1 i Hàm đánh aiá 1 2.328077 1 2J44Z51 40 2 .3 4 5 0 8 7 51 2 .7 3 8 9 3 0 99 2.84 9 2 4 6 137 2.S50217 U5 2.S50227 Bàng 1.1. KCÌ quà của 150 th í hiỊ. 1.2 T h e p riso n er's dilem m a T rong m ụ c này. u sữ trình bàv gách dùng G A dổ học chii'n lược cho m ộl irò cKơi Jơn giàn. Hai người lù bị yiam iroiig liiii phòníi riiiny biỌl, khồnỊj ihò iiCn lục vứi aliau (Jược. Hai ngưừi lần lượt bị gọi riiiniĩ dii Jụ dỏ đáu hàng và phàn b ội ngưừí lù kiu. N ốu chi có 'nội người phàn bội, hun sẽ dược ihườna còn người kia sẽ bị rừng phạt chút íỉ. N ếu cả hai cìng