Trang 2
2.6.3 Tập lưu trữ nghiệm ưu việt (External)
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
2.8. Giải bài toán với thuật toán SPEA2
60
2.9 Tính toán số
63
CHƯƠNG III ỨNG DỤNG THUẬT TOÁN DI TRUYỀN
TỐI ƯU NHIỀU MỤC TIÊU GIẢI BÀI TOÁN
QUẢN LÝ DANH MỤC ĐẦU TƯ
3.1 Mô hình quản lý danh mục đầu tư
66
3.1.1 Giới thiệu danh mục đầu tư
66
3.1.2 Mô hình toán học
67
3.2 Quản lý tối ưu danh mục đầu tư với chi phí giao dịch cố định
77
3.2.1 Giới thiệu mô hình
77
3.2.2 Mô hình toán học
78
3.2.3 Thuật toán di truyền dựa trên thuật toán NSGA-II
80
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
2
(x)) : Vector hàm mục tiêu.
x = (x
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
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: =
+
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
: 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
Γ ∈
: Ma trận hiệp phương sai của
.
, : 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 3
Danh mục các ký hiệu
f = (f
1
(x),f
2
(x)) : Vector hàm mục tiêu.
x = (x
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
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: =
+
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
: 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
Γ ∈
: Ma trận hiệp phương sai của
.
, : 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ư:
kỹ thuật công nghệ, hàng không, thiết kế, tài chính,…
Tối ưu hóa nhiều mục tiêu có nghĩa là tìm phương án tốt nhất theo một nghĩa nhất định
nào đó để đạt được (cực đại hay cực tiểu) nhiều mục tiêu cùng một lúc và một phương án như
vậy thì ta gọi là phương án lý tưởng. Trong một bài toán tối ưu nhiều mục tiêu thường thì các
mục tiêu xung đột với nhau nên việc cố gắng làm “tăng” giá trị cực đại hay cực tiểu một mục
tiêu có thể sẽ làm “giảm” gía trị cực đại hay cực tiểu của các mục tiêu khác nên việc tồn tại
phương án lý tưởng là rất hiếm. Vì vậy cách tốt nhất là tìm một phương án nhằm thỏa mãn tất
cả các yêu cầu các mục tiêu trong một mức độ chấp nhận được và phương án như thế gọi là
phương án thỏa hiệp của các hàm mục tiêu.
Có rất nhiều định nghĩa khác nhau đề cập đến phương án/nghiệm tối ưu như: Pareto,
Borwein, Benson, Geoffrion, Kuhn – Tucker,…Các định nghĩa này thường có sự tương quan
với nhau và chúng được biểu hiện cụ thể thông qua các định lý, mệnh đề và tính chất.
Như chúng ta đã biết một trong những cơ sở để định nghĩa về nghiệm tối ưu là quan hệ
thứ tự trong không gian nhất là quan hệ hai ngôi. Chương I trong luận văn này sẽ trình bày
những khái niệm và các vấn đề liên quan đến quan hệ thứ tự hai ngôi trong không gian, tập
hợp. Đồng thời phát biểu các dạng của bài toán tối ưu nhiều mục tiêu và giới thiệu một số khái
niệm về nghiệm tối ưu, nghiệm tối ưu chặt, yếu, nghiệm tối ưu chính thường theo định nghĩa
Pareto, Borwein, Benson, Geoffrion, Kuhn – Tucker và một số định lý để cho thấy mối liên hệ
giữa chúng.
Trang 6
Chương II là chương giới thiệu các phương pháp mới để giải bài toán tối ưu nhiều mục
tiêu bên cạnh các phương pháp thông dụng như phương pháp ràng buộc, phương pháp tổng
trọng số chúng tôi sẽ trình bày một lớp các phương pháp và thuật giải chính như sau:
Một là: Phương pháp tổng trọng số chấp nhận được cho bài toán hai và nhiều mục tiêu.
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.
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ỳ.
=
{
(
,
)
|
∈ ; ∈ }
Một cách tổng quát, một quan hệ n ngôi là một tập hợp bất kỳ của các bộ n-thứ tự từ n
tập hợp.
Chúng ta chỉ xét trường hợp đơn giản nhất là quan hệ hai ngôi trên một tập hợp. Điều
này có nghĩa là tập hợp của các cặp có thứ tự, ứng với các phần tử của mỗi cặp là thuộc cùng
một tập hợp A.
Định nghĩa 1:
Quan hệ hai ngôi trên tập A là tập hợp con R của . Ta gọi đơn giản là quan hệ hai
ngôi.
Ký hiệu: aRb hoặc R(a,b) hoặc (a,b) ∈ R gọi là "a R-quan hệ b"
Ví dụ 1.2: xét tập hợp S = {1, 2, 3, 4, 5, 6, 7, 8} thì quan hệ “ < ” tập hợp của các cặp có thứ
tự:
{(1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(1,8),(2,3),
(
2,4
)
,
(
2,5
)
,
(
2,6
)
,
(
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
:×→ {,}
Định nghĩa 2:
Quan hệ ngược là một quan hệ 2 ngôi R:AxB được xác định bởi:
∶≡
{
(
,
)
|
(
,
)
}.
Ví dụ 1: <
= {(,) | <} = {(,) | >} = >.
Ví dụ 2: Nếu xét quan hệ R: “Người” x “ăn” được định nghĩa bởi:
a R b a ăn b,
b R
−1
a b thì được ăn bởi a
Định nghĩa 3: Cho R là một quan hệ 2 ngôi trên tập A, khi đó R gọi là:
i. Phản xạ nếu (a, a) ∈ R, ∀ ∈ ( hoặc là
() )
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ụ 5: Quan hệ “ = ” là đối xứng.
iv. Phản xứng nếu ∀, ∈ sao cho
(
,
)
∈ ⟹
(
,
)
∉
Ví dụ 6: Quan hệ “ < ” là phản xứng.
v. Phi đối xứng nếu ∀, ∈ sao cho
(
,
)
∈ à
(
,
)
∈ ⟹ =
Ví dụ 7: các quan hệ , , là Phi đối xứng
vi. Bắc cầu 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 ≠ ⟹
(
,
)
∈ hoặc
(
,
)
∈
Ví dụ 11: cho A = là tập các số chẳn. thì quan hệ chia hết là liên hợp.
x. Liên hợp mạnh nếu ∀,∈ ⟹
(
,
)
∈ hoặc
(
,
)
∈
Ví dụ 12 : Cho A = N. Thì quan hệ >, <,…là liên hợp mạnh.
Định lý 4: R là đối xứng khi và chỉ khi R = R
−1
,
Chứng minh:
Giả sử R là đối xứng. Thì:
(x,y) R (y,x) R (x,y) R
−1
Giả sử R = R
−1
Thì:
(x,y) R (x,y) R
−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.
Không có nhận xét nào:
Đăng nhận xét