یک کاوشگر هدایت شونده عملگر جهش جدید و کاربرد آن برای حل کاردینالیتی محدودیت مشکل بهینه سازی سبد سرمایه گذاری
|کد مقاله||سال انتشار||مقاله انگلیسی||ترجمه فارسی||تعداد کلمات|
|23829||2014||17 صفحه PDF||سفارش دهید||11668 کلمه|
Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)
Journal : Expert Systems with Applications, Volume 41, Issue 14, 15 October 2014, Pages 6274–6290
This paper revisits the classical Polynomial Mutation (PLM) operator and proposes a new probe guided version of the PLM operator designed to be used in conjunction with Multiobjective Evolutionary Algorithms (MOEAs). The proposed Probe Guided Mutation (PGM) operator is validated by using data sets from six different stock markets. The performance of the proposed PGM operator is assessed in comparison with the one of the classical PLM with the assistance of the Non-dominated Sorting Genetic Algorithm II (NSGAII) and the Strength Pareto Evolutionary Algorithm 2 (SPEA2). The evaluation of the performance is based on three performance metrics, namely Hypervolume, Spread and Epsilon indicator. The experimental results reveal that the proposed PGM operator outperforms with confidence the performance of the classical PLM operator for all performance metrics when applied to the solution of the cardinality constrained portfolio optimization problem (CCPOP). We also calculate the True Efficient Frontier (TEF) of the CCPOP by formulating the CCPOP as a Mixed Integer Quadratic Program (MIQP) and we compare the relevant results with the approximate efficient frontiers that are generated by the proposed PGM operator. The results confirm that the PGM operator generates near optimal solutions that lie very close or in certain cases overlap with the TEF.
Evolutionary algorithms (EAs) have been increasingly applied over the past years for the solution of optimization problems with multiple objectives. The typical Multiobjective Evolutionary Algorithm (MOEA) utilizes three basic operators: selection, crossover and mutation (Metaxiotis & Liagkouras, 2012). However, the available literature regarding the variation operators for evolutionary multiobjective optimization remains relatively small. In particular, the mutation operator has received little attention and the majority of MOEAs make use of the Polynomial Mutation (PLM) operator proposed by Deb and Goyal (1996). Later, Deb and Tiwari (2008) proposed a highly disruptive version of the Polynomial Mutation that has been utilized in the latest version of NSGA-II (Deb, Pratap, Agarwal, & Meyarivan, 2002) and SPEA2 (Zitzler, Laumanns, & Thiele, 2001). This paper proposes a new version of the highly disruptive Polynomial Mutation (PLM) named Probe Guided Mutation (PGM) operator that produces better results. More recently, Da Ronco and Benini (2013) presented a Shrink-Mutation operator for MOEAs that belongs to the Gaussian mutations category. However, as the authors admit the PLM operator when applied to IBEA algorithm gives better results than the Shrink-Mutation operator in terms of convergence towards the True Pareto Front (Da Ronco & Benini, 2013). Das, Mallipeddi, and Maity (2013) presented a p-best mutation strategy for Evolutionary Programming (EP). EP relies mainly on its mutation operator for function optimization. Shortly the p-best mutation operator entails that any one of the p top-ranked population members according to fitness value is selected randomly for mutation. Tang and Tseng (2013) presented a new mutation operator called ADM for real coded Genetic Algorithms (GAs). According to the authors, the ADM mutation operator enhances the abilities of GAs in searching global optima as well as in speeding convergence by integrating a local directional search and adaptive random search strategies. The majority of the most recent mutation operators have been developed for differential evolution (DE) algorithms. Thus, Zhou, Li, and Gao (2013) proposed a new mutation operator called intersect mutation differential evolution (IMDE) algorithm. Alguliev, Aliguliyev, and Isazade (2012) proposed a new DE algorithm based on self-adaptive mutation and crossover (DESAMC). The proposed method dynamically adapts scale factor and crossover rate. Gong, Cai, and Liang (2014) present a ranking-based mutation operator that makes the DE algorithm to converge faster. Although the considerable amount of the ongoing work related to mutation operators and their importance for the performance of the entire algorithm, we noticed that the study of mutation operators in the context of MOEAs remains relatively rare. The PLM operator remains undoubtedly the mutation operator of choice when it comes to MOEAs. The motivation of this study is to build on the existing PLM and present a mechanism (the PGM) that allows the better exploration of solution space and is able to generate near optimal solutions that lie very close to the True Efficient Frontier (TEF). The remainder of the paper is organized as follows. In Section 2, a description of the highly disruptive Polynomial Mutation (PLM) is given and in Section 3 the proposed Probe Guided Mutation (PGM) and the formulation of the cardinality constrained portfolio optimization problem (CCPOP) are presented. In Section 4 the implementation of the cardinality constraint and lower and upper bound to the MOEA are presented. The parameters setup is presented in Section 5.1 and in Section 5.2 we formulate the CCPOP as a Mixed Integer Quadratic Program (MIQP) and we extract the True Efficient Frontier for each one of the examined problems with the assistance of CPLEX 12.5. Section 6 presents the performance metrics. In Section 7 we test the performance of the proposed PGM by using data sets from six different stock markets for the solution of the CCPOP. In Section 8 the results are analyzed and finally, Section 9 concludes the paper.
نتیجه گیری انگلیسی
This paper presents a new Probe Guided Mutation (PGM) operator and its application for solving the cardinality constrained portfolio optimization problem (CCPOP). The proposed mutation operator incorporates a fitness functions evaluation mechanism that allows the evaluation of the corresponding fitness for the left hand side region and the right hand side region of the parent solution. The selection between the two alternative child solutions is done with the assistance of the Pareto optimality conditions. Thanks to the PGM operator the algorithm is able to move fast towards the higher fitness regions of the search landscape and discover near optimal solutions. The evaluation of the proposed mutation operator is done with the assistance of six portfolio optimization problems (port1–6) that correspond to six different capital markets. The size of these problems varies from 31 stocks for the smallest and up to 457 stocks for the largest problem. The performance of the proposed PGM operator is assessed in comparison with the classical Polynomial Mutation operator (PLM) with the assistance of two well-known MOEAs, namely the Non-dominated Sorting Genetic Algorithm II (NSGAII) and Strength Pareto Evolutionary Algorithm 2 (SPEA2) for the solution of the CCPOP. The evaluation of the performance is based on a variety of metrics that assess both the proximity of the solutions to the Pareto front and their dispersion on it. The relevant results indicate that the proposed mutation operator outperforms with confidence the PLM operator for all performance metrics, when applied to the NSGAII and SPEA2. We also wanted to find out how well the PGM operator performs when compared to the True Pareto Efficient frontier of the CCPOP. For that purpose, we formulated the CCPOP as a Mixed Integer Quadratic Program (MIQP) and we calculated a number of exact points for each one of the port1–5 portfolio optimization problems with the assistance of CPLEX version 12.5. We found out that the approximate efficient frontiers that are generated by the proposed PGM operator demonstrate a remarkable concentration of the search effort very close or in some cases on top of the True Efficient Frontier (CPLEX). On the contrary, the approximate efficient frontiers that are generated by the classical PLM produce a considerable number of points far away from the True Efficient Frontier and on top of that they demonstrate discontinuities especially for the higher levels of risk and return combinations. Finally, we carried out a final test in order to demonstrate the exploratory capabilities of the proposed methodology. In particular, we revisited the port2 test problem, but this time we used only 40,000 evaluations for the PGM and 200,000 evaluations for the PLM to compensate for the extra fitness functions evaluations introduced by the PGM. We found out that the PGM operator still outperforms with confidence the PLM operator for all performance metrics, when applied to the NSGAII and SPEA2, although we only used a fraction of the evaluations that are being used for the PLM. In our future work, we will attempt to develop a technique that will update the mutation probability (Pm) at run-time according to the performance of the algorithm in a number of metrics such as the hypervolume or epsilon indicator.