Xem mẫu
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI
Khoa Công nghệ thông tin
-------- --------
BÁO CÁO NGHIÊN CỨU KHOA HỌC
Đề tài
THUẬT TOÁN KIẾN SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT
Giáo viên hướng dẫn: Thầy Đỗ Trung Kiên
Sinh viên thực hiện : Quách Thị Hái Oanh _K54A
Nguyễn Thị Hiện_K55B
Trần Thị Hằng_K55B
Nguyễn Thị Hương _K55B
Hà Nội, 04-2008
1
LỜI MỞ ĐẦU
Sự phức tạp của các bài toán tối ưu tổ hợp xuất hiện trong nhiều lĩnh vực
khác nhau như: kinh tế, thương mại, khoa học, công nghiệp và y học. Tuy nhiên,
có một số bài toán khi giải quyết gặp khó khăn trong ứng dụng. Cái khó vốn có là
việc giải quyết các bài toán đã nêu ra trong lý thuyết khoa học máy tính trong thực
tế như một số bài toán đã biết là NP-hard, ở đó không có thuật toán đã biết giải
quyết chúng trong thời gian đa thức.
Metaheuristics hợp nhất các khái niệm từ nhiều lĩnh vực khác nhau như di
truyền học, sinh vật học, trí tuệ nhân tạo, toán học và vật lý… Ví dụ của
metaheuristics bao gồm thuật toán luyện thép, ngăn cản tìm kiếm, tìm kiếm lặp,
tìm kiếm biến gần đúng, thủ tục tìm kiếm thích ứng tham lam ngẫu nhiên và thuật
toán tiến hoá. Thuật toán metaheuristics gần đây nhất là thuật toán kiến (ACO),
được sáng tạo bởi đường tìm kiếm ngắn nhất trong cách kiếm ăn của những con
kiến khác nhau. Tuy nhiên từ công việc ban đầu của Dorigo, Maniezzo, và Colorni
trong hệ thống kiến (Ant System), ACO nhanh chóng trở thành tìm kiếm hoàn
thiện trong lĩnh vực: một số lượng lớn tác giả phát triển mô hình phức tạp hơn để
sử dụng thành công giải quyết một lượng lớn kết hợp bài toán tối ưu phức tạp và
đi sâu vào lý thuyết thuật toán bây giờ trở thành cái sẵn có.
Ở đây, em đã tìm hiểu thuật toán kiến và sử dụng thuật toán này để giải
quyết bài toán Maxsat. Thuật toán này có ứng dụng để giải quyết các bài toán tổ
hợp tối ưu, đặc biệt là một số bài toán đang gặp khó khăn trong việc tìm lời giải.
2
MỤC LỤC
Chương I: TỔNG QUAN THUẬT TOÁN KIẾN ........................................................ 4
I. Thuật toán kiến......................................................................................................... 4
1. Đàn kiến tự nhiên (natural ant colonies) .............................................................. 4
2.Từ những con kiến tự nhiên tới thuật toán ACO .................................................... 6
3. Các loại mô hình ACO ......................................................................................... 7
4. Ứng dụng của ACO.............................................................................................. 7
5. Các bước để giải quyết một bài toán bởi ACO ..................................................... 9
II. Một số ví dụ minh hoạ .......................................................................................... 10
1. Bài toán người du lịch ....................................................................................... 10
2. Xác định ma trận trọng số của mạng Neuron ..................................................... 10
Chương II: XÂY DỰNG KHUNG THUẬT TOÁN KIẾN ....................................... 11
I. Thiết kế khung thuật toán kiến................................................................................ 11
* Sơ đồ chung của thuật toán kiến ......................................................................... 11
2. Lớp đòi hỏi (require) ......................................................................................... 16
II. Khung thuật toán tuần tự ....................................................................................... 17
III. Khung thuật toán song song ................................................................................. 19
Chương III: SỬ DỤNG KHUNG THUẬT TOÁN KIẾN ĐỂ GIẢI QUYẾT BÀI
TOÁN MAXSAT ......................................................................................................... 22
I. Giải quyết bài toán Maxsat ..................................................................................... 22
1. Bài toán Maxsat ................................................................................................. 22
II. Kết quả thực nghiệm ............................................................................................. 24
3
Chương I: TỔNG QUAN THUẬT TOÁN KIẾN
I. Thuật toán kiến
1. Đàn kiến tự nhiên (natural ant colonies)
Loài kiến là loài sâu bọ có tính chất xã hội, chúng sống thành từng đàn, bởi
vậy có sự tác động lẫn nhau, chúng thạo tìm kiếm thức ăn và hoàn thành những
nhiệm vụ từ kiến chỉ huy. Một điều thú vị trong tìm kiếm thức ăn của vài con kiến
đặc biệt là khả năng của chúng để tìm kiếm đường đi ngắn nhất giữa tổ kiến và
nguồn thức ăn. Trên thực tế, điều dễ nhận thấy có trong suy nghĩ nhưng nhiều con
kiến hầu hết không nhận ra vì chúng không dùng thị giác để tìm kiếm những đầu
mối thức ăn.
Trong quá trình đi giữa tổ và nguồn thức ăn, vài con kiến tích tụ một chất
được gọi là mùi lạ (pheromone). Nếu không có mùi lạ sẵn có, những con kiến di
chuyển ngẫu nhiên, nhưng khi có mặt của mùi lạ này chúng có xu hướng đi theo
mùi lạ. Trên thực tế, cuộc thí nghiệm của nhà nghiên cứu sinh là những con kiến
theo thuyết tự nhiên thích những con đường được đánh dấu bởi tập hợp nhiều mùi
lạ. Trong qúa trình thực hiện, lựa chọn giữa những con đường tìm thấy khác nhau
khi có vài con đường phân cách. Sau đó kiến sẽ lựa chọn xác suất một con đường
qua số lượng mùi lạ: mùi lạ càng nhiều thì sự lựa chọn càng cao. Bởi vậy những
con kiến đổi hướng theo mùi lạ trên đường đi, chúng được đề cập như sau: kết quả
tìm kiếm thức ăn trong quá trình tăng cường ảnh hưởng từ sự hình thành của con
đường được đánh dấu bởi tập hợp nhiều mùi lạ. Cách tìm thức ăn này tập trung
kiến tìm đường đi ngắn nhất giữa tổ và nguồn thức ăn.
Kĩ thuật thế nào tập trung được kiến tới phạm vi con đường ngắn nhất được
minh hoạ ở hình 1. Ở đó, không có mùi lạ nào trong môi trường và, khi kiến đến
những chỗ giao nhau, chúng ngẫu nhiên lựa chọn một ngả đường. Tuy nhiên, như
kiến đi du lịch, con đường triển vọng nhất tiếp nhận số lượng mùi lạ nhiều hơn sau
vài lần đi. Nhờ đó, những con đường ngắn hơn, kiến sẽ lựa chọn chúng để tới thức
ăn nhanh hơn và để bắt đầu trở lại hành trình kiếm thức ăn sớm hơn. Từ khi ngả
4
đường ngắn hơn được chọn mùi lạ tồn tại nhiều hơn, quyết định của kiến có xu
hướng tiến về ngả đường ngắn hơn, vì thế, lựa chọn con đường nhiều mùi hơn khi
kiến trở lại nhiều hơn ngả đường dài hơn. Kết quả cuối cùng của quá trình này là
sự tăng xu hướng tiến tới ngả đường ngắn và kết thúc, hội tụ lại là con đường ngắn
nhất.
Thủ tục sau đó được bổ sung trong môi trường tự nhiên bởi thực tế mùi lạ
sẽ bị bay hơi sau vài lần. Con đường này triển vọng ít dần vì mất dần mùi lạ bởi vì
nó được kiến đi ngày càng ít. Tuy nhiên vài nhà sinh vật học đã nghiên cứu chỉ ra
mùi lạ rất bền, vì thế ít ảnh hưởng của sự bay hơi trên đường đi ngăn nhất của quá
trình tìm kiếm thức ăn.
Hình 1
Vài cuộc thí nghiệm được báo cáo cho thấy số đông lấy thêm trong tự nhiên
với một giới hạn, như kết quả tồn tại lâu dài của mùi lạ, nó là điều khó để kiến
quên đường đi với nhiều mùi lạ, mặc dù chúng tìm thấy được đường đi ngắn hơn.
Chú ý, nếu thức ăn trực tiếp dịch trong máy để thiết kế một thuật toán tìm kiếm,
chúng ta có thể có một thuật toán nhanh hơn trở thành tối ưu.
5
nguon tai.lieu . vn
Khoa Công nghệ thông tin
-------- --------
BÁO CÁO NGHIÊN CỨU KHOA HỌC
Đề tài
THUẬT TOÁN KIẾN SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT
Giáo viên hướng dẫn: Thầy Đỗ Trung Kiên
Sinh viên thực hiện : Quách Thị Hái Oanh _K54A
Nguyễn Thị Hiện_K55B
Trần Thị Hằng_K55B
Nguyễn Thị Hương _K55B
Hà Nội, 04-2008
1
LỜI MỞ ĐẦU
Sự phức tạp của các bài toán tối ưu tổ hợp xuất hiện trong nhiều lĩnh vực
khác nhau như: kinh tế, thương mại, khoa học, công nghiệp và y học. Tuy nhiên,
có một số bài toán khi giải quyết gặp khó khăn trong ứng dụng. Cái khó vốn có là
việc giải quyết các bài toán đã nêu ra trong lý thuyết khoa học máy tính trong thực
tế như một số bài toán đã biết là NP-hard, ở đó không có thuật toán đã biết giải
quyết chúng trong thời gian đa thức.
Metaheuristics hợp nhất các khái niệm từ nhiều lĩnh vực khác nhau như di
truyền học, sinh vật học, trí tuệ nhân tạo, toán học và vật lý… Ví dụ của
metaheuristics bao gồm thuật toán luyện thép, ngăn cản tìm kiếm, tìm kiếm lặp,
tìm kiếm biến gần đúng, thủ tục tìm kiếm thích ứng tham lam ngẫu nhiên và thuật
toán tiến hoá. Thuật toán metaheuristics gần đây nhất là thuật toán kiến (ACO),
được sáng tạo bởi đường tìm kiếm ngắn nhất trong cách kiếm ăn của những con
kiến khác nhau. Tuy nhiên từ công việc ban đầu của Dorigo, Maniezzo, và Colorni
trong hệ thống kiến (Ant System), ACO nhanh chóng trở thành tìm kiếm hoàn
thiện trong lĩnh vực: một số lượng lớn tác giả phát triển mô hình phức tạp hơn để
sử dụng thành công giải quyết một lượng lớn kết hợp bài toán tối ưu phức tạp và
đi sâu vào lý thuyết thuật toán bây giờ trở thành cái sẵn có.
Ở đây, em đã tìm hiểu thuật toán kiến và sử dụng thuật toán này để giải
quyết bài toán Maxsat. Thuật toán này có ứng dụng để giải quyết các bài toán tổ
hợp tối ưu, đặc biệt là một số bài toán đang gặp khó khăn trong việc tìm lời giải.
2
MỤC LỤC
Chương I: TỔNG QUAN THUẬT TOÁN KIẾN ........................................................ 4
I. Thuật toán kiến......................................................................................................... 4
1. Đàn kiến tự nhiên (natural ant colonies) .............................................................. 4
2.Từ những con kiến tự nhiên tới thuật toán ACO .................................................... 6
3. Các loại mô hình ACO ......................................................................................... 7
4. Ứng dụng của ACO.............................................................................................. 7
5. Các bước để giải quyết một bài toán bởi ACO ..................................................... 9
II. Một số ví dụ minh hoạ .......................................................................................... 10
1. Bài toán người du lịch ....................................................................................... 10
2. Xác định ma trận trọng số của mạng Neuron ..................................................... 10
Chương II: XÂY DỰNG KHUNG THUẬT TOÁN KIẾN ....................................... 11
I. Thiết kế khung thuật toán kiến................................................................................ 11
* Sơ đồ chung của thuật toán kiến ......................................................................... 11
2. Lớp đòi hỏi (require) ......................................................................................... 16
II. Khung thuật toán tuần tự ....................................................................................... 17
III. Khung thuật toán song song ................................................................................. 19
Chương III: SỬ DỤNG KHUNG THUẬT TOÁN KIẾN ĐỂ GIẢI QUYẾT BÀI
TOÁN MAXSAT ......................................................................................................... 22
I. Giải quyết bài toán Maxsat ..................................................................................... 22
1. Bài toán Maxsat ................................................................................................. 22
II. Kết quả thực nghiệm ............................................................................................. 24
3
Chương I: TỔNG QUAN THUẬT TOÁN KIẾN
I. Thuật toán kiến
1. Đàn kiến tự nhiên (natural ant colonies)
Loài kiến là loài sâu bọ có tính chất xã hội, chúng sống thành từng đàn, bởi
vậy có sự tác động lẫn nhau, chúng thạo tìm kiếm thức ăn và hoàn thành những
nhiệm vụ từ kiến chỉ huy. Một điều thú vị trong tìm kiếm thức ăn của vài con kiến
đặc biệt là khả năng của chúng để tìm kiếm đường đi ngắn nhất giữa tổ kiến và
nguồn thức ăn. Trên thực tế, điều dễ nhận thấy có trong suy nghĩ nhưng nhiều con
kiến hầu hết không nhận ra vì chúng không dùng thị giác để tìm kiếm những đầu
mối thức ăn.
Trong quá trình đi giữa tổ và nguồn thức ăn, vài con kiến tích tụ một chất
được gọi là mùi lạ (pheromone). Nếu không có mùi lạ sẵn có, những con kiến di
chuyển ngẫu nhiên, nhưng khi có mặt của mùi lạ này chúng có xu hướng đi theo
mùi lạ. Trên thực tế, cuộc thí nghiệm của nhà nghiên cứu sinh là những con kiến
theo thuyết tự nhiên thích những con đường được đánh dấu bởi tập hợp nhiều mùi
lạ. Trong qúa trình thực hiện, lựa chọn giữa những con đường tìm thấy khác nhau
khi có vài con đường phân cách. Sau đó kiến sẽ lựa chọn xác suất một con đường
qua số lượng mùi lạ: mùi lạ càng nhiều thì sự lựa chọn càng cao. Bởi vậy những
con kiến đổi hướng theo mùi lạ trên đường đi, chúng được đề cập như sau: kết quả
tìm kiếm thức ăn trong quá trình tăng cường ảnh hưởng từ sự hình thành của con
đường được đánh dấu bởi tập hợp nhiều mùi lạ. Cách tìm thức ăn này tập trung
kiến tìm đường đi ngắn nhất giữa tổ và nguồn thức ăn.
Kĩ thuật thế nào tập trung được kiến tới phạm vi con đường ngắn nhất được
minh hoạ ở hình 1. Ở đó, không có mùi lạ nào trong môi trường và, khi kiến đến
những chỗ giao nhau, chúng ngẫu nhiên lựa chọn một ngả đường. Tuy nhiên, như
kiến đi du lịch, con đường triển vọng nhất tiếp nhận số lượng mùi lạ nhiều hơn sau
vài lần đi. Nhờ đó, những con đường ngắn hơn, kiến sẽ lựa chọn chúng để tới thức
ăn nhanh hơn và để bắt đầu trở lại hành trình kiếm thức ăn sớm hơn. Từ khi ngả
4
đường ngắn hơn được chọn mùi lạ tồn tại nhiều hơn, quyết định của kiến có xu
hướng tiến về ngả đường ngắn hơn, vì thế, lựa chọn con đường nhiều mùi hơn khi
kiến trở lại nhiều hơn ngả đường dài hơn. Kết quả cuối cùng của quá trình này là
sự tăng xu hướng tiến tới ngả đường ngắn và kết thúc, hội tụ lại là con đường ngắn
nhất.
Thủ tục sau đó được bổ sung trong môi trường tự nhiên bởi thực tế mùi lạ
sẽ bị bay hơi sau vài lần. Con đường này triển vọng ít dần vì mất dần mùi lạ bởi vì
nó được kiến đi ngày càng ít. Tuy nhiên vài nhà sinh vật học đã nghiên cứu chỉ ra
mùi lạ rất bền, vì thế ít ảnh hưởng của sự bay hơi trên đường đi ngăn nhất của quá
trình tìm kiếm thức ăn.
Hình 1
Vài cuộc thí nghiệm được báo cáo cho thấy số đông lấy thêm trong tự nhiên
với một giới hạn, như kết quả tồn tại lâu dài của mùi lạ, nó là điều khó để kiến
quên đường đi với nhiều mùi lạ, mặc dù chúng tìm thấy được đường đi ngắn hơn.
Chú ý, nếu thức ăn trực tiếp dịch trong máy để thiết kế một thuật toán tìm kiếm,
chúng ta có thể có một thuật toán nhanh hơn trở thành tối ưu.
5