MỞ ĐẦU Trong những năm gần đây nhu cầu sử dụng dịch vụ của mạng viễn thông càng ngày càng tăng mạnh cùng với sự phát triển và tăng trƣởng của internet. Nhƣng tiện ích, chất lƣợng và khả năng của các mạng viễn thông hiện là có giới hạn, do đó yêu cầu đặt ra là phải thiết kế đƣợc những mạng viễn thông tối ƣu. Sự đa dạng của bài toán kết nối tối ƣu đã nảy sinh không chỉ trong thiết kế, mà còn trong việc quản lý chất lƣợng dịch vụ của mạng viễn thông. Có nhiều vấn đề mới đƣợc yêu cầu, trong nhiều trƣờng hợp, các ứng dụng của các kỹ thuật tối ƣu xuất hiện cho việc giải quyết chúng.
Một trong những vấn đề đó là bài toán kết nối các thiết bị đầu cuối vào các bộ tập trung (terminal assignment – TA). Bài toán TA là một bài toán NP-đầy đủ, nó đã đƣợc rất nhiều các tác giả trên thế giới quan tâm tìm hiểu và đề xuất các cách tiếp cận khác nhau. Trong luận văn này chúng tôi trình bày cách tiếp cận lai ghép giữa giải thuật di truyền và mạng nơ ron Hopfield để tối ƣu hóa bài toán TA. Nội dung chính của luận văn bao gồm 4 chƣơng.
Chƣơng 1: Tổng quan về mạng nơ ron. Chƣơng này trình bày tổng quan về cơ sở của mạng nơ ron nhân tạo bao gồm: giới thiệu về nơ ron sinh học, mô hình mạng nơ ron nhân tạo, phạm vi ứng dụng của mạng nơ ron, ƣu nhƣợc điểm của mạng nơ ron và trình bày về mạng nơ ron Hopfield, phƣơng pháp ánh xạ một bài toán lên mạng nơ ron. Chƣơng 2: Giải thuật di truyền và tính toán tiến hóa. Chƣơng này trình bày về giải thuật di truyền, tính toán tiến hóa, ƣu nhƣợc điểm của giải thuật di truyền.
Ứng dụng của giải thuật di truyền đối với bài toán tối ƣu tổ hợp. Chƣơng 3: Bài toán kết nối các thiết bị đầu cuối vào các bộ tập trung. Trình bày các cách tiếp cận trƣớc đây cho bài toán TA. Cách tiếp cận của chúng tôi cho bài toán này, và đánh giá những ƣu điểm của cách tiếp cận của chúng tôi so với các cách tiếp cận trƣớc đây.
8 z Chƣơng 4: Kết quả thực nghiệm và đánh giá. Chƣơng này trình bày kết quả đạt đƣợc qua thực nghiệm, và so sánh với các phƣơng pháp khác. Tổng quan về mạng nơ ron 1. Giới thiệu về mạng nơ ron 1.
Lịch sử phát triển của mạng nơ ron Quá trình nghiên cứu và phát triển mạng nơ-ron nhân tạo có thể chia thành bốn giai đoạn nhƣ sau: Giai đoạn 1: Có thể tính từ nghiên cứu của William (1890) về tâm lý học với sự liên kết các nơ ron thần kinh. Năm 1940, McCulloch và Pitts đã cho biết: nơ ron có thể đƣợc mô hình hóa nhƣ thiết bị ngƣỡng (giới hạn) để thực hiện các phép tính logic và mô hình mạng nơ ron của McCulloch-Pitts cùng với giải thuật huấn luyện mạng của Hebb ra đời năm 1943. Giai đoạn 2: Vào khoảng gần những năm 1960, một số mô hình nơ ron hoàn thiện hơn đã đƣợc đƣa ra nhƣ: mô hình Perceptron của Rosenblatt (1958), Adaline của Widrow (1962). Trong đó mô hình Perceptron rất đƣợc quan tâm vì nguyên lý đơn giản, nhƣng nó cũng có hạn chế vì nhƣ Marvin Minsky và Seymour Papert của MIT (Massachurehs Insritute of Technology) đã chứng minh nó không dùng đƣợc cho các hàm logic phức (1969).
Còn Adaline là mô hình tuyến tính, tự chỉnh, đƣợc dùng rộng rãi trong điều khiển thích nghi, tách nhiễu và vẫn phát triển cho đến nay. Giai đoạn 3: Có thể tính vào khoảng đầu thập niên 80. Những đóng góp lớn cho mạng nơ ron trong giai đoạn này phải kể đến Grossberg, Kohonen, Rumelhart và Hopfield. Trong đó đóng góp của Hopfield gồm hai mạng phản hồi: mạng rời rạc năm 1982 và mạng liên tục năm 1984.
Đặc biệt, ông đã dự kiến nhiều khả năng tính toán lớn của mạng nơ ron mà một nơ ron không có khả năng đó. Cảm nhận của Hopfield đã đƣợc Rumelhart, Hinton và Williams đề xuất thuật toán sai số truyền ngƣợc nổi tiếng để huấn luyện mạng nơ ron nhiều lớp nhằm giải bài toán mà mạng khác không thể thực hiện đƣợc. Nhiều ứng dụng mạnh mẽ của mạng nơ ron ra đời cùng với các mạng theo kiểu máy Boltzmann và mạng Neocognition của Fukushima. 10 z Giai đoạn 4: Tính từ năm 1987 đến nay, hàng năm thế giới đều mở hội nghị toàn cầu chuyên ngành nơ ron (IJCNN) (International Joint Conference on Neural Networks).
Rất nhiều công trình đƣợc nghiên cứu để ứng dụng mạng nơ ron vào các lĩnh vực, ví dụ nhƣ: kỹ thuật tính toán, tối ƣu, sinh học, y học, thống kê, giao thông, hóa học… Cho đến nay, mạng nơ ron đã tìm đƣợc và khẳng định đƣợc vị trí của mình trong rất nhiều ứng dụng khác nhau. Mô hình mạng nơ ron nhân tạo 1. Nơ ron sinh học Hệ thần kinh ở ngƣời có khoảng 1010 tế bào thần kinh đƣợc gọi là các nơ ron. Mỗi nơ ron gồm có ba phần: Thân nơ ron với nhân ở bên trong (soma), một đầu thần kinh ra (axon) và một hệ thống hình cây thần kinh (dendrite).
Có nhiều loại nơ ron khác nhau về kích thƣớc và khả năng thu phát tín hiệu. Tuy nhiên, chúng có cấu trúc và nguyên lý hoạt động chung.1) là một hình ảnh đơn giản hóa của một loại nơ ron. Trong thực tế có rất nhiều dây thần kinh vào và chúng bao phủ một Khớp nối dây thần kinh (đầu vào) Trục Nhân Đầu ra Tế bào Hình 1. Mô hình nơ ron sinh học diện tích rất lớn (0.25 mm2) để nhận các tín hiệu từ các nơ ron khác.
Đầu thần kinh ra đƣợc rẽ nhánh nhằm chuyển giao tín hiệu từ thân nơ ron tới nơ ron khác. Các nhánh của đầu thần kinh đƣợc nối với các khớp thần kinh (synapse). Các khớp thần kinh này đƣợc nối với thần kinh vào của các nơ ron khác. Thêm vào đó, các nơ ron có thể sửa đổi tín hiệu tại các khớp, trong nơ ron nhân tạo đƣợc gọi là trọng số.
11 z Hoạt động của nơ ron sinh học có thể mô tả tóm tắt nhƣ sau: Mỗi nơ ron nhận tín hiệu vào từ các tế bào thần kinh khác. Chúng tích hợp các tín hiệu vào, khi tổng tín hiệu vƣợt quá một ngƣỡng nào đó chúng tạo tín hiệu ra và gửi tín hiệu này tới các nơ ron khác thông qua dây thần kinh. Các nơ ron liên kết với nhau thành mạng. Mức độ bền vững của các liên kết này xác định một hệ số gọi là trọng số liên kết.
Nơ ron nhân tạo a. Trọng số và tổng tín hiệu đầu vào: Mô phỏng nơ ron sinh học để tạo ra các nơ ron nhân tạo. Mỗi nơ ron có rất nhiều dây thần kinh vào nghĩa là mỗi nơ ron có thể tiếp nhận đồng thời nhiều tín hiệu. Giả sử tại nơ ron i có N tín hiệu vào, mỗi tín hiệu vào Sj đƣợc gán một trọng số Wij tƣơng ứng.
Ta có thể ƣớc lƣợng tổng tín hiệu đi vào nơ ron neti theo một số dạng sau: - Dạng tuyến tính: N net i wij s j (1.1) j 1 - Dạng toàn phƣơng: N net i wij s 2j (1.2) j 1 - Dạng mặt cầu: 2 s w N net i 2 j ij (1.3) j 1 Trong đó: và w ij (j=1,.,N) lần lƣợt là bán kính và tâm mặt cầu. Hàm kích hoạt Hàm biến đổi tín hiệu đầu vào net cho tín hiệu đầu ra out đƣợc gọi là hàm kích hoạt. Hàm này có đặc điểm là không âm và bị chặn. Có nhiều dạng hàm kích hoạt, ngƣời ta thƣờng sử dụng một hàm kích hoạt chung cho toàn mạng.
Một số hàm kích hoạt thƣờng đƣợc sử dụng: 12 z - Hàm McCuloch-Pitts: 1 nÕu net out f net (1.4) 0 nÕu net - Hàm McCuloch-Pitts trễ: 1 nÕu net UTP out f net 0 nÕu net LTP (1.5) f net nÕu kh¸c ở đây UTP > LTP. Trong đó: UTP là ngƣỡng trên (Upper Trip Point) LTP là ngƣỡng dƣới (Lower Trip Point) - Hàm Sigmoid: out f net 1 net (1.6) 1 e Trong đó 0 là hằng số xác định độ nghiêng của hàm c. Nút bias: Là một nút thêm vào nhằm tăng khả năng thích nghi của mạng nơ ron trong quá trình học. Trong các mạng nơ ron có sử dụng bias, mỗi nơ ron có thể có một trọng số tƣơng ứng với bias.
Trọng số này luôn có giá trị là 1. Mô hình của một nút xử lý (nút thứ i): Vi Wi1 Vj Wij Vi Ui= Vi=fi(Ui) WiN VN Hình 1. Mô hình một nơ ron N U i Wij Vj θ i (1.8) 13 z Trong đó: U i là tín hiệu vào tại nơ ron i Vi là tín hiệu ra tại nơ ron i. Wij là trọng số liên kết từ nơ ron j đến nơ ron i.
i là ngƣỡng (đầu vào ngoài) kích hoạt nơ ron i. f i là hàm kích hoạt của nơ ron i. Mạng nơ ron Mạng nơ ron nhân tạo (Artificial Neural Network) là một cấu trúc mạng đƣợc hình thành nên bởi một số lƣợng các nơ ron nhân tạo liên kết với nhau. Mỗi nơ ron có các đặc tính đầu vào, đầu ra và thực hiện một chức năng tính toán cục bộ.
Với việc giả lập các hệ thống sinh học, các cấu trúc tính toán, mạng nơ ron có thể giải quyết đƣợc các lớp bài toán nhất định, nhƣ: bài toán xếp loại, bài toán lập lịch, bài toán tìm kiếm, bài toán nhận dạng mẫu…Các bài toán phức tạp cao, không xác định. Tuy nhiên, sự liên kết giữa một bài toán bất kỳ trong thực tế với một giải pháp mạng nơ ron lại là một việc không dễ dàng. Xét một cách tổng quát, mạng nơ ron là một cấu trúc xử lý song song thông tin phân tán mang các đặc tính nổi bật sau: - Là mô hình toán học dựa trên bản chất của nơ ron. - Bao gồm một số lƣợng rất lớn các nơ ron liên kết với nhau.
- Mạng nơ ron có khả năng học, khái quát hóa tập dữ liệu học thông qua việc gán và hiệu chỉnh các trọng số liên kết. - Tổ chức theo kiểu tập hợp mang lại cho mạng nơ ron khả năng tính toán rất lớn, trong đó không có nơ ron nào mang thông tin riêng biệt.6 là một số mô hình mạng thông dụng. Mạng truyền thẳng: - Mạng truyền thẳng một lớp: Mô hình mạng nơ ron truyền thẳng một lớp là mô hình liên kết cơ bản và đơn giản nhất.