Bài giảng Tính toán tiến hóa - Chương 1: Tổng quan về bài toán tối ưu

Evolutionary Computing Nội dung 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 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 : 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 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 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 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 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 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 Fuzzy systems Genetic Algorithms Genetic Programming Artificial Neural Networks Evolutionary Programming Evolutionary Strategies Differential Evolution PSO, ACO Swarm Intelligence Evolutionary Computing Computational Intelligence [1] [1] Engelbrecht, Andries P.  Computational intelligence: an introduction . John Wiley & Sons, 2007. Các hội thảo, tạp chí đầu ngành WIPO Technology Trends 2019  Artificial Intelligence WIPO: World Intellectual Property Organization AI techniques  AI functional applications  AI application fields   Các track trong Tính toán tiến hóa 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 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 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 t hế hệ sau luôn có xu h ư ớng phát triển và hoàn thiện h ơ n thế hệ trước. Giải thuật tiến hóa Tiến hóa tự nhiên duy trì nhờ hai quá trình cơ bản: Sinh sản : C ác đặc tính di truyền tốt của cá thể cha và mẹ được di truyền cùng nhau vào các thế hệ con (lai ghép) Đ ảm bảo được sự đa dạng của quần thể (đột biến) Chọn lọc tự nhiên: Các cá thể khỏe mạnh hơn, thích nghi hơn với môi trường => tồn tại. K hông thích nghi được với môi trường => b ị đào thải . Các giải thuật tiến hóa cũng mô phỏng hai quá trình này. Sơ đồ chung của EAs Mô hình thuật toán tiến hóa Các thành phần của EAs Mã hóa biểu diễn Hàm định giá (thích nghi) Quần thể Cơ chế chọn cha mẹ Toán tử sinh sản (lai ghép và đột biến) Cơ chế lựa chọn sinh tồn (sự thay thế) Điều kiện dừng Mã hóa biểu diễn Phân biệt kiểu hình và kiểu di truyền Kiểu di truyền là biểu diễn mã hóa lời giải của bài toán không gian kiểu di truyền. Kiểu hình là lời giải của bài toán t ư ơng ứng kiểu di truyền 1 2 3 4 5 6 7 8 Kiểu di truyền: hoán vị của các số từ 1  8 Ví dụ bài toán 8 con hậu: Kiểu hình: 1 cấu trúc bảng Obvious mapping Mã hóa biểu diễn Phân biệt kiểu hình (phenontype) và kiểu di truyền (genontype) Kiểu di truyền là biểu diễn mã hóa lời giải của bài toán không gian kiểu di truyền. Kiểu hình là lời giải của bài toán t ư ơng ứng kiểu di truyền Quá trình mã hóa: kiểu hình => kiểu di truyền (1-n) Quá trình giải mã: kiểu di truyền => kiểu hình (1-1) Để tìm đ ư ợc tối ư u toàn cục, phải đảm bảo luôn tồn tại một mã hóa có kiểu hình biểu diễn đ ư ợc một lời giải khả thi bất kì của bài toán. Hàm đánh giá Hàm đánh giá cho biết mức độ thích nghi của cá thể đối với môi tr ư ờng Giá trị độ thích nghi càng cao, các cá thể có khả năng sinh tồn và c ơ hội tham gia vào quá trình sinh sản càng lớn Độ thích nghi cho biết mức độ tốt của lời giải t ư ơng ứng với biểu diễn cá thể Thông th ư ờng, hàm thích nghi đ ư ợc tính thông qua hàm chi phí lời giải của bài toán VD fitness(individual) = 1 – cost(individual) Hoặc fitness(individual) = 1/ cost(individual) Quần thể Quần thể là một tập hợp các cá thể. Số l ư ợng cá thể trong quần thể th ư ờng cố định Sự đa dạng của quần thể đ ư ợc thể hiện qua: Sự đa dạng giá trị thích nghi Đa dạng về kiểu di truyền Đa dạng về kiểu hình Quá trình chọn lọc cá thể sinh tồn ở thế hệ tiếp theo đ ư ợc thực hiện trên quần thể C ơ chế chọn lọc cha mẹ Xác suất lựa chọn các cá thể làm cha mẹ dựa trên giá trị độ thích nghi của chúng. Một số c ơ chế chọn lựa cha mẹ: Lựa chọn ngẫu nhiên Lựa chọn theo thứ hạng Lựa chọn theo thể thức giao đấu Lựa họn theo bánh xe roulete Toán tử lai ghép Là quá trình hình thành các NST mới ở cá thể con dựa trên các NST của cha mẹ. Các NST ở cá thể con sinh ra bằng cách ghép một hay nhiều đoạn gene của hai hay nhiều NST cha mẹ với nhau Các cá thể lai ghép với xác suất Ví dụ: Toán tử lai ghép một cắt Toán tử đột biến Là hiện t ư ợng cá thể con mang một (số) tính trạng không có trong mã di truyền của cha mẹ Xác suất xảy ra đột biến nhỏ h ơ n rất nhiều xác suất lai ghép Toán tử đột biến giúp đảm bảo tính đa dạng cả quần thể C ơ chế đấu tranh sinh tồn Là c ơ chế chọn ra các cá thể mang đi sinh tồn ở thế hệ tiếp theo Các c ơ chế đấu tranh sinh tồn: Chọn lọc dựa vào tuổi: Loại bỏ các cá thể tồn tại lâu trong quần thể => đảm bảo tính đa dạng, tránh t ư t ư ởng “ cổ hủ ” Chọn lọc theo thứ hạng, giữ lại cá thể ư u tú=> giữ đ ư ợc xu h ư ớng tăng tr ư ởng của quần thể ổn định Nạp lại hoàn toàn Nạp lại ngẫu nhiên Nạp lại một phần Có thể sử dụng các ph ư ơng thức ở bước lựa chọn bố mẹ Điều kiện dừng Điều kiện dừng của thuật toán th ư ờng thỏa mãn nh ư sau: Sau một số thế hệ nhất định, thuật toán không cải thiện chất l ư ợng lời giải Sau một số thế hệ nhất định Thuật toán sử dụng hết l ư ợng phép tính đánh giá cố định Các biến thể EAs phổ biến Giải thuật di truyền – Genetic Algorithm Tiến hóa sai phân – Different Evolutionary Algorithm Chiến lược tiến hóa – Evolution Strategies Lập trình tiến hóa – Evolution Programming Lập trình di truyền – Genetic Programming Tiến hóa đa nhiệm – Multifactorial Evolutionary Algorithm Giải thuật di truyền Đối tượng: - Tối ưu hóa rời rạc Đặc điểm: Representation Binary strings v.v Recombination N-point or uniform Mutation Bitwise bit-flipping with fixed probability Parent selection Fitness-Proportionate Survivor selection All children replace parents Speciality Emphasis on crossover Lập trình di truyền Đối tượng: - Học máy ( Xây dựng các công thức, dự đoán v.v) Đặc điểm: Representation Tree structures Recombination Exchange of subtrees Mutation Random change in trees Parent selection Fitness proportional Survivor selection Generational replacement Representation Tree structures Chiến l ư ợc tiến hóa Đối tượng: - Tối tham số thực Đặc điểm: Representation Real-valued vectors Recombination Discrete or intermediary Mutation Gaussian perturbation Parent selection Uniform random Survivor selection (  ,  ) or (  +  ) Specialty Self-adaptation of mutation step sizes Lập trình tiến hóa Đối tượng: Học máy - sử dụng máy trạng thái xác định Tối ưu số - numercial optimization Đặc điểm : Representation Real-valued vectors Recombination None Mutation Gaussian perturbation Parent selection Deterministic Survivor selection Probabilistic (  +  ) Specialty Self-adaptation of mutation step sizes (in meta-EP) So sánh các biến thể Lập trình tiến hóa (EP) Chiến lược tiến hóa (EG) Lập trình di truyền (GP) Giải thuật di truyền (GA) Áp dụng Học máy, tối ưu số Tối ưu số CT học máy Tối ưu hóa rời rạ Mã hóa NST Véc tơ giá trị thực Véc tơ giá trị thực Cây Xâu nhị phân v.v Lai ghép Không Riêng biệt hoặc trung gian Trao đổi cây con N-point, đồn nhất v.v Đột biến Phân phối Gauss Phân phối Gauss Thay đổi nút Đảo bít v.v Chọn lọc cha mẹ 1 cha sinh 1 con Ngẫu nhiên hay cố định Dựa trên fitness Dựa trên fitness Đấu tranh sinh tồn (  +  ) (  ,  ) or (  +  ) Thay thế toàn bộ Nhiều cách.. Đặc biệt Tự thích nghi Tự thích nghi Cây Lai ghép Thanks for your attention