Luận văn Xây dựng chế độ dinh dưỡng tại trường mầm non bằng logic mờ kết hợp mạng neural và máy học

............................................................................................................................................................... ....................................................................................................................................................................................................... ....................................................................................................................................................................................................... ....................................................................................................................................................................................................... ....................................................................................................................................................................................................... ....................................................................................................................................................................................................... ....................................................................................................................................................................................................... ....................................................................................................................................................................................................... ....................................................................................................................................................................................................... ....................................................................................................................................................................................................... ....................................................................................................................................................................................................... ....................................................................................................................................................................................................... ....................................................................................................................................................................................................... ....................................................................................................................................................................................................... ....................................................................................................................................................................................................... ....................................................................................................................................................................................................... Tp. Hồ Chí Minh, ngày ...... tháng ...... năm 2006 Giáo viên hướng dẫn Th.S. Phạm Thế Bảo 2 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM LỜI CẢM ƠN Chúng em xin bày tỏ lòng biết ơn sâu sắc đến Th.S Phạm Thế Bảo, dù rất bận rộn nhưng thầy luôn quan tâm và tận tình hướng dẫn cho chúng em trong suốt quá trình thực hiện luận văn ; thầy đã giúp đỡ chúng em rất nhiều trong quá trình học tập và gợi mở cho chúng em đến với đề tài này. Chúng em chân thành cảm ơn thầy Phạm Thi Vương và thầy Nguyễn Hiền Lương, các thầy đã giúp đỡ chúng em rất nhiều trong quá trình thực hiện đề tài và cung cấp cho chúng em nhiều tài liệu tham khảo có giá trị để chúng em thực hiện tốt khóa luận này. Xin chân thành cám ơn quý Thầy Cô trong khoa Toán – Tin học đã tận tình giảng dạy, trang bị cho chúng em những kiến thức quý báu trong suốt quá trình học tập và thực hiện đề tài. Cuối cùng xin chân thành cám ơn anh Phan Phúc Doãn và các bạn cùng lớp đã có những ý kiến đóng góp bổ ích giúp chúng em hoàn thành luận văn.. Tp Hồ Chí Minh, ngày 10/7/2006 3 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM MỤC LỤC Trang Lời Cảm Ơn 3 Mục Lục 4 Danh Mục Bảng Biểu, Hình Ảnh 5 Bảng Ký Hiệu Các Chữ Viết Tắt 6 Chương 1 TỔNG QUAN 1.1 Đặt vấn đề 9 1.2 Các hướng giải quyết trong AI 9 1.3 Lý do sử dụng FL . 18 1.4 Kết hợp FL với các kỹ thuật AI khác .... 19 Chương 2 CƠ SỞ LÝ THUYẾT 2.1 Logic mờ 2.1.1 Tập mờ . 22 2.1.2 Hàm thành viên 24 2.1.3 Toán tử tập mờ . 28 2.1.4 Luật mờ 40 2.1.5 Hệ thống vào/ra 42 2.1.6 Mô hình suy luận mờ 44 2.1.7 Khử mờ . 48 2.1.8 Hệ thống mờ - bộ điều khiển mờ 49 2.1.9 Cách lựa chọn logic mờ cho từng hệ thống xây dựng 52 2.2 Khái quát về máy học... 54 2.3 Khái quát về mạng neural.. ..57 Chương 3 XÂY DỰNG THUẬT GIẢI 3.1 Quy định chế độ dinh dưỡng trẻ em . 63 3.2 Nguyên tắc và các bước xây dựng thực đơn ở trường mầm non 63 3.3 Xây dựng tập mờ và hàm thành viên.... 66 3.4 Xây dựng bộ lọc mờ bằng kỹ thuật máy học . 75 3.5 Mạng neural kết hợp hệ mờ phát sinh luật và điều chỉnh trọng số.. 81 Chương 4 CÀI ĐẶT VÀ ĐÁNH GIÁ 4.1 Cài đặt . 4.1.1 Phân tích – Thiết kế.. 86 4.1.2 Mô hình. 94 4. 2 Đánh giá và hướng phát triển . 99 Tài liệu tham khảo 101 4 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM DANH MỤC BẢNG BIỂU, HÌNH ẢNH Trang Hình 1-1 . Các bước giải quyết một vấn đề 18 Hình 2-1 . Hệ thống mờ và nền tảng kiến thức liên quan 22 Hình 2-2 . Ví dụ minh họa đồ thị hàm thành viên 24 Hình 2-3 . Đường biểu diễn của hàm đặc trưng và hàm thành viên của tập những người cao 25 Hình 2-4 . Hàm S tăng 26 Hình 2-5 . Hàm dạng chuông 26 Hình 2-6 . Sử dụng toán tử hội mờ 28 Hình 2-7 . Sử dụng toán tử giao mờ 28 Hình 2-8 . Toán tử bù mờ 29 Hình 2-9 . Các toán tử AND và OR 32 Hình 2-10 . Bốn toán tử t-norm chuẩn 33 Hình 2-11 . Ví dụ về bốn toán tử t-norm chuẩn. 34 Hình 2-12 . Toán tử t-norm Nilpotent Minimum 34 Hình 2-13 . Toán tử t-norm thuộc họ Frank 35 Hình 2-14 . Toán tử t-norm thuộc Họ Hamacher 36 Hình 2-15 . Toán tử t-norm thuộc Họ Schweizer-Sklar 37 Hình 2-16 . Toán tử t-norm thuộc Họ Yager 37 Hình 2-17 . Bốn toán tử t-conorm S chuẩn 38 Hình 2-18 . Ví dụ về bốn toán tử t-conorm chuẩn 39 Hình 2-19 . Phân nhóm các bộ điều khiển theo số tín hiệu vào ra 42 Hình 2-20 . Luật hợp thành là bộ não của điều khiển mờ 43 Hình 2-21 . Hàm thành viên cho biến ngôn ngữ đầu vào có giá trị small, medium và large 45 Hình 2-22 . Hàm thành viên cho biến đầu ra có giá trị small, medium và large 45 Hình 2-23 . Hàm thành viên cho “Small” , “Medium” và “Large” 47 Hình 2-24 . Cấu trúc của hệ thống mờ chuẩn 49 Hình 2-25 . Cấu trúc của bộ xử lý mờ kết hợp khâu giải mờ và khử mờ 50 Hình 2-26 . Cấu trúc của một bộ điều khiển mờ 50 Hình 2-27 . Bộ điều khiển mờ cổ điển (Hình a) và bộ điều khiển mờ phân tán (Hình b) 51 Bảng 2-28 . So sánh mạng neural và bộ điều khiển mờ 60 Hình 3-1. Factor “lượng calo” đối với nhóm nhà trẻ 69 Hình 3-2. Factor lượng calo đối với nhóm mẫu giáo 69 Hình 3-3. Factor “tỉ lệ protein” đối với chuẩn một 70 Hình 3-4. Factor “tỉ lệ lipit” đối với chuẩn một 70 Hình 3-5. Factor “tỉ lệ gluxit” đối với chuẩn một 71 Hình 3-6. Factor “tỉ lệ protein” đối với chuẩn hai 71 Hình 3-7. Factor “tỉ lệ lipit” đối với chuẩn hai 72 Hình 3-8. Factor “tỉ lệ gluxit” đối với chuẩn hai 72 Hình 3-9. Mô hình bộ điều khiển mờ thứ nhất 73 Hình 3-10 Mô hình bộ điều khiển mờ thứ hai 73 Hình 3-11. Factor “tỉ lệ dinh dưỡng” 74 Hình 3-12. Factor “giá tiền” 74 5 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM Hình 3-13. Factor “độ dùng lại” 75 Hình 3-14. Phân khoảng giá trị mẫu 79 Hình 3-15. Sử dụng dữ liệu mẫu để xây dựng cây quyết định 80 Hình 3-16. Sử dụng cây quyết định để lọc dữ liệu 81 Hình 4-1. Giao diện chính của chương trình. 87 Hình 4-2. Sắp lịch ăn trưa trong một tuần. 88 Hình 4-3. Sắp lịch ăn trưa trong một tháng. 89 Hình 4-4. Hiển thị các danh sách các món ăn trong một ngày. 90 Hình 4-5. Hiển thị danh sách các món ăn trong một tuần 91 Hình 4-6. Hiển thị danh sách các món ăn trong một tháng. 92 Hình 4-7. Báo cáo chi tiết của một bữa ăn trưa trong ngày. 93 Hình 4-8. Mô hình ERD 94 Hình 4-9. Mô hình DFD 95 Hình 4-10. Chi tiết ô xử lý “xếp lịch” 96 Hình 4-11. Chi tiết ô xử lý “cập nhật món ăn” 96 Hình 4.12. Chi tiết ô xử lý “cập nhật nguyên liệu” 97 Hình 4-13. Chi tiết ô xử lý “in ấn, báo cao” 97 Hình 4-14. Chi tiết ô xử ly “tra cứu” 98 Hình 4-15. Chi tiết ô xử lý “quản lý hệ thống” 98 Hình 4-16. Mô hình ràng buộc dữ liệu 99 6 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM BẢNG KÍ HIỆU CÁC CHỮ VIẾT TẮT FL Fuzzy Logic Logic mờ MF Member function Hàm thành viên χ Hàm đặc trưng µ Hàm thành viên X Không gian nền A,B, Các tập mờ x,y, các biến ngôn ngữ AI Artificial Intelligence Trí tuệ nhân tạo ID3 The third in a series Thuật toán cây quyết đinh ID3 of identification ERD Entity Relationship Mô hình thực thể quan hệ Diagrams DFD Data Flow Diagrams Sơ đồ luồng dữ liệu ANFIS Adaptive Network Based Hệ mờ thích nghi Fuzzy Inference System MIMO Multi Input – Multi Output Bộ điều khiển mờ SISO Single Input – Single Output Bộ điều khiển mờ MISO Multi Input – Single Output Bộ điều khiển mờ TS Tagagi – Sugeno Mô hình suy luận mờ MOM Mean Of Maximum Phương pháp khử mờ điểm cực đại COA Center Of Area Phương pháp khử mờ điểm trọng tâm 7 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM Chương 1 TỔNG QUAN 1.1 Đặt vấn đề 1.2 Các hướng giải quyết trong AI 1.2.1. Các phương pháp tìm kiếm 1.2.1.1. Các phương pháp tìm kiếm cổ điển 1.2.1.2. Các phương pháp tìm kiếm trên đồ thị 1.2.2. Thuật toán di truyền 1.2.3. Mạng neural 1.2.4. Khai khoáng dữ liệu 1.2.5. Máy học 1.2.6. Logic mờ 1.3 Lý do sử dụng FL 1.4 Kết hợp FL với các kỹ thuật AI khác 8 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM 1.1.Đặt vấn đề Hiện nay tại các trường mầm non, xây dựng khẩu phần ăn cho các bé chủ yếu được thực hiện bằng tay (thủ công), việc này thường mất thời gian và độ đa dạng của các bữa ăn là thấp hoặc không đảm bảo về chế độ dinh dưỡng. Chỉ ở vài trường qui mô lớn thì có thêm sự hỗ trợ của một số hệ thống bán tự động hoặc tự động. Trong nước hiện có phần mềm Babyfood do công ty Đạt An thực hiện, và phần mềm Nutrikids đang được khuyến khích sử dụng, trợ giúp việc sắp xếp bữa ăn cho các bé, tuy nhiên các hệ thống này không thực hiện hoàn toàn tự động mà vẫn phải thông qua khâu xử lý bằng tay của con người. Hệ thống Nutrikids của Công ty cổ phần mạng trực tuyến Việt Sin có thêm hệ thống thiết lập dưỡng chất , thiết lập các bữa ăn ngẫu nhiên từ các món ăn có trong cơ sở dữ liệu phong phú, nhưng không chú trọng đến vấn đề món ăn đó đã được sử dụng khi nào, hay các món ăn có kỵ nhau, một số thiết lập về dinh dưỡng không thể thay đổi, không dùng các kỹ thuật AI và việc sắp xếp khẩu phần ăn tại trường mầm non vẫn do người sắp xếp lịch ăn tại trường thực hiện thủ công lại. Giá của bộ phần mềm Nutrikids của Việt Sin là 990.000VNĐ Nước ngoài thì có phần mềm tự động Nutrikids, nhưng có giá khá cao: bốn module, mỗi module có giá khoảng 250-300USD, và được xây dựng trên nền tảng chế độ dinh dưỡng của trẻ phương Tây nên không phù hợp. Trong khi đó vấn đề tin học hoá ở các trường mầm non đang được mở rộng và khuyến khích phát triển, từ chương trình dạy học cho tới dinh dưỡng của trẻ. Do đó việc phát triển một hệ thống dinh dưỡng tự động mới, phù hợp cho các trường mầm non trong nước là cần thiết và khả thi. Đề tài được thực hiện với một số mục đích sau: • Sắp tự động lịch ăn trưa cho trẻ mầm non trong một tháng với lượng dinh dưỡng phù hợp trong từng ngày, có độ dùng lại thấp, không có các món ăn kỵ nhau. • Hỗ trợ nhà trường trong việc tính toán lại những thay đổi của khẩu phần ăn có liên quan (chẳng hạn, nếu giá cả thay đổi thì việc tính toán lại giá của từng khẩu phần ăn liên quan và cơ chế cho phép điều chỉnh quá trình sắp xếp là hết sức cần thiết) • Giúp cho người quản lý dễ dàng in ra bảng chi tiết nguyên liệu (kèm theo giá cả ) cho bộ phận nấu ăn, cũng như kiểm tra, lập báo cáo hàng tuần , hàng tháng. • Giúp tra cứu bảng dinh dưỡng các chất, xem cách thức chế biến món ăn 1.2 Các hướng giải quyết trong AI 1.2.1 Các phương pháp tìm kiếm: 1.2.1.1 Các phương pháp tìm kiếm cổ điển Trong phương pháp này, chúng ta chọn một khẩu phần ăn, sau đó tiến hành so sánh khẩu phần này với các khẩu phần còn lại. Nếu khẩu phần nào đó tốt hơn, tức là khẩu phần mới đáp ứng tốt hơn với các điều kiện như 9 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM điều kiện về calo, về tỉ lệ cân bằng các chất dinh dưỡng đồng thời thỏa các điều kiện biên và/hoặc có chi phí nhỏ hơn,thì chúng ta sẽ thay thế khẩu phần ban đầu bằng khẩu phần mới và quá trình sẽ lặp lại cho đến khi chúng ta duyệt qua toàn bộ không gian tìm kiếm. Chúng ta cần xác định trước không gian tìm kiếm, tức là không gian khẩu phần ăn. Đồng thời chúng ta cũng phải xác định được các tiêu chí hay các quy tắc cho phép so sánh, đối chiếu để có thể xác định được khẩu phần nào tốt hơn khẩu phần nào. Ưu điểm: Nếu xác định được các tiêu chí so sánh tốt, phương pháp này sẽ cho kết quả tối ưu nhất có trong không gian các khẩu phần ăn. Hạn chế: Việc tìm kiếm trên không gian khẩu phần ăn sẽ gây ra hiện tượng bùng nổ tổ hợp. Ví dụ, nếu chúng ta chỉ dùng ba món trong một khẩu phần ăn thì không gian mẫu sẽ bao gồm n3 mẫu với n là số món trong cùng một loại (canh, mặn, tráng miệng). Ví dụ, mỗi loại có 5 món ăn, khi đó không gian mẫu chúng ta có sẽ là 53 = 125 ; nếu mỗi loại tăng thêm một món ăn, không gian mẫu sẽ trở thành 63 = 226 . Rõ ràng, khi n lớn, việc tìm kiếm sẽ rất tốn kém. Nếu một khẩu phần không chỉ có ba món mà có thể dao động từ ba đến năm món thì việc tìm kiếm sẽ càng khó khăn hơn. Việc xác định các tiêu chí đánh giá để xác định một khẩu phần ăn tốt hơn một khẩu phần khác hay không là một vấn đề lớn. Mỗi món ăn bao gồm rất nhiều thành phần nên một khẩu phần ăn cũng sẽ có rất nhiều thành phần. Các khẩu phần ăn lại phải thỏa mãn nhiều điều kiện khác nhau về dinh dưỡng (calo, chất đạm, ), về tỉ lệ cân bằng giữa các chất, về giá cả, về độ ưa thích... Do vậy, việc xác định một khẩu phần thỏa mãn tất cả điều kiện tốt hơn khẩu phần khác là không dễ dàng. Việc so sánh sẽ càng trở nên phức tạp và nhiều khi không thể thực hiện được nếu các điều kiện này đan xen nhau, trái ngược lẫn nhau. Việc có nhiều điều kiện làm tăng chi phí thực hiện so sánh và tăng thời gian tìm kiếm. 1.2.1.2 Các phương pháp tìm kiếm trên đồ thị Chúng ta có thể xây dựng cây trạng thái từ các món ăn. Các cây được xây dựng trên các tiêu chí định trước như các món trong một nút (hoặc trong các nút có nối với nhau) không được kỵ nhau (điều kiện biên) hay lượng calo phải nằm trong khoảng nào đó (điều kiện dinh dưỡng). Ngoài ra, chúng ta có thể áp dụng một số luật để cây không cao quá như giới hạn số calo, giới hạn số món ăn Ưu điểm: Việc xây dựng cây tốt sẽ làm giảm đáng kể kích thước của không gian tìm kiếm. Hạn chế việc bùng nổ tổ hợp và loại bỏ các khẩu phần không thỏa các điều kiện nào đó. Điều này làm cho việc tìm kiếm trên cây sẽ thực hiện nhanh hơn rất nhiều so với các phương pháp tìm kiếm cổ điển. Việc 10 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM xây dựng cây chỉ cần thực hiện một lần và sau này nếu có thêm một món mới chúng ta chỉ cần cập nhật lại cây mà không phải xây dựng lại từ đầu. Khuyết điểm: Tương tự việc xác định tiêu chí so sánh trong các phương pháp tìm kiếm cổ điển, việc xác định tiêu chí để xây dựng cây cũng rất khó khăn vì có nhiều điều kiện dinh dưỡng và điều kiện biên. Ngoài ra, các cây chỉ có thể cho kết quả đúng (tức là thỏa các điều kiện) chứ ít khi xác định được các kết quả tối ưu. Việc xây dựng cây (phụ thuộc vào các tiêu chí xây dựng cây) nếu thực hiện không tốt sẽ ảnh hưởng lớn đến các thuật toán áp dụng sau này. Chất lượng cây sẽ quyết định chất lượng của chương trình. Nếu cây lớn, thời gian tìm kiếm sẽ lâu hơn và sẽ xảy trường hợp một số khẩu phần hoặc món ăn sẽ không bao giờ được sử dụng 1.2.2 Thuật toán di truyền Ý tưởng chính của thuật toán này xuất phát từ thế giới tự nhiên, các sinh vật sinh trưởng và phát triển. Đến một giai đoạn nào đó, chúng thực hiện giao phối và sinh sản. Quá trình giao phối và sinh sản luôn xuất hiện hai hiện tượng là di truyền và biến dị. Hiện tượng di truyền cho phép thế hệ sau tốt (có khả năng thích nghi) giống thế hệ trước (tức là chí ít cũng không làm xấu đi khả năng thích nghi của loài). Còn hiện tượng biến dị sẽ tạo ra các cá thể có khả năng mới. Nếu khả năng mới là tốt hơn (tức khả năng thích nghi của cá thể đó cao hơn) thì nó sẽ được truyền lại cho các cá thể khác ở thế hệ sau. Nếu khả năng mới là xấu hơn (tức khả năng thích nghi kém hơn) thì khả năng truyền lại cho các cá thể của sau sẽ ít hơn (chứ không phải là không có). Và dần dần, trong quá trình chọn lọc tự nhiên, các đặc tính hạn chế khả năng thích nghi của loài sẽ được loại bỏ hoặc thay thế bằng các đặc tính mới tốt hơn. Tương tự, thuật toán di truyền coi các mẫu hay các khẩu phần ăn trong bài toán của chúng ta là các nhiễm sắc thể, các nhiễm sắc thể sẽ được lai ghép với nhau để tạo ra các nhiễm sắc thể mới, đồng thời một số gen trong quá trình lai ghép bị đột biến cũng tạo thành các nhiễm sắc thể mới. Cuối cùng quá trình chọn lọc tự nhiên sẽ loại bỏ các nhiễm sắc thể có khả năng thích nghi kém ra khỏi quần thể. Biểu diễn các khẩu phần dưới dạng các nhiễm sắc thể Việc biểu diễn các khẩu phần dưới dạng các nhiễm sắc thể ảnh hưởng lớn đến việc cài đặt các phép toán như lai ghép hay đột biến. Trong thuật toán di truyền, chúng ta có thể biểu diễn các nhiễm sắc thể như một chuỗi nhị phân gồm n bit. Trong bài toán xếp lịch các bữa ăn trưa, trong mỗi loại (canh, mặn, tráng miệng), chúng ta biểu diễn mỗi món ăn là một chuỗi nhị phân gồm n bit, với n là số bit ít nhất có thể dùng để biểu diễn được tất cả món ăn. Ví dụ, giả sử có mười món canh, chúng ta xác định n theo công thức n ≥ log 2 10 ≈ 3.3, suy ra n=4. Tương tự, có hai mươi món mặn thì chúng ta cần n=5 bit; có năm món tráng miệng, cần ba bit để biểu diễn. Cần chú ý là số món trong mỗi loại có thể khác nhau nên số bit dùng cho mỗi loại có thể không giống nhau. Sau khi xác định số bit cần để biểu diễn các món cho mỗi loại, chúng ta đặt các chuỗi bit cạnh nhau theo thứ tự xác định trước để biểu diễn các nhiễm sắc thể. Chẳng hạn, chúng ta đặt các chuỗi theo thứ tự canh, mặn và tráng miệng. Lấy lại ví 11 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM dụ trên, chúng ta biểu diễn một nhiễm sắc thể như sau aaaabbbbbccc với các bit a dành cho món canh, b dành cho mặn và c cho tráng miệng. Ngoài cách biểu diễn bằng chuỗi nhị phân, chúng ta cũng có thể biểu diễn các khẩu phần ăn như một chuỗi n số nguyên, với n là số loại món ăn. Trong bài toán của chúng ta, n có giá trị là 3. Trong mỗi loại, chúng ta gán cho mỗi món ăn một số duy nhất, và thông thường các số được gán là các số nguyên dương và cách nhau 1 đơn vị. Tiếp tục ví dụ trên, chúng ta gán mười món canh các giá trị từ 0 đến 9, hai mươi món mặn các giá trị từ 0 đến 19, và 0 đến 4 cho các món tráng miệng. Và chúng ta cũng đặt các số cạnh nhau theo thứ tự xác định trước để biểu diễn nhiễm sắc thể. Theo ví dụ trên, nhiễm sắc thể có dạng như sau abc với a là số gán cho món canh, b cho món mặn và c cho tráng miệng. Lai ghép Lai ghép là phép toán thực hiện lai ghép hai nhiễm sắc thể (hay hai khẩu phần ăn) với nhau để tạo ra các nhiễm sắc thể (khẩu phần ăn) mới tốt hơn hay có khả năng thích nghi cao hơn (đáp ứng tốt hơn với các điều kiện). Với một xác xuất lai k cho trước, chúng ta tiến hành chọn các cặp nhiễm sắc thể (khẩu phần) và thực hiện lai ghép. Tùy thuộc vào việc biểu diễn các nhiễm sắc thể (hay khẩu phần) mà chúng ta có các phép lai khác nhau. Ví dụ: tiếp tục với ví dụ ban đầu, giả sử chúng ta có hai nhiễm sắc thể: aaaabbbbbccc và eeeeggggghhh. Chúng ta tiến hành lai ghép. Giả sử vị trí lai ghép được xác định là vị trí thứ sáu từ trái qua, sau khi lai ghép, chúng ta được hai nhiễm sắc thể mới là aaaabgggghhh và eeeegbbbbccc. Một vấn đề cần quan tâm trong phép lai là chúng ta cần kiểm tra các chuỗi biểu diễn các nhiễm sắc thể có hợp lệ hay không. Chẳng hạn, chúng ta chỉ gán các số từ 0 đến 9 cho các món canh, sau khi thực hiện phép lai, số biểu diễn món canh trong nhiễm sắc thể có thể có giá trị lớn hơn 9. Nếu xảy ra trường hợp đó, chúng ta cần thực hiện điều chỉnh cho phù hợp. Đột biến Đột biến cũng là một phép toán quan trọng trong thuật toán di truyền. Tùy vào việc biểu diễn nhiễm sắc thể mà chúng ta có các cài đặt khác nhau cho phép toán này. Tương tự như lai ghép, phép đột biến cũng căn cứ vào xác xuất đột biến để xác định nhiễm sắc thể nào đột biến. Phép toán này cũng nhằm tạo ra nhiễm sắc thể có độ thích nghi cao hơn. Ví dụ, giả sử nhiễm sắc thể 001110001001 được chọn để tiến hành đột biến và vị trí đột biến được xác định là bit đầu tiên tính từ trái. Sau khi đột biến, chúng ta thu được nhiễm sắc thể 10110001001. Trong ví dụ trên, ta thấy chuỗi bit biểu diễn món canh 1011 có giá trị là 11, nên chuỗi này không có món tương ứng với nó. Chính vì vậy chúng ta cũng cần có cơ chế kiểm tra và xử lý các trường hợp không hợp lệ. Chọn lọc Quá trình chọn lọc là quá trình chọn những nhiễm sắc thể (khẩu phần) có khả năng thích nghi cao và loại bỏ các nhiễm sắc thể (khẩu phần) có độ thích nghi thấp hơn. Tương tự như hai phép toán trên, việc cài đặt phép toán này cũng phụ thuộc vào cách biểu diễn các nhiễm sắc thể. Phép toán này thực hiện ước lượng khả năng thích nghi của các cá thể trong quần thể thông qua một hàm đánh giá. Các cá thể có độ 12 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM thích nghi cao nhất sẽ được giữ lại và một chu kỳ hay một thế hệ mới sẽ ra đời. Thế hệ mới này cũng trải qua qua trình chọn lọc tự nhiên và cứ thế cho đến khi chúng ta thu được các cá thể (nhiễm sắc thể) tối ưu hay có khả năng thích nghi cao nhất. Hàm đánh giá Hàm được sử dụng để ước lượng độ thích nghi của các nhiễm sắc thể hay được dùng để đánh giá các khẩu phần ăn xem khẩu phần nào tốt hơn khẩu phần nào. Chúng ta phải xác định các tiêu chí để đánh giá. Thường hàm này trả về một giá trị số cho biết “độ tốt” của một khẩu phần ăn. Tỉ lệ lai Tỉ lệ lai thể hiện kỳ vọng về số cá thể trong quần thể sẽ được chọn để lai với nhau. Tỉ lệ lai thường dùng là 33% Tỉ lệ đột biến Tỉ lệ đột biến thể hiện kỳ vọng về số cá thể trong quần thể sẽ tạo ra đột biến trong quá trình sinh sản. Tỉ lệ đột biến thường dùng là 0.01% (Các tỉ lệ này có được trong thực nghiệm và tự nhiên) Số cá thể trong quần thể hay số khẩu phần ăn trong một tập các khẩu phần Số lượng cá thể (khẩu phần) trong quần thể (tạp các khẩu phần) sẽ được duy trì từ thế hệ này sang thế hệ khác. Số lượng cá thể (khẩu phần) càng nhiều thì việc xử lý càng tốn kém. Số lượng cá thể (khẩu phần) ít thì việc xác định nhiễm sắc thể (khẩu phần) tối ưu có thể cần nhiều chu kỳ (thế hệ) hơn mới có thể xác định được Số thế hệ Số lần sinh sản của một quần thể Ưu điểm Rõ ràng, với bài toán xác định khẩu phần, thuật toán di truyền cho phép hạn chế hay thu nhỏ không gian tìm kiếm. Thuật toán chỉ tập trung vào những vùng không gian mà khả năng xuất hiện món ăn “tốt”, tức là thỏa mãn tốt các điều kiện, là nhiều nhất. Phép lai ghép cho phép tiến gần đến khẩu phần tốt hơn và phép đột biến sẽ chuyển việc tìm kiếm đến vùng không gian khác có nhiều khả năng chứa khẩu phần “tốt” khác. Thông qua hàm đánh giá, chúng ta có thể biết được khẩu phần nào tốt nhất trong các khẩu phần có được mà không phải trực tiếp so sánh chúng với nhau. Điều này có thể làm giảm tính phức tạp của việc so sánh hay chọn lựa giữa các khẩu phần Thuật toán luôn đảm bảo sẽ tìm được khẩu phần tốt, nhưng không phải là tối ưu, sau số thế hệ được xác định trước. Nếu số thế hệ đủ lớn (đồng nghĩa với thời gian thực hiện lâu hơn), chúng ta có thể nhận được các khẩu phần gần tối ưu. Khuyết điểm Tuy thuật toán luôn cho ra khẩu phần “tốt” nhưng không đảm bảo đó là khẩu phần tối ưu. Độ “tốt” của khẩu phần phụ thuộc vào số thế hệ và số cá thể trong quần thể (số khẩu phần trong tập các khẩu phần) cũng như việc biểu diễn các nhiễm sắc thể (khẩu phần). 13 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM Việc biểu diễn các khẩu phần trong trong thuật toán di truyền thường có định dạng cố định. Chính vì vậy chúng ta không thể có đồng thời các khẩu phần có ba món và khẩu phần có bốn món trong cùng một thuật toán di truyền. Điều này hạn chế khả năng của chương trình vì chỉ cho phép số lượng món cố định, trong khi thực tế có thể thay đổi tùy theo các điều kiện khác nhau. Ngoài ra, việc thay đổi cách biểu diễn có thể dẫn đến việc phải viết lại toàn bộ chương trình. Điều này làm hạn chế khả năng mở rộng của chương trình. Thời gian thực hiện của thuật toán cũng là một vấn đề. Tuy so với các phương pháp tìm kiếm thì thuật toán di truyền thực hiện nhanh hơn, nhưng nếu phải trải qua rất nhiều thế hệ mới xác định được khẩu phần ăn “tốt” thì sẽ rất tốn kém. Việc xây dựng hàm đánh giá cũng phải được quan tâm. Làm thế nào để xây dựng các tiêu chí đánh giá, tiêu chí nào là quan trọng và tiêu chí nào ít quan trọng hơn, Các tiêu chí sẽ ảnh hưởng rất lớn đến thuật toán vì nó quyết định các vùng mà thuật toán cần tập trung tìm kiếm. Chỉ cần đánh giá sai các tiêu chí, thuật toán có thể không cho kết quả tốt mà ngược lại, có thể cho các kết quả không thể chấp nhận được, thuật toán có thể rơi về cục bộ địa phương mà không rơi về điểm tối ưu. Việc xây dựng tiêu chí sẽ rất khó khăn vì các khẩu phần ăn có nhiều ràng buộc về dinh dưỡng hay các điều kiện biên. 1.2.3 Mạng neural Mạng neural được dùng để phân loại hoặc đánh giá và lựa chọn một khẩu phần trong các khẩu phần ứng viên. Mạng có cấu tạo chung bao gồm một hoặc nhiều nút nhập, một hoặc nhiều nút xuất, không có hoặc có nhiều lớp ẩn, mỗi lớp ẩn có thể có một hoặc nhiều nút ẩn. Các nút nhập có các cung nối với các nút ẩn và có thể có các cung nối trực tiếp với các nút xuất, các cung này được gán trọng số thể hiện ảnh hưởng của một nút nhập với một nút ẩn hoặc nút xuất. Các nút thuộc lớp ẩn có thể nối với các nút ẩn khác (trong lớp ẩn sau, trước hoặc trong cùng lớp ẩn) hoặc nối với các nút xuất. Các cung này cũng được gán trọng số thể hiện ảnh hưởng của nút ẩn với các nút nối với nó. Các nút xuất có thể có các cung nối với các nút ẩn và các cung này cũng được gán trọng số. Ngoài ra, bản thân các nút ẩn và các nút xuất cũng có một trọng riêng gọi là trọng ngưỡng. Giá trị này xác định ảnh hưởng của một nút đối với đầu ra của nút đó. Các mạng luôn có hai trang thái là học và ánh xạ. Ở trạng thái học, các mạng sẽ sử dụng dữ liệu đầu vào được cung cấp để cập nhật các trọng sao cho thể hiện mặt lỗi tốt nhất (tức là lỗi trên mẫu học là thấp nhất có thể). Tuy nhiên, trong quá trình học cần tránh hiện tượng qua khớp xảy ra. Hiện tượng quá khớp là hiện tượng mạng hoạt động tốt trên dữ liệu học nhưng không tốt trên dữ liệu khác (không phải dữ liệu học). Trạng thái ánh xạ là trạng thái mà mạng sử dụng các trọng số được cập nhật trong quá trình học cho các mẫu mới để đưa ra các quyết định tương ứng. Ưu điểm Nếu được thiết kế tốt và có nhiều dữ liệu, thì sau quá trình luyện, mạng có thể được sử dụng để xác định kết quả tốt nhất mà nó tìm được. Các mạng có chất lượng thường cho kết quả đúng khoảng trên dưới 95%. Khuyết điểm 14 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM Khuyết điểm đầu tiên là mạng cần có dữ liệu để học hay luyện mạng. Càng nhiều dữ liệu, chất lượng của mạng càng cao. Tuy nhiên, trong bài toán xác định khẩu phần ăn, chúng ta không có dữ liệu để học. Điều này có thể khẳng định ngay là mạng nơron không thích hợp với bài toán này. Chính vì tránh tình trạng quá khớp nên chất lượng của mạng không bao giờ đạt được 100%. Chính vì vậy, mạng chỉ cho ra kết qua tốt nhất có thể trong giới hạn của nó chứ không thể cho ra giá trị tối ưu của bài toán. Việc xác định số nút ẩn hay số lớp ẩn cũng là vấn đề cần được quan tâm. Hiện tại, chưa có công thức cụ thể nào để xác định số lớp cũng như số nút ẩn mỗi lớp. Chúng ta chỉ có thể biết được điều này dựa vào phương pháp thử sai. Điều này sẽ gây tốn kém trong quá trình xây dựng mạng. Việc xác định tất cả tổ hợp có thể có giữa các món ăn có thể là một công việc đơn giản. Tuy nhiên, việc cho tất cả các tổ hợp đó vào mạng để nhận kết quả có thể là việc làm hết sức lãng phí vì vấn đề bùng nổ tổ hợp. Chúng ta có thể dừng quá trình này khi xác định được một khẩu phần thích hợp hoặc một khẩu phần đủ tốt. Nhưng điều này lại dẫn đến hệ quả là các khẩu phần xác định được lại không đảm bảo là khẩu phần tốt nhất. 1.2.4 Khai khoáng dữ liệu Khai khoáng dữ liệu là kỹ thuật được dùng để rút trích tri thức từ các tập dữ liệu lớn một cách tự động. Các tri thức được rút trích thường là các tri thức mới, chưa biết. Hơn nữa, các tri thức mới phải thỏa mãn các yêu cầu hợp lệ, mới lạ, có ích và có thể hiểu được Chúng ta có kiểu dữ liệu ở đây là các chuỗi ký tự, giá trị số, các ...izer-Sklar (Tλ )λ∈[−∞,∞] T (x, y) if - ⎧ M □ = ∞ ⎪ T (x, y) i f P □ = 0 SS ⎪ T (x, y) ⎪ T (x, y) i f ? = D □ ⎨ = ∞ ⎪ 1 ⎪ ⎪(max((x y -1), 0)) i f ,0) (0, ) λ λ λ □ ⎩ + ∈ (−∞ ∪ ∞ 36 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM Hình 2-15 . Toán tử t-norm thuộc Họ Schweizer-Sklar Y - Họ Yager (Tλ )λ∈[0,∞] : ⎧ T (x, y) if ⎪ □ D = 0 Y ⎪ T (x, y) ⎪ T (x, y) i f = M □ = ∞ □ ⎨ ⎪ 1 ⎪ max(1 -((1 -x) (1 -y) ) ,0) i f 0, ) ⎪ λ λ λ □ ⎩ + ∈[ ∞ Hình 2-16 . Toán tử t-norm thuộc Họ Yager 37 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM 2.1.3.4.2 T-conorm -- Mở rộng toán tử OR Toán tử hội mờ còn được gọi là toán tử t-conorm. Như đã đề cập ở trên, có bốn toán tử t-conorm S chuẩn như sau: S (x, y) max(x, y) M = S (x, y) x y -x.y P = + S (x, y) min(x y,1) L = + x if y 0 ⎧ = S (x, y) ⎪ y if x 0 D = = ⎨ ⎪ 1 otherwise ⎩ Hình vẽ minh họa : Hình 2-17 . Bốn toán tử t-conorm S chuẩn. Nhận xét: - ∀x, y ∈[0,1] , chúng ta luôn có: S (x, y) S (x, y) S (x, y) S (x, y) M ≤ P ≤ L ≤ D 38 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM Ta có thể kiểm tra dễ dàng S D là toán tử t-norm lớn nhất , và S M là toán tử t- norm nhỏ nhất. - Chỉ có S M mới có: S(x,x) = x - Ngoại trừ S D , tất cả các toán tử đều liên tục Ví dụ minh họa : Hình 2-18 . Ví dụ về bốn toán tử t-conorm chuẩn Một số toán tử t-conorm khác: F - Họ Frank (Sλ )λ∈[0,∞] : S (x, y) if 0 ⎧ M □ = ⎪ S (x, y) i f 1 ⎪ P □ = F S (x, y) ⎪ S (x, y) i f ? = L = ∞ □ ⎨ ⎪ ( 1 - x 1)( 1 -y 1) ⎪ 1 -log ⎛ 1 □ − □ − ⎞ i f [0,1) 1, ) ⎜ + 1 ⎟ □ ∈ ∪ ( ∞ □ ⎪ ⎜ □ − ⎟ ⎩⎪ ⎝ ⎠ 39 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM H - Họ Hamacher (Sλ )λ∈[0,∞] : ⎧ S (x, y) i f D □ = ∞ H ⎪ S (x, y) ⎪ 1 i f 0 x y 1 = □ = and = = □ ⎨ x y ( -2)xy ⎪ + + □ i f [0, ) and( , ,y) ( 0,1,1) ⎪ 1 (1 -?xy □ ∈ ∞ 腚 x ≠ ⎩ + SS - Họ Schweizer-Sklar (Sλ )λ∈[−∞,∞] ⎧ S (x, y) if - ⎪ M □ = ∞ ⎪ S (x, y) i f ⎪ P □ = 0 SS S (x, y) ⎪ S (x, y) i f ? = D = ∞ □ ⎨ ⎪ 1 ⎪ □ □ 1 -(max(((1 x) (1 y) -1), 0)) □ ⎪ − + − ⎪ if ( ,0) (0, ) ⎩⎪ □ ∈ −∞ ∪ ∞ Y - Họ Yager (Sλ )λ∈[0,∞] ⎧ S (x, y) i f ⎪ □ D = 0 Y ⎪ S (x, y) ⎪ S (x, y) i f = M □ = ∞ □ ⎨ ⎪ 1 ⎪ □ □ max((x y )□ ,1) i f 0, ) ⎪ □ ⎩ + ∈[ ∞ 2.1.4 Luật mờ Phần này sẽ giới thiệu cách mà logic mờ được thực thi. Logic mờ thường sử dụng các luật IF/THEN hoặc xây dựng một cấu trúc tương đương chẳng hạn như ma trận quan hệ mờ. Các luật xây dựng thường có dạng: 40 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM IF x is A THEN y is B, hoặc ngắn gọn là: IF A THEN B. Trong đó x và y là các biến ngôn ngữ (linguistic values) định nghĩa bởi tập mờ trên không gian nền X và Y, A và B là nhãn của tập mờ được mô tả bằng cách xấp xỉ các hàm thành viên. Thành phần if của luật “x is A” được gọi là tiền đề hay giả thuyết, trong khi đó thành phần “y is B” được gọi là kết quả hay kết luận. Nhờ vào dạng rút gọn, luật mờ thường được dùng để thiết lập những phương thức lập luận không chính xác, nhằm thể hiện tính đa dạng trong tri thức của con người. Ví dụ sau mô tả một sự kiện đơn giản (đây là luật mờ loại Mamdani): Nếu tuyết rơi nhiều thì vận tốc xe thấp. Trong đó , tuyết và vận tốc là các biến ngôn ngữ ; nhiều và thấp là các giá trị ngôn ngữ hay các nhãn được mô tả bởi hàm thành viên. Một dạng khác của luật mờ do Takagi và Sugeno đề xuất, có các tập mờ chỉ xuất hiện trong phần giả thuyết của luật (luật mờ loại Sugeno ) : Nếu lưu lượng dòng chảy cao thì mực nước sông = k * lưu lượng dòng chảy Trong đó, cao là phần giả thuyết được mô tả bởi hàm thành viên xấp xỉ. Tuy nhiên, phần kết luận được mô tả bằng một hàm theo biến lưu lượng dòng chảy. Cả hai loại luật mờ trên đều được mở rộng trong cả hai lĩnh vực mô hình hóa và điều khiển tự động 41 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM 2.1.5 Hệ thống vào/ra Hình 2-19 . Phân nhóm các bộ điều khiển theo số tín hiệu vào ra Giống như một bộ điều khiển kinh điển, một bộ điều khiển mờ cũng có thể có nhiều tín hiệu vào và nhiều tín hiệu ra. Ta phân chia chúng thành các nhóm: • Nhóm bộ điều khiển SISO (Single Input, Single Output) nếu nó chỉ có một đầu vào và một đầu ra • Nhóm MIMO (Multi Input, Multi Output) nếu chúng có nhiều đầu vào và nhiều đầu ra • Nhóm bộ điều khiển SIMO nếu nó chỉ có một đầu vào nhưng nhiều đầu ra • Nhóm MISO nếu chúng có nhiều đầu vào và một đầu ra. 42 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM Hình 2-20 . Luật hợp thành là bộ não của điều khiển mờ Nếu một bộ điều khiển mờ có nhiều tín hiệu vào/ra thì tương ứng mệnh đề hợp thành của nó cũng phải có nhiều biến ngôn ngữ vào A1,,Am và nhiều biến ngôn ngữ ra B1,,Bs. Từng biến ngôn ngữ đó lại có nhiều giá trị ngôn ngữ. Ta kí hiệu aki, i=1,2, là một giá trị của biến Ak, k=1,,m cũng như bjl ,j=1,2, là một giá trị của biến Bj, j= 1,,s thì mệnh đề hợp thành của nó sẽ có dạng Nếu A1 = ai1 và và Am = aim thì B1 = bi1 và.... và BS = bis.(*) Bộ nào của điều khiển mờ là luật hợp thành. Luật hợp thành của bộ điều khiển mờ SISO với các mệnh đề hợp thành dạng Nếu A = ai thì B = bj. Được gọi là luật hợp thành đơn. Ngược lại luật hợp thành có các mệnh đề dạng (*) của bộ điều khiển mờ MIMO có tên là luật hợp thành kép. Luật hợp thành MISO có mệnh đề theo cấu trúc: Nếu A1 = ai1 và và Am = aim thì B = b1 (**) Mọi luật hợp thành kép (*) đều có thể được đưa về dạng hợp song song của nhiều luật hợp thànhMISO (**) 43 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM 2.1.6 Mô hình suy luận mờ Có hai loại hệ thống suy luận mờ (mô hình) được ứng dụng rộng rãi trong các ứng dụng khác nhau: Mô hình Mamdani và Mô hình Takagi – Sugeno. Sự khác nhau của hai mô hình nằm ở vế thứ hai của các luật (mệnh đề kết luận). 2.1.6.1 Mô hình Mamdani i luật cho hệ thống vào/ra MISO kiểu Mamdani có dạng như sau: IF x is A and/or x is A and/or .......x is A , THEN y is B 1 i 1 2 i 2 n i n i Trong đó: - x1 ,..., x n là các biến ngôn ngữ của không gian nền sử dụng. Nói chung chúng tương đương với các biến trạng thái. Chúng thuộc những tập mờ với một giá trị phụ thuộc đã biết trước. - A i 1 ,..., Ai n là các tập mờ trong i luật cho các biến ngôn ngữ x1 ,..., x n - y là biến ngôn ngữ thuộc tập mờ kết luận cần rút ra từ các mệnh đề suy luận. - Bi là tập mờ kết luận trong i luật cho biến ngôn ngữ y. Trong thứ tự của quá trình suy luận với các luật mờ, các toán tử kết nối mờ hết sức cần thiết. Hầu hết, t-norms được sử dụng cho “and” và “if-then”, s-norms được sử dụng cho “or” và “also” Thiết kế mô hình điều khiển mờ kiểu Mamdani bao gồm những bước sau: 1. Xác định các biến ngôn ngữ và không gian nền tương ứng của chúng. Bước này tương đương với việc xác định dữ liệu vào và dữ liệu ra của bộ điều khiển mờ. 2. Xác định các tập mờ cho mỗi biến ngôn ngữ, và xác định hàm thành viên và không gian nền cho mỗi tập mờ. Bước này nói chung dựa vào kinh nghiệm của con người. 3. Xác định toán tử mờ sử dụng để thi hành việc kết nối các mệnh đề trong mỗi phát biểu. 4. Xác định cách mờ hóa và cách khử mờ. Nói chung, khâu mờ hóa chuyển đổi dữ liệu đầu vào rõ thành một đơn vị mờ. Có rất nhiều phương pháp khử mờ khác nhau, ví dụ như, phương pháp trọng tâm, phương pháp trung bình hàm thành viên cực đại , v.v If x is A and y is B Then z is C Trong đó A, B là các tập mờ tiền đề, còn C là tập mờ kết luận. Ví dụ: Một mô hình Mamdani cho hệ thống SISO được mô tả như sau: IF X is small THEN Y is small. IF X is medium THEN Y is medium. IF X is large THEN Y is large. Hàm thành viên hình thang cho các biến ngôn ngữ đầu vào small, medium, và large được mô tả ở Hình 2-21 44 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM Hình 2-21 . Hàm thành viên cho biến ngôn ngữ đầu vào có giá trị small, medium và large. Hàm thành viên của các biến đầu vào có dạng: trapmf(x,[-20,-15,-6,-3]),trapmf(x,[-6,-3,3,6]),trapmf(x,[3,6,15,20]) Khi đó, hàm thành viên cho các giá trị ngôn ngữ đầu ra small, medium, và large được mô tả như ở Hình 2-22. Hình 2-22 . Hàm thành viên cho biến đầu ra có giá trị small, medium và large 45 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM Ứng dụng: Đại diện cho tri thức của con người: • Hỗ trợ quyết định • Điều khiển và giám sát • Dò tìm lỗi , chuẩn đoán. 2.1.6.2 Mô hình Takagi - Sugeno Dạng tổng quát với i luật của mô hình hệ thống vào/ra MISO theo kiểu Takagi – Sugeno (TS) có dạng như sau: IF x is A and/or x is A and/or .......x is A , 1 i 1 2 i 2 n i n f(x ,...x, ,c ,...c, ) THEN y = i 1 n i0 in i Trong đó: - x1 ,..., x n là các biến ngôn ngữ của không gian nền sử dụng. Nói chung chúng tương đương với các biến trạng thái. Chúng thuộc những tập mờ với một giá trị phụ thuộc đã biết trước. - A i 1 ,..., Ai n là các tập mờ trong i luật cho các biến ngôn ngữ x1 ,..., x n - y là biến ngôn ngữ thuộc tập mờ kết luận cần rút ra từ các mệnh đề suy luận. - f i là một hàm tùy ý. - ci 0 , ci 1 ,...,ci n là những hàm số trong hàm f i Chú ý : Chỉ có điểm khác biệt duy nhất giữa mô hình hệ thống điều khiển mờ kiểu TS và mô hình hệ thống điều khiển mờ kiểu Mamdani là trong mô hình điều khiển mờ kiểu TS , các kết luận trong các luật là các hàm của giá trị đầu vào rõ , trong khi các kết luận trong các luật trong mô hình hệ thống kiểu Mamdani vẫn là các giá trị mờ. Về mặt lý thuyết, các kết luận chứa trong các luật mờ của mô hình kiểu TS có thể là bất kì hàm nào, mặc dầu vậy, trong thực tế người ta thường sử dụng các hàm tuyến tính. Khâu giải mờ cho mô hình kiểu Mamdani được cho bởi công thức: n □ i□ i ∑i 1 U n = = □ i ∑i 1 = Trong đó, n là tổng số luật trong cơ sở luật, β i là giá trị đúng của luật thứ i , yi là giá trị kết luận nhận được của luật thứ i . Tùy thuộc vào toán tử kết nối mờ sử dụng để nối các luật lại với nhau, β i có thể nhận các giá trị khác nhau. Nói chung, toán tử MIN thường được sử dụng cho phép ‘and’. Trong trương hợp này, β có thể được tính như sau : MIN( i (x ),..., (x )) □ i □ A 1 □ A n = 11 1n Trong đó µ là hàm thành viên của tập mờ A A ij ij 46 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM Tương tự việc thiết kế bộ điều khiển mờ kiểu Mamdani, để thiết kế bộ điều khiển mờ kiểu TS , tập mờ cho mỗi biến ngôn ngữ, hàm thành viên cho mỗi tập mờ, số luật mờ, và những hàm kết luật cần phải được xác định trước. Tuy nhiên, không giống như bộ điều khiển mờ Mamdani, để xác định các tham số ci 0 , ci 1 ,...,ci n là rất khó khăn, nhất là khi chúng không mang một ý nghĩa vật lý nào Tổng số tham số sẽ tăng theo cấp lũy thừa nếu bậc hệ thống tăng lên, do đó với hệ thống có bậc cao (độ phức tạp cao), việc điều chỉnh giữa các tham số sẽ trở nên cực kì khó khăn, nếu không muốn nói là không thể xảy ra. If x is A and y is B Then z = f(x,y), Trong đó A, B là các tập mờ tiền đề , còn z = f(x,y) là một hàm xác định trong kết luận. Thông thường, f(x,y) là một đa thức chứa các biến đầu vào x, y, tuy nhiên nó có thể nhận nhiều lớp hàm khác nhau nhằm mô tả chính xác hơn dữ liệu đầu ra của mô hình từ miền xác định mờ cho bởi các giả thuyết lấy từ luật. Khi f(x,y) là hằng số, chúng ta có một mô hình mờ Sugeno bậc 0. Ví dụ: Mô hình S cho hệ thống SISO như sau : IF X is small THEN Y= X2 +0.1X+6.4 IF X is medium THEN Y= X 2 -0.5X+4 IF X is large THEN Y= X+X-22 Hàm thành viên cho small, medium, và large được minh họa ở Hình 2-23 Hình 2-23 . Hàm thành viên cho “Small” , “Medium” và “Large” 47 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM Hàm thành viên biểu diễn cho từng biến ngôn ngữ là: µSmall (x) = gbellmf(x,[6,4,-10]), µ Medium (x) = gbellmf(x,[4,4,0]), µ Large (x) = gbellmf(x,[6,4,10]) Ứng dụng: Sử dụng quá trình xấp xỉ hàm: • Nhận dạng trong các hệ thống phi tuyến (nonlinear identification) • Điều khiển phi tuyến (nonlinear control) • Hoạch định lợi tức (gain scheduling) 2.1.7 Khử mờ Sau khi thực hiện xong việc tính giá trị luật hợp thành (nguyên lý điều khiển) chúng ta thu được kết quả là tập mờ µA(y) cùng nền với tín hiệu ra. Kết quả đó chưa thể là một giá trị thích hợp để điều khiển, phải là một giá trị rõ, xác định. Việc xác định một giá trị rõ y0 từ tập mờ µR(y) của nó, được gọi là giải mờ. Giá trị rõ y0 xác định được có thể được xem như “phần tử đại diện xứng đáng” cho tập mờ. Căn cứ theo những quan niệm khác nhau về “phần tử đại diện xứng đáng” mà ta sẽ có các phương pháp giải mờ khác nhau. Trong điều khiển người ta thường hay sử dụng hai phương pháp chính, đó là: • Phương pháp điểm cực đại (MOM) • Phương pháp điểm trọng tâm (COA) 2.1.7.1 Phương pháp điểm cực đại Tư tưởng chính của phương pháp giải mờ điểm cực đại là tìm trong tập mờ có hàm thuộc µR(y) một phần tử rõ y0 với độ phụ thuộc lớn nhất (có xác suất thuộc tập mờ lớn nhất trong số những phần tử còn lại. Gồm hai bước: + Xác định miền chứa giá trị rõ y0. Giá trị rõ y0 là giá trị mà tại đó 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 = {y∈Y | µR(y) = H} + Xác định y0 có thể chấp nhận được từ G Được thể hiện bằng công thức: 1 y y0 = ∑ i µ y i ∈ G 2.1.7.2 Phương pháp điểm trọng tâm Phương pháp điểm trọng tâm sẽ cho ra kết quả y0 là hoành độ của điểm trọng tâm miền được tạo bởi trục hoành và đường µR(y) yµ (y)dy ∫ R S y0 = µ (y)dy ∫ R S với S = suppµR(y) = {y | µR(y) ≠ 0 } là miền xác định của tập mờ R 48 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM Phương pháp này cho phép ta xác định giá trị y0 với sự tham gia của tất cả các tập mờ đầu ra của luật điều khiển một cách bình đẳng và chính xác. Tuy nhiên phương pháp này lại không để ý được độ thoả mãn của mệnh đề điều khiển cũng như thời gian tính lâu. Ngoài ra một trong những nhược điểm cơ bản của phương pháp điểm trọng tâm là có thể giá trị y0 xác định được lại có độ thuộc nhỏ nhất, thậm chí bằng 0 2.1.8 Hệ thống mờ - Bộ điều khiển mờ 2.1.8.1 Cấu trúc một hệ thống mờ - Bộ điều khiển mờ. Cấu trúc của hệ thống mờ chuẩn: Hình 2-23. Cấu trúc của hệ thống mờ chuẩn. 49 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM Cấu trúc hệ thống mờ kết hợp với khâu mờ hóa và khử mờ: Hình 2-25 . Cấu trúc của bộ xử lý mờ kết hợp khâu giải mờ và khử mờ. Mở rộng cấu trúc hệ thống mờ cho quá trình xử lý dữ liệu ta thu được cấu trúc của bộ điều khiển mờ hoàn chỉnh. Hình 2-26 . Cấu trúc của một bộ điều khiển mờ Như vậy, ta thấy cấu trúc của một hệ thống mờ có bốn thành phần cơ bản: Fuzzification (khối mờ hóa) , rule base (khối luật mờ) , Inference mechanism (Khối suy diễn mờ) , Defuzzification (Khối giải mờ) . • Khối mờ hóa: ứng với dữ liệu rõ đầu vào, biến đổi bộ giá trị này thành miền giá trị mờ thông qua hàm thành viên đã được xây dựng trước đó. • Khối luật mờ: Tập luật “If then” (“Nếu thì”) chính là tập hợp các luật mờ cơ sở lấy từ tri thức của các chuyên gia, xây dựng mối quan hệ giữa biến ngôn ngữ đầu vào với giá trị biến ngôn ngữ đầu ra. 50 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM • Khối suy luận mờ: sử dụng để biến đổi các giá trị mờ hóa của biến ngôn ngữ đầu vào thành các giá trị mờ của biến ngôn ngữ đầu ra thông qua việc hợp thành các luật cơ sở có trong khối luật mờ. • Khối giải mờ: biến đổi các giá trị mờ của biến ngôn ngữ đầu ra thành các giá trị rõ 2.1.8.2 Phân loại cấu trúc Cấu trúc của bộ điều khiển Logic mờ: gồm hai loại: Bộ điều khiển mờ cổ điển và bộ điều khiển mờ phân tán. Bộ điều khiển mờ cổ điển thường chứa một khối mờ. Khối mờ này có đầu vào là biến trạng thái (xi ) và một đầu ra là điều khiển hoạt động (yi ) như hình vẽ Hình 2-27a . Mỗi đầu vào liên kết với các đầu vào khác thông qua những luật trong bộ luật cơ sở. Tuy nhiên , nếu bài toán cần xây dựng lớn và phức tạp thì sử dụng phương pháp cổ điển này để xây dựng hệ thống mờ là không thực tế bởi vì số lượng luật sẽ tăng theo lũy thừa số lượng đầu vào. Ví dụ , hiện có sáu factor được sử dụng trong nghiệp vụ xây dựng chế độ dinh dưỡng tại trường mầm non , mỗi factor có ba hàm thành viên, khi đó kích thước bộ luật sẽ là 36 = 729 Hình 2-27. Bộ điều khiển mờ cổ điển (Hình a) và bộ điều khiển mờ phân tán (Hình b) 51 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM Một cấu trúc phân tán, như minh họa ở Hình 2-27b, là một sự thay thế cho bộ điều khiển mờ khối đơn cổ điển nêu trên. Trong nghiệp vụ xây dựng khẩu phần ăn trưa tại trường mầm non, nếu với sáu factor ta có thể phân nhóm các factor này theo chức năng và mối quan hệ giữa các factor với nhau, khi ấy số lượng luật sẽ giảm đi rất nhiều so với bộ điều khiển mờ cổ điển. Với ví dụ trên, ta thấy rằng , nếu mỗi đầu vào có ba hàm thành viên, bộ điều khiển mờ cổ điển trong hình a cần 34 = 81 luật, còn với bộ điều khiển phân tán trong hình b chỉ cần 2 2 2 2 3 + 3 + 3 + 3 = 27 luật. Tuy vậy, việc áp dụng cấu trúc cổ điển hay cấu trúc phân tán cần được xem xét một cách kỹ lưỡng. Trong cả hai loại cấu trúc mờ đưa ra, mỗi loại đều có ưu khuyết điểm của nó. Đối với cấu trúc mờ cổ điển, số lượng luật xây dựng là rất lớn, do đó quá trình xây dựng luật sẽ gặp nhiều khó khăn, tốc độ xử lý sẽ bị giảm do có quá nhiều luật, nhưng ưu điểm của cấu trúc này là nó cho phép tất cả các dữ liệu đều được xem xét ở mọi tiêu chuẩn đánh giá, do đó việc lựa chọn sẽ đạt được những yêu cầu mong muốn. Trong khi đó, đối với phương pháp phân tán, số lượng luật được giảm đi rất nhiều (do có nhiều luật ít khi được sử dụng hay không được sử dụng nên chỉ giữ lại tập luật cơ bản được sử dụng nhiều nhất) làm cho việc xử lý dữ liệu trở nên đơn giản hơn, và trong đa số các trường hợp phương pháp này vẫn đảm bảo được các yêu cầu mong muốn. Tuy nhiên, vì số lượng luật ít, điều đó dẫn đến, trong một số trường hợp sẽ không đủ luật để xem xét đánh giá, làm cho việc chọn lựa có thể không đạt được các yêu cầu đặt ra. Hơn nữa, nếu sử dụng phương pháp này, một số bộ dữ liệu có thể không được xem xét, và do đó chúng có thể không bao giờ được sử dụng trong suốt quá trình xây dựng khẩu phần ăn của chúng ta. 2.1.9 Cách lựa chọn logic mờ cho từng hệ thống xây dựng Trong phần này, chúng ta sẽ thảo luận về một hệ thống logic mờ tốt nhất, cách lựa chọn logic mờ tôt nhất tùy theo mục đích sử dụng của chúng ta. Trường hợp: Những logic mờ mạnh mẽ nhất Trong logic mờ, tập các giá trị được đặc trưng bởi các giá trị nằm trong khoảng [0,1]. Vì vậy, giả sử có một phát bỉểu S của chuyên gia, trong cách tiếp cận logic mờ, chúng ta mô tả độ chắc chắn trong lời phát biểu của chuyên gia bởi một số nằm trong khoảng [0,1]. Có nhiều phương pháp khác nhau cho phép xác định giá trị từ chuyên gia.[3] Ví dụ, có một số phương pháp yêu cầu chuyên gia dánh dấu về độ chắc chắn của họ trên một phạm vi, chẳng hạn, từ 0 đến 10. Nếu chuyên gia cho nó là 7, điều đó có nghĩa là giá trị mờ của nó là 0.7 . Các phương pháp khác nhau có thể dẫn đến những kết quả khác nhau. Điều này có thể giải thích một cách trực quan: chúng ta đang cố gắng hình thức hóa những quan điểm chủ quan của các chuyên gia, trong khi đó, các chuyên gia hầu như có thể phân biệt được độ chắc chắn giữa 0.5 và 0.7, nhưng thông thường các chuyên gia lại không thể phân biệt được độ chắc chắn của hai giá trị gần nhau giống như 0.7 và 0.701 Do vậy, để chọn được giá trị mong muốn chúng ta cần lựa chọn toán tử logic sao cho kết quả thu được của những trương hợp không đúng là tối thiểu nhất với tiêu chuẩn dựa vào giá trị của hàm thành viên. 52 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM Nếu chúng ta tìm kiếm một bộ logic mờ mà cho kết quả tôt nhất trong những trường hợp xấu nhất, khi đó sự lựa chọn tối ưu là sử dụng: f ∧ (a,b) = min(a,b) và f ∨ (a,b) = max(a,b) .[8] Mặt khác, nếu chúng ta tìm một bộ logic mờ cho kêt quả tốt nhất trong trương hợp trung bình, khi đó sự lựa chọn tốt nhất là sử dụng: f ∧ (a,b) = a.b và f ∨ (a,b) = a + b - a.b [8]. Trường hợp: Logic mờ dẫn đến bộ điều khiển mờ tốt nhất. Một trong những ứng dụng chính của logic mờ chính là điều khiển mờ. Trong hầu hết các ứng dụng điều khiển mờ, cách tiếp cận theo kiểu Mamdani được sử dụng – kết hợp với việc sử dụng toán tử t-norm và t-conorm. Vì vậy, một ý kiến hợp lý là việc tìm kiếm toán tử logic mờ hướng đến bộ điều khiển tốt nhất. Điều đó cho thấy rằng kết quả của logic mờ phụ thuộc vào cái mà chúng ta muốn điều khiển. Nếu chúng ta muốn tìm một bộ điều khiển cho kết quả mịn nhất (theo một vài cảm giác của chúng ta), khi đó chúng ta nên chọn f ∧ (a,b) = a.b và f ∨ (a,b) = max(a,b) [7,10] Mặt khác, nếu chúng ta đang tìm kiếm một bộ điều khiển ổn định nhất (chẳng hạn, một bộ điều khiển mà mỗi khi hệ thống bị xáo trộn, quá trình điều khiển sẽ trả về nhanh nhất quỹ đạo nguyên bản, khi đó chúng ta nên chọn f ∧ (a,b) = min(a,b) và f ∨ (a,b) = a + b - a.b [7,10]. Đối với các ứng dụng mà kết quả cần được tính toán càng nhanh càng tốt, một chức năng quan trọng của logic mờ là tốc độ tính toán của các toán tử logic tương ứng. Khi đó, chúng ta sẽ chọn lựa các toán tử logic đơn giản nhất đó là: f ∧ (a,b) = a.b and f ∨ (a,b) = max(a,b) [7,10]. Ngoài ra còn có một số tiêu chuẩn chọn lựa logic mờ hợp lý khác - chẳng hạn như dựa vào số lượng thông tin để lựa chọn bộ mờ tốt nhất [4,7] Trong các tình huống khác nhau, các toán tử logic mờ cho kết quả tốt nhất khác nhau. Câu hỏi đặtt ra là khi nào chúng ta sử dụng toán tử and và khi nào thì sử dụng toán tử or ? Chúng ta sẽ xem xét ví dụ thực tế sau: Những người thiết kế thành công hệ chuyên gia MYCIN đầu tiên của thê giới – một hệ thống chuẩn đoán bệnh từ mẫu máu người bệnh – đã mất thời gian khá dài để cố gắng tìm ra toán tử tốt nhất cho quá trình suy luận bệnh trong y học. Sau thành công của MYCIN, họ nghĩ rằng không cần chuyển đổi những suy luận của con người trong về sự chắc chắn, vì vậy họ thiết kế một hệ chuyên gia mới (một shell) có tên eMYCIN (empty MyCin) với mục đích sử dụng những toán tử giống nhau trong các ứng dụng khác nhau. Một điều ngạc nhiên đã đến với họ, lĩnh vực đầu tiên mà họ triển khai – tìm kiếm dầu – sự “hoàn hảo” của toán tử AND trong MYCIN đã không hoạt động như mong đợi. Qua quá trình phân tích, người ta đã tìm ra được nguyên nhân của sự khác nhau này: • Đối với ngành y học, các bác sĩ luôn luôn cẩn trọng, họ sẽ không bao giờ phẩu thuật cho đến khi họ chắc chắn rằng quá trình phẩu thuật không gây hại đối với người bệnh. • Ngược lại, trong lĩnh vực khai thác dầu, người ta sẽ tiến hành đào bới ngay nếu phát hiện ở vị trí nào đó có dầu, chỉ cần có độ chắc chắn khoảng 20% về sự tồn tại của dầu, đây là tỉ lệ rủi ro chấp nhận được. 53 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM Như vậy, sự khác nhau về các suy luận đằng sau tính cẩn trọng và tính rủi ro cao đã dẫn đến sự khác nhau của toán tử “and”. Nói tóm lại, đối với những vấn đề khác nhau, chúng ta cần sử dụng các toán tử khác nhau. 2.2 Khái quát về máy học 2.2.1 Định nghĩa Con người có nhiều cách học như học ký ức, học các sự kiện thông qua sự quan sát và thăm dò, học cải thiện kỹ xảo thông qua thực tiễn, học nhờ sự phát triển của hệ thần kinh sinh học con người và học nhờ gen di truyền từ các thế hệ trước. Giống như cách học của con người, người ta muốn xây dựng các chương trình học cho máy sao cho máy có khả năng thu thập và xử lý tri thức để thích nghi với tình huống mới. Máy có các thể loại học: • Học giám sát: quá trình học có tín hiệu hướng dẫn vào ra chính xác của thầy giáo, dữ liệu học vào ra của hệ thống phải được thiết lập trước. Sau quá trình học hệ thống sẽ tìm ra một luật thích hợp để thực hiện tốt công việc dự báo ngõ ra được kết hợp với ngõ vào mới của hệ thống. • Học không giám sát: còn được gọi là thể loại tự học, với thể loại học này, quá trình học không có sự trợ giúp bất kỳ thông tin hướng dẫn nào của thầy giáo, hệ thống tự khám phá ra một luật thích nghi để thực hiện tốt công việc ngõ ra được kết hợp với ngõ vào mới từ tập các mẫu dữ liệu học ngõ vào mong muốn. 2.2.1 Học với cây quyết định Làm thế nào để phân biệt các lớp, công thức, luật, hoặc cấu trúc nên sử dụng trong việc hình thành mẫu mới? Một kỹ thuật được gọi là Cây quyết định qui nạp (inductive decision tree) sẽ “quan sát” các mẫu và xây dựng một cây nhị phân có thể phân biệt tất cả các lớp. Tiến trình xây dựng cây nhị phân này dựa trên việc chọn đệ qui một node, một thuộc tính, hoặc bất kỳ giá trị nào của nó, mà có thể chia toàn bộ tập hợp mẫu thành hai nhóm. Học với cây quyết định là một phương pháp thích hợp được áp dụng rộng rãi cho kết luận qui nạp, là phương thức đại diện cho các hàm mục tiêu có giá trị rời rạc, việc học được biểu diễn bởi một cây quyết định. Các cây được học có thể được mô tả bởi các tập luật nếu-thì.[12] Các cây quyết định phân loại các thuộc tính đưa ra bằng cách sắp xếp chúng đi xuống từ gốc đến nốt lá với một bộ phân loại theo thuộc tính. Mỗi nốt trong cây chỉ rõ thuộc tính mà các thuộc tính này liên kết với nhau thông qua các nhánh, mỗi nhánh đi xuống chỉ rõ giá trị thuộc tính của nó và đi dần đến nốt lá thích hợp chính là các thuộc tính quyết định. Thuật toán ID3 ID3 (Examples, Target_attribute, Attributes) Example là các mẫu huấn luyện. Target_attribute là thuộc tính mục tiêu trong cây. Attributes là một danh sách các thuộc tính khác mà đã được kiểm tra bởi cây quyết định được học. Trả ra một cây quyết định với phân loại chính xác. 54 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM • Tạo nốt gốc Root của cây • Nếu tất cả Examples là positive, trả ra cây có nốt đơn Root, với nhãn=+ • Nếu tất cả Examples là negative, trả ra cây có nốt đơn Root, với nhãn=- • Nếu Attributes là rỗng, trả ra cây có nốt đơn Root, với nhãn = các giá trị thông thường hầu hết của Target_attribute trong Examples. • Ngược lại Begin - A Å thuộc tính từ Attributes mà là tốt nhất* khi phân loại Examples - Thuộc tính quyết định cho RootÅA - For (mỗi giá trị có thể vi của A) - Thêm nhánh dưới Root, tương ứng vi - Với Examplesvi là tập con của Examples mà có giá trị vi ƒ Nếu Examples rỗng : Thì bên dưới nhánh mới thêm vào nốt lá với nhãn = các giá trị thông thường hầu hết của Target_attribute trong Examples ƒ Ngược lại bên dưới nhánh mới thêm vào cây con ID3(Examplesvi, Target_attribute, Attributes – {A}) End • Return Root *Thuộc tính tốt nhất là thuộc tính mà mức độ thông tin cao nhất Ví dụ: Giả sử có kết quả danh sách các bữa ăn sử dụng hay không sử dụng trong môt khoảng thời gian. Bữa Món Mặn Món Canh Tr.Miệng Trạng thái 1 A B C Có chọn 2 A B F Chưa chọn 3 A E F Có chọn 4 A E C Có chọn 5 D B C Chưa chọn 6 D B F Chưa chọn 7 D E C Có chọn 8 D E F Có chọn • R = {“Có chọn” ,”Chưa chọn} • P = tập hợp 8 bữa quan sát được • 4 thuộc tính : Món Canh, Món Mặn, Tr.Miệng Quinlan: Với mỗi thuộc tính dẫn xuất A còn có thể sử dụng để phân hoạch, tính : • VA(j) = ( T(j , r1), T(j , r2) , , T(j , rn) ) • T(j, ri) = (tổng số phần tử trong phân hoạch có giá trị thuộc tính dẫn xuất A là j và có giá trị thuộc tính mục tiêu là ri ) / ( tổng số phần tử trong phân hoạch có giá trị thuộc tính dẫn xuất A là j ) Trong đó r1, r2, , rn là các giá trị của thuộc tính mục tiêu 55 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM Như vậy nếu một thuộc tính A có thể nhận một trong 5 giá trị khác nhau thì nó sẽ có 5 vector đặc trưng. Một vector VA(j ) được gọi là vector đơn vị nếu nó chỉ có duy nhất một thành phần có giá trị 1 và những thành phần khác có giá trị 0. Thuộc tính được chọn để phân hoạch là thuộc tính có nhiều vector đơn vị nhất. Trở lại ví dụ, lúc ban đầu (chưa phân hoạch): VMặn(A) = (T(A,Có Chọn), T(A, Chưa chọn)) Số món mặn A là: 4 Số món mặn A đã chọn là: 3 Số món mặn A chưa chọn là : 1 Do đó : VMặn(A) = (3/4, 1/4) Tương tự: VMặn(D) = (2/4 , 2/4) = (0.5 , 0.5) VCanh(B) = (1/4 , 3/4) VCanh(E) = (4/4 , 0/4) = (1,0) (vector đơn vị) VTr.Miệng(C) = (3/4 , 1/4) VTr.Miệng(F) = (2/4 , 2/4) Như vậy thuộc tính Món Canh có số vector đơn vị nhiều nhất nên sẽ được chọn để phân hoạch. Phân hoạch theo Món Canh (PB) tập dữ liệu còn lại là: Bữa Món Mặn Tr.Miệng Trạng thái 1 A C Có chọn 2 A F Chưa chọn 5 D C Chưa chọn 6 D F Chưa chọn Phân hoạch PB còn chứa những bữa “chưa chọn” và “có chọn”. Tiếp tục phân hoạch tập này. Tính vector đặc trưng tương ứng với các thuộc tính còn lại VMặn(A) = (1/2 , 1/2) = (1 , 1) VMặn(D) = (0/2 , 2/2) = (0 , 1) (vector đơn vị) VTr.Miệng(C) = (1/2 , 1/2) = (1,1) VTr.Miệng (F) = (0/2 , 2/2) = (0, 1) Hai thuộc tính “Món Mặn” và “Tr.Miệng” đều có 1 vector đơn vị. Ta có thể phân hoạch một trong hai thuộc tính. Ta sẽ chọn thuộc tính “Món Mặn” để phân hoạch (PA) Bữa Tr.Miệng Trạng thái 1 C Có chọn 2 F Chưa chọn 56 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM Cây định danh cuối cùng: Biến đổi cây thành luật : - If (Món canh = E) then (Trạng Thái = Có chọn) - If (Món canh = B) and (Món Mặn = D) then (Kết quả = Chưa chọn) - . Từ các luật được thiết lập, ta thấy nếu bữa ăn có Món canh là B, Món Mặn D và Tráng miệng là F thi chắc chắn không được chọn trong khoảng thời gian khảo sát, bộ lọc máy học sẽ xóa nhữ...TrungBinh) - Độ dùng lại cao (DDL.Cao) Nếu xây dựng bộ điều khiển mờ theo phương pháp cổ điển ta cần sử dụng rất nhiều luật. Chẳng hạn, đối với bài toán của chúng ta, nếu xây dựng theo phương pháp cổ điển cần đến 36 = 729 luật . Do đó, để giảm bớt chi phí tính toán cũng như giảm thiểu số luật, chúng ta sẽ xây dựng bộ điều khiển mờ phân tán: phân nhóm factor và xây dựng bộ điều khiển mờ cho từng nhóm factor. Tiêu chí phân nhóm factor là mối liên hệ giữa các factor. Ở đây chúng ta có thể phân các factor thành ba nhóm: một nhóm factor có quan hệ dinh dưỡng với nhau (nhóm factor có mối quan hệ không thay đổi theo thời gian), nhóm còn lại là nhóm các factor có mối quan hệ thay đổi theo thời gian (thay đổi giá tiền, thay đổi ngày dùng lại ... ) . Do đó, cần có thêm một factor trung gian để liên kết hai nhóm factor này với nhau (Factor Tỉ lệ Dinh Dưỡng): Factor Tỉ lệ Dinh Dưỡng: gồm 5 tập mờ: - Tỉ lệ dinh dưỡng rất thấp (TLDD.RatThap) - Tỉ lệ dinh dưỡng thấp (TLDD.Thap) - Tỉ lệ dinh dưỡng trung bình (TLDD.TrungBinh) - Tỉ lệ dinh dưỡng cao (TLDD.Cao) - Tỉ lệ dinh dưỡng rất cao (TLDD.RatCao) Với việc xây dựng thêm factor trung gian, số luật trong cả hai bộ điều khiển fuzzy giảm đi đáng kể, chỉ còn lại: 126 luật. Do hệ thống xây dựng cần đáp ứng cho cả hai khối nhà trẻ và mẫu giáo , do đó chúng ta cần xây dựng hai bộ điều khiển mờ thích ứng với từng nhóm tuổi. 68 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM 3.3.2 Xây dựng các hàm thành viên Hiện nay, trong quá trình xếp lịch ăn tại trường mầm non tồn tại 2 chuẩn cơ cấu năng lượng - Chuẩn một : Tỉ lệ P:L:G = 12% - 15% : 15% - 20% : 66% - 75% - Chuẩn hai : Tỉ lệ P:L:G = 14% : 26% : 60% Đồng thời, lượng gạo (cung cấp lượng lớn calo trong bữa ăn) đối với nhóm tuổi nhà trẻ và nhóm tuổi mầm non cách nhau khá xa, do vậy chúng ta cần xây dựng bộ điều khiển mờ sao cho đáp ứng được từng nhu cầu của từng nhóm tuổi và hỗ trợ cả hai chuẩn nói trên. Để thực hiện được điều này, chúng ta xây dựng hai hàm thành viên cho factor “lượng calo” và hai nhóm factor “tỉ lệ protein”, “tỉ lệ lipit”, “tỉ lệ gluxit”. Factor “lượng calo”: Đối với nhà trẻ: Hình 3-1: Factor “lượng calo” đối với nhóm nhà trẻ Đối với nhóm mẫu giáo : Hình 3-2: Factor lượng calo đối với nhóm mẫu giáo 69 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM Các factor “tỉ lệ protein”, “tỉ lệ lipit”, “tỉ lệ gluxit” áp dụng cho chuẩn một : Factor “tỉ lệ protein”: Hình 3-3: Factor “tỉ lệ protein” đối với chuẩn một Factor “tỉ lệ lipit”: Hình 3-4: Factor “tỉ lệ lipit” đối với chuẩn một 70 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM Factor “tỉ lệ gluxit”: Hình 3-5: Factor “tỉ lệ gluxit” đối với chuẩn một Các factor “tỉ lệ protein”, “tỉ lệ lipit”, “tỉ lệ gluxit” áp dụng cho chuẩn hai : Factor “tỉ lệ protein” : Hình 3-6: Factor “tỉ lệ protein” đối với chuẩn hai 71 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM Factor “tỉ lệ lipit”: Hình 3-7: Factor “tỉ lệ lipit” đối với chuẩn hai Factor “tỉ lệ gluxit” : Hình 3-8: Factor “tỉ lệ gluxit” đối với chuẩn hai 72 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM Sau đây là mô hình bộ điều khiển mờ thứ nhất : Hình 3-9: Mô hình bộ điều khiển mờ thứ nhất Sử dụng đầu ra của bộ điều khiển mờ thứ nhất làm dữ liệu đầu vào của bộ điều khiển mờ thứ hai : Hình 3-10: Mô hình bộ điều khiển mờ thứ hai 73 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM Trong đó, các factor “tỉ lệ dinh dưỡng”, “giá tiền” và “độ dùng lại” là : Factor “tỉ lệ dinh dưỡng” : Hình 3-11: Factor “tỉ lệ dinh dưỡng” Factor “giá tiền” : Hình 3-12: Factor “giá tiền” 74 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM Factor “độ dùng lại” : Hình 3-13:Factor “độ dùng lại” Sau khi xây dựng xong hai bộ điều khiển mờ, chúng ta tiếp tục xây dựng mạng neural cho phép hiệu chỉnh lại trọng số luật của hai bộ điều khiển mờ. Sau quá trình hiệu chỉnh bằng dữ liệu mẫu, chúng ta thu được bộ điều khiển mờ với kết quả sắp xếp phù hợp, chính xác hơn. Sau khi đã xây dựng và hiệu chỉnh bộ điều khiển mờ, chúng ta xây dựng giải thuật để tạo bộ lọc nhằm giảm thiểu dữ liệu qua bộ điều khiển mờ. Cách xây dựng mạng neural và bộ lọc tiếp tục được trình bày ở phần tiếp theo 3.4 Xây dựng bộ lọc cho fuzzy bằng kỹ thuật máy học. Như đã đề cập ở phần trước, chúng ta có thể sử dụng một bộ lọc để giảm bớt tính toán cho bộ điều khiển mờ. Nếu chúng ta chỉ sử dụng bộ điều khiển mờ, chúng ta cần đánh giá hết tất cả các ứng cử viên (bữa ăn) và chọn ra ứng cử viên tốt nhất. Như thế, hệ thống sẽ phải đánh giá cả những ứng cử viên tồi, hay những ứng cử viên không có khả năng được chọn. Điều này sẽ làm tăng các xử lý không cần thiết và làm giảm chất lượng của hệ thống. Để giảm tải cho bộ điều khiển mờ và tăng tốc độ xử lý chung của toàn hệ thống, chúng ta sẽ sử dụng một bộ lọc. Bộ lọc này có nhiệm vụ lọc tất cả các ứng viên chắc chắn không được chọn hay các ứng cử viên có khả năng được chọn là rất thấp. Điều này có vẻ làm tăng yêu cầu xử lý vì chúng ta phải áp dụng bộ lọc cho từng ứng viên. Tuy nhiên, yêu cầu xử lý chung của toàn hệ thống sẽ giảm đi đáng kể. Chúng ta có thể lấy ví dụ như sau, chẳng hạn một bữa ăn chỉ có ba món (canh, mặn, và tráng miệng), và mỗi loại có n món, như vậy chúng ta sẽ có tất cả n3 ứng viên (hay bữa ăn). Khi đó, việc đánh giá tất cả các ứng cử viên yêu cầu áp dụng tất cả các luật mờ cho từng ứng viên. Thông thường số luật mờ trong một hệ thống là lớn, đặc biệt trong hệ thống sắp xếp món ăn này, do có rất nhiều điều kiện nên có rất nhiều luật mờ. Mặc dù chúng ta đã có những cải tiến khi xây dựng bộ điều khiển mờ phân tán là giảm đi đáng kể số lượng luật, nhưng do việc sử dụng bộ điều khiển mờ thường xuyên trong quá trình xếp lịch nên tổng số phép xử lý của hệ thống sẽ rất 75 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM lớn. Mặt khác, trong số n3 ứng viên chắc chắn có những ứng viên không bao giờ được chọn, chẳng hạn các bữa có các món kỵ nhau, thực phẩm chế biến kỵ nhau, giá tiền quá cao, tỉ lệ dinh dưỡng không phù hợp. Khi sử dụng bộ lọc, thường số luật trong bộ lọc sẽ ít hơn so với số luật trong hệ thống mờ vì bộ lọc chỉ xác nhận thông tin được chọn hay không được chọn của các ứng viên. Các ứng viên sẽ được bộ lọc đánh giá trước, sau đó, các ứng viên “đạt tiêu chuẩn” sẽ tiếp tục được đánh giá trong hệ thống mờ để chọn ra ứng viên tốt nhất. Bộ lọc sử dụng trong hệ thống chỉ được gọi thực hiện khi có sự tổ hợp bữa ăn từ các món ăn nên tổng số phép xử lý dành cho bộ lọc so với bộ điều khiển mờ là không đáng kể. Do đó, mặc dù cần thêm các tính toán cho bộ lọc nhưng yêu cầu tính toán chung của cả hệ thống sẽ giảm. Việc xây dựng bộ lọc cũng tương tự việc xây dựng các luật mờ. Chúng ta có thể sử dụng tri thức của các chuyên gia trong lĩnh vực tương ứng (trong trường hợp này là các chuyên gia dinh dưỡng) để xác định các luật của bộ lọc. Cách thứ hai là chúng ta sử dụng dữ liệu mẫu để xác nhận các mẫu không xuất hiện hay các ứng viên không bao giờ được chọn. Từ các mẫu đó, chúng ta xây dựng nên các luật cho bộ lọc. Trong cách thứ hai, việc thiếu dữ liệu hay dữ liệu không đầy dủ sẽ ảnh hưởng rất lớn đến việc xác định các luật của bộ lọc. Khi xác định sai luật, bộ lọc có thể bỏ qua cả những ứng viên tốt nhất và cũng có thể xác nhận các ứng viên tồi nhất. Chính vì vậy, dữ liệu học cho việc xác định các luật của bộ lọc là rất quan trọng. Phần lớn các luật trong bộ lọc có dạng “Nếu X là A thì bữa ăn (ứng viên) không thỏa”. Trong bộ lọc cũng có thể có các luật gồm hai, ba, thành phần như “Nếu X là A, Y là B, thì ứng viên không thỏa”. Các luật có một thành phần sẽ có tầm ảnh hưởng rộng hơn các luật có hai thành phần. Số lượng thành phần càng lớn thì độ chi tiết của luật càng tăng. Chính vì vậy, chúng ta cần kiểm tra xem có luật nào bao (chứa) luật nào không trong quá trình xác định luật. Điều này sẽ làm giảm số luật cũng như yêu cầu tính toán. Đối với bài toán xếp lịch ăn trưa, chúng ta sẽ tiến hành xây dựng bộ lọc từ các dữ liệu mẫu sử dụng thuật toán quy nạp cây quyết định ID3. Có hai hướng tiếp cận cho việc xây dựng cây quyết định : - Hướng thứ nhất : Xây dựng cây quyết định dựa trên các đặc trưng : món mặn, món canh, món tráng miệng . o Ưu điểm : Với CSDL đã có , kết quả thực hiện lọc chính xác sau khi tạo được cây quyết định o Khuyết điểm : ƒ Khi thêm mới một món ăn vào CSDL , độ chính xác của quá trình lọc giảm dần, đến một lúc nào đó bộ lọc trở nên mất tác dụng. ƒ Số luật tạo được lớn. o Khắc phục: Cần thực hiện việc học lại nếu có thêm một món ăn vào CSDL - Hướng thứ hai : Xây dựng cây quyết định dựa trên các đặc trưng : tỉ lệ dinh dưỡng, độ dùng lại và giá tiền. o Ưu điểm : ƒ số luật tạo được ít hơn hướng tiếp cận thứ nhất ƒ Khi thêm mới dữ liệu, quá trình lọc vẫn giữ được tính ổn định, tuy có giảm nhưng mức độ ảnh hưởng không cao o Khuyết điểm : ƒ Đối với CSDL hiện tại, việc lọc vẫn nhận những giá trị dư thừa, không chính xác như khi tiếp cận theo hướng thứ nhất 76 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM Đối với bài toán của chúng ta, việc thêm một món ăn hay xóa một món ăn ra khỏi CSDL diễn ra thường xuyên, do vậy chúng ta sẽ xây dựng cây quyết định theo hướng tiếp cận thứ hai. Hơn nữa, đối với khuyết điểm của hướng tiếp cận thứ hai này, do chúng ta chỉ lọc bớt dữ liệu giảm tải cho bộ điều khiển mờ nên việc nhận thêm vào những giá trị dư thừa vẫn không làm giảm chất lượng của quá trình sắp lịch. Bộ lọc được xây dựng thành ba thành phần: • Bộ lọc tĩnh: sử dụng các nguyên tắc về dinh dưỡng do Vụ Mầm Non quy định (lượng calo, cơ cấu năng lượng đối với protein, lipit và gluxit) để xây dựng. Các nguyên tắc này là các luật tĩnh và có giá trị tĩnh. • Bộ lọc động : sử dụng các yếu tố: món ăn kỵ nhau, thực phẩm kỵ nhau, giá tiền, khoảng thời gian không sử dụng món ăn hay thực phẩm Các yếu tố này là các luật tĩnh nhưng có giá trị thay đổi theo thời gian hoặc theo kinh nghiệm của người sử dụng. • Bộ lọc sử dụng kỹ thuật máy học : sử dụng dữ liệu mẫu là các bữa ăn trưa đã được sử dụng tại các trường mầm non trong những năm gần đây và sử dụng thuật toán quy nạp cây quyết định ID3 để thực hiện việc học xây dựng cây tạo nên bộ lọc. Do có các luật tĩnh nên việc xây dựng bộ lọc tĩnh và bộ lọc động khá đơn giản. Ở đây, chúng ta tập trung vào việc xây dựng bộ lọc động sử dụng kỹ thuật máy học. Theo hướng tiếp cận thứ hai mà chúng ta đã tìm hiểu ở trên, các đặc trưng của chúng ta là: tỉ lệ dinh dưỡng, độ dùng lại, giá tiền. Do tiêu chí lọc mà chúng ta đã đưa ra: lọc loại bỏ tất cả các bữa ăn không bao giờ được sử dụng. Do đó, nhiệm vụ của bộ lọc là cần tìm ra được danh sách các bữa ăn không bao giờ được sử dụng đó. Ở đây, một bữa ăn có dùng được hiểu là tồn tại một độ dùng lại nào đó sao cho bữa ăn được chọn. Từ đó, một bữa ăn không dùng nghĩa là, với mọi giá trị của độ dùng lại bữa ăn vẫn không được chọn. Do vậy, yếu tố độ dùng lại không được xem là đặc trưng của bộ lọc. Điều này có nghĩa là bộ lọc của chúng ta sẽ có hai đặc trưng, đó là : tỉ lệ dinh dưỡng và giá tiền. Với dữ liệu đầu vào : tỉ lệ dinh dưỡng, giá tiền, ta thực hiện việc chia khoảng cho các đặc trưng này. Nguyên nhân phải thực hiện việc chia khoảng: Ở đây, các đặc trưng của chúng ta đều là số thực. Giả sử chúng ta có luật: “Nếu giá trị của A là 50.5 thì kết luật: không chọn”. Bây giờ, ta có một giá trị khác của A là 50.6, vậy kết luận là gì ? (không thể kết luận được); nếu không chia khoảng thì ứng với từng giá trị ta phải có luật tương ứng. Do các giá trị ở đây là giá trị thực nằm trong một miền liên tục nên chúng ta không thể có đủ số luật. Bằng thực nghiệm, chúng ta thu được các khoảng chia như sau : Đối với đặc trưng tỉ lệ dinh dưỡng: Khoảng chia Miền giá trị 1 0 - 5 2 5 - 10 3 10 - 15 77 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM 4 15 - 20 5 20 - 25 6 25 - 30 7 30 - 35 8 35 - 40 9 40 - 45 10 45 - 50 11 50 - 55 12 55 - 60 13 60 - 65 14 65 - 70 15 70 - 75 16 75 - 80 17 80 - 85 18 85 - 90 19 90 - 95 20 95 - 100 Đối với đặc trưng giá tiền Khoảng chia Miền giá trị 1 0 - 500 2 500 - 1000 3 1000 - 1500 4 1500 - 2000 5 2000 - 2500 6 2500 - 3000 7 3000 - 3500 8 3500 - 4000 9 4000 - 4500 10 4500 - 5000 11 5000 - 5500 12 5500 - 6000 13 6000 - 6500 14 6500 - 7000 15 7000 - 7500 16 7500 - 8000 17 8000 - 8500 18 8500 - 9000 19 9000 - 9500 20 9500 - 10000 78 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM Ứng với bài toán xếp lịch, ta có hai đặc trưng: tỉ lệ dinh dưỡng và giá tiền. Giả sử đặt: tỉ lệ dinh dưỡng là đặc trưng thứ nhất giá tiền là đặc trưng thứ hai. Bước thứ nhất trong quá trình xây dựng bộ lọc là phân khoảng giá trị của các đặc trưng của từng bộ dữ liệu mẫu. Hình 3-14: Phân khoảng giá trị mẫu 79 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM Bước thứ hai: Sau khi chia các khoảng cho các đặc trưng, chúng ta sử dụng dữ liệu mẫu để học và tạo cây quyết định sử dụng thuật toán ID3 Hình 3-15: Sử dụng dữ liệu mẫu để xây dựng cây quyết định 80 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM Bước thứ ba : Sau quá trình sử dụng dữ liệu mẫu để xây dựng cây quyết định. Ở bước này, với một bộ dữ liệu bất kì, ta có thể sử dụng cây để quyết định có chọn mẫu đó hay không. Hình 3-16: Sử dụng cây quyết định để lọc dữ liệu 3.5 Neural Network kết hợp hệ mờ phát sinh luật và điều chỉnh trọng số. Giới thiệu Vấn đề chính của một hệ thống mờ là xác định được tập luật tối ưu. Nếu có tập luật tốt, hệ thống sẽ hoạt động tốt hơn. Ngược lại, tập luật không tốt sẽ làm giảm đáng kể chất lượng của hệ thống và hệ thống sẽ hoạt động kém hiệu quả. Trong một hệ thống mờ, thông thường có nhiều luật trong tập luật được sử dụng để giải quyết vấn đề. Trong tập luật, có thể có một vài luật mâu thuẫn hay thậm chí phủ nhận hoàn toàn các luật khác. Trong hệ thống được xây dựng bởi các chuyên gia, mâu thuẫn giữa các luật sẽ được các chuyên gia điều chỉnh. Còn với hệ thống mờ thích ứng, tiến trình điều chỉnh các luật sẽ được tự động hóa bằng cách sử dụng mạng neural hay thuật toán học tựa neural. Để hiểu được cách hoạt động của quá trình điều chỉnh luật của hệ thống mờ thích ứng, trước hết chúng ta cấn tìm hiểu mạng neural về cách vận hành cũng như quá trình học 81 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM của nó. Mạng neural là một tập hợp gồm các nút và các cạnh nối. Các nút thường được chia thành ba lớp là lớp nhập, (các) lớp ẩn và lớp xuất. Các cạnh nối có trọng số xác định ảnh hưởng của một nút lên nút liên kết với nó. Giá trị nhập được cho vào ở lớp nhập. Thông thường, số nút của lớp nhập bằng với số thành phần của biến (giá trị) nhập. Từng thành phần sẽ được chuyển đến các nút trong lớp ẩn có cạnh nối tương ứng. Tầm ảnh hưởng của từng thành phần đối với nút ẩn được xác định bằng trọng số của cạnh nối. Tại mỗi nút ẩn, trọng ngưỡng của nút ẩn sẽ được cộng với các giá trị được chuyển đến từ các nút nhập (đã nhân với trọng cạnh nối). Đây là tổng trọng hóa của nút ẩn. Sau đó, hàm logistic sẽ được áp dụng trên tổng trọng hóa này để xác định đầu ra của nút ẩn. Đầu ra của mỗi nút ẩn sẽ được chuyển cho các nút ẩn (nếu có lớp ẩn khác) hoặc các nút xuất có cạnh nối tương ứng. Tại các nút xuất này, trọng ngưỡng của nút xuất cộng với các giá trị của các nút ẩn (đã nhân với trọng số của cạnh nối) để tạo thành tổng trọng hóa của nút xuất. Hàm logistic lại được sử dụng để xác định đầu ra cho nút xuất này. Thông thường, số nút xuất của mạng do bài toán quy định. Chẳng hạn nếu mạng dùng để nhận dạng chữ số thì thường có 10 nút xuất tương ứng với 10 chữ số, còn nếu dùng để nhận dạng chữ cái thì thường có 26 nút. Giá trị của từng nút xuất có thể chỉ là giá trị 0 hoặc 1 hoặc cũng là các giá trị thực nằm giữa 0 và 1. Điều này phụ thuộc vào từng bài toán và người cài đặt. Chính do cấu trúc của nó mà mạng neural có thể xấp xỉ bất kỳ hàm nào, miễn là nó có đủ số neural cần thiết. Để có thể xấp xỉ một hàm, mạng cần phải được học hay được huấn luyện. Việc học thực chất là việc cập nhật lại các trọng ngưỡng tại các nút ẩn và các nút xuất và cập nhật các trọng số của các cung nối. Trong cài đặt, người ta thường sử dụng phương pháp học có giám sát để luyện mạng. Trong phương pháp này, dữ liệu học sẽ được đưa vào mạng. Sau khi đi qua mạng, một kết xuất tương ứng sẽ được nhận ở đầu ra và một “thầy giáo” sẽ thông báo khi có một lỗi xảy ra. Lỗi ở đây là kết xuất nhận được không đúng với kết xuất đúng của dữ liệu nhập. Lỗi này sẽ được lan truyền ngược lại trong mạng (từ nút xuất đến nút nhập) và các trọng số sẽ được cập nhập lại. Quá trình này được thực hiện nhiều lần cho đến khi mạng đạt được tỉ lệ cho phép. Trong phần này chúng ta chỉ tìm hiểu cơ bản về mạng neural chứ không đi sâu vào nên nhiều vấn đề quan trọng không được bàn ở đây. Chúng ta chỉ cần hiểu cơ chế hoạt động và quá trình học của mạng neural để có thể hiểu được cách thức học đối với hệ thống mờ. Vậy, tại sao chúng ta phải cho hệ thống mờ học để sinh ra luật? Chúng ta không thể tự tạo ra luật? Như trên đã đề cập, các chuyên gia có thể tạo ra luật và điều chỉnh nó để hệ thống hoạt động tốt hơn. Còn đối với các kỹ sư, không phải là chuyên gia trong lĩnh vực nào đó, khó có thể tự nghĩ ra luật và cũng khó tối ưu luật để tăng chất lượng của hệ thống. Chính vì vậy, khi xây dựng hệ thống mờ, các kỹ sư thường cho hệ thống học để tạo ra và tối ưu các luật đó dựa vào dữ liệu. Ngoài ra, có nhiều trường hợp kiến thức của chuyên gia cũng không thể giúp được gì. Ví dụ máy điều hòa không khí. Mỗi người nghĩ tương tự nhau nhưng không giống nhau khi nói nhiệt độ là “ấm”, “lạnh” hay “thích hợp”. Ngay chính một người thì những từ này không phải lúc nào cũng mang ý nghĩa giống nhau tại các thời điểm khác nhau trong ngày hay trong các mùa khác nhau. Chính vì vậy, mỗi người sử dụng sẽ tạo ra dữ liệu để hệ thống học và như thế hệ thống mới có thể đáp ứng đúng yêu cầu hay hệ thống mới có chất lượng. Sau này, khi yêu cầu thay đổi thì hệ thống chỉ cần học lại và vẫn có thể được sử dụng. Hướng giải quyết Thuộc tính nổi bật của một luật mờ là dạng hình học đơn giản của nó như là một “mảnh” (patch) (có thể tưởng tượng “mảnh” này như sau: giả sử có luật “Nếu x = A thì y = 82 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM B”, trong không gian trạng thái XxY, “mảnh” là hình chữ nhật bị giới hạn có cạnh theo trục X là A và cạnh theo trục Y là B) hoặc tập con mờ trong không gian trạng thái của hệ thống. Người dùng thường tập trung vào hình dạng của các tập mờ vô hướng (như từ 1,6m- 1,7m là cao) tạo thành một luật và bỏ qua hình dạng của luật. Nhưng hình dạng của các tập mờ lại quyết định cấu trúc và hình dạng của luật. Cấu trúc luật này xác định làm thế nào hệ thống mờ có thể ánh xạ dữ liệu nhập thành dữ liệu xuất. Các luật rõ là các luật có dạng đơn giản nhất. Chúng định nghĩa các hộp trong không gian trạng thái nhập-xuất. Các hộp này thuộc về số ít các luật có thể chuyển sang các tập vô hướng. Hầu hết các “mảnh” luật không thể chuyển sang các tập mờ vô hướng. Vì vậy, trong hầu hết các trường hợp, chúng ta không thể ánh xạ một vector trong không gian p-chiều vào trong hệ thống mờ có giá trị vô hướng. Một luật có dạng ellipse (ellipsoidal rule) có hình dạng của một quả trứng. Luật dạng ellipse có thể xem như một độ đo tình trạng không chắc chắn hoặc là một vùng thống kê. Phần này sẽ tìm hiểu chi tiết hệ thống mờ với các luật dạng ellipse. Học không giám sát xác định dạng và điều chỉnh tập luật đầu tiên của các luật dạng ellipse thông qua phương pháp học cạnh tranh. Sau đó, học có giám sát sẽ tối ưu tập luật đó. Một luật mờ có thể có dạng ellipse trong không gian trạng thái nhập-xuất của một hệ thống. Khi đó, hệ thống xấp xỉ một hàm bằng cách bao đồ thị của hàm đó bằng các “mảnh” luật. Hệ thống sẽ lấy trung bình các “mảnh” luật gối lên nhau. Cá luật mờ tốt nhất là các luật có thể phủ được các đầu mút và các phần lồi của hàm. Các hệ thống neural hoặc gom nhóm thống kê có thể xấp xỉ các luật mờ chưa biết từ dữ liệu học. Sau đó, các hệ thống neural có thể điều chỉnh các luật cũ cũng như có thể thêm các luật mới vào tập luật để tăng tính chính xác trong việc xấp xỉ hàm. Chúng ta sử dụng một hệ thống nơron lai, kết hợp giữa học có giám sát và học không có giám sát để tìm và điều chỉnh các luật có dạng ellipse.Học cạnh tranh không giám sát sẽ tìm các nhóm thống kê thứ nhất và thứ hai trong dữ liệu học. Ma trận thống kê của mỗi nhóm sẽ cho một luật dạng ellipse ở tâm vector hoặc ở giữa nhóm dữ liệu. Hệ thống nơron có giám sát sẽ học theo phương pháp giảm gradient. Nó sẽ cực tiểu hóa lỗi của việc xấp xỉ hàm. Trong hệ thống lai, học không giám sát sẽ khởi tạo việc giảm gradient. Hệ thống lai sẽ xấp xỉ hàm với độ chính xác cao hơn các hệ thống chỉ dùng học không giám sát hoặc học có giám sát. Đối với bài toán của chúng ta, chúng ta cần phải xác định ứng cử viên tốt nhất trong tất cả các ứng cử viên. Cụ thể, chúng ta cần xác định một bữa ăn (bao gồm các món) thỏa các điều kiện về dinh dưỡng (như đạm, chất béo,) và các điều kiện khác như ngày ăn gần nhất, giá thành, Nếu chúng ta có dữ liệu, chúng ta có thể áp dụng phương pháp mạng học không giám sát để xác định các luật. Nhưng nếu ta không có dữ liệu, chúng ta có thể nhờ chuyên gia xác định tập luật ban đầu. Từ tập luật ban đầu, chúng ta có thể xác định được các tham số của các luật ellipse (có thể coi chúng là các luật ellipse) để dựa vào đó xác định kết xuất của hệ thống. Chuyển sang giai đoạn học có giám sát, chúng ta sử dụng các tham số đã xác định trong bước trên để điều chỉnh các luật đã có. Như đã nói, chúng ta cần xác định mẫu tốt nhất nên hệ thống không thể học trên một mẫu được mà phải học trên nhiều mẫu cùng một lúc. Vì nếu chúng ta chỉ học trên một mẫu, chúng ta không thể xác định được mẫu tốt nhất. Chúng ta có thể đánh giá thông qua cho điểm nhưng việc cho điểm từng mẫu là vô cùng khó khăn vì có quá nhiều điều kiện. Nói tóm lại, hệ thống sẽ được học trên một tập mẫu đã được sắp xếp. Hệ thống sẽ sắp xếp lại tập mẫu này dựa trên tập luật mà nó đang có hiện 83 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM thời và sau đó so sánh với thứ tự đúng. Hệ thống sẽ căn cứ vào số lỗi sắp xếp sai để cập nhật các tham số. Chúng ta có thể tăng cường lỗi sai bằng cách tăng hình phạt khi khoảng cách giữa vị trí đúng và vị trí hệ thống sắp xếp tăng. Cách này sẽ nhanh chóng đưa các mẫu về gần với vị trí đúng của nó nhưng nó không có nhiều tác dụng trên các tập mà hệ thống đã xếp gần đúng. Chúng ta cũng có thể cho hệ thống học với các tập mẫu đã sắp khác nhau. Điều này có thể làm tăng chất lượng của hệ thống. Sau khi học, chúng ta có thể vừa sử dụng, vừa kiểm tra chất lượng của hệ thống được xây dựng. 84 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM Chương 4 CÀI ĐẶT VÀ ĐÁNH GIÁ 4.1 Cài đặt 4.1.1 Phân tích – Thiết kế 4.1.1.1 Cấu trúc chương trình 4.1.1.2 Giao diện, chức năng chính của chương trình 4.1.2 Mô hình 4.1.2.1 Phân tích ERD 4.1.2.2 Mô hình DFD 4.1.2.3 Mô hình ràng buộc dữ liệu 4.2 Đánh giá và hướng phát triển 4.2.1 Tự đánh giá 4.2.2 Hướng phát triển 85 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM 4.1 Cài đặt 4.1.1 Phân tích – Thiết kế 4.1.1.1 Cấu trúc chương trình: Chương trình gồm có bảy phần chính: • Sắp lịch: sắp xếp các bữa ăn trưa một cách tự động sao cho đảm bảo đủ lượng dinh dưỡng cho các bé ở trường mầm non. • Hiển thị danh sách các món ăn của một bữa: cho phép xem chi tiết thông tin của từng món ăn sẽ dùng trong một bữa đã được xếp. • Quản lý món ăn: cho phép thêm, xóa, sửa một món ăn bất kỳ( ngoại trừ món cơm không được xóa). • Quản lý nguyên liệu món ăn: cho phép thêm, xóa, sửa một nguyên liệu bất kỳ( ngoại trừ ngyên liệu gạo không được xóa). • Lập báo cáo: cho biết chi tiết về những nguyên liệu phải mua đối với một bữa ăn trưa và gía tiền của bữa đó. • Tra cứu: tra cứu các món ăn, nguyên liệu, đồng thời cung cấp thêm một số thông tin cần thiết về dinh dưỡng-sức khỏe. • Quản lý hệ thống: cung cấp một số chức năng cần thiết giúp cho việc quản lý chương trình tốt hơn. 86 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM 4.1.1.2 Giao diện, chức năng chính của chương trình: ng trình. ng trình. ươ a ch ủ n chính c ệ Hình 4-1: Giao di Hình 4-1: Giao 87 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM n. ầ t tu ộ m g a tron ư r n t ă ch ị l p ắ Hình 4-2: S 88 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM t tháng. ộ a trong m a trong ư n tr ă ch ị p l ắ Hình 4-3: s 89 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM t ngày. ộ n trong m ă các danh sách các món sách các các danh ị n th ể Hình 4-4: Hi 90 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM n ầ t tu ộ n trong m ă danh sách các món các món sách danh ị n th ể Hình 4-5: Hi 91 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM t tháng. ộ n trong m ă danh sách các món danh sách các món ị n th ể Hình 4-6: Hi 4-6: Hình 92 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM Hình 4-7: báo cáo chi tiết của một bữa ăn trưa trong ngày. 93 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM 4.1.2 Mô hình 4.1.2.1 Phân tích ERD. Hình 4-8: Mô hình ERD 94 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM 4.1.2.2 Mô hình DFD. Mức 0 : Hình 4-9: Mô hình DFD 95 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM Mức 1: Chi tiết ô xử lý 1.0 (Xếp lịch) Hình 4-10: Chi tiết ô xử lý “xếp lịch” Mức 1 : Chi tiết ô xử lý 3.0 (Cập nhật món ăn) Hình 4-11: Chi tiết ô xử lý “cập nhật món ăn” 96 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM Mức 1 : Chi tiết ô xử lý 4.0 (cập nhật nguyên liệu) Hình 4.12: Chi tiết ô xử lý “cập nhật nguyên liệu” Mức 1 : Chi tiết ô xử lý 5.0 ( In ấn , báo cáo) Hình 4-13: Chi tiết ô xử lý “in ấn, báo cao” 97 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM Mức 1 : Chi tiết ô xử lý 6.0 (Tra cứu) Hình 4-14: Chi tiết ô xử ly “tra cứu” Mức 1 : Chi tiết ô xử lý 8.0 (Quản lý hệ thống) Hình 4-15: Chi tiết ô xử lý “quản lý hệ thống” 98 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM 4.1.2.3 Mô hình ràng buộc dữ liệu. Hình 4-16: Mô hình ràng buộc dữ liệu 4.2 ĐÁNH GIÁ VÀ HƯỚNG PHÁT TRIỂN 4.2.1 Tự đánh giá: Ưu điểm: - Giải quyết trong AI, kết hợp hệ mờ, neural và máy học - Các bữa ăn được chọn sắp xếp đã đảm bảo được về giá thành, không có các món kỵ nhau trong bữa, có độ dùng lại thấp - Chương trình có khả năng sao lưu và khôi phục dữ liệu, nên ta có thể khôi phục lại dữ liệu và sử dụng lại chương trình khi bị hư. - Chương trình đã được chạy xếp lịch cho nhiều tháng và kết quả các bữa ăn thu được vẫn đảm bảo tỉ lệ, thành phần dinh dưỡng trong mỗi bữa. Khuyết điểm: - Thiếu dữ liệu mẫu - Vì thời gian ngắn nên chưa đủ thử nghiệm trên nhiều chỗ khác nhau 99 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM 4.2.2 Hướng phát triển Từ mô hình này có thể phát triển xây dựng chế độ dinh dưỡng không những cho cho trẻ em mà cho cả người lớn ở những nơi công cộng (như công ty, bệnh viện,), cho người bệnh, những người ăn kiêng, 100 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM TÀI LIỆU THAM KHẢO [1] Bùi Công Cường, Nguyễn Doãn Phước , “Hệ mờ, mạng neural và ứng dụng”, NXB KH&KT , 2001. [2] C. Elkan et al., “Fuzzy Logic Symposium", IEEE Expert, August 1994. [3] G. Klir, B. Yuan, Fuzzy sets and fuzzy logic, Prentice Hall, NJ, 1995. [4] V. Kreinovich, G. C. Mouzouris, H. T. Nguyen, “Fuzzy rule based modeling as a universal approximation tool", In: H. T. Nguyen, M. Sugeno (eds.), Fuzzy Systems: Modeling and Control, Kluwer, Boston, MA, 1998, pp. 135 - 195. [5] JunYan, Michael Ryan, James Power, “Using fuzzy logic”, Prentice Hall , 1994 [6] Bart Kosko, “Fuzzy Engineering”, Prentice Hall, 1997 [7] H. T. Nguyen, V. Kreinovich, “Methodology of fuzzy control: an introduction", In: H. T. Nguyen and M. Sugeno (eds.), Fuzzy Systems: Modeling and Control, Kluwer, Boston, MA, 1998, pp. 19 - 62. [8] H. T. Nguyen, E. A.Walker, First course in fuzzy logic, CRC Press, Boca Raton, FL, 1999. [9] Nguyễn Như Phong, “Lý thuyết mờ và ứng dụng”, NXB KH&KT, 2005 [10] M. H. Smith, V. Kreinovich. “Optimal strategy of switching reasoning methods in fuzzy control", In: H. T. Nguyen, M. Sugeno, R. Tong, R. Yager (eds.), Theoretical aspects of fuzzy control, J. Wiley, N.Y., 1995, pp. 117 - 146. [11] Feijun Song, “Cell state fuzzy logic controller automatic design and optimization for high other systems”, Florida Atlantic University , 1999 [12] Th.S Phạm Thế Bảo, “Chuyên đề các hệ thống học: học với cây quyết định”, khoa CNTT, Đại học khoa học tự nhiên, 2006 [13] Chương trình chăm sóc giáo dục trẻ theo lứa tuổi do Bộ Giáo Dục và Đào tạo ban hành năm học 1994 – 1995 [14] Bảng nhu cầu dinh dưỡng khuyến nghị cho người Việt Nam, NXB Y học, Viện dinh dưỡng- Bộ Y tế, 2003 101 Khoa Tóan – Tin học trường Đại Học Khoa Học Tự Nhiên Tp.HCM