MỤC LỤC

Danh mục các ký hiệu

3

Mở đầu

5

CHƯƠNG I KIẾN THỨC CƠ SỞ

1.1 Quan hệ thứ tự trong không gian

7

1.2 Các định nghĩa

7

1.3. Giới thiệu bài toán tối ưu nhiều mục tiêu

12

1.4. Các khái niệm tối ưu

13

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

30

2.4.2 Các khái niệm cơ sở

32

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

34

2.5 Thuật toán di truyền tối ưu nhiều mục tiêu

40

2.5.1 Giới thiệu thuật toán di truyền (Genetic Algorithm)

40

2.5.2 Thuật toán di truyền

40

2.6 Thuật toán di truyền giải bài toán tối ưu nhiều mục tiêu

46

2.6.1 Thuật toán MOGA (Multi-Objective Genetic Algorithm)

46

2.6.2 Nghiệm ưu việt ( Elite)

48

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

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.

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