Ứng dụng giải thuật di truyền trong bài toán lập thời khóa biểu (CH1301085)

Trong ngành khoa học máy tính, tìm kiếm lời giải tối ưu cho các bài toán là vấn đề được các nhà khoa học máy tính đặc biệt rất quan tâm. Mục đích chính của các thuật toán tìm kiếm lời giải là tìm ra lời giải tối ưu cho bài toán trong thời gian nhỏ nhất. Các thuật toán như tìm kiếm được sử dụng nhiều nhưng chỉ với không gian tìm kiếm nhỏ và không hiệu quả khi tìm kiếm trong không gian tìm kiếm lớn. Tuy nhiên, trong thực tiễn có rất nhiều bài toán tối ưu với không gian tìm kiếm rất lớn cần phải giải quyết. Vì vậy, việc đòi hỏi thuật giải chất lượng cao và sử dụng kỹ thuật trí tuệ nhân tạo đặc biệt rất cần thiết khi giải quyết các bài toán đó. Thuật giải di truyền (genetic algorithm) là một trong những kỹ thuật tìm kiếm lời giải tối ưu đã đáp ứng được yêu cầu của nhiều bài toán và ứng dụng.

Thuật giải di truyền đã được phát minh ra để bắt chước quá trình phát triển tự nhiên trong điều kiện quy định sẵn của môi trường. Các đặc điểm của quá trình này đã thu hút sự chú ý của John Holand (ở đại học Michigan) ngay từ những năm 1970. Holand tin rằng sự gắn kết thích hợp trong thuật giải máy tính có thể tạo ra một kỹ thuật giúp giải quyết các vấn đề khó khăn giống như trong tự nhiên đã diễn ra-thông qua quá trình tiến hóa.

Trên thế giới hiện nay, Thuật Giải Di Truyền kết hợp với công nghệ thông tin được ứng dụng để giải quyết những vấn đề phức tạp trong hệ thống điện một cách rất hiệu quả. Nhưng trong đề tài này, chúng ta sẽ nghiên cứu ứng dụng Thuật Giải Di Truyền trong việc xếp thời khoá biểu trong trường đại học.

NỘI DUNG:

MỤC LỤC 1

LỜI MỞ ĐẦU 3

CHƯƠNG I: TÌM HIỂU VỀ BÀI TOÁN LẬP LỊCH 4

1.1 Tìm hiểu chung 4

1.2 Các đặc tính của bài toán lập lịch 4

1.3 Bài Toán Lập Lịch Thời Khoá Biểu 4

1.3.1 Giới thiệu bài toán 4

1.3.2 Dữ liệu bài toán 4

1.4 Một số bước cơ bản để giải quyết bài toán lập lịch thời khoá biếu 5

CHƯƠNG II: GIẢI THUẬT DI TRUYỀN (GAs) 6

2.1 Tìm hiểu chung về GAs 6

2.2 Các toán tử của giải thuật di truyền 9

2.3 Các tham số của giải thuật di truyền. 9

2.4 Công thức của Giải thuật Di Truyền 10

2.5 Các thành phần của thuật giải di truyền 10

2.5.1 Khởi động quần thể ban đầu 10

2.5.2 Đánh giá cá thể 11

2.5.3 Toán tử lai ghép 11

2.5.4 Toán tử đột biến 11

2.5.5 Điều kiện kết thúc 12

CHƯƠNG III: ỨNG DỤNG GIẢI THUẬT DI TRUYỀN VÀO BÀI TOÁN XẾP LỊCH THỜI KHOÁ BIỂU 13

3.1 Giai đoạn 1 - xếp lịch học các lớp 13

3.1.1 Chọn mô hình cá thể 13

3.1.2 Tạo quần thể ban đầu 16

3.1.3 Độ thích nghi - chọn cá thể 16

3.1.4 Thuật toán lai ghép và đột biến 17

3.2 Giai đoạn 2 - xếp lịch học cho toàn bộ cơ sở 17

3.2.1 Chọn mô hình cá thể 17

3.2.2 Tạo quần thể ban đầu 18

3.2.3 Độ thích nghi - chọn cá thể 19

3.2.4 Thuật toán lai ghép và đột biến 19

3.2.5 Chọn điểm dừng thuật toán 19

CHƯƠNG IV: THIẾT KẾ HỆ THỐNG LẬP LỊCH THỜI KHÓA BIỂU 21

4.1 Thiết kế cơ sở dữ liệu bài toán 21

4.2 Các đối tượng của lịch học 21

4.3 Biểu diễn nhiễm sắc thể 22

4.4 Các tham số của giải thuật di truyền 23

4.4.1 Phép lai ghép 24

4.4.2 Phép đột biến 26

4.5 Độ thích nghi 27

4.6 Chương trình thực nghiệm 29

LỜI KẾT 32

Hạn chế: 32

Hướng phát triển trong tương lai 32

TÀI LIỆU THAM KHẢO 33

LINK 1 - TÌM KIẾM SÁCH/TÀI LIỆU ONLINE (GIÁ ƯU ĐÃI NHẤT)

LINK 2 - TÌM KIẾM SÁCH/TÀI LIỆU ONLINE (GIÁ ƯU ĐÃI NHẤT)

LINK 3 - TÌM KIẾM SÁCH/TÀI LIỆU ONLINE (GIÁ ƯU ĐÃI NHẤT)

LINK 4 - TÌM KIẾM SÁCH/TÀI LIỆU ONLINE (GIÁ ƯU ĐÃI NHẤT)

LINK DOWNLOAD (WORD)

LINK DOWNLOAD (PDF)