ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
NGUYỄN ĐỨC VĂN
GIẢI PHÁP TỐI ƯU CÁC THAM SỐ ĐỊNH LƯỢNG NGỮ NGHĨA CỦA ĐẠI SỐ GIA TỬ VÀ ỨNG DỤNG CHO BÀI TOÁN LẬP LUẬN XẤP XỈ MỜ TRONG ĐIỀU KHIỂN
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
THÁI NGUYÊN - 2018
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
NGUYỄN ĐỨC VĂN
GIẢI PHÁP TỐI ƯU CÁC THAM SỐ ĐỊNH LƯỢNG NGỮ NGHĨA CỦA ĐẠI SỐ GIA TỬ VÀ ỨNG DỤNG CHO BÀI TOÁN LẬP LUẬN XẤP XỈ MỜ TRONG ĐIỀU KHIỂN
Chuyên ngành: KHOA HỌC MÁY TÍNH
Mã số: 60.48.01.01
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
Người hướng dẫn khoa học: TS. NGUYỄN DUY MINH
THÁI NGUYÊN - 2018
i
LỜI CAM ĐOAN
Tôi xin cam đoan kết quả đạt được trong luận văn là sản phẩm của cá nhân dưới sự hướng dẫn khoa học của TS. Nguyễn Duy Minh. Trong toàn bộ nội dung luận văn, những nội dung được trình bày là của cá nhân hoặc tổng hợp từ nhiều nguồn tài liệu khác nhau. Tất cả các tài liệu tham khảo đó đều có xuất xứ rõ ràng và được trích dẫn hợp pháp.
Tôi xin chịu trách nhiệm và chịu mọi hình thức kỷ luật theo quy định cho
lời cam đoan của mình.
Thái Nguyên, 15 tháng 4 năm 2018
Tác giả
Nguyễn Đức Văn
ii
LỜI CẢM ƠN
Em xin gửi lời cảm ơn chân thành đến TS. Nguyễn Duy Minh - người hướng dẫn khoa học, thầy đã định hướng và nhiệt tình hướng dẫn, giúp đỡ em trong quá trình làm luận văn.
Em xin gửi lời biết ơn sâu sắc đến quý thầy cô giáo trường Đại học Công nghệ thông tin và Truyền thông; Viện công nghệ thông tin thuộc Viện hàn lâm Khoa học và Công nghệ Việt Nam đã truyền đạt những kiến thức và kinh nghiệm quý báu cho chúng em trong thời gian học tập.
Xin chân thành cảm ơn các bạn bè, đồng nghiệp, ban cán sự và các học viên lớp cao học CK15A, những người thân trong gia đình đã động viên, chia sẻ, tạo điều kiện giúp đỡ trong suốt quá trình học tập và làm luận văn.
Thái Nguyên, 15 tháng 4 năm 2018
Tác giả
Nguyễn Đức Văn
iii
MỤC LỤC
MỤC LỤC ........................................................................................................ iii
DANH MỤC BẢNG ......................................................................................... v
DANH MỤC HÌNH ......................................................................................... vi
DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT ..................................... vii
MỞ ĐẦU ........................................................................................................... 1
CHƯƠNG 1: GIỚI THIỆU MỘT SỐ KIẾN THỨC CƠ SỞ ..................... 3
1.1. Biến ngôn ngữ và mô hình mờ ................................................................... 3
1.1.1. Biến ngôn ngữ ..................................................................................... 3
1.1.2. Mô hình mờ ......................................................................................... 4
1.2. Đại số gia tử ............................................................................................... 5
1.2.1. Độ đo tính mờ của các giá trị ngôn ngữ .............................................. 6
1.2.2. Hàm định lượng ngữ nghĩa ................................................................. 9
1.2.3. Đại số gia tử tuyến tính đầy đủ ......................................................... 10
1.2.4. Khái niệm ngưỡng hiệu chỉnh định lượng ngữ nghĩa ....................... 12
1.3. Phương pháp lập luận xấp xỉ mờ đa điều kiện ......................................... 13
1.4. Bài toán tối ưu và giải thuật di truyền ...................................................... 15
1.4.1. Bài toán tối ưu ................................................................................... 15
1.4.2.1. Các khái niệm cơ bản của giải thuật di truyền ............................................................ 16
1.4.2.2. Cơ chế thực hiện của giải thuật di truyền .................................................................... 19
1.4.2.3. Các phương pháp biểu diễn nhiễm sắc thể và các toán tử di truyền chuyên biệt ........ 22
1.4.2.4. Biểu diễn thực ............................................................................................................. 22
1.4.2.5. Các toán tử chuyên biệt hoá ........................................................................................ 23
1.4.2. Giải thuật di truyền ........................................................................... 16
1.5. Kết luận Chương 1 ................................................................................... 25
CHƯƠNG 2: GIẢI PHÁP TỐI ƯU CÁC THAM SỐ ĐỊNH LƯỢNG NGỮ NGHĨA CHO PHƯƠNG PHÁP LẬP LUẬN MỜ DỰA TRÊN ĐẠI SỐ GIA TỬ .................................................................................................... 26
2.1. Phương pháp lập luận mờ sử dụng đại số gia tử ...................................... 26
2.2. Các giải pháp tối ưu các tham số định lượng ngữ nghĩa .......................... 29
iv
2.3. Giải pháp xác định các tham số định lượng ngữ nghĩa tối ưu ................. 32
2.3.1. Giải pháp tối ưu các tham số của đại số gia tử ................................. 32
2.3.2.1. Phân tích ảnh hưởng các tham số hiệu chỉnh .............................................................. 33
2.3.2.2. Thuật toán xác định mô hình định lượng ngữ nghĩa tối ưu ......................................... 34
2.3.2. Giải pháp xác định mô hình định lượng ngữ nghĩa tối ưu ................ 33
2.4. Phương pháp lập luận mờ sử dụng đại số gia tử dựa trên các mô hình định lượng ngữ nghĩa tối ưu. ................................................................................... 36
2.4.1. Vấn đề xác định giá trị định lượng ngữ nghĩa tối ưu ........................ 36
2.4.2. Sử dụng tham số hiệu chỉnh tối ưu cho phương pháp lập luận mờ sử dụng đại số gia tử ........................................................................................ 37
2.5. Tổng kết Chương 2 .................................................................................. 39
CHƯƠNG 3: ỨNG DỤNG PHƯƠNG PHÁP LẬP LUẬN XẤP XỈ MỜ SỬ DỤNG ĐẠI SỐ GIA TỬ VỚI MÔ HÌNH ĐỊNH LƯỢNG NGỮ NGHĨA TỐI ƯU TRONG ĐIỀU KHIỂN ................................................................. 40
3.1. Mô tả một số bài toán điều khiển logic mờ .............................................. 40
3.1.1. Bài toán 1: Xấp xỉ mô hình mờ EX1 của Cao-Kandel [9] ................ 40
3.1.2. Bài toán 2: Bài toán hệ con lắc ngược [8] ......................................... 41
3.2. Ứng dụng phương pháp lập luận xấp xỉ mờ sử dụng đại số gia tử trong điều khiển ................................................................................................................ 43
3.2.1. Phương pháp điều khiển logic mờ truyền thống ............................... 43
3.2.2. Phương pháp lập luận xấp xỉ mờ sử dụng đại số gia tử trong điều khiển 44
3.2.3. Phương pháp lập luận xấp xỉ mờ sử dụng đại số gia tử với các mô hình định lượng ngữ nghĩa tối ưu trong điều khiển .................................... 47
3.3. Ứng dụng .................................................................................................. 48
3.3.1. Bài toán 1 .......................................................................................... 48
3.3.2. Bài toán 2 .......................................................................................... 52
3.4. Kết luận Chương 3 ................................................................................... 55
KẾT LUẬN .................................................................................................... 57
TÀI LIỆU THAM KHẢO ............................................................................... 58
v
DANH MỤC BẢNG
Bảng 2. 1. So sánh các giá trị ĐLNN .............................................................. 31
Bảng 3. 1. Mô hình EX1 của Cao-Kandel ....................................................... 40
Bảng 3. 2. Các kết quả xấp xỉ EX1 tốt nhất của Cao-Kandel [9] .................... 41
Bảng 3. 3. Mô hình FAM cho hệ con lắc ngược ............................................. 43
Bảng 3. 4. Mô hình SAM gốc - xấp xỉ mô hình EX1 ...................................... 50
Bảng 3. 5. Mô hình SAM (PAR2) – xấp xỉ mô hình EX1 ................................ 50
Bảng 3. 6. Sai số lớn nhất của các phương pháp trên mô hình EX1 ............... 51
Bảng 3. 7. Chuyển nhãn ngôn ngữ cho các biến X1, X2 .................................. 52
Bảng 3. 8. Nhãn ngôn ngữ cho biến u ............................................................. 52
Bảng 3. 9. Mô hình SAM gốc của hệ con lắc ngược ...................................... 52
Bảng 3. 10. Mô hình SAM(PAR2) của hệ con lắc ngược................................. 53
Bảng 3. 11. Sai số các phương pháp của hệ con lắc ngược ............................ 55
vi
DANH MỤC HÌNH
Hinh 1. 1 Độ đo tính mờ ................................................................................... 8
Hinh 1. 2. Mã hoá nhị phân biểu diễn các cá thể ............................................ 17
Hinh 1. 3. Biểu diễn giá trị của đối với hai lần được chọn .......................... 24
Hình 3. 1. Đường cong thực nghiệm của mô hình EX1 ................................. 41
Hình 3. 2. Mô tả hệ con lắc ngược .................................................................. 42
Hình 3. 3. Sơ đồ phương pháp điều khiển CFC .............................................. 44
Hình 3. 4. Sơ đồ phương pháp điều khiển FCHA ........................................... 45
Hình 3. 5. Kết quả xấp xỉ mô hình EX1 của Cao Kandel ............................... 51
Hình 3. 6. Đồ thị lỗi của hệ con lắc ngược ..................................................... 55
vii
DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT
Các ký hiệu:
Tổng độ đo tính mờ của các gia tử âm
Tổng độ đo tính mờ của các gia tử dương
Giá trị định lượng của phần tử trung hòa
Đại số gia tử AX
Đại số gia tử tuyến tính đầy đủ AX*
Phần tử trung hòa trong đại số gia tử W
Ngưỡng hiệu chỉnh định lượng ngữ nghĩa 𝜀
δ Tham số hiệu chỉnh giá trị định lượng ngữ nghĩa
c-, c+ Các phần tử sinh
Các chữ viết tắt:
Định lượng ngữ nghĩa ĐLNN
Đại số gia tử ĐSGT
Genetic Algorithm GA
FMCR Fuzzy Multiple Conditional Reasoning
Fuzzy Associative Memory FAM
Semantic Associative Memory SAM
Hedge Algebras Reasoning HAR
OpPAR Optimal - Parameter
Conventional Fuzzy Control CFC
Fuzzy Control Using Hedge Algebras FCHA
FCOPHA Fuzzy Control using Optimal Hedge Algebras
1
MỞ ĐẦU
Khoa học ngày càng phát triển thì càng có nhiều thiết bị máy móc hỗ trợ cho đời sống con người. Các thiết bị máy móc càng “thông minh” thì càng thay thế sức lao động và do đó các thiết bị dạng này dường như là một trong những cái đích mà con người vươn tới. Như vậy, nhu cầu thiết yếu của cuộc sống là tạo ra các máy móc có thể hành xử giống với con người. Hay nói cách khác là các máy phải biết suy luận để đưa ra các quyết định đúng đắn.
Người tiên phong trong lĩnh vực này là Zadeh [11]. Trong các công trình của mình ông đã mô tả một cách toán học những khái niệm mơ hồ mà ta thường gặp trong cuộc sống như: cao, thấp; đúng, sai bằng các tập mờ. Nhờ việc xây dựng lý thuyết tập mờ mà con người có thể suy diễn từ khái niệm mơ hồ này đến khái niệm mơ hồ khác mà bản thân logic kinh điển không làm được. Trên cơ sở các thông tin không chính xác thu được, người ta có thể đưa ra những quyết định hiệu quả cho từng tình huống của bài toán.
Tuy nhiên, phương pháp lập luận của con người là vấn đề phức tạp và không có cấu trúc. Vì vậy kể từ khi lý thuyết tập mờ ra đời cho đến nay, vẫn chưa có một cơ sở lý thuyết hình thức chặt chẽ theo nghĩa tiên đề hoá cho logic mờ và lập luận mờ.
Để đáp ứng phần nào đối với nhu cầu xây dựng cơ sở toán học cho việc lập luận ngôn ngữ, N.Cat Ho và Wechler [12] đã đề xuất cách tiếp cận dựa trên cấu trúc tự nhiên của miền giá trị của các biến ngôn ngữ, trong các công trình, các tác giả đã chỉ ra rằng, những giá trị của biến ngôn ngữ trong thực tế đều có thứ tự nhất định về mặt ngữ nghĩa, ví dụ ta hoàn toàn có thể cảm nhận được rằng, ‘trẻ’ là nhỏ hơn ‘già’, hoặc ‘nhanh’ luôn lớn hơn ‘chậm’.
Với việc định lượng các từ ngôn ngữ của ĐSGT, một số phương pháp lập luận nội suy ra đời nhằm mục đích giải quyết bài toán lập luận mờ đa điều kiện, một bài toán được ứng dụng nhiều trong tự nhiên, kỹ thuật [11], các phương pháp lập luận này được gọi là các phương pháp lập luận xấp xỉ mờ sử dụng ĐSGT. Tuy nhiên khi thực hiện phương pháp lập luận còn tồn tại: Trong ĐSGT, việc ánh xạ ĐLNN bảo toàn thứ tự ngữ nghĩa định tính, vì vậy phương pháp ĐLNN này hàm chứa những lợi thế trong việc chuyển trung thành các mô hình mờ sang mô hình định lượng (theo trực giác) để giải các bài toán ứng dụng. Tuy nhiên mô hình định lượng tương đối hợp lý nhưng chưa tối ưu. Vì vậy ta phải nghiên cứu một số giải
2
pháp tìm ra được mô hình ĐLNN tối ưu nhất (các tham số ĐLNN của các ĐSGT tối ưu) nhưng vẫn phải đảm bảo thứ tự ngữ nghĩa của ĐSGT.
Với lý do như vậy đề tài “Giải pháp tối ưu các tham số ĐLNN của ĐSGT và ứng dụng cho bài toán lập luận xấp xỉ mờ trong điều khiển” nghiên cứu và đưa ra giải pháp tối ưu các tham số ĐLNN của phương pháp lập luận mờ dựa trên ĐSGT.
Giải pháp tối ưu các tham số ngữ nghĩa định lượng này được cài đặt thử nghiệm trên một số bài toán lập luận xấp xỉ mờ dựa trên ĐSGT trong điều khiển, các kết quả sẽ được đánh giá và so sánh với các phương pháp lập luận khác đã được công bố.
3
CHƯƠNG 1: GIỚI THIỆU MỘT SỐ KIẾN THỨC CƠ SỞ
1.1. Biến ngôn ngữ và mô hình mờ
1.1.1. Biến ngôn ngữ
Một biến ngôn ngữ là biến mà “các giá trị của nó là các từ hoặc câu trong ngôn ngữ tự nhiên hoặc ngôn ngữ nhân tạo”. Ví dụ như khi nói về nhiệt độ ta có thể xem đây là biến ngôn ngữ có tên gọi NHIỆT_ĐỘ và nó nhận các giá trị ngôn ngữ như “cao”, “rất cao”, “trung bình”… Đối với mỗi giá trị này, chúng ta sẽ gán cho chúng một hàm thuộc. Giả sử lấy giới hạn của nhiệt độ trong đoạn [0, 230oC] và giả sử rằng các giá trị ngôn ngữ được sinh bởi một tập các quy tắc. Khi đó, một cách hình thức, chúng ta có định nghĩa của biến ngôn ngữ sau đây:
Định nghĩa 1.1. Biến ngôn ngữ là một bộ gồm năm thành phần (X,T(X), U, R, M), trong đó X là tên biến, T(X) là tập các giá trị ngôn ngữ của biến X, U là không gian tham chiếu của biến cơ sở u, mỗi giá trị ngôn ngữ xem như là một biến mờ trên U kết hợp với biến cơ sở u, R là một qui tắc cú pháp sinh các giá trị ngôn ngữ cho tập T(X), M là qui tắc ngữ nghĩa gán mỗi giá trị ngôn ngữ trong T(X) với một tập mờ trên U.
Ví dụ 1.1. Từ định nghĩa trên ta có tên biến ngôn ngữ X chính là NHIỆT_ĐỘ, biến cơ sở u có miền xác định là U = [0, 230] tính theo oC. Tập các giá trị ngôn ngữ tương ứng của biến ngôn ngữ là T(NHIỆT_ĐỘ) = {cao, rất cao, tương_đối cao, thấp, rất thấp, trung bình, …}. R là một qui tắc để sinh ra các giá trị này. M là quy tắc gán ngữ nghĩa sao cho mỗi một giá trị ngôn ngữ sẽ được gán với một tập mờ. Chẳng hạn, đối với giá trị nguyên thủy cao, M(cao) = {(u, cao(u) | u [0, 230]}, được gán như sau:
cao(u) =
Ngữ nghĩa của các giá trị khác trong T(NHIỆT_ĐỘ) cũng có thể tính thông qua tập mờ của các giá trị nguyên thủy bởi các phép toán tương ứng với các gia tử tác động như rất, tương_đối,…
4
1.1.2. Mô hình mờ
Cấu trúc của một mô hình mờ chính là một tập bao gồm các luật mà mỗi luật là một mệnh đề dạng “If…then…”, trong đó phần “If” được gọi là mệnh đề điều kiện hay tiền đề còn phần “then” được gọi là phần kết luận.
Mô hình mờ dạng đơn giản hay còn gọi là mô hình SISO (Single Input Single Output) là tập các luật mà trong đó mỗi luật chỉ chứa một điều kiện và một kết luận được cho như sau:
if X = A1 then Y = B1
(1.1) if X = A2 then Y = B2
. . . . . . . .
if X = An then Y = Bn
trong đó X, Y là các biến ngôn ngữ thuộc không gian U, V tương ứng và
các giá trị ngôn ngữ A1, A2,…, An, B1, B2, …, Bn là các tập mờ.
Tuy nhiên, trong một số lĩnh vực, chẳng hạn như trong điều khiển, sự phụ thuộc giữa các biến vật lý không chỉ biểu diễn ở dạng đơn giản như mô hình trên mà nó bao gồm nhiều điều kiện ràng buộc. Vì vậy, một mô hình mờ ở dạng tổng quát là một tập các luật (mệnh đề If-then) mà phần tiền đề của mỗi luật là một điều kiện phức được viết như sau:
If X1 = A11 and ... and Xm = A1m then Y = B1
If X1 = A21 and ... and Xm = A2m then Y = B2
. . . . . . . . (1.2)
If X1 = An1 and ... and Xm = Anm then Y = Bn
ở đây X1, X2, …, Xm và Y là các biến ngôn ngữ, Aij, Bi (i = 1,…, n; j =
1,…, m) là các giá trị ngôn ngữ tương ứng ([11]).
Hầu hết các ứng dụng trong hệ chuyên gia mờ, phân cụm mờ, điều khiển mờ,… liên quan đến việc suy diễn thì mô hình mờ là một phần không thể thiếu và do vậy các ứng dụng này luôn gắn liền với các phương pháp giải quyết bài toán lập luận xấp xỉ đa điều kiện. Bài toán lập luận xấp xỉ mờ đa điều kiện được phát biểu như dưới đây:
Cho mô hình mờ (1.2) và các giá trị ngôn ngữ A01, A02, …, A0m tương ứng
với các biến ngôn ngữ X1, X2, …, Xm . Hãy tính giá trị của Y.
5
Có nhiều phương pháp để giải quyết bài toán này. Các phương pháp cụ
thể sẽ được trình bày ở Mục 1.3.
1.2. Đại số gia tử
Trong mô hình mờ thường dùng các mô tả ngôn ngữ cho các biến vật lý. Với mỗi biến ngôn ngữ X, gọi X = Dom(X) là tập các giá trị ngôn ngữ của biến X. Miền giá trị X được xem như một ĐSGT AX = (X, G, H, ) trong đó G là tập các phần tử sinh, H là tập các gia tử còn “” là quan hệ cảm sinh ngữ nghĩa trên X. Ta cũng giả thiết rằng trong G có chứa các phần tử 0, 1, W với ý nghĩa là phần tử bé nhất, phần tử lớn nhất và phần tử trung hòa (neutral) trong X.
Nếu tập X và H là các tập sắp thứ tự tuyến tính, khi đó ta nói AX = (X, C,
H, ) là ĐSGT tuyến tính.
Khi tác động gia tử h H vào phần tử x X, thì ta thu được phần tử ký hiệu hx. Với mỗi x X ta ký hiệu H(x) là tập tất cả các phần tử u thuộc X xuất phát từ x bằng cách sử dụng các gia tử trong H và ta viết u = hn…h1x, với hn, …, h1 H.
Bây giờ chúng ta sẽ xét một vài tính chất được phát biểu trong các định lý
dưới đây của ĐSGT tuyến tính.
Định lý 1.1. ([12]) Cho tập H– và H+ là các tập sắp thứ tự tuyến tính của
ĐSGT AX = (X, G, H, ). Khi đó ta có các khẳng định sau:
(1) Với mỗi u X thì H(u) là tập sắp thứ tự tuyến tính.
(2) Nếu X được sinh từ G bởi các gia tử và G là tập sắp thứ tự tuyến tính thì X cũng là tập sắp thứ tự tuyến tính. Hơn nữa nếu u < v, và u, v là độc lập với nhau, tức là u H(v) và v H(u), thì H(u) H(v).
Một cách tổng quát hơn như đã chứng minh trong tài liệu ([12]), mỗi miền ngôn ngữ của biến ngôn ngữ có thể được tiên đề hóa và được gọi là ĐSGT AX = (X, G, H, ), trong đó H là tập thứ tự tuyến tính bộ phận. Chúng ta có định lý sau.
Định lý 1.2. ([12]) Cho ĐSGT AX = (X, G, H, ). Khi đó ta có các khẳng
định sau:
(1) Các toán tử trong Hc là so sánh được với nhau, c {+, –}.
6
(2) Nếu x X là điểm cố định đối với toán tử h H, tức là hx = x, thì nó
là điểm cố định đối với các gia tử khác.
(3) Nếu x = hn…h1u thì tồn tại chỉ số i sao cho hi…h1u của x là một biểu diễn chuẩn của x tương ứng với u (x = hi…h1u và hi…h1u ≠ hi-1…h1u) và hjx = x với mọi j > i.
(4) Nếu h ≠ k và hx = kx thì x là điểm cố định.
(5) Với bất kỳ gia tử h, k H, nếu x ≤ hx (x ≥ hx) thì x <≤ hx (x ≥> hx) và
nếu hx < kx, h ≠ k, thì hx <≤ kx.
Trong [9] các tác giả đã chỉ ra rằng mỗi ĐSGT đầy đủ là một dàn với phần
tử đơn vị là 1 và phần tử không là 0.
Để thuận tiện về sau, chúng ta nêu ra định lý kế tiếp dùng để so sánh hai
phần tử trong miền ngôn ngữ của biến ngôn ngữ X.
Định lý 1.3. Cho x = hn…h1u và y = km…k1u là hai biểu diễn chuẩn của x và y tương ứng với u. Khi đó tồn tại chỉ số j ≤ min{n, m} + 1 sao cho hj’ = kj’ với mọi j’ < j (ở đây nếu j = min {m, n} + 1 thì hoặc hj là toán tử đơn vị I, hj = I, j = n + 1 ≤ m hoặc kj = I, j = m + 1 ≤ n) và
(1) x < y khi và chỉ khi hjxj < kjxj, trong đó xj = hj-1...h1u.
(2) x = y khi và chỉ khi m = n và hjxj = kjxj.
(3) x và y là không so sánh được với nhau khi và chỉ khi hjxj và kjxj là
không so sánh được với nhau.
1.2.1. Độ đo tính mờ của các giá trị ngôn ngữ
Khái niệm độ đo tính mờ của các giá trị ngôn ngữ là một khái niệm trừu tượng không dễ để xác định bằng trực giác và có nhiều cách tiếp cận khác nhau, để xác định khái niệm này. Thông thường, trong lý thuyết tập mờ, các cách tiếp cận chủ yếu là dựa trên hình dạng của tập mờ. Với ĐSGT có thể xác định được độ đo tính mờ của các giá trị ngôn ngữ một cách hợp lý.
Giá trị ngôn ngữ nào càng đặc trưng thì độ đo tính mờ càng nhỏ. Chẳng hạn, độ đo tính mờ của giá trị ngôn ngữ More_or_less True (MLtrue), Possibly True là nhỏ hơn độ đo tính mờ của True. Tuy nhiên trong lý thuyết tập mờ không thể hiện được điều đó. Thật vậy, giả sử ngữ nghĩa của giá trị ngôn ngữ được biểu diễn bởi tập mờ. Độ đo tính mờ của các giá trị ngôn ngữ là khoảng cách giữa tập mờ biểu thị cho giá trị ngôn ngữ đó với tập rõ gần nó nhất. Nếu
7
chúng ta biểu diễn từ true bởi hàm thuộc µtrue(t)= t trên đoạn [0,1] và MLtrue bởi µMLtrue(t) = tα với α = 2/3 < 1 thì độ đo tính mờ của true bằng 1/4, nhưng độ đo tính mờ của MLtrue bằng
Rõ ràng cách xác định độ đo tính mờ như vậy là không thích hợp so với ý kiến ban đầu đặt ra. Vì vậy để xác định độ đo tính mờ một cách hợp lý, trước hết chúng ta phải tìm ra một số tính chất trực giác về độ đo tính mờ của giá trị ngôn ngữ. Những tính chất này chính là nền tảng cho việc xác lập các định nghĩa.
Ký hiệu fm(τ) là độ đo tính mờ của phần tử τ, τ X và chúng ta cũng giả sử rằng độ đo tính mờ của mỗi phần tử luôn thuộc đoạn [0,1]. Một số tính chất trực giác của fm(τ):
(1) fm(τ) = 0, nếu τ là giá trị rõ.
(2) Nếu h là một gia tử và τ là giá trị mờ thì hτ đặc trưng hơn τ, vì vậy ta
có fm(hτ) < fm(τ).
(3) Xét hai phần tử sinh true và false của ĐSGT. Vì đây là các khái niệm trái ngược nhau nhưng bổ sung cho nhau nên chúng ta có thể chấp nhận điều kiện sau:
fm(true) + fm(false) ≤ 1.
Chúng ta nhận thấy rằng, nếu fm(true) + fm(false) < 1 thì bắt buộc phải tồn tại khái niệm τ khác bổ sung cho cả true và false để fm(true) + fm(false) + fm(τ) = 1. Trường hợp này không tồn tại trong ngôn ngữ tự nhiên. Vì thế, ta có fm(true) + fm(false) = 1. Từ đó suy ra rằng, nếu c+, c– là hai phần tử sinh trong X thì:
fm(c+) + fm(c–) = 1
(4) Bây giờ chúng ta xét tập gia tử H = {Very, More, Possibly, Little} và tập các giá trị H[true] = {VeryTrue, MoreTrue, PossiblyTrue, LittleTrue}, tất cả các phần tử của tập này đều đặc trưng hơn true. Theo nhận định ở điểm (2), độ đo tính mờ của true lớn hơn mọi độ đo của các phần tử trong H[true]. Chúng ta có thể xác định một cách trực giác rằng độ đo tính mờ của true được thiết lập thông qua độ đo tính mờ của các phần tử bắt nguồn từ true và chấp nhận điều kiện sau đây:
8
fm(Very true) + fm(More true) + fm(Poss. true) + fm(Little true) ≤
fm(true).
Tương tự như thảo luận trong (3), ta có:
fm(Very true) + fm(More true) + fm(Poss. true) + fm(Little true) =
fm(true).
Một cách tổng quát, giả sử τ là giá trị ngôn ngữ bất kỳ thuộc X thì:
fm(Very τ) + fm(More τ) + fm(Poss. τ) + fm(Little τ) = fm(τ).
Cuối cùng chúng ta có thể biểu diễn độ đo tính mờ của biến ngôn ngữ
TRUTH như trong Hình 1.1 dưới đây.
True
More
Poss.
True
True
LittleTrue
VeryTrue
1
W
fm(MLTr)
fm(PVTr)
fm(VVTr)
fm(LLTr)
fm(M Tr)
fm(LVTr)
fm(VLTr)
fm(MVTr)
fm(PLTr)
fm(LittleTr)
fm(VeryTrue)
fm(PossTr))
fm(True)
Hinh 1. 1 Độ đo tính mờ Hình 1. 1. Độ đo tính mờ
Định nghĩa 1.2. Xét đại số gia tử AX = (X, G, H, ) của biến ngôn ngữ X. Một hàm φ: X → [0,1] được gọi là hàm độ đo tính mờ trên X nếu tồn tại một xác suất P trên X sao cho P xác định trên tập H(τ). Với mỗi phần tử τ X thì P(H(τ)) = 0 nếu τ {0, 1, W} và φ(τ) = P(H(τ)).
Từ định nghĩa ta thấy “kích cỡ” của tập H(τ) thể hiện độ đo tính mờ của phần tử τ. Chúng ta dễ dàng nhận ra rằng hàm φ thỏa mọi tính chất trực giác đã đề xuất trên. Cụ thể là:
Tính chất (p1): φ(0) = φ(1) = φ(W) = 0.
Tính chất (p2): φ(hτ) ≤ φ(τ), với mọi τ X và h H.
Tính chất (p3): φ(c–) + φ(c+) = 1, với c–, c+ là hai phần tử sinh trong X.
9
Tính chất (p4): , τ X.
Chúng ta cũng có thể viết lại tính chất (p4) như sau: ,
tổng này không thay đổi với mọi τ X. Chúng ta có thể xem tỷ lệ φ(hτ)/φ(τ) là một hằng số và nó đặc trưng cho gia tử h. Ta có tính chất sau:
Tính chất (p5): Tỷ lệ φ(hτ)/φ(τ) không phụ thuộc vào τ và nó được gọi là
độ đo tính mờ của gia tử h, ký hiệu µ(h).
Định lý 1.4. Độ đo tính mờ trên X là duy nhất được xác định bởi các tham số φ(c–), φ(c+) và µ(h), h H thỏa các đẳng thức sau: φ(c–) + φ(c+) = 1, và φ(x) được định nghĩa đệ quy bởi công thức φ(hx’) = µ(h)φ(x’),
với x = hx’, h H.
1.2.2. Hàm định lượng ngữ nghĩa
Nhu cầu tự nhiên trong cách tiếp cận tính toán lập luận của con người là định lượng các giá trị ngôn ngữ, chẳng hạn như trong các lĩnh vực phân cụm mờ, điều khiển mờ, …
Theo cách tiếp cận của tập mờ, các giá trị định lượng của mỗi tập mờ là giá trị khử mờ của hàm thuộc tương ứng. Đối với ĐSGT, vì các giá trị ngôn ngữ tuân theo thứ tự ngữ nghĩa nên chúng ta sẽ thiết lập hàm định lượng các từ (giá trị ngôn ngữ) vào đoạn [0,1] đảm bảo thứ tự, hàm này được gọi là hàm ĐLNN.
Xét ĐSGT AX = (X, G, H, ) trong đó tập gia tử H = H+H– và giả sử rằng H– = {h–1, h–2, …, h–q} thỏa h–1 < h–2 < …< h–q; H+ ={h1, h2, …, hp} thỏa h1 < h2 < …< hp, và h0 = I với I là toán tử đơn vị.
Chúng ta cần có các mệnh đề và định nghĩa sau:
Mệnh đề 1.1. Cho fm là hàm độ đo tính mờ trên X. Ta có:
(1) fm(hx) = (h)fm(x), với x X.
(2) fm(c) + fm(c+) = 1.
(3) , trong đó c {c, c+}
(4) , với x X.
10
(5) và , với , > 0 và + = 1.
Định nghĩa 1.3. (Sign function) Hàm dấu Sign: X {−1, 0, 1} là ánh xạ
được xác định đệ quy sau đây, trong đó h, h’ H và c {c, c+}:
(1) Sign(c) = 1, Sign(c+) = +1,
(2) Sign(h'hx) = Sign(hx), nếu h’hx hx và h' âm đối với h (hoặc tương
ứng với c, nếu h = I & x = c);
(3) Sign(h'hx) = Sign(hx), nếu h’hx hx và h' dương đối với h (hoặc tương
ứng với c, nếu h = I & x = c);
(4) Sign(h'hx) = 0, nếu h’hx = hx.
Mệnh đề 1.2. Với bất kỳ gia tử h H và phần tử x X, nếu Sign(hx) =
+1 thì ta có hx > x và nếu Sign(hx) = 1 thì hx < x.
Định nghĩa 1.4. Cho fm là hàm độ đo tính mờ trên tập X. Hàm định lượng
ngữ nghĩa : X [0,1], kết hợp với hàm fm, được xác định như sau:
(1) (W) = = fm(c), (c) = − fm(c) = fm(c),
(c+) = + fm(c+);
, trong đó (2) (hjx) = (x) +
, và (hjx) =
j {j: q j p & j 0} = [q^p].
Mệnh đề 1.3.
(1) Với mọi x X, 0 ≤ (x) ≤ 1.
(2) Với mọi x, y X, x < y suy ra (x) < (y).
1.2.3. Đại số gia tử tuyến tính đầy đủ
Để thuận tiện trong các chứng minh dưới đây, chúng ta sẽ nhắc lại một số
khái niệm về ĐSGT tuyến tính đầy đủ.
Định nghĩa 1.5. Đại số gia tử đầy đủ AX = (X, G, H, , , ≤) được gọi là tuyến tính nếu tập các phần tử sinh G = {0, c–, W, c+, 1} và tập các gia tử H– = {h-1, ..., h-q} và H+ = {h1,..., hp} là các tập sắp thứ tự tuyến tính, trong đó
11
và là hai phép toán với ngữ nghĩa là cận trên đúng và cận dưới đúng của tập H(x), tức là x = supremum(H(x)), x = infimum(H(x)), H = HH+, và ta luôn luôn giả thiết rằng h-1 < h-2 < ... < h-q; h1 < ...< hp.
Định nghĩa 1.6. Giả sử AX = (X, G, H, , , ) là một ĐSGT đầy đủ, tuyến tính và tự do, fm(x) và (h) tương ứng là các độ đo tính mờ của giá trị ngôn ngữ x và của gia tử h. Khi đó, ta nói là ánh xạ cảm sinh bởi độ đo tính mờ fm của ngôn ngữ nếu nó được xác định như sau:
(1) (W) = = fm(c), (c) = – fm(c) = fm(c),
(c+) = +fm(c+);
(2) ,
trong đó , với
mọi j, –q j p và j 0;
(3) (c) = 0, (c) = = (c+), (c+) = 1, và với mọi j thỏa
–q j p, j 0, ta có:
(hjx) = (x) +
(hjx) = (x) +
Một số tính chất của giá trị ngôn ngữ: Trước hết là việc xây dựng ánh xạ để gán mỗi phần tử x X với một đoạn con của đoạn [0,1] sao cho đoạn con (x) của đoạn [0,1] có độ dài bằng độ đo tính mờ của phần tử x.
Cho trước ĐSGT tuyến tính đầy đủ AX = (X, G, H, , , ) và hàm độ đo tính mờ fm: X [0,1]. Gọi Intv([0,1]) là họ tất cả các đoạn con của đoạn [0,1]. Việc gán ngữ nghĩa mờ được xác định bởi ánh xạ : X Intv([0,1]) thỏa các điều kiện sau:
, c+} thì (c), (c+) là các đoạn con của đoạn [0,1]. Ký hiệu |.| là độ dài của các đoạn, khi đó ta có |(c)| = fm(c), |(c+)| = fm(c+) và (c) ≤ (c+).
(1) Với x {c
12
(2) Giả sử x X, x có độ dài n, ký hiệu l(x) = n, khi đó ta gán |(x)| = fm(x) và nếu x < y thì (x) ≤ (y). Hơn nữa nếu h−qx < … < h−1x < h1x < h2x <…< hpx thì (x) được chia thành (p + q) đoạn con của đoạn [0,1], độ dài của đoạn con |(hix)| = fm(hix), i [ q^p] và (hix) ≤ (hjx), nếu thỏa điều kiện hix < hjx với i,j [ q^p].
Họ {(x) : x X } được gọi là một tựa phân hoạch (semi-partition) của đoạn [0,1] tức là nếu với x,y X, x ≠ y thì đoạn con (x) và (y) có chung với nhau nhiều nhất một điểm và (x) = [0,1]. Để thuận tiện, chúng ta ký hiệu
tập các phần tử có độ dài k là Xk = {x X : l(x) = k}, l(x) là độ dài của x.
Bổ đề 1.1. Cho fm là hàm độ đo tính mờ trên AX và được gán ngữ nghĩa
mờ theo fm. Khi đó:
(1) {(c), (c+)} là một tựa phân hoạch của đoạn [0,1] và với mọi x
X, họ {(hix) : i [q^p]} là một tựa phân hoạch của (x).
(2) Họ {(x) : x Xn} là một tựa phân hoạch của đoạn [0,1] và nếu x <
y và l(x) = l(y) = n thì (x) < (y).
(3) Với y =x, là chuỗi gia tử bất kỳ thì (y) (x).
(4) Với x, y X, x < y, H(x) H(y) = Ø thì (x) ≤ (y).
Trong [12] các tác giả chỉ ra rằng với mỗi giá trị thực r [0,1] đều tồn tại giá trị ngôn ngữ x X có giá trị định lượng xấp xỉ với r. Trong mệnh đề dưới đây chúng tôi sẽ xác định độ dài đủ lớn của giá trị ngôn ngữ x khi xấp xỉ với số r theo độ chính xác ε > 0 cho trước.
một số ε > 0 bé tùy ý. Đặt Mệnh đề 1.4. Cho ĐSGT tuyến tính đầy đủ AX = (X, G, H, Σ, Φ, ) và trong đó λ = max{µ(hj): j
[−q^p]}, và γ = max{fm(c−), fm(c+)}. Khi đó với mọi giá trị thực r [0,1] đều tồn tại giá trị ngôn ngữ x Xk thỏa |(x) − r| ≤ ε.
1.2.4. Khái niệm ngưỡng hiệu chỉnh định lượng ngữ nghĩa
Giả thiết ĐSGT AX* = (X*, G, H, ρ , , ) là tuyến tính, đầy đủ và tự do, trong đó X* là tập cơ sở, G = (0, c-, W, c+, 1) với c-, c+ là 2 phần tử sinh, 0, W, 1 tập các phần tử không sinh nghĩa, (phần tử W còn gọi là phần tử trung hòa), H là tập các gia tử âm và dương, là quan hệ thứ tự toàn phần trên X*, ρ và là hai phép toán mở rộng sao cho với mọi x X*, x, ρx tương ứng là cận dưới
13
đúng và cận trên đúng trong X* của tập H(x), là tập tất cả các phần tử sinh ra
từ x nhờ các gia tử trong H. Giả sử H = HH+ và H = {h-1, ..., h-q}, với h-1 Theo tài liệu [6] đưa ra định nghĩa ngưỡng hiệu chỉnh ĐLNN và phương
pháp xác định ngưỡng hiệu chỉnh ĐLNN của các giá trị ngôn ngữ để sao cho
thứ tự ngữ nghĩa vẫn bảo đảm vốn có của các giá trị ngôn ngữ trong ĐSGT. Định nghĩa 1.7. Số thực , 0 1 được gọi là ngưỡng hiệu chỉnh ĐLNN
của các giá trị ngôn ngữ trong X k nếu với mọi x, y X k thỏa x y kéo theo v(x)
+ 1 v(y) 2 đúng với 0<1, 2 < Định lý 1.5. Cho AX* là ĐSGT tuyến tính, đầy đủ và tự do, ngưỡng hiệu chỉnh ĐLNN cho các giá trị ngôn ngữ trong X k là: k = min {fm(x)/2, fm(x)/2 | x X k }, với k là số nguyên dương tùy ý. 1.3. Phương pháp lập luận xấp xỉ mờ đa điều kiện Từ những năm 70 các phương pháp lập luận đã được phát triển mạnh mẽ
và được ứng dụng nhiều trong các hệ chuyên gia mờ. Một số phương pháp lập
luận mờ đa điều kiện (Fuzzy Multiple Conditional Reasoning - FMCR ) nhằm
giải quyết bài toán lập luận mờ đa điều kiện đã được phát biểu. Theo cách tiếp cận của lý thuyết tập mờ, các phương pháp lập luận mờ đa điều kiện nói chung được mô tả dựa trên hai dạng mô hình sau. Mô hình hội: Xem mô hình mờ (1.2) như là hội của các mệnh đề if -then - Ngữ nghĩa của các giá trị ngôn ngữ của các biến ngôn ngữ trong mô hình mờ được biểu thị bằng các tập mờ tương ứng của chúng. - Từ các luật mờ dạng câu if-then, xây dựng quan hệ mờ R như sau: + Sử dụng phép hội các điều kiện ở tiền đề, mỗi câu if-then xem như là
một phép kéo theo I(s,t), một phép 2-ngôi trong [0,1], lưu ý rằng giá trị
s phụ thuộc m biến đầu vào. + Vì (1.2) được xem là mô hình hội, R được tính bằng hội của các biểu thức phép kéo theo đã xây dựng. 14 - Khi đó ứng với vectơ đầu vào A0, giá trị của biến đầu ra được tính theo công thức B0 = A0R, trong đó là một phép hợp thành nào đó. Mô hình tuyển: Xem (1.2) như là tuyển của các mệnh đề if-then - Phương pháp tiến hành giống như trên cho đến bước xây dựng được các phép kéo theo Ij(s,t) cho mỗi mệnh đề if-then trong (1.2), j = 1, ..., n. - Với vectơ đầu vào A0, giá trị của biến đầu ra B0j dựa trên luật thứ j được tính theo công thức B0j = A0 Ij(s,t), trong đó là một phép hợp thành nào đó. - Cuối cùng, giá trị đầu ra của mô hình mờ (1.2) được tính bằng tuyển của các B0j, j = 1, ..., n. Một cách tổng quát, các phép tuyển và hội được xây dựng dựa trên các phép t-norm và s-norm. Tuy ý tưởng chung về lược đồ phương pháp lập luận mờ là giống nhau,
nhưng những phương pháp lập luận sẽ khác nhau ở cánh thức mô phỏng mô
hình mờ và cách xác định các phép t-norm và s-norm. Hiệu quả của phương pháp lập luận mờ nói chung phụ thuộc nhiều yếu tố rất căn bản chẳng hạn như: - Lựa chọn tập mờ (bài toán xây dựng các hàm thuộc). - Bài toán lựa chọn phép kết nhập (bài toán chuyển mô hình đa điều kiện
về mô hình đơn điều kiện). - Xây dựng quan hệ mờ mô phỏng tốt nhất mô hình mờ (bài toán lựa chọn
phép kéo theo). - Khử mờ (bài toán lựa chọn phương pháp khử mờ). - Luật hợp thành (max-min, min-max, t-norm, s-norm, …). Đó chính là những khó khăn không nhỏ khi xây dựng phương pháp giải bài toán lập luận mờ đa điều kiện. Với mục tiêu tìm kiếm các phương pháp lập luận giải bài toán trên, một
số tác giả đã quan tâm nghiên cứu một phương pháp mới, phương pháp nội suy
mờ. Ý tưởng của phương pháp này là xem các tiền đề của mệnh đề if - then
trong mô hình mờ như là các “điểm lưới”. Mô hình mờ cho ta thông tin của lời
giải tại điểm lưới. Dữ liệu đầu vào A0 sẽ rơi vào một “đoạn thẳng” nào đó xác 15 định bởi các điểm lưới. Trên đoạn này chúng ta giải bằng phương pháp nội suy
trên cơ sở thông tin được cho tại 2 điểm lưới đầu mút của “đọan thẳng”. Có thể thấy phương pháp nội suy mờ có trực quan rõ ràng cho phép người
ta cảm nhận hay dự đoán mức độ nào đó về ứng xử của hệ thống được cho bởi
mô hình mờ. Tuy nhiên, phương pháp này vẫn chứa đựng các yếu tố phức tạp
chẳng hạn như: - Vấn đề xây dựng hàm thuộc dạng tam giác của các tập mờ. - Vấn đề khử mờ để chuyển giá trị mờ đầu ra thành giá trị thực. - Vấn đề tìm lời giải bằng nội suy trên từng tập mức của tập mờ. Đây cũng là những bài toán khá phức tạp vì luôn có thể chỉ ra lời giải chưa tối ưu. Các phương pháp lập luận, đặc biệt là phương pháp lập luận mờ đa điều
kiện có rất nhiều ứng dụng trong thực tiễn như trong xây dựng các hệ chuyên
gia, các hệ trợ giúp quyết định, các hệ mờ. 1.4. Bài toán tối ưu và giải thuật di truyền 1.4.1. Bài toán tối ưu Bài toán tối ưu có dạng: Cho trước một hàm f: A R từ tập hợp A tới tập số thực. Tìm: một phần
tử x0 thuộc A sao cho f(x0) ≤ f(x) với mọi x thuộc A ("cực tiểu hóa") hoặc sao
cho f(x0) ≥ f(x) với mọi x thuộc A ("cực đại hóa"). Miền xác định A của hàm f được gọi là không gian tìm kiếm. Thông
thường, A là một tập con của không gian Euclid Rn, thường được xác định bởi
một tập các ràng buộc, các đẳng thức hay bất đẳng thức mà các thành viên
của A phải thỏa mãn. Các phần tử của A được gọi là các lời giải khả thi.
Hàm f được gọi là hàm mục tiêu, hoặc hàm chi phí. Lời giải khả thi nào cực
tiểu hóa (hoặc cực đại hóa, nếu đó là mục đích) hàm mục tiêu được gọi là lời
giải tối ưu. Thông thường, sẽ có một vài cực tiểu địa phương và cực đại địa phương,
trong đó một cực tiểu địa phương x* được định nghĩa là một điểm thỏa mãn
điều kiện: với giá trị δ > 0 nào đó và với mọi giá trị x sao cho ; 16 Công thức sau luôn đúng Nghĩa là, tại vùng xung quanh x*, mọi giá trị của hàm đều lớn hơn hoặc
bằng giá trị tại điểm đó. Cực đại địa phương được định nghĩa tương tự. Thông
thường, việc tìm cực tiểu địa phương là dễ dàng - cần thêm các thông tin về bài
toán (chẳng hạn, hàm mục tiêu là hàm lồi) để đảm bảo rằng lời giản tìm được
là cực tiểu toàn cục. Phát biểu bài toán có thể có thể mô tả lại bài toán như sau: f (x) = max(min) - Với điều kiện: gi(x) (, =, ) bi, i=1,…, m x X Rn - Hàm f(x) được gọi là hàm mục tiêu. - Hàm gi(x) gọi là các hàm ràng buộc. - Miền ràng buộc D = x X gi (x) (, =, ) bi, i = 1,m 1.4.2. Giải thuật di truyền 1.4.2.1. Các khái niệm cơ bản của giải thuật di truyền Giới thiệu chung: Giải thuật GA lần đầu được tác giả Holland giới thiệu
vào năm 1962. Nền tảng toán học của giải thuật GA được tác giả công bố trong
cuốn sách “Sự thích nghi trong các hệ thống tự nhiên và nhân tạo” xuất bản
năm 1975. Giải thuật GA mô phỏng quá trình tồn tại của các cá thể có độ phù
hợp tốt nhất thông qua quá trình chọn lọc tự nhiên, sao cho khi giải thuật được
thực thi, quần thể các lời giải tiến hoá tiến dần tới lời giải mong muốn. Giải
thuật GA duy trì một quần thể các lời giải có thể của bài toán tối ưu hoá. Thông
thường, các lời giải này được mã hoá dưới dạng một chuỗi các gen. Giá trị của
các gen có trong chuỗi được lấy từ một bảng các ký tự được định nghĩa trước.
Mỗi chuỗi gen được liên kết với một giá trị được gọi là độ phù hợp. Độ phù
hợp được dùng trong quá trình chọn lọc. Cơ chế chọn lọc đảm bảo các cá thể
có độ phù hợp tốt hơn có xác suất được lựa chọn cao hơn. Quá trình chọn lọc
sao chép các bản sao của các cá thể có độ phù hợp tốt vào một quần thể tạm
thời được gọi là quần thể bố mẹ. Các cá thể trong quần thể bố mẹ được ghép
đôi một cách ngẫu nhiên và tiến hành lai ghép tạo ra các cá thể con. Sau khi 17 tiến hành quá trình lai ghép, giải thuật GA mô phỏng một quá trình khác trong
tự nhiên là quá trình đột biến, trong đó các gen của các cá thể con tự thay đổi
giá trị với một xác suất nhỏ. Tóm lại, có 6 khía cạnh cần được xem xét, trước khi áp dụng giải thuật GA để giải một bài toán, cụ thể là: - Mã hoá lời giải thành cá thể dạng chuỗi. - Hàm xác định giá trị độ phù hợp. - Sơ đồ chọn lọc các cá thể bố mẹ. - Toán tử lai ghép. - Toán tử đột biến. - Chiến lược thay thế hay còn gọi là toán tử tái tạo. Có nhiều lựa chọn khác nhau cho từng vấn đề trên. Phần tiếp theo sẽ đưa
ra cách lựa chọn theo Holland khi thiết kế phiên bản giải thuật GA đơn giản lần
đầu tiên. Giải thuật di truyền đơn giản: Holland sử dụng mã hoá nhị phân để biểu
diễn các cá thể, lý do là phần lớn các bài toán tối ưu hoá đều có thể được mã
hoá thành chuỗi nhị phân khá đơn giản. Hàm mục tiêu, hàm cần tối ưu, được
chọn làm cơ sở để tính độ phù hợp của từng chuỗi cá thể. Giá trị độ phù hợp
của từng cá thể sau đó được dùng để tính toán xác suất chọn lọc. Sơ đồ chọn
lọc trong giải thuật SGA là sơ đồ chọn lọc tỷ lệ. Trong sơ đồ chọn lọc này, cá
, ở đây N là số cá thể
thể có độ phù hợp có xác suất chọn lựa có trong quần thể. Toán tử lai ghép trong giải thuật GA là toán tử lai ghép một điểm cắt. Giả sử chuỗi cá thể có độ dài L (có L bít), toán tử lai ghép được tiến
hành qua hai giai đoạn là: Hinh 1. 2. Mã hoá nhị phân biểu diễn các cá thể 18 Hai cá thể trong quần thể bố mẹ được chọn một cách ngẫu nhiên với phân bố xác suất đều. Sinh một số ngẫu nhiên j trong khoảng [1, L - 1]. Hai cá thể con được tạo
ra bằng việc sao chép các ký tự từ 1 đến j và tráo đổi các ký tự từ j + 1 đến L.
Quá trình này được minh hoạ như trong hình 1. Điều đáng lưu ý là giải thuật GA không yêu cầu toán tử lai ghép luôn xảy
ra đối với hai cá thể bố mẹ được chọn. Sự lai ghép chỉ xảy ra khi số ngẫu nhiên
tương ứng với cặp cá thể bố mẹ được sinh ra trong khoảng [0, 1) không lớn hơn
một tham số pc (gọi là xác suất lai ghép). Nếu số ngẫu nhiên này lớn hơn pc,
toán tử lai ghép không xảy ra. Khi đó hai cá thể con là bản sao trực tiếp của hai
cá thể bố mẹ. Tiếp theo, Holland xây dựng toán tử đột biến cho giải thuật GA. Toán tử
này được gọi là toán tử đột biến chuẩn. Toán tử đột biến duyệt từng gen của
từng cá thể con được sinh ra sau khi tiến hành toán tử lai ghép và tiến hành biến
đổi giá trị từ 0 sang 1 hoặc ngược lại với một xác suất pm được gọi là xác suất
đột biến. Cuối cùng là chiến lược thay thế hay còn gọi là toán tử tái tạo. Trong
giải thuật, quần thể con được sinh ra từ quần thể hiện tại thông qua 3 toán tử là
chọn lọc, lai ghép và đột biến thay thế hoàn toàn quần thể hiện tại và trở thành
quần thể hiện tại của thế hệ tiếp theo. Sơ đồ tổng thể của GA được thể hiện qua
thủ tục GA dưới đây. Thủ tục GA () /* Bài toán tối ưu */ {k = 0; // Khởi động quần thể P0 một cách ngẫu nhiên. // Tính giá trị hàm mục tiêu cho từng cá thể. khởi_động (Pk); tính_hàm_mục_tiêu (Pk); // Đặt lời giải của giải thuật bằng cá thể có giá trị hàm mục tiêu tốt nhất. Xbest = tốt_nhất (Pk); do { // Chuyển đổi giá trị hàm mục tiêu thành giá trị độ phù hợp và // tiến hành chọn lọc tạo ra quần thể bố mẹ Pparent Pparent = chọn_lọc (Pk ); 19 // Tiến hành lai ghép và đột biến tạo ra quần thể cá thể con Pchild Pchild = đột_biến (lai_ghép (Pparent)); // Thay thế quần thể hiện tại bằng quần thể cá thể con k = k + 1; Pk = Pchild; tính_hàm_mục_tiêu (Pk); // Nếu giá trị hàm mục tiêu obj của cá thể tốt nhất X trong quần // thể Pk lớn hơn giá trị hàm mục tiêu của Xbest thì thay thế lời giải X = tốt_nhất (Pk); if ( obj (X) > obj (Xbest) ) Xbest = X; } while ( k < G); /* Tiến hành G thế hệ */ return (Xbest); /* Trả về lời giải của giải thuật GA*/ } Giải thuật di truyền phụ thuộc vào bộ 4 (N, pc, pm, G), trong đó N - số cá
thể trong quần thể; pc - xác suất lai ghép; pm - xác suất đột biến và G - số thế
hệ cần tiến hoá, là các tham số điều khiển của giải thuật GA. Cá thể có giá trị
hàm mục tiêu tốt nhất của mọi thế hệ là lời giải cuối cùng của giải thuật GA.
Quần thể đầu tiên được khởi tạo một cách ngẫu nhiên. 1.4.2.2. Cơ chế thực hiện của giải thuật di truyền Trong phần này chúng ta sẽ tìm hiểu về cơ chế thực hiện của giải thuật di
truyền thông qua một bài toán tối ưu số. Không làm mất tính tổng quát, ta giả
định bài toán tối ưu là bài toán tìm cực đại của hàm nhiều biến f. Bài toán tìm
cực tiểu hàm g chính là bài toán tìm cực đại hàm f = -g, hơn nữa ta có thể giả
định hàm mục tiêu f có giá trị dương trên miền xác định của nó, nếu không ta
có thể cộng thêm một hằng số C dương. Cụ thể bài toán được đặt ra như sau: Tìm cực đại một hàm k biến f(x1,..,
xk): RkR. Giả sử thêm là mỗi biến xi có thể nhận giá trị trong miền Di = [ai,bi]
R và f(x1,.., xk) 0 với mọi xi Di. Ta muốn tối ưu hàm f với độ chính xác
cho trước: giả sử cần n số lẻ đối với giá trị của các biến. Để đạt được độ chính xác như vậy mỗi miền Di cần được phân cắt thành (bi - ai) 10n miền con bằng nhau, gọi m là số nguyên nhỏ nhất sao cho 20 Như vậy mỗi biến xi được biểu diễn bằng một chuỗi nhị phân có chiều dài
mi. Biểu diễn như trên rõ ràng thoả mãn điều kiện về độ chính xác theo yêu cầu.
Công thức sau tính giá trị thập phân của mỗi chuỗi nhị phân biểu diễn biến xi Trong đó decimal (string2) cho biết giá trị thập phân của chuỗi nhị phân đó. Bây giờ, mỗi nhiễm sắc thể (là một lời giải) được biểu diễn bằng một chuỗi nhị phân có chiều dài , m1 bit đầu tiên biểu diễn giá trị trong khoảng [a1, b1], m2 bit kế tiếp biểu diễn giá trị trong khoảng [a2, b2], … Để khởi tạo quần thể, chỉ cần đơn giản tạo pop_size nhiễm sắc thể ngẫu nhiên theo từng bit. Phần còn lại của giải thuật di truyền rất đơn giản, trong mỗi thế hệ, ta
lượng giá từng nhiễm sắc thể (tính giá trị hàm f trên các chuỗi biến nhị phân đã
được giải mã), chọn quần thể mới thoả mãn phân bố xác suất dựa trên độ thích
nghi và thực hiện các phép đột biến và lai để tạo ra các cá thể thế hệ mới. Sau
một số thế hệ, khi không còn cải thiện thêm được gì nữa, nhiễm sắc thể tốt nhất
sẽ được xem như lời giải của bài toán tối ưu (thường là toàn cục). Thông thường
ta cho dừng giải thuật sau một số bước lặp cố định tuỳ ý tuỳ thuộc vào điều
kiện tốc độ và tài nguyên máy tính. Đối với tiến trình chọn lọc (chọn quần thể mới thoả phân bố xác suất dựa
trên các độ thích nghi), ta dùng bánh xe quay Rulet với các rãnh được định kích
thước theo độ thích nghi. Ta xây dựng bánh xe Rulet như sau (giả định rằng
các độ thích nghi đều dương). + Tính độ thích nghi eval(vi) của mỗi nhiễm sắc thể vi (i = 1,…, pop_size) + Tìm tổng giá trị thích nghi toàn quần thể: + Tính xác suất chọn pi cho mỗi nhiễm sắc thể vi, (i = 1,…, pop_size): . + Tính vị trí xác suất qi của mỗi nhiễm sắc thể vi, (i = 1,…, pop_size): 21 Tiến trình chọn lọc thực hiện bằng cách quan bánh xe Rulet pop_size lần,
mỗi lần chọn một nhiễm sắc thể từ quần thể hiện hành vào quần thể mới theo
cách sau: + Phát sinh ngẫu nhiên một số r trong khoảng [0..1] + Nếu r q1 thì chọn nhiễm sắc thể đầu tiên v1, ngược lại thì chọn nhiễm sắc thể thứ i, vi (2 i pop_size) sao cho qi-1 r qi Hiển nhiên có thể có một số nhiễm sắc thể được chọn nhiều lần, điều này
là phù hợp vì các nhiếm sắc thể tốt nhất cần có nhiều bản sao hơn, các nhiễm
sắc thể trung bình không thay đổi, các nhiễm sắc thể kém nhất thì chết đi. Bây giờ ta có thể áp dụng phép toán di truyền: kết hợp và lại vào các cá
thể trong quần thể mới vừa được chọn từ quần thể cũ như trên. Một trong nhữn
tham số của giải thuật là xác suất lai pc. Xác suất này cho ta số nhiếm sắc thể
pop_sizepc mong đợi, các nhiễm sắc thể này được dùng trong tác vụ lai tạo.
Ta tiến hành theo cách sau đây: Đối với mỗi nhiễm sắc thể trong quần thể mới: + Phát sinh ngẫu nhiên một số r trong khoảng [0, 1] + Nếu r pc, hãy chọn nhiễm sắc thể đó để lai tạo Bây giờ ta ghép đôi các nhiễm sắc thể đã được chọn một cách ngẫu nhiên:
đối với mỗi cặp nhiễm sắc thể được ghép đôi, ta phát sinh ngẫu nhiên một số
nguyên pos trong khoảng [1, m-1], m là tổng chiều dài - số bit của một nhiễm
sắc thể. Số pos cho biết vị trí của điểm lai, cụ thể hai nhiễm sắc thể: (b1b2…bposbpos+1…bm) và (c1c2.…cposcpos+1…cm) được thay bằng một cặp con của chúng: (b1b2…bposcpos+1…cm) và (c1c2.…cposbpos+1…bm) Phép toán kế tiếp là phép đột biến, được thực hiện trên cơ sở từng bit. Một
tham số khác của giải thuật là xác suất đột biến pm, cho ta số bit đột biến
pmmpop_size mong đợi. Mỗi bit (trong tất cả các nhiễm sắc thể trong quần
thể) có cơ hội bị đột biến như nhau, nghĩa là đổi từ 0 thành 1 hoặc ngược lại.
Vì thế ta tiến hành theo cách sau đây: Đối với mỗi nhiễm sắc thể trong quần thể hiện hành (nghĩa là sau khi lai) và đỗi với mỗi bit trong nhiễm sắc thể: 22 + Phát sinh ngẫu nhiên một số r trong khoảng [0, 1] + Nếu r < pm hãy đột biến bit đó Sau quá trình chọn lọc, lai và đột biến, quần thể mới đến lượt lượng giá kế
tiếp của nó. Lượng giá này được dùng để xây dựng phân bố xác suất (cho tiến
trình chọn lựa kế tiếp), nghĩa là để xây dựng lại bánh xe Rulet với các rãnh
được định kích thước theo các giá trị thích nghi hiện hành. Phần còn lại của tiến
hoá chỉ là lặp lại chu trình của những bước trên. 1.4.2.3. Các phương pháp biểu diễn nhiễm sắc thể và các toán tử di truyền
chuyên biệt Khi ứng dụng giải thuật di truyền vào thực tế, đôi khi gặp những bài toán
đòi hỏi một cách biểu diễn lời giải thích hợp, nếu không giải thuật di truyền
khó cho lời giải tốt được, thường là hội tụ sớm về một lời giải tối ưu không
toàn cục. Biểu diễn nhị phân truyền thống có một số bất lợi khi áp dụng GA giải các
bài toán số cần độ chính xác cao, trong một không gian có số chiều lớn. Ví dụ
tối ưu hàm 100 biến, mỗi biến nhận giá trị trong khoảng [-500, 500], chính xác
đến 6 số lẻ thì chiều dài của véc tơ lời giải nhị phân phải là 3000 và phát sinh
một không gian tìm kiếm khoảng 101000 phần tử. Tìm kiếm trong một không
gian như thế giải thuật di truyền thực hiện rất kém hiệu quả. Với lý do trên trong phần này chúng ta sẽ thử nghiệm với các gen mã hoá
là các số thực cùng với các toán tử di truyền chuyên biệt ứng với cách mã hoá
số thực này. 1.4.2.4. Biểu diễn thực Trong biểu diễn thực, mỗi véc tơ nhiễm sắc thể được mã hoá thành vectơ
thực có cùng chiều dài với véc tơ lời giải. Mỗi phần tử được chọn lúc khởi tạo
sao cho thuộc miền xác định của nó, và các toán tử được thiết kế để bảo toàn
các ràng buộc này (không có vấn đề như vậy trong biểu diễn nhị phân, nhưng
thiết kế của các toán tử này khá đơn giản, ta không thấy điều đó là bất lợi, mặt
khác nó lại cung cấp các lợi ích khác được trình bày dưới đây). Sự chính xác của cách tiếp cận như thế chỉ tuỳ thuộc máy tính nhưng nói
chung là tốt hơn nhiều so với biểu diễn nhị phân. Đương nhiên ta luôn có thể
tăng độ chính xác của biểu diễn nhị phân khi thêm các bit, nhưng điều đó làm
giải thuật chậm đi đáng kể như đã thảo luận ở phần trước. 23 Thêm nữa biểu diễn thực có khả năng biểu diễn một miền rất rộng (hoặc
các trường hợp miền xác định không biết trước cụ thể). Mặt khác trong biểu
diễn nhị phân, độ chính xác sẽ giảm khi tăng kích thước miền, do chiều dài nhị
phân cố định cho trước. Hơn nữa với biểu diễn thực việc thiết kế các công cụ
đặc biệt để xử lý các ràng buộc không tầm thường sẽ dễ hơn. 1.4.2.5. Các toán tử chuyên biệt hoá Các toán tử ta sẽ sử dụng rất khác các toán tử cổ điển, vì chúng làm việc
trong một không gian khác (có giá trị thực). Hơn nữa một vài toán tử không
đồng bộ, nghĩa là hành động của chúng phụ thuộc vào tuổi của quần thể. Nhóm toán tử đột biến: có nhóm đột biến đồng bộ, nhóm đột biến không đồng bộ. + Đột biến đồng bộ: Đột biến đồng bộ được định nghĩa tương tự với định
nghĩa của phiên bản cổ điển: nếu sv = + Đột biến không đồng bộ: Đột biến không đồng bộ là một trong những
toán tử có nhiệm vụ về tìm độ chính xác của hệ thống. Nó được định nghĩa như
sau: nếu st
v = trong đó, hàm (t, y) trả về giá trị trong khoảng [0, y] sao cho xác suất của
(t, y) gần bằng 0 sẽ tăng khi t tăng. Xác suất này buộc toán tử tìm kiếm không
gian thoật đầu là đồng bộ (khi t nhỏ) và rất cục bộ ở những giai đoạn sau. Ta
sử dụng hàm sau: , với r là số ngẫu nhiên trong khoảng [0, 1], T là
số thế hệ tối đa và b là tham số hệ thống xác định mức độ không đồng bộ. Hình
biểu diễn giá trị của đối với hai lần được chọn, hình này hiển thị rõ ràng cách
ứng xử của toán tử. (t, y) (t, y) y y t/T = 0.50, b=2 t/T = 0.90, b=2 r r 1 1 24 Hinh 1. 3. Biểu diễn giá trị của đối với hai lần được chọn Hơn nữa ngoài cách áp dụng đột biến chuẩn ta có một số cơ chế mới: đột
biến không đồng bộ cũng được áp dụng cho một vectơ lời giải thay vì chỉ một
phần tử duy nhất của nó, khiến cho vectơ hơi trượt trong không gian lời giải. Nhóm toán tử lai tạo: lai đơn giản, lai số học đơn, lai số học cục bộ. + Lai đơn giản: v = Phép lai đơn giản được xác định như sau: v = w = Nếu st
thì kết quả là: st + Lai số học đơn: Phép lai số học đơn được xác định như sau: v = w = Nếu st Trong đó: = (lk-wk)/(vk-wk), = (uk-vk)/(wk-vk) = (lk-vk)/(wk-vk), = (uk-wk)/(vk-wk) + Lai ghép số học toàn cục: Lai ghép số học toàn cục là tổ hợp tuyến tính của hai véc tơ được xác định như sau: 25 v = v và st+1 w = w, với a là một tham số tĩnh [0, 1] = ast Nếu st
w+(1- a)st 1.5. Kết luận Chương 1 Trong chương này luận văn đã hệ thống được các kiến thức cơ bản sau: - Tìm hiểu biến ngôn ngữ và mô hình mờ, ĐSGT. - Phương pháp lập luận xấp xỉ mờ là cơ sở để phát triển phương pháp lập luận mờ sử dụng ĐSGT. - Giải thuật di truyền được dùng để tìm kiếm các tham số tối ưu của các ĐSGT trong phương pháp lập luận mờ sử dụng ĐSGT. 26 CHƯƠNG 2: GIẢI PHÁP TỐI ƯU CÁC THAM SỐ ĐỊNH LƯỢNG
NGỮ NGHĨA CHO PHƯƠNG PHÁP LẬP LUẬN MỜ DỰA TRÊN
ĐẠI SỐ GIA TỬ 2.1. Phương pháp lập luận mờ sử dụng đại số gia tử Cho mô hình mờ (1.2). Tư tưởng chính của phương pháp là từ mỗi mệnh
đề “IF...THEN...” sẽ xác định một điểm trong không gian tích Decac
Dom(X1)...Dom(Xm)Dom(Y), ở đây Dom(Xi), Dom(Y) là các miền ngôn ngữ
tương ứng của các biến ngôn ngữ Xi và Y và chúng được xem như các ĐSGT.
Vì vậy, các giả thiết của bài toán xác định một siêu mặt Cf trong không gian
tích Decac này cho nên giải bài toán mô hình mờ đa điều kiện có nghĩa là chúng
ta đi tìm giá trị B ứng với giá trị A = (A01, ..., A0m) bằng cách nội suy trên siêu
mặt Cf. Cụ thể chúng ta phải thực hiện các nội dung sau đây: 1) Xây dựng các ánh xạ ĐLNN Xi và Y , tức là các ánh xạ từ các ĐSGT
Xi, Y vào [0,1]. Các ánh xạ này được xác định bởi độ đo mờ của các phần tử
sinh nguyên thủy và của các gia tử, chúng đóng vai trò các tham số của phương
pháp. Kết quả nội suy sẽ chịu ảnh hưởng từ cách chọn các tham số này. 2) Các ánh xạ ĐLNN trên sẽ chuyển siêu mặt Cf trong
Dom(X1)...Dom(Xm)Dom(Y) thành siêu mặt Cr,m+1 trong không gian thực [0,
d1] ... [0, dm][0, b] với [0, di], [0, b] là miền giá trị của các biến cơ sở của
Xi và Y một cách tương ứng. 3) Sử dụng một phép kết nhập Agg ta sẽ chuyển được siêu mặt thực
Cr,m+1trong bước 2) thành đường cong thực Cr,2 trong [0, a][0, b] với a =
Agg(d1, ..., dm) bằng cách: với mỗi i cố định, i = 1, ..., n. a) Tính các giá trị aij= Xj(Aij), j = 1, ..., m. b) Kết nhập ai = Agg(ai1, ..., aim), c) Tính bi = Y(Bi). Từ các giá trị ai, bi dễ dàng xác định đường cong Cr,2. Cuối cùng, với các
giá trị đầu vào A01, ..., A0m cho trước của các biến X1, ..., Xm, chúng ta sử dụng
phương pháp nội suy tuyến tính thông thường để tính giá trị đầu ra b0 tương
ứng với giá trị đầu vào a0 = Agg(X1(A01), ..., Xm(A0m)). Khi có giá trị b0 chúng
ta sẽ xác định lại giá trị ngôn ngữ. 27 Theo tiếp cận của ĐSGT, Mô hình mờ (1.2) được xem như một tập hợp
các “điểm mờ”, với việc sử dụng các ánh xạ ngữ nghĩa định lượng v mỗi điểm
của mô hình mờ trên có thể được biểu diễn bằng một điểm của siêu mặt thực
và tập các điểm thực cho ta một mô hình gọi là mô hình định lượng ngữ nghĩa.
Sử dụng toán tử kết nhập để kết nhập các điều kiện trong mô hình mờ, khi đó
ta có thể chuyển siêu mặt thực về đường cong thực trong mặt phẳng, đường
cong này còn được gọi là đường cong định lượng ngữ nghĩa. Do đó, bài toán lập luận ban đầu sẽ chuyển về bài toán nội suy kinh điển, phương pháp này gọi là HAR, được thực hiện qua thuật toán sau: Inputs: Mô hình mờ (FAM) bao gồm các luật trong đó mỗi biến ngôn ngữ tương ứng với một ĐSGT. Outputs: Giá trị đầu ra lập luận tương ứng với giá trị đầu vào. Actions: Step 1. Xây dựng các ĐSGT AXi cho các biến ngôn ngữ Xi và AY cho biến ngôn ngữ Y. Step 2. Sử dụng các ánh xạ ngữ nghĩa định lượng Xi và Y chuyển đổi mô hình mờ về mô hình định lượng ngữ nghĩa (gọi là mô hình SAM ). Step 3. Sử dụng một phép kết nhập đưa mô hình định lượng ngữ nghĩa về đường cong Cr,2 gọi là đường cong định lượng ngữ nghĩa. Step 4. Ứng với giá trị đầu vào thực hoặc mờ, xác định giá trị định lượng
tương ứng, sử dụng phép kết nhập và xác định đầu ra tương ứng của phép nội
suy tuyến tính trên cong Cr,2, việc giải định lượng đầu ra của phép nội suy sẽ
cho kết quả lập luận. Kết quả phương pháp lập luận mờ sử dụng ĐSGT phụ thuộc vào 3 yếu tố chính. Cụ thể là: i) Chọn các tham số của các đại số gia tử Chúng ta biết rằng mô hình mờ (1.2) chứa m+1 biến ngôn ngữ, tương ứng
với đó là m+1 ĐSGT trong phương pháp lập luận mờ sử dụng ĐSGT là AXi, i
=1, .., m+1, trong đó AY = AXm+1, nên các các tham số của các ĐSGT gồm: 28 + Độ đo tính mờ của các phần tử sinh: fmAXi(c), fmAXi(c+) thỏa fmAXi(c) + fmAXi(c+) = 1 + Độ đo tính mờ của các gia tử: thỏa , , + = 1 ) = fm(ci Thông thường ta hay sử dụng trực giác để chọn các tham số này, các tham
+) = 0,5 và = = 0,5 trong quá trình lập luận số được chọn là fm(ci
sử dụng ĐSGT. ii) Xác định phép kết nhập và phép nội suy Các phương pháp lập luận mờ sử dụng ĐSGT thường sử dụng các phép
kết nhập AND = “PRODUCT” hoặc AND = “MIN” hoặc phép tích hợp có trọng
số để đưa mô hình ĐLNN về đường cong ngữ nghĩa định lượng, đầu ra được
xác định dựa trên việc định lượng, kết nhập các đầu vào và nội suy tuyến tính
trên đường cong này. iii) Vấn đề định lượng đầu vào thực Phép nội suy được xây dựng từ các mốc nội suy trong mô hình ĐLNN,
nên đầu vào của nó phải là các giá trị định lượng, do đó không gặp khó khăn gì
khi định lượng đầu vào mờ vì đã có hàm ĐLNN vAXi, với đầu vào là giá trị thực
thì việc định lượng thường được thiết lập theo nguyên tắc sau: Giả sử biến ngôn ngữ X thuộc khoảng thực [x0, x1] và các nhãn ngôn ngữ
của nó nhận giá trị định lượng trong khoảng thực [s0, s1]. Khi đó giá trị thực x
[x0, x1] được định lượng theo công thức (2.1). (2.1) Vấn đề giải định lượng được tiến hành ngược lại theo công thức (2.2): (2.2) Ta gọi (x0, x1) là khoảng xác định của biến X và (s0, s1) là khoảng ĐLNN tương ứng. 29 2.2. Các giải pháp tối ưu các tham số định lượng ngữ nghĩa Phương pháp lập luận mờ sử dụng ĐSGT (HAR) để giải bài toán lập luận
xấp xỉ mờ đa điều kiện trước đây, các tham số của các ĐSGT được chọn bởi
trực giác. Tuy nhiên việc chọn các tham số của ĐSGT bằng trực giác sẽ ảnh
hưởng đến các kết quả lập luận, do vậy ta sử dụng lại phương pháp này nhưng
với các tham số tối ưu, tức là các tham số ĐLNN sẽ được xác định bằng giải
thuật di truyền. Phân tích ảnh hưởng của các tham số trong việc định lượng: Trước khi đi vào việc tối ưu các tham số, ta sẽ xét một số ví dụ để thấy rõ hơn sự ảnh hưởng đến các giá trị định lượng của các tham số ĐLNN. Ví dụ 2.1. Để minh họa cho quan hệ giữa ngữ nghĩa của các từ và độ đo
tính mờ, chúng ta sẽ khảo sát miền ngôn ngữ của biến ngôn ngữ SPEED biểu
thị cho vận tốc trong hai trường hợp sau: (i) Vận tốc của mô tô và (ii) Vận tốc
của ô tô. Trường hợp (i): Giả sử chúng ta đang xét ĐSGT tuyến tính của biến vận
tốc SPEED, AX = (X, G, H, ), trong đó G = {0, slow, W, fast, 1}, H = {L, P}
và H+ = {V, M}, với L, P, M và V thay thế cho Little, Possibly, More và Very,
một cách tương ứng. Lấy miền tham chiếu của biến ngôn ngữ X là DS1 = [0,
125] tính theo km. Giả sử rằng vận tốc của mô tô không vượt quá 55 km/h được
xem là chậm (với mức độ nào đó). Vì thế, fm(c) = 55/125 = 0.44 và do đó
fm(c+) = 0.56. Chúng ta cũng giả sử rằng độ đo tính mờ của các gia tử là: (P)
= 0.32, (L) = 0.20, (M) = 0.30 và (V) = 0.18. Do đó ta có = 0.52 và =
0.48. Theo Mệnh đề 1.1, chúng ta có thể tính được độ đo tính mờ của các giá
trị ngôn ngữ trong miền ngôn ngữ X. Chẳng hạn một số độ đo tính mờ của các
giá trị ngôn ngữ được tính dưới đây. fm(Vfast) = (V)fm(c+) = 0.18 0.56 = 0.1008, fm(Pfast) = (P)fm(c+) = 0.32 0.56 = 0.1792 fm(Lslow) = (L)fm(c) = 0.20 0.44 = 0.088, fm(VLslow) = (V)(L)fm(c) = 0.18 0.088 = 0.01584. Trường hợp (ii): Giả sử ĐSGT được xét trong trường hợp này hoàn toàn
giống như trên nhưng miền tham chiếu là khác nhau, tức là DS2 = [0, 200]; Nếu
xem vận tốc của xe ô tô không vượt quá 120 km/h là chậm thì fm(slow) = 30 120/200 = 0.6, và fm(fast) = 0.4; Để dễ dàng so sánh, độ đo tính mờ của các gia
tử được chọn giống như Trường hợp 1, tức là (P) = 0.32, (L) = 0.20, (M) =
0.30 và (V) = 0.18. Khi đó ta có, fm(Vfast) = (V)fm(c+) = 0.18 0.4 = 0.072, fm(Pfast) = (P)fm(c+) = 0.32 0.4 = 0.128, fm(Lslow) = (L)fm(c) = 0.20 0.6 = 0.12, fm(VLslow) = (V)(L)fm(c) = 0.18 0.12 = 0.0216. Trường hợp (ii) với 3 gia tử: Bây giờ chúng ta xét ĐSGT AX chỉ gồm 3
gia tử, trong đó tập các gia tử âm H = {P, L} và tập gia tử dương H+ = {V}.
Vì (P) = 0.32 và (L) = 0.20, nên (V) = = 0.48. Do vậy, fm(Vfast) = (V)fm(c+) = 0.48 0.4 = 0.192, fm(Pfast) = (P)fm(c+) = 0.32 0.4 = 0.128, fm(Lfast) = (L)fm(c+) = 0.20 0.4 = 0.08. (Lưu ý rằng, fm(Vfast) + fm(Pfast) + fm(Lfast) = fm(c+)) fm(Lslow) = (L)fm(c) = 0.20 0.6 = 0.12, fm(VLslow) = (V)(L)fm(c) = 0.48 0.12 = 0.0576. Qua các ví dụ trên ta thấy rằng độ đo tính mờ của các giá trị ngôn ngữ phụ
thuộc rất nhiều vào cấu trúc ĐSGT, tức là phụ thuộc vào số lượng các gia tử,
độ đo tính mờ các phần tử sinh và độ đo tính mờ của các gia tử. Điều này cũng
lý giải tại sao các tham số của hàm ĐLNN cần được xác định phù hợp trong
phương pháp nội suy gia tử. Tiếp theo là ví dụ chứng tỏ sự ảnh hưởng của các tham số tới giá trị ĐLNN.
Để thuận tiện cho việc biểu diễn ngữ nghĩa của các giá trị ngôn ngữ, chúng ta
giả sử rằng miền tham chiếu thông thường của các biến ngôn ngữ là đoạn [a,
b] còn miền tham chiếu ngữ nghĩa là đoạn [0,1]. Việc chuyển đổi tuyến tính từ
[a, b] sang [0,1] được gọi là ngữ nghĩa hóa (semantization) còn việc chuyển
ngược lại từ đoạn [0,1] sang [a, b] được gọi là giải nghĩa (desemantization). Ví dụ 2.2. Chúng ta xét lại các ĐSGT trên của Ví dụ 2.1 và sử dụng hàm
ĐLNN như trong Định nghĩa 1.4. Với mỗi phần tử x X, ta ký hiệu r(x) là giá
trị trong miền tham chiếu [a, b] tương ứng với x. 31 Trường hợp (i): Ta có h–2 = L, h–1 = P, h1 = M, h2 = V. (c) = fm(c) = 0.48 0.44 = 0.2112, (c+) = + fm(c+) = 0.7312; (Vc+) = (c+) + Sign(Vc+) {fm(Mc+) + fm(Vc+) – 0.5[1 + Sign(Vc+)Sign(VVc+)( – )]fm(Vc+)} = = 0.7312 + {0.1680 + 0,1008 – 0.5[2] 0.1008} = 0.951616; r(Vfast) = (Vfast) 125 = 0.951616 125 = 118.952 (km). Trường hợp (ii): h–2 = L, h–1 = P, h1 = M, h2 = V. (c) = fm(c) = 0.48 0.6 = 0.288, (c+) = + fm(c+) = 0.808; (Vc+) = (c+) + Sign(Vc+) {fm(Mc+) + fm(Vc+) – 0.5[1 + Sign(Vc+)Sign(VVc+)( – )]fm(Vc+)} = = 0.808 + {0.120 + 0,072 – 0.5[2] 0.072} = 0.96544; r(Vfast) = (Vfast) 200 = 0.96544 200 = 193.088 (km). Trường hợp (ii) với 3 gia tử: h–2 = L, h–1 = P, h1 = V. (c) = fm(c) = 0.48 0.6 = 0.288, (c+) = + fm(c+) = 0.808; (Vfast) = (c+) + Sign(Vc+) {fm(Vc+) – 0.5[1 + Sign(Vc+)Sign(VVc+)( – )]fm(Vc+)} = = 0.808 + {0.192 – 0.5[2] 0.192} = 0.90784; r(Vfast) = (Vfast) 200 = 0.90784 200 = 181.568 (km). Tổng kết các trường hợp trên ta thu được bảng giá trị sau: Bảng 2. 1. So sánh các giá trị ĐLNN r(Vfast) (c) (c+) (Vfast) Trường hợp (i): fm(c+) = 0.56, (L) = 0.20, (P) = 0.32, 0.2112 0.7312 0.951616 118.952 km (M) = 0.30, (V) = 0.18 32 Trường hợp (ii): fm(c+) = 0.4, (P) = 0.32, (L) = 0.20, 0.2880 0.8080 0.965440 193.088 km (M) = 0.30, (V) = 0.18 Trường hợp (ii) với 3 gia tử: fm(c+) = 0.4, (P) = 0.32, 0.2880 0.8080 0.907840 181.568 km (L) = 0.20, (V) = 0.48 Tóm lại, độ đo tính mờ của các gia tử và các phần tử sinh, số lượng gia tử
trong ĐSGT sẽ quyết định giá trị ngữ nghĩa còn miền tham chiếu của các biến
sẽ quyết định các giá trị trong miền thực. Từ phân tích sự ảnh hưởng của các tham số ĐLNN của các ĐSGT ta đưa ra giải pháp xác định các tham số ĐLNN tối ưu như sau: i) Giải pháp 1: Tối ưu các tham số của các ĐSGT sử dụng giải thuật di truyền (GA); ii) Giải pháp 2: Lựa chọn các tham số của các ĐSGT bằng trực giác sau
đó hiệu chỉnh lại các tham số ĐLNN (tức là xác định mô hình ĐLNN
tối ưu) sử dụng giải thuật di truyền (GA). 2.3. Giải pháp xác định các tham số định lượng ngữ nghĩa tối ưu 2.3.1. Giải pháp tối ưu các tham số của đại số gia tử Giả sử rằng tồn tại một tiêu chuẩn được xác định bởi hàm g(X1(A0,1), …,
Xm(A0,m), Y(B0)) để đánh giá việc thực hiện phương pháp. Chẳng hạn,
g(X1(A0,1), …, Xm(A0,m), Y(B0)) được xác định bởi độ đo gần nhau từ điểm
(Agg(X1(A0,1), …, Xm(A0,m)), Y(B0)) tới đường cong thực Cr,2, đường cong
này được xác định từ các dữ liệu thực nghiệm của ứng dụng được xét. Khi đó,
bài toán tối ưu có thể được phát biểu như sau: Bài toán tối ưu: g(X1(A0,1), …, Xm(A0,m), Y(B0)) min Thỏa các điều kiện sau: j = 1, 2, …, m, và 0 < < 1 0 < j < 1, (2.3) , ji > 0, i = 1, 2, …, kj, j = 1, 2, …, m, 33 , i > 0, i = 1, 2, …, k, , wj > 0, j = 1, 2, …, m. Lưu ý rằng các tham số độ đo tính mờ của các phần tử sinh và các gia tử sẽ giúp cho phương pháp lập luận thích nghi với nhiều ứng dụng. Phương pháp tối ưu các tham số: Sử dụng GA để giải bài toán lập luận
mờ đa điều kiện, gọi là thuật toán tối ưu tham số cho ĐSGT, viết tắt là
OPHA(PAR1, f1), với f1 là hàm thích nghi, PAR1 các tham số của ĐSGT. Phương pháp lập luận mờ sử dụng ĐSGT có nhiều tham số phụ thuộc vào
số lượng các ĐSGT mà ta sử dụng hay số lượng biến ngôn ngữ và số lượng các
gia tử của các đại số, giả sử rằng chúng ta có m ĐSGT AXj, j = 1,…, m, của m
biến ngôn ngữ đầu vào Xj, j = 1,…, m, và một ĐSGT AY của biến ngôn ngữ
đầu ra Y. Tập tất cả các tham số của HA được biểu diễn bởi vectơ thực sau: PAR1 = (11, 12, …, , 1; …; m1, m2, …, , m; 1, 2, …, k, ; (2.4) w1, w2,…,wm) các thành phần của vectơ phải thỏa mãn điều kiện ràng buộc (2.3). Vectơ (2.4) được xem như một cá thể có (m + 2) nhiễm sắc thể: – Nhiễm sắc thể (j1, j2,…, , j) gồm (kj + 1) gien tương ứng cho ĐSGT AXj, j = 1,…, m; – Nhiễm sắc thể (1, 2, …, k, ) gồm (k + 1) gien của ĐSGT AY, – Nhiễm sắc thể (w1, w2, …, wm) gồm m gien biểu diễn cho các trọng số
của toán tử kết nhập. 2.3.2. Giải pháp xác định mô hình định lượng ngữ nghĩa tối ưu Xác định các giá trị ĐLNN bằng trực giác, sau đó dựa vào Định nghĩa 1.7
và Định lý 1.5 ta xác định các tham số hiệu chỉnh của mô hình ĐLNN. Để xác
định mô hình ĐLNN tối ưu bằng cách hiệu chỉnh mô hình ĐLNN (SAM) gốc
tức là hiệu chỉnh các tham số ĐLNN trong mô hình SAM. 2.3.2.1. Phân tích ảnh hưởng các tham số hiệu chỉnh Để thấy rõ sự ảnh hưởng việc hiệu chỉnh giá trị định lượng nghĩa ta xét ví dụ 2.3 cho hai trường hợp k=1 và k =2. 34 Ví dụ 2.3. Xét ĐSGT của biến ngôn ngữ tốc độ vòng quay của một mô tơ với: c– = Slow, W = Medium và c+ = Fast; q = 1 và h-1 = Little; p = 1và h1 = Very; Giả sử ta chọn các tham số của ĐSGT như sau: fm(Slow) = 0.5 và fm(Fast) = 0.5; (Little) = (Very) = 0.5 theo Mệnh đề 1.1 ta có = = 0.5 và theo Định nghĩa 1.7 ta xác định được: v(Slow) =0.25; v(Medium) = 0.5; v(Fast) = 0.75; Theo Định lý 1.5 ta có: Với k = 1, 1 = min {fm(x)/2, fm(x)/2 | x X1} = = min {fm(Slow)/2, fm(Slow)/2, fm(Fast)/2, fm(Fast)/2} = min {0.125; 0.125; 0.125; 0.125} = 0.125 Với k = 2, 1= min {fm(x)/2, fm(x)/2 | x X2} = = min {fm(LitleSlow)/2, fm(LitleSlow)/2, fm(VerySlow)/2,
fm(VerySlow)/2, fm(LitleFast)/2, fm(LitleFast)/2, fm(VeryFast)/2,
fm(VeryFast)/2} = 0.0625 2.3.2.2. Thuật toán xác định mô hình định lượng ngữ nghĩa tối ưu Giả sử có mô hình ngữ nghĩa định lượng có m biến ngôn ngữ đầu vào Xj,
j = 1,…, m và biến ngôn ngữ đầu ra Y, khi đó mỗi biến ngôn ngữ Xj (cố định j
= 1, …,m) ta có n tham số hiệu chỉnh ĐLNN và n tham số hiệu chỉnh ĐLNN
của biến ngôn ngữ Y và tổng quát như sau: - Tham số hiệu chỉnh ĐLNN của biến ngôn ngữ Xj là: ((11,21,…,n1),
(12,22,..,n2),…,(1m,2m,….,nm) - Tham số hiệu chỉnh ĐLNN của biến ngôn ngữ Y là: (1, 2, ….,n) Bộ tham số hiệu chỉnh ĐLNN của các giá trị ngôn ngữ là: (2.5) PAR2=((11,21,…,n1),(12,22,..,n2),…,(1m,2m,..,nm);(1,2,..,n)) với điều kiện ràng buộc: (2.6) |ij|<Xj ;i =1,…, n; j = 1,…, m |i | <Y ;i =1,…, n 35 Sử dụng giải thuật di truyền xác định tham số hiệu chỉnh ĐLNN của
các giá trị ngôn ngữ: Giả sử tồn tại một mô hình sai số của phương pháp lập
luận cho bởi hàm h(g,OPHA(PAR2)) 0, trong đó g là mô hình thực mong
muốn và OPHA(PAR2) là mô hình được xấp xỉ bằng OPHA. Khi đó bài toán
xác định các tham số hiệu chỉnh ĐLNN được phát biểu như sau: Tìm các tham số PAR2 sao cho h(g, OPHA(PAR2)) min Đây là một bài toán tối ưu gồm nhiều biến có ràng buộc, do vậy sử dụng
khả năng cực tiểu hóa hàm nhiều biến của giải thuật di truyền (GA) để xác định
các giá trị hiệu chỉnh ĐLNN của các giá trị ngôn ngữ. - Tập tất cả các tham số hiệu chỉnh ĐLNN được biểu diễn bởi vector thực
sau: ((11,21,…,n1), (12,22,..,n2),…,(1m,2m,….,nm); (1,2,..,n)) Các thành phần của vector phải thỏa mãn điều kiện ràng buộc (2.6) và vector (2.5) được xem như một cá thể có nhiễm sắc thể sau: - Nhiễm sắc thể (1j,2j,..,nj) gồm n genes tương ứng cho ĐSGT AXj, j
=1,…, m; - Nhiễm sắc thể (1, 2,.., n ) gồm n genes tương ứng cho ĐSGT AY Trên cơ sở bộ tham số hiệu chỉnh ĐLNN và hàm thích nghi được xác định,
sử dụng giải thuật di truyền cổ điển với mã hóa nhị phân được đề cập trong
chương 1, ta xác định được bộ tham số hiệu chỉnh ĐLNN theo thuật toán
OPHA. Thuật toán OPHA(PAR2, f) - Optimization Parameters of Hedge Algebras Gọi P là quần thể cần duy trì; Q là quần thể được tạo ra sau khi lai ghép và R là quần thể được tạo ra sau khi đột biến. Inputs: - Mô hình mờ IF … THEN bao gồm các luật trong đó mỗi biến ngôn ngữ tương ứng với một ĐSGT; - f hàm thích nghi được xác định theo tiêu chuẩn g kết hợp với mô hình IF … THEN; Outputs: Bộ tham số tối ưu. 36 Actions: Đặt t := 0; Khởi tạo P(t); /* P(t): Quần thể ở thế hệ thứ t */ Tính độ thích nghi của các cá thể thuộc P(t); While (t T) do t := t + 1; Lai ghép Q(t) từ P(t - 1); /* Q(t) được tạo ra từ P(t - 1)*/ Đột biến R(t) từ P(t - 1); /* R(t) được tạo ra từ P(t - 1) */ Chọn lọc P(t) từ P(t - 1) Q(t) R(t) theo hàm thích nghi f; EndWhile. Return Cá thể có giá trị thích nghi nhất trong P(t); End of OPHA. 2.4. Phương pháp lập luận mờ sử dụng đại số gia tử dựa trên các mô hình
định lượng ngữ nghĩa tối ưu. 2.4.1. Vấn đề xác định giá trị định lượng ngữ nghĩa tối ưu Với mục tiêu xây dựng phương pháp lập luận mờ sử dụng ĐSGT nhằm
nâng cao hiệu quả của phương pháp lập luận xấp xỉ mờ dựa trên ĐSGT. Do đó
việc xác định được các giá trị ĐLNN tốt sẽ làm cho phương pháp lập luận hợp
lý hơn hoặc tốt hơn là tối ưu. Với lý do trên, đề tài nghiên cứu một hướng khác đơn giản hơn so với các
phương pháp lập luận trước là chấp nhận việc chọn các giá trị biến ngôn ngữ
theo trực giác trên cơ sở ĐSGT của các biến ngôn ngữ và các giá trị ĐLNN là
tương đối hợp lý nhưng chưa phải tối ưu. Do vậy, ta chỉ cần hiệu chỉnh các giá
trị ĐLNN bằng trực giác trong một khoảng nào đấy để phương pháp lập luận
là tối ưu. Để hiệu chỉnh các giá trị ĐLNN ta cần ta cần phải xác định ngưỡng hiệu
chỉnh tham số ĐLNN và phương pháp xác định tham số hiệu chỉnh ĐLNN tốt
nhất. 37 2.4.2. Sử dụng tham số hiệu chỉnh tối ưu cho phương pháp lập luận mờ sử
dụng đại số gia tử Phương pháp lập luận mờ sử dụng ĐSGT theo tiếp cận hiệu chỉnh giá trị
ĐLNN với ngưỡng khác với các phương pháp lập luận trong tài liệu [1, 11, 12,
13] ở bước xác định các giá trị ĐLNN của các giá trị ngôn ngữ, và ý tưởng của
phương pháp lập luận như sau: - Các tham số ĐSGT được chọn bằng trực giác, từ đó xác định các giá trị
ĐLNN của các giá trị ngôn ngữ như phương pháp lập luận mờ sử dụng ĐSGT
(HAR). - Hiệu chỉnh bộ nhớ liên hợp định lượng (mô hình SAM gốc) bằng cách
hiệu chỉnh các giá trị ĐLNN của các giá trị ngôn ngữ trong mô hình SAM gốc.
Như vậy ta cố định các giá trị ĐLNN của các giá trị ngôn ngữ, tuy nhiên để các
giá trị ĐLNN tốt hơn ta hiệu chỉnh giá trị ĐLNN bằng cách đưa vào các tham
số hiệu chỉnh, các tham số này phải nhỏ hơn giá trị ngưỡng hiệu chỉnh tồn tại
như trong Định lý 1.5 đã đề cập. - Xây dựng phương pháp lập luận dựa trên cơ sở hiệu chỉnh các giá trị
ĐLNN trong mô hình SAM gốc, phương pháp này gọi là phương pháp lập luận
mờ sử dụng ĐSGT theo tiếp cận hiệu chỉnh giá trị ĐLNN với ngưỡng. Theo đó phương pháp gồm các bước như sau: Input: Mô hình mờ bao gồm các luật trong đó mỗi biến ngôn ngữ tương ứng với một ĐSGT. Output: Giá trị đầu ra tương ứng với giá trị đầu vào. Action: Bước 1. Xây dựng các ĐSGT AXj cho các biến ngôn ngữ Xj, và ĐSGT AY cho biến ngôn ngữ Y. Giả thiết ĐSGT AXj, và Aij (i = 1,…, n; j = 1,…, m) là các giá trị ngôn ngữ
của biến ngôn ngữ Xj, tập giá trị ĐLNN của Xj là (Xj(A1j), Xj(A2j),…,Xj(Aij);
ĐSGT AY, và Bi (i = 1,…,n) là các giá trị ngôn ngữ của biến ngôn ngữ Y, tập
giá trị ĐLNN của Y là (Y(B1), Y(B2),…,Y(Bi)). Bước 2. Sử dụng các ánh xạ ĐLNN xác định mô hình SAM gốc. Xây dựng
mô hình hiệu chỉnh bộ nhớ liên hợp định lượng, tức là ta đưa các tham số hiệu
chỉnh ĐLNN ((Xj(Aij) + ij), (Y(Bi)+ i)) vào mô hình SAM gốc, trong đó ij là 38 tham số hiệu chỉnh ĐLNN của Xj, i là tham số hiệu chỉnh ĐLNN của Y, thoả
mãn điều kiện |ij| < Xj, |i | < Y với Xj, Y là ngưỡng hiệu chỉnh ĐLNN của
các biến ngôn ngữ Xj và Y. Bước 3. Xây dựng một phép nội suy tuyến tính trên cơ sở các mốc nội suy
là các điểm của mô hình SAM có các tham số hiệu chỉnh ĐLNN, gọi là mô hình
SAM(PAR2). Bước 4. Ứng với giá trị đầu vào thực hoặc mờ, xác định đầu ra tương ứng nhờ phép nội suy được xây dựng ở bước 3. Để tiện theo dõi phương pháp lập luận mờ sử dụng ĐSGT theo tiếp cận
hiệu chỉnh giá trị ĐLNN với ngưỡng, ký hiệu là GA_HAR. Cụ thể phương pháp
thực hiện như sau: - Sử dụng giải thuật di truyền để xác định bộ tham số hiệu chỉnh ĐLNN (PAR2) của các giá trị ngôn ngữ trong ĐSGT. Giả sử mô hình SAM gốc có m biến ngôn ngữ đầu vào Xj, j = 1,…, m, và
biến ngôn ngữ đầu ra Y, khi đó mỗi biến ngôn ngữ Xj (cố định j = 1, …,m) ta có
n tham số hiệu chỉnh ĐLNN, và n tham số hiệu chỉnh ĐLNN của biến ngôn
ngữ Y, và tổng quát như sau: - Tham số hiệu chỉnh ĐLNN của biến ngôn ngữ Xj là: ((11,21,…,n1),
(12,22,..,n2),…,(1m,2m,….,nm) - Tham số hiệu chỉnh ĐLNN của biến ngôn ngữ Y là: (1, 2 , ….,n ) Bộ tham số hiệu chỉnh ĐLNN của các giá trị ngôn ngữ là: PAR2=((11,21,…,n1),(12,22,..,n2),…,(1m,2m,..,nm);(1,2,..,n)) (2.7) với điều kiện ràng buộc: (2.8) |ij| < Xj ; i =1,…, n; j = 1,…, m |i | < Y ; i =1,…, n Giải pháp sử dụng giải thuật di truyền cho phương pháp GA_HAR: Giả sử tồn tại một mô hình sai số của phương pháp lập luận cho bởi hàm
h(g,OPHA(PAR2,f)) ≥ 0, trong đó g là mô hình thực mong muốn và
OPHA(PAR2, f) là mô hình xác định bộ tham số (PAR2) của các ĐSGT. Khi đó 39 bài toán xác định bộ tham số của các ĐSGT được phát biểu như sau: Tìm các
tham số PAR sao cho h(g,OPHA(PAR2,f)) min. Đây là một bài toán tối ưu gồm nhiều biến có ràng buộc, do vậy sử dụng
khả năng cực tiểu hóa hàm nhiều biến của giải thuật di truyền để xác định các
giá trị hiệu chỉnh ĐLNN của các giá trị ngôn ngữ. - Tập tất cả các tham số hiệu chỉnh ĐLNN được biểu diễn bởi vector thực
sau: ((11,21,…,n1), (12,22,..,n2),…,(1m,2m,….,nm); (1,2,..,n)) Các thành phần của vector phải thỏa mãn điều kiện ràng buộc (2.8) và vector (2.7) được xem như một cá thể có nhiễm sắc thể sau: - Nhiễm sắc thể (1j,2j,..,nj) gồm n gien tương ứng cho ĐSGT AXj, j
=1,…, m; - Nhiễm sắc thể (1, 2,.., n ) gồm n gien tương ứng cho ĐSGT AY Trên cơ sở bộ tham số hiệu chỉnh ĐLNN và hàm thích nghi được xác định,
sử dụng giải thuật di truyền cổ điển với mã hóa nhị phân được đề cập trong
chương 1 ta xác định được bộ tham số hiệu chỉnh ĐLNN. Đây là một bài toán tối ưu gồm nhiều biến có ràng buộc, do vậy sử dụng
khả năng cực tiểu hóa hàm nhiều biến của giải thuật di truyền để xác định các
tham số của các ĐSGT. 2.5. Tổng kết Chương 2 Nội dung chương đã trình bày tổng quát phương pháp lập luận mờ dựa
trên ĐSGT truyền thống (HAR). Trên cơ sở phân tích các yếu tố ảnh hưởng đến
kết quả lập luận của phương pháp lập luận HAR, luận văn đưa ra giải pháp để
nâng cao hiệu quả của phương pháp lập luận HAR, cụ thể: Tìm hiểu khả năng
tính toán tối ưu các tham số của ĐSGT và các tham số hiệu chỉnh ĐLNN của
các ĐSGT bằng giải thuật di truyền. Trên cơ sở xác định tham số hiệu chỉnh ĐLNN, mô hình ĐLNN tối ưu xây
dựng thuật toán cho phương pháp lập luận mờ dựa trên ĐSGT sử dụng tham số
hiệu chỉnh tối ưu, gọi tắt là GA_HAR. Kết quả Chương 2 có ý nghĩa rất quan trọng trong việc ứng dụng phương pháp GA_HAR vào một số bài toán điều khiển mờ ở Chương 3. 40 CHƯƠNG 3: ỨNG DỤNG PHƯƠNG PHÁP LẬP LUẬN XẤP XỈ MỜ
SỬ DỤNG ĐẠI SỐ GIA TỬ VỚI MÔ HÌNH ĐỊNH LƯỢNG NGỮ
NGHĨA TỐI ƯU TRONG ĐIỀU KHIỂN Trên cơ sở đó chúng ta có thể đưa ra một phương pháp ĐLNN miền ngôn
ngữ. Nhờ các ánh xạ ngữ nghĩa như vậy sẽ dễ dàng xây dựng một phương pháp
lập luận xấp xỉ để giải quyết bài toán lập luận mờ đa điều kiện, nhiều biến trong
kỹ thuật. Với phương pháp lập luận đã nêu trong Chương 2, có rất nhiều khả năng
để ứng dụng. Tuy nhiên, nội dung luận văn chỉ chọn lĩnh vực điều khiển mờ vì
như vậy sẽ dễ dàng cho việc đánh giá các kết quả thực hiện. Điều kiện để ứng
dụng là các bài toán điều khiển mờ cần phải có tập luật xác định trước. 3.1. Mô tả một số bài toán điều khiển logic mờ 3.1.1. Bài toán 1: Xấp xỉ mô hình mờ EX1 của Cao-Kandel [9] Cho mô hình gồm các luật (Bảng 3.1) thể hiện sự phụ thuộc của tốc độ quay N vào cường độ dòng điện I; Bảng 3. 1. Mô hình EX1 của Cao-Kandel If I is ... Then N is ... Null Large Zero Large Small Medium Medium Small Large Zero VeryLarge Zero Cho cường độ dòng điện I nhận giá trị trong đoạn [0, 10] và tốc độ quay N của mô tơ nhận các giá trị trong đoạn [400, 2000] Cần xác định tốc độ vòng quay ứng với các giá trị của cường độ dòng điện
Cao-Kandel đã nghiên cứu các toán tử kéo theo và sử dụng chúng trong lập
luận mờ để giải quyết bài toán trên, tác giả cũng đã đưa ra kết quả thực nghiệm
thể hiện mối quan hệ giữa I và N thể hiện ở Hình 3.1 và gọi đây là đường cong
thực nghiệm, sai số giữa mô hình xấp xỉ và mô hình thực nghiệm được xác
định theo công thức sau: 41 Tác giả đã xác định được 5 toán tử kéo theo cho kết quả lập luận xấp xỉ tốt nhất, kết quả thể hiện ở Bảng 3.2 Hình 3. 1. Đường cong thực nghiệm của mô hình EX1 Bảng 3. 2. Các kết quả xấp xỉ EX1 tốt nhất của Cao-Kandel [9] Phương pháp Sai số lớn nhất
của mô hình EX1 PP của Cao-Kandel với toán tử kéo theo 5* 200 PP của Cao-Kandel với toán tử kéo theo 22* 200 PP của Cao-Kandel với toán tử kéo theo 8 300 PP của Cao-Kandel với toán tử kéo theo 25 300 PP của Cao-Kandel với toán tử kéo theo 31 300 3.1.2. Bài toán 2: Bài toán hệ con lắc ngược [8] Bài toán điều khiển con lắc ngược là bài toán kinh điển với hệ được xét là
một hệ phi tuyến (Hình 3.2). Mục đích của việc điều khiển là đưa con lắc về vị
trí cân bằng. Phương trình vi phân mô tả hệ con lắc ngược được cho như sau: (3.2) 42 d/dt m u Trong đó m là khối lượng của vật ở đầu con lắc; l là chiều dài của con lắc;
là góc lệch so với phương thẳng đứng; u(t), giá trị điều khiển tại thời điểm t;
g là hằng số gia tốc trọng trường. Hình 3. 2. Mô tả hệ con lắc ngược Giả sử rằng x1 = và x2 = d/dt là các biến trạng thái. Trong trường hợp góc lệch nhỏ thì sin() = , với được đo bằng radian. Chọn chiều dài con lắc l = g và khối lượng m = 180/(π.g2), bằng cách tuyến
tính hóa hệ ban đầu như trong [22], ta thu được hệ gồm hai phương trình tuyến
tính rời rạc phi đơn vị. (3.3) x1(k+1) = x1(k) + x2(k) (3.4) x2(k+1) = x1(k) + x2(k) – u(k) trong đó đơn vị đo của x1 là độ, đơn vị đo của x2 là dps (degree per second). Yêu cầu bài toán: Tìm giá trị điều khiển u dựa trên các luật để điều khiển
con lắc luôn giữ ở phương thẳng đứng, vị trí này còn gọi là vị trí ổn định tức là x1 = 0 và x2 = 0. Sai số cho hệ con lắc ngược: (3.5) Hệ luật điều khiển con lắc ngược. Trong [8], các nhãn ngôn ngữ của các biến X1, X2 và u như sau: P(Positive), N (Negative), Z (Zero), PB (Positive Big), NB (Negative Big). Các luật điều khiển thiết kế cho quá trình điều khiển mờ được cho ở Bảng 3.3 (mô hình FAM). 43 Bảng 3. 3. Mô hình FAM cho hệ con lắc ngược X2 P Z N X1 P PB P Z Z P Z N N Z N NB 3.2. Ứng dụng phương pháp lập luận xấp xỉ mờ sử dụng đại số gia tử trong
điều khiển 3.2.1. Phương pháp điều khiển logic mờ truyền thống Mục này, tóm tắt các bước xây dựng phương pháp điều khiển mờ truyền thống, ký hiệu là CFC (Conventional Fuzzy Control). Về nguyên lý, hệ thống điều khiển CFC cũng không có gì khác với các hệ
thống điều khiển khác. Sự khác biệt ở đây là bộ điều khiển CFC làm việc có tư
duy như bộ não dưới dạng trí tuệ nhân tạo hay gọi là mô hình FAM. Hệ thống điều khiển CFC làm việc dựa trên kinh nghiệm và phương pháp
rút ra kết luận theo tư duy của con người, sau đó được cài đặt vào máy tính trên
cơ sở của logic mờ. Hệ thống điều khiển mờ được thiết kế như Hình 3.3 gồm các khâu sau: - Giao diện đầu vào bao gồm khâu fuzzy hóa và các khâu phụ trợ thêm để thực hiện các bài toán động như tích phân, vi phân… - Thiết bị hợp thành là sự triển khai luật hợp thành được xây dựng trên cơ sở luật điều khiển . - Giao diện đầu ra gồm các khâu giải mờ và các khâu giao diện trực tiếp với đối tượng. 44 Hình 3. 3. Sơ đồ phương pháp điều khiển CFC Thông thường phương pháp điều khiển CFC sẽ bao gồm các bước chính sau đây: Bước 1: Xác định biến trạng thái (biến vào) và biến điều khiển (biến ra) của đối tượng điều khiển và xác định tập nền của các biến. Bước 2: Phân hoạch tập nền thành các phần tương ứng với các nhãn ngôn ngữ. Bước 3: Xây dựng các tập mờ cho các nhãn ngôn ngữ, tức là xác định dạng hàm thuộc cho mỗi tập mờ. Bước 4: Xây dựng quan hệ mờ giữa các tập mờ đầu vào, tập mờ trạng thái
và tập mờ điều khiển tạo thành hệ luật điều khiển (bảng điều khiển trên cơ sở
tri thức chuyên gia), gọi là mô hình FAM. Bước 5: Giải bài toán lập luận xấp xỉ, xác định tập mờ đầu vào của biến điều khiển theo từng luật (Phép hợp thành). Bước 6: Kết nhập (aggregation) các giá trị đầu ra. Bước 7: Giải mờ, tìm giá trị điều khiển rõ. 3.2.2. Phương pháp lập luận xấp xỉ mờ sử dụng đại số gia tử trong điều khiển Mô hình mờ (1.2) trong điều khiển gọi là bộ nhớ kết hợp mờ FAM. Vì có m biến đầu vào nên ta gọi FAM là mô hình m chiều. Trong phương pháp này, xem miền giá trị ngôn ngữ của mỗi biến Xj (j=1,…, m) là một ĐSGT. Xác định các ĐSGT AXj= (Xj, Gj, Hj, j) cho các biến vật lý Xj (j=1,…, m)
và đại số AY=(Y, G, H, ) cho biến Y. Với mỗi đại số ta cần xác định tập phần
tử sinh, tập các gia tử và độ đo tính mờ của các gia tử. 45 Định lượng các giá trị ngôn ngữ trong FAM sang các giá trị thực trong
đoạn [0,1] nhờ vào hàm ĐLNN : Xj(Aij), Y(Bi) (i = 1, ..., n, j = 1,..., m). Như
vậy, với mỗi luật if–then sẽ tương ứng với một điểm trong không gian thực
(m+1) chiều. Khi đó mô hình mờ sẽ tương ứng với đường cong thực Cr,m+1 trong
không gian (m+1) chiều. Chuyển mỗi điểm (X1(Ai1), X2(Ai2),…,Xm(Aim),Y(Bi)) trong không gian
thực (m+1) chiều thành điểm Agg(Xj(Ai1), Xj(Ai2),…,Xj(Aim),Y(Bi)) trong
không gian thực hai chiều với Agg là toán tử kết nhập. Đường cong Cr,m+1 trở
thành đường cong thực C2 trong mặt phẳng. Từ bộ giá trị đầu vào (Ai1, Ai2,…,
Aim) ta tính được giá trị thực. a0 = Agg(X1(Ai1), X2(Ai2),…,Xm(Aim),Y(Bi)) Từ đây, giá trị thực đầu ra u0 = Noisuy(a0, C2) – là giá trị nội suy thu được
từ đầu vào a0 trên đường cong thực C2. Như vậy, giá trị điều khiển được tính
theo giá trị ngữ nghĩa u0 và không gian tham chiếu của biến điều khiển. Dựa trên phương pháp lập luận mờ sử dụng ĐSGT [11] mô hình điều
khiển mờ sử dụng ĐSGT, gọi tắt là FCHA (Fuzzy Control using Hedge
Algebras) được mô tả như Hình 3.4. Hình 3. 4. Sơ đồ phương pháp điều khiển FCHA Thuật toán điều khiển gồm các bước chính sau: Bước 1: Ngữ nghĩa hóa (Semantization). - Như chúng ta đã biết, cơ sở tri thức của mỗi ứng dụng được cho ở dạng
mô hình FAM chứa các giá trị ngôn ngữ trong miền ngôn ngữ Xj. Mỗi miền
ngôn ngữ Xj sẽ tương ứng với một ĐSGT và một miền tham chiếu số thực [sj1,
sj2], j = 1, …, m. Vì giá trị ngữ nghĩa được định lượng bởi hàm ĐLNN j của 46 các giá trị ngôn ngữ của biến Xj thuộc đoạn [0,1] nên trong quá trình tính toán
chúng ta cần có ánh xạ để chuyển tuyến tính từ miền tham chiếu [sj1, sj2] sang
miền ngữ nghĩa [0,1]. Việc chuyển này được gọi là ngữ nghĩa hóa. Các giá trị
của hàm j được gọi là giá trị ĐLNN và biến tương ứng với Xj nhận các giá trị
ngữ nghĩa được gọi là biến ngữ nghĩa, ký hiệu xsj. - Vấn đề cốt yếu của quá trình là xác định các tham số như độ đo tính mờ
của các phần tử sinh và độ đo tính mờ của các gia tử trong các ĐSGT của các
biến Xj một cách thích hợp dựa trên phân tích ngữ nghĩa của miền ngôn ngữ.
Chẳng hạn, các tham số của biến vận tốc SPEED sẽ không giống nhau giữa ô
tô và tàu hỏa. Hay, vì Very và Little là đặc trưng hơn More và Possibly, nên
chúng ta có thể giả sử rằng (More) > (Very) và (Possibly) > (Little). Đây
là những tham số có thể hiệu chỉnh. Bước 2: Xây dựng ánh xạ ĐLNN và cơ chế lập luận. Dùng hàm ĐLNN với các tham số đã được xác định trong Bước 1, chuyển
mô hình FAM sang bảng dữ liệu số m-chiều, gọi là mô hình SAM (Semantics
Associative Memory). Lưu ý rằng, n ô của mô hình SAM sẽ xác định n điểm,
mô tả một siêu mặt Cr,m+1 trong không gian thực (m+1) chiều. Kế tiếp, chúng ta
chọn toán tử kết nhập Agg để tích hợp m thành phần của mô hình SAM, từ đó
xây dựng được mô hình mới gọi là mô hình SAM. Từ n ô của mô hình SAM sẽ
xác định n điểm trong không gian thực hai chiều và như vậy ta thu được đường
cong thực Cr,2 trong không gian 2 chiều. Dùng phép nội suy tuyến tính trên
đường cong thực Cr,2 để tính toán giá trị đầu ra cho mô hình (1.2). Bước 3: Giải nghĩa (Desemantization). Đơn giản là thiết lập một ánh xạ để gán mỗi giá trị ngữ nghĩa, tức là giá trị
thực trong đoạn [0,1], với một giá trị thực của miền giá trị của biến điều khiển. Trong các nghiên cứu gần đây [11] ta có cơ sở để tin rằng, phương pháp
điều khiển gồm 3 bước trên như mô tả ở Hình 3.4 đơn giản và hiệu quả hơn so
với phương pháp điều khiển dựa trên lý thuyết tập mờ. Căn cứ để thấy rõ tính
hiệu quả của sơ đồ điều khiển là: i) Thay vì xây dựng các hàm thuộc thì trong phương pháp này chỉ cần xác định các tham số của hàm ĐLNN dựa vào Bước 1. 47 ii) Phương pháp lập luận xấp xỉ dựa trên phương pháp nội suy cổ điển
với đường cong ngữ nghĩa định lượng là rất đơn giản, trực quan và cho
kết quả đầu ra chính xác hơn. iii) Sơ đồ điều khiển ở trên là rất linh hoạt vì có thể dễ dàng thay đổi các
tham số của hàm ĐLNN để thích nghi với nhiều ứng dụng điều khiển
khác nhau. iv) Không cần thiết sử dụng phương pháp khử mờ. v) Tránh được các vấn đề phức tạp, dễ dẫn đến sai sót như xây dựng các
hàm thuộc, chọn toán tử kéo theo, hợp thành các luật và khử mờ. 3.2.3. Phương pháp lập luận xấp xỉ mờ sử dụng đại số gia tử với các mô
hình định lượng ngữ nghĩa tối ưu trong điều khiển Như ta đã biết, phương pháp GA_HAR đã đề xuất chương 2 cho kết quả
rất khả quan. Do vậy, ta sử dụng phương pháp lập luận GA_HAR vào phương
pháp điều khiển mờ. Phương pháp điều khiển mờ sử dụng phương pháp
GA_HAR được gọi là phương pháp lập luận mờ dựa trên ĐSGT với mô hình
ĐLNN tối ưu ứng dụng trong điều khiển, ký hiệu phương pháp điều khiển là
FCOPHA (Fuzzy Control using Optimal Hedge Algebras). Trước tiên, chúng ta nhận thấy rằng thông thường ý nghĩa của bài toán điều
khiển là đưa được đối tượng điều khiển về vị trí cân bằng hoặc tối thiểu hàm mục
tiêu trong toàn bộ quá trình điều khiển. Vì vậy, để tìm được các tham số tối ưu
cho việc thiết kế phương pháp điều khiển cần thực hiện như sau: i). Xác định các yếu tố, các ràng buộc cho trước – Tập cơ sở luật (mô hình FAM) với các giá trị ngôn ngữ mô tả cho các tri thức chuyên gia trong miền ứng dụng. – Các quan hệ tính toán giữa các biến trạng thái và biến điều khiển (nếu có). ii). Xác định các tham số hiệu chỉnh giá trị định lượng ngữ nghĩa 1. Xây dựng các ĐSGT cho các biến ngôn ngữ trong mô hình FAM. 2. Sử dụng các ánh xạ ngữ nghĩa định lượng vXj(Aij) và vY(Bi), chuyển đổi
mô hình mờ FAM sang mô hình SAM gốc. Xác định các tham số hiệu
, Y ; i=1,...,n, j =1,…,m} và các ngưỡng hiệu
chỉnh ĐLNN PAR2 ={ chỉnh của các tham số tương ứng. 48 3. Xác định hàm sai số của điều khiển dựa trên phương pháp lập luận mờ
sử dụng ĐSGT theo tiếp cận hiệu chỉnh ĐLNN với ngưỡng có hàm là
h(g,OPHA(PAR2)). 4. Xác định các tham số PAR2 của các giá trị ngôn ngữ sao cho hàm h(g,
OPHA(PAR2)) → min. iii). Xây dựng thuật toán điều khiển CFOPHA. Trên cơ sở xác định được các
yếu tố, các ràng buộc cho trước (i), và các tham số hiệu chỉnh ĐLNN (ii),
ta xây dựng thuật toán điều khiển gồm các bước sau: Bước 1. Xác định mô hình SAM(PAR2) và ngữ nghĩa hóa: Trong bước
này, chúng ta xây dựng mô hình SAM(PAR2) trên cơ sở đã xác định các giá trị
hiệu chỉnh ĐLNN. Bước 2. Tính toán giá trị ngữ nghĩa điều khiển: Xác định siêu mặt thực
Cr,m+1 từ mô hình SAM(PAR2). Áp dụng phương pháp nội suy để tính giá trị ngữ
nghĩa điều khiển tương ứng với giá trị đầu vào. Bước 3. Giải nghĩa giá trị đầu ra: Ngược với việc ngữ nghĩa hóa, bằng
cách sử dụng công thức 2.3 ta chuyển các giá trị ngữ nghĩa trong [0, 1] sang
miền tham chiếu ta tính được giá trị thực của biến điều khiển. 3.3. Ứng dụng Để thấy được hiệu quả của phương pháp lập luận GA_HAR và thuận tiện
cho việc so sánh, đánh giá hiệu quả phương pháp đề xuất với các phương pháp
lập luận mờ sử dụng ĐSGT trong điều khiển mờ (CFOPHA), và các phương
pháp điều khiển mờ khác hiện nay [8, 9, 11]. Sau đây, sử dụng phương pháp
lập luận GA_HAR giải quyết một số bài toán điều khiển mờ gọi là phương pháp
điều khiển CFOPHA cho bài toán mô hình mờ hình xấp xỉ EX1 của Cao Kandel
[9] và bài toán điều khiển mờ hệ con lắc ngược [8] của Ross. 3.3.1. Bài toán 1 Sử dụng phương pháp điều khiển CFOPHA để xấp xỉ mô hình EX1 của Cao-
Kandel. Các bước được thực hiện như sau: Bước 1: Xây dựng các ĐSGT cho các biến ngôn ngữ. Xây dựng các ĐSGT AI cho biến I và AN cho biến N gồm: - Tập các phần tử sinh: {Small, Medium, Lagre} 49 - Tập các gia tử: {Litle, Very} Chuyển các giá trị ngôn ngữ trong mô hình mờ sang các giá trị ngôn ngữ trong ĐSGT cho các biến I và N như sau. - Đối với biến I: Null →VeryVery Small; Zero → VerySmall; Small → Small; Medium → Medium; Large→ Large; VeryLarge → VeryLarge. - Đối với biến N: Zero→ VerySmall; Small→Small; Medium→ Medium; Large→ Large; VeryLarge→ VeryLarge. Bước 2. Các tham số của ĐSGT này được xác định bằng trực giác như sau: fmI(Small) = 0.5; fmN(Small) = 0.5; N(Very) = 0.5; I(Very) = 0.5 Sử dụng hàm ĐLNN, ta có: - Đối với biến I ta có: I(VeryVerySmall) = 0.0625; I(VerySmall) = 0.125; I(Small) = 0.25; I(Medium) = 0.5; I(Large) = 0.75; I(VeryLarge) = 0.875 - Đối với biến N ta có: N(VerySmall) = 0.125; N(Small) = 0.25; N(Medium) = 0.5; N(Large) = 0.75; N(VeryLarge) = 0.875 Áp dụng Định lý 1.5 xác định ngưỡng hiệu chỉnh của các giá trị ngôn ngữ. - Đối với biến I: có độ sâu k = 3, và ngưỡng hiệu chỉnh ĐLNN là I = 0.03125 - Đối với biến N: có độ sâu k = 2, và ngưỡng hiệu chỉnh ĐLNN là N = 0.0625 Chuyển đổi mô hình FAM sang mô hình SAM, Bảng 3.4. 50 Bảng 3. 4. Mô hình SAM gốc - xấp xỉ mô hình EX1 0.0625 0.125 0.25 0.5 0.75 0.875 Is 0.875 0.75 0.5 0.25 0.125 0.125 Ns Như vậy có 11 tham số hiệu chỉnh khác nhau sẽ ảnh hưởng tới phương
pháp lập luận mờ sử dụng ĐSGT trong bài toán này. Bộ tham số hiệu chỉnh giá
trị ĐLNN là: PAR2 ={Ii, i =1,…,6; Ni , i =7,…,11} với điều kiện: |Ii| < 0.03125 với i = 1,...,6 cho biến I và |Ni| < 0.0625 với i = 7,...,11 cho biến N. Mô hình SAM (PAR2) như trong Bảng 3.5. Bảng 3. 5. Mô hình SAM (PAR2) – xấp xỉ mô hình EX1 Is 0.0625+I1 0.125+I2 0.5 + I4 0.75 + I5 0.875 +I6 0.25
+I3 Ns 0.875 +N7 0.75+N8 0.5+N9 0.25 +N10 0.125+N1
1 0.125+N1
1 Bước 3. Sử dụng mạng phép nội suy tuyến tính kinh điển trên bề mặt của mô hình SAM(PAR2) Bước 4. Xác định đầu ra - Trước hết ta cho đầu vào các giá trị I từ 0 đến 10 với bước nhảy 0.5. - Định lượng giá trị thực và giải định lượng được thực hiện theo Công thức 2.1 và 2.2 với: s0 = 0.0625+I1, s1 = 0.875 +I6 và x0 = 0, x1 = 10 cho biến I. s0 = 0.875 +N7, s1 = 0.125+N11 và x0 = 2000, x1 =480 cho biến N. Sử dụng giải thuật di truyền như đã đề cập ở chương 1, cực tiểu hàm e
(Công thức 3.1) với số thế hệ bằng 300, xác suất lai ghép 0.80; xác suất đột
biến 0.05; kích cỡ quần thể 40; kích thước cá thể 10. Qua một số lần chạy thử trên MATLAB, ta xác định được PAR2 và kết quả xấp xỉ mô hình EX1 của Cao-Kandel là: PAR2={-0.031006;0.011455;0.028501;0.014205;-0.004979; 51 -0.031006;-0.059445;0.016312;0.061034;0.052969;-0.056024} e(EX1, OPHA) = 37.901974 (3.6) Trong khi đó phương pháp tối ưu các tham số tối ưu trong tài liệu [13] có kết quả là: e(EX1) = 62 (3.7) Hình 3. 5. Kết quả xấp xỉ mô hình EX1 của Cao Kandel Hình 3.5 là đường cong xấp xỉ mô hình EX1 của Cao-Kandel bằng phương pháp lập luận với các tham số tối ưu [13] và phương pháp OPHA. Bảng 3. 6. Sai số lớn nhất của các phương pháp trên mô hình EX1 Phương pháp Sai số lớn
nhất của mô
hình EX1 Phương pháp của Cao-Kandel với toán tử kéo theo 5* [9] 200 Phương pháp của Cao-Kandel với toán tử kéo theo 22* [9] 300 Phương pháp của Cao-Kandel với toán tử kéo theo 8 [9] 300 Phương pháp của Cao-Kandel với toán tử kéo theo 25 [9] 300 Phương pháp của Cao-Kandel với toán tử kéo theo 31 [9] 300 Phương pháp lập luận mờ sử dụng ĐSGT (FCHA) [10] 292 52 Phương pháp điều khiển sử dụng tối ưu các tham số [10] 62 Phương pháp điều khiển mờ sử dụng FCOPHA) 37.901974 Nhận xét bài toán 1: - Từ Hình 3.5 ta thấy phương pháp điều khiển FCOPHA bám rất sát đường cong thực nghiệm của Cao – Kandel. - Mặt khác từ Bảng 3.6, sai số lớn nhất của mô hình xấp xỉ EX1 sử dụng
phương pháp điều khiển FCOPHA là nhỏ nhất so với phương pháp lập luận tối
ưu các tham số [10] và các kết quả thử nghiệm của Cao – Kandel. 3.3.2. Bài toán 2 Sử dụng phương pháp FCOPHA cho bài toán điều khiển con lắc ngược. Bước 1: Xây dựng các tham số của các ĐSGT - Các nhãn ngôn ngữ được chuyển như trong Bảng 3.7 và 3.8. Bảng 3. 7. Chuyển nhãn ngôn ngữ cho các biến X1, X2 P Z N Large W Small Trong đó: Biến trạng thái X1 có miền giá trị là [-4, +4], biến trạng thái X2 có miền giá trị là [-10, +10]. Bảng 3. 8. Nhãn ngôn ngữ cho biến u NB N Z P PB More Small Possibly Small W Possibly Large More Large Trong đó: Biến trạng thái u có miền giá trị là [-16, +16]. Kết quả các giá trị ĐLNN của các biến ngôn ngữ X1, X2 và u như trong Bảng 3.9, (gọi là mô hình SAM gốc hệ con lắc ngược). Bảng 3. 9. Mô hình SAM gốc của hệ con lắc ngược X2 L: 0.75 W : 0.5 S : 0.25 X1 53 L : 0.75 ML: 0.8 PL : 0.7 W : 0.5 W : 0.5 PL : 0.7 W : 0.5 PS : 0.3 S : 0.25 W : 0.5 PS : 0.3 MS: 0.2 Bước 2: Từ mô hình SAM gốc trong Bảng 3.9, xây dựng các biến ngôn ngữ X1, X2 và u như sau; - Biến ngôn ngữ X1 có các giá trị ngôn ngữ NSmall, PLarge, ZW,
đây là các giá trị ngôn ngữ có độ sâu k = 1, theo Định lý 2.1 ngưỡng hiệu chỉnh
là 0.125 và giá trị định lượng của các giá trị ngôn ngữ được xác định như sau:
X1(Large) = 0.75+ X11; X1(W) = 0.5+ X12; X1(Small) = 0.25+X13 - Biến ngôn ngữ X2 có các giá trị ngôn ngữ NSmall, PLarge, ZW,
đây là các giá trị ngôn ngữ có độ sâu k = 1, theo Định lý 2.1 ngưỡng hiệu chỉnh
là 0.125 và giá trị định lượng của các giá trị ngôn ngữ được xác định như sau:
X2(Large) = 0.75+ X24; X2(W) = 0.5+ X25; X2(Small) = 0.25+X26 - Biến ngôn ngữ u có các giá trị ngôn ngữ NBMoreSmall,
NPossiblySmall, ZW, PPossiblyLarge, PBMoreLarge đây là các giá
trị ngôn ngữ có độ sâu k = 2, theo Định lý 2.1 ngưỡng hiệu chỉnh là 0.0625 và
giá trị định lượng của các giá trị ngôn ngữ được xác định như sau: u( MoreLarge) = 0.875+ u7; u( PossiblyLarge) = 0.7+ u8; u(W) = 0.5+ u9,
u( PossiblySmall) = 0.3+ u10 ; u( MoreSmall) = 0.2+u11 OpPAR = {X1i, i = 1,...,3; X2i, i = 4,...,6; ui, i = 7,...,10}; với điều kiện |X1i |< 0.125, i = 1,...,3 cho biến X1 |X2i |< 0.125, i = 4,...,6 cho biến X2 |ui |< 0.0625, i = 7,...,10 cho biến u. Khi đó mô hình SAM (PAR2) được xác định như trong Bảng 3.10. Bảng 3. 10. Mô hình SAM(PAR2) của hệ con lắc ngược X2s 0.75+X24 0.5+X25 0.25+X26 X1s 0.75+X11 0.8+u7 0.7+u8 0.5+u9 54 0.5+X12 0.7+u8 0.5+u9 0.3+u10 0.25+X13 0.5+u9 0.3+u10 0.2+u11 Bước 3. Sử dụng phép nội suy tuyến tính với phép kết nhập có trọng số.
Xây dựng phép nội suy tuyến tính với phép kết nhập có trọng số agg =X1s*w1
+ X2s*w2 các trọng số được xác định nhờ công cụ giải thuật di truyền. Bước 4. Xác định đầu ra. Áp dụng phương pháp CFOPHA cho hệ con lắc ngược với giá trị ban đầu của các trạng thái là các giá trị rõ X1(1) = 1.00 và X2(1) = -4. Sử dụng phép nội suy tuyến tính dựa trên các mốc trong mô hình SAM, việc giải định lượng sẽ cho ta giá trị u tại chu kỳ đầu. Tiếp tục tính toán cho các chu kỳ tiếp theo nhờ các phương trình 3.3, 3.4.
Lặp lại quá trình tính cho đến khi hệ con lắc ngược về ví trị cân bằng, sai số e
của hệ được xác định nhờ công thức 3.5. Việc ngữ nghĩa hóa và giải nghĩa tiến hành theo công thức 2.3, 2.4 với: - s0 = 0.75+X11, s1 = 0.25+X13 và x0 = 4, x1 = -4 cho biến X1 - s0 = 0.75+X24, s1 = 0.25+X26 và x0 = 4, x1 = -4 cho biến X2 - s0 = 0.8+u7, s1 = 0.2+u11 và x0 = 16, x1 = -16 cho biến u. Sử dụng giải thuật di truyền cực tiểu hàm e với số thế hệ bằng 200, xác
suất lai ghép 0.80; xác suất đột biến 0.05; kích cỡ quần thể 40; kích thước cá
thể 10. Qua một số lần chạy mô phỏng trên MATLAB, ta xác định OPHA và các trọng số kết nhập là: PAR2= {0.083456; 0.076369; -0.109360; -0.068060; -0.058040; -0.056329; - 0.035618; 0.028409; 0.032319; 0.051259; 0.013991} - Giá trị trọng số phép kết nhập: w1 = 0.222874 ; w2 = 0.777126 - Sai số điều khiển được so sánh trên Bảng 3.11 55 Bảng 3. 11. Sai số các phương pháp của hệ con lắc ngược Phương pháp Sai số Điều khiển Phương pháp lập luận mờ sử dụng ĐSGT (FCHA) [10] 15.48957 Phương pháp lập luận mờ tối ưu các tham số của ĐSGT [10] 4.757936 Phương pháp điều khiển mờ sử dụng FCOPHA 4.643746 Với tiêu chuẩn so sánh này, qua đồ thị ở Hình 3.6 ta thấy phương pháp FCOPHA cho kết quả tốt hơn so với các phương pháp trong [10]. Hình 3. 6. Đồ thị lỗi của hệ con lắc ngược Nhận xét bài toán 2: - Từ Bảng 3.11 ta thấy tổng sai số qua các chu kỳ điều khiển sử dụng
phương pháp lập luận GA_HA (FCOPHA) là nhỏ nhất so với tổng sai số của
các phương pháp lập luận mờ tối ưu các tham số [10] và phương pháp FCHA. - Qua kết quả điều khiển trong Hình 3.5, phương pháp FCOPHA sau 2 chu
kỳ con lắc ngược đã có xu hướng về vị trí cân bằng và hàm mục tiêu nhận giá
trị nhỏ nhất. 3.4. Kết luận Chương 3 Trong Chương 3, đã ứng dụng phương pháp lập luận xấp xỉ mờ sử dụng
ĐSGT trong điều khiển và cài đặt và thử nghiệm cho một số bài toán điều 56 khiển logic mờ, cụ thể là: - Bài toán Xấp xỉ mô hình mờ EX1 của Cao-Kandel [9] - Bài toán Hệ con lắc ngược [8] Qua kết quả ta có thể khẳng định rằng; tính hiệu quả của phương pháp
điều khiển mờ sử dụng GA_HAR và mở ra khả năng ứng dụng tốt vào các bài
toán mô hình mờ phức tạp hơn. 57 KẾT LUẬN Nghiên cứu về lý thuyết ĐSGT, tìm hiểu khả năng tính toán tối ưu các
tham số của ĐSGT và các tham số hiệu chỉnh ĐLNN của các ĐSGT bằng giải
thuật di truyền là một mảng rất rộng mà thế giới đang nghiên cứu và phát triển.
Nếu tìm hiểu tất cả các vấn đề đó là lượng kiến thức khổng lồ. Trong luận văn
học viên đã chú trọng nghiên cứu, trình bày những kiến thức cơ bản về biến
ngôn ngữ và mô hình mờ, phương pháp lập luận xấp xỉ mờ là cơ sở để phát
triển phương pháp lập luận mờ sử dụng ĐSGT và giải thuật di truyền từ đó áp
dụng vào giải bài toán Xấp xỉ mô hình mờ EX1 của Cao-Kandel [9] và bài toán
Hệ con lắc ngược [8]. Qua đó luận văn đã đạt được một số kết quả như sau: Về lý thuyết: Tập trung nghiên cứu các kiến thức chung nhất về biến ngôn
ngữ và mô hình mờ, ĐSGT, phương pháp lập luận xấp xỉ mờ sử dụng ĐSGT và
giải thuật di truyền dùng để tìm kiếm các tham số tối ưu của các ĐSGT. Luận văn
đã phân tích kỹ về phương pháp lập luận xấp xỉ mờ sử dụng ĐSGT. Cụ thể: - Tìm hiểu khả năng tính toán tối ưu các tham số của ĐSGT và các tham số hiệu chỉnh ĐLNN của các ĐSGT bằng giải thuật di truyền. - Sử dụng giải thuật di truyền để xác định bộ tham số hiệu chỉnh tối ưu của các ĐSGT. Về ứng dụng: Cài đặt phương pháp lập luận xấp xỉ mờ sử dụng ĐSGT
với các mô hình ĐLNN tối ưu trong điều khiển cho bài toán Xấp xỉ mô hình
EX1 của Cao-Kandel và bài toán Hệ con lắc ngược của Ross. Trên cơ sở kết
quả cài đặt có so sánh và đánh giá kết quả cài đặt các phương pháp lập luận xấp
xỉ mờ dựa trên ĐSGT - HAR. Phạm vi và khả năng áp dụng: Luận văn là một tài liệu tham khảo tốt
cho những người đang nghiên cứu về lý thuyết ĐSGT và ứng dụng nó trong
các lĩnh vực khoa học kỹ thuật. Hướng nghiên cứu tiếp theo: Hoàn thiện và tối ưu phương pháp lập luận
xấp xỉ mờ dựa trên ĐSGT với các mô hình ĐLNN tối ưu trong điều khiển cho
các bài toán điều khiển mờ phức tạp. 58 TÀI LIỆU THAM KHẢO * Tiếng Việt Luận án tiến sĩ toán học, Viện Công nghệ thông tin. nhiên các bài toán trên máy tính, Nhà xuất bản giáo dục. * Tiếng Anh Edition, John Wiley & Sons. operators”, Fuzzy Sets and Systems , 31, pp. 151-186. to approximate reasoning”, Inform. Sci. 8, pp. 199–249. 59[1] Nguyễn Cát Hồ (2006), “Lý thuyết tập mờ và Công nghệ tính toán mềm”,
Tuyển tập các bài giảng về Trường thu hệ mờ và ứng dụng, in lần thứ 2,
tr. 51–92.
[2] Nguyễn Duy Minh (2012), Tiếp cận đại số gia tử trong điều khiển mờ,
[3] Đặng Thị Thu Hiền (2009), Bài toán nội suy và mạng nơron RBF, Luận
án tiến sĩ chuyên ngành khoa học máy tính cấp nhà nước, Trường Đại học
công nghệ, Đại học quốc gia Hà Nội...
[4] Trần Thái Sơn, Nguyễn Thế Dũng (2005), “Một phương pháp nội suy giải
bài toán mô hình mờ trên cơ sở đại số gia tử”, Tạp chí Tin học và Điều
khiển học, Tập 21(3), tr. 248–260.
[5] Hoàng Kiếm, Lê Hoàng Thái (2000), Giải thuật di truyền – cách giải tự
[6] Nguyễn Duy Minh (2011), “Điều chỉnh ngữ nghĩa định lượng của giá trị
ngôn ngữ trong đại số gia tử và ứng dụng”, Tạp chí khoa học và công
nghệ, Viện Khoa học và Công nghệ Việt Nam, Tập 49(4), tr. 27-40.
[7] Nguyễn Cát Hồ, Vũ Như Lân, Phạm Thanh Hà (2007), “Xác định trọng
số tối ưu cho phép tích hợp trong phương pháp điều khiển sử dụng đại số
gia tử bằng giải thuật di truyền”, Tạp chí tin học và điều khiển học, Tập
23(3), tr. 1-10.
[8] Ross T. J. (2010), Fuzzy logic with Engineering Applications, Third
[9] Cao Z. and Kandel A. (1989), “Applicability of some fuzzy implication
[10] Ho N. C., Lan V. N., Viet L. X. (2008), “Optimal hedge-algebras-based
controller: Design and application”, Fuzzy Sets and Systems, 159(8), pp.
968–989.
[11] Zadeh L. A. (1975), “The concept of linguistic variable and its application
[12] Ho N. C., Wechler W. (1990), “Hedge algebra: An algebraic approach to
structures of sets of linguistic truth values”, Fuzzy Sets and Systems 35,
pp. 281–293.
[13] Ho N. C., Long N. V. (2007), “Fuzziness measure on complete hedge
algebras and quantifying semantics of terms in linear hedge algebras”,
Fuzzy Sets and Systems, 158(4), pp. 452–471.
