Giáo trình Thiết kế & Đánh giá thuật toán - Bài giảng 14: Xấp xỉ - Lê Nguyên Khôi

Phân Tích & Thiết Kế Thuật Toán Xấp Xỉ TS. Lê Nguyên Khôi Trường Đại Học Công Nghệ - ĐHQGHN Nội Dung
Phương pháp chính xác
Phương pháp xấp xỉ
Bài toán tìm kiếm tối ưu
Một số bài toán tiêu biểu
Một số phương pháp 1 P.P. Chính Xác
Tìm được lời giải tốt nhất (tối ưu)
Thời gian tìm kiếm lâu
Với những bài toán phức tạp
Không khả thi (quá lâu)
Với những bài toán thực tế
Thời gian tìm lời giải có vai trò quan trọng 2 P.P. Xấp Xỉ
Tìm lời giải cận tối ưu
Trong khoảng thời gian hợp lý
Phù hợp:
Với những bài toán phức tạp
Với những bài toán thực tế
Đôi khi chỉ cần tìm được lời giải chấp nhận được 3 Bài Toán Tìm Kiếm Tối Ưu
Tìm lời giải tối ưu trong các lời giải khả thi
Lời giải khả thi:
Phải thỏa mãn các ràng buộc cứng
Đánh giá / so sánh giữa các lời giải khả thi:
Tối thiểu các vi phạm ràng buộc mềm
Giữa trên một (hoặc vài) hàm mục tiêu 4 P.P. Xấp Xỉ Với Tìm Kiếm Tối Ưu
P.P. xác định lời giải khả thi
Xây dựng lời giải khả thi bắt đầu từ lời giải rỗng
Xây dựng một lời giải ngẫu nhiên, rồi sửa các vi phạm ràng buộc cứng
P.P. so sánh để xác định lời giải tối ưu
Thông thường dựa trên giá trị hàm mục tiêu
P.P. xác định lời giải cận tối ưu dựa trên
Thời gian
Giá trị hàm mục tiêu
Mức độ thay đổi giá trị hàm mục tiêu 5 Bài Toán Tiêu Biểu
Thời khóa biểu (timetabling)
Lịch sản xuất (job shop scheduling)
Đóng hàng (bin packing)
Lịch làm việc (employee scheduling)
Định tuyến (routing) 6 Thời Khóa Biểu (Timetabling)
Tìm những khoảng thời gian phù hợp để sắp xếp các môn học với nguồn lực hạn chế
Theo 02 cách phân loại
Đại học – trung học phổ thông
Khóa học – kỳ thi 7 Lịch Sản Xuất (Job Shop Scheduling)
Sắp xếp một danh sách các công việc
Mỗi công việc bao gồm nhiều việc nhỏ
Những việc này phải thực hiện theo một thứ tự, và sử dụng máy công cụ nhất định nào đó
Công việc có thể được thực hiện song song
Mục tiêu:
Quá trình sản xuất ngắn nhất
Kho bãi lưu các chi tiết thiết bị là ít nhất 8 Đóng Hàng (Bin Packing)
Tìm tập các đồ vật đóng gói vào thùng chứa
Mỗi đồ vật có khối lượng (hay thể tích)
Thùng chứa có khối lượng (hay thể tích) tối đa không được phép vượt quá
Mục tiêu
Tối đa tổng khối lượng (hay thể tích) tập đồ vật được đóng gói
Ví dụ: Bài toán ba lô 9 Lịch Làm Việc (Employee Scheduling)
Lập lịch làm việc 24/7 (3 ca) phục vụ nhà máy sản xuất, bệnh viện
Ràng buộc thông thường
Ca làm việc phải có đủ nhân viên
Forward shift rotation
Ngày nghỉ 10 Định Tuyến (Routing)
Tìm các tập đường đi hiệu quả cho phương tiện vận tải để phục vụ nhu cầu khách hàng
Ràng buộc thông thường
Nhu cầu khách hàng cần được phục vụ
Trọng tải phương tiện
Mục tiêu:
Tối thiểu tổng chi phí vận tải 11 Bài Toán Phân Phối
Các nhà máy sản xuất hàng tiêu dùng
Dựa trên nhu cầu, hàng tiêu dùng từ nhà máy được vận chuyển đến các tổng kho vận
Tại kho vận, hàng tiêu dùng được phân chia, đóng gói, và chuyển đến các điểm phân phối
Kết hợp bài toán:
Lịch sản xuất
Đóng hàng
Lịch làm việc
Định tuyến 12 Phương Pháp Xấp Xỉ
Dữ liệu lớn, nhiều ràng buộc, lời giải cận tối ưu
Heuristics
Thiết kế cho từng bài toán cụ thể
Không áp dụng được cho các bài toán khác
Metaheuristics
Thiết kế cho giải bài toán tối ưu nói chung
Có thể áp dụng được cho các bài toán khác nhau
Hyperheuristics
Thiết kế cho một họ (lớp) bài toán 13 Phương Pháp Xấp Xỉ - Heuristics
Thiết kế thuật giải dựa trên
Tìm hiểu tập ràng buộc
Phương pháp thỏa mãn từng ràng buộc
Thứ tự áp dụng phương pháp
Ưu điểm
Tìm được lời giải nhanh
Chất lượng lời giải tốt
Nhược điểm
Không áp dụng được cho bài toán khác 14 Phương Pháp Xấp Xỉ - Metaheuristics
Thiết kế thuật giải dựa trên
Xây dựng lời giải chất lượng tương đối
Tối ưu chất lượng (giá trị hàm mục tiêu)
Ưu điểm
Có thể áp dụng được cho bài toán khác nhau
Nhược điểm
Chất lượng lời giải thấp 15 Phương Pháp Xấp Xỉ - Metaheuristics
Local search (tìm kiếm địa phương)
Tabu Search (tìm kiếm tabu)
Simulated Annealing (mô phỏng luyện kim)
Neighbourhood Search (tìm kiếm láng giềng)
Learning mechanism (kỹ thuật học)
Ant Colony Optimisation (đàn kiến)
Neural Network (mạng nơron)
Population (quần thể)
Genetic Algorithm (thuật toán di truyền)
Swarm Optimisation (tối ưu bầy đàn) 16 Phương Pháp Xấp Xỉ - Hyperheuristics
Thiết kế thuật giải dựa trên
Tìm hiểu một họ bài toán
Các phương pháp heuristics giải họ bài toán
Cách kết hợp các phương pháp heuristics
Đánh giá phương pháp heuristics
Phân loại
Heuristic chọn heuristics
Heuristic tạo heuristics 17 Vấn Đề Khác
Đa mục tiêu (multiobjective)
Thỏa mãn các ràng buộc không đơn giản
Chuyển ràng buộc khó thành mục tiêu
Mục tiêu song song / theo thứ tự 18 Vấn Đề Khác
Kiểu hình – kiểu gien (phenotype – genotype)
Phenotype: xác định lời giải nào tốt hơn
Genotype: cung cấp nhiều thông tin hơn 19 Vấn Đề Khác
Dữ liệu thời gian thực (real-time data)
Sự cần thiết tìm lời giải cận tối ưu
Dữ liệu mới thay đổi lời giải vừa tìm được
Re-optimization 20