Home Page OR Soft Computing Research GIẢI THUẬT DI TRUYỀN MỜ
GIẢI THUẬT DI TRUYỀN MỜ

GIẢI THUẬT DI TRUYỀN MỜ

Nguyễn Như Phong

Kỹ thuật Hệ thống Công nghiệp

Đại học Bách Khoa, ĐHQG TPHCM

 

 

1. HỆ MỜ & GIẢI THUẬT DI TRUYỀN

 

Hệ mờ là hệ thống có cấu trúc hay tham số sử dụng lý thuyết mờ. Quan hệ giữa hệ mờ và giải thuật di truyền là 2 chiều:

  • Tối ưu hóa hệ mờ bằng giải thuật di truyền.
  • Mờ hóa giải thuật di truyền bằng lý thuyết mờ.

Ở một chiều, giải thuật di truyền dùng trong các vấn đề tối ưu hoá trong hệ mờ chẳng hạn như việc dùng giải thuật di truyền để các tối ưu hóa các luật suy diễn mờ trong bộ điều khiển mờ hay việc dùng giải thuật di truyền để xây dựng hàm thành viên tập mờ.

 

Ở chiều khác, lý thuyết mờ có thể dùng để mờ hoá giải thuật di truyền để có giải thuật di truyền mờ, là giải thuật hiệu quả hơn, phù hợp hơn giải thuật di truyền cổ điển trong một số áp dụng.

 

 

2. GIẢI THUẬT DI TRUYỀN MỜ

 

Giải thuật di truyền mờ là giải thuật di truyền đã được mờ hoá. Có 2 phương pháp cơ bản để mờ hoá giải thuật di truyền

  • Mờ hóa tập gien và việc mã hoá nhiễm sắc thể
  • Mờ hoá toán tử di truyền

 

a. Mờ hoá tập gien

 

Trong giải thuật di truyền kinh điển, các nhiễm sắc thể thường được mã hoá bở các số nhị phân, tập gien là tập nhị phân :

G = {0,1}

Giải thuật di truyền mờ mờ hoá tập gien bằng cách mở rộng tập gien trên toàn khoảng đơn vị :

            G = [0,1]

Khi mở rộng tập gien trên toàn khoảng đơn vị [0,1], ta không cần phải rời rạc hoá tập phương án như ở giải thuật kinh điển, điều này dẫn đến kết quả là giải thuật sẽ hội tụ nhanh hơn và tin cậy hơn trong việc tìm kiếm lời giải tối ưu mong muốn. Tuy nhiên cần tìm phương pháp thích hợp để mã hoá phương án bởi các nhiễm sắc thể có gien lấy từ tập gien là khoảng đơn vị.

 

Ví dụ:                                                                                                 

Xem lại ví dụ trên : Max f(x) = 2x-x2/16 , xÎ [0,31]

Sử dụng tập gien G=[0,1], ta không cần rời rạc hóa khoảng [0,31]. Một số bất kỳ trong khoảng [0,31] có thể được mã hoá bởi một nhiễm sắc thể có gien lấy từ tập gien G. Chẳng hạn như với nhiễm sắc thể sẽ là mã tương ứng của một số trong khoảng [0,31] được tính như sau :

 

Ví dụ :                                                                                      

Xem bài toán tìm đường đi của người bán hàng với 4 thành phố C1, C2, C3, C4 . Đường đi của người bán hàng có thể được mã hoá bởi nhiễm sắc thể C = 1, x2, x3, x4> trong đó gien xi (i=1÷4) , tương ứng với thành phố Ci, lấy trị trong tập gien G=[0,1] , biễu thị mức độ thành phố được viếng sớm. Chẳng hạn với nhiễm sắc thể là mã của đường đi C3àC4à C2 à C1 à C3

 

b. Mờ hoá toán tử di truyền

 

Việc mở rộng tập gien G từ tập nhị phân {0,1} thành khoảng đơn vị [0,1] trong giải thuật được xem là mờ hoá giải thuật. Tuy nhiên để tăng tính xác thực trong việc mờ hoá giải thuật, ta thường mờ hoá toán tử di truyền

 

Thực tế giải thuật di truyền mờ không chỉ mờ hoá tập gien G, mà còn yêu cầu mờ hoá cả toán tử di truyền. Sanchez [1993] đề nghị một phương pháp mờ hoá toán tử lai ghép. Toán tử lai ghép kinh điển lai ghép các nhiễm sắc thể phối ngẫu x và y của tập Gn:

,

Nhằm lai ghép ở vị trí lai ghép i, iÎNn-1, có thể dùng khuông t:

Các nhiễm sắc thể con sau lai ghép x’ và y’ định bởi khuông t như sau :

            x' = ( x Ù t ) Ú ( y Ù`t  )

            y' = (x Ù`t ) Ú ( y Ù t )

Trong đó:         Ù - toán tử min

Ú - toán tử max

`t   = <`tj ½`tj  =1-tj >

Toán tử lai ghép kinh điển ở trên tạo sự thay đổi đột ngột ở vị trí lai ghép i của nhiễm sắc thể. Việc thay đổi có thể thức hiện dần dần với điểm lai ghép mờ bằng cách dùng khuôn mờ. Khuôn mờ f  cùng các nhiễm sắc thể con x’ và y’, lai ghép từ cặp nhiễm sắc thể phối ngẫu x và y được xác định như sau :

Hay chi tiết hơn :

 

 

 

 

TLTK

Nguyễn Như Phong. Vận trù mềm. NXBĐHBK. 2013.

 

 

 
  • thiet ke noi that chung cu

  • thiet ke noi that chung cu

  • thiet ke noi that chung cu

  • thiet ke noi that chung cu

ABOUT US

ADMIN


GOOD BROWSERS

 
   

STATISTIC

mod_vvisit_countermod_vvisit_countermod_vvisit_countermod_vvisit_countermod_vvisit_countermod_vvisit_countermod_vvisit_counter
mod_vvisit_counterH�m nay136
mod_vvisit_counterH�m qua199
mod_vvisit_counterTu?n n�y1276
mod_vvisit_counterTh�ng n�y1276
mod_vvisit_counterT?t c?731332
Hiện có 15 khách Trực tuyến