Kỹ thuật lựa chọn thích ứng cho giải thuật tiến hóa đa mục tiêu sử dụng điểm KNEE - Nguyễn Xuân Hùng

Kỹ thuật điện tử & Khoa học máy tính N.X.Hùng, N.Long, N.Đ.Định, L.Q.Việt,“Kỹ thuật lựa chọn... sử dụng điểm Knee.” 88 KỸ THUẬT LỰA CHỌN THÍCH ỨNG CHO GIẢI THUẬT TIẾN HÓA ĐA MỤC TIÊU SỬ DỤNG ĐIỂM KNEE NGUYỄN XUÂN HÙNG*, NGUYỄN LONG*, NGUYỄN ĐỨC ĐỊNH**, LÊ QUỐC VIỆT*** Tóm tắt: Trong thực tế các lĩnh vực của đời sống xã hội, bài toán tối ưu là một bài toán phổ biến được các nhà khoa học quan tâm giải quyết. Các bài toán tối ưu thực tế thường có nhiều hơn một mục tiêu và chúng xung đột với nhau. Lớp bài toán này được định nghĩa là lớp bài toán tối ưu đa mục tiêu. Có nhiều phương pháp để giải bài toán này, trong đó giải thuật tiến hóa được các nhà nghiên cứu áp dụng rộng rãi và hiệu quả. Giải thuật tiến hóa đa mục tiêu luôn hướng tới hai tính chất quan trọng đó là tính chất hội tụ và đa dạng của tập kết quả. Gần đây, các kỹ thuật chỉ dẫn được áp dụng để điều khiển quá trình tiến hóa đạt được sự cân bằng giữa khả năng thăm dò và khai thác, từ đó nâng cao chất lượng hội tụ và đa dạng cho tập giải pháp đạt được. Kỹ thuật điểm knee gần đây được giới thiệu mang lại hiệu quả cải thiện giải thuật tiến hóa đa mục tiêu. Tuy nhiên, việc chọn giải pháp điểm knee có khoảng cách tới siêu phẳng cực biên nhỏ hơn thay vì điểm không là knee với khoảng cách siêu phẳng cực biên lớn hơn lại cho kết quả kém hơn. Bài báo đề xuất kỹ thuật lựa chọn thích ứng cho giải thuật tối ưu đa mục tiêu sử dụng điểm knee nhằm nâng cao chất lượng hiệu quả của giải thuật. Từ khóa: Tối ưu đa mục tiêu, Độ đo đa mục tiêu, MOEA, GD, IGD, HV, KnEA, Lựa chọn thích ứng. 1. ĐẶT VẤN ĐỀ Trong lĩnh vực tối ưu đa mục tiêu, vấn đề sử dụng các kỹ thuật để chỉ dẫn giải thuật tiến hóa đa mục tiêu để cải thiện chất lượng thuật toán được nhiều nhà khoa học quan tâm nghiên cứu giải quyết. Trong [1] các tác giả đề xuất phương pháp mà các cá thể trong quần thể được xếp hạng sau đó chia thành các lớp, sử dụng giá trị khoảng cách mật độ (crowding distance) để chỉ dẫn giải thuật ưu tiên lựa chọn các giải pháp trong quá trình tiến hóa nhằm tăng tính chất đa dạng kết hợp tính chất hội tụ của giải pháp thông qua giá trị xếp hạng theo tính chất trội. Trong [2] quần thể được xếp hạng và sau đó được chia thành các lớp, sử dụng ưu tiên lựa chọn các thể ở các lớp không trội, tiếp theo là sử dụng tập các điểm tham chiếu định nghĩa trước để đảm bảo độ đa dạng của các giải pháp kết quả. Các tác giả trong [3] sử dụng hướng cải thiện (theo hướng hội tụ và hướng đa dạng) kết hợp phương pháp niching dựa vào hệ thống tia trong không gian mục tiêu để tăng cường chất lượng hội tụ và đa dạng. Kỹ thuật chính được sử dụng thông qua mật độ tia (ray based density) được định nghĩa trong không gian mục tiêu. Do các mục tiêu thường xung đột nhau nên thay vì một phương án tối ưu đơn, thay vào đó là tập các phương án. Các giải thuật đã đề cập ở trên có thể tìm được một tập các phương án tối ưu trong một lần chạy đơn. Tuy nhiên, các giải thuật đã được đề cập ở trên làm việc tốt với các bài toán tối ưu 2 hoặc 3 mục tiêu. Hiệu quả của các thuật toán trên giảm đi nghiêm trọng khi số mục tiêu tăng lên. Gần đây, giải thuật tiến hóa sử dụng điểm knee (KnEA) được các tác giả trong [4] giới thiệu; giải thuật KnEA này khắc phục được các hạn chế của các lớp giải thuật tương tự như trong [1],[3]. Giải thuật KnEA đã sử dụng ưu tiên đầu tiên là quan hệ trội, nghĩa là các giải pháp không trội có hạng tốt hơn sẽ được chọn; tiếp sau đó nếu cùng hạng thì sẽ ưu tiên chọn các giải pháp là điểm knee; nếu cả hai tiêu chuẩn (thứ nhất và thứ hai) không so sánh được thì sử dụng tiêu chuẩn thứ ba là tổng khoảng cách theo trọng số. Theo đánh giá của bài báo trong [4]: nhìn một cách tổng thể thì KnEA tương đương và tốt hơn so với các giải thuật tiến hóa nhiều mục tiêu tại thời điểm hiện tại như HypE, MOEA/D, GrEA, NSGA-III. Việc ưu tiên chọn giải pháp là điểm knee với mục tiêu để có giá trị HV [8] lớn, tuy nhiên, trong một số trường hợp thì lại chọn giải pháp có giá trị HV nhỏ. Nhìn vào hình 1 Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 36, 04- 2015 89 sẽ thấy rằng: nếu cần chọn 4 giải pháp cho thế hệ tiếp theo thì rõ ràng chọn giải pháp điểm Knee F sẽ cho kết quả kém hơn so với chọn giải pháp điểm không Knee B. Hình 1.Mô tả cách chọn điểm Knee. Trong bài báo này, tác giả tập trung phân tích, đánh giá hiệu quả giải thuật tiến hóa đa mục tiêu sử dụng điểm knee, đưa ra giả thiết nguyên nhân mất cân bằng giữa khả năng thăm dò và khai thác của quá trình tiến hóa. Từ giả thiết đó, bài báo đề xuất phương pháp lựa chọn thích ứng mới áp dụng cho giải thuật thuật toán tiến hóa đa mục tiêu sử dụng điểm Knee nhằm duy trì tính cân bằng giữa khả năng thăm dò và khai thác của giải thuật, từ đó nâng cao chất lượng và hiệu quả của giải thuật. Nội dung bài báo sẽ được trình bày như sau: Mục 2 sẽ là những kiến thức tổng quan, trong đó tóm tắt về bài toán tối ưu đa mục tiêu, quan hệ trội, tối ưu Pareto, độ đo; giải thuật sử dụng kỹ thuật điểm knee gốc cũng được trình bày tóm tắt trong mục này; tiếp đến là Mục 3 đưa ra kỹ thuật lựa chọn thích ứng dùng cho giải thuật tiến hóa đa mục tiêu sử dụng điểm Knee cùng với các kết quả thử nghiệm và cuối cùng là kết luận. 2. TỔNG QUAN 2.1. Bài toán tối ưu đa mục tiêu Bài toán được định nghĩa như sau [5]: min{f1(x), f2(x),...,fk(x)} với xS, trong đó, k(2) là số mục tiêu, fi : R n  R là các hàm mục tiêu. Véc tơ các hàm mục tiêu được kí hiệu là f(x)=( f1(x), f2(x),...,fk(x)) T. Véc tơ (biến) quyết định x=(x1,x2,...xn) T thuộc miền chấp nhận được, véc tơ này là không gian con của không gian biến Rn. Thuật ngữ min nghĩa là tất cả các biến được cực tiểu hóa đồng thời. Nếu không có sự xung đột giữa các hàm mục tiêu, thì một giải pháp có thể tìm được nơi mà mọi hàm mục tiêu là tối ưu. Trong trường hợp này, không cần đến một phương pháp đặc biệt. Để tránh trường hợp tầm thường này, giả sử rằng không tồn tại một giải pháp tối ưu với tất cả các mục tiêu. Điều này có nghĩa là các hàm mục tiêu ít nhất xung đột nhau một phần. Miền khả thi được kí hiệu là Z (=f(S)) còn được gọi là miền mục tiêu chấp nhận được là tập con của không gian mục tiêu Rk. Các phần tử thuộc Z được gọi là véc tơ (hàm) mục tiêu được kí hiệu là f(x) hay z=(z1, z2, ..., zk) T trong đó zi=fi(x) với i=1, 2, .., k là các giá trị hàm mục tiêu. Để đơn giản, giả sử tất cả các hàm mục tiêu là min. Nếu một hàm mục tiêu fi là max, nó tương đương với min của fi . 2.2. Quan hệ trội Trong thực tế, các phương pháp xấp xỉ thường sử dụng định nghĩa trội để so sánh các giải pháp trong nhiều mục tiêu [8]: Kỹ thuật điện tử & Khoa học máy tính N.X.Hùng, N.Long, N.Đ.Định, L.Q.Việt,“Kỹ thuật lựa chọn... sử dụng điểm Knee.” 90 Định nghĩa : Một giải pháp x1 được gọi là trội hơn x2 nếu x1 không xấu hơn x2 ở tất cả k mục tiêu và tốt hơn x2 ở ít nhất một mục tiêu. Nếu x1 không trội hơn x2 và x2 không trội hơn x1 thì x1 và x2 không trội hơn nhau. 2.3. Tối ưu Pareto Một nghiệm x* của bài toán được gọi là nghiệm lý tưởng nếu: fi(x*) fi(x) xX : i= {1, k} Nói một cách khác một nghiệm lý tưởng là một nghiệm mà nó phải thỏa mãn tất cả các hàm mục tiêu cần tối ưu ứng với miền chấp nhận được là X. Thực tế thì những nghiệm như vậy rất ít khi tồn tại nên người ta đưa ra một số khái niệm khác về tối ưu có vẻ “mềm dẻo” hơn đó là nghiệm tối ưu Pareto. Hình 2. Minh họa điểm tối ưu Pareto. Một điểm nghiệm x∗ được gọi là một nghiệm tối ưu Pareto nếu không tồn tại một nghiệm x ≠ x*X sao cho x trội hơn x*. Nghĩa là: f(x) <f(x*). Điểm tối ưu Pareto (điểm đen trong không gian mục tiêu) được minh họa trong Hình 2. 2.4. Độ đo Để đánh giá chất lượng của thuật toán, có 2 tiêu chí mỗi thuật toán cần đạt được đó là (1) độ hội tụ (gần của tập phương án tìm được tới tập phương án Pareto) và (2) độ đa dạng (sự phân bố của tập phương án tìm được dọc theo tập phương án Pareto). Hai tiêu chí này là độc lập nhau, có nhiều độ đo khác nhau có thể giải quyết một hoặc cả hai tiêu chí. Độ đo GD [9] được định nghĩa là khoảng cách trung bình từ các điểm trong tập giải pháp tìm được tới tập Pareto: 𝐺𝐷 = 𝑑𝑖 𝑛 𝑖=1 𝑛 ; trong đó, di là khoảng cách Ơ-cơ-lit từ điểm giải pháp i tới điểm gần nhất trong tập Pareto và n là kích thước của tập giải pháp. Ngoài ra, độ đo IGD [9] được định nghĩa là khoảng cách trung bình từ các điểm trong tập Pareto tới điểm gần nhất trong tập phương án tìm được và tính theo công thức: 𝐼𝐺𝐷 = 𝑑𝑖 𝑁 𝑖=1 𝑁 trong đó, 𝑑𝑖 là khoảng cách Ơ-cơ-lit từ điểm i trong tập Pareto tới điểm gần nhất trong tập phương án tìm được và 𝑁 là tổng số điểm trong tập Pareto. Trong thực tế khó hoặc không có được tập tối ưu Pareto. [8] đưa ra độ đo HVsiêu khối trong không gian mục tiêu xác định bởi tập phương án và điểm tham chiếu và được tính theo công thức 𝐻𝑉 = 𝑉𝑜𝑙𝑢𝑚𝑒 𝑣𝑖 𝑁 𝑖=1 ; trong đó, vi: khối xác định bởi giải pháp i và điểm tham chiếu. Điểm tham chiếu được xác định là điểm biên của không gian mục tiêu nếu có biên của không gian mục tiêu, ngược lại được xác định là điểm có các tọa độ xấu nhất trên mỗi mục tiêu. 2.5 Giải thuật tiến hóa đa mục tiêu sử dụng điểm Knee Ý tưởng đưa ra là các điểm knee được ưu tiên chọn trước tiên trong những giải pháp không trội nếu không có một ưu tiên rõ ràng từ người dùng. Điều này sẽ thiên về một siêu thể tích lớn do đó nâng cao hiệu quả hội tụ trong tối ưu đa mục tiêu. Hơn nữa, nhiều nhất là một giải pháp được xác định là điểm knee trong lân cận của mỗi giải pháp trong lớp không trội, không cần cơ chế duy trì đa dạng nên tăng đáng kể tốc độ tính toán. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 36, 04- 2015 91 Hình 3. Mô tả điểm Knee. Trong [10] điểm knee được định nghĩa: Cho tập tối ưu Pareto, đường cực biên được xây dựng dựa trên hai cực điểm A và B. Với mọi đểm biên z (trên đường cực biên giới), điểm tối ưu Pareto Pz được xác định trên pháp tuyến của đường ranh giới đi qua z. Điểm tối ưu Pareto Pz* với khoảng cách lớn nhất từ điểm biên tương ứng z* dọc theo pháp tuyến được gọi là điểm Knee. Điểm knee được mô tả trong hình 3. 2.5.1. Giải thuật Kỹ thuật điểm knee thực hiện trong mỗi bước lặp: chia quần thể thành các lớp không trội, trong các lớp không trội này thực hiện xác định điểm knee và xác định khoảng cách theo trọng số; thực hiện chọn, lai ghép, đột biến dựa trên lần lượt các tiêu chí: lớp không trội, điểm knee, giá trị khoảng cách theo trọng số. Các bước chính của giải thuật [4]: Đầu vào: Kích thước quần thể N, tập điểm knee K, tỉ lệ điểm knee trong quần thể T Bước 1: Khởi tạo các tham số thích nghi r=1, t=0; khởi tạo quẩn thể cha P(kích thước N) Bước 2: Sinh quần thể con: Phép chọn(sử dụng tiêu chuẩn quan hệ trội, tiêu chuẩn điểm knee và tiêu chuẩn khoảng cách trọng số); Phép lai ghép; Tính các hàm mục tiêu. Bước 3: Gộp quần thể cha và quần thể con vừa sinh ra Bước 4: Trong quần thể vừa gộp thực hiện sắp xếp không trội Bước 5: Với từng lớp không trội thực hiện xác định điểm knee. Bước 6: Chọn N cá thể cho thế hệ tiếp theo. 2.5.2. Thủ tục xác định điểm knee với mỗi lớp không trội Thực hiện tìm các điểm cực biên theo mỗi chiều mục tiêu (điểm cực biên được xác định là điểm có tọa độ lớn nhất). Phương trình siêu phẳng được xác định từ các điểm cực biên tìm được. Tiếp theo, tính khoảng cách từ mỗi điểm (giải pháp) tới siêu phẳng. Sắp xếp các điểm theo thứ tự giảm dần của khoảng cách tìm được. Cuối cùng duyệt lần lượt: cho điểm được duyệt là điểm knee và loại những điểm trong vùng lân cận của điểm knee này; thực hiện duyệt tương tự duyệt với các điểm còn lại cho đến hết. 2.5.3. Thủ tục xác định vùng lân cận của một điểm Khi duyệt mỗi điểm cần xác định lân cận của chúng. Trong đó lân cận được là siêu khối theo từng thế hệ Rjg (chiều thứ j, thế hệ g): 𝑅𝑔 𝑗 = 𝑓𝑚𝑎𝑥𝑔 𝑗 − 𝑓𝑚𝑖𝑛𝑔 𝑗 . 𝑟𝑔 Với 𝑓𝑚𝑎𝑥𝑔 𝑗 ,𝑓𝑚𝑖𝑛𝑔 𝑗 : giá trị lớn nhất, nhỏ nhất theo chiều j tại thế hệ g. rg tính theo công thức 𝑟𝑔 = 𝑟𝑔−1 ∗ 𝑒 − 1− 𝑡𝑔−1 𝑇 𝑀 là tỉ số kích thước của lân cận với độ rộng trục mục tiêu thứ j trong lớp không trội Fi tại thế hệ thứ g; tg: tham số t tại thế hệ g; M: tổng số mục tiêu của bài toán; T: tham số ngưỡng lân cận, T (0;1) 2.5.4. Thủ tục chọn các cá thể cho thế hệ tiếp Đầu vào: Quần thể được sắp xếp thành các lớp không trội F; Tập các điểm knee K; Kích thước quần thể N Kỹ thuật điện tử & Khoa học máy tính N.X.Hùng, N.Long, N.Đ.Định, L.Q.Việt,“Kỹ thuật lựa chọn... sử dụng điểm Knee.” 92 Bước 1: Lần lượt chọn các cá thể trong các lớp có hạng trong các tập sắp xếp không trội vào tập Q trong khi |Q|<N. Bước 2: Chọn tiếp các cá thể trong lớp tiếp theo với thứ tự ưu tiên: điểm knee, khoảng cách đến siêu phẳng (giảm dần) đến khi |Q|=N 2.5.5. Đánh giá hiệu quả của giải thuật tiến hóa đa mục tiêu sử dụng điểm knee Thông qua kết quả thí nghiệm của bài báo công bố trong [4], giải thuật đề xuất xác định điểm knee trong tập giải pháp không trội đạt được kết quả tương đối khả quan với các giải thuật tiến hóa đa mục tiêu phổ biến: MOEA/D, NSGA-III, HypE, GrEA thông qua kết quả của độ đo IGD và HV. Kỹ thuật sử dụng điểm knee giúp giải thuật tiến hóa đa mục tiêu tăng cường chất lượng hội tụ rất tốt. Tuy nhiên, qua phân tích tác giả nhận thấy rằng giải thuật sử dụng kỹ thuật lựa chọn ưu tiên theo điểm knee có ràng buộc chặt, đây có thể là nguyên nhân giải thuật mất cân bằng giữa khả năng thăm dò và khai thác của quá trình tiến hóa. Từ đó làm cho giải pháp đạt được có thể đạt chất lượng hội tụ tốt nhưng có thể làm giảm tính chất đa dạng thông qua việc phân tích cụ thể như sau: Hình 1 biểu diễn các điểm (kèm theo tọa độ): A(1, 16), B(6, 8), C(7, 7), D(9, 6.5), E(12.5, 6), F(13, 5), G(14.5, 4) và điểm H(16, 1)  tập các giải pháp (điểm) của bài toán tối ưu 2 mục tiêu (cực tiểu 2 mục tiêu). Các giải pháp này thuộc một lớp không trội. Trong đó, điểm tham chiếu có tọa độ là (20, 20) và giả sử đường thẳng đi qua 2 điểm cực biên có phương trình x+y19=0. Yêu cầu đặt ra là chọn 4 điểm. Thực hiện theo giải thuật tiến hóa đa mục tiêu sử dụng điểm knee gốc thì 3 điểm knee A, C, H được chọn trước. Khi đó giá trị HV là diện tích phần tô màu xám là (2016)*(201) +(167)*(207)+ (71)*(2016)=217.0 đơn vị diện tích (đvdt). Sau khi chọn 3 điểm knee trên, thực hiện chọn tiếp điểm knee tiếp theo là F khi đó HV tăng thêm (75)*(1613)=6.0 đvdt. Nếu không chọn điểm knee F mà chọn điểm không phải là điểm knee B; khi đó giá trị HV tăng thêm (168.5)*(76)=7.5 đvdt. Như vậy, trong trường hợp này việc chọn điểm knee không hiệu quả bằng chọn điểm không phải là knee. Bài báo giả thiết việc lựa chọn như vậy là khá chặt, nguyên nhân dẫn đến mất cân bằng giữa khả năng thăm dò và khai thác của giải thuật. 3. KỸ THUẬT LỰA CHỌN THÍCH ỨNG TRONG GIẢI THUẬT TIẾN HÓA ĐA MỤC TIÊU SỬ DỤNG ĐIỂM KNEE 3.1. Kỹ thuật lựa chọn thích ứng Từ giả thiết nguyên nhân lựa chọn chặt trong [4], tác giả đề xuất và thử nghiệm phương pháp lựa chọn thích ứng giữa tiêu chí lựa chọn điểm knee và giá trị khoảng cách phù hợp. Kỹ thuật vẫn tận dụng ưu thế điểm knee, đồng thời tận dụng được tiêu chí khoảng cách distance (từ điểm giải pháp đến siêu phẳng cực biên). Nội dung như sau: Bảng 1. Ví dụ giá trị khoảng cách mở rộng đến siêu phẳng Điểm knee Tọa độ distance =0.35 =0.65 x y distance_ext Thứ tự chọn distance_ext Thứ tự chọn A TRUE 1 16 1.414214 2.6517 3 3.712311 2 B FALSE 6 8.5 3.181981 3.1820 2 3.181981 4 C TRUE 7 7 3.535534 4.7730 1 5.833631 1 D FALSE 9 6.5 2.474874 2.4749 5 2.474874 6 E FALSE 12.5 6 0.353553 0.3536 7 0.353553 7 F TRUE 13 5 0.707107 1.9445 6 3.005204 5 G FALSE 14.5 4 0.353553 0.3536 7 0.353553 7 H TRUE 16 1 1.414214 2.6517 3 3.712311 2 Trong mỗi lớp không trội, xác định giá trị khoảng cách lớn nhất của điểm giải pháp tới siêu phẳng cực biên distance_max. Tiến hành gán giá trị distance cho distance_ext của mỗi điểm giải pháp. Với những điểm knee thực hiện cộng *distance_max cho Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 36, 04- 2015 93 distance_ext. Trong đó distance_max=max{distancei} với distancei là khoảng cách từ điểm i tới siêu phẳng. distance_exti= distancei + *distance_max*knee[i] trong đó i0,..Size(F) 3.1.1. Thủ tục lựa chọn thích ứng AdaptiveEnvironmentSelection (F, N, ) Đầu vào: Quần thể được sắp xếp thành các lớp không trội F; Kích thước quần thể N ; Hệ số thích ứng  (0<<1) Bước 1: Với mỗi lớp không trội F: xác định giá trị khoảng cách distance_max Tính giá trị khoảng cách mở rộng của từng điểm giải pháp: distance_ext=distance, với điểm giải pháp không là knee. distance_ext=distance+*distance_max, với điểm giải pháp là knee. Bước 2: Lần lượt chọn các cá thể trong các lớp có hạng trong các tập sắp xếp không trội vào tập Q trong khi |Q|<N. Bước 3: Chọn tiếp các cá thể trong lớp tiếp theo thứ tự giá trị distance_ext giảm dần đến khi |Q|=N 3.1.2. Thủ tục lựa chọn lai ghép AdaptiveMatingSelection (P, N) Đầu vào: P (quần thể), N (kích thước quần thể); Cho Q ← ∅ while |Q| < N do chọn ngẫu nhiên a và b từ P if a trội hơn b then Q ← Q  {a} else if b trội hơn a then Q ← Q  {b} else if distance_ext (a) > distance_ext (b) then Q ← Q  {a} else if distance_ext (a) < distance_ext (b) then Q ← Q  {b} else Q ← Q  {chọn ngẫu nhiên a hoặc b} end if end if end if end while return Q 3.2. Thử nghiệm Bài toán thử nghiệm Bài báo tiến hành thử nghiệm, so sánh hiệu quả của giải thuật tiến hóa đa mục tiêu cải tiến so với giải thuật tiến hóa đa mục tiêu gốc [4] với các bài toán chuẩn DTLZ1, DTLZ2, DTLZ3, DTLZ4; số mục tiêu để thử nghiệm tương ứng là [2, 4, 6, 8,10]. Số biến trong không gian quyết định n=M-1+k (theo khuyến nghị của [12]) cho k=5 cho DTLZ1, k=10 cho DTLZ2, DTLZ3, DTLZ4; trong đó M là số chiều trong không gian mục tiêu. Trong đó sắp xếp không trội sử dụng thuật toán ENS-SS [11]. Thiết lập các tham số Thử nghiệm sử dụng lai ghép SBX [8], đột biến đa thức [7]; Giá trị các tham số: phân bố chỉ số lai ghép 𝜂𝑐 = 20, phân bố chỉ số đột biến 𝜂𝑚 = 20, xác suất lai ghép 𝑝𝑐 = 1.0, xác suất đột biến pc = 1/D (trong đó D là số chiều trong không gian quyết định). Số lần chạy độc lập 10 lần cho mỗi bài toán và số thế hệ là 500. Độ đo được sử dụng là GD và IGD. Đánh giá kết quả: Kỹ thuật điện tử & Khoa học máy tính N.X.Hùng, N.Long, N.Đ.Định, L.Q.Việt,“Kỹ thuật lựa chọn... sử dụng điểm Knee.” 94 Kết quả chạy thử nghiệm được liệt kê ở Bảng 2 (giá trị trung bình trong các lần chạy). Ở giải thuật gốc sử dụng tham số T với các giá trị T=0.2; T=0.5 và T=0.8. Trong giải thuật sử dụng hệ số thích ứng  lần lượt là 0.3 và 0.6 cho mỗi giá trị tham số T. Trong các cột Giải thuật sử dụng kỹ thuật thích ứng các ô được tô màu chứa giá trị tốt hơn cột Giải thuật gốc, còn các ô không được tô màu có kết quả kém hơn Giải thuật gốc tương ứng. Thông qua kết quả thử nghiệm, có thể thấy: Với bài toán DTLZ1: Giải thuật sử dụng lựa chọn thích ứng cho kết quả tốt hơn giải thuật gốc ở phần lớn các lần chạy và kết quả không bằng với độ đo IGD trong hai trường hợp (T=0.2; =0.6 và T=0.8; =0.6) Với bài toán DTLZ2: Giá trị GD của giải thuật sử dụng lựa chọn thích ứng tốt hơn trong phần lớn các trường hợp khi tham số =0.3. Tuy nhiên nhìn một cách tổng thể giải thuật gốc tốt hơn một chút (33 cặp so với 27). Bảng 2. Kết quả chạy thử nghiệm. Bài toán Số chiều Giải thuật gốc Giải thuật sử dụng kỹ thuật lựa chọn thích ứng T=0.2 T=0.5 T=0.8 T=0.2 T=0.5 T=0.8       GD IGD GD IGD GD IGD GD IGD GD IGD GD IGD GD IGD GD IGD GD IGD DTLZ1 2 0.2969 0.4173 0.6963 0.5577 1.4199 0.9404 0.6630 0.8125 0.5880 0.5391 0.4847 0.4479 0.5153 0.5169 0.4453 0.4834 0.7757 0.6572 DTLZ1 4 0.8424 0.8603 1.1291 1.1355 0.8675 0.9935 0.5380 0.8210 1.0319 1.0240 0.6908 0.8541 0.7932 0.8585 0.9325 1.3534 0.7840 1.0345 DTLZ1 6 1.3330 1.1603 1.3291 1.3355 0.9475 1.0335 0.9380 0.8610 1.1575 1.4527 0.7508 0.9741 0.7736 0.9985 0.9912 1.1189 0.8840 1.0326 DTLZ1 8 1.7110 1.1073 1.1740 1.1457 1.6334 1.5488 1.0783 0.9766 1.2388 1.3504 1.0226 0.8939 0.4840 1.0886 1.4205 1.5640 1.3136 1.5141 DTLZ1 10 2.0781 1.7868 2.2247 2.0405 1.0902 1.1400 1.1715 1.0358 1.1714 1.4233 1.6736 1.9713 2.0016 2.3416 1.1599 1.2960 1.1901 1.5682 DTLZ2 2 0.6015 0.5605 0.7328 0.6502 0.7452 0.7510 0.5591 0.5973 0.5868 0.6863 0.6973 0.7123 0.6175 0.8492 0.7326 0.7402 0.6845 0.7569 DTLZ2 4 0.7558 0.7850 0.7751 0.6875 0.5845 0.8208 0.7552 0.7632 0.7960 0.8262 0.7533 0.8670 0.7802 0.8577 0.7958 0.7834 0.8326 0.7830 DTLZ2 6 0.8495 0.8989 0.8892 0.9187 0.8845 0.9008 0.8152 0.9298 0.5960 0.9462 0.7873 0.9670 0.9813 0.9589 0.8490 0.9389 0.8726 0.8353 DTLZ2 8 1.0497 0.6547 0.4039 0.6577 0.7968 0.7026 1.3284 1.1894 1.5327 1.2260 0.9858 1.2145 0.5896 1.1819 0.4464 1.1886 0.5745 1.2281 DTLZ3 10 1.6690 1.5770 1.6598 1.9256 1.6662 0.9689 1.5112 1.4086 1.7948 1.6154 1.4935 1.4314 1.6503 1.4340 1.5223 1.3179 1.9601 1.2437 DTLZ3 2 1.4312 1.2969 1.2472 1.1415 1.3105 1.6755 1.2557 1.2677 1.1069 1.7941 1.1182 1.3789 1.0084 1.4992 1.4171 1.5281 1.5633 1.4798 DTLZ3 4 1.7014 1.6451 1.7687 1.8755 1.7857 1.8334 1.6495 1.6208 1.6115 1.7095 1.5396 1.3139 1.5226 1.8121 1.3427 1.5331 1.3326 1.8816 DTLZ3 6 1.7766 1.9285 1.7110 2.1060 1.9956 1.8211 1.3303 1.8585 1.8056 2.1334 1.9343 1.8783 2.7035 2.1135 1.6785 2.0347 1.7590 1.9411 DTLZ3 8 2.2834 1.9017 1.7692 2.6091 2.1850 1.9901 1.4357 1.9253 1.9016 2.5334 2.0532 2.1537 2.8809 2.2036 2.2745 2.2799 2.1390 2.5239 DTLZ3 10 2.4570 2.0825 1.8203 2.7910 2.2387 2.1668 1.6160 1.9674 2.0253 2.7209 1.7375 2.2531 3.0630 2.3262 2.1239 2.0973 2.3060 2.5946 DTLZ4 2 0.6611 0.8843 0.9301 0.9312 0.9408 0.9406 0.6282 0.8704 0.5888 0.7747 0.7286 0.8907 0.8315 1.0261 1.2521 0.9259 0.8822 0.9062 DTLZ4 4 0.7670 0.9238 0.9441 0.9750 1.0249 1.0306 0.6729 0.9036 1.0047 0.8632 0.8530 1.0989 0.8636 0.8019 0.8313 1.4742 1.0106 0.9289 DTLZ4 6 0.8232 0.9740 1.2034 1.1961 1.0323 1.2079 0.7060 0.9734 0.9011 0.9059 1.0632 1.1334 1.2580 1.1991 1.4100 1.1185 0.9541 1.3340 DTLZ4 8 0.9213 1.1230 1.3441 1.3382 1.1245 1.2528 0.7429 1.7280 1.0158 1.3689 1.7034 1.5592 1.3234 1.2227 1.4303 1.7920 1.0549 1.7613 DTLZ4 10 1.5013 1.1150 1.4627 1.2126 0.3445 1.7243 1.1082 1.6952 1.4959 1.2866 1.7180 1.5318 0.7875 1.3759 1.4021 1.6011 0.9426 1.6774 Với bài toán DTLZ3: Kết quả của bài toán này tương tự như bài toán DTLZ1 khi hầu hết các cặp giá trị so sánh thì giá trị tốt hơn thuộc về giải thuật sử dụng lựa chọn thích ứng (35 giá trị tốt hơn so với 25). Với bài toán DTLZ4: Phần lớn kết quả của giải thuật lựa chọn thích ứng tốt hơn giải thuật gốc; trong các cặp so sánh thì có nhiều giá trị IGD của giải thuật sử dụng lựa chọn thích ứng tốt hơn giá trị IGD của giải thuật gốc. Ngoài ra, hình 4 - hình 7 so sánh giá trị GD, IGD giữa giải thuật gốc và giải thuật sử dụng kỹ thuật lựa chọn thích ứng cho bài toán DTLZ1 với số mục tiêu là 2,3; tham số T =0.1; hệ số thích ứng lần lượt là 0.3 và 0.6 cho thấy giải thuật sử dụng kỹ thuật lựa chọn thích ứng cho kết quả tốt hơn. Tổng kết lại, thông qua thực nghiệm giải thuật với kỹ thuật lựa chọn thích ứng giữa tiêu chí điểm Knee và giá trị khoảng cách, giải thuật đã được duy trì tốt hơn cân bằng giữa khả năng thăm dò và khai thác của quá trình tiến hóa, qua đó chất lượng giải pháp đạt được đạt Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 36, 04- 2015 95 giá trị hội tụ và đa dạng tốt hơn. Điều đó chỉ ra rằng, việc sử dụng ràng buộc quá chặt về ưu tiên lựa chọn điểm knee mặc dù giúp cho giải thuật hội tụ tốt nhưng sẽ giảm tính chất đa dạng của quần thể do mất cân bằng giữa khả năng thăm dò và khai thác của quá trình tiến hóa. Kỹ thuật lựa chọn thích ứng là một kỹ thuật hiệu quả nhằm duy trì khả năng thăm dò và khai thác của giải thuật, từ đó cải thiện chất lượng của giải thuật một cách hiệu quả. Hình 4. GD khi =0.3;=0.6 và thuật toán gốc cho DTLZ1 (2 mục tiêu, T=0.1). Hình 5. IGD khi =0.3;=0.6 và thuật toán gốc cho DTLZ1 (2 mục tiêu, T=0.1). Hình 6. GD khi =0.3; =0.6 và thuật toán gốc cho DTLZ1 (3 mục tiêu, T=0.4). Hình 7. IGD khi =0.3; =0.6 và thuật toán gốc cho DTLZ1 (3 mục tiêu, T=0.4). 4. KẾT LUẬN Giải thuật tiến hóa tối ưu đa mục tiêu sử dụng điểm Knee có chất lượng khá tốt với nhiều mục tiêu, tuy nhiên với đặc điểm sử dụng tiêu chuẩn điểm knee chặt đôi khi dẫn đến kết quả không như mong muốn: trong một số trường hợp sẽ đạt được mục tiêu là tính chất hội tụ nhưng sẽ giảm mất tính đa dạng dọc theo tập phương án tối ưu Pareto. Tác giả đã mềm hóa tiêu chuẩn Knee và tận dụng tiêu chuẩn khoảng cách đến siêu phẳng và đề xuất kỹ thuật lựa chọn thích ứng để đảm bảo tính cân bằng giữa thăm dò và khai thác của giải thuật từ đó nâng cao chất lượng giải pháp đạt được về tính chất hội tụ và đa dạng làm cho giải thuật tiến hóa đa mục tiêu có hiệu quả. Lời cảm ơn: Nhóm tác giả cảm ơn sự giúp đỡ trong thí nghiệm tại bộ môn CNPM- Khoa CNTT – Học viện KTQS. TÀI LIỆU THAM KHẢO [1]. K. Deb et al, "A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II", IEEE Transactions On Evolutionary Computation, Vol. 6, No. 2, April 2002. [2]. K. Deb and H. Jain, "An Evolutionary Many-Objective Optimization Algorithm Using Reference-point Based Non-dominated Sorting Approach, Part I: Solving Problems with Box Constraints", IEEE Transactions on Evolutionary Computation, 2014. [3]. Long Nguyen, Lam Thu Bui, and Hussein, "DMEA-II: The Direction-based Multi- objective Evolutionary Algorithm-II", Soft Computing, November 2014, Volume 18, Issue 11, pp 2119-2134. [4]. X. Zhang et al, "A Knee Point Driven Evolutionary Algorithm for Many-Objective Optimization", IEEE Transactions On Evolutionary Computation, 2014 000000 000000 000001 001001 001001 001 0 500 GD Số thế hệ gốc   Kỹ thuật điện tử & Khoa học máy tính N.X.Hùng, N.Long, N.Đ.Định, L.Q.Việt,“Kỹ thuật lựa chọn... sử dụng điểm Knee.” 96 [5]. Kaisa Miettinen, "Nonlinear Multiobjective Optimization", Kluwer Academic Publishers, 1999. [6]. K. Deb and R. B. Agrawal, “Simulated binary crossover for continuous search space,” Complex Systems, vol. 9, no. 4, pp. 115–148, 1995. [7]. K. Deb and M. Goyal, “A combined genetic adaptive search (GeneAS) for engineering design,” Computer Science and Informatics, vol. 26, no. 4, pp. 30, 1996. [8]. K. Deb, "Multi-objective Optimization using Evolutionary Algorithms", John Wiley & Sons, Ltd, 2001. [9]. D.A.V. Veldhuizen, "Multiobjective Evolutionary Algorithms: Classifications, Analyses, and New Innovation". PhD thesis, Department of Electrical Engineering and Computer Engineering, Airforce Institute of Technology, Ohio, 1999. [10]. K. Deb and S. Gupta, " Understanding Knee Points in Bicriteria Problems and Their Implications as Preferred Solution Principles", KanGAL Report No. 2010005, 2010. [11]. X. Zhang et al, "An Efficient Approach to Non-dominated Sorting for Evolutionary Multi-objective Optimization", IEEE Transactions On Evolutionary Computation, 2014. [12]. K. Deb, L. Thiele, M. Laumanns and E. Zitzler, "Scalable Test Problems for Evolutionary Multi-Objective Optimization", TIK-Technical Report No.112, 2001. ABSTRACT AN ADAPTIVE SELECTION SCHEME FOR MANY-OBJECTIVE EVOLUTIONARY ALGORITHM USING KNEE POINTS In many areas of social life, optimization problem has gathered significant research interests. There often exist more than one objective which conflicts to each other. This class of problem is defined as Multi Objective Problems. There have been many methods to solve these problems, in which Multiobjective Evolutionary Algorithms (MOEAs) have been widely and effectively used. The MOEAs target two goals: (1) obtaining the solutions as close to the Pareto optimal solution as possible and (2) retrieving the solutions as diverse as possible along Pareto optimal front. Recently, guide techniques have been applied in order to control the evolution process to balance exploration and exploitation, which then helps improve closeness and diversity qualities. Knee Point Driven Algorithm (KnEA), which has just been introduced, has improved MOEA. However, choosing knee points with less distance to hyperplane instead of non-knee points with distance greater leads to worse results in some cases. This paper proposes an adaptive environment selection and an adaptive mating selection technique for Many-Objective Optimization Algorithm using knee points in order to improve exploration and exploitation. Keywords: Evolutionary multiobjective, Optimization, Generational Distance, Inverse Generational Distance, HyperVolume, Knee Point, Adaptive environment selection, Adaptive mating selection. Nhận bài ngày 01 tháng 12 năm 2014 Hoàn thiện ngày 10 tháng 4 năm 2015 Chấp nhận đăng ngày 15 tháng 4 năm 2015 Địa chỉ: * Học viện Kỹ thuật Quân sự – nguyenxuanhung@outlook.com, longit76@gmail.com ** Viện Công nghệ Thông tin/Viện KHCNQS–nddinh76@gmail.com ***Bệnh viện Trung ương Quân đội 108