Đề tài: ỨNG DỤNG KỸ THUẬT TRONG GIẢI THUẬT
DI TRUYỀN GIẢI CÁC BÀI TOÁN TỐI ƯU
HỌC VIỆN KỸ THUẬT QUÂN SỰ
KHOA CÔNG NGHỆ THÔNG TIN
Giáo viên hướng dẫn: PGS. TSKH Nguyễn Xuân Huy
Học viên : Trần Thị Kim Dung
Lớp : Cao học CNTT – Vinh
Khóa : K23
HÀ NỘI 2013
Báo cáo luận văn thạc sỹ
NỘI DUNG
CNTT-K23
GIỚI THIỆU
- Hiện trạng: Phương pháp liệt kê hay duyệt toàn bộ,…..
- Nhu cầu thực tế: Giải thuật di truyền (GA) là giải thuật đang được nhiều nhà nghiên cứu quan tâm.
Tốt: Không gian tìm kiếm nhỏ. Ngược lại, không tốt
Ứng dụng các kỹ thuật trong giải thuật di truyền các bài toán tối ưu
Mục tiêu của đề tài: Nghiên cứu BTTƯ; Nghiên cứu giải thuật SA và áp dụng giải một số bài toán tối ưu; Đề xuất giải thuật SA cải tiến.
CNTT-K23
NỘI DUNG
CNTT-K23
TỔNG QUAN VỀ BÀI TOÁN TỐI ƯU
CNTT-K23
BÀI TOÁN TỐI ƯU TỔNG QUÁT

Phát biểu bài toán:
- Thuật ngữ “tối ưu” chỉ việc nghiên cứu các bài toán có dạng:

- Với điều kiện:


- Hàm f(x) được gọi là hàm mục tiêu
- Hàm gi(x) gọi là hàm ràng buộc
- Miền ràng buộc:
CNTT-K23
MỘT SỐ BTTƯ ĐIỂN HÌNH
1. Bài toán xếp ba lô 0-1 và các phương pháp giải:
Bài toán phát biểu bằng toán học như sau:
- Cực đại hóa:

- Sao cho:
Các phương pháp giải:
Phương pháp vét cạn (Brute – force)
Phương pháp quy hoạch động
Phương pháp tham lam
CNTT-K23
MỘT SỐ BTTƯ ĐIỂN HÌNH
2. Bài toán người du lịch và các phương pháp giải:
Phát biểu bài toán:
Cij : Là chi phí đi từ tp I đến tp j.
Các ràng buộc:
Các phương pháp giải:
Phương pháp vét cạn
Phương pháp tham lam
Phương pháp nhánh cận
CNTT-K23
MỘT SỐ BTTƯ ĐIỂN HÌNH
3. Bài toán vận tải và các phương pháp giải:
Phát biểu bài toán:

Trong đó:
Với các ràng buộc:




với i=1,2,..,n và j=1,2,..,k


CNTT-K23
NỘI DUNG
CNTT-K23
THUẬT GIẢI DI TRUYỀN (GA)
CNTT-K23
THUẬT GIẢI DI TRUYỀN (GA)
Sơ đồ thuật giải di truyền
CNTT-K23
THUẬT GIẢI DI TRUYỀN (GA)
- Chọn cách biểu diễn lời giải là biểu diễn bằng nhiễm sắc thể: dạng dãy nhị phân, hoán vị, véc tơ…
- Các toán tử cơ bản trong giải thuật GA:
+ Toán tử chọn lọc
+ Toán tử lai ghép
+ Toán tử đột biến
- Với mỗi toán tử này, có rất nhiều cách lựa chọn. Do vậy, trong từng bài toán cụ thể sẽ có lựa chọn cụ thể.

CNTT-K23
NỘI DUNG
CNTT-K23
CÀI ĐẶT VÀ THỬ NGHIỆM
CNTT-K23
CÀI ĐẶT VÀ THỬ NGHIỆM
CNTT-K23
CÀI ĐẶT VÀ THỬ NGHIỆM
Nhận xét:
Khi tạo ra thế hệ kế tiếp, mất các cá thể tốt rất nhiều chạy nhiều lần thì mới có kết quả tốt nhất.
Nguyên nhân: Tham số kích thước quần thể là quan trọng nhất và bị giảm trong quá trình tiến hóa. Và hai tham số còn lại phụ thuộc vào tham số kích thước quần thể.
Nếu chúng ta khởi tạo cho kích thước quần thể lớn thì cho kết quả rất tốt. Ngược lại, cho kết quả xấu.
CNTT-K23
CÀI ĐẶT VÀ THỬ NGHIỆM
Cải tiến như sau:
Cải tiến cách thành lập thế hệ kế tiếp trong lược đồ SGA:
Thế hệ kế tiếp được hình thành từ quần thể bố mẹ và các cá thể con sau khi đã được đột biến. Sau đó, lựa chọn các cá thể tốt sao cho đủ kích thước quần thể và kích thước này thay đổi trong quá trình tiến hóa.
Thuật toán cụ thể như sau:
CNTT-K23
CÀI ĐẶT VÀ THỬ NGHIỆM
CNTT-K23
CÀI ĐẶT VÀ THỬ NGHIỆM
CNTT-K23
NỘI DUNG
CNTT-K23
KẾT QUẢ VÀ ĐÁNH GIÁ
Kết quả:
Đôi khi đưa ra được kết quả gần tối ưu và phải chạy nhiều lần mới ra được kết quả tối ưu, vì:
+ Tạo ra quần thể mới bằng cách sử dụng AverageFitness
+ Kỹ thuật tái sinh sử dụng lấy ngẫu nhiên.
+ Trong chương trình, chỉ sử dụng toán tử lai ghép, chưa sử dụng toán tử đột biến.
Đánh giá: Chương trình còn chạy chậm.
CNTT-K23
KẾT LUẬN VÀ KIẾN NGHỊ
Đã làm được:
Đã đề xuất một kỹ thuật biến đổi kích cỡ quần thể ngay trong quá trình tiến hóa.
Chưa làm được:
Chưa dùng toán tử đột biến.
Hướng phát triển:
- Sử dụng toán tử đột biến
- Sử dụng một số mô hình để thử nghiệm và so sánh kết quả thu được giữa các mô hình.
CNTT-K23
XIN CHÂN THÀNH CẢM ƠN !