Bài giảng Hệ thống điều khiển thông minh - Chương 2: Lý thuyết cơ sở - Huỳnh Thái Hoàng

10 20 30 40 50 60 70 80 90 100 0 Percent full Hàm liên thuộc của hai tập mờ mô tả hai giá trị ngôn ngữ "cao", "thấp" Biến ngôn ngữ là biến chỉ nhận các giá trị ngôn ngữ. Thí dụ: Biến ngôn ngữ “mực chất lỏng” có thể nhận hai giá trị ngôn ngữ là “thấp” và “cao” 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 17 Mệnh đề mờ ĐỊNH NGHĨA Mệnh đề mờ, ký hiệu P~ , là phát biểu có chứa thông tin không rõ ràng. Trong kỹ thuật, các phát biểu sau đây là các mệnh đề mờ: - "Nhiệt độ" là "cao" - "Mưc chất lỏng" là "thấp"ï - "Vận tốc" là "trung bình", ⇒Mệnh đề mờ là phát biểu có dang: ï "biến ngôn ngữ " là "giá trị ngôn ngữ ". Về mặt toán học, mệnh đề mờ là biểu thức: AxP ~:~ ∈ Tập mờ A~ đặc trưng cho giá trị ngôn ngữ trong mệnh đề mờ. 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 18 Mệnh đề mờ GIÁ TRỊ THẬT CỦA MỆNH ĐỀ MỜ Khác với mệnh đề kinh điển chỉ có hai khả năng sai hoặc đúng (0 hoặc 1), giá trị thật của mệnh đề mờ là một giá trị bất kỳ nằm trong đoạn [0,1]. Gọi )~(PT là giá trị thật của mệnh đề mờ P~ : )()~( xPT μ ~A= Biểu thức trên cho thấy "độ đúng" của mệnh đề AxP ~:~ ∈ bằng độ phụ thuộc của x vào tập mờ A~ . 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 19 Các phép tốn trên mệnh đề mờ PHÉP PHỦ ĐỊNH Cho mệnh đề mờ AxP ~:~ ∈ . Phủ định của mệnh đề P~ là mệnh đề : AxP ~:~ ∉ Giá trị thật của mệnh đề phủ định: )(1)~(1)~( ~ xPTPT Aμ−=−= 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 20 Các phép tốn trên mệnh đề mờ PHÉP HỢP Hợp của hai mệnh đề mờ AxP ~:~ ∈ , BxQ ~:~ ∈ là mệnh đề xác định bởi AxQP ~:~~ ∈∨ hoặc Bx ~∈ ⇒ BAxQP ~~:~~ ∪∈∨ Giá trị thật của mệnh đề hợp là: )()~~( ~~ xQPT BA∪=∨ μ 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 21 Các phép tốn trên mệnh đề mờ PHÉP GIAO Giao của hai mệnh đề mờ AxP ~:~ ∈ , BxQ ~:~ ∈ là mệnh đề xác định bởi AxQP ~:~~ ∈∧ và Bx ~∈ ~~~~⇒ BAxQP : ∩∈∧ Giá trị thật của mệnh đề giao là: )()~~( QPT ~~ xBA∩=∧ μ 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 22 Các phép tốn trên mệnh đề mờ PHÉP KÉO THEO (IMPLICATION) Mệnh đề kéo theo: : ~~ QP→ Nếu Ax ~∈ thì Bx ~∈ trong đó mệnh đề AxP ~:~ ∈ được gọi là mệnh đề điều kiện và h đ à Q ~~ đ i l ø ä h đ à k á l ämện e Bx: ∈ ược gọ a men e et uan. Giá trị thật của mệnh đề kéo theo được xác định bởi toán tử I (Implication) . ))(),(()~~( ~~ xxIQPT BA μμ=→ Các toán tử I thường sử dụng để xác định giá trị thật của mệnh đề kéo theo MIN và PROD. 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 23 Qui tắc mờ Qui tắc mờ là phát biểu nếu−thì, trong đó mệnh đề điều kiện và ä h đ à k át l ä l ø ù ä h đ à ờ T ä h đ à đi à ki ämen e e uan a cac men e m . rong men e eu en có thể có các phép giao, phép hợp hoặc phép phủ định. Thí dụ phát biểu sau đây là một qui tắc mờ: nếu x1 là 1 ~A và x2 là 2 ~A thì y là B~ 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 24 Hệ qui tắc mờ Hệ qui tắc mờ gồm nhiều qui tắc mờ. Thí dụ hệ k qui tắc mờ đối với n biến ngõ vào có dạng như sau: r1: nếu x1 là 1,1 ~A va ø va ø nx là 1, ~ nA thì y là 1 ~B r2: nếu x1 là 2,1 ~A va ø va ø nx là 2, ~ nA thì y là 2 ~B rk: nếu x1 là kA ,1 ~ va ø va ø nx là knA , ~ thì y là kB ~ 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 25 Suy luận mờ Giả sử chúng ta có qui tắc mờ: nếu x là A~ thì y là B~ Nếu biết ngõ vào x là A′~ thì có thể suy ra giá trị ngõ ra y là B′~ được không? Nếu được thì B′~ được tính bằng cách nào? ~ ~ nếu x là A thì y là B x là A′~ y là B′~ ? Câu trả lời là được. Quá trình suy ra giá trị B′~ được gọi là sự suy luận mờ . 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 26 Phương pháp suy diễn MAX-MIN Xét qui tắc thứ k của một hệ qui tắc mờ: rk: nếu (x1 là kA1 ~ ) và ( x2 là kA2 ~ ) thì (y là kB ~ ) Giả sử ngõ vào x1 là 1 ~A′ và x2 là 2~A′ , tìm y. Ngõ ra y tính theo phương pháp suy diễn MAX−MIN như sau: Nếu và thìα1k 1 kA1 ~ 1 ~A′ α2k 1 kA2 ~ 2 ~A′ β 1 kB ~ B′~ x1 x2 k y k 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 27 Phương pháp suy diễn MAX-PROD Xét qui tắc thứ k của một hệ qui tắc mờ: rk: nếu (x1 là kA1 ~ ) và ( x2 là kA2 ~ ) thì (y là kB ~ ) Giả sử ngõ vào x1 là 1 ~A′ và x2 là 2~A′ , tìm y. Ngõ ra y tính theo phương pháp suy diễn MAX−PROD như sau: Nếu và thì 1 kA1 ~ 1 ~A′ α 1 kA2 ~ 2 ~A′ 1 kB ~ B′~βkα1k x1 2k x'2 x2 y k y' 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 28 Suy luận từ hệ qui tắc mờ ‘ Kết quả suy luận của hệ qui tắc mờ bằng hợp kết quả suy luận của từng qui tắc. Thí dụ: xét hệ gồm 2 qui tắc mờ: r1: nếu (x1 là 11 ~A ) và ( x2 là 21 ~A ) thì (y là 1 ~B ) r : nếu (x là ~A ) và ( x là ~A ) thì (y là ~B ) 2 1 12 2 22 2 Giả sử ngõ vào x1 là 1 ~A′ và x2 là 2~A′ 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 29 Suy luận từ hệ qui tắc mờ Nếu và thìα111 11 ~A 1 ~A′ 1 21 ~A 2 ~A′ 1 1 ~B ~′ x1 α21 x'2 x2 β1 y 1B ~A~A′ ~B~A ~A′ Nếu và thìα12 1 121 β2 1 2 2 ~B′α22 1 22 2 2 ~B1 ~B x1 yx'2 x2 1 B′~ 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 30 y Hệ mờ Hệmờ cơ bản Tiền Mờ Hệ qui tắc Giải Hậu xử lý hóa Phương pháp suy diễn mờ xử lý 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 31 Khối tiền xử lý ‘ Tín hiệu vào bộ điều khiển thường là giá trị rõ từ các mạch đo, bộ tiền xử lý cĩ chức năng xử lý các giá trị đo này trước khi đưa vào bộ điề khiể ờ bả u n m cơ n. ‘ Khối tiền xử lý cĩ thể: Ž Lượng tử hĩa hoặc làm trịn giá trị đo . Ž Chuẩn hĩa hoặc tỉ lệ giá trị đo vào tầm giá trị chuẩn. Ž Lọc nhiễu. 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 32 ố ế ổ Mờ hĩa Kh i mờ hĩa cĩ chức năng bi n đ i giá trị rõ sang giá trị ngơn ngữ, hay nĩi cách khác là sang tập mờ, vì hệ qui tắc mờ chỉ cĩ thể suy diễn trên các tập mơ. 1 A~′ 1 A~′ 1 A~′ (a) (b) (c) Tập mờ ở ngõ ra của khâu mờ hóa x x' xx'−1 +1% xx' (a) Tập mờ A~′ khi tín hiệu vào x' không có sai số, không có nhiễu (b) Tập mờ A~′ khi tín hiệu vào x' có sai số ±1% ~′ ã á 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 33 (c) Tập mờ A khi tín hiệu vào x' có nhieu phân bo Gauss Hệ qui tắc mờ ắ ể ể ễ‘ Hệ qui t c mờ cĩ th xem là mơ hình tốn học bi u di n tri thức, kinh nghiệm của con người trong việc giải quyết bài tốn dưới dạng các phát biểu ngơn ngữ. ‘ Cĩ hai loại qui tắc điều khiển thường dùng: Ž Qui tắc mờ Mamdani Ž Qui tắc mờ Sugeno 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 34 Đ â l ø l i i é đ d ø ù ù d đ à i â û Qui tắc Mamdani ay a oạ qu tac ược ung trong cac ưng ụng au t en cua điều khiển mờ (Mamdani, 1974; Assilian, 1974; Mamdani và Assilian, 1975) và có dạng tổng quát sau đây: ri: nếu (x1 là iA ,1 ~ ) và và ( xn là inA , ~ ) thì (y1 là iB ,1 ~ ), , (ym là imB , ~ ) Trong đó: n làsố tín hiệu vào m là số tín hiệu ra ki 1 ới k l ø á i t é đi à khi å ..= , v a so qu ac eu en. Qui tắc mờ Mamdani là loại qui tắc mờ đã xét trong các chương t ướ K át l ä û i t é đi à khi å ờ M d i l ø ä h đ à ờr c. e uan cua qu ac eu en m am an a men e m . Thí dụ một qui tắc mờ Mamdani như sau: nếu sai số "lớn" và tốc độ thay đổi sai số "nhỏ" 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 35 thì tín hiệu điều khiển "lớn" é å Qui tắc Sugeno Qui tac mờ này được Sugeno đưa ra vào năm 1983 và có dạng tong quát như sau: ri: nếu (x1 là iA ,1 ~ ) và và ( xn là inA ~ ) , thì ),...,( 1,11 ni xxfy = , , ),...,( 1, nimm xxfy = Kết luận của qui tắc điều khiển mờ Sugeno là hàm của các tín hiệu à åvào bộ đieu khien. Nếu dùng hàm tuyến tính ở kết luận thì qui tắc mờ Sugeno có dạng: á A ~ A~ ∑+ n xbby ri: neu (x1 là i,1 ) và và ( xn là in, ) thì == j iiji 1 ,,0 Thí dụ: nếu e "lớn" và Δe "nhỏ" thì u = 4e + 2Δe T đ ù l ø í hi ä đi à khi å l ø i á ø Δ l ø đ h ø b ä h á rong o u a t n eu eu en, e a sa so va e a ạo am ac n at của sai số Qui tắc mờ Sugeno có thể đơn giản hơn khi cho bj,i = 0, ( nj ..1= , n là 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 36 số tín hiệu vào). Khi đó kết luận của qui tắc mờ Sugeno là hằng số. Giải mờ ‘ Ngõ ra của bộ điều khiển mờ là các giá trị ngơn ngữ, hay nĩi cách khác là các tập mờ. Trong khi đĩ các đối tượng điều khiển chỉ “hiể ” đ á iá ị ậ lý ( iá ị õ) ì ậ ầ hải h ểu ược c c g tr v t g tr r , v v y c n p c uy n các tập mờ ở ngõ ra bộ điều khiển mờ sang giá trị rõ. Quá trình này gọi là giải mờ (defuzzification) . ‘ Các phương pháp giải mờ cĩ thể qui vào hai nhĩm chính: Ž Giải mờ dựa vào độ cao. Ž Giải mờ dựa vào điểm trọng tâm. 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 37 Các phương pháp giải mờ dựa vào độ cao 1 μ 1 μ Phương pháp độ cao Phương pháp trung bình 0 y* y 0 a y* b y của độ phụ thuộc cực đại 1 μ cận phải cực đại * Phương pháp cận trái cực đại (hay cận phải cực đại) 0 y y cận trái cực đại 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 38 Các phương pháp giải mờ dựa vào trọng tâm 1 μ 1 μ 0 y* y 0 y* y Phương pháp trọng tâm (COG) Phương pháp trọng tâm vùng có diện tích lớn nhất 1 μ .5 .9 Phương pháp trung bình có trọng số 0 a b y 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 39 Khối hậu xử lý ể ẩ‘ Chuy n giá trị chu n hĩa [-1, 1] (khơng thứ nguyên) thành giá trị vật lý. ‘ Khuếch đại . ‘ Mạch tích phân, 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 40 MANG THẦN KINHÏ 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 41 Tế bào thần kinh [ ]Tmxxx K21=x [ ]Twww K21=w vector tín hiệu vào tế bào thần kinh vector trọng số tế bào thần kinh 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 42 m Hàm xử lý ngõ vào tế bào thần kinh ế θθ −=−⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛== ∑ xwTm jj xwnetf ‘ Hàm tuy n tính (linear function): =j 1 ‘ Hàm tồn phương (quadratic function): θ−⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛== ∑ = m j jj xwnetf 1 2 ‘ Hàm cầu (spherical function): θρθρ −−−=−⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ −== −− ∑ )()()( 2 1 22 wxwx T m j jj wxnetf 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 43 = Hàm tác động ế‘ Hàm tuy n tính: dố b h ffa =)( ⎪⎧ >11 fnếu‘ Hàm c ão ịa ⎪⎩ ⎨ < ≤≤= 00 10)( f fffa nếu nếu ‘ Hàm tuyến tính bão hịa ⎪ ⎪⎨ ⎧ ≤≤ > = 10 11 )( ff f fa nếu nếu ⎩ −<− 11 fnếu fa = 1)(‘ Hàm dạng S đơn cực fe λ−+1 12)( −=fa‘ Hàm dạng S lưỡng cực 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 44 1+ − fe λ Các dạng hàm tác động Hàm dốc bão hịa Hàm dạng S đơn cực Hàm tuyến tính Hàm tuyến tính bão hịa Hàm dạng S lưỡng cực 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 45 Mạng truyền thẳng 3 lớp 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 46 Biểu thức ngõ ra mạng truyền thẳng 3 lớp ‘ Tổ ĩ t ố tí hiệ à tế bà thầ ki h thứ ở lớ ẩng c rọng s n u v o o n n q p n: ∑ = = m j jqjq xvnet 1 ‘ Ngõ ra tế bào thần kinh thứ q ở lớp ẩn: ( ) ⎟⎟⎞⎜⎜⎛== ∑m jqjhqhq xvanetaz ⎠⎝ =j 1 ‘ Tổng cĩ trọng số tín hiệu vào tế bào thần kinh thứ i ở lớp ra: ∑ = = l q qiqi zwnet 1 ( ) ⎟⎟⎞⎜⎜⎛== ∑ l qiqoioi zwanetay ‘ Ngõ ra tế bào thần kinh thứ i ở lớp ra: 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 47 ⎠⎝ =q 1 Thuật tốn huấn luyện cập nhật trọng số mạng ‘ Cậ hật t ố lớp n rọng s p ra: )()()()1( kzkkwkw qoiiqiq ηδ+=+ Trong đĩ: ))](())][()([()( knetakykdk ioiioi ′−=δ ‘ Cập nhật trọng số lớp ẩn: n ⎤⎡ )()()()1( kxkkvkv jhqqjqj ηδ+=+ ))(()()()( 1 knetakwkk qh i iqoihq ′⎥⎦⎢⎣ = ∑ = δδTrong đĩ: 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 48 Mạng hàm cơ sở xuyên tâm ∑∑ −−ll q2σ μx == == q iq q qiqi qewzwy 11 ‘Ngõ ra mạng RBF: 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 49 )()( q T qq μμμ −−=− xxxTrong đĩ Thuật tốn huấn luyện mạng RBF ‘ Cá h 1 dù th ật t á l t ề để h ấ l ệ RBFc : ng u o n an ruy n ngược u n uy n mạng ‘ Cách 2: huấn luyện mạng RBF qua 2 bước: ¾ Bước 1: Xác định tâm và độ phân tán của các hàm cơ sở dùng giải thuật phân nhĩm ố¾ Bước 2: Xác định trọng s lớp ra dùng giải thuật bình phương tối thiểu. 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 50 GIẢI THUẬT DI TRUYỀN 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 51 Giới thiệu GA GA l ø i ûi h ki á l øi i ûi ái h û h ù h‘ a g a t uật tìm em ơ g a to ưu p ong t eo qua trìn tiến hóa của sinh vật trong tự nhiên. ‘ Quá trình tiến hóa: Ž Chọn lọc tự nhiên (Natural Selection) Ž Lai ghép (sinh sản) (Crossover) Ž Đột biến (Mutation) 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 52 Lưu đồ giải thuật 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 53 Giải bài toán dùng giải thuật di truyền 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 54 Giải bài toán dùng giải thuật di truyền øi ù ái h ù b û à i ûi l h đi à khi å‘ Ba toan to ưu oa cơ an can g a trong ĩn vực eu en: min J(θ) với θ [θ θ θ ]T = 1, 2,, n 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 55 Mã hóa h ù hị h‘ Mã oa n p ân ‘ Mã hóa thập phân ‘ Mã hóa số thưc ï 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 56 Mã hóa nhị phân i à h i k ù hi 0 ø 1‘ Bộ g en gom a y ệu va . ‘ Mỗi biến được mã hóa thành một đoạn gien, chuỗi NST gồm nhiều đoan gien ï . ‘ Giả sử: Ž Biến θ cần tìm trong đoan θ ≤θ ≤ θ i ï i min i imax Ž Biến θi được mã hóa thành chuỗi nhị phân có độ dài Li ‘ Chiều dài của đoan gien đươc xác định dưa trên độ chính xác ï ï ï mong muốn tương ứng với mỗi biến: ⎟⎞⎜⎛ − iiL θθ minmaxl 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 57 ⎟⎠⎜⎝ = i i ε2og Mã hóa nhị phân ‘ M ãi đ õ hị h â đươ i ûi õ)(o oạn ma n p an ïc g a ma thành giá trị của biến θi như sau: ,,,..., 0121, iiiLii sssss i −= )( 12 minmax min iL ii ii sDVi − −+= θθθθ 1L trong đó DV(si) là giá trị thập phân của chuỗi si ∑− = = 0 .2)( i j ij j i ssDV 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 58 Thí dụ 1 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 59 Thí dụ 2: h ù hị h b øi ù ị h ø‘ Mã oa n p ân a toan tìm cực tr am: 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 60 Mã hóa thập phân ‘ Bộ gien gồm 10 ký hiệu 0 1 2 9 , , ,, ‘ Mỗi biến được mã hóa thành một đoạn gien: mỗi đoạn gien gồm có: Ž 1 gien để biểu diễn dấu của biến Ž các gien còn lại biểu diễn các chữ số có nghĩa ‘ Qui ước gien mã hóa dấu: ⎨⎧ −dấu:4-0 bằnggientrịGiá ‘ Vị trí dấu chấm thập phân của mỗi gien đươc lưu trữ để sử dung ⎩ + dấu :9-5 bằnggien trị Giá 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 61 ï ï khi giải mã Thí dụ 3 ‘ Nếu sử dụng cách mã hóa thập phân với 5 chữ số có nghĩa thì đoạn gien biểu diễn biến θi = −56.4172 là si = (056417), đồng thời lưu trữ vị trí dấu chấm thập phân là 2. ‘ Nếu sử dụng cách mã hóa thập phân với 4 chữ số có nghĩa, vị trí dấu chấm thập phân là 0 thì đoạn gien si = (71428), sẽ được giải mã thành lời giải θi = 0.1428. 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 62 Thí dụ 4 M h ù hậ h â b øi ù ì ị h ø‘ ã oa t p p an a toan t m cực tr am: 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 63 Hàm thích nghi ø h h hi d ø đ å đ ù h i ù ù ù h å ù h å ø ù đ‘ Ham t íc ng ung e an g a cac ca t e, ca t e nao co ộ thích nghi tốt hơn sẽ tồn tại qua quá trình chọn lọc tự nhiên và có nhiều cơ hội để lai ghép. ‘ Thường hàm thích nghi chính là hàm cần tìm cực trị hoặc biến đổi tương đương của hàm cần tìm cực trị. ‘ Các hàm thích nghi thường dùng: Ž Bài toán tìm cực đại hàm )(θJ Ž Bài toán tìm cưc tiểu hàm CJfitness += )(θ )(θJ ï CJ fitness += )( 1 θ 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 64 Chọn lọc tự nhiên ‘ N â t é ơ b û û ù hươ h ù h l l ø NST ù đ äguyen ac c an cua cac p ng p ap c ọn ọc a co o thích nghi càng cao thì có xác suất chọn lựa càng lớn. ‘ Các phương pháp chọn lọc Ž Chọn lọc tỉ lệ Ž Chọn lọc đấu vòng Ž Ch l étọn ọc ca Ž Chọn lọc sắp hạng tuyến tính Ž Chọn lọc sắp hạng lũy thừa. ‘ Cường độ chọn lọc σ MMI −= * trong đó M và M* là độ thích nghi trung bình của quần thể trước và sau chọn lọc, σ2 là phương sai của độ thích nghi trước 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 65 chọn lọc Chọn lọc tỉ lệ ‘ Xác suất chon loc tỉ lệ với độ thích nghiï ï 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 66 Chọn lọc đấu vòng ‘ Chon ra t cá thể ngẫu nhiên (t goi là qui mô đấu vòng) cá thểï ï , nào có độ thích nghi tốt nhất trong t cá thể trên sẽ được chọn để lai ghép. Lặp lại N lần bước trên để chọn đủ N cá thể. 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 67 Chọn lọc cắt ‘ Chon loc cắt với mức ngưỡng T (T ∈ [0 1]) chỉ có T N cá thểï ï , , . tốt nhất mới có cơ hội được lựa chọn và xác xuất chọn lựa của các cá thể này như nhau. 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 68 Chọn lọc cắt )2/( 2 2 11)( Cfe T TI −= π ∫∞ −= Cf f dfeT )2/( 2 2 1 π 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 69 Chọn lọc sắp hạng tuyến tính 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 70 Chọn lọc sắp hạng tuyến tính 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 71 Chọn lọc sắp hạng tuyến tính ⎥⎦ ⎤⎢⎣ ⎡ −−+= 1 1)1(21 N k N pk ηη − π ηη )1()( −=I 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 72 Chọn lọc sắp hạng lũy thừa 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 73 Chọn lọc sắp hạng lũy thừa 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 74 Chọn lọc sắp hạng lũy thừa )..1(; Nkcp N jN kN k == ∑ − 1cj= − απα )/ln(ln588.0)( ≈I α69.3 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 75 Lai ghép (Crossover) i h ù k á h đ đi å û h i S h đ å h i‘ La g ep et ợp ặc em cua a N T c a mẹ e tạo ra a NST con với triển vọng cha mẹ tốt sẽ tạo ra con tốt hơn. ‘ Phép lai ghép thường không tác động đến tất cả các NST mà trái lại chỉ xảy ra giữa hai NST cha mẹ được lựa chọn ngẫu nhiên với xác suất pC (gọi là xác suất lai ghép). é é 㑠Nguyên tac thực hiện phép lai ghép là bat cặp ngau nhiên hai NST trong quần thể sau khi đã qua bước chọn lọc để tạo ra hai NST con, mỗi NST con thừa hưởng một phần gien của cha, một phần gien của mẹ. ‘ Các phương pháp lai ghép: åŽ Lai ghép một điem Ž Lai ghép nhiều điểm Ž Lai ghép đều 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 76 Lai ghép một điểm 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 77 Lai ghép nhiều điểm 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 78 Lai ghép đều 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 79 Đột biến (Mutation) h ù ù đ bi á h đ åi ã hi h hi à‘ P ep toan ột en t ay o ngau n ên một oặc n eu gene của một cá thể để làm tăng sự đa dạng về cấu trúc trong quần thể. ‘ Đột biến chỉ được phép xảy ra với xác xuất pM thấp. ‘ Các phương pháp đột biến Ž Đột biến một biến Ž Đột biến nhiều điểm 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 80 Đột biến một điểm 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 81 Đột biến nhiều điểm 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 82 Các thông số của giải thuật di truyền h h ù à h å 20 30‘ Kíc t ươc quan t e: - ‘ Xác suất lai ghép: 0.8-0.9 ‘ Xác suất đột biến: 0 01 0 1. - . 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 83 Thí dụ: GA tìm cực tiểu hàm 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 84 Giải bài toán dùng giải thuật di truyền 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 85 Thí dụ GA tìm cực tiểu hàm (tt) h ù‘ Mã oa: ŽMã hóa thập phân ŽMỗi lời giải của bài toán tìm cưc trị là một cặp (x x ) đươcï 1, 2 ï mã hóa thành chuỗi NST có dạng như sau: 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 86 Thí dụ GA tìm cực trị hàm (tt) ø h h hi‘ Ham t íc ng : fitness = 1 ‘ Kích thước quần thể là N=20 Cxxf +),( 21 ‘ Khởi động: thế hệ đầu khởi động ngẫu nhiên. ‘ Các phép toán di truyền: Ž chọn lọc tỉ lệ Ž lai ghép 2 điểm với xác suất pC=0.9 á à Ꭰđột bien đeu với xác suat pM=0.1 Ž lưu giữ NST ưu việt trong quá trình tiến hóa. 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 87 Thí dụ GA tìm cực trị hàm (tt) á û h h h‘ Ket qua c ạy c ương trìn : 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 88 Thí dụ: GA tìm đường đi ngắn nhất é á åHoạch định đường đi ngan nhat cho robot di động giữa M điem có tọa độ biết trước để robot thực hiện một tác vụ nào đó. 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 89 Giải bài toán dùng giải thuật di truyền 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 90 Thí dụ GA tìm đường đi ngắn nhất h ù‘ Mã oa: Ž Đặt tên cho các điểm mà robot cần phải di chuyển tới là các số tư nhiên 1 2 Mï , ,, . ŽMột lời giải của bài toán tìm đường đi được mã hóa thành một chuỗi NST gồm có các gien là tên của các điểm Ž Chú ý do đường đi phải qua tất cả các điểm nên chuỗi NST hơp lệ phải có tên của tất cả các điểm và không có gien nàọ có giá trị giống nhau. 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 91 Thí dụ GA tìm đường đi ngắn nhất ø h h hi‘ Ham t íc ng : Ž Gọi là tọa độ của điểm thứ Ž D là độ dài đoan đường mà robot phải di chuyển ))(),(( iyix )..1(, Mii = ï . Ž Độ dài đường đi tương ứng với chuỗi NST gồm các gien đươc tính theo công thức:],,,[ 21 Mggg K ï 2 2 1 2 1 )]()([)]()([ M i iiii gygygxgxD +−+−= ∑ −− å å 2 1 2 1 )]()([)]()([ MM gygygxgx −+−+ = Ž Bài toán tìm cực tieu đường đi D được chuyen thành bài toán tìm cực đại hàm thích nghi định nghĩa như sau: 1 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 92 D fitness = Thí dụ GA tìm đường đi ngắn nhất Ch l hi‘ ọn ọc tự n ên: Ž Áp dụng phương pháp chọn lọc sắp hạng tuyến tính với hệ số chon loc là 5.0=−ηï ï Ž Chú ý rằng các phương pháp chọn lọc khác cũng có thể áp dụng 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 93 Thí dụ GA tìm đường đi ngắn nhất i h ù‘ La g ep 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 94 Thí dụ GA tìm đường đi ngắn nhất bi ᑠĐột en 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 95 Thí dụ GA tìm đường đi ngắn nhất á û‘ Ket qua Đồ thị thay đổi hàm thích nghi Đường đi ngắn nhất 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 96 Thí dụ GA ứng dụng trong bài toán đo tốc độ lưu chất é đ á đ l h á d ø h h ù û l ù û h‘ Nguyên tac o toc ộ ưu c at ung p ương p ap xư y an 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 97 Giải bài toán dùng giải thuật di truyền 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 98 Thí dụ GA ứng dụng trong bài toán đo tốc độ lưu chất Ả h h h û h 2 l à li i á ù h h kh û h øi‘ n ạt p an quang c ụp an ên t ep cac n au oang t ơ gian Δt 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 99 Thí dụ GA ứng dụng trong bài toán đo tốc độ lưu chất ‘ Vị trí trong tâm các điểm phản quangï 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 100 ‘ Bài toán đặt ra là tương ứng các điểm phản quang ở 2 ảnh Thí dụ GA ứng dụng trong bài toán đo tốc độ lưu chất ‘ Mã hóa Ž Giả sử các hạt phản quang trong hai ảnh lần lượt được đánh số thứ tự từ 1 đến n và 1 đến m (giả sử n>m) Ž Lời giải của bài toán tương ứng hạt phản quang là các cặp (ai,bi), với ai và bi là số nguyên hai bất kỳ thuộc đoạn [1,n] ø [1 ]va ,m , Ž Lời giải này có thể mã hóa thành một cá thể gồm hai chuỗi NST như sau: 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 101 Thí dụ GA ứng dụng trong bài toán đo tốc độ lưu chất ‘ Hàm thích nghi: Ž Hàm thích nghi đơn giản nhất là nghịch đảo tổng khoảng cách giữa các cặp tương ứng: 1 1 22 )]()([)]()([ − = ⎥⎦ ⎤⎢⎣ ⎡ −+−= ∑m i iiii byaybxaxfitness Ž Hàm thích nghi để ý đến tính chuyển động “cùng hướng” của các hat lân cận nhau:ï 1−⎤⎡ m l r 1 1= = ⎥⎦⎢⎣ −= ∑∑ i k ki rdfitness r 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 102 Thí dụ GA ứng dụng trong bài toán đo tốc độ lưu chất ‘ Chon loc tư nhiên:ï ï ï Ž Áp dụng phương pháp chọn lọc sắp hạng lũy thừa Ž Lưu giữ bảo toàn cá thể ưu việt 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 103 Thí dụ GA ứng dụng trong bài toán đo tốc độ lưu chất ‘ Lai ghép 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 104 Thí dụ GA ứng dụng trong bài toán đo tốc độ lưu chất ‘ Đột biến 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 105 Thí dụ GA ứng dụng trong bài toán đo tốc độ lưu chất ‘ Kết quả 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 106 GIẢI THUẬT DI TRUYỀN Mà HÓA SỐ THƯC Ï 2 April 2010 © H. T. Hồng - ÐHBK TPHCM 107 Giải thuật di truyền mã số thực ‘ C ù h õ h ù á thư bi å di ã ù i t ư ti á l ø ù á thưac ma oa so ïc: eu en cac g en r ïc ep a cac so ï