A Manifold Learning-Based Multi-Objective Estimation Of Distribution Algorithm

Multi-Objective Problems arise in many scientific research and engineering areas, which generally contain multiple conflicting objectives and no single solution can optimize all the objectives at the same time. In order to find a best design, we must solve multi-objective and multi-constrained optimization problems, namely multi-objective optimization problems (Multi-Objective Optimization Problems, MOPs).Multi-objective optimization problems are usually different from single objective optimization problems, the optimal solutions of multi-objective optimization problems is a set. Multi-objective evolutionary algorithm (MOEA) is a kind of intelligent and heuristic search algorithm. They are based on population and the solutions form a set, thus they are becoming the most effective approach for solving multi-objective optimization problems. Traditional multi-objective evolutionary algorithms use crossover and mutation operators to generate new solutions, and best solutions are kept to next generation from elitist selection operator. MOEA iterates in this way until finds the final solution set. But there are still many shortcomings:(1) crossover and mutation operators reduce the performance of the algorithms when algorithm is close to convergence; (2) Reproduction operators such as crossover and mutation, were originally developed for scalar optimization. For many multi-objective problems, their Pareto Sets usually have a distribution rules in decision space. However, these distribution properties are ignored by traditional reproduction operators.Estimation of distribution algorithm (EDA) is another excellent intelligent optimization algorithm. Different from the traditional evolutionary algorithm, it does not use crossover or mutation operator, it explicitly extracts globally statistical information from current solutions and builds a probability distribution model of promising solutions instead. Based on extracted information, new solutions are sampled from the model thus built. EDA gains a focus from different researchers and scholars because it makes a good use of distribution information of population. In 2007, Qingfu Zhang etc. proposed a regularity model-based multi-objective estimation of distribution algorithm (RM-MEDA) for continuous multi-objective optimization problems with variable linkages. RM-MEDA captured and utilized the regularity of the Pareto set in the decision space based on the regularity property:under mild smoothness conditions, the Pareto set (in the decision space) of continuous MOP is a piecewise continuous (m-1)-dimension manifold, where m is the number of objectives. Systematic experiments have showed that RM-MEDA outperforms GDE3, PCX-NSGA-â…¡and MIDEA on a set of test instances with variable linkages. In fact RM-MEDA also has some shortcomings such as the need to partition clusters, the complex of probabilistic modeling and much time cost. Especially in early stage of algorithm, regularity property of the distribution is not obvious, new solutions generated from the probability model make the search direction far away from the actual search direction, the algorithm does not effectively use the individual's local information as well.Based on the above background, this paper proposes a manifold learning-based multi-objective estimation of distribution algorithm (ML-MEDA). In order to make better use of population's manifold structure, the algorithm introduces the manifold learning methods, using self-organizing map (SOM) to learn the manifold structure. This algorithm also uses an adaptive strategy integrating the SOM modeling operation and genetic reproduction operators. At the beginning of the algorithm, most part of solutions is generated by reproduction operators, and more and more solutions are generated from manifold model built by SOM as algorithm iterates. In this algorithm, we use both SOM's exploitation ability to global information and genetic operators' exploration ability to local information between individuals. Therefore, this algorithm proposed in this paper effectively combines the advantages of multi-objective evolutionary algorithm and multi-objective estimation of distribution algorithm.In this paper, three different categories of test problems are adopted to evaluate the algorithm's capability with NSGA-â…¡and RM-MEDA. These test problems are non variable linkage,linear variable linkage and nonlinear variable linkage. From the experimental results on test instances with non variable linkage, it is clear that ML-MEDA is better than the other two algorithms on convergence and IGD metrics, and RM-MEDA has best diversity. On test instances with linear variable linkage, RM-MEDA and ML-MEDA are much better than NSGA-â…¡with three metrics. The experimental results on nonlinear variable linkage test instances show that RM-MEDA has best performance, ML-MEDA is slightly worse than RM-MEDA, and NSGA-â…¡which uses traditional crossover and mutation operations has worst diversity, it is even difficult to find the whole Pareto optimal front. Overall, the proposed algorithm in this paper performs well on various test problems, and the introduction of SOM for learning the manifold structure of PS is proved to be feasible.