Xây dựng 1 phân hệ hỗ trợ một số quy trình phân loại và sắp xếp các phương án cần lựa chọn

ong những vướng mắc của em, luôn giúp đỡ, cung cấp cho em những tài liệu bổ ích để em có thể hoàn thành đồ án của mình. Em xin chân thành cảm ơn tập thể các thầy, cô giáo trong Khoa Công nghệ Thông Tin – Viện Đại Học Mở Hà Nội đã truyền đạt kiến thức và giúp đỡ em trong quá trình học tập tại trường. Cuối cùng em xin cám ơn các bạn, các anh và các thầy cô trong tập thể Seminal – Khoa Toán ứng dụng – Trường Đại Học Bách Khoa hà Nội những người đã chỉ bảo, bàn bạc và giúp đỡ em trong quá trình học tập, nghiên cứu các lĩnh vực cơ bản của toán học là nền tảng để em có thể hoàn thành đồ án của mình. Do thời gian nghiên cứu có hạn nên đồ án của em sẽ không tránh khỏi những sai sót, hoặc không chính xác trong ngôn ngữ chuyên ngành, vì vậy em rất mong nhận được sự chỉ bảo, của các thầy cô giáo và sự đóng góp của toàn thể các bạn sinh viên. Hà Nội 20/6/2004 Sinh viên: Nguyễn Thành Huylời nói đầu Lý thuyết tập mờ (Fuzzy Set Theory) được ra đời từ năm 1965 do công trình nghiên cứu của nhà toán học người Mỹ L.Zadeh đã đặt nền móng cho việc xây dựng một loạt các lý thuyết quan trọng dựa trên lý thuyết tập mờ. Nhưng sự bùng nổ của lý thuyết tập mờ thì chỉ thực sự diễn ra trong khoảng 20 năm gần đây, nhờ những ứng dụng vào thực tiễn mà đặc trưng là dự án lớn LIFE của Nhật Bản(1989-1995). Kết hợp với mạng Nơ-ron (Neuron) nhân tạo lý thuyết tập mờ đã tạo nên hai công nghệ hiện đại chính để tạo nên công nghệ tích hợp mới đó là công nghệ tính toán mềm (soft computing). Một trong những ứng dụng quan trọng của lý thuyết tập mờ là việc mô hình hoá các quá trình tư duy, lập luận của con người để tự động hoá hỗ trợ các hoạt động tư duy, xây dựng các hệ chuyên gia lấy quyết định…. Được tiếp cận với giáo trình của lý thuyết tập mờ, đồng thời dưới sự hướng dẫn tận tình của GS-TSKH Bùi Công Cường em đã nhận thấy được những ứng dụng ban đầu của lý thuyết tập mờ vào trong bài toán lấy quyết định và phân loại những phương án lựa chọn dựa trên lý thuyết tập mờ. Do đó em xin mạnh dạn lựa chọn đề tài : “ Xây dựng một phân hệ hỗ trợ một số quy trình phân loại và sắp xếp các phương án cần lựa chọn. ” làm đề tài đồ án tốt nghiệp cho mình. Đồ án của em gồm 3 chương: Chương I : Những kiến thức cơ bản về lý thuyết tập mờ. Chương II: Bài toán lấy quyết định và các quy trình, phương pháp lấy quyết định. Chương III : Xây dựng chương trình thực nghiệm phân loại đánh giá dự án kinh tế Mục lục Chương I Những kiến thức cơ bản về lý thuyết tập mờ Lý thuyết tập mờ Tập mờ: Trước khi lý thuyết tập mờ ra đời thì lý thuyết tập hợp là công cụ cơ bản để giải quyết các bài toán thực tiễn. Với lý thuyết tập hợp việc xác định 1 tập A thuộc không gian nền X nào đó thực chất là việc xác định một hàm đặc trưng: A (x)= Thay vì việc đánh giá bằng hàm đặc trưng với hai điểm rời rạc 0,1 L.Zadeh đã xây dựng khái niệm tập mờ bằng một hàm liên tục trên đoạn [0,1] được định nghĩa như sau: Định nghĩa: A là tập mờ trên không gian nền X nếu A được xác định bởi hàm: A: X [0,1] A là hàm thuộc (membership function) còn A(x) là độ thuộc của x vào tập mờ A. Kí hiệu: A = {(A(x)/x): x X} b) Ví dụ : Cho không gian nền là thời gian sống U={0,135 năm} khi đó A là tập mờ với người có độ tuổi trung niên là: A={(0, 29), (0.1, 30), (0.2, 32), (0.3, 34),…,(0.8,45),(0.9, 48),(1, 50)} Giả sử tập B là tập người có độ tuổi trung niên được phân mức theo lý thuyết tập rõ là như sau: B={30,31,32,33…,50} Rõ ràng ở đây ta thấy rằng nếu sử dụng tập rõ thì tồn tại sự không công bằng trong việc đánh giá một người thuộc độ tuổi trung niên hay không. Khi đó lý thuyết tập mờ đã chỉ ra rằng: - Độ thuộc của người 29 tuổi là 0 nghĩa là người này không thuộc lớp trung niên - Độ thuộc của người 30 tuổi là 0.1 …. Như vậy việc sử dụng tập mờ cho ta cách đánh giá gần với ngôn ngữ tự nhiên hơn, như “còn trẻ ”, “ hơi già”, “đứng tuổi”, “cỡ trung niên”… 1.2 Các phép toán đại số trên tập mờ: Phép giao của hai tập mờ: Cho A, B là hai tập mờ trên không gian nền X, có các hàm thuộc A,, B . Khi đó phép giao AB là tập mờ trên X có hàm thuộc: A(x) = min{ A (x), B (x)} Phép hợp của hai tập mờ: Cho A, B là hai tập mờ trên không gian nền X có các hàm thuộc A,, B . Khi đó phép hợp AB là tập mờ trên X có hàm thuộc: A(x) = max{ A (x), B (x)} Phần bù của một tập mờ: Cho A là tập mờ trên không gian nền X có hàm thuộc A . Phần bù của A trên X là một tập mờ có hàm thuộc: Ac(x) = 1- A(x) Định nghĩa nằm trong của tập mờ: Cho A, B là hai tập mờ trên không gian nền X có các hàm thuộc A,, B . Tập A được gọi là nằm trong B, kí hiệu AB nếu A B xX. Định nghĩa hai tập mờ bằng nhau: Cho A, B là hai tập mờ trên không gian nền X có các hàm thuộc A,, B . Tập A được gọi là bằng tập B, kí hiệu A=B nếu A= B xX. Tập mức: Cho [0,1], A là một tập mờ trên không gian nền X có hàm thuộc A. Tập hợp A thoả mãn A = {x| A (x)} được gọi là tập mức của tập mờ A. Số mờ: Tập mờ trên đường thẳng số thực R1 là một số mờ nếu thoả mãn: M chuẩn hoá, tức là có điểm x’ sao cho M(x’) = 1 ứng với mỗi , tập mức {x| M(x)} Trong hệ mờ có 3 dạng số mờ chính đó là: + Số mờ hình tam giác: M(x) x m1 m2 m3 + Số mờ dạng hình thang: M(x) x m1 m2 m3 m4 + Số mờ dạng hàm Gauss: M(x) x 1.4 Logic mờ (Fuzzy Logic): Trong các lý thuyết toán học việc chứng minh một mệnh đề, một định lý toán học thực chất đều dựa trên việc suy luận toán học từ các mệnh đề cơ sở hoặc các tiên đề. Để có được các suy luân toán học đó thì logic đóng một vai trò chủ chốt và là công cụ chính để tạo nên các suy luận toán học. * Nhắc lại logic cổ điển: Ta kí hiệu P tập các mệnh đề và P1, P2, P3 ,Q1, Q2… là các mệnh đề. Với mỗi mệnh đề PiP, ta gán một giá trị v(P) của mệnh đề. Logic cổ điển đề nghị v(P)=1 nếu P là đúng, v(P) = 0 nếu P là sai. Các phép toán cơ bản của logic cổ điển gồm: Phép tuyển: P OR Q, kí hiệu PQ, đó là mệnh đề “hoặc P hoặc Q” Phép hội: P AND Q, kí hiệu PQ, đó là mệnh đề “ vừa P vừa Q” Phép phủ định : NOT P, kí hiệu P, đó là mệnh đề “không P” Dựa trên các phép toán logic cơ bản này người ta đã định nghĩa ra các phép toán quan trọng khác đặc biệt là phép kéo theo (implication), kí hiệu PQ hay thường được thể hiện dưới dạng luật rất quen thuộc đối với máy tính là mệnh đề “IF P1 THEN Q1 ”. Dưới đây là bảng chân lý của các phép toán logic cơ bản: (giá trị chân lý của phép kéo theo và phép tương đương phụ thuộc vào giá trị của các mệnh đề gốc ban đầu P, Q) P Q 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 0 1 1 Sử dụng những định nghĩa trên, trong logic cổ diển đã xuất hiện rất nhiều các luật suy diễn rất quan trọng sau: - Modus pones: (P(PQ))Q - Modus tollens: ((PQ)Q)P - Syllogism: ((PQ)(QR))(PR) - Contraposition: (PQ)(QP) 1.5 Các công cụ cơ bản của logic mờ: Năm 1973 L.Zadeh đã đưa vào khái niệm “biến ngôn ngữ” và bước đầu ứng dụng vào trong suy diễn mờ. Đây là bước khởi đầu rất quan trọng trong việc tính toán các suy diễn chủ chốt trong hệ mờ. L.Zadeh đề nghị suy rộng các phép toán logic cơ bản với các mệnh đề v(P) thay vi chỉ nhận giá trị 0, 1 bây giờ giá trị v(P) nằm trong đoạn [0,1]. Từ tiên đề này ta có được các phép toán logic cơ bản sau trong tập mờ: Phép phủ định: Phủ định (negation) là một trong những phép toán logic cơ bản. Để suy rộng ta cần tới toán tử v(NOT P) xác định giá trị chân lý của NOT P đối với mỗi mệnh đề P. Định nghĩa 1.1: Hàm n: [0,1 [0,1] không tăng thoả mãn các điều kiện n(0)=1, n(1)=0 gọi là hàm phủ định (Negation – phép phủ định). Định nghĩa 1.2: Hàm n là phép phủ định chặt (Strict) nếu nó là hàm liên tục và giảm chặt Hàm phủ định là mạnh (Strong) nếu nó là chặt và thoả mãn n(n(x))=x, với " x ẻ [0,1]. Ví dụ: Một số hàm phủ định cụ thể - Hàm phủ định chuẩn (do Zadeh định nghĩa): n(x) = 1 - x - Hàm phủ định : n(x)= 1- x2 - Hàm phủ định (Sugeno, 1977): với > -1 - Phủ định trực cảm (Yager, 1980): n(x) = 1 nếu x=0 và n(x) = 0, nếu x>0 Phép hội: Phép hội (vẫn quen gọi là phép AND - conjunction) cũng là một trong những phép toán logic cơ bản. Nó chính là cơ sở để dịnh nghĩa phép giao của hai tập mờ Định nghĩa 1.3: Hàm T: [0,1] x[0,1][0,1] là một t-chuẩn (chuẩn tam giác hay t-norm) nếu thoả mãn các điều kiện sau: T(1,x) = x với mọi 01. T có tính giao hoán, tức là T(x,y) = T(y,x) với mọi 01. T không giảm theo nghĩa T(x,y)T(u,v) với mọi x. T có tính kết hợp: T(x,T(y,z))=T(T(x,y),z) với mọi 01. Ví dụ: Về một số hàm t-chuẩn - Min (Zadeh 1965) T(x,y) = min(x,y) - Dạng tích T(x,y) = xy - t-chuẩn Lukasiewicz T(x,y) = max{ x+y-1, 0 } - Min nilpotent (Fodor 1993) TN(x,y) = - t-chuẩn yếu nhất (drastic product) Z(x,y)= * Nhận xét: Ta thấy rằng với mỗi t- chuẩn thì Z(x,y)T(x,y) min(x,y) với mọi 01 Phép tuyển: Phép tuyển hay toán tử logic OR (disjunction) thông thường thoả mãn các tiên đề sau: Định nghĩa 1.4: Hàm S : [0,1x[0,1][0,1] gọi là phép tuyển (OR suy rộng) hay là t-đối chuẩn (t-conorm) nếu thoả mãn các tiên đề sau: S(0,x) = x với mọi x[0,1] S có tính giao hoán: S(x,y) = S(y,x) với mọi 01 S không giảm: S(x,y)S(u,v) với mọi 01 và 01 S có tính kết hợp: S(x, S(y,z)) = S(S(x,y), z) với mọi 01 Ví dụ: Một số hàm t-đối chuẩn. Chọn phép phủ định n(x)=1-x chúng ta có các quan hệ giữa T và S như sau: T(x,y) S(x,y) min(x,y) max(x,y) Xy x +y – xy Max{ x+y-1, 0 } min{x+y, 1} Bộ ba De Morgan: Xuất phát từ luật De Morgan nổi tiếng trong lý thuyết tập hợp như sau: Cho A, B là hai tập con của X khi đó: (AB)C = AC B C (AB) C = ACBC Suy rộng ra cho logic mờ ta có một dạng luật De Morgan như sau: Định nghia 1.5: Cho T là t-chuẩn, S là t-đối chuẩn, n là phép phủ định chặt. Chúng ta nói bộ ba (T,S,n) là một bộ ba De Morgan nếu: n(S(x,y)) = T(nx, ny) Phép kéo theo: Phép kéo theo (implication) là một công đoạn quan trọng, chủ chốt của quá trình suy diễn mờ, do đó có rất nhiều nghiên cứu về phép kéo theo. Để tính toán được, chúng ta cần những dạng cụ thể của phép kéo theo nhưng tất cả các phép kéo theo đều được xây dung từ định nghĩa cơ bản sau: Định nghĩa 1.6: Phép kéo theo là một hàm số I :[0,1]x[0,1][0,1] thoả mãn các điều kiện sau: Nếu xz thì I(x,y) I(z,y) với mọi y[0,1] Nếu yu thì I(x,y) I(x,u) với mọi x[0,1] I(0,x) = 1 với mọi x[0,1] I(x,1) = 1 với mọi x[0,1] I(1,0) = 0. Ngoài ra trong bài báo của Dubois và Prade phép kéo theo còn có một số tính chất sau: I6- I(1,x) = x, với "xẻ[0,1]. I7- I(x,I(y,z)) = I(y,I(x,z)). I8- x y nếu và chỉ nếu I(x,y) =1 (phép kéo theo xác lập một thứ tự ) I9- I(x,0) = n(x) ( n - là một phép phủ định mạnh) I10- I(x,y) ³ y với "x, y. I(x,x) = 1, với "x. I(x,y) = I(n(y), n(x)) ( n - là một phép phủ định mạnh). I(x,y), là hàm liên tục trên [0,1]. Một số dạng của phép kéo theo cụ thể: Cho T là t-chuẩn, S là t-đối chuẩn, n là phép phủ định mạnh Định nghĩa 1.6.1: Dạng kéo theo thứ nhất. Hàm IS1(x,y) xác định trên [0,1]x[0,1] bằng biểu thức IS1(x,y) = S(n(x),y). Định lý 1.6.2: Với bất kỳ t-chuẩn T, t-đối chuẩn S và phép phủ định mạnh n nào, IS được định nghĩa như trên là một phép kéo theo. Định nghĩa 1.6.3: Dạng kéo theo thứ hai. Cho T là một t-chuẩn, hàm IT(x,y) xác định trên [0,1]x[0,1] bằng biểu thức: IT(x,y) = sup{u: T(x,u) Ê y }. Định lý 1.6.4: Với bất kỳ t-chuẩn T nào, IT được định nghĩa như trên là một phép kéo theo. Định nghĩa 1.6.5: Dạng kéo theo thứ ba. Cho (T, S, n) là bộ ba De Morgan với n là phép phủ định mạnh, phép kéo theo thứ ba IQL(x,y) (QL – Implication – Từ Logic lượng tử - Quantum Logic) xác định trên [0,1]2 bằng biểu thức: IQL(x,y) = S(T(x,y), n(x)). Ví dụ: Một số dạng của phép kéo theo thứ ba phụ thuộc vào việc chọn bộ ba De Morgan: a) Chọn n(x) = 1-x; T(x,y) = min(x,y) thì IS(x,y) = max{min(x,y),1-x} b) Chọn n(x) = 1-x, T(x,y) = max{0, x+y-1} thì IS(x,y) = max(1-x,y) Suy diễn xấp xỉ và suy diễn mờ 2.1 Suy diễn mờ: Suy diễn xấp xỉ thường được trình bày dưới dạng những mệnh đề với các biến ngôn ngữ hay sử dụng trong đời thường vẫn dùng như: “cỡ trung niên”, “ga yếu”, “hơi lạnh” hay còn được thể hiện dưới dạng quy tắc, những luật dạng mệnh đề “nếu góc tay quay lớn thì tốc độ xe sẽ nhanh”. Suy luận xấp xỉ hay còn gọi là suy luận mờ là quy trình suy ra những kết luận dưới dạng các mệnh đề mờ trong điều kiện các quy tắc, các luật, các dữ liệu đầu vào cho trước cũng không hoàn toàn xác định. Trước tiên ta nhớ lại trong giải tích toán học đã dùng quá trình lập luận sau: Định lý: Nếu một hàm số khả vi thì nó liên tục Sự kiện: Hàm f khả vi Kết luận: f liên tục Đây là dạng suy luận dựa vào luật modus ponens. Bây giờ ta tìm cách diễn đạt cách suy luận quen thuộc trên dưới dạng sao cho có thể suy rộng cho logic mờ. Ký hiệu : U= không gian nền = không gian tất cả các hàm số. Ví dụ đơn giản có thể hiểu U= { g: R đ R}. A ={các hàm khả vi}, B = { các hàm liên tục }. Hãy chọn hai mệnh đề P = "g ẻ A" và Q = " g ẻ B ". Khi ấy chúng ta có Luật (tri thức) gB Sự kiện: P đúng (true) Kết luận: Q đúng (true) ở đây chúng ta đã sử dụng luật modus ponens (( P ị Q) Ù P) ị Q. Bây giờ đã có thể chuyển sang suy diễn mờ cùng dạng: Luật mờ Nếu góc tay quay ga lớn thì xe sẽ đi nhanh Sự kiện mờ: Góc tay quay ga khá lớn Kết luận: Xe đi khá nhanh Zadeh đã diễn đạt sự kiện trên bằng các biến ngôn ngữ : góc tay quay, tốc độ, nhiệt độ, áp lực, tuổi tác và các mệnh đề mờ dạng tương ứng. 2.2 Biến ngôn ngữ: Biến ngôn ngữ là một khái niệm rất quan trọng trong logic mờ và suy luận xấp xỉ, nó đóng vai trò quyết định trong rất nhiều ứng dụng, đặc biệt là trong lĩnh vực xây dựng các hệ chuyên gia mờ và lấy quyết định hội đồng. Về cơ bản, biến ngôn ngữ là có các giá trị là những từ hay những câu trong ngôn ngữ tự nhiên hoặc nhân tạo. * Ví dụ 1. Ta nói "Nam có tuổi trung niên ", khi ấy chọn: x = biến ngôn ngữ " Tuổi ", không gian nền là thời gian sống U = [0, 130 năm ]. A= tập mờ " trung niên ". Một cách tự nhiên, ta gán cho A là một tập mờ trên U với hàm thuộc A(u) : Uđ [0,1]. Sự kiện "có thể tuổi của Nam là 40" dĩ nhiên không chắc chắn và khá hợp lý nếu diễn đạt như một khả năng, Zadeh đề nghị Khả năng( Tuổi của Nam=40 )= Poss( x= 40 )= độ thuộc của số 40 vào tâp mờ A= A(40). Mệnh đề mờ "Nam có tuổi trung niên" bây giờ được diễn đạt thành mệnh đề P = { x = A } = { biến x nhận giá trị mờ A trên không gian nền U }   = { x is A } ( theo dạng tiếng Anh ). * Ví dụ 2: Đối với suy luận mờ cho ở đầu mục này chúng ta có thể dùng biến ngôn ngữ x= "góc tay quay" trên không gian nền U= [ 0. 360 0] (cho phép quay tay ga của xe máy), A = ''góc lớn" là một tập mờ trên U (trong trường hợp này tiện hơn dùng khái niệm số mờ A ), với hàm thuộc A(u) : U đ[0,1]. Tương tự, biến ngôn ngữ y = "tốc độ xe", với không gian nền V = [0 km/giờ, 150 km/giờ], Q = ''xe đi nhanh" = một tập mờ B trên không gian nền V với hàm thuộc B(v) : V đ [0,1]. Khi ấy P = " góc tay quay lớn " = { x = A } ( x is A ), Q = " xe đi nhanh " = { y = B }, và luật mờ có dạng P ị Q. Như vậy một luật mờ dạng '' If P then Q" sẽ được biểu diễn thành một quan hệ mờ R của phép kéo theo P ị Q với hàm thuộc của R trên không gian nền U x V được cho bởi phép kéo theo mà bạn dự định sử dụng : R(A,B)(u,v) = R PịQ(u,v) = I(A(u), B(v)) , với mọi (u,v) ẻ U xV. Bây giờ quy trình suy diễn mờ đã có thể xác định : Luật mờ tri thức P ị Q, với quan hệ cho bởi I(A(u), B(v)) Sự kiện mờ P' = { x = A' }, xác định bởi tập mờ A' trên U Kết luận Q' = { y = B' } Sau khi đã chọn phép kéo theo I xác định quan hệ mờ R(A,B), B' là một tập mờ trên V với hàm thuộc của B' được tính bằng phép hợp thành B' = A'° R(A,B), cho bởi công thức B'(v) = max u ẻU{ min ( A'(u), I( A(u), B(v) ))}. với mỗi v ẻ V. * Tiếp tục cách biểu diễn và diễn đạt như vậy, ta có thể xét dạng " If P then Q else Q1 " quen biết trong logic cổ điển và thường hay sử dụng trong các ngôn ngữ lập trình của ngành Tin học. Có thể chọn những cách khác nhau diễn đạt mệnh đề này ,sau đấy tìm hàm thuộc của biểu thức tương ứng. Chẳng hạn, chúng ta chọn " If P then Q else Q1 " = ( P ÙQ ) Ú ( ự P ÙQ1). Thông thường Q và Q1 là những mệnh đề trong cùng một không gian nền. Giả thiết, Q và Q1 được biểu diễn bằng các tập mờ B và B1 trên cùng không gian nền V, với các hàm thuộc tương ứng B : Vđ[0,1] và B1: Vđ [0,1]. Nếu Q và Q1 không cùng không gian nền thì cũng sẽ xử lý tương tự nhưng với công thức phức tạp hơn. Kí hiệu R(P,Q,Q') = R(A,B, B1) là quan hệ mờ trên U x V với hàm thuộc cho bởi biểu thức R(u,v) = max{min(A(u), B(v)), min(1-A(u), B1(v))}, với mọi (u,v) ẻUxV. Tiếp tục quy trình này chúng ta có thể xét những quy tắc lấy quyết định phức tạp hơn. Chẳng hạn chúng ta xét một quy tắc trong hệ thống mờ có 2 biến đầu vào và một đầu ra dạng If A1 and B1 then C1 else If A2 and B2 then C2 else ........ * Một dạng suy rộng khác trong bài toán điều khiển mờ có thể phát biểu dưới dạng sau: Cho x1,x2,...,xm là các biến vào của hệ thống, y là biến ra . Các tập Aij , Bj, với i = 1,....,m , j = 1,....,n là các tập mờ trong các không gian nền tương ứng của các biến vào và biến ra đang sử dụng của hệ thống , các Rj là các suy diễn mờ (các luật mờ) dạng "Nếu ... thì '' (dạng if .... then ) R1 : Nếu x1 là A1,1 và ... và xm là Am,1 thì y là B1 R2 : Nếu x1 là A1,2 và ... và xm là Am,2 thì y là B2 ...... Rn : Nếu x1 là A1,n và ... và xm là Am,n thì y là Bn Cho : Nếu x1 là e1* và ... và xm là em* -------------------------------------------------------------------------- Tính : y là u*, ở đây e1*, ...., em* là các giá trị đầu vào hay sự kiện ( có thể mờ hoặc giá trị rõ ),. 2.3 Mô hình mờ: Mô hình mờ và phương pháp lập luận mờ được Zadeh đề xuất. Sau đó một số tác giả như Kizska, Cao-Kandel đã phát triển tiếp ý tưởng của Zadeh và đề xuất một số phương pháp lập luận mờ mới. Chúng ta xét lựơc đồ lập luận mờ đa điều kiện, mô hình mờ có chứa nhiều mệnh đề điều kiện dạng Nếu … thì: Mệnh đề 1 Nếu X1= A11 và .. và Xn = A1n thì Y = B1 Mệnh đề 2 Nếu X1= A21 và .. và Xn = A2n thì Y = B2 …. Mệnh đề m Nếu X1= Am1 và .. và Xn = Amn thì Y = Bm Kết luận Y=B0 Tập hợp mệnh đề đầu tiên trong (M) được gọi là mô hình Mờ, trong đó Ai, Bi là các khái niệm Mờ. Mô hình này mô tả mối quan hệ (hay sự phụ thuộc) giữa hai đại lượng X và Y. Giá trị X = A0 được gọi là input còn Y=B0 được gọi là output của mô hình. Phương pháp lập luận xấp xỉ tính Y=B0 gồm các bước sau; 1) Bước 1: Giải nghĩa các mệnh đề điều kiện: Chúng ta xem các khái niệm mờ Ai, Bi là nhãn của các tập mờ biểu thị ngữ nghĩa của Ai, Bi. để tiện cho hàm thuộc chúng đươc ký hiệu tương ứng là Ai(u) và Bi(u) trên các không gian tham chiếu U và V Một cách trực cảm, mỗi mệnh đề Nếu … thì trong mô hình Mờ có thể hiểu là một phép kéo theo (implication oprator) trong một hệ logic nào đó và được viết Ai(u) ị Bi(u). Khi u và v biến thiên, biểu thức này xác định một quan hệ Mờ Ri: UxV đ [0,1]. Như vậy mỗi mệnh đề điều kiện trong (M) xác định một quan hệ Mờ. 2) Bước 2: Kết nhập (aggregation) các quan hệ mờ thu được bằng công thức: R = @ni=1Ri, trong đó @ là một phép tính t-norm hay t-conorm nào đó. Chẳng hạn R = Ùni=1Ri hay Ú ni=1Ri trong đó Ù, Ú là các phép tính min và max. Việc kết nhập như vậy đảm bảo R chứa thông tin được cho bởi các mệnh đề if … then có trong mô hình Mờ. 3) Bước 3: Tính output B0 theo công thức B0 = A0oR, trong đó o là phép hợp thành giữa hai quan hệ Ao và R 4) Bước 4: Khử Mờ (Defuzzification). Giá trị đầu ra B0 ở bước 3 là một tập mờ. Trong các bài toán thực tế và đặc biệt là trong các bài toán điều khiển người ta cần tính giá trị thực (rõ). Do đó người ta cần có 1 phương pháp để tính tương ứng giữa tập mờ B0 với một giá trị thực nào đó. Quá trình tính tương ứng đó người ta gọi là giải mờ. Có nhiều phương pháp giải mờ khác nhau mà tuỳ thuộc vào bài toán thực tế mà người ta chọn các phương pháp giải mờ khác nhau: Phương pháp lấy trọng tâm: Đây là phương pháp được sử dụng rộng rãi nhất trong điều khiển mờ. Cách khử mờ như sau: y0 = với S = supp(y) = {y| (y)0 } là miền xác định của tập mờ R. * Chú ý: Nếu đặt Mi = ; Ai = i=1..n. Xét riêng với số mờ hình thang ta có được: Mk =(3m - 3m + b2- a2 + 3m2b + 3m1a); Ak = (2m2 – 2m1 + a + b); ( Chứng minh xem [1 trang 119] ) Tuy nhiên nhược điểm cơ bản của phương pháp này là có thể cho giá trị y0 có độ thuộc nhỏ nhất hoặc có giá trị bằng 0. Minh họa như hình vẽ sau: Phương pháp lấy cực đại: Tư tưởng chính của phương pháp là tìm trong tập mờ có hàm thuộc (y) một phần tử rõ y0 với độ phụ thuộc lớn nhất tức là: y0 = arg maxy(y) Nhược điểm của phương pháp này là có thể đưa đến vô số nghiệm do đó ta phải xác định được miền chứa giá trị rõ y0. Giá trị rõ y0 là giá trị mà ở đó hàm thuộc đạt giá trị cực đại (bằng độ thoả mãn đầu vào H) tức là miền: G = { yY | R(y) = H} Phương pháp lấy trung bình các điểm cực đại y0 = i=1,2,…n Phương pháp lấy điểm giữa của các điểm cực đại: y0 = 2.4 Một số phương pháp suy diễn: Phương pháp suy diễn tổng quát: 1. Với mỗi luật Ri tìm mức đốt (kích hoạt) li 2. Với mỗi luật Ri sử dụng mức đốt li và tập hệ quả Bi, tìm đầu ra thực B’i 3. Gộp các đầu ra riêng rẽ của các luật để tính đầu ra gộp của toàn hệ B 4. Giải mờ, tìm kết quả ra của toàn hệ y* Để tiện cho cài đặt thuật toán suy diễn cụ thể, ta xét trường hợp sau: ứng với luật mờ Ri, xét các giá trị mờ Aij, j = 1,2,…, n là những tập mờ trên tập biến ngôn ngữ Xi. Phương pháp suy diễn Max-Min ( Phương pháp Mamdani) Tín hiệu đầu vào là vectơ x* = (x1*, x2*, .., xn*) 1. Với mỗi luật Ri, tính li = min (Aij(xj*): j = 1,2,…, n) 2. Xác định Bi’(y) = min (li , Bi’(y)), với mỗi yẻV 3. Xác định B’(y) = max(Bi’(y): i = 1,2,…m) 4. Giải mờ tập B’, thu được kết quả y* là một số rõ Phương pháp suy diễn Max-prod (Phương pháp Larsen) Tín hiệu đầu vào là vectơ x* = (x1*, x2*, .., xn*) 1. Với mỗi luật Ri, tính li = Pj (Aij(xj*): j = 1,2,…, n) 2. Xác định Bi’(y) = min (li, Bi’(y)), với mỗi yẻV 3. Xác định B’(y) = max(Bi’(y): i = 1,2,…m) 4. Giải mờ tập B’, thu được kết quả y* là một số rõ 2.5 Ví dụ tổng hợp: Xét bài toán điều khiển mờ sau( hình vẽ). Yêu cầu của đầu bài là không phụ thuộc vào lượng nước chảy ra khỏi bình ta phải chỉnh van nước chảy vào bình vừa đủ để mực nước trong bình là h luôn không đổi. Ta có thể dựa vào kinh nghiệm để nói rằng van sẽ điều chỉnh theo nguyên tắc sau: a) Nếu mực nước là thấp nhiều thì van ở mức độ mở to. b) Nếu mực nước là thấp ít thì van ở mức độ mở nhỏ c) Nếu mực nước là cao thì van ở vị trí đóng. d) Nếu mực nước là đủ thì van ở vị trí đóng. - Bíên ngôn ngữ mực nước có bốn giá trị: thấp nhiều, thấp ít, đủ, cao. - Biến van có ba giá trị: to, nhỏ, đóng. Tương ứng với 4 giá trị của biến mực nước ta có 4 tập mờ: + Tập mờ thấp nhiều(x) cho giá trị thấp nhiều. + Tập mờ thấp ít(x) cho giá trị thấp ít + Tập mờ đủ(x) cho giá trị đủ + Tập mờ cao(x) cho giá trị cao Giả sử mực nước x = 2m thì lúc đó thấp nhiều(x) = 0; cao(x) = 0 thấp ít(x) = 0.4; đủ (x) = 0.7 Tương tự ta có 3 tập mờ tương ứng với ba giá trị đầu ra đóng(x), nhỏ (x), to(x) Với 4 quy tắc điều chỉnh ta có được các phép suy diễn: R1: Nếu mực nước = thấp nhiều thì van = to R2: Nếu mực nước = thấp ít thì van = nhỏ R1: Nếu mực nước = cao thì van = đóng R1: Nếu mực nước = đủ thì van = đóng Chọn phép hợp thành max- min ta có các bước như sau: R1(y) = thấp nhiềuto(y) = min{ thấp nhiều (2), to(y) } = 0 R2(y) = thấp ítnhỏ (y) = min{ thấp ít (2), nhỏ(y) } = min{0.4, nhỏ(y)} R3(y) = caođóng (y) = min{ cao(2), đóng(y) } = 0 R4(y) = đủđóng (y) = min{ đủ(2), đóng(y) } = min{0.7, đóng(y)} Xác định tập mờ chung cho cả 4 tập mờ trên để có được kết quả R(y) tương ứng với mực nước đầu vào là 2m. Chọn phép hợp là max ta có: R(y) = max{0, R2(y), 0, R4(y)} = max{ R2(y), R4(y) } Xác định giá trị đầu ra y0 (giải mờ): áp dụng giải mờ bằng phương pháp trọng tâm đối với số mờ hình thang ta có: + Với hình thang R4(y): M4=(3*(8.9)2-3*(3.5)2+(11-8.9)2-(3.5-2.3)2+3*8.9*(11-8.9)+3*3.5*(3.5-2.3))=31.794 A4=(2*8.9 – 2*3.5 + (3.5 – 2.3) + (11 – 8.9)) = 4.935 Với hình thang R2(y): M2=(3*(15.5)2-3*(10)2+(16.8-15.5)2-(10-8.2)2+3*15.5*(16.815.5)+3*10*(10-8.2)) = 35.577 A2 = (2*15.5 – 2*10 – (10 - 8.2) + (16.8 – 15.3)) = 2.82 Giá trị đầu ra: y0 = = = 8.688 các toán tử gộp (aggregation operator) Các họ toán tử gộp là cầu nối trung gian giữa phép toán logic phép tuyển – OR và phép hội – AND. Trong thực tế ứng dụng nhiều bài toán sẽ cho kết quả không tốt nếu chỉ sử dụng hai phép toán logic trên. Các họ toán tử gộp được nghiên cứu và phát triển rất nhiều và tuỳ thuộc vào từng bài toán mà người ta sẽ sử dụng các loại toán tử gộp đặc trưng riêng. Sau đây là hai loại toán tử gộp chính để phục vụ cho việc xây dựng quy trình phân loại và sắp xếp các phương án: 3.1 Toán tử OWA (Ordered Weighted Averaging Operator) Định nghĩa: Cho vectơ trọng số w = [w1, w2, …., wn]T, các trọng số wi thoả 0 wi 1, với mỗi i = 1, 2, …, n và thoả điều kiện = 1 Cho vectơ a = (a1, a2, …., an) Rn. Toán tử OWA là một ánh xạ F: RnR, xác định bởi: F(a) = trong đó bj là phần tử lớn thứ j của vectơ a Ví dụ: w = [0.4, 0.3, 0.2, 0.1]T, a = ( 0.7, 1, 0.3, 0.6) vectơ b sẽ là b = (1, 0.7, 0.6, 0.3) vậy F(a) = 0.4(1) + 0.3(0.7) + 0.2(0.6) + 0.1(0.3) =0.76 * Một số trường hợp đặc biệt: 1) F*: trong trường hợp w =w* = [1, 0, ….., 0]T thì F*(a1, a2,…, an) = maxi(ai) 2) F*: trong trường hợp w =w* = [0, 0, ….., 1]T thì F*(a1, a2,…, an) = mini(ai) 3) FAve : khi w = w Ave = [1/n, …., 1/n]T thì FAve(a1, a2,…, an) = Một số độ đo gắn với toán tử OWA: 1) Độ phân tán hay entropy (dispersion or entropy): Độ phân tán hay entropy của vector w được xác định bởi Disp(w) = -ồi wi ln wi. Độ phân tán thể hiện mức độ tích hợp đều nhau, khi toán tử OWA trùng với toán tử Min(F*) hay Max(F*) thì Disp(w)=0 2) Độ đo tính tuyển (orness): Độ đo orness được định nghĩa: orness(w) = Orness(W*) = 1, Orness(W*) = 0, Orness(WAve) = 0.5 Độ đo orness thể hiện xu hướng của toán tử OWA, nếu độ đo này lớn hơn 0.5 thì có nghĩa là trọng số tập trung chủ yếu vào các giá trị lớn. 3) Độ đo tính hội (andness): Độ đo tính hội được định nghĩa: Andness(W)=1-Orness(W) Độ đo Andness cũng thể hiện xu hướng của toán tử OWA, nhưng ngược với độ đo Orness. Độ đo này càng lớn thì trọng số tập trung chủ yếu vào các giá trị nhỏ. 3.2 Tập nhãn ngôn ngữ: Toán tử OWA đã tỏ ra có hiệu quả khi tích hợp các ý kiến của chuyên gia dưới dạng số. Tuy nhiên trong nhiều trường hợp, một chuyên gia không thể đưa ra mức độ ưa thích hơn của mình một cách chính xác bằng một giá trị số. Khi đó một khả năng khác là sử dụng tập nhãn ngôn ngữ để đưa ra độ ưa thích của mình về khả năng lựa chọn thông qua một quan hệ thích hơn ngôn ngữ. Định nghĩa: Tập nhãn ngôn ngữ là một tập các nhãn ngôn ngữ xác định và có một giá trị ngữ nghĩa xác định trong một hoàn cảnh nào đó theo một hàm thuộc định nghĩa trước. Tập nhãn có thứ tự là tập gồm các phần tử sánh được với nhau. Tập nhãn trong bài toán ra quyết định đa mục tiêu là tập gồm các nhãn để nói lên các ý kiến đánh giá của chuyên gia hay nói cách khác chúng chính là các đánh giá ngôn ngữ. Do vậy tập nhãn dùng trong bài toán phải là tập nhãn sánh được. Các nghiên cứu trước đây khuyên rằng nên sử dụng tập nhãn ngôn ngữ với lực lượng lẻ, nhãn trung tâm thể hiện khả năng xấp xỉ 0.5, các nhãn còn lại được đặt đối xứng qua nhãn trung tâm và giới hạn số phần tử trong tập hợp thường nhỏ hơn 11. Ngữ nghĩa của các nhãn được đặc trưng bởi các giá trị mờ trong khoảng [0,1], và được biểu diễn bằng các hàm thuộc. Hay nói cách khác, mỗi nhãn biểu diễn một giá trị có thể cho một biến thực ngôn ngữ, tức là thuộc tính mờ trên [0,1]. Nói chung ta thấy khó có thể xảy ra trường hợp tất cả các chuyên gia sẽ đồng ý trên cùng một hàm thuộc gán cho các biến ngôn ngữ, và vì vậy chúng ta không có bất kỳ hàm thuộc nào chuẩn nào cho các nhãn. Với cùng một nhãn, chúng ta có thể định nghĩa hai hàm thuộc khác nhau tuỳ theo quan niệm của mỗi chuyên gia, chẳng hạn ta có hai cặp nhãn giống nhau nhưng hàm phân phối khác nhau ví dụ như hình vẽ dưới: Một số tính chất của tập nhãn: Chúng ta xét tập nhãn có thứ tự hoàn toàn và xác định S={Si}, iẻH; H={1,..,T}, thường có số phần tử lẻ như 7 hay 9, với mỗi nhãn Si, biểu diễn một giá trị có thể cho một biến thực ngôn ngữ, nhận một giá trị trên [0,1], khi đó tập nhãn sẽ phải đảm bảo một số tính chất như sau: Tập S là một tập có thứ tự Si ³Sj nếu i ³ j Tồn tại một toán tử đảo: Neg(si)=sj trong đó j=(T+1)-i Toán tử max: max(si, sj)=si nếu si ³ sj Toán tử min: min(si, sj)= si nếu sj ³ si Thông thường, chúng ta giả sử R thoả mãn một số tính chất sau: Tính đối xứng mềm Rkii =s(T+1)/2 với mọi xi ẻ X Nếu rij ³ s(T+1)/2 thì s(T+1)/2 ³ rji Tính chất đầu là một sự ngầm định giữa các chuyên gia, nếu xi được sánh với chính nó thì chọn nhãn s(T+1)/2. Tính chất sau được xem là tất nhiên và hợp lý nếu xi được đánh giá là ưa thích hơn dương so với xj, thì ngược lại xj được đánh giá là ưa thích hơn âm đối với xi ( nếu ta giả sử S(T+1)/2 là điểm gốc so sánh). 3.3 Toán tử LOWA(Linguistic Ordered Weighted Averaging Operator) Từ toán tử OWA nhóm nghiên cứu của F.Herrera đã định nghĩa một lớp toán tử LOWA trực tiếp suy rộng toán tử OWA của R.Yager và áp dụng vào bài toán lấy quyết định tập thể. Trên nền gợi ý của nhóm nghiên cứu F.Herrera, từ năm 1998 GS-TSKH Bùi Công Cường đã sử dụng công thức tính sau: [2] [3] Định nghĩa: Cho S={s1, s2,..,sT} là tập nhãn, sắp toàn phần s1 im-1> ...>i1. Cho w={w1, w2, ..., wn} là vector trọng số, wiẻ[0,1] và ồi wi=1. Toán tử LOWA là một tổ hợp thực của của vector a với trọng số w, Low:(a,w) S cho bởi công thức truy toán sau: Low (a,w) = C{ (wim, aim), (1-wim,Low(a’,w’) } ở đây a’={ai(m-1),...,ai1}, w’=[w’i1, w’i2, ...,w’i(m-1)], w’=wj/(1-wim), C là phép tổ hợp của 2 nhãn (si,sj), j>=i với trọng số wi>0, wi>0, wi+wj=1, C{(wj, sj),(wi, si)}=sk, với k=i+round(wj, (j-i)) trong đó round là phép làm tròn số. Ví dụ: Cho a=(s1, s2, s3). Cho w=(0.2,0.3,0.5). Khi đó b=(s3, s2, s1) w3=0.5, w2=0.3, w1=0.2 và Low(a,w)=C{(0.5,s3), (0.5, Low((s2, s1),(0.2/0.5,0.3/0.5))} song Low((s2, s1), (0.2/0.5,0.3/0.5))=C{(3/5, s3), (2/5, s2)}=sk1 k1=1+round((3/5)(2-1)=1+1=2 Do vậy Low(a,w)=C{(0.5,s3),(0.5, s2)}=sk, k= 2+round(0.5.(3-2))=3 chương ii Bài toán lấy quyết định và các quy ._.