ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Nguyễn Quỳnh Anh
THUẬT TOÁN PHÂN LỚP ĐÀN KIẾN VỚI THUỘC
TÍNH LIÊN TỤC
KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin
HÀ NỘI - 2010
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Nguyễn Quỳnh Anh
THUẬT TOÁN PHÂN LỚP ĐÀN KIẾN VỚI THUỘC
TÍNH LIÊN TỤC
KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin
Cán bộ hướng dẫn: PGS.TS Hoàng Xuân Huấn
Cán bộ đồng hướng dẫn:Ths Đỗ Đức Đông
HÀ NỘI - 2010
Tóm tắt nội dung
Khóa luận trình bày thuật toán phân lớp sử dụng phương pháp tối ưu hóa đàn
kiến làm việc với thuộc tính liên tục. Đầu tiên giới thiệu phương pháp tối ưu hóa đàn
kiến. Đây là mô hình thiết kế các thuật toán cho bài toán tối ưu hóa tổ hợp. Trong các
thuật toán này người ta kết hợp thông tin Heuristic và thông tin học tăng cường thể
hiện qua các vết mùi của các con kiến nhân tạo để giải các bài toán tối ưu tổ hợp khó
bằng cách đưa về bài toán tìm đường đi tối ưu trên đồ thị cấu trúc tương ứng được xây
dựng từ đặc điểm của từng bài toán. Một số thuật toán dựa vào phương pháp này đã
được đưa ra như Ant System, Ant Colony System, Min Max Ant System. Tiếp theo
là bài toán phân loại dựa trên luật kết hợp. Từ một bộ dữ liệu có nhiều mẫu, mỗi mẫu
có một số thuật tính, tìm ra các luật để chia các mẫu này vào các lớp khác nhau. Để
giải quyết bài toán phân loại thuậ toán ID3 đã được đưa ra. Thuật toán này sẽ xây
dựng một cây quyết định, dựa vào cây này để phân lớp tập dữ liệu. Từ thuật toán này

thông qua một số thủ tục cắt tỉa cây hình thành thuật toán C4.5. Cây quyết định sẽ
được cắt tỉa để đưa ra các luật và sẽ dùng các luật này để phân lớp. Áp dụng phương
pháp tối ưu hóa đàn kiến vào bài toán phân lớp chúng ta có thuật toán Ant-miner. Ant-
miner chỉ áp dụng với dữ liệu đã qua bước rời rạc hóa. Một phát triển của Ant-miner là
cAnt-miner làm việc với các thuộc tính liên tục. Các thuộc tính liên tục trong cAnt-
miner sẽ được xử lý dựa trên thông tin Entropy. Và cuối cùng là thử nghiệm phương
pháp cập nhật mùi khác vào trong thuật toán cAnt-Miner. Chương trình thực nghiệm
được viết bằng ngôn ngữ JAVA để kiểm tra các kết quả đã nêu trên.
Mục lục
Bảng các kí hiệu, chữ viết tắt
Ant Colony Optimization ACO
Ant System AS
Ant Colony System ACS
Max Min Ant System MMAS
Mở đầu
Bài toán phân lớp là một vấn đề quan trọng và được quan tâm nhiều trong lĩnh
vực khai thác dữ liệu. Có rất nhiều thuật toán đã được đưa ra để giải quyết bài toán
này. Gần đây phương pháp tối ưu hóa đàn kiến đã được áp dụng để xây dụng thuật
toán Ant-miner dùng cho phân lớp dữ liệu. Thuật toán này đã tỏ ra khá hiệu quả, kết
quả thực nghiệm nhìn chung là tốt hơn hẳn các thuật toán đã có. Tuy nhiên nó chỉ làm
việc với dữ liệu đã rời rạc hóa. Trong [4] Fernando et al giới thiệu cAnt-miner là một
cải tiến của Ant-Miner làm việc với dữ liệu liên tục.
Khóa luận này trình bày khảo cứu của tác giả về thuật toán CAnt-Miner theo tài
liệu [2]. Trên cơ sở đó, xây dựng chương trình thử nghiệm thuật toán và so sánh hiệu
quả của nó với các quy tắc cập nhật mùi mới SMMAS.
Ngoài phần kết luận, nội dung của khóa luận được trình bày như sau.
Chương 1- giới thiệu phương pháp tối ưu hóa đàn kiến và các phương pháp cập
nhật mùi chính như: AS, ACS và Mã-Min AS và minh họa bằng bài toán TSP và bài
toán dò đường.

Chương 2- giới thiệu bài toán phân lớp nhờ các luật kết hợp và các phương pháp
tìm luật kết hợp như ID3, C4.5 và Ant-Miner
Chương 3- Trình bày thuật toán Cant-Miner đã nêu trong [2] và nghiên cứu về
hiệu quả của thuật toán và các quy tắc cập nhật mùi khác nhau: MMAS, SMMAS và
3-LAS. chương trình được viết bằng JAVA.

6
Chương 1 Giới thiệu về phương pháp tối ưu hóa đàn kiến ACO
Chương này giới thiệu khái quát về phương pháp ACO giải bài toán tối ưu hóa tổ
hợp. Sau khi chỉ ra các đặc điểm của phương pháp: Bước chọn ngẫu nhiên, cập nhật
vết mùi, giả lập hành động cho kiến; chúng tôi nêu một số thuật toán chính: Ant
System (AS), Ant colony system (ACS), Max min ant system (MMAS). Và chỉ ra sự
khác biệt giữa các thuật toán này. Lược đồ ứng dụng cho bài toán Travel Saleman
Problem (TSP) sau đó là Vehicle Route Problems (VRPs) được giới thiệu để minh họa
cho phương pháp.
1.1 Ý tưởng của phương pháp
Tối ưu hóa đàn kiến (ACO) là một phương pháp dùng để thiết kế các heuristic
cho thuật toán giải bài toán tối ưu hóa tổ hợp. Thuật toán đầu tiên được phân vào trong
khuôn khổ này đã được đề xuất vào năm 1991bởi M. Dorigo [5] và sau đó rất nhiều
phiên bản dựa trên nguyên tắc cơ bản của ACO đã được đưa ra trong các hội nghị
khoa học. Đặc điểm chính của thuật toán ACO là sự kết hợp của thông tin heuristic và
thông tin vết mùi.
Phương pháp tối ưu hóa đàn kiến là cách tiếp cận meta-Heuristic mô phỏng hành
vi tìm đường đi từ tổ tới nguồn thức ăn và ngược lại của con kiến thực trong tự nhiên.
Trên đường đi của mình các con kiến thực để lại một vết hóa chất được gọi là vết mùi
báo cho các con kiến khác thông tin về đường đi đó một cách gián tiếp. Sau đó các con
kiến khác sẽ lựa chọn đường đi nào có cường độ mùi lớn nhất tại thời điểm lựa chọn
để đi nhờ đó tìm được đường đi ngắn nhất.
Thuật toán Meta-heuristic dùng để thoát khỏi cực trị địa phương dựa vào một số
heuristic cơ bản: heuristic xây dựng từ một giải pháp chưa hoàn chỉnh và bổ sung

thêm các yếu tố để xây dựng một giải pháp tốt, hoặc một heuristic tìm kiếm địa
phương bắt đầu từ một giải pháp hoàn chỉnh và lặp đi lặp lại quá trình sửa đổi một số
yếu tố của nó để đạt được một giải pháp tốt hơn. Thông thường, cơ chế kiểm soát được
thực hiện bằng tập hợp xác định hoặc ngẫu nhiên các giải pháp láng giềng gần nhất để
xem xét trong việc tìm kiếm địa phương, hoặc bằng cách kết hợp các yếu tố khác nhau
được thực hiện bởi các giải pháp (như trường hợp của chiến lược tiến hóa và di
truyền).
7
Đặc điểm của thuật toán ACO là sử dụng các yếu tố của các giải pháp trước đó.
Trong thực tế nó xây dựng một giải pháp thông qua việc sử dụng các bước ngẫu nhiên.
Và xác suất ngẫu nhiên này được tính thông qua heuristic của giáp pháp trước đó
cùng với thông tin vết mùi. Tuy nhiên hai thông tin này cần được điều chỉnh bằng các
tham số cụ thể.
Trong các thiết kế thuật toán sử dụng phương pháp ACO phải đối mặt với sự cân
nhắc mức độ giữa các thông tin đặc trưng được sử dụng và thông tin vết mùi để có
được phân bố xác suất có hiệu quả cho sự xuất hiện của các giải pháp tốt. Các ứng
dụng khác nhau sử dụng thay đổi một trong hai tham số cấp độ của biến quyết định, do
đó đòi hỏi số lượng lớn các lần lặp lại trước khi nhận được một phân phối chính xác.
1.2 Phương pháp tối ưu hóa đàn kiến ACO(Ant Colony Optimization)
ACO là một lớp các thuật toán, thành viên đầu tiên được gọi là Ant system (AS),
đã được đề xuất bởi Colorni, Dorigo và Maniezzo trong [6] . Ý tưởng cơ bản chính là
các hành vi của loài kiến trong thực tế, đó là một tìm kiếm song song trên một số giải
pháp để xây dựng tính toán dựa trên dữ liệu địa phương và một cấu trúc bộ nhớ động
có chứa thông tin về chất lượng của các kết quả thu được trước đó.
Một bài toán tối ưu hóa tổ hợp là một bài toán được xác định trên một bộ các
thành phần cơ bản C = c
1
, , C
n
. Một tập con S của các thành phần đại diện cho một

giải pháp F ⊆ 2
C
là tập con của các giải pháp khả thi, do đó một giải pháp S là khả thi
khi và chỉ khi S ⊆ F. Một hàm chi phí z được định nghĩa trên miền giải pháp, z: 2
C

R, mục tiêu là để tìm một giải pháp khả thi chi phí tối thiểu S *, tức là để tìm S*: S*
∈ F và z(S*) ≤ z(S), ∀ S ∈ F.
Vì thế các chức năng của một thuật toán ACO có thể được tóm tắt như sau. Một
tập hợp tính toán đồng bộ và không đồng bộ (một thuộc địa của loài kiến) di chuyển
qua các trạng thái của bài toán tương ứng với các giải pháp giải quyết một phần của
bài toán. Chúng di chuyển bằng cách áp dụng một chính sách quyết định ngẫu nhiên
địa phương dựa trên hai tham số, gọi là đường mòn và vết mùi. Bằng cách di chuyển,
xây dựng từng bước một giải pháp cho vấn đề. Khi một con kiến hoàn thành một giải
pháp, hoặc trong giai đoạn xây dựng, tổ kiến đánh giá các giải pháp và sửa đổi các giá
trị đường mòn trên các thành phần được sử dụng trong giải pháp của nó. Thông tin vết
mùi (pheromone) sẽ chỉ đạo các tìm kiếm của kiến trong tương lai.
8
Hơn nữa, một thuật toán ACO bao gồm hai cơ chế khác: bốc hơi và các giả lập
hành động. Bốc hơi làm giảm tất cả các giá trị đường mòn qua thời gian, để tránh tích
tụ không giới hạn của vết mùi qua một số thành phần. Giả lập hành động có thể được
sử dụng để thực hiện các hành động tập trung mà không thể thực hiện bởi kiến duy
nhất, chẳng hạn như gọi trình thủ tục tối ưu hóa địa phương, hoặc cập nhật thông tin
toàn cục sử dụng để ra quyết định trong quá trình tìm kiếm từ một điểm địa phương .
Cụ thể hơn, một kiến là một tính toán đơn giản, được lặp đi lặp lại xây dựng một
giải pháp để giải quyết vấn đề, các giải pháp của một phần vấn đề được xem là một
trạng thái. Và quá trình chính là cốt lõi của thuật toán ACO, trong đó tại mỗi lần lặp,
mỗi kiến di chuyển (thực hiện một bước) từ trạng thái i đến một trạng thái ψ, tương
ứng với một phần để hoàn chỉnh giải pháp. Ở mỗi bước σ, mỗi kiến k thiết lập một bộ
Ak

σ
(ι) mở rộng của giải pháp khả thi hiện nay, và di chuyển đến một trong những
trạng thái tiếp quyết định bởi giá trị xác suất. Phân bố xác suất được quy định như sau.
Đối với kiến k, xác suất p
ι

ψ
k
từ trạng thái i đến một ψ phụ thuộc vào sự kết hợp của
hai giá trị:
η
ι

ψ
được tính bởi hàm đánh giá (heuristic) cho việc di chuyển từ ι đến ψ.
τ
ιψ
thông tin vết mùi mà các con kiến lưu lại.
Đương đi được cập nhật khi tất cả các con kiến đã hoàn thành giải pháp của
mình, tăng, giảm mức độ đường đi tương ứng với mức độ "tốt" hay "xấu" của các giải
pháp tương ứng.
1.2.1 Ant system
Thuật toán hệ kiến (Ant System – AS) là thể hiện đầu tiên và điển hình của thuật
toán ACO
Phân bố xác suất di chuyển được xác định bằng 0 cho tất cả di chuyển được tính
không khả thi (tức là, đường đi đang có trong danh sách bị cấm của kiến k, đó là một
danh sách chứa tất cả các trạng thái mà kiến k không thể tới từ trạng thái i), nếu không
chúng được tính toán bằng công thức sau, trong đó và là các tham số thay đổi (0, 1):
9
Nếu α = 0 con kiến sẽ lựa chọn đỉnh tiếp theo dựa vào tư tưởng tham lam thông

thường tức là cạnh nào ngắn nhất sẽ được ưu tiên chọn trước, nếu β = 0 sự lựa chọn sẽ
chỉ phụ thuộc vào cường độ vết mùi bài toán dễ rơi vào trường hợp tối ưu địa phương.
Sau mỗi vòng lặp t của thuật toán, tức là khi tất cả các con kiến đã hoàn thành
giải pháp của mình, những đường đi được cập nhật bằng công thức:
đại diện cho tổng các vết mùi đóng góp của tất cả các con kiến đi qua nó (đi từ
trạng thái i đến trạng thái ψ) để xây dựng giải pháp của chúng, (0 1) là một tham số
người dùng định nghĩa được gọi là hệ số bốc hơi. Những kiến đóng góp tỷ lệ thuận với
chất lượng của các giải pháp đạt được, tức là các giải pháp tốt hơn sẽ đóng góp nhiều
hơn vào đường đi nó sử dụng.
Ví dụ, trong trường hợp của TSP, di chuyển tương ứng với cạnh của đồ thị, do đó
việc di chuyển từ trạng thái i đến trạng thái j tương ứng với cạnh(ij) được thêm vào lúc
kết thúc và việc di chuyển sẽ là cạnh (ij). Chất lượng của giải pháp của kiến k sẽ là L
k
chiều dài của các đường đi tìm thấy bởi các kiến và công thức sẽ trở thành
với
m là số kiến là lượng cập nhật của kiến k cho cạnh ij và được tính bởi
Thuật toán AS
10
1.Khởi tạo
Khởi tạo
2.Xây dựng lời giải
Với mỗi kiến K (ở trạng thái i) bắt đầu
Lặp
Chọn một sác xuất di chuyển
Thêm trạng thái di chuyển vào danh sách cấm của kiến K
Dừng khi kiến k đã xây dụng xong lời giải
3.Cập nhật mùi
For mỗi kiến di chuyển từ i tới j do
tính
cập nhật ma trận mùi

end for
4.Điều kiên dừng
Tìm ra giải pháp
Nếu chưa kết thúc quay lại 2
1.2.2 Thuật toán ACS (Ant colony system)
AS là thuật toán đầu tiên lấy ý tưởng từ hành vi thực tế của loài kiến. Và đã được
áp dụng cho người bán hàng TSP nhưng không thể cạnh tranh với các thuật toán nổi
tiếng trong lĩnh vực này. Mặt khác, nó đã có công giới thiệu thuật toán ACO và cho
thấy tiềm năng của việc sử dụng vêt mùi nhân tạo và những con kiến nhân tạo vào việc
xây dựng giải pháp tìm kiếm tốt hơn cho bài toán tối ưu hóa luôn luôn phức tạp. Các
nghiên cứu tiếp theo đã được thúc đẩy bởi hai mục tiêu: đầu tiên là để cải thiện hiệu
suất của thuật toán và thứ hai là để kiểm tra và giải thích hành vi của nó tốt hơn.
Gambardella và Dorigo đề xuất trong năm 1995 thuật toán Ant-Q, một phần mở rộng
của AS được tích hợp một số ý tưởng từ Q-learning, và vào năm 1996 đưa ra Ant
Colony System (ACS) một phiên bản đơn giản của Ant-Q mà vẫn duy trì mức độ hiệu
suất, đo bằng độ phức tạp thuật toán và kết quả của nó. Kể từ khi ra đời ACS là cơ sở
11
của nhiều thuật toán được xây dựng trong những năm tiếp theo. ACS khác với AS
trước đó bởi vì trong ba khía cạnh chính:
Cập nhật vết mùi
AS cập nhật các dấu vết mùi bằng cách sử dụng tất cả các giải pháp sinh ra bởi
các con kiến. Mỗi cạnh thuộc một trong các giải pháp được sửa đổi bởi một số lượng
mùi tỷ lệ thuận với giá trị của giải pháp của đó. Vào cuối giai đoạn này các vết mùi
của toàn bộ hệ thống bay hơi và quá trình xây dựng và cập nhật được lặp lại. Ngược
lại, trong ACS chỉ có giải pháp tốt được sử dụng để cập nhật các vết mùi. Như trường
hợp trong AS, cập nhật toàn cục được dự định để tăng xác suất của tuyến đường có thể
nhưng ACS cơ chế hiệu quả hơn vì nó tránh được thời gian hội tụ dài bằng cách trực
tiếp tập trung tìm kiếm trong một khu vực tốt nhất của các giải pháp hiện hành của
thuật toán.
Trong ACS, giai đoạn bốc hơi cuối cùng được thay thế bằng một cập nhật địa

phương của vết mùi áp dụng trong giai đoạn xây dựng lời giải. Mỗi lần di chuyển kiến
từ trạng thái hiện nay để đến trạng thái tiếp theo vết mùi liên quan đã được sửa đổi
theo cách sau:
trong đó 0 ≤ ρ ≤ 1 là một tham số (thường đặt ở 0,9)
là giá trị vết mùi ban đầu
L
nn
là độ dài đường đi được sinh ra bởi việc thực hiện một lần lặp ACS mà không
có thành phần vết mùi (điều này tương đương với một hàm đánh giá k láng giềng gần
nhất).
Hiệu quả của cập nhật địa phương là làm cho xác suất của các cạnh thay đổi tự
động: mỗi một con kiến sử dụng một cạnh này sẽ thêm cho nó một lượng mùi và chỉ
cho các cạnh mà không bao giờ thuộc về đường đi tốt nhất thì vết mùi vẫn là
τ

0
. Một
tính chất thú vị các cập nhật địa phương và toàn cục là các cơ chế cập nhật là vết mùi
τ
ij
(t) của mỗi cạnh sẽ hạn chế bởi
τ

0
. Một cách tiếp cận tương tự như đã được đề xuất
với cái tên Max Min-AS (MMAS) trong đó vết mùi được giới hạn với giá trị của các
lượng mùi ban đầu.
12
Chuyển trạng thái
Trong khi xây dựng một giải pháp mới chuyển đổi trạng thái quy định là giai

đoạn mà mỗi kiến quyết định trạng thái tiếp theo để chuyển đến. Trong ACS một bước
chuyển đổi trạng thái gọi là tỷ lệ giả ngẫu nhiên(pseudo-random-proportional) được
đưa ra. Đó một so sánh giữa sự lựa chọn trạng thái giả ngẫu nhiên thường được sử
dụng trong Q-learning và tỉ lệ ngẫu nhiên thường được sử dụng trong Ant System.
Với nguyên tắc giả ngẫu nhiên chọn trạng thái tốt nhất với xác suất q
0
(khai thác)
trong khi một trạng thái được lựa chọn ngẫu nhiên với xác suất 1 - q
0
(thăm dò). Tiếp
theo sử dụng tỉ lệ ngẫu nhiên theo quy tắc AS lựa chọn ngẫu nhiên với một phân phối
xác suất tùy thuộc vào
η

ij
và
τ

ij
. Các ACS tỉ lệ giả ngẫu nhiên chuyển đổi trạng thái
cung cấp một cách trực tiếp để cân bằng giữa các tiểu trạng thái mới thăm dò và khai
thác , tích lũy kiến thức. Trạng thái tốt nhất được chọn với xác suất q
0
(đó là một tham
số 0≤ q
0
≤ 1 thường cố định đến 0,9) và với xác suất (1 - q
0
) trạng thái tiếp theo được
lựa chọn ngẫu nhiên với một phân bố xác suất dựa trên

η

ij
và
τ

ij
trong đó α thường
bằng 1) và
β
((thường là bằng 2).
nếu q<q
0
Lai tạo và cải tiến hiệu suất
ACS được áp dụng cho các giải pháp của đối xứng và bất đối xứng cho vấn đề
người bán hàng (TSP / ATSP) . Một danh sách ứng cử viên là một cấu trúc dữ liệu tĩnh
của cl, trong đó có một thành phố i, các thành phố ưa thích cl được viếng thăm. Một
kiến trong ACS đầu tiên sử dụng danh sách ứng cử viên với các quy tắc chuyển trạng
thái để lựa chọn thành phố di chuyển đến. Nếu không một thành phố nào trong danh
sách ứng cử viên có thể đến thăm các con kiến lựa chọn các thành phố gần nhất có sẵn
chỉ bằng cách sử dụng giá trị hàm đánh giá
η

ij
( heuristic). ACS cho TSP (ATSP) đã
được cải thiện bằng cách kết hợp các đánh giá (heuristic) tối ưu hóa địa phương (lai
tạo) ý tưởng là mỗi thời điểm một giải pháp được tạo ra bởi các kiến nó được lấy ở
mức tối thiểu trong các trạng thái bằng cách áp dụng một đánh giá (heuristic) tối ưu
hóa địa phương dựa trên một chiến lược cạnh trao đổi, giống như 2-opt, 3-opt. Các giải
pháp tối ưu hóa mới được coi là giải pháp cuối cùng được sinh ra tại thời điểm hiện tại

của con kiến và được sử dụng để cập nhật vết mùi toàn cầu cho đường đi.
13
Thuật toán ACS này thực hiện một chính sách kết hợp quản lý vết mùi mới, một
chiến lược chuyển trạng thái mới và các thủ tục tìm kiếm địa phương cạnh tranh thuật
toán cho các giải pháp của TSP. Điều này đã mở ra một ranh giới mới cho các thuật
toán dựa ACO. Theo đó một phương pháp tiếp cận kết hợp một giai đoạn xây dựng
các vết mùi và giai đoạn tìm kiếm địa phương xây dựng giải pháp tối ưu hóa, thuật
toán ACO đã có thể giải quyết một số vấn đề tối ưu hóa, kể cả vấn đề định tuyến và
lập lịch sẽ được trình bày trong phần sau .
1.2.3 Thuật toán hệ kiến MaxMin-AS
Max-Min Ant System (MMAS) được đề xuất bởi Stutzle và Hoos trong [8] là
một cải tiến để khai thác ưu điểm của phương pháp hệ kiến ban đầu (AS). Việc cập
nhật vết mùi của AS có thể dẫn đến hiện tượng tắc nghẽn (stagnation) trong khi tìm
kiếm.Cần có một cơ chể để tránh sự tắc nghẽn này, max min - Ant được thể phát triển
để đáp ứng các yêu cầu này, khác với AS tại 3 điểm chính:
i, để khai thác lời giải tốt nhất trong mỗi lần lặp hoặc trong cả thuật toán, sau
mỗi lần lặp việc cập nhật vết mùi được thực hiện. Kiến này có thể là kiến tìm thấy lời
giải tốt nhất trong lầnlặp lại hiện tại (iteration-best ant) hoặc là kiến tìm thấy lời giải
tốt nhất từ đầu đến thời điểm hiện tại (global-best ant)
ii, Để tránh tắc nghẽn việc cập nhật mùi được giới hạn trong khoảng [τ
min
,τ
max
]
iii, ngoài ra việc khởi tạo vết mùi được thực hiện theo τ
max
, theo cách này để có
thể khám phá ở mức cao hơn khi bắt đầu thuật toán
cập nhật vết mùi
vết mùi được cập nhật sau mỗi lần lặp theo công thức:

trong đó và là độ dài của đương đi tốt nhất trong lần lặp hiên tại S
ib
hoặc lời
giải tốt nhất của thuật toán đến thời điểm hiện tại S
gb
.
Thông thường S
gb
được sử dụng
trong thuật toán ACS, MMAS tập trung vào lời giải hiện tại
Giới hạn cập nhật vết mùi
Trong quá trình xây dựng lời giải MMAS sử dụng giới hạn vết mùi cho các
cạnh . Sau mỗi lần lặp cần xác định vết mùi có vượt quá giới hạn hay không. Nếu ta
đặt nếu ta đặt
14
1.3 Một số bài toán đã được giải quyết bằng phương pháp ACO
1.3.1 Người bán hàng TSP (traveling salesman problem)
Các ứng dụng ACO đầu tiên được dành để giải quyết vấn đề đối xứng và bất đối
xứng trong bài toán người bán hàng (TSP). Một người bán hàng cần đi tới rất nhiều
thành phố để giao hàng, anh ta cần tìm con đường ngắn nhất đi qua tất cả các thành
phố ( mỗi thành phố một lần) sau đó quay lại thành phố suất phát. Cho một tập các
thành phố V = (v
1
, , v
n
}, một tập các cạnh (mỗi cạnh là đường nối giữa 2 thành phố)
A = ((i, j): i, j ∈ V) và chi phí d
ij
= d
ji

(độ dài đường đi từ thành phố i đến thành phố
j)liên quan đến cạnh (i, j) ∈ A, TSP là vấn đề của việc tìm kiếm đường đi độ dài tối
thiểu đóng và thăm mỗi thành phố một lần. Trong trường hợp d
ij
và d
ji
của ít nhất một
cạnh (i, j) có giá trị khác nhau bài toán TSP trở nên bất đối xứng.
Để giải bài toán TSP, AS sử dụng các vệt mùi τ
ij
gắn với mỗi cạnh (i,j) và ban
đầu được khởi tạo bởi giá trị τ
0
. Đồ thị của bài toán là một đồ thị có cấu trúc, mỗi cạnh
là đường nối giữa hai thành phố. Có m con kiến nhân tạo được đặt ngẫu nhiên tại các
đỉnh trong đồ thị, và mỗi bước lặp t của thuật toán, chúng thực hiện các thủ tục xây
dựng lời giải và cập nhật mùi. Một con kiến ở cạnh i sẽ chọn cạnh đi đến theo xác suất
ngẫu nhiên:
Trong đó τ là giá trị vết mùi η là giá trị độ dài đường đi
Bước cập nhật mùi và giả lập hành động cho kiến thực hiện như trong thuật toán
AS nêu trên.
Kết quả cuối cùng sẽ đưa ra một đường đi giải quyết bài toán TSP.
15
1.3.2 Vấn đề dò đường cho phương tiện giao thông
Đây là một phần mở rộng trực tiếp của TSP, vấn đề đầu tiên được áp dụng cho
AS, là vấn đề định tuyến xe (VRPs). Chúng ta có một tập hợp các phương tiện đóng tại
một trạm để phục vụ cho các khách hàng trước khi trở về trạm, và mục tiêu là để giảm
thiểu số lượng xe sử dụng và tổng khoảng cách chuyến đi.
Đồ thị sử dụng cho bài toán là một đồ thị có cấu trúc, mỗi đỉnh là một điểm đến,
mỗi cạnh là một đường đi có thể giữa 2 điểm đến, trọng số trên mỗi cạnh là độ dài

đường đi. Một số khó khăn gặp phải: năng lực vận chuyển là hạn chế là đối với các
chuyến xe, cũng như có thể một số khó khăn khác phát sinh từ thực tế ứng dụng,
chẳng hạn như khung thời gian, trọng tải xe, chiều dài tối đa của chuyến đi, vv . Đó là
vấn đề cơ bản mà VRP phải giải quyết, các phương pháp xếp hạng AS, các phiên bản
dựa trên xếp hạng AS và đạt kết quả tốt. Các tác giả sử dụng các tiêu chuẩn đánh giá
khác nhau để nâng cao chất lượng các giải pháp và VRP thay đổi cách xây dựng danh
sách cấm để hạn chế về tổng chiều dài tối đa của một xe và về năng lực của nó.
Từ những kết quả này, và những kết quả tuyệt vời thu được bằng cách sử dụng
ACS với TSP, SOP và QAP, ACS đã được áp dụng cho một phiên bản VRP tốt hơn để
đưa vào thực tế, được gọi là VRPTW. VRPTW được dùng để giải quyết vấn đề giảm
thiểu thời gian và chi phí trong trường hợp một đội xe phân phối hàng hóa từ kho đến
một tập hợp các khách hàng. VRPTW đã giảm thứ bậc, chức năng phân cấp: mục tiêu
đầu tiên là giảm thiểu số lượng các chuyến đi (hoặc xe) và mục tiêu thứ hai là để giảm
thiểu tổng thời gian di chuyển. Một giải pháp với một số lượng các chuyến đi thấp hơn
luôn luôn là một giải pháp thích hợp ngay cả khi thời gian đi là cao hơn. Vấn đề thứ
bậc VRPTW là rất hay gặp và có thể trong trường hợp vấn đề khó khăn rất nhỏ (đối
với ví dụ khi tổng năng lực tối thiểu của số lượng xe rất gần với tổng khối lượng để
cung cấp hoặc khi khung thời gian của khách hàng hạn hẹp), cả hai mục tiêu có thể là
đối nghịch: các giải pháp xây dựng thời gian tối thiểu có thể bao gồm một số lượng xe
cao hơn giải pháp với số lượng xe tối thiểu.
Để đáp ứng vấn đề đa mục tiêu với ACS, Multiple Ant Colony System cho
VRPTW (Mac-VRPTW) đã được đưa ra. Mac-VRPTW được tổ chức với một hệ
thống cấp bậc đàn kiến nhân tạo của ACS được thiết kế để tối ưu hóa hệ thống với
mục tiêu đa chức năng: đàn kiến ACS đầu tiên (ACS-VEI) giảm thiểu số lượng xe
trong khi đàn kiến ACS thứ hai (ACS-TIME) giảm thiểu khoảng cách chuyến đi. Cả
16
hai đều sử dụng vết mùi trên đương đi nhưng chúng hợp tác bằng cách trao đổi thông
tin lẫn nhau thông qua các cập nhật vết mùi. Trong thuật toán cả hai được tối ưu hóa
mục tiêu cùng một lúc: ACSVEI cố gắng giảm số lượng xe trong khi tìm kiếm một
giải pháp khả thi với số lượng xe luôn luôn ít hơn các giải pháp khả thi trước đó.

Do đó ACS-VEI khác với ACS truyền thống áp dụng cho TSP. Trong ACS-VEI
giải pháp tốt nhất hiện thời là giải pháp (thường là không khả thi) với số lượng cao
nhất của khách hàng được phục vụ, trong khi ở ACS giải pháp tốt nhất hiện thời là một
giải pháp ngắn nhất. Ngược lại, ACS-TIME là một ACS truyền thống: ACSTIME, tối
ưu hóa thời gian đi lại của các giải pháp khả thi được tìm thấy bởi ACS-VEI. Trong
HAS-SOP, ACS-TIME là kết hợp với một thủ tục tìm kiếm địa phương để cải thiện
chất lượng của các giải pháp tính toán. Việc tìm kiếm địa phương sử dụng cấu trúc dữ
liệu tương tự như cấu trúc dữ liệu thực hiện trong HAS-SOP và được dựa trên việc
trao đổi hai dây chuyền phụ của khách hàng. Một trong chuỗi này phụ trách sản phẩm,
còn lại thực hiện chèn thêm một khách hàng.
Thực nghiệm đã chỉ ra rằng hiệu suất của hệ thống tăng lên trong trường hợp giải
pháp tốt nhất của ACS-TIME được sử dụng, kết hợp với các giải pháp tốt nhất của
ACS − VEI, để cập nhật các vết trong ACS-VEI.
Chương 2 Bài toán phân lớp vào các thuật toán giải quyết
2.1 Nội dung bài toán
Về mặt hình thức, bài toán có thể diễn giải như sau: cho sẵn một tập huấn luyện
ta cần tạo ra một phân lớp mà có thể ánh xạ
một đối tượng vào nhãn phân loại của nó.
2.2 Thuật toán phân loại cây quyết định (ID3)
Thuật toán ID3 được sử dụng để xây dựng cây quyết định. Cho môt tập huấn
luyện T của các mẫu, mỗi mẫu có các thuộc tính c
1
, …. ,c
n
Thuật toán ID3 ( R: tập các thuộc tính chưa phân loại, C: tập các thuộc tính đã
phân loại, S: tập huấn luyện ) trả về một cây quyết định :
ID3
17
• Tạo nút gốc (Root) cho cây
• Nếu tất cả các mẫu đều là khẳng định, trả về cây một nút gốc với nhãn là

+
• Nếu tất cả các mẫu đều là phủ định, trả về cây một nút gốc với nhãn là -
• Nếu tập các thuộc tính là rỗng, trả về cây một nút gốc có nhãn là giá phổ
biến nhất của thuộc tính đich trong tập mẫu
• Trường hợp khác:
Begin:
o A  thuộc tính phân loại tập các mẫu tốt nhất trong tập các thuộc tính
o Thuộc tính quyết định cho nút gốc A
o Với mỗi giá trị có thể a
i
của thuộc tính A
 thêm một nhánh cây mới bên dưới nút gốc tương ứng với điều kiện A =
a
i

 Giả sử tập mẫu Example
vi
là tập con của tập các giá trị a
i
ở thuộc tính A
 Nếu nó là rỗng thì
• Thêm vào dưới nhánh mới này một nút lá với nhãn = giá trị phổ biến
nhất của thuộc tính đích trong tập các mẫu
 Trái lại, thêm vào dưới nhánh mới một cây con
ID3(Example
vi
, C, S - {A})
• Kết thúc
Gain entropy
S: tập huấn luyện

A thuộc tính với các giá trị a
1
,a
2
,… ,a
k
S
a
tập dữ liệu với A = a
Tầm nhìn Nhiệt độ Gió Đi chơi
Nắng 33 Không Không
Nắng 31 Có Không
U ám 32 Không Có
Mưa 28 Không Có
Mưa 26 Không Có
18
Mưa 25 Có không
U ám 24 Có Có
Nắng 29 Không không
Nắng 24 Không Có
Mưa 30 Không Có
Nắng 30 Có Có
U ám 28 Có Có
U ám 31 Không Có
Mưa 28 Có Không
2.3 Thuật toán phân loại C4.5
Đây là một mở rộng của ID3 với một số thủ tục cắt tỉa. ID3 sinh ra cây quyết
định còn C4.5 sẽ sinh ra tập luật
cắt tỉa cây
19

Cây quyết định sinh ra từ dữ liệu huấn luyện với cách thức xây dựng trên thì
đúng với hầu hết dữ liệu. Tuy nhiên trong thực tế để làm được điều đó cây quyết định
khá phức tạp và các cây con là không đồng đều.
Tỉa cây quyết định là việc thay cả cây con bằng một nút lá. Và thay thế được thực
hiện khi tỉ lệ lỗi trong cây con sẽ lớn hơn tỉ lệ lỗi trong nút lá.
Sau khi cây quyết định được sinh ra, thủ tục cắt tỉa của C4.5 bắt đầu theo hướng
từ dưới lên. Với mỗi T không phải là nút lá của cây quyết định từ tập huấn luyện S có
cây quyết định:
với mỗi T
*
i
đã được tỉa và T*
f
là cây con thường gặp nhất trong B và L là nút lá
thường gặp nhất của các lớp trong tập S. Số trương hợp chưa phân lớp trong S của T ,
T*
f
và L lần lượt là E
T
,E
Tf
và E
L
thuật toán C4.5 quyết định việc tỉa cây bằng các hàm
lỗi sau:
+ U
cf
(E
T
,S)

+ U
cf
(E
Tf
,S)
+ U
cf
(E
L
,S)
Phụ thuộc vào độ lớn của chúng C4.5 quyết định
các lá T không đổi
Thay T bằng L
Thay T bằng cây con T
f
20
2.4 Ant-Miner
2.4.1 Giới thiệu
Mục tiêu của Ant-Miner là để trích ra các quy tắc phân loại IF-THEN của biểu
mẫu IF (term1) AND (term2) AND AND (termn) THEN (class) từ dữ liệu. Mỗi điều
kiện trong luật là một ba (thuộc tính, toán tử, giá trị), trong đó toán tử đại diện cho
một toán tử quan hệ và giá trị tượng trưng cho miền giá trị các thuộc tính (ví dụ:
Sex = nam). IF tương đương với luật đứng trước và THEN là kết quả của luật, đại diện
cho lớp được dự báo bởi các luật. Một ví dụ thỏa mãn các luật đứng trước sẽ chỉ định
các lớp dự báo bởi luật. Tuy nhiên Ant-Miner nguyên bản chỉ hoạt động với các thuộc
tính xác định (rõ ràng và rời rạc), toán tử quan hệ duy nhất là “=”. Do đó các thuộc
tính liên tục cần được rời rạc hóa ở bước tiền xử lý. Về bản chất, Ant-Miner làm việc
như sau:
Nó bắt đầu với một danh sách các luật rỗng (chưa có luật nào) và lặp lại việc
thêm một luật ở một thời điểm vào danh sách đó khi số lượng ví dụ huấn luyện chưa

được gắn nhãn lớn hơn giá trị lớn nhất được chỉ ra (trong vòng lặp). Để khởi tạo một
luật, một kiến đơn bắt đầu với một luật rỗng(không có điều kiện trước nó) và thêm một
điều kiện ở một thời điểm vào luật đứng trước (lặp lại đến khi hết vòng lặp). Nó có thể
lựa chọn điều kiện để thêm vào bộ phận luật hiện tại dựa trên giá trị của lượng lớn
pheromone (τ) và một đánh giá vấn đề phụ thuộc information (η) kết hợp với các điều
kiện. Một giá trị vết mùi và một giá trị heuristic được kết hợp với các điều kiện có thể
mộ bộ ba (thuộc tính, toán tử, giá trị). Như thường lệ trong ACO, giá trị heuristic là
cố định (dựa trên thông tin lý thuyết lượng giá về dự đoán mức độ của điều kiện ), khi
giá trị vết mùi được cập nhật lại dựa vào giá trị của luật xây dựng bởi kiến. Kiến lưu
giữ điều kiện được thêm vào bộ phân luật cho đến khi bất kì điều kiên nào được thêm
vào phía trước làm cho luật gắn nhãn các ví dụ huấn luyện dưới mức được chỉ ra, làm
cho các luật quá khác biệt và không đáng tin, hoặc tất cả các thuộc tính đã được sử
dụng hết bởi kiến. Bất kỳ một luật mới nào được thêm vào đều phải bao phủ một số
trường hợp theo một ngưỡng quy định người sử dụng, được gọi là Min_cases_per_rule
(số trường hợp tối thiểu cho mỗi luật). Và điều kiện dừng ở đây là tất cả các thuộc tính
đã được sử dụng bởi các kiến, vì vậy không có thuộc tính nào để thêm vào luật.
Giá trị của vết mùi trong mỗi đường mòn được cập nhật, tăng vết mùi trong các
đường đi của kiến tiếp theo (theo chất lượng của các luật R
t
) và giảm các vết mùi trong
21
những con đường mòn khác (mô phỏng bay hơi vết mùi). Sau đó kiến khác bắt đầu
xây dựng luật của nó, bằng cách sử dụng giá trị vết mùi mới để xây dựng xác suất
ngẫu nhiên trong tìm kiếm. Quá trình này lặp đi lặp lại cho đến khi một trong hai điều
kiện sau đây được đáp ứng:
- Số lượng các quy tắc xây dựng bằng hoặc lớn hơn ngưỡng No_of_ants
người dùng chỉ định.
- Các kiến hiện tại đã xây dựng một luật đó là giống hoàn toàn luật luật
xây dựng bởi các No_rules_converg, trong đó No_rules_converg là viết tắt của
số lượng các quy tắc được sử dụng để thử nghiệm hội tụ của các loài kiến.

Một khi các vòng lặp đến khi hoàn thành, các luật tốt nhất trong số các luật xây
dựng bởi tất cả các loài kiến được thêm vào danh sách các luật khám phá ra, như đã đề
cập trước đó, và hệ thống bắt đầu một vòng lặp mới, và tất cả các con đường được
khởi tạo với cùng một giá trị của vết mùi.
Từ quan điểm khai thác dữ liệu các hoạt động cốt lõi của Ant-Miner là bước đầu
tiên của vòng lặp đến khi dừng, trong đó kiến hiện tại lặp đi lặp lại thêm một điều kiện
vào luật nó xây dựng. Một điều kiện term
ij
trong quy tắc có dạng Ai = Vij, trong đó Ai
là thuộc tính thứ i và Vij là giá trị thứ j của miền của Ai. Xác suất rằng term
ij
được
chọn để được thêm vào các nguyên tắc một phần hiện tại được cho bởi phương trình :
Trong đó:
n
ij
là giá trị của hàm đánh đối với term
ij
, giá trị n
ij
này càng tăng thì sự phân loại
của term
ij
càng rõ ràng vì vậy xác suất của toán hạng này được lựa chọn càng cao.
Hàm định nghĩa giá trị đánh giá dựa trên giả thuyết thông tin và nó được trình bày
trong phần tiếp theo. T
ij
(t) là lượng mùi liên quan tới term
ij
ở vòng lặp thứ t tương ứng

với lượng mùi hiện tại có ở vị trí thứ ij của một phần quãng đường được xây dựng bởi
22
kiến. Tính đúng đắn của luật được xây dựng bởi Kiến tốt hơn khi lượng mùi đưa vào
nhiều hơn trên những đoạn đường kiến đi qua.
Bởi vậy khi những đoạn đường tốt nhất kiến đi qua thì những term tốt nhất
(thuộc tính và giá trị) được thêm vào trong luật có nhiều mùi hơn, tăng khả năng lựa
chọn của xác suất.
a là tổng số lượng các thuộc tính
x
i
= 1 nếu A
i
chưa sử dụng
x
i
= 0 trong trường hợp ngược lại.
b
i
là số lượng giá trị trong miền thuộc tính thứ i.
Với các luật khởi tạo sau tiêu chí dừng là cần thiết bởi vì một thuộc tính có thể
chỉ xuất hiện một lần trong phía trước của luật, để tránh mâu thuẫn ví dụ như (Sex =
male) AND (Sex = female). Một sản xuất của một luật khởi tạo đã hoàn thành, đầu tiên
luật khởi tạo bởi kiến cần được cắt bớt để loại bỏ các điều kiện không thích hợp từ các
luật phía trước. Sau đó hệ quả của luật sẽ được chọn làm giá lớp hay xảy ra nhất trong
tập các ví dụ huấn luyện gắn nhãn bởi luật. Cuối cùng vết mùi được cập nhật và một
kiến khác bắt đầu khởi tạo một luật mới. Quá trình tạo các luật được lặp lại cho tới khi
các luật đạt đến số lượng đã chỉ ra hoặc kiến hiện tại đã tạo ra một luật thực sự giống
luật tạo ra bởi số lượng giá trị định nghĩa của của các kiến trước làm việc như luật
kiểm tra hội tụ. Trong đó luật tốt, dựa trên đánh giá chất lượng Q , tìm theo quá trình
lặp này được thêm vào danh sách luật và phân lớp chính xác các ví dụ huấn luyện đã

loại bỏ từ tập huấn luyện. Và một ví dụ được coi là phân loại đúng nếu thỏa mãn luật
phía trước và các lớp dự đoán bởi các luật hệ quả.
Mô tả cho thuật toán Ant-Miner:
Thuật toán Ant-Miner
begin Ant-Miner
tập huấn luyện ← tất cả các ví dụ huấn luyện;
rule list ← ∅; // tập luật rỗng
//khi tập huấn luyện vẫn lớn hơn mức nhất định
23
while |training set| > max uncovered training examples do
τ ← initializes pheromones;//khởi tạo vết mùi
rule
best
← ∅;//Lưu lại luật tốt
i ← 1;//chỉ số của kiến
repeat
rule
i
← CreateRule();
ComputeConsequent(rule
i
);//Tính toán luật
Prune(rule
i
);//tỉa luật
UpdatePheromones(τ, rule
i
);//cập nhật vết mùi
//cập nhật lâij luật tốt
if Q(rule

i
) > Q(rule
best
) then
rule
best
← rule
i
;
end
i ← i +1;//tăng chỉ số kiến
//khi số kiến vượt giới hạn
until i ≥ max number rules OR convergence ;
rule list ← rule list ∪ rule
best
;//thêm luật tốt vào danh sách luật
training set ← training set \ CorrectlyCoveredExamples(rule
best
);
end
end
Ant-Miner được so sánh với các thuật toán C4.5 và CN2. Trong điều kiện dự
đoán chính xác, kết quả chỉ ra rằng Ant-Miner có thể cạnh tranh với C4.5 và CN2. Sự
khác biệt lớn nhất có thể thấy là quan hệ phức tạp của việc khám phá các luật. Ant-
Miner có thể tìm các luật đơn quan trọng, cả trong điều kiện số lượng nhỏ các luật và
lượng nhỏ các điều kiện trong luật hơn C4.5 và CN2
24
2.4.2 Các hàm đánh giá
Chức năng heuristic (η) được dựa trên số lượng thông tin (đo bằng entropy) liên
kết với các thuộc tính i với k giá trị, tức là (i | j). Lượng thông tin được cho bởi phương

trình :
trong đó:
• k là số các lớp học trong dataset;
• | Tij | là tổng số các trường hợp trong Tij phân vùng dữ liệu (phân vùng chứa
các trường hợp thuộc tính i bằng với giá trị j);
• Thường Tij
w
đại diện cho số trường hợp trong đó Tij thuộc về lớp w.
entropy (infoTij) càng lớn, có nghĩa là lớp phân bố đều hơn, nhỏ hơn sức mạnh
tiên đoán của các cặp thuộc tính-giá trị (i | j).
Trong trường hợp thuộc tính i có giá trị j (i | j) không xuất hiện trong bất kỳ
trường hợp của phân vùng Tij, đó là, giá trị k là không có mặt trong bộ đào tạo, sau đó
chúng tôi đặt infoTij = log2 (số lớp) , là entropy tối đa. Nếu thuộc tính i với k giá trị
xác định chỉ có một lớp trong Tij phân vùng, sau đó infoTij = 0, là entropy tối thiểu.
Lớn hơn giá trị của infoTij (0 ≤ infoTij ≤ log2 (số lớp học)), các xác suất nhỏ hơn mà
các con kiến đã chọn thuộc tính i có giá trị j. Vì vậy, các tiêu chí heuristic được cho
bởi phương trình :
trong đó:
• a là tổng số các thuộc tính;
• b
i
là số giá trị trong lĩnh vực thuộc tính i.
25