Balancing Pareto Front exploration of Non-dominated Tournament Genetic Algorithm (B-NTGA) in solving multi-objective NP-hard problems with constraints

• URL: http://arxiv.org/abs/2410.05701v2
• Date: Mon, 14 Oct 2024 12:01:59 GMT
• Title: Balancing Pareto Front exploration of Non-dominated Tournament Genetic Algorithm (B-NTGA) in solving multi-objective NP-hard problems with constraints
• Authors: Michał Antkiewicz, Paweł B. Myszkowski,
• Abstract summary: The paper presents a new balanced selection operator applied to the proposed Balanced Non-dominated Tournament Genetic Algorithm (B-NTGA) The proposed B-NTGA is investigated on two benchmark multi- and many-objective optimization real-world problems, like Thief Traveling Problem and Multi-Skill Resource-Constrained Project Scheduling Problem. The results of experiments show that B-NTGA has a higher efficiency and better performance than state-of-the-art methods.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The paper presents a new balanced selection operator applied to the proposed Balanced Non-dominated Tournament Genetic Algorithm (B-NTGA) that actively uses archive to solve multi- and many-objective NP-hard combinatorial optimization problems with constraints. The primary motivation is to make B-NTGA more efficient in exploring Pareto Front Approximation (PFa), focusing on 'gaps' and reducing some PFa regions' sampling too frequently. Such a balancing mechanism allows B-NTGA to be more adaptive and focus on less explored PFa regions. The proposed B-NTGA is investigated on two benchmark multi- and many-objective optimization real-world problems, like Thief Traveling Problem and Multi-Skill Resource-Constrained Project Scheduling Problem. The results of experiments show that B-NTGA has a higher efficiency and better performance than state-of-the-art methods.

Related papers

• A Primal-Dual-Assisted Penalty Approach to Bilevel Optimization with Coupled Constraints [66.61399765513383]
  We develop a BLOCC algorithm to tackle BiLevel Optimization problems with Coupled Constraints. We demonstrate its effectiveness on two well-known real-world applications.
  arXiv  Detail & Related papers  (2024-06-14T15:59:36Z)
• A biased random-key genetic algorithm with variable mutants to solve a vehicle routing problem [0.0]
  The paper explores the Biased Random-Key Genetic Algorithm (BRKGA) in the domain of logistics and vehicle routing. The application of the algorithm is contextualized within the framework of the Vehicle Routing Problem with Occasional Drivers and Time Window (VRPODTW) This research introduces a new BRKGA, characterized by a variable mutant population which can vary from generation to generation, named BRKGA-VM.
  arXiv  Detail & Related papers  (2024-05-01T01:25:16Z)
• An Efficient Learning-based Solver Comparable to Metaheuristics for the Capacitated Arc Routing Problem [67.92544792239086]
  We introduce an NN-based solver to significantly narrow the gap with advanced metaheuristics. First, we propose direction-aware facilitating attention model (DaAM) to incorporate directionality into the embedding process. Second, we design a supervised reinforcement learning scheme that involves supervised pre-training to establish a robust initial policy.
  arXiv  Detail & Related papers  (2024-03-11T02:17:42Z)
• A Constrained Optimization Approach to Bilevel Optimization with Multiple Inner Minima [49.320758794766185]
  We propose a new approach, which convert the bilevel problem to an equivalent constrained optimization, and then the primal-dual algorithm can be used to solve the problem. Such an approach enjoys a few advantages including (a) addresses the multiple inner minima challenge; (b) fully first-order efficiency without Jacobian computations.
  arXiv  Detail & Related papers  (2022-03-01T18:20:01Z)
• Niching-based Evolutionary Diversity Optimization for the Traveling Salesperson Problem [17.268191781480745]
  We consider the problem of finding a set of tours to a traveling salesperson problem (TSP) instance maximizing diversity, while satisfying a given cost constraint. This study aims to investigate the effectiveness of applying niching to maximize diversity rather than simply maintaining it.
  arXiv  Detail & Related papers  (2022-01-25T13:40:27Z)
• 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)
• Improved Branch and Bound for Neural Network Verification via Lagrangian Decomposition [161.09660864941603]
  We improve the scalability of Branch and Bound (BaB) algorithms for formally proving input-output properties of neural networks. We present a novel activation-based branching strategy and a BaB framework, named Branch and Dual Network Bound (BaDNB) BaDNB outperforms previous complete verification systems by a large margin, cutting average verification times by factors up to 50 on adversarial properties.
  arXiv  Detail & Related papers  (2021-04-14T09:22:42Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)
• A Multifactorial Optimization Paradigm for Linkage Tree Genetic Algorithm [13.056730270950235]
  We introduce Multifactorial Tree Genetic Algorithm (MF-LTGA) to tackle multiple optimization tasks at the same time. MF-LTGA is able to tackle multiple optimization tasks at the same time, each task learns the dependency between problem variables from the shared representation. In comparison to LTGA and existing methods, MF-LTGA outperforms in quality of the solution or in time.
  arXiv  Detail & Related papers  (2020-05-06T19:28:39Z)
• Tip the Balance: Improving Exploration of Balanced Crossover Operators by Adaptive Bias [2.610470075814367]
  The use of balanced crossover operators in Genetic Algorithms (GA) ensures that the binary strings generated as offsprings have the same Hamming weight of the parents. Although this method reduces the size of the search space, the resulting fitness landscape often becomes more difficult for the GA to explore. This issue has been studied in this paper by applying an adaptive bias strategy to a counter-based crossover operator.
  arXiv  Detail & Related papers  (2020-04-23T17:26:43Z)
• 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)

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.