Search

When solving constrained multiobjective optimization problems, an important issue is how to balance convergence, diversity, and feasibility simultaneously. To address this issue, this paper proposes a parameter-free constraint handling technique, a two-archive evolutionary algorithm, for constrained multiobjective optimization. It maintains two collaborative archives simultaneously: one, denoted as the convergence-oriented archive (CA), is the driving force to push the population toward the Pareto front; the other one, denoted as the diversity-oriented archive (DA), mainly tends to maintain the population diversity. In particular, to complement the behavior of the CA and provide as much diversified information as possible, the DA aims at exploring areas under-exploited by the CA including the infeasible regions. To leverage the complementary effects of both archives, we develop a restricted mating selection mechanism that adaptively chooses appropriate mating parents from them according to their evolution status. Comprehensive experiments on a series of benchmark problems and a real-world case study fully demonstrate the competitiveness of our proposed algorithm, in comparison to five state-of-the-art constrained evolutionary multiobjective optimizers. [ABSTRACT FROM AUTHOR]

Nurse rostering is an important search problem with many constraints. In the literature, a number of approaches have been investigated including penalty function methods to tackle these constraints within genetic algorithm frameworks. In this paper, we investigate an extension of a previously proposed stochastic ranking method, which has demonstrated superior performance to other constraint handling techniques when tested against a set of constrained optimization benchmark problems. An initial experiment on nurse rostering problems demonstrates that the stochastic ranking method is better at finding feasible solutions, but fails to obtain good results with regard to the objective function. To improve the performance of the algorithm, we hybridize it with a recently proposed simulated annealing hyper-heuristic (SAHH) within a local search and genetic algorithm framework. Computational results show that the hybrid algorithm performs better than both the genetic algorithm with stochastic ranking and the SAHH alone. The hybrid algorithm also outperforms the methods in the literature which have the previously best known results. [ABSTRACT FROM AUTHOR]

This paper proposes a constraint handling technique for multiobjective evolutionary algorithms based on an adaptive penalty function and a distance measure. These two functions dependent upon the objective function value and the sum of constraint violations of an individual. Through this design, the objective space is modified to account for the performance and constraint violation of each individual. The modified objective functions are used in the nondominance sorting to facilitate the search of optimal solutions not only in the feasible space but also in the infeasible regions. The search in the infeasible space is designed to exploit those individuals with better objective values and lower constraint violations. The number of feasible individuals in the population is used to guide the search process either toward finding more feasible solutions or favor in search for optimal solutions. The proposed method is simple to implement and does not need any parameter tuning. The constraint handling technique is tested on several constrained multiobjective optimization problems and has shown superior results compared to some chosen state-of-the-art designs. [ABSTRACT FROM AUTHOR]

In this paper, we propose a generic, two-phase framework for solving constrained optimization problems using genetic algorithms. In the first phase of the algorithm, the objective function is completely disregarded and the constrained optimization problem is treated as a constraint satisfaction problem. The genetic search is directed toward minimizing the constraint violation of the solutions and eventually finding a feasible solution. A linear rank-based approach is used to assign fitness values to the individuals. The solution with the least constraint violation is archived as the elite solution in the population. In the second phase, the simultaneous optimization of the objective function and the satisfaction of the constraints are treated as a biobjective optimization problem. We elaborate on how the constrained optimization problem requires a balance of exploration and exploitation under different problem scenarios and come to the conclusion that a non-dominated ranking between the individuals will help the algorithm explore further, while the elitist scheme will facilitate in exploitation. We analyze the proposed algorithm under different problem scenarios using Test Case Generator-2 and demonstrate the proposed algorithm's capability to perform well independent of various problem characteristics. In addition, the proposed algorithm performs competitively with the state-of-the-art constraint optimization algorithms on 11 test cases which were widely studied benchmark functions in literature. [ABSTRACT FROM AUTHOR]

To prevent the population from getting stuck in local areas and then missing the constrained Pareto front fragments in dealing with constrained multiobjective optimization problems (CMOPs), it is important to guide the population to evenly explore the promising areas that are not dominated by all examined feasible solutions. To this end, we first introduce a cost value-based distance into the objective space, and then use this distance and the constraints to define an indicator to evaluate the contribution of each individual to exploring the promising areas. Theoretical studies show that the proposed indicator can effectively guide population to focus on exploring the promising areas without crowding in local areas. Accordingly, we propose a new constraint handling technique (CHT) based on this indicator. To further improve the diversity of population in the promising areas, the proposed indicator-based CHT divides the promising areas into multiple subregions, and then gives priority to removing the individuals with the worst fitness values in the densest subregions. We embed the indicator-based CHT in evolutionary algorithm and propose an indicator-based constrained multiobjective algorithm for solving CMOPs. Numerical experiments on several benchmark suites show the effectiveness of the proposed algorithm. Compared with six state-of-the-art constrained evolutionary multiobjective optimization algorithms, the proposed algorithm performs better in dealing with different types of CMOPs, especially in those problems that the individuals are easy to appear in the local infeasible areas that dominate the constrained Pareto front fragments. [ABSTRACT FROM AUTHOR]

Constrained optimization problems (COPs) are frequently encountered in real-world design applications. For some COPs, the evaluation of the objective(s) and/or constraint(s) may involve significant computational/temporal/financial cost. Such problems are referred to as expensive COPs (ECOPs). Surrogate modeling has been widely used in conjunction with optimization methods for such problems, wherein the search is partially driven by an approximate function instead of true expensive evaluations. However, for any true evaluation, nearly all existing methods compute all objective and constraint values together as one batch. Such full evaluation approaches may be inefficient for cases where the objective/constraint(s) can be evaluated independently of each other. In this article, we propose and study a constraint handling strategy for ECOPs using partial evaluations. The constraints are evaluated in a sequence determined based on their likelihood of being violated; and the evaluation is aborted if a constraint violation is encountered. Modified ranking strategies are introduced to effectively rank the solutions using the limited information thus obtained, while saving on significant function evaluations. The proposed algorithm is compared with a number of its variants to establish the utility of its key components systematically. Numerical experiments and benchmarking are conducted on a range of mathematical and engineering design problems to demonstrate the efficacy of the approach compared to state-of-the-art evolutionary optimization approaches. [ABSTRACT FROM AUTHOR]

Constrained multiobjective optimization problems (CMOPs) widely exist in real-world applications, and they are challenging for conventional evolutionary algorithms (EAs) due to the existence of multiple constraints and objectives. When the number of objectives or decision variables is scaled up in CMOPs, the performance of EAs may degenerate dramatically and may fail to obtain any feasible solutions. To address this issue, we propose a paired offspring generation-based multiobjective EA for constrained large-scale optimization. The general idea is to emphasize the role of offspring generation in reproducing some promising feasible or useful infeasible offspring solutions. We first adopt a small set of reference vectors for constructing several subpopulations with a fixed number of neighborhood solutions. Then, a pairing strategy is adopted to determine some pairwise parent solutions for offspring generation. Consequently, the pairwise parent solutions, which could be infeasible, may guide the generation of well-converged solutions to cross the infeasible region(s) effectively. The proposed algorithm is evaluated on CMOPs with up to 1000 decision variables and ten objectives. Moreover, each component in the proposed algorithm is examined in terms of its effect on the overall algorithmic performance. Experimental results on a variety of existing and our tailored test problems demonstrate the effectiveness of the proposed algorithm in constrained large-scale multiobjective optimization. [ABSTRACT FROM AUTHOR]

Operational researchers and decision modelers have aspired to optimization technologies with a self-adaptive mechanism to cope with new problem formulations. Self-adaptive mechanisms not only free users from low-level and complex development tasks to enhance optimization efficiency but also allow them to focus on addressing high-level real-world operational requirements. In recent years, there has been a growing interest in applying machine learning and artificial intelligence techniques to improve self-adaptive mechanisms. However, learning to optimize hard combinatorial optimization problems remains a challenging task. This article proposes a new genetic programming approach to evolve efficient variable selectors to enhance the search mechanism in constraint programming. Starting with a set of training instances for a specific combinatorial optimization problem, the proposed approach evaluates variable selectors and evolves them to be more efficient over a number of generations. The novelties of our proposed approach are threefold: 1) a new representation of variable selectors; 2) a new mechanism for fitness evaluations; and 3) a preselection technique. We examine performance of the proposed approach on different job-shop scheduling problems, and the results show that variable selectors can be evolved efficiently. In particular, there are substantial reductions in the computational effort required for the search component of the constraint solver as well as increased chances of finding the optimal solutions. Further analyses also confirm the efficacy of our approach in respect to scalability, generalization, and interpretability of the evolved variable selectors. [ABSTRACT FROM AUTHOR]

Constrained multiobjective optimization problems (CMOPs) are challenging because of the difficulty in handling both multiple objectives and constraints. While some evolutionary algorithms have demonstrated high performance on most CMOPs, they exhibit bad convergence or diversity performance on CMOPs with small feasible regions. To remedy this issue, this article proposes a coevolutionary framework for constrained multiobjective optimization, which solves a complex CMOP assisted by a simple helper problem. The proposed framework evolves one population to solve the original CMOP and evolves another population to solve a helper problem derived from the original one. While the two populations are evolved by the same optimizer separately, the assistance in solving the original CMOP is achieved by sharing useful information between the two populations. In the experiments, the proposed framework is compared to several state-of-the-art algorithms tailored for CMOPs. High competitiveness of the proposed framework is demonstrated by applying it to 47 benchmark CMOPs and the vehicle routing problem with time windows. [ABSTRACT FROM AUTHOR]