Tài liệu Tìm kiếm thông minh với ứng dụng của tập mờ trực cảm

i ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN TUẤN CƢỜNG TÌM KIẾM THÔNG MINH VỚI ỨNG DỤNG CỦA TẬP MỜ TRỰC CẢM LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Thái Nguyên, tháng 10 năm 2013 Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/ i ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN TUẤN CƢỜNG TÌM KIẾM THÔNG MINH VỚI ỨNG DỤNG CỦA TẬP MỜ TRỰC CẢM Chuyên ngành: KHOA HỌC MÁY TÍNH Mã số: 60.48.01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Giáo viên hƣớng dẫn khoa học: TS. NGUYỄN TÂN ÂN Thái Nguyên, tháng 10 năm 2013 Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/ i LỜI CAM ĐOAN Tôi xin cam đoan toàn bộ nội dung trong luận văn này do tôi tự nghiên cứu, đọc, dịch tài liệu, tổng hợp và thực hiện. Trong luận văn tôi có sử dụng một số tài liệu tham khảo như đã trình bày trong phần tài liệu tham khảo. Ngƣời viết luận văn Nguyễn Tuấn Cƣờng Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/ ii LỜI CẢM ƠN Đầu tiên tôi xin gửi lời cảm ơn chân thành đến thầy TS Nguyễn Tân Ân – Đại học Sư phạm Hà Nội đã tận tình hướng dẫn, chỉ bảo cho tôi trong suốt quá trình làm luận văn. Tôi cũng xin gửi lời cảm ơn đến các thầy cô trường Đại học Công nghệ thông tin và Truyền thông – Đại học Thái Nguyên, các thầy cô Viện Công nghệ thông tin đã truyền đạt những kiến thức và giúp đỡ tôi trong suốt quá trình học của mình. Tôi cũng xin gửi lời cảm ơn tới các đồng nghiệp trong đơn vị công tác, gia đình và bạn bè những người đã động viên tạo mọi điều kiện giúp đỡ tôi trong suốt hai năm học. Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/ iii MỤC LỤC LỜI CAM ĐOAN ....................................................................................................... i LỜI CẢM ƠN ............................................................................................................ ii MỤC LỤC ................................................................................................................. iii DANH MỤC CÁC KÍ HIỆU, CHỮ CÁI VIẾT TẮT............................................... iv DANH MỤC CÁC HÌNH ...........................................................................................v MỞ ĐẦU ....................................................................................................................1 Chƣơng 1: NHỮNG KIẾN THỨC CƠ SỞ TẬP MỜ, TẬP MỜ TRỰC CẢM, VẤN ĐỀ TÌM KIẾM ................................................................................................4 1.1. Tập mờ ..............................................................................................................4 1.1.1. Định nghĩa tập mờ, số mờ [1]........................................................................4 1.1.2. Các phép toán trên tập mờ, số mờ hình thang, số mờ tam giác ....................9 1.2. Tập mờ trực cảm.............................................................................................18 1.2.1. Định nghĩa ...................................................................................................18 1.2.2. Các phép toán trên số mờ trực cảm hình thang, hình tam giác ...................20 1.3. Bài toán tìm kiếm lời giải và những kỹ thuật tìm kiếm .................................26 1.4. Kết luận chương 1 ..........................................................................................37 Chƣơng 2: TÌM KIẾM THÔNG MINH VỚI ỨNG DỤNG CỦA TẬP MỜ TRỰC CẢM.............................................................................................................38 2.1. Tìm kiếm thông minh .....................................................................................38 2.2. Thuật toán tìm kiếm thông minh với ứng dụng tập mờ trực cảm ..................53 2.3. Kết luận chương 2 ..........................................................................................58 Chƣơng 3: VÍ DỤ ÁP DỤNG .................................................................................59 3.1. Một số bài toán tìm kiếm ................................................................................59 3.2. Lời giải ...........................................................................................................61 3.3. Kết luận chương 3 ..........................................................................................82 KẾT LUẬN ..............................................................................................................83 TÀI LIỆU THAM KHẢO ......................................................................................84 Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/ iv DANH MỤC CÁC KÍ HIỆU, CHỮ CÁI VIẾT TẮT Vague sets (VS) Tập mờ trực cảm Vague Number (VN) Số mờ trực cảm Vague Relation (VR) Quan hệ mờ trực cảm Vague Tolerance Relation (VTR) Quan hệ gần đúng Vague Proximity Relation (VPR) Quan hệ lân cận Depth First Search (DFS) Tìm kiếm theo chiều sâu Breadth First Search (BFS) Tìm kiếm theo chiều rộng Domain (Dom) Miền Not less than (nlt) Không nhỏ hơn Sup Cận trên Inf Cận dưới Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/ v DANH MỤC CÁC HÌNH Hình 1.1: Biểu diễn tập mờ cho số "integer nhỏ" ....................................................... 4 Hình 1.2: Biểu diễn tập mờ cho các tập người thấp, trung bình và cao ...................... 5 Hình 1.3: Tập mờ lồi ................................................................................................... 6 Hình 1.4: Đồ thị hàm thành viên nhóm hàm đơn điệu ................................................ 7 Hình 1.5: Đồ thị hàm thành viên nhóm hàm hình chuông .......................................... 7 Hình 1.6: Hàm thành viên của phần bù mờ ................................................................ 9 Hình 1.7: Hàm thành viên của hợp hai tập mờ có cùng cơ sở .................................... 9 Hình 1.8a: Phép hợp hai tập mờ không cùng cơ sở: Hàm thành viên của 2 tập mờ A, B ................................................................................................. 10 Hình 1.8b: Phép hợp hai tập mờ không cùng cơ sở: Đưa 2 tập mờ về chung một cơ sở MxN ...................................................................................... 10 Hình 1.8c: Phép hợp hai tập mờ không cùng cơ sở: Hợp 2 tập mờ trên cơ sở MxN ....... 10 Hình 1.9: Phép giao hai tập mờ cùng cơ sở .............................................................. 11 Hình 1.10: Phép giao hai tập mờ không cùng cơ sở ................................................. 12 Hình 1.11: Số mờ hình thang .................................................................................... 17 Hình 1.13: Số mờ trực cảm hình thang ..................................................................... 21 Hình 1.14: Số mờ trực cảm tam giác ........................................................................ 21 Hình 1.15: Đồ thị không gian trạng thái ................................................................... 28 Hình 1.16: Trạng thái ban đầu và trạng thái kết thúc của bài toán 8 số .................... 30 Hình 1.17: Các trạng thái của cây trò chơi................................................................ 36 Hình 1.18: Cây tìm kiếm và sự bùng nổ tổ hợp ........................................................ 37 Hình 2.1: Hình ảnh của tìm kiếm chiều sâu. Nó chỉ lưu ý "mở rộng" trạng thái được chọn mà không "mở rộng" các trạng thái khác (nút màu trắng). .................... 39 Hình 2.2: Hình ảnh của tìm kiếm chiều rộng. Tại một bước, mọi trạng thái đều được mở rộng, không bỏ sót trạng thái nào ............................................. 41 Hình 2.3: Chi phí ước lượng h‟ = 6 và chi phí tối ưu thực sự h = 4+5 = 9 (đi theo đường 1-3-7) .................................................................................... 43 Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/ vi Hình 2.5: Đồ thị không gian trạng thái ..................................................................... 47 Hình 2.6: Cây tìm kiếm Beam................................................................................... 48 Hình 2.7: Đồ thị không gian trạng thái ..................................................................... 50 Hình 2.8: Sơ đồ biểu thị đường đi ............................................................................. 51 Hình 2.9: Đồ thị không gian trạng thái ..................................................................... 55 Hình 3.1: Trạng thái ban đầu và trạng thái kết thúc của bài toán 8 số ...................... 59 Hình 3.2: Giải bài toán Ta canh bằng phương pháp tìm kiếm theo chiều sâu .......... 59 Hình 3.3: Giải bài toán Ta canh bằng thuật giải Heuristics tìm đường đi có giá nhỏ nhất với tri thức bổ sung ................................................................... 60 Hình 3.1: Trạng thái ban đầu và trạng thái kết thúc của bài toán 8 số ...................... 61 Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/ 1 MỞ ĐẦU Xuất phát từ sự bùng nổ thông tin và mạng internet kết nối hầu hết các máy tính của các tổ chức thành những kho dữ liệu khổng lồ. Tuy nhiên, dữ liệu được bố trí sắp xếp và phân tán thành nhiều tập dữ liệu được lưu trữ trên các hệ thống máy tính lớn nằm rải rác trên toàn thế giới. Với một kỹ thuật đơn giản thì việc tìm kiếm thông tin là rất khó khăn và không chính xác mất nhiều thời gian tìm kiếm. Câu hỏi đặt ra là làm thế nào để con người có thể vươn tới tầm cao tri thức làm chủ được công nghệ, tìm kiếm thông tin nhanh và chính xác. Cùng với việc phát minh ra các thuật toán tìm kiếm tối ưu các kỹ thuật mới xuất hiện và có tốc độ phát triển rất nhanh đóng góp vai trò quan trọng trong việc tìm kiếm dữ liệu, các thuật toán mới xuất hiện với thời gian tính toán đã phần nào giải quyết được những vướng mắc nói trên. Ngoài ra còn có sự hỗ trợ của nhiều phương pháp, liên quan đến nhiều lĩnh vực, ngành khác như: lý thuyết thuật toán, thị giác máy tính (Visualization), Data Warehouses, OLAP, tính toán song song, cấu trúc ôtômát mờ và các phép tính toán kết quả cao…nhưng chủ yếu dựa trên nền tảng của xác suất thống kê, cơ sở dữ liệu, lý thuyết mờ, lý thuyết ôtômát và học máy. Đây là một quá trình mang tính định tính với mục đích xác định được lĩnh vực yêu cầu phát hiện tri thức và xây dựng bài toán tổng thể. Trong thực tế, các cơ sở dữ liệu được chuyên môn hoá và phân chia theo các lĩnh vực khác nhau như sản xuất, kinh doanh, tài chính... Với mỗi tri thức phát hiện được, có thể có giá trị trong lĩnh vực này nhưng lại không mang nhiều ý nghĩa đối với một lĩnh vực khác. Vì vậy việc xác định lĩnh vực và định nghĩa bài toán giúp định hướng cho giai đoạn tiếp theo – thu thập và tiền xử lý dữ liệu. Các cơ sở dữ liệu thu được thường chứa rất nhiều thuộc tính nhưng lại không đầy đủ, không thuần nhất, có nhiều lỗi và các giá trị đặc biệt. Vì vậy, giai đoạn thu thập và tiền xử lý dữ liệu trở nên rất quan trọng trong quá trình phát hiện tri thức từ cơ sở dữ liệu phục vụ cho việc tìm kiếm dữ liệu. Quá trình tìm kiếm lời giải thực sự là một bài toán khó. Các phương pháp vét cạn kinh điển như tìm kiếm sâu (DFS), tìm kiếm rộng (BFS),… đều không thể áp Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/ 2 dụng trong không gian tìm kiếm lớn bởi độ phức tạp thời gian. Trong môi trường mờ vấn đề tìm kiếm càng khó. Lý thuyết tập mờ được L.Zadeh đề nghị năm 1965 đã khẳng định được tính ưu việt của nó. Tuy nhiên lý thuyết mờ cũng không ngừng được phát triển. Năm 1993 Gau and Buehrer đã đưa ra tập mờ trực cảm (intuitionistic fuzzy (vague) sets) [6]. Trong nhiều trường hợp tập mờ trực cảm mô tả thông tin mờ một cách hợp lý hơn và cho kết quả xử lý thông tin tốt hơn tập mờ của Zadeh. Những nghiên cứu về tập mờ trực cảm, tìm kiếm thông minh trong môi trường mờ nói chung và trong môi trường được mô tả bởi tập mờ trực cảm nói riêng còn ít. Vì thế trong khuôn khổ của luận văn thạc sĩ, em chọn đề tài “Tìm kiếm thông minh với ứng dụng của tập mờ trực cảm” nhằm tìm hiểu các thuật toán tìm kiếm lời giải, một nội dung kiến thức rất quan trọng của những chuyên gia về công nghệ thông tin. Đối tƣợng và phạm vi nghiên cứu - Vấn đề tìm kiếm lời giải - Tập mờ, tập mờ trực cảm - Tìm kiếm thông minh với ứng dụng của tập mờ trực cảm Hƣớng nghiên cứu của đề tài Nghiên cứu thuật toán tìm kiếm thông minh ứng dụng tập mờ trực cảm Những nội dung nghiên cứu chính Chƣơng 1: Những kiến thức cơ sở Tập mờ, tập mờ trực cảm, vấn đề tìm kiếm 1.1. Tập mờ 1.1.1. Định nghĩa tập mờ, số mờ 1.1.2. Các phép toán trên tập mờ, số mờ hình thang, số mờ tam giác 1.2. Tập mờ trực cảm 1.2.1. Định nghĩa 1.2.2. Các phép toán trên số mờ trực cảm hình thang, hình tam giác 1.3. Bài toán tìm kiếm lời giải và những kỹ thuật tìm kiếm 1.4. Kết luận chương 1 Chƣơng 2: Tìm kiếm thông minh với ứng dụng của tập mờ trực cảm 2.1. Tìm kiếm thông minh Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/ 3 2.2. Thuật toán tìm kiếm thông minh với ứng dụng tập mờ trực cảm 2.3. Kết luận chương 2 Chƣơng 3: Ví dụ áp dụng 3.1. Một số bài toán tìm kiếm 3.2. Lời giải 3.3. Kết luận chương 3 Phƣơng pháp nghiên cứu - Nghiên cứu lý thuyết: Tìm đọc tài liệu, đối chiếu, so sánh, rút trích, hệ thống hóa,... viết thành luận văn - Thực hành: Tìm kiếm lời giải trong một số trường hợp. Ý nghĩa khoa học của đề tài Áp dụng và khẳng định tính ưu việt của tập mờ trực cảm trong một số trường hợp cụ thể, đặc biệt trong tìm kiếm thông minh. Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/ 4 Chƣơng 1 NHỮNG KIẾN THỨC CƠ SỞ TẬP MỜ, TẬP MỜ TRỰC CẢM, VẤN ĐỀ TÌM KIẾM 1.1. Tập mờ Trong thực tế chúng ta đánh giá kết quả không chỉ mang tính chất đúng hoặc sai mà còn mang tính chất định tính không chắc chắn thông qua việc sử dụng các biến ngôn ngữ để phản ánh. Một trong những cách đánh giá và xử lý dạng biếu diễn thông tin thu được những kết quả rất tốt đó là cách tiếp cận mờ. Từ năm 1965, L.A.Zadeh đã xây dựng lý thuyết tập mờ, tạo ra một cơ sở toán học cho việc tiếp cận lập luận tính toán của con người. Ý tưởng của ông là mở rộng tập logic cổ điển (logic Boole), làm tăng thêm khả năng suy luận của con người, góp phần đánh giá kết quả đi đến độ chính xác nhất. Sau đây là một số khái niệm và tính chất cơ bản của tập mờ. 1.1.1. Định nghĩa tập mờ, số mờ [1] Định nghĩa tập mờ Cho tập vũ trụ U, tập A U được gọi là tập mờ nếu A được xác định bởi hàm A :U [0,1]. A được gọi là hàm thuộc, hàm thành viên hay hàm đặc trưng. Với x U thì A (x) được gọi là mức độ thuộc của x vào A. Như vậy ta có thể coi tập rõ là một trường hợp đặc biệt của tập mờ, trong đó hàm thành viên chỉ nhận 2 giá trị 0 và 1. Ví dụ 1. Một sự biểu diễn tập mờ cho số "integer nhỏ". 1 1 2 3 ..... int Hình 1.1: Biểu diễn tập mờ cho số "integer nhỏ" Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/ 5 Ví dụ 2. Một sự biểu diễn tập mờ cho các tập người thấp, trung bình và cao thấp trung bình cao 1 4‟ chiều cao 4‟6” 5‟ 5‟6” 6‟ 6‟6” Hình 1.2: Biểu diễn tập mờ cho các tập người thấp, trung bình và cao Ví dụ 3. Cho U={1, 2, 3, 4, 5}, tập mờ A trên U tương ứng với ánh xạ A như sau: 1 0 A: 2 1 3 0.5 4 0.3 5 0.2 Ta có tập mờ A={(1,0),(2,1),(3,0.5),(4,0.3),(5,0.2)} Cách viết trên là sự liệt kê các phần tử khác nhau cùng với mức độ thuộc về tập hợp A. Từ định nghĩa trên chúng ta có thể suy ra: - Tập mờ A là rỗng nếu và chỉ nếu hàm thuộc về µA(x)= 0, a U - Tập mờ A là toàn phần nếu và chỉ nếu µA(x) = 1, a U - Hai tập mờ A và B bằng nhau nếu µA(x) = µB(x) a U Ký hiệu tập mờ, ta có các dạng ký hiệu sau:  Liệt kê phần tử: giả sử U={a,b,c,d} ta có thể xác định một tập mờ A= 0.1 0.3 a b  A = x, A 0.2 c 0 d ( x) | x U ( x) trong trường hợp U là không gian rời rạc x  A= A x U  A= A ( x ) / x trong trường hợp U là không gian liên tục U Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/ 6 Lưu ý là các ký hiệu và không phải là các phép tính tổng hay tích phân, mà chỉ là ký hiệu biểu thị tập hợp mờ. Ví dụ 4. Tập mờ A là tập “số gần 2” xác định bởi hàm thuộc có thể ký hiệu: A = x, ( x 2) 2 | x U hoặc A = A e ( x 2) 2 ta ( x 2) 2 / x . Tập mờ cắt mức ( -cut) Tập mờ cắt mức là tập rõ trong đó hàm thành viên A(x)>= . Tập mờ lồi Cho tập mờ A xác định trong không gian X có hàm thành viên A(x). Khi đó tập mờ A được gọi là tập mờ lồi nếu hàm thành viên của tập mờ có dạng lồi hay nói cách khác tập mờ sẽ là tập mờ lồi nếu với mọi điểm x1, x2, x3 thuộc không gian X sao cho x1[0,1]. Nhưng trong thực tế thì có các dạng hàm thành viên sau đây là quan trọng và có tính ứng dụng cao hơn cả. Nhóm hàm đơn điệu Nhóm này gồm đơn điệu tăng và đơn điệu giảm. Ví dụ 5. Tập hợp người già có hàm thành viên đơn điệu tăng theo tuổi trong khi đó tập hợp người trẻ có hàm thành viên đơn điệu giảm theo tuổi. Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/ 7 Ví dụ 6. Cho tập vũ trụ E = Tốc độ = {20,50,80,100,120} đơn vị là km/h. Xét tập mờ F=Tốc độ nhanh xác định bởi hàm thành viên nhanh như đồ thị hình 1.4. Như vậy tốc độ dưới 20km/h được coi là không nhanh. Tốc độ càng cao thì độ thuộc của nó vào tập F càng cao. Khi tốc độ là 100km/h trở lên thì độ thuộc là 1. 1 nhanh 0.85 0.5 E 20 50 80 100 120 Hình 1.4: Đồ thị hàm thành viên nhóm hàm đơn điệu Nhóm hàm hình chuông Nhóm hàm này có đồ thị dạng hình chuông, bao gồm dạng hàm tam giác, hàm hình thang, gauss. Xét ví dụ cũng với tập vũ trụ E ở trên, xét tập mờ F=Tốc độ trung bình xác định bởi hàm thành viên trungbình 0 ( x 20) / 30 khi x 20 x 100 khi 20 x 50 (100 x) / 50 khi 1 50 x 100 trungbình 0.4 E 20 50 80 100 120 Hình 1.5: Đồ thị hàm thành viên nhóm hàm hình chuông Các khái niệm liên quan Giả sử A là tập mờ trên vũ trụ U, có hàm thuộc Số hóa bởi trung tâm học liệu A thì ta có các khái niệm sau: http://www.lrc-tnu.edu.vn/ 8  Giá đỡ của A, ký hiệu sup(A) là một tập rõ bao gồm tất cả các phần tử x U sao cho A (x) > 0.  Nhân của A là một tập rõ bao gồm tất cả các phần tử x A U sao cho (x)=1.  Biên của A là một tập rõ bao gồm tất cả các phần tử x 0< A U sao cho (x)<1.  Độ cao của A, ký hiệu height(A) là cận trên đúng của height(A)= sup A A (x). ( x) . x U  Tập mờ A được gọi là tập mờ chuẩn tắc (normal fuzzy set) nếu height(A)=1. Tức là tập mờ chuẩn tắc có nhân khác rỗng. Các tập mờ hay tập hợp mờ (Fuzzy set) là một mở rộng của lý thuyết tập hợp cổ điển và được dùng trong lôgic mờ. Trong lý thuyết tập hợp cổ điển, quan hệ thành viên của các phần tử trong một tập hợp được đánh giá theo kiểu nhị phân theo một điều kiện rõ ràng - một phần tử hoặc thuộc hoặc không thuộc về tập hợp. Ngược lại, lý thuyết tập mờ cho phép đánh giá từ từ về quan hệ thành viên giữa một phần tử và một tập hợp; quan hệ này được mô tả bằng một hàm thành viên (membership function) [0,1]. Các tập mờ được coi là một mở rộng của lý thuyết tập hợp cổ điển là vì, với một universe (không gian tham chiếu hay tập vũ trụ) nhất định, một hàm thành viên có thể giữ vai trò của một hàm đặc trưng (indicator function) ánh xạ mỗi phần tử tới một giá trị 0 hoặc 1 như trong khái niệm cổ điển. Một lớp tập mờ quan trọng có nhiều ứng dụng thực tế là số mờ Định nghĩa số mờ Tập mờ M trên đường thẳng thực R là tập số mờ nếu: - M là chuẩn hoá, tức là có điểm x sao cho - Ứng với mỗi R , tập mức x : M x M x 1 là đoạn đóng Người ta thường dùng các số mờ tam giác, hình thang và dạng Gauss Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/ 9 1.1.2. Các phép toán trên tập mờ, số mờ hình thang, số mờ tam giác Các phép toán trên tập mờ [2] Giả sử A và B là các tập mờ trên vũ trụ U thì ta có các định nghĩa sau: Quan hệ bao hàm A được gọi là bằng B khi và chỉ khi x U, A x B x . A được gọi là tập con của B, ký hiệu A B khi và chỉ khi A x x U, x B Phần bù Phần bù mờ của tập mờ A là tập mờ A với hàm thành viên được xác định bởi: A x 1 A (1) x A(x) 1 1 A x x x b) a) Hình 1.6: Hàm thành viên của phần bù mờ Tập bù A của tập mờ A a) Hàm thành viên của tập mờ A b) Hàm thành viên của tập mờ A Phép hợp Hợp của hai tập mờ A và B có cùng cơ sở M là một tập mờ cũng xác định trên cơ sở M với hàm thành viên: A B x max A x , B (2) x A(x) B(x) Hình 1.7: Hàm thành viên của hợp hai tập mờ có cùng cơ sở Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/ 10 Có nhiều công thức khác nhau được dùng để tính hàm thành viên A B của hợp hai tập mờ như: 1. max A x , 1 nếu min x A B 2. A B x 3. A B x 4. A B x a) min 1, 1 A A x x x x , B x 0 0 (Phép hợp Lukasiewicz) x B B B A x B B x nếu min x x , A x A x A B (Tổng Einstein) x A x . (Tổng trực tiếp)... x B A(x) A(y) x y Hình 1.8a: Phép hợp hai tập mờ không cùng cơ sở: Hàm thành viên của 2 tập mờ A, B b) A x, y x, y B x M N x M N y y Hình 1.8b: Phép hợp hai tập mờ không cùng cơ sở: Đưa 2 tập mờ về chung một cơ sở MxN c) A B x, y x M N y Hình 1.8c: Phép hợp hai tập mờ không cùng cơ sở: Hợp 2 tập mờ trên cơ sở MxN Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/ 11 Có hai tập mờ A (cơ sở M) và B (cơ sở N). Do hai cơ sở M và N độc lập với nhau nên hàm thành viên và ngược lại B x ,y x , x M của tập mờ A sẽ không phụ thuộc vào N A N của tập mờ B cũng sẽ không phụ thuộc vào M. Điều này thể hiện ở chỗ trên cơ sở mới là tập tích MxN hàm dọc theo trục y và B A x phải là một mặt “cong” y là một mặt “cong” dọc theo trục x. Tập mờ A được định nghĩa trên hai cơ sở M và MxN. Để phân biệt được chúng, ký hiệu A sẽ được dùng để chỉ tập mờ A trên cơ sở MxN. Tương tự, ký hiệu B được dùng để chỉ tập mờ B trên cơ sở MxN, với những ký hiệu đó thì: N và A x, y A x , y B x, y B y , x M. Sau khi đã đưa được hai tập mờ A, B về chung một cơ sở là MxN thành A và B thì hàm thành viên A, B x, y của tập mờ A B được xác định theo công thức tính tổng trực tiếp. Phép Giao Giao của tập mờ A và tập mờ B là tập mờ A B với hàm thuộc được xác định bởi: A B (x) = min( A (x), B A B A x (x)) (3) x B x x Hình 1.9: Phép giao hai tập mờ cùng cơ sở Trong công thức trên kí hiệu min xác định phép tính lấy cực tiểu được thực hiện trên tập mờ, bản chất phép tính không có gì thay đổi. Có nhiều công thức khác nhau được dùng để tính hàm thành viên A B giao hai tập mờ như: Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/ của 12 1. A B min A x , 0 nếu max x 2. A B x 3. A B x 4. A B x m ax 0, A 2 A A x . x A x , x A x B x B nếu max B x B x A A x . B x 1 (Tích Einstein) (Tích đại số)... x B x (Phép giao Lukasiewicz) x x B 1 1 B x , Công thức trên cũng áp dụng được cho hợp hai tập mờ không cùng cơ sở bằng cách đưa cả hai tập mờ về chung một cơ sở là tích của hai cơ sở đã cho. Chẳng hạn có hai tập mờ A định nghĩa trên cơ sở M và B định nghĩa trên cơ sở N. Do hai cơ sở M và N độc lập với nhau nên hàm thành viên tập mờ A sẽ không phụ thuộc vào N và ngược lại B y ,y B y x , x M của N của tập mờ B cũng sẽ không phụ thuộc vào M. Trên cơ sở mới là tập tích MxN hàm “cong” dọc theo trục y và A A x là một mặt là một mặt “cong” dọc theo trục x. Tập mờ A (hoặc B) được định nghĩa trên hai cơ sở M (hoặc N) và MxN. Để phân biệt kí hiệu A (hoặc B ) sẽ được dùng để chỉ tập mờ A (hoặc B) trên cơ sở mới là MxN. Với những kí hiệu đó thì: N và A x, y , y B x, y , x M A B x x M N y Hình 1.10: Phép giao hai tập mờ không cùng cơ sở Số hóa bởi trung tâm học liệu http://www.lrc-tnu.edu.vn/