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 TRẦN THỊ HƢƠNG GIANG TỐI ƢU HÓA THAM SỐ CỦA PHƢƠNG PHÁP LẬP LUẬN MỜ SỬ DỤNG ĐẠI SỐ GIA TỬ LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Thái Nguyên – 2014 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ ii LỜI CẢM ƠN Lời đầu tiên em xin gửi lời cảm ơn chân thành đến toàn thể các thầy cô giáo Viện Công nghệ Thông tin, cùng toàn thể quý Thầy Cô trong trƣờng Đại học Công nghệ Thông tin & Truyền thông đã tận tình dạy dỗ tận tình truyền đạt những kiến thức quý báu và tạo điều kiện thuận lợi cho tôi trong suốt quá trình học tập, nghiên cứu và thực hiện luận văn tốt nghiệp. Đặc biệt em xin bày tỏ lòng biết ơn sâu sắc tới Thầy giáo PGS- TS.Nguyễn Văn Long, Trƣờng Đại học Giao thông vận tải - Hà Nội đã quan tâm hƣớng dẫn và đƣa ra những gợi ý, góp ý, chỉnh sửa vô cùng quý báu cho em trong quá trình làm luận văn tốt nghiệp. Cuối cùng xin chân thành cảm ơn những ngƣời bạn đã giúp đỡ, chia sẽ với tôi trong suốt quá trình làm luận văn. Thái Nguyên, tháng 07 năm 2014 Học viên thực hiện Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ iii MỤC LỤC PHẦN MỞ ĐẦU 1 CHƢƠNG 1: PHƢƠNG PHÁP LẬP LUẬN MỜ SỬ DỤNG ĐẠI SỐ GIA TỬ……. 3 1.1 Tập mờ và các phép toán trên tập mờ 3 1.1.1.Tập mờ (fuzzy set) 3 1.1.2 Các phép toán đại số trên tập mờ 6 1.1.3 Khử mờ 8 1.2 Phƣơng pháp lập luận mờ đa điều kiện 8 1.2.1 Mô hình mờ 8 1.2.2 Phƣơng pháp lập luận mờ đa điều kiện 9 1.3 Đại số gia tử của biến ngôn ngữ 15 1.3.1 Khái niệm biến ngôn ngữ 15 1.3.2 Đại số gia tử của biến ngôn ngữ 18 1.4 Độ đo tính mờ và ánh xạ định lƣợng ngữ nghĩa 21 1.5 Phƣơng pháp lập luận mờ sử dụng đại số gia tử 26 CHƢƠNG 2: GIẢI THUẬT DI TRUYỀN 37 2.1 Giải thuật di truyền 37 2.1.1 Các khái niệm cơ bản của giải thuật di truyền 37 2.2.2 Minh họa cơ chế thực hiện của giải thuật di truyền 42 CHƢƠNG 3: TỐI ƢU HÓA THAM SỐ CỦA PHƢƠNG PHÁP LẬP LUẬN MỜ SỬ DỤNG ĐẠI SỐ GIA TỬ BẰNG GIẢI THUẬT DI TRUYỀN 47 3.1. Giải pháp tối ƣu hóa tham số của phƣơng pháp lập luận mờ sử dụng đại số gia tử …47 3.2 Ứng dụng xấp xỉ mô hình mờ EX1 của Cao – Kandel. 48 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ iv 3.3 Ứng dụng xấp xỉ mô hình mờ EX6 của Cao – Kandel. 55 KẾT LUẬN 63 TÀI LIỆU THAM KHẢO 64 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: Tập mờ hình thang 5 Hỉnh 1.2 Ví dụ về hệ khoảng 24 Hình 1.3 Các hàm thuộc của các tập mờ của biến h 30 Hình 1.4 Các hàm thuộc của các tập mờ của biến v 30 Hình 1.5 Các hàm thuộc của các tập mờ của biến f 30 Hình 1.6 Đƣờng cong định lƣợng ngữ nghĩa 34 Hình 2.1. Minh họa bánh xe rulet 44 Hình 3.1. Đƣờng cong thực nghiệm của mô hình EX1. 50 Hình 3.2 Kết quả xấp xỉ mô hình EX1 bằng vHAR. 55 Hình 3.3 Đƣờng cong thực nghiệm của mô hình EX6. 57 Hình 3.4 Kết quả xấp xỉ mô hình EX6 bằng vHAR. 62 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ vi DANH MỤC CÁC BẢNG Bảng 1.1. Các giá trị ngôn ngữ của các biến HEALTH và AGE 17 Bảng 1.2. Ví dụ về tính âm dƣơng giữa các gia tử 19 Bảng 1.3. Các nhãn tập mờ của các biến ngôn ngữ h, v, f 29 Bảng 1.4. Mô hình FAM của bài toán hạ cánh máy bay 31 Bảng 1.5. Kết quả điều khiển sử dụng lập luận mờ qua 4 chu kỳ 31 Bảng 1.6: Mô hình SAM 33 Bảng 1.7. Kết quả điều khiển mô hình máy bay hạ cánh 35 Bảng 2.1. Minh họa quá trình chọn lọc 41 Bảng 2.2. Minh họa quá trình lai ghép 42 Bảng 3.1. Mô hình EX1 của Cao – Kandel. 49 Bảng 3.2. Các kết quả xấp xỉ EX1 tốt nhất của Cao - Kandel [8] 50 Bảng 3.3. Mô hình định lƣợng ứng với vPAR1 52 Bảng 3.4. Mô hình EX6 của Cao – Kandel 56 Bảng 3.5. Dữ liệu thực nghiệm của EX6. 56 Bảng 3.6. Các kết quả xấp xỉ EX6 tốt nhất của Cao - Kandel [8] 57 Bảng 3.7. Mô hình định lƣợng ứng với vPAR2 59 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ vii DANH MỤC VIẾT TẮT FAM : Fuzzy Associate Memory SAM : Semantization Associate Memory ĐSGT : Đại số gia tử FMCR: Fuzzy Multiple Conditional Reasoning GA: Genetic Algorithm Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 1 PHẦN MỞ ĐẦU Đặt vấn đề Đại số gia tử (ĐSGT) và phƣơng pháp lập luận mờ sử dụng ĐSGT đã đƣợc ứng dụng vào một số lĩnh vực nhƣ xây dựng mô hình cơ sở dữ liệu mờ. Đánh giá kết quả học tập và giải quyết bài toán hƣớng nghiệp cho học sinh phổ thông. Gần đây phƣơng pháp lập luận mờ sử dụng ĐSGT đã đƣợc ứng dụng vào lĩnh vực điều khiển mờ. Các kết quả ứng dụng đã bƣớc đầu cho thấy các bài toán sử dụng tiếp cận ĐSGT cho kết quả tốt hơn nhiều so với các bài toán sử dụng tiếp cận mờ truyền thống. Đề tài của luận văn sẽ tập trung nghiên cứu phƣơng pháp lập luận mờ sử dụng đại số gia tử, đặc biệt là nghiên cứu việc sử dụng giải thuật di truyền để tối ƣu hóa các tham số trong phƣơng pháp lập luận mờ sử dụng đại số gia tử. Mục tiêu của đề tài - Nghiên cứu các khái niệm cơ bản về đại số gia tử, phƣơng pháp lập luận mờ sử dụng đại số gia tử. - Nghiên cứu các khái niệm cơ bản của giải thuật di truyền - Nghiên cứu ứng dụng giải thuật di truyền để tối ƣu hóa các tham số trong phƣơng pháp lập luận mờ sử dụng đại số gia tử. Phạm vi của đề tài - Nghiên cứu các khái niệm cơ bản về đại số gia tử, phƣơng pháp lập luận mờ sử dụng đại số gia tử. - Nghiên cứu ứng dụng giải thuật di truyền để tối ƣu hóa các tham số trong phƣơng pháp lập luận mờ sử dụng đại số gia tử. Phƣơng pháp nghiên cứu. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 2 + Nghiên cứu tài liệu, các bài báo trên các tạp chí và trên internet và viết tổng quan để nắm vững nội dung lý thuyết chuyên ngành và khả năng ứng dụng. + Nghiên cứu so sánh tìm ra sự khác biệt giữa các cách tiếp cận, giữa các phƣơng pháp lập luận làm cơ sở cho việc đề xuất các giải pháp của đề tài. + Lập trình mô phỏng thuật toán trên máy tính để thuận lợi trong nghiên cứu hiệu quả của phƣơng pháp. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 3 CHƢƠNG 1: PHƢƠNG PHÁP LẬP LUẬN MỜ SỬ DỤNG ĐẠI SỐ GIA TỬ 1.1 Tập mờ và các phép toán trên tập mờ Để mô tả những khái niệm mơ hồ, chẳng hạn nhƣ nhiệt độ “cao”, tốc độ “nhanh”,… ngƣời ta thƣờng sử dụng lý thuyết tập mờ. Dƣới đây là các định nghĩa và các phép toán cơ bản trong lý thuyết này. 1.1.1.Tập mờ (fuzzy set) Cho tập vũ trụ U (còn gọi là không gian tham chiếu), một tập con thông thƣờng A (tập rõ) của U có thể đƣợc đặc trƣng bởi hàm  A nhƣ sau:       Ax Ax x A ,0 ,1 )(  Ví dụ cho tập U = {x 1 , x 2 , x 3 , x 4 , x 5 }, A = {x 2 , x 3 , x 5 }. Khi đó  A (x 1 ) = 0,  A (x 2 )= 1,  A (x 3 ) = 1,  A (x 4 ) = 0,  A (x 5 ) = 1. Gọi A là phần bù của tập A, ta có A  A = , A  A = U. Nếu x  A thì x  A , ta viết  A (x) = 1, A  (x) = 0. Dễ dàng ta có, nếu A, B là hai tập con của U, thì hàm đặc trƣng của các tập AB, AB đƣợc xác định:        BAx BAx x BA ,0 ,1 )(  và        BAx BAx x BA ,0 ,1 )(  [...]... (LittleLarge)=0.62;(VeryVerySmall)=0.072 1.5 Phƣơng pháp lập luận mờ sử dụng đại số gia tử Trong phần này ta sẽ xem xét phƣơng pháp lập luận mờ sử dụng ĐSGT xấp xỉ mô hình mờ (1.2), mô hình mờ (1.1) chỉ là trƣờng hợp riêng của mô hình mờ (1.2) với m = 1 Theo tiếp cận của ĐSGT, mô hình mờ FAM (1.2) đƣợc xem nhƣ một tập hợp các “điểm mờ Với việc sử dụng các ánh xạ định lƣợng ngữ nghĩa v mỗi điểm của mô hình mờ trên có thể đƣợc biểu... nghĩa, việc giải định lượng đầu ra của phép nội suy sẽ cho kết quả lập luận Phƣơng pháp lập luận mờ sử dụng ĐSGT hàm chứa rất nhiều các yếu tố mở cho ngƣời sử dụng lựa chọn nhƣ: i) Chọn các tham số của các đại số gia tử: Phƣơng pháp lập luận sử dụng các ánh xạ Xi và Y để định lƣợng giá trị ngôn ngữ Tuy nhiên các ánh xạ định lƣợng này đƣợc xây dựng dựa trên các tham số của các ĐSGT AXi, i = 1, , m+1,... hành khử mờ theo phƣơng pháp lấy max, ta tìm đƣợc giá trị lớn nhất 0.9 và vị trí lớn nhất 2, do đó giá trị khử mờ 2000 Phƣơng pháp lập luận mờ đa điều kiện đƣợc ứng dụng trong việc xây dựng các hệ mờ dựa tập luật, trên thực tế đã có một loạt các hệ mờ đã đƣợc xây dựng và ứng dụng trong thực tế nhƣ các hệ chuyên gia, các hệ trợ giúp quyết định, các hệ điều khiển,… Hiệu quả của phƣơng pháp lập luận mờ nói... sinh từ thứ tự giữa các phần tử trong {hix: – q  i  p, i  0} Ta gọi J(x) là khoảng mờ của phần tử x, và kí hiệu  = {J(x) : x  X} là tập các khoảng mờ của X Sau đây là ví dụ về hệ khoảng mờ liên kết với fm của đại số gia tử với 2 phần tử sinh là True và False, tập các gia tử gồm Litle, Poss, More, Very Hỉnh 1.2 Ví dụ về hệ khoảng mờ Trên cơ sở định nghĩa hệ khoảng mờ việc định lƣợng giá trị cho... trong những yếu tố ảnh hƣởng đến phƣơng pháp là các tham số của các ĐSGT: + Độ đo tính mờ của các phần tử sinh: fmAXi(c), fmAXi(c+) thỏa fmAXi(c) + fmAXi(c+) = 1; + Độ đo tính mờ của các gia tử:  AXi (h j ) thỏa  j  q  AXi (h j )   , 1 i  pi j 1  AXi (h j )   ,  +  = 1; Thông thƣờng ngƣời ta hay sử dụng trực giác để chọn các tham số này, Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/... những ứng dụng thực tiễn quan trọng Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 10 Một trong số những phƣơng pháp lập nhƣ vậy là các phƣơng pháp lập luận mờ đa điều kiện (Fuzzy Multiple Conditional Reasoning - FMCR) nhằm giải quyết bài toán lập luận mờ đa điều kiện sau: Cho trƣớc mô hình mờ ở dạng (1.1) hoặc (1.2) Khi đó ứng với các giá trị (hoặc giá trị mờ, hoặc giá trị thực) của các biến... khử mờ theo tham số  nhƣ sau: n x*   x (x )  i 1 n i i  (x ) ,   0,    i i 1 Một số dạng khử mờ đƣợc sử dụng khi U là tập số thực   = 1, ta có phƣơng pháp trọng tâm   , x* đƣợc tính theo phƣơng pháp cực đại Giả sử x1, , xk là các giá trị mà tại đó hàm  đạt giá trị cực đại, khi đó: k x  * x i 1 i k  Phƣơng pháp điểm giữa x* = (x1 + xk)/2 Lƣu ý rằng khi chọn phƣơng pháp khử mờ. .. hãy tính giá trị của biến đầu ra Y Dựa trên cách tiếp cận của lý thuyết tập mờ, các phƣơng pháp lập luận mờ đa điều kiện nói chung dựa trên ý tƣởng sau: - Ngữ nghĩa của các giá trị ngôn ngữ của các biến ngôn ngữ trong mô hình mờ đƣợc biểu thị bằng các tập mờ - Kết nhập các đầu vào của các luật mờ trong mô hình (nếu n > 1) để chuyển mô hình mờ về mô hình đơn điều kiện - Từ các luật mờ dạng if – then... còn đƣợc gọi là mô hình mờ đơn điều kiện và (1.2) đƣợc gọi là mô hình mờ đa điều kiện, ngoài ra (1.2) còn đƣợc gọi là bộ nhớ kết hợp mờ (Fuzzy Associate Memory - FAM) vì nó biểu diễn tri thức của chuyên gia trong lĩnh vực ứng dụng nào đó đang đƣợc xét 1.2.2 Phƣơng pháp lập luận mờ đa điều kiện Trên cơ sở lý thuyết tập mờ, từ những năm 60 của thế kỷ trƣớc, các phƣơng pháp lập luận xấp xỉ đã đƣợc phát... tiếp theo ta tiến hành mờ hóa các đầu vào theo nguyên tắc mờ hóa đơn trị (Singleton): Cụ thể với x=20 đƣợc mờ hóa thành tập mờ A0=[0 1 0 0], Với y=300 đƣợc mờ hóa thành tập mờ B0=[0 0 1] Tiến hành kết nhập 2 đầu vào A0, B0 bằng cách lấy tích đề các mờ A0B0=[0 0 0 0 0 1 0 0 0 0 0 0] Tính tập mờ đầu ra C0= A0B0oR với o là phéo hợp thành max-min, ta có: C0=[0.60 0.90 0.90 0.60 0.50] Số hóa bởi Trung tâm Học . CHƢƠNG 3: TỐI ƢU HÓA THAM SỐ CỦA PHƢƠNG PHÁP LẬP LUẬN MỜ SỬ DỤNG ĐẠI SỐ GIA TỬ BẰNG GIẢI THUẬT DI TRUYỀN 47 3.1. Giải pháp tối ƣu hóa tham số của phƣơng pháp lập luận mờ sử dụng đại số gia tử …47. bản về đại số gia tử, phƣơng pháp lập luận mờ sử dụng đại số gia tử. - Nghiên cứu ứng dụng giải thuật di truyền để tối ƣu hóa các tham số trong phƣơng pháp lập luận mờ sử dụng đại số gia tử. . ƣu hóa các tham số trong phƣơng pháp lập luận mờ sử dụng đại số gia tử. Mục tiêu của đề tài - Nghiên cứu các khái niệm cơ bản về đại số gia tử, phƣơng pháp lập luận mờ sử dụng đại số gia tử.