Tài liệu Lập luận mờ sử dụng đại số gia tử theo tiếp cận hiệu chỉnh định lượng ngữ nghĩa của các giá trị ngôn ngữ và ứng dụng

1 ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG PHẠM ĐỨC CƢỜNG LẬP LUẬN MỜ SỬ DỤNG ĐẠI SỐ GIA TỬ THEO TIẾP CẬN HIỆU CHỈNH ĐỊNH LƢỢNG NGỮ NGHĨA CỦA CÁC GIÁ TRỊ NGÔN NGỮ VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH THÁI NGUYÊN - 2016 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn 1 ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG PHẠM ĐỨC CƢỜNG LẬP LUẬN MỜ SỬ DỤNG ĐẠI SỐ GIA TỬ THEO TIẾP CẬN HIỆU CHỈNH ĐỊNH LƢỢNG NGỮ NGHĨA CỦA CÁC GIÁ TRỊ NGÔN NGỮ VÀ ỨNG DỤNG 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 - 2016 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn i LỜI CAM ĐOAN Tôi xin cam đoan luận văn này do chính tôi thực hiện, dƣới sự hƣớng dẫn khoa học của TS. Nguyễn Duy Minh, số liệu và kết quả nghiên cứu trong luận văn này hoàn toàn trung thực và chƣa sử dụng để bảo vệ một công trình khoa học nào, các thông tin, tài liệu trích dẫn trong luận văn đã đƣợc chỉ rõ nguồn gốc. Mọi sự giúp đỡ cho việc hoàn thành luận văn đều đã đƣợc cảm ơn. Nếu sai tôi hoàn toàn chịu trách nhiệm. Thái Nguyên, tháng 04 năm 2016 Học viên Phạm Đức Cƣờng Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn ii LỜI CẢM ƠN Trƣớc hết em xin trân trọng cảm ơn các thầy giáo, cô giáo trƣờng đại học công nghệ thông tin đã giảng dạy em trong quá trình học tập chƣơng trình sau đại học. Dù rằng, trong quá trình học tập có nhiều khó khăn trong việc tiếp thu kiến thức cũng nhƣ sƣu tầm tài liệu học tập, nhƣng với sự nhiệt tình và tâm huyết của thầy cô cộng với những nỗ lực của bản thân đã giúp em vƣợt qua đƣợc những trở ngại đó. Em xin bày tỏ lòng biết ơn sâu sắc tới thầy giáo TS.Nguyễn Duy Minh ngƣời hƣớng dẫn khoa học, đã tận tình hƣớng dẫn em trong suốt quá trình làm luận văn. Xin chân thành cảm ơn các bạn bè, đồng nghiệp, các bạn học viên lớp cao học CK13B, 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. Một lần nữa em xin chân thành cảm ơn. Thái Nguyên, tháng 04 năm 2016 Học viên Phạm Đức Cƣờng Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn iii MỤC LỤC Lời cam đoan ........................................................................................................ i Lời cảm ơn ........................................................................................................... ii Mục lục ............................................................................................................... iii Danh mục các bảng ............................................................................................... v Danh mục các hình ............................................................................................... vi LỜI MỞ ĐẦU ....................................................................................................... 1 CHƢƠNG 1:TỔNG QUAN VỀ LÝ THUYẾT ........................................................ 3 1.1 Biến ngôn ngữ .....................................................................................3 1.1.1 Khái niệm hàm thuộc .....................................................................3 1.1.2 Định nghĩa biến ngôn ngữ .................................................................. 3 1.2 Đại số gia tử ................................................................................................... 5 1.2.1 Đại số gia tử của biến ngôn ngữ ........................................................... 5 1.2.2 Độ đo tính mờ và ánh xạ định lượng ngữ nghĩa ................................... 8 1.3 Mô hình mờ ....................................................................................... 15 1.4 Bài toán tối ƣu và giải thuật di truyền................................................. 16 1.4.1. Bài toán tối ưu ........................................................................... 16 1.4.2. Giải thuật di truyền .................................................................... 17 1.4.2.1 Giới thiệu chung ........................................................................ 17 1.4.2.2 Giải thuật di truyền đơn giản ................................................... 19 1.4.2.3. Cơ chế thực hiện của giải thuật di truyền ............................... 22 1.5 Kết luận chƣơng 1 ............................................................................... 25 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn iv CHƢƠNG 2:PHƢƠNG PHÁP XÁC ĐỊNH GIÁ TRỊ HIỆU CHỈNH ĐỊNH LƢỢNG NGỮ NGHĨA CỦA CÁC NGÔN NGỮ ..................................... 26 2.1 Phƣơng pháp lập luận mờ sử dụng đại số gia tử ............................................ 26 2.2Hiệu chỉnh định lƣợng ngữ nghĩa của giá trị ngôn ngữ ....................... 35 2.2.1Vấn đề hiệu chỉnh định lƣợng ngữ nghĩa ..................................... 35 2.2.2Khái niệm ngưỡng hiệu chỉnh định lượng ngữ nghĩa ......................... 36 2.2.3 Phân tích ảnh hƣởng các tham số hiệu chỉnh ............................. 40 2.2.4Thuật toán xác định các tham số hiệu chỉnh định lượng ngữ nghĩa của các gia trị ngôn ngữ...................................................................................... 40 2.3Phƣơng pháp lập luận mờ sử dụng ĐSGT theo tiếp cận hiệu chỉnh định lƣợng ngữ nghĩa .................................................................................................. 42 2.4Kết luận chƣơng2 ............................................................................. 44 CHƢƠNG 3:ỨNG DỤNG LẬP LUẬN MỜ DỰA TRÊN ĐẠI SỐ GIA TỬ VỚI THAM SỐ HIỆU CHỈNH TỐI ƢU ............................................................ 43 3.1Mô tả bài toán con lắc ngƣợc ........................................................... 43 3.2 Ứng dụng phƣơng pháp lập luận dựa trên ĐSGT với tham số hiệu chỉnh ...... 44 3.2.1Phƣơng pháp lập luận mờ dựa trên đại số gia tử ........................ 44 3.2.2Phương pháp lập luận mờ dựa trên đại số gia tử với tham số hiệu chỉnh tối ưu ......................................................................................................... 47 3.4Kết luận chƣơng3 ............................................................................. 55 KẾT LUẬN............................................................................................ 55 TÀI LIỆU THAM KHẢO .................................................................... 57 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn v DANH MỤC CÁC BẢNG Bảng 1.1. Ví dụ về tính âm dƣơng giữa các gia tử .................................7 Bảng 2.1 Mô hình EX1 của Cao – Kandel ............................................. 27 Bảng 2.2. Các kết quả xấp xỉ EX1 tốt nhất của Cao- Kande .............. 28 Bảng 2.3 Mô hình mờ EX1 đƣợc định lƣợng theo trƣờng hợp 1 ........ 30 Bảng 2.4 Mô hình mờ EX1 đƣợc định lƣợng theo trƣờng hợp 2 ........ 31 Bảng 3.1.Bảng mô hình tập các luật cho bài toán con lắc ngƣợc ........ 44 Bảng 3.2. Mô hình FAM cho hệ con lắc ngƣợc .................................... 45 Bảng 3.3 Chuyển nhãn ngôn ngữ cho các biến X1, X2 ......................... 45 Bảng 3.4. Nhãn ngôn ngữ cho biến u .................................................. 45 Bảng 3.5. Mô hình ngữ nghĩa định lƣợng SAM của hệ con lắc ngƣợc46 Bảng 3.6. Kết quả tính toán bài toán con lắc ngƣợc ............................ 47 Bảng 3.7. Mô hình SAM - xấp xỉ mô hình EX1 ................................... 49 Bảng 3.8 Mô hình SAM (PAR) – xấp xỉ mô hình EX1 ......................... 49 Bảng 3.9. Sai số lớn nhất của các phƣơng pháp trên mô hình EX1 .... 51 Bảng 3.10. Mô hình SAM(PAR) 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 .................. 54 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn vi DANH MỤC CÁC HÌNH Hình 1.1. Hình ảnh minh hoạ của toán tử lai ghép một điểm cắt... .... 18 Hình 2.1.Đường cong thực nghiệm của mô hình EX1 .............................. 28 Hình 2.2.Đƣờng cong ngữ nghĩa định lƣợng của ví dụ 2.1, trƣờng hợp 1 .......................................................................................... 30 Hình 2.3. Đƣờng cong ngữ nghĩa định lƣợng của ví dụ 2.1, trƣờng hợp 1 .......................................................................................... 32 Hình 2.4. Kết quả xấp xỉ EX1 trong ví dụ 2.3....................................... 33 Hình 2.5. Các khoảng mờ của X .......................................................... 35 Hình 2.6. Khoảng mờ J(y) và phân hoạch của nó ................................ 36 Hình 2.7. Khoảng mờ J(x) và J(y)......................................................... 36 Hình 3.1. Mô tả hệ con lắc ngƣợc ........................................................ 43 Hình 3.2. Đƣờng cong ngữ nghĩa ......................................................... 46 Hình 3.3. Kết quả xấp xỉ mô hình EX1 của Cao Kandel .................... 51 Hình 3.4. Đồ thị lỗi của hệ con lắc ngƣợc ............................................ 54 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn 1 LỜI NÓI ĐẦU 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ờ. Lý thuyết tập mờ và logic mờ đƣợc L.A. Zadeh đề xuất vào giữa thập niên 60 của thế kỷ trƣớc. Kể từ khi ra đời, lý thuyết tập mờ và ứng dụng của tập mờ đã đƣợc phát triển liên tục với mục đích xây dựng các phƣơng pháp lập luận xấp xỉ để mô hình hóa quá trình suy luận của con ngƣời. Cho đến nay phƣơng pháp lập luận xấp xỉ dựa trên lý thuyết tập mờ đã đƣợc quan tâm nghiên cứu trên cả phƣơng diện lý thuyết và ứng dụng trong nhiều lĩnh vực rất khác nhau, đã đạt đƣợc nhiều thành tựu ứng dụng, đặc biệt là các ứng dụng trong các hệ chuyên gia mờ, điều khiển mờ [13]. Để đá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 đã đề 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ữ, 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‟. Xuất phát từ quan hệ ngữ nghĩa đó các tác giả đã phát triển lý thuyết đại số gia tử (ĐSGT). Với việc định lƣợng các từ ngôn ngữ nhƣ đã đề cập, một số phƣơng pháp lập luận mờ dựa trên ĐSGT ra đời nhằm mục đích giải quyết các bài toán lập luận mờ, các bài toán đƣợc ứng dụng nhiều trong tự nhiên, kỹ thuật [1],[7],[10], phƣơng pháp này đƣợc gọi là phƣơng pháp lập luận mờ dựa trên ĐSGT (HAIRMd - Hedge Algebras-based Interpolative Reasoning Method). Thực tế các tác giả đã nghiên cứu định lƣợng các giá trị ngôn ngữ trong ĐSGT, đƣa ra đƣợc công thức giải tích xác định ánh xạ định lƣợng ngữ nghĩa với các tham số là độ đo tính mờ của các phần tử sinh và độ đo tính mờ của các gia tử. Theo đó mỗi giá trị ngôn ngữ có độ sâu k bất kỳ của biến ngôn ngữ đƣợc Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn 2 định lƣợng bằng một giá trị thực thuộc khoảng [0,1] sao cho thứ tự của các giá trị ngôn ngữ của một đại số đƣợc bảo toàn. Tuy nhiên khi ứng dụng ĐSGT vào giải các bài toán thực tế, ta chỉ sử dụng các giá trị ngôn ngữ có độ sâu k hữu hạn. Với việc hạn chế độ sâu giá trị ngôn ngữ, ta hoàn toàn có thể hiệu chỉnh định lƣợng ngữ nghĩa của các giá trị ngôn ngữ này mà vẫn bảo toàn đƣợc thứ tự của chúng. Và mục tiêu của đề tài là tìm ra giá trị hiệu chỉnh định lƣợng ngữ nghĩa hợp lý của các giá trị ngôn ngữ khi độ sâu của giá trị ngôn ngữ đƣợc giới hạn và ứng dụng vào giải quyết một số bài toán thực tế. Để thực hiện điều này đề tài tìm hiểu các lý thuyết liên quan và nghiên cứu về việc hiệu chỉnh định lƣợng ngữ nghĩa và ứng dụng của nó trong lập luận mờ sử dụng ĐSGT. Phƣơng pháp này đƣợc cài đặt thử nghiệm trên một số bài toán lập luận mờ, 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ố. Nội dung nghiên cứu đƣợc trình bày trong đề tài: Lập luận mờ sử dụng đại số gia tử theo tiếp cận hiệu chỉnh định lƣợng ngữ nghĩa của giá trị ngôn ngữ và ứng dụng Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn 3 CHƢƠNG 1: TỔNG QUAN VỀ LÝ THUYẾT 1.1 Biến ngôn ngữ 1.1.1 Khái niệm hàm thuộc Giả thiết một tập vũ trụ U (còn gọi là không gian tham chiếu), một tập con thông thƣờng A (tập rõ) của U có thể đƣợc đặc trƣng bởi hàm A nhƣ sau: 1, x  A 0, x  A  A ( x)   Gọi A là phần bù của tập A, ta có A A = , A A = U. Nếu x A thì x  A , ta viết A(x) = 1,  A (x) = 0. Dễ dàng ta có, nếu A, B là hai tập con của U, thì hàm đặc trƣng của các tập AB, AB đƣợc xác định: 1, x  A  B 0, x  A  B  A B ( x)   và 1, x  A  B 0, x  A  B  A B ( x)   Định nghĩa 1.1.([11]) Cho U là vũ trụ các đối tƣợng. Tập mờ A trên U là tập các cặp có thứ tự (x, A(x)), với A(x) là hàm từ U vào [0,1] gán cho mỗi phần tử x thuộc U giá trị A(x) phản ánh mức độ của x thuộc vào tập mờ A. Nếu A(x) = 0 thì ta nói x hoàn toàn không thuộc vào tập A, ngoài ra nếu A(x)= 1 thì ta nói x thuộc hoàn toàn vào A. Trong Định nghĩa 1.1, hàm còn đƣợc gọi là hàm thuộc (membership function). Hàm thuộc có thể đƣợc biểu diễn dƣới dạng liên tục hoặc rời rạc. Đối với vũ trụ U là vô hạn thì tập mờ A trên U thƣờng đƣợc biểu diễn dạng Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn 4 A    A ( x) / x , còn đối với vũ trụ hữu hạn hoặc rời rạc U = {x1, x2, …, xn}, thì tập mờ A có thể đƣợc biểu diễn A = {µ1/x1 + µ2/x2 + … + µn/xn}, trong đó các giá trị µi (i = 1, …, n) biểu thị mức độ thuộc của xi vào tập A. Có nhiều dạng hàm thuộc để biểu diễn cho tập mờ A, mà trong đó dạng hình thang, hình tam giác và hình chuông là thông dụng nhất. 1.1.2 Định nghĩa biến ngôn ngữ Khái niệm biến ngôn ngữ lần đầu tiên đƣợc Zadeh giới thiệu trong [11], ta có thể hình dung khái niệm này qua Định nghĩa 1.2. Định nghĩa 1.2. 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, Rlà 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: Biến ngôn ngữ X = NHIET_ĐO đƣợc xác định nhƣ sau: - 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(NHIET_DO) = {cao, rất cao, tương_đối cao, thấp, rất thấp, trung bình, …}. - R là một tập các qui tắc để sinh ra các giá trị ngôn ngữ của biến NHIET_ĐO, 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: u  170 0,  u  170  , 170  u  185 cao(u) =  15  185  u 1,  Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn 5 1.2 Đại số gia tử 1.2.1 Đại số gia tử của biến ngôn ngữ Giả sử X là một biến ngôn ngữ và miền giá trị của X là Dom(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 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, H là tập các gia tử và quan hệ “” là quan hệ cảm sinh ngữ nghĩa trên X. Ví dụ 1.2: Giả sử X là tốc độ quay của một mô tơ điện thì X = {fast, very fast, possible fast, very slow, low... }{0, W, 1 }, G = {fast, slow,0, W, 1 }, với 0, W, 1 là phần tử bé nhất, phần tử trung hòa và phần tử lớn nhất tƣơng ứng, H={very, more, possible, little} với X = H(G). Nếu các tập X, H– và H+ là các tập sắp thứ tự tuyến tính, khi đó ta nói AX= (X , G, 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ử đƣợc ký hiệu là 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 sinh ra từ x bằng cách sử dụng các gia tử trong H tác động vào x và ta viết u = hn…h1x, với hn, …, h1H. Trong luận án sử dụng ký hiệu X thay cho Dom(X). Nhƣ chúng ta đã biết trong [4], cấu trúc AX đƣợc xây dựng từ một số tính chất của các phần tử ngôn ngữ. Các tính chất này đƣợc biểu thị bởi quan hệ thứ tự ngữ nghĩa  của các phần tử trong X. Sau đây ta sẽ nhắc lại một số tính chất trực giác: i) Hai phần tử sinh của biến ngôn ngữ có khuynh hƣớng ngữ nghĩa trái ngƣợc nhau: fast có khuynh hƣớng “đi lên” còn gọi là hƣớng dƣơng ký hiệu c+, slow có khuynh hƣớng “đi xuống” còn gọi là hƣớng âm, ký hiệu c-. Đơn giản, theo quan hệ thứ tự ngữ nghĩa ta có: c+>c. Chẳng hạn fast>slow. ii) Về trực giác, mỗi gia tử có khuynh hƣớng làm tăng hoặc giảm ngữ nghĩa của phần tử sinh nguyên thủy. Chẳng hạn nhƣ Very fast>fast và Very Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn 6 slow slow vì thế Little có khuynh hƣớng làm yếu đi ngữ nghĩa của phần tử sinh. Ta nói Very là gia tử dƣơng và Little là gia tử âm. Ta ký hiệu H là tập các gia tử âm, H+ là tập các gia tử dƣơng và H = H-  H+. Nếu cả hai gia tử h và k cùng thuộc H+ hoặc H, thì vì AX là tuyến tính, nên chúngsánh đƣợc với nhau. Dễ thấy Little và Possible là sánh đƣợc với nhau (Little>Posible) do vậy Little false>Possible false>false. Ngƣợc lại, nếu h và k không đồng thời thuộc H+ hoặc H-, khi đó ta nói h, k ngƣợc nhau. iii) Hơn nữa, chúng ta nhận thấy mỗi gia tử đều có tác động làm tăng hoặc làm giảm tác động của các gia tử khác. Vì vậy, nếu k làm tăng tác động của h, ta nói k là dƣơng đối với h. Ngƣợc lại, nếu k làm giảm tác động của h, ta nói k là âm đối với h. Chẳng hạn xét các gia tử ngôn ngữ V(Very), M(More), L(Little), P (Possible), của biến ngôn ngữ TRUTH. Vì L true 0 và  +  = 1. Định nghĩa 1.6 (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+}: a) Sign(c) = 1, Sign(c+) = +1, b) Sign(hc)= Sign(c)nếu hc  c và h là âm tính đối với c; c) Sign(hc)= Sign(c)nếu hc  c và h là dƣơng tính đối với c; d) Sign(h'hx) = Sign(hx), nếu h’hx  hx vàh' âm tính đối với h ; e) Sign(h'hx) = Sign(hx), nếu h’hx  hx và h' dƣơng tínhđối với h ; f) Sign(h'hx) = 0, nếuh’hx = hx. Dấu hàm Sign đƣợc đƣa ra để sử dụng nhận biết khi nào gia tử tác động vào các từ làm tăng hay giảm ngữ nghĩa của giá trị ngôn ngữ. Bổ đề 1.1.Với mọi h và x, nếu Sign(hx)= +1 thì hx>x, nếu Sign(hx) = 1 thì hx - Xem thêm -