Chuyên Đề Giải thuật di truyền các kĩ thuật và áp dụng trong các bài toán thực tế

Bài viết này là tổng kết của quá trình tìm hiểu và áp dụng giải thuật di truyền trong việc giải quyết các bài toán tối ưu. Trong chương đầu tiên chúng ta sẽ nhắc lại cấu trúc của giải thuật di truyền bao gồm một số các kĩ thuật về mã hóa, lai ghép, đột biến Sang chương tiếp theo chúng ta sẽ áp dụng giải thuật di truyền vào giải quyết một bài toán ứng dụng, cụ thể là bài toán xấp xỉ nghiệm của một hệ phương trình. Và chương cuối cùng là đề xuất một hướng giải cho bài toán thực tế “Xây dựng chương trình gợi ý đăng kí học tập cho sinh viên” bằng giải thuật di truyền.

Các file gồm có:
- file doc (63 trang)
- file source gồm có source của chương trình xấp xỉ nghiệm của hệ phương trình (code theo giải thuật di truyền)
mục lục file doc
Mở Đầu. 2
Chương I Giới thiệu về giải thuật di truyền. 3
Phần I Tổng quan về giải thuật di truyền. 3
1.1 Sơ lược về lịch sử 3
1.2 Đặc điểm của giải thuật di chuyền. 3
1.3 Các ứng dụng điển hình của giải thuật di chuyền. 3
1.4 Bài toán mở đầu. 3
Phần II Các phương pháp mã hóa trong giải thuật di chuyền. 5
2.1 Mã hóa nhị phân. 5
2.2 Mã hóa đa giá trị 5
2.3 Mã hóa hoán vị 5
2.4 Mã hóa cây. 5
2.5 Mã hóa rời rạc hóa trị thực. 5
Phần III Các cách lai ghép trong giải thuật di chuyền. 6
3.1 Lai hóa điểm cắt. 6
3.2 Lai hóa theo thứ tự 6
3.3 Lai ghép tương hợp bộ phận. 6
3.4 Phép lai chu trình. 6
3.5 Phép lai số học. 6
3.6 Lai ghép trộn cạnh. 7
Phần IV. Các phương pháp đột biến. 9
4.1Đảo bit. 9
4.2 Các đột biến dùng trong mã hóa hoán vị 10
PhầnV. Các phương pháp chọn lọc cha mẹ. 12
5.1 Chọn lọc ngẫu nhiên. 12
5.2 Chọn lọc theo vòng quay roulette. 12
5.3 Chọn lọc theo cơ chế lấy mẫu toàn phần. 13
5.4 Chọn lọc theo xếp hạng. 13
5.5 Chọn theo thể thức giao đấu. 15
Phần VI. Phương pháp đấu tranh sinh tồn. 16
6.1 Nạp lại hoàn toàn. 16
6.2 Nạp lại ngẫu nhiên. 16
6.3 Giữ lại cá thể ưu tú. 16
6.4 Các điều kiện đặc biệt. 16
6.5 Áp dụng các phương pháp của chọn lọc cha mẹ. 16
Chương II Áp dụng giải thuật di truyền để giải bài bài toán xấp xỉ nghiệm cho hệ phương trình. 17
Phần I Giới thiệu bài toán. 17
Bài toán toán xử lý. 17
Ngôn ngữ lập trình: java. 17
Thuật toán sử dụng: giải thuật di truyền. 17
Phần II Tiếp cận bài toán. 18
2.1 phân tích yêu cầu bài toán. 18
2.2 Phân chia bài toán thành các module. 18
Phần III Giải bài toán. 19
3.1 Cấu trúc của một hệ phương trình nhập vào. 19
3.2 các phép tính, hằng số và các hàm chương trình hỗ trợ 20
3.3 Tính toán giá trị biểu thức. 21
3.4 Cách mã hóa lời giải 22
3.5 Lai ghép. 23
3.6 Đột biến. 25
Các phương pháp đấu tranh sinh tồn trong quần thể. 26
Phần IV Các class chính của chương trình. 28
Class Solution. 28
Class CrossMutationManager. 32
Phần V Hướng dẫn sử dụng giao diện. 37
Phần VI Một số kết quả Test. 40
6.1 phương trình một biến chứa hàm ln. 40
6.2 phương trình một biến bậc cao. 40
6.3 Hệ phương trình tuyến tính 3 ẩn. 40
6.4 Hàm mũ cho phương trình 3 biến. 41
6.5 Phương trình hỗn hợp. 41
Chương III Áp dụng giải thuật di truyền vào giải bài toán gợi ý đăng kí học tập cho sinh viên. 43
Phần I Giới thiệu bài toán. 43
Phần II Phân tích bài toán. 44
2.1 Input và output của bài toán. 44
2.2 Các tài nguyên cần thiết để xây dựng hệ thống. 44
2.3 Các bảng cơ sở dữ liệu sử dụng trong bài toán. 44
Phần III Giải bài toán. 49
3.1 Mã hóa lời giải 49
3.2 Tính fitness. 49
3.3 Phép lai ghép. 54
3.4 Đột biến. 58
3.5 Phép chọn lọc. 59