Tiểu luận:PHƯƠNG PHÁP BƯỚC ĐI NGẪU NHIÊN TRONG GIẢI QUYẾT CÁC BÀI TOÁN TIN HỌC

Chia sẻ: Vang Thi | Ngày: | Loại File: PDF | Số trang:17

Thêm vào BST

Báo xấu

105
lượt xem 9
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Ngày nay, sức mạnh máy tính đã có những bước phát triển vượt trội giúp con người đạt được nhiều thành tựu trong các lĩnh vực của cuộc sống. Sức mạnh tính toán của máy tính được phát triển dựa trên những thành tựu của khoa học – kỹ thuật để ngày càng thu nhỏ hơn và tích hợp nhiều hơn những bóng bán dẫn trên cùng một bộ vi xử lý để tăng khả năng xử lý.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tiểu luận:PHƯƠNG PHÁP BƯỚC ĐI NGẪU NHIÊN TRONG GIẢI QUYẾT CÁC BÀI TOÁN TIN HỌC

\ ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN ----------------------------------------------------- PHƯƠNG PHÁP NGHIÊN CỨU KHOA HỌC TRONG TIN HỌC PHƯƠNG PHÁP BƯỚC ĐI NGẪU NHIÊN TRONG GIẢI QUYẾT CÁC BÀI TOÁN TIN HỌC Trang 1
\ Mục lục trang 1. Đặt vấn đề ............................................................................................................... 2 2. Các thuật toán dựa trên phương pháp “bước đi ngẫu nhiên” ............................. 3 2.1 Thuật giải áp dụng trên đồ thị ............................................................................ 3 2.1.1 Thuật giải gom cụm Markov Cluster.............................................................. 3 2.1.2 Thuật giải đánh giá liên kết HITS .................................................................. 7 2.2 Thuật giải tối ưu hóa mô phỏng hành vi đàn kiến ............................................. 10 3. Áp dụng thực tiễn từ các thuật giải ..................................................................... 12 4. Kết luận ................................................................................................................ 14 Tài liệu tham khảo.............................................................................................. 15 Phụ lục..................................................................................................................... 16 Chương trình minh họa................................................................................................ 16 Trang 2
\ 1. Đặt vấn đề Ngày nay, sức mạnh máy tính đã có những bước phát triển vượt trội giúp con người đạt được nhiều thành tựu trong các lĩnh vực của cuộc sống. Sức mạnh tính toán của máy tính được phát triển dựa trên những thành tựu của khoa học – kỹ thuật để ngày càng thu nhỏ hơn và tích hợp nhiều hơn những bóng bán dẫn trên cùng một bộ vi xử lý để tăng khả năng xử lý. Nhiều năm qua, tốc độ phát triển tính toán của máy tính đều tuân theo định luật Moore với nội dung là sau mỗi 2 năm tốc độ tính toán máy tính lại tăng gấp đôi. Tuy tốc độ tính toán đã những bước phát triển vượt bậc nhưng những công việc của máy tính thực hiện về tác vụ chính chỉ ràng buộc trong một số thao tác cơ bản như lưu trữ, tìm kiếm và cập nhật thông tin. Và để giải quyết một vấn đề nào đó trong cuộc sống, máy tính vẫn phải dựa trên các phương pháp giải quyết của con người, để nhằm được cung cấp cho máy tính những phương thức và quá trình giải quyết vấn đề đó. Quá trình giải quyết các vấn đề trong cuộc sống của con người ít bị thay đổi theo thời gian. Nó là một sự mở rộng và hoàn thiện các phương pháp nhưng tất cả đều tựu chung theo một phương pháp tổng quan nhất: - Quan sát và tập hợp các sự kiện ở trong quá khứ và hiện tại. - Bổ sung, kết hợp và biến đổi những sự kiện trước đó. - Kiểm tra và đánh giá những kết quả đạt được. - Ghi nhận, xử lý các kết quả (kết quả đúng và sai) và đưa ra hướng giải quyết mới. - Quay lại bước quan sát – tập hợp và lặp lại quá trình giải quyết như vậy. Quá trình như vậy được lặp lại cho đến khi đạt được kết quả mong muốn. Kết quả mong muốn ở đây có thể là một kết quả không cần đúng hoàn toàn, chỉ cần kết quả đúng một phần trong một giới hạn cho phép. Ví dụ các lý thuyết trong vật lý và kinh tế, nó được dẫn giải và giải thích đúng một số hiện tượng nhưng các lý thuyết đó vẫn chưa thể được chứng minh đúng hoàn toàn như thuyết tương đối, thuyết thị trường hiệu quả… Riêng đối tin học, các giải pháp đưa ra cho một vấn đề đôi khi không thể giải quyết để thỏa mãn cùng lúc tất cả các yêu cầu của vấn đề. Đôi khi, phải sử dụng các phương pháp gián tiếp với kết quả trả về được chấp nhận theo các điều kiện nào đó. Ví dụ: tìm kiếm trên Google không dựa trên ngữ nghĩa mà dựa trên tìm kiếm theo từ khóa và đánh giá nội dung theo các link các trang web bên trong nhưng vẫn cung cấp được các kết quả tìm kiếm tương đối chính xác với nội dung tìm kiếm của người dùng. Trang 3
\ Như vậy, việc kết hợp sức mạnh của máy tính về tính toán, lưu trữ với phương pháp giải quyết các vấn đề một cách tổng quan của con người có thể được áp dụng cho nhiều lĩnh vực khác nhau trong cuộc sống với hiệu quả cao hơn, giải quyết được nhiều vấn đề hơn. Hiện nay, khi các giải pháp tin học đã được áp dụng rộng rãi trong tất cả các ngành thì đã nổi bật lên ý tưởng về phương pháp “bước đi ngẫu nhiên” (tên tiếng Anh là Random Walk) để giải quyết các vấn đề trong cuộc sống. Phương pháp, ý tưởng của “bước đi ngẫu nhiên” là một nền tảng chung nhất, tùy vào các yêu cầu bài toán sẽ có những biến đổi để tạo ra những giải pháp mới, những thuật giải mới. Phương pháp “bước đi ngẫu nhiên” mang tính chất gần gũi với cách giải quyết của con người đồng thời tận dụng được sức mạnh của máy tính để giải quyết hiệu quả các vấn đề được đặt ra trong cuộc sống. Ví dụ: thuật toán đánh giá nội dung trang Web của Google với thuật giải đàn kiến trong việc tối ưu, tuy hoàn toàn khác nhau về phương pháp thực hiện cũng như thuộc 2 bài toán khác nhau nhưng về cơ bản cả hai thuật giải trên đều xuất phát từ khái niệm “bước đi ngẫu nhiên” để phát triển thành hai thuật giải hiệu quả để giải quyết các yêu cầu của mỗi bài toán. 2. Các thuật toán dựa trên phương pháp “bước đi ngẫu nhiên” Phương pháp “bước đi ngẫu nhiên” là một phương pháp tổng quan. Tùy vào các yêu cầu bài toán mà phương pháp “bước đi ngẫu nhiên” có những sự thay đổi để hình thành thuật giải mới phù hợp với nhu cầu. Phương pháp “bước đi ngẫu nhiên” là một phương pháp với nền tảng đơn giản. Đó là lựa chọn ngẫu nhiên các giải pháp trong tập giải pháp với những ràng buộc giữa những giải pháp. Việc lựa chọn này tiếp tục với phương pháp lưu vết hoặc kết quả lặp lại giữa những giải pháp hoặc tăng cường – làm yếu đi các liên kết để làm xuất hiện những kết quả mà các phương pháp khác khó tiếp cận. Dưới đây là một số thuật toán áp dụng phương pháp “bước đi ngẫu nhiên” để giải quyết bài toán cụ thể: 2.1 Các thuật giải áp dụng trên đồ thị. Đồ thị là một tập hợp các đỉnh và các cạnh nối các đỉnh với nhau. Mô hình đồ thị là một trong những mô hình biểu diễn rất tốt các đặc điểm, mối quan hệ giữa các sự vật, thực thể khác nhau. Một số mô hình đồ thị tiêu biểu như mạng xã hội, mạng ngữ nghĩa, mạng đặc điểm nhận dạng khuôn mặt, protein… Dưới đây một số thuật giải trên đồ thị xuất phát từ phương pháp “bước đi ngẫu nhiên” để giải quyết một số bài toán nổi bật: Trang 4
\ 2.1.1 Thuật giải gom cụm: Markov Cluster Algorithm (MCL) [1] Bài toán gom cụm dữ liệu là một bài toán thuộc lớp phân lớp không giám sát. Trong đó, yêu cầu của bài toán là từ tập dữ liệu lớn sẽ được gom cụm các tài liệu trong tập thành các nhóm tài liệu dựa trên chỉ số có thể so sánh với nhau giữa các tài liệu(độ đồng dạng, độ khác biệt, khoảng cách Euclid…). Các thuật toán kinh điển và được sử dụng phổ biến khi gom cụm như thuật giải K-Mean, EM đã đạt nhiều kết quả khả quan… nhưng phần lớn các thuật toán đều không có sự ổn định khi xuất kết quả, đồng thời hiệu quả của thuật toán không phụ thuộc hoàn toàn vào số liệu mà phụ thuộc vào thiết kế ban đầu để chạy thuật toán như phải xác định số lượng nhóm cho trước, thiết kế quy tắc chọn phần tử trung tâm của nhóm… mà từ đó có những ảnh hưởng rõ rệt đến kết quả của bài toán. Từ yêu cầu bài toán gom cụm có thể mô hình hóa tập dữ liệu theo mô hình đồ thị như sau: mỗi đỉnh của đồ thị là một tài liệu và cạnh nối giữa các tài liệu thể hiện một chỉ số so sánh (ví dụ như độ đồng dạng của tài liệu). Lưu ý: với những cặp tài liệu độ đồng dạng thấp thì có thể bỏ qua sự kết nối thông qua cạnh giữa 2 tài liệu đó. Ví dụ: cho 7 tài liệu như hình 1 minh họa. Trong đó, nếu giữa 2 cặp tài liệu bất kỳ được xem là tương đối giống nhau thì tồn tại một cạnh nối 2 tài liệu đó. Hình 1: minh họa mô hình đồ thị Ý tưởng của phương pháp “bước đi ngẫu nhiên” được sử dụng ở đây là nếu chúng ta bắt đầu xuất phát tại một đỉnh bất kỳ của đồ thị và thực hiện “bước đi ngẫu nhiên” - chọn ngẫu nhiên tới một đỉnh khác thông qua cạnh liên kết giữa chúng thì dường như chúng ta đi qua chủ yếu các cạnh giữa các đỉnh cùng thuộc một nhóm nhiều hơn là đi qua các cạnh nối giữa các nhóm với nhau. Từ đặc điểm này có thể tiến hành gom cụm dữ liệu với độ chính xác cao. Ví dụ từ hình 1: cạnh nối đỉnh 2 và đỉnh 5, có mật độ di chuyển qua lại ít hơn các cạnh khác, do nó là cạnh nối liền 2 nhóm đỉnh. Việc tính toán gom cụm dữ liệu trên phương pháp “bước đi ngẫu nhiên” sẽ được tính toán dựa trên nền tảng lý thuyết toán học xích Markov (Markov Chain). Trong phạm vi bài luận này, xích Markov chỉ được giới thiệu một cách tổng quan nhất. Trang 5
\ Xích Markov là một dãy các trạng thái X1, X2, X3, … được xác định bởi trạng thái hiện thời không phụ thuộc vào trạng thái ở quá khứ và tương lai. Trong đó, các trạng thái X1, X2, X3… trong phạm vi thuật giải gom cụm được xem là một ma trận xác suất (trong đó, tổng các thành phần trên mỗi cột là 1 và giá trị mỗi phần tử trong ma trận có giá trị từ 0 đến 1). Từ hình 1 nhận thấy, từ đỉnh 1 có xác suất ngẫu nhiên để đi tới đến các đỉnh 2, 3, 4 là 33% (0.33) và từ đỉnh 1 đến đỉnh các còn lại là 0%. Từ đây sẽ hình thành được một ma trận xác suất với trên mỗi cột là xác suất từ đỉnh đó tới các đỉnh khác. Hình 2: minh họa ma trận xác suất Các bước tổng quan gom cụm dữ liệu dựa trên ý tưởng “bước đi ngẫu nhiên” - Bước 1: Xác định mối quan hệ giữa các tài liệu và mô hình hóa bài toán thành đồ thị. Trong đó, nếu 2 tài liệu có quan hệ thì giá trị biểu diễn trên ma trận của đồ thị là 1 ngược lại là 0. - Bước 2: Chuyển giá trị trên đường chéo chính của ma trận thành 1. - Bước 3: Chuẩn hóa ma trận trên thành ma trận xác suất. Trong đó, giá trị phần tử sau khi chuẩn hóa có giá trị từ 0 đến 1 và tổng giá trị trên mỗi cột là 1. - Bước 4: Tự nhân ma trận với chính nó để hình thành một ma trận mới. - Bước 5: Tiến hành thực hiện làm mạnh các liên kết được xem là mạnh (có thể trong cùng 1 nhóm) và làm yếu đi các liên kết được xem là yếu (các cạnh kết nối các nhóm với nhau). Gọi A[i, j] là giá trị phần tử ma trận với n phần tử thì công thức làm mạnh và yếu các liên kết được tính như sau: [, ] [, ]= ∑ [ , ] Trang 6
\ - Bước 6: Tiến hành chuẩn hóa là thành ma trận xác suất với tổng giá trị trên cột là 1 và giá trị mỗi phần tử có giá trị từ 0 đến 1. - Bước 7: Sau khi chuẩn hóa nếu ma trận hội tụ, đạt được trạng thái cân bằng (giá trị bằng giá trị sau khi chuẩn hóa ma trận sau bước 3) và trạng thái trên mỗi dòng có các phần tử khác 0 thì cùng giá trị với nhau. - Bước 8: nếu đã xác định được ma trận hội tụ tiến hành phân tích kết quả thành các nhóm dữ liệu. Mỗi dòng trên ma trận là một nhóm dữ liệu với trong đó các tài liệu mang giá trị khác 0. Lưu ý: một tài liệu có thể thuộc nhiều nhóm. Từ hình 2, trải qua 1 vòng lặp (nhân ma trận – chuẩn hóa), ma trận có trạng thái: 0.25 0.2 0.25 0.25 0.01 0 0 0.25 0.32 0.25 0.25 0.06 0.02 0.02 ⎛ ⎞ 0.25 0.2 0.25 0.25 0.01 0 0 ⎜ ⎟ ⎜0.25 0.2 0.25 0.25 0.01 0 0 ⎟ ⎜0.01 0.05 0.01 0.01 0.38 0.32 0.32⎟ 0 0.01 0 0 0.26 0.32 0.32 ⎝ 0 0.01 0 0 0.26 0.32 0.32⎠ Trải qua 4 vòng lặp, ma trận có trạng thái bên dưới. Tuy chưa hội tụ nhưng quá trình xử lý Markov Cluster đã làm gia tăng sức mạnh các cạnh liên kết trong nhóm và triệt tiêu dần các cạnh nối giữa 2 nhóm. 0.17 0.17 0.17 0.17 0 0 0 0.51 0.51 0.51 0.51 0 0 0 ⎛ ⎞ 0.17 0.17 0.17 0.17 0 0 0 ⎜ ⎟ ⎜0.17 0.17 0.17 0.17 0 0 0 ⎟ ⎜ 0 0 0 0 0.62 0.62 0.62⎟ 0 0 0 0 0.19 0.19 0.19 ⎝ 0 0 0 0 0.19 0.19 0.19⎠ Sau 8 vòng lặp, ma trận đạt trạng thái hội tụ. Từ đây những dòng ma trận có giá trị khác 0 sẽ hình thành nên các nhóm dữ liệu. Như hình bên dưới, tồn tại 2 dòng ma trận (dòng 2 và dòng 5) tạo thành nhóm 1 gồm các đỉnh (1, 2, 3, 4) và nhóm 2 gồm các đỉnh (5, 6, 7). 0 0 0 0 0 0 0 1 1 1 1 0 0 0 ⎛ ⎞ 0 0 0 0 0 0 0 ⎜ ⎟ ⎜0 0 0 0 0 0 0⎟ ⎜0 0 0 0 1 1 1⎟ 0 0 0 0 0 0 0 ⎝0 0 0 0 0 0 0⎠ Trang 7
\ 2.1.2 Thuật giải đánh giá các liên kết: Hyperlink Induce Topic Search (HITS) [2] Bài toán đánh giá dựa trên các liên kết được áp dụng rộng rãi trong nhiều lĩnh vực như kinh tế, phân tích dữ liệu nhưng nổi bật nhất đó là phân tích liên kết giữa các trang Web trên mạng Internet, hỗ trợ cho việc tìm kiếm thông tin trên mạng Internet. Trong đó, thuật giải đánh giá các liên kết Hyperlink Induce Topic Search (HITS) là một trong những thuật giải nổi bật trong việc đánh giá xếp hạng nội dung các trang Web dựa trên sự liên kết giữa các trang Web. Thuật giải HITS phát triển bởi giáo sư Kleinberg ở đại học Cornell và được công bố vào năm 1998. Nếu xem các trang Web là một đỉnh và các link liên kết giữa các trang Web là cạnh nối các đỉnh với nhau thì mô hình trang Web trên mạng Internet có thể được xem như là một mô hình đồ thị khổng lồ. Và để đánh giá nội dung 1 tập các trang Web (tương ứng với một câu lệnh tìm kiếm) có thể dựa trên sự phân tích mối liên kết giữa các trang Web với nhau. Trong đó, thuật giải HITS đánh giá các trang Web qua 2 điểm: Hub (Hub score) và Authority (Authority score). Minh họa dễ hiểu về Hub và Authority dưới thể hiện bên dưới. Cho một tập trang Web được rút trích từ các từ khóa sau: Top automobile makers. Hình 3: minh họa điểm Hub và điểm Authority Theo thuật giải HITS thì một trang Web có một điểm Hub cao khi trang Web đó chứa nhiều link liên kết tới các trang Web có điểm Authority cao. Ngược lại, một trang Web có điểm Authority cao là một trang Web được liên kết (trỏ tới) từ nhiều trang Web có Trang 8
\ điểm Hub cao. Tùy vào mục đích tìm kiếm mà căn cứ vào điểm Hub hoặc điểm Authority để xác định nội dung trang Web, như dưới ví dụ mô tả, tính chất mà điểm Hub và điểm Authority đóng góp cho quá trình đánh giá nội dung trang Web. Ví dụ đơn giản hơn: như hình minh họa ở trên khi chúng ta cần mua một chiếc xe. Chúng ta cần tham khảo trước hết từ những người bạn mà đã sử dụng qua nhiều loại xe. Đồng thời, các loại xe của những người bạn đấy đã sử dụng phải là những loại xe tốt để chúng ta có cái nhìn toàn diện tương ứng với chất lượng xe mà chúng ta cần tìm. Từ đó, một người bạn thỏa các tiêu chí như sử dụng nhiều loại xe và chất lượng các dòng xe họ dùng thuộc dạng tốt thì họ chính là những người bạn đáng cho chúng ta tham khảo khi mua xe. Và quá trình đánh giá như vậy sẽ được tương tư cho điểm Hub – điểm Hub dành cho những người ta cần tham khảo mua xe. Còn điểm Authority là điểm dành cho các loại xe mà được nhiều người dùng, đồng thời những người dùng này cũng đã dùng nhiều loại xe tốt khác (để có thể so sánh chất lượng mua xe với nhau). Vậy cuối cùng khi mua xe, chúng ta cần tham khảo từ những người bạn có điểm Hub cao và các hãng xe được tìm hiểu phải có điểm Authority cao để xác định được loại xe tốt nhất để mua. Như vậy, cả hai loại điểm Hub và điểm Authority đều hỗ trợ cho việc tìm kiếm thông tin nhưng tùy vào mục đích mà xác định ưu tiên một trong hai loại điểm Hub hoặc Authority và kết hợp chúng lại với nhau. Thuật giải HITS cũng dựa trên phương pháp “bước đi ngẫu nhiên” gần tương tự với thuật giải gom cụm Markov Cluster, nhưng có một chút khác biệt so với Markov Cluster. Vì mục đích của bài toán HITS là đánh giá trang Web, đồng thời mô hình đồ thị ở đây là một mô hình đồ thị có hướng nên thuật giải HITS có những bước tính toán khác với Markov Cluster. “Bước đi ngẫu nhiên” được thực hiện trong thuật giải HITS như sau: chọn một đỉnh bất kỳ đồ thị và thực hiện lựa chọn ngẫu nhiên đi tới các đỉnh kết nối với nhau trên cạnh có hướng của đồ thị. Mỗi lần thực hiện đi ngẫu nhiên, sẽ cập nhật thông tin Hub và Authority cho mỗi trang Web. “Bước đi ngẫu nhiên” trên thuật giải HITS cũng được tính toán trên xích Markov nhưng thay vì làm mạnh các liên kết giữa các cạnh của các đỉnh trong một nhóm và làm yếu đi cạnh nối giữa các nhóm với nhau thì xích Markov được dùng trong trường hợp thuật giải HITS là đánh giá theo điểm Hub và điểm Authority dựa trên số lượng liên kết có hướng giữa các trang Web với nhau. Các bước tính toán của thuật giải HITS: - Bước 1: Biểu diễn đồ thị bằng một ma trận kề. Gọi ma trận đó là A - Bước 2: Nhân ma trận đó với ma trận chuyển vị của chính nó. A = A.AT Trang 9
\ - Bước 3: Xây dựng một vector xác suất h (hub vector) với số lượng phần tử bằng số lượng các trang Web cần đánh giá. Trong đó, các phần tử trên vector có giá trị bằng nhau (giá trị từ 0 đến 1) và tổng giá trị các phần tử trên vector có giá trị là 1. - Bước 4: Nhân vector h với ma trận A. Vector t = A.h - Bước 5: Chuẩn hóa vector t thành vector xác suất. Nếu vector t bằng với vector h thì gán các giá trong trong vector t cho vector h và chuyển sang bước 6. Ngược lại, chuyển về bước 5 lặp lại đến khi vector t bằng vector h. - Bước 6: Vector Authority a bằng cách nhân vector h (hub) với ma trận chuyển vị của ma trận A. a = AT.h - Bước 7: Chuẩn hóa vector Authority thành vector xác suất. Mỗi giá trị lần lượt trên vector Hub và vector Authority là các điểm Hub và điểm Authority cho mỗi trang Web. Lưu ý: nếu tính HITS từ đồ thị vô hướng thì kết quả của điểm Hub và điểm Authority là giống nhau vì khi trong đồ thị vô hướng thì 1 cạnh nối 2 đỉnh được xem như là 2 cạnh có hướng đối nghịch nhau, đỉnh A trỏ tới đỉnh B và ngược lại. Ví dụ từ hình 1: điểm Hub và điểm Authority cho 7 đỉnh Đỉnh 1: Hub: 0.19 Authority: 0.19 Đỉnh 2: Hub: 0.22 Authority: 0.22 Đỉnh 3: Hub: 0.19 Authority: 0.19 Đỉnh 4: Hub: 0.19 Authority: 0.19 Đỉnh 5: Hub: 0.1 Authority: 0.1 Đỉnh 6: Hub: 0.05 Authority: 0.05 Đỉnh 7: Hub: 0.05 Authority: 0.05 Vì đây là một đồ thị vô hướng nên điểm Hub và điểm Authority của mỗi đỉnh là bằng nhau. Đỉnh 2 có nhiều link liên kết nên có số điểm Hub và Authority cao nhất, còn các đỉnh 6 và đỉnh 7 có số liên kết thấp nhất nên có số điểm Hub và Authority thấp nhất. Trang 10
\ 2.2 Thuật giải tối ưu hóa dựa trên mô phỏng hành vi đàn kiến [3] Thuật giải tối ưu hóa dựa trên mô phỏng hành vi của đàn kiến trong tự nhiên. Ý tưởng xuất phát từ một công trình nghiên cứu sinh học vào năm 1989. Khi nhà bác học người Đan Mạch Deneubourg và các cộng sự công bố kết quả nghiên cứu về thí nghiệm trên đàn kiến Argentina, gọi là thí nghiệm trên chiếc “Chiếc cầu đôi”. Cụ thể, họ đã đặt một chiếu cầu đôi gồm hai nhánh (nhánh dài hơn có độ dài bằng hai lần nhánh ngắn hơn) nối tổ của đàn kiến với nguồn thức ăn, sau đó thả một đàn kiến và bắt đầu quan sát hoạt động của chúng trong một thời gian đủ lớn. Kết quả ban đầu các con kiến đi theo cả hai nhánh của chiếc cầu với số lượng gần như ngang nhau, nhưng càng về cuối thời gian quan sát người ta nhận thấy các con kiến có xu hướng chọn nhánh ngắn hơn để đi (80-100% số lượng). Kết quả được các nhà sinh học lý giải như sau: do đặc tính tự nhiên và đặc tính hóa học, mỗi con kiến khi di chuyển luôn để lại một lượng hóa chất gọi là các vết mùi trên đường đi và thường thì chúng sẽ đi theo con đường có lượng mùi đậm đặc hơn. Các vết mùi này là những loại hóa chất bay hơi theo thời gian, do vậy ban đầu thì lượng mùi ở hai nhánh là xấp xỉ như nhau, nhưng sau một khoảng thời gian nhất định nhánh ngắn hơn sẽ có lượng mùi đậm đặc hơn so với nhánh dài hơn do ban đầu cùng lượng mùi gần xấp xỉ nhau nhưng sau một khoảng thời gian nhất định nhánh ngắn hơn sẽ có lượng mùi đậm đặc hơn so với nhánh dài do mật độ phân bố mùi ở nhánh dài không dày như mật độ mùi trên nhánh ngắn và lượng mùi bay hơi trên nhánh dài sẽ bay hơi nhanh hơn nhánh ngắn nên dần dần đàn kiến lựa chọn con đường có mùi đậm đặc. Từ đặc tính này, đàn kiến đã lựa chọn được con đường tối ưu. Với cơ sở là kết quả của thí nghiệm trên, năm 1991 nhà khoa học người Bỉ Marco Dorigo đã xây dựng thuật giải đàn kiến (Ant Algorithm) để giải quyết tự nhiên các bài toán trong tin học. Nhìn một cách tổng quan về thuật giải đàn kiến, thuật giải này là một mô hình biến đổi từ phương pháp giải bài toàn tin học theo phương pháp “ bước đi ngẫu nhiên”, thuật giả đàn kiến gần tương tự với thuật giải gom cụm Markov Cluster ở trên về mặt ý tưởng. Nếu mô hình hóa bài toán thành đồ thị, mật độ phân bố mùi trên các đường đi chính là độ lớn của cạnh nối các đỉnh với nhau. Trong đó, sau một thời gian thuật giải đàn kiến cố gắng làm giảm độ lớn các cạnh (mùi bị bốc hơi) và dựa trên tổng độ lớn trên các cạnh của đường đi sẽ đưa bài toán về gần hơn với kết quả chính xác, đó là sự tối ưu hóa dựa trên mô phỏng đàn kiến trong tự nhiên. Còn thuật giải gom cụm Markov Cluster dựa trên mật độ di chuyển qua lại giữa các cạnh liên kết các đỉnh với nhau và qua các bước tính toán Trang 11
\ làm yếu dần dần các cạnh liên kết giữa các nhóm và dần dần hình thành được các nhóm dữ liệu. Minh họa cho thuật giải đàn kiến, đó là việc áp dụng thuật giải đàn kiến cho bài toán kinh điển: bài toán người du lịch. Bài toán người du lịch là bài toán tìm đường đi ngắn nhất cho người thương nhân hay còn gọi là người chào hàng xuất phát từ một thành phố, đi qua lần lượt tất cả các thành phố duy nhất một lần và quay về thành phố ban đầu với chi phí rẻ nhất, được phát biểu vào thế kỷ 17 bởi hai nhà toán học vương quốc Anh là Sir William Rowan Hamilton và Thomas Penyngton Kirkman. Phát biểu bài toán dưới dạng đồ thị như sau: Cho đồ thị n đỉnh đầy đủ và có trọng số G = (V-tập đỉnh, E-tập cạnh) có hướng hoặc vô hướng. Tìm chu trình v1  v2  …  vn  v1 với vi∈ , vi vj, i, j = 1, …, n. Phương pháp tìm đường đi mô phỏng hành vi con kiến sẽ được thực hiện như sau: Các con kiến sẽ tiến hành tìm đường đi từ đỉnh xuất phát qua một loạt các đỉnh và quay trở về đỉnh ban đầu, tại đỉnh u một con kiến sẽ chọn đỉnh v chưa được đi qua trong tập láng giềng của u theo xác suất sau: Hình 4: xác suất lựa chọn đỉnh tiếp theo chưa được đi qua. Trong đó, UV(u) là tập các đỉnh láng giềng của u chưa được con kiến hiện tại đi qua. gọi là thông tin heuristic giúp đánh giá chính xác hơn sự lựa chọn của con kiến khi quyết định đi từ đỉnh u qua đỉnh v. Heuristic dựa trên độ dài của cạnh nối giữa đỉnh u và đỉnh v. Cạnh càng dài thì xác suất đi qua càng thấp và ngược lại. Công thức ở hình 4 biểu diễn xác suất chọn các đỉnh đi tiếp có thể hiểu một cách đơn giản: quyết định lựa chọn đỉnh tiếp theo để đi của con kiến được lựa chọn ngẫu nhiên (phương pháp “ bước đi ngẫu nhiên”) – tức là đỉnh nào có xác suất cao hơn sẽ có khả năng được chọn cao hơn nhưng không có nghĩa là các đỉnh xác suất thấp hơn không được chọn mà nó được chọn với cơ hội thấp hơn. Sau khi tính được xác suất chọn các đỉnh đi tiếp thì việc lựa chọn đỉnh tiếp theo được thực hiện nhờ kỹ thuật bánh xe ru-lét. Giả sử V = {v1, v2, …, vn} là tập đỉnh láng giềng của đỉnh u với các xác suất như sau: p1, p2, …, pn. Trước tiên, tính cộng dồn phần trăm Trang 12
\ tương ứng cho mỗi xác suất. Ví dụ: p1 = 30%, p2 = 20%, p3 =50%. Gọi là vector v là vector biểu diễn vùng giá trị cho 3 xác suất p1, p2 và p3 thì tương ứng vùng biểu diễn của v cho p1 là từ 0 đến 30, vùng biểu diễn của v cho p2 là từ 31 đến 50 và vùng biểu diễn của v cho p3 là từ 51 đến 100. Sau khi biểu diễn vector, sẽ tiến hành chọn lựa đỉnh đi tiếp bằng cách phát sinh 1 số ngẫu nhiên từ 0 đến 100. Nếu số ngẫu nhiên này rơi vào vùng nào trên vector thì đỉnh tương ứng trên đó được chọn. Ví dụ: nếu số ngẫu nhiên là 20 rơi vào vùng biểu diễn của v1 (từ 0 đến 30) nên v1 được chọn là đỉnh tiếp theo. Trong thuật giải đàn kiến thì mỗi lần phát sinh số ngẫu nhiên được hiểu là quá trình mà mỗi con kiến tiến hành lựa chọn đường đi tiếp theo. Sau khi và kể cả trong quá trình các con kiến tìm đường đi các vết mùi sẽ được cập nhật lại, vì chúng bị biến đổi do quá trình bay hơi và do quá trình tích lũy của các con kiến trên đường đi đó. Có nhiều cách cập nhật mùi nhưng trong phạm vi bài luận chỉ giới thiệu cách cập nhật mùi đơn giản nhất, vết mùi trên mỗi cạnh (đường đi) được cập nhật lại theo công thức sau: . Trong đó ∈ [0, 1] gọi là tham số bay hơi vì sau mỗi lần cập nhật lượng mùi trên cạnh (i, j) sẽ mất đi một lượng là . Ngoài lượng bay hơi mất đi, mỗi cạnh (i, j) còn được tích tụ thêm một lượng mùi ∆i, j nhất định tùy thuộc vào từng con kiến đi qua, cụ thể được tính như sau: Hình 5: công thức cập nhật lượng mùi khi các con kiến đi qua. Trong đó, Q là một hằng số, Lk là độ hành trình của con kiến thứ k. Nhờ việc cập nhật mùi mà sau mỗi lần lựa chọn đi tiếp đến các cạnh mà nồng độ vết mùi các cạnh sẽ thay đổi (hoặc giảm hoặc tăng dần) ảnh hưởng đến quyết định chọn của các con kiến, có thể ở bước lặp này chọn một cạnh để đi nhưng đến bước lặp khác vẫn con kiến đó lại không đi qua cạnh đó nữa. Nhờ vậy thuật toán có khả năng tìm được lời giải tốt trong những trường hợp dữ liệu lớn. 3. Áp dụng thực tiễn từ các thuật giải Qua các minh họa bởi các thuật toán trên, phương pháp “bước đi ngẫu nhiên” đã ứng dụng vào nhiều thuật toán khác nhau. Tùy vào mỗi yêu cầu – mục đích của bài toán mà phương pháp “bước đi ngẫu nhiên” mà có phương thức xử lý linh hoạt khác nhau. Mỗi thuật toán ứng dụng phương pháp “bước đi ngẫu nhiên” đã được ứng dụng nhiều trong thực tế và thu được những kết quả tốt. Phương pháp “bước đi ngẫu nhiên” đơn giản là Trang 13
\ ngẫu nhiên chọn lựa một giải pháp tiếp theo với xác suất kèm theo để tùy theo nhu cầu bài toán mà có thể lưu vết hoặc tăng giảm liên kết các thực thể để làm xuất hiện kết quả. Thuật giải gom cụm Markov Cluster thể hiện sự chính xác cao so với các thuật toán gom cụm khác. Tuy độ tính toán của thuật giải Markov Cluster được xem là phức tạp, thể hiện qua việc tính toán chính của thuật giải là nhân các ma trận với nhau nhưng trong một thời đại mà kỹ thuật tính toán trên máy tính đang phát triển mạnh mẽ sẽ giúp hạn chế điẻm yếu này. Như việc sử dụng tính toán song song, thiết kế lại cấu trúc ma trận (trên vector đặc biệt) đồng thời, đưa việc tính toán lên điện toán đám mây sẽ giúp giải quyết yếu điểm về tính toán phức tạp của thuật giải Markov Cluster. Thuật giải gom cụm Markov Cluster được sử dụng cho việc gom cụm tự động các tài liệu, qua đó phân lớp văn bản tốt hơn. Ngoài ra, Markov Cluster còn được sử dụng gom cụm – nhận dạng các cấu trúc protein. (gom nhóm các cấu trúc protein gần giống nhau – để qua đó rút trích được đặc điểm, tính chất nổi bật), sử dụng trong kinh tế khi phân lớp tự động danh sách khách hàng để giúp đề ra các sản phẩm kinh doanh tốt hơn. Thuật giải đánh giá liên kết HITS với nội dung đánh giá dựa trên điểm Hub và điểm Authority được xem là nền tảng trong việc phát triển đánh giá nội dung trang Web trên các máy tìm kiếm trên Internet như Google, Yahoo, Wolfram Anpha… Không chỉ áp dụng phân tích trang Web mà thuật giải HITS còn mở rộng áp dụng cho lĩnh vực khác như viễn thông, kinh tế. Chẳng hạn, áp dụng vào phân tích các cuộc gọi điện thoại hằng ngày để xác định các đặc điểm, tính chất khách hàng và chất lượng cuộc gọi được đáp ứng để đưa ra các chiến lược kinh doanh. Cũng như mô tả bảng chất lượng Thuật toán tối ưu hóa dựa trên mô phỏng đàn kiến (thuật giải đàn kiến) đã giải quyết nhiều các bài toán một cách tự nhiên hơn. Khác biệt với 2 thuật giải trước, chỉ giải quyết trong phạm vi bài toán cụ thể. Thuật giải đàn kiến tương tự như thuật giải di truyền được sử dụng để giải quyết cho nhiều bài toán khác nhau. Thuật giải đàn kiến được áp dụng vào các bài toán cần tối ưu như tối ưu hàm đơn biến, tối ưu hàm đa biến, sắp xếp, tìm kiếm đường đi ngắn nhất phù hợp. Sử dụng cho các bài toán mà phương pháp giải trực tiếp không hiệu quả (hạn chế thời gian tính toán, dữ liệu sử dụng lớn) và kết quả giải được không cần đúng hoàn toàn mà chỉ cần đúng một cách tương đối không quá sai biệt với kết quả thực của bài toán. Một số ứng dụng thực tế như quy hoạch đô thị, giao thông, thiết kế mạng lưới, lịch làm việc cho các tổ chức. 4. Kết luận Trang 14
\ Phương pháp “bước đi ngẫu nhiên” là một phương pháp tổng quan được áp dụng trong nhiều thuật giải khác nhau. Nó không phải là một phương pháp cố định mà được biến đổi, áp dụng vào nhiều lớp bài toán tùy vào nhu cầu bài toán, là một ý tưởng để phát sinh ra các cách giải quyết cho các bài toán riêng biệt. Phương pháp “bước đi ngẫu nhiên” cho phép suy nghĩ, giải quyết các bài toán gần gũi với cách giải quyết của con người nên ý tưởng và phương pháp của “bước nhảy ngẫu nhiên” dễ dàng làm nền tảng, kết hợp với các ý tưởng khác nhau để phát triển các thuật giải hiệu quả khác nhau áp dụng cho nhiều lớp bài toán. Phương pháp “bước đi ngẫu nhiên” ngày càng được sử dụng nhiều hơn không chỉ trong lĩnh vực tin học mà còn được áp dụng cho nhiều lĩnh vực khác như kinh tế, phân tích dữ liệu. Đồng thời, phương pháp “bước đi ngẫu nhiên” cũng cần kết hợp với các kiến thức toán học để xây dựng các thuật giải hiệu quả hơn và mở rộng hơn các bài toán. Tài liệu tham khảo Trang 15
\ [1] http://www.cs.ucsb.edu/~xyan/classes/CS595D-2009winter/MCL_Presentation2.pdf cập nhật ngày 12/04/2012 [2] http://www.math.cornell.edu/~mec/Winter2009/RalucaRemus/Lecture4/lecture4.html cập nhật ngày 12/04/2012 [3] http://vnschool.net/modules.php?name=News&file=article&sid=4332 cập nhật ngày 12/04/2012 Phụ lục Chương trình minh họa một vài thuật giải áp dụng phương pháp “bước đi ngẫu nhiên” Trang 16
\ Chương trình chạy thử 2 thuật toán: gom cụm Markov Cluster và đánh giá liên kết HITS Giao diện chương trình: Trong đó, bao gồm: - Nút Load file: load ma trận kề từ file lên. File ma trận là file dòng đầu ghi số đỉnh. Các dòng còn lại ghi ma trận kề. Để sẵn file tên matrix.txt trong cùng file chạy .exe. - Nút Markov Cluster từng bước: thao tác từng vòng lặp của thuật giải Markov Cluster. - Nút Tính kết quả Cluster: hiển thị nhóm ở phần Kết quả Cluster. Lưu ý: chỉ xử lý khi ma trận sau tính toán đã đạt trạng thái hội tụ. - Nút Tính HITS: tính điểm Hub và Authority tại ma trận đang xét và hiển thị kết quả ở phần Kết quả HITS. Chương trình chỉ là thể hiện phần minh họa đơn giản đối với một ma trận có số lượng đỉnh nhỏ, không áp dụng xử lý cho ma trận kề với số đỉnh trên ma trận lớn. Chương trình được viết trên ngôn ngữ C#. Máy tính cần cài thêm bộ .Net framework để có thể chạy được chương trình. Trang 17