Luận văn Một lớp các phương pháp giải bài toán tối ưu nhiều mục tiêu

c. Trên cơ sở này người ta cố gắng áp dụng thuật toán di truyền để giải quyết các bài toán loại này. Thuật toán di truyền đa mục tiêu xuất hiện trên cơ sở này. Cho đến nay có rất nhiều thuật toán di truyền để giải bài toán tối ưu đa mục tiêu dựa trên cơ sở thuật toán di truyền chẳng hạn: thuật toán MOGA, NSGA, NSGA II, SPEA, SPEA2, MOEA…Ứng với mỗi thuật toán đều có những thuật lợi và khó khăn nhất định. Từ việc phân tích này tôi đã lựa chọn trình bày 3 thuật toán là: MOGA, SPEA và NSGA. Thông qua các thuật toán này ta có thể xấp xỉ được biên Pareto tốt nhất từ các nghiệm khởi tạo ban đầu. 2.5.2. Thuật toán di truyền. Sau đây là các bước trong thuật toán di truyền: Bước 1:  Đặt: t = 0  Tạo ngẫu nhiên NP >1 cá thể để hình thành quần thể thứ 1 gọi là: Pt  Đánh giá độ thích nghi của nghiệm trong quần thể Pt Trang 41 Bước 2: Chéo hóa - Dùng toán tử Chéo hóa để tạo quần thể con Qt như sau:  Chọn 2 nghiệm x và y trong quần thể Pt dựa trên độ thích nghi.  Sử dụng toán tử chéo hóa tạo nghiệm con và bổ sung nghiệm con này vào tập Qt Bước 3: Đột biến - Dùng toán tử đột biến để tạo sự biến đổi ở mỗi nghiệm x  Qt với mức biến đổi cho trước. Bước 4: Gán độ thích nghi cho mỗi cá thể trong quần thể. x  Qt dựa trên giá trị hàm mục tiêu và khả năng không chấp nhận của nghiệm này. Bước 5:Lựa chọn NP cá thể từ Qt dựa trên độ thích nghi của chúng và đưa tất cả các nghiệm này vào tập Pt+1. Bước 6:  Dừng nếu điều kiện dừng thỏa mãn (ví dụ như: số lượng cá thể trong quần thể, số lượng thế hệ…) và đưa ra quần thể hiện tại.  Ngược lại : t  t+1 và quay lại thực hiện bước 2. Sơ đồ khối của thuật toán Di truyền Gán độ thích nghi Áp dụng toán tử chéo hoá Áp dụng toán tử đột biến Khởi tạo các cá thể trong quần thể Áp dụng toán tử Lựa chọn Điều kiện dừng thỏa mãn ? Kết thúc No Yes Trang 42 a. Quá trình lựa chọn: Sự lựa chọn là một toán tử lựa chọn 2 cá thể cha (được mã hóa bằng 2 chuỗi nhị phân) nhằm mục đích tạo một cá thể mới mà ta gọi là cá thể con. Trong toán tử lựa chọn, cá thể nào có độ thích nghi càng cao thì càng có nhiều cơ hội được chọn lựa với tư cách là cá thể cha. Có 2 cách thức để lựa chọn được cá thể cha: Một là: lựa chọn ngẫu nhiên (hay còn được gọi là vòng quay roulette) Hai là: lựa chọn dựa trên thứ hạn của mỗi cá thể. i. Lựa chọn ngẫu nhiên bằng cách sử dụng toán tử lựa chọn. Cho ௣ܰ là số lượng cá thể trong quần thể P – kích thước quần thể. Mỗi nghiệm/ cá thể ݔ௜ , ݅ = {1, … , ௉ܰ} được lựa chọn làm cá thể cha với khả năng là ௌܲ(ݔ௜) và được tính như sau: ௌܲ(ݔ௜) = ݂(ݔ௜) ∑ ݂൫ݔ௝൯ ேು ௝ୀଵ , ݒớ݅ ݅ = 1,2, … , ௣ܰ Trong đó f(.) là độ thích nghi của nghiệm x. ii. Lựa chọn dựa trên cơ sở thứ hạng của mỗi cá thể. Theo cách này thì các cá thể ݔ௜, ݅ = {1, … , ௉ܰ} trong quần thể được sắp xếp theo thứ tự giảm dần dựa trên độ thích nghi của chúng. Các cá thể sẽ được lựa chọn dựa trên thứ hạng của chúng. Ví dụ 15: Bảng sau đây minh họa số lượng cá thể được chọn làm cha dựa trên phần trăm số lượng cá thể trong quần thể: Thứ hạng 1 2 … NP - 1 NP % của NP 20% 10% … 0,1% 0% b. Quá trình Chéo hóa: Toán tử Chéo hóa dùng để tạo cá thể mới từ các cá thể cha đã được chọn. Toán tử Chéo hóa thường áp dụng trên cá thể cha – được mã hóa bằng các chuỗi nhị phân và chuỗi hoán vị. Ta xét một vài toán tử Chéo hóa sau: i. Chéo hóa tại một điểm: Chéo hóa tại một điểm là toán tử thường dùng nhất cho chuỗi nhị phân. Toán tử này thì áp dụng trên các chuỗi cha đã được chọn lựa như sau: Điểm Chéo hóa được lựa chọn ngẫu Trang 43 nhiên giữa hai chuỗi nằm trong hai cá thể cha nhằm tạo ra hai cá thể con mới bằng cách hoán đổi phần đầu tính từ điểm chéo hóa của mỗi chuỗi. Toán tử Chéo hóa áp dụng cho chuỗi số nguyên hoán vị. Toán tử chéo hóa áp dụng cho chuỗi nhị phân. ii. Chéo hóa thứ tự tại một điểm. Chọn một điểm chéo hóa tại một vị trí bất kỳ trong cá thể cha thứ I. Sau đó thay các gen tính từ điểm bắt đầu chéo hóa bằng các gen của cá thể cha thứ II. Từ đây ta được một cá thể con. Toán tử Chéo hóa áp dụng cho chuỗi hoán vị iii. Chéo hóa thứ tự tại hai điểm. Cá thể con được tạo thành như sau: chọn hai điểm chéo hóa bất kỳ trong cá thể cha thứ I. Sau đó thay thế các gen nằm giữa hai điểm chéo hóa này bằng các gen tương ứng của của cá thể cha thứ II. Trang 44 iv. Chéo hóa bằng cách cố định vị trí của các gen. Chọn và cố định vị trí một vài gen của cá thể cha thứ I. Sau đó thay thế các gen còn lại trong cá thể cha thứ I này bởi các gen tương ứng của cá thể cha thứ II. v. Ngoài ra còn có các toán tử Chéo hóa khác như: artially matched crossover in Goldberg [23],(5) Cycle crossover in Oliver et al.[89], Edge recombination crossover in Whitley et al.[118], Enhanced Edge recombination crossover in Starkweather et al.[101]. c. Quá trình tạo đột biến: Toán tử Đột biến nhằm tạo sự biến đổi ở mỗi cá thể mà sau khi áp dụng toán tử Chéo hóa trên cá thể cha để tạo cá thể mới này. Ta xét một số toán tử Đột biến sau: i. Tạo đột biến hai gen gần nhau Hai cá thể gần nhau thì được hoán vị cho nhau để tạo sự biến đổi hay đột biến. ii. Tạo đột biến hai gen cách xa nhau Trang 45 Hai cá thể cách xa nhau thì được hoán vị cho nhau để tạo sự biến đổi iii. Tạo đột biến ba gen cách xa nhau Ba cá thể cách xa nhau sẽ hoán vị cho nhau để tạo nên sự biến đổi – trong cách Đột biến này thì có nhiều cá thể mới tạo thành một cách ngẫu nhiên. iv. Tạo đột biến bằng cách dịch chuyển: Chọn ngẫu nhiên hai chromosome của cá thể, sau đó chèn 1 gen vào vị trí của gen còn lại để tạo sự biến đổi. v. Tạo đột biến bằng cách đảo ngược chuổi con. Chọn ngẫu nhiên một dãy con gồm các gen của một cá thể cha thông qua việc chọn hai gen tùy ý cách xa nhau. Sau đó đảo ngược dãy gồm các gen này để tạo sự đột biến. Nhận xét: Việc sử dụng 2 toán tử chéo hóa và đột biến trong thuật toán di truyền có thể sẽ giúp cho thuật toán di truyền trở nên hiệu quả hơn trong quá trình tính toán kết quả và thời gian thực thi. Nhưng việc áp dụng toán tử nào trong các toán tử chéo hóa và đột biến sẽ ảnh hưởng đến Trang 46 tính hiệu quả về mặt toán học của thuật toán di truyền. 2.6 Thuật toán Di truyền giải bài toán tối ưu nhiều mục tiêu 2.6.1. Thuật toán MOGA (Multi-Objective Genetic Algorithm) Sau đây là các bước chính yếu trong thuật Toán MOGA: Bước 1: Khởi tạo các cá thể trong quần thể ଴ܲ ngẫu nhiên ; thiết lập t = 0. Bước 2: Dừng nếu điều kiện dừng thỏa mãn và trả về tập ௧ܲ Bước 3: Đánh giá độ thích nghi của quần thể như sau: i. Gán cho mỗi nghiệm ݔ ∈ ௧ܲ một thứ hạng tương ứng là: r(x,t) = 1+nq(x,t) Trong đó: nq(x,t) – là số nghiệm trội của thế hệ t ii. Gán độ thích nghi cho mỗi nghiệm dựa trên thứ hạng của nghiệm như sau: ݂(ݔ, ݐ) = ܰ − ∑ ݊௞௥(௫,௧)ିଵ௞ୀଵ − 5. ൫݊௥(௫,௧) − 1൯ Trong đó nk – là số nghiệm với thứ hạng k. iii. Tính số lượng nghiệm nằm trong bán kính ߪ௦௛௔௥௘ có tâm tính từ nghiệm ݔ ∈ ௧ܲ . Ký hiệu là: nc(x,t) như sau: ݊ܿ(ݔ, ݐ) = ෍ ݉ܽݔ ൜ߪ௦௛௔௥௘ − ݀(ݔ, ݕ)ߪ௦௛௔௥௘ ; 0ൠ ௬∈௉; ௥(௬,௧)ୀ௥(௫,௧) Trong đó:  d(x,y) – là khoảng cách euclid giữa các cặp nghiệm trong không gian hàm mục tiêu giữa 0 và 1 ݀(ݔ, ݕ) = ඩ෍ቆ ௞݂(ݔ) − ௞݂(ݕ) ௞݂ ௠௔௫ − ௞݂ ௠௜௡ ቇ ଶ௄ ௞ୀଵ Với ௞݂௠௔௫ và ௞݂௠௜௡ là giá trị cựa đại và cực tiểu của ௞݂(. ) xác định được trong quá trình tìm kiếm.  ߪ௦௛௔௥௘ là bán kính có tâm tính từ nghiệm x được xác định như sau: Trang 47 ߪௌ௛௔௥௘ = 12ඩ෍Δ ௜݂ଶ௞ ௜ୀଵ Với Δ ௜݂ = ܯܽݔ{ | ௜݂(ݔ)− ௜݂(ݕ)| ∶ ݔ,ݕ ∈ ௧ܲ} Hình 11: Minh hoạ bán kính ࢙࣌ࢎࢇ࢘ࢋ iv. Tính độ thích nghi được chia sẻ của mỗi nghiệm ݔ ∈ ௧ܲ bằng cách sau: ݂ ᇱ(ݔ) = ݂(ݔ, ݐ) ݊ܿ(ݔ, ݐ) v. Chuẩn hóa độ thích nghi bằng cách sử dụng độ thích nghi chia sẻ: ' ( , )'' ' ( , ) ( , ) ( , ) ( ) ( , ) ( , ) t r x t y P r y t r x t f x t n f x f x t f x t     Bước 4: Dùng phương pháp lựa chọn ngẫu nhiên dựa trên ݂’’ để chọn cha cho nhóm phối giống.  Áp dụng toán tử Chéo hóa và đột biến vào nhóm phối giống cho đến khi quần thể con đạt được kích thước là N: Tức là | ܳ௧ | = ܰ.  Thiết lập ࡼ࢚ା૚ = ࡽ࢚ Trang 48 ' ( , )" ' ( , ). ( ) ( , ) ( , ) t r x t y P f x t n f x f x t f x t    Bước 5: Thiết lập t = t+1 và quay lại “bước 2”. 2.6.2 Nghiệm ưu việt (Elite) Định nghĩa 38: Cá thể ưu việt trong thuật toán di truyền đa mục tiêu có nghĩa là nghiệm tốt nhất được tìm thấy từ tổ hợp của quần thể cha và con trong quá trình xấp xỉ biên Pareto và nghiệm này luôn “sống sót” qua các thế hệ. Như vậy theo định nghĩa này thì tất cả các nghiệm không trội được tìm kiếm bởi thuật toán di truyền là các nghiệm ưu việt. Tuy nhiên, việc tìm kiếm nghiệm ưu việt trong thuật toán tối ưu đa mục tiêu thì không khó như trong một mục tiêu vì số lượng nghiệm ưu việt trong bài toán đa mục tiêu là rất lớn. Các thuật toán tối ưu nhiều mục tiêu bằng phương pháp di truyền ngày trước không đề cập đến nghiệm ưu việt nhưng hầu hết các thuật toán để giải bài toán tối ưu đa mục tiêu bằng thuật toán di truyền ngày nay lại sử dụng nghiệm ưu việt rất nhiều. Thuật toán để giải bài toán tối ưu đa mục tiêu bằng phương pháp di truyền thường dùng 2 Quần thể được khởi tạo đầu Miền chấp nhận được Quần thể nhận được cuối Z2 Z1 Hình12: Minh họa thuật toán MOGA Trang 49 cách tiếp cận chính để tìm nghiệm ưu việt: a. Duy trì số lượng nghiệm ưu việt trong quần thể b. Lưu trữ các nghiệm ưu việt trong tập “lưu trữ nghiệm ưu việt” sau đó bổ sung trở lại các nghiệm này vào trong quần thể. 2.6.3 Tập lưu trữ nghiệm ưu việt (External) Trong quá trình thực thi thuật toán di truyền thì khi xác định được cá thể ưu việt ta dùng một tập riêng để lưu trữ các cá thể này gọi là E. Khi dùng tập E để lưu trữ nghiệm ưu việt thì có một số vấn đề phải được giải quyết: Thứ 1: Các nghiệm ưu việt này sẽ tiếp tục được lưu trữ trong tập E. Hầu hết các thuật toán di truyền đa mục tiêu đều lưu trữ các nghiệm không trội trong quá trình tìm kiếm và tập E này sẽ cập nhật lại mỗi khi một nghiệm mới như sau: i. Nếu nghiệm mới này trội hơn nghiệm ưu việt chứa trong tập E thì nghiệm ưu việt này sẽ được thay thế bởi các nghiệm mới này (tức nghiệm ưu việt trong E sẽ bị xóa ) ii. Nếu các nghiệm ưu việt tồn tại trong E Không trội so với nghiệm mới này thì ta sẽ bổ sung nghiệm mới này vào tập E. Thứ 2: là kích thước của tập E (tức là số lượng các nghiệm ưu việt trong E). Khi một bài toán mà có nhiều nghiệm tối ưu Pareto thì kích thước của tập E sẽ rất lớn. Với những vấn đề trên có một số thuật toán đã được đề xuất nhằm tác động đến kích thước của tập E chẳng hạn như: SPEA - Thuật toán đều nhằm làm giải kích thước của tập E sao cho kích thước tập E này nằm trong giới hạn trên là N, khi số lượng nghiệm không trội trong vượt quá N. 2.6.3.1 Thuật toán SPEA : Bước 1: Khởi tạo bằng cách gán cho mỗi nghiệm ݔ ∈ ܧ một chỉ số thuộc một cụm nào đó gọi là ܿ௜ ∈ ܥ ݒớ݅ ݅ = {1, … ,ܯ} Bước 2: Tính khoảng cách giữa tất cả các cặp cụm ܿ௜ ݒà ௝ܿ như sau: ݀௖೔ ,௖ೕ = 1|ܿ௜|| ௝ܿ| ෍ ݀(ݔ, ݕ)௫∈ ௖೔,௬∈௖ೕ Trong đó: d(x,y) – là khoảng cách giữa 2 cá thể được xác định bằng công thức: Trang 50 - Trong không gian hàm mục tiêu: ݀(ݔ, ݕ) = ඩ෍ቆ ௞݂(ݔ) − ௞݂(ݕ) ௞݂ ௠௔௫ − ௞݂ ௠௜௡ ቇ ଶ௄ ௞ୀଵ - Trong không gian quyết định: ݀(ݔ, ݕ) = ඩ1 ܯ ෍(ݔ௜ − ݕ௜)ଶெ ௜ୀଵ Bước 3: Trộn các cặp ܿ௜ ݒà ௝ܿ nào có khoảng cách nhỏ nhất trong tất cả các cặp vào trong một “cụm”. Bước 4: Nếu | ܥ | ≤ ܰ thực hiện tiếp bước 5. Ngược lại quay lại bước 2. Bước 5: Đối với mỗi cụm xác định nghiệm nào mà có khoảng cách trung bình nhỏ nhất so với tất cả các nghiệm khác trong cùng một cụm – ta gọi là nghiệm trung tâm. Lưu trữ các nghiệm trung tâm đối với mỗi cụm và xóa các nghiệm từ tập E. Thứ 3: Cách thức lựa chọn các cá thể ưu việt từ tập E sau đó sao chép các cá thể này vào quần thể. Các nghiệm trong ௧ܲାଵ được lựa chọn từ tập ௧ܲ⋃ܧ௧, điều này được thực hiện bằng cách gán độ thích nghi cho mỗi nghiệm trong ௧ܲ⋃ܧ௧. Sau đó N nghiệm được lựa chọn cho thế hệ tiếp theo ௧ܲାଵ dựa trên độ thích nghi. Ứng với điều trình bày trên ta có thuật toán SPEA2 như sau: 2.6.3.2 Thuật toán SPEA2: Một số ký hiệu: NE :Số lượng lớn nhất mà tập E có thể chứa được các nghiệm không trội. NP :Số lượng cá thể trong quần thể/kích thước tập P. k :Tham số của mật độ tính toán: ݇ = ඥ ாܰ + ௉ܰ Bước 1: Tạo ngẫu nhiên các nghiệm đầu tiên trong P0 và thiết lập ܧ଴ = ∅ Bước 2: Tính toán độ thích nghi của mỗi nghiệm x trong ௧ܲ⋃ܧ௧ như sau: i. ݎ(ݔ, ݐ) = ∑ ݏ(ݕ, ݐ)௬ ∈ ௉೟ ⋃ா೟ ௬ ≺ ௫ Trong đó: s(y,t) là số nghiệm trong ܲ ௧⋃ܧ௧ mà trội bởi y. Trang 51 Hình 13: Minh họa tính toán độ thích nghi của các cá thể ii. Tính toán mật độ nghiệm như sau: ݉(ݔ, ݐ) = (ߪ௫௞ + 2)ିଵ . Trong đó: ߪ௫௞ là khoảng cách giữa nghiệm x đếm nghiệm lân cận gần nhất thứ k trong tập ܧ௧ାଵ. iii. Gán độ thích nghi như sau: ݂(ݔ, ݐ) = ݎ(ݔ, ݐ) +݉(ݔ, ݐ) Bước 3: Sao chép tất cả các nghiệm không trội trong ௧ܲ⋃ܧ௧ vào ܧ௧ାଵ . Điều này sẽ dẫn đến 2 trường hợp sau: Trường hợp 1: Nếu |ܧ௧ାଵ| > ாܰ thì giảm đi (|ܧ௧ାଵ|− ாܰ ) nghiệm bằng cách xóa bỏ các nghiệm nào có ߪ௞ nhỏ nhất thông qua kiểm tra các ߪ௟ ݒớ݅ ݈ = ݇ − 1, … ,1 còn lại Hình 14: Minh họa cách xóa bỏ các nghiệm nào có ࣌࢑ nhỏ nhất Trang 52 Trường hợp 2: Nếu |ܧ௧ାଵ| ≤ ாܰ thì sao chép ( ாܰ − |ܧ௧ାଵ|) nghiệm trội có độ thích nghi tương ứng từ ௧ܲ⋃ܧ௧ vào ܧ௧ାଵ Bước 4: Nếu điều kiện dừng thỏa mãn ( t > T, với T là số thế hệ lớn nhất cần đạt được) thì dừng và xuất ra các nghiệm không trội trong ܧ௧ାଵ Bước 5: Chọn các cá thể cha từ ܧ௧ାଵ bằng cách sử dụng toán tử lựa chọn vòng nhị phân. Bước 6: Sử dụng toán tử chéo hóa và đột biến để tạo ܰ௉ cá thể con từ các nghiệm cha. Sao chép các cá thể con vào ௧ܲାଵ , gán t = t+1 và quay lại bước 2. Sơ đồ khối của thuật toán SPEA2 Khởi tạo quần thể ban đầu: P0 Tập : ܧ଴ = ∅ và gán t = 0 Tính toán độ thích nghi của mỗi cá thể trong ௧ܲ và ܧ௧ Thực hiện quá trình Chọn lựa môi trường trên các phần tử và chép các phần tử này vào tập ܧ௧ାଵ Kiểm tra kích thước tập |ܧ௧ାଵ| Bổ sung phần tử trội nhất vào ܧ௧ାଵ Loại phần tử dựa vào tiêu chuẩn lân cận gần nhất Quá lớn Quá nhỏ Thực hiện toán tử: Lựa chọn; chéo hoá và đột biến trên tập ܧ௧ାଵ để tạo thành ௧ܲାଵ . Gán ݐ = ݐ + 1 T= số thế hệ lớn nhất ? Dừng, Xuất tập ࡱ࢚ା૚ là các nghiệm trên biên Pareto No Yes Trang 53 2.6.3.3 Thuật toán NSGA (Thuật toán di truyền sắp xếp các nghiệm không trội ) a. Biên chứa các nghiệm không trội và thứ hạn. Để gán độ thích nghi của các cá thể trong quần thể ta thường gán cho các cá thể các thứ hạng tương ứng bằng cách đưa các xếp cá thể phù hợp vào các biên chứa các nghiệm không trội. Hình 15: Minh họa biên chứa các nghiệm không trội và thứ hạng tương ứng Tính chất: i. Nghiệm hay cá thể nào nằm trên biên thứ nhất - R1 thì có độ thích nghi cao nhất và tất cả các nghiệm này được gán là hạng thứ 1. ii. Tất cả các nghiệm nằm trên cùng một biên chứa các nghiệm không trội thì có cùng độ thích nghi và chúng có cùng thứ hạng. b. Kí hiệu và thuật toán NSGA: Các kí hiệu : nu : Số nghiệm trội hơn nghiệm u Su : Tập nghiệm trội bởi nghiệm u P : Quần thể ban đầu. Fj : Biên chứa các nghiệm không trội thứ j, j = 1,…,R Q : Tập lưu trữ nghiệm không trội qua mỗi thế hệ Trang 54 c. Thuật toán NSGA: Bước 1: ∀ݑ ∈ ܲ Gán: nu=0 ; Su=0 Bước 2: ∀ݑ ∈ ܲ Nếu u trội v Su=Su  { v } Ngước lại nếu v trội hơn u Gán: nu = nu + 1 Bước 3: ∀ݑ  ܲ Nếu: nu= 0 Giữ u trong biên chứa các nghiệm không trội thứ nhất Gán: ݆ = 1 Bước 4: Trong khi ܨ݆ ≠ ∅ thì: khởi tạo ܳ = ∅ ∀ݑ  ܨ݆ V  Su nv= nv – 1 Nếu nv = 0 thì Q = Q  { v } Gán j = j + 1 Fj = Q Trang 55 2.6.3.4 Thuật toán NSGA-II: Các kí hiệu và thuật toán trong thuật toán NSGA – II cải tiến từ thuật toán NSGA Các biến: Pt - Quần thể cha. Qt - Quần thể con tạo thành từ các cá thể trong Pt Fj - Biên chứa các nghiệm không trội, với j=1,…,R N - Là số lượng cá thể trong quần thể Pt Thuật toán: Bước 1:  Tạo ngẫu nhiên quần thể cha ଴ܲ với | ଴ܲ | = ܰ  Gán ݐ = 0 Bước 2:  Áp dụng toán tử chéo hóa và đột biến đối với các cá thể trong quần thể ଴ܲ để tạo quần thể con ܳ ଴ với |ܳ଴| = ܰ Bước 3:  Nếu điều kiện dừng thỏa mãn thì dừng và xuất ra các cá thể trong quần thể ௧ܲ. Bước 4:  Đặt ܴ௧ = ௧ܲ ∪ ܳ௧ Bước 5:  Dùng thuật toán sắp xếp các nghiệm không trội - NSGA để nhận diện các biên chứa các nghiệm không trội ܨଵ,ܨଶ, … ,ܨ௞ trong ܴ௧ Bước 6:  Với mỗi ݅ = 1, … , ݇ ta thực hiện các bước sau: i. Tính khoảng cách “quy tụ” của các nghiệm trong ܨ௜ ii. Tạo quần thể ௧ܲାଵ như sau: Trường hợp 1: Nếu | ௧ܲାଵ | + |ܨ௜| ≤ ܰ thì thiết lập ௧ܲାଵ = ௧ܲ ∪ ܨ௜ Trường hợp 2: Nếu | ௧ܲାଵ | + |ܨ௜| > ܰ thì bổ sung ܰ − | ௧ܲାଵ| nghiệm mà có các cá thể khác quy tụ là ít nhất từ quần thể ܨ௜ vào ௧ܲାଵ. Trang 56 Bước 7:  Sử dụng toán tử lựa chọn vòng nhị phân dựa trên khoảng cách quy tụ quanh nghiệm x để lựa chọn các cá thể cha từ quần thể ௧ܲାଵ  Áp dụng toán tử chéo hóa và đột biến đối với quần thể ௧ܲାଵ để tạo quần thể con ܳ௧ାଵ với |ܳ௧ାଵ| = ܰ Bước 8:  Gán: t ← t + 1  Quay lại “bước 3”. Sơ đồ khối thể hiện thuật toán NSGA-II 2.6.4 Khoảng cách quy tụ - Crowding Distance Định nghĩa 40: Khoảng cách quy tụ của cá thể hay nghiệm x nằm trên một biên là chiều dài trung bình các cạnh của một hình hộp(cuboid) Trang 57 Hình 16: Minh họa khoảng cách quy tụ quanh nghiệm i Tính chất 39: i. Cho 2 nghiệm x và y, nghiệm x được thích hơn nghiệm y nếu ܴ௫ < ܴ௬ hoặc (ܴ௫ = ܴ௬ và ݀௫ > ݀௬ ) Trong đó: ܴ௫ ,ܴ௬ là các biên thứ x và thứ y và ݀௫ và ݀௬ là khoảng cách quy tụ của nghiệm x và y tương ứng. ii. Giữa 2 nghiệm không trội nếu nghiệm có thứ hạn thấp hơn thì nghiệm đó được ưu tiên lựa chọn hơn nghiệm còn lại. Hình 17: Minh họa các biên và thứ hạng iii. Khi 2 nghiệm không trội có cùng thứ hạng nghĩa 2 nghiệm này nằm trên cùng một biên, nghiệm nào nằm trong vùng có sự quy tụ thấp nhất thì sẽ được ưu tiên lựa chọn hơn nghiệm còn lại. Trang 58 Hình 18: Minh họa sự quy tụ của các nghiệm quanh một nghiệm. 2.6.5. Thuật toán tính khoảng cách quy tụ Cách tiếp cận nhằm dàn các nghiệm ra dọc theo biên Pareto một cách tốt nhất mà không phải dùng đến tham số - ߪshare Phương pháp khoảng cách quy tụ được thực hiện như sau: Bước 1:  Xếp thứ hạng các nghiệm và nhận dạng các biên chứa các nghiệm không trội Fj với j ∈ {1, … , R}  Ứng với mỗi biên ݆ ∈ {1, … ,ܴ} ta thực hiện “bước 2” và “bước 3” như sau: Bước 2:  Ứng với mỗi hàm mục tiêu k ta sắp xếp các nghiệm trong biên Fj theo thứ tự tăng dần như sau: ܫ௞ = ݏ݋ݎݐ( ௞݂(. ), >)  Cho ݈ = |ܨ௝| ; ࢞[࢏,࢑] là nghiệm thứ i trong ݅௞  Gán ݀௞൫ݔ[ଵ ,௞]൯ = 0 và ݀௞൫ݔ[௟ ,௞]൯ = ∞  Ứng với ݅ = 2, … ݈ − 1 ta tính ࢊ࢑൫࢞[࢏ ,࢑]൯ = ࢌ࢑൫࢞[࢏ା૚ ,௞]൯ − ࢌ࢑(࢞[࢏ି૚ ,࢑] ࢑ࢌ࢑࢓ࢇ࢞ − ࢌ࢑࢓࢏࢔ Bước 3: Tính tổng khoảng cách quy tụ tương ứng với mỗi hàm mục tiêu: Trang 59 ࢊ(࢞) =෍ࢊ࢑(࢞) ࢑ Hình 19: Minh họa khoảng cách quy tụ quanh nghiệm x 2.7 So sánh ưu điểm và khuyết điểm của các thuật toán di truyền đa mục tiêu. a) Một số đặc điểm của thuật toán MOGA; SPEA2 và NSGA – II: Thuật toán Gán độ thích nghi Cơ chế đa dạng Cá thể ưu việt E-Tập lưu trữ cá thể ưu việt Ưu điểm Khuyết điểm MOGA Dựa trên thứ hạng Pareto Không có Không Không Đây là thuật toán mở rộng của thuật toán di truyền một mục tiêu - Thuật toán luôn hội tụ về biên Pareto chậm vì có liện quan đến tham số ߪ௦௛௔௥௘ là bán kính tính từ nghiệm x đến nghiệm SPEA2 Dựa trên thế mạnh của các nghiệm trội. Tính toán mật độ dựa trên nghiệm lận cận gần nhất của nghiệm x Có Có - Cải thiện từ thuật toán SPEA2 - Các nghiệm cực biên được bảo toàn (nếu có) Mất nhiều thời gian cho việc tính toán mật độ nghiệm và độ thích nghi. NSGA - II Xếp thứ hạng thông qua việc sắp xếp Khoảng cách quy tụ của các cá thể quanh cá thể Có Không - Số lượng nghiệm đạt được cuối cùng sẽ không thay đổi nhiều khi - Khoảng cách quy tụ của các cá thể quanh cá thể x chỉ có hiệu lực trong không gian Trang 60 các nghiệm không trội. x ta thay đổi các thiết lập thông số đầu vào của thuật toán như : Số lượng cá thể trong quần thể (N), số lượng thế hệ cần đạt được. hàm mục tiêu. - Khi số lượng cá thể trong quần thể lớn, số lượng thế hệ cần đạt được lớn thì thời gian thực hiện thuật toán sẽ chậm. b) Ưu điểm của thuật toán SPEA2 so với thuật toán SPEA: Thuật toán SPEA2 là thuật toán cải tiến từ thuật toán SPEA. Thuật toán sẽ hội tụ và phân phối các nghiệm trên biên Pareto tốt hơn thuật toán SPEA trong hầu hết các bài toán tối ưu nhiều mục tiêu. c) Ưu điểm của thuật toán SPEA2 so với thuật toán NSGA – II: - Trong thuật toán NSGA – II tính ổn định của kết quả và độ mịn của biên Pareto xấp xỉ phụ thuộc vào điều kiện dừng – tức là số lượng thế hệ tối đa cần đạt đến. - Trong thuật toán SPEA2 và NSGA - II khi thiết lập các thông số đầu vào: số lượng cá thể trong mỗi thế hệ và số lượng thế hệ tối đa cần đạt đến càng tăng thì biên Pareto xấp xỉ càng mịn. - Khi số lượng hàm mục tiêu – tức là số chiều trong không gian hàm mục tiêu lớn thì thuật toán SPEA2 sẽ phân phối các nghiệm trên biên Pareto xấp xỉ tốt hơn NSGA – II. Theo những phân tích ưu và khuyết điểm của hải thuật toán, trong luận văn này tôi sẽ chọn thuật toán SPEA2 để giải một số bài toán cụ thể, qua đó chúng ta sẽ thấy được hiệu quả của thuật toán SPEA2 trong việc tìm biên Pareto xấp xỉ một cách tốt nhất. 2.8 Giải bài toán với thuật toán SPEA2: Xét bài toán tối ưu 2 mục tiêu sau: (P1) ܯin ଴ஸ௫ { ଵ݂(ݔ), ଶ݂(ݔ)} Trong đó: ଵ݂(ݔ) = √1 + ݔ ଶ݂(ݔ) = ݔଶ − 4ݔ + 5 Trang 61 Các thông số đầu vào của thuật toán SPEA2 trong Matlab lần lượt như sau: Trong đó các toán tử di truyền được sử dụng là:  Toán tử Chéo hóa: Simulated Binary Crossover – SBX (Chéo hoá tại một điểm).  Toán tử đột biến: Polynomial Mutation. Kết quả chạy thuật toán với số lượng thế hệ tối đa là 20 và số lượng cá thể trong mỗi thế hệ là 20. Kích thước quần thể Số lượng thế hệ Kích thước Tour eta_rec eta_mut v_rec_p v_mut_p 20 20 2 20 20 0,9 1 50 50 2 20 20 0,9 1 Trang 62 Kết quả chạy thuật toán với số lượng thế hệ tối đa là 50 và số lượng cá thể trong mỗi thế hệ là 50. 2.9 Tính toán số: Giải “ ví dụ 14” bài toán tối ưu hai hàm mục tiêu (P2) sau bằng thuật toán SPEA2: min ିସஸ௫,భ,௫మஸସ{ ଵ݂(ݔଵ,ݔଶ), ଶ݂(ݔଵ, ݔଶ)} Với: ଵ݂(ݔଵ,ݔଶ) = 3ݔଵଶ − 2ݔଵݔଶ + 4ݔଶ + ݔଶଶ ଶ݂(ݔଵ,ݔଶ) = ݔଵଶ − ݔଵ − ݔଵݔଶ + 0.5ݔଶଶ Thiết lập các thông số đầu vào cho thuật toán sau: Trong đó các toán tử di truyền là: Kích thước quần thể Số lượng thế hệ Kích thước Tour eta_rec eta_mut v_rec_p v_mut_p 50 50 2 20 20 0,9 1 100 100 2 20 20 0,9 1 200 200 2 20 20 0,9 1 Trang 63  Toán tử chéo hóa: Simulated Binary Crossover – SBX. Tương đương với toán tử chéo hóa tại một điểm.  Toán tử đột biến: Polynomial Mutation Kết quả thực hiện thuật toán với thông số đầu vào: số lượng cá thể trong mỗi thế hệ là: 50 và số lượng thế hệ tối đa là 50 Trang 64 Kết quả thực hiện thuật toán với thông số đầu vào: số lượng cá thể trong mỗi thế hệ là: 100 và số lượng thế hệ tối đa là 100 Trang 65 Kết quả thực hiện thuật toán với thông số đầu vào: số lượng cá thể trong mỗi thế hệ là: 200 và số lượng thế hệ tối đa là 200 Trang 66 CHƯƠNG III ỨNG DỤNG THUẬT TOÁN DI TRUYỀN TỐI ƯU NHIỀU MỤC TIÊU GIẢI BÀI TOÁN QUẢN LÝ DANH MỤC ĐẦU TƯ 3.1 Mô hình quản lý danh mục đầu tư 3.1.1. Giới thiệu danh mục đầu tư Harry Markowitz đã mô hình hóa quá trình lựa chọn danh mục đầu tư dưới dạng một bài toán quy hoạch phi tuyến (bài toán Markowitz). Mục tiêu của bài toán Markowitz là tìm các tỉ trọng của các chứng khoán trong danh mục đầu tư sao cho giảm tới mức tối thiểu phương sai (rủi ro) của danh mục mà đạt được một mức thu nhập đã định. Giải liên tiếp bài toán với các mức thu nhập mong đợi người ta xác định được một tập hợp các danh mục đầu tư có hiệu quả. Từ đây nhà đầu tư sẽ lựa chọn một danh mục nằm trong tập hợp các danh mục dựa trên quan điểm của mình về việc “đánh đổi” giữa thu nhập và rủi ro. Lý thuyết của Markowitz cũng chỉ ra rằng việc đa dạng hóa danh mục đầu tư sẽ giảm thiểu rủi ro phi hệ thống đối với các nhà đầu tư. Những rủi ro phi hệ thống như: sự mất giá của tiền đồng so với đồng Dollar hay sự bất ổn về mặt chính trị của một quốc gia nơi mà các công ty có cổ phiếu niêm yết trên sàn giao dịch hoặc tình hình dịch bệnh cũng ảnh hưởng đến một nhóm cổ phiếu của các công ty thuộc các hngành liên quan có cổ phiếu niêm yết trên sàn giao dịch,… Hiện nay có rất nhiều mô hình toán học liên quan đến việc lựa chọn danh mục đầu tư đã được xây dựng và phát triển dựa trên mô hình của Markorwitz. Hầu hết các mô hình này cố gắng xây dựng theo hướng thực tiễn tức là phải đạt tối đa lợi nhuận có thể được, cực tiểu hóa rủi ro của các loại chứng khoán trong danh mục đầu tư và cực tiểu hóa chi phí giao dịch,…nhưng phải phù hợp với sự biế