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

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