Bài giảng Thiết kế và đánh giá thuật toán - 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