Đồ án 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

) 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 trình, phương pháp lấy quyết định giới thiệu về bài toán Trong mọi hoạt động thực tế của xã hội, con người luôn luôn phải đưa ra những quyết định của mình trong nhiều vấn đề khác nhau. Từ việc đơn giản như mua bán hàng hoá hàng ngày, khi mua một mặt hàng ta luôn phải dựa trên những chỉ tiêu khác nhau như: giá cả, chất lượng, nhãn hiệu,.. Hay khi ta mua mặt hàng mà không thuộc trong lĩnh vực chuyên môn của mình ta phải dựa vào ý kiến của những người có chuyên môn trong lĩnh vực đó, nhờ họ tư vấn rồi sau đó mới đưa ra quyết định có nên mua hay không mua mặt hàng đó. . Chúng ta có thể hiểu và thấy tầm quan trọng của quá trình ra quyết định nói chung và ra quyết định trên nhiều mục tiêu nói riêng. Để có một quyết định chính xác và hiệu quả đòi hỏi người ra quyết định phải có một tầm hiểu biết, một cách nhìn nhận, một vốn kiến thức khá sâu sắc và khả năng tổng hợp tri thức một cách tuyệt vời. Thông thường khi đánh giá xem xét một phương án nào đó người ta thường quan tâm đầu tiên đến các giá trị mang tính định lượng. Ví dụ như trong các cuộc thi đấu thể thao nghệ thuật để tìm ra thí sinh giỏi nhất người ta thường đánh giá cho điểm trên các chỉ tiêu biểu diễn khác nhau rồi sau đó tích hợp lại để tìm ra thí sinh có điểm số cao nhất đó là thí sinh giỏi nhất trong số tất cả các thí sinh. Bên cạnh những chỉ tiêu định lượng, chẳng hạn như trong các dự án lớn người ta vẫn thường xuyên phải quan tâm đến các chỉ tiêu định tính như: Độ may rủi (Potential Risk), Tính khả thi (Feasibility), Độ tương thích (Suiability).v.v… Trên những chỉ tiêu định tính này các Hội đồng mong muốn nhận được các đánh giá bằng số của các chuyên gia. Chẳng hạn họ muốn các chuyên gia phát biểu dưới dạng: “ độ khả thi của dự án A4 là 30%” hay “ độ may rủi của dự án A1 là 25% ”. Điều này gây rất nhiều khó khăn cho chúng ta trong quá trình lấy quyết định trên các chỉ tiêu. Lấy quyết định bao gồm rất nhiều mô hình, mô hình lấy quyết định một chỉ tiêu, mô hình lấy quyết định nhiều chỉ tiêu với một người đánh giá, với nhiều người đánh giá, mô hình lấy quyết định dựa trên giá trị định lượng. mô hình lấy quyết định dựa trên giá trị định tính… Tất cả các tham số này ta có thể tổ hợp thành các bài toán ra quyết định khác nhau. Tuy nhiên do thời gian nghiên cứu có hạn nên trong đồ án này em chỉ xét mô hình bài toán quyết định nhiều chỉ tiêu dựa trên đánh giá bằng ngôn ngữ ở dạng so sánh cặp. một số phương pháp lấy quyết định 2.1 Hàm tích hợp Borda: Từ thực tế bầu cử, Borda (1733-1799) một người toán học người Pháp đã công bố hàm tích hợp của mình vào năm 1784. Phương pháp của ông là phương pháp đánh giá theo thứ tự . Với m phương án trong tập phương án A, mỗi phương án sẽ được đánh giá điểm theo thứ tự ưa thích nhất, ưa thích thứ hai,.. và ưa thích cuối cùng. Sau đó sử dụng tính tổng điểm của các phương án theo hàm Borda. Phương án nào có điểm cao nhất sẽ là phương án tối ưu. Hàm Borda được tính như sau: Ví dụ: Ta xét ví dụ trong bầu cử như sau: Có 100 cử tri đi bỏ phiếu bầu cho 3 ứng cử viên. Sau khi tổng hợp lại các phiếu bầu ta có được các đánh giá như sau: 40 cử tri cho rằng: a> b> c 15 cử tri cho rằng: b> c> a 25cử tri cho rằng: b> a> c 8 cử tri cho rằng: c> a> b 12 cử tri cho rằng: c> b> a Giả sử rằng cách cho điểm như sau: 3 điểm cho phương án đứng thứ 1, 2 điểm cho phương án đứng thứ 2, và 1 điểm cho phương án đứng thứ 3. áp dụng hàm tích hợp Borda ta có các giá trị tương ứng với các phương án a, b, c như sau: a: 2 x 40 +1x (25+8) + 0 x (15+12) =113 b: 2x (15+25) + 1 x (40+12) + 0 x 8 =132 c: 2 x (8+12) + 1 x 15 + 0 x (40+25) =55 Biểu diễn dưới dạng so sánh cặp như sau; a b c fB a - 48 65 113 b 52 - 80 132 c 35 20 - 55 Vậy thứ tự các phương án được sắp xếp lần lượt như sau: b > a > c Phương pháp tích hợp của Borda là sử dụng để tích hợp cho các đánh giá dưới dạng giá trị số. Để tích hợp thông tin đánh giá cho dưới dạng ngôn ngữ hiện nay có hai luồng nghiên cứu chính: Nghiên cứu của nhóm Tây Ban Nha, sử dụng toán tử LOWA và độ nhất trí Nghiên cứu ở Việt Nam sử dụng toán tử LOWA và nghiệm tập thể mờ FCS Do thời gian nghiên cứu có hạn nên trong đồ án này em chỉ tập trung nghiên cứu theo hướng thứ hai: Toán tử LOWA và nghiệm tập thể mờ FCS (Fuzzy Collection Solution). 2.2 Mô hình bài toán lấy quyết định dựa trên nghiệm tập thể mờ FSC: Ra quyết định đa mục tiêu là một lĩnh vực phong phú trong việc nghiên cứu lý thuyết quyết định quy chuẩn. Trong một bài toán ra quyết định, chúng ta có một tập các phương án sẽ được phân tích theo các mục tiêu khác nhau để chọn ra phương án tốt nhất. Với mỗi một mục tiêu, một tập các giá trị về các phương án sẽ được biết. Một cách tổng quát ta có thể phát biểu bài toán như sau: Cho A là tập các phương án cần lựa chọn A={A1, A2, .., An}. Cho E là tập các chuyên gia E={e1, e2, ..., ek}. Cho C là tập các mục tiêu C={c1, c2, ..., cm} mà các phương án cần đạt được. Với tập chuyên gia, chúng ta có tập vector trọng số đánh giá sự quan trọng của họ W(ek): E [0,1]. Với tập mục tiêu, chúng ta có tập vector trọng số đánh giá mức độ quan trọng của mục tiêu W(ct) C [0,1]. Cho tập các đánh giá của các chuyên gia dưới dạng ngôn ngữ và các đánh giá là dạng so sánh từng cặp phương án. Nhiệm vụ chủ yếu của bài toán là sắp xếp và tìm ra phương án tối ưu nhất. Sơ đồ của mô hình được thể hiện như sau: Nhìn trên sơ đồ ta thấy hiển nhiên rằng người chủ tịch hội đồng đóng vai trò rất quan trọng trong bài toán lấy quyết định tập thể. Chủ tịch hội đồng phải là người quyết định lấy ý kiến của chuyên gia nào, độ quan trọng của chuyên gia đó là bao nhiêu. Tương tự như vậy người chủ tịch hội đồng cũng phải quyết định độ quan trọng của từng mục tiêu tương ứng với từng bài toán lấy quyết định cụ thể. 2.3 Đánh giá của chuyên gia: Trong bài toán này chúng ta chỉ xét đánh giá của chuyên gia cho ở dạng so sánh từng cặp phương án. Do đó nếu có tập A gồm n phương án thì đánh giá của mỗi chuyên gia cho ở dạng một ma trận như sau: A1 A2 ..... An A1 e11 e12 ..... e1n A2 e21 e22 ..... e2n ..... ..... ..... ..... ..... An en1 en2 ..... enn Với mô hình của bài toán thì đánh giá của các chuyên gia đều cho ở dưới dạng bằng lời vì vậy ta cần phải tìm được một tập nhãn S nào đó để thể hiện đánh giá của chuyên gia giữa phương án Ai và A 2.4 Tập nhãn sử dụng trong bài toán: Như đã trình bày trong khái niệm về tập nhãn ngôn ngữ, trong thực tế thì việc hội đồng nhất trí chọn được một hàm thuộc phân bố cho tập nhãn là một công việc rất khó khăn. Do vậy trong đồ án này em tạm giả thiết rằng các chuyên gia cùng nhất trí chọn một hàm thuộc phân bố trên cùng một tập nhãn. Tập nhãn được sử dụng trong đồ án là tập nhãn được nghiên cứu bởi nhóm Tây Ban Nhan và được F.Herrera công bố trong tài liệu [4], tập nhãn gồm các phần tử như sau: S9 C Certain (1, 1, 1, 1) S8 EL Extremely_likely (0.93, 0.98, 0.99, 1) S7 ML Most_likely (0.72, 0.78, 0.92, 0.97) S6 MC Meaningful_Chance (0.58, 0.63, 0.80, 0.86) S5 IM It_May (0.32, 0.41, 0.58, 0.65) S4 SC Small_Chance (0.17, 0.22, 0.36, 0.42) S3 VLC Very_Slow_Chance (0.04, 0.10, 0.18, 0.23) S2 EU Extremely_Unlikely (0.00, 0.01, 0.02, 0.07) S1 I Impossible (0, 0, 0, 0) Đồ thị của các hàm liên thuộc các nhãn đánh giá được thể hiện như sau: Như vậy mỗi đánh giá của một chuyên gia sẽ có dạng pk(i,j) = sl (sl S). Nghĩa là đánh giá của chuyên gia k cho phương án Ai so với phương án Aj là sl Ví dụ: Cho tập 4 chuyên gia E = {e1, e2, e3, e4}. Tập 3 phương án là A={A1, A2, A3}. Ta có một đánh giá p3(2,3) = s9 = Certain. Nghĩa là chuyên gia 3 cho rằng phương án 2 “ hiển nhiên ” là hơn phương án 3. 2.5 Thuật toán tích hợp sử dụng toán tử LOWA và nghiệm tập thể mờ FCS: Để hiểu rõ hơn về thuật toán cho bài toán lấy quyết định nhiều chỉ tiêu, trước hết ta hãy cùng xem xét cho bài toán lấy quyết định một chỉ tiêu 2.5.1 Thuật toán cho bài toán quyết định một chỉ tiêu: Với bài toán một chỉ tiêu ta tạm coi như là tập chỉ tiêu chỉ có 1 phần tử và trọng số của phần tử đó bằng 1. Vậy trong quá trình tính toán ta không quan tâm đến trọng số của chỉ tiêu đó nữa. . Mỗi chuyên gia ek cho đánh giá dạng so sánh dự án Ai với dự án Aj bằng một phép đánh giá Pk: A x A đ S, ký hiệu là Pk(i, j). Chúng ta giả thiết rằng Pk(i, i) = s(T+1)/2. Thuật toán gồm bẩy bước như sau: Bước 1: Thu thập các quan hệ mờ { Pk } Bước 2: Dựa vào vector trọng số W={ w(1), w(2), ...,w(k)}, w(k) là trọng số của chuyên gia ek, 0Ê w(k)) Ê 1, chuẩn hoá w’(k)=w(k)/w0, ở đây w0=Skw(k) Bước 3: Tính trọng số gộp theo từng nhãn st đối với cặp phương án (Ai, Aj) đó chính là độ nhất trí chọn st trong so sánh của cả hội đồng. IC(i,j)[sT] = Sk {w’(k): Pk(Ai, Aj) = st} Bước 4: Tính độ trội tương đối của mỗi cặp phương án (Ai, Aj) (cho bằng từ) bằng toán tử LOWA E(i,j) = LOWA(S, U(i, j)) trong đó U(i, j)={u1,..., uT} với ut = IC(i, j)[st] với mỗi t Thấy rằng E(i, j) là một ma trận, đó là một quan hệ mờ cấp 2 đo độ trội tương đối theo ý kiến đã tích hợp của cả hội đồng. Bước 5: Tìm nghiệm tập thể mờ FCS ( fuzzy collective solution ) FCS = (mFCS(A1)/A1,..., mFCS(An)/An) trong đó mFCS(Ai) = LOWA(S, V(i)), V(i)=[v1, v2, ..., vT] với mỗi vt =# {j: E(i,j)=st , jại}/n-1, # biểu thị cho lực lượng Bước 6: Phân cụm. Dùng {mFCS(Ai): Ai ẻA để phân cụm tập phương án A thành các lớp Y1, Y2,..,YT sao cho YT = { Ai mFCS(Ai)=st } với mỗi st ẻS t*=max{t: Yt ạ ặ, st ẻS}. Bước 7: Cố định tập S’ và tính toán độ trội địa phương D(Ai, Yt*, S’). Lời giải của bài toán chính là DS(Yt*) trong đó S’= {s(T+1)/2 +1, ..., sT} Định nghĩa 2.2.1: Độ trội địa phương D của phương án Ai đối với phương án Aj là: D(i, j, S’)=ồt { IC(i, j)[st]: st ẻ S’} Định nghĩa 2.2.2: Độ trội địa phương D của phương án Ai trên tập A’ tương ứng xét trong S’ là tổng các độ trội D của phương án Ai đối với toàn bộ các phương án còn lại của A’ D(Ai, A’, S’) = ồj {D(i, j, S’): Aj ẻ A’, j ạ i }/(|A’| -1). trong đó: A’ A và S’ S Ta thấy rằng bước một và bước hai của thuật toán chỉ là bước đầu chuẩn bị cho quá trình tính toán, hai quá trình này chỉ để thu thập thông tin về các phương án, về chuyên gia và các đánh giá của họ trên từng mục tiêu. Thuật toán này để giải quyết bài toán quyết định mà các đánh giá của các chuyên gia lại cho ở dạng so sánh cặp. Điều này rất phù hợp đối với các bài toán quyết định khi đánh giá các dự án. Ví dụ: Trong một dự án kinh tế để đánh giá về mục tiêu: Độ may rủi. Rõ ràng với chỉ tiêu này khó có thể cho một đánh giá chính xác một giá trị cụ thể cho một phương án nào đó được. Do đó với các bài toán như vậy việc đánh giá của các chuyên gia cho ở dạng so sánh cặp là hợp lý và có thể giải quyết được khó khăn cho chính các chuyên gia trong quá trình đánh giá các phương án. Trong bước ba của thuật toán chúng ta cần tính toán giữa cặp phương án Ai và Aj mức độ đồng ý của các chuyên gia với nhãn s9 là bao nhiêu, s8 là bao nhiêu,..., và mức độ đó được thể hiện qua trọng số của các chuyên gia. Bước này là bước đệm để có thể tích hợp ý kiến chung của các chuyên gia giữa phương án Ai và phương án Aj. Bước thứ tư sử dụng toán tử LOWA để tích hợp. Kết quả sau khi kết hợp là một ma trận biểu thị ý kiến của tất cả các chuyên gia về mối liên hệ giữa từng cặp phương án. Bước thứ năm trong thuật toán chúng ta cùng xem xét một khái niệm mới, nghiệm tập thể mờ ( fuzzy collection selection ). Đây là một khái niệm mới, được đưa ra nhằm thể hiện độ trội tương đối giữa các phương án. Nghiệm tập thể mờ cũng được tính toán bằng toán tử LOWA, tuy nhiên cách tính trọng số cho toán tử này hoàn toàn khác so với cách tính ở bước thứ tư. Bước thứ sáu của thuật toán là quá trình phân cụm các phương án từ đó tìm ra được tập phương án có đánh giá tốt nhất theo các chuyên gia. Cuối cùng tính toán độ trội địa phương để tìm ra được phương án tốt nhất, đó chính là kết quae mong muốn của cả hội đồng. Sau đây là một ví dụ cụ thể cho thuật toán trên: Ví dụ: Xét trên mục tiêu C, Tập 4 phương án A1, A2, A3, A4 Tập 4 chuyên gia E1, E2, E3, E4 với trọng số tương ứng {0.4, 0.3, 0.1, 0.2}. Bước 1: Thu thập các đánh giá của các chuyên gia: Chuyên gia 1 Chuyên gia 2 Chuyên gia 3 Chuyên gia 4 Bước 2: Dựa vào trọng số các chuyên gia, chuẩn hoá Bước 3: Tính trọng số gộp cho từng nhãn: Dựa vào công thức ta có được IC s1 s2 s3 s4 s5 s6 s7 s8 s9 (1,1) 0 0 0 0 1 0 0 0 0 (1,2) 0 0.2 0 0 0 0 0 0.1 0.7 (1,3) 0 0.2 0 0 0 0 0 0.4 0.4 (1,4) 0 0.4 0.2 0 0 0.3 0 0 0.1 (2,1) 0 0 0.3 0.5 0 0.2 0 0 0 (2,2) 0 0 0 0 1 0 0 0 0 (2,3) 0 0 0 0 0 0 0.5 0.3 0.2 (2,4) 0 0 0 0.3 0 0.4 0 0.3 0 (3,1) 0.3 0.4 0.1 0 0 0 0 0.2 0 (3,2) 0.1 0.3 0.6 0 0 0 0 0 0 (3,3) 0 0 0 0 1 0 0 0 0 (3,4) 0.2 0 0 0.1 0 0 0.7 0 0 (4,1) 0 0.1 0 0.3 0 0 0 0.2 0.4 (4,2) 0 0.2 0.1 0.4 0 0 0 0 0.3 (4,3) 0 0.3 0.4 0 0 0 0 0.2 0.1 (4,4) 0 0 0 0 1 0 0 0 0 Bước 4: Tính độ trội tương đối của mỗi cặp phương án, sử dụng toán tử LOWA với véc-tơ trọng số là trọng số gộp theo từng nhãn đã tính ở trên ta có được: E(i,j) Phương án A1 Phương án A2 Phương án A3 Phương án A4 Phương án A1 IM ML EL SC Phương án A2 SC IM ML MC Phương án A3 VLC VLC IM MC Phương án A4 ML IM IM IM Bước 5: Tìm nghiệm tập thể mờ cho từng phương án; Tìm vt cho từng phương án: vt [s1] [s2] [s3] [s4] [s5] [s6] [s7] [s8] ]s9] A1 0 0 0 1/3 0 0 1/3 1/3 0 A2 0 0 0 1/3 0 1/3 1/3 0 0 A3 0 0 2/3 0 0 1/3 0 0 0 A4 0 0 0 0 2/3 0 0 1/3 0 Dùng toán tử LOWA để tính được nghiệm tập thể mờ ta được: FCS Phương án A1 Phương án A2 Phương án A3 Phương án A4 MC MC SC MC Bước 6: Phân cụm: Y6 = {A1, A2, A4} Y4 = {A3} Bước 7: Tính toán độ trội địa phương Cố định tập phương án { A1, A2, A4 } là tập phương án có đánh giá tốt nhất của các chuyên gia. Tiến hành tính toán độ trội địa phương ta được: DS(A1) = 1 ; DS(A2) = 1; DS(A4) = 2. Vậy A4 là phương án cần tìm. 2.5.2 Thuật toán cho bài toán quyết định nhiều mục tiêu: Với bài toán ra quyết định nhiều mục tiêu, ngoài trọng số của các chuyên gia còn có trọng số của các mục tiêu để đánh giá độ quan trọng của nó trong tập mục tiêu. Tư tưởng giải bài toán này là cố định từng mục tiêu ta tiến hành tích hợp như thuật toán đối với bài toán lấy quyết định một mục tiêu rồi sau đó tích hợp lại một lần nữa theo các mục tiêu và trọng số tương ứng của nó. Thuật toán cụ thể gồm các bước sau: Với mỗi một mục tiêu, thực hiện từ bước 1 đến bước 4. Bước 1: Thu thập các quan hệ mờ { Pk m} là đánh giá của các chuyên gia trên một mục tiêu. Bước 2: Dựa vào tập vector trọng số W(k), W(m) trong đó w(k), w(m) tương ứng là trọng số của chuyên gia ek, của mục tiêu cm, 0Ê w(k), w(m) Ê 1. Thực hiện chuẩn hoá w’(k)=w(k)/w0, w’(m)/w trong đó w0=Skw(k), w=ồmw(m). Bước 3: Tính trọng số gộp theo từng nhãn st đối với cặp phương án (Ai, Aj) đó chính là độ nhất trí chọn st trong so sánh của tập chuyên gia. ICm(i,j)[sT] = Sk {w’(k): Pkm(Ai, Aj) = st}, trong đó Pmk(Ai, Aj) là đánh giá của chuyên gia k theo mục tiêu m Bước 4: Tính độ trội tương đối của mỗi cặp phương án (Ai, Aj) (cho bằng từ) dưới đánh giá của tập chuyên gia trên mỗi mục tiêu bằng toán tử LOWA Em(i,j) = LOWA(S, Um(i, j)) trong đó Um(i, j)={um1,..., umT} với umt = ICm(i, j)[st] với mỗi t Thấy rằng Em(i, j) là một ma trận, đó là một quan hệ mờ cấp 2 đo độ trội tương đối theo ý kiến đã tích hợp của cả hội đồng trên mục tiêu m Như vậy sau bước 4 ta có m ma trận quan hệ đo độ trội tương đối theo ý kiến đã tích hợp của hội đồng theo m mục tiêu khác nhau. Bây giờ chúng ta sẽ tích hợp theo các mục tiêu do đó sẽ được mức tích hợp chung. Bước 5: Tính trọng số gộp theo từng nhãn st đối với cặp phương án (Ai, Aj) đó chính là độ nhất trí chọn từ st trong so sánh của tất cả các chuyên gia trên tất cả các mục tiêu. ICFT(i,j)[sT] = Sm {w’(m): Em(Ai, Aj) = st}, Bước 6: Tính độ trội tương đối của mỗi cặp phương án (Ai, Aj) (cho bằng từ) bằng toán tử LOWA EFT(i,j) = LOWA(S, U(i, j)) trong đó U(i, j)={u1,..., uT} với ut = ICFT(i, j)[st] với mỗi t Thấy rằng EFT(i, j) là một ma trận, đó là một quan hệ mờ cấp hai đo độ trội tương đối theo ý kiến đã tích hợp theo tất cả các chuyên gia và mục tiêu Bước 7: Tìm nghiệm tập thể mờ FCS ( fuzzy collective solution ): FCS = (mFCS(A1)/A1,..., mFCS(An)/An) trong đó mFCS(Ai) = LOWA(S, V(i)), V(i)=[v1, v2, ..., vT] với mỗi vt =# {j: EFT(i,j)=st , jại}/n-1 Bước 8: Phân cụm. Dùng {mFCS(Ai): Ai ẻA để phân cụm tập phương án A thành các lớp Y1, Y2,..,YT sao cho YT = { Ai mFCS(Ai)=st } với mỗi st ẻS t*=max{t: Yt ạ ặ, st ẻS} Bước 9: Cố định tập S’ và tính toán độ trội địa phương D(Ai, Yt*, S’). Lời giải của bài toán chính là DS(Yt*) 2.6 Ưu điểm của phương pháp: Tích hợp theo phương pháp này có ưu điểm nổi bật là tính mềm dẻo trong đánh giá các phương án. Thay vì cần phải có một đánh giá chính xác mang tính định lượng ta có thể mềm dẻo hơn khi áp dụng phương pháp đánh giá trên với các giá trị đánh giá thể hiện bằng một số mờ. Nhờ tính chất này phương pháp tích hợp trên đã phát huy được thế mạnh của mình đặc biệt là trong việc đánh giá các dự án, đánh giá về con người v.v…. 2.7 Nhược điểm: Nhược điểm của phương pháp này đã được đề cập trong phần trên của đồ án đó là việc chọn được tập nhãn có cùng phân bố hàm thuộc làm tập nhãn cơ sở để tiến hành việc thu ý kiến đánh giá của các chuyên gia. Công việc này hết sức khó khăn và đòi hỏi người phân tích phải am hiểu tương đối rõ trong lĩnh vực cần xem xét đánh giá. Ngoài ra với thuật toán đã trình bày ở trên ta có thể nhận thấy rằng việc gán trọng số cho các chuyên gia chưa thật linh hoạt khi các chuyên gia có trọng số cố định để đánh giá các mục tiêu khác nhau. Với nhược điểm này hướng khắc phục là ta nên thay đổi mềm dẻo các trọng số của từng chuyên gia trên từng mục tiêu cố đị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ế phân tích bài toán: Với phần lý thuyết được trình bày trong các chương trước, chúng ta có thể áp dụng vào nhiều bài toán thực tế khác nhau như bài toán đánh giá trình độ công nghệ của các doanh nghiệp, đánh giá nơi nào xây dựng một khu công nghệ cho phù hợp, các bài toán về chiến lược maketting, chiến lược kinh doanh v v.. .áp dụng phần lý thuyết trên em đã xây dựng chương trình thực nghiệm đánh giá dự án đầu tư kinh tế để xây dựng nhà máy chế biến nông sản. Mô hình bài toán được phát biểu: Một dự án kinh tế đầu tư của nước ngoài vào Việt Nam để xây dựng nhà máy nông sản xuất khẩu. Sau thời gian tìm hiểu tại Việt Nam dự án đầu tư đã tìm ra được một số phương án để xây dựng nhà máy là các địa phương như sau: Số thứ tự Phương án đề xuất 1 Hải Phòng 2 Ninh Bình 3 Thanh Hoá 4 Hà Tĩnh 5 Long An 6 Cần Thơ Bên nước ngoài có nhờ đoàn tư vấn gồm một sô chuyên gia Việt Nam tư vấn đánh giá để tìm ra được địa điểm thích hợp để xây dựng nhà máy dựa trên các mục tiêu sau: Số thứ tự Chỉ tiêu 1 Nguồn nhiên liệu 2 Nguồn nhân công 3 Chính sách ưu đãi( của địa phương ) 4 Cơ sở vật chất hạ tầng 5 Thủ tục hành chính Các chuyên gia sẽ đánh giá theo ý kiến của mình so sánh từng cặp phương án dựa trên từng mục tiêu cụ thể. Nhiệm vụ của chương trình đặt ra là phải tính toán trên các đánh giá của chuyên gia, dựa vào trọng số của các chuyên gia, trọng số của các mục tiêu từ đó tích hợp để tìm ra phương án cuối cùng là địa phương nào có khả năng đáp ứng tốt nhất các mục tiêu trên. thiết kế chương trình: 2.1 Sơ đồ phân cấp chức năng: Chương trình bao gồm các chức năng như sau: Chức năng nhập dữ liệu: Nhập dữ liệu từ file: Các thông tin về phương án, chuyên gia, mục tiêu và các đánh giá của từng chuyên gia đã được lưu sẵn dưới dạng các file dữ liệu. Chức năng này làm nhiệm vụ nạp dữ liệu vào chương trình để tính toán. Nhập dữ liệu từ bàn phím: Nhập thông tin về các phương án, chuyên gia, mục tiêu chuẩn bị cho quá trình tính toán. Chức năng tích hợp: Sử dụng các dữ liệu có được từ chức năng nhập dữ liệu tính toán lưu vào các biến. Các chức năng khác: Xem kết quả: Hiển thị kết quả sau khi tính toán được lưu trong các biến toàn cục ra màn hình. Trợ giúp: Hướng dẫn sử dụng chương trình và tra cứu giá trị tập nhãn đánh giá. 2.2 Sơ đồ luồng dữ liệu; Theo các chức năng của chương trình được phân tích ở trên ta có được sơ đồ luồng dữ liệu được biểu diễn như sau: 2.3 Thiết kế cơ sở dữ liệu: Với phần lý thuyết đã phân tích như trên ta có thể thiết kế cơ sở dữ liệu theo các bảng như sau: Bảng mục tiêu bài toán Tên Kiểu ý nghĩa Criterial_ID Criterial_Name Criterial_Weight Text Text float Khoá chính của mục tiêu Tên mục tiêu Trọng số của mục tiêu Bảng chuyên gia: Tên Kiểu ý nghĩa Expert_ID Expert_Name Expert_Weight Text Text float Khoá chính của chuyên gia Tên chuyên gia Trọng số của chuyên gia Bảng phương án: Tên Kiểu ý nghĩa Alternative_ID Alternative _Name Alternative _Weight Text Text float Khoá chính của phương án Tên phương án Trọng số của phương án Bảng đánh giá: Tên Kiểu ý nghĩa a1 a2 ... an Text Text ... Text Các đánh giá Ta nhân thấy rằng bảng chuyên gia là một bảng được thiết kế đặc biệt các trường trong bảng có ý nghĩa như sau: Nếu trường a1 bắt đầu bằng kí tự “@” thì trường a2 và trường a3 biểu diễn số lượng chuyên gia và số lượng mục tiêu cần đánh giá. Nếu trường a1 bắt đầu bằng kí tự “ * ” thì trường kí tự tiếp theo của chuyên gia thứ i và trường a2 biểu diễn mục tiêu thứ j nào đó. Nếu không bắt đầu bằng các kí tự đặc biệt trên thì mỗi bản ghi là một đánh giá theo một mục tiêu của một phương án so với các phương án còn lại. 2.4 Cài dặt chương trình và kết quả thực hiện: Lưu trữ cơ sở dữ liệu: Dữ liệu của chương trình là thông tin về tiêu chuẩn, khả năng lựa chọn tương đối thích hợp với các file cơ sở dữ liệu của các hệ quản trị cơ sở dữ liệu như Microsoft Access, SQL server..... Việc lưu trữ dữ liệu dưới dạng cơ sở sữ liệu rất thuận lợi cho việc phân tán , quản lý, đặc biệt khi dữ liệu quá lớn. Nhưng nó cũng có nhược điểm là mỗi lần thay đổi bài toán thì chúng ta phải tạo một cơ sở dữ liệu cho bài toán có cùng cấu trúc dữ liệu và việc này thì tốn nhiều bộ nhớ cho cấu trúc chương trình. Tuy nhiên với việc bước đầu xây dựng thử nghiệm, chương trình còn đơn giản do đó em đã quyết định chọn các lưu trữ cơ sở dữ liệu bằng hệ quản trị cơ sở dữ liệu Microsoft Access. Lý do để lựa chọn hệ quản trị cơ sở dữ liệu này vì nó có giao diện tương đối thân thiện với người lập trình dễ thay đổi, cập nhật, sửa, xoá.. Bên cạnh đó Microsoft Access là hệ quản trị tương đối “nhẹ” vì thế thích hợp với các chương trình chạy trên máy đơn, không đòi hỏi cấu hình máy lớn Lựa chọn ngôn ngữ lập trình: * Giới thiệu qua về ngôn ngữ lập trình hướng đối tượng Visual Basic: Ngày nay, hầu như Windows đã thống lĩnh hầu hết các máy PC trên toàn thế giới. Các ứng dụng sẽ được phát triển theo hệ điều hành. Từ khi Windows 95 ra đời đã mở ra một kỷ nguyên mới cho công nghệ thông tin. Các ngôn ngữ lập trình đã phát triển không ngừng, đáp ứng được sự tích hợp khác chạy cùng môi trường. VISUAL BASIC là một trong những công cụ lập trình theo hướng đối tượng, can thiệp tới mọi ứng dụng trong Windows (Access, Excel, Winword,...). Việc tạo ra các đối tượng là đơn giản trong VB, tạo ra các Activex (ứng dụng trên các Intranet) tương ứng với Applet của Java. Một ứng dụng đang chạy ở chế độ máy đơn có thể chuyển sang Activex (chạy Server). Chương trình được viết bằng VB có thể chuyển ngay sang Java. Và VB có thể truy nhập tới tất cả các cơ sở dữ liệu như: Oracle, SQL Server, Access, Foxpro... VISUAL BASIC cung cấp đầy đủ các đối tượng trong thư viện sẵn có của nó. Các đối tượng như DAO, RDO để truy cập tới Database, các đối tưọng điều khiển như Textbox,ComboBox, DBGrid, DataControl... dùng để thiết kế giao diện và hiển thị dữ liệu lấy từ các đối tượng Database, Recordset và Resultset. Các đối tượng điều khiển là các tệp .OCX. Với Visual basic chúng ta rất dễ dàng sửa đổi một đối tượng điều khiển đã có thành đối tượng của mình bằng cách thêm hoặc bớt các đặc tính của nó. VISUAL BASIC có một hệ soạn thảo tuyệt vời. Các thủ tục không cần sắp xếp tuần tự như Pascal, C, hay C++. Các thủ tục của Visual Basic được viết ra sắp xếp theo các đối tượng. Để thiết kế các thủ tục (các sự kiện) của một đối tượng nào đó bất kì, ta chỉ cần Double click mouse lên đối tượng đó. Những lợi điểm khi dùng Visual Basic chính là ở chỗ tiết kiệm thời gian và công sức hơn so với các ngôn ngữ lập trình khác khi xây dựng cùng một ứng dụng. Vì vậy, em đã lựa chọn ngôn ngữ lập trình hướng đối tượng Visual Basic làm môi trường để xây dựng chương trình của mình. * Cài đặt chương trình: Chạy file .exe để thực hiện chương trình: - Nhập dữ liệu từ file: - Nhập dữ liệu từ bàn phím: - Nhập các đánh giá: - Trợ giúp chương trình: * Kết quả thử nghiệm chương trình: Với dữ liệu đầu vào ta có các chuyên gia như sau: Mã chuyên gia Chuyên gia Trọng số 001 Nguyễn Bích Vượng 0.2 002 Nguyễn Thanh Hà 0.1 003 Nguyễn Hồng Hạnh 0.1 004 Lê Quang Phúc 0.2 005 Lê Chí Ngọc 0.2 006 Nguyễn Thành Huy 0.2 Với các mục tiêu: Mã mục tiêu Mục tiêu Trọng số 001 Nguồn nhiên liệu 0.3 002 Nguồn nhân công 0.1 003 Chính sách ưư đãi 0.2 004 Cơ sở hạ tầng 0.3 005 Thủ tục hành chính 0.1 Các đánh giá của chuyên gia như sau: Pi,j là đánh giá của chuyên gia i trên mục tiêu j P1,1 = P1,2 = P1,3= P1,4= P1,5= P2,1 = P2,2= P2,3= P2,4= P2,5= P3,1 = P3,2 = P3,3= P3,4= P3,5= P4,1 = P4,2= P4,3 = P4,4= P4,5= P5,1= P5,2= P5,3= P5,4= P5,5 = P6,1 = P6,2 = P6,3 = P6, = P6,5= Kết quả ta có giá trị FSC sau khi tích hợp ta được các giá trị như sau: Ninh Bình : IM Thanh Hoá: IM Hà Tĩnh: SC Long An: VLC Cần Thơ: MC Hải Phòng: MC Cố dịnh hai phương án có cùng giá trị MC là Cần Thơ và Hải Phòng, tính toán độ trội địa phương ta được Cần Thơ: 0.6, Hải Phòng: 0.4 vậy phương án tốt nhất được hội đồng đánh giá là Cần Thơ. kết luận Do thời gian nghiên cứu có hạn nên đồ án không có điều kiện tập trung đi sâu vào nghiên cứu các ứng ụng của toán tử LOWA và một số quy trình lấy quyết định tập thể khác dựa trên toán tử LOWA. Tuy nhiên đồ án cũng có được một số kết quả bước đầu, cụ thể như sau: Thứ nhất đồ án tập trung nghiên cứu bài toán lấy quyết định đa mục tiêu để tìm được phương án tốt nhất theo ý kiến tích hợp của cả hội đồng. Ưu điểm của đồ án là đã tìm hiểu được thuật toán cho bài toán lấy quyết định nhiều mục tiêu bằng toán tử tích hợp LOWA là toán tử tích hợp trên miền giá trị ngôn ngữ. Đây là hướng phát triển mới sau nhưng toán tử tích hợp trung bình hoặc các hàm tích hợp Borda là những phương pháp tích hợp lấy quyết định tập thể dựa trên các đánh giá ở dạng giá trị số. Đồ án cũng áp dụng khái niệm nghiệm tập thể mờ FCS (Fuzzy Collection Solution) và độ trội địa phương là hai khái niệm tương đối mới để giải quyết hiệu quả hơn bài toán lấy quyết định nhiều mục tiêu Thứ hai là về mặt chương trình, đồ án đã tận dụng được một sô điểm mạnh của công cụ lập trình Visual Basic và bước đầu xây dựng được chương trình thu thập xử lý, sắp xếp các phương án theo đánh giá của chuyên gia. Kết quả thử nghiệm chương trình với một số bộ dữ liệu khác nhau là đáng tin cậy. Tuy nhiên đồ án còn một số điểm hạn chế như: Chưa nghiên cứu được nhiều hơn các hàm tích hợp mạnh, kết hợp với toán tử LOWA hoặc kết hợp toán tử tích hợp LOWA và các phương pháp tích hợp dựa trên các giá trị rõ. Hạn chế của chương trình là ở chỗ mới chỉ xây dựng chương trình trên máy đơn, chưa mở rộng được để chạy trên môi trường phân tán, do đó việc tổng hợp các đánh giá của chuyên gia cũng rất khó khăn. Với thời gian nghiên cứu có hạn nên đồ án không có điều kiện giải quyết những hạn chế trên do vậy em hy vọng rằng hạn chế của đồ án cũng chính là một vấn đề mở để trong một tương lai gần em hoặc các bạn sinh viên khác ham thích nghiên cứu khoa học sẽ khắc phục được những hạn chế của đồ án nhằm mang lại kết quả tối ưu cho bài toán lấy quyết định nhiều mục tiêu. Một lần nữa em xin cảm ơn và mong nhận được sự chỉ bảo tận tình của các thầy cô, sự đóng góp ý kiến của các bạn sinh viên. tài liệu tham khảo [1]. Hệ mờ Mạng Nơron và ứng dụng – Chủ biên : Bùi Công Cường, Nguyễn Doãn Phước. Nhà xuất bản khoa học và kĩ thuật. [2]. B.C.Cuong: A new process in group decision making using linguistic consensus measures and linguistic OWA operator, Preprint 98/1, Insitute of Mathematics, Ha Noi, 1998. [3]. B.C.Cuong: On group decision making under linguistic assessments, Int, Journal of Uncertainly, Fuzzyness and Knowledge – Based Systems, Vol 7, no.4, 1999 , 403-408 [4]. F.Herrera, E.Herrera Viedma and J.L.Verdegay: A sequential selection process in group decision making with a linguistic assessment approach, Information Sciences, 85 (1995), 233-239. [5] Bùi Công Cường: Logic mờ và các ứng dụng đa dạng của nó, Viện toán học Hà Nội, Preprint 99/35, Hà Nội 10/1999. [6] Đồ án tốt nghiệp sinh viên Lê Thị Thanh Bình – Khoa Công nghệ thông tin Viện Đại Học Mở Hà Nội