ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ
THÔNG TIN VÀ TRUYỀN THÔNG

LÊ THÁI HÒA

PHƢƠNG PHÁP TỐI ƢU ĐÀN KIẾN GIẢI BÀI TOÁN
TÌM TẬP THỐNG TRỊ NHỎ NHẤT CỦA MỘT ĐỒ THỊ

LUẬN VĂN THẠC SĨ KHOA HỌC

Thái Nguyên - Năm 2015

Số hóa bởi Trung tâm Học liệu – ĐHTN




ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ
THÔNG TIN VÀ TRUYỀN THÔNG

LÊ THÁI HÒA

PHƢƠNG PHÁP TỐI ƢU ĐÀN KIẾN GIẢI BÀI TOÁN
TÌM TẬP THỐNG TRỊ NHỎ NHẤT CỦA MỘT ĐỒ THỊ
Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01.01

LUẬN VĂN THẠC SĨ KHOA HỌC



LỜI CẢM ƠN
Em xin chân thành cảm ơn thầy giáo TS. Đỗ Đức Đông đã trực tiếp
giao cho em đề tài, tận tình hƣớng dẫn và tạo mọi điều kiện cho em hoàn
thành luận văn.
Em xin chân thành cảm ơn các thầy cô giáo, các cán bộ nhân viên
phòng đào tạo, ban lãnh đạo Trƣờng Đại học Công nghệ thông tin và
Truyền thông đã giúp đỡ tạo điều kiện cho em hoàn thành bản luận văn
này.
Em xin bày tỏ lòng cảm ơn của mình đến giáo sƣ Raka Jovannovic,
ngƣời đã chia sẻ cho em rất nhiều tài liệu về thuật toán tối ƣu hóa đàn kiến
và cũng là ngƣời đã cung cấp cho em bộ dữ liệu để em thử nghiệm trong
bài luận văn này.
Cuối cùng, em xin chân thành cảm ơn sự quan tâm giúp đỡ của gia
đình, bạn bè và tập thể lớp Cao học K12I đã cổ vũ động viên em hoàn
thành tốt luận văn của mình.

Thái nguyên, ngày 23 tháng 7 năm 2015
Học viên Lê Thái Hòa

Số hóa bởi Trung tâm Học liệu – ĐHTN




iii

MỤC LỤC
LỜI CAM ĐOAN .......................................................................................... i
LỜI CẢM ƠN ............................................................................................... ii

iv

2.3.2. Các thuật toán ACO giải bài toán TSP ....................................... 24
2.3.2.1. Hệ kiến AS ........................................................................... 27
2.3.2.2. Hệ đàn kiến ACS ................................................................. 30
2.3.2.3. Hệ kiến Max-Min ................................................................ 33
2.3.2.4. Phƣơng pháp Max-Min trơn: SMMAS (Smoothed Max Min
Ant System) ....................................................................................... 36
2.4. Một số lƣu ý khi sử dụng các thuật toán ACO ................................. 36
2.4.1. Thông tin heuristic ...................................................................... 37
2.4.2. Số lƣợng kiến .............................................................................. 37
2.4.3. Tham số bay hơi.......................................................................... 38
2.5. Kết luận chƣơng ................................................................................ 38
Chƣơng 3. PHƢƠNG PHÁP TỐI ƢU HÓA ĐÀN KIẾN GIẢI BÀI TOÁN
TÌM TẬP THỐNG TRỊ NHỎ NHẤT CỦA ĐỒ THỊ................................. 39
3.1. Xây dựng lời giải .............................................................................. 40
3.2 Cập nhật mùi cho bài toán MWDSP .................................................. 41
3.3. Thực nghiệm và đánh giá .................................................................. 43
3.4. Kết luận chƣơng ................................................................................ 48
KẾT LUẬN ................................................................................................. 49
TÀI LIỆU THAM KHẢO ........................................................................... 51

Số hóa bởi Trung tâm Học liệu – ĐHTN




v

Danh mục các ký hiệu và chữ viết tắt


Ant Colony System (Hệ đàn kiến)

AS

Ant System (Hệ kiến)

G-best

Global-best (Lời giải tốt nhất tính đến thời điểm hiện
tại)

I-best

Iteration-best (Lời giải tốt nhất trong bƣớc lặp hiện tại)

MLAS

Multi-level Ant System (Hệ kiến đa mức)

Số hóa bởi Trung tâm Học liệu – ĐHTN




vi

MMAS

Max-Min Ant System (Hệ kiến Max Min)

Bảng 3.4: Kết quả thực nghiệm trên bộ dữ liệu 2 với kích thƣớc
lớn…………………………………………………………………. 47

Số hóa bởi Trung tâm Học liệu – ĐHTN




viii

Danh mục các hình
Trang
Hình 1.1: Thuật toán tham lam tìm tập phủ đỉnh ..………………..

6

Hình 1.2: Một ví dụ về đồ thị làm cho Greedy1 sai kết quả………..

7

Hình 1.3: Thuật toán tính

trong Greedy1_new………………..

8

Hình 1.4: Thuật toán tính 

trong Greedy2_new………………..


42

Số hóa bởi Trung tâm Học liệu – ĐHTN




1

MỞ ĐẦU
Hiện nay, có rất nhiều bài báo, luận văn, luận án hay các công trình
nghiên cứu đề cập đến vấn đề giải quyết các bài toán tối ƣu tổ hợp. Đa số
các bài toán này thuộc lớp các bài toán NP – khó. Trừ các bài toán cỡ nhỏ
có thể tìm lời giải bằng cách tìm kiếm vét cạn, còn lại thì thƣờng không thể
tìm đƣợc lời giải tối ƣu.
Đối với các bài toán kích thƣớc lớn không có phƣơng pháp giải
đúng. Hiện nay, ngƣời ta thƣờng tìm lời giải gần đúng nhờ các thuật toán
mô phỏng tự nhiên nhƣ giải thuật di truyền (Genetic Algorithm - GA), tối
ƣu bầy đàn (Particle Swarm Optimization -PSO)…
Trong các phƣơng pháp mô phỏng tự nhiên, tối ƣu hóa đàn kiến (Ant
Colony Optimization - ACO) là cách tiếp cận metaheuristic tƣơng đối mới,
đƣợc giới thiệu bởi Dorigo năm 1991 đang đƣợc nghiên cứu và ứng dụng
rộng rãi cho các bài toán TƢTH - khó.
Các thuật toán ACO mô phỏng cách tìm đƣờng đi của các con kiến
thực. Trên đƣờng đi, mỗi con kiến thực để lại một vết hoá chất gọi là vết
mùi (pheromone trail) và theo vết mùi của các con kiến khác để tìm đƣờng
đi. Đƣờng có nồng độ vết mùi càng cao thì càng có nhiều khả năng đƣợc
các con kiến chọn. Nhờ cách giao tiếp gián tiếp này đàn kiến tìm đƣợc
đƣờng đi ngắn nhất từ tổ tới nguồn thức ăn. Theo ý tƣởng đó, các thuật toán
ACO sử dụng kết hợp thông tin kinh nghiệm (heuristic) và học tăng cƣờng

tổ hợp (TƢTH) NP - khó. Chƣơng này giới thiệu các bài toán tối ƣu tổ hợp
dƣới dạng tổng quát, bài toán tìm tập thống trị nhỏ nhất và các cách tiếp
cận hiện nay.
1.1. Bài toán tối ƣu tổ hợp tổng quát
Trong đời sống thực tế ta thƣờng phải giải quyết nhiều bài toán
TƢTH quan trọng. Chẳng hạn nhƣ: tìm đƣờng đi ngắn nhất nối hai điểm
trên một đồ thị đã cho, lập kế hoạch phân phối nguồn hàng tới nơi tiêu thụ
với chi phí cực tiểu, lập thời khóa biểu cho giáo viên và học sinh thuận lợi
nhất, định tuyến cho các gói dữ liệu trong Internet, lập lịch hợp lý cho các
hệ thống sản xuất, đối sánh các chuỗi gen trong sinh học phân tử v.v…
Mỗi bài toán TƢTH ứng với một bộ ba ( S , f , ) trong đó:
- S là tập hữu hạn trạng thái (lời giải tiềm năng hay phƣơng án);
- f là hàm mục tiêu xác định trên ;
-  là tập các ràng buộc.
Mỗi phƣơng án s  S thỏa mãn các ràng buộc  gọi là phƣơng án trả
lời (hay lời giải). Mục đích của ta là tìm phƣơng án chấp nhận đƣợc s* tối
ƣu hóa toàn cục hàm mục tiêu , tức là một phƣơng án s* tốt nhất. Chẳng
hạn với bài toán cực tiểu thì ta phải tìm

với mọi phƣơng án

trả lời .
Số hóa bởi Trung tâm Học liệu – ĐHTN




4

Mỗi bài toán đều có thể chỉ ra một tập hữu hạn gồm


đƣợc xác

trong

.

và ánh xạ

, trong đó tập

rỗng với mọi

có độ dài không quá

từ

lên

sao cho

không

có thể xây dựng đƣợc từ tập con

nhờ thủ tục mở rộng tuần tự dƣới đây.
nhƣ sau:

ta mở rộng tuần tự thành



biến, trong đó mỗi biến nhận giá trị trong tập hữu hạn

kể cả giá trị

rỗng. Nói một cách khác, nó là bài toán tìm kiếm trong không gian vectơ
độ dài không quá

trên đồ thị đầy đủ có các đỉnh có nhãn trong tập .

Chú ý:
Với các bài toán TƢTH có dạng giải tích: Tìm cực trị hàm
trong đó mỗi biến

nhận giá trị trong tập hữu hạn

ứng và các biến này thỏa mãn các ràng buộc  nào đó, thì
Số hóa bởi Trung tâm Học liệu – ĐHTN

tƣơng

là tập




5

là các vectơ





là tập

.

sao cho mọi đỉnh thuộc

. Trong các tập thống trị đó,

tập thống trị nhỏ nhất là tập thống trị mà tổng trọng số của tất cả các đỉnh
thuộc

nhỏ nhất.
Bài toán tìm tập thống trị nhỏ nhất của đồ thị thuộc lớp bài toán NP-

khó và có nhiều ứng dụng trong thực tế. Đã có nhiều nhà nghiên cứu đƣa ra
các phƣơng pháp khác nhau để giải quyết bài toán trên, tuy nhiên các thuật
toán này chƣa thực sự hiệu quả.
1.3. Các cách tiếp cận hiện nay giải quyết bài toán tìm tập thống trị
nhỏ nhất của đồ thị
1.3.1. Thuật toán tham lam tìm tập phủ đỉnh nhỏ nhất.
Trƣớc hết ta xét đồ thị mà chƣa quan tâm đến trọng số của các đỉnh
(coi mỗi đỉnh đều có trọng số bằng 1). Khi đó bài toán trở thành “Tìm tập
phủ đỉnh có số lƣợng đỉnh ít nhất”.
Để dễ hình dung ta gọi:
- Tập các đỉnh đã đƣợc chọn vào làm kết quả là các đỉnh tô màu đen
( ).
- Tập các đỉnh không thuộc

đƣợc xác định bởi giá trị của

là những đỉnh trắng kề với ).
Thuật toán đƣợc mô ta nhƣ sau:
;
While

;
Do

;

Begin
Tìm

(|

| lớn nhất).

;
{ };
;
End;
Hình 1.1: Thuật toán tham lam tìm tập phủ đỉnh
1.3.2. Thuật toán tham lam 1 (Greedy1)
Với ý tƣởng trình bày trong tài liệu [12] ngƣời ta biến đổi đồ thị ban
đầu thành đồ thị đầy đủ bằng cách thêm các cạnh vào đồ thị. Khi đó những
cạnh ban đầu của đồ thị có trọng số bằng 1 (kí hiệu bằng màu đen), cạnh
đƣợc thêm vào có trọng số bằng 0 (kí hiệu bằng màu đỏ).
Khi thêm một đỉnh vào tập


thì giải pháp đƣợc chọn

để ƣu tiên nhƣ sau:
∑

(1.2)
(1.3)
thực chất là số lƣợng những đỉnh kề

Từ (1.1) và (1.2) ta thấy

với mà chƣa đƣợc phủ (còn là đỉnh màu trắng).
Nhƣ vậy việc chọn một đỉnh để kết nạp vào

dựa trên hai tiêu chí:

+ Số lƣợng đỉnh màu trắng kề với nó càng nhiều càng tốt.
+ Trọng số của đỉnh đó càng nhỏ càng tốt.
Phép cộng 1 vào tử số để đảm bảo đƣợc việc so sánh giữa các đỉnh
không còn kết nối nữa, tức là những đỉnh cô lập (khi đó ta sẽ chọn đỉnh nào
có trọng số nhỏ hơn).
Theo công thức (1.3) ta thấy rằng khi đồ thị

chỉ gồm các đỉnh cô

lập thì việc lựa chọn đỉnh nào chỉ phụ thuộc vào trọng số của nó chứ không
phân biệt đỉnh đó đã đƣợc phủ hay chƣa. Tức là có thể chọn thêm vào kết
quả đỉnh đã đƣợc tô màu xám mà không kề với bất kỳ đỉnh màu trắng nào.


Ta có thể cải tiến thuật toán này bằng cách thêm vào đồ thị ban đầu
những cạnh khuyên

với

Khi đó nếu một đỉnh màu xám

nằm cô lập (đã đƣợc phủ bởi đỉnh khác) thì giá trị

của nó sẽ bằng

không, trong khi một đỉnh màu trắng nằm cô lập thì giá trị

của nó lại

bằng 1. Vì vậy ta không cần cộng thêm 1 vào tử số, đồng thời tránh đƣợc
sai sót nhƣ trong ví dụ trên (cải tiến này đƣợc minh họa trong chƣơng 3
bằng thuật toán Greedy1_new). Khi đó công thức (1.3) sẽ đƣợc biến đổi
nhƣ sau:

(1.4)

For

to

do

If kề và là đỉnh mầu trắng then


chí để chọn lựa đỉnh nào là đỉnh tiếp theo kết nạp vào kết quả. Trên thực tế
ta thấy việc chọn những đỉnh màu xám không có ý nghĩa gì mà chỉ làm xấu
đi kết quả. Vì vậy, để thuật toán tốt hơn ta vẫn phải thêm vào đồ thị ban
đầu những cạnh

với

. Do đó ta có thể sửa công thức (1.5)

thành công thức sau:


∑

(1.6)

Cải tiến này làm cho kết quả tốt hơn đáng kể so với thuật toán
Greedy2 trong [11] (ta gọi thuật toán đã cải tiến là Greedy2_new).
Trong hai thuật toán tham lam đã đề cập ở trên việc thêm những
cạnh khuyên vào đồ thị làm cho thuật toán cải thiện đáng kể vì tránh đƣợc
việc chọn những đỉnh màu xám vào tập kết quả trong khi nó không còn kề
với một đỉnh màu trắng nào. Việc chỉnh sửa công thức chỉ là thay đổi cho
phù hợp sau khi đã thêm các cạnh khuyên chứ không phải là nguyên nhân
chủ yếu làm cho kết quả tốt hơn.
Số hóa bởi Trung tâm Học liệu – ĐHTN




10

thì đƣơng nhiên ngôi làng

sẽ đƣợc phủ sóng,

ngoài ra có thể có một số ngôi làng khác cũng sẽ đƣợc phủ sóng. Do giá
thành mặt bằng để thuê đặt cột phát sóng, cũng nhƣ nhiều yếu tố khác làm
cho việc xây dựng và thuê đặt địa điểm của các cột phát sóng tại các ngôi
làng là khác nhau. Vấn đề đặt ra cho công ty này là làm sao xây dựng các

Số hóa bởi Trung tâm Học liệu – ĐHTN




11

cột phát sóng để có thể phát sóng cho tất cả mọi ngƣời dân trong

ngôi

làng nói trên nhƣng có chi phí thuê và lắp đặt nhỏ nhất.
Ứng dụng 2: Ứng dụng trong việc xây dựng các công trình nƣớc sạch phục
vụ cho đồng bào vùng cao. Việc xây dựng một công trình nƣớc sạch tại
một địa phƣơng nào đó có thể cấp phát nƣớc cho địa phƣơng đó cũng nhƣ
một số địa phƣơng lân cận khác. Chi phí để xây dựng công trình nƣớc sạch
tại những địa phƣơng khác nhau là khác nhau do việc vận chuyển vật liệu
cũng nhƣ giá thuê nhân công. Vì vậy bài toán đặt ra là phải xây dựng các
công trình nƣớc sạch sao cho có giá thành nhỏ nhất nhƣng vẫn đảm bảo cấp
phát nƣớc đầy đủ cho tất cả các địa phƣơng trên.
Trên thực tế còn có rất nhiều bài toán đƣợc mô hình hóa bởi bài toán


12

sai lệnh nhiều so với kết quả thực tế của bài toán. Việc nghiên cứu cách
giải bài toán trên để đạt kết quả tốt hơn là một lĩnh vực đƣợc nhiều nhà
khoa học trong nƣớc và thế giới quan tâm.

Số hóa bởi Trung tâm Học liệu – ĐHTN




13

Chƣơng 2. PHƢƠNG PHÁP TỐI ƢU ĐÀN KIẾN

Bài toán tối ƣu hóa tổ hợp là bài toán hấp dẫn và thú vị bởi vì phần
lớn chúng đều dễ để hình dung nhƣng khó mà tìm ra lời giải cho chúng.
Nhiều bài toán tối ƣu tổ hợp là các bài toán NP-khó và chúng không thể
giải đƣợc trong thời gian đa thức. Trên thực tế ngƣời ta thƣờng giải quyết
các bài toán này bằng các phƣơng pháp xấp xỉ, chúng có nghiệm gần tối ƣu
và thời gian chạy khá ngắn. Các thuật toán thuộc lại này tạm gọi là các
thuật toán heuristic, chúng đƣợc sử dụng để giải quyết các bài toán cụ thể.
Mở rộng của chúng là các thuật toán metaheuristic có thể giải quyết đƣợc
cả một lớp các bài toán rộng lớn. ACO là một phƣơng pháp theo hƣớng tiếp
cận nhƣ thế.
Tối ƣu đàn kiến (ACO) là một phƣơng pháp metaheuristic dựa trên ý
tƣởng mô phỏng cách tìm đƣờng đi từ tổ tới nguồn thức ăn của các con
kiến tự nhiên. Đến nay phƣơng pháp này đƣợc cải tiến đa dạng và có nhiều
ứng dụng. Trƣớc khi giới thiệu phƣơng pháp ACO, luận văn sẽ giới thiệu


là độ dài của nhánh dài còn

là độ dài

của nhánh ngắn.
Trong thực nghiệm thứ nhất, chiếc cầu đôi có hai nhánh bằng nhau (r
= 1, hình 2.1.a). Ban đầu, kiến lựa chọn đƣờng đi một cách tự do từ tổ đến
nguồn thức ăn, cả hai nhánh đều có kiến đi, nhƣng sau một thời gian các
con kiến này tập trung đi theo cùng một nhánh. Kết quả có thể đƣợc giải
thích nhƣ sau: ban đầu không có vết mùi nào trên cả hai nhánh, do đó kiến
lựa chọn nhánh bất kỳ với xác suất nhƣ nhau. Một cách ngẫu nhiên, sẽ có
một nhánh có số lƣợng kiến lựa chọn nhiều hơn nhánh kia. Do kiến để lại
vết mùi trong quá trình di chuyển, nhánh có nhiều kiến lựa chọn sẽ có nồng
độ mùi lớn hơn nồng độ mùi của nhánh còn lại. Nồng độ mùi trên cạnh lớn
hơn sẽ ngày càng lớn hơn vì ngày càng có nhiều kiến lựa chọn. Cuối cùng,
hầu nhƣ tất cả các kiến sẽ tập trung trên cùng một nhánh. Thực nghiệm này
cho thấy là sự tƣơng tác cục bộ giữa các con kiến với thông tin gián tiếp là
vết mùi để lại cho phép điều chỉnh hoạt động vĩ mô của đàn kiến.
Số hóa bởi Trung tâm Học liệu – ĐHTN




15

Hình 2.1: Thực nghiệm cây cầu đôi
(a) Hai nhánh có độ dài bằng nhau. (b) Hai nhánh có độ dài khác nhau.

Hình 2.2. Tỉ lệ các con kiến chọn đƣờng đi.