Tích hợp giải thuật di truyền với giải thuật huấn luyện mạng Nơ ron truyền thẳng nhiều lớp và ứng dụng trong dự báo dữ liệu

  • Số trang: 89 |
  • Loại file: PDF |
  • Lượt xem: 12 |
  • Lượt tải: 0
nhattuvisu

Đã đăng 26946 tài liệu

Mô tả:

Đ Ạ I HỌC Q U Ố C G IA H À N Ộ I KHOA CÔNG NGHỆ N G U Y Ẽ N LONG G IANG T ÍC H H Ợ• P G I Ả I T H Ư Ậ• T DI T R U Y È N V Ớ I G I Ả I T H U Ậ• T H U Ấ N L U Y Ệ N M Ạ N G N O R O N T R U Y Ề N T H Ả N G N H ỈÈ U LỚ P V À Ừ NG D Ụ N G T R O N G DỤ B Á O DỮ L IỆ• U • • C H U Y Ê N N G À N H : C Ô N G N G H Ệ T H Ô N G T IN M Ả SỐ : 1.01.10 LUẬN VẢN THẠC s ĩ NGƯ Ờ I HƯỚNG D ẢN K H O A HỌC PGS.TS. V Ũ Đ Ứ C THI H À N Ộ I - 2003 í ITRlifil I i____ I M ỤC LỤC M ục l ụ c .................................................................................................................................................. I M ục lục từ viết t á t .........................................................................................................................III Mở đ ầ u ................................................................................................................................................. I Những đóng góp chính của luậnv ã n ............................................................................. 2 Câu trúc của luận văn.........................................................................................................2 C hương 1 : C ác khái niệm CƯ bán về m ạng nơ r ơ n .......................................................4 1.1. Nơ ron sinh học và mạng nơ ron sinh h ọ c .........................................................4 1.2. Nơ ron nhân t ạ o .........................................................................................................4 1.3. Mạng nơ ron nhân tạ o .............................................................................................. 6 1.4. Thủ tục học của mạng nơ r o n ................................................................................8 1.5. Phạm vi ứng dụng của mạng nơ r o n ..................................................................10 C hương 2 : Giải thuật di tr u y ề n ..............................................................................................12 2.1. Tổng quan về giải thuật di truyền.......................................................................... 12 2.2. Giải thuật di truyền đơn g iả n ............................................................................... 14 2.3. Nền tảng toán học của giải thuật di truyền.....................................................20 2.4. Những cải tiến của giải thuật di truyền.............................................................21 Chưưng 3 : Tích hựp giai thuật di truvền với giái thuật huân luyện mạng nư ron truvền thảng nhiều lứp................................................................................ 26 3.1. Mạng nơ ron truyền thẳng và thuật toán lan truyền ngược của sai số ....26 3.1.1. Kiến trúc cơ b ả n ..................................................................................... 26 3.1.2. Cơ chế học của mạng nơ ron truyền thảng nhiều lớp................. 28 3.1.3. Giải thuật lan truyền ngược của sai s ố ............................................29 3. i .4. Một số cải tiến của giải thuật BP.............................................. 40 II 3.2. Sử dụng giải thuật di truyền kết hợp với giải thuật lan truyền ngược của sai số trong việc huấn luyện mạng nơ ron truyền thẳng nhiều lớp........................................................................................................................... 42 3.2.1 Đặt vấn đề................................................................................................ 42 3.2.2. Giải thuật di truyền trong việc huấn luyện mạng nơ ron truyền thẳng nhiều lớ p ......................................................................................43 3.2.3. Ghép nối với giải thuật lan truyền ngược của sai s ố .....................45 C h ư ơ n g 4 : Cài đật ch ư ơ n g t r ì n h ..............................................................................................47 4.1. Cấu trúc dữ liệu và các khai báo cần thiết.....................................................47 4.2. Thiết kế giải thuật ............................................................................................... 48 C hư ư n g 5 : ứ n g d ụ n g m ạ n g nư ron tru vền th ả n g n h iều lớp tro n g d ự báo d ữ liệ u .............................................................................................................................................................. 60 5.1. Sư lược về ứng dụng mạng nơ ron trong dựbáo dữ liệ u ............................. 60 5.2. Các bước chính trong việc thiết kế mô hình mạng nơ ron dự b á o .......... 61 5.3. Úng dụng mạng I1Ơ ron truyền thẳng nhiều lớp trong dự báo đinh lũ sông Trà Khúc trạm Sơn G ia n g .........................................................................65 5.4. Chương trình dự báo dữ liệ u ............................................................................. 68 Kết l u ậ n ...................................................................................................................................................74 Tài liệu th am k h ả o ............................................................................................................................ 76 Phụ l ụ c ......................................................................................................................................................... i Ill M Ụ C L Ụ C T Ừ V IẾ T T Ắ T T ừ v iết tắt N g h ĩ a t iế n g V iệt T iế n g A n h tư ư n g ứ n g GA Giải thuật di truyền Genetic algorithm SG A Giải thuật di truyền đơn giản Simple genetic algorithm BP Giải thuật lan truvềnngược Back-Propagation o f Error của sai sô M Ở ĐẦU Dự báo dữ liệu là bài toán quan trọng mang lại nhiều lợi ích thiết thực phục vụ con người, nó giúp con người nắm bắt được các quy luật vận động trong tự nhiên và trong đời sông kinh tế xã hội. Trong những năm gần đây, các mạng nơ ron truyền thẳng nhiều lớp được thực tiễn chứns minh là khá mạnh và hiệu quả trong các bài toán dự báo và phân tích số liệu, đặc biệt trong các bài toán dự báo sử dụng năng lượng, dự báo kinh tế. dự báo trong tự nhiên... Các mạng nơ ron truyền thằng phải được huấn luyện trước khi sử cỉụng đê thực thi một bài toán dự báo trong thực tế. Với một cấu trúc mạng được chọn, quá trình huấn luyện mạng là quá trình hiệu chinh các trọng số của mạng và thường được phát biểu dưới dạng một bài toán tối thiểu hoá hàm sai số huấn luyện. Thú tục huấn luyện cần một giải thuật tìm kiếm có khả năng tìm lời giải toàn cục, không phụ thuộc vào quá trình khởi động các trong số ban đầu. Ngoài ra, các giải thuật này phải có khả năng tìm kiếm hiệu quả trong không gian nhiều chiều do số lượng trọng sô trong các mạng nơ ron là khá lớn. Giải thuật GA là giải thuật tìm kiếm dựa trên quá trình chọn lọc tự nhiên, di truyền và tiến hóa. Các nguyên lý cơ bản của giải thuật được tác giả J.H.Holland đề xuất lần đầu vào năm 1962, nền tảng toán học của giải thuật GA được tác giả công hố trong cuốn sách “Sự thích nghi trong các hệ thống tự nhiên và nhân tạo” xuất bản năm 1975. Giải thuật GA được xem như một phương pháp tìm kiếm có bước chuyển ngẫu nhiên mang tính tổng quát để giải các bài toán tối ưu hoá. Với những đặc thù riêng của mình, giải thuật GA được sử dụng khá hiệu quả trong thú tục huấn luyện mạng nơ ron. Tuy nhiên, giải thuật GA gặp khó khăn về sự hội tụ. Giải thuật GA đơn giản do Holland đề xuất đã được chứng minh là không bảo đảm sự hội tụ hoặc không hội tụ tới lời giải toàn cục. Ngoài ra, các giải pháp cải tiến chiến lược thay thế hoặc toán tử đột biến tuy giúp cho giải thuật GA hội tụ, nhưng sự hội tụ này dễ dẫn đến hiện tượng hội tụ sớm, nghĩa là giải thuật kết thúc tại một cực trị địa phương mà không có khả năng tìm thấy cực trị toàn cục. 2 Giải thuật huấn luyện kinh điển lan truyền ngược của sai số (giải thuật BP) được sử dụng rộng rãi nhất trong việc huân luyện mạng nơ ron truyền thảng. Giải thuật này đám bảo sự hội tụ nhưng dễ hội tụ tại một cực trị địa phương mà không có khả năng tìm kiếm cực trị toàn cục. Mặt khác, kết quá huấn luyện của giải thuật này phụ thuộc vào nhiều yếu tố, đặc biệt là quá trình khởi động các trọng số ban đầu. Do nhu cầu cấp thiết phải xây dựng một giải thuật vừa có khá năng tìm kiếm lời giải toàn cục, vừa phải đảm báo sự hội tụ để huấn luyện cho mạng nơ ron truyền thẳng thực thi một bài toán dự báo trong thực tế, luận văn tập trung nghiên cứu giải pháp tích hợp giải thuật GA với giải thuật BP trong việc huấn luyện mạng nơ ron truyền thẳng. Trên cơ sở đó, luận văn trình bày các bước chính để xây dụng mô hình mạng nơ ron dự báo dữ liệu và ứng dựng mô hình đó trong bài toán dự báo đỉnh lũ sông Trà Khúc tại trạm khí tượng Sơn Giang. Những đóng góp chính cua luận văn • Luận văn trình bày các vấn để lý thuyết về mạng nơ ron, mạng nơ ron truyền thẳng nhiểu lớp và thuật toán BP dạng tổng quát để huấn luyện mạng, một số vấn đề về sử dụng giải thuật BP đế huấn luyện mạng thực thi một bài toán trong thực tế. • Luận văn trình bày các vấn đề lý thuyết về giải thuật SGA và những cải tiến của giải thuật SGA. • Luận văn xây dựng giải pháp tích hợp giải thuật GA với giải thuật BP thành một giải thuật lai GA - BP dể huấn luyện mạng nơ ron truyền thẳng nhiêu lớp. • Luận văn trình bày ứng dụng giải thuật lai GA - BP trong mô hình mạng nơ ron dự báo. Giải thuật lai GA - BP đã được cài đặt và thử nghiệm để huân luyện mạng nơ ron truyền thẳng trong bài toán dự báo khí tượng thuỷ văn. Cấu trúc của luận vãn Phấn mớ đầu của luận văn giới thiệu nội dung nghiên cứu, tính cấp thiết của đề tài và những đóng góp chính của luận văn. Chương 1 giới thiệu các khái niệm cơ bản và phạm vi ứng dụng cùa mạng nơ ron. Chương 2 giới thiệu về giải thuật SGA 3 và các cải tiến của giải thuật SGA. Chương 3 giới thiệu về mạng nơ ron truyền thẳng nhiều lớp, giải thuật BP. các vấn đề về sử dụng giải thuật BP và xây dựng giải pháp tích hợp giải thuật GA với giải thuật BP trong việc huấn luyện mạng nơ ron truyền thảng nhiều lớp. Chương 4 trình bày mô hình thuật toán và cài đặt giải thuật lai GA - BP. Chương 5 trình bày các bước xây dựng mô hình mạng nơ ron dự báo và thứ nghiệm giải thuật GA - BP trong việc huấn luyện mạng nơ ron đê thực thi bài toán dự báo đinh lũ sông Trà Khúc tại trạm Sơn Giang. Phđn kết luận nêu ra các kết luận từ luận văn và các hướng nghiên cứu tiếp theo. Phần phụ lục đưa ra một số chức năng của chương trình được viết bằng Visual Basic. 4 Chương 1 CÁC KHÁI NIỆM C ơ BẨN VỂ M Ạ N G N ơ RON Chương này đề cập đến các vân đề sau: 1.1. Nơ ron sinh học và mạng nơ ron sinh học 1.2. Nơ ron nhân tạo 1.3. Mạng nơ ron nhân tạo 1.4. Thủ tục học của mạng nơ ron 1.5. Phạm vi ứng dụng của mạng nơ ron 1.1. Nơ ron sinh học và mạng nơ ron sinh học Hệ thần kinh ở người có khoảng 10'° tế bào thần kinh được gọi là các nơ ron [24]. Mỗi nơ ron gồm có ba phần: thân nơ ron với nhân ở bên trong, một đầu thần kinh ra và một hệ thống hình cây các đầu thần kinh vào. Độ lớn của các tín hiệu vào có thể bị thay đổi khi được truyền qua các khớp thần kinh có trên các nhánh thần kinh vào. Tỷ lệ biến đổi tín hiệu ở khớp thần kinh được gọi là độ khuyếch đụi khớp và được gọi là các trọng s ố trong các nơ ron nhân tạo. Theo các nghiên cứu về sinh học, chức năng của hệ thần kinh không phụ thuộc nhiều vào vai trò của từng nơ ron đơn lé mà phụ thuộc vào cách mà toàn bộ các nơ ron được nối với nhau, gọi là mạng nơ von sinli học [24], 1.2. Nư ron nhân tạo Nơ ron nhân tạo là mò hình toán học mô phỏng nơ ron sinh học. Mỗi nơ ron nhân tạo được gọi là một đơn vị xử lý với chức nâng: nhận tín hiệu vào từ các đơn vị phía trước (hay một nguồn bên ngoài), tính tín hiệu ra từ các tín hiệu vào và lan truyền tín hiệu ra sang các đơn vị khác. 5 a Jl ^ g(at) H’ a,= Ỹ , w>‘x‘+ e' Zj = g(aj) Hình 1. 1: Đơn vị xử lý thứ j Mồi tín hiệu đầu vào nơ ron thứ j được ký hiệu là Xị với trọng số tương ứng là Wjị. Đại lượng đo tín hiệu tổng cộng đi vào nơ ron thứ j, ký hiệu là ơj, được xác định một cách đơn giản như sau : • dị là hàm của các tín hiệu X, và các trọng số Wjị, gọi là Hàm kết hợp • Hàm kết hợp là tổng các tích của tín hiệu Xị và trọng số tương ứng Wj: n a>= ^ W jiXi 6j + Trong đó 0 là một tham số được gọi là ngưỡng của nơ ron. Nếu Wjị>0, nơ ron được coi là ở trong trạng thái kích thích. Nếu Wjị < 0, nơ ron ở trạng thái kiềm chế. Quá trình biến đổi giá trị dj thành tín hiệu đầu ra Zj được thực hiện bới hàm kích hoạt (hàm chuyên) phi tuyến Zj= g(dj). Hàm kích hoạt phải thoả mãn các điều kiện sau: • Tín hiệu đầu ra Zj là không âm với bất kể giá trị nào của dj • g là hàm liên tục và bị chặn trong khoảng [0,1 ] Những hàm thỏa mãn điều kiện trên còn được gọi là các hàm nén theo nghĩa chúng nén tín hiệu đầu ra vào một khoảns nhỏ. Có khá nhiều hàm thoả mãn các điều kiện trên, song trong thực tế chi có một số hàm thường được sử dụng trong các mạng nơ ron như sau 1) Hàm tuyến tính (Linear): g(.x) = X 2) Hàm ranh giới cứng (Hard-Limiter) : Hàm này chỉ có hai giá trị là 0 và 1, ngoài ra hàm còn có một giá trị ngưỡng 6. Tín hiệu đầu ra phụ thuộc tổng tín hiệu đầu vào và giá trị ngưỡng. ifị x >6 ) if(jc < e ) 6 Vi hàm này rất thuận tiện khi đưa câu trả lời có hay không nên nó thường xuyên được sử dụng cho các tín hiệu ra cuối cùng của mạng. 3) Hàm ngưỡng logic: if(.T > 9 ) if(jt < 0) 4) Hàm sigmoid (Sigmoid function (logsig)) gW = \ + e~x Hàm này đặc biệt thuận lợi khi sử dụng cho các mạng được huấn luyện bằng giái thuật BP. bởi vì nó dễ lấy đạo hàm, do đó có thể giảm đáng kể tính toán trong quá trình huấn luyện. Mặt khác, hàm này được ứng dụng cho các bài toán mà đầu ra mong muốn rơi vào khoang [0,1]. 1.3. Mạng nư ron nhân tạo Khái niệm Mạng nơ ron nhân tạo là hệ thống bao gồm nhiều nơ ron nhân tạo kết hợp với nhau. Hệ thống này có khả năng học số liệu và tổng quát hóa từ các số liệu được Cáu trúc Mạng nơ ron nhân tạo được biểu diễn bàng một đồ thị gồm một tập các nút và các cung có hướng, mỗi nút tương ứng với một nơ ron, các cung biểu diễn các liên kết giữa các nơ ron. Cấu trúc mans nơ ron gồm cơ cấu tổ chức và sơ đồ kết nối. Cơ cấu tổ chức thường được xác định bởi số lớp mạng và số nơ ron trong mỗi lớp: • Lớp vào : Các nơ ron trong lớp vào gọi là các nơ ron vào, chúng không xử lý thông tin mà chí mã hóa mẫu đưa vào mạng để xử lý. Thông thường, số thuộc tính của mẫu đưa vào mạng bằng số nơ ron vào, chính là số đầu vào của mạng. • Lớp ẩn : Các nơ ron trong lớp này gọi là các nơ ron ẩn vì chúng không thể 7 quan sát trực tiếp được. Mạnơ có thê có một hay nhiều lớp ẩn. Chúng cung cấp các mô hình toán học phi tuyến cho mạng. • Lớp ra : Các nơ ron ở lớp này gọi là các nơ ron ra, các nơ ron này mã hoá giá trị hay khái niệm của các mẫu đưa vào mạng. Ví dụ, trong bài toán phân lớp. mỗi đầu ra là đại diện cho một lớp các đối tượng. Sơ đồ kết nối xác định bởi phương thức kết nối giữa các nơ ron trong mạng [21]: • Mạng truyền thẳng : Luồng dữ liệu đi từ các nơ ron vào đến các nơ ron ra chí được truyền thẳng. Khống có các liên kết từ các nơ ron ra tới các nơ ron vào trong cùng một lớp hay của các lớp trước đó. Lớp vào w (1) " 11 Lớp ân (2) wl Lớp ra Hình ỉ . 2: Mạng nơron truyền thẳng nhiều lớp (Feed-Forward Neural Network) • Mạng hồi quy: Có chứa các liên kết ngược, nghĩa là các liên kết từ nơ ron lớp ra tới nơ ron lớp vào trong cùng một lớp hoặc các lớp trước đó. h0 ^ Lớp vào Lớp ẩn o Lớp ra Hình 1.3: Mạng hồi quy (Recurrent Neural Network) Các thông số cấu trúc của mạng Dưới đây là các thông số cấu trúc của mạng nơ ron nhân tạo: • Sơ đồ kết nối (mạng truyền thảng hay hồi quy) • Sỏ tin hiệu vào và số tín hiệu ra • Số lớp mạng • Số nơ ron trên mỗi lớp • Số lượng các trọng số của mỗi lớp 1.4. Thủ tục học của mạng nư ron Thành phần quan trọng nhất và không thể thiếu của các mạng nơ ron là các thủ tục học (giải thuật huấn luyện mạng). Có thể chia các thủ tục này thành hai nhóm chính là h ọ c th a m s ố và h ọ c c ấ u trú c . Cả hai thủ tục học này có thể được thực hiện đồng thời hoặc tách biệt. Các thủ tục học tham số lại có thể được chia thành ba lớp nhỏ hơn là h ọ c có th ầ y [24], h ọ c tă n g cư ờ ng [6] và h ọ c k h ô n g c ó th ầ y [16]. Học tham sò Với một cấu trúc mạng cho trước, các trọng số của mạng (gọi là các tham số của mạng) phải được xác định trước khi sử dụng mạng để thực thi một nhiệm vụ cụ thể. Ngoại trừ trường hợp các mạng nơ ron một lớp Hopfield (các trọng số được tính toán một cách giải tích), thông thường, các trọng số của mạng được khởi tạo ngẫu nhiên trong một khoáng nhất định. Học tham số là quá trình điểu chỉnh các trọng số đế mạng nhận biết được mối quan hệ giữa đầu vào và đầu ra mong muốn. Rất nhiều các thuật toán học được đề xuất để tìm tập trọng số tối ưu đối với mỗi bài toán, các thuật toán đó có thể chia thành hai nhóm chính : H ọ c c ó th ầ y (Supervised learning) và H ọ c k h ô n g c ó th ầ y (Unsupervised Learning). • H ọ c c ó th ầ y Mạng được học bằng cách cung cấp cho nó các cặp mẫu đầu vào và đầu ra inonỉỉ muốn. Sai số giữa các đầu ra thực tế so với các đầu ra mong muốn được thuật toán sử dụng để hiệu chính các trọng số tronạ mạng. 9 Tập mẫu là tập các cặp véc tơ vào - ra mong muốn M = {x¡,y¡)} được sử dụng đê luyện mạng nơ ron. Đối với mỗi véc tơ tín hiệu vào Xị, mạng nơ ron tính toán tín hiệu ra out và so sánh tín hiệu này với tín hiệu ra mong muốn y, để tạo ra tín hiệu sai số. Tín hiệu sai số này xác định bể mặt sai số là hàm của các trọng số, có thể dùng như hàm mục tiêu để hiệu chinh các trọng số. Các giải thuật tìm kiếm được áp dụng trong thủ tục học đê hiệu chỉnh các trọng số sao cho mạng nơ ron có thê sản sinh ra các tín hiệu ra out với một sai số chấp nhận được so với tín hiệu ra mong muốn [13]. H ình 1.4. Sơ đồ học có thầy • H ọ c không có thầy Với phương pháp học không có thầy, không có thông tin phản hồi từ môi trường bên ngoài để chi ra rằng đầu ra out của mạng là đúng hay sai. Mạng nơ ron phái tự khám phá các đặc trưng, các mối tương quan, tính cân xứng của các mẫu học một cách tự động. Đối với phần lớn các biến thể của học không có thầy, các đích trùng với đáu vào. Nói một cách khác, học không có thầy luôn thực hiện một công việc tương tự như một mạng tự liên hợp, cô đọng thông tin từ dữ liệu vào. H ọ c càu trú c Trong phần học tham số, giả định là đã có một cấu trúc mạng. Thú tục học tham số tinh chinh các giá trị trọng số sao cho mạng hoạt động như mong muốn. Thu tục học cấu trúc tìm kiếm các tham sô cấu trúc của mạng để tạo ra một mạng hoạt động tốt nhất. Thực chất, học cấu trúc là việc tìm ra số lớp ẩn và số nơ ron trên 10 mỗi lớp ẩn vì số đầu vào và số đầu ra của mạng là xác định đối với một bài toán cụ Kết quả học cấu trúc phụ thuộc nhiều vào kết quả học tham số. Do đó, việc xây dựng một giải thuật tìm kiếm cho thú tục học tham số là cần thiết. Giải thuật tìm kiếm này phải có khả năng tìm kiếm lời giải toàn cục, tìm kiếm hiệu quả trong không gian nhiều chiều và có thể sử dụng cho nhiều cấu trúc mạng khác nhau. Trong những nãm gần đây, một số giải thuật tối ưu toàn cục mang tính tất định và một số giải thuật mang tính xác suất đã được đề xuất. Các giải thuật mang tính xác suất hao gồm các giải thuật tiến hóa{3] mà giải thuật GA là một ví dụ điển hình. Giải thuật GA sẽ được trình bày trong chương 2 của luận văn. 1.5. Phạm vỉ ứng dụng của mạng nơ ron Mạng nơ ron thường được ứng dụng trong các lĩnh vực như phân loại (classification), mô hình hóa (modeling), biến đổi (transformation and mapping) và dự báo các sự kiện phụ thuộc thời gian. P h an lo ạ i Phân loại là cách sắp xếp các đối tượng vào các tập hoặc vào các lớp con của các lứp lớn hơn. Việc phân loại thường được tiến hành nhiều mức giống như phép toán ra quyết định, phân lớp đối tượng vào nhóm, nhóm con; vào chủng loại, chủng loại con hoặc vào lớp, lớp con. Một đối tượng có thể đồng thời thuộc vào nhiều lớp khác nhau, do đó kết quả của việc phân loại là tích của hai hay nhiều quyết định. M ò h ìn h hóa Hệ thống phân loại thường đưa ra câu trả lời rời rạc như có, không hoặc một số nguyên định danh đối tượng đầu vào thuộc lớp nào. Tuy nhiên, việc mô hình hóa yêu cầu hệ thống phải sản sinh ra các câu trả lời mang tính liên tục. Một số lượng nhỏ các số liệu thực nghiệm được sử dụng đê xây dựng mô hình, mô hình này có thể đưa ra các dự báo cho tất cả các đối tượng đầu vào có thể. Việc tìm ra đường cong phù hợp với các số liệu thực nghiệm là một ví dụ ứng dụng thuộc dạng này. Các ứng dụng thuộc dạng này phần lớn là thủ tục của một biến vào và một biến ra như sau: y = f (x, a, b......p) 11 Hàm f chứa một tập các tham số a, b..... p. Các tham số này phải được xác định bàng việc tối thiểu hóa độ chênh lệch giữa số liệu thực nghiệm và giá trị tính toán từ mô hình. Mô hình hóa cũng có thể mở rộng cho bài toán nhiều biến vào một biến ra hoặc nhiều biến vào - nhiều biến ra. Việc mô hình hóa thường được sử dụng cho các đối tượng có ít biến, khoảng từ 1 đến 10. Điều này có nghĩa là thường sử dụng các mạng nhỏ, thời gian tính cũng như tài nguyên máy tính ít hơn so với các mạng dùng cho việc phân loại. B iế n đổi Việc biến đổi nhằm mục đích nén các đối tượng từ không gian m chiều vào không gian có số chiều nhỏ, khoáng hai hoặc ba. Qua việc nén các đối tượng này, chúng sẽ bộc lộ những đặc điểm mà chúng ta không nhận thấy khi chứng ở trong khỏng gian nhiều chiều. Việc biến đổi tương tự như việc nhóm các đối tượng hay phân loại. Sự khác biệt không lớn làm nằm ở phương pháp biểu diễn các kết quả. Những câu hỏi mà việc biến đổi có thể trá lời là bàn đồ của toàn bộ đối tượng như thế nào, có bao nhiêu vùng trên bản đồ có thể phân biệt được, hình dáng các vùng đó như thế nào... Một trong những ứng dụng của biến đổi là tiền xử lý số liệu. Thông qua tiền xử lý, các đối tượng điển hình được chọn từ tập vô số các đối tượng ngẫu nhiên nhận được, loại trừ được các đối tượng dư thừa hay trùne lặp. Điều này rất quan trọng khi chọn các đối tượng làm mẫu học cho mạng truyền thầng huấn luyện bằng giải thuật BP đề cập ở chương 3. D ự báo các sự kiệ n p h ụ th u ộ c th ờ i g ian Lĩnh vực nghiên cứu các quá trình phụ thuộc ihời gian là một trong những lĩnh vực chính trong nghiên cứu điều khiển quá trình, ở đây, mô hình dự báo được xây dựng dựa trên một chuỗi số liệu được ghi nhận theo thời gian. Trong mô hình này, các biến của tín hiệu vào và tín hiệu ra về cơ bản là giống nhau. Chỉ một điều khác biệt là, tín hiệu vào là các giá trị hiện tại và quá khứ của các biến quá trình, tín hiệu ra là giá trị dự báo trong tương lai của các biến quá trình đó. 12 Chương 2 G I Ả I T H U Ậ T DI T R U Y Ể N Chương này trình bày các vấn đề sau: 2.1. Tổng quan về giải thuật di truyền 2.2. Giải thuật di truyền đơn giản 2.3. Nền táng toán học của giải thuật di truyền 2.4. Những cải tiến tiếp theo của giải thuật di truyền 2.1. Tổng quan về giải thuật di truyền Giải thuật GA thuộc lớp các giải thuật tìm kiếm tiến hóa. Khác với phần lớn các giai thuật tìm kiếm theo điểm, giải thuật GA thực hiện tìm kiếm song song trên một tập gọi là quần thể các lời giải có thể. Thống qua việc áp dụng các toán tử di truyền, giải thuật GA trao đổi thông tin giữa các cực trị và do đó làm giám thiếu khá năng kết thúc giải thuật tại một cực trị địa phương. Trong thực tế, giải thuật GA đã được áp dụng thành công trong nhiều lĩnh vực bao gồm cả thú tục huấn luyện mạng nơ ron [7, 11]. N ộ i d u n g g ia i th u ậ t d i truyền Giải thuật GA lần đầu tiên được tác giả J. H. Holland giới thiệu vào năn 1962 [12, 14]. Giải thuật GA mô phỏng quá trình tồn tại của các cá thể có độ phù hợp tốt thông qua quá trình tiến hóa trong tự nhiên, sao cho khi thực thi giải thuật, quần thể các lời giải ban đầu tiến hoá dần tới lời giải mong muôn. Giải thuật GA duy trì một quần thể các lời giải có thể của bài toán tối ưu hóa. Mỗi lời giải gọi là một cá thế hay một nhiễm sắc thể, thường được mã hóa dưới dạng một chuỗi các gen, giá trị của các gen có trong chuỗi được lấy từ một báng các ký tự được định nehĩa trước. Mỗi chuỗi gen được liên kết với một giá trị gọi là giá trị thích nghi, còn gọi là độ phù hcrp của chuỗi. Độ phù hợp của mỗi chuỗi gen đánh giá độ 13 thích nehi của nó với môi trường (độ tốt xấu của lời giải) và được dùng trong quá trình chọn lọc. Quần thể mới được tạo ra bàng cách sử dụng các quá trình chọn lọ c , la i ghép và đột biến. Ọuá trình chọn lọc sao chép các cá thẻ có độ phù hợp tốt vào một quần thế tạm thời được gọi là quần thể bố mẹ. Các cá thê trong quần thể bố mẹ được ghép đôi một cách ngẫu nhiên và tiến hành lai ghép tạo ra các cá thể con. Sau khi tiến hành quá trình lai ghép, giải thuật GA mô phỏng một quá trình khác trong tự nhiên là quá trình đột biến, trong đó các gen của các cá thể con tự thay đổi giá trị với một xác xuất nhỏ. Như vậy, giải thuật GA xuất phát với tập lời giải ban đầu, thông qua nhiều hước trons quá trình tiến hoá hình thành các tập lời giải mới tốt hơn, và cuối cùng tìm ra lời giải đủ tốt chấp nhận được (lời giải gần với lời giải tối ưu). Dưới đây là sơ đồ khối của giải thuật di truvền Ỉ-ÌHT Sinh quàn ti Ifc* bdl IdU : Hh' ♦ Co Cd thê" nào đạt đẽn ÒI gứí tối ưu xar 1nh l o th ú I IJII -ùđ cac cá thế trorg quan thế ìr r h \ray ớùa? lơ j ---- T T Xây dưhq quár ttip’ mríi ằỵ dư’nq thé hẻ t ẻ tiẽp 2.1. Sơ đổ khối của giải thuật di truyền - ?i- 14 Các bước chính trong việc áp dụng giải thuật di truyền Để áp dụng giải thuật GA giải một bài toán trong thực tế, các bước sau đày cần được thực hiện: Bước l : Chọn tập lời giải ban đầu cho bài toán. Bước 2 : Mã hoá các lời giải dưới dạng các chuỗi, thông thường các lời giải được mã hóa thành các chuỗi nhị phân. Bước 3 : Tìm hàm số thích nahi (hàm phù hợp) cho bài toán và tính giá trị thích nahi cho mỗi lời g iả i, còn sọi là giá trị độ phù hợp. Bước 4 : Dựa trên giá trị thích nshi của mỗi lời giải đê’ thực hiện chọn lọc (selecttion) và tiến hóa các lời giải. Các phương pháp tiến hóa gồm la i ghép (crossover) và đột biến (mutation). Bước 5 : Tính các giá trị thích nghi cho các lời giải mới và loại bỏ các lời giải kém nhất, chỉ giữ lại một số nhất định các lời giải Bước 6 : Nếu chưa tìm được lời giải tối ưu hay chưa hết hạn chu kỳ xác định thì trở lại Bước 4 để tìm lời giải mới. Bước 7 : Tim được lời giải tối ưu chấp nhận được hoặc nếu chu kỳ cho phép đã chấm dứt thì báo cáo kết quả tính được. Có nhiều lựa chọn khác nhau cho từng vấn đề trên. Phần tiếp theo sẽ đưa ra cách lựa chọn theo J.H.Holland khi thiết kế phiên bản giải thuật GA đầu tiên. Giải thuật này được gọi là giải thuật di truyền đơn giản (SGA) [12,14] 2.2. G iải thuật di truyền đon giản J. H. Holland sử dụng mã hóa nhị phân để biểu diễn các cá thể, lý do là phần lớn các bài toán tối ưu hóa, lời giải đều có thể được mã hóa thành chuỗi nhị phân khá đơn giản [14], Mỗi lời giải được mã hóa thành một chuỗi bít, mỗi chuỗi bít sau dó được giải mã để lấy lại giá trị thực và giá trị hàm mục tiêu được tính theo giá trị thực này. Tuỳ từnR bài toán cực tiểu hay cực đại, giá trị hàm mục tiêu được biến đổi thành giá trị thích nghi cho từng chuỗi. Quần thể chuỗi ban đầu được khới động ngẫu nhiên và sau đó được tiến hóa từ thê hệ này sang thế hệ khác bàng cách sử dụng ba toán tử : 15 Chọn lọc (selecttion) L a i tạo (crossover) Đ ột biến (m u ta tio n ) C họn lọc Chọn lọc là việc lựa chọn các cá thê để tham gia vào các pha tiếp theo của quá trình tiến hóa, việc lựa chọn này phụ thuộc vào giá trị thích nghi của cá thê’ đó, nghĩa là những cá thể nào có giá trị thích nghi cao hơn sẽ có khả năng có nhiéu con cháu hơn trong các thế hệ tiếp theo. Giá trị thích nghi quyết định sự tồn tại hay diệt vong của một cá thể. Giá trị thích nghi được tính từ hàm thích nghi, việc ánh xạ từ hàm mục tiêu sang hàm thích nghi được trình bày ở phẩn sau. Mô hình chọn lọc thường được dùng là bánh xe xổ số (roulette wheel selection). Giải thuật GA sử dụng một vòng tròn trong đó mỏi cá thể chiếm một phần tương với của cá thể Vị độ rộng là xác suất chọn lọc của mỗi cá thể. Xác suất chọn lọc Pi được tính theo công thức p,= eval(v;)/F, trong đó eval(vị) là giá trị thích nghi của cá thể Vị, F là tổng giá trị thích nghi của toàn quần thể F = ịe v a lịv j). Mỗi khi thực hiện một lần quay vòn tròn, một ứng cử viên được chọn cho việc lai ghép. Việc quay vòng tròn được thực hiện qua những bước sau: Bước I : Đánh số các cá thể trong quần thể. Tính tổng giá trị thích nghi của toàn quần thể và gọi nó là tổng thích nghi (Total fitness). Bước 2 : Sinh một số ngẫu nhiên n trong khoảng từ 0 đến tổng thích nghi. Bước 3 : Trả lại cá thể đầu tiên trong quần thể có giá trị thích nghi của nó cộng với giá trị thích nghi của các cá thể trước đấy lớn hơn hoặc bằng n. L a i ghép Toán tử chọn lọc nhằm tìm ra những cá thể tốt nhất nhưng không tạo ra cá thê mới. Tuy vậy, trong tự nhiên, các con sẽ thừa hưởng di truyền những đặc tính tốt từ cả cha và mẹ. Toán tử tác động trên các cá thể cha và mẹ để tạo ra các con lai tốt được gọi là lai ghép. Chúng chỉ được áp dụng lên cặp cha mẹ được chọn với xác suất lai ghép ký hiệu là PLT0SS[14], Xác xuất này cho chúng ta số lượng Pcross*pop_size cá 16 thể được dùng cho hoạt động lai ghép với pop_size là kích thước quần thế. Ngoài các cá thế đó ra. các cá thể con là bản sao trực tiếp từ cha mẹ. Toán tử lai ghép trong giải thuật SGA là toán tử lai ghép một điểm cắt. Giả sử chuỗi cá thể có độ dài L (chuỏi có L bít), toán từ lai ghép được tiến hành qua hai giai đoạn là : • Phát sinh một số ngẫu nhiên r trong miền [0; 1] • Nếu r < Pcrosschọn cá thể đó đê lai ghép. Sau đó. kết hợp các cá thể được chọn một cách ngẫu nhiên. Với mỗi cặp cá thể, phát sinh một số ngẫu nhiên pos từ miền [1, L]. Số pos báo hiệu vị trí của điểm lai ghép. Hai cá thể : (b|b2...b p0SbpHS+|...b L) và (ccc2... Cpos^pos+1 • • -CL) d ư ợ c th a y t h ế bởi c ặ p c o n c h á u : ( b , b 2. . . b p - Xem thêm -