Bài giảng Tính toán tiến hóa - Bài 2: Tổng quan về bài toán tối ưu - Huỳnh Thị Thanh Bình
Nội dung
2
Tổng quan về bài toán tối ưu
Tổng quan về Tính toán tiến hóa
Tổng quan về Bài toán tối ưu
Tổng quan về bài toán tối ưu
4
Tất cả các bài toán trong thực tế đều có thể phát biểu
dưới dạng bài toán tối ưu
Bài toán tối ưu là các bài toán mà chúng ta cần đi tìm
kiếm một lời tốt nhất (min hoặc max) trong tập các lời
giải có thể
Mỗi bài toán tối ưu gồm 2 thành phần (X,f)
X: tập các lời giải khả thi (không gian tìm kiếm)
f là hàm mục tiêu của bài toán cần tối thiểu (minimize)
푓: 푋 → 푅
Mục tiêu tìm của bài toán là tìm 푥∗ ∈ 푋 sao cho
푓 푥∗ ≤ 푓 푥 ∀푥 ∈ 푋
Tổng quan về bài toán tối ưu
5
푓(푥∗) : Giá trị tối ưu
푆 = { 푥 ∈ 푋| 푓(푥) = 푓(푥∗)} : Tập các lời giải tối ưu
Phân loại bài toán tối ưu theo số lượng hàm mục tiêu
Bài toán có 01 hàm mục tiêu: => Bài toán tối ưu đơn mục
tiêu (single-objective problem)
Bài toán có hai hoặc ba hàm mục tiêu => Bài toán tối ưu đa
mục tiêu (multi-objective problem)
Bài toán có số mục tiêu >= 4 => Bài toán tối ưu nhiều mục
tiêu (many-objective problem)
Tổng quan về bài toán tối ưu
6
Phân loại bài toán tối ưu theo lý thuyết tính toán
P: Tồn tại thuật toán có thể giải trong thời gian đa thức
NP: Có thể kiểm tra lời giải trong thời gian đa thức
NP Khó: Chưa có hoặc không tồn tại thuật toán giải chính
xác trong thời gian đa thức.
NP đầy đủ: Các bài toán vừa thuộc NP, vừa thuộc NP-Khó
Tổng quan về bài toán tối ưu
7
Tại sao bài toán tối ưu khó?
Kích thước không gian tìm kiếm : LỚN
Không gian tìm kiếm phức tạp
Tổng quan về bài toán tối ưu
8
Tại sao bài toán tối ưu khó?
Constraints của không gian lời giải.
Hàm mục tiêu thay đổi theo thời gian (dynamic, non-
stationary optimization problems).
Conflict giữa nhiều mục tiêu- Pareto optimality
Tổng quan về bài toán tối ưu
9
Các hướng tiếp cận giải bài toán tối ưu
Sử dụng thuật toán chính xác
Sử dụng thuật toán xấp xỉ gần đúng
Hầu hết các bài toán tối trong thực tế là bài toán NP-Khó
=> hướng sử dụng các thuật toán chính xác là không khả
thi
=> Khóa học này trình bày các kỹ thuật tìm kiếm xấp xỉ thông
minh dựa trên các quá trình tự nhiên để giải bài toán tối ưu
khó!
Tổng quan về Tính toán tiến hóa
Tổng quan về Tính toán tiến hóa
11
Tính toán tiến hóa nghiên cứu các giải thuật tối ưu tìm
kiếm dựa trên học thuyết tiến hóa của Darwin
Các giải thuật này gọi là tên chung là Giải thuật tiến hóa
(Evolutionary Algorithms – EAs)
EAs là thuật toán ngẫu nhiên dựa trên quần thể
Tốc độ nhanh, hiệu quả
Xử lý các bài toán tối ưu liên tục, rời rạc, tìm cực trị hàm
đa biến, phi tuyến, không khả vi, multi-modal,….
Cho chất lượng lời giải tốt trong thời gian chấp nhận
được
Đang được sử dụng rộng rãi trong việc giải quyết các bài
toán tối ưu NP-Khó, NP-đầy đủ
Tổng quan về Tính toán tiến hóa
12
Computational
Intelligence [1]
Evolutionary
Computing
Artificial Neural
Networks
Swarm
Intelligence
Fuzzy
systems
Genetic
Algorithms
Genetic
Programming
Evolutionary
Programming
Evolutionary
Strategies
PSO,
ACO…
Differential
Evolution
[1] Engelbrecht, Andries P. Computational intelligence: an introduction. John Wiley & Sons,
2007.
Các hội thảo, tạp chí đầu ngành
13
14
WIPO Technology Trends 2019
Artificial Intelligence
WIPO: World Intellectual Property Organization
AI techniques
15
AI functional applications
16
AI application fields
17
Các track trong Tính toán tiến hóa
18
EC in Game
EC in Healthcare and E-health
EC in Vehicles and Transportation Systems
EC in Cyber Security
EC in Data Mining
EC in Big Data
EC in Dynamic and Uncertain Environments
EC for Engineering Solutions
EC in Multimedia Signal and Vision Processing
EC in Feature Analysis, Selection and Learning in Image
and Pattern Recognition
Ứng dụng của Tính toán tiến hóa
19
Planning: routing optimization and scheduling;
Design: neural network architectures and structural
optimization;
Control: controllers for game engines, and visual
guidance systems for robots;
classification and clustering;
function approximation and time series modeling;
Regression;
Composing music; and
Data mining.
Giải thuật tiến hóa
20
Giải thuật tiến hóa (Evolutionary Algorithms- EAs) được hình
thành dựa trên quan niệm :
“Quá trình tiến hoá tự nhiên là quá trình hoàn hảo nhất, hợp lý nhất
và tự nó đã mang tính tối ưu”
Các thế hệ sau luôn có xu hướng phát triển và hoàn thiện hơn thế
hệ trước.
Tải về để xem bản đầy đủ
40 trang
27/04/2022
8760
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Tính toán tiến hóa - Bài 2: Tổng quan về bài toán tối ưu - Huỳnh Thị Thanh Bình", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_tinh_toan_tien_hoa_bai_2_tong_quan_ve_bai_toan_toi.ppt
2. IntroEC_new_new.pdf
