Search

The Steiner tree problem (STP) aims to determine some Steiner nodes such that the minimum spanning tree over these Steiner nodes and a given set of special nodes has the minimum weight, which is NP-hard. STP includes several important cases. The Steiner tree problem in graphs (GSTP) is one of them. Many heuristics have been proposed for STP, and some of them have proved to be performance guarantee approximation algorithms for this problem. Since evolutionary algorithms (EAs) are general and popular randomized heuristics, it is significant to investigate the performance of EAs for STP. Several empirical investigations have shown that EAs are efficient for STP. However, up to now, there is no theoretical work on the performance of EAs for STP. In this article, we reveal that the (1+1) EA achieves 3/2-approximation ratio for STP in a special class of quasi-bipartite graphs in expected runtime [Formula: see text], where [Formula: see text], [Formula: see text], and [Formula: see text] are, respectively, the number of Steiner nodes, the number of special nodes, and the largest weight among all edges in the input graph. We also show that the (1+1) EA is better than two other heuristics on two GSTP instances, and the (1+1) EA may be inefficient on a constructed GSTP instance.

The maximum internal spanning tree (MIST) problem is to find a spanning tree with maximum number of internal node for an undirected graph. It is a variation of the well-known minimum spanning tree problem and is NP-hard. Evolutionary algorithms (EAs) have been successfully applied to solve many NP-hard combinatorial optimization problems in numerical empirical studies. However, researchers know little about their performance guarantees from theory aspect. This paper designs a valid fitness function to guide the well-studied evolutionary algorithm, (1 + 1) EA , to optimize the MIST problem, and presents theoretical analysis to show that it can obtain a performance guarantee of 2 and 5/3 in expected runtime O (n m 2) and O (n m 4) , respectively. Moreover, this paper proves that the (1+1) EA can achieve a performance guarantee of 3 for a variation of the MIST problem, where each vertex is associated with a weight. In addition, comparison analyses on two family instance graphs are presented to show that (1 + 1) EA is better than two local search algorithms. This theoretical study provides insight into the process of (1 + 1) EA constructing a performance guarantee solution for the MIST problem. [ABSTRACT FROM AUTHOR]

The Vehicle Routing Problem (VRP) is a classical NP-hard combinatorial optimization problem. In recent years, a lot of heuristic algorithms have been proposed for optimizing the problem, and many simulation and practical experiments are performed to evaluate and verify the effectiveness of different heuristic algorithms. In this paper, we focus on the Vehicle Routing Problem with stochastic demands (VRPSD) in which the customer demands follow known probability distributions. A hybrid algorithm called DSMO-GA which combines discrete spider monkey algorithm (SMO) with genetic algorithm (GA) is proposed for solving the VRPSD problem. In the proposed DSMO-GA for VRPSD, the individuals are coded as sets and sequences, and a conflict elimination method is designed to cancel the infeasible codes. Accordingly, a non adjacent 2-OPT is designed to enhance population diversity. The proposed DSMO-GA effectively integrates the advantages of DSMO and GA to further balance the global exploration and local exploitation capacity. Five groups of different experiments are conducted and the results show that DSMO-GA is valid for the VRPSD. Furthermore, the impact of various parameters on the performance of DSMO-GA are also investigated. [ABSTRACT FROM AUTHOR]