Các phương pháp giải bài toán tối ưu nhiều mục tiêu

Trang 24 CHƯƠNG II: CÁC PHƯƠNG PHÁP GIẢI BÀI TOÁN TỐI ƯU NHIỀU MỤC TIÊU 2.1 Phương pháp ràng buộc (the constraint method). a) Mô hình bài toán. Cho một bài toán đa mục tiêu với p mục tiêu: ܯ݅݊ ൛ ଵ݂(ݔ), ଶ݂(ݔ), … , ௣݂(ݔ)ൟ (2.1) Sao cho: ݔ ∈ ܴ௡ Trong đó: ݔ = (ݔଵ, … ,ݔ௡) ∈ ܴ௡: là không gian quyết định. Ta chuyển bài toán trên thành bài toán ràng buộc là: ܯܽݔ ௛݂(ݔଵ, … , ݔ௡) Sao cho (ݔଵ, … , ݔ௡) ∈ ܴ௡ (2.2) ௞݂(ݔଵ, … ,ݔ௡) ≥ ܮ௞ ݇ = 1, … ,ℎ − 1,ℎ, ℎ + 1, … ,݌ Trong đó mục tiêu thứ h được chọn tùy ý để lấy max. Công thức này là bài toán đơn mục tiêu. Do đó có thể giải được bằng phương pháp đơn hình cho bài toán quy hoạch tuyến tính. b) Thuật toán: Bước 1: xây dựng một bảng thỏa hiệp a. Giải lần lượt p bài toán đơn mục tiêu ứng và các ràng buộc tương ứng. Gọi nghiệm ứng với mục tiêu thứ k là: ݔ௞ = (ݔଵ௞, … ݔ௡௞) với k = 1, … , p. Sau đó tính giá trị của p hàm mục tiêu này đạt được tại các ݔ௞ tương ứng, ta gọi là: ଵ݂(ݔଵ௞), ଶ݂(ݔଶ௞), … , ௣݂(ݔ௣௞). b. Sắp xếp p giá trị ứng với p mục tiêu vừa tính được ở trên vào trong bảng. Ở đây, hàng ứng với các ݔଵ, … ݔ௞ và cột là nhãn của mục tiêu. Trang 25 Bảng thoả hiệp cho một bài toán với p hàm mục tiêu. ଵ݂(ݔ௞) ଶ݂(ݔ௞) … ௣݂(ݔ௞) ݔଵ ଵ݂(ݔଵ) ଶ݂(ݔଵ) … ௣݂(ݔଵ) ݔଶ ଵ݂(ݔଶ) ଶ݂(ݔଶ) … ௣݂(ݔଶ) … … … … … ݔ௞ ଵ݂(ݔ௞) ଶ݂(ݔ௞) … ௣݂(ݔ௞) c. Tìm số lớn nhất và nhỏ nhất trong cột thứ k, lần lượt kí hiệu là ܯ௞, ݊௞ với ݇ = 1, … ,݌. Bước 2: Quy ước một bài toán quy hoạch đa mục tiêu được cho ở (2.1) tương ứng với bài toán ràng buộc của nó như ở (2.2) Bước 3: Chọn giá trị của ܮ௞ với ݇ ≠ ℎ trong đoạn [݊௞,ܯ௞] bằng cách chia [݊௞,ܯ௞] ra ݎ phần bằng nhau. ܮ௞ có thể nhận một trong r giá trị sau: ܮ௞ = ݊௞ + ௧௥ିଵ (ܯ௞ − ݊௞) với ݐ = 0,1, … . , ݎ − 1 Bước 4: Ứng với mỗi giá trị của ܮ௞ ta giải bài toán (2.2) và mỗi bài toán cho một nghiệm chấp nhận được. Trong những nghiệm này ta chọn nghiệm tốt nhất. 2.2 Phương pháp tổng trọng số. Bài toán tối ưu nhiều mục tiêu dạng tổng quát được phát biểu: ܯ݅݊ { ଵ݂(ݔ), ଶ݂(ݔ), … , ௣݂(ݔ)} Sao cho: ݔ ∈ ܴ௡ Trong đó: ݔ = (ݔଵ, … , ݔ௡) ∈ ܴ௡ : là không gian nghiệm. Ta chuyển bài toán trên thành bài toán một bài toán tổng sau: ܯ݅݊ ݂ = ݓଵ ଵ݂(ݔ) + ݓଶ ଶ݂(ݔ) +⋯+ ݓ௣ ௣݂(ݔ) Sao cho ݔ ∈ ܴ௡ Trong đó: ݓ௜ ≥ 0 với ݅ = 1, … ,݊ và Trang 26 ෍ݓ௜ ௣ ௜ୀଵ = 1 Ứng với mỗi bộ trọng số ݓ௜ ta sẽ tìm được một nghiệm tối ưu Pareto. Ví dụ 14: Giải bài toán tối ưu hai hàm mục tiêu sau: min ିସஸ௫,భ,௫మஸସ{ ଵ݂(ݔଵ,ݔଶ), ଶ݂(ݔଵ,ݔଶ)} Với: ଵ݂(ݔଵ,ݔଶ) = 3ݔଵଶ − 2ݔଵݔଶ + 4ݔଶ + ݔଶଶ ଶ݂(ݔଵ,ݔଶ) = ݔଵଶ − ݔଵ − ݔଵݔଶ + 0.5ݔଶଶ Sau khi thực hiện các bước tính toán ta xác định được giá trị của mỗi hàm mục tiêu như sau: ݓ = (ݓଵ,ݓଶ) (0,1) (0.2, 0.8) (0.4, 0.6) (0.6, 0.4) (0.8, 0.2) (1,0) ଵ݂(ݔଵ,ݔଶ) ≈ 6 -2.2 -4.45 2.53 -0.76 -6 ଶ݂(ݔଵ,ݔଶ) ≈ - 0,5 0.11 0.3 1.97 -0.88 3.5 2.3 Phương pháp tổng trọng số chấp nhận được đối với bài toán tối ưu 2 mục tiêu. 2.3.1 Khái niệm cơ sở Trong phần trình bày này chúng ta giới thiệu một phương pháp xác định hiệu quả biên Pareto đối với bài toán tối ưu hai mục tiêu và đây cũng chính là cơ sở giúp ta nghiên cứu phương pháp tổng trọng số chấp nhận được đối với bài toán tối ưu đa mục tiêu. Phần trình bài trước phương pháp tổng trọng số tìm kiếm từng nghiệm một - tối ưu Pareto bằng cách thay đổi trọng số tương ứng của các hàm mục tiêu mà các trọng số này được lựa chọn từ người giải. Phương pháp này thường sinh ra trên biên Pareto rất ít các nghiệm tối ưu và đặt biệt là sẽ không tìm ra nghiệm tối ưu Pareto trên miền không lồi. Mục đích chính của phương pháp tổng trọng số chấp nhận được là tập trung tìm kiếm nghiệm tối ưu trên những vùng chưa được tìm kiếm nằm trên biên Pareto bằng cách thay đổi một cách hợp lý các trọng số, hơn là ưu tiên vào việc lựa chọn các trọng số và chỉ định các ràng buộc bất đẳng thức bổ sung. Phương pháp này sẽ tìm được nhiều nghiệm tối ưu Pareto hơn và tìm được nghiệm tối ưu trong miền không lồi, đồng thời bỏ qua các nghiệm non-Pareto. Một số kí hiệu: f = (f1(x),f2(x)) : là vector hàm mục tiêu. Trang 27 x = (x1,…,xn) : là vector quyết định p=(p1, p2) : là vector tham số cố định. g : là vector ràng buộc bất đẳng thức. h : là vector ràng buộc đẳng thức. w = (w1,…,wn) : là vector trọng số ݂௜ : Hàm mục tiêu được chuẩn hóa. f U : Điểm Utopia f N : Điểm Nadir ni : số lượng đoạn cần mịn hóa thứ i li : Chiều dài của đoạn thứ i. ݈௔௩௚ : Chiều dài trung bình của tất cả các đoại tại mỗi bước C : Hệ số nhân. P1, P2 : Điểm cuối của đoạn. ߜ௃ : Khoảng cách từ các điểm trên biên Pareto đã được tuyến tính thành từng đoạn đến nón ܴା ொ ߜ௜ : Khoảng cách vuông góc từ các điểm trên biên đền nón ܴ ା ொ ∆xଵ, ∆xଶ : Kích thước của lưới HÌNH 4: Tuyến tính hóa các đoạn trên biên Pareto Trang 28 Trong phần này ta phát biểu bài toán tối ưu 2 mục tiêu dưới dạng như sau: Minݓ ଵ݂(ݔ) ଵ݂ഥ (ݔ) + (1 − ݓ) ଶ݂(ݔ)ଶ݂ഥ (ݔ) ܵܽ݋ ܿℎ݋ ݔ ∈ ܺ Trong đó: ܺ = { ݔ ∈ ܴொ|݃(ݔ) ≤; ℎ(ݔ) = 0 ݒà ݓ ∈ [0,1] } ଵ݂ഥ (ݔ) ݒà ଶ݂ഥ (ݔ) : là các hàm chuẩn hóa tương ứng của ଵ݂(ݔ) ݒà ଶ݂(ݔ) 2.3.2 Phương pháp tổng trọng số chấp nhận được dành cho bài toán 2 mục tiêu: Sau đây là các bước chi tiết để giải bài toán tối ưu 2 mục tiêu bằng phương pháp Tổng trọng số chấp nhận được: Bước 1: Chuẩn hóa các hàm mục tiêu trong không gian hàm mục tiêu. Khi x ୧∗ là vector nghiệm tối ưu cho từng bài toán một mục tiêu ୧݂(x) với i = 1,2 thì hàm mục tiêu chuẩn hóa ݂୧ được xác định như sau: ݂௜ = ௜݂ − ௜݂௎ ௜݂ ே − ௜݂ ௎ (1) Trong đó : ݂௎ : là điểm Utopia và được định nghĩa là: ݂௎ = [ ଵ݂(ݔ௜∗), ଶ݂(ݔ ௜∗)] (2) ݂ே: là điểm Nadir và được định nghĩa là: ݂ே = [ ଵ݂ே, ଶ݂ே] (3) Và ௜݂ே = max[ ௜݂(ݔଵ∗), ௜݂(ݔଶ∗)] (4) Bước 2: Giải bài toán đa mục tiêu bằng phương pháp tổng trọng số với số nhỏ của phép chia - ݊଴. Ta sẽ lấy ݊଴ = 5~10. Từ đó tính giá trị của trong số w theo công thức: ∆ݓ = 1݊ ଴ (5) Bước 3: Tính toán độ dài của các đoạn giữa tất cả các nghiệm lân cận nhau trên biên Pareto. Xóa các nghiệm trùng nhau. Khi sử dụng phương pháp tổng trọng số để tìm nghiệm tối ưu sẽ xảy ra trường hợp các nghiệm tối ưu trùng nhau khi đó khoảng cách Euclid Trang 29 giữa chúng là 0, trong các nghiệm này chỉ có duy nhất một nghiệm tối ưu nằm trên biên Pareto sẽ được chọn. Bước 4: Xác định số lượng đoạn cần tinh lọc (liên quan với chiều dài trung bình của tất cả các đoạn), nếu đoạn nào dài hơn thì cần phải được tinh lọc hơn. Việc tinh lọc trên biên Pareto được xác định dựa trên độ dài tương đối của các đoạn: ݊௜ = ൤ܥ ௟೔௟ೌೡ೒൨ cho mỗi đoạn thứ i (6) Trong đó ݊௜ :là số lượng cần lọc đối với đoạn thứ i ݈௜ :là chiều dài của đoạn thứ i ݈௔௩௚ :là chiều dài trung bình của tất cả các đoạn C :là hệ số nhân, ta thường lấy giá trị của C = [1,2] Bước 5: Nếu ݊௜ ≤ 1 thì không cần phải lọc đoạn này. Nếu ݊௜ > 1 thì thực hiện bước 6 Bước 6: Tính khoảng cách của ߜଵ ݒà ߜଶ dựa trên ߜ௃ như sau: HÌNH 5 Trang 30 ߜଵ = ߜ௃ܿ݋ݏߠ ݒà ߜଶݏ݅݊ߠ (7) Và ߠ được tính như sau: ߠ = ݐܽ݊ିଵ ቆ− ଵܲଵ − ଶܲଵ ଵܲ ଶ − ଶܲ ଶቇ (8) Với: P1 = ( ଵܲଵ, ଵܲଶ) và ଶܲ = ( ଶܲଵ, ଶܲଶ) Bước 7: Giải bài toán tối ưu con: ܯ݅݊ ݓ ଵ݂ഥ(ݔ) + (1− ݓ) ଶ݂ഥ (ݔ) Sao cho: ଵ݂ഥ(ݔ) ≤ ଵܲ௫ − ߜଵ ଶ݂ ഥ (ݔ) ≤ ଶܲ௫ − ߜଶ ℎ(ݔ) = 0 và g(x) ≤ 0, w ∈ [0,1] Trong đó: ௜ܲ௫ ݒà ௜ܲ௬ là vị trí x và y tương ứng của các điểm cuối. Sau đó ứng với mỗi ݊௜ đã xác định trong bước 4. Ta tính toán ࢝࢏ cho mỗi miền chấp nhận được. ∆ݓ௜ = 1݊ ௜ (9) Bước 8: Tính chiều dài của các đoạn giữa các nghiệm lân cận nhau. Xóa các nghiệm trùng nhau. - Nếu chiều dài của tất cả các đoạn nhỏ hơn chiều dài đã được chỉ định thì kết thúc thuật toán. - Nếu có một đoạn mà chiều dài lớn hơn tất cả các chiều dài thì lặp lại bước 4. 2.4 Phương pháp tổng trọng số chấp nhận được cho bài toán tối ưu đa mục tiêu 2.4.1 Giới thiệu phương pháp tổng trọng số chấp nhận được: Phần này giới thiệu phương pháp “Tổng trọng số chấp nhận được” cho bài toán tối ưu hóa nhiều mục tiêu. Xuất phát từ phương pháp “tổng trọng số chấp nhận được” dành cho bài toán hai mục tiêu - xác định một cách hình thức không gian nghiệm tối ưu Pareto, tìm nghiệm trên tập không lồi và bỏ qua các nghiệm tối ưu non-Pareto. Tuy nhiên phương pháp này chỉ có thể giải bài toán tối ưu với 2 hàm mục tiêu. Tổng trọng số chấp nhận được là phương pháp mở rộng của phương pháp tổng trọng số chấp nhận được hai mục tiêu để giải bài toán tối ưu với nhiều hàm mục tiêu. Trong phần trước thì phương pháp Tổng trọng số đã được trình bài để xấp Trang 31 xỉ tập nghiệm Pareto một cách nhanh chóng. Đồng thời mạng lưới các điểm trên biên Pareto cũng được xác định hay tập nghiệm Pareto được chia ra thành nhiều đoạn biên Pareto nhỏ. Sau đó mỗi đoạn trên biên Pareto được lọc bớt đi bằng cách áp thêm các ràng buộc đẳng thức thông qua điểm giả Nadir và các nghiệm tối ưu Pareto chấp nhận được trên từng đoạn của không gian hàm mục tiêu. Phương pháp Tổng trọng số chấp nhận được sẽ sinh ra các đoạn nằm trên biên Pareto có sự phân bố tốt trên tập nghiệm Pareto, đồng thời phương pháp này cũng cho phép chúng ta tìm nghiệm đối với tập không lồi. Một số kí hiệu: f(x,p) : là hàm mục tiêu của vector x và vector tham số cố định p x = (x1,…,xn) : là vector quyết định p : vector các tham số cố định g(x,p) : vector ràng buộc bất đẳng thức h(x,p) : vector ràng buộc đẳng thức m : số lượng hàm mục tiêu w = (w1,…,wn) : là vector trọng số ݂௜̅ : Hàm mục được chuẩn hóa ݂௎ : Điểm utopia ݂ே : Điểm nadir ݂௜∗ : Điểm anchor thứ i ܲ௝ :Vector vị trí của nghiệm chấp nhận được thứ j trên từng đoạn tuyến tính nằm trên biên Pareto cần được mịn hóa. Bài toán tối ưu nhiều mục tiêu được phát biểu như sau: min ݂(ݔ,݌) Sao cho: ݃(ݔ,݌) ≤ 0 ℎ(ݔ,݌) = 0 ݔ௜ ,௅஻ ≤ ݔ௜ ≤ ݔ௜,௎஻ ݒớ݅ ݅ = 1, … ,݊ Trang 32 Trong đó: xi,LB và xi,UB : là các biên dưới và biên trên của các biến thứ i tương ứng. 2.4.2 Các khái niệm cơ sở Đặt trưng cơ bản của phương pháp Tổng trọng số chấp nhận được là làm mịn một cách chấp nhận được biên Perato. Trong giai đoạn thứ nhất, phương pháp này xác định hình dạng gồ ghề lúc đầu của biên Perato. Bằng tính toán kích thước của từng đoạn nằm dọc theo biên Perato (là một đoạn thẳng trong trường hợp 3 chiều), sau đó ta tiến hành mịn hóa biên Pareto trong không gian mục tiêu đã được xác định. Giai đoạn tiếp theo, các đoạn này được xem là miền chấp nhận đối với bài toán con - Sub- Optimizaton bằng cách thêm vào các ràng buộc (trong phương pháp tổng trọng số chấp nhận được hai mục tiêu, miền chấp nhận được khi tìm kiếm thêm thì được xác định bằng cách thêm 2 ràng buộc bất đẳng thức). Sau đó chúng ta giải bài toán con - Sub-Optimization trong các miền chấp nhận này để đạt được nhiều phương án tối ưu Pareto hơn. Khi tập các phương án tối ưu Pareto mới được xác định, thông qua việc tính toán để xác định kích thước của từng đoạn trên biên Pareto được xem như là quá trình làm mịn biên Pareto. Bước này được lặp lại cho đến khi tìm được nghiệm Pareto tối ưu nhất. Hình 6 sau so sánh phương pháp Tổng trọng số cổ điển với phương pháp tổng trọng số chấp nhận được hai mục tiêu cho cùng một bài toán mà có miền phẳng và không lồi. Hình 6: Biên Pareto tìm được bằng phương pháp tổng trọng số. Trang 33 Hình 7: Biên Pareto tìm được bằng phương pháp tổng trọng số chấp nhận được hai mục tiêu. Ta thấy rằng ràng buộc bất đẳng thức như là biên cho việc xây dựng miền chấp nhận được không phù hợp đối với bài toán tối ưu đa mục tiêu. Miền chấp nhận được đối với việc mịn hóa trong trường hợp 2 chiều có thể được định nghĩa một cách dễ dàng bằng cách đặt 2 ràng buộc bất đẳng thức song song đến mỗi trục mà khoảng cách đã được chỉ định từ điểm cuối vì biên Pareto là đường cong 2 chiều và luôn có 2 điểm cuối đối với mỗi đoạn thuộc biên Pareto. Tuy nhiên trong trường hợp lớn hơn 2 chiều thì biên Pareto sẽ là một siêu phẳng (nếu có nhiều hơn 3 hàm mục tiêu), và điều này trở nên rất khó để thiết lập các ràng buộc cho bài toán con - Sub-Optimization trên từng đoạn thuộc biên Pareto vốn đã được lựa chọn và mịn hóa sao cho chấp nhận được. Vì các đoạn trên biên Pareto có thể có những hình dạng tùy ý và số cạnh của mỗi đoạn biên Pareto rất đa dạng. Hơn nữa, khi số đỉnh lớn hơn số chiều của không gian hàm mục tiêu, thì tất cả các đỉnh hoặc cạnh liên kết các đỉnh này có thể không nằm trong cùng một mặt phẳng hay siêu phẳng, do đó rất khó để thiết lập các ràng buộc cho bài toán con - Sub- Optimization và để mịn hóa thích hợp trong các giai đoạn tiếp theo. Trang 34 2.4.3 Các thủ tục của phương pháp tổng trọng số chấp nhận được đa mục tiêu: Trong phần này chúng ta trình bày chi tiết các thủ tục cho việc thực hiện phương pháp tổng trọng số chấp nhận được đa mục tiêu. Bước 1: Chuẩn hóa các hàm mục tiêu. Khi ݔ௜∗ là vector nghiệm tối ưu đối với hàm mục tiêu fi thứ i. Điểm Utopia ࢌ௎ được định nghĩa như sau: ݂௎ = [ ଵ݂(ݔଵ∗) ଶ݂(ݔଶ∗) … ௠݂(ݔ௠∗) ] Điểm giả Nadir ࢌࡺ được định nghĩa là: ݂ே = [ ଵ݂ே ଶ݂ே… ௠݂ே] Trong đó: Mỗi thành phần ௜݂ ே được xác định bởi: ௜݂ ே = max[ ଵ݂(ݔଵ∗) ଶ݂(ݔଶ∗) … ௠݂(ݔ௠∗) ] (5) Điểm anchor ݂ ௜∗ thứ i được định nghĩa như sau: ࢌ࢏∗ = ൣ ଵ݂൫ݔ௜∗൯ ଶ݂൫ݔ௜∗൯… ௠݂൫ݔ௜∗൯ ൧ (6) Và bây giờ hàm mục tiêu chuẩn hóa ࢌത ࢏ đạt được là: ݂௜̅ = ௜݂ − ௜݂௎ ௜݂ ே − ௜݂ ௎ (7) Trang 35 Bước 2: Tối ưu nhiều mục tiêu sử dụng cách tiếp cận bằng phương pháp tổng trọng số với số lượng phân chia nhỏ - ࢔૙ Đối với bài toán 3 hàm mục tiêu, hàm mục tiêu tổng fTotal với các trọng số wi đạt được như sau: ௧݂௢௧௔௟ = ݓଶ[ݓଵ ଵ݂ + (1− ݓଵ) ଶ݂] + (1 − ݓଶ) ଷ݂ = ݓଵݓଶ ଵ݂ + (1− ݓଵ)ݓଶ ଶ݂ + (1 −ݓଶ) ଷ݂ ݒớ݅ ݓ௜ ∈ [0,1] (8) Một cách tổng quát, hàm mục tiêu tổng ܨ்௢௧௔௟௠ của m hàm mục tiêu được xác định bởi: ்݂ ௢௧௔௟ ௠ = ݓ௠ିଵ்݂ ௢௧௔௟௠ିଵ + (1 − ݓ௠ିଵ) ௠݂, ݉ ≥ 2 (9) Trong đó: ்݂ ௢௧௔௟ ௠ ≡ ଵ݂ Chú ý rằng m-1 nhân tố trọng số thì cần để tìm không gian mục tiêu m chiều. Bước hình thức kích thước của nhân tố trọng số thứ i là wi được xác định bởi số lượng phân chia ban đầu cùng với số chiều của hàm mục tiêu thứ i: ∆w୧ = 1n଴; ୧ , i = 1, … , m − 1 (10) Trong phần trình bày này, ta sử dụng cùng một giá trị của trọng số wi. Có một lược đồ để xác định giá trị của trọng số wi một cách có hệ thống, điều này sẽ giúp ích rất nhiều trong việc tạo ra nghiệm có sự phân bố tốt hơn. Tuy nhiên trong phương pháp Tổng trọng số chấp nhận được thì đẳng thức (10) có thể được dùng đến duy chỉ một lần và sau đó quá trình mịn hóa sẽ được áp dụng đối với bài toán tối ưu đa mục tiêu xấp xỉ. Bước 3: Loại bỏ các nghiệm trùng nhau. Vì khi sử dụng phương pháp Tổng trọng số có thể sinh ra ra các nghiệm trùng nhau này. Khoảng cách Euclid giữa các nghiệm này là 0 và trọng số các nghiệm trùng nhau này chỉ chọn 1 nghiệm nằm trên biên Pareto. Trong khi thực hiện tính toán nếu khoảng cách giữa các nghiệm trong không gian mục tiêu nhỏ hơn  - khoảng cách đã xác định trước đó, thì khi đó ta nhận tất cả các nghiệm này và sẽ xóa bỏ nghiệm trước đó. Bước 4: Trang 36 Nhận dạng các đoạn trên biên Pareto. Các đoạn với hình dạng bất kỳ nào được dùng, nhưng trong phần trình bày này ta sử dụng mặt có hình dạng là tứ giác trong bài toán 3 chiều. 4 nghiệm tối ưu Pareto trở thành 4 nốt của mỗi mặt và các cạnh là các đoạn thẳng nối 2 điểm cạnh nhau của mỗi mặt. Việc xây dựng và duy trì các lưới trên biên Pareto có thể sẽ rất dài dòng nhưng có 2 thuận lợi : i) Các mặt đóng vai trò quan trọng khi sử dụng mịn hóa các mặt trong những pha tiếp theo. ii) Nếu chỉ tìm thấy điểm không trội thì rất khó vẽ hay hình dung ra hình dạng của biên Pareto. Nhưng khi có lưới thì việc này sẽ dễ hơn nhất là khi các lưới là hữu hạn. Bước 5: Xác định cách bố trí để mịn hóa mỗi mặt trên biên Pareto. Khi các mặt càng lớn thì nó cần phải được lọc nhiều hơn. Hình 9: Trong trường hợp 3 chiều, biên Pareto là mặt và mảnh biên Pareto đã được tuyến tính hóa bằng 4 đoạn thẳng nối 4 đỉnh. Hình ảnh này cũng cho thấy ví dụ về quá trình mịn hóa, trong đó các mặt được tạo thành bởi 4 nốt trong không gian mục tiêu 3 chiều. Vì mặt dưới thấp hơn thì lớn hơn, nên nó sẽ được làm mịn nhiều. Trong mỗi lưới (gồm nhiều mặt tạo thành ), vị trí của nghiệm chấp nhận được xác định bằng phép nội suy và bài toán con Sub-Optimization được giải cùng với đường thẳng nối điểm giả Nadir và các nghiệm chấp nhận được. Nghiệm hiện tại có thể khác biệt với nghiệm chấp nhận được và có thể có nghiệm trội – nghiệm này sẽ được xóa đi trong quá trình làm mịn biên Pareto. Trang 37 Vector vị trí của nghiệm chấp nhận được thứ j trên từng mặt đã được làm mịn trên biên Pareto –ܲ௝ đạt được như là tổng trọng số của 4 vector nghiệm (ương ứng là 4 node) như sau: ܲ௝ = ߚଵܰଵ + ߚଶܰଶ + ߚଷܰଷ + ߚସܰସ ߚ௜ ∈ [0,1] (11) Trong đó: ܰ௜ là vector vị trí nút thứ i của mảnh biên Pareto (hình 9.b) ߚ௜ là nhân tố trọng số đối với phép nội suy. Vector chuẩn hóa của ܲ௝ đạt được như sau: തܲ௝ = ௜ܲ௝ − ௜݂௎ ௜݂ ே − ௜݂ ௎ (12) Trong đó: ௜ܲ ௝ là tọa độ thứ i của vector ܲ௝. Mức độ mịn được đặc trưng bởi giá trị của trọng số thì được xác định dựa trên độ dài trung bình tương đối của mặt trên mỗi hướng. Bước 6: Áp đặt ràng buộc bất đẳng thức bổ sung cho mỗi nghiệm chấp nhận được và giải bài toán con Sub-Optimization bằng phương pháp tổng trọng số. Đối với nghiệm chấp nhận được các hàm chuẩn hóa thứ j, തܲ௝ , bài toán con Sub-Optimization được định nghĩa như sau: min [−൫ തܲ௝ − ݂̅ே൯.݂(̅ݔ)] Sao cho: ( തܲ௝ − ݂̅ே). (݂(̅ݔ)− ݂̅ே)| തܲ௝ − ݂̅ே|. |݂̅(ݔ)− ݂ே̅| = 1 (13) ℎത(ݔ) = 0 ݃̅(ݔ) ≤ 0 Trong đó: ݓ = −൫ തܲ௝ − ݂̅ே௔ௗ௜௥൯ :Giá trị trọng số. ℎത(ݔ) và ݃̅(ݔ) :Các vector ràng buộc đẳng thức và bất đẳng thức tương ứng. Chú ý rằng: điểm nadir chuẩn hóa - ݂̅ே là vector đơn vị. Tức là: ݂̅ே = (1,1, … ,1) Trang 38 Hình 10: Hình minh họa 3 chiều mô tả ràng buộc đẳng thức bổ sung cho quá trình mịnh hóa biên Pareto. Ràng buộc đẳng thức: ( തܲ௝ − ݂̅ே). (݂̅(ݔ)− ݂̅ே)| തܲ௝ − ݂̅ே|. |݂(̅ݔ) − ݂̅ே| = 1 Làm cho 2 vector ( തܲ௝ − ݂̅ே) và (݂̅(ݔ)− ݂̅ே) trở nên đồng tuyến tính. Do đó ràng buộc này đảm bảo rằng nghiệm đạt được chỉ nằm trên đường thẳng ( തܲ௝ − ݂̅ே) kết nối nghiệm chấp nhận được trên các “mảnh”mặt phẳng tuyến tính và điểm giả Nadir. Hàm mục tiêu −൫ തܲ௝ − ݂̅ே൯.݂(̅ݔ) là một hàm vô hướng cần được cực tiểu để xác định nghiệm gần điểm Utopia theo hướng của −൫ തܲ௝ − ݂̅ே൯ Nghiệm hiện tại có được sau khi chuẩn hoá thứ j, തܲ௝∗ sẽ khác với nghiệm chấp nhận được. Trong hình 10, vector തܲ௝ − ݂̅ே = (0,0,0) Bước 7: Mịn hóa biên Pareto. Trong phương pháp tổng trọng số chấp nhận được đối với bài toán 2 hàm mục tiêu, nghiệm tối ưu non-Pareto thì được loại bỏ một cách tự động nên việc lọc thì không cần thiết. Tuy nhiên theo phương pháp tổng trọng số chấp nhận được đa mục tiêu thì bất cứ nghiệm nào dựa trên ràng buộc đẳng thức đều chấp nhận được và nghiệm tối ưu non-Pareto có được. Trong mỗi bước, ta cần phải thực hiện việc mịn hóa biên Pareto để đạt được biên Pareto thực. Bước 8: Xóa nghiệm trùng nhau. Trang 39 Nhận dạng các đoạn (siêu phẳng) trên biên Pareto với tất cả nghiệm tối ưu Pareto kể cả nghiệm đã đạt được ở các bước trước. Nếu tiêu chuẩn cuối cùng được tìm thấy thì dừng ngược lại quay lại bước 5, một vài tiêu chuẩn dùng có thể được dùng là: i) Số pha đáp ứng yêu cầu. ii) Kích thước đoạn (mặt) trên biên Pareto lớn nhất tương ứng giá trị đã được chỉ định. iii) Độ lệch chuẩn giữa kích thước của tất cả các đoạn (mặt) trên biên Pareto tương ứng với giá trị đã được chỉ định. Trong phần trình bày này, số lượng lớn nhất của các pha thì được sử dụng như là tiêu chuẩn để kết thúc. Trang 40 2.5 Thuật toán di truyền tối ưu nhiều mục tiêu 2.5.1 Giới thiệu thuật toán di truyền (Genetic Algorithm) Ý tưởng thuật toán di truyền được đề xuất bởi John Holland vào những năm 1970. Lấy cảm hứng từ quá trình chọn lọc một cách ngẫu nhiên các cá thể thông qua sự tác động của môi trường tự nhiên. Nếu cá thể nào có mức độ thích nghi cao với sự tác động này thì chúng sẽ tiếp tục sống sót, ngược lại sẽ chúng sẽ bị loại bỏ. Ý tưởng này đã được áp dụng để giải quyết các bài toán tố