Bài giảng Tính toán tiến hóa - Huỳnh Thị Thanh Bình

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) 28 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ể 29 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 30 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 31 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ể 32 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ẹ 33 Đ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 34 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 35 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 36 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 37 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 38 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) 39 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 40 Thanks for your attention PGS.TS Huỳnh Th Thanh Bìnhị Email: binhht@soict.hust.edu.vn Genetic Algorithm (GA) 2T ng quanổ  Bắt đầu được nghiên cứu từ những năm 70 bởi J. Holland, K. DeJong, D. Goldberg  Thường được áp dụng với:  Tối ưu hóa rời rạc  Tính chất:  Không quá nhanh  Sử dụng các heuristic để mang lại kết quả lại tạo tốt  Đặc biệt:  Lại tạo từ các cá thể cha mẹ tốt, có chọn lọc  Áp dụng các mô hình chọn lọc và lai tạo khác nhau 3T ng quanổ Các thuật toán GAs khác nhau ở việc sử dụng các toán tử:  Biểu diễn mã hóa  Đột biến  Lai ghép  Cơ chế chọn lọc sinh tồn, sinh sản 4Sơ đ thu t toán GAồ ậ Khởi tạo quần thể i t t Đánh giá độ thích nghi i t í i Sinh quần thể mới i t i Chọn lọc l Kiểm tra điều kiện dừng i tr i i Kết thúct t 5Các thành ph n c a GAầ ủ I. Phương pháp mã hóa lời giải II. Phương pháp lai tạo III. Phương pháp đột biến IV. Phương pháp chọn lọc cha mẹ V. Phương pháp đấu tranh sinh tồn 6Các ph ng pháp mã hóa l i gi iươ ờ ả Mã hóa nhị phân Mã hóa đa giá trị Mã hóa hoán vị Mã hóa cây (cạnh, Prufer, mã hóa đỉnh cha ) Rời rạc hóa 7Các ph ng pháp mã hóa l i gi iươ ờ ả - Mã hóa nhị phân Genotype space = {0,1}L Phenotype space Encoding (representation) Decoding (inverse representation) 011101001 010001001 10010010 10010001 8Các ph ng pháp mã hóa l i gi iươ ờ ả - Mã hóa đa giá trị  Thường sử dụng mã hóa giá trị phức tạp  Giá trị được mã hóa có thể là:  Nguyên hay thực  Rời rạc hay liên tục  Hữu hạn hay vô hạn 9Các ph ng pháp mã hóa l i gi iươ ờ ả - Mã hóa đa giá trị - Ví dụ 1.7 2.3 5.6 5.2 A C B A Black White Yellow Yellow a. Các gene trong nhiễm sắc thể nhận giá trị thực. b. Các gene trong nhiễm sắc thể nhận giá trị rời rạc, từ một tập vô hạn hoặc hữu hạn 10 Các ph ng pháp mã hóa l i gi iươ ờ ả - Mã hóa hoán vị NST là một hoán vị của một tập các gene Phù hợp với các bài toán liên quan đến tính hoán vị VD: TSP 1 3 6 7 8 2 5 4 9 11 Các ph ng pháp mã hóa l i gi iươ ờ ả - Mã hóa Cây Mã hóa cạnh: (1,2),(2,3), (1,4),(4,5) Mã hóa đỉnh cha Parent(1) = 1, Parent(2) = 1. 1 2 4 3 5 436 151 21 12 Các ph ng pháp mã hóa l i gi iươ ờ ả - Mã hóa Cây – tiếp Prufer:  Biểu diễn một cây bằng một vector số nguyên  Kích thước mã hóa bằng n-2, n là số đỉnh của đồ thị  Mã hóa:  Bước 1: Đánh nhãn các đỉnh trên cây từ 1 đến n  Bước 2: Tìm đỉnh là đỉnh có id nhỏ nhất và có bậc = 1 trong cây  Bước 3: Đỉnh là đỉnh kết nối với ( duy nhất 1 đỉnh tồn tại, do bậc của là 1) và thêm j vào trong mã hóa  Bước 4: Loại bỏ đỉnh và cạnh (, ) trên cây  Bước 5: Lặp lại bước 2 cho tới khi cây còn 2 đỉnh 13 Các ph ng pháp mã hóa l i gi iươ ờ ả - Mã hóa Cây – tiếp Prufer:  Giải mã  Bước 1: Tìm tập đỉnh S mà không xuất hiện trên mã hóa P  Bước 2: Tìm là đỉnh có id nhỏ nhất trong S, là phần tử trái nhất trong mã hóa  Bước 3: Loại bỏ đỉnh khỏi S và thêm cạnh (, ) vào cây  Bước 4: Lặp lại bước 1 cho tới khi S chỉ còn 2 đỉnh (giả sử a,b)  Bước 5: Thêm hai cạnh (a,b) vào cây 14 Các ph ng pháp mã hóa l i gi iươ ờ ả - Mã hóa Cây – tiếp Prufer: Ví dụ 15 Các ph ng pháp mã hóa l i gi iươ ờ ả - Mã hóa Cây – tiếp NetKeys:  Gán độ ưu tiên cho mỗi cạnh  thêm lần lượt các cạnh theo thứ tự độ ưu tiên sao cho không tạo thành chu trình  Kích thước vector mã hóa = số cạnh trong đồ thị  Đồ thị đẩy đủ => nxn  Mềm dẻo  Độ dư thừa mã hóa cao 16 Các phư ng pháp lai ghépơ Trên mã hóa nhị phân, đa giá trị  Lai ghép theo điểm cắt  Lai ghép đồng bộ Trên mã hóa hoán vị  Lai ghép thứ tự -OX  Lai ghép tương hợp bộ phận –PMX  Lai chu trình – CX Trên mã hóa số thực  Lai ghép chéo hóa nhị phân – SBX Trên mã hóa cây  Lai ghép trộn cạnh 17 Các phư ng pháp lai ghépơ Lai ghép theo đi m c tể ắ a. Một điểm cắt b. Hai điểm cắt c. N điểm cắt Thích h p v i mã hóa nh phânợ ớ ị 18 Các phư ng pháp lai ghépơ Lai ghép đ ng bồ ộ Thích h p v i mã hóa nh phânợ ớ ị Tại mỗi vị trí của cá thể con, lấy ngẫu nhiên 1 số thực u trong [0,1] u<0.5: lấy gene của cha u>= 0.5: lấy của mẹ 19 Các phư ng pháp lai ghépơ Lai ghép th tứ ự Chọn 2 điểm lai bất kì, khác nhau Con 1:  Sao chép phần giữa 2 điểm lai của cha 1 vào con 1  Các gen chưa được sao chép, tiến hành thêm vào con 1 bắt đầu từ điểm lai thứ 2, theo thứ tự xuất hiện ở cha 2 20 Các phư ng pháp lai ghépơ Lai ghép tư ng h p b ph nơ ợ ộ ậ Chọn 2 điểm lai bất kì Con thứ nhất:  Sao chép phần giữa 2 điểm lai của cha 1 sang con  Các vị trí còn trống, sao chép các gene tương ứng ở cha 2 mà chưa có mặt trong con  Các vị trí còn lại thực hiện tìm kiếm “đối sánh” 21 Các phư ng pháp lai ghépơ Lai ghép tư ng h p b ph nơ ợ ộ ậ 8 4 2 3 1 59 76 5 9 4 8 3 17 62 P1 P2 9 4 8 4 2 3 O1 O2 9 4 8 1 576 5 4 2 3 17 6 O1 O2 9 9 4 8 1 72 68 2 4 2 3 1 56 73 O1 O2 3 576 5 8 17 69 Bước 1: Bước 2: Bước 3: 9->4->2 8->3 22 Các phư ng pháp lai ghépơ Lai ghép chu trình Tìm các chu trình Copy lần lượt các chu trình vào con theo thứ tự nghịch đảo xen kẽ. 23 Các phư ng pháp lai ghépơ Lai ghép Chéo hóa nh phân - SBXị Với hai cá thể cha mẹ , SBX sinh ra hai cá thể con như sau:  Bước 1: Lấy ngẫu nhiên một số thực  Bước 2: Tính hệ số theo công thức: trong đó, là hệ số phân bố thường trong khoảng từ 2 đến 10. càng cao thì cá thể con sinh ra càng gần cha mẹ. 24 Các phư ng pháp lai ghépơ Lai ghép Chéo hóa nh phân - SBXị Bước 3: Các cá thể con và được sinh ra theo công thức Đặc điểm:  Hai con có phân phối gần với phân phối của cha mẹ giúp duy trì và kế thừa được những đặc tính tốt của hai cha mẹ. 25 Các phư ng pháp lai ghépơ Lai ghép tr n c nhộ ạ Trộn tập cạnh của hai cây tương ứng thu được tập cạnh E Thực hiện thuật toán PrimRST để sinh cây khung ngẫu nhiên trên E 1 2 4 3 5 1 3 5 1 4 3 5 22 4 1 4 3 5 2 PrimRST 26 Các ph ng pháp đ t bi nươ ộ ế Đảo bít : Biểu diễn nhị phân Đổi chỗ: Biểu diễn nhị phân, hoán vị Đổi giá trị: số nguyên, số thực Đảo đoạn: nhị phân, hoán vị, số nguyên Đột biến cây: biểu diễn cây Đột biến đa thức: số thực 27 Các phư ng pháp đ t bi nơ ộ ế Đ o bítả Áp dụng với mã hóa nhị phân 28 Các phư ng pháp đ t bi nơ ộ ế Đ o đ i chả ổ ỗ Áp dụng với mã hóa nhị phân/ hoán vị 29 Các phư ng pháp đ t bi nơ ộ ế Đ i giá trổ ị Tiến hành thêm bớt một lượng nhỏ vào giá trị của gene 30 Các phư ng pháp đ t bi nơ ộ ế Đ o đo nả ạ  Chọn 2 ví trí ngẫu nhiên  Đảo đoạn nằm giữa 2 ví trí đó 31 Các phư ng pháp đ t bi nơ ộ ế Đ t bi n câyộ ế  Cắt một cây con (subtree) trên cây ban đầu và gắn vào một nút khác trong cây 32 Các phư ng pháp đ t bi nơ ộ ế Đ t bi n đa th cộ ế ứ  Đối tượng: Biểu diễn số thực  Cá thể đột biến từ theo các bước sau:  Bước 1: Lấy ngẫu nhiên một giá trị u thuộc [0,1]  Bước 2: Tại mỗi vị trí trên p tính các giá trị và Cập nhật vị trí tương ứng trên cá thể con : 33 Các phư ng pháp đ t bi nơ ộ ế Đ t bi n đa th cộ ế ứ  Đặc điểm:  Phân phối của các cá thể con gần với cha mẹ  Toán tử parent-centric 34 Các ph ng pháp ch n l c cha mươ ọ ọ ẹ Chọc lọc ngẫu nhiên Chọn lọc theo vòng quay roulette Chọn lọc theo xếp hạng Chọn lọc theo thể thức giao đấu 35 Các phư ng pháp l a ch n cha mơ ự ọ ẹ L a ch n ng u nhiênự ọ ẫ  Các cá thể cha mẹ mang đi giao phối được chọn ngẫu nhiên hoàn toàn 36 Các phư ng pháp l a ch n cha mơ ự ọ ẹ L a ch n theo bánh xe rouleteự ọ  Tính tổng độ thích nghi của cả quần thể  Tính xác suất lựa chọn cá thể thứ là  Xác suất quỹ tích của cá thế thứ là  Lấy ngẫu nhiên một số thực r trong [0,1]  Cá thể thứ được lựa chọn nếu 37 Các phư ng pháp l a ch n cha mơ ự ọ ẹ L a ch n theo th h ngự ọ ứ ạ  Tiến hành xếp hạng các cá thể trong quần thể dựa trên độ thích nghi  Các xếp hạng có thể chỉ đơn giản là sắp xếp, cũng có thể sử dụng các hàm đặc biệt  Dựa trên hạng đã xếp chọn tỉ lệ tương ứng các cá thể theo ý muốn. Ví dụ:  Chọn 50% tốt nhất  Chọn 40% tốt nhất và 10% tồi nhất  Chia ra làm 3 khoảng: Tốt, trung bình, xấu. Mỗi khoảng lấy 50% tốt nhất (Elitsm) 38 Các phư ng pháp l a ch n cha mơ ự ọ ẹ L a ch n theo th th c giao đ uự ọ ể ứ ấ  Chọn ngẫu nhiên k cá thể cha mẹ  Ghép cặp cá thể được so sánh ngẫu nhiên với nhau và chọn ra hai cá thể tốt nhất làm cha mẹ A B C D A D Fitness(D) > Fitness(C) Fitness(A) > Fitness(B) 39 Phương pháp đấu tranh sinh tồn Nạp lại hoàn toàn Nạp lại ngẫu nhiên Giữ lại cá thể ưu tú Áp dụng các phương pháp của chọn lọc cha mẹ 40 Các phư ng pháp đ u tranh sinh t nơ ấ ồ N p l i hoàn toànạ ạ  Sinh ra số con bằng số lượng cha mẹ và tiến hành thay thế tất cả cha mẹ bằng con  Có thể gây ra việc mất đi cá thể cha mẹ tốt  Tính tăng trưởng ổn định của quần thể bị giảm  Nguy cơ bị cục bộ thấp hơn 41 Các phư ng pháp đ u tranh sinh t nơ ấ ồ N p l i ng u nhiênạ ạ ẫ  Sau khi lai tạo có k con  Chọn ngẫu nhiên k cha mẹ của quần thể để thay thế bằng k con mới  Có thể gây ra việc mất đi cá thể cha mẹ tốt 42 Các phư ng pháp đ u tranh sinh t nơ ấ ồ N p l i ng u nhiênạ ạ ẫ  Luôn luôn giữ lại cá thể ưu tú nhất của quần thể  Đảm bảo quần thể không bao giờ bị suy giảm chất lượng 43 Các phư ng pháp đ u tranh sinh t nơ ấ ồ Áp d ng phụ ư ng pháp c a l a ch n cha mơ ủ ự ọ ẹ Kết hợp các phương pháp chọn lọc để chọn ra cá thể của quần thể cũ bị đào thải Hoặc trộn các cá thể con vào quần thể và sử dụng các phương pháp chọn lọc để chọn các cá thể bị đào thải (con có thể cũng bị loại) Cũng có thể căn cứ vào tuổi của cá thể để đào thải 44 Giải thuật di truyền cơ bản Giải thuật di truyền cho không gian thực Giải thuật di truyền cho các biểu diễn có thứ tự và hoán vị Giải thuật di truyền trên cây và đồ thị Giải thuật di truyền cho các bài toán tối ưu có ràng buộc Cấu trúc quần thể Giải thuật di truyền song song 45 Thanks for your attention PGS.TS Huỳnh Th Thanh Bìnhị Email: binhht@soict.hust.edu.vn Genetic Programming 2N i dungộ  Tổng quan Genetic Programming (GP)  Các toán tử của GP  Ví dụ minh họa 3T ng quan v Genetic Programmingổ ề  Genetic Programming (Lập trình di truyền – GP) có thể coi là một thuật toán di truyền đặc biệt  Sơ đồ của GP giống sơ đồ của thuật toán GA  Điểm khác biệt giữa GA và GP  GA: Biểu diễn mỗi cá thể (nhiễm sắc thể) dưới dạng chuỗi các alen  GP: Mỗi cá thể là một hàm số hay chương trình máy tính, được biểu diễn dưới dạng cây  Mục tiêu của GP là tìm một chương trình tối ưu trong tập không gian các chương trình có thể, để thu được hiệu suất cao nhất  Ưng dụng: Tối ưu kiến trúc mạng Neural 4T ng quan v Genetic Programmingổ ề  Tại mỗi thế hệ, mỗi cá thể (hàm, chương trình) được tiến hóa để tìm ra hàm số ẩn tối ưu, có độ lỗi thấp nhất cho bài toán  Ví dụ: Tìm 1 hàm số f(x) sao cho đi qua tất cả các đỉnh A1, A2, A3, A4 5Các toán t c a GPử ủ  Biểu diễn cá thể  Lai ghép  Đột biến  Đánh giá độ thích nghi 6Bi u di n cá thể ễ ể  Mỗi cá thể trong GP biểu diễn một chương trình máy tính hay một hàm ẩn cần tìm  Để đảm bảo ngữ pháp của chương trình, ta cần xác định hai tập:  Tập kết thúc (terminal set) chứa các biến, hằng số, modun cơ bản có thể của chương trình  Tập hàm ( function set) chứa tất cả các hàm toán học cơ bản có thể dùng: +,-,*,/, exp, log, and , or, xor hoặc các cấu trúc quyết định if- then-else, 7Bi u di n cá thể ễ ể  Mỗi cá thể được biểu diễn dưới dạng một cấu trúc cây  Các nút lá của cây: Chọn từ tập kết thúc  Các nút trong của cây: Chọn từ tập hàm  Mỗi cá thể được khởi tạo như sau:  Nút gốc: được chọn ngẫu nhiên trong tập hàm  Nút không phải gốc: Chọn ngẫu nhiên trong tập hàm hoặc tập kết thúc  Chọn trong tập kết thúc: Nút trở thành nút lá  Chọn trong tập hàm: Nút là nút trong  Số lượng nhánh tại mỗi nút phụ thuộc vào hàm cơ bản tại nút đó 8Bi u di n cá th - Ví dể ễ ể ụ y := x * ln(a) + sin(z) / exp(-x) - 3.4 • Tập kết thúc: x, a, z, 3.4 • Tập hàm: *, +, - , /, ln, sin, exp 9Lai ghép  Các phương pháp chọn lọc cha mẹ sử dụng giống GA  Toán tử lai ghép trong GP: Chọn ngẫu nhiên một cây con trong mỗi cây cha mẹ và tráo đổi chúng cho nhau 10 Lai ghép – Ví dụ 11 Đ t bi nộ ế  Các phương pháp đột biến trong GP  Đột biến nút trong  Đột biến nút kết thúc  Đột biến đảo  Đột biến phát triển cây  Đột biến Gauss  Đột biến cắt tỉa cây 12 Đ t bi n - Đ t bi n nút trongộ ế ộ ế Thay thế hàm tại nút đó bằng một hàm khác trong tập hàm 13 Đ t bi n - Đ t bi n nút k t thúcộ ế ộ ế ế Thay thế biến, hằng tại nút đó bằng một biến, hằng khác trong tập kết thúc 14 Đ t bi n - Đ t bi n đ oộ ế ộ ế ả Chọn ngẫu nhiên một nút trong và đảo hai nút con của nó 15 Đ t bi n - Đ t bi n phát tri n cây ộ ế ộ ế ể Chọn ngẫu nhiên một nút và thay thế toàn bộ cây con của nút đó bằng một cây con ngẫu nhiên khác 16 Đ t bi n - Đ t bi n Gaussộ ế ộ ế Chọn ngẫu nhiên một nút lá chứa hằng số và thêm giá trị nhiễu Gauss vào nút đó 17 Đ t bi n - Đ t bi n c t t a câyộ ế ộ ế ắ ỉ Chọn ngẫu nhiên một nút và thay thế nút đó bởi một biến hay hằng số ngẫu nhiên trong tập kết thúc 18 Đánh giá đ thích nghiộ  Các cá thể được đánh giá trên cùng tập mẫu dữ liệu và giá trình hiệu suất trung bình thu được trên mẫu đó được sử dụng là giá trị độ thích nghi  Giả sử có một tập mẫu X và mỗi mẫu chứa ba giá trị đầu vào (a,x,z) và giá trị đích y. Độ thích nghi được tính như sau:  Tính giá trị đầu y^ ra thu được của chương trình mà cá thể biểu diễn với mỗi đầu vào (a,x,z)  Tính giá trị lỗi y^ so với y  Độ sai số trung bình MSE trên toàn bộ tập dữ liệu được xem như tiêu chí để đánh giá độ thích nghi 19 Ví d minh h aụ ọ  GP tìm Activation Function tối ưu cho Deeplearning [1]  Bước 1: Xác định tập kết thúc và tập hàm  Tập kết thúc: :  Tập hàm: x1 + x2, x1 − x2, x1 · x2, x1/(x2 + ϵ), max{x1, x2}, min{x1, x2} [1] Bingham, Garrett, William Macke, and Risto Miikkulainen. "Evolutionary optimization of deep learning activation functions." arXiv preprint arXiv:2002.07224 (2020) (GECCO 2020) 20 Ví d minh h aụ ọ  Đột biến chương trình  21 Ví d minh h aụ ọ  Lai ghép 22 Ví d minh h a- K t qu thu đụ ọ ế ả ư cợ 23 Thanks for your attention PGS.TS Huỳnh Th Thanh Bìnhị Email: binhht@soict.hust.edu.vn Evolutionary Programming 2N i dungộ  Tổng quan Evolutionary Programming (EP)  Các toán tử của EP  Ví dụ minh họa 3T ng quan v Evolutionary ổ ề Programming  Evolutionary Programming (Lập trình tiến hóa – EP) về cơ bản khác GA và GP:  Lấy cảm hứng từ việc mô phỏng các hành vi trong quá trình tiến hóa  GP tìm một tập hành vi tối ưu trong tập không gian hành vi quan sát được  GP không sử dụng toán tử lai ghép, chỉ sử dụng toán tử đột biến để sinh ra quần thể con mới 4Sơ đ thu t toán EPồ ậ  Bước 1: Khởi tạo một quần thể P(0) có N cá thể, t =0  Bước 2: Đánh giá độ thích của các cá thể trong P(t)  Bước 3: Đột biến mỗi các thể trong P(t) để sinh ra một quần thể con O(t)  Bước 4: Đánh giá các cá thể trong O(t)  Bước 5 : Chọn lọc P(t+1) từ P(t) và O(t)  Bước 6: t = t+1 và lặp lại bước 2,3,4,5 cho đến khi thỏa mã DK dừng 5Các toán t c a GPử ủ  Biểu diễn cá thể  Đột biến và chọn lọc sinh tồn <- Khác biệt  Đánh giá độ thích nghi 6Đ t bi n và ch n l c sinh t nộ ế ọ ọ ồ  Phép đột biến được thực hiện trên mỗi cá thể trong quần thể  Cá thể con sinh ra sẽ cạnh tranh với cá thể cha để sinh tồn trong thế hệ tiếp theo  Quá trình chọn lọc được diễn ra theo các cách sau:  Trên tất cả các cá thể: Cá thể cha và con có cơ hội được lựa chọn như nhau. Có thể dung các toán tử chọn lọc sinh tồn trong GA như tournament( giao đấu)..  Elitist: gọi S = N1 cá thể tốt nhất trong P(t)  P(t+1) = S U {N-N1 cá thể tốt nhất trong (P(t)\S) và O(t) }  Cull strategy: Loại bỏ các cá thể cha và con tồi nhất Vi dụ 1: EP tiến hóa máy trạng thái Ví dụ 2: EP tối ưu hàm số f(x) Ví dụ minh họa Ví dụ 1- EP tiến hóa máy trạng thái 9Ví d 1- EP ti n hóa máy tr ng thái h u h nụ ế ạ ữ ạ  Máy trạng thái hữu hạn (Finite-state machine FSM) là gì ?  Là một chuuwong trình máy tính biểu diễn các hành ddoogj cần thực thi  Các hành động phụ thuộc vào trạng thái hiện tại của máy và tham số đầu vào  FSM được định nghĩa như sau:  Với S: tập hữu hạn các trạng thái  I : Tập hữu hạn các kí hiệu đầu vào  O: Tập hữu hạn các kí hiệu đầu ra  : hàm trạng thái tiếp thoe  : hàm kí hiệu tiếp theo 10 Ví d 1- EP ti n hóa máy tr ng thái h u h nụ ế ạ ữ ạ 11 Ví d 1- EP ti n hóa máy tr ng thái h u h nụ ế ạ ữ ạ  Biểu diễn cá thể: Chuỗi nhị phân 6 bit  Bit 1:  1: trạng thái đang hoạt động,  0: không hoạt động  Bit 2: Biểu diễn kí hiệu đầu vào ( do chỉ có 0,1 nên dung 1 bít)  Bit 3,4: Biểu diễn trạng thái tiếp theo của máy ( do có 3 trạng thái)  Bit 5,6: Biểu diễn trạng kí hiệu đầu ra tiếp theo ( Do có 3 kí hiệu đầu ra có thể) 12 Ví d 1- EP ti n hóa máy tr ng thái h u h nụ ế ạ ữ ạ  Độ thích nghi:  Độ thích nghi của các cá thể được đo bằng khả năng dự đoán đúng kí hiệu đầu ra  Đột biến: Có thể áp dụng các phương pháp sau: 1. Thay đổi trạng thái ban đầu 2. Xóa trạng thái 3. Thêm một trạng thái 4. Thay đổi một dịch chuyển trạng thái 5. Thay đổi kí hiệu đầu ra với trạng thái hiện tại và đầu vào không đổi  Các toán tử có thể áp dụng như sau 13 Ví d 1- EP ti n hóa máy tr ng thái h u h nụ ế ạ ữ ạ  Các toán tử đột biến có thể áp dụng theo các cách như sau  Chọn ngâu nhiên đều 1 trong 5 phương pháp đầu tiên và áp dụng với xác xuất đột biến pm  Sinh một số theo phân phối Possion với trung bình . Lựa chọn ngẫu nhiên đều toán tử đột biến và áp dụng theo thứ tự Ví dụ 2- EP tối ưu hàm số f(x) 15 Ví d 2- EP t i ụ ố ưu hàm f(x)  Giả sử cần tối thiểu hàm số f(x) trong đoạn [0,2]  Mỗi cá thể được biểu diễn bằng một vector số thực chỉ chứa 1 phần tử  Mỗi cá thể được khởi tạo ngẫu nhiên đều trong đoạn [0,2]  Độ thích nghi: Cá teher nào cho giá trị f(x) càng nhỏ thì có độ thích nghi càng cao  Đột biến: Sử dụng đột biến Gauss: Cộng thêm một lượng giá trị nhỏ vào cá thể P(i) như sau: 16 Ví d 2- EP t i ụ ố ưu hàm f(x)  có thể được lựa chọn theo các cách như sau:  Không đổi, và giá trị nhỏ  Ban đầu lớn và giảm dần qua các thế hệ: Tăng khả năng khám phá của thuật toán ở giai đoạn ban đầu và khả năng khai thác ở các giai đoạn sau để thuật toán tội tụ  bằng độ lệch chuẩn của quần thể bố mẹ  Tự thích nghi. 17 Thanks for your attention PGS.TS Huỳnh Th Thanh Bìnhị Email: binhht@soict.hust.edu.vn Evolution Strategy 2N i dungộ  Tổng quan Evolution Strategy (ES)  Các loại ES  Ví dụ minh họa 3T ng quan v Evolution Strategyổ ề  Evolution Strategy (Chiến lược tiến hóa – ES)  Thuộc lớp các thuật toán tiến hóa EAs, dựa trên quần thể  Lấy cảm hứng từ chiến lược chọn lọc tự nhiên  Rất hiệu quả cho việc tối ưu số thực 4T ng quan v Evolution Strategyổ ề  Cho hộp đen với hàm mục tiêu cần tối ưu f(x)  Không thể tính được đạo hàm, không lồi.  f(x) là tất định  Gọi là phân phối của các lời giải tốt cho việc tối ưu f(x)  Nếu dạng phân phối là xác định (giả sử gauss) thì  là tham số mang thông tin về lời giải tốt nhất  được cập nhật qua mỗi thế hệ trong EAs 5T ng quan v Evolution Strategyổ ề  Bắt đầu với giá trị khởi tạo , Các thuật toán ES cập nhật theo 3 bước như sau:  Bước 1: Sinh một quần thể ban đầu P(t) , với N mẫu.  Bước 2: Đánh giá các cá thể trong P(t)  Bước 3: Chọn một tập con cá thể có độ thích nghi tốt nhất trong P(t) và cập nhật lại  Bước 4: t = t+1 và lặp lại bước 1 cho đến khi thỏa mã ĐK dừng 6Các lo i ESạ  Dựa theo chiến lược chọn lọc sinh tồn  (: Chọn cá thể tốt nhất từ cá thể con để sinh tồn ở thế hệ tiếp theo  ( : Chọn cá thể tốt nhất từ tập hợp của  cá thể con và  cá thể cha trước đó  Các thuật toán ES phổ biến:  Simple Gaussian Evolution Strategies  Covariance Matrix Adaptation Evolution Strategies (CMA-ES) 7Simple Gaussian Evolution Strategies  Là chiến lược tiến hóa đơn giản và cổ điển nhất của ES  Phân phối của các cá thể là phân phối Gauss n- chiều  lưu trữ thông tin của giá trị trung bình và độ lệch chuẩn  Các bước của thuật toán  Bước 1: Khởi tạo  Bước 2: Sinh ngẫu nhiên cá thể từ phân phối  Bước 3: Chọn ngẫu nhiên cá thể tốt nhất trong P(t+1) để cập nhật lại và  Bước 4: Lặp lại bước 2 và 3 8Simple Gaussian Evolution Strategies – Ví d ụ Bước 1: Khởi tạo 1- Initial Solution 9Simple Gaussian Evolution Strategies – Ví d ụ Bước 2: Sinh ra cá thể con 10 Simple Gaussian Evolution Strategies – Ví d ụ Bước 3: Chọn ra cá thể con tốt nhất 11 Simple Gaussian Evolution Strategies – Ví d ụ Bước 4: Cập nhật giá trị trung bình của phân phối và lặp lại bước 2 và 3 12 Simple Gaussian Evolution Strategies  càng cao: Mức độ khám phá của thuật toán càng lớn  Tuy nhiên giá trị khá tương đồng với  Khả năng hội tụ kém khi cao  Hình dạng của phân phối trong SGES là giống nhau ở mọi thởi điểm 13 Covariance Matrix Adaptation Evolution Strategies (CMA-ES)  Để khắc phụ những điểm yếu của SGES, CMA-ES xây dựng cơ chế thích nghi, điều chỉnh không gian khám phá sau mỗi thế hệ  Hình dạng của phân phối thay đổi và cập nhật sau mỗi thế hệ 14 Covariance Matrix Adaptation Evolution Strategies (CMA-ES) 15 Covariance Matrix Adaptation Evolution Strategies (CMA-ES)  CMA-ES thay đổi hình dạng của phân phối thông qua việc thích nghi hiệp phương sai C 16 Covariance Matrix Adaptation Evolution Strategies (CMA-ES)  Hiệp phương sai chỉ ra hướng mà quần thể nên tiến hóa Varian ce Covarian ce 17 Covariance Matrix Adaptation Evolution Strategies (CMA-ES) 18 Covariance Matrix Adaptation Evolution Strategies (CMA-ES) 19 Covariance Matrix Adaptation Evolution Strategies (CMA-ES) 20 Covariance Matrix Adaptation Evolution Strategies (CMA-ES) 21 Covariance Matrix Adaptation Evolution Strategies (CMA-ES)  Phân phối của các cá thể được xác định theo biểu thức  điều khiển mức độ scale của phân phối, gọi là step-size Step- size 22 Covariance Matrix Adaptation Evolution Strategies (CMA-ES)  Các bước của CMA-ES:  Bước 1: Khởi tạo: Ma trận hiệp phương sai C = I (ma trận đơn vị) m : vector nx1 chứa giá trị NST trung bình ban đầu của quần thể  : Step size ( vector nx1 chứa độ lệch chuẩn của các biển trong NST)  Bước 2: Sinh ra cá thể con thông qua cơ chế đột biến vector trung bình 23 Covariance Matrix Adaptation Evolution Strategies (CMA-ES)  Bước 3: Đánh giá độ thích nghi các cá thể con vừa sinh ra  Bước 4: Sắp xếp các cá thể con theo thứ tự giảm dần độ thích nghi:  Bước 5: Update giá trị trung bình m của quần thể Với là cá thể tốt nhất đầu tiên trong quần thể con sau khi sắp xếp  là vector hằng số ( ): Hệ số đóng góp của các cá thể vào vector trung bình 24 Covariance Matrix Adaptation Evolution Strategies (CMA-ES)  Bước 6: Cập nhật đường tiến hóa step –size Với : tốc độ phân hủy C: ma trận hiệp phương sai  = với : Vector ngẫu nhiên để đột biến trung bình sinh ra cá thể i  Bước 7: Cập nhật step-size Với ||X|| là chuẩn Euclid của vector X: 25 Covariance Matrix Adaptation Evolution Strategies (CMA-ES)  Bước 8: Cập nhật đường tiến hóa của ma trận hiệp phương sai C Với : tốc độ phân hủy  Bước 9: Cập nhật ma trận C * Với , 26 Covariance Matrix Adaptation Evolution Strategies (CMA-ES)  Điểm mạnh của CMA-ES  Hội tụ nhanh sau một số lượng thế hệ nhỏ  Giải quyết được các bài toán số chiều cao, không gian tìm kiếm rộng lớn, hoặc có hàm mục tiêu không tính được đạo hàm  Điểm yếu: Tốc độ tính toán, nhiều kiến thức toán học, lý thuyết 27 Thanks for your attention PGS.TS Huỳnh Th Thanh Bìnhị Email: binhht@soict.hust.edu.vn Differential Evolution (DE) 2T ng quan ổ Giải thuật tiến hóa sai phân (Differential Evolution - DE):  Thuật toán tối ưu ngẫu nhiên dựa trên quần thể  Được giới thiệu bởi Storn và Price vào năm 1996  Thuộc lớp giải thuật tiến hóa  Xử lý các bài toán tối ưu tham số thực, tìm cực trị hàm đa biến, phi tuyến, không khả vi  Các dạng bài toán mà DE giải quyết Hàm mục tiêu Mục tiêu bài toán tìm giá trị x* sao cho 3Sơ đ c a DEồ ủ Khởi tạo Đột biến Lai ghép Chọn lọc 4Mô hình thu t toánậ 5Kh i t oở ạ Giả sử cần tối ưu tham số Tham số thứ trong khoảng giá trị Kích thước quần thể Mỗi cá thể được biểu diễn bằng một vector D chiều Cá thể thứ i 6Đ t bi nộ ế Mỗi cá thể trong DE đều tham gia vào quá trình đột biến +lai ghép+ chọn lọc Quá trình đột biến được thực hiện trước khi lai ghép Với mỗi cá thể ta chọn ngẫu nhiên 3 cá thể khác nhau Toán tử đột biến được thực hiện bằng cách thêm sự chênh lệch giữa 2 cá thể vào cá thể thứ 3  F là hằng số để scale chênh lệnh,  là vector đột biến 7Lai ghép Cá thể con được sinh ra bằng cách lai ghép cá thể và vector đột biến Toán tử lai ghép sử dụng lai ghép nhị thức  Chọn ngẫu nhiên một số nguyên Sinh ra 1 con 8Ch n l cọ ọ Cá thể con sinh ra được so sánh với cá thể cha của chúng Nếu độ thích nghi của lớn hơn thì cá thể con sẽ thay thế cá thể cha trong thế hệ tiếp theo 9Các bi n th c a DEế ể ủ Khác nhau ở cách tính vector đột biến Adaptive ? DE/rand/1 : DE/rand/2: DE/best/1: DE/best/2: DE/target-to-best/1: 10 Hi u ch nh tham s trong DEệ ỉ ố Kích thước quần thể (N) F CR 11 Hi u ch nh tham s trong DE ệ ỉ ố Kích thư c qu n thớ ầ ể Các giải thuật tiến hóa mong muốn khám phá được nhiều không gian tìm kiếm trong các thế hệ đầu Ở các thế hệ cuối, quá trình tập trung khai thác những vùng có chứa lời giải hứa hẹn. Các giải thuật tiến hóa khác nhau ở mức độ khám phá và khai thác của chúng Khám phá => Kích thước quần thể lớn Khai thác => Kích thước quần thể nhỏ  Storn và Price chỉ ra nên chọn kích thước quần thể với D là số chiều không gian tìm kiếm 12 Hi u ch nh tham s trong DE ệ ỉ ố T l lai ghép (CR) và h s scale Fỷ ệ ệ ố  jDE  Điều kiển F và CR bởi 2 tham số  Cập nhật F và CR 13 Hi u ch nh tham s trong DE ệ ỉ ố T l lai ghép (CR) và h s scale Fỷ ệ ệ ố SaDE  F = lấy ngẫu nhiên theo phân phối chuẩn N(0.5,0.3)  . Giá trị trung bình ban đầu =0.5  Trong một số thế hệ (cụ thể 5), CR không đổi. Sau đó CR được sinh lại theo phân phối  Sau một số thế hệ (25 thế hệ) , được tính lại từ giá trị trung bình của các giá trị CR của các cá thể con thành công ở các thế hệ trước  Mỗi khi tính lại , các giá trị CR cũ bị xóa bỏ 14 Hi u ch nh tham s trong DE ệ ỉ ố T l lai ghép (CR) và h s scale Fỷ ệ ệ ố  JADE  ,  Cập nhật  là tập các giá trị CR của các cá thể con thành công  F , F  Cập nhật  15 Hi u ch nh tham s trong DE ệ ỉ ố T l lai ghép (CR) và h s scale Fỷ ệ ệ ố SHADE  Sử dụng Lehmer mean (Cec 14) để tính  Lưu trữ cảu mỗi thế hệ vào trong lịch sử  là mảng số thực có H phần tử  Cặp giá trị được chọn bằng cách lấy ngẫu nhiên một số k trong khoảng [1,H] 16 Hi u ch nh tham s trong DE ệ ỉ ố T l lai ghép (CR) và h s scale Fỷ ệ ệ ố SHADE  k = 2 17 Hi u ch nh tham s trong DE ệ ỉ ố T l lai ghép (CR) và h s scale Fỷ ệ ệ ố SHADE  Các phần tử trong ban đầu được khởi tạo đều là 0.5  được sử dụng bởi các cá thể con thành công được lưu trong  Sau mỗi thế hệ thứ i, tính lại và lưu trữ lại vị trí k = i mod H +1 trong mảng tương ứng 18 Hi u ch nh tham s trong DE ệ ỉ ố T l lai ghép (CR) và h s scale Fỷ ệ ệ ố SHADE 19 Thanks for your attention PGS.TS Huỳnh Th Thanh Bìnhị Email: binhht@soict.hust.edu.vn Ant Colony Optimization (ACO) 2Gi i thu t t i u hóa b y ki nả ậ ố ư ầ ế Xu t phát t ý t ng đàn ki n đi tìm ấ ừ ưở ế th c ănứ 3 Gi i thu t t i u hóa b y ki nả ậ ố ư ầ ế 4Gi i thu t t i u hóa b y ongả ậ ố ư ầ D a trên ph ng th c đàn ong đi tìm hoa ự ươ ứ l y m tấ ậ 5Gi i thu t t i u hóa b y đànả ậ ố ư ầ L ch s :ị ử Đ c đ xu t năm 1995 b i giáo s ượ ề ấ ở ư Russell Eberhart và nhà tâm lý h c James ọ Kenedy Russell Eberhart James Kenedy 6Gi i thu t t i u hóa b y đànả ậ ố ư ầ  L y ý t ng t vi c đàn chim tìm ki m ấ ưở ừ ệ ế th c ănứ Ví d đ n gi n minh h a:ụ ơ ả ọ 7T ng quanổ Ant Colony Optimization: Được giới thiệu bởi Marco Dorigo ở đầu những năm 1990s. Thuộc lớp các thuật toán tối ưu sử dụng Trí thông minh bầy đàn.  Lấy cảm hứng từ tập tính xã hội trong việc tìm kiếm thức ăn của đàn kiến trong tự nhiên. Thuật toán dựa trên quần thể. Đối tượng áp dụng: các bài toán tối ưu rời rạc (bài toán tìm đường đi). 8Quá trình tìm ki m th c ăn c a đàn ki nế ứ ủ ế  Ban đầu, các cá thể kiến đi theo các hướng ngẫu nhiên để tìm kiếm thức ăn.  Nếu tìm thấy thức ăn, các cá thể kiến mang thức ăn về tổ và để lại một chất hóa học (được gọi là pheromone) trên đường quay lại của nó.  Pheromone trên mỗi đường đi giảm dần theo thời gian  Đường có pheromone càng cao thì khả năng lựa chọn đi theo đường đi đó của các cá thể kiến khác càng lớn.  Càng nhiều cá thể kiến tìm thấy thức ăn trên một đường đi , thì pheromone của đường đi đó càng cao. 9Quá trình tìm ki m th c ăn c a đàn ki nế ứ ủ ế  Đàn kiến có thể tìm được đường đi ngắn nhất giữa tổ và thức ăn bằng cách nào?  Đầu tiên: Các cá thể kiến đi ngẫu nhiên theo mọi hướng  Nếu đường đi có khả năng dẫn tới nguồn thức ăn => Pheromone được rải trên đường quay trở lại  Đường đi càng ngắn, các cá thể kiến càng quay lại tổ nhanh => Nồng độ pheromone của đường đi đó được tăng cường sớm.  Đường đi càng dài=> Các cá thể kiến quay lại tổ lâu hơn => Nồng độ pheromone được cập nhật chậm và giảm dần do sự bay hơi  Sau một thời gian => Các cá thể kiến chỉ đi theo một đường đi duy nhất 10 Gi i thu t t i ả ậ ố ưu hóa đàn ki nế 11 Gi i thu t t i ả ậ ố ưu hóa đàn ki nế Quá trình xây d ng đ ng đi cho cá th ki nự ườ ể ế  Xét cá thể kiến . Quá trình xây dựng đường đi cho kiến như sau:  Giả sử kiến đang ở nút  Xác xuất đi từ đến nút là Với  là pheromone trên cạnh (i,j)  là mức độ thu hút của cạnh (i,j)  là tập các nút hàng xóm của mà chưa đi qua  và là tham số thuật toán 12 Gi i thu t t i ả ậ ố ưu hóa đàn ki nế Quá trình xây d ng đ ng đi cho cá th ki nự ườ ể ế  Nút , mà kiến di chuyển đến, sẽ được chọn theo bánh xe Roulete  Quá trình tiếp tục cho đến khi kiến có thể đến được (lời giải hợp lệ) hoặc không thể tiếp tục (lời giải không hợp lệ) 13 Gi i thu t t i ả ậ ố ưu hóa đàn ki nế Quá trình c p nh t pheromoneậ ậ  Pheromone trên mỗi cạnh (i,j) được cập nhật như sau:  Với là tốc độ bay hơi của các pheromone trước đó trên dường đi  là tổng các pheromone mới mà các cá thể kiến để lại trên đường đi của chúng: 14 Gi i thu t t i ả ậ ố ưu hóa đàn ki nế Quá trình c p nh t pheromoneậ ậ  Giá trị pheromone để lại bởi kiến trên đường đi của nó được tính như sau: Với   là chiều dài của hành trình  Q là hằng số kinh nghiệm 15 Gi i thu t t i ả ậ ố ưu hóa đàn ki nế Ý nghĩa c a các tham s , thu c tínhủ ố ộ  là mức độ thu hút hay kinh nghiệm của việc lựa chọn cạnh (i,j)  chỉ ra mức độ xuất hiện của cạnh (i,j) trên đường đi của các cá thể kiến  Nếu : Các cạnh trên đường đi được lựa chọn tham lam theo kinh nghiệm  Nếu : Ưu tiên sử dụng các cạnh có xu hướng được xuất hiện nhiều nhất trước đó 16 ACO for TSP problem  : Mong muốn đi theo các cạnh có chi phí nhỏ nhất Thêm thành phần “kiến tinh hoa”: Đánh trọng số cho pheromone của cạnh nằm trên đường đi tốt nhất Với Tham số thuật toán: 17 Gi i quy t m t bài toán b ng ACOả ế ộ ằ Phải chuyển bài toán về dạng đồ thị có trọng số G(V,E,w) Định nghĩa được pheromone trên cạnh Xác định biểu thức  Lựa chọn các toán tử cụ thể ( xây dựng đường đi cho kiến, cập nhật pheromone) cho bài toán cần giải quyết Hiệu chỉnh các tham số thuật toán 18 Th c nghi mự ệ Antsim v1.1 19 Thanks for your attention PGS.TS Huỳnh Th Thanh Bìnhị Email: binhht@soict.hust.edu.vn Particle Swarm Optimization (PSO) 2T ng quanổ Particle Swarm Optimization:  Được giới thiệu bởi Kennedy & Eberhart 1995  Lấy cảm hứng từ các hành vi xã hội của bầy chim và đàn cá  Thuộc lớp các thuật toán tối ưu sử dụng Trí thông minh bầy đàn  Thuật toán tối ưu dựa trên quần thể 3Các thành ph n c a thu t toán PSOầ ủ ậ Swarm (bầy) : Tập các cá thể (S) Particle (cá thể): ứng cử viên lời giải của bài toán  Vị trí,  Vận tốc ,  Vị trí tốt nhất đạt được của cá thể trong quá khứ : Cá thể tốt nhất trong bầy đàn: 4PSO Algorithm Các bước của thuật toán PSO: 1. Khởi tạo một bầy gồm N cá thể 2. Đánh giá độ thích nghi của mỗi cá thể trong bầy 3. Cập nhật vị trí tốt nhất (kinh nghiệm) của mỗi cá thể . 4. Cập nhật vị trí của cá thể tốt nhất của trong bầy đàn. 5. Cập nhật vận tốc và vị trí của mỗi cá thể theo và 6. Quay lại bước 2, và lặp cho đến khi thỏa mãn điều kiện dừng. 5PSO Algorithm (cont.) Biểu thức cập nhật vận tốc :  Hệ số ngẫu nhiên  : hệ số gia tốc Quán tínhT ành phần nhận thứcThành phần xã hội 6PSO Algorithm (cont.) Biểu thức cập nhật vận tốc :  Hệ số ngẫu nhiên  : hệ số gia tốc Cập nhật vị trí: Quán tínhThành phận nhận thứcThành phần xã hội 7PSO Algorithm – Tham số Hệ số gia tốc  Giá trị quá nhỏ làm hạn chế bước nhảy của các cá thể trong bầy đàn=> hội tụ chậm  Giá trị quá lớn : không hội tụ  Thông thường Giá trị vận tốc tối đa  Giá trị vận tốc tối đa của một cá thể ở chiều thứ d trong không gian: 8Ví d thu t toán PSO (B c 1 + 2 +3)ụ ậ ướ 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 0 0.5 1 1.5 2 2.5 3 • Khởi tạo 1 bầy đàn với 4 cá thể (t=0) • Đánh giá độ thích nghi, • Đánh dấu gbest gbest 9Ví d thu t toán PSO (B c 4)ụ ậ ướ 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 0 0.5 1 1.5 2 2.5 3 Cập nhât vận tốc của mỗi cá thể (t=1) gbest 10 Ví d thu t toán PSO (Bụ ậ ư c 4 ti p)ớ ế 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 0 0.5 1 1.5 2 2.5 3 Cập nhật vị trí của cá thể sau khi di chuyển (t=2) gbest 11 Ví d thu t toán PSO (Bụ ậ ư c 2+3)ớ 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 0 0.5 1 1.5 2 2.5 3 Đánh giá độ thích nghi và Cập nhật vị trí tốt nhất của mỗi cá thể và vị trí tốt nhất toàn cục (t=2) gbest 12 Ví d thu t toán PSO (Bụ ậ ư c 4)ớ 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 0 0.5 1 1.5 2 2.5 3 gbest Cập nhật vận tốc cho mỗi cá thể (t=2) Quán tính Nhận thức Xã hội Tổng hợp Quán tínhThành phần nhận thứcThành phần xã hội 13 Thu t toán PSO r i r cậ ờ ạ  Binary PSO:  Được giới thiệu bởi kennedy and Eberhart.  Mỗi cá thể (particle) là một biểu diễn nhị phân 0-1.  Biểu thức cập nhật vận tốc: Trạng thái trước đó Vận tốc Vị trí tốt nhất trước đó của cá thể đạt được Vị trí tốt nhất của cá thể tốt nhất trong cả bầy đàn 14 Binary PSO (cont.)  xác định một ngưỡng trong hàm xác xuất và nằm trong đoạn [0.0, 1.0].  Trạng thái của chiều thứ d trong biểu diễn của cá thể id ở thế hệ thứ t được xác định như sau: Với là một số ngẫu nhiên với phân phối đều Vid 1 15 Các bi n th PSOế ể  Hybrid PSO  Incorporate the capabilities of other evolutionary computation techniques.  Adaptive PSO  Adaptation of PSO parameters for a better performance.  PSO in complex environments  Multiobjective or constrained optimization problems or tracking dynamic systems.  Other variants  variations to the original formulation to improve its performance. 16 Hybrid PSO GA-PSO:  combines the advantages of swarm intelligence and a natural selection mechanism.  jump from one area to another by the selection mechanism  accelerating the convergence speed.  capability of “breeding”.  replacing agent positions with low fitness values, with those with high fitness, according to a selection rate 17 Hybrid PSO EPSO:  Evolutionary PSO  Incorporates a selection procedure  Self-adapting of parameters The particle movement is defined as: 18 Hybrid PSO : EPSO Mutation of weights and global best:  Learning parameters can be either fixed or dynamically changing as strategic parameters. Survival Selection:  Stochastic tournament. 19 Hybrid PSO : EPSO 20 Hybrid PSO : DEPSO  Hybrid of Differential Evolution and PSO.  A DE operator applied to the particle’s best position to eliminate the particles falling into local minima.  Alternation:  Original PSO algorithm at the odd iterations.  DE operator at the even iterations. 21 Hybrid PSO : DEPSO  DE mutation on particle’s best positions:  where k is a random integer value within [1,n] which ensures the mutation in at least one dimension. Trial point: For each dth dimention: 22 Hybrid PSO : DEPSO 23 Applications  Convenience of realization, properties of low constraint on the continuity of objective function and joint of search space, and ability of adapting to dynamic environment, make PSO be applied in more and more fields.  Some PSO applications:  Electronics and electromagnetic  Signal, Image and video processing  Neural networks  Communication networks  24 Thanks for your attention PGS.TS Huỳnh Th Thanh Bìnhị Email: binhht@soict.hust.edu.vn MULTI-OBJECTIVE OPTIMIZATION 2N i dungộ TỐI ƯU ĐA MỤC TIÊU  Bài toán đa mục tiêu  Hướng tiếp cận 1: Quy về đơn mục tiêu  Hướng tiếp cận 2: Pareto optimal A MULTI-OBJECTIVE EVOLUTIONARY ALGORITHM BASED ON DECOMPOSITION  Một số khái niệm  Cấu trúc thuật toán  Đánh giá TỐI ƯU ĐA MỤC TIÊU 4Bài toán đa m c tiêuụ Bài toán tối ưu đa mục tiêu (Multi-objective optimization problem):  Bài toán yêu cầu tối ưu 2 hay nhiều hàm mục tiêu cùng lúc.  Mô hình hóa:  (Giả sử các mục tiêu đều là cực tiểu hóa)  là tập nghiệm chấp nhận được của bài toán  hàm mục tiêu khác nhau: 5Bài toán đa m c tiêuụ  Ví dụ:  Xây dựng hệ thống mạng:  Tối đa phạm vi phủ sóng  Tối thiểu chi phí triển khai  Lập kế hoạch đầu tư:  Tối đa lợi nhuận  Tối thiểu rủi ro  Trong bài toán tối ưu đa mục tiêu, các hàm mục tiêu thường xung đột lẫn nhau, do đó hiếm có một lời giải tối ưu với tất cả mục tiêu cùng lúc. 6Bài toán đa m c tiêuụ Hướng tiếp cận giải bài toán đa mục tiêu:  Quy về đơn mục tiêu: Đưa ra công thức ánh xạ nhiều mục tiêu về 1 mục tiêu, rồi giải như bài toán đơn mục tiêu.  Pareto optimal: Dựa trên khái niệm tính trội và biên Pareto, tìm ra một số lời giải tốt với các hàm mục tiêu khác nhau, để một decision maker (ở đây có thể là con người) tự lựa chọn lời giải thích hợp nhất. 7H ng ti p c n 1: Quy v đ n m c tiêuướ ế ậ ề ơ ụ Một số phương pháp quy về đơn mục tiêu:  Vector trọng số  Tchebycheff  Penalty-based boundary intersection (PBI) (không giới thiệu) 8H ng ti p c n 1: Quy v đ n m c tiêuướ ế ậ ề ơ ụ Vector trọng số  Quy mục tiêu về 1 mục tiêu  Định nghĩa vector trọng số , sao cho  Trọng số 1 mục tiêu càng lớn thì mục tiêu đó càng được ưu tiên  Mục tiêu mới:  Ví dụ: Hai mục tiêu: 9H ng ti p c n 1: Quy v đ n m c tiêuướ ế ậ ề ơ ụ  Vector trọng số  Điểm tham chiếu  Biên tốt nhất tìm được theo từng mục tiêu  Giả sử các mục tiêu đều là minimize, với mọi lời giải tìm được:  Mục tiêu mới: Cực tiểu hóa: 10 H ng ti p c n 2: Pareto optimalướ ế ậ Tính trội (Pareto dominance):  Phương pháp so sánh 2 lời giải trong bài toán đa mục tiêu.  Lời giải được gọi là trội hơn nếu:  không tệ hơn ở mọi mục tiêu tương ứng  tốt hơn ở ít nhất 1 mục tiêu  Ví dụ trong bài toán cực tiểu hóa: 11 H ng ti p c n 2: Pareto optimalướ ế ậ Biên Pareto (Pareto front):  Một tập lời giải của bài toán đa mục tiêu trong đó không lời giải nào trội hơn (dominate) lời giải nào  Minh họa biên Pareto trong bài toán cực tiểu hóa 2 mục tiêu: 12 H ng ti p c n 2: Pareto optimalướ ế ậ  Các thuật toán áp dụng khái niệm Pareto optimal sẽ tập trung tìm kiếm biên Pareto tối ưu hoặc gần tối ưu cho bài toán  Một số thuật toán tiến hóa điển hình:  Non-dominated Sorting Genetic Algorithm II (NSGA- II)  Strength Pareto Evolutionary Algorithm 2 (SPEA2)  A Multi-objective Evolutionary Algorithm Based on Decomposition (MOEA/D) A MULTI-OBJECTIVE EVOLUTIONARY ALGORITHM BASED ON DECOMPOSITION (MOEA/D) 14 M t s khái ni mộ ố ệ  Phân hoạch  Hàng xóm  A multi-objective evolutionary algorithm based on decomposition 15 M t s khái ni mộ ố ệ Phân hoạch (Decomposition):  Nhắc lại: Phương pháp vector trọng số  Quy bài toán đa mục tiêu về đơn mục tiêu  Cho vector khác nhau: 1 bài toán đa mục tiêu  bài toán đơn mục tiêu khác nhau  lời giải tối ưu khác nhau  Phân hoạch: Phương pháp quy bài toán đa mục tiêu thành bài toán đơn mục tiêu khác nhau, kết hợp giải bài toán con này để được tập lời giải tạo thành biên Pareto của bài toán gốc 16 M t s khái ni mộ ố ệ Phân hoạch (Decomposition):  Ví dụ phân hoạch bài toán 2 mục tiêu: Bài toán g c:ố Bài toán con 1: Bài toán con 2: Bài toán con 9: 17 M t s khái ni mộ ố ệ Hàng xóm:  Trong phân hoạch ở trên, một số bài toán con có hàm mục tiêu (hay vector ) gần nhau hơn các bài toán khác  Ví dụ: Bài toán gốc có 2 mục tiêu, bài toán con đang xét có . Có 2 bài toán con khác: và . Dễ thấy bài toán gần với hơn.  Định nghĩa: “Hàng xóm” của 1 bài toán con là bài toán con gần với nó nhất trong bài toán con (bao gồm chính nó)  là hằng số cho trước ()  Khoảng cách 2 bài toán con là khoảng cách Euclid giữa 2 vector trọng số tương ứng  Ký hiệu: Hàng xóm của bài toán con : 18 M t s khái ni mộ ố ệ Hàng xóm:  Ví dụ xây dựng tập hàng xóm cho bài toán con 2:  : Mỗi bài toán con có 3 hàng xóm  3 bài toán con gần nhất là 1, 2, 3 (bao gồm chính nó)  Hàng xóm của 2: Bài toán con 1: Bài toán con 2: Bài toán con 3: Hàng xóm? 19 M t s khái ni mộ ố ệ A multi-objective evolutionary algorithm based on decomposition (MOEA/D)  Giải thuật tiến hóa đa mục tiêu dựa trên phân hoạch  Ý tưởng:  Phân hoạch bài toán đa mục tiêu thành bài toán đơn mục tiêu con  Tạo vector trọng số khác nhau  Duy trì 1 lời giải tốt nhất cho từng bài toán con  Tối ưu lời giải bài toán con bằng cách kết hợp lời giải của các “hàng xóm” (các bài toán gần nhau thì thường có lời giải tốt gần nhau)  Đánh giá lời giải:  1 trong các phương pháp quy về đơn mục tiêu đã nêu  Trong slide này dùng phương pháp Tchebycheff 20 C u trúc thu t toánấ ậ Thuật toán MOEA/D gồm 3 bước chính:  Bước 1: Khởi tạo  Bước 2: Tiến hóa theo thế hệ  Lặp lại nhiều lần tới khi thỏa mãn điều kiện dừng  Bước 3: Điều kiện dừng 21 C u trúc thu t toánấ ậ Đầu vào:  Các tham số:  vector trọng số  : Số hàng xóm của 1 bài toán con  Các đối tượng được duy trì và cập nhật qua từng thế hệ:  Quần thể: lời giải của bài toán con  Điểm tham chiếu : Dùng cho phương pháp đánh giá Tchebycheff  Không cần thiết nếu không dùng Tchebycheff  Quần thể ngoài EP: Biên Pareto của tất cả lời giải tìm được tính đến thế hệ hiện tại  Không cần thiết nếu trực tiếp dùng quần thể làm đầu ra 22 C u trúc thu t toánấ ậ Bước 1: Khởi tạo  Bước 1.1: Đặt quần thể ngoài  Bước 1.2: Xây dựng tập hàng xóm:  : Tập hàng xóm của bài toán thứ  - vector trọng số gần với vector nhất  Bước 1.3: Khởi tạo ngẫu nhiên quần thể:  Bước 1.4: Khởi tạo điểm tham chiếu : 23 C u trúc thu t toánấ ậ 𝑓=( 𝑓 1 , 𝑓 2,, 𝑓 𝑑) Bài toán 1 Bài toán 2 Bài toán N 𝒙𝟏 𝒙𝟐 𝒙𝟗 EP B c 1.1ướ 24 C u trúc thu t toánấ ậ Bước 2: Tiến hóa theo thế hệ (1) Với mỗi bài toán con :  Bước 2.1: Tạo lời giải mới  Chọn ngẫu nhiên 2 lời giải hàng xóm của ()  Lai ghép:  lời giải mới  Đột biến  lời giải mới  Bước 2.2: Sửa chữa/Cải thiện lời giải  Nếu không là lời giải hợp lệ, cần sửa chữa hoặc loại bỏ  Cải thiện nếu có thể (tùy bài toán) 25 C u trúc thu t toánấ ậ Bài toán 1 Bài toán 2 Bài toán N 𝒙𝟏 𝒙𝟐 𝒙𝟗 EP B c 2.1: T o l i gi i m iướ ạ ờ ả ớ Xét bài toán 2 Ch n ọCh n ọ Lai ghép + Đ t bi nộ ế 𝒚 B c 2.2: ướ S a ch a / ử ữ C i thi nả ệ 𝒚 ′ 26 C u trúc thu t toánấ ậ Bước 2: Tiến hóa theo thế hệ (2) Với mỗi bài toán con :  Bước 2.3: Cập nhật  Bước 2.4: Cập nhật các hàng xóm:  Với mọi  nếu (theo Tchebycheff)  thay bằng  Bước 2.5: Cập nhật EP:  Loại mọi lời giải bị trội bởi  Thêm vào EP nếu nó không bị trội bởi lời giải nào 27 C u trúc thu t toánấ ậ Bài toán 1 Bài toán 2 Bài toán N 𝒙𝟏 𝒙𝟐 𝒙𝟗 EP 𝒚 ′B c 2.4: ướSo sánh + Thay thế B c 2.5: ướ C p nh t EPậ ậ 28 C u trúc thu t toánấ ậ Bước 3: Điều kiện dừng  Điều kiện dừng: Tương tự các thuật toán GA thông thường  Số thế hệ tối đa  Số thế hệ tối đa mà EP không được cập nhật   Đầu ra: EP (Biên Pareto) 29 Đánh giá  Ưu điểm:  Nhanh, độ phức tạp tương đương GA thông thường  Biên Pareto đều  Khả năng duy trì cân bằng các hàm mục tiêu (ví dụ: tránh hội tụ sớm khi áp dụng tìm kiếm cục bộ quá mạnh lên 1 mục tiêu)  Nhược điểm:  Hiệu quả phụ thuộc lớn vào tham số người dùng tự đặt (đặc biệt là cách chia vector trọng số)  Không hiệu quả bằng các thuật toán như NSGA-II trong nhiều bài toán thông thường (khả năng tối ưu các mục tiêu tương đối đồng đều) 30 Thanks for your attention