Đề tài Mạng nơ-Ron nhân tạo truyền thẳng nhiều lớp

Lời cảm ơn Em xin bày tỏ lòng biết ơn sâu sắc tới GS.TS. Hà Quang Thụy, thày đã hướng dẫn, chỉ dạy tận tình để em hoàn thành luận văn này. Em xin chân thành cảm ơn các thày, cô giáo khoa Công nghệ thông tin - Trường Đại học công nghệ - Đại học Quốc gia Hà nội đã truyền thụ kiến thức cho em trong suốt quá trình học tập vừa qua. Tôi cũng xin cảm ơn cơ quan, bạn bè đồng nghiệp, gia đình và những người thân đã cùng chia sẻ, giúp đỡ, động viên, tạo mọi điều kiện thuận lợi để tôi hoàn thành nhiệm vụ học tập và cuốn luận văn này. Hà nội, ngày 09 tháng 11 năm 2007 Học viên Phạm Thị Hoàng Nhung 4 Mục lục Lời cảm ơn............................................................................................................... i Mục lục .............................................................................................................. 4 Danh sách hình vẽ.................................................................................................. 7 Danh sách bảng biểu ............................................................................................. 9 MỞ ĐẦU ............................................................................................................ 10 CHƯƠNG 1 - MẠNG NƠ-RON NHÂN TẠO TRUYỀN THẲNG NHIỀU LỚP.................................................................................................... 13 1.1 Giới thiệu về mạng nơ-ron nhân tạo.......................................................... 13 1.1.1 Khái niệm cơ bản................................................................................ 13 1.1.2 Mô hình mạng nơ-ron nhân tạo.......................................................... 15 1.1.3 Khả năng ứng dụng của mạng nơ-ron nhân tạo ................................. 18 1.2 Mạng nơ-ron lan truyền thẳng nhiều lớp................................................... 19 1.2.1 Mạng perceptron một lớp ................................................................... 19 1.2.2 Mạng perceptron nhiều lớp ................................................................ 22 1.2.3 Một số vấn đề cần chú ý khi sử dụng mạng MLP.............................. 30 Kết luận chương .............................................................................................. 33 CHƯƠNG 2 - KẾT HỢP GIẢI THUẬT DI TRUYỀN VỚI GIẢI THUẬT LAN TRUYỀN NGƯỢC SAI SỐ ĐỂ TỐI ƯU HOÁ TRỌNG SỐ MẠNG NƠ-RON NHÂN TẠO ....................................................... 34 2.1 Giới thiệu giải thuật di truyền ................................................................... 34 2.1.1 Giới thiệu............................................................................................ 34 2.1.2 Tư tưởng chính của giải thuật di truyền ............................................. 35 2.1.3 Giải thuật di truyền đơn giản.............................................................. 37 2.1 Ứng dụng giải thuật di truyền vào bài toán tối ưu hoá trọng số của mạng nơ-ron nhân tạo ......................................................................................... 41 2.2.1 Xây dựng hàm giá .............................................................................. 42 2.2.2 Mã hoá nhiễm sắc thể ......................................................................... 42 2.2.3 Lai ghép .............................................................................................. 43 5 2.2.4 Đột biến .............................................................................................. 44 2.2.5 Thử nghiệm ........................................................................................ 45 2.2.6 Giải thuật đề xuất ............................................................................... 49 2.3 Kết hợp giải thuật di truyền với giải thuật lan truyền ngược sai số để tối ưu hoá trọng số mạng nơ-ron nhân tạo .......................................................... 51 2.3.1 Đặt vấn đề........................................................................................... 51 2.3.2 Kết hợp giải thuật di truyền và giải thuật lan truyền ngược sai số..... 53 Kết luận chương .............................................................................................. 55 CHƯƠNG 3 - ỨNG DỤNG MẠNG NƠ RON NHÂN TẠO VÀO VIỆC DỰ BÁO LƯU LƯỢNG NƯỚC ĐẾN HỒ HOÀ BÌNH ...................... 57 3.1 Điều kiện địa lý, tự nhiên, khí tượng thuỷ văn lưu vực sông Đà .............. 57 3.1.1 Vị trí địa lý.......................................................................................... 57 3.1.2 Địa hình .............................................................................................. 58 3.1.3 Điều kiện địa chất............................................................................... 58 3.1.4 Điều kiện thổ nhưỡng......................................................................... 58 3.1.5 Đặc điểm khí hậu................................................................................ 58 3.1.6 Đặc điểm chế độ thuỷ văn .................................................................. 59 3.1.7 Thống kê dữ liệu thu thập được.......................................................... 63 3.2 Các phương pháp dự báo........................................................................... 64 3.2.1 Dựa trên mô hình vật lý...................................................................... 64 3.2.2 Dựa trên mô hình toán........................................................................ 66 3.2.3 Hướng tiếp cận mới ............................................................................ 67 3.3 Một số chỉ tiêu đánh giá kết quả dự báo.................................................... 67 3.4 Dự báo lưu lượng đến hồ Hoà Bình trước 10 ngày................................... 68 3.4.1 Phần mềm xây dựng ........................................................................... 68 3.4.2 Số liệu sử dụng ................................................................................... 69 3.4.3 Các tham số ........................................................................................ 70 3.4.4 Các phương án dự báo........................................................................ 70 Kết luận chương .............................................................................................. 75 KẾT LUẬN .......................................................................................................... 76 6 TÀI LIỆU THAM KHẢO .................................................................................. 78 PHỤ LỤC 80 Phụ lục A - Giới thiệu về phần mềm dự báo................................................... 80 Phụ lục B - Mẫu học thử nghiệm so sánh các phương pháp lai ghép và đột biến............................................................................................................ 85 Phụ lục C - Số liệu học và kiểm tra trong bài toán dự báo lưu lượng nước đến hồ Hoà Bình .............................................................................................. 86 7 Danh sách hình vẽ Hình 1.1 Cấu tạo của tế bào nơ-ron sinh học............................................................. 14 Hình 1.2 Mô hình nơ-ron nhân tạo............................................................................. 14 Hình 1.3 Mạng nơ-ron nhân tạo chỉ có một nút và có sự phản hồi............................ 16 Hình 1.4 Mạng nơ-ron truyền thẳng một lớp............................................................. 16 Hình 1.5 Mạng nơ-ron truyền thẳng nhiều lớp .......................................................... 17 Hình 1.6 Mạng nơ-ron hồi quy một lớp.................................................................... 17 Hình 1.7 Sự khác nhau giữa hồi quy tuyến tính và mạng nơ-ron ............................. 19 Hình 1.8 Mạng perceptron một lớp............................................................................ 20 Hình 1.9 Thực hiện hàm XOR bằng mạng MLP ....................................................... 22 Hình 1.10 Lan truyền tín hiệu trong quá trình học theo phương pháp lan truyền ngược sai số........................................................................................................ 23 Hình 1.11 Sai số E được xét là hàm của trọng số W ................................................. 25 Hình 1.12 Minh họa về ý nghĩa của quán tính trong thực tế..................................... 30 Hình 1.13 Hàm sigmoid g(x) = 1/(1+e-x) .................................................................. 30 Hình 1.14 Nội suy hàm y = sin(x/3) + v, 0≤ x ≤ 20 sử dụng MLP............................ 32 Hình 2.1 Sự sinh sản đơn giản phân bố các chuỗi con cháu nhờ sử dụng bánh xe roulette với các khe hở tỷ lệ với độ thích nghi................................................... 38 Hình 2.2 Lưu đồ thuật toán của giải thuật di truyền đơn giản ................................... 41 Hình 2.3 Mã hoá nhị phân trọng số theo phương pháp GENITOR ........................... 43 Hình 2.4 Ví dụ về phương pháp mã hoá trọng số bằng số thực................................. 43 Hình 2.5 Lai ghép nút (crossover-nodes)................................................................... 44 Hình 2.6 Kết hợp giải thuật di truyền và giải thuật lan truyền ngược sai số ............. 54 Hình 3.1: Bản đồ phân bố các trạm trên sông Đà ...................................................... 61 Hình 3.2 Mô hình dự báo dựa trên công nghệ học máy............................................. 67 Hình 3.3 Giao diện chính của phần mềm thử nghiệm ............................................... 69 Hình 3.3 Kết quả dự báo với dữ liệu kiểm tra theo phương án 1 .............................. 71 Hình 3.4 Kết quả dự báo với dữ liệu kiểm tra theo phương án 1 trên đồ thị scatter.. 72 Hình 3.5 Kết quả dự báo với dữ liệu kiểm tra theo phương án 2 .............................. 73 8 Hình 3.6 Kết quả dự báo với dữ liệu kiểm tra theo phương án 2 trên đồ thị scatter.. 73 Hình 3.7 Kết quả dự báo với dữ liệu kiểm tra theo phương án 3 .............................. 74 Hình 3.8 Kết quả dự báo với dữ liệu kiểm tra theo phương án 3 trên đồ thị scatter.. 74 9 Danh sách bảng biểu Bảng 2.1 Các chuỗi của bài toán mẫu và các giá trị thích nghi.....................................38 Bảng 2.2 So sánh các phương pháp đột biến.................................................................45 Bảng 2.3 So sánh các phương pháp lai ghép.................................................................46 Bảng 2.4 Kết quả thử nghiệm so sánh GA và BP với ngưỡng sai số 0.0005................48 Bảng 2.5 Kết quả thử nghiệm với giải thuật đề xuất .....................................................50 Bảng 2.6 Kết quả thử nghiệm so sánh GA’ và BP với ngưỡng sai số 0.0005 ..............52 Bảng 2.7 So sánh khả năng hội tụ của mạng khi sử dụng hai phương pháp học GA’ và BP với sai số dừng lặp khác nhau..........................................................................53 Bảng 2.8 Kết quả thử nghiệm giải thuật kết hợp GA’ và BP với ngưỡng sai sô 0.0005 ...............................................................................................................................54 Bảng 3.1 Thống kê số liệu mưa thu thập được..............................................................63 Bảng 3.2 Thống kê số liệu lưu lượng thu thập được .....................................................64 10 MỞ ĐẦU Dự báo thuỷ văn là công việc dự báo trước một cách có khoa học về trạng thái biến đổi các yếu tố thuỷ văn trong tương lai. Đây là một ngành khoa học có nhiệm vụ báo trước sự xuất hiện các yếu tố thủy văn trên cơ sở nghiên cứu các quy luật của chúng. Hiện nay có rất nhiều bài toán dự báo thuỷ văn được đặt ra như dự báo dòng chảy, dự báo mực nước, dự báo lưu lượng nước trên sông, dự báo lũ, và dự báo các hiện tượng khác trên sông ngòi và hồ... [3]. Tùy vào quan điểm phân chia mà tồn tại một số phân loại dự báo thủy văn. Chẳng hạn, theo yêu cầu phục vụ thì có các loại dự báo như dự báo cho nông nghiệp, dự báo cho giao thông, dự báo cho chống lũ lụt; còn theo đối tượng dự báo thì có các loại dự báo mực nước, dự báo lưu lượng, dự báo bùn cát… Tuy nhiên, phân loại dự báo theo thời gian là một phân loại điển hình với các loại dự báo là ngắn hạn, trung hạn, dài hạn và siêu dài hạn. Dự báo ngắn hạn với khoảng thời gian dự báo từ một đến ba ngày. Dự báo trung hạn với khoảng thời gian dự báo dài hơn dự báo ngắn hạn nhưng tối đa không quá mười ngày. Dự báo dài hạn có khoảng thời gian dự báo từ hơn mười ngày đến một năm. Khi thời gian dự báo lớn hơn một năm đó là dự báo siêu dài hạn. Thuỷ văn là một quá trình tự nhiên phức tạp, chịu tác động của rất nhiều yếu tố. Tính biến động của các yếu tố này phụ thuộc vào cả không gian và thời gian nên gây khó khăn rất lớn cho quá trình dự báo, tìm ra được mối liên quan giữa các yếu tố. Thêm vào đó, do thiếu các trạm quan trắc cần thiết và thiếu sự kết hợp giữa các ngành liên quan cho nên dữ liệu quan trắc thực tế thường là không đầy đủ, không mang tính chất đại diện. Yêu cầu chung mà tất cả các bài toán dự bảo thủy văn cần phải giải quyết là làm cách nào để có thể phân tích và sử dụng chuỗi dữ liệu có trong quá khứ để dự đoán được giá trị tương lai. Hiện nay, có rất nhiều phương pháp dự báo đã được đưa ra dựa trên mô hình vật lý và mô hình toán học. Trong nhiều trường hợp, kết quả nghiên cứu dự báo thủy văn theo các mô hình nói trên đã đạt được một số thành công đáng ghi nhận [1]. Tuy nhiên, vấn đề tìm kiếm phương pháp đủ tốt, đáp ứng các yêu cầu thực tế giải quyết bài toán dự báo thuỷ văn vẫn là nội dung nghiên cứu thời sự hiện nay. Ở trong nước, tại Viện Khí tượng Thủy văn có hàng chục công trình nghiên cứu liên quan tới dự báo thủy văn, đặc biệt có tới 4 đề tài cấp Nhà nước [3]. Trên thế giới, việc áp dụng các phương pháp của khai phá dữ liệu (đặc biệt là các phương pháp học máy mạng neuron và kết hợp với thuật toán gene) vào dự báo thủy văn đã trở thành nội dung nghiên cứu dự báo thủy văn thời sự trong thời gian gần đây [5-7,12-14, 19]. Khai phá dữ liệu là một trong những lĩnh vực nghiên cứu của khoa học máy tính hiện nay đang được phát triển rất mạnh mẽ. Nó kết hợp giữa học máy, công nghệ cơ sở 11 dữ liệu và một số chuyên ngành khác để tìm ra những tri thức, bao gồm cả các thông tin dự báo, từ những cơ sở dữ liệu lớn. Luận văn này tập trung khảo sát một số phương pháp học máy tiên tiến, thực hiện việc kết hợp giữa phương pháp học máy mạng neuron [5-7,9-20] với thuật toán gene [4,8,21] và ứng dụng vào bài toán dự báo lưu lượng nước đến hồ Hòa Bình. Luận văn tập trung khảo sát một số công trình nghiên cứu liên quan trên thế giới [5-7, 12-14, 19]. Demetris F. Lekkas [12] cung cấp một khung nhìn phương pháp luận về các phương pháp dự báo dòng chảy. Ibrahim Can cùng các đồng tác giả [5] và Cristiane Medina Finzi Quintao cùng các đồng tác giả [19] công bố một số kết quả nghiên cứu cập nhật về dự báo dòng chảy của một số dòng sông tại Thổ Nhĩ Kỳ và Brazin. Đặc biệt, các công trình này đã cung cấp cách thức đánh giá kết quả thực nghiệm các phương pháp dự báo thủy văn được đề cập. Các công trình nghiên cứu khác về phương pháp mạng nơron, thuật toán gene và kết hợp chúng được luận văn sử dụng để làm nền tảng khoa học cho các nghiên cứu phát triển. Luận văn đã hoàn thành phần mềm thử nghiệm và tiến hành thực nghiệm trên bộ dữ liệu được thu thập tin cậy thông qua hệ thống đo đạc thủy văn dọc sông Đà, nguồn nước chính chảy vào hồ Hòa Bình. Đóng góp khoa học của luận văn là một báo cáo khoa học đã được trình bày tại Hội thảo khoa học quốc gia Một số vấn đề chọn lọc về Công nghệ thông tin và Truyền thông lần thứ X được tổ chức tại Đại Lải vào tháng 9/2007 với kết quả thực hiện cho dự báo nước trước 10 ngày có chỉ số R2 khá cao, lên tới 0.8737 [2]. Cải tiến do luận văn đề xuất kết hợp đột biến BIASED với đột biến UNBIASED trong đó đột biến BIASED sẽ đóng vai trò chủ đạo nhằm vượt ra khỏi cực trị địa phương (D. Montana and L. Davis [16]) là có ý nghĩa. Các kết quả thực nghiệm cải tiến trên cho thấy mọi tiêu chí đánh giá đều tốt lên, chỉ số R2 nâng lên 0.8742 (so với 0.8737 [2]), sai số quân phương là 72.28 m3/s (so với 76.10 m3/s [2]). Nội dung chính của luận văn được tổ chức thành 3 chương có nội dung được mô tả như dưới đây. Chương I. Mạng nơ-ron nhân tạo truyền thẳng nhiều lớp. Chương này trình bày những lý thuyết cơ bản về mạng nơ-ron nhân tạo, tập trung nghiên cứu mạng truyền thẳng nhiều lớp. Chương này cung cấp một cách nhìn tổng quát nhất, và những vấn đề về quá trình huấn luyện mạng và thuật toán học của mạng mà tập trung chủ yếu vào thuật toán lan truyền ngược sai số. Chương II. Kết hợp giải thuật di truyền với giải thuật lan truyền ngược sai số để tối ưu hoá trọng số mạng nơ-ron nhân tạo. Chương này trình bày về lý thuyết của giải thuật di truyền và khả năng ứng dụng của giải thuật này kết hợp với thuật toán lan truyền ngược sai số nhằm đạt tới một kết quả tốt hơn đối với bài toán tối ưu trọng số mạng nơ-ron nhân tạo. 12 Chương III. Ứng dụng mạng nơ ron nhân tạo vào việc dự báo lưu lượng nước đến hồ Hoà Bình. Chương này giới thiệu sơ lược về bộ dữ liệu sử dụng, các phương pháp đánh giá kết quả dự báo và tập trung vào thử nghiệm các phương pháp để dự báo lưu lượng nước đến hồ Hoà Bình trước mười ngày, từ đó đánh giá được khả năng ứng dụng các phương pháp học máy đã trình bày trong dự báo chuỗi thời gian, cụ thể là dự báo lưu lượng. Phần kết luận tổng kết những kết quả đã đạt được của luận văn và hướng phát triển nghiên cứu tiếp theo. Phần phụ lục giới thiệu về phần mềm dự báo và hướng dẫn cách thức cơ bản sử dụng phần mềm. 13 CHƯƠNG 1 - MẠNG NƠ-RON NHÂN TẠO TRUYỀN THẲNG NHIỀU LỚP Mạng nơ-ron nhân tạo được coi là một công cụ mạnh để giải quyết các bài toán có tính phi tuyến, phức tạp và đặc biệt trong các trường hợp mà mối quan hệ giữa các quá trình không dễ thiết lập một cách tường minh. Có nhiều loại mạng nơ-ron khác nhau trong đó mạng nơ-ron truyền thẳng nhiều lớp là một trong những mạng nơ-ron thông dụng nhất. Đã có nhiều nghiên cứu sử dụng mạng nơ-ron truyền thẳng nhiều lớp trong bài toán dự báo [5][7], [10], [14] và đã chứng tỏ đây là hướng tiếp cận rất hiệu quả. Trong chương này chúng ta sẽ tìm hiểu những kiến thức về mạng nơ-ron nhân tạo, mạng nơ-ron truyền thẳng nhiều lớp và khả năng ứng dụng của chúng trong bài toán dự báo. 1.1 Giới thiệu về mạng nơ-ron nhân tạo 1.1.1 Khái niệm cơ bản Theo các nhà nghiên cứu sinh học về bộ não, hệ thống thần kinh của con người bao gồm khoảng 100 tỷ tế bào thần kinh, thường gọi là các nơ-ron. Mỗi tế bào nơ- ron gồm ba phần: • Thân nơ-ron với nhân bên trong (gọi là soma), là nơi tiếp nhận hay phát ra các xung động thần kinh. • Một hệ thống dạng cây các dây thần kinh vào (gọi là dendrite) để đưa tín hiệu tới nhân nơ-ron. Các dây thần kinh vào tạo thành một lưới dày đặc xung quanh thân nơ-ron, chiếm diện tích khoảng 0,25 mm2 • Đầu dây thần kinh ra (gọi là sợi trục axon) phân nhánh dạng hình cây, có thể dài từ một cm đến hàng mét. Chúng nối với các dây thần kinh vào hoặc trực tiếp với nhân tế bào của các nơ-ron khác thông qua các khớp nối (gọi là synapse). Thông thường mỗi nơ-ron có thể có từ vài chục cho tới hàng trăm ngàn khớp nối để nối với các nơ-ron khác. Có hai loại khớp nối, khớp nối kích thích (excitatory) sẽ cho tín hiệu qua nó để tới nơ-ron còn khớp nối ức chế (inhibitory) có tác dụng làm cản tín hiệu tới nơ-ron. Người ta ước tính mỗi nơ-ron trong bộ não của con người có khoảng 104 khớp nối (hình 1.1) Chức năng cơ bản của các tế bào nơ-ron là liên kết với nhau để tạo nên hệ thống thần kinh điều khiển hoạt động của cơ thể sống. Các tế bào nơ-ron truyền tín hiệu cho nhau thông qua các dây thần kinh vào và ra, các tín hiệu đó có dạng xung điện và được tạo ra từ các quá trình phản ứng hoá học phức tạp. Tại nhân tế bào, khi điện 14 thế của tín hiệu vào đạt tới một ngưỡng nào đó thì nó sẽ tạo ra một xung điện dẫn tới trục dây thần kinh ra. Xung này truyền theo trục ra tới các nhánh rẽ và tiếp tục truyền tới các nơ-ron khác. Hình 1.1 Cấu tạo của tế bào nơ-ron sinh học Với mục đích tạo ra một mô hình tính toán phỏng theo cách làm việc của nơ-ron trong bộ não con người, vào năm 1943, các tác giả McCulloch và Pitts [15] đã đề xuất một mô hình toán cho một nơ-ron như sau: Hình 1.2 Mô hình nơ-ron nhân tạo Trong mô hình này, một nơ-ron thứ i sẽ nhận các tín hiệu vào xj với các trọng số tương ứng là wij , tổng các thông tin vào có trọng số là 1 m ij j j w x = ∑ Thông tin đầu ra ở thời điểm t+1 được tính từ các thông tin đầu vào như sau: ( 1) ( )ij j iout t g tw x θ⎛ ⎞+ = −⎜ ⎟⎝ ⎠∑ (1.1) Trong đó g là hàm kích hoạt (còn gọi là hàm chuyển) có dạng là hàm bước nhảy, nó đóng vai trò biến đổi từ thông tin đầu vào thành tín hiệu đầu ra w1 wm Nếu f > 0 Nếu f ≤ 0 ⎩⎨ ⎧= 0 1 )( fg (1.2) 15 Như vậy, out = 1 (ứng với việc nơ-ron tạo tín đầu ra) khi tổng các tín hiệu vào lớn hơn ngưỡng θi , còn out = 0 (nơ-ron không tạo tín hiệu ở đầu ra) khi tổng các tín hiệu vào nhỏ hơn ngưỡng θi. Trong mô hình nơ-ron của McCulloch và Pitts, các trọng số wij thể hiện ảnh hưởng của khớp nối trong liên kết giữa nơ-ron j (nơ-ron gửi tín hiệu) và nơ-ron i (nơ-ron nhận tín hiệu). Trọng số wij dương ứng với khớp nối kích thích, trọng số âm ứng với khớp nối ức chế còn wij bằng 0 khi không có liên kết giữa hai nơ-ron. Hàm chuyển g ngoài dạng hàm bước nhảy còn có thể chọn nhiều dạng khác nhau và sẽ được đề cập ở các phần sau. Thông qua cách mô hình hoá đơn giản một nơ-ron sinh học như trên, McCulloch và Pitts đã đưa ra một mô hình nơ-ron nhân tạo có tiềm năng tính toán quan trọng. Nó có thể thực hiện các phép toán lô-gíc cơ bản như AND, OR và NOT khi các trọng số và ngưỡng được chọn phù hợp. Sự liên kết giữa các nơ-ron nhân tạo với các cách thức khác nhau sẽ tạo nên các loại mạng nơ-ron nhân tạo (Artificial Neural Network - ANN) với những tính chất và khả năng làm việc khác nhau. 1.1.2 Mô hình mạng nơ-ron nhân tạo Như đã được giới thiệu, mạng nơ-ron nhân tạo là một hệ thống xử lý thông tin được xây dựng trên cơ sở tổng quát hoá mô hình toán học của nơ-ron sinh học và phỏng theo cơ chế làm việc của bộ não con người. Mạng nơ-ron nhân tạo được thể hiện thông qua ba thành phần cơ bản: mô hình của nơ-ron, cấu trúc và sự liên kết giữa các nơ-ron, phương pháp học được áp dụng cho mạng nơ-ron. a. Các phần tử xử lý Việc xử lý thông tin tại mỗi nơ-ron có thể xem là gồm hai phần: xử lý tín hiệu vào (input) và đưa tín hiệu ra (output). Tương ứng với phần vào của mỗi nơ-ron là một hàm tương tác (interaction) f, hàm này kết hợp các thông tin truyền tới nơ-ron và tạo thành thông tin đầu vào tổng hợp (gọi là net input) của nơ-ron đó . Một nơ-ron thứ i trong mạng thường có hàm fi ở dạng tuyến tính như sau : 1 m i i ij j i j f net w x θ = ∆ = −∑ (1.3) Thao tác thứ hai trong mỗi nơ-ron là tính giá trị đầu ra tương ứng với giá trị đầu vào f thông qua hàm kích hoạt hay còn gọi là hàm chuyển g(f) (hàm kích hoạt). Một số hàm chuyển thường được sử dụng: 16 • Hàm bước nhảy ⎪⎩ ⎪⎨ ⎧ < ≥= 00 01 )( fkhi fkhi fg (1.4) • Hàm dấu ⎪⎩ ⎪⎨ ⎧ <− ≥== 01 01 )sgn()( fkhi fkhi ffg (1.5) • Hàm sigmoid fe fg λ−+= 1 1)( hoặc 1 1 2)( −+= − fefg λ (1.6) b. Liên kết trong mạng nơ-ron nhân tạo Mạng nơ-ron nhân tạo gồm các nơ-ron và liên kết có trọng số giữa chúng. ANN tạo nên một hệ thống xử lý thông tin làm việc trên cơ sở phỏng theo cách làm việc của hệ thống các nơ-ron trong bộ não con người. Tuy nhiên, trong bộ não của con người, các tế bào nơ-ron liên kết với nhau chằng chịt và tạo nên một mạng lưới vô cùng phức tạp. Các loại mạng nơ-ron nhân tạo được xác định bởi cách liên kết giữa các nơ-ron , trọng số của các liên kết đó và hàm chuyển tại mỗi nơ-ron. Các hình vẽ dưới đây thể hiện các cách kết nối khác nhau. Hình 1.3 Mạng nơ-ron nhân tạo chỉ có một nút và có sự phản hồi Hình 1.4 Mạng nơ-ron truyền thẳng một lớp 17 (Single-layer feedforward network) Mạng nơ-ron truyền thẳng một lớp là loại mạng chỉ có lớp nơ-ron đầu vào và một lớp nơ-ron đầu ra (thực chất lớp nơ-ron đầu vào không có vai trò xử lý, do đó ta nói mạng chỉ có một lớp). Loại mạng này còn được gọi là mạng perceptron một lớp. Mỗi nơ-ron đầu ra có thể nhận tín hiệu từ các đầu vào x1, x2, …, xm để tạo ra tín hiệu đầu ra tương ứng. Hình 1.5 Mạng nơ-ron truyền thẳng nhiều lớp (Multil-layer feedforward network). Trong mạng nơ-ron truyền thẳng nhiều lớp, lớp nhận tín hiệu vào của mạng gọi là lớp vào (input layer), nó thường không thực hiện việc chuyển đổi thông tin mà chỉ làm chức năng nhận tín hiệu. Tín hiệu ra của mạng được đưa ra từ lớp ra (output layer). Các lớp ở giữa lớp vào và lớp ra gọi là các lớp ẩn. Trong mạng truyền thẳng (feedforward network) không có nút nào mà đầu ra của nó là đầu vào của một nút khác trên cùng lớp với nó hoặc lớp trước. Mạng có phản hồi (feedback network) là mạng mà đầu ra của một nơ-ron có thể trở thành đầu vào của nơ-ron trên cùng một lớp hoặc của lớp trước đó. Mạng feedback có chu trình khép khín gọi là mạng quy hồi (recurrent network) Hình 1.6 Mạng nơ-ron hồi quy một lớp Lớp vào Các lớp ẩn Lớp ra 18 c. Các luật học của mạng nơ-ron nhân tạo Như đã được đề cập ở phần đầu luật học là một trong ba yếu tố quan trọng tạo nên một mạng nơ-ron nhân tạo. Có hai vấn đề cần học đối với mỗi mạng nơ-ron nhân tạo đó là học tham số (parameter learning) và học cấu trúc (structure learning). Học tham số là việc thay đổi trọng số của các liên kết giữa các nơ-ron trong một mạng, còn học cấu trúc là việc điều chỉnh cấu trúc của mạng bao gồm thay đổi số lớp nơ-ron, số nơ-ron của mỗi lớp và cách liên kết giữa chúng. Hai vấn đề này có thể được thực hiện đồng thời hoặc tách biệt. Về mặt phương pháp học, có thể chia ra làm ba loại: học có giám sát hay còn gọi là học có thầy (supervised learning), học tăng cường (reinforcement learning) và học không có giám sát hay còn gọi là học không có thầy ( unsupperviced learning). 1.1.3 Khả năng ứng dụng của mạng nơ-ron nhân tạo Đặc trưng của mạng nơ-ron nhân tạo là khả năng học và xử lý song song. Nó có thể gần đúng mối quan hệ tương quan phức tạp giữa các yếu tố đầu vào và đầu ra của các quá trình cần nghiên cứu và khi đã học được thì việc kiểm tra độc lập thường cho kết quả tốt. Sau khi đã học xong, mạng nơ-ron nhân tạo có thể tính toán kết quả đầu ra tương ứng với bộ số liệu đầu vào mới. Về mặt cấu trúc, mạng nơ-ron nhân tạo là một hệ thống gồm nhiều phần tử xử lý đơn giản cùng hoạt động song song. Tính năng này của ANN cho phép nó có thể được áp dụng để giải các bài toán lớn. Về khía cạnh toán học, theo định lý Kolmogorov, một hàm liên tục bất kỳ f( x1, x2,.. , xn ) xác định trên khoảng In ( với I =[0,1]) có thể được biểu diễn dưới dạng: 2 1 1 1 ( ) ( ( )) n n j ij i j i f x xχ ψ+ = = = ∑ ∑ (1.7) trong đó : χj , Ψij là các hàm liên tục một biến. Ψij là hàm đơn điệu, không phụ thuộc vào hàm f. Mặt khác, mô hình mạng nơ-ron nhân tạo cho phép liên kết có trọng số các phần tử phi tuyến (các nơ-ron đơn lẻ) tạo nên dạng hàm tổng hợp từ các hàm thành phần. Do vậy, sau một quá trình điều chỉnh sự liên kết cho phù hợp (quá trình học), các phần tử phi tuyến đó sẽ tạo nên một hàm phi tuyến phức tạp có khả năng xấp xỉ hàm biểu diễn quá trình cần nghiên cứu. Kết quả là đầu ra của nó sẽ tương tự với kết quả đầu ra của tập dữ liệu dùng để luyện mạng. Khi đó ta nói mạng nơ-ron nhân tạo đã học được mối quan hệ tương quan đầu vào - đầu ra của quá trình và lưu lại mối quan hệ tương quan này thông qua bộ trọng số liên kết giữa các nơ- ron. Do đó, mạng nơ-ron nhân tạo có thể tính toán trên bộ số liệu đầu vào mới để đưa ra kết quả đầu ra tương ứng. 19 Hồi qui tuyến tính Xấp xỉ bằng mạng nơron Y = a1X + a2 Y=f(X, a1, …. , an) Hình 1.7 Sự khác nhau giữa hồi quy tuyến tính và mạng nơ-ron Với những đặc điểm đó, mạng nơron nhân tạo đã được sử dụng để giải quyết nhiều bài toán thuộc nhiều lĩnh vực của các ngành khác nhau. Các nhóm ứng dụng mà mạng nơ-ron nhân tạo đã được áp dụng rất có hiệu quả là: • Bài toán phân lớp: Loại bài toán này đòi hỏi giải quyết vấn đề phân loại các đối tượng quan sát được thành các nhóm dựa trên các đặc điểm của các nhóm đối tượng đó. Đây là dạng bài toán cơ sở của rất nhiều bài toán trong thực tế: nhận dạng chữ viết, tiếng nói, phân loại gen, phân loại chất lượng sản phẩm,… • Bài toán dự báo: Mạng nơ-ron nhân tạo đã được ứng dụng thành công trong việc xây dựng các mô hình dự báo sử dụng tập dữ liệu trong quá khứ để dự đoán số liệu trong tương lai. Đây là nhóm bài toán khó và rất quan trọng trong nhiều ngành khoa học. • Bài toán điều khiển và tối ưu hoá: Nhờ khả năng học và xấp xỉ hàm mà mạng nơ-ron nhân tạo đã được sử dụng trong nhiều hệ thống điều khiển tự động cũng như góp phần giải quyết những bài toán tối ưu trong thực tế. Tóm lại, mạng nơ-ron nhân tạo được xem như là một cách tiếp cận đầy tiềm năng để giải quyết các bài toán có tính phi tuyến, phức tạp và đặc biệt là trong tình huống mối quan hệ bản chất vật lý của quá trình cần nghiên cứu không dễ thiết lập tường minh. 1.2 Mạng nơ-ron lan truyền thẳng nhiều lớp 1.2.1 Mạng perceptron một lớp Mạng perceptron một lớp do F.Rosenblatt đề xuất năm 1960 [15] là mạng truyền thẳng chỉ một lớp vào và một lớp ra không có lớp ẩn. Trên mỗi lớp này có thể có 20 một hoặc nhiều nơ-ron. Mô hình mạng nơ-ron của Rosenblatt sử dụng hàm ngưỡng đóng vai trò là hàm chuyển. Do đó, tổng của các tín hiệu vào lớn hơn giá trị ngưỡng thì giá trị đầu ra của nơ-ron sẽ là 1, còn trái lại sẽ là 0. Ngay từ khi mạng Perceptron một lớp được đề xuất nó đã được sử dụng để giải quyết bài toán phân lớp. Một đối tượng sẽ được nơ-ron i phân vào lớp A nếu Tổng thông tin đầu vào : ij j iw x θ>∑ Trong đó wij là trọng số liên kết từ nơ-ron j tới nơ-ron i , xj là đầu vào từ nơ-ron j, và θ là ngưỡng của nơ-ron i. Trong trường hợp trái lại đối tượng sẽ được phân vào lớp B. Việc huấn luyện mạng dựa trên phương pháp học có giám sát với tập mẫu học là {(x(k), d(k))}, k= 1,2, …, p .Trong đó d(k) = [d1(k), d2(k), …, dn(k)]T là đầu ra quan sát được tương ứng với đầu vào x(k) = [x1(k), x2(k), …, xm(k)]T (với m là số đầu vào, n là số đầu ra và p là cặp mẫu đầu vào - đầu ra dùng cho việc học). Như vậy chúng ta mong rằng sau quá trình học, đầu ra tính toán được y(k) = [y1(k), y2(k), …, yn(k)]T sẽ bằng với đầu ra của mẫu học d(k) ( ) ( ) ( ) ( ) 1 ( ) ( ) m k T k k k i i ij j i j y g w x g w x d = = = =∑ với i=1, 2, …, n ; k = 1,2 , …, p (1.8) ` Hình 1.8 Mạng perceptron một lớp . . x1 x2 xm =-1 y1 y2 yn w11 w12 w1m wn1 wn2 wnm e d Đầu ra tính toán Đầu ra mong muốn d2 e2 . . e d (w1m = θ1 , w2m = θ2 , wnm = θn ) Outi = 1 nếu neti ≥ θ 0 nếu neti < θ với neti = ∑wijxj là tổng thông tin đầu vào của nơ-ron i 21 Để bắt đầu quá trình luyện mạng, các trọng số được gán giá trị ngẫu nhiên trong khoảng [-3, 3]. Sau đó hiệu chỉnh các trọng số cho phù hợp với mẫu học để làm giảm sai số giữa y(k) và d(k) Các bước tiến hành : • Xác định ngẫu nhiên bộ trọng số. • Với mỗi mẫu học (x(k), d(k)) , k=1,2, …, p thực hiện các bước: o Tính giá trị y(k) theo công thức o Xác định sai số δi tại nơ-ron i: δi = di – yi , trong đó di là giá trị đầu ra quan sát được và yi là giá trị đầu ra tính toán tại nơ-ron thứ i o Tính ∆wij là số gia của trọng số wij (trọng số liên kết giữa đầu vào j tới nơ-ron i) theo công thức: ∆wij =ηδixj trong đó η là tốc độ học (0<η<1) o Hiệu chỉnh wij(t+1) = wij(t) + ∆wij =wij(t) +ηδi(t)xj(t) trong đó wij(t+1) là trọng số sau khi điều chỉnh ở lần học tại thời điểm t Rosenblatt đã chứng minh rằng quá trình học của mạng Perceptron sẽ hội tụ tới bộ trọng số W, biểu diễn đúng các mẫu học với điều kiện là các mẫu này biểu thị các điểm rời rạc của một hàm khả tách tuyến tính nào đó (f: Rn → R được gọi là khả tách tuyến tính nếu các tập {F-1(xk)}, với xk thuộc miền trị của f, có thể tách được với nhau bởi các siêu phẳng trong không gian Rn ). Năm 1969, Minsky và Papert đã chứng minh một cách chặt chẽ rằng lớp hàm thể hiện sự phụ thuộc giữa đầu vào và đầu ra có thể học bởi mạng Perceptron một lớp là lớp hàm khả tách tuyến tính. Khả tách tuyến tính là trường hợp tồn tại một mặt siêu phẳng để phân cách tất cả các đối tượng của một lớp này với một lớp khác, ví dụ một mặt phẳng sẽ phân chia không gian ba chiều thành hai vùng riêng biệt. Mở rộng ra, nếu có n đầu vào , n>2 thì công thức 1 n ij j i i w x θ = =∑ tạo nên một siêu phẳng có n-1 chiều trong không gian n chiều, nó chia không gian đó thành hai nửa. Trong nhiều bài toán thực tế đòi hỏi chia các vùng của các điểm trong một siêu không gian thành các lớp riêng biệt. Loại bài toán này gọi là bài toán phân lớp. Bài toán phân lớp có thể giải quyết bằng cách tìm các tham số thích hợp cho một siêu phẳng để nó có thể chia không gian n chiều thành các vùng riêng biệt. Với tính chất của như đã nêu trên, mạng perceptron một lớp có thể mô tả các hàm logic như AND, OR và NOT. Tuy nhiên nó không thể hiện được hàm XOR. Như vậy chứng tỏ mô hình perceptron một lớp không thể giải quyết bài toán này. Vấn đề này sẽ được giải quyết bằng mô hình mạng nơ-ron perceptron nhiều lớp (Multilayer Perceptron - MLP). 22 1.2.2 Mạng perceptron nhiều lớp Mạng perceptron nhiều lớp (Multilayer Perceptron –MLP) còn được gọi là mạng truyền thẳng nhiều lớp là sự mở rộng của mô hình mạng perceptron với sự bổ sung thêm những lớp ẩn và các nơ-ron trong các lớp ẩn này có hàm chuyển (hàm kích hoạt) dạng phi tuyến. Mạng MLP có một lớp ẩn là mạng nơ-ron nhân tạo được sử dụng phổ biến nhất, nó có thể xấp xỉ các hàm liên tục được định nghĩa trên một miền có giới hạn cũng như những hàm là tập hợp hữu hạn của các điểm rời rạc. a. Giải quyết bài toán XOR với mạng MLP Ta thấy có thể dùng hai đường thẳng để phân tách với trường hợp hàm XOR. -0,5+x1+x2=0 và -1,5+x1+x2=0 Hay ta giải hệ bất phương trình Dễ thấy mỗi bất phương trình ở trên có thể được thực hiện bằng một nơ-ron và đầu ra của hai nơ-ron này (2 bất phương trình) là đầu vào của một hàm AND. Do vậy có thể sử dụng mạng MLP sau để thực hiện chức năng của hàm XOR như sau: Hình 1.9 Thực hiện hàm XOR bằng mạng MLP b. Thuật toán học theo phương pháp lan truyền ngược sai số Thuật toán học theo phương pháp lan truyền ngược sai số do Rumelhart và các cộng sự đề xuất [20] là một trong số những kết quả nghiên cứu quan trọng nhất đối 1 1 X1 X2 -0,5 1,5 -1 1 -1 1 1 -1,5 1 Y=X1 XOR X2 X X -0,5+x1+x2 > 0 -1,5+x1+x2 < 0 -0,5 + x1 + x2 > 0 1,5 - x1 - x2 > 0 23 với sự phát triển của mạng nơ-ron nhân tạo. Thuật toán này được áp dụng cho mạng truyền thẳng nhiều lớp trong đó các nơ-ron có thể sử dụng các hàm chuyển là các hàm liên tục có các dạng khác nhau. Thuật toán sử dụng một tập các mẫu gồm các cặp đầu vào - đầu ra để luyện mạng. Với mỗi cặp đầu vào - đầu ra (x(k),d(k)) thuật toán lan truyền ngược sai số thực hiện hai giai đoạn sau: • Giai đoạn thứ nhất, mẫu đầu vào x(k) được truyền từ lớp vào tới lớp ra, và ta có kết quả đầu ra tính toán được là y(k). • Giai đoạn tiếp theo, tín hiệu lỗi được tính toán từ sự khác nhau giữa đầu ra quan sát được d(k) với đầu ra tính toán y(k) sẽ được lan truyền ngược lại từ lớp ra đến các lớp trước để điều chỉnh các trọng số của mạng. Để làm ví dụ ta xét mạng truyền thẳng có một lớp ẩn dưới đây, đối với các mạng có kích thước lớn hơn thì thao tác cũng tương tự. Mạng nơ-ron được xét có m nơ-ron ở lớp vào, l nơ-ron trong lớp ẩn và n nơ-ron ở lớp ra. Đường kẻ liền thể hiện luồng tín hiệu được truyền từ đầu vào tới đầu ra còn các đường kẻ nét đứt thể hiện luồng tín hiệu lỗi được truyền ngược trở lại từ đầu ra. Hình 1.10 Lan truyền tín hiệu trong quá trình học theo phương pháp lan truyền ngược sai số Chúng ta xét một cặp đầu vào - đầu ra để luyện mạng (x,d), để đơn giản chúng ta bỏ ký hiệu mũ k thể hiện số thứ tự của cặp mẫu này trong bộ mẫu dùng để luyện mạng. Khi đưa vào đầu vào x, nơ-ron thứ q trong lớp ẩn sẽ nhận tín hiệu vào của mạng là: Lớp vào Lớp ẩn Lớp ra wiq zq (q=1,…, l) 24 ∑ = = m j jqjq xvnet 1 (1.9) nơ-ron q ở lớp ẩn sẽ tính toán và tạo kết quả ở đầu ra của nó là: ∑ = == m j jqjqq xvgnetgz 1 )()( (1.10) Do đó tín hiệu vào của nơ-ron thứ i trên lớp ra sẽ là: 1 1 1 ( ) l l m i iq q iq qj j q q j net w z w g v x = = = = =∑ ∑ ∑ (1.11) Và cuối cùng, đầu ra của nơ-ron i trên lớp ra sẽ là: 1 1 1 ( ) ( ) ( ( )) l l m i i iq q iq qj j q q j y g net g w z g w g v x = = = = = =∑ ∑ ∑ (1.12) Công thức trên cho biết quá trình lan truyền tín hiệu từ đầu vào qua lớp ẩn tới đầu ra. Tiếp theo chúng ta xét tín hiệu lỗi được lan truyền ngược lại từ lớp ra. Trước hết, đối với mỗi cặp giá trị vào – ra chúng ta xây dựng một hàm giá như sau: [ ] 2 22 1 1 1 1 1 1 1( ) ( ) ( ) ( ) 2 2 2 n n n l i i i i i iq q i i i q E w d y d g net d g w z = = = = ⎡ ⎤= − = − = −⎢ ⎥⎣ ⎦∑ ∑ ∑ ∑ (1.13) Như vậy với một tập gồm p mẫu học, chúng ta lần lượt xây dựng được p hàm giá như vậy. Việc học của mạng hay nhiệm vụ của giải thuật thực chất là tìm kiếm tập trọng số W trong không gian RM (M là số trọng số có trong mạng) để lần lượt tối thiểu hoá các hàm giá như vậy. Điều đáng chú ý là việc tối thiểu hoá được tiến hành liên tiếp nhau và theo chu kỳ đối với các hàm giá. Để tối thiểu hoá các hàm giá như vậy, giải thuật lan truyền ngược sai số sử dụng phương pháp giảm gradient để điều chỉnh các trọng số liên kết giữa các nơ-ron. Bản chất của phương pháp này là khi sai số E được vẽ như hàm của tham số gây ra sai số sẽ phải có một cực tiểu tại bộ giá trị nào đó của tham số. Khi quan sát độ dốc của đường cong, chúng ta quyết định phải thay đổi tham số thế nào để có thể tiến gần đến cực tiểu cần tìm kiếm hơn. Trong hình vẽ dưới đây, giá trị của trọng số phải giảm nếu đạo hàm dE/dW là dương 25 Hình 1.11 Sai số E được xét là hàm của trọng số W Bằng biểu thức, chúng ta có thể biểu diễn phương pháp giảm gradient như sau: ∆w= w(new) – w(old) = -η.∂E/∂w (1.14) Ở đây η là hằng số dương xác định tốc độ giảm giá trị của w, còn dấu âm chỉ chiều giảm gradient. Áp dụng phương pháp giảm gradient đối với các trọng số liên kết giữa các nơ- ron trong lớp ẩn tới các nơ-ron của lớp ra ta có: iq iq Ew w η ∂∆ = − ∂ (1.15) Do hàm sai số E là một hàm phức tạp và là hàm gián tiếp của trọng số wiq (công thức 1.13). Sử dụng nguyên tắc tính đạo hàm của hàm gián tiếp cho iq E w ∂ ∂ ta có: [ ] [ ]'( )i iiq i i i q oi q i i iq y netEw d y g net z z y net w η η ηδ∆⎡ ⎤⎡ ⎤ ⎡ ⎤∂ ∂∂ ⎡ ⎤∆ = − = − =⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎣ ⎦∂ ∂ ∂⎢ ⎥⎣ ⎦ ⎣ ⎦ ⎣ ⎦ (1.16) Trong đó δoi là tín hiệu sai số và chỉ số oi có nghĩa là nút thứ i trong trên lớp ra. Tín hiệu sai số được tính như sau: [ ] [ ]'( )ioi i i i i i i yE E d y g net net y net δ ∆ ⎡ ⎤ ⎡ ⎤ ⎡ ⎤∂∂ ∂=− = − = −⎢ ⎥ ⎢ ⎥ ⎢ ⎥∂ ∂ ∂⎣ ⎦ ⎣ ⎦ ⎣ ⎦ (1.17) Trong đó neti là tín hiệu vào của nơ-ron thứ i trên lớp ra và g’(neti) = ∂g(neti)/∂net. Kết quả này tương tự luật học delta áp dụng cho mạng perceptron một lớp với đầu vào bây giờ là đầu ra zq của lớp ẩn. W W dE/dw = tan α > tan α 0 E 26 Để điều chỉnh trọng số của các liên kết giữa lớp vào tới lớp ẩn ta cũng sử dụng phương pháp giảm gradient và lấy đạo hàm theo các biến trung gian như đã áp ở trên. Xét liên kết giữa nơ-ron thứ j ở lớp vào và nơ-ron thứ q trên lớp ra: q q q qj qj q qj q q qj net z netE E Ev v net v z net v η η η⎡ ⎤ ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ ⎡ ⎤∂ ∂ ∂∂ ∂ ∂∆ = − = − = −⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥∂ ∂ ∂ ∂ ∂ ∂⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎣ ⎦ ⎣ ⎦ ⎣ ⎦ ⎣ ⎦ ⎣ ⎦ ⎣ ⎦ (1.18) Từ công thức (1.13) mỗi thành phần lỗi [di-yi] , i=1, 2,…, n, là hàm của zq do vậy công thức trên có thể tiếp tục biến đổi: ( ) ( ) ( ) 1 ' ' n qj i i i iq q j i v d y g net w g net xη = ⎡ ⎤∆ = −⎣ ⎦∑ (1.19) Sử dụng công thức (1.13) chúng ta viết lại biểu thức (1.15) như sau: ( ) 1 ' n qj oi iq q j hq j i v d w g net x xη µδ = ⎡ ⎤∆ = =⎣ ⎦∑ (1.20) Trong đó δhq là tín hiệu lỗi của nơ-ron thứ q trong lớp ẩn và được định nghĩa như sau: ( ) 1 ' n q hq q oi iq iq q q zE E g net w net z net δ δ∆ = ⎡ ⎤ ⎡ ⎤ ⎡ ⎤∂∂ ∂=− = − =⎢ ⎥ ⎢ ⎥ ⎢ ⎥∂ ∂ ∂⎢ ⎥ ⎢ ⎥ ⎢ ⎥⎣ ⎦ ⎣ ⎦ ⎣ ⎦ ∑ (1.21) Với netq là tín hiệu vào của nơ-ron thứ q, như vậy tín hiệu lỗi của nơ-ron trên lớp ẩn khác với tín hiệu lỗi của nơ-ron trên lớp ra (xem công thức 1.17 và 1.21). Vì sự khác nhau này, thủ tục điều chỉnh trọng số được gọi là luật học delta mở rộng. Nhìn lại công thức (1.21) tín hiệu lỗi δhq của nơ-ron thứ q trong lớp ẩn được xác định từ các tín hiệu lỗi δoi, của các nơ-ron trên lớp ra. Tổng quát đối với lớp bất kỳ, luật lan truyền ngược có dạng: jinputioutputjiij xxw __ηδηδ ==∆ (1.22) Trong đó “output_i ” là đầu ra của nơ-ron i và “ input_j ” là đầu vào của nơ-ron j, δi là tín hiệu học được định nghĩa trong công thức (4.10) Từ các phân tích trên, thuật toán lan truyền ngược sai số được xây dựng như sau: Xét một mạng nơ-ron truyền thẳng có Q lớp, q = 1, 2, …, Q, và gọi neti và yi là tín hiệu vào và ra của nơ-ron thứ i trong lớp q. Mạng này có m đầu vào và n đầu ra. Đặt qwij là trọng số của liên kết từ nơ-ron thứ j trong lớp q-1 tới nơ-ron thứ i trong lớp q. 27 Đầu vào : Một tập các cặp mẫu học {(x(k),d(k)) | k= 1, 2, …, p } và véc tơ đầu vào được bổ sung thêm x(k)m+1 = - 1 . Bước 0 (khởi tạo) Chọn một hằng số η > 0 và Emax (dung sai cho phép). Khởi tạo ngẫu nhiên các trọng số trong khoảng giá trị nhỏ. Đặt E =0 và k = 1. Bước 1 (thực hiện một quá trình lặp cho việc huấn luyện mạng) Sử dụng mẫu học thứ k : Tại lớp vào (q =1), với mọi i ta có : qyi = 1yi = x(k)i Bước 2 (Lan truyền tín hiệu từ lớp vào tới lớp ra) ( ) ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛== ∑ − j i q ij q i q i q ywgnetgy 1 Bước 3 (Xác định tín hiệu lỗi Qδi tại lớp ra) ( ) ( ) ( )iQiQkiiQ n i i Qk i netgyd EydE ' , 2 1 )( 2 1 )( −= +−= ∑ = δ Bước 4 (Lan truyền ngược sai số) Lan truyền ngược sai số để điều chỉnh các trọng số và tính toán tín hiệu lỗi q-1δi cho các lớp trước: i q i q ij q yw 1−=∆ δη và ijqoldijqnewijq www ∆+= ( )1 1'q q q qi i ji j j g net wδ δ− −= ∑ với q = Q, Q-1, …, 2 Bước 5 (Kiểm tra điều kiện lặp) Kiểm tra: if ( k < p ) then Begin k=k+1; Goto bước1; End Else Goto bước6; 28 Bước 6 (Kiểm tra lỗi tổng cộng hiện thời đã chấp nhận được chưa) If (E < Emax) then {kết thúc quá trình học và đưa ra bộ trọng số cuối cùng} Else Begin E=0; K=1; Goto bước1 {để bắt đầu một lần học tiếp theo }; End; Mỗi lần toàn bộ tập mẫu học được lan truyền qua mạng được gọi là một epoch. Số epoch phụ thuộc vào từng trường hợp cụ thể và sự khởi tạo ban đầu. Có trường hợp thuật toán phải sau hàng chục nghìn epoch mới hội tụ tới lời giải. Nếu tham số khởi tạo không phù hợp có thể làm cho quá trình học không đạt kết quả mong muốn. Đối với mỗi epoch ta tính sai số trung bình của mạng theo công thức sau: 2 1 1 ( ) . p n i i k i y d RMS p n = = − = ∑∑ (1.23) Trong đó p là số mẫu được dùng để luyện mạng, n là số biến của véc-tơ đầu ra. Sai số RMS thường được dùng để đánh giá kết quả học của mạng nơ-ron. c. Một số yếu tố ảnh hưởng đến quá trình học theo phương pháp lan truyền ngược sai số Khởi tạo các trọng số Các giá trị được khởi tạo ban đầu cho các trọng số trong mạng lan truyền ngược sai số ảnh hưởng rất lớn đến kết quả học cuối cùng của mạng. Các giá trị này thường được khởi tạo ngẫu nhiên trong phạm vi giá trị tương đối nhỏ. Thông thường hàm chuyển sử dụng cho mạng MLP là hàm sigmoid, do vậy nếu ta chọn các giá trị trọng số khởi tạo lớn thì các hàm này có thể bão hoà ngay từ đầu và dẫn tới hệ thống có thể bị tắc ngay tại một cực tiểu địa phương hoặc tại một vùng bằng phẳng nào đó gần điểm xuất phát. Theo nghiên cứu của Wessels và Barnard, năm 1992 [18], thì việc khởi tạo các trọng số liên kết wij nên trong phạm vi 3 / , 3 /i ik k⎡ ⎤−⎣ ⎦ với ki là số liên kết của các nơ-ron j tới nơ-ron i . Hằng số học η 29 Hằng số học η cũng là một yếu tố quan trọng ảnh hưởng đến hiệu quả và độ hội tụ của giải thuật lan truyền ngược sai số. Không có hằng số η phù hợp cho tất cả các bài toán khác nhau. Hằng số học này thường được chọn bằng thực nghiệm cho mỗi bài toán ứng dụng cụ thể bằng phương pháp thử sai. Trong nhiều ứng dụng thực tế cho thấy một hằng số học có thể phù hợp ở thời điểm bắt đầu của quá trình học nhưng lại không phù hợp với giai đoạn sau của quá trình học. Do đó, có một phương pháp hiệu quả hơn đó là sử dụng hằng số học thích nghi. Một cách xử lý đơn giản cho vấn đề này đó là kiểm tra xem các trọng số mới có làm giảm hàm giá hay không, nếu không thì có thể các trọng số đã vượt quá xa vùng cực tiểu và như vậy hằng số η cần phải giảm. Trái lại, nếu sau vài vòng lặp hàm giá liên tục giảm thì ta có thể thử tăng hằng số η để đẩy nhanh hơn tốc độ hội tụ đến giá trị cực tiểu. Năm 1991, trong nghiên cứu của mình Hertz và các cộng sự [9] đã đề xuất luật điều chỉnh hằng số học như sau: trong đó ∆E là thay đổi của hàm giá, a và b là các hằng số dương, việc ∆E luôn nhỏ hơn 0 được đánh giá dựa trên k bước lặp liên tiếp. Hằng số quán tính Tốc độ học của giải thuật lan truyền ngược sai số có thể rất chậm nếu hằng số học nhỏ, nhưng nếu hằng số học lớn thì nó lại có thể gây ra sự dao động lớn trong quá trình tìm giá trị cực tiểu theo phương pháp giảm gradient. Để giải quyết vấn đề này người ta thường thêm thành phần quán tính vào các phương trình hiệu chỉnh trọng số như sau: ∆w(t) = -η∇E(t) + α ∆w( t-1) (α là hằng số quán tính, α∈[ 0, 1] ) Nhờ thành phần này, quá trình học có thể vượt qua điểm cực tiểu địa phương để tìm đến điểm cực tiểu toàn cục, đồng thời thành phần quán tính cũng ngăn cản sự thay đổi đột ngột của các trọng số theo hướng khác với hướng mà lời giải đang di chuyển đến. ∆ +a nếu ∆E luôn nhỏ hơn 0 (hàm giá liên tục được giảm) -bη nếu ∆E >0 0 trong các trường hợp còn lại 30 Hình 1.12 Minh họa về ý nghĩa của quán tính trong thực tế Hàm giá: Trong phần nghiên cứu trên hàm giá được chọn là hàm bình phương sai số 2 1 1( ) ( ) 2 n i i i E w d y = = −∑ . Tuy nhiên, nó có thể được thay thế bằng một hàm F(yi, di) bất kỳ có đạo hàm và đạt cực tiểu khi hai đối số di và yi bằng nhau. Thông thường hàm giá được chọn có dạng : 1 1 ( ) n p i i i E d y p = = −∑ với 1≤ p ≤ ∞ (1.24) Như vậy khi chọn p = 2 ta có hàm giá là hàm bình phương sai số như đã xét ở trên. 1.2.3 Một số vấn đề cần chú ý khi sử dụng mạng MLP Mạng nơ-ron perceptron nhiều lớp là loại mạng nơ-ron được sử dụng trong nhiều ứng dụng thực tế. Tuy nhiên, để mạng có thể đưa ra kết quả tốt, chúng ta cần quan tâm đến một số vấn đề có ảnh hưởng khá quan trọng đến hiệu quả làm việc của nó bao gồm: vấn đề chuẩn hoá số liệu đầu vào, vấn đề học chưa đủ và học quá của mạng, vấn đề lựa chọn một cấu trúc mạng phù hợp với bài toán. a. Vấn đề chuẩn hoá số liệu đầu vào Mạng MLP thường sử dụng hàm chuyển là hàm sigmoid có dạng như sau: Hình 1.13 Hàm sigmoid g(x) = 1/(1+e-x) 0 x g(x) = 1/(1+e-x) 1 2 3-3 -2 -1 1 0.5 31 Với dạng hàm này, giá trị ở đầu ra của mỗi nơ-ron nằm trong phạm vi khoảng (0,1) và nó đạt các giá trị bão hoà ( xấp xỉ 0 hay 1 ) khi ⎢x ⎢ lớn. Do đó, khi đầu vào của mạng có giá trị tuyệt đối lớn thì ta cần chuẩn hoá nó về khoảng có giá trị nhỏ, nếu không thì các nơ-ron tại các lớp ẩn ngay ban đầu đã có thể đạt giá trị bão hoà và quá trình học của mạng không đạt kết quả mong muốn. Với dạng hàm như trên thì giá trị đầu vào của mạng thường được chuẩn hoá về khoảng thuộc đoạn [-3, 3] . Mặt khác, do tín hiệu đầu ra của nơ-ron nằm trong khoảng giá trị (0,1) nên các giá trị đầu ra thực tế trong các mẫu học cũng cần chuẩn hoá về khoảng giá trị này để có thể dùng cho quá trình luyện mạng. Do vậy trong quá trình tính toán, để có các giá trị thực tế ở đầu ra của mạng chúng ta cần phải chuyển các giá trị trong khoảng (0,1) về miền các giá trị thực tế. b. Vấn đề học chưa đủ và học quá thuộc của mạng Vấn đề mấu chốt khi xây dựng một mạng nơ-ron nhân tạo là làm thế nào mạng có khả năng tổng quát hoá cao để đưa ra kết quả tốt cả với những trường hợp đầu vào của mạng không nằm trong tập mẫu đã dùng để luyện mạng. Giống như các mô hình hồi quy phi tuyến khác, đối với mạng nơ-ron nhân tạo ta cũng phải giải quyết hai vấn đề là ANN học chưa đủ (underfitting) và học quá (overfitting). Khi mạng có cấu trúc (số nút ẩn và liên kết) cũng như số lần học chưa đủ so với nhu cầu của bài toán thì sẽ dẫn tới tình trạng mạng không đủ khả năng mô tả gần đúng mối quan hệ tương quan giữa đầu vào và đầu ra của quá trình cần dự báo và dẫn tới học chưa đủ. Trái lại, nếu mạng quá phức tạp (quá nhiều nút ẩn và quá nhiều tham số) và được học “quá khít” đối với các mẫu dùng để luyện mạng thì có thể dẫn tới tình trạng mạng học cả thành phần nhiễu lẫn trong các mẫu đó, đây là tình trạng “học quá thuộc” của mạng. Vấn đề nêu trên có thể làm cho nhiều loại mạng nơ-ron, đặc biệt là mạng MLP có thể có những trường hợp cho kết quả dự đoán rất sai lệch với thực tế. Một số giải pháp cho vấn đề học quá của mạng: • Sử dụng tập số liệu có tính đại diện tốt để luyện mạng: Đây được xem là một cách khá tốt để tránh hiện tượng overfitting. Khi tập mẫu dùng để luyện mạng thể hiện được nhiều trạng thái có thể xẩy ra của quá trình cần nghiên cứu thì sau khi học mạng sẽ có khả năng tổng quát hoá tương đối tốt từ tập dữ liệu đó và sẽ không chịu ảnh hưởng nhiều của hiện tượng overfitting. Ngoài ra một số biện pháp dưới đây cũng có thể góp phần quan trọng giúp khắc phục hiện tượng overfitting của mạng. • Lựa chọn cấu trúc mô hình phù hợp: Việc lựa chọn mô hình của mạng (số lớp ẩn, số nơ-ron trên mỗi lớp ẩn) có ảnh hưởng quan trọng đến hiện tượng học chưa đủ (underfitting) và học quá (overfitting) của mạng. Nghiên cứu của Steve Lawrence và C.Lee Giles [11] về bài toán nội suy hàm y = sin(x/3) + v, 0≤ x ≤20. 32 với v là biến ngẫu nhiên nằm trong khoảng (- 0.25 , 0.25) cho thấy nếu mạng chỉ gồm một nút ẩn thì mạng không thể học được hàm này. Mạng có hai nút ẩn có khả năng tổng quát hoá tốt nhất (tuy không chính xác hoàn toàn với các mẫu nhưng nó tạo nên giáng điệu gần với hàm cần xấp xỉ nhất và nó đã không quá khít với nhiễu của mẫu học). Các mạng có độ phức tạp hơn (10 nút ẩn, 50 nút ẩn) tuy nó có thể học khá chính xác các mẫu được sử dụng nhưng chính điều này lại làm cho nó học quá nhiều cả thành phần nhiễu nên khả năng tổng quát hoá giảm và dẫn tới hiện tượng học quá (overfitting). Hình 1.14 Nội suy hàm y = sin(x/3) + v, 0≤ x ≤ 20 sử dụng MLP • Dừng học đúng lúc: Năm 1991, trong một nghiên cứu về vấn đề học quá của mạng, hai tác giả Nelson và Illingworth [17] đã đưa ra giải pháp dừng học đúng lúc để tránh hiện tượng học quá của mạng như sau: o Tập mẫu được chia làm hai phần: một phần dùng để luyện mạng và phần còn lại để kiểm thử. o Sử dụng các giá trị khởi tạo nhỏ o Sử dụng hằng số tốc độ học có giá trị thấp. o Tính toán sự thay đổi lỗi kiểm thử trong quá trình luyện mạng. o Dừng học khi thấy lỗi kiểm thử bắt đầu tăng c. Lựa chọn kích thước mạng Các công trình dựa trên định lý của Kolmogorov dự kiến rằng toàn bộ các ánh xạ liên tục từ [0,1]p đến [0,1]n đều có thể được xấp xỉ bằng một mạng perceptron ba lớp có lớp vào gồm p nơ-ron, lớp ra gồm n nơ-ron và lớp ẩn gồm (2p+1) nơ-ron. Tuy nhiên không thể chỉ ra được chính xác số lượng nơ-ron tối ưu trong mạng, tính chất của các nơ-ron, tức là dạng phi tuyến cụ thể thực hiện phép xấp xỉ này. 33 Một số công trình nghiên cứu về chủ đề này cho rằng số nơ-ron tối ưu ở lớp ẩn thường nhỏ hơn (2p+1). Ngoài ra cũng cần phải nói cơ sở dữ liệu học phải có kích thước phù hợp với kiến trúc mạng. Theo Vapnik và Chervonenkis, cơ sở dữ liệu học phải có số mẫu thoả mãn: N ≈ 10.Nw, ở đó Nw là số trọng số của mạng. (1.18) Gọi số nơ-ron thuộc lớp ẩn là L, số nơ-ron ở lớp vào là p thì trọng số của các kết nối giữa lớp vào và lớp ẩn thứ nhất (kể cả ngưỡng) là: D=(p+1).L (1.19) Theo một số kết quả nghiên cứu, số mẫu của cơ sở dữ liệu học cần phải thoả mãn N ≈ 4.D (1.20) Khi số lượng mẫu của cơ sở dữ liệu học chưa đạt đến giới hạn cần thiết thì ta nên làm giảm số lượng các kết nối để tránh hiện tượng học thuộc lòng. Kết luận chương Trong chương này chúng ta đã tìm hiểu các khái niệm, cấu trúc và khả năng ứng dụng của mạng nơ-ron nhân tạo. Luận văn đã trình bày chi tiết về mạng nơ-ron nhiều lớp truyền thẳng và các thuật toán học đối với loại mạng này. Mạng nơ-ron nhân tạo được coi là một công cụ mạnh, mềm dẻo để giải quyết các bài toán có tính phi tuyến, phức tạp và đặc biệt trong các trường hợp mà mối quan hệ giữa các quá trình không dễ thiết lập một cách tường minh. Do đó, khả năng ứng dụng của nó là rất lớn đặc biệt trong bài toán dự báo. Trong chương tiếp theo, chúng ta sẽ nghiên cứu giải thuật di truyền và ứng dụng giải thuật di truyền vào việc tối ưu hoá trọng số của mạng nơ- ron nhân tạo. 34 CHƯƠNG 2 - KẾT HỢP GIẢI THUẬT DI TRUYỀN VỚI GIẢI THUẬT LAN TRUYỀN NGƯỢC SAI SỐ ĐỂ TỐI ƯU HOÁ TRỌNG SỐ MẠNG NƠ-RON NHÂN TẠO Trong chương trước chúng ta đã nghiên cứu giải thuật “lan truyền ngược sai số”, đây là một phương pháp học của mạng nơ-ron nhân tạo, nó cho phép điều chỉnh trọng số của mạng để tối thiểu hoá hàm sai số E. Giải thuật này hoạt động dựa trên cơ chế giảm gradient, với những hàm đơn giản có một cực trị thì phương pháp giảm gradient đưa ta đến cực trị toàn cục. Tuy nhiên, chúng ta biết rằng hàm sai số E trong mạng nơ-ron nhiều lớp là một hàm có bề mặt rất phức tạp với rất nhiều cực trị địa phương, do đó phương pháp này không thể đảm bảo cho ta tìm thấy được một cực trị toàn cục trên bề mặt hàm giá này. Chính vì vậy, để cải thiện giải thuật, người ta thường tìm cách thay đổi hằng số học hoặc thêm vào đó thành phần quán tính để cho phép có thể vượt qua những cực trị địa phương trong quá trình tìm kiếm [8,9,10,16,18,20,21]. Việc lựa chọn hằng số học và hằng số quán tính cũng là một vấn đề rất khó khăn, bởi vì nếu chúng quá lớn đôi khi dẫn đến tình trạng không ổn định của quá trình tìm kiếm, còn nếu chọn quá nhỏ thì lại dẫn đến tốc độ học chậm và khả năng vượt qua các cực trị địa phương thấp. Quá trình tìm kiếm trên những hàm giá như thế này đã được chứng minh là một bài toán NP đầy đủ nghĩa là ta không thể sử dụng được một giải pháp tổng quát có độ phức tạp đa thức để đạt đến kết quả. Giải thuật di truyền (Genetic Algorithms-GA) được biết đến như một giải thuật tìm kiếm dựa trên học thuyết về chọn lọc tự nhiên và nó cho phép ta đạt được tới cực trị toàn cục. Luận văn nghiên cứu việc sử dụng giải thuật di truyền vào bài toán tối ưu hoá trọng số của mạng nơ-ron nhân tạo giúp mạng có thể học được tốt hơn [8]. 2.1 Giới thiệu giải thuật di truyền Giải thuật di truyền đã được đề cập trong rất nhiều tài liệu, trong đó có các công trình của D.E. Goldberg [8] và Thomas Back [4]. Phần này chỉ trình bày các khái niệm căn bản của giải thuật di truyền cũng như khả năng ứng dụng của nó. 2.1.1 Giới thiệu Từ trước đến nay, trong các nghiên cứu và ứng dụng tin học đã xuất hiện nhiều bài toán chưa tìm ra được phương pháp giải nhanh và hợp lý. Phần lớn đó là các bài toán tối ưu nảy sinh trong các ứng dụng. Để giải các bài toán này người ta thường phải tìm đến một giải thuật hiệu quả mà kết quả thu được chỉ là xấp xỉ tối ưu. Trong 35 nhiều trường hợp chúng ta có thể sử dụng giải thuật xác suất, tuy không bảo đảm kết quả tối ưu nhưng có thể chọn các giá trị sao cho sai số đạt được sẽ nhỏ như mong muốn. Theo lời giải xác suất, việc giải bài toán quy về quá trình tìm kiếm trên không gian tập hợp các lời giải có thể. Tìm được lời giải tốt nhất và quá trình được hiểu là tối ưu. Với miền tìm kiếm nhỏ, một số thuật toán cổ điển được sử dụng. Tuy nhiên đối với các miền lớn, phải sử dụng các kỹ thuật trí tuệ nhân tạo đặc biệt, giải thuật di truyền là một trong những công cụ đó. Ý tưởng của GA là mô phỏng những gì mà tự nhiên đã thực hiện. GA hình thành dựa trên quan niệm cho rằng: quá trình tiến hoá tự nhiên là quá trình hoàn hảo nhất, hợp lý nhất và tự nó đã mang tính tối ưu. Giải thuật di truyền áp dụng quá trình tiến hóa tự nhiên để giải các bài toán tối ưu trong thực tế (từ tập các lời giải có thể ban đầu thông qua nhiều bước tiến hóa hình thành các tập hợp mới với lời giải tốt hơn và cuối cùng sẽ tìm được lời giải gần tối ưu) [4]. Những vấn đề căn bản được đặt ra là: Áp dụng di truyền tự nhiên vào giải thuật di truyền như thế nào? Cách biểu diễn tập hợp các lời giải ra sao? Chúng ta sẽ tìm hiểu chi tiết vấn đề này trong phần tiếp theo. 2.1.2 Tư tưởng chính của giải thuật di truyền Giải thuật di truyền là một loại thuật toán mô phỏng các hiện tượng tự nhiên: kế thừa và đấu tranh sinh tồn để cải tiến lời giải và khảo sát không gian lời giải. Khái niệm kế thừa và đấu tranh sinh tồn được giải thích qua ví dụ về sự tiến hoá của một quần thể thỏ như sau: Có một quần thể thỏ. Trong số đó có một số con nhanh nhẹn và thông minh hơn những con khác. Những chú thỏ nhanh nhẹn và thông minh có xác suất bị chồn, cáo ăn thịt nhỏ hơn, do đó chúng tồn tại để làm những gì tốt nhất có thể: tạo thêm nhiều thỏ tốt. Dĩ nhiên, một số thỏ chậm chạp, đần độn cũng sống chỉ vì may mắn. Quần thể những chú thỏ còn sống sót sẽ bắt đầu sinh sản. Việc sinh sản này sẽ tạo ra một hỗn hợp tốt về “nguyên liệu di truyền thỏ”: Một số thỏ chậm chạp có con với những con thỏ nhanh, một số thỏ nhanh với thỏ nhanh, một số thỏ thông minh với thỏ đần độn,… Và trên tất cả, thiên nhiên thỉnh thoảng lại ném vào một con thỏ “hoang dã” bằng cách làm đột biến nguyên liệu di truyền thỏ. Những chú thỏ con, do kết quả này sẽ nhanh hơn và thông minh hơn những con trong quần thể gốc vì có nhiều bố mẹ nhanh nhẹn và thông minh hơn đã thoát chết khỏi chồn, cáo. (Thật hay là những con chồn cáo cũng trải qua những tiến trình tương tự, nếu không những con thỏ sẽ trở nên nhanh chóng và thông minh đến nỗi những con chồn, cáo không thể bắt chúng được). 36 Khi tìm kiếm lời giải tối ưu, GA cũng thực hiện các bước tương ứng với câu chuyện đấu tranh sinh tồn của loài thỏ. GA cũng sử dụng các thuật ngữ vay mượn của di truyền học. Ta có thể nói về các cá thể (hay kiểu gen, cấu trúc) trong một quần thể, những cá thể này cũng còn được gọi là các nhiễm sắc thể (chromosome). Điều này có thể gây một chút nhầm lẫn: mỗi tế bào của một cơ thể của một chủng loại đã cho mang một số loại nhiễm sắc thể nào đó (ví dụ ở người có 46 nhiễm sắc thể), nhưng trong GA ta chỉ nói về những cá thể có một nhiễm sắc thể. Các nhiễm sắc thể được tạo thành từ các đơn vị - các gen - biểu diễn trong một chuỗi tuyến tính. Mỗi gen kiểm soát một hoặc nhiều đặc trưng. Gen với những đặc trưng nhất định có vị trí nhất định trong nhiễm sắc thể. Bất cứ đặc trưng nào của cá thể cũng có thể tự biểu hiện một cách phân biệt và gen có thể nhận một số giá trị khác nhau. Một nhóm các gen (nhiễm sắc thể) sẽ biểu diễn một lời giải của bài toán đang giải (ý nghĩa, cấu trúc của nhiễm sắc thể được người sử dụng xác định trước). Một tiến trình tiến hoá được thực hiện trên một quần thể các nhiễm sắc thể tương ứng với một quá trình tìm kiếm lời giải trong không gian lời giải. Thực ra, GA thuộc lớp các thuật toán xác suất, nhưng lại rất khác những thuật toán ngẫu nhiên vì chúng kết hợp các phần tử tìm kiếm trực tiếp và ngẫu nhiên. Khác biệt quan trọng giữa phương pháp tìm kiếm của GA và các phương pháp tìm kiếm khác là GA duy trì và xử lý một tập các lời giải (quần thể) - tất cả các phương pháp khác chỉ xử lý một điểm trong không gian tìm kiếm. Chính vì thế, GA mạnh hơn các phương pháp tìm kiếm hiện có rất nhiều. Cấu trúc của giải thuật di truyền đơn giản tương tự như cấu trúc của bất kì một chương trình tiến hoá nào. Ở bước lặp t, giải thuật di truyền duy trì một quần thể các lời giải (các nhiễm sắc thể), { }1 2( ) , ,...,t t tnP t x x x= . Mỗi lời giải tix được lượng giá để biết được độ “thích nghi” của nó. Sau đó ở lần lặp thứ t+1, một quần thể mới được hình thành bằng cách chọn giữ lại những cá thể thích nghi nhất. Một số cá thể của quần thể này trải qua những biến đổi nhờ lai tạo (phép lai) và đột biến (phép đột biến), hình thành nên những lời giải mới. Phép lai kết hợp các tính chất của hai nhiễm sắc thể ‘cha’ và ‘mẹ’ để tạo ra các nhiễm sắc thể ‘con’ bằng cách hoán vị các đoạn gen tương ứng của cha và mẹ. Ví dụ: nếu cha mẹ được biểu diễn bằng vectơ 5 chiều (a1,b1,c1,d1,e1) và (a2,b2,c2,d2,e2), thì lai tạo, hoán vị tại vị trí thứ 2 sẽ sinh ra các nhiễm sắc thể con (a1,b1,c2,d2,e2) và (a2,b2,c1,d1,e1). Phép lai cho phép trao đổi thông tin giữa các lời giải. Khác với phép lai, phép đột biến thay đổi một cách ngẫu nhiên một hay nhiều gen của nhiễm sắc thể được chọn, thay đổi này được thực hiện với một xác suất thể hiện tốc độ đột biến. Phép đột biến cho phép đưa thêm các thông tin mới vào quần thể làm cho chất liệu di truyền phong phú thêm. 37 Sau đây chúng ta sẽ tìm hiểu về một giải thuật di truyền đơn giản. 2.1.3 Giải thuật di truyền đơn giản a. Cấu trúc của giải thuật di truyền đơn giản Trong giải thuật di truyền đơn giản, hệ gen của cá thể được biểu diễn thành một chuỗi nhị phân gồm 2 giá trị 0 và 1. Mỗi thành phần trong chuỗi số gọi là allele (gen tương ứng). Giải thuật di truyền đơn giản bao gồm 3 toán tử sau: - Tái tạo (Reproduction) - Lai ghép (Crossover) - Đột biến (Mutation) Xét ví dụ bài toán hộp đen như sau: Cho một hộp đen với một dãy 5 công tắc ở đầu vào. Một tổ hợp các trạng thái của 5 công tắc ứng với một tín hiệu ra (output) của hàm f, biểu diễn theo toán học là f(s), trong đó s là một tổ hợp các trạng thái cụ thể của 5 công tắc. Mục tiêu của bài toán là phải đặt các công tắc như thế nào để đặt được giá trị tối đa có thể có của hàm f. Với những phương pháp khác của bài toán tối ưu, chúng ta có thể làm việc trực tiếp với bộ các thông số (việc đặt các công tắc) và bật tắt các công tắc từ một trạng thái này sang trạng thái khác bằng cách dùng những quy tắc chuyển đổi theo phương pháp chuyên biệt. Với giải thuật di truyền đơn giản, đầu tiên ta mã hoá dãy các công tắc thành một chuỗi có chiều dài xác định. Cách mã hoá rất tự nhiên: dùng chuỗi dài 5 kí tự gồm các giá trị 0 và 1, với quy ước ‘0’ = tắt, ‘1’ = mở. Ví dụ: chuỗi 11101 nghĩa là công tắc thứ 4 tắt, 4 công tắc còn lại mở. Với giải thuật di truyền đơn giản, ta không cần biết nguyên tắc làm việc của hộp đen. Giải thuật di truyền đơn giản bắt đầu với một quần thể các chuỗi và sau đó sẽ phát sinh thành công những quần thể chuỗi khác. Với bài toán hộp đen, một sự bắt đầu ngẫu nhiên bằng cách tung đồng tiền (ngửa = ‘1’, sấp= ‘0’) có thể sản sinh quần thể ban đầu có kích thước n=4 như sau: 01101 11000 01000 10011 Tiếp theo, dưới sự tác động của các toán tử di truyền, quần thể trên sẽ tiến hoá để cho ra đời quần thể mới có độ thích nghi cao hơn. Tái tạo: Tái tạo là một quá trình trong đó các chuỗi biểu diễn cá thể được sao chép lại tuỳ theo giá trị của hàm mục tiêu f (hàm thích nghi). Toán tử này được xem là quá trình 38 chọn lọc trong tự nhiên. Hàm mục tiêu f(i) được gán cho mỗi cá thể trong quần thể. Việc sao chép lại các chuỗi tuỳ theo giá trị thích nghi của chúng có nghĩa là: Những chuỗi có giá trị thích nghi cao hơn sẽ có nhiều cơ hội đóng góp các chuỗi con cho thế hệ tiếp theo. Thao tác sinh sản hay còn gọi là thao tác chọn cha mẹ được điều khiển bằng cách quay bánh xe roulette, trong đó mỗi chuỗi trong quần thể chiếm một khe có kích thước tỉ lệ với độ thích nghi (fitness) của nó trên bánh xe. Giả sử các chuỗi của quần thể ban đầu đã khởi tạo trong bài toán hộp đen có các giá trị hàm thích nghi như trong bảng sau. Lấy tổng độ thích nghi của 4 chuỗi, chúng ta được 1170. Ta sẽ tính tỉ lệ % độ thích nghi của từng chuỗi trong quần thể: Bảng 2.1 Các chuỗi của bài toán mẫu và các giá trị thích nghi STT Chuỗi Độ thích nghi Tỉ lệ (%) 1 01101 169 14.4 2 11000 576 49.2 3 01000 64 5.5 4 10001 361 30.9 Tổng cộng 1170 100.0 Bánh xe rollete được đánh trọng số phù hợp cho sự tái tạo của thế hệ này được thể hiện trên hình sau: 1 14.4% 2 49.2% 3 5.5% 4 30.9% Hình 2.1 Sự sinh sản đơn giản phân bố các chuỗi con cháu nhờ sử dụng bánh xe roulette với các khe hở tỷ lệ với độ thích nghi Với bài toán hộp đen, để sinh sản chúng ta chỉ cần quay bánh xe roulette 4 lần đối với bài toán này, chuỗi 1 có giá trị thích nghi là 169, đại diện cho 14.4% bánh xe roulette, và cứ mỗi lần quay xác suất chọn chuỗi 1 là 0.144. Tương tự với các chuỗi còn lại. Mỗi khi chúng ta yêu cầu một thế hệ khác, một vòng quay đơn giản của bánh xe đánh trọng số sẽ chọn ra được ứng cử viên để sinh sản. Bằng cách này, những chuỗi thích nghi hơn sẽ có một số lượng con cháu lớn hơn trong thế hệ kế tiếp. 39 Lai ghép: Mỗi khi một chuỗi được chọn để sinh sản, một bản sao chính xác của chuỗi đó sẽ được tạo ra. Các bản sao này được đưa vào bể ghép đôi (matingpool). Toán tử lai ghép đơn giản có thể được tiến hành theo hai bước: Bước 1: Các thành viên của các chuỗi đơn giản mới ở trong bể ghép được ghép đôi với nhau một cách ngẫu nhiên. Bước 2: Mỗi cặp chuỗi sẽ trải qua việc ghép chéo như sau: Một số nguyên chỉ vị trí k dọc theo chuỗi sẽ được lựa chọn qua giá trị ngẫu nhiên nằm trong khoảng từ 1 đến chiều dài chuỗi L-1 ([1, L-1]). Hai chuỗi mới sẽ được tạo ra bằng cách hoán đổi tương ứng các chuỗi ký tự từ vị trí 1 đến k và từ k+1 đến L của hai chuỗi cha-mẹ cho nhau. Ví dụ: xét 2 chuỗi A1 và A2 từ quần thể ban đầu: A1 = 0110|1 A2 = 1100|0 Giả sử trong khi chọn một số ngẫu nhiên nằm trong khoảng từ 1 đến 4, chúng ta được k = 4 (như được chỉ ra bằng dấu ngăn cách “|”). Kết quả của việc ghép chéo làm sinh ra hai chuỗi mới A’1 và A’2, trong đó dấu ’ có nghĩa là các chuỗi này là phần tử của thế hệ mới. A’1 = 01100 A’2 = 11001 Cơ chế sinh sản và ghép chéo đơn giản, bao gồm việc sinh số ngẫu nhiên, sao chép chuỗi và trao đổi các chuỗi thành phần. Tuy nhiên, điểm cần nhấn mạnh là việc sinh sản và trao đổi thông tin có cấu trúc (dù là một cách ngẫu nhiên) của cả quá trình ghép chéo làm cho các giải thuật di truyền tăng thêm sức mạnh. Đột biến: Nếu sự sinh sản theo độ thích nghi kết hợp với sự ghép chéo cho giải thuật di truyền có năng lực xử lý tốt hơn, thì sự đột biến đóng một vai trò quyết định thứ hai trong hoạt động của giải thuật di truyền. Sự đột biến là cần thiết bởi vì: cho dù sự sinh sản và ghép chéo đã tìm kiếm hiệu quả và tái kết hợp lại các gen với nhau, nhưng thỉnh thoảng chúng có thể làm mất một vài gen hữu ích nào đó (bít 1 hay bít 0 tại những vị trí đặc biệt nào đó). Trong các hệ thống gen nhân tạo, toán tử đột biến sẽ chống lại sự mất mát không được khôi phục đó. Trong giải thuật di truyền đơn giản, đột biến là sự thay đổi ngẫu nhiên và không thường xuyên (với xác xuất nhỏ) trị số vị trí của một chuỗi. Trong việc mã hóa nhị phân của bài toán hộp đen có nghĩa là chỉ cần đổi 1 thành 0 và ngược lại. Sự đột biến là một hoạt động ngẫu nhiên trong 40 không gian chuỗi, khi được dùng cùng với sự sinh sản và ghép chéo nó sẽ là một chính sách bảo hiểm chống lại nguy cơ mất mát những gen quan trọng. Ba toán tử tái tạo, lai ghép, đột biến được áp dụng lặp đi lặp lại để tạo ra nhiễm sắc thể mới. Coi như một thế hệ mới tương ứng với một quá trình sinh sản đã được tạo xong bao gồm một quần thể các chuỗi nhiễm sắc thể, trong giải thuật di truyền có thể sinh ra nhiều thế hệ. b. Sơ đồ giải thuật di truyền đơn giản Giải thuật di truyền bao gồm các bước sau: 1. Khởi tạo quần thể ban đầu của các chuỗi nhiễm sắc thể. 2. Xác định giá trị hàm mục tiêu cho mỗi một chuỗi nhiễm sắc thể. 3. Tạo các chuỗi nhiễm sắc thể mới bằng sinh sản từ các chuỗi nhiễm sắc thể hiện tại, có tính đến ghép chéo và đột biến xảy ra (nếu có). 4. Xác định hàm mục tiêu cho các chuỗi nhiễm sắc thể mới và đưa nó vào trong một quần thể mới. 5. Nếu điều kiện dừng đã thỏa mãn thì dừng lại và trả về chuỗi nhiễm sắc thể tốt nhất cùng với giá trị hàm mục tiêu của nó, nếu không thì quay về bước 3. Lưu đồ thuật toán: 41 Hình 2.2 Lưu đồ thuật toán của giải thuật di truyền đơn giản 2.1 Ứng dụng giải thuật di truyền vào bài toán tối ưu hoá trọng số của mạng nơ-ron nhân tạo Như chúng ta đã biết sử dụng giải thuật lan truyền ngược sai số để tối ưu hoá trọng số của mạng nơ-ron nhân tạo đang được sử dụng rộng rãi hiện nay. Tuy nhiên, giải thuật này hoạt động theo cơ chế giảm gradient nên nó khó có thể tìm ra được cực trị toàn cục. Trong nghiên cứu của mình tôi sử dụng giải thuật di truyền để tối ưu hoá trọng số của mạng giúp quá trình học của mạng được tốt hơn. Để có thể sử dụng được giải thuật di truyền vào việc học của mạng nơ-ron cần phải thực hiện một số bước như sau: - Xây dựng hàm giá - Mã hoá nhiễm sắc thể - Thực hiện giải thuật di truyền Tạo quần thể ban đầu của các chuỗi nhiễm sắc thể Xác định giá trị hàm mục tiêu của các chuỗi nhiễm sắc thể Tạo các chuỗi nhiễm sắc thể bằng cách sinh sản từ các chuỗi nhiễm sắc thể hiện tại. (Có xét đến ghép chéo và đột biến xảy ra) Tính toán các giá trị mục tiêu của các chuỗi nhiễm sắc thể mới và đưa nó vào một quần thể mới Kiểm tra xem điều kiện dừng đã thoả mãn chưa? Kết thúc Y N 42 2.2.1 Xây dựng hàm giá Hàm giá này sẽ được sử dụng để tạo nên độ phù hợp của các cá thể và của cả quần thể trong GA. Trong nghiên cứu này tôi sử dụng hàm sai số căn quân phương RMSE của tập mẫu học. ( )2 1 1 1 p n ij ij i j RMSE y d pn = = = −∑∑ (2.1) Trong đó: - yij, dij là đầu ra của mạng và đầu ra mong muốn của đầu ra thứ j tại mẫu học thứ i - n là số đầu ra của mạng - p là số mẫu học Trong quá trình tiến hoá của toàn bộ quần thể, hàm giá này sẽ dần dần đạt tới cực tiểu toàn cục. 2.2.2 Mã hoá nhiễm sắc thể Mỗi cá thể trong GA sẽ thay mặt cho một bộ trọng số của mạng nơ-ron. Ở đây ta không cần phải phân biệt trọng số nào ở lớp nào mà ta chỉ cần trải tất cả các trọng số lên sơ đồ gen của nhiễm sắc thể. a. Mã hoá nhị phân Một phương pháp mã hoá nhiễm sắc thể khá nổi tiếng do Whitley cùng các đồng tác giả [21] đề xuất gọi là GENITOR. Có một số phiên bản của GENITOR, về cơ bản mỗi trọng số của mạng được mã hoá thành một chuỗi bit như trên hình dưới. Index-bit để chỉ ra rằng kết nối có tồn tại hay không (bằng 1 - có kết nối, bằng 0 – không có kết nối). Chuỗi bit nhị phân còn lại sẽ biểu diễn giá trị của trọng số. Whitley sử dụng 8-bit để mã hoá dải giá trị từ -127 đến +127 số 0 được mã hoá 2 lần. Với cách mã hoá này các toán tử đột biến, lai ghép thực hiện khá đơn giản. Tuy nhiên, muốn tăng độ chính xác của việc mã hoá cần phải tăng số bit mã hoá trên một trọng số. Do đó, chiều dài của nhiễm sắc thể sẽ tăng theo dẫn đến việc thực thi thuật toán sẽ chậm. 43 Hình 2.3 Mã hoá nhị phân trọng số theo phương pháp GENITOR b. Mã hoá số thực Montana D. và Davis L. [16] mã hoá trực tiếp các trọng số bằng các số thực là các giá trị của các trọng số. Điều này làm tăng độ chính xác của phép mã hoá cũng như giảm được kích thước của nhiễm sắc thể. Trong nghiên cứu của mình chúng tôi cũng sử dụng phương pháp này để thực hiện việc mã hoá trọng số của mạng. Các gen (trọng số) được khởi tạo ngẫu nhiên trong khoảng (-3, +3). Tuy nhiên với kỹ thuật mã hoá này ta cần thay đổi các toán tử lai ghép, đột biến cho phù hợp. Hình 2.4 Ví dụ về phương pháp mã hoá trọng số bằng số thực 2.2.3 Lai ghép Có một số cách tiếp cận trong lai ghép giữa các nhiễm sắc thể [16]. 44 a. Lai ghép trọng số (crossover-weights) Toán tử lai ghép này sẽ đưa một giá trị vào mỗi vị trí của nhiễm sắc thể con bằng cách lấy ngẫu nhiên một giá trị tại cùng vị trí của nhiễm sắc thể cha hoặc mẹ. b. Lai ghép nút (crossover-nodes) Việc lai ghép được thực hiện giữa các nút cùng vị trí của cha và mẹ. Mỗi khi hai nút tại một lớp nào đó được lai ghép các trọng số của tất cả các liên kết đầu vào tới các nút đó sẽ được hoán vị cho nhau (hình 2.5). Hình 2.5 Lai ghép nút (crossover-nodes) 2.2.4 Đột biến a. Đột biến trọng số (mutate weights) Một gen (trọng số) được lựa chọn ngẫu nhiên với một xác suất pmutation để tiến hành đột biến. Có hai phương pháp đột biến trọng số [16] là: UNBIASED: với mỗi gen được chọn đột biến nó sẽ được thay thế bằng một giá trị ngẫu nhiên xung quanh 0. BIASED: với mỗi gen được chọn đột biến nó sẽ được cộng thêm một giá trị ngẫu nhiên. Montana [16] đã thử nghiệm hai phương pháp đột biến trọng số này. Kết quả phương pháp BIASED chạy tốt hơn. Điều này có thể được giải thích là do khi chạy bộ giá trị các trọng số có xu hướng tốt hơn. Do đó, việc đột biến thay thế giá trị gốc bằng các giá trị ngẫu nhiên xung quanh giá trị gốc (BIASED) sẽ cho kết quả tốt hơn là thay thế bằng các giá trị ngẫu nhiên xung quanh 0 (UNBIASED). 45 b. Đột biến nút (mutate nodes) Toán tử đột biến nút sẽ chọn ra n nút không phải là các nút đầu vào. Tất cả các liên kết tới các nút này sẽ lần lượt được cộng thêm một giá trị ngẫu nhiên. 2.2.5 Thử nghiệm a. Thử nghiệm giải thuật di truyền với các phương pháp đột biến khác nhau So sánh hai phương pháp đột biến ‘đột biến trọng số BIASED’ và ‘đột biến nút’, cả hai phương pháp này đều sử dụng phương pháp ‘lai ghép trọng số’. Thử nghiệm với mẫu học dạng hình sin gồm 30 mẫu, chi tiết trong phụ lục B. Các tham số giống nhau với cả hai phương án: - Số lượng quần thể: 100 - Xác suất lai: 0.3 - Xác suất đột biến: 0.1 - Ngưỡng dừng lặp: 0.05 Việc thử nghiệm được tiến hành với 100 lần chạy mỗi phương án. Dưới đây là bảng thống kê các lần chạy và số thế hệ cần thiết để đạt được yêu cầu về sai số. (1) – phương án ‘đột biến trọng số BIASED’ (2) – phương án ‘đột biến nút’ Bảng 2.2 So sánh các phương pháp đột biến STT (1) (2) STT (1) (2) STT (1) (2) 1 61 100 36 134 50 71 59 151 2 227 21 37 143 35 72 133 157 3 152 33 38 59 151 73 40 43 4 97 15 39 35 231 74 66 85 5 27 33 40 188 37 75 112 20 6 60 170 41 522 97 76 87 85 7 164 593 42 38 48 77 163 32 8 181 152 43 39 514 78 794 55 9 31 104 44 487 76 79 55 167 10 57 116 45 205 163 80 260 139 11 167 101 46 99 37 81 141 101 12 146 91 47 75 72 82 674 63 13 780 647 48 153 44 83 67 91 14 342 56 49 26 40 84 102 108 15 100 377 50 62 58 85 52 43 16 235 515 51 146 59 86 235 155 17 138 42 52 152 105 87 85 58 18 44 54 53 80 18 88 100 29 46 19 71 118 54 63 67 89 27 80 20 316 161 55 905 43 90 49 58 21 37 153 56 66 298 91 48 22 22 70 96 57 71 369 92 276 48 23 80 45 58 134 158 93 443 565 24 68 100 59 36 163 94 32 144 25 249 20 60 523 28 95 56 130 26 123 82 61 22 56 96 246 67 27 55 41 62 39 69 97 66 146 28 89 33 63 82 58 98 341 105 29 39 24 64 8 129 99 215 44 30 77 43 65 219 60 100 72 329 31 247 150 66 128 37 32 159 60 67 35 15 33 73 11 68 84 35 34 130 40 69 55 22 35 67 5 70 99 101 Trung bình 152.67 112.65 Nhận xét: Kết quả trung bình sau 112.65 thế hệ phương pháp ‘đột biến nút’ đã đạt yêu cầu, nhỏ hơn nhiều so với phương pháp ‘đột biến trọng số BIASED’ là 152.67 thế hệ. b. Thử nghiệm giải thuật di truyền với các phương pháp lai ghép khác nhau So sánh hai phương pháp lai ghép là ‘lai ghép trọng số’ và ‘lai ghép nút’ cả hai phương pháp này đều sử dụng phương pháp ‘đột biến nút’. Các tham số giống nhau với cả hai phương án: - Số lượng quần thể: 100 - Xác suất lai: 0.3 - Xác suất đột biến: 0.1 - Ngưỡng dừng lặp: 0.05 Việc thử nghiệm được tiến hành với 100 lần chạy mỗi phương án. Dưới đây là bảng thống kê số thế hệ cần thiết trong từng lần chạy để đạt được yêu cầu về sai số là 0.05. (1) – phương án ‘lai ghép nút’ (2) – phương án ‘lai ghép trọng số’ Bảng 2.3 So sánh các phương pháp lai ghép STT (1) (2) STT (1) (2) STT (1) (2) 1 294 100 36 176 50 71 183 151 2 202 21 37 32 35 72 113 157 3 21 33 38 50 151 73 120 43 47 4 42 15 39 114 231 74 42 85 5 50 33 40 29 37 75 42 20 6 43 170 41 18 97 76 57 85 7 73 593 42 179 48 77 155 32 8 108 152 43 46 514 78 69 55 9 127 104 44 114 76 79 488 167 10 31 116 45 21 163 80 203 139 11 46 101 46 139 37 81 39 101 12 54 91 47 79 72 82 25 63 13 48 647 48 82 44 83 182 91 14 68 56 49 74 40 84 55 108 15 59 377 50 55 58 85 32 43 16 130 515 51 35 59 86 35 155 17 61 42 52 186 105 87 56 58 18 135 54 53 88 18 88 145 29 19 70 118 54 32 67 89 172 80 20 77 161 55 147 43 90 36 58 21 83 153 56 59 298 91 32 22 22 12 96 57 131 369 92 50 48 23 66 45 58 1268 158 93 277 565 24 44 100 59 122 163 94 23 144 25 24 20 60 65 28 95 44 130 26 150 82 61 211 56 96 20 67 27 187 41 62 25 69 97 56 146 28 60 33 63 26 58 98 25 105 29 30 24 64 50 129 99 184 44 30 67 43 65 66 60 100 26 329 31 28 150 66 124 37 32 47 60 67 10 15 33 178 11 68 44 35 34 39 40 69 8 22 35 159 5 70 109 101 Trung bình 99.13 112.65 Nhận xét: Kết quả trung bình sau 99.13 thế hệ phương pháp ‘lai ghép nút’ đã đạt yêu cầu thấp hơn một chút so với phương pháp ‘lai ghép trọng số’ là 112.65 thế hệ. c. Thử nghiệm so sánh giải thuật di truyền và giải thuật lan truyền ngược sai số Thử nghiệm hai phương pháp với bài toán nổi tiếng XOR. Có 4 mẫu học như sau: X1 X2 Y 0 0 0 0 1 1 1 0 1 1 1 0 Tham số chung cho cả hai phương pháp: 48 - Mạng nơ-ron sử dụng là mạng có một lớp ẩn - Số nơ-ron trong lớp ẩn: 2 - Ngưỡng sai số dừng lặp: 0.05 hoặc quá 10000 vòng lặp Tham số của giải thuật lan truyền ngược sai số: - Hằng số học: 0.3 Tham số của giải thuật di truyền: - Số lượng quần thể: 100 - Xác suất lai: 0.3 - Xác suất đột biến: 0.1 - Sử dụng phương pháp lai ghép nút và đột biến nút Sau đây là bảng thống kê số bước lặp để mạng hội tụ với mỗi phương án trong 100 lần thử nghiệm khác nhau. GA: giải thuật di truyền BP: giải thuật lan truyền ngược sai số - : mạng không hội tụ (số lần lặp lớn hơn 10000) Bảng 2.4 Kết quả thử nghiệm so sánh GA và BP với ngưỡng sai số 0.0005 STT GA BP STT GA BP STT GA BP 1 1075 1515 36 283 - 71 1936 - 2 613 1005 37 - 1417 72 2004 3827 3 4629 1613 38 692 2863 73 2550 1594 4 372 1121 39 703 - 74 628 - 5 - - 40 - 1827 75 298 1754 6 678 1770 41 - 1930 76 612 2665 7 777 - 42 254 1848 77 461 - 8 704 - 43 - - 78 812 911 9 - 1666 44 527 - 79 1088 - 10 2198 1618 45 - 4613 80 206 - 11 1392 3397 46 2307 - 81 1051 - 12 - - 47 285 1591 82 - 1323 13 5645 5569 48 - 1612 83 - 2319 14 - 2822 49 1663 - 84 479 2495 15 2330 - 50 - 1457 85 - - 16 - 2935 51 1067 - 86 1931 - 17 426 1373 52 - 2462 87 566 4041 18 844 2023 53 793 - 88 730 1833 19 875 - 54 261 2710 89 594 - 20 - 3320 55 5262 - 90 - - 49 21 790 2397 56 - - 91 - 1555 22 - 1176 57 - 1325 92 1986 1493 23 1542 - 58 635 1279 93 252 1850 24 714 - 59 326 - 94 243 1195 25 629 2018 60 929 - 95 739 - 26 550 - 61 3106 1572 96 - - 27 566 - 62 6286 3351 97 903 1238 28 1462 - 63 692 - 98 - - 29 1238 1751 64 - - 99 2149 - 30 844 - 65 - 2879 100 760 3040 31 - - 66 487 1729 32 791 1150 67 209 1347 33 1153 1604 68 910 - Số lần mạng hội tụ 70 58 34 - 7368 69 - 2083 35 - 1558 70 2505 1050 Trung bình 1228.59 2152.53 Kết quả trong 100 lần chạy : - Giải thuật di truyền chạy thành công được 70 lần trung bình 1228.59 vòng lặp một lần chạy. - Giải thuật lan truyền ngược sai số chạy thành công được 58 lần trung bình 2152.53 vòng lặp. Ta có thể thấy rằng giải thuật di truyền có khả năng đạt được yêu cầu về hội tụ (sai số ≤ 0.05) tức tìm vùng chứa cực trị toàn cục dễ dàng hơn so với giải thuật lan truyền ngược sai số. Hay nói cách khác giải thuật lan truyền ngược sai số dễ rơi vào vùng chứa cực tiểu cục bộ hơn giải thuật di truyền. Trong 100 lần chạy, GA chỉ có 30 lần không tìm được cực trị toàn cục trong khi đó BP là 42 lần. 2.2.6 Giải thuật đề xuất Trong thử nghiệm so sánh GA với BP ở trên ta thấy: tuy GA có khả năng đưa mạng vùng chứa cực tiểu toàn cục dễ dàng hơn so với BP tuy nhiên vẫn còn nhiều trường hợp GA không làm mạng hội tụ được (trong thử nghiệm trên 30/100 lần mạng không hội tụ với GA). Nguyên nhân nào đã làm cho mạng rơi vào cực tiểu địa phương mà không thoát ra được? Sau nhiều lần thử nghiệm, chúng tôi nhận thấy rất nhiều trường hợp mạng không thể hội tụ vì một số giá trị trọng số của mạng đã quá lớn. Có thể giải thích điều này là do phương pháp đột biến sử dụng là chỉ đột biến kiểu BIASED (phần 2.2.4). Phương pháp đột biến này sẽ cộng vào trọng số được đột biến một giá trị ngẫu nhiên xung quanh 0. Như Montana D. và Davis L. [16] đã thử nghiệm và nhận xét rằng phương pháp đột biến này là hiệu quả hơn UNBIASED (trọng số được đột biến sẽ được thay thế bằng một giá trị ngẫu nhiên xung quanh 0) do kế thừa được tính "tốt" của thế hệ trước. Tuy nhiên một số trường hợp đột biến kiểu BIASED sẽ đẩy một số trọng số ngày càng rời xa gốc 0 và có thể mạng sẽ rơi 50 vào cực tiểu cục bộ mà không thoát ra được. Làm sao có thể tận dụng được những ưu điểm của đột biến dạng BIASED nhưng lại giúp mạng không rơi vào cực tiểu cục bộ chúng tôi đề xuất một phương pháp đột biến như sau: Kết hợp đột biến BIASED với đột biến UNBIASED trong đó đột biến BIASED sẽ đóng vai trò chủ đạo (xác suất đột biến lớn hơn). Đột biến UNBIASED được đưa thêm vào với mục đích giúp cho các trọng số có giá trị quá lớn chuyển về các giá trị nhỏ (giá trị ngẫu nhiên xung quanh 0). Do đó, có thể giúp mạng thoát khỏi cực tiểu cục bộ. Việc thử nghiệm giải thuật cải tiến được tiến hành với các tham số giống như thuật toán GA trong thử nghiệm 2.3.5 nhưng có kết hợp thêm đột biến UNBIASED với xác suất đột biến nhỏ: 0.03. Sau đây là số lần lặp để mạng hội tụ với phương pháp đột biến đề xuất : Bảng 2.5 Kết quả thử nghiệm với giải thuật đề xuất STT Số lần lặp STT Số lần lặp STT Số lần lặp 1 8510 36 277 71 1538 2 1052 37 1339 72 654 3 404 38 457 73 2986 4 215 39 - 74 190 5 912 40 2153 75 568 6 - 41 3177 76 169 7 7322 42 7414 77 201 8 873 43 627 78 - 9 4701 44 4248 79 6371 10 1014 45 1076 80 - 11 - 46 272 81 292 12 825 47 219 82 - 13 840 48 - 83 838 14 2835 49 6985 84 9910 15 157 50 2552 85 1207 16 216 51 473 86 4587 17 8552 52 8128 87 418 18 976 53 - 88 326 19 258 54 809 89 - 20 1151 55 4745 90 5244 21 481 56 - 91 216 22 4024 57 9084 92 514 23 835 58 1133 93 516 24 839 59 5617 94 1047 25 305 60 164 95 728 26 729 61 186 96 896 27 2935 62 525 97 900 28 614 63 8968 98 813 51 29 890 64 334 99 565 30 1020 65 1522 100 4819 31 1816 66 461 32 6075 67 5859 33 223 68 323 Số lần mạng hội tụ 89 34 - 69 533 35 1667 70 630 Trung bình 2135.61 Có thể rút ra một số nhận xét sau thử nghiệm này: - Số lần mạng hội tụ tăng lên rất nhiều so với đột biến chỉ dùng phương pháp BIASED (89 so với 70). - Số lần lặp để mạng hội tụ của phương pháp cải tiến cao hơn nhiều so với đột biến chỉ dùng phương pháp BIASED (2135.61 so với 1228.59). Có nghĩa là phương pháp cải tiến có nhiều khả năng đưa mạng về trạng thái hội tụ tuy nhiên thời gian hội tụ trung bình dài hơn so với phương pháp đột biến chỉ dùng BIASED. 2.3 Kết hợp giải thuật di truyền với giải thuật lan truyền ngược sai số để tối ưu hoá trọng số mạng nơ-ron nhân tạo 2.3.1 Đặt vấn đề Mặc dù GA có khả năng đạt tới cực trị toàn cục cho quá trình tìm kiếm nhưng do có kết hợp những yếu tố ngẫu nhiên nên tốc độ tìm kiếm nói chung là rất chậm. Mặt khác nó không thể hoàn toàn đạt được tới cực trị toàn cục mà chỉ cho những kết quả xung quanh đó. Đối lập với GA, giải thuật lan truyền ngược sai số (BP) lại cho phép đạt được những cực trị nếu như điểm xuất phát của quá trình tìm kiếm nằm trong vùng cực trị toàn cục. Để chứng minh nhận xét này chúng ta sẽ xem xét thử nghiệm sau: Thử nghiệm được tiến hành với bài toán XOR có các tham số như trong thử nghiệm 2.2.5c. Riêng giá trị sai số dừng lặp giảm đi 100 lần là: 0.0005. Khi đạt được giá trị sai số rất nhỏ như vậy có thể coi mạng đã đạt được gần chính xác vị trí cực tiểu toàn cục. Thử nghiệm so sánh hai giải thuật: GA’ - giải thuật di truyền sử dụng phương pháp đột biến đề xuất (2.2.6) BP - giải thuật lan truyền ngược sai số Sau đây là bảng thống kê số bước lặp để mạng hội tụ với mỗi phương án trong 100 lần thử nghiệm khác nhau. 52 Bảng 2.6 Kết quả thử nghiệm so sánh GA’ và BP với ngưỡng sai số 0.0005 STT GA’ BP STT GA’ BP STT GA’ BP 1 - 4329 36 - 3150 71 - - 2 - - 37 2216 - 72 - 3811 3 - 7599 38 - 6215 73 - - 4 - 5122 39 - 3299 74 - 5214 5 - 5741 40 - - 75 - - 6 1791 - 41 - 4142 76 - 5388 7 - 6796 42 - - 77 - 3458 8 - - 43 - 9778 78 - - 9 2882 - 44 - - 79 - - 10 - 6960 45 - 6099 80 - - 11 - - 46 - 4066 81 6291 - 12 - 3792 47 - 3420 82 - - 13 - 2905 48 - 3974 83 - 4567 14 3860 - 49 - - 84 - - 15 - 6098 50 - - 85 - - 16 - - 51 - 3424 86 - 5535 17 - 5307 52 - 7975 87 - 5532 18 - 5935 53 - - 88 - 4443 19 - - 54 - 4838 89 - - 20 - 4014 55 - 6510 90 - - 21 - - 56 - 3979 91 - - 22 - 4710 57 - - 92 - 3523 23 - - 58 - 5583 93 - - 24 - 4314 59 - 3207 94 - - 25 - - 60 - 4802 95 - 6073 26 - 3798 61 - 5154 96 - 5708 27 - 3735 62 - 4030 97 - 4090 28 - 7098 63 - 5222 98 - - 29 - - 64 - - 99 - - 30 - - 65 - 3916 100 - - 31 - - 66 - 3940 32 - 8349 67 - - 33 - - 68 - 6560 Số lần mạng hội tụ 6 57 34 - 2987 69 - 3149 35 874 5030 70 - 4121 Trung bình 2985.67 4956.39 Qua thử nghiệm này có thể dễ dàng nhận thấy rằng chỉ rất ít trường hợp GA’ đạt được giá trị sai số mong muốn. Kết hợp với kết quả trong bảng 2.4 và 2.5 ta có thể tóm tắt khả năng hội tụ của mạng với hai phương pháp học: giải thuật di truyền và giải thuật lan truyền ngược sai số khi ngưỡng sai số dừng lặp khác nhau. 53 Bảng 2.7 So sánh khả năng hội tụ của mạng khi sử dụng hai phương pháp học GA’ và BP với sai số dừng lặp khác nhau Số lần hội tụ trong 100 lần thử nghiệm Sai số dừng lặp GA’ BP 0.05 89 58 0.0005 6 57 Từ bảng 2.7 ta có nhận xét: GA có thể đạt đến vùng chứa cực tiểu toàn cục (sai số 0.05) dễ dàng hơn so với BP (89 lần so với 58 lần). Tuy nhiên, để đạt đến chính xác vị trí cực tiểu toàn cục (sai số 0.0005) thì GA lại rất kém (chỉ có 6 lần). Trong khi đó, hầu hết các trường hợp BP khi đã đưa mạng đến được vùng chứa cực tiểu toàn cục (sai số 0.05) thì BP sẽ đưa mạng đến chính xác cực tiểu toàn cục (sai số 0.0005). Do đó, việc kết hợp GA và BP có nhiều cơ hội đưa mạng đến được chính xác cực tiểu toàn cục. 2.3.2 Kết hợp giải thuật di truyền và giải thuật lan truyền ngược sai số Có thể kết hợp cả GA và BP nhằm đạt tới một kết quả trọn vẹn của bài toán tối ưu trọng số mạng nơ-ron nhân tạo. Trong giải thuật kết hợp này, GA được sử dụng như một bộ khởi tạo cho BP. Tập trọng số được mã hoá thành các nhiễm sắc thể và được tiến hoá nhờ GA. Kết thúc quá trình tiến hoá, bộ trọng số tốt nhất tương ứng với cá thể ưu việt nhất trong quần thể được lựa chọn làm những trọng số khởi tạo cho giải thuật BP. Nó chính là bộ tham số cho phép xác định điểm gần cực trị nhất của hàm giá. Với sự kết hợp này, giải thuật BP sẽ cần phải được thay đổi một vài yếu tố : - Giải thuật không tự khởi tạo trọng số mà nhận các trọng số từ GA. - Thành phần quán tính được loại bỏ để làm tăng tốc độ của quá trình hội tụ và loại bỏ dao động. 54 Hình 2.6 Kết hợp giải thuật di truyền và giải thuật lan truyền ngược sai số Việc thử nghiệm giải thuật kết hợp này được tiến hành với bài toán XOR ngưỡng sai số mong muốn là 0.0005. Giải thuật di truyền sử dụng phương pháp đột biến đề xuất (2.2.6). Các tham số cũng như các phần trước. Giải thuật gồm hai bước chính : - (1) GA sẽ đưa mạng đạt đến sai số 0.05 - (2) BP sẽ nhận bộ trọng số tốt nhất của GA đóng vai trò là trọng số khởi tạo (có sai số 0.05) để đưa mạng đến sai số mong muốn 0.0005. Bảng 2.8 Kết quả thử nghiệm giải thuật kết hợp GA’ và BP với ngưỡng sai sô 0.0005 STT (1) (2) STT (1) (2) STT (1) (2) 1 352 1366 36 4273 - 71 434 1793 2 924 2354 37 396 3428 72 - - 3 2520 1853 38 2636 - 73 320 1325 4 591 1260 39 509 1858 74 - - 5 362 1511 40 - - 75 751 1436 6 6949 1750 41 336 1988 76 876 1420 7 604 1768 42 568 922 77 - - 8 695 1730 43 4159 3411 78 1138 4423 9 348 2058 44 4235 1436 79 6986 1736 10 304 2372 45 265 2013 80 439 2724 11 2108 3171 46 2929 1548 81 640 3496 12 6109 1406 47 257 2692 82 472 2014 13 2615 1328 48 674 327 83 - - Khởi tạo tập trọng số Giải thuật di truyền Giữ lại nhiễm sắc thể tốt nhất Tập các trọng số Học bằng giải thuật lan truyền ngược sai số có thay đổi 55 14 653 3173 49 2370 5923 84 5173 1530 15 416 1265 50 242 2906 85 520 2769 16 2702 1783 51 594 1948 86 - - 17 535 2177 52 4925 861 87 3675 881 18 2856 1426 53 127 1248 88 373 2266 19 347 814 54 622 2006 89 632 1244 20 2800 1474 55 784 536 90 851 1331 21 1281 1184 56 272 6247 91 3852 1901 22 - - 57 8297 2247 92 3728 2300 23 3090 1399 58 7299 1356 93 1700 2806 24 426 2177 59 634 1434 94 - - 25 1685 1961 60 442 6227 95 3448 1020 26 1373 3254 61 220 1978 96 772 1850 27 1249 1993 62 3227 4801 97 332 4244 28 165 941 63 1177 - 98 1253 1826 29 605 1439 64 - - 99 764 1480 30 895 2082 65 704 4860 100 952 1499 31 708 2301 66 3922 1161 32 6097 2084 67 460 958 33 260 3072 68 613 1305 Số lần mạng hội tụ 90 87 34 8761 1914 69 - - 35 308 2376 70 164 1850 Trung bình 1778.956 2103.506 Nhận xét: - Cũng giống như lần thử nghiệm trước giải thuật di truyền sử dụng đột biến kết hợp (2.2.6), kết quả mạng hội tụ với sai số 0.05 rất cao (90/100). - Trong 90 lần nhận trọng số khởi tạo từ GA, BP có 87 lần đưa mạng từ sai số 0.05 về sai số 0.0005. Chỉ có 3 lần BP không đưa mạng đến yêu cầu sai số mong muốn (lần thử nghiệm thứ 36, 38, 63). - So sánh với việc sử dụng GA và BP riêng rẽ thì giải thuật kết hợp này cho kết quả tốt hơn rất nhiều. Kết luận chương Trong chương này chúng ta đã nghiên cứu các khái niệm và khả năng ứng dụng của giải thuật di truyền cũng như cách thức để tiến hành thực hiện một bài toán bằng giải thuật di truyền. Giải thuật di truyền được biết đến như một giải thuật tìm kiếm dựa trên học thuyết về chọn lọc tự nhiên và nó cho phép ta đạt được tới cực trị toàn cục. Do đó, áp dụng giải thuật di truyền vào bài toán tối ưu hoá trọng số mạng nơ- ron nhân tạo là một cách tiếp cận tiềm năng. Trong chương này chúng tôi đã nghiên cứu và thử nghiệm một số phương án và đưa ra một số cải tiến về phương pháp đột biến giúp cho quá trình học của mạng nơ-ron được tốt hơn. Ngoài ra chúng tôi cũng kết hợp giải thuật di truyền và giải thuật lan truyền ngược sai số nhằm đạt tới một kết 56 quả trọn vẹn của bài toán tối ưu trọng số mạng nơ-ron nhân tạo. Trong chương tiếp theo chúng ta sẽ nghiên cứu việc ứng dụng mạng nơ-ron nhân tạo với các phương pháp học kết hợp đã đề cập trong chương này vào việc dự báo lưu lượng nước đến hồ Hoà Bình. 57 CHƯƠNG 3 - ỨNG DỤNG MẠNG NƠ RON NHÂN TẠO VÀO VIỆC DỰ BÁO LƯU LƯỢNG NƯỚC ĐẾN HỒ HOÀ BÌNH Luận văn đề cập tới bài toán dự báo lưu lượng dòng chảy đến hồ Hoà Bình phục vụ tốt mục tiêu điều tiết vận hành hồ. Nguồn nước chính cung cấp cho hồ Hoà Bình là nguồn nước từ sông Đà. Dọc theo hệ thống sông Đà có các trạm đo quan trắc khí tượng và thuỷ văn bắt đầu hoạt động từ năm 1902. Trạm đo thuỷ văn gần hồ Hoà Bình nhất là trạm đo Tà Bú. Dự báo nước đến hồ Hoà Bình thực chất là dự báo lưu lượng nước tại trạm Tà Bú. Trong chương này, luận văn trình bày một số nội dung liên quan đến bài toán dự báo và một số thử nghiệm sử dụng những nghiên cứu trong chương 2 để dự báo nước đến hồ Hoà Bình trước 10 ngày. 3.1 Điều kiện địa lý, tự nhiên, khí tượng thuỷ văn lưu vực sông Đà Sông Đà là chi lưu lớn nhất của sông Hồng bắt nguồn từ dãy Ngụy Sơn thuộc tỉnh Vân Nam Trung Quốc chảy vào Việt Nam theo hướng Tây Bắc – Đông Nam ở độ cao trên 1500m sau đó ngoặt sang hướng Đông ở Pa Vinh, khi tới thị xã Hòa Bình thì sông chảy theo hướng Bắc đổ vào sông Hồng ở Trung Hà. Sông Đà có diện tích lưu vực 52.900 km2 trong đó 50.6% thuộc phần lãnh thổ Việt Nam, bao gồm phần trung và hạ lưu sông và chiếm 37% diện tích tập trung nước của sông Hồng. Sông Đà có chiều dài dòng chính là 980km (phần thuộc lãnh thổ Việt Nam dài 540 km). Lưu vực sông Đà có dạng hình thuôn dài chạy dọc theo hướng Tây Bắc – Đông Nam, kéo dài từ 20o40’ đến 25o00’ độ vĩ Bắc và từ 100o22’ đến 105o24’ độ kinh Đông với chiều dài lưu vực 690km (phần thuộc lãnh thổ Việt Nam là 380 km) và chiều rộng bình quân lưu vực 76km (phần trong nước là 80 km). Chiều rộng lưu vực lớn nhất là 165 km thuộc tỉnh Lai Châu còn phần hẹp nhất 25km, thuộc tỉnh Hòa Bình. Độ dốc bình quân lòng sông trung bình 0.41‰, trong đó độ dốc lòng sông thuộc lãnh thổ Trung Quốc là 2,54‰. 3.1.1 Vị trí địa lý Lưu vực sông Đà nằm giữa các dãy núi cao và trung bình chạy dài theo hướng Tây Bắc - Đông Nam. Đặc điểm nổi bật của lưu vực sông Đà là các dạng địa hình núi cao và cao nguyên đều cao và bị chia cắt theo chiều thẳng đứng rất mạnh. Điều nhận thấy rõ rệt là địa hình núi và cao nguyên ở đây có sự sắp xếp song song có ảnh hưởng lớn đến khí hậu của vùng. Có thể nói lưu vực sông Đà chia làm 3 nhóm địa hình: Nhóm kiểu địa hình núi, nhóm kiểu địa hình cao nguyên, nhóm kiểu địa hình thung lũng. 58 3.1.2 Địa hình Địa hình lưu vực sông Đà thuộc vùng Tây Bắc nước ta từ biên giới Việt - Trung, Việt - Lào tới Lai Châu, Mường Lay chủ yếu là các dãy núi ở độ cao trên 1000 m. Địa hình có hình dáng đường sống núi hẹp, có đỉnh cao nhất đạt tới 3076 m, chủ yếu cấu tạo bởi granit, ven rìa xen đá phiến và đá vôi. 3.1.3 Điều kiện địa chất Về cấu trúc địa chất, sông Đà là vùng có cấu trúc địa chất phức tạp và chưa ổn định. Toàn bộ lưu vực phân bố rộng trên nền đá vôi, tạo nên cấu trúc Karst phức tạp, có nhiều đứt gãy ngang. Ba đới đứt gãy chính là đứt gãy sông Hồng, đứt gãy Điện Biên – Lai Châu và đứt gãy sông Mã. Về các hoạt động địa chấn, do lưu vực có địa hình núi chia cắt nên có nhiều quá trình ngoại sinh huỷ hoại, quá trình xói mòn đất, kết hợp với cấu trúc địa chất kém ổn định thường diễn ra các hoạt động địa chấn như động đất. Ngoài ra trong vùng còn thường xuyên có động đất kích thích xảy ra như nứt, trượt, sạt lở đất đặc biệt ở các vùng dốc cao, do tổng hợp của nhiều nguyên nhân khác nhau gây ra: do tác động của trọng lực, do hoạt hoá trở lại của các đứt gãy kiến tạo, vv ... các quá trình địa chất này chủ yếu xảy ra trong giai đoạn đầu khi các hồ chứa tích nước. Các kết quả nghiên cứu trong nhiều năm qua cho thấy cùng với sự tích nước của hồ chứa, các hoạt động địa chất đã tăng lên, hiện tượng động đất kích thích xảy ra mạnh mẽ nhất ở khu vực xung quanh đập thuộc địa phận Thị xã Hoà Bình. 3.1.4 Điều kiện thổ nhưỡng Tây Bắc là vùng rừng núi cao, có độ chia cắt mạnh nhất Việt Nam; riêng với lưu vực sông Đà, thổ nhưỡng có đặc điểm chủ yếu là trên nền đá vôi và đất phong hoá trên nền đá vôi. Tuy nhiên, do địa hình chia cắt mạnh và diễn biến khác biệt về chế độ khí hậu, thuỷ văn giữa các tiểu vùng sinh thái nên loại hình phân bố thổ nhưỡng của lưu vực sông Đà rất đa dạng và phong phú. 3.1.5 Đặc điểm khí hậu Có thể nói rằng khí hậu vùng lưu vực sông Đà là khí hậu nhiệt đới, gió mùa vùng núi với hai mùa rõ rệt. Mùa đông lạnh, suốt mùa đông duy trì một tình trạng hanh khô điển hình, có sương muối và ít mưa (mùa khô) trùng với mùa gió Đông Bắc, kéo dài từ tháng Mười Một năm trước tới tháng Ba năm sau. Mùa hè trùng với mùa gió Tây Nam, nóng có gió tây khô nóng và nhiều mưa (mùa mưa), kéo dài từ tháng Năm tới tháng Chín hàng năm. Giữa hai mùa (tháng Tư, tháng Mười) là thời kỳ chuyển tiếp, nền nhiệt ẩm và có tính ôn hoà. 59 Về cơ bản, mùa mưa gần như trùng với mùa nóng và mùa khô trùng với mùa lạnh. Mưa đá cũng thường xảy ra trong thời kỳ quá độ từ mùa lạnh sang mùa nóng. Lượng mưa ở vùng lưu vực sông Đà phân bố rất không đều phụ thuộc vào đặc điểm của địa hình, giá trị trung bình năm biến đổi khá mạnh mẽ từ 1300-3200mm. Vùng mưa lớn Hoàng Liên – Sa Pa đạt tới trên 2000mm, trong khi vùng mưa ít Nam Sơn La chỉ đạt 1200 - 1600mm. Tương ứng với vùng mưa lớn cũng là vùng có lượng ẩm phong phú quanh năm, đồng thời vùng mưa ít cũng là vùng thiếu ẩm, chủ yếu là trong mùa Đông. Lưu vực sông Đà có độ ẩm cao và ít thay đổi. Độ ẩm tuyệt đối dao động trong phạm vi từ 11 - 32mb và độ ẩm tương đối khá cao, trung bình năm trong toàn vùng lưu vực sông Đà dao động trong khoảng từ 80 – 85% và không chênh lệch nhiều giữa các vùng (mùa nóng độ ẩm không khí trung bình khoảng 84 – 87%, mùa lạnh có khí hậu khô lạnh, độ ẩm không khí chỉ có 72 – 75%). Lượng bốc hơi lớn nhất (đo bằng ống Piche) dao động trong phạm vi khá rộng, từ 666 đến 1052 mm/năm. Thời kỳ giữa mùa khô đến đầu mùa mưa (II-V) có lượng bốc hơi lớn nhất, đạt 70-150mm/tháng. Vào thời kỳ còn lại, lượng bốc hơi dao động trong khoảng 40-70mm/tháng. Toàn lưu vực sông Đà chịu tác động của cơ chế gió mùa Đông Nam Á với hai mùa gió: gió mùa đông và gió mùa hạ. Gió mùa đông bị chi phối bởi không khí cực đới lục địa và không khí nhiệt đới biển Đông đã biến tính. Gió mùa hạ bị chi phối bởi ba khối không khí: không khí nhiệt đới biển Bắc Ấn Độ Dương (gió Tây Nam), không khí xích đạo (gió Nam) và không khí biển Thái Bình Dương. Cơ chế gió mùa và sự thay đổi điều kiện bức xạ theo chu kỳ năm tạo nên biến đổi tuần hoàn năm của hầu hết các yếu tố khí hậu, nổi bật nhất là sự hình thành và diễn biến của các mùa. 3.1.6 Đặc điểm chế độ thuỷ văn a. Mạng lưới sông ngòi Sông ngòi trong lưu vực sông Đà có những đặc điểm khác so với những vùng Đông Bắc. Dòng chính của sông Đà có hướng trùng kiến tạo của khu Tây Bắc. Sông suối trong lưu vực sông Đà thuộc loại sông trẻ, thung lũng sông hẹp, nhiều đoạn có dạng hẻm vực sâu, chứng tỏ địa hình mới được nâng lên rất mạnh. Phần lớn lòng sông cao hơn mặt biển từ 100 - 500m. Do đó sông đang đào lòng mạnh, trắc diện hẹp, bồi tụ ít và lắm thác ghềnh. Thượng lưu sông Đà kể từ nguồn tới Pắc Ma, dòng sông chảy theo hướng Tây Bắc - Đông Nam. Lòng sông đoạn này hẹp, mùa cạn rộng, trung bình 40 - 60m. Độ 60 dốc lớn chỉ tính từ biên giới Việt Trung tới Lai Châu dài khoảng 125km, đạt độ dốc bình quân tới 160cm/km. Trung lưu sông Đà từ Pắc Ma tới Suối Rút, sông vẫn chảy theo hướng Tây Bắc - Đông Nam. Dòng sông chảy giữa hai bờ núi rất cao. Độ dốc đáy sông giảm xuống rõ rệt, còn khoảng 38 - 40cm/km nhưng thác ghềnh còn nhiều. Về mùa cạn, lòng sông rộng trung bình 90 - 100m. Tại hạ lưu sông Đà từ Suối Rút tới cửa sông (Trung Hà), lòng sông mở rộng rõ rệt, trung bình khoảng 200m về mùa cạn. Độ dốc dòng sông giảm không nhiều. Ngoài Thác Bờ, trên đoạn này không còn thác nữa, trong khi đó bãi bồi lại khá nhiều. Từ suối Rút, sông Đà chảy theo hướng Tây Đông cho tới Hoà Bình. Qua Hoà Bình, sông Đà chuyển theo hướng Tây Nam - Đông Bắc. Chính những khối núi Ba Vì, Viên Nam, Đối Thôi đã buộc sông Đà phải đổi hướng như vậy. Thung lũng sông trên đoạn này mở rộng tới 10km, giao thông tương đối thuận lợi. Không kể những phụ lưu lớn, dòng chính sông Đà có mạng lưới thuỷ văn phân bố không đồng đều. Mật độ sôn