Evolutionary Algorithm and Multifactorial Evolutionary Algorithm on Clustered Shortest-Path Tree problem

• URL: http://arxiv.org/abs/2010.09309v1
• Date: Mon, 19 Oct 2020 08:37:18 GMT
• Title: Evolutionary Algorithm and Multifactorial Evolutionary Algorithm on Clustered Shortest-Path Tree problem
• Authors: Phan Thi Hong Hanh, Pham Dinh Thanh and Huynh Thi Thanh Binh
• Abstract summary: Clustered Shortest-Path Tree Problem (CluSPT) is an NP-hard problem. To enhance the performance of the search process, two approaches are proposed.
• Score: 2.578242050187029
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In literature, Clustered Shortest-Path Tree Problem (CluSPT) is an NP-hard problem. Previous studies often search for an optimal solution in relatively large space. To enhance the performance of the search process, two approaches are proposed: the first approach seeks for solutions as a set of edges. From the original graph, we generate a new graph whose vertex set's cardinality is much smaller than that of the original one. Consequently, an effective Evolutionary Algorithm (EA) is proposed for solving CluSPT. The second approach looks for vertex-based solutions. The search space of the CluSPT is transformed into 2 nested search spaces (NSS). With every candidate in the high-level optimization, the search engine in the lower level will find a corresponding candidate to combine with it to create the best solution for CluSPT. Accordingly, Nested Local Search EA (N-LSEA) is introduced to search for the optimal solution on the NSS. When solving this model in lower level by N-LSEA, variety of similar tasks are handled. Thus, Multifactorial Evolutionary Algorithm applied in order to enhance the implicit genetic transfer across these optimizations. Proposed algorithms are conducted on a series of datasets and the obtained results demonstrate superior efficiency in comparison to previous scientific works.

Related papers

• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms. Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability. We propose a method for accelerating cutting-plane algorithms via reinforcement learning.
  arXiv  Detail & Related papers  (2023-07-17T20:11:56Z)
• Optimizing NOTEARS Objectives via Topological Swaps [41.18829644248979]
  In this paper, we develop an effective method for a set of candidate algorithms. At the inner level, given a subject, we utilize off-the-the-art constraints. The proposed method significantly improves the score of other algorithms.
  arXiv  Detail & Related papers  (2023-05-26T21:49:37Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
  arXiv  Detail & Related papers  (2023-01-30T15:46:39Z)
• Efficient Non-Parametric Optimizer Search for Diverse Tasks [93.64739408827604]
  We present the first efficient scalable and general framework that can directly search on the tasks of interest. Inspired by the innate tree structure of the underlying math expressions, we re-arrange the spaces into a super-tree. We adopt an adaptation of the Monte Carlo method to tree search, equipped with rejection sampling and equivalent- form detection.
  arXiv  Detail & Related papers  (2022-09-27T17:51:31Z)
• Best Subset Selection with Efficient Primal-Dual Algorithm [24.568094642425837]
  Best subset selection is considered the gold standard' for many learning problems. In this paper, we investigate the dual forms of a family of $ell$-regularized problems. An efficient primal-dual method has been developed based on the primal and dual problem structures.
  arXiv  Detail & Related papers  (2022-07-05T14:07:52Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  Bilevel optimization has been widely applied in many important machine learning applications. We propose two new algorithms for bilevel optimization. We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
  arXiv  Detail & Related papers  (2021-06-08T21:05:30Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  We consider the task of minimizing the sum of smooth and strongly convex functions stored in a decentralized manner across the nodes of a communication network. We design two optimal algorithms that attain these lower bounds. We corroborate the theoretical efficiency of these algorithms by performing an experimental comparison with existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-06-08T15:54:44Z)
• A bi-level encoding scheme for the clustered shortest-path tree problem in multifactorial optimization [1.471992435706872]
  The Clustered Shortest-Path Tree Problem (CluSPT) plays an important role in various types of optimization problems in real-life. Recently, some Multifactorial Evolutionary Algorithm (MFEA) have been introduced to deal with the CluSPT. This paper describes a MFEA-based approach to solve the CluSPT.
  arXiv  Detail & Related papers  (2021-02-12T13:36:07Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• A global-local neighborhood search algorithm and tabu search for flexible job shop scheduling problem [3.946442574906068]
  This work presents a new meta-heuristic algorithm called GLNSA (Global-local neighborhood search algorithm) The proposed algorithm is complemented with a tabu search that implements a simplified version of the Nopt1 neighborhood. Experiments carried out show a satisfactory performance of the proposed algorithm, compared with other results published in recent algorithms.
  arXiv  Detail & Related papers  (2020-10-23T23:08:51Z)
• 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.