Arising from the need of all time for optimization of irrigation systems, distribution network and cable network, the Cluster shortestpathtreeproblem (CSTP) has been attracting a lot of attention and interest from ...
详细信息
ISBN:
(纸本)9781509060177
Arising from the need of all time for optimization of irrigation systems, distribution network and cable network, the Cluster shortestpathtreeproblem (CSTP) has been attracting a lot of attention and interest from the research community. For such an NP-Hard problem with a great dimensionality, the approximation approach is usually taken. Evolutionary Algorithms, based on biological evolution, has been proved to be effective in finding approximate solutions to problems of various fields. The multifactorial evolutionary algorithm (MFEA) is one of the most recently exploited realms of EAs and its performance in solving optimization problems has been very promising. The main difference between the MFEA and the traditional Genetic Algorithm (GA) is that the former can solve multiple tasks at the same time and take advantage of implicit genetic transfer in a multitasking problem, while the latter solves one problem and exploit one search space at a time. Considering these characteristics, this paper proposes a MFEA for CSTP tasks, together with novel genetic operators: population initialization, crossover, and mutation operators. Furthermore, a novel decoding scheme for deriving factorial solutions from the unified representation in the MFEA, which is the key factor to the performance of any variant of the MFEA, is also introduced in this paper. For examining the efficiency of the proposed techniques, experiments on a wide range of diverse sets of instances were implemented and the results showed that the proposed algorithms outperformed an existing heuristic algorithm for most of the testing cases. In the experimental results section, we also pointed out which cases allowed for a good performance of the proposed algorithm.
The wide range of applications of Cluster treeproblems has been motivating extensive research into various algorithms and techniques with a view to promoting both efficiency of the solving and qualities of solutions....
详细信息
ISBN:
(纸本)9781509060177
The wide range of applications of Cluster treeproblems has been motivating extensive research into various algorithms and techniques with a view to promoting both efficiency of the solving and qualities of solutions. A representative of Cluster treeproblems, the Cluster shortest-pathtreeproblem (CSTP) arose from the practical need to optimize network systems such as irrigation systems, network cables and distribution systems. In this paper, we proposed the Multifactorial Evolutionary Algorithm (MFEA) to approach the CSTP with a representation scheme based on the Cayley Code. The proposed algorithm exploit advantages of Cayley Code for improving the MFEAs performance and quality solutions. This approach also applied new decoding method to transform the solution from the unified search space to the tasks. Experiments were conducted to compare the performances of the proposed to another approximation algorithm on various set of instances. The experimental results show that proposed algorithm surpass existing algorithm on almost test cases.
Linkage tree Genetic Algorithm (LTGA) is an effective Evolutionary Algorithm (EA) to solve complex problems using the linkage information between problem variables. LTGA performs well in various kinds of single-task o...
详细信息
Linkage tree Genetic Algorithm (LTGA) is an effective Evolutionary Algorithm (EA) to solve complex problems using the linkage information between problem variables. LTGA performs well in various kinds of single-task optimization and yields promising results in comparison with the canonical genetic algorithm. However, LTGA is an unsuitable method for dealing with multi-task optimization problems. On the other hand, Multifactorial Optimization (MFO) can simultaneously solve independent optimization problems, which are encoded in a unified representation to take advantage of the process of knowledge transfer. In this paper, we introduce Genetic Algorithm (MF-LTGA) by combining the main features of both LTGA and MFO. 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. This knowledge serves to determine the high-quality partial solutions for supporting other tasks in exploring the search space. Moreover, MF-LTGA speeds up convergence because of knowledge transfer of relevant problems. We demonstrate the effectiveness of the proposed algorithm on two benchmark problems: clustered shortest-path tree problem and Deceptive Trap Function. In comparison to LTGA and existing methods, MF-LTGA outperforms in quality of the solution or in computation time. (C) 2020 Elsevier Inc. All rights reserved.
暂无评论