ĐẠ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
Nondeterministic polynomial Problem
NP
Polynomial Problem
P
Minimum dominating set
MDS
Minimum Connected Dominating Set
MCDS
Minimum Independent Dominating Set
MIDS
Minimum k-dominating Set
MkDS
MWDS Minimum Weighted Dominating Set
Genetic Algorithm
GA
Ant Colony Optimization
ACO
Particle Swarm Optimization
PSO
Memetic Algorithm
MA
Local Search
LS
Large Neighborhood Search
LNS
Integer Programming
IP
MMAS Max-Min Ant System
Greedy Randomized Adaptive Search Procedure
GRASP
5
Hybrid Genetic Algorithm
HGA
ACO-LS Hybrid ACO and local search
Hybrid ACO and local search with intialization
ACO-PP- LS
Hybrid Memetic Algorithm
HMA
Binary Particle Swarm Optimization
BPSO
iterated greedy
R-BPIG
Randomized population-based algorithm
iterated
Hybrid Randomized population-based greedy algorithm
hyb-R- PBIG
CC2FS
Two-level configuration checking and frequency based scoring function
HTS-DS Hybrid tabu search matheuristic
Hybrid large neighborhood search
HLNS
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- 46
selector
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
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
Trên một đồ thị vô hướng G = (V, E), một tập đỉnh S ⊆ V là tập đỉnh thống trị, nếu bất kỳ đỉnh v ∈ V và v ∉ S, ∃ đỉnh u ∈ S là đỉnh kề với đỉnh v. Trên một đồ thị vô hướng G bất kỳ luôn tồn tại ít nhất một tập đỉnh thống trị. Các vấn đề liên quan đến tập đỉnh thống trị gồm:
1. Tìm tập đỉnh thống trị có số lượng nhỏ nhất - MDS (minimum
dominating set),
2. Tìm tập đỉnh thống trị liên thông nhỏ nhất - MCDS (minimum
connected dominating set),
3. Tìm tập đỉnh thống trị độc lập nhỏ nhất - MIDS (minimum independent
dominating set),
4. Tìm tập đỉnh thống trị S với việc mỗi đỉnh v ∉ S, ∃ đỉnh u ∈ S, sao cho tồn tại đường đi giữa hai đỉnh không quá k cạnh - MkDS (minimum k- dominating set),
5. Tìm tập đỉnh thống trị có trọng số nhỏ nhất - MWDS (minimum
dominating set).
Với đồ thị vô hướng G = (V, E), ta gọi C là ma trận kề biểu diễn các cạnh của đồ thị, trong đó: mỗi phần tử Cij = 1 biểu thị có cạnh kết nối giữa đỉnh i và đỉnh j, Cij = 0 biểu thị không có cạnh kết nối giữa đỉnh i và đỉnh j. Vec tơ W là vec tơ trọng số, trong đó w(i) là giá trị của thành phần thứ i của W, biểu diễn trọng số của đỉnh i. Mỗi một tập đỉnh D ⊆ V được biểu diễn bởi một vec tơ nhị phân x, trong đó x(i) là giá của thành phần thứ i và nhận giá trị 0 hoặc 1 biểu thị đỉnh đó được chọn đỉnh thống trị hay không. Một tập đỉnh S ⊆ V với biểu diễn x là tập đỉnh thống trị nếu thỏa mãn điều kiện (1.1)
∑
𝐶𝑖𝑗 × 𝑥𝑗
+ 𝑥𝑖 ≥ 1, ∀𝑖 = 1, 𝑛 (1.1)
𝑛 𝑗=1
Từ đây, các bài toán MDS, MCDS, MIDS, MkDS, MWDS được mô hình
hóa mô hình hóa toán học như sau:
1. bài toán tìm tập đỉnh thống trị có kích thước nhỏ nhất (MDS) được
mô hình hóa theo công thức (1.2)
𝑛
𝑚𝑖𝑛𝑥 ∑ 𝑥𝑖
𝑖=1
21
∗ 𝑥𝑗 + 𝑥𝑖 ≥ 1, ∀𝑖 = 1, 𝑛 (1.2)
𝑛 𝑠. 𝑡: ∑ 𝐶𝑖𝑗 𝑗=1
2. bài toán tìm tập đỉnh thống trị liên thông có kích thước nhỏ nhất
(MCDS) được mô hình hóa theo công thước (1.3)
𝑛
𝑚𝑖𝑛𝑥 ∑ 𝑥𝑖
𝑖=1
𝑛
𝑠. 𝑡: ∑ 𝐶𝑖𝑗 ∗ 𝑥𝑗 + 𝑥𝑖 ≥ 1, ∀= 1, 𝑛
𝑗=1
𝑛ế𝑢 𝑥𝑖 + 𝑥𝑗 = 2, 𝑡ℎì 𝐶𝑖𝑗 = 1 (1.3)
3. bài toán tìm tập đỉnh thống trị độc lập có kích thức nhỏ nhất (MIDS)
được mô hình hóa theo công thức (1.4)
𝑛
𝑚𝑖𝑛𝑥 ∑ 𝑥𝑖
𝑖=1
𝑛
𝑠. 𝑡: ∑ 𝐶𝑖𝑗 ∗ 𝑥𝑗 + 𝑥𝑖 ≥ 1, ∀𝑖 = 1, 𝑛
𝑗=1
𝑛ế𝑢 𝑥𝑖 + 𝑥𝑗 = 2, 𝑡ℎì 𝐶𝑖𝑗 = 0 (1.4)
4. bài toán tìm tập đỉnh thống trị có kích thước nhỏ nhất (MkDS) được
mô hình hóa theo công thức (1.5)
𝑛
𝑚𝑖𝑛𝑥 ∑ 𝑥𝑖
𝑖=1
22
𝑛
𝑠. 𝑡: ∑ 𝐶𝑖𝑗 ∗ 𝑥𝑗 + 𝑥𝑖 ≥ 1, ∀𝑖 = 1, 𝑛
𝑗=1
𝑛ế𝑢 𝑥𝑖 + 𝑥𝑗 = 2, 𝑐ó đườ𝑛𝑔 đ𝑖
𝑔𝑖ữ𝑎 𝑖 𝑣à 𝑗 𝑘ℎô𝑛𝑔 𝑞𝑢á 𝑘 đỉ𝑛ℎ (1.5)
5. bài toán tìm tập đỉnh thống trị có trọng số nhỏ nhất (MWDS) được
mô hình hóa theo công thức (1.6)
𝑛 𝑚𝑖𝑛𝑥 ∑ 𝑤𝑖𝑥𝑖 𝑖=1
∗ 𝑥𝑗 + 𝑥𝑖 ≥ 1, ∀𝑖 = 1, 𝑛 (1.6)
𝑛 𝑠. 𝑡: ∑ 𝐶𝑖𝑗 𝑗=1
Tất cả các bài toán trên đều được chứng minh là bài toán NP-Hard. Việc chứng minh này dựa vào phép rút gọn xấp xỉ L-approximation giữa các bài toán tập đỉnh thống trị và tập phủ [3][5]. Do bài toán tập phủ (set covering) là một trong 21 bài toán được chứng minh thuộc lớp NP-Hard bởi R.Karp [9], nên các bài toán liên quan đến tập đỉnh thống trị đều là NP-Hard.
Sau đây là phép rút gọn xấp xỉ L-reduction giữa bài toán tập đỉnh thống trị nhỏ nhất và tập phủ nhỏ nhất. Từ bài toán tập phủ sang tập đỉnh thống trị: với bài toán p = (S, U), trong đó: U = u1, ... , um là tập chứa toàn bộ các thành phần cơ bản, S = S1, S2, ..., Sn là tập các tập đỉnh thỏa mãn S ⊆ U. Cho I là tập hợp các chỉ mục của S, tại đây đồ thị G = (E, V) được xây dựng trong đó E = U ∪ I là tập các đỉnh của G, V được biểu diễn bằng ma trận kề trong đó các đỉnh thuộc I tạo thành một đồ thị đầy đủ, các đỉnh thuộc U là các đỉnh độc lập lẫn nhau (tức là: CIi, Ij = 1, ∀Ii, Ij ∈ I , Cui, uj = 0, và CIi, uk = 1 ∀uk ∈ Si).
1. Nếu tồn tại một tập phủ P ∪ S, thì tồn tại tập đỉnh thống trị tương ứng là tập con của I trên G. Ví dụ: bài toán p = (S, U), trong đó: U = u1, u2, u3, u4, u5, S = S1, S2, S3 với S1 = u1, u2, S2 = u1, u3, u4, S3 = u4, u5. Đồ thị G = (V, E) được xây dựng gồm V = I1, I2, I3, u1, u2, u3, u4,
23
u5. E = (I1, I2), (I2, I3), (I3, I1), (I1, u1), (I1, u2), (I2, u1), (I2, u3), (I2, u4), (I3, u4), (I3, u5) (xem hình vẽ (1)). Tại đây, tồn tại duy nhất một tập phủ P = S1, S2, S3, và trên đồ thị G ta có tập đỉnh thống trị tương ứng là D = I1, I2, I3,
2. Từ bài toán tập đỉnh thống trị sang tập phủ: với đồ thị G = (V, E) (V = v1, v2, ..., vn), ta xây dựng bài toán tập phủ với U = V, S = S1, S2 , ... , Sn, với Si là tập hợp của vi với các đỉnh kề nó. Với mỗi tập phủ D trên đồ thị G ta có tập phủ P trên đồ tập S tương ứng. Ví dụ: đồ thị G = (V, E) (V = v1, v2, v3, v4, v5, E = (v1, v2), (v1, v3), (v2, v4), (v2, v5), (v3, v4), (v3, v5)), ta có tập đỉnh thống trị D = (v2, v3) tương ứng với tập phủ P = (S2, S3) (xem hình vẽ 2).
I
1 2 3
U
Hình 1: Đồ thị chuyển đổi giữa bài toán SC và bài toán MDS
1 3 4 5 2
1
G = (V, E)
2 3
S2
S3
Hình 2: Đồ thị chuyển đổi từ bài toán tập MDS sang bài toán SC
4 5
Các bài toán MDS, MCDS, MIDS, MkDS, MWDS là các bài toán thuộc lớp bài toán NP-hard. Lời giải của một trong bài toán trên có thể được áp dụng
24
lại cho nhau với một số thay đổi nhất định. Chẳng hạn, lời giải của vấn đề MDS có thể được áp dụng cho lời giải của MCDS với việc thêm rằng buộc liên thông vào trong thuật toán. lời giải của bài toán MWDS có thể áp dụng được trực tiếp cho bài toán MDS với việc đặt trọng số mỗi đỉnh bằng 1. Do mối quan hệ mật thiết giữa các bài toán này, luận văn trình bày phương pháp để giải quyết cho vấn đề MWDS là bài toán tổng quát nhất trong số các bài toán trên.
1.2 Các nghiên cứu liên quan
Bài toán tập đỉnh thống trị là một trong những bài toán chưa có lời giải chính xác trong thời gian đa thức trên những thiết bị phần cứng hiên nay. Do độ phức tạp tính toán hiện nay cho các bài toán dạng này là độ phức tạp theo hàm mũ nên cộng đồng nghiên cứu ứng dụng thường ưu thích sử dụng các phương pháp metaheuristic với độ tốt của lời giải tỷ lệ với thời gian thực thi của thuật toán. Do vậy, trong khoảng thời gian vừa đủ, chất lượng của lời giải thường sai khác so với lời giải chính xác một lượng chấp nhận được tùy vào từng yêu cầu của các ứng dụng trong thực tế. Các phương pháp metaheuristic chủ yếu dành cho lớp bài toán này thường là:
1. giải thuật di truyền (GA) [17], 2. phương pháp tối ưu đàn kiến (ACO) [17][19], 3. phương pháp tối ưu bầy đàn (PSO) [13], 4. phương pháp memetic (MA) [14], 5. tìm kiếm địa phương (LS) [1][26], 6. tìm kiếm với số lượng hàng xóm lớn (LNS)[14].
Các phương pháp trên là những phương pháp kinh điển để giải quyết lớp bài toán NP-Hard được nghiên cứu và sử dụng trong gần 50 năm của ngành khoa học máy tính. Các phương pháp trên đều mô phỏng lại các hiện tượng tự nhiên như thuật toán di truyền lấy cảm hướng từ việc giao phối giữa các cá thể trong loài với nhau, phương pháp tối ưu đàn kiến lấy cảm hứng từ việc kiếm mồi của đàn kiến, phương pháp tối ưu bầy đàn lấy cảm hứng từ việc kiếm mồi của đàn chim trong tự nhiên. Các phương pháp này đều sử dụng lại kinh nghiệm thu được từ lần khám phá trước để đưa ra lời giải tiếp theo.
Các kinh nghiệm này đến từ kinh nghiệm người dùng hoặc là các lời giải từ các lần khám phá ngẫu nhiên trong không gian tìm kiếm. Ngoài ra, một hướng nghiên cứu mới matheuristic gần đây kết hợp giữa phương pháp metaheuristic với quy hoạch nguyên (IP) để đưa ra lời giải với chất lượng tốt trong thời gian hợp lý cũng đã thu được một số thành tựu đáng kể.
25
Trong khoảng 20 năm nghiên cứu về tập đỉnh thống trị, các phương pháp đã có rất nhiều công trình nghiên cứu về tập đỉnh thống trị và ứng dụng của nó, dưới đây là một số phương pháp được đề xuất cho bài toán tìm tập đỉnh thống trị có trọng số nhỏ nhất:
1. Một thuật toán tối ưu hóa đàn kiến cho MWDS [19], 2. Các thuật toán kết hợp phương pháp metaheuristic cho MWDS [17], 3. Một kết hợp các mô hình thuật toán cho MWDS [2], 4. Một thuật toán kết hợp memetic hiệu quả cho bài toán tìm MWDS [14], 5. Tìm kiếm địa phương cho bài toán tìm MWDS với hai mức kiểm tra cấu hình và hàm điểm dựa vào tần suất [26], 6. Một thuật tìm kiếm địa phương hiệu quả cho MWDS trên đồ thị khổng lồ [27], 7. Một thuật toán matheuristic hiệu quả cho MWDS [1], 8. Một thuật toán tìm kiếm bầy đàn nhị phân cho MWDS [13].
Vào năm 2010, phương pháp tối ưu đàn kiến được đề xuất cho bài toán tìm tập đỉnh thống trị (RAKA-ACO). Phiên bản được tối ưu đàn kiến được sử dụng ở trong công bố này là MMAS. Không gian duyệt được tạo thành là các đỉnh của đồ thị, do vậy vết mùi sẽ được lưu trên đỉnh thay vì đặt tại cách cạnh.
Hàm heuristic được sử dụng là tỉ lệ giữa tổng trọng số của đỉnh tự do kề với một đỉnh và trọng số của đỉnh đó. Công thức cập nhật mùi toàn cục không có gì thay đổi so với phiên bản gốc, và việc cập nhật phụ thuộc vào con kiến tìm ra hành trình tốt nhất và lượng thay đổi tỷ lệ nghịch với giá trị độ dài của hành trình đó. Thuật toán không sử dụng thêm các hàm tìm kiếm địa phương để cải thiện lời giải.
Thuật toán đã được thực nghiệp trên hai bộ dữ liệu nhân tạo, và so sánh với hai thuật toán heuristic cơ bản. Kết quả thu được chỉ ra rằng thuật toán tối ưu đàn kiến có chất lượng lời giải tốt hơn 10% đến 20% so với hai thuật toán kia, vì trong các thực nghiệm các thụât toán metaheuristic thường tốt hơn các thuật toán heuristic. Tuy nhiên, so với các thuật toán gần đây thì chất lượng của thuật toán rất kém so với những công bố gần đây. Bên cạnh đó, thời gian thực thi là một vấn đề lớn đối với thuật toán này vì sử dụng bầy đàn để dò tìm và cập nhật lời giải [19].
Năm 2013, việc áp dụng giải thuật di truyền cho bài toán MWDS được đề xuất (HGA). Bên cạnh đó, thuật toán ACO-LS được xuất dựa trến tối ưu đàn
26
kiến việc thay đổi công thức cập nhật mùi, kết hợp với tìm kiếm địa phương. Thuật toán ACO-PP-LS là giống với thuật toán ACO-LS chỉ khác nhau ở phần khởi tạo. Thuật toán HGA sử dụng theo phương thức nguyên mẫu so với phiên bản gốc [17]. Thuật toán sử dụng các hàm heuristic dựa vào trạng thái của các đỉnh hiện tại trong đồ thị để xây dựng tập đỉnh thống trị. Mỗi một đỉnh trong đồ thị sẽ có thể ở một trong ba trạng thái sau: đỉnh thống trị, đỉnh bị thống trị, đỉnh tự do. Trong đó, đỉnh thống trị là đỉnh được thêm vào tập đỉnh để tập đỉnh đó thành tập đỉnh thống trị, đỉnh bị trị là đỉnh kề với ít nhất một đỉnh thống trị, và đỉnh tự do là đỉnh không có kề với bất cứ một đỉnh thống trị nào. Từ đó, 4 hàm heuristic được đề xuất để lựa chọn đỉnh sẽ được lựa chọn làm đỉnh thống trị:
1. Tỉ lệ giữa số lượng các đỉnh tự do liên quan đến một đỉnh và trọng số của đỉnh đó (1.7) với S là danh sách các đỉnh có khả năng được chọn, d(u) là số lượng đỉnh của các đỉnh tự do liên quan đến u và w(u) là trọng số của u,
(1.7)
𝐺1(𝑢) = 𝑚𝑎𝑥𝑢∈𝑆
𝑑(𝑢) 𝑤(𝑢)
2. Tỉ lệ giữa tổng trọng số của các đỉnh tự do liên quan đến một đỉnh và trọng số của đỉnh đó với S là danh sách các đỉnh có khả năng được chọn, W(u) là tổng trọng số của các đỉnh tự do liên quan đến u, và w(u) là tổng số của đỉnh u,
(1.8)
𝐺2(𝑢) = 𝑚𝑎𝑥𝑢∈𝑆
𝑊(𝑢) 𝑤(𝑢)
3. Hiệu giữa tổng trọng số của các đỉnh tự do liên quan đến một đỉnh và trọng số của đỉnh đó (1.9). Với S là danh sách các đỉnh có khả năng được chọn, W(u) là tổng trọng số của các đỉnh tự do liên quan đến u, và w(u) là tổng trọng số của u,
𝐺3(𝑢) = 𝑚𝑎𝑥𝑢∈𝑆(𝑊(𝑢) − 𝑤(𝑢)) (1.9)
4. Tỉ lệ của Tích giữa tổng số đỉnh tự do liên quan đến đỉnh và tổng trọng số của các đỉnh tự do liên quan đến đỉnh với trọng số của đỉnh đó (1.10). Với S là danh sách các đỉnh có khả năng được chọn, d(u)
27
là tổng số đỉnh tự do liên quan đến u, W(u) là tổng trọng số của các đỉnh tự do liên quan đến u, w(u) là trọng số của đỉnh u.
(1.10)
𝑚𝑎𝑥𝑢∈𝑆
𝑑(𝑢)𝑊(𝑢) 𝑤(𝑢)
Thuật toán HGA sử dụng giải thuật di truyền theo phương thức truyền thống với điểm khác là chỉ có một cặp cha mẹ được lựa chọn ngẫu nhiên tạo ra cá thể mới tại mỗi lần lặp. Toán tử tương giao chéo là phần chung giữa bố và mẹ và có thêm phần đột biến gen và kết hợp với toán tử chỉnh sửa là 1 trong 4 hàm heursitic trên để cho cá thể được tạo ra là hợp lệ. Thuật toán sử dụng tìm kiếm địa phương là thuật toán loại bỏ các thành phần dư thừa để làm tối ưu giá trị của các thể vừa mới được tạo ra. Việc cập nhật quần thể không có gì thay đổi so các thuật toán di truyền khác.
Bên cạnh đó, thuật toán ACO-LS là sự kết hợp giữa tối ưu đàn kiến phiên bản MMAS và tìm kiếm địa phương nhưng không sử dụng thông tin heuristic. Lượng cập nhật mùi được thay đổi theo công thức sau (1.11):
𝛿 =
(1.11)
2.0 5.0 + 𝑓 − 𝐹𝑏𝑒𝑠𝑡
Trong đó, f là giá trị đạt được tốt nhất mà đàn kiến tìm được tại lần lặp
hiện tại, Fbest là giá trị tốt nhất cho đến thời điểm hiện tại mà đàn kiến đạt được.
Các thành phần khác của thuật toán không khác so với phiên bản gốc và thuật toán cũng không sử dụng thông tin heuristic. Thuật toán ACO-PP-LS là ACO-LS nhưng sử dụng phần khởi tạo vào trong phần khởi tạo vết mùi tại các đỉnh. Kết quả thực nghiệm đã chỉ ra cả ba thuật toán trên đều tốt hơn cả về chất lượng và thời gian so với thuật toán RAKA-ACO.
Bên cạnh đó, các thuật toán này đều có chất lượng ngang nhau, nhưng các thuật toán dựa vào đàn kiến có thời gian thực thi nhanh hơn thuật toán dựa vào giải thuật di truyền khá nhiều. Tuy nhiên, nếu so với các thuật toán hiện tại cả 3 thuật toán này đều có chất lượng kém hơn nhiều so với các thuật toán công bố gần đây.
Năm 2016, phương pháp kết hợp các mô hình thuật toán với nhau được đề xuất với việc kết hợp sử dụng quần thể, toán tử xóa và toán tử chỉnh sửa tham lam theo phân bố đều (R-PIG). Bên cạnh đó, thuật toán còn kết hợp thêm cả quy
28
hoạch nguyên để cải thiện chất lượng lời giải (Hyb-R-PIG) [2]. Kết quả thực nghiệm cho thấy hai thuật toán này cho chất lượng kết quả tốt hơn nhiều so với các thuật toán trước đây, nhưng vẫn kém so với các thuật toán gần đây. Bên cạnh đó, thời gian các thuật toán có thời gian thực thi khá lâu do thuật toán R- PIG sử dụng quần thể. Ngoài ra, với những bài toán cỡ lớn, việc kết hợp quy hoạch nguyên trở nên ít tác dụng hơn do việc duyệt trong không gian lớn khá tốn thời gian.
Trong cùng năm đó, thuật toán memetic được đề xuất cho bài toán MWDS (HMA) với tốc độ thực thi nhanh hơn 6 lần so với các thuật toán dựa vào tối ưu đàn kiến. Thuật toán này kết hợp của ba thành phần chính là thủ tục xây dựng thích nghi ngẫu nhiên (GRACP), giải thuật di truyền, tìm kiếm địa phương sử dụng phương pháp phạt thích nghi [14]. Phương pháp GRACP được sử dụng cho việc khởi tạo quần thể và trong phần giao phối giữa một cá thể cha và cá thể mẹ. Phương pháp này giúp tạo ra các lời giải đủ tốt cho các bước sau.
Qua mỗi lần lặp, chỉ có một cặp cha mẹ được chọn ngẫu nhiên được sinh con để tiến hóa quần thể. Tiếp theo đó, thuật toán tìm kiếm địa phương được sử dụng để cải thiện chất lượng cá thể con. Việc sử dụng phương pháp hàm phạt thích nghi giúp cho chất lượng của cá thể con tốt hơn, cũng như việc hạn chế không gian tìm kiếm không có lợi. Ngoài ra, phương pháp path relinking được sử dụng để tăng khả năng thăm dò của thuật toán. Thủ tục cập nhật quần thể sử dụng hàm liên quan đến sự khác biệt của cá thể đó với quần thể và chất lượng của cá thể đó. Kết quả thực nghiệm đã chỉ ra thuật toán chạy khá nhanh so với các thuật toán trước đây với chất lượng tốt hơn hẳn các thuật toán từ trước năm 2013.
Năm 2017, thuật toán tìm kiếm địa phương sử dụng cấu hình kiếm tra với hàm điểm dựa trên tần số được sử dụng (CC2FS) [26]. Thuật toán hoạt động khá hiệu quả với chất lượng tốt và thời gian thực thi khá nhanh. Thuật toán chủ yếu gồm hai thao tác chính là xóa hai phần tử thuộc tập đỉnh thống trị và chỉnh sửa lại tập đang xét để thành tập đỉnh thống trị trở lại. Thuật toán sử dụng hàm điểm để lựa chọn phần tử bị xóa hoặc được thêm, nếu đỉnh đó thuộc tập đỉnh thống trị điểm của nó sẽ bị âm, nếu đỉnh và các đỉnh liên quan đến nó bị thống trị điểm của nó sẽ bằng 0, các trường hợp còn lại đỉnh đó có điểm dương.
Việc sử dụng hàm điểm này thuận lợi ở việc, nếu tập đỉnh đang là tập đỉnh thống trị, các đỉnh dư thừa sẽ bị loại bỏ ra khỏi đỉnh thống trị. Nếu không, hai đỉnh thống trị sẽ bị loại bỏ phụ thuộc vào trọng số của nó và tần suất của các
29
đỉnh liên quan đến nó. Các đỉnh được thêm vào cũng như vậy. Việc sử dụng tần suất các đỉnh mà chưa được sử dụng tại mỗi lần thêm đỉnh giúp khuyến khích các đỉnh liên quan đến đỉnh đó được lựa chọn giúp cho việc tìm kiếm tập trung vào những đỉnh giàu tiềm năng hơn.
Việc sử dụng cấu hình kiểm tra kết hợp với danh sách tabu góp phần làm giảm tính chu kỳ hay mắc phải của các thuật toán tìm kiếm địa phương. Cấu hình kiểm tra sẽ cấm không cho đỉnh vừa bị xóa được thêm vào, khuyến khích các đỉnh liên quan đến nó được chọn khiến cho nó ít có khả năng quay trở lại làm đỉnh thống trị. Danh sách tabu sẽ cấm không cho các đỉnh vừa được thêm vào bị xóa đi. Thực nghiệm đã chứng minh thuật toán chạy tốt với các bộ dữ liệu đã dùng và việc đạt chất lượng vượt trội so với các thuật toán trước đây trong một thời gian ngắn.
Năm 2018, mô hình matheuristic được đề xuất là việc kết hợp thuật toán tìm kiếm địa phương sử dụng danh sách tabu với quy hoạch nguyên (HTS-DS) [1]. Điểm nổi bật của thuật toán là sử dụng hàm phạt theo giá trị của tập đỉnh hiện tại vào số lượng của các đỉnh chưa bị thống trị. Hàm phạt ở trên cho phép duyệt bài toán trong vùng không gian không hợp lệ, giúp loại bỏ các ràng buộc của tập đỉnh thống trị. Tại mỗi bước lặp, ba toán tử được sử dụng gồm có phép thêm một đỉnh, phép xóa một đỉnh và phép đổi trạng thái của hai đỉnh cho nhau. Tất cả các phép biến đổi này đều được ước lượng giá trị bởi hàm phạt ở trên. Việc lựa chọn toán tử tiếp theo sẽ phụ thuộc vào giá trị của phép biến đổi đó và danh sách tabu.
Bên cạnh đó, để hạn chế việc mắc kẹt trong một vùng tìm kiếm hoặc vùng tìm kiếm đó không có giá trị đáng kể. Thuật toán sử dụng phương pháp xóa một lượng lớn các đỉnh thống trị và thay thế bằng các đỉnh khác theo một quy luật nhất định sau mỗi một khoảng thời gian ngắn cố định, điều này góp phần làm thay đổi điểm đang duyệt cách một khoảng không quá xa so với điểm duyệt trước đó. Kích thước của danh sách tabu được lựa chọn trong bài cố định và tham số thực tế vừa đủ để việc duyệt tập trung hơn vào vùng được xét duyệt thay vì đi sang vùng xét duyệt khác một nhanh chóng.
Sau khi kết thúc việc sử dụng tìm kiếm địa phương, bài toán quy hoạch nguyên rút gọn được xây dựng từ tần số của các đỉnh được lựa chọn làm đỉnh thống trị. Mỗi bài toán quy hoạch nguyên rút gọn được giải với ràng buộc về thời gian. Mục đích của việc giải quyết bài toán rút gọn này nhằm tìm ra lời giải tốt hơn sau khi đã thực thi phần tìm kiếm địa phương. Kết quả thực nghiệm đã
30
chỉ ra thuật toán chạy tốt hơn rất nhiều so với các thuật toán trước đây cả về chất lượng và thời gian. Thực nghiệm còn chỉ ra là thuật toán thu được kết quả tốt hơn trong khoảng thời gian ngắn hơn so với thuật toán CC2FS chạy trong 1000s.
Trong cùng năm đó, thuật toán nhị phân tìm kiếm theo bầy đàn được đề xuất cho MWDS (BPSO) [13]. Thuật toán sử dụng thuật toán bầy đàn và tìm kiếm với số lượng hàng xóm lớn để cải thiện chất lượng của đàn. Tại mỗi lần lặp, chỉ một cá thể ngẫu nhiên được thay đổi vị trí bằng các toán tử liên quan đến vị trí của cá thể tốt nhất và nó. Thực nghiệm đã chỉ ra thuật toán chay khá nhanh so với thuật toán HMA. Tuy nhiên, chất lượng lời giải của BPSO bị giảm một chút so với thuật toán HMA.
1.3 Các ứng dụng liên quan đến bài toán tập đỉnh thống trị
Bài toán tìm tập đỉnh thống trị là bài toán lõi quan trọng trong nhiều nghiên cứu về các ứng dụng thực tế. Các ứng này liên quan đến các mạng lưới hay các đồ thị được tạo thành từ nhu cầu nguời dùng trong thực tế. Các ứng dụng này đòi hỏi tìm ra một tập các đỉnh hoặc các tập các thành phần cơ bản mà có ảnh hưởng tới toàn bộ mạng lưới. Khi xác định được các thành phần này, việc tìm hiểu thiết kế mạng lưới sẽ cải tiến hơn do các thứ quan trọng thường liên quan đến những thành phần này. Bên cạnh đó, sự tác động lên trên các thành phần này có thể giúp người dùng tác động lên toàn bộ phần còn lại của hệ thống. Các ứng dụng có sử dụng tập đỉnh thống trị gồm có:
1. ứng dụng trong mạng cảm biến không dây cho việc tiết kiệm năng lượng
giúp tăng tuổi thọ của hệ thống,
2. ứng dụng trong phân tích và sử dụng mạng xã hội hiệu quả, 3. ứng dụng trong xử lý văn bản, trích rút thông tin quan trọng.
Các mạng cảm biến không dây đang ngày càng đóng góp nhiều vai trò trong các ứng dụng gồm: theo dõi sức khỏe, thời tiết, môi trường, phát hiện đe dọa như cảnh báo an ninh, cháy nhà, cháy rừng, mạng cảm biến trong ô tô. Trong đó, hệ thống theo dõi sức khỏe người dùng gồm một mạng cảm biến được bố trí xung quanh không gian sống, hoặc gắn lên trên một số vị trí trên cơ thể người để theo dõi các dữ liệu cần thiết mà từ đó, sau một quá trình xử lý từ các máy trung tâm, các thông tin quan trọng được trích rút mà từ đó người ta biết được thể trạng và tính hình sức khỏe của con người. Các thông số trích rút được gồm, nhịp thở, nhịp tim, lượng calo tiêu thụ, dữ liệu về rèn luyện mỗi ngày.
31
Bên cạnh đó, người ta còn đo được cả lượng mỡ, lượng cơ trên cơ thể con người để giúp họ có thể tùy chỉnh lối sống cải thiện sức khỏe cho phù hợp nhất với công việc và môi trường của họ. Hệ thống cảm biến theo dõi thời gian là hệ thống các cảm biến về nhiệt độ, tốc độ gió, độ âm, lượng mưa, được bố trí tại các khu vực thí điểm tạo thành hệ thống mạng lưới để theo dõi tình hình thời tiết của một khu vực giúp cho việc dự đoán dự báo thời tiết chính xác hơn. Hệ thống cảm biến môi trường theo dõi mức độ ô nhiễm đất đai, nguồn nước, không khí với việc thiết lập một hệ thống mạng lưới các cảm biến trong các vùng và đối tượng cần thiết như rừng, sông ngòi, các nút thắt giao thông để có thể ứng phó và xử lý kịp với tình trạng rác thải công nghiệp tăng nhanh như hiện nay.
Các cảm biến theo dõi an ninh, cháy nhà, cháy rừng được thiết lập tại các vị trí cần thiết để có thể theo dõi an ninh của khu vực, mức độ khói, bức xạ nhiệt để có thể phát hiện kịp thời giúp cho đội an ninh, cứu hỏa có mặt đúng nơi đúng lúc làm giảm thiểu thiệt hại do kẻ xâm nhập, các tình huống cháy nổ gây ra. Cuối cùng, các hệ thống cảm biến trên ô tô là hệ thống các cảm biến gia tốc, âm thanh, ánh sáng, hình ảnh, ... để theo dõi tình trạng hiện tại của ô tô hoặc môi trường xung quanh giúp cho hệ điều khiển trên xe tùy chỉnh toàn bộ các thiết bị trên xe cho phù hợp nhất với môi trường hiện tại. Người lái xe dựa vào các thông tin trên để có thể xử lý cho phù hợp với hoàn cảnh hiện tại.
Các cảm biến được sử dụng hình thành hệ thống mạng lưới các cảm biến không dây. Hệ thống này hoạt động trong một khu vực lớn như các hệ thống ngoài trời, tại các nhà ga, trong điều kiện năng lượng hạn chế. Do vậy, việc điều khiển mạng lưới hệ thống này hoạt động hiệu quả sẽ làm tăng hiệu suất của mạng và đặc biệt là thời gian sống của mạng này. Mỗi một cảm biến không dây có lượng năng lượng nhất định vì vậy khi hoạt động trên mạng nó có thể chuyển sang chế độ ngủ để tiết kiệm năng lượng và thức dây khi cần thiết.
Thông tin và sự điều khiển cảm biến trong một số trường hợp không thể truyền về trạm trung tâm xử lý mà cần xử lý tại chính địa điểm đó. Hai vấn đề trên có thể xử lý bằng việc chọn một tập các cảm biến trong hệ thống mạng lưới đó để làm nốt điều khiển phần còn lại. Từ đây, bài toán liên quan đến tập đỉnh thống trị được áp dụng để có thể tìm ra tập cảm biến tốt nhất làm nốt điều khiển [6][15] [18] [22].
Mạng xã hội cũng là một trong những lĩnh vực có nhiều ứng dụng cho tập đỉnh thống trị. Mỗi một mạng xã hội liên kết người dùng INTERNET với nhau qua mọi vùng miền bất kể khoảng cách mọi lúc mọi nơi. Thông qua mạng xã
32
hội, các bạn trẻ có thể trao đổi thông tin cho nhau. Lứa đôi có thể nhắn tin hẹn hò với nhau, và hơn nữa các bạn trẻ có thể tìm kiếm bạn bè và tình yêu cho chính mình. Các thanh niên lao động thông qua mạng xã hội có thể kết nối với cha mẹ hỏi thăm tình hình sức khỏe của cha mẹ. Mạng xã hội còn tạo ra cơ hội để cho những người trẻ có cùng ý tưởng tụ tập lại với nhau cùng nhau trao đổi những thông tin bổ ích.
Người dùng có thể đưa ra các thông tin xã hội và từ đó sẽ lan truyền đến các người dùng khác theo nhiều hình thức khác nhau. Chẳng hạn, thông tin đắc cử của tổng thống Mỹ có thể lan truyền đến hàng triệu người dùng mạng xã hội với chỉ một vài bài viết nhỏ. Hiện nay, với hàng tỷ lượt người dùng mỗi tháng, các mạng xã hội đang là mảnh đất màu mỡ cho các dịch vụ kinh doanh và quảng cáo. Các bạn trẻ có thể buôn bán một số thứ như quần áo, giầy dép qua mạng xã hội để kiếm thêm thu nhập cũng như học hỏi về cách kinh doanh.
Các công ty tìm đến mạng xã hội để nhờ tiếp thị sản phẩm. Nếu như bạn từng xem youtube.com thì sẽ thấy được cứ mỗi phút lại có một đoạn quảng cáo xuất hiện. Mỗi đoạn quảng cáo này trị giá từ vài triệu cho đến cả trăm triệu. Doanh thu đến từ quảng cáo từ mạng xã hội là rất lớn. Các mạng xã hội lớn nhất hành tinh có thể kể đến facebook.com, qq.com, youtube.com, ...
Ngoài ra, phân tích mạng xã hội sẽ cho bạn biết được sở thích hành vi của người dùng từ đó sử dụng để truyền đạt các thông tin thích hợp làm tăng mức độ ảnh hưởng của bạn đến các người dùng khác. Một số bài toán đã được nghiên cứu trên mạng xã hội gồm có: bài toán tập đỉnh thống trị trên mạng xã hội, sự ảnh hưởng tích cực của tập đỉnh thống trị qua mạng xã hội, bài toán về mức độ lan truyền trên mạng xã hội, và bài toán tối đa hóa mức độ lan truyền qua mạng xã hội [10], [11], [24], [25].
Tóm tắt văn bản theo yêu cầu của người dùng là một trong những chủ đề đáng được quan tâm, do mức độ gia tăng về số lượng và kích cỡ văn bản trong thời đại công nghiệp hóa hiện đại hóa. Việc tóm tắt văn bản sẽ giúp cho người sử dụng tránh phải tiếp cận với những thông tin dư thừa, tập trung vào những thông tin quan trọng giúp cho họ nhanh nắm bắt thông tin. Điều này giúp cho họ nhanh tiếp cận các vấn đề và phân loại vấn đề làm giảm thời gian ra quyết định. Ngoài ra, việc tạo ra các văn bản cũng thể được giải quyết giống cách giải quyết của việc tóm tắt văn bản nhưng theo hướng ngược lại.
33
Các bài toán trên hoàn toàn có thể được mô hình hóa thành các đồ thị và giải quyết bằng các phương pháp liên quan đến tập đỉnh thống trị. Tóm tắt văn bản có nhiều mức độ khác nhau như tách các từ khóa quan trọng, tóm tắt văn bản, hoặc tóm tắt một nhóm các văn bản có chung một chủ đề. Chẳng hạn, bạn học đọc tiếng anh hàng ngày, xác định từ khóa là một trong những thứ căn bản cần nắm vững. Thông thường bạn sẽ mất khoảng 2-3 phút cho một đoạn văn bản ngắn và từ 5-10 phút cho một bài báo. Với tóm tắt tự động bạn chỉ cần một lần bấm, trong khoảng thời gian ngắn các từ khóa đã được đánh dấu xong. Ngoài ra, tóm tắt văn bản còn có thể giúp bạn tạo các văn bản điều tra về một vấn đề gì đó nhanh chóng với việc kê khai các thông tin quan trọng đến từ các văn bản đầu vào. Hiện nay, tập đỉnh thống trị đã được áp dụng trong tóm tắt đa văn bản đã [21].
1.4 Một số định lý quan trọng
1.4.1 Đinh lý Cook-levin
Trong lý thuyết về độ phức tạp tính toán, các lớp bài toán được con người xem xét và xử lý chủ yếu thuộc lớp các bài toán NP được quan tâm và dành rất nhiều nghiên cứu từ khi khoa học máy tính phát triển, trong đó các bài toán loại này được chia thành hai lớp:
1. lớp bài toán P: là các bài toán kiểm tra hiệu quả trong thời gian đa
thức,
2. lớp bài toán NP-complete: là các bài toán còn lại không thuộc lớp P và mọi bài toán NP khác đều có thể rút gọn về bài toán đó thông qua phép biến đổi xấp xỉ.
Bài toán thỏa mãn biểu thức logic (SAT) là bài toán đầu tiên được chứng minh là bài toán NP-complete, dựa vào 2 định lý được đưa ra trong [4].
Định lý 1.1 Nếu một tập xâu S là chấp nhận được bởi một số máy Turing phi tất định trong thời gian đa thức, thì S là rút gọn được trong thời gian đa thức về bài toán DNF tautologies.
Định lý 1.2 Các bài toán sau là rút gọn được trong thời gian đa thức cho nhau (và do vậy mỗi bài toán đều có chung độ mức độ khó đa thức): tautologies, DNF tautologies, D3, subgraph pairs.
Ngay sau khi định lý được đưa ra, tập hợp 21 bài toán quan trọng nhất của lớp bài toán NP-complete được trình bày bởi R.Karp [9]. Trong các bài toán đó
34
có các bài toán tập phủ, bài toán người đưa thư, bài toán quy hoạch nguyên, bài toán đỉnh phủ là một trong số chúng. Các bài toán tập phủ và đỉnh phủ có mối quan hệ khá gần gũi với bài toán tập đỉnh thống trị. Cho đến bây giờ, một câu hỏi nổi tiếng được đặt ra liệu tập P, NP là một vẫn chưa được giải quyết và đây là một câu hỏi chưa được giải quyết quan trọng nhất của ngành khoa học máy tính.
1.4.2 Định lý không có bữa trưa miễn phí
Các nhà nghiên cứu đã cố gắng tìm ra giải quyết lớp bài toán NP- complete bằng các phương pháp xấp xỉ, với các công bố khác nhau so sánh các thuật toán xem thuật toán nào tốt hơn thuật toán nào để giải quyết vấn đề này. Trong một khoảng thời gian dài, rất nhiều nghiên cứu ứng dụng các thuật toán metaheursitic để giải quyết các bài toán tối NP-complete.
Họ luôn so sánh xem thuật toán nào là tốt nhất, chẳng hạn việc so sánh tối ưu giữa các thuật toán tối ưu bầy đàn, tối ưu đàn kiến, giải thuật di truyền. Để chứng minh thuật toán nào tốt nhất, họ sử dụng một lượng hữu hạn các bộ dữ liệu mà họ tạo ra hoặc thu được từ các đo đạc trong thực tế. Cuộc tranh luận kéo dài cho đến khi định lý không có bữa trưa miễn phí cho tìm kiếm và tối ưu ra đời vào năm 1995 và 1997 [28], [29].
Định lý 1.3 hai thuật toán bất kỳ có hiệu suất trung bình như nhau cho
toàn bộ các vấn đề có thể có.
Đinh lý trên cho chúng ta biết bất kỳ thuật toán nào có hiệu suất tốt trên một số tập dữ liệu sẽ phải trả một cái giá về sự giảm hiệu năng trên các tập dữ liệu còn lại. Cuộc tranh luận về các thuật toán nào tốt hơn chấm dứt. Bên cạnh đó, các công bố trên còn cho phép cách áp dụng định lý bữa trưa miễn phí vào để ước lượng hiệu năng của thuật toán cho một số vấn đề nhất định.
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
2.1 Thuật toán HLNS
Thuật toán HLNS là sự kết hợp giữa thuật toán LNS và GRASP để giải quyết bài toán MWDS. Thuật toán LNS khắc phục nhược điểm của các thuật toán tìm kiếm địa phương với việc bị lặp bởi các chu trình hoặc mắc kẹt tại các nghiệm cục bộ như các thuật toán tìm kiếm địa phương với sự thay đổi nhỏ từ điểm duyệt trước đến điểm duyệt sau. Bên cạnh đó, thuật toán có khả năng nhanh tìm kiếm lời giải tốt hơn các thuật toán tìm kiếm địa phương khác. Do vậy ngay cả trong trường hợp các thuật toán tìm kiếm địa phương kia có sử dụng các kỹ thuật thoát khỏi nghiệm cục bộ. Thuật toán 3 được áp dụng cho bài toán MWDS.
Procedure Thuật toán HLNS
Đồ thị G= (V, E) với trọng số W
Input
Begin
1. Khởi tạo lời giải S; // dựa vào thuật toán 2
2. S*← S;
3. while (chưa hết thời gian tìm kiếm) do 4. for i in (1, k) do
5. Si ← DEL(S); //xóa ngẫu nhiên phân bố đều dùng
thuật toán 3
6. Si ← REPAIR(Si);// tạo ra lời giải hợp lệ 7. end-for 8. S** là lời giải tốt nhất từ S1, …, Sk
9. if (S** tối ưu hơn S*) then
10. S*← S**;
11. end-if
12. S ← S**;
13. end-while;
14. Đưa ra lời giải S*;
36
End;
Thuật Toán 3: Thuật toán HLNS
Thuật toán HLNS sử dụng thuật toán 4 để khởi tạo. Việc khởi tạo không yêu cầu chất lượng lời giải phải quá tốt, chỉ yêu cầu khởi tạo nhanh. Thuật toán sử dụng phép toán DEL_REDUANT nên chất lượng lời giải không quá tệ.
Thuật toán HLNS duyệt trong không gian duyệt theo phương pháp đi đến điểm tốt nhất trong các lời giải được tạo thành sau các phép xóa và sửa. Trong đó, thuật toán phép DEL và REPAIR để tạo ra k lời giải hai lời giải S1, S2, …, Sk tại mỗi bước tìm kiếm của thuật toán. Trong đó, phép DEL xóa các đỉnh một cách ngẫu nhiên với phân bố đều trong tập đỉnh đang xét. Thuật toán REPAIR áp dụng thuật toán GRASP với đầu vào là tập đỉnh chưa phải là tập đỉnh thống trị và thêm vào các đỉnh cho đến khi hợp lệ.
Thuật toán lựa chọn điểm duyệt tiếp theo là lời giải tốt nhất trong số các lời giải S1, S2, …, Sk làm điểm duyệt tiếp theo. Ngoài ra, thuật toán còn có thể mở rộng bằng việc thêm các phép xóa, sửa và kết hợp lại với nhau để có thể tạo nhiều kiểu thành viên hơn, làm cải thiện chất lượng lời giải. Tuy nhiên, trong luận văn này chỉ sử dụng hai phép toán tử xóa DEL, và sửa REPAIR.
2.2 Thuật toán khởi tạo cho tập đỉnh thống trị
Thuật toán khởi tạo sử dụng việc thêm đỉnh ngẫu nhiên theo phân bố đều với xác suất 𝛾. Giá trị của 𝛾 ∈ (0, 1), giá trị càng cao càng nhiều đỉnh được lựa chọn, giá trị càng thấp càng ít đỉnh được lựa chọn. Sau đó, toán tử REPAIR được sử dụng để thêm vào các đỉnh để tạo ra lời giải hợp lệ.
Procedure Thuật toán khởi tạo
Begin
1. S ←{}; 2. For u in (1, n) do 3. If rand() < 𝛾 then 4. S ←S ∪ {u}; 5. End-if 6. End-for
7. S ← REPAIR(S);
37
8. Đưa ra lời giải S;
End;
Thuật Toán 4: Thuật toán khởi tạo tập đỉnh
2.3 Các thuật toán xóa các đỉnh trong tập đỉnh thống trị
Thuật toán DEL dùng để xóa các đỉnh trong lời giải S để tạo ra lời giải không chấp nhận được S−. Các phần tử thuộc danh sách S có khả năng bị loại bỏ như nhau với cùng một xác suất delta β. Số lượng ứng viên bị xóa trung bình phụ thuộc vào số lượng phần tử ban đầu trong S và β theo công thức xác định kỳ vọng. Thuật toán có ưu điểm là tạo cơ hội ngang nhau cho tất cả các nhánh có thể được tạo ra từ S. Thuật toán DEL được trình bày trong thuật toán 5.
Procedure Thuât toán xóa đỉnh ngẫu nhiên DEL
một tập đỉnh thống trị S
Input
Begin
1. S- ← S
2. for (đỉnh u in S) do
3. if rand() < β then
4. S- ← S- / {u};
5. end-if;
6. end-for;
7. Đưa ra S-;
End;
Thuật Toán 5: Thuật toán xóa đỉnh DEL
2.4 Các thuật toán sửa tập đỉnh
Phép toán REPAIR sử dụng lời giải S− làm đầu vào, đây là các lời giải tạo thành do các đỉnh bị xóa từ lời giải chấp nhận được (xem thuật toán 6). Tiếp theo, phép toán sẽ thêm vào các đỉnh để tạo ra lời giải S. Quá trình kết thúc khi S là một tập đỉnh thống trị. Tại mỗi bước thêm đỉnh, thuật toán sẽ chọn đỉnh v một đỉnh tự do để tạo danh sách là các đỉnh kề với đỉnh v là Rv. Hàm G2 sẽ được sử dụng để đánh giá chất lượng của đỉnh trong danh sách Rv. Đỉnh có chất lượng ước lượng lớn nhất trong danh sách Rv được lựa chọn với xác xuất µ, nếu
38
không danh sách giới hạn RCL gồm (α * kích thước của Rv) đỉnh có chất lượng tốt nhất được được tạo thành, đỉnh được chọn là đỉnh ngẫu nhiên trong RCL.
Procedure Thuật toán thêm đỉnh REPAIR
Một tập đỉnh S-
Input
Begin
1. S ← S-
2. while (S chưa phải là một tập đỉnh thống trị) do
3. v ← chọn một đỉnh chưa bị trị 4. Rv ← là các đỉnh kề với v 5. P ← {G2(Rvi) | Rvi ∉ S}
6. if rand() < µ then 7. u ← đỉnh Rvi với P(Rvi) đạt giá trị lớn nhất 8. else 9. RCL ← (α * kích thước của Rv) đỉnh có chất lượng tốt nhất 10. u ← phần tử ngẫu nhiên trong RCL 11. end-if
12. S← S∪ u
13. end-while
14. S ←DEL-REDUNDANT(S);
15. Đưa ra lời giải S;
End;
Thuật Toán 6: Thuật toán thêm đỉnh REPAIR
2.5 Các thuật toán xóa bỏ đỉnh dư thừa trong tập đỉnh thống trị
Cuối cùng, thuật toán DEL-REDUNDANT xóa bỏ thành phần dư thừa để cải thiện lời giải (xem thuật toán 7). Thuật toán duyệt lần lượt các đỉnh thống trị trong S, nếu đỉnh đó và các đỉnh kề với nó bị thống trị bởi các đỉnh khác thì đỉnh đó là đỉnh dư thừa, thuật toán sẽ loại bỏ đỉnh đó. Việc loại bỏ các đỉnh dư thừa sẽ cải thiện chất lượng lời giải. Tuy nhiên, chiến thuật toán bỏ khác nhau có thể cải thiện chất lượng tập đỉnh khác nhau, chẳng hạn như việc xóa đỉnh lần lượt
39
một cách ngẫu nhiên hoặc theo một hàm ước lượng đánh giá nào đó. Bên cạnh đó, các thuật toán xóa bỏ các đỉnh dư thừa có thể được sử dụng phối hợp lẫn nhau để cải thiện chất lượng lời giải, không nhất thiết phải có định một chiến thuật loại bỏ đỉnh dư thừa.
Cụ thể, thuật toán tạo ra một danh sách R các đỉnh có khả năng là đỉnh dư thừa trong tập đỉnh thống trị. Thuật toán sẽ lựa chọn ngẫu nhiên đỉnh trong danh sách R và xóa đỉnh đó trong tập đỉnh thống trị nếu đỉnh đó là đỉnh dư thừa. Thuật toán kết thúc khi danh sách R là danh sách trống rỗng (xem thuật toán 7).
Procedure Thuật toán DEL-REDUNDANT
Một tập đỉnh thống trị S
Input
Begin
1. Sopt← S; 2. R ← danh sách các đỉnh có khả năng loại bỏ khỏi S
3. While R không rỗng do
4. u ← đỉnh được chọn ngẫu nhiên trong R 5. if u là đỉnh dư thừa then
6. Sopt← Sopt / {u};
7. end-if; 8. R ← R / {u}
9. end-for;
10. Đưa ra lời giải Sopt
End;
Thuật Toán 7: Thuật toán DEL-REDUNDANT
40
Chương 3. Thực nghiệm
2.1 Giới thiệu thực nghiệm
Chương này trình bày về thực nghiệm của thuật toán HLNS để so sánh hiệu năng của thuật toán so với các thuật toán khác. Chương trình được thử nghiệm trên máy tính intel core-i7-8700 CPU 3.20 GHz, 6 cores, 12 threads và bộ nhớ RAM 8 Gb. Chương trình được thực thi trên hệ điều hành LINUX, ngôn ngữ java 1.8. Mọi lần thử nghiệm đều được tiến hành trên một luồng.
Chương trình được thử nghiệm trên hai bộ dữ liệu DIMACS và BHOSLIB được lấy tại địa chỉ: https://w1.cirrelt.ca/∼vidalt/en/research-data.html. Trong đó bộ dữ liệu DIMACS là bộ dữ liệu của viện toán học thuộc trung tâm toán học rời rạc và khoa học máy tính Rutgers (http://dimacs.rutgers.edu/). Đây là bộ dữ liệu được công bố để thực hành các thuật toán cho một số vấn đề mà trung tâm đưa ra. Bộ dữ liệu BHOSLIB được lấy từ dữ liệu thuôc học viện hàng không vũ trụ Bắc Kinh (http://www.buaa.edu.cn/). Đây là bộ dữ liệu dành cho các vấn đề liên quan đến đồ thị để thử nghiệm hiệu năng của các bài toán (Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring). Thuật toán được thử nghiệm trên 51 dữ liệu thuộc bộ dữ liệu DIMACS và 41 dữ liệu thuộc bộ dữ liệu BHOSLIB. Số lượng các đỉnh và cạnh thuộc hai bộ dữ liệu trên từ 200 đến 4000 đỉnh và số cạnh từ 200 đến 1 triệu cạnh. Thuật toán thử nghiệm với trường hợp trọng số các đỉnh theo công thức w(u) = u mod 200 + 1.
Các trọng số được sử dụng trong thuật toán lần lượt trong bảng (3.1). Các trọng số trên được hiệu chỉnh thông qua các thực nghiệm khởi đầu và được lựa chọn cho đến khi các tham số phù hợp.
Bảng 1: Tham số cấu hình cho HLNS
Thông số
Ký hiệu
Giá trị
Số lượng lời giải trong lần duyệt
k
4
Ngưỡng để chọn cho danh sách giới hạn
0.3
𝛼
41
Xác suất để xóa một đỉnh thống trị
𝛽
Từ 0.2 đến 0.4
Xác xuất để khởi tạo tập đỉnh
0.1
𝛾
Xác xuất để lựa chọn cách chọn đỉnh
µ
0.9
Có hai thông số chính để đánh giá thuật toán là giá trị tốt nhất fbest và giá trị
trung bình faverage thu được của thuật toán được cho bởi hai công thức (3.1), (3.2).
𝑓𝑏𝑒𝑠𝑡 = 𝑚𝑖𝑛(𝑓1, 𝑓2, … , 𝑓𝑝) (3.1)
𝑝
(3.2)
𝑓𝑎𝑣𝑒𝑟𝑎𝑔𝑒 =
1 𝑝
∑ 𝑓𝑖 𝑖=1
trong đó fi là kết quả của lần chạy thứ i, p là số lần chạy thuật toán.
Thuật toán được so sánh với các thuật toán tốt nhất hiện nay cho bài toán MWDS là CC2FS, và HTS-DS. Các bảng 2, 3 đưa ra kết quả so sánh của các thuật toán này. Trong đó, các kết quả thực nghiệm của CC2FS, HTS-DS được lấy từ công bố [1]. Theo đó, CC2FS được chạy gần 1000s, còn HTS-DS thực thi với thời gian ít hơn. Từ các kết quả của các bảng 2, 3, ta thấy rõ ràng thuật toán HLNS vượt trội hơn nhiều so với tất cả các thuật toán đã đuợc công bố cả về chất lượng và thời gian thực thi.
Thực nghiệm được bố trí thành 2 loại thử nghiệm:
TH1: Thực nghiệm trên bộ dữ liệu DIMACS với w(u) = u mod 200 + 1,
TH2: Thực nghiệm trên bộ dữ liệu BHOSLIB với w(u) = u mod 200 + 1.
2.2 Kết quả thực nghiệm
2.2.1 Thực nghiệm trên TH1
Trên bộ dữ liệu DIMACS với trọng số w(u) = u mod 200 + 1, chúng ta thấy rõ ràng thuật toán HLNS vượt trội hơn hẳn so với các thuật toán còn lại về cả chất
42
lượng lời giải và tốc độ thực thi. Thuật toán CC2FS kém hơn rõ rệt so với các thuật toán còn lại về chất lượng. Trong khi các thuật toán HLNS chạy ổn định trên hầu hết bộ dữ liệu thực nghiệm và tốt hơn HTS-DS.
Bảng 2: Kết quả thực nghiệm trên TH1
Bộ Dữ Liệu CC2FS HTS-DS HLNS STT Name Best Avg Best Avg Time Best Avg Time |V | |E|
1 brock200_2 200 10024 23 23 0.14 23 23 23 23 0.10
2 brock200_4 200 6811 68 68 0.23 68 68 68 68 0.10
3 brock400_2 400 20014 65 65 0.91 65 65.4 0.12 65 65
4 brock400_4 400 20035 75 75 1.1 75 75 75 75 0.13
5 brock800_2 800 111434 28 28 5.19 28 28 28 28 1.73
6 brock800_4 800 111957 31 31 13.98 31 31 31 31 1.70
7 C1000.9 1000 49421 194.8 191 191 14.87 191 191.1 191 1.09
8 C2000.5 2000 999164 10 10 49.81 10 10 10 10 24.86
9 C2000.9 2000 199468 130 130 38.85 130 130 130 130 3.94
10 C250.9 250 3141 235 235 0.18 235 235 0.24 235 235
11 C4000.5 500 12418 9 9 9 214.9 9 9 9 110.26
12 c-fat200-1 200 1534 226 226 226 226 0.05 226 226 0.12
13 c-fat200-2 200 3235 57 57 0.07 57 57 0.17 57 57
14 c-fat200-5 200 8473 9 9 0.08 9 9 0.15 9 9
15 c-fat500-1 500 4459 522 522 0.31 522 522 522 522 0.19
16 c-fat500-2 500 9139 261 261 0.34 261 261 261 261 0.21
17 c-fat500-5 500 23191 20 20 0.52 20 20 20 20 0.30
18 gen200-p0.9-44 200 1990 458 458 2.54 458 464.9 470 470 0.04
19 gen200-p0.9-55 200 1990 433 433 0.15 433 433.3 433 433 0.03
20 gen400-p0.9-55 400 7980 284 284 0.2 284 284.2 288 288 0.09
21 gen400-p0.9-65 400 7980 287 287 0.86 287 290.2 287 287 0.10
22 gen400-p0.9-75 400 7980 307 307 1.15 307 307 307 307 0.09
23 86 86 0.37 86 86 1.75 86 86 hamming10-4 1024 89600
24 hamming8-2 256 1024 5.24 1744 1744 1737 1737 1737 1738.3 0.43
25 hamming8-4 256 11776 68 68 0.28 68 68 0.45 71 71
26 johnson32-2-4 496 14880 192 192 0.53 192 192 192 192 0.41
27 keller4 171 5100 220 220 1.07 220 220 220 220 0.21
28 keller5 776 74710 181 181 0.34 181 181.9 1.42 182 182
29 keller6 80 80 12.12 80 80 30.18 80 80 3361 1026582
30 405 405 0.13 405 405 405 405 MANN_a27 378 702 0.07
31 0.84 1080 1080 MANN_a45 1035 1980 1080 1080 1080 1080 0.13
32 8.58 3402 3402 MANN_a81 3321 6480 3402 3402 3402 3402 0.24
33 32.04 56 56 39.50 p-hat1500-1.clq 1500 284923 56 56 56 56
34 30.51 14 14 87.33 p-hat1500-2.clq 1500 568960 14 14 14 14
43
35 p-hat1500-3.clq 1500 847244 5 5 5 5 31.24 5 5 156.18
36 p0-hat300-1.clq 300 10933 99 99 99.6 99 0.53 99 99 0.29
37 p-hat300-2.clq 300 21928 31 31 31 31 0.43 31 31 0.35
38 p-hat300-3.clq 300 33390 8 8 8 8 0.48 8 8 0.52
39 p-hat700-1.clq 700 60999 67 67 67 67 3.43 67 67 7.24
40 p-hat700-2.clq 700 121728 21 21 21 21 2.98 21 21 10.40
41 p-hat700-3.clq 700 183010 6 6 6 6 3.21 6 6 2.36
42 san1000 1000 250500 8 8 8 8 55.31 6 6 3.11
43 san200-0.7-1 200 5970 73 73 73 73 0.17 73 73 0.22
44 san200-0.7-2 200 5970 53 53 53 53 0.17 53 53 0.19
45 san200-0.9-1 200 1990 368 368 368 368 0.04 368 368 0.16
46 san200-0.9-2 200 1990 406 406 406 406 0.06 406 406 0.15
47 san200-0.9-3 200 1990 328 328 328 328 0.05 328 328 0.16
48 san400-0.5-1 400 39900 16 16 16 16 0.73 16 16 0.73
49 san400-0.7-1 400 23940 44 44 44 44 0.71 44 44 0.56
50 san400-0.7-2 400 23940 42 42 42 42 0.56 42 42 0.52
51 san400-0.7-3 400 23940 40 40 40 40 0.76 40 40 0.51
2.2.2 Thực nghiệm trên TH2
Trên bộ dữ liệu BHOSLIB với trọng số w(u) = u mod 200 + 1, chúng ta thấy rõ ràng thuật toán HLNS chạy tốt hơn hoàn toàn so với thuật toán CC2FS về chất lượng lời giải. Thuật toán HLNS có chất lượng tốt hơn và tốt độ nhanh hơn so với thuật toán HTS-DS, cụ thể các bộ dữ liệu frb45-21-5, frb50-23-5, frb59-26- 2, frb59-26-3, frb59-26-4 đều có chất lượng và thời gian thực thi tốt hơn.
Bảng 3: Kết quả thực nghiệm trên TH2
Bộ Dữ Liệu CC2FS HTS-DS HLNS STT Name |V| |E| Best Avg Best Avg Time Best Avg Time
1 frb30-15-1 450 17827 214 212 214 212 12.96 212 212 0.53
2 frb30-15-2 450 17874 242 242 242 242 4.46 242 242 0.53
3 frb30-15-3 450 17809 175 175 175 175 6.75 175 175 0.54
4 frb30-15-4 450 17831 166 166 167 166 4.54 166 167.2 0.49
5 frb30-15-5 450 17794 160 160 160 160 5.39 160 160 0.46
6 frb35-17-1 595 27856 274 274 274 274 13.88 274 274 0.76
7 frb35-17-2 595 27847 208 208 208 208 5.66 208 208.8 0.69
8 frb35-17-3 595 27931 201 201 201 201 6.11 201 201 0.75
9 frb35-17-4 595 27842 287 286 287 286 16.47 286 286 0.74
10 frb35-17-5 595 28143 295 295 297 295 3.97 295 295.4 0.69
11 frb40-19-1 760 41314 262 262 262 262 6.3 262 262 0.92
12 frb40-19-2 760 41263 243 243 244 243 25.05 243 243 1.03
44
250 250 24.52 250 251.3 13 frb40-19-3 760 41095 252 252 1.06
22.39 250 250 0.99 14 frb40-19-4 760 41605 250 250 249 249
272 272 19.84 272 272 15 frb40-19-5 760 41619 272 283 1.03
328 328 23.98 328 328 16 frb45-21-1 945 59186 328 334 6.28
259 259 27.22 259 259 17 frb45-21-2 945 58624 259 259 6.02
233 233 41.14 233 233 18 frb45-21-3 945 58245 233 234 5.78
399 399 24.82 399 399 19 frb45-21-4 945 58549 399 399 6.39
312 313 28.68 20 frb45-21-5 945 58579 318 318 312 312.1 6.67
261 261 49.65 261 261 21 frb50-23-1 1150 80072 261 268 7.97
277 277 50.39 277 277 22 frb50-23-2 1150 80851 277 277 10.27
281 281 39.22 281 282.6 23 frb50-23-3 1150 81068 297 298 8.32
265 265 59.52 265 265 24 frb50-23-4 1150 80258 265 265 8.09
404 408 33.8 25 frb50-23-5 1150 80035 415 421 402 402.4 8.15
229 229 27.07 229 229 26 frb53-24-1 1272 94227 229 229 19.44
298 298 108.5 298 298 27 frb53-24-2 1272 94289 298 300 19.50
182 182 66.35 182 182 28 frb53-24-3 1272 94127 182 182 17.73
189 189 88.61 189 189 29 frb53-24-4 1272 94308 189 189 17.13
204 204 24.37 204 204 30 frb53-24-5 1272 94226 204 204 17.52
229 229 33.54 229 229 31 frb56-25-1 1400 109676 229 229 18.73
319 319 45.2 319 319 32 frb56-25-2 1400 109401 319 319 20.66
336 336 50.85 336 336 33 frb56-25-3 1400 109379 336 343 20.43
265 265 52.85 265 265 34 frb56-25-4 1400 110038 268 268 22.52
408 411 39.96 408 411.9 53.31 35 frb56-25-5 1400 109601 426 430
262 263 59.98 36 frb59-26-1 1534 126555 262 263 262 262 22.24
383 387 49.61 37 frb59-26-2 1534 126163 383 389 383 383 26.56
246 247 108.5 38 frb59-26-3 1534 126082 248 248 246 246 26.14
248 248 111.4 39 frb59-26-4 1534 127011 248 248 247 247.9 24.32
288 288 123.5 288 289.8 40 frb59-26-5 1534 125982 290 291 2.82
350 350 300.2 350 350 41 frb100-40 4000 350 350 156.34
572774
45
Chương 4. Ứng dụng chọn người điều hành cho nhóm moderator-selector
4.1 Giới thiệu ứng dụng chọn người điều hành cho nhóm moderator-selector
Ngày nay, hầu như mọi người đều tham gia vào ít nhất một nhóm người nào đó. Các nhóm đó thường ở trong một tổ chức nào đó tồn tại trong thế giới loài người. Các tổ chức đó được chia thành các loại như sau:
1. đơn vị hành chính nhà nước, 2. các cơ quan, đoàn thể, 3. các tổ chức dân sự tự phát.
Trong đó, các đơn vị hành chính nhà nước gồm các tổ chức bên trong nhà nước như các đơn vị hành chính cấp xã, huyện, tỉnh, đất nước. Chẳng hạn, cấp tỉnh gồm có hội sổ xố, hội người già, hội khuyến nông, ... Các cơ quan đoàn thể gồm có các doanh nghiệp, công ty, tập đoàn tư nhân. Các tổ chức dân sự tự phát gồm các nhóm hội được thành lập dân sự có cùng ý chí, nguyện vọng, tư tưởng với nhau tụ hợp nhau cho một mục tiêu nào đó. Các tổ chức này có thể là các tổ chức buôn bán tại các chợ, các tổ chức trên mạng xã hội, ...
Mỗi nhóm trong mỗi tổ chức gồm một tập hợp nhóm người có tương tác qua lại để phục vụ cho mục tiêu của nhóm. Các nhóm này có kích cỡ phụ thuộc vào cấu trúc của các tổ chức nó. Ví dụ các hội người già ở cấp tỉnh có từ vài nghìn đến vài chục nghìn, các hội nhóm tình nguyện trên nhà nước có vài nghìn đến vài chục nghìn. Các nhóm này thường được vận hành theo cơ chế phân quyền, trong đó các thành viên sẽ chịu sự quản lý của một nhóm người điều hành (moderators). Một lượng nhỏ các nhóm còn lại có thể hoạt động theo cơ chế mở và ít chịu sự tác động của người điều hành. Tuy nhiên, các nhóm này vẫn chịu tác động chính từ một số các người dùng nổi bật. Để có thể vận hành hoặc tương tác với nhóm tốt hơn, mỗi nhóm cần chọn ra một tập các người điều hành hoặc là tập các người nổi bật.
Sự tương tác giữa các người dùng trong cùng một nhóm tạo nên đồ thị với các đỉnh là các người dùng, mỗi cạnh thể hiện sự tương tác giữa hai người dùng. Mỗi người dùng có một giá trị gọi là điểm đánh giá mức độ ảnh hưởng có thể có cho nhóm. Giá trị này có thể phụ thuộc vào thời gian người dùng đó dành cho nhóm, của cải vật chất của người dùng cho nhóm, quyền lực chính trị của người
46
đó, ... Ngoài ra, các điều kiện ràng buộc cho người dùng cũng có thể được thêm vào để giúp việc lựa chọn người điều hành tốt hơn ví dụ như không chọn người nào trên 60 tuổi. Từ đây, lời giải của bài toán tìm tập đỉnh thống trị có trọng số nhóm nhất được áp dụng cho ứng dụng này.
Luận văn trình bày về ứng dụng moderator-selector để lựa chọn người điều hành cho một nhóm người (xem hình 4.1). Ứng dụng được viết bằng C++ với QT framework và chạy trên môi trường Linux. Ứng dụng cho phép người dùng xử lý trên các tệp dịnh dạng json với định dạng như sau: trong đó, names là trường có giá trị là môt mảng các tên của người dùng, values là trường có giá trị là một mảng tên giá trị của người dùng tương ứng, v1, v2 lần lượt có giá trị là các mảng chứa số thứ tự của người dùng và v1(i) và v2(i) thể hiện mối quan hệ của người dùng thứ v1(i) và v2(i).
{
"names" : Danh sách các người dùng
"values" : Danh sách các giá trị tương ứng
"v1" :
Danh sách các chỉ số người dùng
"v2" :
Danh sách các chỉ số người dùng
}
47
4.2 Cách sử dụng ứng dụng
Hình 3: Ứng dụng moderators-selector
Ứng dụng moderators-selector (xem hình 3) được sử dụng để chọn lựa những nhà điều hành một nhóm một cách hiệu quả, giúp việc quản lý và vận hành tổ chức tốt hơn các cách thông thường, với sự lựa tối ưu từ các thông số cần thiết được truyền vào ứng dụng.
Để lựa chọn một tệp đầu vào, người dùng nhấn chuột trái vào thẻ File và
chọn “Open” (hoặc có thể sử dụng tổ hợp phím “CTRL + O”) (xem hình 4).
48
Hình 4: Mở một tệp đầu vào dưới định dạng json
Sau khi mở một tệp đầu vào, danh sách người dùng, giá trị của họ sẽ được hiển thị ra trên màn hình (xem hình 5). Trong danh sách này, tên người dùng và giá trị tương ứng ở cột 1, và 2 theo thứ tự xuất hiện trong tệp đầu vào.
Hình 5: Hiển thị tên người dùng và giá trị của họ
Mối tương tác giữa người dùng sẽ được hiển thị trong thẻ “user interactions”, theo thứ tự xuất hiện trong tệp đầu vào (xem hình 6).
49
Hình 6: Hiển thị mối liên hệ giữa các người dùng
Sau khi đã tải dữ liệu vào chương trình, người dùng có thể nhấn chuột trái vào thẻ “Tools” và chọn “Run” hoặc sử dụng tổ hợp phím ALT + R. Sau khi thực hiện thao tác trên, chương trình sẽ bắt đầu lựa chọn những người điều hành và hiển thị họ ở trên màn hình trong thẻ moderators. Bên cạnh đó, số lượng người được chọn và tổng giá trị của họ cũng được hiển thị ngay tại thẻ đó (xem hình 7).
Hình 7: Hiển thị những người điều hành được chọn
50
Ngoài ra, người dùng có thể tùy chọn thời gian để lựa chọn người điều hành bằng việc mở “settings” trong thẻ “Tools” hoặc sử dụng tổ hợp phím “ALT + S” (xem hình 8).
Hình 8: Thiết lập chương trình
![Văn hoá doanh nghiệp tại Ngân hàng Indovina: Luận văn Thạc sĩ [Tối ưu SEO]](https://cdn.tailieu.vn/images/document/thumbnail/2026/20260324/hoatudang2026/135x160/31081774521739.jpg)
