Bài tiểu luận: Logic mờ và ứng dụng vào việc xác định thời gian đề thi trắc nghiệm khách quan tự động

pdf
Số trang Bài tiểu luận: Logic mờ và ứng dụng vào việc xác định thời gian đề thi trắc nghiệm khách quan tự động 43 Cỡ tệp Bài tiểu luận: Logic mờ và ứng dụng vào việc xác định thời gian đề thi trắc nghiệm khách quan tự động 1 MB Lượt tải Bài tiểu luận: Logic mờ và ứng dụng vào việc xác định thời gian đề thi trắc nghiệm khách quan tự động 1 Lượt đọc Bài tiểu luận: Logic mờ và ứng dụng vào việc xác định thời gian đề thi trắc nghiệm khách quan tự động 58
Đánh giá Bài tiểu luận: Logic mờ và ứng dụng vào việc xác định thời gian đề thi trắc nghiệm khách quan tự động
4.3 ( 6 lượt)
Nhấn vào bên dưới để tải tài liệu
Đang xem trước 10 trên tổng 43 trang, để tải xuống xem đầy đủ hãy nhấn vào bên trên
Chủ đề liên quan

Nội dung

ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN TIỂU LUẬN TOÁN HỌC CHO KHOA HỌC MÁY TÍNH Đề tài: LOGIC MỜ VÀ ỨNG DỤNG VÀO VIỆC XÁC ĐỊNH THỜI GIAN ĐỀ THI TRẮC NGHIỆM KHÁCH QUAN TỰ ĐỘNG Giảng viên hướng dẫn: TS. DƯƠNG TÔN ĐẢM Học viên thực hiện: Lê Bảo Trung CH1301112 Lâm Hàn Vũ CH1301119 Nguyễn Văn Kiệt CH1301095 UIT, ngày 26 tháng 11 năm 2014 TOÁN HỌC CHO KHOA HỌC MÁY TÍNH GVHD: TS. DƯƠNG TÔN ĐẢM MỤC LỤC MỤC LỤC ................................................................................................................................. 2 LỜI CẢM ƠN ........................................................................................................................... 4 CHƯƠNG 1. KHÁI QUÁT VỀ LOGIC MỜ (FUZZY LOGIC) .............................................. 5 1.1. Lịch sử hình thành và phát triển của Logic mờ ............................................................. 5 1.2. Khái niệm về logic mờ .................................................................................................. 6 CHƯƠNG 2. LOGIC MỜ VÀ CƠ CHẾ SUY DIỄN MỜ........................................................ 8 2. 1. Tập mờ .......................................................................................................................... 8 2.1.1. Định nghĩa ............................................................................................................... 8 2.1.2. Các phép toán trên tập mờ ...................................................................................... 8 2.1.3. Độ cao, miền xác định và miền tin cậy của tập mờ................................................. 9 2. 2. Logic mờ ..................................................................................................................... 10 2.2.1. Các phép toán cơ bản của logic mờ ...................................................................... 10 2.2.1.1. 2.2.1.2. 2.2.1.3. 2.2.1.4. Phép hợp (hay toán tử OR) ............................................................ 10 Phép giao (hay toán tử AND) ........................................................ 11 Phép bù (hay toán tử NOT) ........................................................... 12 Các phép toán mở rộng.................................................................. 12 2.2.2. Quan hệ mờ ........................................................................................................... 15 2.2.2.1. 2.2.2.2. Khái niệm quan hệ mờ .................................................................. 15 Phép hợp thành .............................................................................. 15 2. 3. Số mờ .......................................................................................................................... 16 2.3.1. Định nghĩa ............................................................................................................. 16 2.3.2. Các phép toán........................................................................................................ 17 2.3.3. Nguyên lý suy rộng của Zadeh .............................................................................. 17 2. 4. Cơ chế suy diễn mờ ..................................................................................................... 18 2.4.1. Biến ngôn ngữ ....................................................................................................... 18 2.4.2. Mệnh đề mờ ........................................................................................................... 19 2.4.3. Các phép toán mệnh đề mờ ................................................................................... 19 2.4.4. Phép toán kéo theo mờ .......................................................................................... 20 2.4.5. Tập luật mờ ........................................................................................................... 21 2.4.6. Phương pháp lập luận xấp xỉ dựa trên tập mờ ..................................................... 21 2.4.7. Phép suy diễn mờ .................................................................................................. 24 2. 5. Mờ hóa và giải mờ ...................................................................................................... 26 2.5.1. Mờ hóa .................................................................................................................. 26 2.5.1.1. 2.5.1.2. Bộ mờ hóa Singleton (đơn trị)....................................................... 26 Bộ mờ hóa Gaussian ...................................................................... 26 2 LOGIC MỜ VÀ ỨNG DỤNG VÀO VIỆC XÁC ĐỊNH THỜI GIAN ĐỀ THI TRẮC NGHIỆM KHÁCH QUAN TỰ ĐỘNG TOÁN HỌC CHO KHOA HỌC MÁY TÍNH 2.5.1.3. GVHD: TS. DƯƠNG TÔN ĐẢM Bộ mờ hóa tam giác ....................................................................... 26 2.5.2. Giải mờ .................................................................................................................. 27 2.5.2.1. 2.5.2.2. 2.5.2.3. Phương pháp cực đại ..................................................................... 27 Nguyên lý trung bình:.................................................................... 28 Nguyên lý cận trái ......................................................................... 28 2.5.2.4. 2.5.2.5. Nguyên lý cận phải ........................................................................ 28 Phương pháp điểm trọng tâm ........................................................ 29 2.5.2.6. 2.5.2.7. Phương pháp điểm trọng tâm cho luật hợp thành SUM-MIN ...... 30 Phương pháp độ cao ...................................................................... 30 CHƯƠNG 3. ỨNG DỤNG LOGIC MỜ VÀO VIỆC XÁC ĐỊNH THỜI GIAN LÀM BÀI THI TRẮC NGHIỆM KHÁCH QUAN ......................................................................................... 31 3. 1. Giới thiệu chung .......................................................................................................... 31 3. 2. Mờ hóa dữ liệu ............................................................................................................ 31 3.2.1. Đầu vào “Độ khó của đề thi” (K) ......................................................................... 31 3.2.2. Đầu vào “Số lượng câu hỏi” (C) .......................................................................... 32 3.2.3. Đầu ra “Thời gian làm bài thi” (T) ...................................................................... 32 3.2.4. Bảng quyết định ..................................................................................................... 32 3. 3. Các hàm thành viên ..................................................................................................... 32 3.3.1. Hàm thành viên cho Độ khó K(x) .......................................................................... 32 3.3.2. Hàm thành viên cho Số lượng câu hỏi C(y) .......................................................... 33 3.3.3. Hàm thành viên cho Thời gian làm bài thi T(z) .................................................... 33 3. 4. Lập luận mờ: ............................................................................................................... 34 3. 5. Giải mờ ........................................................................................................................ 35 CHƯƠNG 4. CÀI ĐẶT, THỬ NGHIỆM VÀ ĐÁNH GIÁ .................................................... 30 CHƯƠNG 5. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ........................................................ 32 TÀI LIỆU THAM KHẢO ....................................................................................................... 33 PHỤ LỤC ................................................................................................................................ 34 HƯỚNG DẪN SỬ DỤNG WEBSITE DEMO....................................................................... 34 3 LOGIC MỜ VÀ ỨNG DỤNG VÀO VIỆC XÁC ĐỊNH THỜI GIAN ĐỀ THI TRẮC NGHIỆM KHÁCH QUAN TỰ ĐỘNG TOÁN HỌC CHO KHOA HỌC MÁY TÍNH GVHD: TS. DƯƠNG TÔN ĐẢM LỜI CẢM ƠN Chúng em xin chân thành gửi lời cảm ơn chân thành đến TS. Dương Tôn Đảm, người thầy giảng dạy và hướng dẫn khoa học nghiêm túc và nhiệt tâm. Thầy là người đã truyền đạt cho chúng em những kiến thức quý báu trong môn học “Toán cho Khoa học máy tính”. Nhờ có những kiến thức của Thầy mà chúng em có thể có đủ kiến thức cùng với những công cụ cần thiết để thực hiện bài tiểu luận này. Được học tập và được truyền thụ kiến thức trong môn “Toán học cho Khoa học máy tính” cùng với thời gian nghiên cứu, tìm hiểu từ các tài liệu và Internet. Em chọn tìm hiểu về logic mờ và ứng dụng logic mờ vào việc xác định thời gian làm bài thi trắc nghiệm khách quan để làm tiểu luận môn học. Đây cũng là một nội dung mới và có liên quan đến lĩnh vực hiện tại chúng em đang công tác trong ngành giáo dục. Nội dung của tiểu luận này được thể hiện qua 4 chương, bao gồm: Chương 1: Khái quát về Logic mờ (fuzzy logic); Chương 2: Logic mờ và cơ chế suy diễn mờ; Chương 3: Ứng dụng logic mờ vào việc xác định thời gian làm bài thi trắc nghiệm khách quan; Chương 4: Cài đặt, thử nghiệm và đánh giá; Chương 5: Kết luận và hướng phát triển; Do thời gian và khả năng nghiên cứu có hạn nên tiểu luận này chắc chắn sẽ không tránh khỏi những thiếu sót nhất định. Kính mong được sự thông cảm và góp ý của Thầy để hướng nghiên cứu sắp tới của em sẽ hoàn thiện và đạt hiệu quả hơn. Em xin cảm ơn. Học viên thực hiện Lê Bảo Trung Lâm Hàn Vũ Nguyễn Văn Kiệt 4 LOGIC MỜ VÀ ỨNG DỤNG VÀO VIỆC XÁC ĐỊNH THỜI GIAN ĐỀ THI TRẮC NGHIỆM KHÁCH QUAN TỰ ĐỘNG TOÁN HỌC CHO KHOA HỌC MÁY TÍNH GVHD: TS. DƯƠNG TÔN ĐẢM CHƯƠNG 1. KHÁI QUÁT VỀ LOGIC MỜ (FUZZY LOGIC) 1.1. Lịch sử hình thành và phát triển của Logic mờ Logic mờ được công bố lần đầu tiên tại Mỹ vào năm 1965 do giáo sư Lotfi Zadeh. Kể từ đó, logic mờ đã có nhiều phát triển qua các chặng đường sau : phát minh ở Mỹ, áp dụng ở Châu Âu và đưa vào các sản phẩm thương mại ở Nhật. Ứng dụng đầu tiên của logic mờ vào công nghiệp được thực hiện ở Châu Âu, khoảng sau năm 1970. Tại trường Queen Mary ở Luân Đôn – Anh, Ebrahim Mamdani dùng logic mờ để điều khiển một máy hơi nước mà trước đây ông ấy không thể điều khiển được bằng các kỹ thuật cổ điển. Và tại Đức, Hans Zimmermann dùng logic mờ cho các hệ ra quyết định. Liên tiếp sau đó, logic mờ được áp dụng vào các lĩnh vực khác như điều khiển lò xi măng, … nhưng vẫn không được chấp nhận rộng rãi trong công nghiệp. Kể từ năm 1980, logic mờ đạt được nhiều thành công trong các ứng dụng ra quyết định và phân tích dữ liệu ở Châu Âu. Nhiều kỹ thuật logic mờ cao cấp được nghiên cứu và phát triển trong lĩnh vực này. Cảm hứng từ những ứng dụng của Châu Âu, các công ty của Nhật bắt đầu dùng logic mờ vào kỹ thuật điều khiển từ năm 1980. Nhưng do các phần cứng chuẩn tính toán theo giải thuật logic mờ rất kém nên hầu hết các ứng dụng đều dùng các phần cứng chuyên về logic mờ. Một trong những ứng dụng dùng logic mờ đầu tiên tại đây là nhà máy xử lý nước của Fuji Electric vào năm 1983, hệ thống xe điện ngầm của Hitachi vào năm 1987. Những thành công đầu tiên đã tạo ra nhiều quan tâm ở Nhật. Có nhiều lý do để giải thích tại sao logic mờ được ưa chuộng. Thứ nhất, các kỹ sư Nhật thường bắt đầu từ những giải pháp đơn giản, sau đó mới đi sâu vào vấn đề. Phù hợp với việc logic mờ cho phép tạo nhanh các bản mẫu rồi tiến đến việc tối ưu. Thứ hai, các hệ dùng logic mờ đơn giản và dễ hiểu. Sự “thông minh” của hệ không nằm trong các hệ phương trình vi phân hay mã nguồn. Cũng như việc các kỹ sư Nhật thường làm việc theo tổ, đòi hỏi phải có một giải pháp để mọi người trong tổ đều hiểu được hành vi của hệ thống, cùng chia sẽ ý tưởng để tạo ra hệ. Logic mờ cung cấp cho họ một phương tiện rất minh bạch để thiết kế 5 LOGIC MỜ VÀ ỨNG DỤNG VÀO VIỆC XÁC ĐỊNH THỜI GIAN ĐỀ THI TRẮC NGHIỆM KHÁCH QUAN TỰ ĐỘNG TOÁN HỌC CHO KHOA HỌC MÁY TÍNH GVHD: TS. DƯƠNG TÔN ĐẢM hệ thống. Và cũng do nền văn hóa, người Nhật không quan tâm đến logic Boolean hay logic mờ; cũng như trong tiếng Nhật, từ “mờ’ không mang nghĩa tiêu cực. Do đó, logic mờ được dùng nhiều trong các ứng dụng thuộc lĩnh vực điều khiển thông minh hay xử lý dữ liệu. Máy quay phim và máy chụp hình dùng logic mờ để chứa đựng sự chuyên môn của người nghệ sĩ nhiếp ảnh. Misubishi thông báo về chiếc xe đầu tiên trên thế giới dùng logic mờ trong điều khiển, cũng như nhiều hãng chế tạo xe khác của Nhật dùng logic mờ trong một số thành phần. Trong lĩnh vực tự động hóa, Omron Corp. có khoảng 350 bằng phát minh về logic mờ. Ngoài ra, logic mờ cũng được dùng để tối ưu nhiều quá trình hóa học và sinh học. Năm năm trôi qua, các tổ hợp Châu Âu nhận ra rằng mình đã mất một kỹ thuật chủ chốt vào tay người Nhật và từ đó họ đã nỗ lực hơn trong việc dùng logic mờ vào các ứng dụng của mình. Đến nay, có khoảng 200 sản phẩm bán trên thị trường và vô số ứng dụng trong điều khiển quá trình – tự động hóa dùng logic mờ. Từ những thành công đạt được, logic mờ đã trở thành một kỹ thuật thiết kế “chuẩn” và được chấp nhận rộng rãi trong cộng đồng. Trong những năm gần đây, lý thuyết logic mờ đã có nhiều áp dụng thành công trong lĩnh vực điều khiển. Bộ điều khiển dựa trên lý thuyết logic mờ gọi là bộ điều khiển mờ. Trái với kỹ thuật điều khiển kinh điển, kỹ thuật điều khiển mờ thích hợp với các đối tượng phức tạp, không xác định mà người vận hành có thể điều khiển bằng kinh nghiệm. Đặc điểm của bộ điều khiển mờ là không cần biết mô hình toán học mô tả đặc tính động của hệ thống mà chỉ cần biết đặc tính của hệ thống dưới dạng các phát biểu ngôn ngữ. Đồng thời chất lượng của bộ điều khiển mờ phụ thuộc rất nhiều vào kinh nghiệm của người thiết kế. 1.2. Khái niệm về logic mờ Logic mờ có hai cách hiểu khác nhau:  Theo nghĩa hẹp có thể xem logic mờ là hệ thống logic được mở rộng từ logic đa trị (khác với logic cổ điển dựa trên đại số Bool). 6 LOGIC MỜ VÀ ỨNG DỤNG VÀO VIỆC XÁC ĐỊNH THỜI GIAN ĐỀ THI TRẮC NGHIỆM KHÁCH QUAN TỰ ĐỘNG TOÁN HỌC CHO KHOA HỌC MÁY TÍNH GVHD: TS. DƯƠNG TÔN ĐẢM  Tổng quát hơn, logic mờ hoàn toàn gắn liền với lý thuyết về tập mờ. Một lý thuyết liên quan đến việc phân nhóm các đối tượng bởi một đường bao mờ, việc xác định một đối tượng có thuộc vào một nhóm hay không sẽ dựa vào giá trị của hàm phụ thuộc cho bởi nhóm đó (giá trị đầu vào không cần phải là giá trị số mà có thể là ngôn ngữ thường ngày). Như vậy, có thể nói logic mờ hiểu theo nghĩa hẹp chỉ là một trường hợp đặc biệt của logic mờ tổng quát. Một điều quan trọng là ngay cả khi hiểu logic mờ theo nghĩa hẹp thì những thao tác trong logic mờ cũng khác về ý nghĩa lẫn phương pháp so với logic cổ điển dựa trên đại số Bool. Một khái niệm rất thường dùng trong logic mờ là biến ngôn ngữ. Biến ngôn ngữ là những biến chứa giá trị là chữ thay vì là số. Có thể hiểu logic mờ theo nghĩa tổng quát là một phương pháp tính toán trên các giá trị chữ thay vì là tính toán trên giá trị số như các trường phái cổ điển. Mặc dù các giá trị ngôn ngữ vốn đã không chính xác bằng các giá trị số nhưng nó lại gần với trực giác của con người. Hơn nữa, việc tính toán trên các giá trị ngôn ngữ cho phép chấp nhận tính mơ hồ của dữ liệu nhập do đó dẫn đến giải pháp ít tốn kém hơn. 7 LOGIC MỜ VÀ ỨNG DỤNG VÀO VIỆC XÁC ĐỊNH THỜI GIAN ĐỀ THI TRẮC NGHIỆM KHÁCH QUAN TỰ ĐỘNG TOÁN HỌC CHO KHOA HỌC MÁY TÍNH GVHD: TS. DƯƠNG TÔN ĐẢM CHƯƠNG 2. LOGIC MỜ VÀ CƠ CHẾ SUY DIỄN MỜ 2. 1. Tập mờ Để hiểu rõ khái niệm “MỜ” là gì ta hãy thực hiện phép so sánh sau: Trong toán học phổ thông ta đã học khá nhiều về tập hợp, ví dụ như các tập số thực R, tập số nguyên tố P = 2,3,5,...... Những tập hợp như vậy được gọi là tập hợp kinh điển hay tập rõ, tính “RÕ” ở đây được hiểu là với một tập xác định S chứa n phần tử thì ứng với phần tử x ta xác định được một giá trị y = S(x). Giờ ta xét phát biểu thông thường về tốc độ một chiếc xe môtô: Chậm, trung bình, hơi nhanh, rất nhanh. Phát biểu “CHẬM” ở đây không được chỉ rõ là bao nhiêu km/h, như vậy từ “CHẬM” có miền giá trị là một khoảng nào đó, ví dụ 5 km/ h – 20km/h chẳng hạn. Tập L = chậm, trung bình, hơi nhanh, rất nhanh như vậy được gọi là một tập các biến ngôn ngữ. Với mỗi thành phần ngôn ngữ xk của phát biểu trên nếu nó nhận được một khả năng F(xk) thì tập F gồm các cặp (x, F(xk)) được gọi là tập mờ. 2.1.1. Định nghĩa Tập mờ F xác định trên tập kinh điển X là một tập mà mỗi phần tử của nó là một cặp các giá trị (x, F(x)) trong đó xX và F là ánh xạ: F:X0;1 (2.2) Ánh xạ F được gọi là hàm thuộc (hoặc hàm phụ thuộc) của tập mờ F. Tập không gian X được gọi là nền của tập mờ F. Sử dụng các hàm phụ thuộc để tính độ phụ thuộc của một phần tử x nào đó có hai cách:  Tính trực tiếp (nếu F(x) cho trước dưới dạng công thức tường minh)  Tra bảng (nếu F(x) cho dưới dạng bảng) 2.1.2. Các phép toán trên tập mờ Cho A, B là hai tập mờ trên không gian nền X có các hàm thuộc tương ứng là A, B, khi đó:  Phép hợp hai tập mờ: A ∪ B  Theo luật Max:  A B (x) = Max  A (x),  B (x) 8 LOGIC MỜ VÀ ỨNG DỤNG VÀO VIỆC XÁC ĐỊNH THỜI GIAN ĐỀ THI TRẮC NGHIỆM KHÁCH QUAN TỰ ĐỘNG TOÁN HỌC CHO KHOA HỌC MÁY TÍNH GVHD: TS. DƯƠNG TÔN ĐẢM  Theo luật Sum:  A B (x) = Min1,  A (x) +  B (x)  Tổng trực tiếp:  A B (x) =  A (x) +  B (x) -  A (x).  B (x)  Phép giao hai tập mờ: A ∩ B  Theo luật Min:  A B (x) = Min  A (x),  B (x)  Theo luật Lukasiewicz:  A B (x) = Max0,  A (x) +  B (x) - 1  Theo luật Prod:  A B (x) =  A (x).  B (x)  Phép bù tập mờ: μ¬A(x) = 1 – μA(x) 2.1.3. Độ cao, miền xác định và miền tin cậy của tập mờ  Độ cao (độ phụ thuộc) của một tập mờ F (được định nghĩa trên không gian X) là giá trị: Một tập mờ có ít nhất một phần tử có độ phụ thuộc bằng 1 được gọi là tập mờ chính tắc, tức là H = 1, ngược lại một tập mờ F với H < 1 được gọi là tập mờ không chính tắc.  Miền xác định của tập mờ F (được định nghĩa trên không gian X), được ký hiệu bởi S, là tập con của X thoả mãn: S =  xX  F(x) >0   Miền tin cậy của tập mờ F (được định nghĩa trên không gian X), được ký hiệu bởi T, là tập con của X thoả mãn: T =  xX  F(x) =1  Hình 2.1: Ví dụ về miền xác định và miền tin cậy của tập mờ 9 LOGIC MỜ VÀ ỨNG DỤNG VÀO VIỆC XÁC ĐỊNH THỜI GIAN ĐỀ THI TRẮC NGHIỆM KHÁCH QUAN TỰ ĐỘNG TOÁN HỌC CHO KHOA HỌC MÁY TÍNH 2. 2. GVHD: TS. DƯƠNG TÔN ĐẢM Logic mờ Logic mờ cho phép lập luận trên các đối tượng thực tế được định nghĩa không rõ ràng. Trong logic mờ, chỉ có các đối tượng xấp xỉ chứ không có các đối tượng chính xác, do đó các kiểu lập luận cũng là xấp xỉ. Mọi thứ trong logic mờ, kể cả giá trị chân lý (true value) đều là các độ đo (degree) trong khoảng [0, 1] hay là một nhãn nào đó như đúng, rất đúng, sai, ít sai hơn, … 2.2.1. Các phép toán cơ bản của logic mờ Ta có 3 toán tử logic trên tập mờ quan trọng sau: OR, AND, NOT 2.2.1.1. Phép hợp (hay toán tử OR) Hình 2.2. Hàm liên thuộc của hợp hai tập mờ cùng cơ sở Phép hợp hay toán tử logic OR của hai tập mờ A và B có cùng tập nền X là một tập mờ A∪B thể hiện mức độ một phần tử thuộc về một trong hai tập là bao nhiêu cũng được xác định trên nền X có hàm thuộc μA∪B(x) được tính bằng công thức: μA∪B(x) = max {μA(x), μB(x)} Ví dụ 2.1: μTrẻ(An) = 0.8 và μTrung niên(An) = 0.3  μTrẻ ∪ Trung Niên(An) = max( 0.8, 0.3) = 0.8 10 LOGIC MỜ VÀ ỨNG DỤNG VÀO VIỆC XÁC ĐỊNH THỜI GIAN ĐỀ THI TRẮC NGHIỆM KHÁCH QUAN TỰ ĐỘNG
This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.