Luận án Nghiên cứu một thuật toán tìm điểm tối ưu toàn cục trong quá trình luyện mạng nơron bằng thuật toán vƣợt khe có sự kết hợp với giải thuật di truyền

uấn luyện chất lƣợng mạng, performance learning, là một lớp quan trọng khác của luật huấn luyện, trong phƣơng pháp này thì các thông số mạng đƣợc điều chỉnh để tối ƣu hóa chất lƣợng của mạng. Thuật toán lan truyền ngƣợc là một phát minh chính trong nghiên cứu về mạng nơ-ron, thuộc loại thuật học chất lƣợng mạng (học có giám sát). Ngƣợc dòng thời gian, chúng ta thấy rằng sau khoảng mƣời năm kể từ khi lan truyền ngƣợc bắt đầu đƣợc thai nghén, năm 1974, thì thuật học lan truyền ngƣợc đƣợc chính thức nghiên cứu lại và mở rộng ra một cách độc lập bởi David Rumelhart, Geoffey Hinton và Ronald Williams; David Parker và Yann Le Cun. Thuật toán đã đƣợc phổ biến hóa bởi cuốn sách Parallel Distributed Processing của nhóm tác giả David Rumelhart và James Mc Clelland. Tuy nhiên, thuật toán nguyên thủy thì quá chậm chạp đối với hầu hết các ứng dụng thực tế [1], có nhiều lý do cho việc hội tụ chậm trong đó có sự ảnh hƣởng của bƣớc học. Luận án Tiến sĩ Kỹ thuật 2013 111 Nhắc lại rằng lan truyền ngƣợc, tiền thân của nó là thuật học Widow-Hoff (thuật toán LMS, Least Mean Square), là một thuật toán xấp xỉ giảm dốc nhất. Giống với luật học LMS, hàm mục tiêu là trung bình bình phƣơng sai số. Điểm khác giữa thuật toán LMS và lan truyền ngƣợc chỉ là cách mà các đạo hàm đƣợc tính. Đối với mạng tuyến tính một lớp đơn giản, sai số là hàm tuyến tính tƣờng minh của các trọng số, và các đạo hàm của nó liên quan tới các trọng số có thể đƣợc tính toán một cách dễ dàng. Trong các mạng nhiều lớp với các hàm phi tuyến, mối quan hệ giữa các trọng số mạng và sai số là cực kỳ phức tạp. Để tính các đạo hàm, chúng ta cần sử dụng luật chuỗi. Chúng ta đã thấy rằng giảm dốc nhất là một thuật toán đơn giản, và thông thƣờng chậm nhất. Thuật toán gradient liên hợp và phƣơng pháp Newton’s nói chung mang đến sự hội tụ nhanh hơn [6]. Khi nghiên cứu về các thuật toán nhanh hơn thì thƣờng rơi vào hai trƣờng phái. Trƣờng phái thứ nhất phát triển về các kỹ thuật tìm kiếm. Các kỹ thuật tìm kiếm bao gồm các ý tƣởng nhƣ việc thay đổi tốc độ học, sử dụng qui tắc mô-men, bƣớc học thích nghi. Trƣờng phái khác của nghiên cứu nhằm vào các kỹ thuật tối ƣu hóa số chuẩn, điển hình là phƣơng pháp gradient liên hợp, hay thuật toán Levengerg-Marquardt (một biến thể của phƣơng pháp Newton). Tối ƣu hóa số đã là một chủ đề nghiên cứu quan trọng với 30, 40 năm, nó dƣờng nhƣ là nguyên nhân để tìm kiếm các thuật toán huấn luyện nhanh. Ta biết rằng, thuật toán LMS đƣợc đảm bảo để hội tụ tới một lời giải cực tiểu hóa trung bình bình phƣơng sai số, miễn là tốc độ học không quá lớn. Điều này là đúng bởi vì trung bình bình phƣơng sai số cho một mạng tuyến tính một lớp là một hàm toàn phƣơng. Hàm toàn phƣơng chỉ có một điểm tĩnh. Hơn nữa, ma trận Hessian của hàm toàn phƣơng là hằng số, cho nên độ dốc của hàm theo hƣớng là không thay đổi, và các hàm đồng mức có dạng hình e-lip. Lan truyền ngƣợc giảm dốc nhất (SDBP) cũng nhƣ LMS, nó cũng là một thuật toán xấp xỉ giảm dốc nhất cho việc cực tiểu trung bình bình phƣơng sai số. Thật vậy, lan truyền ngƣợc giảm dốc nhất là tƣơng đƣơng thuật toán LMS khi sử dụng trên mạng tuyến tính một lớp. Bâ . . Luận án Tiến sĩ Kỹ thuật 2013 112 . . . (1985). . . . . C Luận án Tiến sĩ Kỹ thuật 2013 113 . . phân loại nhau, gradient descend. Tóm lại, khi giải quyết bài toán bằng mạng nơron theo thủ tục truyền ngƣợc có những vấn đề rút ra là: - Sẽ có bao nhiêu nơron trong mạng, bao nhiêu ngõ vào, bao nhiêu ngõ ra và bao nhiêu lớp ẩn. Càng nhiều lớp ẩn bài toán trở nên phức tạp nhƣng có thể giải quyết đƣợc những vấn đề lớn. - Thuật toán Back propagation cung cấp một phƣơng pháp “xấp xỉ” cho việc tìm trong không gian trọng số (nhằm tìm ra những trọng số phù hợp cho mạng). Chúng ta càng lấy giá trị của tham số học càng nhỏ bao nhiêu thì sự thay đổi trọng số càng nhỏ bấy nhiêu và quỹ đạo không gian học sẽ càng trơn. Tuy nhiên điều này lại làm cho tốc độ học chậm đi. Trái lại, nếu chúng ta chọn tham số tốc độ học quá lớn, sự thay đổi lớn của các trọng số có thể làm cho mạng trở nên không ổn định. Về mặt ý tƣởng, tất cả các nơron trong mạng nên chọn cùng một tốc độ học, tham số học  nên gán một giá trị nhỏ. Các nơron với nhiều ngõ vào nên chọn một tham số tốc độ học nhỏ hơn để giữ một thời gian học tƣơng tự cho nhau cho tất cả các nơron trong mạng. Luận án Tiến sĩ Kỹ thuật 2013 114 II.3.2. Hiệu quả của lan truyền ngƣợc . (w) trọng hóa  i ijij zwa , v i ji ; trên (w). (w) (w 2 ) g O(w) (w) để lan truyền ngƣợc (w) (w 2 ) (w) - . II.4. Các vấn đề trong xây dựng mạng MLP II.4.1. Chuẩn bị dữ liệu a. Kích thước mẫu Không có nguyên tắc nào hƣớng dẫn kích thƣớc mẫu phải là bao nhiêu đối với một bài toán cho trƣớc. Hai yếu tố quan trọng ảnh hƣởng đến kích thƣớc mẫu: ♦ Dạng hàm đích: khi hàm đích càng phức tạp thì kích thƣớc mẫu cần tăng. ♦ Nhiễu: khi dữ liệu bị nhiễu (thông tin sai hoặc thiếu thông tin) kích thƣớc mẫu cần tăng. Luận án Tiến sĩ Kỹ thuật 2013 115 Đối với mạng truyền thẳng, cho hàm đích có độ phức tạp nhất định, kèm một lƣợng nhiễu nhất định thì độ chính xác của mô hình luôn có một giới hạn nhất định. Có thể cần tập mẫu vô hạn để đạt đến giới hạn chính xác. Nói cách khác độ chính xác của mô hình là hàm theo kích thƣớc tập mẫu. Khi kích thƣớc mẫu tăng, độ chính xác sẽ đƣợc cải thiện - lúc đầu nhanh, nhƣng chậm dần khi tiến đến giới hạn. Dạng tổng quát của mối liên hệ giữa sai số và kích thƣớc mẫu nhƣ sau: Hình 3: Mối liên hệ giữa sai số và kích thước mẫu Trong thực hành thƣờng gặp phải 2 vấn đề sau: ♦ Đối với hầu hết bài toán thực tế, mẫu bị ràng buộc chặt chẽ với dữ liệu có sẵn. Ta thƣờng không có đƣợc số lƣợng mẫu mong muốn. ♦ Kích thƣớc mẫu cũng có thể bị giới hạn bởi bộ nhớ hoặc khả năng lƣu trữ của máy tính. Nếu tất cả các dữ liệu đồng thời đƣợc giữ trong bộ nhớ suốt thời gian luyện, kích thƣớc bộ nhớ máy tính sẽ bị chiếm dụng nghiêm trọng. Nếu lƣu trữ trên đĩa sẽ cho phép dùng mẫu lớn hơn nhƣng thao tác đọc đĩa từ thế hệ này sang thế hệ khác khiến cho tiến trình chậm đi rất nhiều. Chú ý: việc tăng kích thƣớc mẫu không làm tăng thời gian luyện. Những tập mẫu lớn hơn sẽ yêu cầu ít thế hệ luyện hơn. Nếu ta tăng gấp đôi kích thƣớc của mẫu, mỗi thế hệ luyện sẽ tốn thời gian khoảng gấp đôi, nhƣng số thế hệ cần luyện sẽ giảm đi một nửa. Điều này có nghĩa là kích thƣớc mẫu (cũng có nghĩa là độ chính xác của mô hình) không bị giới hạn bởi thời gian luyện. Luật cơ bản là: Sử dụng mẫu lớn nhất có thể sao cho đủ khả năng lƣu trữ trong bộ nhớ trong (nếu lƣu trữ đồng thời) hoặc trên đĩa từ (đủ thời gian đọc từ đĩa). Luận án Tiến sĩ Kỹ thuật 2013 116 b. Mẫu con Trong xây dựng mô hình cần chia tập mẫu thành 2 tập con: một để xây dựng mô hình gọi là tập huấn luyện (training set), và một để kiểm nghiệm mô hình gọi là tập kiểm tra (test set). Thông thƣờng dùng 2/3 mẫu cho huấn luyện và 1/3 cho kiểm tra. Điều này là để tránh tình trạng quá khớp (overfitting). c. Sự phân tầng mẫu Nếu ta tổ chức mẫu sao cho mỗi mẫu trong quần thể đều có cơ hội nhƣ nhau thì tập mẫu đƣợc gọi là tập mẫu đại diện. Tuy nhiên khi ta xây dựng một mạng để xác định xem một mẫu thuộc một lớp hay thuộc một loại nào thì điều ta mong muốn là các lớp có cùng ảnh hƣởng lên mạng, để đạt đƣợc điều này ta có thể sử dụng mẫu phân tầng. Xét ví dụ sau: Giả sử ta xây dựng mô hình nhận dạng chữ cái viết tay tiếng Anh, và nguồn dữ liệu của ta có 100.000 ký tự mà mỗi ký tự đƣợc kèm theo một mã cho biết nó là chữ cái nào. Chữ cái xuất hiện thƣờng xuyên nhất là e, nó xuất hiện 11.668 lần chiếm khoảng 12%; chữ cái xuất hiện ít nhất là chữ z, chỉ có 50 lần chiếm 0,05%. Trƣớc hết do giới hạn của bộ nhớ máy tính, giả sử bộ nhớ chỉ có thể xử lý đƣợc 1300 mẫu. Ta tạo hai dạng tập mẫu: tập mẫu đại diện và tập mẫu phân tầng. Với tập mẫu đại diện, chữ e sẽ xuất hiện 152 lần (11,67% của 1300) trong khi đó chữ z chỉ xuất hiện một lần (0,05% của 1300). Ngƣợc lại ta có thể tạo tập mẫu phân tầng để mỗi chữ có 50 mẫu. Ta thấy rằng nếu chỉ có thể dùng 1300 mẫu thì tập mẫu phân tầng sẽ tạo ra mô hình tốt hơn. Việc tăng số mẫu của z từ 1 lên 50 sẽ cải thiện rất nhiều độ chính xác của z, trong khi nếu giảm số mẫu của e từ 152 xuống 50 sẽ chỉ giảm chút ít độ chính xác của e. Bây giờ giả sử ta dùng máy tính khác có bộ nhớ đủ để xử lý một lƣợng mẫu gấp 10 lần, nhƣ vậy số mẫu sẽ tăng lên 13000. Rõ ràng việc tăng kích thƣớc mẫu sẽ giúp cho mô hình chính xác hơn. Tuy nhiên ta không thể dùng tập mẫu phân tầng nhƣ trên nữa vì lúc này ta sẽ cần tới 500 mẫu cho chữ z trong khi ta chỉ có 50 mẫu trong nguồn dữ liệu. Để giải quyết điều này ta tạo tập mẫu nhƣ sau: tập mẫu gồm tất cả các chữ hiếm với số lần xuất hiện của nó và kèm thêm thông tin về chữ có nhiều mẫu nhất. Chẳng hạn ta tạo tập mẫu có 50 mẫu của chữ z (đó là tất cả) và 700 mẫu của chữ e (chữ mà ta có nhiều mẫu nhất). Nhƣ vậy trong tập mẫu của ta, chữ e có nhiều hơn chữ z 14 lần. Nếu ta muốn các chữ z cũng có nhiều ảnh hƣởng nhƣ các chữ e, khi học chữ z ta cho chúng trọng Luận án Tiến sĩ Kỹ thuật 2013 117 số lớn hơn 14 lần. Để làm đƣợc điều này ta có thể can thiệp chút ít vào quá trình lan truyền ngƣợc trên mạng. Khi mẫu học là chữ z, ta thêm vào 14 lần đạo hàm, nhƣng khi mẫu là chữ e ta chỉ thêm vào 1 lần đạo hàm. Ở cuối thế hệ, khi cập nhật các trọng số, mỗi chữ z sẽ có ảnh hƣởng hơn mỗi chữ e là 14 lần, và tất cả các chữ z gộp lại sẽ có bằng có ảnh hƣởng bằng tất cả các chữ e. d. Chọn biến Khi tạo mẫu cần chọn các biến sử dụng trong mô hình. Có 2 vấn đề cần quan tâm: ♦ Cần tìm hiểu cách biến đổi thông tin sao cho có lợi cho mạng hơn: thông tin trƣớc khi đƣa vào mạng cần đƣợc biến đổi ở dạng thích hợp nhất, để mạng đạt đƣợc hiệu suất cao nhất. Xét ví dụ về bài toán dự đoán một ngƣời có mắc bệnh ung thƣ hay không. Khi đó ta có trƣờng thông tin về ngƣời này là “ngày tháng năm sinh”. Mạng sẽ đạt đƣợc hiệu quả cao hơn khi ta biến đổi trƣờng thông tin này sang thành “tuổi”. Thậm chí ta có thể quy tuổi về một trong các giá trị: 1 = “trẻ em” (dƣới 18), 2 = “thanh niên” (từ 18 đến dƣới 30), 3 = “trung niên” (từ 30 đến dƣới 60) và 4 = “già” (từ 60 trở lên). ♦ Chọn trong số các biến đã đƣợc biến đổi biến nào sẽ đƣợc đƣa vào mô hình: không phải bất kì thông tin nào về mẫu cũng có lợi cho mạng. Trong ví dụ dự đoán ngƣời có bị ung thƣ hay không ở trên, những thuộc tính nhƣ “nghề nghiệp”, “nơi sinh sống”, “tiểu sử gia đình”, là những thông tin có ích. Tuy nhiên những thông tin nhƣ “thu nhập”, “số con cái”, là những thông tin không cần thiết. II.4.2. Xác định các tham số cho mạng a. Chọn hàm truyền Không phải bất kỳ hàm truyền nào cũng cho kết quả nhƣ mong muốn. Để trả lời cho câu hỏi «hàm truyền như thế nào được coi là tốt ? » là điều không hề đơn giản. Có một số quy tắc khi chọn hàm truyền nhƣ sau: ♦ Không dùng hàm truyền tuyến tính ở tầng ẩn. Vì nếu dùng hàm truyền tuyến tính ở tầng ẩn thì sẽ làm mất vai trò của tầng ẩn đó: Xét tầng ẩn thứ i: Tổng trọng số ni = wiai-1 + bi ai = f(ni) = wf ni +bf (hàm truyền tuyến tính) Khi đó: tổng trọng số tại tầng thứ (i + 1) ni+1 = wi+1ai + bi+1 Luận án Tiến sĩ Kỹ thuật 2013 118 = wi+1[wf ni +bf] + bi+1 = wi+1 [wf(wiai-1 + bi) + bf] + bi+1 = Wai-1 + b Nhƣ vậy ni+1 = Wai-1 + b, và tầng i đã không còn giá trị nữa. ♦ Chọn các hàm truyền sao cho kiến trúc mạng nơron là đối xứng (tức là với đầu vào ngẫu nhiên thì đầu ra có phân bố đối xứng). Nếu một mạng nơron không đối xứng thì giá trị đầu ra sẽ lệch sang một bên, không phân tán lên toàn bộ miền giá trị của output. Điều này có thể làm cho mạng rơi vào trạng thái bão hòa, không thoát ra đƣợc. Trong thực tế ngƣời ta thƣờng sử dụng các hàm truyền dạng – S. Một hàm s(u) đƣợc gọi là hàm truyền dạng – S nếu nó thỏa mãn 3 tính chất sau: – s(u) là hàm bị chặn: tức là tồn tại các hằng số C1 ≤ C2 sao cho: C1 ≤ s(u) ≤ C2 với mọi u. – s(u) là hàm đơn điệu tăng: giá trị của s(u) luôn tăng khi u tăng. Do tính chất thứ nhất, s(u) bị chặn, nên s(u) sẽ tiệm cận tới giá trị cận trên khi u dần tới dƣơng vô cùng, và tiệm cận giá trị cận dƣới khi u dần tới âm vô cùng. – s(u) là hàm khả vi: tức là s(u) liên tục và có đạo hàm trên toàn trục số. Có 3 dạng hàm kích hoạt thƣờng đƣợc dùng trong thực tế: *Hàm dạng bước:         00 01 x x xstep           x x xstep 0 1 *Hàm dấu:         01 01 x x xstep           x x xstep 1 1 *Hàm sigmoid:     xe xSigmoid 1 1 )( Một hàm truyền dạng - S điển hình và đƣợc áp dụng rộng rãi là hàm Sigmoid. Luận án Tiến sĩ Kỹ thuật 2013 119 b. Xác định số nơron tầng ẩn Câu hỏi chọn số lƣợng noron trong tầng ẩn của một mạng MLP thế nào là khó, nó phụ thuộc vào bài toán cụ thể và vào kinh nghiệm của nhà thiết kế mạng. Nếu tập dữ liệu huấn luyện đƣợc chia thành các nhóm với các đặc tính tƣơng tự nhau thì số lƣợng các nhóm này có thể đƣợc sử dụng để chọn số lƣợng nơron ẩn. Trong trƣờng hợp dữ liệu huấn luyện nằm rải rác và không chứa các đặc tính chung, số lƣợng kết nối có thể gần bằng với số lƣợng các mẫu huấn luyện để mạng có thể hội tụ. Có nhiều đề nghị cho việc chọn số lƣợng nơron tầng ẩn h trong một mạng MLP. Chẳng hạn h phải thỏa mãn h>(p-1)/(n+2), trong đó p là số lƣợng mẫu huấn luyện và n là số lƣợng đầu vào của mạng. Càng nhiều nút ẩn trong mạng, thì càng nhiều đặc tính của dữ liệu huấn luyện sẽ đƣợc mạng nắm bắt, nhƣng thời gian học sẽ càng tăng. Một kinh nghiệm khác cho việc chọn số lƣợng nút ẩn là số lƣợng nút ẩn bằng với số tối ƣu các cụm mờ (fuzzy clusters)[8]. Phát biểu này đã đƣợc chứng minh bằng thực nghiệm. Việc chọn số tầng ẩn cũng là một nhiệm vụ khó. Rất nhiều bài toán đòi hỏi nhiều hơn một tầng ẩn để có thể giải quyết tốt. Để tìm ra mô hình mạng nơron tốt nhất, Ishikawa and Moriyama (1995) sử dụng học cấu trúc có quên (structural leanrning with forgetting), tức là trong thời gian học cắt bỏ đi các liên kết có trọng số nhỏ. Sau khi huấn luyện, chỉ các noron có đóng góp vào giải quyết bài toán mới đƣợc giữ lại, chúng sẽ tạo nên bộ xƣơng cho mô hình mạng nơron. c. Khởi tạo trọng số Trọng thƣờng đƣợc khởi tạo bằng phƣơng pháp thử sai, nó mang tính chất kinh nghiệm và phụ thuộc vào từng bài toán. Việc định nghĩ thế nào là một bộ trọng tốt cũng không hề đơn giản. Một số quy tắc khi khởi tạo trọng: ♦ Khởi tạo trọng sao cho mạng nơron thu đƣợc là cân bằng (với đầu vào ngẫu nhiên thì sai số lan truyền ngƣợc cho các ma trận trọng số là xấp xỉ bằng nhau): |ΔW1/W1| = |ΔW2/W2| = |ΔW3/W3| Nếu mạng nơron không cân bằng thì quá trình thay đổi trọng số ở một số ma trận là rất nhanh trong khi ở một số ma trận khác lại rất chậm, thậm chí không đáng kể. Do đó để các ma trận này đạt tới giá trị tối ƣu sẽ mất rất nhiều thời gian. Luận án Tiến sĩ Kỹ thuật 2013 120 ♦ Tạo trọng sao cho giá trị kết xuất của các nút có giá trị trung gian. (0.5 nếu hàm truyền là hàm Sigmoid). Rõ ràng nếu ta không biết gì về giá trị kết xuất thì giá trị ở giữa là hợp lý. Điều này cũng giúp ta tránh đƣợc các giá trị thái quá. Thủ tục khởi tạo trọng thƣờng đƣợc áp dụng: – B1: Khởi tạo các trọng số nút ẩn (và các trọng số của các cung liên kết trực tiếp giữa nút nhập và nút xuất, nếu có) giá trị ngẫu nhiên, nhỏ, phân bố đều quanh 0. – B2: Khởi tạo một nửa số trọng số của nút xuất giá trị 1, và nửa kia giá trị -1. Giải thuật di truyền Giải thuật di truyền (Genetic Algorithms - GA) đã đƣợ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 [26] và Thomas Back [27]. Trong phần này chỉ trình bày các khái niệm cơ bản về giải thuật di truyền và khả năng ứng dụng của nó. I.2. Tóm tắt về giải thuật di truyền Từ trƣớc tới 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 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ũ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 giải thuật di truyền 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 hóa 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 Luận án Tiến sĩ Kỹ thuật 2013 121 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). Giải thuật di truyền là một kỹ thuật của khoa học máy tính nhằm tìm kiếm giải pháp thích hợp cho các bài toán tối ƣu tổ hợp (combinatorial optimization). Giải thuật di truyền là một phân ngành của giải thuật tiến hóa vận dụng các nguyên lý của tiến hóa nhƣ di truyền, đột biến, chọn lọc tự nhiên, và trao đổi chéo. Giải thuật di truyền thƣờng đƣợc ứng dụng nhằm sử dụng ngôn ngữ máy tính để mô phỏng quá trình tiến hoá của một tập hợp những đại diện trừu tƣợng (gọi là những nhiễm sắc thể) của các giải pháp có thể (gọi là những cá thể) cho bài toán tối ƣu hóa vấn đề. Tập hợp này sẽ tiến triển theo hƣớng chọn lọc những giải pháp tốt hơn. Thông thƣờng, những giải pháp đƣợc thể hiện dƣới dạng nhị phân với những chuỗi 0 và 1, nhƣng lại mang nhiều thông tin mã hóa khác nhau. Quá trình tiến hóa xảy ra từ một tập hợp những cá thể hoàn toàn ngẫu nhiên ở tất cả các thế hệ. Trong từng thế hệ, tính thích nghi của tập hợp này đƣợc ƣớc lƣợng, nhiều cá thể đƣợc chọn lọc định hƣớng từ tập hợp hiện thời (dựa vào thể trạng), đƣợc sửa đổi (bằng đột biến hoặc tổ hợp lại) để hình thành một tập hợp mới. Tập hợp này sẽ tiếp tục đƣợc chọn lọc lặp đi lặp lại trong các thế hệ kế tiếp của giải thuật. Giải thuật di truyền cũng nhƣ các thuật toán tiến hoá đều đƣợc hình thành dựa trên một quan niệm đƣợc coi là một tiên đề phù hợp với thực tế khách quan. Đó là quan niệm "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". Quá trình tiến hoá thể hiện tính tối ƣu ở chỗ thế hệ sau bao giờ cũng tốt hơn thế hệ trƣớc. Quá trình phát triển của giải thuật di truyền có thể đƣợc chỉ ra qua các mốc thời gian sau: 1960: Ý tƣởng đầu tiên về Tính toán tiến hoá đƣợc Rechenberg giới thiệu trong công trình "Evolution Strategies" (Các chiến lƣợc tiến hoá). Ý tƣởng này sau đó đƣợc nhiều nhà nghiên cứu phát triển. Luận án Tiến sĩ Kỹ thuật 2013 122 1975: Giải thuật gen do John Holland phát minh và đƣợc phát triển bởi ông cùng với các đồng nghiệp và những sinh viên. Cuốn sách "Adaption in Natural and Artificial Systems" (Sự thích nghi trong các hệ tự nhiên và nhân tạo) xuất bản năm 1975 đã tổng hợp các kết quả của quá trình nghiên cứu và phát triển đó. 1992: John Koza đã dùng GA để xây dựng các chƣơng trình giải quyết một số bài toán và gọi phƣơng pháp này là "lập trình gen". Ngày nay giải thuật di truyền càng trở nên quan trọng, đặc biệt là trong lĩnh vực tối ƣu hoá, một lĩnh vực có nhiều bài toán thú vị, đƣợc ứng dụng nhiều trong thực tiễn nhƣng thƣờng khó và chƣa có giải thuật hiệu quả để giải. I.3. Các khái niệm cơ bản Giải thuật di truyền dựa vào quá trình tiến hoá trong tự nhiên nên các khái niệm và thuật ngữ của nó đều có liên quan đến các thuật ngữ của di truyền học. I.3.1. Cá thể, nhiễm sắc thể Một cá thể trong giải thuật di truyền, biểu diễn một giải pháp của bài toán. Tuy nhiên không giống với trong tự nhiên, một cá thể có nhiều nhiễm sắc thể (NST),có 1 thì gọi là thể đơn bội, còn nếu có nhiều thì là thể đa bội, ở đây để giới hạn trong giải thuật di truyền ta quan niệm một cá thể có một nhiễm sắc thể. Do đó khái niệm cá thể và nhiễm sắc thể trong giải thuật di truyền coi nhƣ là tƣơng đƣơng. Một NST đƣợc tạo thành từ nhiều gen, mỗi gen có thể có các giá trị khác nhau để quy định một tính trạng nào đó. Trong GA, một gen đƣợc coi nhƣ một phần tử trong chuỗi NST. I.3.2. Quần thể Quần thể là một tập hợp các cá thể có cùng một số đặc điểm nào đấy. Trong giải thuật di truyền ta quan niệm quần thể là một tập các lời giải của một bài toán. I.3.3. Các toán tử di truyền a. Chọn lựa Trong tự nhiên, quá trình chọn lọc và đấu tranh sinh tồn đã làm thay đổi các cá thể trong quần thể. Những cá thể tốt, thích nghi đƣợc với điều kiện sống thì có Luận án Tiến sĩ Kỹ thuật 2013 123 khả năng đấu tranh lớn hơn, do đó có thể tồn tại và sinh sản. Các cá thể không thích nghi đƣợc với điều kiện sống thì dần mất đi. Dựa vào nguyên lý của quá trình chọn lọc và đấu tranh sinh tồn trong tự nhiên, chọn lựa các cá thể trong GA chính là cách chọn các cá thể có độ thích nghi tốt để đƣa vào thế hệ tiếp theo hoặc để cho lai ghép, với mục đích là sinh ra các cá thể mới tốt hơn. Có nhiều cách để lựa chọn nhƣng cuối cùng đều nhằm đáp ứng mục tiêu là các cá thể tốt sẽ có khả năng đƣợc chọn cao hơn. b. Lai ghép Lai ghép trong tự nhiên là sự kết hợp các tính trạng của bố mẹ để sinh ra thế hệ con. Trong giải thuật di truyền, lai ghép đƣợc coi là một sự tổ hợp lại các tính chất (thành phần) trong hai lời giải cha mẹ nào đó để sinh ra một lời giải mới mà có đặc tính mong muốn là tốt hơn thế hệ cha mẹ. Đây là một quá trình xảy ra chủ yếu trong giải thuật di truyền. c. Đột biến Đột biến là một sự biến đổi tại một (hay một số) gen của nhiễm sắc thể ban đầu để tạo ra một nhiễm sắc thể mới. Đột biến có xác suất xảy ra thấp hơn lai ghép. Đột biến có thể tạo ra một cá thể mới tốt hơn hoặc xấu hơn cá thể ban đầu. Tuy nhiên trong giải thuật di truyền thì ta luôn muốn tạo ra những phép đột biến cho phép cải thiện lời giải qua từng thế hệ. I.4. Mô hình giải thuật di truyền Luận án Tiến sĩ Kỹ thuật 2013 124 Nhận các tham số của bài toán Khởi tạo quần thể ban đầu Tính giá trị thích nghi Sinh sản Lai ghép Đột biến Điều kiện dừng Kết thúc Bắt đầu Lựa chọn giải pháp tốt nhất Với các khái niệm đƣợc nêuở trên, giải thuật di truyền đƣợc mô tả nhƣ sau: 1.[Bắt đầu] Nhận các tham số cho thuật toán. 2.[Khởi tạo] Sinh ngẫu nhiên một quần thể gồm n cá thể (là n lời giải cho bài toán). 3. [Quần thể mới] Tạo quần thể mới bằng cách lặp lại các bƣớc sau cho đến khi quần thể mới hoàn thành. a.[Thích nghi] Ƣớc lƣợng độ thích nghi eval(x) của mỗi cá thể. Hình 4: Mô hình của giải thuật di truyền Luận án Tiến sĩ Kỹ thuật 2013 125 b.[Kiểm tra] Kiểm tra điều kiện kết thúc giải thuật. c.[Chọn lọc] Chọn hai cá thể bố mẹ từ quần thể cũ theo độ thích nghi của chúng (cá thể có độ thích nghi càng cao thì càng có nhiều khả năng đƣợc chọn) d.[Lai ghép] Với một xác suất lai ghép đƣợc chọn, lai ghép hai cá thể bố mẹ để tạo ra một cá thể mới. e.[Đột biến] Với một xác suất đột biến đƣợc chọn, biến đổi cá thể mới 4. [Chọn kết quả] Nếu điều kiện dừng đƣợc thỏa mãn thì thuật toán kết thúc và trả về lời giải tốt nhất trong quần thể hiện tại. 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. Luận án Tiến sĩ Kỹ thuật 2013 126 PHỤ LỤC 2: MÃ NGUỒN CHƢƠNG TRÌNH LUYỆN MẠNG NƠRON VỚI BƢỚC HỌC VƢỢT KHE NHẬN DẠNG ĐỐI TƢỢNG % Lap trinh tong quat cho thuat toan vuot khe % Date:15-10-2011 % Version 1 %------------------------------------------------------- a=ap; u0=up; % huongtim d1=subs(Ju1,u1);%d1=diff(J,u1) d2=subs(Ju2,u2);%d2=diff(J,u2) Ju=[d1 d2]; s0=-Ju; PPThammuctieu %J=(u1-5)^2+(u2-5)^2; Jtruoc=J; %Buoc 1 ---------------------------------------- %XL=anpha %XU=beta XL=a; u01=u0+XL*s0; u1=u01(1); u2=u01(2); %J=(u1-5)^2+(u2-5)^2; PPThammuctieu Jsau=J; if Jsau > Jtruoc %Jsau=Jsau; Jtruoc=Jtruoc XL=0; XU=a; else XL=a; b=1.5*a; XU=b; Jtruoc=Jsau; end u02=u0+XU*s0; u1=u02(1); u2=u02(2); PPThammuctieu Jsau=J; while Jsau<Jtruoc % if Jsau > Jtruoc` % F=Jtruoc; % break % else XL=a; b=1.5*a; XU=b; Jtruoc=Jsau; u03=u0+XU*s0; Luận án Tiến sĩ Kỹ thuật 2013 127 u1=u03(1); u2=u03(2); PPThammuctieu Jsau=J; end %end if Jsau > Jtruoc F = Jtruoc; end % Buoc 2 --------------------------------------- % FL1=abs(XU-XL) while (abs(XU-XL)>FD) %FL=abs(XU-XL); %FL1=FL; % if FL <=FD % break % else TH=XL+gama*(XU-XL); teta = TH; u04=u0+TH*s0; u1=u04(1); u2=u04(2); PPThammuctieu Jsau=J; if Jsau<F XU =TH; Jtruoc = F; else XL=TH; u05=u0+XL*s0; u1=u05(1); u2=u05(2); PPThammuctieu Jtruoc=J; end % end end tocdohoc=TH; % if abs(XU-XL)<=FD % XL=XU % end c=tocdohoc %Gradient------------------------------ e{3}=t(:,k)-x{3}; J=J+sum(e{3}.^2); Ju1=diff(J,u1); Ju2=diff(J,u2); %Ham muc tieu e{3}=t(:,k)-x{3}; J=J+sum(e{3}.^2); Luận án Tiến sĩ Kỹ thuật 2013 128 %------------------------------------------ % Lap trinh tong quat cho thuat toan vuot khe % Date:15-10-2011 % Version 1 %------------------------------------------------------- function y = PPTbexulynuocthai(p,t) clc clear; %Nhap du lieu vao he thong L=3;%so lop g=inline('1./(1+exp(-x))');%Activation function unl=[5 16 3];%The units of each layers % lt=0.3;% learning rate J=1; sum=0; sum1=0; %Initital the Weights and biases for i=1:L-1 for n=1:unl(i) for m=1:unl(i+1) w{i}(m,n)=1*rand;%The Weights end end for m=1:unl(i+1) b{i}(m,1)=1*rand;% The biases end end w{L}=eye(unl(L)); while (J>0.00001)& sum<1000 sum=sum+1;%Number of Loops J=0; for k=1:length(p) x{1}=p(:,k);% Inputs vector % Feed forward Propagation for i=1:L-1 s{i}=w{i,1}*x{i}+b{i}; x{i+1}=g(s{i}); %x{i+1}; end %The caculatar error PPThammuctieu %Feed back Propagation for i=L-1:-1:1 e{i}=(x{i+1}.*(1- x{i+1})).*(w{i+1}'*e{i+1}); thuattoanvuotkhe%Su dung thuat toan vuot khe de xac %dinh toc do hoc cua mang neural deltw{i}=(c.*e{i})*x{i}; w{i}=w{i}+deltw{i};% The modify Weights Luận án Tiến sĩ Kỹ thuật 2013 129 deltb{i}=(c.*e{i}).*ones(unl(i+1),1); b{i}=b{i}+deltb{i};% The modify biases end end J=J/2; if mod(sum,100)==0 sum1=sum1+1; data(sum1,1)=sum; data(sum1,2)=J; end end % Example a value x{1} = [22 35 1 6 36]'; for i=1:L-1 s{i}=w{i}*x{i}+b{i}; x{i+1}=g(s{i}); end x{i+1} %x{L} semilogy(data(:,1),data(:,2)),grid %------------------------------- Luận án Tiến sĩ Kỹ thuật 2013 130 PHỤ LỤC 3: MÃ NGUỒN CHƢƠNG TRÌNH LUYỆN MẠNG NƠRON VỚI BƢỚC HỌC VƢỢT KHE ĐỂ NHẬN DẠNG CHỮ VIẾT dinhnghia.h /* *=======================================================================* *------------------------------------------------------------------------ * * DE TAI : HUAN LUYEN MANG NO-RON VOI BUOC HOC TINH THEO NGUYEN LY VUOT KHE * * NGON NGU : C * TRINH DICH : VISUAL C++ * TEN TEP : dinhnghia.h *-----------------------------------------------------------------------* *=======================================================================* */ #define SIGMF(x) 1/(1 + exp(-(double)x))//HAM KICH HOAT NO RON #define DSIGM(y) (float)(y)*(1.0-y))//DAO HAM CUA HAM KICH HOAT NO RON #define SLNRLV 35 // SO LUONG NO RON LOP VAO #define SLNRLA 5 // SO LUONG NO RON LOP AN #define SLNRLR 10 // SO LUONG NO RON LOP RA #define EPSILON 0.06 // SAI SO TRUNG BINH BINH PHUONG DE DUNG QUA TRINH LUYEN MANG #define SLMHL 18 // SO LUONG MAU HUAN LUYEN MANG #define STEPinit 0.5 // GIA TRI KHOI TAO BUOC HOC, CO THE DUNG CHO NHIEU TRUONG HOP #define DCBH 0.0001 // DIEU CHINH BUOC HOC #define MSDCBH 5 // MAU SO DIEU CHINH BUOC HOC #define TSDCBH 5 // TU SO DIEU CHINH BUOC HOC #define BLTD 30000 // BUOC LAP TOI DA #define FD 1e-1 // taphuanluyen.h /* *====================================================================* *-----------------------------------------------------------------------* * DE TAI : HUAN LUYEN MANG NO-RON VOI BUOC HOC TINH THEO NGUYEN LY VUOT KHE * * NGON NGU : C * TRINH DICH : VISUAL C++ * TEN TEP : taphuanluyen.h *-----------------------------------------------------------------------* *=======================================================================* */ #include "dinhnghia.h" //TAP MAU HUAN LUYEN DAU VAO int TAPHUANLUYEN[SLMHL][SLNRLV] = { { 0,1,1,1,1,1,0, /* 0 */ 1,0,0,0,0,0,1, 1,0,0,0,0,0,1, 1,0,0,0,0,0,1, 0,1,1,1,1,1,0 }, { 0,0,0,0,0,0,0, /* 1 */ 0,1,0,0,0,0,1, 1,1,1,1,1,1,1, 0,0,0,0,0,0,1, Luận án Tiến sĩ Kỹ thuật 2013 131 0,0,0,0,0,0,0 }, { 0,1,0,0,0,0,1, /* 2 */ 1,0,0,0,0,1,1, 1,0,0,0,1,0,1, 1,0,0,1,0,0,1, 0,1,1,0,0,0,1 }, { 1,0,0,0,0,1,0, /* 3 */ 1,0,0,0,0,0,1, 1,0,0,1,0,0,1, 1,1,1,0,1,0,1, 1,0,0,0,1,1,0 }, { 0,0,0,1,1,0,0, /* 4 */ 0,0,1,0,1,0,0, 0,1,0,0,1,0,0, 1,1,1,1,1,1,1, 0,0,0,0,1,0,0 }, { 1,1,1,0,0,1,0, /* 5 */ 1,0,1,0,0,0,1, 1,0,1,0,0,0,1, 1,0,1,0,0,0,1, 1,0,0,1,1,1,0 }, { 0,0,1,1,1,1,0, /* 6 */ 0,1,0,1,0,0,1, 1,0,0,1,0,0,1, 1,0,0,1,0,0,1, 0,0,0,0,1,1,0 }, { 1,0,0,0,0,0,0, /* 7 */ 1,0,0,0,0,0,0, 1,0,0,1,1,1,1, 1,0,1,0,0,0,0, 1,1,0,0,0,0,0 }, { 0,1,1,0,1,1,0, /* 8 */ 1,0,0,1,0,0,1, 1,0,0,1,0,0,1, 1,0,0,1,0,0,1, 0,1,1,0,1,1,0 }, { 0,1,1,0,0,0,0, /* 9 */ 1,0,0,1,0,0,1, 1,0,0,1,0,0,1, 1,0,0,1,0,1,0, 0,1,1,1,1,0,0 }, { 1,1,1,1,0,0,0, /* 4 */ 0,0,0,1,0,0,0, 0,0,0,1,0,0,0, 0,0,0,1,0,0,0, 1,1,1,1,1,1,1 }, { 1,1,1,1,0,1,0, /* 5 */ 1,0,0,1,0,0,1, 1,0,0,1,0,0,1, 1,0,0,1,0,0,1, 1,0,0,0,1,1,0 }, Luận án Tiến sĩ Kỹ thuật 2013 132 { 1,0,0,0,0,0,0, /* 7 */ 1,0,0,0,0,0,0, 1,0,0,1,0,0,0, 1,1,1,1,1,1,1, 0,0,0,1,0,0,0 }, { 0,1,0,0,0,1,0, /* 3 */ 1,0,0,0,0,0,1, 1,0,0,1,0,0,1, 1,0,1,0,1,0,1, 0,1,1,0,1,1,0 }, { 1,0,0,0,0,1,1, /* 2 */ 1,0,0,0,1,0,1, 1,0,0,1,0,0,1, 1,0,1,0,0,0,1, 1,1,0,0,0,0,1 }, { 1,1,1,1,0,0,0, /* 4 */ 0,0,0,1,0,0,0, 0,0,0,1,0,0,0, 1,1,1,1,1,1,1, 0,0,0,1,0,0,0 }, { 1,1,1,1,1,1,1, /* 0 */ 1,0,0,0,0,0,1, 1,0,0,0,0,0,1, 1,0,0,0,0,0,1, 1,1,1,1,1,1,1 }, { 0,1,1,0,0,0,1, /* 9 */ 1,0,0,1,0,0,1, 1,0,0,1,0,0,1, 1,0,0,1,0,0,1, 0,1,1,1,1,1,1 } }; //DAU RA MONG MUON TUONG UNG int DRMM[SLMHL][SLNRLR] = { { 1,0,0,0,0,0,0,0,0,0 }, /* 0 */ { 0,1,0,0,0,0,0,0,0,0 }, /* 1 */ { 0,0,1,0,0,0,0,0,0,0 }, /* 2 */ { 0,0,0,1,0,0,0,0,0,0 }, /* 3 */ { 0,0,0,0,1,0,0,0,0,0 }, /* 4 */ { 0,0,0,0,0,1,0,0,0,0 }, /* 5 */ { 0,0,0,0,0,0,1,0,0,0 }, /* 6 */ { 0,0,0,0,0,0,0,1,0,0 }, /* 7 */ { 0,0,0,0,0,0,0,0,1,0 }, /* 8 */ { 0,0,0,0,0,0,0,0,0,1 }, /* 9 */ { 0,0,0,0,1,0,0,0,0,0 }, /* 4 */ { 0,0,0,0,0,1,0,0,0,0 }, /* 5 */ { 0,0,0,0,0,0,0,1,0,0 }, /* 7 */ { 0,0,0,1,0,0,0,0,0,0 }, /* 3 */ { 0,0,1,0,0,0,0,0,0,0 }, /* 2 */ { 0,0,0,0,1,0,0,0,0,0 }, /* 4 */ { 1,0,0,0,0,0,0,0,0,0 }, /* 0 */ { 0,0,0,0,0,0,0,0,0,1 } };/* 9 */ backprop5.c /* *=======================================================================* Luận án Tiến sĩ Kỹ thuật 2013 133 *------------------------------------------------------------------------ * * DE TAI : HUAN LUYEN MANG NO-RON VOI BUOC HOC TINH THEO NGUYEN LY VUOT KHE * * NGON NGU : C * TRINH DICH : VISUAL C++ * TEN TEP : backprop.c *------------------------------------------------------------------------ * *=======================================================================* */ #include #include #include #include "taphuanluyen.h" #include "dinhnghia.h" /************************** DINH NGHIA CAC BIEN TOAN CUC ****************************/ float MTTSLA[SLNRLV][SLNRLA]; //MA TRAN TRONG SO LOP AN float MTTSLR[SLNRLA][SLNRLR]; //MA TRAN TRONG SO LOP RA float BTMTTSLA[SLNRLV][SLNRLA];//BIEN THIEN MA TRAN TRONG SO LOP AN float BTMTTSLR[SLNRLA][SLNRLR];//BIEN THIEN MA TRAN TRONG SO LOP RA float x[SLNRLV]; //VEC-TO DAU VAO LOP VAO float y[SLNRLA]; //VEC TO DAU RA LOP AN float z[SLNRLR]; //VEC TO DAU RA LOP RA float HW1[SLNRLV][SLNRLA]; //KHONG SU DUNG float HW2[SLNRLV][SLNRLA]; //KHONG SU DUNG float OW1[SLNRLA][SLNRLR]; //KHONG SU DUNG float OW2[SLNRLA][SLNRLR]; //KHONG SU DUNG float SSLA[SLNRLA]; //SAI SO LOP AN float SSLR[SLNRLR]; //SAI SO LOP RA int PATR[SLMHL]; float ECM[SLMHL]; float TOCDOHOC=2; //TOC DO HOC int SOBUOCLAP=0; float BVK=0; //BUOC VUOT KHE int NBS=0; float FX[SLMHL]; float F[SLMHL]; float A,GAMA; float QUANTINH=0.1; //TOAN HANG QUAN TINH int MTDVKT[35]; //MA TRAN DAU VAO KIEM TRA long int itr; int HTHL; //HOAN THANH HUAN LUYEN int LCBH; //LUA CHON BUOC HOC int RESET; //RESET MANG int RES=1; //RESET MANG int SDM; //SU DUNG MANG /*************** KET THUC DINH NGHIA CAC BIEN TOAN CUC ****************/ /*************************** CAC NGUYEN MAU HAM ***********************/ int KHOITAOMANG(); void QUATRINHHUANLUYEN(); void DAPUNGDAURA(int afer[]); float GIATRIHAMMUCTIEU(int x[],float y[],int SIZE); void DIEUCHINHTRONGSO(int k); void HAMMUCTIEU(); void BUOCLAP(); /***************************** CAC HAM VA CAC THU TUC ******************/ Luận án Tiến sĩ Kỹ thuật 2013 134 /*---------------------------------------------------------------------- Ten Ham: KHOITAOMANG Mo ta: 1. KHOI TAO MA TRAN TRONG SO LOP AN, VOI CACS GIA TRI NGAU NHIEN BI CHAN 2. KHOI TAO MA TRAN TRONG SO LOP RA, VOI CACS GIA TRI NGAU NHIEN BI CHAN Cac dau vao: KHONG CO Gia tri tra ve: 1 --------------------------------------------------------------------*/ int KHOITAOMANG() { int i,j; int ch; int num; NBS=0; HTHL=2; RESET=0; RES=1; MHL=0; srand(time(0)); for(i=0;i<SLNRLV;i++) for(j=0;j<SLNRLA;j++) { MTTSLA[i][j] = -0.5+ (float) rand()/RAND_MAX; BTMTTSLA[i][j] = 0; } for(i=0;i<SLNRLA;i++) for(j=0;j<SLNRLR;j++) { MTTSLR[i][j] = -0.5 + (float) rand()/RAND_MAX; BTMTTSLR[i][j] = 0; } for(i=0;i<SLMHL;i++) PATR[i] = 0; for(i=0;i<35;i++) MTDVKT[i]=0; return 1; } /*--------------------------------------------------------------------- Ten Thu tuc: TOCDOHOCZERO Mo ta: 1. CAC DAU RA CUA MANG VAN LA ZERO, VI TOC DO HOC LA ZERO. 2. CAC SAI SO HOAN TOAN BANG VOI CAC DAU RA MONG MUON. 3. THU TUC NAY DUNG DE PHUC VU CHO VIEC TINH TOAN BUOC VUOT KHE. Cac dau vao: KHONG CO Gia tri tra ve: KHONG CO ------------------------------------------------------------------------ */ void TOCDOHOCZERO(void) { int t; TOCDOHOC=0; Luận án Tiến sĩ Kỹ thuật 2013 135 BUOCLAP(); HAMMUCTIEU(); for(t=0;t<SLMHL;t++) FX[t] = ECM[t]; } /*--------------------------------------------------------------------- Ten Thu tuc: TINHBUOCHOCVUOTKHE Ngay sua : 03-11-2007 Phien ban : V2 Mo ta: THU TUC TINH BUOC HOC THEO NGUYEN LY VUOT KHE Cac dau vao: KHONG CO Gia tri tra ve: KHONG CO ----------------------------------------------------------------------*/ void TINHBUOCHOCVUOTKHE(void) { float XL,XU,FL[SLMHL],temp; int i,t,j; if(NBS==0) { A=0.5; GAMA=0.1; TOCDOHOC=A; } for(t=0;t<SLMHL;t++) FL[t]=FX[t]; XL=0; BUOC1: TOCDOHOC=A; BUOCLAP(); HAMMUCTIEU(); for(t=0;t<SLMHL;t++) F[t] = ECM[t]; if(F[t]>FL[t]) { XU=A; goto BUOC2; } //XL=A; for(t=0;t<SLMHL;t++) FL[t]=F[t]; XL=A; A=1.5*A; XU=A; goto BUOC1; BUOC2: if(FD>=(XU-FL)) goto BUOC3; A=XL+GAMA*(XU-XL); temp=TOCDOHOC; TOCDOHOC=A; BUOCLAP(); HAMMUCTIEU(); TOCDOHOC=temp; for(t=0;t<SLMHL;t++) F[t] = ECM[t]; for(t=0;t<SLMHL;t++) Luận án Tiến sĩ Kỹ thuật 2013 136 if(FL[t]>F[t]) { XU=A; for(j=0;j<SLMHL;j++) FL[j]=F[j]; goto BUOC2; } for(t=0;t<SLMHL;t++) if(F[t]>FL[t]) { for(j=0;j<SLMHL;j++) FL[j]=F[j]; XL=A; goto BUOC2; } BUOC3: for(t=0;t<SLMHL;t++) FX[t]=F[t]; NBS=NBS+1; TOCDOHOC=A; } /*----------------------------------------------------------------------- ---- Ten Thu tuc: TINHTOANBUOCHOC Mo ta: TINH TOAN TOC DO HOC SAU MOI BUOC LAP Cac dau vao: KHONG CO Gia tri tra ve: KHONG CO -----------------------------------------------------------------------*/ void TINHTOANBUOCHOC() { TOCDOHOC=TSDCBH/(SOBUOCLAP*0.001+MSDCBH); } /*----------------------------------------------------------------------- Ten Thu tuc: BUOCLAP Mo ta: DIEU CHINH CAC TRONG SO CUA MANG Cac dau vao: KHONG CO Gia tri tra ve: KHONG CO ------------------------------------------------------------------------ */ void BUOCLAP() { int i; i=0; //LUA CHON MAU HUAN LUYEN NGAU NHIEN: i = (int)(SLMHL*rnd), VOI 0<rnd<1 do { i = (int)(SLMHL*(float) rand() / RAND_MAX); }while(PATR[i]); DAPUNGDAURA(TAPHUANLUYEN[i]); DIEUCHINHTRONGSO(i); } /*----------------------------------------------------------------------- Ten Thu tuc: HUANLUYENCODINH Mo ta: HUAN LUYEN MANG DE TB-BINH PHUONG SAI SO DAU RA NHO HON EPSILON CHO TRUOC BUOC HOC LA MOT HANG SO. Cac dau vao: KHONG CO Gia tri tra ve: KHONG CO Luận án Tiến sĩ Kỹ thuật 2013 137 -----------------------------------------------------------------------*/ void HUANLUYENCODINH() { int t,l; printf("\nDANG HUAN LUYEN MANG VOI BUOC HOC CO DINH...\n"); START: if(RES==0) printf("\nKHOI DONG VA HUAN LUYEN LAI MANG!"); KHOITAOMANG(); //Luyen mang do { TOCDOHOC=0.2; BUOCLAP(); HAMMUCTIEU(); l = 1; for(t=0;t<SLMHL;t++) { PATR[t] = ECM[t] < EPSILON; l = l && (PATR[t]); } SOBUOCLAP++; RESET++; if(RESET>15000)break; if(SOBUOCLAP>BLTD) { HTHL=0; printf("\nQUA TRINH HUAN LUYEN MANG THAT BAI! \n"); printf("\nDE NGHI HUAN LUYEN LAI! \n"); break; } }while(!l);//while(!l && !kbhit()); if(RESET>15000) { RES=0; goto START; } if(SOBUOCLAP<BLTD) { printf("\n\nMANG DA DUOC HUAN LUYEN XONG SAU: "); printf("%ld",RESET); printf(" BUOC LAP!\n\n"); } } /*----------------------------------------------------------------------- - Ten Thu tuc: HUANLUYENGIAMDAN Mo ta: HUAN LUYEN MANG DE TB-BINH PHUONG SAI SO DAU RA NHO HON EPSILON CHO TRUOC BUOC HOC DUOC TINH THEO PHUONG PHAP GIAM DAN DON GIAN Cac dau vao: KHONG CO Gia tri tra ve: KHONG CO ------------------------------------------------------------------------- -*/ void HUANLUYENGIAMDAN() { int t,l; printf("\n\nDANG HUAN LUYEN MANG VOI BUOC HOC GIAM DAN...\n"); Luận án Tiến sĩ Kỹ thuật 2013 138 START: if(RES==0) printf("\n\nKHOI DONG VA HUAN LUYEN LAI MANG!"); KHOITAOMANG(); //Luyen mang do { TINHTOANBUOCHOC(); BUOCLAP(); HAMMUCTIEU(); l = 1; for(t=0;t<SLMHL;t++) { PATR[t] = ECM[t] < EPSILON; l = l && (PATR[t]); } SOBUOCLAP++; RESET++; if(RESET>3000)break; if(SOBUOCLAP>BLTD) { HTHL=0; printf("\nQUA TRINH HUAN LUYEN MANG THAT BAI! \n"); printf("\nDE NGHI HUAN LUYEN LAI! \n"); break; } }while(!l);//while(!l && !kbhit()); if(RESET>3000) } if(SOBUOCLAP<BLTD) { HTHL=1; printf("\n\nMANG DA DUOC HUAN LUYEN XONG SAU: "); printf("%ld",RESET); printf(" BUOC LAP!\n\n"); } } /*----------------------------------------------------------------------- - Ten Thu tuc: HUANLUYENVUOTKHE Mo ta: HUAN LUYEN MANG DE TB-BINH PHUONG SAI SO DAU RA NHO HON EPSILON CHO TRUOC BUOC HOC DUOC TINH THEO NGUYEN LY VUOT KHE Cac dau vao: KHONG CO Gia tri tra ve: KHONG CO ------------------------------------------------------------------------ */ void HUANLUYENVUOTKHE() { int t,l; printf("\n\nDANG HUAN LUYEN MANG THEO BUOC VUOT KHE...\n"); START: if(RES==0){ printf("\nKHOI DONG VA HUAN LUYEN LAI MANG!"); } KHOITAOMANG(); TOCDOHOCZERO(); TINHBUOCHOCVUOTKHE(); //Luyen mang Luận án Tiến sĩ Kỹ thuật 2013 139 do { TINHBUOCHOCVUOTKHE(); BUOCLAP(); HAMMUCTIEU(); l = 1; for(t=0;t<SLMHL;t++) { PATR[t] = ECM[t] < EPSILON; l = l && (PATR[t]); } SOBUOCLAP++; RESET++; // printf("lan lap thu %d\n",RESET); if(RESET>100)break; if(SOBUOCLAP>BLTD) { HTHL=0; printf("\nQUA TRINH HUAN LUYEN MANG THAT BAI! \n"); printf("\nDE NGHI HUAN LUYEN LAI! \n"); break; } }while(!l);//while(!l && !kbhit()); if(RESET>100) { RES=0; goto START; } if(SOBUOCLAP<BLTD) { HTHL=1; printf("\n\nMANG DA DUOC HUAN LUYEN XONG SAU: "); printf("%ld",RESET); printf(" BUOC LAP!\n\n"); } } /*----------------------------------------------------------------------- - Ten Thu tuc: DAPUNGDAURA Mo ta: TINH CAC DAU RA LOP AN, y, VA DAU RA LOP RA, z, TU DAU VAO LOPA VAO, x. Cac dau vao: VEC-TO DAU VAO x[i] Gia tri tra ve: KHONG CO ------------------------------------------------------------------------ */ void DAPUNGDAURA(int afer[]) { int i,j; float totin; for(i=0;i<SLNRLV;i++) x[i] = (float)afer[i]; for(j=0;j<SLNRLA;j++) { totin = 0; for(i=0;i<SLNRLV;i++) totin = totin + x[i]*MTTSLA[i][j]; Luận án Tiến sĩ Kỹ thuật 2013 140 y[j] = SIGMF(totin); } for(j=0;j<SLNRLR;j++) { totin = 0; for(i=0;i<SLNRLA;i++) totin = totin + y[i]*MTTSLR[i][j]; z[j] = SIGMF(totin); } } /*----------------------------------------------------------------------- Ten Ham: TB_BINHPHUONGSAISO Mo ta: TINH BINH PHUONG SAI SO DAU RA CUA MANG THEO VEC-TO DAU RA VA VEC-TO DICH Cac dau vao: 1. VEC-TO DAU RA MONG MUON DRMM[i], 2. VEC-TO DAU RA CU LOP RA z[i], 3. SO LUONG NO-RON CUA LAOP DAU RA, SLNRLR Gia tri tra ve: TRUNG BINH BINH PHUONG SAI SO DAU RA CUA LOP RA ------------------------------------------------------------------------ */ float TB_BINHPHUONGSAISO(int a[],float b[],int SIZE) { int i; float e=0; for(i=0;i<SIZE;i++) e = e + ((float)a[i] - b[i])*(a[i] - b[i]); e = 0.5 * e; return e; } /*----------------------------------------------------------------------- - Ten Thu tuc: SAISODAURA Mo ta: TINH SAI SO DAU RA CUA MANG THEO VEC-TO DAU RA VA VEC-TO DICH 1. VEC-TO DAU RA MONG MUON DRMM[i], 2. VEC-TO DAU RA CU LOP RA z[i], Cac dau vao: SO THU TU MAU Gia tri tra ve: KHONG CO ------------------------------------------------------------------------ */ void SAISODAURA(int i) { int j; for(j=0;j<SLNRLR;j++) SSLR[j] = 0; for(j=0;j<SLNRLR;j++) SSLR[j] = z[j] - (float)DRMM[i][j]; } /*----------------------------------------------------------------------- Ten Thu tuc: SAISOLOPAN Mo ta: TINH SAI SO DAU RA CUA LOP AN THEO SAI SO LOP RA VA DAO HAM CUA SIGMF Cac dau vao: KHONG CO Gia tri tra ve: KHONG CO -----------------------------------------------------------------------*/ Luận án Tiến sĩ Kỹ thuật 2013 141 void SAISOLOPAN() { int i,j; for(i=0;i<SLNRLA;i++) SSLA[i] = 0; for(i=0;i<SLNRLA;i++) for(j=0;j<SLNRLR;j++) SSLA[i] = SSLA[i] + MTTSLR[i][j]*z[j]*(1-z[j])*SSLR[j]; } /*------------------------------------------------------------------- Ten Thu tuc: DIEUCHINHTRONGSO Mo ta: CAP NHAT MA TRAN TRONG SO LOP AN VA LOP RA Cac dau vao: SO THU TU MAU Gia tri tra ve: KHONG CO ----------------------------------------------------------------------*/ void DIEUCHINHTRONGSO(int k) { int i,j; float temp; SAISODAURA(k); SAISOLOPAN(); for(i=0;i<SLNRLA;i++) { for(j=0;j<SLNRLR;j++) { temp = -TOCDOHOC*y[i]*z[j]*(1-z[j])*SSLR[j]; MTTSLR[i][j] = MTTSLR[i][j] + temp + QUANTINH*BTMTTSLR[i][j]; BTMTTSLR[i][j] = temp; } } for(i=0;i<SLNRLV;i++) { for(j=0;j<SLNRLA;j++) { temp = -TOCDOHOC*x[i]*y[j]*(1-y[j])*SSLA[j]; MTTSLA[i][j] = MTTSLA[i][j] + temp + QUANTINH*BTMTTSLA[i][j]; BTMTTSLA[i][j] = temp; } } } /*---------------------------------------------------------------------- Ten Thu tuc: HAMMUCTIEU Mo ta: TINH BINH PHUONG SAI SO DAU RA CUA MANG THEO VEC-TO DAU RA VA VEC-TO DICH Cac dau vao: KHONG CO Gia tri tra ve: KHONG CO ---------------------------------------------------------------------*/ void HAMMUCTIEU() { int i; Luận án Tiến sĩ Kỹ thuật 2013 142 for(i=0;i<SLMHL;i++) { DAPUNGDAURA(TAPHUANLUYEN[i]); ECM[i]=TB_BINHPHUONGSAISO(DRMM[i],z,SLNRLR); } } /*---------------------------------------------------------------------- Ten Thu tuc: KIEMTRAMANG Mo ta: NGUOI SU DUNG NHAP MA TRAN DAU VAO, TINH TOAN DAP UNG DAU RA CUA MANG Cac dau vao: KHONG CO Gia tri tra ve: KHONG CO ------------------------------------------------------------------------ */ void KIEMTRAMANG() { int i,j,t,ind; float temp; float tempz1[SLNRLR]; float tempz2[3]; ind=0; for(;;) { printf("\n\nXIN MOI DUA VEC-TO DAU VAO DE KIEM TRA MANG\n\n"); for(i=0;i<7;i++) { for(j=0;j<5;j++) scanf("%d",&MTDVKT[j*7+i]); printf("\n"); } printf("\n\nDAP UNG DAU RA CUA MANG:\n"); DAPUNGDAURA(MTDVKT); for(i=0;i<SLNRLR;i++) printf("\nNO-RON %d, Z = %f",i,z[i]); for(i=0;i<SLNRLR;i++) tempz1[i]=z[i]; printf("\n\nBA DAU RA CO DAP UNG CAO NHAT UNG VOI VEC-TO DAU VAO:\n"); for(t=0;t<3;t++) { temp=0; ind=0; for(i=0;i<SLNRLR;i++) if(temp<=tempz1[i]) { temp=tempz1[i]; ind=i; } tempz2[t]=temp; printf("\nDAU RA THU %d LA %3.0f%%",ind, tempz2[t]*100); tempz1[ind]=0; } temp=z[0]; ind=0; Luận án Tiến sĩ Kỹ thuật 2013 143 for(i=0;i<SLNRLR;i++) if(temp<=z[i]) { temp=z[i]; ind=i; } printf("\n\nKET LUAN CUA MANG NO-RON:\n"); printf("\nVEC-TO DAU VAO MANG LA MA CUA KY TU: %d",ind); } } /*---------------------------------------------------------------------- Ten Thu tuc: MATRANTRONGSOLOPAN Mo ta: IN MA TRAN TRONG SO LOP AN RA MAN HINH Cac dau vao: KHONG CO Gia tri tra ve: KHONG CO ------------------------------------------------------------------------ */ void MATRANTRONGSOLOPAN() { int i,j; printf("\n\nMA TRAN TRONG SO LOP AN MTTSLA[slnrlv][slnrla]:\n\n"); for(i=0;i<SLNRLV;i++) { for(j=0;j<SLNRLA;j++) { if(MTTSLA[i][j]>=0) printf("+%f ",MTTSLA[i][j]); else printf("%f ",MTTSLA[i][j]); } printf("\n"); } } /*---------------------------------------------------------------------- Ten Thu tuc: MATRANTRONGSOLOPRA Mo ta: IN MA TRAN TRONG SO LOP RA RA MAN HINH Cac dau vao: KHONG CO Gia tri tra ve: KHONG CO ---------------------------------------------------------------------*/ void MATRANTRONGSOLOPRA() { int i,j; printf("\n\nMA TRAN TRONG SO LOP RA MTTSLR[slnrla][slnrlr]:\n\n"); for(j=0;j<SLNRLR;j++) { for(i=0;i<SLNRLA;i++) { if(MTTSLR[i][j]>=0) printf("+%f ",MTTSLR[i][j]); else printf("%f ",MTTSLR[i][j]); } printf("\n"); } } Luận án Tiến sĩ Kỹ thuật 2013 144 /******************************* HAM CHINH ***********************/ void main(int argc,char *argv[]) { int read; char c; KHOITAOMANG(); printf("*******************************************\n\n"); printf("* CHUONG TRINH HUAN LUYEN MANG NO-RON *\n\n"); printf("* BUOC HOC TINH THEO NGUYEN LY VUOT KHE *\n\n"); printf("*******************************************\n\n"); /* printf("/Vao\\ /~~~~Lop an~~~~\\ /~~~~~Lop ra~~~~~\\\n"); printf(" -- ------- ---- --------- ---- \n"); printf("| | | | | |Y | | | | Z\n"); printf("|X |->| W11 |->| f1 |->| W21 |->| f2 |-->\n"); printf("| | | (35x5)| | | | (5x10) | | |\n"); printf("| | | | | | | | | |\n"); printf(" -- ------- ---- --------- ---- \n"); printf("\\35/ \\__Y=f1(W11.X)__/ \\__Z=f1(W11.X)___/ \n\n"); printf(" f=sigm(net) \n\n"); printf("\nSU DUNG MANG: TRUOC KHI HOC, t, SAU KHI HOC, s.\n"); SDM = getchar(); if(SDM=='t') KIEMTRAMANG();// SU DUNG MANG TRUOC KHI HUAN LUYEN else if(SDM=='s') { printf("\n\nLUA CHON LOAI BUOC HOC\n"); printf("\nCO DINH: c, GIAM DAN: g, NGUYEN LY VUOT KHE: v\n\n"); c = getchar(); } LCBH = getchar(); switch(LCBH) { case 'c': HUANLUYENCODINH(); break; case 'g': HUANLUYENGIAMDAN(); break; case 'v': HUANLUYENVUOTKHE(); break; } */ HUANLUYENVUOTKHE(); if(HTHL==1)//NEU MANG DA DUOC HUAN LUYEN XONG { MATRANTRONGSOLOPAN(); MATRANTRONGSOLOPRA(); // KIEMTRAMANG(); } }