检索结果-内蒙古大学图书馆

Evolutionary algorithm and multifactorial evolutionary algorithm on clustered shortest-path tree problem

INFORMATION SCIENCES 2021年 553卷 280-304页

作者： Phan Thi Hong Hanh Pham Dinh Thanh Huynh Thi Thanh Binh Quantitat Hedge Fund Singapore Singapore Taybac Univ Fac Nat Sci Technol Son La Vietnam Hanoi Univ Sci & Technol Sch Informat & Commun Technol Hanoi Vietnam

In literature, clustered shortest-path tree problem (CluSPT) is an NP-hard problem. Previous studies focus on approximation algorithms which search for an optimal solution in relatively large space. Thus, these algorithms consume a large amount of computational resources while the quality of obtained results is lower than expected. In order to enhance the performance of the search process, this paper proposes two different approaches which are inspired by two perspectives of analyzing the CluSPT. The first approach intuition is to narrow down the search space by reducing the original graph into a multi-graph with fewer nodes while maintaining the ability to find the optimal solution. The problem is then solved by a proposed evolutionary algorithm. This approach performs well on those datasets having small number of edges between clusters. However, the increase in the size of the datasets would cause the excessive redundant edges in multi-graph that pressurize searching for potential solutions. The second approach overcomes this limitation by breaking down the multi-graph into a set of simple graphs. Every graph in this set is corresponding to a mutually exclusive search space. From this point of view, the problem could be modeled into a bi-level optimization problem in which the search space includes two nested search spaces. Accordingly, the Nested Local Search Evolutionary Algorithm (N-LSEA) is introduced to search for the optimal solution of glscluspt, the upper level uses a simple Local Search algorithm while the lower level uses the Genetic Algorithm. Due to the neighboring characteristics of the local search step in the upper level, the lower level reduced graphs share the common traits among each others. Thus, the Multi-tasking Local Search Evolutionary Algorithm (MLSEA) is proposed to take advantages of these underlying commonalities by exploiting the implicit transfer across similar tasks of multi-tasking schemes. The improvement in experimental results ove

关键词： Bi-level Optimization clustered shortest-path tree problem Evolutionary Algorithms Multifactorial Evolutionary Algorithm

来源：评论

学校读者我要写书评

暂无评论

An Effective Genetic Algorithm for Solving the clustered shortest-path tree problem

引用

IEEE ACCESS 2021年 9卷 15570-15591页

作者： Cosma, Ovidiu Pop, Petrica C. Zelina, Ioana Tech Univ Cluj Napoca North Univ Ctr Baia Mare Dept Math & Comp Sci Baia Mare 430122 Romania

The clustered shortest-path tree problem (CluSPTP) is an extension of the classical single-source shortest-path problem, in which, given a graph with the set of nodes partitioned into a predefined, mutually exclusive and exhaustive set of clusters, we are looking for a shortest-path spanning tree from a given source to all the other nodes of the graph, with the property that each cluster should induce a connected subtree. CluSPTP belongs to the class of generalized combinatorial optimization problems, and, in general, is proved to be a non-deterministic polynomial time hard (NP-hard) problem. In this paper, we propose a novel genetic algorithm (GA), which is designed to fit the challenges of the investigated problem. The main features of our GA are: the use of an innovative representation scheme that allows us to define meaningful genetic operators and the use of a hybrid initial population. Extensive computational results are reported and discussed for two sets of instances: euclidean and non-euclidean. The performance of the proposed algorithm was evaluated on six types of benchmark euclidean instances available in the literature and on six types of non-euclidean instances obtained from the corresponding euclidean ones. The obtained results show an improvement with respect to existing methods from the literature, both in terms of the quality of the achieved solutions and the computation times necessary to obtain them. They demonstrate that our genetic algorithm outperforms all the existing methods from the literature, providing for all the existing benchmark instances the optimal solutions in all 30 independent trials.

关键词： Single-source shortest-path problem clustered shortest-path tree problem genetic algorithms

来源：评论

学校读者我要写书评

暂无评论

New approach to solving the clustered shortest-path tree problem based on reducing the search space of evolutionary algorithm

引用

KNOWLEDGE-BASED SYSTEMS 2019年第0期180卷 12-25页

作者： Huynh Thi Thanh Binh Pham Dinh Thanh Ta Bao Thang Hanoi Univ Sci & Technol Sch Informat & Commun Technol Hanoi Vietnam Taybac Univ Fac Math Phys Informat Son La Vietnam

Along with the development of manufacture and services, the problem of distribution network optimization has been growing in importance, thus receiving much attention from the research community. One of the most recently introduced network optimization problems is the clustered shortest-path tree problem (CluSTP). Since the problem is NP-Hard, recent approaches often prefer to use approximation algorithms to solve it, several of which used Evolutionary Algorithms (EAs) and have been proven to be effective. However, most of the prior studies directly applied EAs to the whole CluSTP problem, which leads to a great amount of resource consumption, especially when the problem size is large. To overcome these limitations, this paper suggests a method for reducing the search space of the EAs applied to CluSTP by decomposing the original problem into two sub-problems, the solution to one of which is found by an EAs and that to the other is found by another method. The goal of the first sub-problem is to determine a spanning tree which connects among the clusters, while the goal of the second sub-problem is to determine the best spanning tree for each cluster. In addition, this paper proposes a new EAs, which can be applied to solve the first sub-problem and suggests using the Dijkstra's algorithm to solve the second sub-problem. The proposed approach is comprehensively experimented and compared with existing methods. Experimental results prove that our method is more efficient and more importantly, it can obtain results which are close to the optimal results. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Genetic algorithm clustered shortest-path tree problem Evolutionary algorithms

来源：评论

学校读者我要写书评

暂无评论

Hardness, approximability, and fixed-parameter tractability of the clustered shortest-path tree problem

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2019年第1期38卷 165-184页

作者： D'Emidio, Mattia Forlizzi, Luca Frigioni, Daniele Leucci, Stefano Proietti, Guido Univ Aquila Dept Informat Engn Comp Sci & Math Laquila Italy Swiss Fed Inst Technol Dept Comp Sci Zurich Switzerland CNR Ist Anal Sistemi & Informat Antonio Ruberti Rome Italy

Given an n-vertex non-negatively real-weighted graph G, whose vertices are partitioned into a set of k clusters, a clustered network design problem on G consists of solving a given network design optimization problem on G, subject to some additional constraints on its clusters. In particular, we focus on the classic problem of designing a single-source shortest-path tree, and we analyse its computational hardness when in a feasible solution each cluster is required to form a subtree. We first study the unweighted case, and prove that the problem is NP-hard. However, on the positive side, we show the existence of an approximation algorithm whose quality essentially depends on few parameters, but which remarkably is an O(1)-approximation when the largest out of all the diameters of the clusters is either O(1) or (n). Furthermore, we also show that the problem is fixed-parameter tractable with respect to k or to the number of vertices that belong to clusters of size at least 2. Then, we focus on the weighted case, and show that the problem can be approximated within a tight factor of O(n), and that it is fixed-parameter tractable as well. Finally, we analyse the unweighted single-pair shortest path problem, and we show it is hard to approximate within a (tight) factor of n1-E, for any E>0.

关键词： clustered shortest-path tree problem Hardness Approximation algorithms Fixed-parameter tractability Network design

来源：评论

学校读者我要写书评

暂无评论

A Two-Level Hybrid Based Genetic Algorithm to Solve the clustered shortest-path tree problem Using the Prufer Code 17th

A Two-Level Hybrid Based Genetic Algorithm to Solve the Clus...

引用

17th International Conference on Hybrid Artificial Intelligent Systems (HAIS)

作者： Petrovan, Adrian Pop, Petrica C. Sabo, Cosmin Zelina, Ioana Tech Univ Cluj Napoca Cluj Napoca Romania North Univ Ctr Baia Mare Dr Babes 62A Baia Mare 430083 Romania

ISBN: (纸本)9783031154713;9783031154706

The clustered shortest-path tree (CluSPT) problem is a generalization of the popular shortest path problem, in which, given a graph with the set of vertices divided into a given set of clusters, we look for a shortest-path spanning tree from a predefined source vertex to all the other vertices of the graph, with the property that every cluster should generate a connected subgraph. In this paper, we describe a two-level hybrid algorithm to solve the CluSPT problem, in which a framework with a macro-level genetic algorithm (GA) used to generate trees connecting the clusters using Prufer code, is combined with a micro-level algorithm based on dynamic programming (DP) that determines the best corresponding feasible solution of the CluSPT problem associated to a given tree spanning the clusters. Finally, some preliminary computational results are stated on a set of 40 standard benchmark non-euclidean instances from the literature to illustrate the performance of our developed two-level hybrid algorithm. The obtained computational results demonstrate that our novel hybrid algorithm is highly competitive against the existing algorithms.

关键词： Hybrid algorithms Genetic algorithms clustered shortest-path tree problem

来源：评论

学校读者我要写书评

暂无评论

A Heuristic Based on Randomized Greedy Algorithms for the clustered shortest-path tree problem

A Heuristic Based on Randomized Greedy Algorithms for the Cl...

引用

IEEE Congress on Evolutionary Computation (IEEE CEC)

作者： Pham Dinh Thanh Huynh Thi Thanh Binh Do Dinh Dac Nguyen Binh Long Le Minh Hai Phong Taybac Univ Fac Math Phys Informat Son La Vietnam Hanoi Univ Sci & Technol Sch Informat & Commun Technol Hanoi Vietnam

ISBN: (纸本)9781728121536

Randomized Greedy Algorithms (RGAs) are interesting approaches incorporating the random processes into the greedy algorithms to solve problems whose structures are not well understood as well as problems in combinatorial optimization. This paper introduces a new algorithm that combines the major features of RGAs and shortest path tree Algorithm (SPTA) to deal with the clustered shortest-path tree problem (CluSPT). In our algorithm, SPTA is used to determine the shortest path tree in each cluster while the combination between characteristics of the RGAs and search strategy of SPTA are used to construct the edges connecting clusters. To evaluate the performance of the algorithm, various types of Euclidean benchmarks are selected. The experimental results show the strengths of the proposed algorithm in comparison with some existing algorithms. We also analyze the influences of the parameters on the performance of the algorithm.

关键词： Randomized Greedy Algorithms clustered shortest-path tree problem Random Optimization Random Search Heuristics shortest path tree Algorithm

来源：评论

学校读者我要写书评

暂无评论

A bi-level encoding scheme for the clustered shortest-path tree problem in multifactorial optimization

引用

ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE 2021年 100卷 104187-104187页

作者： Huynh Thi Thanh Binh Ta Bao Thang Nguyen Duc Thai Pham Dinh Thanh Hanoi Univ Sci & Technol Sch Informat & Commun Technol Hanoi Vietnam Taybac Univ Fac Nat Sci & Technol Son La Vietnam

The clustered shortest-path tree problem (CluSPT) plays an important role in various types of optimization problems in real-life. Recently, some Multifactorial Evolutionary Algorithms (MFEAs) have been introduced to deal with the CluSPT, but these researches still have some shortcomings, such as evolution operators only perform on complete graphs and huge resource consumption for finding the solution on large search spaces. To overcome these limitations, this paper describes an MFEA-based approach to solve the CluSPT. The proposed algorithm utilizes Dijkstra?s algorithm to construct the spanning trees in clusters while using evolutionary operators for building the spanning tree connecting clusters. This approach takes advantage of both exact and approximate algorithms, so it enables the algorithm to function efficiently on complete and sparse graphs alike. Furthermore, evolutionary operators such as individual encoding and decoding methods are also designed with great consideration regarding performance and memory usage. We have included proof of the repairing method?s efficacy in ensuring all solutions are valid. We have conducted tests on various types of Euclidean instances to assess the effectiveness of the proposed algorithm and methods. Experiment results point out the effectiveness of the proposed algorithm existing heuristic algorithms in most of the test cases. The impact of the proposed MFEA was analyzed, and a possible influential factor that may be useful for further study was also pointed out.

关键词： Multifactorial Evolutionary Algorithm clustered shortest-path tree problem Evolutionary Algorithms Multifactorial optimization

来源：评论

学校读者我要写书评

暂无评论

Novel two-level hybrid genetic algorithms based on different Cayley-type encodings for solving the clustered shortest-path tree problem

引用

EXPERT SYSTEMS WITH APPLICATIONS 2023年 215卷

作者： Petrovan, Adrian Pop, Petrica Sabo, Cosmin Zelina, Ioana Tech Univ Cluj Napoca North Univ Ctr Baia Mare Dept Elect & Comp Sci Baia Mare 430083 Romania Tech Univ Cluj Napoca North Univ Ctr Baia Mare Dept Math & Comp Sci Baia Mare 430122 Romania

This paper investigates the clustered shortest-path tree (CluSPT) problem, a generalized network design problem that has several applications in various areas such as network design, agricultural irrigation settings, distribution of goods and products, etc. The main characteristic of the investigated problem is its hierarchical structure with the nodes of the underlying graph split into a given number of clusters. Its aim is finding a shortest-path spanning tree from a predefined source node to all the other nodes of the graph, with the property that every cluster should generate a connected subgraph. In this paper, we present two different two-level genetic algorithms (GAs) for solving the clustered shortest-path tree problem, in which, a framework with a macro-level sub-problem is used to generate trees spanning the clusters using two different Cayley encodings. The encodings in question are Prufer and Dandelion codes. This sub-problem is coupled with a micro-level sub-problem that determines the best corresponding feasible solution of the CluSPT problem associated to a given tree spanning the clusters by means of a dynamic programming algorithm. Extensive computational results are stated and interpreted on the two sets of benchmark instances available from the literature and containing 452 non-euclidean instances. The achieved results prove that our novel two-level based genetic algorithms are highly competitive against the existing solution approaches from the specialized literature, more precisely, 146 best known solutions were equaled and new improved solutions were found for 292 out of 452 benchmark instances. Between our proposed solution approaches the differences are not remarkable for small instances, but when the size of the problem grows, the GA based on Dandelion code outperforms the GA based on Prufer code, being better suited to evolutionary search due to its locality and heritability properties.

关键词： clustered shortest-path tree problem Genetic algorithms Decomposition methods Cayley-type encodings Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

An efficient strategy for using multifactorial optimization to solve the clustered shortest path tree problem

引用

APPLIED INTELLIGENCE 2020年第4期50卷 1233-1258页

作者： Thanh, Pham Dinh Binh, Huynh Thi Thanh Trung, Tran Ba Taybac Univ Fac Math Phys Informat Son La Vietnam Hanoi Univ Sci & Technol Sch Informat & Commun Technol Hanoi Vietnam

Arising from the need of all time for optimization of irrigation systems, distribution network and cable network, clustered shortest-path tree problem (CluSPT) has been attracting a lot of attention and interest from the research community. On the other hand, the Multifactorial Evolutionary Algorithm (MFEA) is one of the most recently exploited realms of Evolutionary Algorithms (EAs) and its performance in solving optimization problems has been very promising. Considering these characteristics, this paper describes a new approach using the MFEA for solving the CluSPT. The MFEA has two tasks: the goal of the first task is to determine the best tree (w.r.t. cost minimization) which envelops all vertices of the CluSPT while the goal of the second task is to find the fittest solution possible for the problem. The purpose of the second task is to find good materials for implicit genetic transfer process in MFEA to improve the quality of CluSPT. To apply this new algorithm, a decoding scheme for deriving individual solutions from the unified representation in the MFEA is also introduced in this paper. Furthermore, evolutionary operators such as population initialization, crossover and mutation operators are also proposed. These operators are applicable for constructing valid solution from both sparse and complete graph. Although the proposed algorithm is slightly complicated for implementation, it can enhance ability to explore and exploit the Unified Search Space (USS). To prove this increment in performance i.e, to assess the effectiveness of the proposed algorithm and methods, the authors implemented them on both Euclidean and Non-Euclidean instances. Experiment results show that the proposed MFEA outperformed existing heuristic algorithms in most of the test cases. The impact of the proposed MFEA was analyzed and a possible influential factor that may be useful for further study was also pointed out.

关键词： Multifactorial evolutionary algorithm clustered shortest-path tree problem Evolutionary algorithms Genetic algorithm Multifactorial optimization

来源：评论

学校读者我要写书评

暂无评论

Two levels approach based on multifactorial optimization to solve the clustered shortest path tree problem

引用

EVOLUTIONARY INTELLIGENCE 2022年第1期15卷 185-213页

作者： Huynh Thi Thanh, Binh Pham Dinh, Thanh Hanoi Univ Sci & Technol Sch Informat & Commun Technol Hanoi Vietnam Taybac Univ Fac Nat Sci & Technol Son La Vietnam

The clustered shortest-path tree problem (CluSPT) has a great meaning in theoretical research as well as a wide range of applications in everyday life, especially in the field of network optimization. Being able to solve the CluSPT will path the way for improving practical systems such as agricultural irrigation and product distribution. Multifactorial Evolutionary Algorithm (MFEA) is a variant of Evolutionary Algorithm (EA) aiming at simultaneously solving multiple factorial tasks which can be diverse in types, dimensionalities and search spaces. The applications of MFEA have yet to be fully exploited, but the realm has recently attracted much interest from the research community, especially those who are working on evolutionary multitasking. Considering these characteristics, this paper describes a new approach using the MFEA for solving the CluSPT. The MFEA has two tasks: the first is solving the CluSPT problem and the second is solving a new problem which is decomposed from the CluSPT problem. The goal of the first task is finding the fittest solution as possible for the CluSPT while the goal of the second task is determining the best tree (w.r.t. cost minimization) which envelops all vertices of the problem. This paper also introduces mutation, crossover and population initialization operators for a proposed MFEA to solve the CluSPT. Each of these operators deals with individuals in two phases, one of which ensures that the resulted individual is a spanning tree and the other phase ensures that each of its clustered sub-graphs is also a spanning tree. As the MFEA had to deal with these two tasks, a decoding method was also created to allow communication between the tasks. To assess the effectiveness of the proposed algorithm and methods, the authors implemented them on both Euclidean and Non-Euclidean instances. Experiment results show that the proposed MFEA outperformed the existing MFEA algorithms on two-thirds instances with average improvement value of 47%.

关键词： Multifactorial evolutionary algorithm clustered shortest-path tree problem Evolutionary algorithms Genetic algorithm Multifactorial optimization

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：