Đồ án: Tìm hiểu giải thuật di truyền ứng dụng giải bài toán lập lịch

192 lượt xem
Share

Đồ án Tìm hiểu giải thuật di truyền ứng dụng giải bài toán lập lịch tìm hiểu về bài toán lập lịch, giải thuật di truyền GAs, ứng dụng giải thuật di truyền và thiết kế hệ thống.

Mục lục nội dung

Đồ án: Tìm hiểu giải thuật di truyền ứng dụng giải bài toán lập lịch

1. Mở đầu

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 nhất cho bài toán trong thời gian nhỏ nhất. Các thuật toán như tìm kiếm không có thông tin /vét cạn (tìm kiếm trên danh sách, trên cây hoặc đồ thị) sử dụng phương pháp đơn giản nhất và trực quan nhất hoặc các thuật toán tìm kiếm có thông tin sử dụng heurictics để áp dụng các tri thức về cấu trúc của không gian tìm kiếm nhằm giảm thời gian cần thiết cho việc 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 có không gian tìm kiếm lớ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.

2. Nội dung

2.1 Tìm hiểu về bài toán lập lịch

Tìm hiểu chung 

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

Bài toán lập lịch thời khoá biểu

  • Giới thiệu bài toán
  • Dữ liệu bài toán

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

2.2 Giải thuật di truyền (GAs)

Tìm hiểu chung về GAs

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

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

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

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

  • Khởi động quần thể ban đầu
  • Đánh giá cá thể
  • Toán tử lai ghép
  • Toán tử đột biến
  • Điều kiện kết thúc

2.3 Ứng dụng giải thuật di truyền

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

  • Chọn mô hình cá thể
  • Tạo quần thể ban đầu
  • Độ thích nghi - chọn cá thể
  • Thuật toán lai ghép và đột biến

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

  • Chọn mô hình cá thể
  • Tạo quần thể ban đầu
  • Độ thích nghi - chọn cá thể
  • Thuật toán lai ghép và đột biến
  • Chọn điểm dừng thuật toán

2.4 Thiết kế hệ thống

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

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

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

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

  • Phép lai ghép
  • Phép đột biến

Độ thích nghi

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

3. Kết luận

Kết quả đạt được:

  • Áp dụng được giải thuật di truyền để giải quyết bài toán sắp thời khoá biểu.
  • Xây dựng thành công chương trình demo sắp xếp thời khoá biểu

Hạn chế:

  • Do giải thuật di truyền mang tính chất ngẫu nhiên nên đôi khi kết quả đạt được không phải là 100%.
  • Giải thuật Di Truyền có thể giải quyết bài toán tối ưu bất kỳ (cực tiểu hóa hàm mục tiêu) với n biến vào. Tuy nhiên, với số lượng biến vào khá nhiều, các giá trị hàm mục tiêu đạt được thường không gần với kết quả tối ưu thực sự. Để khắc phục vấn đề này, có thể tăng số lượng vòng lặp, hy vọng lần sinh sản muộn sẽ hình thành những con cháu với độ thích nghi cao ứng với các giá trị hàm mục tiêu gần kết quả tối ưu thực sự nhất.

4. Tài liệu tham khảo

Lập trình tiến hoá_Ts. Nguyễn Đình Thúc

Giới thiệu giải thuật Di truyền và Tính toán Tiến hóa _PGS.TS Randy Ribler khoa tin trƣờng đại học

Lynchburg,VA,USA

http://forum.mait.vn

http://www.kh-sdh.udn.vn

http://baigiang.violet.vn

http://www.vninformatics.com

--- Nhấn nút TẢI VỀ hoặc XEM ONLINE để tham khảo đầy đủ nội dung Đồ án trên ---

192 lượt xem
Share
Ngày:07/09/2020 Chia sẻ bởi:
TẢI VỀ XEM ONLINE

CÓ THỂ BẠN QUAN TÂM