Đề tài Tối ưu hoá cấu trúc của mạng nơron mờ bằng giải thuật di truyền

Nội dung text: Đề tài Tối ưu hoá cấu trúc của mạng nơron mờ bằng giải thuật di truyền

1. Đề tài: Tối ưu hoá cấu trúc của mạng nơron mờ bằng giải thuật di truyền
2. MỤC LỤC I: MẠNG NƠRON 2 I.1 Giới Thiệu Mạng Nơron 2 I.1.1 Lịch sử phát triển 2 I.1.2 Căn nguyên sinh học 3 I.1.3 Đơn vị xử lý 5 I.1.4 Hàm xử lý 6 I.1.5 Ứng dụng 11 I.2 Mạng Norn Một Lớp 11 I.3 Mạng Noron Nhiều Lớp (Multi-layer Neural Network) 12 II: MẠNG NƠRON MỜ: 12 III: GIẢI THUẬT DI TRUYỀN 15 1: Các toán tử của giải thật di truyền 16 1.1 Chọn lọc 16 1.2 Lai ghép 17 1.3 Đột biến 19 1.4 Hàm thích nghi 20 2: Xét trong mối quan hệ giữa mạng nơron và giải thuật di truyền 21 2.1 Cross-over (Lai ghép) 22 2.2 Mutation (Đột biến) 23 2.3 Fitness function (Hàm thích nghi) 23 2.4 Selection (chọn lọc) 25 3: Chiến lƣợc điều chỉnh mờ tự động 25 IV: KẾT LUẬN 26
3. Đề tài: Tối ƣu hoá cấu trúc của mạng nơron mờ bằng giải thuật di truyền BÁO CÁO NGHIÊN CỨU KHOA HỌC Tên đề tài: TỐI ƢU HOÁ CẤU TRÚC CỦA MẠNG NƠRON MỜ BẰNG GIẢI THUẬT DI TRUYỀN MỞ ĐẦU Lý do chọn đề tài: Gần đây suy diễn mờ đƣợc ứng dụng trong rất nhiều các vấn đề khác nhau nhƣ: điều khiển máy móc hay trong các hệ thống sản xuất. Một trong những suy diễn mờ đó là mạng nơron mờ. Có lẽ mạng noron không chỉ hấp dẫn đối với những ngƣời yêu thích công nghệ thông tin bởi khả năng do con ngƣời huấn luyện, mà còn bởi những ứng dụng thực tiễn trong cuộc sống của nó. Chúng ta hoàn toàn có thể nhận dạng dấu vết vân tay của tội phạm trong hình sự, có thể dự đoán thị trƣờng chứng khoán, dự đoán thời tiết, dự toán chi phí cho một dự án đƣờng cao tốc, khôi phục những tấm ảnh, hay một chiếc xe lăn dành cho ngƣời khuyết tật có thể nhận đƣợc mệnh lệnh điều khiển bằng cử chỉ, hành động, thậm chí là suy nghĩ của ngƣời ngồi trên xe v.v nhờ có mạng noron nhân tạo. Mạng nơron ban đầu có cấu trúc thô, vấn đề quan trọng là chúng ta phải làm sao cho cấu trúc thô đó trở thành cấu trúc tƣơng đối thích hợp. Do đó vấn đề tối ƣu hoá cấu trúc của mạng nơron là rất cần thiết. Một trong những giải thuật dùng để tối ƣu hoá cấu trúc của mạng nơron là giải thuật di truyền và giải thuật di truyền đƣợc xem là thích hợp nhất. Sinh viên: Trần Thị Thu Hoài_K54C_CNTT 1
4. Đề tài: Tối ƣu hoá cấu trúc của mạng nơron mờ bằng giải thuật di truyền I: MẠNG NƠRON I.1 Giới Thiệu Mạng Nơron I.1.1 Lịch sử phát triển Sự phát triển của mạng nơron trải qua cả quá trình đƣa ra các khái niệm mới lẫn thực thi các khái niệm này. Dƣới đây là các mốc đáng chú ý trong lịch sử phát triển của mạng nơron. * Cuối thế kỷ 19, đầu thế kỷ 20, sự phát triển chủ yếu chỉ là các công việc có sự tham gia của cả ba ngành Vật lý học, Tâm lý học và Thần kinh học, bởi các nhà khoa học nhƣ Hermann von Hemholtz, Ernst Mach, Ivan Pavlov. Các công trình nghiên cứu của họ chủ yếu đi sâu vào các lý thuyết tổng quát về HỌC (learning), NHÌN (vision) và LẬP LUẬN (conditioning), và không hề đƣa ra những mô hình toán học cụ thể mô tả hoạt động của các nơron. * Mọi chuyện thực sự bắt đầu vào những năm 1940 với công trình của Warren McCulloch và Walter Pitts. Họ chỉ ra rằng về nguyên tắc, mạng của các nơron nhân tạo có thể tính toán bất kỳ một hàm số học hay logic nào. * Tiếp theo đó là Donald Hebb, ông đã phát biểu rằng việc thuyết lập luận cổ điển (classical conditioning) (nhƣ Pavlov đƣa ra) là hiện thực bởi do các thuộc tính của từng nơron riêng biệt. Ông cũng nêu ra một phƣơng pháp học của các nơron nhân tạo. * Ứng dụng thực nghiệm đầu tiên của các nơron nhân tạo có đƣợc vào cuối những năm 50 cùng với phát minh của mạng nhận thức (perceptron network) và luật học tƣơng ứng bởi Frank Rosenblatt. Mạng này có khả năng nhận dạng các mẫu. Điều này mở ra rất nhiều hy vọng cho việc nghiên cứu mạng nơron. Tuy nhiên nó có hạn chế là chỉ có thể giải quyết một số lớp hữu hạn các bài toán. * Cùng thời gian đó, Bernard Widrow và Ted Hoff đã đƣa ra một thuật toán học mới và sử dụng nó để huấn luyện cho các mạng nơron tuyến tính thích nghi, mạng có cấu trúc và chức năng tƣơng tự nhƣ mạng của Rosenblatt. Luật học Widrow-Hoff vẫn còn đƣợc sử dụng cho đến nay. Sinh viên: Trần Thị Thu Hoài_K54C_CNTT 2
5. Đề tài: Tối ƣu hoá cấu trúc của mạng nơron mờ bằng giải thuật di truyền * Tuy nhiên cả Rosenblatt và Widrow-Hoff đều cùng vấp phải một vấn đề do Marvin Minsky và Seymour Papert phát hiện ra, đó là các mạng nhận thức chỉ có khả năng giải quyết các bài toán khả phân tuyến tính. Họ cố gắng cải tiến luật học và mạng để có thể vƣợt qua đƣợc hạn chế này nhƣng họ đã không thành công trong việc cải tiến luật học để có thể huấn luyện đƣợc các mạng có cấu trúc phức tạp hơn. * Do những kết quả của Minsky-Papert nên việc nghiên cứu về mạng nơron gần nhƣ bị đình lại trong suốt một thập kỷ do nguyên nhân là không có đƣợc các máy tính đủ mạnh để có thể thực nghiệm. * Mặc dù vậy, cũng có vài phát kiến quan trọng vào những năm 70. Năm 1972 Teuvo Kohonen và James Anderson độc lập nhau phát triển một loại mạng mới có thể hoạt động nhƣ một bộ nhớ. Stephen Grossberg cũng rất tích cực trong việc khảo sát các mạng tự tổ chức (Self organizing network). * Vào những năm 80, việc nghiên cứu mạng nơron phát triển rất mạnh mẽ cùng với sự ra đời của PC. Có hai khái niệm mới liên quan tới sự hồi sinh này, đó là: + Việc sử dụng các phƣơng pháp thống kê để giải thích hoạt động của một lớp các mạng hồi quy (recurrent network) có thể đƣợc dùng nhƣ bộ nhớ liên hợp (associative memory) trong công trình của nhà vật lý học Johh Hopfield. + Sự ra đời của thuật toán lan truyền ngƣợc (back- propagation) để luyện các mạng nhiều lớp đƣợc một vài nhà nghiên cứu độc lập tìm ra nhƣ: David Rumelhart, James McCelland, Đó cũng là câu trả lời cho Minsky-Papert. I.1.2 Căn nguyên sinh học Bộ não con ngƣời chứa khoảng 1011 các phần tử liên kết chặt chẽ với nhau (khoảng 104 liên kết đối với mỗi phần tử) gọi là các nơron. Dƣới con mắt của những ngƣời làm tin học, một nơron đƣợc cấu tạo bởi các thành phần: tế bào hình cây (dendrite), tế bào thân (cell body) và sợi trục thần kinh Sinh viên: Trần Thị Thu Hoài_K54C_CNTT 3
6. Đề tài: Tối ƣu hoá cấu trúc của mạng nơron mờ bằng giải thuật di truyền (axon). Tế bào hình cây có nhiệm vụ mang các tín hiệu điện tới tế bào thân, tế bào thân sẽ thực hiện gộp (sum) và phân ngƣỡng (threshold) các tín hiệu đến. Sợi trục thần kinh làm nhiệm vụ đƣa tín hiệu từ tế bào thân ra ngoài. Điểm tiếp xúc giữa một sợi trục thần kinh của nơron này và tế bào hình cây của một nơron khác đƣợc gọi là khớp thần kinh (synapse). sự sắp xếp của các nơron và mức độ mạnh yếu của các khớp thần kinh đƣợc quyết định bởi các quá trình hoá học phức tạp, sẽ thiết lập chức năng của mạng nơron. Một vài nơron có sẵn từ khi sinh ra, các phần khác đƣợc phát triển thông qua việc học, ở đó có sự thiết lập các liên kết mới và loại bỏ các liên kết cũ. Cấu trúc của mạng nơron luôn luôn phát triển và thay đổi. Các thay đổi sau này có khuynh hƣớng bao gồm chủ yếu là việc làm tăng hay giảm độ mạnh của các mối liên kết thông qua các khớp thần kinh. Mạng nơron nhân tạo không tiếp cận đến sự phức tạp của bộ não. Mặc dù vậy có hai sự tƣơng quan cơ bản giữa mạng nơron nhân tạo và sinh học. Thứ nhất, cấu trúc khối tạo thành chúng đều là các thiết bị tính toán đơn giản (mạng nơron nhân tạo đơn giản hơn nhiều) đƣợc liên kết chặt chẽ với nhau. Thứ hai, các liên kết giữa các nơron quyết định chức năng của mạng. Cần chú ý rằng mặc dù mạng nơron sinh học hoạt động rất chậm so với các linh kiện điện tử (10-3 so với 10-9 giây) nhƣng bộ não có khả năng thực hiện nhiều công việc nhanh hơn nhiều so với các máy tính thông thƣờng. Đó một phần là do cấu trúc song song của mạng nơron sinh học: toàn bộ các nơron hoạt động một cách đồng thời tại một thời điểm. Mạng nơron nhân tạo cũng chia sẻ đặc điểm này. Mặc dù hiện nay, các mạng nơron chủ yếu đƣợc thực nghiệm trên các máy tính số, nhƣng cấu trúc song song của chúng khiến chúng ta có thể thấy cấu trúc phù hợp nhất là thực nghiệm chúng trên các vi Sinh viên: Trần Thị Thu Hoài_K54C_CNTT 4
7. Đề tài: Tối ƣu hoá cấu trúc của mạng nơron mờ bằng giải thuật di truyền mạch tích hợp lớn (VLSI: very large scale integrated circuit), các thiết bị quang và các bộ xử lý song song. Mạng nơron đôi khi đƣợc xem nhƣ là các mô hình liên kết (connectionist models), là các mô hình phân bố song song (parallel-distributed models) có các đặc trƣng phân biệt sau: * Tập các đơn vị xử lý; * Trạng thái kích hoạt hay là đầu ra của đơn vị xử lý; * Liên kết giữa các đơn vị. Xét tổng quát, mỗi liên kết đƣợc định nghĩa bởi một trọng số wjk cho ta biết hiệu ứng mà tín hiệu của đơn vị j có trên đơn vị k; * Một luật lan truyền quyết định cách tính tín hiệu ra của từng đơn vị đầu vào của nó; * Một hàm kích hoạt, hay hàm chuyển (activation function, transfer function), xác định mức độ kích hoạt khác dựa trên mức độ kích hoạt hiện tại; * Một đơn vị điều chỉnh (độ lệch) (bias, offset) của mỗi đơn vị; * Phƣơng pháp thu thập thông tin (luật học- learning rule); * Môi trƣờng hệ thống có thể hoạt động I.1.3 Đơn vị xử lý Một đơn vị xử lí (Hình 1) cũng đƣợc gọi là một nơron hay một nút (node), thực hiện một công việc rất đơn giản: nó nhận tín hiệu vào từ các đơn vị phía trƣớc hay một nguồn bên ngoài và sử dụng chúng để tính tín hiệu ra sẽ đƣợc lan truyền sang các đơn vị khác Sinh viên: Trần Thị Thu Hoài_K54C_CNTT 5
8. Đề tài: Tối ƣu hoá cấu trúc của mạng nơron mờ bằng giải thuật di truyền Trong đó: xi : các đầu vào wji : các trọng số tƣơng ứng với các đầu vào θj : độ lệch (bias) aj : đầu vào mạng (net-input) zj : đầu ra của nơron g(x) : hàm chuyển (hàm kích hoạt). Trong một mạng nơron có ba kiểu đơn vị: * Các đơn vị đầu vào (input units), nhận tín hiệu từ bên ngoài; * Cá đơn vị đầu ra (output units), gửi dữ liệu ra bên ngoài; * Các đơn vị ẩn (hidden units), tín hiệu vào (input) và ra (output) của nó nằm trong mạng. Mỗi đơn vị j có thể có một hoặc nhiều đầu vào: x0, x1, x2, xn, nhƣng chỉ có một đầu ra zj. Một đầu vào tới một đơn vị có thể là dữ liệu từ bên ngoài mạng, hoặc đầu ra của một đơn vị khác, hoặc là đầu ra của chính nó. I.1.4 Hàm xử lý Hàm kết hợp Mỗi một đơn vị trong một mạng kết hợp các giá trị đƣa vào nó thông qua các liên kết với các đơn vị khác, sinh ra một giá trị gọi là net-input. Hàm thực hiện nhiệm vụ này gọi là hàm kết hợp (combination Sinh viên: Trần Thị Thu Hoài_K54C_CNTT 6
9. Đề tài: Tối ƣu hoá cấu trúc của mạng nơron mờ bằng giải thuật di truyền function), đƣợc định nghĩa bởi một luật lan truyền cụ thể. Trong phần lớn các mạng nơron, chúng ta giả sử rằng mỗi một đơn vị cung cấp một bộ cộng nhƣ là đầu vào cho đơn vị mà nó có liên kết. Tổng đầu vào đơn vị j đơn giản chỉ là tổng trọng số của các đầu ra riêng lẻ từ các đơn vị kết nối cộng thêm ngƣỡng hay độ lệch θj n aj =  w ji xij  i 1 Trƣờng hợp wji > 0, nơron đƣợc coi là đang ở trong trạng thái kích thích. Tƣơng tự, nếu nhƣ wji < 0, nơron ở trạng thái kiềm chế. Chúng ta gọi các đơn vị với luật lan truyền nhƣ trên là các sigma units. Trong một vài trƣờng hợp ngƣời ta cũng có thể sử dụng các luật lan truyền phức tạp hơn. Một trong số đó là luật sigma-pi, có dạng nhƣ sau: n m aj =  w ji xi  xik  j i 1 k 1 Rất nhiều hàm kết hợp sử dụng một “độ lệch” hay “ngƣỡng” để tính net-input tới đơn vị. Đối với một đơn vị đầu ra tuyến tính, thông thƣờng θj đƣợc chọn là hằng số và trong bài toán xấp xỉ đa thức θj =1 Hàm kích hoạt (hàm chuyển) Phần lớn các đơn vị trong mạng nơron chuyển net-input bằng cách sử dụng một hàm vô hƣớng (scalar-to-scalar function) gọi là hàm kích hoạt, kết quả của hàm này là một giá trị gọi là mức độ kích hoạt của đơn vị (unit’s activation). Loại trừ khả năng đơn vị đó thuộc lớp ra, giá trị kích hoạt đƣợc đƣa vào một hay nhiều đơn vị khác. Các hàm kích hoạt thƣờng bị ép vào một khoảng giá trị xác định, do đó thƣờng đƣợc gọi là các hàm bẹp (squashing). Các hàm kích hoạt hay đƣợc sử dụng là: + Hàm đồng nhất (Linear function, Identity function) g(x) = x Sinh viên: Trần Thị Thu Hoài_K54C_CNTT 7
10. Đề tài: Tối ƣu hoá cấu trúc của mạng nơron mờ bằng giải thuật di truyền Nếu coi các đầu vào là một đơn vị thì chúng sẽ sử dụng hàm này. Đôi khi một hằng số đƣợc nhân với net-input để tạo ra một hàm đồng nhất + Hàm bƣớc nhị phân (binary step function, hard limit function) Hàm này cũng đƣợc biết đến với tên “hàm ngƣỡng”. Đầu ra của hàm này đƣợc giới hạn vào một trong hai giá trị: 1 nếu (x ≥ 0) g(x) = 0 nếu (x ≤ 0) Dạng hàm này đƣợc sử dụng trong các mạng chỉ có một lớp. Trong hình vẽ sau, θ đƣợc chọn bằng 1. Sinh viên: Trần Thị Thu Hoài_K54C_CNTT 8
11. Đề tài: Tối ƣu hoá cấu trúc của mạng nơron mờ bằng giải thuật di truyền + Hàm sigmoid (Sigmoid function (logsig)) 1 gx() 1 e x Hàm này đặc biệt thuận lợi khi sử dụng cho các mạng đƣợc huấn luyện (trained) bởi thuật toán lan truyền ngƣợc (back-propagation) bởi vì nó dễ lấy đạo hàm, do đó có thể giảm đáng kể tính toán trong quá trình huấn luyện. Hàm này đƣợc ứng dụng trong các chƣơng trình ứng dụng mà các đầu ra mong muốn rơi vào khoảng [0,1]. + Hàm sigmoid lƣỡng cực (Bipolar sigmoid function (tansig)) 1 e x gx() 1 e x Hàm này có các thuộc tính tƣơng tự hàm sigmoid. Nó làm việc tốt đối với các ứng dụng có đầu ra yêu cầu trong khoảng [-1,1]. Sinh viên: Trần Thị Thu Hoài_K54C_CNTT 9
12. Đề tài: Tối ƣu hoá cấu trúc của mạng nơron mờ bằng giải thuật di truyền Các hàm chuyển của các đơn vị ẩn (hidden units) là cần thiết để biểu diễn sự phi tuyến vào trong mạng. Lý do là hợp thành của các hàm đồng nhất là một hàm đồng nhất. Mặc dù vậy nhƣng nó mang tính chất phi tuyến (nghĩa là khả năng biểu diễn các hàm phi tuyến) làm cho các mạng nhiều tầng có khả năng rất tốt trong biểu diễn các ánh xạ phi tuyến. Tuy nhiên đối với luật học lan truyền ngƣợc, hàm phải khả vi và sẽ có ích nếu nhƣ hàm đƣợc gắn trong một khoảng nào đó. Do vậy hàm sigmoid là lựa chọn thông dụng nhất. Đối với các đơn vị đầu ra (output units), các hàm chuyển cần đƣợc chọn sao cho phù hợp với sự phân phối của các giá trị đích mong muốn. Chúng ta đã thấy rằng đối với các giá trị ra trong khoảng [0,1], hàm sigmoid là có ích; đối với các giá trị đích mong muốn là liên tục trong khoảng đó thì hàm này cũng vẫn có ích, nó có thể cho ta các giá trị ra hay giá trị đích đƣợc căn trong một khoảng của hàm kích hoạt đầu ra. Nhƣng nếu các giá trị đích không đƣợc biết trƣớc khoảng xác định thì hàm hay đƣợc sử dụng nhất là hàm đồng nhất. Nếu giá trị mong muốn là dƣơng nhƣng không biết cận trên thì nên sử dụng một hàm kích hoạt dạng mũ (exponential output activation function). Sinh viên: Trần Thị Thu Hoài_K54C_CNTT 10
13. Đề tài: Tối ƣu hoá cấu trúc của mạng nơron mờ bằng giải thuật di truyền I.1.5 Ứng dụng Trong quá trình phát triển, mạng nơron đã đƣợc ứng dụng thành công trong rất nhiều lĩnh vực. Dƣới đây là một số lĩnh vực ứng dụng chính của mạng nơron: Aerospace: Phi công tự động, giả lập đƣờng bay, các hệ thống điều khiển lái máy bay, bộ phát hiện lỗi. Automotive: Các hệ thống dẫn đƣờng tự động cho ô tô, các bộ phân tích hoạt động của xe. Banking: Bộ đọc séc và các tài liệu, tính tiền của thẻ tín dụng. Defense: Định vị- phát hiện vũ khí, dò mục tiêu, phát hiện đối tƣợng, nhận dạng nét mặt, các bộ cảm biến thế hệ mới, xử lí ảnh radar, Electronics: Dự đoán mã tuần tự, sơ đồ chip IC, điều khiển tiến trình, phân tích nguyên nhân hỏng chip, nhận dạng tiếng nói, mô hình phi tuyến. Entertaiment: Hoạt hình, các hiệu ứng đặc biệt, dự báo thị trƣờng. Financial: Định giá bất động sản, cho vay, kiểm tra tài sản cầm cố, đánh giá mức độ hợp tác, phân tích đƣờng tín dụng, chƣơng trình thƣơng mại qua giấy tờ, phân tích tài chính liên doanh, dự báo tỉ lệ tiền tệ. Insurance: Đánh giá việc áp dụng chính sách, tối ƣu hoá sản phẩm. I.2 Mạng Norn Một Lớp Mạng Perceptron Mạng Hopfield Sinh viên: Trần Thị Thu Hoài_K54C_CNTT 11
14. Đề tài: Tối ƣu hoá cấu trúc của mạng nơron mờ bằng giải thuật di truyền Mạng Kiểu Bộ Nhớ Hai Chiều Kết Hợp Thích Nghi (Adaptive Bidirectional Associative) Mạng Kohonen I.3 Mạng Noron Nhiều Lớp (Multi-layer Neural Network) Mạng nơron có từ 2 lớp trở lên đƣợc gọi là mạng nơron nhiều lớp. Mạng nơron nhiều lớp bao gồm một lớp vào, một lớp ra, một hoặc nhiều lớp ẩn Mạng noron nhiều lớp lan truyền ngƣợc sai số(Back- propagation Neural Network) Mạng noron nhiều lớp ngƣợc hƣớng (Counter – propagation Neural Network) II: MẠNG NƠRON MỜ: Việc tích hợp kỹ thuật mạng nơron và logic mờ cho phép kết hợp ƣu điểm của cả hai. Một mặt, mạng nơron cung cấp cấu trúc tính toán dựa trên liên kết (dung thứ lỗi và các tính chất biểu diễn phân tán) và khả năng học cho các hệ logic mờ. Mặt khác, các hệ logic mờ sẽ đƣa vào mạng nơron cơ chế suy diễn dựa trên các luật “if then”, chính sự kết hợp phong phú này cho phép xây dựng các hệ thống tích hợp: Hệ mờ nơron, mạng nơron mờ và các hệ lai. Trong mạng nơron mờ có thể là tín hiệu vào, tín hiệu ra hay trọng số là những số mờ Cũng có trƣờng hợp mạng nơron mờ với tất cả các yếu tố. * Mạng nơron như một công cụ suy diễn Nói mạng nơron nhƣ một công cụ suy diễn vì: mạng nơron có khả năng suy diễn. Với mỗi tín hiệu vào thì mạng nơron sẽ cho một đầu ra tƣơng ứng * Suy diễn mờ dựa trên mạng nơron: Biểu diễn luật mờ: Sinh viên: Trần Thị Thu Hoài_K54C_CNTT 12
15. Đề tài: Tối ƣu hoá cấu trúc của mạng nơron mờ bằng giải thuật di truyền Keller (1992) đề xuất mô hình mạng nơron truyền thẳng nhiều lớp biểu diễn các luật suy diễn cơ sở: If X1 = A1 then Y = B ' ' ' ' a11 a1m1 an1 anmn Lớp vào w w w w Lớp kiểm 11 1m1 n1 nm tra từng mệnh đề d d 1 n 1-t Kết hợp các mệnh đề u u 1 k Lớp ra ' ' b1 bk Mạng noron biểu diễn một luật mờ Giả sử véc tơ độ thuộc của Ai là {ai1, , aimi}, I = 1 n. Có hai cách xác định trọng số: Sinh viên: Trần Thị Thu Hoài_K54C_CNTT 13
16. Đề tài: Tối ƣu hoá cấu trúc của mạng nơron mờ bằng giải thuật di truyền Cách 1: wij = 1 - aij . Khi đó lớp ẩn đầu tiên đo sự bất cập giữa thông tin vào với Ai. Ta xác định di nhƣ là di = max{(1- aij ) aij ' } Hoặc di = max{min(1- aij ), a 'ij } Ở đây Ai’ = {ai1’, ,aimi’}là véc tơ vào tƣơng ứng với mệnh đề X= Ai’ Cách 2 : wij a ij . Khi đó, dj = max{| aij = aij ' |} Các hệ số ai xác định trọng số của mệnh đề X = Ai trong luật (ai có thể đƣợc ngƣời thiết kế cung cấp hoặc đọc từ dữ liệu) Ta thấy t = max {aidi}. Giả sử B tƣơng ứng với tập mờ có độ thuộc {b1, , bk}. Khi đó trọng số ui đƣợc xác định bởi ui = 1- bi. Cuối cùng với bộ đầu vào (A1’, , An’) ta có kết quả: Bj(y ), j 1, p (*) Từ (*) dễ dàng thấy t=0 (tức là bộ đầu vào (A1’, , An’) trùng với (A1, , An) thì bi’= bi) với mọi i nghĩa là Y=B. Ngƣợc lại, khi tổng bất cập giữa thông tin vào với các mệnh đề bằng 1 thì bi’ = 1 đối với mọi i, nghĩa là hệ đƣa ra kết luận: Y = “không biết”. Suy diễn mờ: Mô hình suy diễn mờ dựa trên mạng nơron do Takagi và Hayaki đề nghị là một biến thể của cơ chế suy diễn mờ của Takagi-Sugeno-Kang bao gồm các bƣớc nhƣ sau: + Lựa chọn biến vào ra trong tệp mẫu học. + Chia tập mẫu học thành hai phần: phần huấn luyện và phần kiểm tra. Sinh viên: Trần Thị Thu Hoài_K54C_CNTT 14
17. Đề tài: Tối ƣu hoá cấu trúc của mạng nơron mờ bằng giải thuật di truyền + Xây dựng mạng NNmemb để biểu thị hàm phụ thuộc cho phần IF của các luật. Huấn luyện mạng NNmemb tƣơng ứng với phần IF của luật mờ. + Đơn giản phần THEN của các luật theo phƣơng pháp loại bỏ ngƣợc. + Xác định kết quả ra và diễn giải mờ. III: GIẢI THUẬT DI TRUYỀN Giải thuật di truyền (Genetic Algorithsm- GA) là kĩ thuật giúp giải quyết bài toán bằng cách mô phỏng theo sự tiến hoá của con ngƣời hay của sinh vật nói chung (Dựa trên thuyết tiến hoá con ngƣời của Darwin) trong điều kiện môi trƣờng sống luôn thay đổi. Thuật giải di truyền là một hƣớng tiếp cận tính toán gần đúng, nghĩa là mục tiêu của thuật giải di truyền không nhằm đƣa ra lời giải chính xác tối ƣu mà là đƣa ra lời giải tƣơng đối tối ƣu. Lý thuyết này do Johm Henry Holland (Giáo sƣ của trƣờng đại học Michigan- Mỹ) đề xƣớng vào giữa thập niên 70, thế kỉ XX. Thuật giải di truyền về bản chất là thuật toán tìm kiếm dựa theo quy luật của quá trình tiến hoá tự nhiên. Giải thuật kết hợp sự sống sót của cấu trúc khoẻ nhất trong số các cấu trúc biểu diễn các nhiễm sắc thể với một sự trao đổi thông tin đƣợc lựa chọn ngẫu nhiên để tạo thành một thuật toán tìm kiếm. Giải thuật di truyền nằm trong lĩnh vực tính toán tiến hoá, sử dụng các biểu diễn nhị phân và các sơ đồ để mô hình hoá sự chọn lọc, lai ghép và đột biến. Giải thuật di truyền giải quyết đƣợc vấn đề trên máy tính nhờ vào chƣơng trình tin học để thực hiện những ý tƣởng nêu trên. Không giống nhƣ phƣơng pháp giải tích dựa trên các công thức toán học hay phƣơng pháp suy luận dựa trên kinh nghiệm của các chuyên gia chỉ để ý tới một số có giới hạn các lời giải. Giải thuật di truyền xét đến toàn bộ các lời giải, bằng cách xét trƣớc nhất một số lời giải, sau đó loại bỏ một số thành phần không thích hợp Sinh viên: Trần Thị Thu Hoài_K54C_CNTT 15
18. Đề tài: Tối ƣu hoá cấu trúc của mạng nơron mờ bằng giải thuật di truyền và chọn những thành phần thích nghi hơn để chọn lọc và biến hoá nhằm mục đích tạo ra nhiều lời giải mới có hệ số thích nghi ngày càng cao 1: Các toán tử của giải thật di truyền Giải thuật di truyền sử dụng ba toán tử sau đây: Chọn lọc Lai ghép Đột biến 1.1 Chọn lọc Chọn lọc là quá trình trong đó các cá thể đƣợc sao chép trên cơ sở độ thích nghi của nó. Độ thích nghi là một hàm gán một giá trị thực cho các cá thể trong quần thể. Quá trình này đƣợc mô tả nhƣ sau: * Tính độ thích nghi của từng cá thể trong quần thể hiện hành, lập bảng cộng dồn các giá trị thích nghi (theo số thứ tự gán cho từng cá thể). Giả sử quần thể có n cá thể, gọi độ thích nghi của cá thể thứ I là Fi, tổng dồn thứ i là Fti, tổng độ thích nghi của toàn quần thể là Fm. * Tạo một số ngẫu nhiên F trong đoạn từ 0 đến Fm * Chọn cá thể k đầu tiên thoả mãn Ftk-1 ≤ F ≤ Ftk đƣa vào quần thể của thế hệ mới. Ví dụ: Giả sử quần thể ban đầu là 6 chuỗi nhiễm sắc thể. Tổng giá trị của hàm mục tiêu là 50 nhƣ bảng sau: STT Chuỗi nhiễm sắc Hàm mục % của total total thể tiêu 1 01110 8 16 8 2 11000 15 30 23 3 00100 2 4 25 Sinh viên: Trần Thị Thu Hoài_K54C_CNTT 16
19. Đề tài: Tối ƣu hoá cấu trúc của mạng nơron mờ bằng giải thuật di truyền 4 10010 5 10 30 5 01100 12 24 42 6 00010 8 16 50 Sau đó ta sẽ tạo các số ngẫu nhiên trong khoảng (0, 50), với mỗi số, việc chọn lọc một nhiếm sắc thể đầu tiên với giá trị hàm mục tiêu lớn hơn hay bằng số ngẫu nhiên. Bảy số ngẫu nhiên đƣợc tạo cùng các chuỗi đƣợc chọn thể hiện nhƣ bảng sau: Số ngẫu nhiên 26 2 49 15 40 36 9 Chuỗi nhiễm sắc 4 1 6 2 5 5 2 thể Ví dụ trên chứng tỏ rằng chuỗi nào có giá trị hàm mục tiêu cao sẽ có nhiều con cháu hơn trong thế hệ sau. Khi một chuỗi đã đƣợc chọn cho quá trình tái tạo thì sẽ đƣợc đƣa vào để lai ghép nhằm tạo ra những chuỗi mới. 1.2 Lai ghép Toán tử chọn lọc nhằm tìm ra những cá thể tồn tại tốt nhất nhƣng nó không tạo ra những cá thể mới. Tuy vậy, trong tự nhiên, các con sẽ thừa hƣởng những đặc tính tốt từ cả cha lẫn mẹ chúng. Toán tử tác động trên các cá thể cha mẹ để tạo ra những con lai tốt đƣợc gọi là lai ghép. Chúng đƣợc áp dụng lên cặp cha mẹ đƣợc chọn lựa với xác suất lai ghép pcross. Xác suất này cho ta số lƣợng pcross* popsize (popsize kích thƣớc của quần thể đƣợc lai tạo) nhiễm sắc thể đƣợc lai ghép. Với mỗi nhiễm sắc thể trong quần thể: Phát sinh một số ngẫu nhiên r trong miền [0;1] Nếu r < pcross, chọn nhiễm sắc thể đó để lai ghép Sinh viên: Trần Thị Thu Hoài_K54C_CNTT 17
20. Đề tài: Tối ƣu hoá cấu trúc của mạng nơron mờ bằng giải thuật di truyền Sau đó, ta kết hợp các nhiễm sắc thể đƣợc chọn một cách ngẫu nhiên lại. Mỗi cặp nhiễm sắc thể, chúng ta có thể phát sinh một số ngẫu nhiên pos từ miền [1;L] (L là tổng số bít trong nhiễm sắc thể). Số pos này sẽ cho ta vị trí của điểm lai ghép. Ví dụ ta có 2 nhiễm sắc thể: (a1 a2 aposapos+1 aL) và (b1 b2 bposbpos+1 bL) Sau khi đƣợc lai ghép, nó sẽ đƣợc thay thế bởi cặp con cháu (a1 a2 apos bpos+1 bL) và (b1 b2 bpos apos+1 aL) Nhƣ vậy toán tử này sau khi đƣợc thực hiện sẽ cho ra hai chuỗi mới, mỗi chuỗi đều đƣợc thừa hƣởng những đặc tính lấy ra từ cha và mẹ của chúng. Chọn lọc cá thể và lai ghép cho phép giải thuật di truyền sử dụng những thông tin đã có để tìm kiếm trực tiếp trên những vùng tốt hơn. Các ví dụ dƣới đây thể hiện các hình thức của lai ghép: Ví dụ 1 Trƣớc khi lai ghép 1001101 0000110 Sau khi lai ghép tại vị trí giữa số thứ tự 4 và 5, chúng ta sẽ có: (A) 100| 1101 000| 1101 (B’) (B) 000| 0110 100| 0110 (A’) Ví dụ 2 Sinh viên: Trần Thị Thu Hoài_K54C_CNTT 18
21. Đề tài: Tối ƣu hoá cấu trúc của mạng nơron mờ bằng giải thuật di truyền Trƣớc khi lai ghép 1001101 0000110 Sau khi lai ghép tại vị trí giữa số thứ tự 3 và 4, chúng ta sẽ có: (A) 1001| 101 0000| 101 (B’’) (B) 0000| 110 1001| 110 (A’’) 1.3 Đột biến Là việc thay đổi trị số của một số trong dãy số, thí dụ 0 thành 1 hoặc 1 thành 0, cho trƣờng hợp dùng dãy số theo hệ nhị phân. So với lai ghép, toán tử này rất ít xảy ra. Theo kết quả nghiên cứu của Kenneth De Jong thì tỉ lệ lai ghép trung bình là 0.6 trong khi tỉ lệ đột biến là 0.001, phần còn lại 0.399 là chọn lọc Lai ghép dùng lại những tin tức có sẵn trong các thành phần của thế hệ trƣớc và truyền lại cho thế hệ sau, trong khi đó đột biến tạo ra những tin tức hoàn toàn mới. Các toán tử đột biến nhằm tạo ra những thông tin mới trong quần thể đem lai tạo tại các vị trí bít (gen) nào đó (quần thể mà ta xem xét ở đây có popsize cá thể, mỗi cá thể đƣợc biểu thị qua L bít/gen). Đột biến đƣợc áp dụng với xác suất pmu. Số lƣợng bít đột biến là pmu*L*popsize bít. Mỗi bít có cơ hội đột biến là nhƣ nhau. Toán tử này có thể đƣợc xử lý nhƣ sau: Với mỗi nhiễm sắc thể trong quần thể và mỗi bít trong nhiễm sắc thể : Phát sinh một số ngẫu nhiên r trong miền [0;1]. Nếu r < pmu, tiến hành đột biến tại bít đó. Các thao tác xử lý này đƣợc áp dụng lặp lại cho tới khi các cá thể con, cháu của chúng tăng trƣởng tới kích cỡ mong muốn của quần thể. Ví dụ 1: Sinh viên: Trần Thị Thu Hoài_K54C_CNTT 19
22. Đề tài: Tối ƣu hoá cấu trúc của mạng nơron mờ bằng giải thuật di truyền 100111 sẽ đƣợc đột biến thành 100110, trong đó số 1 ở hàng cuối (tính từ trái) đã đƣợc đổi thành 0. Ví dụ 2: 110110 sẽ đƣợc biến đổi thành 111110, trong đó số 0 ở vị trí thứ 3 (tính từ trái) đã đƣợc đổi thành 1. 1.4 Hàm thích nghi I.4.1 Ánh xạ giá trị hàm mục tiêu sang giá trị thích nghi Vì hàm thích nghi phải nhận giá trị không âm, do đó cần phải xây dựng ánh xạ hàm mục tiêu đang xét trong bài toán sang hàm thích nghi thông qua một hoặc nhiều lần ánh xạ. Nếu bài toán tối ƣu là cực tiểu một hàm đánh giá g(x), việc chuyển từ hàm đánh giá sang hàm thích nghi để sử dụng với giải thuật di truyền nhƣ sau: Cmax – g(x) khi g(x) < Cmax f(x) = 0 trong các trƣờng hợp khác Ở đây, Cmax là một tham số đầu vào. Ví dụ, có thể lấy Cmax là giá trị lớn nhất của g(x) trong quần thể hiện tại hoặc có thể là giá trị lớn nhất sau k vòng lặp. Nói chung Cmax khác nhau tuỳ thuộc vào giá trị các biến của quần thể Nếu hàm mục tiêu gốc tăng hoặc đang xét bài toán cực đại hoá một hàm u(x) nào đó, ta có thể chuyển sang hàm thích nghi nhƣ sau: Cmin + u(x) khi u(x) < Cmin Sinh viên: Trần Thị Thu Hoài_K54C_CNTT 20
23. Đề tài: Tối ƣu hoá cấu trúc của mạng nơron mờ bằng giải thuật di truyền f(x) = 0 trong các trƣờng hợp khác Ở đây, Cmin là tham số đầu vào, có thể là trị tuyệt đối của u(x) bé nhất trong quần thể hiện tại hoặc trong k vòng lặp cuối cùng hoặc là một hàm của biến quần thể. I.4.2 Điều chỉnh độ thích nghi Một vấn quan trọng là điều chỉnh số con cháu. Điều này đặc biệt quan trọng cho một vài vòng lặp đầu tiên, khi một vài cá thể “siêu” có tiềm năng chiếm lĩnh phần lớn quần thể và làm cho hội tụ sớm. Điều chỉnh độ thích nghi có thể giúp giải quyết vấn đề này. Có nhiều kiểu điều chỉnh khác nhau, tuy nhiên điều chỉnh tuyến tính là hay gặp nhất. Gọi f là độ thích nghi gốc, f’ là độ thích nghi đã đƣợc biến đổi. Độ thích nghi theo điều chỉnh tuyến tính đƣợc xác định theo quy tắc: f’ = a*f + b Trong đó, hệ số a, b đƣợc xác định sao cho: f’avg = favg Và f’max = Cmult*favg Ở đây, Cmult là số các bản sao cần thiết đối với một thành viên tốt nhất. Với lƣợng biến tƣơng đối nhỏ (n = 50 đến 100) 2: Xét trong mối quan hệ giữa mạng nơron và giải thuật di truyền Các toán tử lai ghép, đột biến, chọn lọc và hàm thích nghi đƣợc áp dụng một cách cụ thể Một cá thể bao gồm các thông tin: các hàm thuộc hình tam giác và các giá trị thực. Sinh viên: Trần Thị Thu Hoài_K54C_CNTT 21
24. Đề tài: Tối ƣu hoá cấu trúc của mạng nơron mờ bằng giải thuật di truyền 2.1 Cross-over (Lai ghép) Toán tử lai ghép nghĩa là thay đổi vị trí đỉnh của hàm thành viên thô. Cách thức làm việc của toán tử này thể hiện trong hình 4. Có hai chuỗi (cha, mẹ) trong một mẫu đƣợc lựa chọn bất kỳ. Sử dụng các chuỗi lựa chọn này, điểm lai ghép cũng đƣợc lựa chọn giữa các giá trị để xây dựng nên vị trí đỉnh của Sinh viên: Trần Thị Thu Hoài_K54C_CNTT 22
25. Đề tài: Tối ƣu hoá cấu trúc của mạng nơron mờ bằng giải thuật di truyền hàm thành viên. Cấu trúc đƣợc thay đổi giữa mỗi chuỗi dựa trên điểm lai, các kết quả, chúng phải trải qua toán tử lai tạo ra 4 kiểu. (1) các giá trị ở bên phải của chuỗi đƣợc kế thừa từ một chuỗi (A) và các giá trị bên cạnh đƣợc kế thừa từ một chuỗi khác (B), trong đó mỗi giá trị là bản sao bởi tổng các giá trị của một chuỗi. (2) Các giá trị ở bên phải của chuỗi đƣợc kế thừa từ chuỗi (B) và các giá trị bên cạnh đƣợc kế thừa từ chuỗi (A), trong đó mỗi giá trị là bản sao của tổng các giá trị của chuỗi. (3) Cũng giống nhƣ cách thức trên, các giá trị bên trái của chuỗi đƣợc kế thừa từ chuỗi (A). (4) các giá trị bên trái của chuỗi đƣợc kế thừa từ chuỗi (B). Nhƣ đã thể hiện ở hình 4, đỉnh của hàm thành viên đƣợc thay đổi đối với mỗi kết quả. Kết quả có thể kế thừa thông tin di truyền ở mức cao hơn từ hai cha mẹ bởi toán tử lai ghép. Các giá trị thứ hai và thứ ba trong thao tác mã hoá đƣợc thừa kế mà không thay đổi. 2.2 Mutation (Đột biến) Toán tử đột biến xuất hiện đối với các chuỗi, chúng trải qua toán tử đột biến, với xác suất Pm. Toán tử đột biến trong này có nghĩa là hàm thành viên lựa chọn đƣợc cắt bớt, đƣợc thể hiện trong hình 5. Chúng ta có thể mong rằng để làm giảm bớt số luật mờ và thu đƣợc cấu trúc nhỏ nhất của mô hình mờ bởi thao tác này. Theo cách này, một chuỗi mới đƣợc sinh ra bằng các thao tác lai ghép và đột biến. Các thao tác này nhằn đƣa ra một cấu trúc thích hợp của mô hình mờ, tƣơng ứng với quá trình điều chỉnh thô. 2.3 Fitness function (Hàm thích nghi) Sinh viên: Trần Thị Thu Hoài_K54C_CNTT 23
26. Đề tài: Tối ƣu hoá cấu trúc của mạng nơron mờ bằng giải thuật di truyền Chúng ta đặt hàm thích nghi để đánh giá mỗi chuỗi liệu có mong muốn đƣợc hay không. Hàm thích nghi này bao gồm số các hàm thành viên và tổng bình phƣơng lỗi giữa giá trị ra của mô hình mờ và giá trị mong muốn. Chúng ta xác định hàm F này nhƣ sau: F(si) = E + A*N Trong đó, si là chuỗi thứ i, E là tổng bình phƣơng lỗi giữa giá trị ra của mô hình mờ và giá trị mong muốn, A là hằng số, N là số hàm thành viên. Chúng ta xác định đƣợc rằng chuỗi nào có độ thích nghi nhỏ hơn hay lớn hơn. Sinh viên: Trần Thị Thu Hoài_K54C_CNTT 24
27. Đề tài: Tối ƣu hoá cấu trúc của mạng nơron mờ bằng giải thuật di truyền 2.4 Selection (chọn lọc) Dựa vào giá trị thích nghi, mỗi chuỗi đƣợc lựa chọn hay không ở thế hệ kế tiếp. Chúng ta chấp nhận duy trì chiến lƣợc là các chuỗi có độ thích nghi cao tồn tại trong thế hệ kế tiếp và chiến lƣợc lấy mẫu rằng các chuỗi đƣợc lựa chọn tồn tại một cách ngẫu nhiên trong thế hệ kế tiếp. Các chuỗi trải qua các phép toán di truyền nhiều có độ thích nghi cao, hơn nữa chúng sẽ tiếp tục tồn tại trong thế hệ kế tiếp bằng phép chọn lọc. Phép chọn lọc này, chúng thay đổi mẫu của các chuỗi, thực hiện “sự tiến hoá.” 3: Chiến lược điều chỉnh mờ tự động Thuật toán điều chỉnh để thu đƣợc mô hình mờ tối ƣu. Thủ tục này đƣợc thể hiện ở hình 6 (1) Thế hệ khởi tạo có một vài chuỗi trong đó mỗi chuỗi bao gồm một tham số để xây dựng mô hình mờ đƣợc sinh ra một cách ngẫu nhiên (2) Các toán tử đột biến và lai ghép thực hiện việc tạo các chuỗi mới. Thuật toán di truyền xác định cấu trúc của mô hình mờ thô và số luật Sinh viên: Trần Thị Thu Hoài_K54C_CNTT 25
28. Đề tài: Tối ƣu hoá cấu trúc của mạng nơron mờ bằng giải thuật di truyền mờ nhỏ nhất. Các toán tử này phù hợp với quá trình điều chỉnh thô, nhƣ đã đề cập trƣớc đó (3) Sử dụng các chuỗi trải qua các toán tử di truyền, các hàm thành viên và các giá trị thực trong mỗi chuỗi đƣợc ăn khớp với luật delta [8]. Luật delta xác định cấu trúc mô hình mờ tốt.Thao tác này phù hợp với quá trình điều chỉnh thô (4) Mỗi chuỗi đƣợc đánh giá trên cơ sở một hàm thích nghi để đạt đƣợc biện pháp định hƣớng (5) Dựa trên giá trị thích nghi, mỗi chuỗi trải qua thao tác lựa chọn, chúng thay đổi mẫu của chuỗi và thực hiện “sự tiến hoá”. (6) Nếu chúng ta thu đƣợc chuỗi mục tiêu hoặc tìm kiếm đạt đến thế hệ giới hạn, sự tìm kiếm là quá rộng; nói cách khác là quay trở lại toán tử di truyền(2). Chúng ta xác định đƣợc chuỗi mục tiêu khi độ thích nghi của chuỗi đó hội tụ trong lỗi đích. IV: KẾT LUẬN Đề tài: Tối ƣu hoá cấu trúc của mạng nơron là một đề tài khó và đang trong quá trình tiếp tục đƣợc nghiên cứu. Mong đƣợc sự đóng góp của thầy cô và các bạn để đề tài đƣợc hoàn thiện Sinh viên: Trần Thị Thu Hoài_K54C_CNTT 26