A Hybrid Decomposition-based Multi-objective Evolutionary Algorithm for
the Multi-Point Dynamic Aggregation Problem
- URL: http://arxiv.org/abs/2105.04934v1
- Date: Tue, 11 May 2021 10:53:16 GMT
- Title: A Hybrid Decomposition-based Multi-objective Evolutionary Algorithm for
the Multi-Point Dynamic Aggregation Problem
- Authors: Guanqiang Gao, Bin Xin, Yi Mei, Shuxin Ding, and Juan Li
- Abstract summary: This paper focuses on a multi-objective MPDA problem which is to design an execution plan of the robots.
We develop a hybrid decomposition-based multi-objective evolutionary algorithm (HDMOEA) using $ varepsilon $-constraint method.
Experimental results show that the proposed HDMOEA method significantly outperforms the state-of-the-art methods in terms of several most-used metrics.
- Score: 2.6474550925822964
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: An emerging optimisation problem from the real-world applications, named the
multi-point dynamic aggregation (MPDA) problem, has become one of the active
research topics of the multi-robot system. This paper focuses on a
multi-objective MPDA problem which is to design an execution plan of the robots
to minimise the number of robots and the maximal completion time of all the
tasks. The strongly-coupled relationships among robots and tasks, the
redundancy of the MPDA encoding, and the variable-size decision space of the
MO-MPDA problem posed extra challenges for addressing the problem effectively.
To address the above issues, we develop a hybrid decomposition-based
multi-objective evolutionary algorithm (HDMOEA) using $ \varepsilon
$-constraint method. It selects the maximal completion time of all tasks as the
main objective, and converted the other objective into constraints. HDMOEA
decomposes a MO-MPDA problem into a series of scalar constrained optimization
subproblems by assigning each subproblem with an upper bound robot number. All
the subproblems are optimized simultaneously with the transferring knowledge
from other subproblems. Besides, we develop a hybrid population initialisation
mechanism to enhance the quality of initial solutions, and a reproduction
mechanism to transmit effective information and tackle the encoding redundancy.
Experimental results show that the proposed HDMOEA method significantly
outperforms the state-of-the-art methods in terms of several most-used metrics.
Related papers
- Weighted strategies to guide a multi-objective evolutionary algorithm
for multi-UAV mission planning [12.97430155510359]
This work proposes a weighted random generator for the creation and mutation of new individuals.
The main objective of this work is to reduce the convergence rate of the MOEA solver for multi-UAV mission planning.
arXiv Detail & Related papers (2024-02-28T23:05:27Z) - A First-Order Multi-Gradient Algorithm for Multi-Objective Bi-Level Optimization [7.097069899573992]
We study the Multi-Objective Bi-Level Optimization (MOBLO) problem.
Existing gradient-based MOBLO algorithms need to compute the Hessian matrix.
We propose an efficient first-order multi-gradient method for MOBLO, called FORUM.
arXiv Detail & Related papers (2024-01-17T15:03:37Z) - Towards Multi-Objective High-Dimensional Feature Selection via
Evolutionary Multitasking [63.91518180604101]
This paper develops a novel EMT framework for high-dimensional feature selection problems, namely MO-FSEMT.
A task-specific knowledge transfer mechanism is designed to leverage the advantage information of each task, enabling the discovery and effective transmission of high-quality solutions.
arXiv Detail & Related papers (2024-01-03T06:34:39Z) - Multi-Objective Policy Gradients with Topological Constraints [108.10241442630289]
We present a new algorithm for a policy gradient in TMDPs by a simple extension of the proximal policy optimization (PPO) algorithm.
We demonstrate this on a real-world multiple-objective navigation problem with an arbitrary ordering of objectives both in simulation and on a real robot.
arXiv Detail & Related papers (2022-09-15T07:22:58Z) - Large-scale matrix optimization based multi microgrid topology design
with a constrained differential evolution algorithm [30.792124441010447]
A binary-matrix-based differential evolution algorithm is proposed to solve nonlinear problems.
To deal with the constraints, we propose an improved feasibility rule based environmental selection strategy.
arXiv Detail & Related papers (2022-07-18T00:35:29Z) - Collaborative Intelligent Reflecting Surface Networks with Multi-Agent
Reinforcement Learning [63.83425382922157]
Intelligent reflecting surface (IRS) is envisioned to be widely applied in future wireless networks.
In this paper, we investigate a multi-user communication system assisted by cooperative IRS devices with the capability of energy harvesting.
arXiv Detail & Related papers (2022-03-26T20:37:14Z) - Neural Stochastic Dual Dynamic Programming [99.80617899593526]
We introduce a trainable neural model that learns to map problem instances to a piece-wise linear value function.
$nu$-SDDP can significantly reduce problem solving cost without sacrificing solution quality.
arXiv Detail & Related papers (2021-12-01T22:55:23Z) - Result Diversification by Multi-objective Evolutionary Algorithms with
Theoretical Guarantees [94.72461292387146]
We propose to reformulate the result diversification problem as a bi-objective search problem, and solve it by a multi-objective evolutionary algorithm (EA)
We theoretically prove that the GSEMO can achieve the optimal-time approximation ratio, $1/2$.
When the objective function changes dynamically, the GSEMO can maintain this approximation ratio in running time, addressing the open question proposed by Borodin et al.
arXiv Detail & Related papers (2021-10-18T14:00:22Z) - Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learning [89.31889875864599]
We propose an efficient model-based reinforcement learning algorithm for learning in multi-agent systems.
Our main theoretical contributions are the first general regret bounds for model-based reinforcement learning for MFC.
We provide a practical parametrization of the core optimization problem.
arXiv Detail & Related papers (2021-07-08T18:01:02Z) - Multifactorial Cellular Genetic Algorithm (MFCGA): Algorithmic Design,
Performance Comparison and Genetic Transferability Analysis [17.120962133525225]
Multiobjective optimization is an incipient research area which is lately gaining a notable research momentum.
In this work we propose a novel algorithmic scheme for Multifactorial Optimization scenarios.
The proposed MFCGA hinges on concepts from Cellular Automata to implement mechanisms for exchanging knowledge among problems.
arXiv Detail & Related papers (2020-03-24T11:03:55Z) - Multi-factorial Optimization for Large-scale Virtual Machine Placement
in Cloud Computing [15.840835256016259]
Evolutionary algorithms (EAs) have been performed promising-solving on virtual machine placement (VMP) problems in the past.
As growing demand for cloud services, the existing EAs fail to implement in large-scale virtual machine placement problem.
This paper aims to apply the MFO technology to the LVMP problem in heterogeneous environment.
arXiv Detail & Related papers (2020-01-18T02:59:18Z)
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.