ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
*** ***
LÊ VĂN HIỆP
MỘT LỚP CÁC PHƯƠNG PHÁP
GIẢI BÀI TOÁN TỐI ƯU NHIỀU MỤC TIÊU
LUẬN VĂN THẠC SĨ TOÁN HỌC
Chuyên ngành Lý Thuyết Tối Ưu Và Hệ Thống
THÀNH PHỐ HỒ CHÍ MINH
NĂM 2009
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
*** ***
LÊ VĂN HIỆP
MỘT LỚP CÁC PHƯƠNG PHÁP
GIẢI BÀI TOÁN TỐI ƯU NHIỀU MỤC TIÊU
Chuyên ngành: Lý thuyết tối ưu và hệ thống
Mã số: 60 46 20
LUẬN VĂN THẠC SĨ TOÁN HỌC
Người hướng dẫn khoa học:
PGS.TS Trần Thị Huệ Nương
THÀNH PHỐ HỒ CHÍ MINH
NĂM 2009
LỜI CÁM ƠN
Lời trước tiên trong luận văn này tôi muốn gửi lời cám ơn chân thành nh ất đến
PGS.TS Trần Thị Huệ Nương - người đã tận tình giúp đỡ và chỉ dẫn tôi rất nhiều để
hoàn tất luận văn này.
Tôi xin cám ơn Th.S Nguyễn Thành Ngọc Bảo đã hỗ trợ tôi hoàn thiện luận văn
này. Đồng thời tôi cũng xin gửi lời cám ơn chân thành nh ất của tôi đến với ba má và anh
chị trong gia đình đã đôn đốc và hỗ trợ về mặt tinh thần cho tôi trong quá trình th ực hiện
luận văn này.
1.4.1 Tối ưu Pareto
13
1.4.2 Nghiệm tối ưu Pareto chặt và yếu
15
1.4.3 Nghiệm tối ưu Pareto chính thường và điểm hữu hiệu chính thường
17
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
24
2.2 Phương pháp tổng trọng số
25
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
26
2.3.1 Khái niệm cơ sở
26
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
28
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
30
2.4.1 Giới thiệu phương tổng trọng số chấp nhận được
49
2.6.3.1 Thuật toán SPEA
49
2.6.3.2 Thuật toán SPEA2
50
2.6.3.3 Thuật toán NSGA (
Nondominated Sorting Genetic Algorithm )
53
2.6.3.4
Thuật toán NSGA-
II
55
2.6.4
Khoảng cách quy tụ
56
2.6.5
Thuật toán tính khoảng cách quy tụ
58
2.7 So sánh ưu điểm và khuyết điểm của các thuật toán di truyền đa mục tiêu
59
3.2.4 Thuật toán GA dựa trên NSGA-II và Genocop
82
3.3 Quản lý và tối ưu danh mục đầu tư với chi phí giao dịch biến đổi
86
3.3.1 Giới thiệu quản lý và tối ưu danh mục đầu tư với chi phí giao dịch biến đổi
86
3.3.2 Quản lý danh mục đầu tư nhiều mục tiêu
87
3.3.3 Áp dụng thuật toán di truyền vào bài toán quản lý danh mục đầu tư
90
3.3.4 Chiến lược tiến hóa
92
Kết luận
96
Tài liệu tham khảo
98
Trang 3
Danh mục các ký hiệu
f = (f
1
(x),f
, ∆x
: Kích thước của lưới
f(x,p) : Hàm mục tiêu của vector x và vector tham số cố định p
p : Vector các tham số cố định
g(x,p) : Vector ràng buộc bất đẳng thức với tham số p
h(x,p) : Vector ràng buộc đẳng thức với tham số p
, : Vector trọng số
̅
: Hàm mục tiêu được chuẩn hóa
: Điểm utopia
: Điểm nadir
∗
: Điểm anchor thứ i
N
E
: Số lượng lớn nhất mà tập E có thể chứa được các nghiệm không trội.
N
P
: Số lượng cá thể trong quần thể/kích thước tập P.
k : Tham số của mật độ tính toán: =
: Lợi nhuận khi đầu tư vào loại chứng khoán thứ i, ∈ .
=
= (
) : Kỳ vọng của
.
: Phương sai của
: Hiệp phương sai giữa
à
.
: Vector giá trị kỳ vọng của
Γ ∈
1
,…,x
n
) : Vector biến quyết định
n
i
: Số lượng đoạn cần mịn hóa thứ i
l
i
: 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.
P
1
, P
2
: Điểm cuối của đoạ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
n
u
: Số nghiệm trội hơn nghiệm
u
S
u
: Tập nghiệm trội bởi nghiệm u
P
0
, P
t
: Quần thể ban đầu và tại thế hệ thứ t
Q
t
: Quần thể con tạo thành từ các cá thể trong P
t
Trang 4
F
j
: Biên chứa các nghiệm không trội. Với j=1,…,R
, : Tập các chứng khoán mà các nhà đầu tư định đầu tư vào với số vốn là C.
: Số lượng tối thiểu của loại cổ phiếu thứ j.
: Chi phí tương ứng có liên quan với loại chứng khoán thứ j
: Giá của loại chứng khoán thứ j tại thời điểm niêm yết trên sàn giao dịch.
: Giá mua thấp nhất cho loại chứng khoán j.
(
), () : Kỳ vọng về lợi nhuận của danh mục đầu tư.
() : Rủi ro của danh mục đầu tư được tính bằng phương sai .
Trang 5
MỞ ĐẦU
Trong cuộc sống, một cá nhân, hay một tổ chức thường bị đặt vào tình huống phải lựa
chọn phương án tối ưu để giải quyết một vấn đề nào đó. Khi ấy chúng ta phải tiến hành thu
thập, phân tích và chọn lựa thông tin nhằm tìm ra một giải pháp tốt nhất để hành động. Các
phương án đề xuất ấy có thể giải quyết một hay nhiều vấn đề cùng một lúc tùy thuộc vào tình
huống và yêu cầu đặt ra của chúng ta. Trong toán học có rất nhiều lý thuyết cơ sở làm nền tảng
giúp tìm ra một phương án tối ưu để giải quyết vấn đề như: lý thuyết thống kê, lý thuyết quyết
định, lý thuyết tối ưu, vận trù học,… Do tính ưu việt và hiệu quả, tối ưu hóa nhiều mục tiêu là
một trong những lý thuyết toán học ngày càng được ứng dụng rộng rãi trên nhiều lĩnh vực như:
Hai là: Dùng ý tưởng từ thuật toán di truyền để giải bài toán tối ưu nhiều mục tiêu bao
gồm cách thuật toán chính yếu: MOGA, SPEA2, NSGA-II. Cách thức tìm nghiệm của các
thuật toán này là từ các nghiệm được khởi tạo một cách ngẫu nhiên ban đầu qua đó thuật toán
sẽ tìm nghiệm tối ưu Pareto thông qua việc tìm biên Pareto xấp xỉ của bài toán.
Ngoài ra chương II cũng minh họa thêm hình ảnh và tính toán số trong Matlab để giải
bài toán tối ưu nhiều mục tiêu bằng hai thuật toán SPEA2, NSGA-II.
Chương III sẽ trình bày nội dung ứng dụng thực tế của các thuật giải di truyền nhằm giải
quyết một dạng bài toán thực tiễn đó là bài toán lựa chọn danh mục đầu tư tối ưu nhiều mục
tiêu với hai mô hình: Mô hình lựa chọn danh mục đầu tư tối ưu với chi phí cố định và mô hình
lựa chọn danh mục đầu tư tối ưu với chi phí biến đổi.
Trang 7
CHƯƠNG I: KIẾN THỨC CƠ SỞ
1.1 Quan hệ thứ tự trong không gian.
Trong Toán học, quan hệ hai ngôi là sự kết hợp hai phần tử bất kỳ trong cùng một tập
hợp hoặc với các phần tử của tập hợp khác. Quan hệ hai ngôi được sử dụng trong nhiều nhánh
khác nhau của toán học như trong số học ta có các quan hệ: lớn hơn hoặc bằng, bằng… Trong
hình học ta có các quan hệ: đồng dạng, đối xứng, song song,… Trong lý thuyết đồ thị ta có các
quan hệ: kề nhau, liên thông,...Quan hệ hai ngôi cũng được sử dụng trong khoa học máy tính,
nhất là trong các mô hình quan hệ cơ sở dữ liệu như: các quan hệ: một – nhiều, nhiều – nhiều.
Trong lý thuyết tối ưu nhiều mục tiêu quan hệ thứ tự hai ngôi có ý nghĩa rất quan trọng
trong việc đưa ra các khái niệm về nghiệm tối ưu. Thông qua các khái niệm này ta lựa chọn
nghiệm nào là nghiệm tốt nhất cho bài toán.
1.2 Các định nghĩa
Xuất phát từ khái niệm tích Đề-cát của hai tập hợp là một tập hợp các cặp có thứ tự của
hai tập hợp A, B bất kỳ.
)
,
(
2,7
)
,
(
2,8
)
,
(
3,4
)
,
(
3,5
)
,
(
3,6
)
,
(
3,7
)
,(3,8),(4,5),(4,6),(4,7),(4,8),(5,6),(5,7),(5,8),(6,7),(6,8),(7,8)}
Trang 8
Quan hệ hai ngôi R tương ứng với hàm đặc trưng
() )
Ví dụ 3: Các quan hệ =, `có cùng tính chất toán học’,
<=,>=,
,
,… là phản xạ
ii. Phi phản xạ nếu
(
,
)
∉, ∀ ∈ hoặc là
(
)
Ví dụ 4: Quan hệ <, >, ‘có tính chất toán học khác nhau’, là phi phản xạ.
iii. Đối xứng nếu ∀, ∈ sao cho
(
,
)
∈ ⟹
(
,
)
∈
(
,
)
∈
Ví dụ 8: Quan hệ “ ≥, <, >, = “ là bắc cầu.
vii. Phủ định bắc cầu nếu ∀,, ∈ sao cho
(
,
)
∉ à
(
,
)
∉
⟹
(
,
)
∉
Ví dụ 9: Nếu “ chó sói ăn cừu ” và “ cừu ăn cỏ ” nhưng “ sói không ăn cỏ ” thì quan
hệ “ ăn ” là phủ định và bắc cầu
viii. Phản bắc cầu nếu: ∀,,∶
⋀
⟹ ¬
Trang 9
Ví dụ 10: Nếu “ A quen B “ và “ B quen C “ nhưng “ A chưa chắc quen C “ thì quan hệ
“quen” là phản bắc cầu
ix. Liên hợp nếu ∀,∈ sao cho ≠ ⟹
(
−1
(y,x) R
Định nghĩa 5: Cho R là một quan hệ 2 ngôi trên A khi đó:
i. R được gọi là quan hệ tương đương nếu R có tính chất phản xạ, đối xứng và bắc
cầu.
ii. R được gọi là tiền thứ tự nếu R có tính chất phản xạ và bắc cầu.
Ví dụ 13: =; “các tập tương đương”; “chia hết”; mod…
Trong trường hợp quan hệ R là tiền thứ tự thì cặp (A,R) được gọi là tập tiền thứ tự.
Để tiện ta thay đổi quan hệ R là ≼ . Do đó ta quy ước viết:
≼ thay cho (a, b) ∈ ≼
⋠ thay cho (a, b) ∉ ≼
với bất kỳ một quan hệ ≼ là tiền thứ tự nào thì cũng có quan 2 quan hệ khác mà ta định nghĩa
chúng như sau:
≺ ⟺ ≺ à ≰ (1.9)
~ ⟺ ≼ à ≼ (1.10)
Mệnh đề 6: Cho ≼ là một tiền thứ tự trên tập A. Khi đó:
Quan hệ ≺ định nghĩa trong (1.9) là phi phản xạ và bắc cầu.
Quan hệ ~ định nghĩa trong (1.10) là quan hệ tương đương.
Trang 10
Mệnh đề 7:
Một quan hệ hai ngôi phản xứng là phi phản xạ.
Một quan hệ hai ngôi bắc cầu và phi phản xạ là phản xứng.
Định nghĩa 8: Một quan hệ hai ngôi ≼ trên A là:
Tiền thứ tự tổng quát nếu ≼ là phản xạ, bắc cầu và liên hợp.
Thứ tự tổng quát nếu ≼ là tiền thứ tự tổng quát phi đối xứng. Như quan hệ ≤
đối với số nguyên là thứ tự tổng quát.
Thứ tự yếu chặt nếu ≼ là phản xứng và phủ định bắc cầu.
Mệnh đề 9:
với i= 1,..,n
Nếu
≤
với i= 1,..,n; ≠
Nếu
<
với i= 1,..,n
Nếu
<
hoặc x = y
Nếu max
,…,
{
}≤ max
,…,
{
}
Thứ tự từng phần yếu
Thứ tự từng phần
Thứ tự từng phần chặt
Thứ tự tự điển
+(1−
)∈ với mọi
,
∈ và 0 < < 1
Nhọn nếu
∩
(
−
)
⊂ {0}
Mệnh đề 14: Cho một quan hệ thứ tự ≼ trên
, ta định nghĩa tập:
≼
=
{
−
|
≼}
Khi đó
≼
là nón.
Chứng minh:
Cho ∈
≼
≼
(ii): Giả sử quan hệ ≼ là Bắc cầu và Cho ,∈
≼
Nên: −0∈
≼
và 0−∈−
≼
Điều này có nghĩa là: 0≼ và −≼ 0 .Mà ≼ là Bắc cầu ⟹−≼
Do đó: − = +∈ tức là K lồi
(iii): Giả sử ta có 0≠∈
≼
.
Thì =−∈
≼
và – =−∈
≼
với ,∈
Do 0≠ nên ≼ và ≼ nhưng ≠. Điều này vô lý.
Trang 12
Định nghĩa 16: Cho K là nón. Ta định nghĩa thứ tự theo nón ≼
là:
≼
≼
Và ≼
nghĩa là: − =
(
+
)
−(+)
Do đó:
(
+
)
≼
(+)
(1). Cho ∈
. Khi đó − = 0∈⟺ ≼
(2). Cho ≼
và ≼
khi đó : −∈ và −∈
Do K lồi nên: −+− =−∈
≼
}
(P
)
Sao cho: ∈
Trong đó:
x là biến quyết định.
=
{
∈ R
|
(
)
≤ 0; ℎ
(
)
= 0 với = 1,…, < } là không gian quyết định.
f
i
: R
n
R với i = 1,…, k là các hàm mục tiêu.
(
)
∀∈ , = {1,…}
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 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.
Định nghĩa 19: Một nghiệm = (
,
,…,
) được gọi là trội hơn nghiệm =
(
,
,…,
) ký hiệu là: ≤ , nếu:
(
)
≤
được gọi là nghiệm không trội hơn nghiệm
=
(
,
,…,
)
nếu:
∀∈, ∄∈ ℎ: ≻
1.4 Các khái niệm tối ưu.
1.4.1 Tối ưu Pareto:
Định nghĩa 21:
Một điểm
∗
∈ được gọi là một nghiệm tối ưu Pareto nếu không tồn tại một nghiệm
≠
∗
∈ sao cho x trội hơn
∗
. Nghĩa là:
(
)
<(
∗
)
trội hơn
(
)
3. Tập tất cả các nghiệm tối ưu Pareto
∗
∈ và tập các điểm hữu hiệu.
=(
∗
)∈ lần lượt là:
và
Định nghĩa 23: Các định nghĩa tương đương khác. x
*
là nghiệm tối ưu Pareto nếu:
1. Không tồn tại một nghiệm ∈ sao cho: f(x) trội hơn f(x
*
)
2. Không tồn tại một nghiệm ∈ sao cho:
(
)
−
(
∗
)
−
)
={
(
∗
)
}
5. Không tồn tại ()∈
(
)
\{
(
∗
)
} sao cho:
(
)
∈
(
∗
)
1.4.2 Nghiệm tối ưu Pareto chặt và yếu.
Hình 3a Minh hoạ cho định
nghĩa: 1, 4 và 5
Hình 3b Minh hoạ cho định
nghĩa: 2 và 3
(
∗
)
()
()
(
∗
−
)
−
(
∗
)
∈ gọi là điểm hữu hiệu yếu.
Tập nghiệm tối ưu Pareto yếu và tập các điểm hữu hiệu yếu lần lượt ký hiệu là:
và
Định nghĩa 25:
Nghiệm
∗
∈ được gọi là một nghiệm tối ưu chặt Pareto nếu không tồn tại một
nghiệm ∈ và ≠
∗
sao cho:
(
)
≤
(
∗
)
.
Khi đó: Tập nghiệm tối ưu Pareto chặt ký hiệu là:
)
≤(
)} được gọi là tập mức của tại
ii.
(
(
)
)
=
{
∈
|
(
)
=(
)} được gọi là mặt mức của tại
iii.
(
.
Nhận xét: Từ định nghĩa ta nhận thấy:
(
(
)
)
⊂
(
(
)
)
Định lý 27: Cho
∗
∈ và định nghĩa
=
(
∗
) khi đó:
i.
∗
là nghiệm tối ưu Pareto chặt nếu và chỉ nếu:
)
Trang 16
iii.
∗
là nghiệm tối ưu Pareto yếu nếu và chỉ nếu:
(
) =∅
Chứng minh:
(1): “
∗
là nghiệm tối ưu Pareto chặt ”
không tồn tại một nghiệm ∈ và ≠
∗
sao cho:
(
)
≤
(
∗
)
⟺
(
) ={
∗
}
(2): ”
∗
là nghiệm tối ưu Pareto: “
không tồn tại một nghiệm ∈ sao cho:
(
)
<
(
∗
)
với = 1,
và
(
) =
(
)
(3):”
∗
là nghiệm tối ưu Pareto yếu”
không tồn tại một nghiệm ∈ sao cho:
(
)
<
(
∗
)
với =1,k
Sự thỏa hiệp giữa các tiêu chuẩn này được đo bằng cách tính toán việc giảm giá trị của hàm
mục tiêu
trên đơn vị tăng về mặt giá trị của hàm mục tiêu
.
Định nghĩa 28: (Geoffrion 1986)
∗
∈ được gọi là tối ưu Pareto chính thường theo Geoffrion nếu
∗
là nghiệm tối ưu
Pareto và nếu có một số M > 0 sao cho: mỗi à ∀ ∈ thỏa mãn
(
)
<
(
∗
)
và tồn
tại một chỉ số j sao cho
(
∗
)
∗
là:
∗
=
(
∗
)
gọi là điểm hữu hiệu
chính thường.
Nhận xét: Một nghiệm tối ưu Pareto chính thường có biên thỏa hiệp giữa tất cả các hàm mục
tiêu.
Ta xét bài toán lồi sau đây:
min
∈
(
)
(
)
Thì (
) gọi là bài toán trọng tổng số.
Cho
∗
là nghiệm tối ưu Pareto của bài toán (
). Để thấy rằng
∗
là nghiệm tối ưu Pareto ta
giả sử rằng tồn tại
∈ với
(
)
<
(
∗
)
>0 với = 1,…, và
(
)
−
(
có một sự thỏa hiệp lớn hơn M dẫn đến sự mâu thuẫn vối tính tối ưu của
∗
đối với bài toán
tổng trọng số. Cho
= (−1)max
,
Giả sử
∗
không là nghiệm tối ưu Pareto chính thường. Tức là tồn tại một i và ∈ sao cho
(
∗
)
<
(
)
và
(
∗
Do đó:
(
∗
)
−
(
)
>
(
)
−
(
∗
)
≠ bằng cách chọn M.
Nhân hai vế của bất đẳng thức trên với
∗
)
⟹
(
∗
)
−
(
)
>
(
)
−
)
+
(
)
Trang 19
(
∗
)
>
(
=1 và ∀∈ thỏa mãn:
ℎ
(
)
≥ 0
Định lý 31 (Geoffrion 1968):
Cho ⊂
là một tập lồi và giả sử rằng
: ⟶ là ánh xạ lồi. Khi đó
∗
∈ là
nghiệm tối ưu Pareto chính thường nếu và chỉ nếu
∗
là nghiệm tối ưu đối với bài toán (∗) với
.
> 0 với = 1,k
Chứng minh:
(
)
−
(
∗
)
≤⟺
(
)
+
(
)
<
(
∗
)
+
(
(
)
+
()
≥
(
∗
)
+
(
∗
)
+
(
∗
)
≥
(
∗
)
+
(
∗
)
+
(
∗
)
(
∗
)
⟺
(
)
+
(
)
≥
(
∗
)
+
)
+
(
∗
)
⟹ 1+
(
)
≥1+
1. Nón tiếp xúc của Y tại y là:
(
)
=
{
∈
|
∃
(
)
⊂ ℎ
(
→
)
và
(
−
)
)
= {0}
Định nghĩa 34 (Benson 1979):
Nghiệm ∈ được gọi là nghiệm tối ưu Pareto chính thường nếu:
(+
−
(
)
∩
(
−
)
= {0}
Copyright: Tài liệu đại học ©