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

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.

pdf104 trang | Chia sẻ: lvcdongnoi | Lượt xem: 5791 | Lượt tải: 1download
Bạn đang xem trước 20 trang tài liệu 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, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
nhà đầu tư sẽ muốn cực đại lượng tiền mặt nhận được một cách chắc chắn, đây là lý do căn bản trực tiếp dẫn đến khả năng tất định tương đương (a). Tung một đồng xu cho đến khi mặt của nó là: “xấp”. Các tay chơi cá cược sẽ nhận được 1 đồng nếu khi tung đồng xu lần đầu là mặt “xấp”. 2 đồng nếu qua 2 lần tung đồng xu thì được mặt “xấp”, 4 đồng nếu qua 3 lần tung đồng xu thì được mặt “xấp”, một cách tổng quát là sẽ được 2h-1 đồng nếu qua h lần tung đồng xu thì được mặt “xấp”. Giá trị kỳ vọng của cuộc cá cược là không xác định, nhưng trong thực tế nhiều tay cá cược sẽ sẵn lòng chấp nhận chỉ với một lượng nhỏ khi cá cược. Do đó, Bernoulli đề nghị không so sách kết quả bằng tiền mặt mà so sánh thông qua tính “lợi ích” của tiền mặt. Hàm lợi ích của tiền mặt được xác định như sau: ܷ ∶ ܴ  ܴ Do đó chúng ta có: ܷ(ܥܧ) = ܧ[ܷ(ݎ௣)] Điều này có nghĩa là lợi ích của CE bằng kỳ vọng lợi ích của danh mục đầu tư ngẫu nhiên. Nhà đầu tư hy vọng cực đại U(CE), điều này dẫn đến bài toán cơ sở Bernoulli nhằm cực đại lợi ích mong đợi như sau: ܯܽݔ {ܧൣܷ൫ݎ௣൯൧} (2) ݏܽ݋ ܿℎ݋ ݔ ∈ ܵ Hàm U rõ ràng tăng cùng với rp, điều này có nghĩa là với bất kỳ x nào là nghiệm của (2) thì là nghiệm của (1) và ngược lại. Mặc dù bài toán lợi ích kỳ vọng cực đại của Bernoulli- Trang 70 (2) được xác định là tương đương với (1), chúng ta vẫn gọi đây là một bài toán xác định “không tất định” tương đương bởi vì bài toán không xác định một cách đầy đủ các tham số hàm lợi ích chưa biết và không thể giải được ở dạng hiện tại. Tuy nhiên với những nhà đầu tư giả sử rằng có những rủi ro ngoài ý muốn. Trong bài toán (2) thì U là một hàm lõm và bất định nên ta cần phải tham số hóa hàm U và sau đó cố gắng giải bài toán (2). Markowitz để xuất hàm lợi ích bậc 2 đã tham số hóa như sau: ܷ(ݔ) = ݔ − ߣ2 ݔଶ (3) Kể từ khi U(x) ở trên đã được chuẩn hóa sao cho: U(0) = 0 và U’(0) = 1, điều này dẫn đến chính xác một tham số λ – hệ số rủi ro ngoài ý muốn. Với các tham số này Markowitz cho thấy một cách chính xác tất cả các phương án cực đại tiềm năng của bài toán không tất định (undetermined) tương ứng – (2) với rủi ro ngoài ý muốn, thì các nhà đầu tư có thể đạt được điều này bằng cách giải bài toán khả năng tất định tương đương (c) max {ܧൣݎ௣൧} min {ܸൣݎ௣൧} ݏܽ݋ ܿℎ݋ ݔ ∈ ܵ ∀ݔ ߳ ܵ thì việc tăng hay giảm thiểu rủi ro cũng không làm giảm lợi nhuận kỳ vọng đạt được từ danh mục đầu tư của nhà đầu tư. Như đã biết tập các vector x như vậy thay cho tập hữu hiệu (không gian thành phần đầu tư) và tập tất cả các ảnh của các điểm hữu hiệu thay cho tập không trội (trong không gian tiêu chuẩn). Do đó với U như trong (3), thì (c) là bài toán tất định tương đương thích hợp nhất của 5 bài toán nêu trên. Chú ý rằng ứng với giá trị cực biên ߣ = 0 ( rủi ro trung lập) hoặc ߣ  ∞ (rủi ro ngoài ý muốn), chúng ta đạt được khả năng (a) hoặc (b) một cách tương ứng, như trường hợp đặc biệt (c). Nên chú ý rằng kể từ khi hàm giới hạn U không tồn tại khi ߣ  ∞, (b) thì không đạt được một cách trực tiếp các phương án làm cực đại lợi ích kỳ vọng. Chỉ đạt được khi giới hạn của các phương án của lợi ích kỳ vọng đối với việc tăng rủi ro ngoài ý muốn. Ta xét một tình huống cực biên khác trong đó: Trang 71 ܷ(ݔ) = ൞ 1, ܿ + ߝ ≤ ݔ ݔ − ܿ ߝ , ܿ ≤ ݔ < ܿ + ߝ 0, ݔ < ܿ Với tham số chưa biết ܿ và ࣕ > 0 , ta thấy rằng: ܲ(ݎ ≥ ܿ) ≥ ܧ[ܷ(ݎ)] ≥ ܲ(ݎ ≥ ܿ + ߝ) Khi r là biến ngẫu nhiên liên tục, chúng ta đạt được: ܧ[ܷ(ݎ)] = ܲ(ݎ ≥ ܿ) Khi ߳  ∞, điều này dẫn đến bài toán (݀) và (݁). Thực tế, cho ܿ là mức rủi ro tự do của việc lợi nhuận. Sau đó (d) có ý nghĩa rằng khả năng để nhận ít mức rủi ro tự do của lợi nhuận nhất của danh mục đầu tư cần cực đại. Nếu r = (r1,…,rn ) là phân phối chuẩn nhiều chiều, trong trường hợp ܿ bằng với mức rủi ro tự do, sau đó lời giải (d) với danh mục đầu tư sẽ đạt được nhiều lợi tức. Lần nữa, cần phải chú ý rằng (d) và (e) không đạt được phương án tối ưu cực đại lợi ích kỳ vọng. Ngoài ra một khả năng tất định tương đương thứ 6 đưa vào (1) là: (f) max {ܧൣݎ௣൧ =෍ݎ௜ݔ௜௡ ௜ୀଵ } min {ܸൣݎ௣൧ =෍෍ߪ௜௝௡ ௝ୀଵ ௡ ௜ୀଵ ݔ௜ݔ௝} ݉ܽݔ{ܵ݇݁ݓൣݎ௣൧ =෍෍෍ߛ௜௝௞௡ ௞ୀଵ ௡ ௝ୀଵ ݔ௜ݔ௝ݔ௞ ௡ ௜ୀଵ } ݏܽ݋ ܿℎ݋: ݔ ∈ ܵ Trong đó: Skew là ký hiệu của đối xứng lệch. ߛ௜௝௞ = ܧൣ(ܴ௜ − ݎ௜)( ௝ܴ − ݎ௝)(ܴ௞ − ݎ௞)൧ Với các vector tiêu chuẩn độ dài 3, (f) là bài toán danh mục đầu tư đa mục tiêu. Công thức này có thể là công thức tiêu chuẩn đa mục tiêu duy nhất, không giống như lựa chọn danh mục đầu tư thông thường khi kết quả của lợi nhuận nằm trong đối xứng. Tuy nhiên, ta Trang 72 không chú trọng vào công thức (f) - như là một kết quả không tuyến tính của tiêu chuẩn thứ 3, không được ưa thích nhiều trong thực tế. Thay vào đó, ta tập trung vào các loại mới của bài toán lựa chọn danh mục đầu tư đa mục tiêu vì điều này đã xuất hiện như là một kết quả của nhiều mục đích phức tạp của các nhà đầu tư. Khi các công thức đa mục tiêu cho thấy nhiều tham vọng của nhà đầu tư hơn trong lựa chọn danh mục đầu tư thông thường thì các công thức tiêu chuẩn đa mục tiêu hầu như thích hợp khi cố gắng đáp ứng những nhu cầu mẫu mực của các nhà đầu tư với hàm lợi ích đa đối số. Trường hợp 2 trong các hàm lợi ích đa đối số sẽ không dễ xảy ra với lý do như sau:  Thứ 1: Việc tăng thêm lợi nhuận từ danh mục đầu tư, một nhà đầu tư có những suy xét khác nhau, chẳng hạn: để cực đại hóa trách nhiệm xã hội và cực tiểu số lượng cổ phần trong danh mục đầu tư. Như vậy thay vì quan tâm trong việc cực đại các mục tiêu ngẫu nhiên là lợi nhuận đạt được từ danh mục đầu tư, nhà đầu tư có thể tối ưu một số tổ hợp của một vài mục tiêu ngẫu nhiên và tất định.  Thứ 2 : trong đó hàm lợi ích đa đối số liên quan là khi một nhà đầu tư không sẵn lòng chấp nhận giả thiết rằng tất cả giá trị kỳ vọng ߤ௜ , phương sai ߪ௜ và hiệp phương sai ߪ௜௝ có thể coi như đã biết tại thời kỳ bắt đầu nắm giữ các loại cổ phiếu. Để phản ứng lại nhà đầu tư có thể muốn giám sát sự “hình thành” danh mục đầu tư của họ với sự trợ giúp của các tiêu chuẩn bổ sung, chẳng hạn như: cổ tức, sự tăng trưởng trong việc bán hàng, lượng đầu tư trong nghiên cứu và phát triển và những thứ khác có liên quan, để đảm bảo chống lại việc dựa vào các tiêu chuẩn đơn lẻ hoàn toàn không liên quan. Cho z1 là là một phương án của rp. Khi đó, danh sách của các giá trị tiêu chuẩn zi, từ những đối số có thể được lựa chọn để bố trí hàm lợi ích đa đối số của nhà đầu tư như sau: Max { Z1 = Lợi nhuận danh mục đầu tư } Max { Z2 = Tiền lãi cổ phần/cổ tức } Max { Z3 = Tăng trưởng trong bán hàng } Max { Z4 = Trách nhiệm xã hội } Trang 73 Max { Z5 = Khả năng thanh khoản bằng tiền mặt } Max { Z6 = Lợi nhuận đạt được từ các loại chứng khoán đã chọn từ danh mục } Max { Z7 = Lượng tiền đầu tư cho việc nghiên cứu và phát triển } Min { Z8 = Phần trăm của độ lệch trong việc phân phối tài sản } Min { Z9 = Số lượng chứng khoán trong danh mục đầu tư } Min { Z10 = doanh thu } Min { Z11 = cực đại tỉ trọng cân xứng đầu tư } Min { Z12 = Lượng tiền từ việc bán cổ phiếu trong thời gian ngắn hạn } Min { Z13 = Số lượng cổ phiếu bán trong thời gian ngắn hạn } Tất nhiên các zi có thể hình dung được. Chú ý sự khác biệt giữa z1 đến z6 và z8 đến z13. Đối với 6 hàm z đầu tiên, có thể không biết các giá trị thực tế của zi ( i =[1,6] ) cho đến khi kết thúc thời kỳ giữ cổ phiếu. Phụ thuộc vào việc tăng các biến ngẫu nhiên liên quan với cổ phần n, như z1,..,z6 là một biến ngẫu nhiên. Do đó sáu hàm z1 z6 là các hàm mục tiêu ngẫu nhiên. Từ z8 z13, giá trị thực của chúng đối với bất kỳ vector tỉ lệ đầu tư x thì có hiệu lực tại thời kỳ bắt đầu nắm giữa cổ phiếu. Ví dụ: bất kỳ vector tỉ lệ đầu tư x, z9 thì được đặc trưng bởi các thành phần khác 0 trong vector x. Với z8z13 nếu xét từ lúc nắm giữ cổ phiếu thì thì chúng là các hàm mục tiêu tất định. Và z7 là một ví dụ về chuẩn mực có thể được thảo luận theo cách khác nhau. Nó có thể được thảo luận nhắm vào số lượng đầu tư hiện tại trong việc nghiên cứu và phát triển (R&D) mà có liên quan đến tình huống tại thời kỳ kết thúc việc nắm giữ cổ phiếu do cho phép hàm mục tiêu được xem như là tất định. Thứ nhất có thể hỏi tại sao không thể tăng thêm hàm mục tiêu được hiểu theo nghĩa các ràng buộc? Điểm khó là việc thiết lập giá trị bên phía vế phải của ràng buộc. Tổng quát, mô hình để tạo biên kỳ vọng – phương sai không trội chứa các tiêu chuẩn của danh mục đầu tư tối ưu thì cần phải biết giá trị tối ưu của mỗi mục tiêu đã được mô hình hoá, trong nhiều trường hợp điều này là rất khó. Z1 hầu như chắc chắn là đối số của hàm mục lợi ích của nhà đầu tư, các đối số bổ sung phụ thuộc vào các nhà đầu tư. Ví dụ, tập các đối số của nhà đầu tư bao gồm {z1, z2, z10} Trang 74 và các tập khác bao gồm {z1, z5, z7, z8, z11}. Lưu ý là hành vi nhà đầu tư thường thì khác nhau. Nếu ta đặt k là số các mục tiêu đã được lựa chọn, trong trường hợp của nhà đầu tư thứ nhất, k = 3 và trong trường hợp nhà đầu tư thứ 2, k = 5. Tất nhiên, tập các đối số của nhà đầu tư kỳ vọng- phương sai thông thường chỉ là {z1} khi k = 1. Hình 21: Cấu trúc phân tầng của bài toán tuyến tính ngẫu nhiên, tương đương với bài toán tuyến tính tất định “không xác định” và bài toán tuyến tính bổ sung tất định tương ứng của việc lựa chọn danh mục đầu tư chuẩn. Hình 21 là mô hình để cực đại biến lợi nhuận ngẫu nhiên từ danh mục đầu tư. Mục tiêu ngẫu nhiên cần cực đại của danh mục đầu tư Bài toán ngẫu nhiên ban đầu Bài toán xác định không tất định Bài toán tất định 2 mục tiêu Trang 75 Hình 22: Cấu trúc bài toán tuyến tính ngẫu nhiên đa mục tiêu ban đầu, tương ứng với bài toán tuyến tính tất định. Hình 22 là mô hình để tối ưu một vài tổ hợp của mục tiêu ngẫu nhiên và tất định.  là ký hiệu số hàm mục tiêu ngẫu nhiên cần quan tâm và 1 ( )iD x  là hàm mục tiêu đầu tiên trong số k  hàm mục tiêu tất định mà ta quan tâm. Chẳng hạn như, nếu D13(x) nằm trong số k  hàm mục tiêu này thì D13(x) sẽ được xem như là hàm sẽ trả về giá trị của các xi có giá trị âm. Bài toán bất định tương đương với bài toán tuyến tính tất định bổ sung cho việc lựa chọn danh mục đầu tư đa mục tiêu. Trong bước 3 của hình 22 là bài toán tuyến tính tất định “không xác định” : Bài toán tất định đa mục tiêu Bài toán xác định không tất định Bài toán ngẫu nhiên ban đầu đa mục tiêu Các mục tiêu ngẫu nhiên và tất định cần tối ưu Trang 76 ܯܽݔ൛ܧൣܷ൫ݖ௜భ , … , ݖ௜೙ ,ݖ௜೙శభ, … , ݖ௜ೖ൯൧ൟ (4) ݏܽ݋ ܿℎ݋ ݔ ∈ ܵ Tận dụng cặp kỳ vọng và phương sai cho mỗi đối số ngẫu nhiên của hàm lợi ích, ta có bài toán tuyến tính tất định bổ sung tương đương – bước cuối cùng trong hình 22. Ta sử dụng nhóm từ “bổ sung” bởi vì đây là bài toán tất định thực tế được bổ sung. Chú ý rằng tất cả các mục tiêu tất định của bài toán tuyến tính ngẫu nhiên đa mục tiêu ban đầu được lặp lại không đổi trong bài toán tuyến tính bổ sung tất định tương đương. Như một vấn đề thực tế, đối với những mục tiêu tất định mà sự thay đổi/dao động là nhỏ hoặc không đáng để chú ý, thì có khả năng đặt nó trong bài toán tuyến tính bổ sung tất định tương đương trong bước cuối cùng của hình 22 bằng (a) thay vì (c). Điều này sẽ rất thuận lợi nếu có thể. Giả sử tập các nhà đầu tư là {z1, z2, z3}. Khi đó các mục tiêu này là tuyến tính. Bài toán tuyến tính ngẫu nhiên ban đầu của nhà đầu tư sẽ là: max{ܧ[ݖଵ]} (5) Min{V[zଵ]} max {ܧ[ݖଶ]} max {ܧ[ݖହ]} ݏܽ݋ ܿℎ݋ ݔ ∈ ܵ Thuận lợi trong việc sử dụng (a) thay vì (c) với mục tiêu ngẫu nhiên là lợi nhuận đạt được từ danh mục đầu tư với rủi ro được đánh giá qua phương sai_V đối với mỗi mục tiêu, như vậy có thể được loại bỏ từ bài toán tuyến tính bổ sung tất định. Điều này không chỉ đơn giản yêu cầu tập hợp dữ liệu mà còn giảm bớt gánh nặng tính toán tập chứa các nghiệm không trội. b) Tập nghiệm không trội của kỳ vọng - phương sai. Để thuận tiện bây giờ ta sử dụng ký hiệu ma trận. Để chuẩn bị cho việc áp dụng bốn bước giải pháp Markowitz nhằm tạo ra các bài toán lựa chọn danh mục đầu tư đa mục tiêu, điều này rất hữu ích cho việc nghiên cứu những chi tiết lớn về công thức kỳ vọng phương sai bước cuối ở hình 21: Trang 77 ܯܽݔ{ܧ[ݖଵ] = ߤ்x } (6) ܯ݅݊{ܸ[ݖଵ] = x୘Γx } ݏܽ݋ ܿℎ݋ ݔ ∈ ܵ Trong đó: ߤ ߳ ܴ : Vector giá trị kỳ vọng của ݎ௜ Γ ∈ ܴ௡୶௡ : Ma trận hiệp phương sai của ߪ௜௝. 3.2 Quản lý tối ưu danh mục đầu tư với chi phí giao dịch cố định 3.2.1 Giới thiệu mô hình. Mô hình tính toán giá trị kỳ vọng và phương sai đã được đề xuất trong việc lựa chọn danh mục đầu tư với chi phí giao dịch cố định và những chi phi giao dịch tối thiểu khác. Bài toán lựa chọn danh mục đầu tư là bài toán quy hoạch nguyên đa mục tiêu không tuyến tính và không trơn nên việc dùng các phương pháp truyền thống để giải mô hình bài toán này rất phức tạp và việc đề xuất dùng thuật toán di truyền để giải mô hình toán này là cách tiếp cận hợp lý vì nó cho phép xác định được biên Pareto rất tốt Phương pháp dựa trên phương sai và kỳ vọng được đề xuất bởi Mazkowitz đóng vai trò rất quan trọng trong lý thuyết lựa chọn danh mục đầu tư và được xem là một công cụ rất tốt cho việc phân tích đầu tư tài chính. Mô hình toán học của Markowitz đối với việc lựa chọn danh mục đầu tư chính là bài toán quy hoạch toàn phương với ma trận nửa xác định dương. Tuy nhiên mô hình toán này cũng mắc phải những khó khăn trong việc giải quyết một số trường hợp phát sinh từ thực tế như: chi phí giao dịch cố định hoặc các giao dịch tối thiểu khác vì mô hình này là một bài toán quy hoạch toán học với các biến là số nguyên và hàm mục tiêu không tuyến tính. Có rất nhiều mô hình toán học khác nhau được đề xuất để giải quyết những khó khăn trên, trong đó mô hình sử dụng phương pháp di truyền là một trong những phương pháp được đề cập nhiều nhất để giải bài toán quản lý danh mục đầu tư tối ưu đa mục tiêu. Trong phần này ta sẽ trình bày một mô hình toán học cho bài toán lựa chọn danh mục đầu tư với chi phí cố định và các số lượng tối thiểu của các loại cổ phiếu khác. Sau Trang 78 đó sẽ đề xuất thuật toán NSGA-II để giải quyết bài toán lựa chọn danh mục đầu tư tối ưu như đã đề cập. 3.2.2 Mô hình toán học: Mô hình toán học cho bài toán lựa chọn danh mục đầu tư với chi phí cố định và số lượng tối thiểu của các loại cổ phiếu khác dựa trên giá trị kỳ vọng và phương sai: Một số ký hiệu: S : 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 và giả sử ܥ ∈ [ܥ଴,ܥଵ] là cố định. Ta có thể xem [ܥ଴,ܥଵ] là số tiền lớn nhỏ nhất và lớn nhất mà nhà đầu tư có thể đầu tư. ݊ = |ܵ| ∶ Số lượng chứng khoán trong danh mục niêm yết. ݎ௜ : Tỷ lệ lợi nhuận ngẫu nhiên khi đầu tư vào loại chứng khoán thứ i, ݅ ∈ ܵ. giả thiết là tất cả các chứng khoán trong danh mục – S yêu cầu phải được nhân với số lượng tối thiểu của loại cổ phiếu. ௝ܰ : 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 với ௝ܿ = ௝ܰ .݌௝ ܴ௜ = ܧ(ݎ௜) : Kỳ vọng của lợi nhuận đầu tư vào chứng khoán thứ i trong danh mục đầu tư ߪ௜௝ = ܿ݋ݒ൫ݎ௜, ݎ௝൯ = ܧ ቀ(ݎ௜ − ܴ௜)൫ݎ௝ − ௝ܴ൯ቁ : Hiệp phương sai giữa ݎ௜ ݒà ݎ௝ . ܹ = ( ݓଵ, … ,ݓ௡ ): Có thể xem như danh mục đầu tư. Trong đó giá trị wj là giá trị trọng số đặt trưng cho chứng khoán thứ j trong danh mục đầu tư. Với loại chứng khoán thứ ݆ ∈ ܵ ta áp đặt một số lượng vốn tối đa đã đầu tư vào chứng khoán này và ta ký hiệu là ݑ௝ . Trong trường hợp nhà đầu tư bắt buộc phải trả chi phí cố định tương ứng ௝݂ khi chứng khoán j trong danh mục được chọn và chi phí cố định phải chịu vào cuối thời kỳ giao dịch và được trích từ lợi nhuận danh mục đầu tư. Do đó, lợi nhuận kỳ vọng ròng E(W) của danh mục đầu tư W có thể được viết lại như sau: Trang 79 ܧ(ܹ) = 1 ܥ .ቌ෍൫ ௝ܴ − ௝݀൯ ௝ܿݓ௝ − ௝∈ௌ ෍ ௝݂ݖ௝ ௝∈ௌ ቍ Trong đó: ܥ = ∑ ௝ܿݓ௝௝∈ௌ là tổng số vốn đầu tư trong danh mục và ݖ௝ = ൜ 1 ݇ℎ݅ ݒà ܿℎỉ ݇ℎ݅ ௝݇ > 0 0 ܰ݃ượܿ ݈ạ݅ V(W) : Phương sai, được xác định như sau: ܸ(ܹ) =෍෍ߪ௜௝ݕ௜ݕ௝ ௝∈ௌ௜∈ௌ Trong đó: ݕ௝ = ௪ೕ௖ೕ஼ là phân số cho thấy tỉ lệ của vốn C đầu tư vào chứng khoán thứ j. Mô hình bài toán lựa chọn danh mục đầu tư với chi phí giao dịch cố định và số lượng tối thiểu của các cổ phiếu được trình bày trong luận văn này là bài toán quy hoạch hai mục tiêu. Bài toán được phát biểu như sau: (P1) : ܯ݅݊ (−ܧ(ܹ),ܸ(ܹ)) Sao cho: ܥ଴ ≤ ∑ ݓ௝ ௝ܿ௝∈ௌ = ܥ ≤ ܥଵ (ܽ) 0 ≤ ݓ௝ ௝ܿ ≤ ݑ௝ (ܾ) ݖ௝ ∈ {0,1} ݒớ݅ ݆ ∈ ܵ Danh mục đầu tư ܹ = ( ݓଵ, … ,ݓ௡) chấp nhận được đối với bài toán (P1) nếu thỏa mãn tất cả các ràng buộc của (P1) Một danh mục đầu tư chấp nhận được W* được gọi là hiệu quả nếu W* là nghiệm tối ưu Pareto của bài toán (P1) nghĩa là không tồn tại một danh mục đầu tư W khác sao cho ܧ(ܹ) ≥ ܧ(ܹ∗) và ܸ(ܹ) ≤ ܸ(ܹ∗) với ít nhất một ràng buộc bất đẳng thức thỏa chặt. Tập tất cả các danh mục đầu tư hiệu quả được gọi là biên hiệu quả của bài toán ( P1). Trong thuật toán di truyền, nghiệm được gọi là các chromosome. Có nhiều cách xác định chí phí giao dịch cố định chẳng hạn như chi phí giao dịch cố định được xác định dựa trên tổng số tiền đầu tư vào mỗi loại chứng khoán vượt quá biên hay thực tế hơn chi phí giao dịch cố định khác nhau được xác định dựa trên tổng số vốn đầu tư. Trang 80 Trong bài toán (P1) có 2 ràng buộc:  Ràng buộc (a) là ràng buộc của số vốn đã đầu tư. Ràng buộc này cho thấy rằng số vốn có thể đầu tư tối đa vào danh mục đầu tư.  Ràng buộc (b) có nghĩa là việc bán và mua ngắn hạn không cho phép và số lượng vốn tối đa được áp đặt đối với mỗi chứng khoán. Để giải bài toán (P1) nếu dùng các phương pháp cổ điển sẽ rất khó do đây là bài toán quy hoạch phi tuyến không trơn vì vậy cách tốt nhất là ta dùng thuật toán di truyền để tìm kiếm và xấp xỉ biên Pareto của bài toán (P1). 3.2.3 Thuật toán di truyền dựa trên thuật toán NSGA-II Trong luận văn này tôi giới thiệu một thuật toán di truyền dựa trên thuật toán NSGA-II để giải bài toán (P1). Vì bài toán (P1) chứa đựng các ràng buộc của các biến rời rạc nên ta sẽ thay đổi thuật toán NSGA-II một chút để việc xác định biên hiệu quả một cách thích hợp hơn. Tuy nhiên khung chính của thuật toán vẫn không thay đổi. Sau đây tôi sẽ giới thiệu một số sự thay đổi trong đối với thuật toán NSGA-II trong phần trình bài trước như: mã khởi tạo, quá trình khởi tạo quần thể, các toán tử chéo hóa và đột biến. a) Mã khởi tạo: khi sử dụng thuật toán NSGA ta có thể chọn giá trị khởi tạo là mã nhị phân hay số thực. Mã khởi tạo nhị phân được sử dụng trong thuật toán di truyền có một vài bất lợi khi áp dụng vào bài toán quy hoạch nguyên (P1) và (P2). Ví dụ 16: Nếu có một chứng khoán i thứ ki trong khoảng [0,100], sau đó sẽ rất khó để sử dụng chromosome nhị phân chiều dài cố định để mã hóa chính xác các số nguyên trong khoảng [0,100]. Một chuỗi chromosome nhị phân có độ dài là 6 có thể mã hóa được 64 giá trị nằm trong khoảng [0,63], và một chuỗi chromosome nhị phân có độ dài là 7 có thể mã hóa được 128 giá trị nằm trong khoảng [0,127]. Ta sẽ xem mỗi nghiệm nguyên là giá trị đặc trưng của các chromosome và mã hóa là một chuỗi các số nguyên. ܹ = (ݓଵ, … ,ݓ௡) Trang 81 ݓ௜ ∈ [0,ݑ݌݌݁ݎ(݅)]. Trong đó ݑ݌݌݁ݎ(݅) = [ݑ ܿ⁄ ] với mỗi ݅ ∈ ܵ với [.] là hàm làm tròn lên. Điều này cho phép ràng buộc (b) được bảo đảm với mỗi ݅ ∈ ܵ. b. Quá trình khởi tạo: Trong thuật toán NSGA – II không cần phải xử lý riêng lẻ ràng buộc (a). Chú ý giữ nghiệm từ quá trình khởi tạo và tính toán sao cho thỏa mãn ràng buộc (b). Để làm điều này ta tạo ngẫu nhiên số nguyên ݓ௜ ∈ [0,ݑ݌݌݁ݎ(݅)] với mỗi ݅ ∈ ܵ sau đó nghiệm khởi tạo ܹ = (ݓଵ, … ,ݓ௡) được tạo. Lặp lại với điều kiện là pop_size với pop_size là tham số cho biết số lượng cá thể trong quần thể. c. Toán tử chéo hóa: trong thuật toán NSGA – II, toán tử chéo hóa - SBX được sử dụng cho chromosome được mã hóa là số thực. Để phù hợp cho các chromosome được mã hóa bằng các số nguyên vì sau mỗi lần thực hiện chéo hóa (một cách tổng quát không đạt giá trị nguyên) các nghiệm con sẽ có giá trị nguyên ݓ௜ ta thực hiện kỹ thuật sau: ݓ௜ = ൜[ݓ௜] ℎ݋ặܿ [ݓ௜ + 1] ݊݃ẫݑ ݊ℎ݅ê݊ ܰếݑ [ݓ௜] + 1 ≤ ݑ݌݌݁ݎ(݅) ݑ݌݌݁ݎ(݅) ܰ݃ượܿ ݈ạ݅ (3.1) Với kỹ thuật trên thì ݓ௜ sẽ có giá trị nguyên trong khoảng [0,ݑ݌݌݁ݎ(݅)] d. Toán tử đột biến dựa trên tham số: Toán tử đột biến sử dụng trong thuật toán NSGA – II sẽ được thay đổi để phù hợp hơn cho bài toán (P1) cụ thể là các mã, mã hóa cho các chromosome sẽ có giá trị nguyên. Các chromosome cha ܹ = (ݓଵ, … ,ݓ௡) nếu có các i, 1 ≤ i ≤ n. W được chọn để gây đột biến tạo thành ܹ’ bằng cách sử dụng toán tử đột biến cổ điển áp dụng cho các chromosome được mã hóa bởi giá trị thực. Sau đó w sẽ được chuyển đổi thành số nguyên ݓ௜ ᇱ bởi công thức (3.1). Có 2 đặt trưng của thuật toán NSGA – II và thuật toán di truyền đã đề xuất. Với ràng buộc (a) một nghiệm w của bài toán (P1) có thể thỏa mãn ràng buộc (a) nhưng không thỏa mãn ràng buộc (b) và ngược lại, ta gọi điều này là xung đột giữa các ràng buộc. Để tính mức độ xung đột của ràng buộc (b) ta dùng hàm g(w) được định nghĩa như sau: ݃(ݓ) = ቐ0 ܰếݑ ܥ଴ ≤ ܥ ≤ ܥଵܥ଴ − ܥ ܰếݑ ܥ < ܥ଴ ܥ − ܥଵ ܰếݑ ܥ > ܥଵ (3.2) Trang 82 Rõ ràng một nghiệm gọi là chấp nhận được nếu và chỉ nếu ݃(ݓ) = 0 và hàm g(w) này cho thấy rằng: một nghiệm chấp nhận được thì luôn tốt hơn nghiệm không chấp nhận được đồng thời một nghiệm không chấp nhận được với giá trị của hàm g(w) nhỏ sẽ tốt hơn một nghiệm không chấp nhận khác mà có giá trị hàm g(w) lớn. Để đơn giản chúng ta gọi thuật toán cải tiến từ thuật toán NSGA – II để giải bài toán (P1) là thuật toán “di truyền 1”. 3.2.4 Thuật toán di truyền dựa trên NSGA-II và Genocop. Khi sử dụng thuật toán di truyền 1 để giải bài toán (P1) thì vẫn còn tồn tại một số hạn chế đó là việc sử dụng các toán tử di truyền. Như ràng buộc (a) thì rất khó để thỏa mãn vì các toán tử trong thuật toán di truyền không thể bảo đảm tính chấp nhận của bất kỳ thế hệ con được tạo ra từ các thế hệ cha đã chấp nhận được vì có nhiều cá thể không chấp nhận được tạo trong quá trình tiến hóa và có nhiều tính toán. Thuật toán Genocop (The Genetic Algorithm for Numerical Optimization of Constrained Promblems) thì giả sử rằng các ràng buộc là tuyến tính và quần thể khởi tạo chấp nhận được. Tập đóng của các toán tử duy trì tính chấp nhận của nghiệm. Chẳng hạn khi một thành phần wi của vector nghiệm ܹ = (ݓଵ, … ,ݓ௜) với ݅ ∈ [2,݊] bị thay đổi qua toán tử đột biến, thuật toán sẽ xác định một miền hiện tại dom(w) và giá trị mới của w từ dom(w) đã được làm giảm bằng cách sử dụng toán tử Đột biến. Vector nghiệm con thì luôn chấp nhận được. Với các nghiệm chấp nhận được của bài toán (ܲ1) ܹ = (ݓଵ, … ,ݓ௡) mà thỏa mãn ràng buộc (a) trong khi w1 thì được chọn để biến đổi thông qua toán tử đột biến, w1 có thể là một số nguyên nằm trong miền giá trị: ቈ ܥ଴ − ∑ ݓ௜݌௜ ௡ ௜ୀଵ ݌ଵ ,ܥଵ − ∑ ݓ௜݌௜௡௜ୀଵ ݌ଵ ቉ሩ [0,ݑ݌݌݁ݎ(1)] Khi các ràng buộc là chặt và ( ܥଵ – ܥ଴ ) nhỏ thì w1 sẽ được thay đổi thành các giá trị khác nhau. Bằng cách kết hợp các phân tích đã thảo luận ở trên cộng với ý tưởng của thuật toán di truyền 1 và Genocop ta có thể duy trì tính chấp nhận được của tất cả các nghiệm được tạo qua các thế hệ. Ta gọi thuật toán mới này là thuật toán di truyền 2. Trang 83 Các thành phần chính của thuật toán di truyền 2 khác so với thuật toán di truyền 1 được mô tả như sau: a) Quá trình khởi tạo: Khi thực hiện thuật toán Genocop thì tất cả các cá thể trong quần thể khởi tạo phải chấp nhận được. Tuy nhiên như đã nói để tìm nghiệm chấp nhận được của bài toán (P1) thì rất khó. Tất cả các cá thể chấp nhận được của bài toán (P1) là nghiệm của bài toán đơn mục tiêu sau: ܯ݅݊ ݃ଶ(ݔ) (P2) Sao Cho: 0 ≤ ௝ܿݓ௝ ≤ ݑ௝ với ݆ ∈ ܵ Bài toán (P2) có thể xem như là một trường hợp đặc biệt của bài toán tối ưu nhiều mục tiêu và (P2) sẽ được giải bởi thuật toán di truyền 1. Thuật toán này sẽ dừng khi tất cả các cá thể trong quần thể là chấp nhận được và quần thể này sẽ phục vụ như là quần thể khởi tạo cho thuật toán di truyền 2. b) Vô hướng hoá hàm tính độ thích nghi: Trước hết ta giải từng bài toán quy hoạch một mục tiêu (P3) và (P4) sau: (P3) ܯ݅݊ ܸ(ܹ) Sao cho: ܥ଴ ≤ ∑ ݓ௝ ௝ܿ௝∈ௌ = ܥ ≤ ܥଵ 0 ≤ ݓ௝ ௝ܿ ≤ ݑ௝ ݖ௝ ∈ {0,1} ݒớ݅ ݆ ∈ ܵ (P4) ܯܽݔ ܧ(ܹ) Sao cho: ܥ଴ ≤ ∑ ݓ௝ ௝ܿ௝∈ௌ = ܥ ≤ ܥଵ 0 ≤ ݓ௝ ௝ܿ ≤ ݑ௝ ݖ௝ ∈ {0,1} ݒớ݅ ݆ ∈ ܵ Nghiệm của bài toán (P3) và (P4) là phương sai cực tiểu toàn cục và kỳ vọng cực đại toàn cục và độ thích nghi được ký hiệu tương ứng là: (ܧ௠௜௡ , ௠ܸ௜௡) và ( ܧ௠௔௫, ௠ܸ௔௫ ). Hai Trang 84 nghiệm này sẽ đưa vào quần thể khởi tạo để thay thế cho 2 cá thể đã được lựa chọn ngẫu nhiên. Hàm tính độ thích nghi trong bài toán (P1) có được bằng cách vô hướng hóa và ta được một bài toán mới thay cho bài toán (P1) như sau: min ൬ −ܧ(ܹ) ܧ௠௔௫ − ܧ௠௜௡ , ܸ(ܹ) ௠ܸ௔௫ − ௠ܸ௜௡ ൰ Sao cho ܥ଴ ≤ ∑ ݓ௝ ௝ܿ௝∈ௌ = ܥ ≤ ܥଵ 0 ≤ ݓ௝ ௝ܿ ≤ ݑ௝ ݖ௝ ∈ {0,1} ݒớ݅ ݆ ∈ ܵ c) Toán tử đột biến: Thay vì xử lý ràng buộc (a) như là một đẳng thức ta sẽ trích một biến với hy vọng không phải là biến tự do. Không mất tính tổng quát, ta giả sử w1 sẽ được trích từ ܹ = (ݓଵ, … ,ݓ௡). Với một cá thể ݓ’ = ( ݓଶ, … ,ݓ௡ ) khi wj với ݆ = 2, … , ݊ được chọn để tạo thành ݓ௝ ᇱ ݒớ݅ ݓ௝ᇱ ∈ ݀݋݉(ݓ௝) thì ݓ௝ᇱ phải thỏa mãn bất đẳng thức được bổ sung vào trong ràng buộc (b) sau: ܥ଴ − ݌ଵ.ݑ݌݌݁ݎ(1)−෍݌௜ݓ௜௡ ௜ୀଶ ௜ஷ௝ ≤ ݓ௝ ᇱ݌௝ ≤ ܥଵ − ෍݌௜ݓ௜௡ ௜ୀଶ ௜ஷ௝ (3.3) Do đó bất đẳng thức: ܥ଴ − ݌ଵ.ݑ݌݌݁ݎ(1) ≤෍݌௜ݓ௜௡ ௜ୀଶ ௜ஷ௝ +ݓ௝ᇱ݌௝ ≤ ܥଵ (3.4) Và ta có: ܥ଴ −෍݌௜ݓ௜ ௡ ௜ୀଶ ௜ஷ௝ − ݓ௝ ᇱ݌௝ ≤ ݌ଵ.ݑ݌݌݁ݎ[1] ≤ ܥଵ − ෍݌௜ݓ௜௡ ௜ୀଶ ௜ஷ௝ − ݓ௝ ᇱ݌௝ (3.5) Từ (1.4) ta thấy rằng: ܥ଴ −෍݌௜ݓ௜ ௡ ௜ୀଶ ௜ஷ௝ −ݓ௝ ᇱ݌௝ ≤ ݌ଵ. ݑ݌݌݁ݎ(1) Trang 85 Và 0 ≤ ܥଵ − ෍݌௜ݓ௜௡ ௜ୀଶ ௜ஷ௝ −ݓ௝ ᇱ݌௝ Do đó có ít nhất một số nguyên ݓଵᇱ ∈ [0,ݑ݌݌݁ݎ(1)] tồn tại và một cá thể ݓ ᇱᇱ = (ݓଵᇱ,ݓଶ, … ,ݓ௝ᇱ, …ݓ௡) là nghiệm chấp nhận được của bài toán (P1). d) Toán tử chéo hóa: Trong thuật toán Geconop có cả 3 toán tử chéo hóa được dùng. Khi 2 cá thể được chọn để chéo hóa bằng cách sử dụng toán tử chéo hóa số học sẽ tạo ra các cá thể con chúng được mã hóa bằng mã số thực, sau đó mã số thực này sẽ được ước lượng thành số nguyên thông qua công thức (3.1). Từ đó 2 cá thể con được mã hóa bằng các số nguyên được hình thành. Tính chấp nhận được của 2 cá thể con này trong bài toán (P1) được kiểm tra, cả 2 cá thể con này sẽ được chấp nhận nếu cả 2 đều được chấp nhận, nếu không được chấp nhận thì 2 cá thể cha sẽ phải thực hiện chéo hóa một lần nữa. Quá trình xử lý này lặp lại cho đến khi tạo được các cá thể chấp nhận được hoặc số lần thử tạo cá thể con chấp nhận được vượt quá số lần thử như đã được qui định. Và các toán tử chéo hóa còn lại cũng được thực hiện tương tự. Tóm lại ta có các bước để giải mô hình toán quản lý danh mục đầu tư tối ưu như sau: Bước 0: Nhập vào các tham số như:  Pop_size : kích thước của quần thể (số lượng cá thể trong quần thể)  Pc : xác suất chéo hóa  Pm : xác suất đột biến  Maxgen: Số thế hệ cực đại cần đạt tới. Bước 1: Dùng thuật toán di truyền 1 giải bài toán (P2) để tạo quần thể khởi tạo, gồm tất cả nghiệm chấp nhận được của bài toán (P1). Bước 2:  Dùng thuật toán di truyền 1 giải bài toán (P3) và (P4) để xác định nghiệm cực tiểu và cực đại tương ứng, sau đó đưa các nghiệm này vào quần thể khởi tạo.  Vô hướng hóa hàm tính độ thích nghi. Trang 86 Bước 3: Cập nhật lại các cá thể trong quần thể hiện tại bằng cách thực hiện các toán tử chéo hóa và đột biến. Bước 4: Tính độ thích nghi của hàm đã được vô hướng trong bước 2 cho tất cả các cá thể. Bước 5:  Lựa chọn các cá thể bằng cách sử dụng thuật toán lựa chọn vòng nhị phân.  Lựa chọn các cá thể ưu việt để tạo thế hệ tiếp theo trong quá trình tiến hóa. Bước 6: Quay lại bước 3 đến bước 5 cho đến khi đạt được một thế hệ mà có các gen đặt trưng hay thoả mãn Maxgen Bước 7: Xuất các cá thể trong quần thể cuối cùng. 3.3 Quản lý và tối ưu danh mục đầu tư với chi phí giao dịch biến đổi. 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 Mô hình quản lý danh mục đầu tư hiện đại đã được Markowitz đề xuất vào năm 1987. Để quản lý và đầu tư vào mỗi cổ phiếu trong danh mục đầu tư một cách hiệu quả, Markowitz tập trung vào việc giảm thiểu rủi ro trên mỗi cổ phiếu bằng cách phân chia tài sản để đầu tư trên mỗi cổ phiếu, đồng thời cũng mong muốn tối ưu hóa lợi nhuận đạt được trên mỗi cổ phiếu. Việc phân chia tài sản để đầu tư sẽ giảm bớt rủi ro khi ta tập trung đầu tư vào cho một loại cổ phiếu duy nhất nào đó trong danh mục đầu tư. Chẳng hạn việc thiếu nợ ngân hàng của công ty có niêm yết cổ phiếu trong sàn danh mục đầu tư. Tuy nhiên những rủi ro khách quan liên quan đến thị trường như: sự trượt giá của đồng tiền trong nước so với thế giới sẽ ảnh hưởng tiêu cực đến giá mỗi cổ phiếu, hay tình hình chính trị bất ổn của một nước cũng sẽ ảnh hưởng xấu đến giá cổ phiếu trong danh mục đầu tư,…thì không nằm trong lý thuyết của Mazkowitz. Một trong những khó khăn của lý thuyết tài chính hiện đại – dựa trên lý thuyết của Markowitz là việc áp dụng nó vào việc xây dựng một mô hình toán học phù hợp để đạt được một danh mục đầu tư tối ưu. Mô hình này phải đủ chính xác để phản ảnh hành vi Trang 87 của thị trường trong thực tế và có rất nhiều mô hình toán học cũng đã được đề xuất để đáp ứng điều này. Tuy nhiên trong một điều quan trọng khác nữa là việc tính toán tối ưu danh mục đầu tư dựa trên các mô hình này cũng phải được đặt ra. Từ đó ta sẽ quyết định lựa cho mô hình nào là thích hợp nhất để áp dụng. Phương thức tối ưu sẽ mang lại một trọng số nhất định cho mỗi loại cổ phiếu mà nhà đầu tư phân chia tài sản tương ứng để đầu tư. Vì vậy nhà đầu tư phải biết cách phân phối tài sản một cách hợp lý để cực đại lợi ích kỳ vọng và cực tiểu hóa rủi ro cho danh mục đầu tư. Tóm lại bài toán tối ưu danh mục đầu tư có thể được xem như là bài toán quản lý nguồn tài nguyên. Vốn của nhà đầu tư được xem như là tài nguyên có giới hạn và được phân phối cho các loại cổ phiếu trong danh mục đầu tư với mong muốn là cực đại gía trị hàm mục tiêu – tức là lợi nhuận thu được từ việc đầu tư vào các loại cổ phiếu. Có hai vấn đề cần phải được đề cập và xem xét trong bài toán quản lý danh mục đầu tư: Một là tính chất năng động và tính thay đổi theo thời gian của thị trường. Hai là rủi ro và giá trị thu được từ việc đầu tư vào mỗi cổ phiểu thì không phải là bất biến. Do đó việc chọn phương pháp để áp dụng giải bài toán quản lý danh mục đầu tư phải phù hợp với những tính chất trên. Từ đây ta thấy thuật toán di truyền là phương pháp thích hợp để giải bài toán quản lý danh mục đầu tư tối ưu. 3.3.2 Quản lý danh mục đầu tư nhiều mục tiêu. a) Mô hình danh mục đầu tư: Giả sử trong danh danh mục đầu tư có N cổ phiếu. Với mỗi cổ phiếu ݊ ∈ ܰ thì ݎ௡௧ là lợi nhuận đạt được từ cổ phiếu thứ n tại thời điểm t và ܸ(ݓ௡௧) là rủi ro của cổ phiếu thứ n đo được tại thời điểm t. Dựa vào giả thiết này ta tạo một bài toán tối ưu hóa danh mục đầu tư đa mục tiêu mà ta cần phải tối ưu hóa để đạt được 3 mục tiêu sau: - Thứ I là cực tiểu hóa rủi ro danh mục đầu tư. - Thứ II là cực đại lợi nhuận đạt được từ việc đầu tư vào cổ phiểu và thứ 3 là cực tiểu chi phí giữa danh mục đầu tư hiện đại (tại thời gian t) và danh mục đầu tư trước (tại thời gian t-1). Trang 88 b) Giới thiệu danh mục đầu tư: Kết quả của bài toán tối ưu hóa danh mục đầu tư đa mục tiêu là chỉ ra những cổ phiếu nào trong danh mục đầu tư nên đầu tư tại thời điểm t. Danh mục đầu tư là một tập hợp các loại cổ phiểu mà trong đó mỗi loại cổ phiếu được đặc trưng bởi một giá trị trọng số. Ta kí hiệu là: ܹ௧ là tập hợp danh mục đầu tư, cũng đồng thời là tập các giá trị trọng số. Trong đó:  ݓ௡ ∈ ܹ௧ là trọng số cho việc đầu tư vào cổ phiếu thứ n – Giá trị trọng số ݓ௡ phản ánh việc nhà đầu tư có nên hay không nên đầu tư vào cổ phiếu n.  ∑ ݓ௜௡௜ୀଵ = 1 và 0 ≤ ݓ௜ ≤ 1 c) Lợi nhuận của danh mục đầu tư: Lợi nhuận đạt được của việc đầu tư vào các loại cổ phiếu trong mô hình được biểu diễn bởi hàm lo-ga-rít. Để tiện cho việc tính toán ta sử dụng giá đóng của loại cổ phiếu tại thời điểm t và (t-1) Gọi ௡ܲ௧ ݒà ௡ܲ௧ିଵ là giá đóng của loại cổ phiếu thứ n vào thời điểm t và (t-1). Khi đó ta có công thức xác định lợi nhuận đạt được từ việc đầu tư vào cổ phiếu thứ n tại thời điểm t như sau: ݎ௡ ௧ = log ቆ ௡ܲ௧ ௡ܲ ௧ିଵቇ Khi đó lợi nhuận đạt được của toàn bộ danh mục đầu tư tương ứng với giá trị trọng số của mỗi loại cổ phiếu tại thời điểm t được tính như sau: ݎௐ ௧ = ෍ݓ௡ݎ௡௧ே ௡ୀଵ d) Rủi ro của danh mục đầu tư Rủi ro khi nhà đầu tư lựa chọn để đầu tư vào cổ phiếu được đánh giá dựa trên phương sai của lợi nhuận đạt được từ việc đầu tư vào cổ phiếu. Rủi ro của danh mục đầu Trang 89 từ tại thời gian t thì được xác định bằng tổng trọng số của rủi ro khi đầu tư vào các loại cổ phiếu: ܸ(ܹ௧) =෍෍ݓ௜ݓ௝ߪ௜௝ே ௝ୀଵ ே ௜ୀଵ Trong đó ߪ௜௝ = ܿ݋ݒ൫ݎ௜, ݎ௝൯ : Hiệp phương sai giữa ݎ௜ ݒà ݎ௝ . e) Chi phí cho giao dịch của danh mục đầu tư. Chi phí giao dịch được tính toán trong quá trình nhà đầu tư mua và bán cổ phiếu của họ, chi phí giao dịch sẽ ảnh hưởng đến lợi nhuận của nhà đầu tư. Nếu số lần giao dịch nhiều thì chi phí giao dịch sẽ cao. Tuy nhiên trong thực tế chi phí giao dịch phụ thuộc vào chính sách của mỗi công ty chứng khoán. Các công ty này sẽ tính chi phí giao dịch dựa vào số lần giao dịch thành công hoặc là số lượng cổ phiếu giao dịch trong một lần giao dịch hay dựa vào loại (giá trị, vị thế) cổ phiếu. Ta tiếp cận việc tính toán chi phí giao dịch một cách gián tiếp bằng cách giả sử chi phí giao dịch được xác định dựa trên số lượng cổ phiếu trong danh mục được mua hay bán thành công trong mỗi lần giao dịch và để xác định chi phí giao dịch của danh mục đầu tư bằng cách tính toán khoảng cách metric giữa các trọng số trong danh mục đầu tư hiện tại và danh mục đầu tư mong muốn (là danh mục đầu tư mà trong đó ta dự định sẽ mua hay bán cổ phiểu thành công) như sau: ݀( ௔ܹ, ௕ܹ) = ඩ෍(ݓ௡௔ − ݓ௡௕)ଶே ௡ୀଵ Trong đó: ௔ܹ ݒà ௕ܹ là 2 danh mục đầu tư vào thời điểm hiện tại và danh mục đầu tư mong muốn tương ứng. Khoảng cách giữa 2 danh mục đầu tư càng cao nghĩa là chi phí để dịch chuyển từ danh mục này sang danh mục kia càng cao. Trang 90 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ư a) Tiến hóa tối ưu Ta dùng thuật toán di truyền để tạo nhiều tổ hợp danh mục đầu tư khác nhau và kiểm tra tính hiệu quả của các tổ hợp danh mục đầu tư này dựa trên các dữ liệu trước. Tỉ số (rủi ro)/( lợi nhuận) của danh mục đầu tư gọi là tỉ số Sharpe được dùng để đo giá trị thích nghi và để tính giá trị thích nghi nay ta sẽ ước lượng lợi nhuận của danh mục đầu tư bằng cách sữ dụng đường “trung bình dịch chuyển”. Trong phần này ta sẽ giải thích chi tiết mỗi thành phần trong bài toán tối ưu 1 mục tiêu sau đó đề xuất một kỹ thuật để giải bài toán tối ưu danh mục đầu tư đa mục tiêu. b) Giới thiệu về hệ gen (genome): Hệ gen của mỗi cá thể thì được biểu diễn bởi 2 mảng: Mảng chỉ số I và mảng trọng số W. Mảng I gồm N các phần tử mà mỗi phần tử trong mảng chỉ nhận 2 giá trị là {True, False} với N là số lượng tài sản của nhà đầu tư. Mỗi phần tử In biểu diễn tài sản thứ n có đầu tư vào một loại chứng khoán trong danh mục đầu tư nào đó hay không. Mảng W gồm N phần tử giá trị thực không âm, với N là số lượng tài sản của nhà đầu tư. Mỗi phần tử Wn biểu diễn trọng số chưa được chuẩn hóa tương ướng với mỗi chứng khoán trong danh mục đầu tư. Các tham số sử dụng trong thuật toán di truyền là: Tên tham số Miền giá trị Ý nghĩa Number of Generations N Số tương tác trong thuật toán di truyền Number of individuals N Số lượng cá thể trong mỗi thế hệ Time length N Thời gian để biểu diễn đường trung bình dịch chuyển. Legacy Size N Tham số tạo quần thể Fill ratio [0,1] Tham số tạo cá thể Elite Size N Số lượng nghiệm ưu việt Trang 91 Tournament k N Tham số lựa chọn vòng K_phân Crossover Ratio [0,1] Xác suất chéo hóa Mutation Ratio Flip [0,1] Xác suất đột biến trong mảng chỉ số I Mutation Ratio Perturb N Xác suất đột biến trong mảng trọng số W Pos [0,1] Xác suất lựa chọn độ thích nghi. Để tạo một danh mục đầu tư hiệu quả từ các tham số trên ta cần phải chuẩn hóa Genome. Trước tiên ta thiết lập giá trị của các phần tử trong mảng W là ௡ܹ = 0 và các ܫ௡ tương ứng trong mảng chỉ số là “False”. Sau đó ta sẽ chuẩn hóa các giá trị này. Các cá thể ngẫu nhiên được tạo bằng cách tạo các giá trị cho 2 mảng một cách ngẫu nhiên. Đối với mảng trọng số, các giá trị được tạo ngẫu nhiên trong khoảng [0,1] còn đối với mảng chỉ số I các phần tử có xác suất là “True” bằng với tham số fill_Ratio, ngược lại các phần tử thì được thiết lập giá trị “False”. Các tham số này cho phép ta giới hạn danh mục đầu tư mà có số lượng chứng khoán lớn. Ta nhận thấy trong các thuật toán tối ưu nhiều mục tiêu thường dùng mảng trọng số để cho thấy mức độ quan trọng của các mục tiêu. Tuy nhiên trong thuật toán di truyền này ta đề xuất dùng thêm mảng chỉ số I vì khi số lượng chứng khoán trong danh mục đầu tư tăng cùng với tài sản thì mảng chỉ số sẽ giúp ta kiểm tra để bổ sung hay loại bỏ các chứng khoán từ danh mục đầu tư một các hiệu quả. c) Ước lượng giá trị lợi nhuận Ta sử dụng một kỹ thuật truyền thống để phân tích chứng khoán bằng cách sử dụng đường trung bình dịch chuyển để tính lợi nhuận kỳ vọng đối với tài sản đầu tư và danh mục đầu tư. Cho một tài sản đặc trưng thứ n thì giá trị lợi nhuận kỳ vọng của tài sản này được tính như sau: ܧ(ݎ௡) = ∑ ݎ௡௧ି௜்௜ୀଵܶ (5.2.1) Trong đó: ݎ௡ ௧ି௜ : lợi nhuận của tài sản thứ n tại thời điểm (t-i), với t là thời gian hiện tại. Trang 92 T : tham số xác định kích thước của đường trung bình dịch chuyển. Lợi nhuận kỳ vọng của danh mục đầu tư được tính như sau: ܧ(ݎௐ) =෍ݓ௜ே ௜ୀଵ ܧ(ݎ௜) (5.2.2) Nhận xét: Mức độ chính xác của công thức tính toán này phụ thuộc vào sự lựa chọn tham số T – tham số này xác định có bao nhiêu thời kỳ được đưa vào trong quá trình tính toán lợi nhuận kỳ vọng. Nếu T quá lớn thì xu hướng tăng hoặc giảm trên phạm vi cục bộ của đường trung bình dịch chuyển. điều này không thể phản ánh đúng xu hướng hiện tại. Nếu T quá nhỏ thì kết quả của đường trung bình dịch chuyển chỉ phản ánh được xu hướng cục bộ của thị trường. Ta gọi T là tham số Time_length và để chọn giá trị T tốt nhất ta ước lượng giá trị mà có sự khác biệt nhỏ nhất giữa lợi nhuận kỳ vọng và lợi nhuận hiện tại tại thời điểm (t-1). d) Tính độ thích nghi Có hai cách khác nhau để tính toán độ thích nghi nhằm tối ưu danh mục đầu tư. Một là sử dụng tỉ số Sharpe_Ration và hai là sử dụng tỉ số khoảng cách Euclid. Tỉ số Sharpe_Ratio đề cập đến giá rủi ro của thị trường, nói một các khác tỉ số này nói lên rằng có bao nhiêu lợi nhuận kỳ vọng sẽ tăng nếu ta tăng rủi ro trong việc đầu tư. Tỉ số này được tính như sau: ܵ(ݎ௪) = ܧ(ݎௐ)− ܴܸ(ܹ) (5.2.3) Trong đó: R là tài sản với mức rủi ro tùy ý (là tài sản mà không biết trước khả năng sinh lợi nhuận trong tương lai). Tỉ số Sharpe_Ratio càng cao thì giá trị của danh mục đầu tư càng hiệu quả và tỉ số này cũng đặc trưng cho chỉ số của thị trường. Khoảng cách Euclid đã được đề cập trong phần trước. 3.3.4 Chiến lược tiến hóa Việc lựa chọn được xử lý bằng cách kết hợp giữa chiến lược tìm cá thể ưu việt và toán tử lựa chọn vòng. Trang 93 Trước hết số lượng cá thể được định nghĩa bởi tham số Elite_size đã được sao chép đến thế hệ tiếp theo mà không có xử lý đột biến và chéo hóa. Các cá thể khác trong thế hệ tiếp theo này được tạo bởi toán tử chéo hóa. Tham số lựa chọn Tournament_K thì lựa chọn ngẫu nhiên với xác suất bằng nhau trên mỗi cá thể và cá thể nào có độ thích nghi cao sẽ được lựa chọn làm cá thể cha. Khi 2 cá thể cho đã được chọn, toán tử chéo hóa (trong mô hình toán này ta dùng toán tử chéo hóa tại K điểm sẽ thực hiện với xác suất bằng với tham số xover_chance. Nếu toán tử chéo hóa không thực hiện thì cả 2 cá thể cha sẽ được sao chép vào thế hệ tiếp theo nhưng có thể bị ràng buộc bởi quá trình đột biến (không giống như các cá thể đã được chọn bởi quá trình lựa chọn cá thể ưu việt). Quá trình đột biến sẽ được áp dụng trên tất cả các cá thể đã được tạo bởi toán tử chéo hóa bằng cách chuyển 1 thành 0 và ngược lại trong mã nhị phân mã hóa cho mỗi cá thể thông qua tham số mutation_flip. Mỗi phần tử của vector trọng số trong mảng W được biến đổi bằng cách ±10% thông qua tham số mutation_perturb. Phân phối xác suất của việc cộng thêm hay trừ đi là phân phối chuẩn. a) Quản lý danh mục đầu tư Quản lý danh mục đầu tư là một tên gọi mà ta đặt cho bài toán tối ưu cấu trúc của danh mục đầu tư dựa trên nhiều mục tiêu khác nhau. Bên cạnh bài toán tối ưu danh mục đầu tư 1 mục tiêu thì trong quản lý danh mục đầu tư ta cũng phải giải quyết vấn đề chi phí giao dịch và những hạn chế thương mại giới hạn danh mục đầu tư. Ta có thể lựa chọn một kịch bản danh mục đầu tư hiệu quả tại thời điểm hiện tại dựa trên kịch bản của danh mục đầu tư trước đó. Kỹ thuật quản lý danh mục đầu tư đơn giản là sự hiệu chỉnh lại danh mục đầu tư. Bằng các hiệu chỉnh ta kỳ vọng xác lập các thành phần cơ bản của danh mục đầu tư thay đổi do những dao động về giá trị chứng khoán. Chẳng hạn, giả sử tại thời điểm t trong danh mục đầu tư có 2 loại chứng khoán A và B với trọng số tương ứng là 0.2 và 0.8. Lợi nhuận của chứng khoán A là 2 và của B là 1.5. Do những biến động về mặt giá cả thì trọng số của danh mục đầu tư là 0.25 và 0.75 Trang 94 vào ngày tiếp theo. Để hiệu chỉnh danh mục đầu tư thì nhà đầu tư cần phải hoặc là bán A hoặc là mua B. Hành vi này thể hiện việc mua thấp – bán cao. Trong phần này ta sẽ tiếp cận bài toán trên bằng cách dựa trên thông tin của kịch bản được lựa chọn bằng kỹ thuật di truyền trước đó để lựa chọn một kịch bản hiện tại cách hiệu quả nhất b) Kỹ thuật ươm (Seeding) Trong khi tạo một quần thể mới để đạt được danh mục đầu tư tối ưu tại thời gian t, ta sẽ giới thiệu vài cá thể từ quần thể cuối cùng của kịnh bản danh mục đầu tư trước đó vào thời điểm ( t-1). Các cá thể mới này được sao chép vào thế hệ đầu tiên trong kịch bản mới. Kỹ thuật bao gồm việc bổ sung tham số legacy_size vào trong bài thuật toán. Giá trị này đề cập đến số lượng cá thể từ kịch bản trước được sao chép vào kịch bản mới. Lược đồ mô tả phương pháp ươm Tạo quần thể No Các cá thể có Legacy_Size tốt nhất Ươm thế hệ tiếp theo Đánh giá độ thích nghi Thế hệ cuối? Nghiệm Danh mục đầu tư tại thời gian T Yes Tạo quần thể Các cá thể có Legacy_Size tốt nhất Ươm thế hệ tiếp theo Các cá thể có Legacy_Size tốt nhất Đánh giá độ thích nghi Thế hệ cuối ? Nghiệm Danh mục đầu tư tại thời gian T+1 No Yes Trang 95 c) Kỹ thuật chia sẻ mục tiêu (Objective Sharing) Chia sẻ mục tiêu là kỹ thuật thứ 2 mà ta sử dụng để thực hiện việc quản lý danh mục tối ưu đa mục tiêu. Kỹ thuật chia sẻ mục tiêu là kỹ thuật xác định khoảng cách Euclid giữa mỗi cá thể tức là nghiệm hiện tại và nghiệm tốt nhất từ kịch bản trước. Khoảng cách Euclid giữa 2 nghiệm được tính toán như mô tả trong công thức 5.1.4 Với việc tính hàm mục tiêu mới này, ta phải thay đổi quá trình tiến hóa cho cả hai. Mỗi thế hệ, một trong hai phương pháp tính độ thích nghi được sử dụng để đánh giá quần thể. Xác suất của một trong hai sẽ được chọn thông qua tham số pos với pos > 0. Tính độ thích nghi và tỉ số Sharpe Ration sẽ được lựa chọn với xác suất ௦ܲ௥ = 1 − ଵ௣೚ೞ. Phương pháp thứ 2 để tính mức độ thích nghi là dùng khoảng Euclid với xác suất lựa chọn: ௗܲ = ଵ௣೚ೞ Khi một trong hai mục tiêu được chọn thì quá trình lựa chọn và kỹ thuật ươm sẽ được thực hiện theo cùng cách đã mô tả trong phần trước, sau đó hàm mục tiêu còn lại sẽ được chọn cho thế hệ tiếp theo. Trong cách này, quần thể sẽ đáp ứng cả hai mục tiêu. Giá trị của pos có thể được điều chỉnh để xác định mức độ ưu tiên tương quan của 2 hàm mục tiêu. Trang 96 KẾT LUẬN Để kết thúc, chúng tôi tóm lược lại một số vấn đề chính yếu được nghiên cứu trong luận văn cùng các kết quả đạt được. Trong luận này tôi đã khảo sát một số phương pháp mới để giải bài toán tối ưu đa mục tiêu. Thứ nhất: Để khắc phục những hạn chế từ phương pháp tổng trọng số như: Người giải phải lựa chọn giá trị cho vector trọng số ݓ = (ݓଵ, …ݓ௡) tương ứng với n hàm mục tiêu của bài toán, nghiệm tối ưu không phân bố điều trên biên Pareto,…thì bằng phương pháp tổng trọng số chấp nhận được (được cải tiến từ phương pháp tổng trọng số) ta sẽ tìm được nhiều nghiệm tối ưu phân bố trên biên Pareto hơn bằng cách mịn hóa các đoạn (các siêu phẳng nếu là không gian có số chiều lớn hơn 2) được nối với nhau bằng hai điểm trên biên Pareto; tìm được nghiệm tối ưu trong miền không lồi và bỏ qua các nghiệm non- Pareto. Tuy nhiên do tính phức tạp của phương pháp này nên tôi quyết định không giải minh họa một bài toán cụ thể bằng Matlab. Thứ hai: Dựa trên thuật toán di truyền, luận văn đã giới thiệu một số phương pháp mới để giải bài toán tối ưu nhiều mục tiêu đó là: MOGA, SPEA2 và NSGA – II . Ưu điểm của các phương pháp này là có thể xấp xỉ một cách gần chính xác biên Pareto thực từ các cá thể hay nghiệm khởi tạo ngẫu nhiên ban đầu. Từ đó có thể chọn được nghiệm tối ưu tốt nhất cho bài toán tối ưu nhiều mục tiêu, thậm chí bài toán là không lồi. Đồng thời chúng tôi cũng minh hoạ các thuật toán thông qua việc giải các ví dụ bằng chương trình trên Matlab. Tuy nhiên thuật toán cũng có một số hạn chế là: sự hội tụ về biên Pareto thực phụ thuộc vào việc khởi tạo quần thể ban đầu và tốc độ hội tụ về biên Pareto thực còn chậm khi số lượng quần thể được lựa như là tiêu chuẩn dừng lớn. Sau khi đã giới thiệu và phân tích các ưu khuyết điểm của các thuật toán di truyền để giải bày toán tối ưu đa mục tiêu trong chương II chúng tôi sẽ trình bày những ứng dụng của chúng trong chương III, cụ thể là giải bài toán quản lý tối ưu danh mục đầu tư đa mục tiêu. Có thể hiểu một cách đơn giản về vấn đề đặt ra của bài toán này là làm sao tìm được các cổ phiếu mà có tổng lợi nhuận là lớn nhất với ít rủi ro nhất. Trong luận văn này chúng Trang 97 tôi chỉ đi phân tích và xây dựng các mô hình khác nhau cho bài toán quản lý tối ưu danh mục đầu tư mà vẫn chưa qua kiểm nghiệm trên các số liệu thực tế của các công ty chứng khoán tại Việt Nam và đây cũng là một trong những điều còn hạn chế trong luận văn. Trang 98 TÀI LIỆU THAM KHẢO Tiếng Việt [1] Nguyễn Hoàng Hải – Nguyễn Việt Anh (2004), Lập trình Matlab và ứng dụng, NXB KH & KT, Hà Nội. [2] Vũ ngọc Phàn (2005), Cơ sỡ lý thuyết và ứng dụng trong công nghệ bưu chính viễn thông, NXB Bưu điện. Tiếng Anh [1] Aravind Seshadri, Multi – Objective optimization using evolutionnary algorithm (Moea). [2] Ashish Ghosh – Stchidananda Dehuri (2004), Evolution algorithm for Multi- Criterion optimization: A survey, International journal of computing & information sciences, vol 2, no 1. [3] Abdullah Konak, David W. Coit, Alice E. Smithc (2006), Multi-objective optimization using genetic algorithms: A tutorial, Reliability Engineering and System Safety 91 (2006) 992–1007. [4] Abdullah Konak, David W. Coit, Alice E. Smith, Multi-Objective Optimization Using Genetic Algorithms: A Tutorial. [5] Claus Aranha (2007), Portfolio management with cost model using multi objective genetic algorithm. [6] Chueh-Yung Tsao, Chao-Kung Liu, Incorporating Value-at-Risk in Portfolio Selection: An Evolutionary Approach. [7] Dan Lin, Shouyang Wang, Hong Yan, a multiobjective genetic algorithm for porfolio selection problem. [8] Dr.-Ing. Dipl.-Inform. Jörn Mehnen (2005), Multiobjective Evolutionary Algorithms, 4th Workshop on Quality Improvement, Bommerholz. [9] Eckart Zitzler, A Tutorial on Evolutionary A Tutorial on Evolutionary Multiobjective Multiobjective Optimization Optimization. [10] Fangguo He Huan Qi Qiong Fan, An Evolutionary Algorithm for the Multi- objective Shortest Path Problem. Trang 99 [11] Jürgen Branke, Deb Kalyanmoy, Kaisa Miettinen, Ralph E. Steuer, Practical Approaches to Multi-Objective Optimization. [12] Kumara Sastry1, Martin Pelikan2, David E. Goldberg1, Limits of Scalability of Multi-objective Estimation of Distribution Algorithms. [13] Miss Sunantha Sodsee (2004), A multi-objective bisexual reproduction genetic algorithm for computer network design, ISBN 974-19-0316-2 [14] Matthias Ehrgott (2000), Multicriteria optimization”, Springer, ISBN 3-540- 67869-7. [15] Matthias Ehrgott, Multiobjective (Combinatorial) Optimisation –Some Thoughts on Applications. [16] Nur Evin Özdemirel (2002), Deb et al., A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Transactions on Evolutionary Computation 6. [17] Ralph E. Steuer, Yue Qi, Markus Hirschberger (2005), Multiple Objectives in Portfolio selection. [18] Ramesh Rajagopalan, Chilukuri K. Mohan, Kishan G. Mehrotra, and Pramod K. Varshney, An Evolutionary Multi-Objective Crowding Algorithm (EMOCA): Benchmark Test Function Results, NY 13244-4100 [19] Ralph E. Steuer and Yue Qi, Markus Hirschberger, Developments in Multi- Attribute Portfolio Selection. [20] P. Jana, T.K.Roy and S.K. Mazumder (2007), Multi-objective Mean-variance- skewness model for Portfolio Optimization, ISSN: 1841-4311 [21] Shapour Azar, Brian J. Reynolds, Sanjay Narayanan (1999), Comparison of two multiobjective optimization techniques with and within genetic algorithm, DETC99/DAC-8584 [22] Sabbir U. Ahmad and Andreas Antoniou Sabbir U. Ahmad and Andreas Antoniou, A Multiobjective Genetic Algorithm for the A Multiobjective Genetic Algorithm for the Design of Asymmetric FIR Filters Design of Asymmetric FIR Filter. [23] Tushar Goel, Elitist Non-dominated Sorting Genetic Algorithm: NSGA-II. [24] Tadahiko Murata (1997), Genetic algorithm for multi-objective optimization.

Các file đính kèm theo tài liệu này:

  • pdfMột lớp các phương pháp giải bài toán tối ưu nhiều mục tiêu.pdf
Luận văn liên quan