The Experts below are selected from a list of 360 Experts worldwide ranked by ideXlab platform

Huynh Thi Thanh Binh - One of the best experts on this subject based on the ideXlab platform.

  • a bi level encoding scheme for the clustered Shortest Path Tree problem in multifactorial optimization
    Engineering Applications of Artificial Intelligence, 2021
    Co-Authors: Huynh Thi Thanh Binh, Ta Bao Thang, Nguyen Duc Thai, Pham Dinh Thanh
    Abstract:

    Abstract 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.

  • evolutionary algorithm and multifactorial evolutionary algorithm on clustered Shortest Path Tree problem
    Information Sciences, 2021
    Co-Authors: Phan Thi Hong Hanh, Pham Dinh Thanh, Huynh Thi Thanh Binh
    Abstract:

    Abstract 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 over N-LSEA via this multi-tasking scheme inspires the future works to apply M-LSEA in graph-based problems, especially for those could be modeled into bi-level optimization.

  • evolutionary algorithm and multifactorial evolutionary algorithm on clustered Shortest Path Tree problem
    arXiv: Neural and Evolutionary Computing, 2020
    Co-Authors: Phan Thi Hong Hanh, Pham Dinh Thanh, Huynh Thi Thanh Binh
    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.

  • An efficient strategy for using multifactorial optimization to solve the clustered Shortest Path Tree problem
    Applied Intelligence, 2020
    Co-Authors: Pham Dinh Thanh, Huynh Thi Thanh Binh, Tran Ba Trung
    Abstract:

    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.

  • new approach to solving the clustered Shortest Path Tree problem based on reducing the search space of evolutionary algorithm
    Knowledge Based Systems, 2019
    Co-Authors: Huynh Thi Thanh Binh, Pham Dinh Thanh, Ta Bao Thang
    Abstract:

    Abstract 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.

Pham Dinh Thanh - One of the best experts on this subject based on the ideXlab platform.

  • a bi level encoding scheme for the clustered Shortest Path Tree problem in multifactorial optimization
    Engineering Applications of Artificial Intelligence, 2021
    Co-Authors: Huynh Thi Thanh Binh, Ta Bao Thang, Nguyen Duc Thai, Pham Dinh Thanh
    Abstract:

    Abstract 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.

  • evolutionary algorithm and multifactorial evolutionary algorithm on clustered Shortest Path Tree problem
    Information Sciences, 2021
    Co-Authors: Phan Thi Hong Hanh, Pham Dinh Thanh, Huynh Thi Thanh Binh
    Abstract:

    Abstract 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 over N-LSEA via this multi-tasking scheme inspires the future works to apply M-LSEA in graph-based problems, especially for those could be modeled into bi-level optimization.

  • evolutionary algorithm and multifactorial evolutionary algorithm on clustered Shortest Path Tree problem
    arXiv: Neural and Evolutionary Computing, 2020
    Co-Authors: Phan Thi Hong Hanh, Pham Dinh Thanh, Huynh Thi Thanh Binh
    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.

  • An efficient strategy for using multifactorial optimization to solve the clustered Shortest Path Tree problem
    Applied Intelligence, 2020
    Co-Authors: Pham Dinh Thanh, Huynh Thi Thanh Binh, Tran Ba Trung
    Abstract:

    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.

  • new approach to solving the clustered Shortest Path Tree problem based on reducing the search space of evolutionary algorithm
    Knowledge Based Systems, 2019
    Co-Authors: Huynh Thi Thanh Binh, Pham Dinh Thanh, Ta Bao Thang
    Abstract:

    Abstract 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.

Seth Pettie - One of the best experts on this subject based on the ideXlab platform.

  • sensitivity analysis of minimum spanning Trees in sub inverse ackermann time
    arXiv: Data Structures and Algorithms, 2014
    Co-Authors: Seth Pettie
    Abstract:

    We present a deterministic algorithm for computing the sensitivity of a minimum spanning Tree (MST) or Shortest Path Tree in $O(m\log\alpha(m,n))$ time, where $\alpha$ is the inverse-Ackermann function. This improves upon a long standing bound of $O(m\alpha(m,n))$ established by Tarjan. Our algorithms are based on an efficient split-findmin data structure, which maintains a collection of sequences of weighted elements that may be split into smaller subsequences. As far as we are aware, our split-findmin algorithm is the first with superlinear but sub-inverse-Ackermann complexity. We also give a reduction from MST sensitivity to the MST problem itself. Together with the randomized linear time MST algorithm of Karger, Klein, and Tarjan, this gives another randomized linear time MST sensitivity algoritm.

  • sensitivity analysis of minimum spanning Trees in sub inverse ackermann time
    International Symposium on Algorithms and Computation, 2005
    Co-Authors: Seth Pettie
    Abstract:

    We present a deterministic algorithm for computing the sensitivity of a minimum spanning Tree or Shortest Path Tree in O(m log α(m,n)) time, where α is the inverse-Ackermann function. This improves upon a long standing bound of O(mα(m,n)) established by Tarjan. Our algorithms are based on an efficient split-findmin data structure, which maintains a collection of sequences of weighted elements that may be split into smaller subsequences. As far as we are aware, our split-findmin algorithm is the first with superlinear but sub-inverse-Ackermann complexity.

Ta Bao Thang - One of the best experts on this subject based on the ideXlab platform.

  • a bi level encoding scheme for the clustered Shortest Path Tree problem in multifactorial optimization
    Engineering Applications of Artificial Intelligence, 2021
    Co-Authors: Huynh Thi Thanh Binh, Ta Bao Thang, Nguyen Duc Thai, Pham Dinh Thanh
    Abstract:

    Abstract 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.

  • new approach to solving the clustered Shortest Path Tree problem based on reducing the search space of evolutionary algorithm
    Knowledge Based Systems, 2019
    Co-Authors: Huynh Thi Thanh Binh, Pham Dinh Thanh, Ta Bao Thang
    Abstract:

    Abstract 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.

Subhansu Bandyopadhyay - One of the best experts on this subject based on the ideXlab platform.

  • lifetime maximizing dynamic energy efficient routing protocol for multi hop wireless networks
    Simulation Modelling Practice and Theory, 2013
    Co-Authors: Sanghita Bhattacharjee, Subhansu Bandyopadhyay
    Abstract:

    Abstract Energy efficiency is recognized as a critical problem in wireless networks. Many routing schemes have been proposed for finding energy efficient routing Paths with a view to extend lifetime of the networks – however it has been observed that the energy efficient Path depletes quickly. Further, an unbalanced distribution of energy among the nodes may cause early death of nodes as well as network. Hence, balancing the energy distribution is a challenging area of research in wireless networks. In this paper we propose an energy efficient scheme that considers the node cost of nodes for relaying the data packets to the sink. The node cost considers both the remaining energy of the node as well as energy efficiency. Using this parameter, an energy efficient routing algorithm is proposed which balances the data traffic among the nodes and also prolongs the network lifetime. Simulation shows that proposed routing scheme improves energy efficiency and network lifetime than widely used methods viz., Shortest Path Tree (SPT) and Minimum Spanning Tree (MST) based PEDAP, Distributed Energy Balanced Routing (DEBR) and Shortest Path Aggregation Tree Based Routing Protocol.