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<br /> <br /> KỸ THUẬT LỰA CHỌN THÍCH ỨNG CHO GIẢI THUẬT TIẾN<br /> HÓA ĐA MỤC TIÊU SỬ DỤNG ĐIỂM KNEE<br /> NGUYỄN XUÂN HÙNG*, NGUYỄN LONG*, NGUYỄN ĐỨC ĐỊNH**, LÊ QUỐC VIỆT***<br /> 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<br /> 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ế<br /> 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<br /> đị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<br /> 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<br /> 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<br /> 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 để<br /> đ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<br /> 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<br /> đ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<br /> 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<br /> 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<br /> 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<br /> ư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.<br /> 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.<br /> <br /> 1. ĐẶT VẤN ĐỀ<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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ử<br /> 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<br /> 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<br /> [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<br /> 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à<br /> đa dạng. Kỹ thuật chính được sử dụng thông qua mật độ tia (ray based density) được định<br /> 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<br /> 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ó<br /> 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<br /> 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<br /> 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.<br /> 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<br /> 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ư<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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.<br /> 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<br /> 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<br /> <br /> <br /> <br /> 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.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> 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<br /> 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.<br /> <br /> <br /> <br /> <br /> Hình 1.Mô tả cách chọn điểm Knee.<br /> 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<br /> 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<br /> 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<br /> 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<br /> đ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,<br /> từ đó nâng cao chất lượng và hiệu quả của giải thuật.<br /> 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,<br /> 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<br /> 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<br /> 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ử<br /> 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.<br /> 2. TỔNG QUAN<br /> 2.1. Bài toán tối ưu đa mục tiêu<br /> Bài toán được định nghĩa như sau [5]:<br /> min{f1(x), f2(x),...,fk(x)} với xS,<br /> trong đó, k(2) là số mục tiêu, fi : Rn  R là các hàm mục tiêu.<br /> 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<br /> đị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<br /> 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<br /> 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<br /> 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. Để<br /> 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ả<br /> 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.<br /> 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<br /> 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<br /> 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.<br /> Để đơ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ó<br /> tương đương với min của fi .<br /> 2.2. Quan hệ trội<br /> 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<br /> giải pháp trong nhiều mục tiêu [8]:<br /> <br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 36, 04- 2015 89<br />  Kỹ thuật điện tử & Khoa học máy tính<br /> <br /> Đị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<br /> mục tiêu và tốt hơn x2 ở ít nhất một mục tiêu.<br /> 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.<br /> 2.3. Tối ưu Pareto<br /> Một nghiệm x* của bài toán được gọi là nghiệm lý tưởng nếu:<br /> fi(x*) fi(x) xX : i= {1, …k}<br /> 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<br /> 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ư<br /> 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”<br /> hơn đó là nghiệm tối ưu Pareto.<br /> <br /> <br /> <br /> <br /> Hình 2. Minh họa điểm tối ưu Pareto.<br /> 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<br /> nghiệm x ≠ x*X sao cho x trội hơn x*. Nghĩa là: f(x)