Bài giảng Thiết Kế & Đánh Giá Thuật Toán - Xấp sỉ - Lê Nguyên Khôi

Nội dung text: Bài giảng Thiết Kế & Đánh Giá Thuật Toán - Xấp sỉ - Lê Nguyên Khôi

2. 
   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
3. 
   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
4. 
   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
5. 
   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
6. 
   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
7. 
   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
8. a ea
   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
9. e
   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
10. a
    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
11. eee
    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
12. 
    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
13. 
    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
14. ơ
    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
15. ơ e
    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
16. ơ eae
    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
17. ơ eae
    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
18. ơ ee
    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
19. 
    Đ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
20. 
    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
21. 
    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