Luận văn Thạc sĩ Công nghệ thông tin: Phương pháp ACO và bài toán thời khoá biểu cho trường Đại học

ĐẠI HỌC QUỐC GIA HÀ NỘI

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

NGUYỄN VĂN TUÂN

PHƯƠNG PHÁP ACO VÀ BÀI TOÁN

THỜI KHOÁ BIỂU CHO TRƯỜNG ĐẠI HỌC

LUẬN VĂN THẠC SĨ NGÀNH CÔNG NGHỆ THÔNG TIN

Hà Nội - 2015

ĐẠI HỌC QUỐC GIA HÀ NỘI

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

NGUYỄN VĂN TUÂN

PHƯƠNG PHÁP ACO VÀ BÀI TOÁN

THỜI KHOÁ BIỂU CHO TRƯỜNG ĐẠI HỌC

Ngành: Công nghệ Thông tin

Chuyên ngành: Hệ thống Thông tin

Mã số: 60.48.01.04

LUẬN VĂN THẠC SĨ NGÀNH CÔNG NGHỆ THÔNG TIN

NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS HOÀNG XUÂN HUẤN

Hà Nội - 2015

LỜI CẢM ƠN

Tôi xin gửi lời cảm ơn chân thành nhất tới PGS.TS. Hoàng Xuân Huấn, người thầy đáng kính đã tận tình chỉ bảo, hướng dẫn tôi trong suốt quá trình tìm hiểu, nghiên cứu và hoàn thiện luận văn. Với kiến thức sâu rộng, nhiều năm nghiên cứu trong lĩnh vực tối ưu hóa cũng như phương pháp tối ưu hệ kiến của thầy đã giúp tôi hiểu rõ, sâu sắc nhiều bài toán khó khăn gặp phải trong quá trình nghiên cứu. Thầy cũng đưa ra những góp ý chi tiết, tỉ mỉ hết sức quý báu giúp cho tôi có thể hoàn thành quyển luận văn này.

Tôi cũng xin được gửi lời cảm ơn sâu sắc tới Tiến Sĩ Đỗ Đức Đông và Thạc sĩ Trần Ngọc Hà, những người đã giúp đỡ tôi giải quyết những khúc mắc trong quá trình viết chương trình để chạy thực nghiệm.

Do thời gian và kiến thức có hạn nên luận văn chắc không tránh khỏi những thiếu sót nhất định. Tôi rất mong nhận được những sự góp ý quý báu của thầy cô và các bạn.

Hà Nội, tháng 01 năm 2015

Nguyễn Văn Tuân

TÓM TẮT

ài toán lập thời khóa biểu là một trong những lĩnh vực được nhiều người uan

tâm vì tính ứng ng cao của nó trong các t chức giáo c, trường học trên thế giới,

là vấn đề đau đầu mà hàng năm bất k hệ thống trường học nào trên thế giới cũng phải

đối mặt. ác bài toán lập thời khóa biểu rất phong phú và đa ạng b i các ràng buộc và yêu cầu của t ng t chức.

Bài toán thời khóa biểu thuộc lớp NP khó [12] nên khó giải bằng các thuật toán

truyền thống. Đến nay các thuật toán mô phỏng tự nhiên tỏ ra là phương pháp hữu hiệu

nhất để giải các bài toán này. Thuật toán i truyền là một trong những thuật toán mô phỏng tự nhiên đầu tiên dựa vào sự tiến hóa và phát triển của ngành di truyền học. Gần đây phương pháp tối ưu hóa đàn kiến o Dorigo đề xuất là một trong số các cách tiếp cận mới nhất. Đây là hai thuật toán tiêu biểu cho lớp thuật toán mô phỏng tự nhiên để

giải uyết các bài toán tối ưu khó nói chung và bài toán thời khóa biểu nói riêng. M c

tiêu luận văn “Phương pháp ACO và bài toán thời khoá biểu cho trường Đại học” là

nghiên cứu và áp d ng phương pháp A O vào bài toán thời khoá biểu. Phương pháp

ACO sử d ng quy tắc cập nhật mùi Max-Min Ant System (MMAS) đã được áp d ng

cho bài toán thời khoá biểu và đã có kết quả khá tốt so với các phương pháp khác.

Luận văn sẽ xem xét áp d ng thuật toán cập nhật mùi Smooth-Max Min Ant

System(SMMAS) cho bài toán thời khoá biểu. Smooth-Max Min Ant System là quy

tắc cập nhật mùi mới được PGS.TS Hoàng Xuân Huấn và đồng nghiệp đề xuất năm

2011. Hệ kiến SMMAS đã được áp d ng vào bài toán TSP và chứng tỏ được hiệu quả

của nó hơn hẳn hệ kiến MMAS (một hệ kiến được áp dùng nhiều nhất hiện nay).

Trong luận văn này chúng tối tiến hành cài đặt mới thuật toán ACO theo quy tắc cập

nhật mùi SMMAS và chạy thực nghiệm so sánh với hai quy tắc cập nhật mùi MMAS,

i

kết quả cho thấy hai thuật toán SMMAS có kết quả tốt hơn hẳn so với MMAS.

LỜI CAM ĐOAN

Tôi xin cam đoan rằng đây là công trình nghiên cứu của cá nhân tôi ưới sự hướng dẫn giúp đỡ của PGS.TS. Hoàng Xuân Huấn. Các kết quả được viết chung với các tác giả khác đều được sự đồng ý của tác giả trước khi đưa vào luận văn. Trong toàn bộ nội dung nghiên cứu của luận văn, các vấn đề được trình bày đều là những tìm hiểu và nghiên cứu của chính cá nhân tôi hoặc là được trích dẫn t các nguồn tài liệu có ghi tham khảo rõ ràng, hợp pháp.

Trong luận văn, tôi có tham khảo đến một số tài liệu của một số tác giả được

liệt kê tại m c tài liệu tham khảo

Hà nội, tháng 01 năm 2016

ii

Nguyễn Văn Tuân

MỤC LỤC TÓM TẮT ......................................................................................................................... i

LỜI AM ĐOAN ........................................................................................................... ii

MỤC LỤC ..................................................................................................................... iii

DANH SÁCH CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT .................................................... v

DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ ........................................................................ vi

DANH SÁCH BẢNG BIỂU .......................................................................................... vi

MỞ ĐẦU ......................................................................................................................... 1

hương 1. GIỚI THIỆ I TO N P T ỜI A IỂ .................................... 3

1.1. ác bài toán lập thời khóa biểu ............................................................................ 3

1.1.1. ài toán lập thời khóa biểu cho trường ph thông (School timetabling) ...... 3

1.1.2. Bài toán xếp lịch thi (Examination timetabling) ........................................... 4

1.1.3. ài toán lập thời khóa biểu cho trường đại học ( niversity timetabling) ..... 4

1.2. Các cách tiếp cận hiện nay ................................................................................... 4

hương 2. P ƯƠNG P P TỐI Ư Đ N IẾN ........................................................ 8

2.1. T kiến tự nhiên đến kiến nhân tạo ...................................................................... 8

2.1.1. Kiến tự nhiên ................................................................................................. 8

2.1.2. Kiến nhân tạo (Artificial Ant) ..................................................................... 11

2.2. Phương pháp tối ưu đàn kiến .............................................................................. 11

2.3. Đồ thị cấu trúc .................................................................................................... 12

2.4. Mô tả thuật toán ACO t ng quát ........................................................................ 14

2.5. Các hệ kiến ......................................................................................................... 16

2.5.1. Hệ kiến AS .................................................................................................. 16

2.5.2. Hệ kiến ACS ................................................................................................ 18

2.5.3. Hệ kiến MAX-MIN ..................................................................................... 20

2.5.4. Hệ kiến ba mức ............................................................................................ 22

2.5.5. Hệ kiến đa mức ........................................................................................... 23

2.5.6. Hệ kiến Smooth-Max Min ........................................................................... 23

2.6. Một số vấn đề liên quan ...................................................................................... 24

2.6.1. Đặc tính hội t ............................................................................................. 24

2.6.2. ACO kết hợp với tìm kiếm địa phương ....................................................... 25

2.6.3. Thông tin heuristic ....................................................................................... 25

iii

2.6.4. Số lượng kiến ............................................................................................... 26

2.6.5. Tham số bay hơi .......................................................................................... 26

hương 3. P ƯƠNG P P A O CHO BÀI TOÁN UTCP ....................................... 27

3.1. Áp d ng thuật toán ACO cho bài toán UCTP .................................................... 27

3.1.1. ây ựng đồ thị cấu trúc cho bài toán TP ............................................. 27

3.1.2. Ma trận m i ................................................................................................. 28

3.1.3. Thông tin heuristic ....................................................................................... 28

3.1.4. Tìm kiếm c c bộ .......................................................................................... 28

3.1.5. Thuật toán ghép cặp cực đại để tìm lời giải hoàn chỉnh .............................. 30

3.1.6. Mô tả thuật toán ........................................................................................... 29

3.2. Các thuật toán ACO được áp d ng cho bài toán UCTP ..................................... 32

3.2.1. Thuật toán hệ kiến MMAS .......................................................................... 32

3.2.2. Thuật toán hệ kiến Smooth-Max Min Ant System...................................... 34

hương 4. T ỰC NGHIỆM ......................................................................................... 36

4.1. Dữ liệu thực nghiệm ........................................................................................... 36

4.2. Thực nghiệm ....................................................................................................... 39

4.3. Kết quả ................................................................................................................ 39

ẾT N ................................................................................................................... 42

iv

TÀI LIỆU THAM KHẢO ............................................................................................. 43

DANH SÁCH CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT

STT Từ viết tắt

1 ACO

2 AS

3 ACS

4 MMAS

5 SMMAS

6 MLAS

7 Từ hoặc cụm từ Ant Colony Optimization (Tối ưu hóa đàn kiến) Ant System (Hệ kiến AS) Ant Colony System (Hệ kiến ACS) Max-Min Ant System (Hệ kiến MMAS) Smooth-Max Min Ant System (Hệ kiến MMAS trơn) Multi-level Ant System (Hệ kiến đa mức MLAS) Optimization Opt

8 Avg

9 TSP Average Travelling Salesman Problem ( ài toán người chào hàng)

10 global-best g-best

11 iteration-best i-best

v

12 UCTP University Course Timetabling Problem (bài toán xếp thời khoá biểu)

DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ

Hình 2.1. Thể hiện hành vi của mỗi con kiến trong tự nhiên .......................................... 8

Hình 2.2: Thực nghiệm cây cầu đôi ................................................................................ 9

Hình 2.3. Thí nghiệm b xung ....................................................................................... 10

ình 2.4. Đồ thị cấu trúc t ng quát cho bài toán cực trị hàm .................... 14

Hình 2.5. Lựa chọn đỉnh đi tiếp theo ............................................................................. 15

ình 2.6. Đặc tả thuật toán ACO .................................................................................. 15

ình 3.1. Đồ thị cấu trúc cho bài toán UCTP ............................................................... 27

DANH SÁCH BẢNG BIỂU

ảng 4.1. Giá trị các tham số đầu vào cho ba loại bộ dữ liệu ....................................... 39

ảng 4.2. ác tham số tĩnh sử d ng cho bài toán UCTP các thuật toán đàn kiến ..... 40

vi

ảng 4.4. So sánh thuật toán hệ kiến SMMAS, đa mức và hệ kiến Max-Min với các bộ dữ liệu điển hình ............................................................................................................ 41

MỞ ĐẦU

ài toán lập thời khóa biểu là một trong những lĩnh vực được nhiều người uan

tâm vì tính ứng ng cao của nó trong các t chức giáo c, trường học trên thế giới,

là vấn đề đau đầu mà hàng năm bất k hệ thống trường học nào trên thế giới cũng phải đối mặt. ác bài toán lập thời khóa biểu rất phong phú và đa ạng b i các ràng buộc

và yêu cầu của t ng t chức.

Bài toán thời khóa biểu thuộc lớp NP khó[12] nên khó giải bằng các thuật toán

truyền thống. Đến nay các thuật toán mô phỏng tự nhiên tỏ ra là phương pháp hữu hiệu

nhất để giải các bài toán này. Thuật toán i truyền là một trong những thuật toán mô phỏng tự nhiên đầu tiên dựa vào sự tiến hóa và phát triển của ngành di truyền học. Gần

đây phương pháp tối ưu hóa đàn kiến o Dorigo đề xuất là một trong số các cách tiếp cận mới nhất. Đây là hai thuật toán tiêu biểu cho lớp thuật toán mô phỏng tự nhiên để

giải uyết các bài toán tối ưu khó nói chung và bài toán thời khóa biểu nói riêng.

Trong nước ta, mô hình đào tạo đại học theo niên chỉ đang chuyển sang đào tạo

hệ tín chỉ nhưng bài toán này chưa được nghiên cứu nhiều và trong thực tế chưa có

phần mềm nào sử d ng được. Với đề tài “Phương pháp ACO và bài toán thời khoá

biểu cho trường Đại Học”, luận văn mạnh ạn nghiên cứu phương pháp giải cho bài

toán lập thời khóa biểu trường đại học hệ tín chỉ theo mẫu của một bài toán chu n trên

internet (www.metaheuristics.org) và thực hiện thực nghiệm trên thuật toán tối ưu đàn

kiến. Đối với thuật toán tối ưu đàn kiến chúng tôi tìm hiểm các hệ kiến đã áp ng cho

bài toán thời khoá biểu hiện nay bao gồm hệ kiến ACS, hệ kiến Max-Min Ant

System(MMAS) đồng thời sử d ng qui tắc cập nhật mùi Smooth-Max Min Ant

System(SMMAS) mới áp d ng cho bào toán này. iệu uả của thuật toán áp d ng quy

tắc cập nhật mùi Smooth-Max Min Ant System so với MMAS được so sánh bằng thực

nghiệm dựa trên các test chu n trên mạng (http://iridia.ulb.ac.be/~msampels/tt.data).

Kết quả thực nghiệm cho thấy hiệu quả của thuật toán Smooth-Max Min tốt hơn Max-

Min. Vì thời gian làm luận văn ngắn, nên chúng tôi chưa đưa ra được phần mềm sử ng được của bài toán này, hi vọng trong thời gian tới có thể phát triển mô hình này

áp ng cho các bài toán lập thời khóa biểu cho một số trường đại học thực tế Việt Nam.

Phần còn lại của luận văn được t chức như sau:

1

Chương 1: Trong chương này luận văn giới thiệu về các mô hình thời khóa biểu cho các trường học bao gồm cả trường ph thông và đại học trên thế giới và bài toán chu n TP ( niversity ourse TimeTabling Problem), đồng thời giới thiệu ua về một số cách tiếp cận hiện nay cho bài toán lập thời khóa biểu.

Chương 2: Giới thiệu phương pháp tối ưu hóa đàn kiến lịch sử phát triển, các

thuật toán A O, và một số nguyên tắc ứng ng A O

Chương 3: Trình bày về cách thức chung để áp ng tối ưu đàn kiến giải bài toán UCTP. (Đồng thời trong chương này chúng tôi trình bày các cải tiến c thể trong

áp d ng tối ưu hóa đàn kiến với bài toán UCTP)

Chương 4: Chương này giới thiệu về bộ ữ liệu chu n cho bài toán TP, các

kết uả thực nghiệm và đánh giá trên thuật toán tối ưu đàn kiến sử d ng các quy tắc

2

cập nhật mùi SMMAS và MMAS.

Chương 1. GIỚI THIỆU BÀI TOÁN ẬP THỜI H A BIỂU

1.1. C n h h u

ác t chức giáo c trên thế giới hàng k phải đối mặt với một công việc khó

khăn là đưa ra lịch học của các học viên đáp ứng được nhiều ràng buộc khó và phức tạp. ài toán lập thời khóa biểu là một bài toán tối ưu t hợp NP-khó[12] một trường

hợp riêng của bài toán lập lịch trong đó đưa ra một chuỗi các sự kiện (thông thường là

các môn học, bài giảng hoặc các môn thi) và bao gồm các giáo viên và học viên trong

một khoảng thời gian định trước và thỏa mãn một tập hợp các ràng buộc của t ng loại thời khóa biểu khác nhau. ác ràng buộc bao gồm khả năng học tập của sinh viên và

khả năng làm việc của giáo viên, sức chứa của ph ng học và yêu cầu đáp ứng của các

sự kiện.

ài toán thời khóa biểu bao gồm rất nhiều loại khác nhau đã được đưa ra xuất

phát t các loại sự kiện, mỗi loại t chức (trường học, viện nghiên cứu hoặc trường đại

học ...) và các loại ảnh hư ng khác đến các ràng buộc của bài toán t y thuộc vào t ng

điều kiện khác nhau. Nói chung bài toán lập thời khóa biểu được chia làm 3 ạng chung được mô tả khác nhau ài toán lập thời khóa biểu cho trường ph thông, bài

toán lập thời khóa biểu cho trường đại học, bài toán xếp lịch thi.

1.1.1. B n h h u h ư ng h h ng S h ng

ài toán lập thời khóa biểu cho trường ph thông hay bài toán phân chia giáo

viên, lớp học trong một tuần đối với tất cả các môn học của một trường học.

Với ba tập hợp cho trước là tập giáo viên, tập lớp học và tập tiết học và một ma

trận ràng buộc số bài giảng một giáo viên được phân công ạy một lớp. ài toán yêu

cầu phân chia các bài giảng vào các tiết sao cho không giáo viên hay lớp học nào có

c ng một bài giảng trong c ng một thời gian và mỗi giáo viên đều có một số lượng

nhất định các bài giảng với mỗi lớp học.

ác ràng buộc thêm vào bao gồm chế độ nghỉ của giáo viên, các bài giảng liên tiếp nhau cho hai hay nhiều lớp học, các giáo viên tr ng giờ ạy, và tính phức tạp của

một thời khóa biểu cho một lớp. Đặc biệt là ràng buộc chặt các lớp học phải có giờ trong bất k tiết học nào tr tiết đầu hoặc tiết cuối của ngày. Độ chặt này là yếu tố uyết định sự khác nhau giữa thời khóa biểu cho trường ph thông và thời khóa biểu cho trường đại học. Thực tế, những ràng buộc như vậy làm cho bài toán lập thời khóa

biểu cho trường ph thông phải lấp đầy các tiết học chính nhưng có thể tồn tại một

3

ràng buộc khó có thể thỏa mãn được.

1.1.2. Bài toán xếp lịch thi (Examination timetabling)

ài toán lập lịch thi yêu cầu đưa ra bộ lịch của một số các k thi cho trước với

một lượng thời gian cho trước và tập hợp các ph ng thi.

ài toán lập lịch thi tương tự như bài toán lập thời khóa biểu cho trường đại học

nhưng ta cần phân biệt sự khác nhau giữa hai bài toán này. ài toán lập lịch thi có

những đặc điểm khác sau đây:

 hỉ có một k thi cho mỗi một môn thi.

 ác điều kiện xung đột nói chung là hạn chế. Thực tế, chúng ta có thể chấp nhận một sinh viên có thể bỏ ua một bài giảng o sự chồng ch o các môn

học nhưng không có sinh viên nào được ph p bỏ ua một k thi.

 Và một số ràng buộc khác nhau ví hầu hết một sinh viên sẽ chỉ có một k thi trong một ngày và không có nhiều uá các k thi liên tiếp nhau với một

sinh viên.

 Số tiết của k thi có thể khác nhau, ngược lại với bài toán lập thời khóa biểu

cho trường đại học cái đó là cố định.

 ó thể có nhiều hơn một k thi trong một ph ng nhưng lại không thể có nhiều

bài giảng được diễn ra trong một phòng tại một thời điểm.

1.1.3. B n h h u h ư ng h Un ng)

ài toán lập thời khóa biểu cho trường đại học là bài toán lập lịch cho các bài

giảng (lectures) vào t ng khóa học với một số lượng ph ng học và tiết học cho trước.

Điểm khác biệt chính với bài toán lập thời khóa biểu trường ph thông là đặc trưng

của các khóa học trường đại học, các sinh viên tham ự khóa học, trong khi các lớp

học trường ph thông được tạo b i tập hợp các học sinh và có thể coi như là một

thực thể đơn. Ở các trường đại học, hai khóa học khác nhau có thể có tr ng sinh viên

tham ự và điều đó có thể tạo ra xung đột và sẽ không thể lập lịch được trong c ng

một tiết học.

Thêm vào đó, các giáo viên trường ph thông luôn ạy nhiều hơn một lớp trong khi trường đại học một giáo sư thường chỉ ạy một khóa học hay một môn học trong một k .

4

uối c ng, với bài toán trường đại học kích cỡ các ph ng học chiếm một vai tr uan trọng trong khi với bài toán trường ph thông vấn đề này là không uan trọng b i vì trong hầu hết các trường ph thông mỗi lớp có một ph ng học riêng.

Trong luận văn này chỉ xét bài toán lập thời khóa biểu cho trường đại học theo hệ

tín chỉ ( niversity ourse Timetabling Problem - UCTP). Để tiện cho việc so sánh giữa các thuật toán, bài toán lập thời khóa biểu cho trường đại học được thu gọn về

thành bài toán mẫu chu n (được phát biểu tại: www.metaheuristics.org) để thực

nghiệm với các thuật toán mô phỏng tự nhiên.

ài toán được phát biểu như sau

Có N môn học được các sinh viên đăng ký tham gia cần được xếp lịch vào một tuần gồm K tiết học tương ứng. ác môn học được t chức tại các ph ng học đáp ứng

đủ các điều kiện học tập của môn học đó (mỗi ph ng học chỉ chứa được một lượng

người nhất định và đáp ứng được một số các điều kiện học tập cho trước, trong khi

mỗi một môn học lại yêu cầu phải có một số điều kiện học tập cho riêng nó).

Một lời giải hay một thời khóa biểu chấp nhận được là tất cả các môn học đều

được chia vào các tiết học và các ph ng tương ứng và thỏa mãn các điều kiện ngặt sau:

- hông sinh viên nào tham ự hơn một môn học trong c ng một thời gian. - Ph ng học đủ lớn cho các sinh viên đăng ký môn học và đáp ứng đủ các điều

kiện của môn học đó.

- hỉ có một môn học được t chức tại một ph ng trong bất k một khoảng

thời gian cho trước nào.

Thêm vào đó, một thời khóa biểu chấp nhận được sẽ được đánh giá bằng số vi

phạm các ràng buộc mềm được cho như sau:

- Hạn chế số sinh viên phải tham ự một môn học vào tiết cuối c ng trong

ngày (tồn tại mỗi một sinh viên như vậy thì tính là một vi phạm).

- Hạn chế các sinh viên phải tham ự uá nhiều môn học liên tiếp nhau trong cùng một ngày (trong thực nghiệm, nếu có ba môn học t chức liên tiếp với

một sinh viên trong một ngày sẽ được tính là một vi phạm).

- Hạn chế các sinh viên chỉ học đúng có một môn học trong ngày (một sinh

viên như vậy tương ứng với một vi phạm).

1.2. Các cách tiếp c n hiện nay

5

Bài toán thời khóa biểu nói riêng và các bài toán tối ưu t hợp nói chung là rất khó giải. Sự khó khăn của chúng được thể hiện độ phức tạp tính toán và với những bài toán thuộc lớp NP-khó như vậy thời gian để giải thường tăng theo hàm mũ của kích thước bài toán.

Như chúng ta đã biết, trong thuật toán “v t cạn” (tìm kiếm theo bề rộng hoặc

theo độ sâu), về mặt nguyên tắc các phương pháp tìm được nghiệm của bài toán nếu

bài toán có nghiệm, song trên thực tế, những bài toán NP-khó không thể áp d ng được phương pháp này, vì ta phải phát triển một không gian trạng thái rất lớn, trước khi đi

tới trạng thái đích, mà o những hạn chế về thời gian tính toán và ung lượng bộ nhớ,

không cho ph p chúng ta làm được điều đó.

Chẳng hạn, với bài toán thời khóa biểu cho 40 lớp học, mỗi lóp có 8 môn học,

mỗi lớp có 25 tiết mỗi tuần thì không gian tìm kiếm rất lớn là 825*40 trường hợp. Rõ ràng, nếu ng phương pháp v t cạn thì thời gian chạy rất lâu, khó chấp nhận được.

Vì vậy đã có rất nhiều thuật toán được đề xuất để giải gần đúng các bài toán NP

khó. ác thuật toán này tìm được lời giải gần tối ưu và là một trong những xu thế phát

triển hiện nay đối với các bài toán chưa thể tìm được lời giải tối ưu thực sự trong đó các thuật toán mô phỏng theo tự nhiên như thuật toán luyện kim, thuật toán di truyền,

thuật toán hệ kiến... Trong đó thuật toán i truyền và thuật toán hệ kiến tỏ ra là phương

pháp hữu hiệu nhất.

Thuật toán i truyền[12] kết hợp ý tư ng leo đồi và thuật toán luyện kim. Trong

thuật toán “leo đồi” sử d ng kỹ thuật “nâng cấp lặp”, kỹ thuật này áp d ng cho một

điểm đơn (điểm hiện tại) trong không gian tìm kiếm. Trong một lần nâng cấp, một

điểm mới được chọn trong số các điểm lân cận của điểm hiện hành nếu điểm đó cho kết quả tốt hơn của hàm m c tiêu. Việc tìm kiếm sẽ kết thúc khi không thể nâng cấp

thêm được nữa. Rõ ràng thuật toán leo đồi chỉ cho ta kết quả tối ưu c c bộ, kết quả này

ph thuộc vào sự lựa chọn của điểm xuất phát, mặt khác ta không có được thông tín sai

số về kết quả tìm được so với kết quả tối ưu toàn c c

Để khắc ph c nhược điểm trên, thuật toán leo đồi đã được cải tiến bằng cách tăng

số lượng các điểm xuất phát (điểm xuất phát cho mỗi lần chạy có thể được lựa chọn

ngẫu nhiên hoặc được chọn tùy theo kết quả của các lần chạy trước). Sự thành công

hay thất bại của mỗi lần chạy (cho ta kết quả tối ưu toàn c c hay c c bộ), ph thuộc vào sự lựa chọn điểm xuất phát và hình dáng của “mặt cong” của hàm giá. Nếu mặt

cong chỉ có một số ít cực trị địa phương thì tối ưu toàn c c được tìm ra rất nhanh. Nhưng ngược lại, nếu số cực đại địa phương nhiều thì khả năng tìm tối ưu toàn c c là rất nhỏ. Chính vì vậy mà kể cả sau khi đã được cải tiến thì thuật toán vẫn chưa tốt.

6

Trong thuật toán luyện kim[12], người ta dùng kỹ thuật thay đ i entropy của hệ. Ở phương pháp này người ta đã điều khiển tốc độ hội t của quần thể bằng cách biến đ i nhiệt động học với một tham số nhiệt độ T toàn c c. Để hạn chế việc tối ưu c c bộ và tăng khả năng khám phá không gian tìm kiếm, người ta đã ng thủ thuật giảm

nhiệt độ T t ng bước (đến một mức nào đó). Tuy nhiên vì T chỉ giảm đến một mức

nhất định, vì vậy phương pháp này cũng không tránh khỏi hạn chế trong việc khám

phá không gian tìm kiếm mới và s hội t địa phương.

Bằng cách duy trì một quần thể (tập hợp các lời giải có thể) thuật toán i truyền

khuyến khích sự hình thành và trao đ i thông tin giữa các cá thể (thể hiện qua phép tráo

đ i chéo). Một quá trình tiến hóa được thực hiện trên một quần thể tương đương với sự

tìm kiếm trong một không gian các lời giải có thể. Sự tìm kiếm này đ i hỏi sự cân bằng

giữa hai m c đích tìm lời giải tốt nhất và khám phá không gian tìm kiếm mới.

Gần đây, phương pháp tối ưu đàn kiến [15](A O - Ant olony Optimi ation) o

Dorigo đề xuất là một trong số các cách tiếp cận mới nhất. Một thành phần ngẫu nhiên

trong ACO cho phép các con kiến xây dựng được một lượng lớn các lời giải khác nhau

và t đó tìm kiếm được một lượng lời giải lớn hơn hẳn so với phương pháp khác. Và tại cùng một thời gian, việc sử d ng các thông tin kinh nghiệm sẽ hướng dẫn các con

kiến tìm kiếm được các lời giải hứa hẹn. Quan trọng hơn, kinh nghiệm tìm kiếm của

con kiến được sử d ng để học tăng cường trong quá trình lặp xây dựng thuật toán.

Thêm vào đó, việc sử d ng đàn kiến sẽ làm cho các thuật toán ứng d ng ACO phức

tạp có thêm một tập hợp các tác nhân lặp hiệu quả để giải quyết bài toán. Hiệu quả của

nó đã được chứng minh bằng thực nghiệm và cho thấy n i trội hơn so với các thuật

toán mô phỏng tự nhiên khác như luyện kim, di truyền, tính toán tiến hóa. Miền ứng d ng của các bài toán ACO rất rộng. Về nguyên lý, ACO có thể được áp d ng cho bất

k bài toán tối ưu rời rạc nào. Trong chương 3 chúng ta sẽ tìm hiểu chi tiết thuật toán

7

tối ưu hóa đàn kiến cho bài toán UCTP.

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

Ở chương 1 luận văn đã được tìm hiểu về bài toán UCTP và một số cách tiếp cận

để giải bài toán, chương này luận văn sẽ tìm hiểu phương pháp tối ưu đàn kiến để giải

bài toán trên.

2.1. Từ kiến tự nh ên ến kiến nhân t o

Những hình ảnh nhận thức đặc biệt của đàn kiến chỉ đơn giản là sự phát triển và

hoàn toàn mò mẫm. Trong thực tế, một điều quan trọng trong nghiên cứu về loài kiến

là hành vi liên lạc giữa các con kiến hoặc giữa các cá nhân với môi trường, được dựa trên việc sử d ng các sản ph m hóa chất của các loài kiến. Các hóa chất đó được gọi là

mùi (vết mùi).

2.1.1. Kiến tự nhiên

hi tìm đường đi, đàn kiến trao đ i thông tin gián tiếp và hoạt động theo phương

thức tự t chức. Phương thức này tuy đơn giản nhưng đã giúp cho đàn kiến có thể thực

hiện được những công việc phức tạp vượt xa khả năng của t ng con kiến, đặc biệt là

khả năng tìm đường đi ngắn nhất t t đến nguồn thức ăn (xem hình 2.1) (mặc dù, kiến không có khả năng đo độ ài đường đi). iến chịu ảnh hư ng của các vết mùi của các

con kiến khác chính là ý tư ng thiết kế thuật toán ACO.

Hình 2.1. Thể hiện hành vi của mỗi con kiến trong tự nhiên

8

Để làm được điều đó, trên đường đi, mỗi con kiến để lại vết m i ng để đánh dấu đường đi. ằng cách cảm nhận vết mùi, con kiến có thể lần theo đường đi đến

nguồn thức ăn được các con kiến khác khám phá theo phương thức chọn ngẫu nhiên,

có định hướng theo nồng độ vết mùi.

Con kiến chịu ảnh hư ng của các vết mùi của các con kiến khác, đây là ý tư ng

chính để thiết kế thuật toán ACO.

Thí nghiệm trên cây cầu :

Có nhiều thực nghiệm nghiên cứu về hành vi để lại vết m i và đi theo vết mùi

của loài kiến. Thực nghiệm, được thiết kế b i Deneubourg và các đồng nghiệp [15] dùng một chiếc cầu đôi nối t t kiến tới nguồn thức ăn, như minh họa trong hình 2.2.

giữa hai nhánh khác nhau của chiếc Họ đã thực nghiệm với tỉ lệ độ ài đường

cầu đôi, trong đó 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 ( hình 2.2.a). an đầu, kiến lựa chọn đường đi một cách tự o đi 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 an đầu không có vết mùi

nào trên cả hai nhánh, o đó 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ánhcò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ấylà 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.

Hình 2.2: Thực nghiệm cây cầu đôi

9

(a) ai nhánh có độ dài bằng nhau. (b) Hai nhánh có độ dài khác nhau.

Trong thực nghiệm thứ hai (xem hình 2.2 b), độ dài của nhánh dài gấp đôi độ dài

nhánh ngắn (tỉ lệ ). Trong trường hợp này, sau một thời gian tất cả các con kiến

đều chọn đoạn đường ngắn hơn. ũng như trong thực nghiệm thứ nhất, ban đầu đàn kiến lựa chọn hai nhánh đi như nhau, một nửa số kiến đi theo nhánh ngắn và một nửa

đi theo nhánh ài (mặc dù trên thực tế, do tính ngẫu nhiên có thể một nhánh nào đó được nhiều kiến lựa chọn hơn nhánh kia). Nhưng thực nghiệm này có điểm khác biệt

quan trọng với thực nghiệm thứ nhất: Những kiến lựa chọn đi theo nhánh ngắn sẽ

nhanh chóng quay tr lại t và khi phải lựa chọn giữa nhánh ngắn và nhánh dài, kiến

sẽ thấy nồng độ mùi trên nhánh ngắn cao hơn nồng độ m i trên nhánh ài, o đó sẽ ưu tiên lựa chọn đi theo nhánh ngắn hơn. Tuy nhiên, trong thời gian đầu không phải tất cả

các kiến đều đi theo nhánh ngắn hơn.Phải mất một khoảng thời gian tiếp theo nữa bầy

kiến mới lựa chọn đi theo nhánh ngắn. Điều này minh chứng bầy kiến đã sử d ng

phương thức thăm , tìm đường mới.

Một điểm thú vị nữa là quan sát xem sẽ xảy ra điều gì khi quá trình tìm kiếm

đang hội t , lại xuất hiện một đường mới t t đến nguồn thức ăn. Việc này được thực

nghiệm như sau an đầu t t đến nguồn thức ăn chỉ có một nhánh dài và sau 30 phút,

thêm một nhánh ngắn (xem hình 2.3). Trong trường hợp này, nhánh ngắn thường

không được kiến chọn mà chúng tập trung đi trên nhánh ài. Điều này có thể giải thích

như sau nồng độ vết mùi trên cạnh dài cao và sự bay hơi của vết mùi diễn ra chậm nên

đại đa số các con kiến vẫn lựa chọn nhánh dài (có nồng độ vết mùi cao).Hành vi này

tiếp t c được củng cố kiến chọn đi theo nhánh ài, ngay cả khi có một nhánh ngắn

xuất hiện. Việc bay hơi vết m i là cơ chế tiện lợi cho việc tìm đường mới, nghĩa là

việc bay hơi có thể giúp kiến uên đi đường đi tối ưu địa phương đã được tìm thấy

trước đây để tìm khám phá đường đi mới, tốt hơn.

Hình 2.3. Thí nghiệm b xung

10

( an đầu chỉ có một nhánh và sau 30 phút thêm nhánh ngắn hơn)

2.1.2. Kiến nhân t o (Artificial Ant)

Thực nghiệm cây cầu đôi cho thấy đàn kiến tự nhiên có thể sử d ng luật di

chuyển theo xác suất, dựa trên thông tin địa phương để tìm được đường đi ngắn nhất giữa hai địa điểm. Vết mùi của đàn kiến cho ph p liên tư ng tới cách học tăng cường

(reinforcement learning) trong bài toán chọn tác động tối ưu[2], gợi m mô hình mô

phỏng cho bài toán tìm đường đi ngắn nhất giữa hai nút (tương ứng là t và nguồn

thức ăn) trên đồ thị, trong đó các tác tử (agent) là đàn kiến nhân tạo.

Tuy nhiên, trong các bài toán ứng d ng các đồ thị thường phức tạp hơn.T mỗi đỉnh có thể có nhiều cạnh, nên nếu mô phỏng thực sự hành vi của đàn kiến tự nhiên

nhiều con kiến sẽ đi lu n qu n và o đó hiệu quả thuật toán sẽ rất kém. Vì vậy, người

ta dùng kỹ thuật đa tác tử (multiagent) mô phỏng đàn kiến nhân tạo, trong đó mỗi con

kiến nhân tạo có khả năng nhiều hơn so với kiến tự nhiên. Kiến nhân tạo (về sau trong luận án ta sẽ gọi đơn giản là kiến) có bộ nhớ riêng, có khả năng ghi nhớ các đỉnh đã

thăm trong hành trình và tính được độ ài đường đi nó chọn. Ngoài ra, kiến có thể trao

đ i thông tin với nhau, thực hiện tính toán cần thiết, cập nhật m i…

Sử d ng mô hình kiến nhân tạo này, Dorigo (1991) [15] đã xây ựng thuật toán

Hệ kiến (AS) giải bài toán người chào hàng. Hiệu quả của thuật toán so với các

phương pháp mô phỏng tự nhiên khác như SA và GA đã được kiểm chứng bằng thực

nghiệm. Thuật toán này về sau được phát triển và có nhiều ứng d ng phong phú, được gọi chung làphương pháp A O.

2.2. Phương h ố ưu n ến

Tối ưu đàn kiến (Ant Colony Optimization - ACO) là một phương pháp

metaheuristic được đề xuất b i Dorigo vào năm 1991[14] dựa trên ý tư ng mô phỏng

cách tìm đường đi t t tới nguồn thức ăn và ngược lại của các con kiến tự nhiên để

giải gần đúng bài toán TƯT NP-khó.

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 (pheromone trail), đặc điểm sinh hóa học của vết mùi này là có khả năng ứ đọng,

bay hơi và là phương tiện giao tiếp báo cho các con kiến khác thông tin về đường đi đó một cách gián tiếp. Các con kiến sẽ lựa chọn đường đi nào tồn đọng lượng m i hay có cường độ vết m i lớn nhất tại thời điểm lựa chọn để đi, nhờ cách giao tiếp mang tính

11

gián tiếp và cộng đồng này mà đàn kiến trong tự nhiên tìm được đường đi ngắn nhất trong uá trình tìm thức ăn mang về t và ngược lại. Sử d ng mô hình kiến nhân tạo này Dorigo (1991) [4] đã xây ựng thuật toán hệ kiến (AS) giải bài toán người chào hàng. Thuật toán này đã được chứng minh tính hiệu quả thông qua thực nghiệm so với

các mô phỏng tự nhiên khác như SA (mô phỏng luyện kim) và GA (giải thuật di

truyền). Thuật toán này về sau được phát triển và có nhiều áp d ng phong phú trong

thực tế, được gọi chung là phương pháp A O.

Theo ý tư ng này, các thuật toán ACO sử d ng thông tin heuristic kết hợp thông

tin học tăng cường qua các vết mùi của các con kiến nhân tạo (artificial ant) để 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 c thể. Thuật toán

A O đầu tiên là hệ kiến (Ant System - AS) giải bài toán Người chào hàng TSP, đến nay các thuật toán A O đã áp ng một cách phong phú để giải nhiều bài toán tối ưu

t hợp khác nhau và hiệu uả n i trội của nó đã được chứng tỏ bằng thực nghiệm.

Nhờ những thành uả to lớn trong việc ứng ng phương pháp tối ưu đàn kiến

vào giải các bài toán tối ưu t hợp khó m ra một lĩnh vực nghiên cứu và ứng ng mới thu hút được sự uan tâm của đông đảo các nhà khoa học trên thế giới, Dorigo đã

được ội đồng châu u trao giải thư ng đặc biệt Marie urie (Marie Curie

Excellence Award) trao hai năm một lần giành cho năm nhà khoa học có nhiều đóng

góp cho nền khoa học và công nghệ châu u vào ngày 05 11 2003. ho đến nay, các

hội nghị về đàn kiến đã t chức 6 lần (ANT 98, ANT 2000, ANTS 2002, ANTS

2004, ANTS 2006, ANTS 2008) và mỗi hội nghị có khoảng 30-40 báo cáo về các

công trình nghiên cứu lý thuyết và thực nghiệm có ý nghĩa khoa học và ứng ng uan trọng góp phần chứng tỏ A O là phương pháp tối ưu mới m và hiệu uả (xem

http://iridia.ulb.ac.be/~ants/).

2.3. Đồ thị cấu trúc

t bài toán TƯT t ng uát ưới dạng bài toán cực tiểu hóa (S,f,Ω), trong đó

S là tập hữu hạn trạng thái, f là hàm m c tiêu xác định trên S, c n Ω là các ràng buộc

để xác định tập S có các thành phần được lấy t tập hữu hạn C. Các tập S, và Ω có các đặc tính sau:

1) Ký hiệu là tập các dãy trong độ dài không quá { }. hi đó, mỗi phương án trong được xác địnhb i ít nhất một vectơ trong .

2) Tồn tại tập con của và ánh xạ t lên sao cho không rỗng với mọi , trong đó tập có thể xây dựng được t tập con của nhờ m rộng tuần tự ưới đây.

3) T ta m rộng tuần tự thành như sau

12

i) Ta xem là m rộng được với mọi

ii) Giả sử là m rộng được và chưa thuộc . T tập ràng buộc , xác định tập con của , sao cho với mọi thì là m rộng được.

iii) Áp d ng thủ t c m rộng t các phần tử cho phép ta xây dựng được mọi

phần tử của .

Như đã nói trong chương 1, mỗi bài toánTƯT được xem như một bài toán tìm

kiếm vectơ độ dài không quá trên đồ thị đầy đủ có các đỉnh được gán nhãn trong tập

. Để tìm các lời giải chấp nhận được, ta xây dựng đồ thị đầy đủ với tập đỉnh , mỗi

đỉnh của nó tương ứng với mỗi thành phần của Các lời giải chấp nhận được sẽ là các vectơ được xác định theo thủ t c m rộng tuần tự hay m rộng ngẫu nhiên

Thông thường, đối với các bài toán thuộc loại NP-khó, người ta đưa ra các

phương pháp heuristic tìm lời giải đủ tốt cho bài toán. Các thuật toán ACO kết hợp thông tin heuristic này với phương pháp học tăng cường, mô phỏng hành vi của đàn

kiến, để tìm lời giải tốt hơn.

Mỗi cạnh nối đỉnh có trọng số heuristic để định hướng chọn thành phần m rộng là khi thành phần cuối của trạng thái hiện tại là (theo thủ t c m rộng tuần tự đã nêu trên). Ký hiệu là vectơ các trọng số heuristic của cạnh (trong bài toán TSP đó là vectơ có các thành phần là nghịch đảo của độ dài cạnh tương ứng), còn là vectơ biểu thị các thông tin học tăng cường (gọi là vết m i, ban đầu được kh i tạo giá trị >0). Trường hợp đặc biệt và chỉ ph thuộc vào , các thông tin này sẽ gắn với các đỉnh. Không làm mất tính t ng uát, ta x t trường hợp các thông tin

này gắn vào các cạnh.

Ta gọi đồ thị là đồ thị cấu trúc của bài toán tối ưu t hợp, trong

đó là tập đỉnh, là tập cạnh, và là các thông tin gắn với cạnh. T các cạnh, xây dựng tập nhờ m rộng tập theo thủ t c tuần tự. Nếu không có thông tin heuristic thì ta xem có các thành phần như nhau và bằng 1.

13

Trường hợp t ng quát, là đồ thị đầy đủ.Tuy nhiên, tùy theo ràng buộc của bài toán, các cạnh có thể lược bớt để giảm miền tìm kiếm lời giải theo thủ t c m rộng tuần tự. Chẳng hạn, với bài toán tìm cực trị của hàm giải tích ,với thuộc tập giá trị hữu hạn , đồ thị cấu trúc có tầng, tầng chứa các đỉnh thuộc tập , còn tập cạnh chỉ gồm các cạnh nối các đỉnh thuộc tầng với các đỉnh thuộc tầng như trong hình 2.1. hi đó tập là tập , mỗi m rộng tuần tự của lời giải sẽ được xây dựng t một đỉnh thuộc tập này.

Hình 2.4. Đồ thị cấu trúc t ng quát cho bài toán cực trị hàm

2.4. Mô tả thu t toán ACO t ng quát

Sử d ng điều kiện kết thúc (có thể theo số bước lặp hoặc/và giới hạn thời gian

chạy), ta ng đàn kiến có con, tiến hành lặp quá trình xây dựng lời giải trên đồ thị cấu trúc như sau Tại mỗi lần lặp, kiến chọn ngẫu nhiên một đỉnh làm thành phần kh i tạo { } và thực hiện xây dựng lời giải theo thủ t c bước ngẫu nhiên. Dựa trên lời giải tìm được, đàn kiến sẽ thực hiện cập nhật mùi theo cách

học tăng cường.

Thủ tục bước ngẫu nhiên:

tập con sao cho với mọi của ,

[ ]

Giả sử là m rộng được và chưa thuộc . T tập ràng buộc , xác định thì là m rộng được. Đỉnh để m rộng, được chọn với xác suất như sau

∑

[ ] [ ] [ ]

(2.3) {

̅

Quá trình m rộng tiếp t c cho tới khi kiến tìm được lời giải chấp nhận được

14

trong và o đó .

Hình 2.5. Lựa chọn đỉnh đi tiếp theo

Để tiện trình bày, về sau ta sẽ xem và như nhau và không phân biệt với .

Cập nhật mùi:

Tùy theo chất lượng của lời giải tìm được, vết mùi trên mỗi cạnh sẽ được điều chỉnh tăng hoặc giảm t y theo đánh giá mức độ ưu tiên tìm kiếm về sau. ượng mùi cập nhật theo các quy tắc cập nhật mùi khác nhau sẽ cho các thuật toán khác nhau. Vì

vậy,quy tắc cập nhật m i thường dùng làm tên gọi thuật toán, và chúng có dạng t ng

quát là:

(2.2)

trong đó là hằng số thuộc khoảng (0,1) là tỷ lệ lượng mùi bị bay hơi.

Procedure Thuật toán ACO;

Begin Kh i tạo tham số, ma trận mùi, kh i tạo con kiến;

repeat

for to do

Kiến xây dựng lời giải;

end-for Cập nhật mùi;

Cập nhật lời giải tốt nhất;

Until (Điều kiện kết thúc);

Đưa ra lời giải tốt nhất; End;

Hình 2.6. Đặc tả thuật toán ACO

Nhận xét chung về các thuật toán ACO:

Nhờ kết hợp thông tin heuristic, thông tin học tăng cường và mô phỏng hoạt

15

động của đàn kiến, các thuật toán A O có các ưu điểm sau:

1) Việc tìm kiếm ngẫu nhiên dựa trên các thông tin heuristic tr nên linh hoạt

và mềm d o trên miền rộng hơn so với các phương pháp heuristic đã có. Do đó, cho ta

lời giải tốt hơn và có thể tìm được lời giải tối ưu.

2) Học tăng cường thông qua thông tin về cường độ vết mùi cho phép t ng

bước thu hẹp không gian tìm kiếm, mà vẫn không loại bỏ các lời giải tốt, o đó nâng

cao chất lượng thuật toán.

Chú ý. Khi áp d ng phương pháp A O cho các bài toán c thể, ba yếu tố sau có ảnh

hư ng quyết định đến hiệu quả thuật toán:

1) Xây dựng đồ thị cấu trúc thích hợp. Trong m c 2.2.1 đã chỉ ra rằng việc xây

dựng đồ thị cấu trúc để tìm được lời giải cho bài toán theo thủ t c tuần tự không

khó. hó khăn chính là với các bài toán cỡ lớn, không gian tìm kiếm quá rộng, đ i hỏi

ta sử d ng các ràng buộc một cách hợp lý để giảm miền tìm kiếm của kiến.

2) Chọn thông tin heuristic. Thông tin heuristic tốt sẽ tăng hiệu quả thuật toán.

Tuy nhiên, trong nhiều bài toán không có thông tin này thì có thể đánh giá chúng như

nhau. hi đó, ban đầu thuật toán chỉ đơn thuần chạy theo phương thức tìm kiếm ngẫu

nhiên, vết mùi thể hiện định hướng của học tăng cường và thuật toán vẫn thực hiện

được.

3) Chọn quy tắc cập nhật mùi. Quy tắc cập nhật mùi thể hiện chiến lược học

của thuật toán. Trong khi đồ thị cấu trúc và thông tin heuristic ph thuộc vào bài toán

c thể, quy tắc cập nhật mùi lại là yếu tố ph d ng và thường ng để đặt tên cho thuật

toán. Có nhiều quy tắc cập nhật m i đã được đề xuất, luận văn này sẽ tìm quy tắc thích hợp cho hai loại bài toán, tùy theo thông tin heuristic ảnh hư ng nhiều hay ít tới thủ

t c tìm kiếm lời giải.

2.5. Các hệ kiến

2.5.1. Hệ kiến AS

an đầu có ba phiên bản của AS được Dorigo đề xuất (xem [3-6]) là ant-density, ant-quantity và ant-cycle. Ở phiên bản ant-density và ant-quantity, kiến cập nhật vết

16

mùi trực tiếp lên cạnh v a đi, c n trong phiên bản ant-cycle vết m i được cập nhật khi tất cả kiến đã xây ựng xong hành trình và lượng m i được cập nhật ph thuộc vào độ dài hành trình mà kiến tìm được. Hai thuật toán ant-density và ant-quantity không hiệu quả so với thuật toán ant-cycle, nên khi nói tới thuật toán AS ta chỉ uan tâm đến phiên bản ant-cycle.

Hai bước chính trong thuật toán AS là xây dựng lời giải của kiến và cập nhật

mùi. Trong AS, lời giải tìm được dựa trên phương pháp heuristic (chẳng hạn phương

cạnh là:

pháp tham ăn) khi xác định vết mùi kh i tạo. Giá trị vết mùi kh i tạo cho tất cả các trong đó là số kiến, là độ dài lời giải tìm được của thuật toán heuristic. Lý do lựa chọn này là nếu kh i tạo vết mùi quá thấp,quá trình tìm kiếm có khuynh hướng hội t về hành trình đầu tiên tìm được, dẫn đến việc tìm kiếm

sa lầy vào vùng này,làm cho chất lượng lời giải không tốt. Nếu kh i tạo vết mùi quá cao, có thể phải mất nhiều vòng lặp bay hơi m i trên các cạnh không tốt và cập nhật

b sung thêm mùi cho các cạnh tốt mới để thể hướng việc tìm kiếm đến vào vùng

không gian có chất lượng tốt.

Xây dựng lời giải

Trong thuật toán AS, kiến đồng thời xây dựng lời giải. an đầu, các con kiến được đặt ngẫu nhiên tại các thành phố. Ở mỗi bước, kiến sử d ng xác suất theo

phương thức tỉ lệ ngẫu nhiên (ran om proportional) để chọn đỉnh tiếp theo. C thể, khi

[ ]

∑

[ ] [ ] [ ]

kiến đang đỉnh sẽ lựa chọn đỉnh với xác suất:

{

̅

(2.3)

là các đỉnh lân cận của đỉnh tương uan giữa thông tin mùi và thông tin heuristic, kiến có thể đi đến (là tập các đỉnh kiến chưa đến, xác suất các đỉnh không thuộc bằng 0). Theo quy tắc ngẫu nhiên này, xác suất lựa chọn cạnh tăng theo giá trị thông tin mùi và thông tin heuristic . Vai trò của hai tham số như sau nếu , thành phố gần nhất sẽ được lựa chọn, khi đó thuật toán tương đương với thuật toán chọn ngẫu nhiên theo nghịch đảo độ dài cạnh, không có học tăng cường.

là giá trị heuristic, là hai tham số quyết định đến sự ảnh hư ng trong đó

Nếu , chỉ có thông tin học tăng cường biểu thị qua vết m i được sử d ng,không

có thông tin heuristic. Nếu lớn, thuật toán nhanh chóng bị tắc nghẽn (tất cả kiến sẽ lựa chọn cùng một hành trình) và lời giải tìm được hội t về lời giải tối ưu địa phương.

17

Để cài đặt, kiến sẽ duy trì một bộ nhớ chứa thông tin lần lượt các thành phố đã đi ua. Thông tin trong bộ nhớ ng để xác định các thành phố lân cận phù hợp trong (2.3). ơn nữa, thông tin trong bộ nhớ giúp kiến tính được độ dài hành trình và ng để xác định các cạnh được cập nhật mùi.

Liên quan đến việc xây dựng lời giải, có hai cách để thực hiện: xây dựng lời giải

song song và xây dựng tuần tự. Theo cách xây dựng song song, tại mỗi bước tất cả

kiến sẽ di chuyển sang đỉnh tiếp theo, trong khi đó với cách xây dựng tuần tự lần lượt t ng kiến xây dựng lời giải (kiến này xây dựng xong rồi mới đến kiến tiếp theo).

Trong AS, cả hai cách xây dựng này là như nhau, vì không có ảnh hư ng gì.Điều này

không đúng với thuật toán ACS.

Cập nhật mùi

Sau khi tất cả các kiến xây dựng xong hành trình, vết mùi sẽ được cập nhật như sau Trước tiên, tất cả các cạnh sẽ bị bay hơi theo một tỉ lệ không đ i, sau đó các cạnh

có kiến đi ua sẽ được thêm một lượng mùi. Việc bay hơi m i trên tất cả các cạnh

được thực hiện như sau

(2.4)

trong đó là hệ số bay hơi.Tham số được sử d ng để tránh sự tích t vết mùi quá nhiều trên một cạnh và giúp cho kiến “ uên” đi các uyết định sai lầm. Trên

thực tế, nếu một cạnh không được kiến lựa chọn vết mùi nhanh chóng bị giảm theo cấp

số nhân. Sau khi bay hơi, tất cả kiến sẽ để lại vết mùi trên cạnh đi ua

là lượng mùi do kiến cập nhật trên cạnh kiến đi ua. Giá trị này

(2.5) ∑

trong đó bằng:

{

(2.6)

trong đó là độ dài hành trình do kiến xây dựng.Giá trị này được tính bằng t ng độ dài các cạnh thuộc hành trình. Theo công thức (2.6), các cạnh thuộc hành trình

tốt hơn sẽ được cập nhật nhiều hơn. Như vậy, cạnh nào càng có nhiều kiến sử d ng và

thuộc hành trình ngắn, sẽ càng được cập nhật mùi nhiều hơn.Do đó sẽ được kiến lựa chọn nhiều hơn trong các bước lặp sau.

Hiệu quả của thuật toán AS so với các phương pháp metaheuristic khác giảm khi

kích thước bài toán tăng, vì vậy có nhiều nghiên cứu tập trung cải tiến thuật toán AS.

2.5.2. Hệ kiến ACS

Thuật toán A S o Dorigo và Gambar ella đề xuất năm 1997[5], khác với AS

18

ba điểm chính sau đây

- Thứ nhất, khai thác kinh nghiệm tìm kiếm mạnh hơn trong AS,thông ua việc

sử d ng quy tắc lựa chọn dựa trên thông tin tích lũy nhiều hơn.

- Thứ hai, cơ chế bay hơi m i và để lại mùi chỉ trên các cạnh thuộc vào lời giải

tốt nhất đến lúc đó (Global-best: G-best).

- Thứ ba, tăng cường việc thăm o đường mới. Mỗi lần kiến đi ua cạnh vết mùi sẽ bị giảm trên cạnh . Sau đây chúng ta sẽ tìm hiểu chi tiết những điểm khác đã nêu.

Xây dựng lời giải

Trong thuật toán ACS, kiến đang đứng đỉnh ,sẽ lựa chọn di chuyển đến

{ [ ] }

đỉnh theo qui tắc:

(2.7) {

trong đó là một biến ngẫu nhiên, phân bố đều trong [0,1], là một tham số cho trước và là một biến ngẫu nhiên, lựa chọn theo phân bố xác suất như trong (2.3) với . Nói cách khác, với xác suất kiến sẽ lựa chọn khả năng tốt nhất có thể, dựa trên kết hợp của thông tin học t vết mùi và thông tin heuristic (trong trường hợp này, ta nói kiến khai thác thông tin đã học).Ta cũng nói với xác suất kiến thực hiện khám phá trên các cạnh. Điều chỉnh tham số sẽ cho phép thay đ i mức độ khai thác và lựa chọn tập trung tìm kiếm quanh lời giải G-best hoặc khám phá các hành trình khác.

Cập nhật mùi toàn cục

Trong ACS chỉ có duy nhất một kiến tìm được lời giải G-best được ph p để lại mùi sau mỗi lần lặp. C thể, với các cạnh thuộc lời giải G-best được cập nhật như sau:

(2.8)

trong đó

, là độ dài lời giải G-best. Điều quan trọng cần chú ý trong ACS là vết m i được cập nhật bao gồm cả bay hơi và để lại mùi và chỉ cho các cạnh thuộc (chứ không phải cho tất cả các cạnh như trong AS). Tham số là tham số bay hơi. hông giống như AS, trong (2.4) và (2.5) trong (2.8) vết m i được để

lại sẽ giảm theo tham số . Kết quả của việc cập nhật này là vết m i được thay đ i theo trung bình trọng số của vết mùi cũ và lượng m i được để lại.

Trong thí nghiệm, người ta cũng sử d ng chọn lời giải tốt nhất trong bước lặp

19

hiện tại (Iteration-best: I-best) để cập nhật mùi.

Cập nhật mùi cục bộ

Ngoài việc cập nhật mùi toàn c c, ACS còn sử d ng cơ chế cập nhật mùi c c bộ.

Việc cập nhật mùi c c bộ được thực hiện ngay khi cạnh có kiến đi ua theo công thức:

(2.9)

trong đó và là hai tham số. Giá trị chính là giá trị kh i tạo mùi cho tất cả các cạnh. Theo thực nghiệm giá trị tốt cho bằng 0.1, giá trị là , trong đó là số thành phố, là độ dài hành trình theo thuật toán heuristic tham ăn. iệu quả của thuật toán cập nhật mùi c c bộ thể hiện chỗ mỗi khi kiến đi ua cạnh thì vết mùi trên cạnh bị giảm, làm cho kiến ít lựa chọn lại cạnh này. Nói cách khác, việc cập nhật mùi c c bộ làm tăng khả năng khám phá các cạnh chưa được sử d ng. Trên thực tế, hiệu quả của cách cập nhật mùi này chính là chỗ không bị tắc nghẽn

(nghĩa là, các kiến không bị dồn vào một đường đi nào) như trong AS.

Đối với AS, kiến xây dựng hành trình song song hay tuần tự là không ảnh hư ng

gì. Nhưng trong A S, công việc này có ảnh hư ng, vì ACS sử d ng cơ chế cập nhật

mùi c c bộ. Trong thực nghiệm, thuật toán ACS yêu cầu mọi kiến đồng thời xây dựng

hành trình, mặc dù không có kết quả thực nghiệm chứng tỏ sự lựa chọn nào tốt hơn.

ACS là thuật toán A O đầu tiên sử d ng danh sách ứng cử viên để hạn chế số

lượng lựa chọn trong quá trình xây dựng lời giải. Danh sách ứng cử viên bao gồm các

lựa chọn được đánh giá tốt nhất theo một số tiêu chí heuristic. Trong TSP, danh sách

ứng cử viên cho mỗi thành phố là các thành phố gần với . Theo cách này, danh sách ứng cử viên có thể được xây dựng trước khi bắt đầu tìm kiếm và cố định trong

suốt quá trình tìm kiếm. Khi kiến đang đỉnh , kiến sẽ lựa chọn trong số các ứng cử viên chưa thăm.Trong trường hợp tất cả các thành phố trong danh sách ứng cử viên

đều đã được thăm, thì chọn một thành phố chưa được thăm ngoài anh sách. Trong bài

toán TSP, kết quả thực nghiệm cho thấy việc sử d ng danh sách ứng cử viên làm tăng

chất lượng lời giải và làm giảm độ phức tạp.

2.5.3. Hệ kiến MAX-MIN

Thuật toán MMAS (Max-Min Ant System) o Stut le và oos đề xuất năm 2000

[7] với bốn điểm thay đ i so với AS.

- Thứ nhất, để tăng cường khai thác lời giải tốt nhất tìm được: các cạnh thuộc vào lời giải I-best hoặc G-best được cập nhật m i. Điều này có thể dẫn đến tắc

nghẽn, tất cả các kiến sẽ c ng đi một hành trình, b i vì lượng mùi trên các cạnh

20

thuộc hành trình tốt được cập nhật quá nhiều, mặc dù hành trình này không phải là hành trình tối ưu.

- Thứ hai, để khắc ph c nhược điểm trong thay đ i thứ nhất, MMAS là đưa ra

miền giới hạn cho vết mùi, vết mùi sẽ thuộc [ ].

- Thứ ba là vết m i ban đầu được kh i tạo bằng và hệ số bay hơi nhỏ nhằm

tăng cường khám phá trong giai đoạn đầu.

- Điểm thay đ i cuối cùng là vết mùi sẽ được kh i tạo lại khi tắc nghẽn hoặc

không tìm được lời giải tốt hơn sau một số bước.

Cập nhật mùi

Sau khi tất cả kiến xây dựng lời giải, vết m i được cập nhật bằng thủ t c bay hơi giống như AS (công thức 2.4), và được thêm một lượng mùi cho tất cả các cạnh thuộc

lời giải tốt như sau

(2.10)

khi dùngI-best để cập

khi dùng G-best hoặc nhật m i. Sau đó vết mùi sẽ bị giới hạn trong đoạn [ ] như sau

trong đó

(2.11) {

[ ]

Nói chung, MMAS dùng cả I-best và G-best thay phiên nhau. Rõ ràng, việc lựa

chọn tần số tương đối cho hai cách cập nhật mùi ảnh hư ng đến hướng tìm kiếm. Nếu

luôn cập nhật bằng G-best thì việc tìm kiếm sẽ sớm định hướng quanh G-best còn khi

cập nhật bằng I-best thì số lượng cạnh được cập nhật mùi nhiều o đó việc tìm kiếm

giảm tính định hướng hơn.

Giới hạn vết mùi

Trong MMAS sử d ng giới hạn trên và giới hạn ưới đối với vết mùi của tất cả các cạnh để tránh tình trạng tắc nghẽn. Đặc biệt, việc giới hạn vết mùi sẽ có ảnh hư ng đến giới hạn xác suất trong đoạn [ ]ph c v lựa chọn đỉnh , | thì khi kiến đang đỉnh với . Chỉ khi | .

Dễ thấy, trong một thời gian dài, cận trên của vết mùi là

trong đó là độ dài và ( là một tham số) mỗi khi tìm được lời giải tốt hơn. ết quả

hành trình tối ưu. Dựa trên kết quả đó, MMAS cập nhật lại cận trên

cận ưới

21

thực nghiệm chỉ ra rằng để tránh tắc nghẽn, cận ưới đóng vai tr uan trọng

hơn cận trên . Tuy nhiên, hữu ích trong việc thiết đặt giá trị vết mùi khi kh i tạo lại.

Khởi trị và khởi tạo lại vết mùi

Khi bắt đầu thuật toán, vết mùi trên tất cả các cạnh được thiết đặt bằng cận trên của vết mùi . Cách kh i tạo như vậy, kết hợp với tham số bay hơi nhỏ sẽ cho phép làm chậm sự khác biệt vết mùi giữa các cạnh. Do đó, giai đoạn đầu của MMAS

mang tính khám phá.

Để tăng cường khả năng khám phá, MMAS kh i tạo lại vết mùi mỗi khi gặp tình trạng tắc nghẽn (Thuật toán kiểm tra tình trạng tắc nghẽn dựa trên sự thống kê vết mùi

trên các cạnh) hoặc sau một số bước lặp nhưng không tìm được lời giải tốt hơn.

MMAS là thuật toán được nghiên cứu nhiều nhất trong số các thuật toán ACO và

nó có rất nhiều m rộng. Một trong các cải tiến là khi kh i tạo lại vết mùi, cập nhật mùi dựa trên lời giải tốt nhất tìm được tính t khi kh i tạo lại vết mùi thay cho G-best.

Một cải tiến khác là sử d ng luật di chuyển theo kiểu ACS.

Thuật toán MMAS tập trung tìm kiếm các cạnh thuộc vào lời giải tốt nhất mà

không phân biệt các cạnh không được ng với các cạnh có được ng nhưng không

b . Nếu chọn

lớn thì thuộc lời giải tốt vì vậy sẽ giảm khả năng khám phá nếu thuật toán sẽ gần với tìm kiếm ngẫu nhiên ựa trên thông tin heuristic và giảm hiệu

uả học tăng cường.

2.5.4. Hệ kiến ba mức

Để khắc ph c nhược điểm của hai uy tắc cập nhật m i trên, các cạnh ít sử ng

sẽ có xu hướng hội t về và các cạnh thường sử ng sẽ hội t về . úc

này không phải so sánh với như MMAS nữa và phạm vi tìm kiếm có thể điều

khiển nhờ tỷ lệ giữa .

Quy tắc cập nhật mùi mới được đề xuất là lai giữa hai quy tắc nói trên, theo quy

tắc này vết mùi tại cạnh (i, j) được cập nhật toàn c c theo công thức (2.10) trong đó:

22

(2.12) ngược lại

2.5.5. Hệ kiến ứ (xem [1]):

Quy tắc cập nhật m i đa mức là cải tiến của uy tắc ba mức. uá trình học tăng

cường sẽ thực hiện khi và xích ra xa nhau c n ngược lại sẽ là uá trình tìm kiếm

ngẫu nhiên, s ĩ có được điều này là o theo 2 ui tắc cập nhật m i (2.13) và (2.14)

thì các cạnh có con kiến đi ua sẽ tiến về c n các cạnh thuộc hành trình của con

kiến tốt nhất sẽ tiến về , và theo cách cập nhật mùi này thì không cần quá trình bay

hơi nữa vì trong mỗi vòng lặp hai cận điều khiển được tăng lên như vậy các cạnh ít

không thay đ i mà các cạnh thuộc hành trình của con kiến hoặc các cạnh thuộc hành trình của con kiến tốt nhất tiến về hai cận đó cho nên coi như là các cạnh ít sử d ng bị

bay hơi. Về mặt ý tư ng thì cải tiến này là rất đẹp nhưng lại vô c ng gây khó khăn cho

người làm thực nghiệm khi phải điều chỉnh tỷ lệ thích hợp của việc tăng hay giảm tỷ lệ

giữa và .

C p nh t i on in : một con kiến đang đỉnh i và đi đến đỉnh j thì cạnh (i,j)

được cập nhật m i như sau:

(2.13)

C p nh t i o in : sau khi tất cả các con kiến tìm ra hành trình của mình thì các cạnh thuộc hành trình của con kiến tốt nhất (i-best hoặc g-best) sẽ được cập nhật

m i theo công thức như sau:

(2.14)

ban đầu các cạnh có cường độ m i được kh i tạo bằng , trong uá trình chạy hai

cận và sẽ được điều chỉnh tăng lên.

2.5.6. Hệ kiến Smooth-Max Min

Theo quy tắc MMAS việc tìm kiếm chỉ tập trung quanh lời giải tốt nhất tìm

được, còn các cạnh không thuộc lời giải này sẽ có cường độ vết mùi nhanh chóng t t

về min. ơn nữa, việc thay b i max không ảnh hư ng tới việc học tăng cường.

Để tăng hiệu quả của thuật toán này quy tắc Max-Min trơn [1] được đề xuất như sau:

23

(2.15)

Trong đó (2.16)

Với cách cập nhật mùi SMMAS thì cạnh không thuộc hành trình của các con

kiến sẽ có cường độ vết mùi giảm chậm về min làm tăng khả năng tìm kiếm. Đồng thời cách cập nhật mùi SMMAS sẽ không mất thời gian điều khiển vết mùi nằm trong [ min, max] như cách cập nhật mùi MMAS.

Ta thấy thuật toán SMMAS có một số ưu điểm sau so với ACS và MMAS.

1) Với A S và MMAS, để xác định 0 hay min, max và người ta cần tìm một lời giải theo phương pháp heuristic và ựa vào giá trị hàm m c tiêu của nó. Vì giá trị hàm

m c tiêu này nhận được ngẫu nhiên, nên khó xác định tốt tham số cho học tăng cường.

Quy tắc cập nhật mới cho ph p ta xác định các tham số này đơn giản và hợp lý hơn, c

thể: trong SMMAS ta không cần xác định chính xác giá trị min, max mà chỉ cần xác định tỉ lệ giữa min, max. Trong thực nghiệm nên xác định qua tỉ lệ giữa min, max. Cần nhấn mạnh rằng, việc chỉ cần lựa chọn tỉ lệ giữa min, max đơn giản và mất ít thời gian thực nghiệm hơn rất nhiều so với việc lựa chọn c thể hai tham số min, max.

2) Việc thêm mùi cho các cạnh thuộc lời giải tốt mỗi bước lặp trong thuật toán

ACS và MMAS, ta phải xây dựng hàm để tính lượng m i được thêm dựa trên chất

lượng lời giải do kiến xây dựng được. Ví d , trong bài toán TSP, ACS và MMAS sử

d ng hàm nghịch đảo độ ài đường đi được kiến xác định. Điều này cũng là một trong

66 những khó khăn khi áp ng ACS (hoặc MMAS) đối với một bài toán mới. Tuy

nhiên, trong SMMAS và 3-LAS không cần phải xây dựng hàm này.

3) Dễ dàng kiểm tra được các thuật toán này có c ng độ phức tạp như MMAS và

A S, nhưng ít ph p toán hơn MMAS vì không phải tính hàm m c tiêu lượng mùi

cập nhật và không phải so sánh để giới hạn vết mùi trong khoảng [ min, max]. Theo cách cập nhật của SMMAS và 3-LAS, vết mùi luôn trong khoảng [ min, max].

2.6. Một số vấn ề liên quan

2.6.1. Đặc tính hội tụ

Gutjahr [12-13] là một trong những người đầu tiên nghiên cứu đặc tính hội t của thuật toán MMAS, nhưng chưa x t đến yếu tố có sử d ng thông tin heuristic. Ký hiệu

là xác suất tìm thấy lời giải của thuật toán MMAS trong vòng phép lặp, là

24

lời giải tốt nhất bước lặp . Nhờ sử d ng mô hình Markov không thuần nhất, Gutjahr đã chứng minh rằng với xác suất bằng 1 ta có:

(2.17) 1)

(2.18) 2) , = với mọi cạnh thuộc lời giải tối ưu

Mô hình này của Gutjahr không áp d ng được cho A S. Trong trường hợp

MMAS không sử d ng thông tin heuristic, Stüt le và Dorigo [3] đã chứng minh rằng:

(2.19) đủ lớn ,

(2.20) o đó .

Các tác giả cũng suy ra rằng kết quả này cũng đúng cho cả thuật toán ACS. Với

giả thiết tìm được lời giải tối ưu sau hữu hạn bước, Stützle và Dorigo suy ra rằng vết mùi của các cạnh thuộc lời giải tối ưu tìm được sẽ hội t đến , còn vết mùi trên các cạnh không thuộc lời giải sẽ hội t về hoặc .

Plelegrini và Elloro chỉ ra rằng sau một thời gian chạy, đa số vết mùi trên cạnh

tr nên bé và chỉ có số ít cạnh có giá trị vết mùi là lớn vượt trội.

2.6.2. ACO kết hợp với tìm kiế ị hương

Môt số tài liệu chỉ ra rằng với các phương pháp metaheuristic, một cách tiếp cận

đầy hứa hẹn cho phép nhận được lời giải có chất lượng cao là kết hợp với thuật toán

tìm kiếm địa phương.

Mô hình ACO có thể bao gồm cả tìm kiếm địa phương. Sau khi kiến xây dựng

xong lời giải, có thể áp d ng tìm kiếm địa phương để nhận được lời giải tối ưu địa

phương.Việc cập nhật m i được thực hiện trên các cạnh thuộc lời giải tối ưu địa

phương này. ết hợp xây dựng lời giải với tìm kiếm địa phương sẽ là một cách tiếp

cận có triển vọng, là do trên thực tế, cách xây dựng lời giải của ACO có sử d ng lân

cận khác với tìm kiếm địa phương. Thực nghiệm cho thấy khả năng kết hợp tìm kiếm

địa phương cải tiến được lời giải là khá cao.

2.6.3. Thông tin heuristic

Ta biết rằng thuật toán ACO mà không sử d ng tìm kiếm địa phương, thông tin heuristic sẽ rất cần thiết để có được lời giải tốt. Trên thực tế, giai đoạn đầu vết mùi

được kh i tạo như nhau. hi đó vết mùi không thể giúp kiến tìm đường đi ẫn tới các lời giải tốt, vì chưa khác nhau nhiều. Vai trò chính của thông tin heuristic là để khắc

25

ph c điều này, giúp kiến có thể xây dựng được các hành trình tốt ngay trong giai đoạn đầu. Trong nhiều trường hợp, nhờ sử d ng tìm kiếm địa phương, kiến vẫn có thể tìm được lời giải tốt ngay trong giai đoạn đầu, không cần sử d ng thông tin heuristic nào cả, mặc dù có làm cho quá trình tìm kiếm chậm hơn.

2.6.4. Số ượng kiến

Như đã nói trên, nếu không sử d ng tìm kiếm địa phương và thông tin heuristic

ít (hoặc không có), trong giai đoạn đầu vết mùi không thể giúp kiến tìm đường đi ẫn tới các lời giải tốt. Nếu sử d ng số lượng kiến ít, trong giai đoạn đầu sẽ không tìm

được lời giải tốt và như vậy, việc cập nhật m i được cập nhật dựa trên các lời giải

không tốt. hi đó, sẽ hướng việc tìm kiếm xung quanh lời giải không tốt và o đó

thuật toán sẽ không hiệu quả. Có thể khắc ph c phần nào nhược điểm này bằng cách

tăng số kiến, để tăng khả năng tìm được lời giải tốt mỗi vòng lặp. Khi có sử d ng tìm kiếm địa phương hoặc thông tin heuristic mạnh, sử d ng nhiều kiến là lãng phí.

2.6.5. Tham số hơ

Ở mỗi vòng lặp, khi xây dựng được lời giải tốt (sử d ng tìm kiếm địa phương

hoặc thông tin heuristic mạnh), tham số bay hơi sẽ được xác lập có giá trị lớn, điều này giúp kiến uên đi những lời giải đã xây ựng, tập trung công việc tìm kiếm xung

quanh lời giải tốt mới được xây dựng. Trong trường hợp ngược lại, mỗi vòng lặp,

khả năng kiến tìm được lời giải tốt không cao thì tham số bay hơi phải được thiết lập

26

với giá trị nhỏ.

Chương 3. PHƯƠNG PHÁP ACO CHO BÀI TOÁN UTCP

3.1. Áp dụng hương h ACO cho bài toán UCTP

Các con kiến tìm đường đi trên đồ thị được xây dựng đồng nghĩa với việc sắp

xếp các môn học vào các tiết học tương ứng, chi tiết sẽ được trình bày trong phần xây dựng đồ thị cấu trúc, sau đó các môn học đã được phân vào các tiết học này được ghép

với các ph ng tương ứng đáp ứng đủ điều kiện bằng một thuật toán ghép cặp cực đại

để có được lời giải hoàn chỉnh. Thuật toán có sử d ng thủ t c tìm kiếm địa phương

nhằm cải tiến lời giải cho con kiến có lời giải có số vi phạm ràng buộc ngặt là ít nhất

3.1.1. â ựng ồ hị ấu h n UCTP

Một trong những công việc uan trọng đầu tiên của việc áp ng phương pháp

tối ưu hóa A O metaheuristic là ánh xạ bài toán vào một đồ thị cấu trúc tương ứng khi

đó một đường đi trên đồ thị thể hiện một lời giải chấp nhận được. Để giải uyết bài toán, Socha và đồng sự đã đề xuất ra (xem [11]) đồ thị với tập đỉnh x T trong đó mỗi

một con kiến đi theo anh sách các môn học và ứng với mỗi một môn học e E (E là

tập các môn học) con kiến lựa chọn một tiết học t T (T là tập các tiêt học) tương ứng.

Mỗi một môn học được chọn ứng chỉ với một tiết học và có thể có nhiều hơn một môn

học được học trong tiết đó (vì có nhiều ph ng học khác nhau).

Hình 3.1. Đồ thị cấu trúc cho bài toán UCTP

Các con kiến bắt đầu tại đỉnh Start, đi theo anh sách các môn học và ứng với

mỗi một môn học ei E con kiến sẽ lựa chọn một tiết học t T, kết thúc tại đỉnh Stop. hi đó con kiến xây dựng xong hành trình của mình.

Tại mỗi bước một con kiến có thể lựa chọn sự phân chia theo xác suất biến đ i để xây ựng một lời giải thành phần Ai: EiT với i 0, 1, ..., trong đó e1, e2, . Sau khi xây ựng được ..., ei , ban đầu các con kiến xuất phát với lời giải rỗng A0 =

27

lời giải Ai-1 thì lời giải Ai = Ai-1 {(ei, t) sẽ được xây ựng một cách ngẫu nhiên.

ph thuộc vào ma trận m i Môn học ei được xếp vào tiết học t T với xác suất

( ) với bất k một thông tin heuristic

được tính theo công thức sau:

(3.1)

trong đó thông tin m i và thông tin heuristic đều có đối số là lời giải thành phần

Ai-1. Sự ảnh hư ng của thông tin m i và thông tin heuristic được đánh giá uá hai . Phần tiếp theo sẽ trình bày về các cách khác nhau định nghĩa thông tham số và

tin m i và thông tin heuristic.

3.1.2. M n

Thông tin m i được thể hiện bằng sự chính xác của việc đặt các môn học vào các

tiết học. Với cách thể hiện này, ma trận m i được cho b i , i 1, ..., và

thông tin m i không ph thuộc vào lời giải thành phần Ai. Và trong trường hợp này, thông tin m i sẽ được gắn liền với các đỉnh của đồ thị chứ không phải là các cạnh của

đồ thị. Nhược điểm của cách thể hiện thông tin m i này là sự chính xác trong việc đặt

các môn học vào các tiết học không đóng vai tr uan trọng nhiều lắm đến việc đánh

giá một thời khóa biểu hay một lời giải tốt mà uan trọng là sự sắp xếp uan hệ giữa

các môn học. Ví với một thời khóa biểu tốt, ta hoàn toàn có thể thay đ i trật tự một số nhóm tiết học mà không làm thay đ i chất lượng của thời khóa biểu. Và hệ uả là

cách thể hiện này làm giảm khả năng học trong uá trình xây ựng lời giải, và nếu có

một môn học được xếp vào một tiết học “không đúng” sẽ làm cho các môn học khác

không chọn được tiết học “đúng” của nó nữa, điều này làm cho thời khóa biểu tồi hơn

rất nhiều.

ràng là có nhiều cách thể hiện thông tin m i, nhưng với rất nhiều ràng buộc

đa ạng phải thỏa mãn trong bài toán, rất khó để thiết kế được một mô hình thông tin m i chứa toàn bộ các thông tin liên uan. iện nay, các hệ kiến thường sử ng cách

thể hiện trên như là cách tốt nhất hiện có.

3.1.3. Thông tin heuristic

húng ta hãy xem x t một công thức tính thông tin heuristic được

28

cho như sau:

(3.2)

trong đó là số vi phạm ràng buộc nảy sinh khi thêm thành phần (e, t) vào lời giải thành phần Ai-1. àm V có thể được tính theo t ng số một vài hoặc tất cả vi phạm ràng buộc ngặt và ràng buộc mềm. Tuy nhiên o tính tự nhiên của bài toán TP, độ phức tạp tính toán khi tính một số loại vi phạm ràng buộc có thể rất cao.

húng ta có thể lựa chọn các lợi điểm của các thông tin heuristic để hướng ẫn uá trình xây ựng lời giải nhưng chỉ trong một số ít v ng lặp của bài toán với một hạn chế thời gian cho trước. Vì vậy phải xem x t và đánh giá các lợi điểm đó và việc sử ng các thông tin heuristic không làm tăng chất lượng của lời giải xây ựng bằng thuật toán MMAS có kết hợp sử ng tìm kiếm địa phương. hi không sử ng các thủ t c tìm kiếm địa phương, các thông tin heuristic vẫn có thể không cải thiện được chất lượng lời giải nhưng không c ng mức độ khi sử ng tìm kiếm địa phương.

3.1.4. Tìm kiếm cục bộ

Trong thủ t c tìm kiếm c c bộ ta định nghĩa hai ph p ịch chuyển: Phép dịch chuyển thứ nhất là chuyển một môn học sang một tiết học khác, phép dịch chuyển thứ hai là tráo đ i hai tiết học của hai môn học tương ứng cho nhau. Như vậy các lân cận của một lời giải là lời giải nhận được bằng cách sử d ng một trong hai phép dịch chuyển trên.

Thủ t c tìm kiếm c c bộ được thực hiện như sau Ta uyệt danh sách các môn học theo một thứ tự ngẫu nhiên, nếu môn học đang x t vi phạm ràng buộc ta thử tất cả các phép dịch chuyển có thể sang các lân cận (mỗi lần dịch chuyển tính là một bước lặp). Trước tiên cố gắng giảm các ràng buộc ngặt, nếu thời khóa biểu chấp nhận tìm được (không vi phạm ràng buộc ngặt), ta sẽ cố gắng giảm các ràng buộc mềm.

Mô tả chi tiết thủ t c tìm kiếm c c bộ với số bước lặp cho trước và các sử d ng hai phép dịch chuyển mô tả trên.

Procedure Local Search;

1. Sinh một thứ tự ngẫu nhiên các môn học

Ev_count  0; đặt con trỏ trước đầu danh sách các môn học

số bước local search  0;

2. Ev_count  Ev_count+1; // di chuyển con trỏ sang môn học tiếp theo

If ( Ev_count = N+1 ) { //không còn vi phạm điều kiện cứng nào

Ev_count  0;

goto 3;

}

a) if (môn học hiện tại không gây ra vi phạm cứng) goto 2;

b) tính lân cận ( N1, N2 )

29

tăng số bước local search;

if ( đủ số bước local search ) END LOCAL SEARCH;

c) Áp d ng thuật toán cặp ghép cựa đại cho lân cận v a tìm được

d) If ( số ràng buộc ngặt của lân cận giảm ) {

chuyển sang lân cận;

Ev_count  0;

goto 2;

}

e) goto 2 (b);

3. Ev_count  Ev_count + 1;

If ( Ev_count = N+1 ) END LOCAL SEARCH;

a) If (môn học hiện tại không gây ra ràng buộc mềm) goto 3;

b) tính lân cận ( N1, N2 )

tăng số bước local search;

if ( đủ số bước local search ) END LOCAL SEARCH;

c) Áp d ng thuật toán cặp ghép cựa đại cho lân cận v a tìm được

d) If ( số ràng buộc mềm của lân cận giảm ) {

chuyển sang lân cận;

Ev_count  0;

goto 3;

}

goto 3 (b);

End;

3.1.5. Thu t toán ghép cặp cự tìm l i giải hoàn chỉnh

Với đồ thị cấu trúc đã cho ta biết các môn học được t chức vào tiết học nào,

việc xác định phòng học ta có thể sử d ng thuật toán cặp ghép cực đại để tìm được

thời khóa biểu hoàn chỉnh. Với mỗi tiết học, áp d ng thuật toán thực hiện trên đồ thị hai phía gồm hai tập: tập các môn học được xếp trong cùng tiết học đó và tập các

phòng, với quan hệ gh p được môn học vào phòng học là phòng học phải đáp ứng đủ các điều kiện của môn học đó.

Sau khi áp d ng thuật toán cặp ghép cực đại, nếu tồn tại những môn học không được ghép với phòng học nào ta sẽ gh p chúng vào ph ng đáp ứng được điều kiện và ít “bận” nhất trong tiết học đó, chấp nhận vi phạm ràng buộc cứng và có lời giải không

30

chấp nhận được (ít “bận” đây được hiểu theo nghĩa ít môn học được t chức tại ph ng đó tại tiết học đang x t)

3.1.6. M ả hu n

Thuật toán áp ng mô hình chu n của các thuật toán đàn kiến kết hợp với các

đặc trưng của bài toán. Người ta sử ng một tập hợp bao gồm m con kiến và tại mỗi v ng lặp, mỗi con kiến xây ựng một lời giải (hay một sự sắp xếp môn học-tiết học)

bằng cách đặt các môn học tương ứng một-một vào các tiết học. ác môn học được

tiền xử lý bằng cách sắp xếp theo thứ tự giảm ần của số ràng buộc cạnh giữa các môn

học. Sự lựa chọn tiết học cho môn học là một hàm ngẫu nhiên ựa vào thông tin m i

được mô tả công thức (3.1). an đầu các tham số của hệ kiến và ma trận

cường độ m i được kh i tạo t y theo thuật toán đàn kiến được áp ng và sẽ được cập

nhật theo các cách (online, ngay sau khi con kiến tìm được một tiết học cho một môn

học và offline, sau khi các con kiến đã xây ựng được lời giải của mình). Sau khi một con kiến xây ựng xong lời giải, các sắp xếp môn học-tiết học sẽ được chuyển thành

một thời khóa biểu bằng cách sử ng thuật toán gh p cặp. Và sau khi cả đàn kiến đều

sinh ra được thời khóa biểu của mình, mỗi thời khóa biểu sẽ được đánh giá bằng một

hàm thích nghi (fitness funtion), sau đó lời giải i-best sẽ được áp ng các thủ t c tìm

kiếm địa phương và nếu tìm được láng giềng tốt nhất nó sẽ được thay thế bằng lời giải

láng giềng đó. uối c ng là thủ t c cập nhật m i toàn c c cho ma trận cường độ m i,

cũng được thực hiện theo các tính chất của t ng hệ kiến.

Thu n 1. ệ kiến cho bài toán lập thời khóa biểu

Input: ộ ữ liệu I

h i tạo các tham số

h i tạo ma trận m i

Tính c(e, e ) với

Tính (e)

Sắp xếp E theo thứ tự

while (điều kiện kết thúc chưa xảy ra) do for a = 1 to m do uá trình xây ựng lời giải của con kiến a

for i = 1 to |E| do ựa chọn tiết học t một cách ngẫu nhiên theo công thức xác

suất cho môn học ei.

{ }

31

p ng các thủ t c cập nhật m i online (có hoặc không)

end for C lời giải hoàn chỉnh sau khi áp ng thuật toán gh p cặp cho An Citeration-bestbest(C, Citeration-best)

end for

p ng các thủ t c tìm kiếm địa phương cho iteration-best (có hoặc không)

Cglobal-bestbest(C, Citeration-best) p ng thủ t c cập nhật m i offline.

end while Output: Một lời giải chấp nhận được global-best cho bộ ữ liệu I.

iải th ch chi tiết t th ng tin trong thu t toán:

- Tiền xử lý thông tin các môn học

(3.3) nếu tồn tại 1 sinh viên theo học cả hai môn e và e ngược lại

(e) e E\ e c(e, e ) 0 (bậc của e) (5)

- Định nghĩa một thứ tự toàn phần cho các môn học như sau:

trong đó là một hàm ánh xạ

Trong thuật toán đàn kiến áp ng cho bài toán, lời giải hay thời khóa biểu nào

vi phạm ít ràng buộc ngặt nhất sẽ được lựa chọn để cải tiến bằng tìm kiếm địa phương

3.2. Các thu n ACO ược áp dụng cho bài toán UCTP

Các quy tắc cập nhật m i được áp d ng cho bài toán UCTP bao gồm các quy

tắc cập nhật mùi sau:

 Quy tắc Max Min Ant System (hệ kiến MMAS)

 Quy tắc Smooth-Max Min Ant System (hệ kiến MMAS trơn)

3.2.1. Thu t toán hệ kiến MMAS cho bài toán UCTP

Trong hệ kiến MMAS không sử d ng cập nhật mùi online mà chỉ cập nhật mùi

offline cho các cạnh thuộc global best

Theo uy tắc này các vết m i đều được bay hơi một lượng theo hệ số bay hơi

32

và những thành phần (e,t) thuộc lời giải hay thời khóa biểu tốt nhất sẽ được cộng thêm một lượng m i mà đây thuật toán MMAS chọn bằng hằng số 1 như sau:

nếu

(3.4) ngược lại

Theo uy tắc cập nhật m i MMAS, các vết m i sẽ bị khống chế thuộc khoảng

như sau:

nếu (3.5)

nếu

Thu n 2. ệ kiến MMAS cho bài toán lập thời khóa biểu ngược lại

Input: ộ ữ liệu I

max  1/ (e,t)  max (e,t) E x T

Tính c(e, e ) với

Tính (e)

Sắp xếp E theo thứ tự

while (điều kiện kết thúc chưa xảy ra) do

for a = 1 to m do

uá trình xây ựng lời giải của con kiến a

for i = 1 to |E| do

ựa chọn tiết học t một cách ngẫu nhiên theo công thức xác

suất cho môn học ei.

{ }

end for C lời giải hoàn chỉnh sau khi áp ng thuật toán gh p cặp cho An Citeration-bestbest(C, Citeration-best)

end for p ng các thủ t c tìm kiếm địa phương cho iteration-best (có hoặc không) Cglobal-bestbest(C, Citeration-best) p ng thủ t c cập nhật m i offline.

33

end while Output: Một lời giải chấp nhận được global-best cho bộ ữ liệu I.

3.2.2. Thu t toán Smooth-Max Min Ant System(2011)

Thuật toán Smooth-Max Min Ant System được Hoàng Xuân huấn và cộng sự

[1] đề xuất d ng giải bài toán TSP, đó là thuật toán SMMAS (Smooth-Max Min Ant System). Thuật toán SMMAS được đánh giá tốt hơn r rệt so với thuật toán MMAS,

áp d ng cho bài toán TSP.

Theo quy tắc MMAS việc tìm kiếm chỉ tập trung quanh lời giải tốt nhất tìm

được, còn các cạnh không thuộc lời giải này sẽ có cường độ vết mùi nhanh chóng t t

về min. Để tăng hiệu quả của thuật toán này bằng cách sử d ng quy tắc Max-Min trơn (SMMAS) như sau

(3.6)

Trong đó

(3.7)

Thu n 4. ệ kiến SMMAS cho bài toán lập thời khóa biểu

Input: ộ ữ liệu I

max  1 (e,t)  max (e,t) E x T

Tính c(e, e ) với

Tính (e)

Sắp xếp E theo thứ tự

while (điều kiện kết thúc chưa xảy ra) do

for a = 1 to m do uá trình xây ựng lời giải của con kiến a

for i = 1 to |E| do

ựa chọn tiết học t một cách ngẫu nhiên theo công thức xác

suất cho môn học ei.

{ }

end for C lời giải hoàn chỉnh sau khi áp ng thuật toán gh p cặp cho An Citeration-bestbest(C, Citeration-best)

34

end for

p ng các thủ t c tìm kiếm địa phương cho iteration-best(có hoặc không) Cglobal-bestbest(C, Citeration-best) p ng thủ t c cập nhật m i offline.

35

end while Output: Một lời giải chấp nhận được global-best cho bộ ữ liệu I.

Chương 4. THỰC NGHIỆM

4.1. Dữ liệu thực nghiệm

Thực nghiệm cho thuật toán hệ kiến MAX-MIN, hệ kiến SMMAS cho các bộ dữ liệu

chu n được lấy trên internet(http://iridia.ulb.ac.be/~msampels/tt.data).

Định d ng dữ liệu input như u:

Một tập tin chứa dữ liệu input có dạng sau (tất cả các số đều là số nguyên, các

ng được ngăn cách b i 1 khoảng trống)

 Dòng thứ nhất: Số sự kiện, số phòng, số chức năng, số sinh viên

 Các dòng tiếp theo ghi kích thước(số lượng học viên có thể chứa) của mỗi

phòng.

 Các dòng tiếp theo ghi giá trị 0 hoặc 1 cho biết mỗi sinh viên có tham gia

sự kiện thứ i hay không. 0 nghĩa là các sinh viên không tham gia sự kiên, 1

nghĩa là các sinh viên tham gia sự kiện.

Ví d , nếu có 3 sinh viên và 4 sự kiện như bên ưới:

0

1

0

0

1

1

0

0

0

0

1

0

36

Sẽ có ma trận tham dự sau

Sự kiện

0 0 1 0

Sinh viên 1 0 1 0

0 0 0 1

Nghĩa là

- Sinh viên thứ nhất tham gia sự kiện thứ 2

- Sinh viên thứ 2 tham gia sự kiện thứ nhất và sự kiện thứ 2

- Sinh viên thứ 3 tham gia sự kiện thứ nhất

 Các dòng tiếp theo nhận gái trị 0 hoặc 1 cho biết số phòng thứ i có đáp ứng

được chức năng k hay không. Nhận giá trị 0 nếu phòng không thỏa mãn các

chức năng, hoặc 1 nếu ph ng đáp ứng các chức năng.

Ví d , nếu có 3 phòng và 4 chức năng như sau

0

1

0

0

1

1

0

0

0

0

1

0

37

Sẽ có ma trận phòng chức năng sau:

Chức năng

0 1 0 0

phòng 1 1 0 0

0 0 1 0

Nghĩa là

- Phòng thứ nhất thỏa mãn chức năng thứ 2

- Phòng thứ hai thỏa mãn chức năng thứ nhất và chức năng thứ hai

- Phòng thứ ba thỏa mãn chức năng thứ ba

 Các dòng tiếp theo lần lượt cho t ng sự kiện cho biết sự kiện j có cần yêu

cầu ph ng đáp ứng chức năng k hay không. Nhận giá trị 0 nếu sự kiện

không đ i hỏi chức năng, hoặc 1 nếu đ i hỏi

Ví d , nếu có 3 sự kiện và 4 chức năng như ưới đây

0

1

0

0

1

1

0

0

0

0

1

0

38

Sẽ có ma trận chức năng sự kiện:

Chức năng

0 1 0 0

Sự kiện 1 1 0 0

0 0 1 0

Nghĩa là

- Sự kiện thứ nhất cần chức năng thứ hai

- Sự kiện thứ hai cần chức năng thứ nhất và chức năng thứ hai

- Sự kiện thứ ba cần chức năng thứ ba

Các bộ dữ liệu được chia ra làm 3 loại kích cỡ nhỏ, v a và lớn tương ứng với các

tham số đầu vào được cho trong bảng ưới.

ảng 4.1. Giá trị các tham số đầu vào cho ba loại bộ dữ liệu

Nhỏ Vừa Lớn

Số môn học 100 400 400

Số tiết học/tuần** 45 45 45

Số phòng học 5 10 10

Số đặc trưng/phòng học 5 5 10

Số đặc trưng đáp ứng/phòng học 3 3 5

Tỷ lệ số đặc trưng được sử dụng (%) 70 80 90

80 Số sinh viên 200 400

20 20 20 Số môn học tối đa/sinh viên

20 50 100 Số sinh viên tối đa/môn học

Số tiết học = 9 tiết/ngày * 5 ngày/tuần = 45tiết/tuần.

Định d ng dữ liệu output như u:

Giải pháp tốt nhất (số vi phạm ràng buộc ít nhất) được tìm thấy b i các thuật toán

39

phải được viết trên một tập tin đầu ra với phần đuôi m rộng .sln trong đó

D ng đầu ghi số vi phạm ràng buộc ít nhất tìm được.

Đối với mỗi sự kiện, theo thứ tự như trong tập tin đầu vào mỗi dòng ghi: Số lượng khe

thời gian, số lượng phòng.

- Số lượng khe thời gian là một số nguyên giữa 0 và 44 đại diện các khe thời gian

được phân b cho sự kiện này.

- Các phòng là phòng số được gán cho sự kiện này. Ph ng được đánh số theo thứ tự

như trong tập tin dữu liệu đầu vào, bắt đầu t số không.

4.2. Thực nghiệm

hương trình thực nghiệm được viết bằng ngôn ngữ lập trình C++, trên cùng

một máy tính cấu hình: Intel(R) Pentium(R) CPU B940 @ 2.2 GHz 2.00GHZ,

RAM 4GB, trên nền Windows. Kết quả đưa ra là số ràng buộc mềm ít nhất bị vi

phạm, và trung bình số ràng buộc vi phạm mềm sau 10 lần chạy cho mỗi test. Nếu lời

giải vi phạm ràng buộc ngặt thì coi như không tìm được lời giải.

Khi thiết lập các tham cho cho chạy thực nghiệm trên hai chương trình là

MMAS và SMMAS chúng tôi đã sử d ng các tham số chu n được Socha [12] sử d ng

trong kết quả chạy thực nghiệm demo MMAS của mình để so sánh. Điểm khác biệt

đây là chúng tôi sử d ng số vòng lặp cho mỗi lần chạy làm điều kiện d ng thay vì giới

hạn thời gian chạy như trong bài báo của tác giả. Với SMMAS thì việc chọn tham số

, chỉ cần chọn tỉ lệ cho hai tham số sao cho phù hợp cho kết quả tốt là được.

= 1000* cho kết quả tốt nhất.

Trong demo thực nghiệm chúng tôi thấy chọn Các tham số khác thiết lập như trong MMAS

ảng 4.2. Các tham số tĩnh sử d ng cho bài toán UCTP các thuật toán đàn kiến

Các tham số MMAS SMMAS

0.30 0.30

1/ =1000*

0.0078 0.001

1.0 1.0

0.0 0.0

40

m 10 10

4.3. Kết quả

ảng 4.4. So sánh hai thuật toán hệ kiến SMMAS và hệ kiến MMAS với các bộ dữ liệu điển hình, các bộ dữ liệu nhỏ được chạy 500 bước lặp (500 bước tìm kiếm địa phương), bộ dữ liệu cỡ v a chạy 1000 bước lặp (1000 bước tìm kiếm địa phương) và cỡ lớn là 10.000 bước lặp (2000 bước tìm kiếm địa phương)

MMAS SMMAS

T t Trung T t Trung Bộ dữ liệu nhất bình nhất bình

4 13.2 1 5.9 Small1

14 24.2 10 15.6 Small2

6 13.8 2 5.8 Small3

0 8.9 0 4.2 Small4

4 7.9 0 3.4 Small5

311 386.5 228 249.4 Medium1

325 376.3 229 238.6 Medium2

Không có lời giải 917 925 Large

Với kết quả chạy thử nghiệm trên cho thấy thuật toán sử d ng quy tắc cập nhật

mùi SMMAS tốt hơn so với thuật toán sử d ng quy tắc cập nhật mùi MMAS. Về thời

gian thực chạy thuật toán sét với cùng số vòng lặp thì SMMAS cũng nhanh hơn so với

MMAS.

S ĩ có được kết uả như vậy là o đặc trưng của bài toán thời khóa biểu là

thông tin heuristic là rất đặc biệt và khó sử ng cho nên việc điều chỉnh các vết m i là

41

uan trọng nhất trong bài toán này.

ẾT UẬN

Bài toán lập thời khóa biểu là một bài toán được nhiều người quan tâm vì tính ứng d ng cao của nó trong các t chức giáo d c. Bài toán thuộc lớp NP khó nên khó giải

bằng các thuật toán truyền thống. Các thuật toán mô phỏng tự nhiên tỏ ra là phương

pháp hữu hiệu để giải các bài toán tối ưu t hợp nói chung và bài toán lập thời khóa biểu

nói riêng. Luận văn này đã trình bày phương pháp ACO để giải bài toán thời khóa biểu

cho trường học. Với thuật toán tối ưu hóa đàn kiến, luận văn cài đặt áp d ng quy tắc cập nhật mùi SMMAS mới. Thực nghiệm cho thấy thuật toán SMMAS tốt hơn thuật toán đa

mức và MMAS khi áp d ng cho bài toán UCTP. Đây chỉ là những thành công bước đầu

của hướng phát triển mới trong lĩnh vực tối ưu hóa đàn kiến và ứng d ng, luận văn hi

vọng các kết quả sẽ là một động lực để phát triển tiếp các chương trình ứng d ng khác t tối ưu hóa đàn kiến.

Với thời gian thực hiện luận văn ngắn, chúng tôi chưa đưa ra được chương trình

ứng ng hoàn thiện. Một trong những hướng phát triển của đề tài là xây ựng thời

42

khóa biểu cho trường đại học hệ tín chỉ Việt Nam với tình hình khảo sát c thể hơn.

TÀI LIỆU THAM KHẢO

Tiếng Việt

1. Đỗ Đức Đông (2012), Phương pháp tối ưu đàn kiến và ứng dụng, Luận án tiến sĩ công

nghệ thông tin Đ N-Đ G N.

Tiếng Anh

2. Dong Do Duc, uan oang uan, an uy . Dinh (2012), “M TA-REG: A computational meteheuristic method to improve the regulatory activity prediction”, Proc. of the 4th International Conference on the Development of Biomedical Engineering, pp. 450-453.

3. M. Dorigo, and T.Stützle (2004), Ant Colony Optimization, The MIT Press,

Cambridge, Masachusetts.

4. M. Dorigo, V. Maniezzo and A. Colorni (1991), The Ant System: An autocatalytic optimizing process, Technical Report 91-016 Revised, Dipartimento di Elettronica,

Politecnico di Milano, Milano, Italy.

5. M. Dorigo (1992), Optimization, learning and natural algorithms, PhD. dissertation,

Milan Polytechnique, Italy.

6. M. Dorigo and L.M. Gambardella (1997), “Ant colony system: A cooperative learning approach to the traveling salesman problem”, IEEE Trans. on evolutionary

computation, Vol 1 (1), pp. 53-66.

7. [GPS03] J. Gottlieb, M. Puchta, and C. Solnon. A study of greedy, local searchand ant colony optimization approaches for car sequencing problems.In Applications of

evolutionary computing, volume 2611 of LNCS, pages246–257. Springer, 2003.

8. [SH00] T. St¨utzle and H.H. Hoos. MAX-MIN Ant System. Journal of FutureGeneration Computer Systems, special issue on Ant Algorithms, 16:889–914,

2000.

9. Solnon, C.: Ants can solve constraint satisfaction problems. IEEE Transactionson

Evolutionary Computation 6(4) (2002) 347–357

10. I OG Ilog solver user s manual. Technical report, I OG (1998).

11. [LLW98] J.H.M. Lee, H.F. Leung, and H.W. Won. Performance of a comprehensive and efficient constraint library using local search. In 11th Australian JCAI, LNAI. Springer-Verlag, 1998.

12. Krzysztof Socha. Ant Algorithms for the University Course Timetabling Problem with

43

Regard to the State-of-the-Art. 2003

13. M.Dorigo and Thomas Stutzle. A short Convergence Proof for a class of Ant Colony

Optimization Algorithms, IEEE, 2002.

14. W.J. Gutjahr. ACO Algorithms with guaranteed convergence to the optimal solution

and A. Colorni

(1991), The Ant System: An

problem, Info.Processing Lett., vol.83, no.3, 2002, pp 145-153.

15. M. Dorigo, V. Maniezzo

autocatalytic optimizing process, Technical Report 91 -016 Revised, Dipartimento di Elettronica, Politecnico di Milano, Milano, Italy.

44