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

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.
Nội dung trích xuất từ tài liệu:
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 Kỹ thuật điện tử & Khoa học máy tính 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 88 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.” Nghiên cứu khoa học công nghệ 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á ...