Time filter

Source Type

Lai X.,South China University of Technology | Lai X.,Shangrao Normal University | Zhou Y.,South China University of Technology | He J.,Aberystwyth University | And 3 more authors.
IEEE Transactions on Evolutionary Computation | Year: 2014

A few experimental investigations have shown that evolutionary algorithms (EAs) are efficient for the minimum label spanning tree (MLST) problem. However, we know little about that in theory. In this paper, we theoretically analyze the performances of the (1+1) EA, a simple version of EA, and a simple multiobjective evolutionary algorithm called GSEMO on the MLST problem. We reveal that for the MLSTbproblem, the (1+1) EA and GSEMO achieve a b+1/2-approximation ratio in expected polynomial runtime with respect to n , the number of nodes, and k , the number of labels. We also find that GSEMO achieves a (2ln n+1) -approximation ratio for the MLST problem in expected polynomial runtime with respect to n and k. At the same time, we show that the (1+1) EA and GSEMO outperform local search algorithms on three instances of the MLST problem. We also construct an instance on which GSEMO outperforms the (1+1) EA. © 1997-2012 IEEE. Source

Zhong J.-H.,Sun Yat Sen University | Zhong J.-H.,Key Laboratory of Digital Life | Zhong J.-H.,Key Laboratory of Software Technology | Shen M.,Beijing Information Science and Technology University | And 6 more authors.
IEEE Transactions on Evolutionary Computation | Year: 2013

Railway timetable scheduling is a fundamental operational problem in the railway industry and has significant influence on the quality of service provided by the transport system. This paper explores the periodic railway timetable scheduling (PRTS) problem, with the objective to minimize the average waiting time of the transfer passengers. Unlike traditional PRTS models that only involve service lines with fixed cycles, this paper presents a more flexible model by allowing the cycle of service lines and the number of transfer passengers to vary with the time period. An enhanced differential evolution (DE) algorithm with dual populations, termed 'dual-population DE' (DP-DE), was developed to solve the PRTS problem, yielding high-quality solutions. In the DP-DE, two populations cooperate during the evolution; the first focuses on global search by adopting parameter settings and operators that help maintain population diversity, while the second one focuses on speeding up convergence by adopting parameter settings and operators that are good for local fine tuning. A novel bidirectional migration operator is proposed to share the search experience between the two populations. The proposed DP-DE has been applied to optimize the timetable of the Guangzhou Metro system in Mainland China and six artificial periodic railway systems. Two conventional deterministic algorithms and seven highly regarded evolutionary algorithms are used for comparison. The comparison results reveal that the performance of DP-PE is very promising. © 1997-2012 IEEE. Source

Zhan Z.-H.,University of South Africa | Zhan Z.-H.,Key Laboratory of Software Technology | Zhang J.,University of South Africa | Zhang J.,Key Laboratory of Software Technology | Shi Y.-H.,Xian Jiaotong - Liverpool University
3rd International Workshop on Advanced Computational Intelligence, IWACI 2010 | Year: 2010

Particle swarm optimization (PSO) has been witnessed fast developments these years for the algorithm performance improvements and the applications in real-world problems. However, the experimental study on the population diversities is not taken seriously by the PSO researchers. This paper intends to make a comprehensive experimental study on the PSO diversity, in order to monitor the evolutionary process of the PSO algorithms, and also to give some discussions based on the observations of the experimental results. Source

Zhan Z.-H.,Sun Yat Sen University | Zhan Z.-H.,Key Laboratory of Digital Life | Zhan Z.-H.,Key Laboratory of Software Technology | Li J.,Hong Kong Polytechnic University | And 6 more authors.
IEEE Transactions on Cybernetics | Year: 2013

Traditional multiobjective evolutionary algorithms (MOEAs) consider multiple objectives as a whole when solving multiobjective optimization problems (MOPs). However, this consideration may cause difficulty to assign fitness to individuals because different objectives often conflict with each other. In order to avoid this difficulty, this paper proposes a novel coevolutionary technique named multiple populations for multiple objectives (MPMO) when developing MOEAs. The novelty of MPMO is that it provides a simple and straightforward way to solve MOPs by letting each population correspond with only one objective. This way, the fitness assignment problem can be addressed because the individuals' fitness in each population can be assigned by the corresponding objective. MPMO is a general technique that each population can use existing optimization algorithms. In this paper, particle swarm optimization (PSO) is adopted for each population, and coevolutionary multiswarm PSO (CMPSO) is developed based on the MPMO technique. Furthermore, CMPSO is novel and effective by using an external shared archive for different populations to exchange search information and by using two novel designs to enhance the performance. One design is to modify the velocity update equation to use the search information found by different populations to approximate the whole Pareto front (PF) fast. The other design is to use an elitist learning strategy for the archive update to bring in diversity to avoid local PFs. CMPSO is comprehensively tested on different sets of benchmark problems with different characteristics and is compared with some state-of-the-art algorithms. The results show that CMPSO has superior performance in solving these different sets of MOPs. © 2012 IEEE. Source

Xu R.-T.,Sun Yat Sen University | Xu R.-T.,Key Laboratory of Software Technology | Zhang J.,Sun Yat Sen University | Zhang J.,Key Laboratory of Software Technology | And 2 more authors.
Proceedings - International Conference on Technologies and Applications of Artificial Intelligence, TAAI 2010 | Year: 2010

A portfolio selection problem is about finding an optimal scheme to allocate a fixed amount of capital to a set of available assets. The optimal scheme is very helpful for investors in making decisions. However, finding the optimal scheme is difficult and time-consuming especially when the number of assets is large and some actual investment constraints are considered. This paper proposes a new approach based on estimation of distribution algorithms (EDAs) for solving a cardinality constrained portfolio selection (CCPS) problem. The proposed algorithm, termed PBIL-CCPS, hybridizes an EDA called population-based incremental learning (PBIL) algorithm and a continuous PBIL (PBILc) algorithm, to optimize the selection of assets and the allocation of capital respectively. The proposed algorithm adopts an adaptive parameter control strategy and an elitist strategy. The performance of the proposed algorithm is compared with a genetic algorithm and a particle swarm optimization algorithm. The results demonstrate that the proposed algorithm can achieve a satisfactory result for portfolio selection and perform well in searching nondominated portfolios with high expected returns. © 2010 IEEE. Source

Discover hidden collaborations