Multi-Space Evolutionary Search for Large-Scale Optimization
- URL: http://arxiv.org/abs/2102.11693v2
- Date: Wed, 24 Feb 2021 01:58:32 GMT
- Title: Multi-Space Evolutionary Search for Large-Scale Optimization
- Authors: Liang Feng, Qingxia Shang, Yaqing Hou, Kay Chen Tan and Yew-Soon Ong
- Abstract summary: This paper proposes a new search paradigm, namely the multi-space evolutionary search, to enhance the existing evolutionary search methods for solving large-scale optimization problems.
The proposed paradigm makes no assumptions about the large-scale optimization problem of interest, such as that the problem is decomposable or that a certain relationship exists among the decision variables.
- Score: 31.592330078642828
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In recent years, to improve the evolutionary algorithms used to solve
optimization problems involving a large number of decision variables, many
attempts have been made to simplify the problem solution space of a given
problem for the evolutionary search. In the literature, the existing approaches
can generally be categorized as decomposition-based methods and
dimension-reduction-based methods. The former decomposes a large-scale problem
into several smaller subproblems, while the latter transforms the original
high-dimensional solution space into a low-dimensional space. However, it is
worth noting that a given large-scale optimization problem may not always be
decomposable, and it is also difficult to guarantee that the global optimum of
the original problem is preserved in the reduced low-dimensional problem space.
This paper thus proposes a new search paradigm, namely the multi-space
evolutionary search, to enhance the existing evolutionary search methods for
solving large-scale optimization problems. In contrast to existing approaches
that perform an evolutionary search in a single search space, the proposed
paradigm is designed to conduct a search in multiple solution spaces that are
derived from the given problem, each possessing a unique landscape. The
proposed paradigm makes no assumptions about the large-scale optimization
problem of interest, such as that the problem is decomposable or that a certain
relationship exists among the decision variables. To verify the efficacy of the
proposed paradigm, comprehensive empirical studies in comparison to four
state-of-the-art algorithms were conducted using the CEC2013 large-scale
benchmark problems.
Related papers
- The Differentiable Feasibility Pump [49.55771920271201]
This paper shows that the traditional feasibility pump and many of its follow-ups can be seen as gradient-descent algorithms with specific parameters.
A central aspect of this reinterpretation is observing that the traditional algorithm differentiates the solution of the linear relaxation with respect to its cost.
arXiv Detail & Related papers (2024-11-05T22:26:51Z) - An Effective and Efficient Evolutionary Algorithm for Many-Objective
Optimization [2.5594423685710814]
We develop an effective evolutionary algorithm (E3A) that can handle various many-objective problems.
In E3A, inspired by SDE, a novel population maintenance method is proposed.
We conduct extensive experiments and show that E3A performs better than 11 state-of-the-art many-objective evolutionary algorithms.
arXiv Detail & Related papers (2022-05-31T15:35:46Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
We present an end-to-end method to learn the proximal operator across non-family problems.
We show that for weakly-ized objectives and under mild conditions, the method converges globally.
arXiv Detail & Related papers (2022-01-28T05:53:28Z) - Multidimensional Assignment Problem for multipartite entity resolution [69.48568967931608]
Multipartite entity resolution aims at integrating records from multiple datasets into one entity.
We apply two procedures, a Greedy algorithm and a large scale neighborhood search, to solve the assignment problem.
We find evidence that design-based multi-start can be more efficient as the size of databases grow large.
arXiv Detail & Related papers (2021-12-06T20:34:55Z) - Manifold Interpolation for Large-Scale Multi-Objective Optimization via
Generative Adversarial Networks [12.18471608552718]
Large-scale multiobjective optimization problems (LSMOPs) are characterized as involving hundreds or even thousands of decision variables and multiple conflicting objectives.
Previous research has shown that these optimal solutions are uniformly distributed on the manifold structure in the low-dimensional space.
In this work, a generative adversarial network (GAN)-based manifold framework is proposed to learn the manifold and generate high-quality solutions.
arXiv Detail & Related papers (2021-01-08T09:38:38Z) - Optimistic variants of single-objective bilevel optimization for
evolutionary algorithms [6.788217433800101]
A partial partial evolutionary approach has been proposed to solve the benchmark problems and have outstanding results.
A new variant has also been proposed to the commonly used convergence approaches, i.e. optimistic and pessimistic.
The experimental results demonstrate the algorithm converges differently to optimum solutions with the optimistic variants.
arXiv Detail & Related papers (2020-08-22T23:12:07Z) - Balancing Common Treatment and Epidemic Control in Medical Procurement
during COVID-19: Transform-and-Divide Evolutionary Optimization [10.29490155247067]
Balancing common disease treatment and epidemic control is a key objective of medical supplies procurement in hospitals during a pandemic such as COVID-19.
We present an approach that first transforms the original high-dimensional, constrained multiobjective optimization problem to a low-dimensional, unconstrained multiobjective optimization problem.
We show that the proposed approach exhibits significantly better performance than that of directly solving the original problem.
arXiv Detail & Related papers (2020-08-02T04:47:34Z) - Follow the bisector: a simple method for multi-objective optimization [65.83318707752385]
We consider optimization problems, where multiple differentiable losses have to be minimized.
The presented method computes descent direction in every iteration to guarantee equal relative decrease of objective functions.
arXiv Detail & Related papers (2020-07-14T09:50:33Z) - EOS: a Parallel, Self-Adaptive, Multi-Population Evolutionary Algorithm
for Constrained Global Optimization [68.8204255655161]
EOS is a global optimization algorithm for constrained and unconstrained problems of real-valued variables.
It implements a number of improvements to the well-known Differential Evolution (DE) algorithm.
Results prove that EOSis capable of achieving increased performance compared to state-of-the-art single-population self-adaptive DE algorithms.
arXiv Detail & Related papers (2020-07-09T10:19:22Z) - MineReduce: an approach based on data mining for problem size reduction [58.720142291102135]
This paper presents an approach named MineReduce, which uses mined patterns to perform problem size reduction.
We present an application of MineReduce to improve a for the heterogeneous fleet vehicle routing problem.
arXiv Detail & Related papers (2020-05-15T08:49:50Z) - Devolutionary genetic algorithms with application to the minimum
labeling Steiner tree problem [0.0]
This paper characterizes and discusses devolutionary genetic algorithms and evaluates their performances in solving the minimum labeling Steiner tree (MLST) problem.
We define devolutionary algorithms as the process of reaching a feasible solution by devolving a population of super-optimal unfeasible solutions over time.
We show how classical evolutionary concepts, such as crossing, mutation and fitness can be adapted to aim at reaching an optimal or close-to-optimal solution.
arXiv Detail & Related papers (2020-04-18T13:27:28Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.