Overlapping solutions occur when more than one solution in the space of decisions maps to the same solution in the space of objectives. This situation threatens the exploration capacity of multiobjective Evolutionary...
详细信息
Overlapping solutions occur when more than one solution in the space of decisions maps to the same solution in the space of objectives. This situation threatens the exploration capacity of multiobjective Evolutionary Algorithms (MOEAs), preventing them from having a good diversity in their population. The influence of overlapping solutions is intensified on multi-objectivecombinatorialproblems with a low number of objectives. This paper presents a hybrid MOEA for handling overlapping solutions that combines the classic NSGA-II with a strategy based on objective Space Division (OSD). Basically, in each generation of the algorithm, the objective space is divided into several regions using the nadir solution calculated from the current generation solutions. Furthermore, the solutions in each region are classified into non-dominated fronts using different optimization strategies in each of them. This significantly enhances the achieved diversity of the approximate front of non-dominated solutions. The proposed algorithm (called NSGA-II/OSD) is tested on a classic Operations Research problem: the multi-objective Knapsack Problem (0-1 MOKP) with two objectives. Classic NSGA-II, MOEA/D and Global WASF-GA are used to compare the performance of NSGA-II/OSD. In the case of MOEA/D two different versions are implemented, each of them with a different strategy for specifying the reference point. These MOEA/D reference point strategies are thoroughly studied and new insights are provided. This paper analyses in depth the impact of overlapping solutions on MOEAs, studying the number of overlapping solutions, the number of solution repairs, the hypervolume metric, the attainment surfaces and the approximation to the real Pareto front, for different sizes of 0-1 MOKPs with two objectives. The proposed method offers very good performance when compared to the classic NSGA-II, MOEA/D and Global WASF-GA algorithms, all of them well-known in the literature.
This paper deals with an interesting facility location problem known as the bi-objective p-Median and p-Dispersion problem (BpMD problem). The BpMD problem seeks to locate p facilities to service a set of n demand poi...
详细信息
This paper deals with an interesting facility location problem known as the bi-objective p-Median and p-Dispersion problem (BpMD problem). The BpMD problem seeks to locate p facilities to service a set of n demand points, and the goal is to minimize the total distance between facilities and demand points and, simultaneously, maximize the minimum distance between all pairs of hosted facilities. The problem is addressed with a novel path relinking approach, called reactive path relinking, which hybridizes two of the most extended path relinking variants: interior path relinking and exterior path relinking. Additionally, the proposal is adapted to a multi-objective perspective for finding a good approximation of the Pareto front. Computational results prove the superiority of the proposed algorithm over the best procedures found in the literature.
multi-objectiveoptimizationproblems often lead to large nondominated sets, as the size of the problem or the number of objectives increases. Generating the whole nondominated set requires significant computation tim...
详细信息
multi-objectiveoptimizationproblems often lead to large nondominated sets, as the size of the problem or the number of objectives increases. Generating the whole nondominated set requires significant computation time, while most of the corresponding solutions are irrelevant to the decision maker. Another approach consists in obtaining preference information, which reduces the computation time and produces one or a very limited number of solutions. This requires the elicitation of precise preference parameters most of the time, which is often difficult and partly arbitrary, and might discard solutions of interest. An intermediate approach consists in using partial preference models. In this thesis, we present several partial preference models. We especially focused on the generation of the nondominated set according to these preference relations. This approach shows competitive performances both on computation time and quality of the generated preferred sets.
暂无评论