Chương 1 CƠ SỞ LÝ THUYẾT Chương này trình bày các kiến thức cơ sở về bài toán tối ưu, các phương pháp giải bài toán tối ưu đơn mục tiêu và đa mục tiêu. Ngoài ra, các nghiên cứu liên quan đến bài toán tối ưu thời gian sống của mạng cảm biến không dây cũng được trình bày.1 Bài toán tối ưu Trong thực tế, chúng ta thường gặp những vấn đề có nhiều cách giải quyết khác nhau. Một cách tự nhiên, những cách làm “tốt nhất” (hay còn gọi là cách làm tối ưu nhất) thường được lựa chọn, ví dụ như: nhanh nhất, chi phí rẻ nhất hoặc tốn ít nhân công nhất,. Trong khoa học máy tính, việc tìm lời giải “tốt nhất” trong một tập các lời giải khả thi cho một vấn đề nào đó được gọi là tối ưu hóa [13].
Trong nghiên cứu [13], các tác giả đã đưa ra một số cách phân loại bài toán tối ưu, một trong số đó là phân loại dựa vào số lượng mục tiêu. Theo cách phân loại này, bài toán tối ưu được phân thành hai loại: bài toán tối ưu đơn mục tiêu và bài toán tối ưu đa mục tiêu.1 Bài toán tối ưu đơn mục tiêu Bài toán tối ưu đơn mục tiêu được định nghĩa như sau: Định nghĩa 1.1) Ràng buộc: gi (x) ≤ 0 i = 1, ., xn ) với xk là các biến liên tục hoặc rời rạc, k = 1, 2,. ❼ f (x): Rn → R là hàm mục tiêu của bài toán. ❼ gi (x) ≤ 0 là các ràng buộc bất đẳng thức, q là số ràng buộc bất đẳng thức.
❼ hj (x) = 0 là các ràng buộc đẳng thức, p là số ràng buộc đẳng thức.2 Bài toán tối ưu đa mục tiêu Tối ưu đa mục tiêu (tối ưu Pareto) là tìm lời giải cho bài toán liên quan đến nhiều hơn một mục tiêu (tiêu chí) tối ưu. Các mục tiêu trong một bài toán được gọi là không xung đột nếu việc tối ưu một mục tiêu sẽ không ảnh hưởng đến các mục tiêu còn lại. Do đó, tập lời giải của bài toán tối ưu dạng này chỉ gồm một lời giải. Những bài toán tối ưu với các mục tiêu như vậy, người ta gọi là tối ưu đa mục tiêu tầm thường.
Ngược lại, nếu bài toán tối ưu với các mục tiêu xung đột nhau được gọi là tối ưu đa mục tiêu không tầm thường. Các mục tiêu được gọi là xung đột nếu việc tối ưu một mục tiêu sẽ làm giảm tính tối ưu của các mục tiêu khác. Tập lời giải của bài toán đa mục tiêu không tầm thường sẽ bao gồm nhiều lời giải khác nhau. Tùy vào mục đích, người quyết định có thể lựa chọn lời giải phù hợp.
Phần này sẽ trình bày tổng quan về bài toán tối ưu đa mục tiêu, các khái niệm trong tối ưu đa mục tiêu và các phương pháp thường được dùng để giải quyết bài toán tối ưu đa mục tiêu không tầm thường. Không mất tính tổng quát, giả sử rằng tất cả mục tiêu của bài toán tối ưu đa mục tiêu đều được cực tiểu hóa. Bài toán tối ưu m mục tiêu được định nghĩa như sau: Định nghĩa 1.5) Ràng buộc: gi (x) ≤ 0 i = 1, .7) xlk ≤ xk ≤ xuk k = 1, ., fm (x)) là véc tơ hàm mục tiêu., xn ) là véc tơ lời giải. Giá trị xlk là cận dưới và xuk là cận trên.
❼ gi (x) ≤ 0 là các ràng buộc bất đẳng thức, q là số ràng buộc bất đẳng thức ❼ hj (x) = 0 là các ràng buộc đẳng thức, p là số ràng buộc đẳng thức.1 Không gian thiết kế và không gian mục tiêu Định nghĩa 1. Không gian thiết kế Ω ∈ Rn của bài toán MOO là tập các véc tơ x thỏa mãn các ràng buộc 1.8 của bài toán.1: Minh họa hai hàm mục tiêu f1 , f2 trong không gian thiết kế [14]. Đường biểu diễn hai hàm mục tiêu lần lượt là các đường tròn có tâm tại (0, 0) và (2, 0). Không gian thiết kế của bài toán này là: Ω = {x ∈ R2 |x1 ≥ 0, x2 ≥ 0}.
Đây chính là góc phần tư thứ nhất trong hình 1. Hàm f1 đạt cực tiểu tại điểm O(0, 0), hàm f2 đạt cực tiểu tại điểm B(2, 0). Tuy nhiên, f2 (O) = 4 và f1 (B) = 4 không phải là điểm cực tiểu. Như vậy, không có một điểm nào làm cho f1 và f2 cùng đạt cực tiểu.
Có thể thấy rằng bất cứ một điểm nào nằm ngoài đường thẳng nối giữa hai điểm O và B (có nghĩa là x2 = 0 và x1 ∈ / (0, 2)) đều không thể làm giảm giá trị cả hai hàm mục tiêu một cách đồng thời. Ví dụ, tại điểm C(3, 0), f1 (C) = 9 và f2 (C) = 1. Ngược lại, bất cứ một lời giải nào nằm giữa hai điểm O và B đều được coi là chấp nhận được vì không thể thực hiện việc giảm giá trị một hàm mục tiêu mà không làm tăng giá trị của hàm mục tiêu còn lại. Do đó, lời giải tối ưu của bài toán là Sp = {x ∈ R2 |0 ≤ x1 ≤ 2, x2 = 0}.
Đối với một bài toán đơn giản như trong ví dụ 1, tập lời giải tối ưu có thể được tìm thấy dễ ràng trong không gian thiết kế. Tuy nhiên, đối với nhiều bài 10 toán khó, việc tìm tập lời giải tối ưu không hề đơn giản. Việc sử dụng không gian thiết kế là không đủ để tìm ra tập lời giải tối ưu. Để hiểu khái niệm bài toán đa mục tiêu và các kỹ thuật giải, bài toán sẽ phải được chuyển sang một không gian mới gọi là không gian mục tiêu (criterion space/ objective space).
Định nghĩa về không gian mục tiêu được đưa ra như sau: Định nghĩa 1. Không gian mục tiêu được định nghĩa là tập của các giá trị hàm mục tiêu tương ứng với các điểm trong không gian thiết kế. Bài toán đa mục tiêu trong ví dụ 1 có thể được biểu diễn trong không gian mục tiêu như trong hình 1.2(b) với các trục là các hàm mục tiêu. Các ràng buộc ban đầu của bài toán được chuyển sang không gian mục tiêu bằng cách giải x1 và x2 theo f1 và f2 như trong phương trình (1.
Không gian mục tiêu Z của bài toán này được định nghĩa trong phương trình (1.13) là tập các giá trị các hàm mục tiêu tương ứng với các điểm khả thi trong không gian thiết kế: Z = {F(x)|x ∈ Ω}.13) Như trong hình 1.2(a), các điểm O, A, B trong không gian thiết kế sẽ được ánh xạ thành các điểm o, a, b trong không gian mục tiêu. Tập các lời giải tối ưu trong không gian thiết kế là Sp , được chuyển thành đường cong Zp trong p không gian mục tiêu, Zp = {F = (f1 , f2 ) ∈ R2 |0 ≤ f1 ≤ 4, 0 ≤ f2 ≤ 4, f1 − x21 = p f1 − (0. Đường cong Zp trong không gian mục tiêu biểu diễn các lời giải tối ưu của bài toán tối ưu đa mục tiêu. Từ không gian mục tiêu trong hình 1.
Hơn nữa, mỗi một mục tiêu f1 , f2 không thể giảm hơn nữa mà không làm tăng giá trị của hàm mục tiêu còn lại tại bất cứ một điểm nào trên đường cong Zp. Đối với mỗi điểm không thuộc đường cong Zp , ví dụ như điểm d(4, 4), có thể giảm 11 đồng thời giá trị của hai hàm mục tiêu bằng cách di chuyển điểm đó gần về phía đường cong này. Cần lưu ý rằng, mỗi điểm trong không gian thiết kế có thể ánh xạ tới một điểm trong không gian mục tiêu. Tuy nhiên, điều ngược lại có thể không đúng; nghĩa là mọi điểm trong không gian mục tiêu không nhất thiết phải tương ứng với các điểm hoặc một điểm duy nhất trong không gian thiết kế.2, điểm e(0, 0) trong không gian mục tiêu không ánh xạ đến bất cứ một điểm nào trong không gian thiết kế.
Điểm d(4, 4) trong không gian mục tiêu ánh xạ đến 2 √ √ điểm D1 (1, 3) và D2 (1, − 3) trong không gian thiết kế, D1 ∈ Ω và D2 ∈ / Ω. (a) Không gian thiết kế (b) Không gian mục tiêu Hình 1.2: Minh họa không gian thiết kế và không gian mục tiêu [14].2 Tối ưu Pareto Việc xác định các lời giải cho bài toán MOO được gọi là tối ưu Pareto. Một điểm x∗ trong không gian thiết kế Ω được gọi là tối ưu Pareto (Pareto optimal ) nếu không có điểm nào khác trong Ω làm giảm tại ít nhất một mục tiêu mà không làm tăng các mục tiêu khác. Tối ưu Pareto được định nghĩa một cách tường minh như sau: Định nghĩa 1.
Một điểm x∗ ∈ Ω được gọi là tối ưu Pareto nếu và chỉ nếu không tồn tại một điểm x trong không gian thiết kế Ω mà fi (x) ≤ fi (x∗ ) với mọi i và fi (x) < fi (x∗ ) với ít nhất một mục tiêu i, i = 1,. Để minh họa cho định nghĩa 1.5, giả sử rằng x∗ = (3, 0) được gọi là tối ưu Pareto (đây chính là điểm C trong hình 1. Tại điểm này, f1 (x∗ ) = 9 và f2 (x∗ ) = 1. Có 12 nhiều điểm x thỏa mãn điều kiện F(x) ≤ F(x∗ ) và fi (x) < fi (x∗ ) với ít nhất một mục tiêu i.
Do đó từ định nghĩa 1.5, điểm x∗ = (3, 0) không là tối ưu Pareto. Mặt khác, nếu chọn x∗ = (1, 0) (điểm A), f1 (x∗ ) = 1 và f2 (x∗ ) = 1, không tồn tại bất cứ một điểm nào mà f1 và f2 nhỏ hơn hoặc bằng giá trị của nó tại điểm (1, 0). Do đó, x∗ = (1, 0) được gọi là tối ưu Pareto. Một véc tơ của các mục tiêu F∗ = F(x∗ ) ∈ Z là không bị trội nếu và chỉ nếu không tồn tại một véc tơ F ∈ Z mà fi (x) ≤ fi (x∗ ) ∀i và fi (x) < fi (x∗ ) với ít nhất một i.
Ngược lại, F∗ là bị trội. Nói một cách khác, một nghiệm x∗ được gọi là trội so với nghiệm x, nếu hai điều kiện sau đây được thỏa mãn: ❼ Nghiệm x∗ không xấu hơn nghiệm x trong tất cả các giá trị của hàm mục tiêu, tức là fi (x∗ ) ≤ fi (x) với mọi i = 1, 2,. ❼ Nghiệm x∗ tốt hơn nghiệm x trên ít nhất một mục tiêu, tức là fi (x∗ ) < fi (x) trên ít nhất một i. Nếu hai điều kiện trên bị vi phạm, ta nói nghiệm x∗ không trội so với nghiệm x.
Là tập bao gồm tất cả các lời giải không bị trội bởi bất cứ một lời giải nào P = {x ∈ Ω|¬∃x′ ∈ Ω, F(x′ ) F(x)} (1.
