Luận văn Thạc sĩ Khoa học máy tính: Một thuật toán hiệu quả cho tập đỉnh thống trị có trọng số nhỏ nhất

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:61

Thêm vào BST

Báo xấu

8
lượt xem 2
download

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

Luận văn "Một thuật toán hiệu quả cho tập đỉnh thống trị có trọng số nhỏ nhất" được hoàn thành với mục tiêu nhằm đề xuất áp dụng thuật toán kết hợp tìm kiếm với số lượng hàng xóm lớn với GRASP cho bài toán tìm tập đỉnh thống trị có trọng số cực tiểu. Việc kết hợp này được hình thành dựa vào việc áp dụng các chiến thuật xóa đỉnh khác nhau, và áp dụng GRASP cho phần khởi tạo và thuật toán chỉnh sửa đỉnh để tạo thành các tập đỉnh thống trị có chất lượng tốt.

Chủ đề:

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

Lưu

Nội dung Text: Luận văn Thạc sĩ Khoa học máy tính: Một thuật toán hiệu quả cho tập đỉnh thống trị có trọng số nhỏ nhất

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ ĐINH VĂN VIỆT MỘT THUẬT TOÁN HIỆU QUẢ CHO TẬP ĐỈNH THỐNG TRỊ CÓ TRỌNG SỐ NHỎ NHẤT LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH HÀ NỘI – 2021
Lời Cảm Ơn Đầu tiên, tôi xin gửi lời cảm ơn đến PGS. TS. Hoàng Xuân Huấn, giảng viên tại bộ môn khoa học máy tính thuộc khoa công nghệ thông tin. Trong khi làm luận văn, thầy đã hướng dẫn tôi rất tận tình chu đáo. Không chỉ giới thiệu những kiến thức hữu ích, thầy còn truyền cảm hứng đến tôi về những ứng dụng tự nhiên lý thú. Tôi ngày càng trưởng thành hơn không chỉ về nhiều kiến thức hơn, mà còn cả về nhận thức về đời sống thực tại. Tôi vô cùng kính phục và cám ơn thầy. Tiếp theo, tôi vô cùng cảm ơn bố mẹ đã luôn ở bên cạnh hỗ trợ tôi, giúp tôi trong hầu hết các vấn đề gặp phải trong cuộc sống. Tôi xin cảm ơn gia đình tôi, nơi tôi được sinh ra và lớn lên, nơi có rất nhiều kỷ niệm đẹp ảnh hưởng sâu sắc đến những tư duy của tôi trong luận văn này. Nhờ tình thương vô bờ bến của họ, tôi đã không phải chịu quá nhiều áp lực của cuộc sống mưu sinh đầy vất vả, có thêm nhiều thời gian dành cho luận văn này. Đây là động lực chính giúp tôi hoàn thành xong luận văn này. Cuối cùng, tôi cảm ơn bạn bè và đồng nghiệp đã tạo điều kiện giúp tôi, cùng tôi đi tiếp trên những chặng đường đầy thách thức không chỉ trong công việc mà còn các vấn đề ngoài cuộc sống. Tôi xin gửi lời cảm ơn đến toàn bộ tập thể trường đại học Công Nghệ, trực thuộc đại học quốc gia Hà Nội. Ở đây, tôi đã được sống trong môi trường năng động, trẻ trung, tràn trề cơ hội và thách thức. Cảm ơn tất cả đã mở ra cánh cửa tương lai tươi sáng cho chính tôi! Tác giả Đinh Văn Việt 3
Lời Cam Đoan Tôi xin cam đoan đây là công trình nghiên cứu của tôi dưới sự giám sát của PGS.TS Hoàng Xuân Huấn. Các phần đóng góp trong luận văn này chưa được nộp cho một trình độ hoặc bằng cấp tại đây hoặc bất cứ các tổ chức nghiên cứu giáo dục đại học. Các đóng góp và kết quả được trình bày trong luận văn này hoàn toàn được kiểm nghiệm rõ ràng bằng các thực nghiệm dựa trên nhiều bộ dữ liệu được chấp thuận và sử dụng bởi cộng đồng khoa học. Các phần có sự đóng góp của người khác vào luận văn này đều được xin phép và có được sự đồng ý chấp thuận của họ. Các phần kiến thức liên quan được sử dụng trong luận văn này đều được tham chiếu rõ ràng từ các nguồn tham khảo được công đồng khoa học công nhận và được liệt kê đầy đủ tại mục liệt kê tham khảo. Tác giả Đinh Văn Việt 4
Danh sách ký hiệu và viết tắt NP Nondeterministic polynomial Problem P Polynomial Problem MDS Minimum dominating set MCDS Minimum Connected Dominating Set MIDS Minimum Independent Dominating Set MkDS Minimum k-dominating Set MWDS Minimum Weighted Dominating Set GA Genetic Algorithm ACO Ant Colony Optimization PSO Particle Swarm Optimization MA Memetic Algorithm LS Local Search LNS Large Neighborhood Search IP Integer Programming MMAS Max-Min Ant System GRASP Greedy Randomized Adaptive Search Procedure 5
HGA Hybrid Genetic Algorithm ACO-LS Hybrid ACO and local search ACO-PP- Hybrid ACO and local search with intialization LS HMA Hybrid Memetic Algorithm BPSO Binary Particle Swarm Optimization R-BPIG Randomized population-based iterated greedy algorithm hyb-R- Hybrid Randomized population-based iterated PBIG greedy algorithm CC2FS Two-level configuration checking and frequency based scoring function HTS-DS Hybrid tabu search matheuristic HLNS Hybrid large neighborhood search 6
Tóm Tắt Nội Dung Bài toán tập đỉnh thống trị có trọng số nhỏ nhất (MWDS) là một trong những bài toán NP-Hard kinh điển được nhiều nhà nghiên cứu quan tâm và đã được ứng dụng vào trong thực tiễn. Nhiều ứng dụng được tạo ra để đáp ứng sự phát triển của các mạng lưới từ sự phát triển của xã hội. Các ứng dụng này chủ yếu liên quan đến việc thiết kế và tận dụng các tài nguyên lợi ích thu được từ các mạng lưới này. Hầu hết, các ứng dụng đều có liên quan đến bài toán tập đỉnh thống trị. Tuy đã có rất nhiều thuật toán được đề xuất, nhưng các thuật toán vẫn chưa đủ hiệu quả để giải quyết bài toán trên. Luận văn này đề xuất thuật toán kết hợp tìm kiếm với số lượng hàng xóm lớn (HLNS) để giải quyết bài toán đạt chất lượng kết quả tốt trong lượng thời gian xác định trên một số bộ dữ liệu chuẩn. Thực nghiệm đã chỉ ra rằng thuật toán hiệu quả hơn các thuật toán đã có trên các bộ dữ liệu thực tế BHOSLIB và DIMACS. Cuối cùng, luận văn giới thiệu về ứng dụng moderator-selector để chọn người điều hành cho một nhóm hoặc một tổ chức trên một mạng lưới cho trước. 7
Mục lục Lời Cảm Ơn ........................................................................................................... 3 Lời Cam Đoan ....................................................................................................... 4 Danh sách ký hiệu và viết tắt ................................................................................ 5 Tóm Tắt Nội Dung ................................................................................................ 7 Mục lục .................................................................................................................. 8 Danh sách thuật toán ........................................................................................... 10 Danh sách hình vẽ ............................................................................................... 11 Danh sách bảng ................................................................................................... 12 Mở Đầu................................................................................................................ 13 Chương 1. Giới Thiệu Bài Toán Tập Đỉnh Thống Trị Có Trọng Số Nhỏ Nhất . 20 1.1 Bài toán tập đỉnh thống trị có trọng số cực tiểu và các bài toán liên quan 21 1.2 Các nghiên cứu liên quan .............................................................. 25 1.3 Các ứng dụng liên quan đến bài toán tập đỉnh thống trị ............... 31 1.4 Một số định lý quan trọng ............................................................. 34 1.4.1 Đinh lý Cook-levin .................................................................. 34 1.4.2 Định lý không có bữa trưa miễn phí........................................ 35 Chương 2. Thuật toán kết hợp tìm kiếm với số lượng hàng xóm lớn................. 36 2.1 Thuật toán HLNS .......................................................................... 36 2.2 Thuật toán khởi tạo cho tập đỉnh thống trị .................................... 37 2.3 Các thuật toán xóa các đỉnh trong tập đỉnh thống trị .................... 38 2.4 Các thuật toán sửa tập đỉnh ........................................................... 38 2.5 Các thuật toán xóa bỏ đỉnh dư thừa trong tập đỉnh thống trị ........ 39 Chương 3. Thực nghiệm ..................................................................................... 41 2.1 Giới thiệu thực nghiệm ................................................................. 41 2.2 Kết quả thực nghiệm ..................................................................... 42 2.2.1 Thực nghiệm trên TH1 ............................................................ 42 2.2.2 Thực nghiệm trên TH2 ............................................................ 44 8
Chương 4. Ứng dụng chọn người điều hành cho nhóm moderator-selector ...... 46 4.1 Giới thiệu ứng dụng chọn người điều hành cho nhóm moderator- selector 46 4.2 Cách sử dụng ứng dụng................................................................. 48 Kết Luận Và Thảo Luận ...................................................................................... 52 Tài liệu tham khảo ............................................................................................... 53 9
Danh sách thuật toán Thuật Toán 1: Tìm kiếm với số lượng hàng xóm lớn - LNS .................... 18 Thuật Toán 2: Thủ tục tham lam thích nghi ngẫu nhiên GRASP ............ 19 Thuật Toán 3: Thuật toán HLNS .............................................................. 37 Thuật Toán 4: Thuật toán khởi tạo tập đỉnh ............................................. 38 Thuật Toán 5: Thuật toán xóa đỉnh DEL .................................................. 38 Thuật Toán 6: Thuật toán thêm đỉnh REPAIR ......................................... 39 Thuật Toán 7: Thuật toán DEL-REDUNDANT ...................................... 40 10
Danh sách hình vẽ Hình 1: Đồ thị chuyển đổi giữa bài toán SC và bài toán MDS 24 Hình 2: Đồ thị chuyển đổi từ bài toán tập MDS sang bài toán SC 24 Hình 3: Ứng dụng moderators-selector 48 Hình 4: Mở một tệp đầu vào dưới định dạng json 49 Hình 5: Hiển thị tên người dùng và giá trị của họ 49 Hình 6: Hiển thị mối liên hệ giữa các người dùng 50 Hình 7: Hiển thị những người điều hành được chọn 50 Hình 8: Thiết lập chương trình 51 11
Danh sách bảng Bảng 1: Tham số cấu hình cho HLNS ...................................................... 41 Bảng 2: Kết quả thực nghiệm trên TH1 .................................................... 43 Bảng 3: Kết quả thực nghiệm trên TH2 .................................................... 44 12
Mở Đầu Một lượng lớn các liên kết tồn tại trong thế giới hiện nay đã kết nối hầu hết mọi thứ lại với nhau, và phát triển dần về số lượng tạo ra một số lượng khổng lồ các mạng lưới. Các mạng lưới được tạo ra từ các tổ chức xã hội được hình thành ở trong hầu hết các nơi mà con người đang sinh sống. Với một xã hội hiện đại như ngày nay, trẻ con đến trường tham vào các tổ chức trong trường học. Người lớn đi làm và tham gia vào rất nhiều tổ chức và mạng lưới trong xã hội như: hệ thống tổ chức lao động, hệ thống bảo hiểm xã hội, … Người già thường ít tham gia vào các tổ chức hơn, hầu hết trong số đó là các tổ chức về hưu trí và hội những người bạn già. Các tổ chức này thường được hình thành một cách tự nhiên từ các nhu cầu cần thiết của cuộc sống, hình thành các mạng lưới với đầy đủ kích cỡ khác nhau. Các mạng lưới được tạo thành từ dựa trên các hệ thống khổng lồ như mạng điện, mạng INTERNET, và mạng viễn thông. Các mạng lưới này được phát triển mạnh mẽ trong thời kỳ kỷ nguyên của kỹ thuật số và trí tuệ nhân tạo. Hiện nay, các mạng điện cung cấp đủ điện cho hàng tỷ người dùng ở khắp nơi trên thế giới với kết cấu rất linh hoạt và phong phú phụ thuộc vào địa hình. Tiếp theo, các mạng xã hội nổi tiếng như Twitter, Wechat, QQ, Facebook, với số lượng người dùng từ vài trăm triệu đến tỷ người dùng. Trên các mạng này, mọi người được sử dụng rất nhiều tiện ích như nhắn tin, trò chuyện trực tiếp, chơi trò chơi cùng nhau. Cuối cùng, các mạng viễn thông hiện nay được phủ song hầu như toàn bộ các nơi tập trung đông đảo con người sinh sống, cho phép hàng triệu người dùng giao tiếp với nhau trong một khoảng rộng lớn một cách linh hoạt không bị gò bó như các mạng lưới cố định. Các mạng cảm biến được hình thành để thu thập các thông tin cần thiết phục vụ cho các ứng dụng thực tiễn. Các mạng lưới cảm biến được sử dụng rất nhiều trong thực tế và trong cuộc sống vạn vật kết nối như ngày nay. Đầu tiên, các ứng dụng về nhà ở thông minh cần đến hàng trăm cảm biến để thu thập các thông tin về môi trường, sức khỏe, các tiện ích giải trí, và các công cụ hỗ trợ. Bên cạnh đó, các ứng dụng về phương tiện đi lại như ô tô, máy bay, tàu vũ trụ cần rất nhiều các cảm biến với đầy đủ các loại kể cả tối tân nhất hiện nay. Thêm vào nữa, các ứng dụng bảo vệ môi trường cũng cần rất nhiều các cảm biến đến có thể theo dõi chính xác tình hình môi trường hiện nay, giúp các nhà điều hành 13
và người có trách nhiệm, cũng như toàn bộ dân cư ứng phó kịp thời với các điều kiện môi trường thay đổi thất thường phức tạp như ngày nay. Cuối cùng, các ứng dụng liên quan đến hàng không vũ trụ đang được quan tâm nhất với các thiết bị chủ yếu gồm các tổ hợp, mạng lưới phức tạp giúp con người khám phá và chinh phục vũ trụ. Hầu hết các mạng lưới được hình thành với những khởi đầu không quá phức tạp phục vụ cho những đối tượng mục tiêu bình thường. Sau đó, cùng với sự phát triển của đời sống và nhu cầu thực tế, các mạng này phát triển với số lượng và kích thước như khổng lồ và đa dạng và thành phần. Chẳng hạn như, mạng xã hội Facebok với khởi đầu chỉ khoảng vài chục ngàn người dùng, trong đó chủ yếu là các sinh viên đại học. Các tiện ích bạn đầu chủ yếu là nhắn tin và chia sẽ ảnh cá nhân qua mạng. Khoảng chục năm về sau, mạng xã hội này đã phát triển lên đến vài trăm triệu người dùng với rất nhiều tiện ích và có tới cả trăm ngàn gian hàng trên mạng xã hội nay. Cho đến bây giờ, hầu hết những người dùng INTERNET hiện đại đều biết đến mạng xã hội Facebook với hơn tỷ người dùng ở khắp mọi người trên thế giới với đủ các thành phần từ người dân bình thường, doanh nhân cho đến các người nổi tiếng. Phân tích các mạng lưới sẽ giúp con người khai thác hiệu quả chúng. Việc tìm hiểu về một mạng lưới sẽ giúp con người hiểu rõ hơn các tính chất của một mạng lưới, các thành phần liên quan và sự phát triển của mạng lưới đó. Từ đó, họ sẽ đưa ra các quyết định vào mạng lưới đó để thu được hiệu quả lớn nhất cho chính họ. Chẳng hạn, việc triển khai INTERNET trên một phạm vi địa lý cần tìm hiểu về sự phân bố dân cư, tính chất địa lý của vùng miền, yếu tố sử dụng của người dụng để có thể quyết định đặt các thiết bị ở các vị trí hợp lý giúp giảm thiểu công sức chi phí, thời gian triển khai mạng cũng như làm giảm chi phí bảo trì mạng này. Phân tích và khai thác các mạng lưới hiệu quả luôn tạo ra các giá trị to lớn cho người sử dụng, đặc biệt trong kỷ nguyên của vạn vật kết nối (IOT). Một trong những yếu tố được quan tâm là tập các nốt ảnh hưởng đến toàn bộ mạng lưới, và bài toán được quan tâm gần đây là bài toán tìm tập đỉnh thống trị có trọng số nhỏ nhất. Phân tích mạng lưới để khai thác và phát triển mạng lưới, giúp các hệ thống nên mạnh mẽ, hoạt động tốt hơn, nhiều tính năng hơn, giúp người dùng và nhà quản lý mạng có thêm nhiều lợi ích. Các mạng lưới phân tích bao gồm: mạng xã hội, mạng di động, mạng cảm biến, mạng lưới tổ chức xã hội. Việc 14
khai thác từ các mạng này chủ yếu khai thác tăng kích thước hệ thống, kích thích người dùng tham gia vào hệ thống, kích thích người dùng sử dụng dịch vụ trên mạng, kéo dài tuổi thọ của mạng, giảm thiểu chi phí vận hành và bảo trì, và quản lý hệ thống. Phân tích mạng xã hội và các tổ chức xã hội liên quan đến các bài toán quản lý mạng xã hội, nguồn thông tin lan truyền trên mạng xã hội, bài toán về quảng cáo trên mạng xã hội. Việc phân tích mạng xã hội, giúp cho nhà phát hành sử dụng thông tin từ mạng xã hội hiệu quả để triển khai các dịch vụ và giảm thiểu chi phí vận hành hệ thống. Người dùng sử dụng các dịch vụ như quảng cáo trên mạng xã hội, tìm kiếm bạn bè, tạo dựng hình ảnh trên mạng xã hội, mạng lại lợi ích lớn hơn cho họ. Các tổ chức xã hội tốt hơn khi chọn lựa được các nhà quản lý hiệu quả phù hợp và tối ưu. Ví dụ: người dùng mạng xã hội Youtube thường hay xem những quảng cáo bao cao su DUREX ở trên trong các nhóm youtuber nổi tiếng, và thường chia sẻ nó với những người bạn của họ thông qua các mạng xã hội khác như Facebook, Zalo. Bài toán tìm tập đỉnh thống trị có trọng số nhỏ nhất trên mạng lưới được áp dụng để khai thác các yếu tố về việc tìm ra tập các thành phần có khả năng chi phối toàn bộ các thành phần còn lại trong mạng. Đó là được áp dụng cho đồ thị vô hướng để tìm ra một tập đỉnh chính có tổng trọng số nhỏ nhất sao cho các đỉnh không thuộc đã chọn kề với tập đỉnh đã chọn. Việc tìm ra tập đỉnh này giúp việc phân tích thiết kế trên mạng hiệu quả hơn, do thông thường các tác động lên đồ thị sẽ ảnh hưởng chủ yếu bởi tập đỉnh chính. Tại mỗi thành viên trong tập đỉnh chính, người dùng có thể tập trung dùng chúng để quản lý chi phối, hoặc xử lý các tác vụ nặng. Điều này giúp giảm thiểu các công việc phải làm trên toàn bộ hệ thống vì chỉ cần tập trung vào một tập đỉnh chính là một bộ phận của mạng. Có rất nhiều nghiên cứu ứng dụng về tập đỉnh trị đã được công bố về các ứng dụng liên quan đến mạng xã hội, mạng di động, và mạng cảm biến, … Tuy rằng, các nghiên cứu về tập đỉnh thống trị có trọng số nhỏ nhất rất lâu nhưng hoàn toàn có giá trị trong kỷ nguyên của kết nối vạn vật với một lượng dữ liệu khổng lồ được lưu chuyển và xử lý. Trong gần 20 năm gần đây, đã có rất nhiều nghiên cứu cho bài toán này. Do bài toán được chứng minh thuộc lớp bài toán NP-hard nên cho đến thời điểm nay vẫn chưa có một thuật toán hiệu quả để xử lý bài toán với kết quả chính xác trong thời gian đa thức. Các thuật toán chính xác hiện nay có độ phức tạp tính toán theo hàm mũ, nên chỉ mang tính lý thuyết mà chưa thể áp dụng trong thực 15
tế. Các nghiên cứu này gồm các thuật toán chính xác cho tập đỉnh thống trị của Fomin, Van Rooij dựa trên thuật toán nhánh và rút gọn [8][23]. Các thuật toán khả dụng hiện nay cho bài toán này là các thuật toán metaheuristic với các phương pháp kinh điển gồm tối ưu đàn kiến, giải thuật di truyền, tối ưu bầy đàn, các thuật toán memetic, các thuật toán tìm kiếm địa phương, và thuật toán matheuristic. Các thuật toán matheuristic có ưu điểm là đưa ra lời giải đủ tốt trong một thời gian hợp lý so với các thuật toán tham lam hoặc các thuật toán ngẫu nhiên. Các công trình nghiên cứu bao gồm: áp dụng thuật toán tối ưu đàn kiến để tìm tập đỉnh thống trị [17] [19], áp dụng thuật toán di truyền để tìm các tập thống trị [17], áp dụng thuật toán bầy đàn để tìm tập đỉnh thống trị [13], áp dụng các thuật toán memetic để tìm tập đỉnh thống trị [14], áp dụng thuật toán tìm kiếm địa phương với kỹ thuật cấu hình kiểm thử dựa trên các hàm điểm tần suất [26], các nghiên cứu lên quan đến matheuristic như kết hợp các thuật toán tham lam với quy hoạch nguyên và việc kết hợp tìm kiếm tabu với quy hoạch nguyên [1] [2]. Các thuật toán bầy đàn thì dựa vào số lượng cá thể và phương pháp phát triển quần thể nên thường chạy khá chậm hoặc là chúng bị tăng một lượng chi phí về thời gian do kết hợp với cả các thuật toán tìm kiếm địa phương để cải thiện kết quả. Các thuật toán matheuristic là sự kết hợp với các thuật toán metaheuristic với quy hoạch nguyên. Trong các phương pháp matheuristic được đề xuất hiện này thì có hai chiến lược được đề ra là có gắng khởi tạo lời giải tốt và sử dụng quy hoạch nguyên để tiếp tục tìm kiếm lời giải hoặc hạn chế không gian tìm kiếm để đưa ra bài toán rút gọn sau đó dùng quy hoạch nguyên để giải quyết. Điều kiện kết thúc của các thuật toán trên thường dựa trên số lần lặp hoặc giới hạn thời gian chạy và các tham số này được người dùng đưa ra do quá trình thực nghiệm. Các kết quả thực nghiệm đưa ra đã cho thấy hiện nay các thuật toán tìm kiếm địa phương hoặc các thuật toán tabu kết hợp quy hoạch nguyên là tốt nhất trong số tất cả các thuật toán đã được áp dụng để tìm tập đỉnh thống trị. Ngoài ra, các thuật toán tìm kiếm địa phương còn được áp dụng cho các tập dữ liệu lớn [12] [2]. Các thuật toán tìm kiếm địa phương hoạt động khá tốt tuy nhiên còn rất nhiều điểm hạn chế về chất lượng như kết quả thực nghiệm trên bộ dữ liệu BHOSLIB và bộ dữ liệu DIMACS trong thực nghiệm. Các nghiên cứu việc áp dụng các phương pháp khác thì có chất lượng lời giải hạn chế hoặc thời gian 16
gian chạy khá chậm. Các hạn chế này có thể được khắc phục bởi thuật toán tìm kiếm với số lượng hàng xóm lớn (LNS). Bên cạnh đó, để hạn chế bớt các đỉnh kém chất lượng, thuật toán GRASP được sử dụng để làm giải quyết vấn đề này. Tìm kiếm với số lượng hàng xóm lớn là thuật toán sử dụng số lượng lớn các ứng viên trong một vùng rộng lớn hơn các thuật toán tìm kiếm địa phương đã biết trước đó. Thuật toán được đề xuất lần đầu tiên bởi L.Shaw, và đã được áp dụng hiệu quả để giải quyết bài toán định tuyến giao thông [20]. Ý tưởng của thuật toán là lựa chon các ứng viên có khoảng cách lớn trong không gian tìm kiếm so với ứng viên hiện tại (thuật toán (1)). Thuật toán LNS sử dụng hai phép toán là DEL (phép xóa) và REPAIR (phép sửa) để tìm kiếm lời giải có chất lượng tốt, trong đó để tạo ra ứng viên mới S+ sẽ được tạo ra từ lời giải hiện tại S. Nếu S+ được chấp nhận bởi ACCEPT(S, S+), thuật toán sẽ tiếp tục tiến hành xét duyệt tại ứng viên S+. Phép toán DEL sẽ xóa đi một phần trong lời giải S để tạo S−. Do việc loại bỏ một phần lời giải nên S− thường vi phạm các điều kiện đặt ra. Do vậy, để tạo ra ứng viên mới chấp nhận được phép toán REPAIR sẽ thêm vào một số thành viên vào S− để tạo ứng viên S+. Do hai phép toán DEL và REPAIR bớt và thêm một phần của lời giải S nên S+ và S có sự sai khác khá lớn. Số lượng ứng viên mới có thể được tạo ra từ S là nhiều hơn rất nhiều so với các thuật toán tìm kiếm địa phương trước đây. Các phép toán DEL và REPAIR rất đa dạng và phong phú phụ thuộc vào từng loại bài toán khác nhau và do người dùng lựa chọn. Các thuật toán này kết hợp với nhau để tạo nên một thuật toán hiệu quả. Ví dụ, việc lựa chọn phần tử để loại bỏ trong một lời giải S có thể tuân theo phân bố chuẩn, hoặc phân bố đều. Việc kết hợp sử dụng các phép toán này sẽ làm tăng độ hiệu quả của thuật toán và phương pháp thích nghi tìm kiếm với số lượng hàng xóm lớn được đề xuất. Phương pháp này dựa vào việc gán trọng số cho mỗi thuật toán và cập nhập các trọng số này sau mỗi lần thực thi một phép toán nào đó [16]. procedure Tìm kiếm với số lượng hàng xóm lớn – LNS; Begin Khởi tạo lời giải S; S∗←S while ( chưa chạy hết thời gian tìm kiếm ) do S− ← DELETE(S); // hàm DELETE xóa một số thành phần trong lời giải S 17
S+ ← REPAIR(S−); // hàm REPAIR thêm một số đỉnh cho đến khi hợp lệ if ACCEPT(S, S+) then // lời giải S+ có được chấp nhận để xét tiếp không S← S+; end-if if (S+ tối ưu hơn S∗ ) then S∗ = S+ end-if end-while Đưa ra lời giải S; End; Thuật Toán 1: Tìm kiếm với số lượng hàng xóm lớn - LNS Thủ tục GRASP được sử dụng lần đầu tiên để giải quyết bài toán tập phủ [7]. Đây là sự kết hợp khéo léo giữa các thuật toán tham lam, danh sách hạn chế và sự lựa chọn ngẫu nhiên được trình bày trong thuật toán (2). Các hàm đánh giá ở trong thủ tục đều là các hàm tham lam, và các ngưỡng để tuyển chọn ứng viên đều do người dùng tự thiết lập. Việc chọn tham số tối ưu thường là do người dùng sử dụng thực nghiệm. Thuật toán này có ưu điểm là dễ cài đặt, độ phức tạp thấp và cho chất lượng lời giải vừa phải. Thuật toán đã áp dụng để giải quyết bài toán tìm tập đỉnh thống trị trong thuật toán memetic được đề xuất bởi Gen Ling [14]. Procedure Thuật toán GRASP Input X = {x1, x2, …, xn} Begin S ← {}; while (S chưa là lời giải hợp lệ) do pi←{fval{xi} | xi∉S}; // fval là hàm đánh giá giá trị của xi pmax ←maxp (p); RCL ← {xi | pi≤ 𝛼 ∗ 𝑝𝑚𝑎𝑥}; // danh sách hạn chế RCL xp ← lựa chọn ngẫu nhiên với phân bố đều từ danh sách RCL; S ← S ∪ xp ; 18
end-while; Đưa ra lời giải S; End; Thuật Toán 2: Thủ tục tham lam thích nghi ngẫu nhiên GRASP Thuật toán tạo danh sách RCL dựa trên mức ngưỡng tỉ lệ 𝛼 với giá trị đánh giá lớn nhất trên tập các ứng viên X. Giá trị 𝛼 nếu càng lớn thì kích thước của RCL càng lớn và ngược lại càng bé. Nếu RCL chỉ có 1 phần tử, thuật toán GRASP sẽ trở thành thuật toán tham lam. Thông thường, giá trị 𝛼 được chọn vừa đủ để giới hạn kích thước của RCL và chọn những ứng viên tiềm năng đê tạo ra các lời giải có chất lượng tốt hơn. Bên cạnh đó, ứng viên được thêm vào sẽ được chọn ngẫu nhiên trong danh sách RCL, nên thuật toán có thể cho ra lời giải khác nhau trên cùng một đầu vào. Số lượng các lời giải có thể tạo ra từ thuật toán này phụ thuộc vào giá trị 𝛼. Từ đây, tôi đề xuất áp dụng thuật toán kết hợp tìm kiếm với số lượng hàng xóm lớn với GRASP cho bài toán tìm tập đỉnh thống trị có trọng số cực tiểu. Việc kết hợp này được hình thành dựa vào việc áp dụng các chiến thuật xóa đỉnh khác nhau, và áp dụng GRASP cho phần khởi tạo và thuật toán chỉnh sửa đỉnh để tạo thành các tập đỉnh thống trị có chất lượng tốt. Trong đó, các phần đóng góp gồm: 1. Đề xuất thuật toán tìm kiếm với số lượng hàng xóm lớn, 2. Chứng minh độ hiệu quả của thuật toán so với các thuật toán khác bằng thực nghiệm, 3. Áp dụng cho ứng dụng chọn người điều hành nhóm moderators- selector. Luận văn được tổ chức thành 4 chương ngoại trừ phần kết luận. Chương 1 giới thiệu vấn đề, các nghiên cứu, ứng dụng liên quan, và một số định lý quan trọng trong lý thuyết về độ phức tạp tính toán. Chương 2 trình bày về thuật toán kết hợp tìm kiếm với số lượng hàng xóm lớn HLNS cho bài toán tìm tập đỉnh thống trị có trọng số cực tiểu, thuật toán cho lời giải khá tốt. Chương 3 đưa ra kết quả thực nghiệm của thuật toán trên 2 bộ dữ liệu BHOSLIB và DIMACS với các phân tích so sánh nhận xét đánh giá so với cá thuật toán đã có. Chương 4 trình bày về áp dụng thuật toán tìm tập đỉnh thống trị vào trong ứng dụng chọn người điều hành trong nhóm trên mạng xã hội. 19
Chương 1. Giới Thiệu Bài Toán Tập Đỉnh Thống Trị Có Trọng Số Nhỏ Nhất Chương này chủ yếu giới thiệu về bài toán tập đỉnh thống trị và những nghiên cứu về nó, gồm có: 1. Trình bày về bài toán liên quan đến tập đỉnh thống trị MDS, MCDS, MIDS, MkDS, MWDS, 2. Trình bày về các nghiên cứu về phương pháp giải cứu bài toán MWDS, 3. Trình bày các ứng dụng liên quan đến tập đỉnh thống trị, 4. Trình bày một số định lý quan trọng trong lý thuyết về độ phức tạp tính toán: a) Định lý Cook-Levin, b) Định lý về không có bữa trưa miễn phí (no free-lunch theorem). 20