Improved Genetic Algorithm on Minimum Spanning Tree of Length Constraint Problem

Abstract:

The first minimum spanning tree of length constraint problem (MSTLCP) is put forward, which can not be solved by traditional algorithms. In order to solve MSTLCP, improved genetic algorithm is put forward based on the idea of global and feasible searching. In the improved genetic algorithm, chromosome is generated to use binary-encoding, and more reasonable fitness function of improved genetic algorithm is designed according to the characteristics of spanning tree and its cotree; in order to ensure the feasibility of chromosome, more succinct check function is introduced to three kinds of genetic operations of improved genetic algorithm (generation of initial population, parental crossover operation and mutation operation); three kinds of methods are used to expand searching scope of algorithm and to ensure optimality of solution, which are as follows: the strategy of preserving superior individuals is adopted, mutation operation is improved in order to enhance the randomness of the operation, crossover rate and mutation rate are further optimized. The validity and correctness of improved genetic algorithm solving MSTLCP are explained by a simulate experiment where improved genetic algorithm is implemented using C programming language. And experimental results are analyzed: selection of population size and iteration times determines the efficiency and precision of the simulate experiment.

• Periodical: Applied Mechanics and Materials (Volumes 713-715)
• Pages: 1737-1740
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.713-715.1737
• Online since: January 2015
• Authors: Ying Ying Duan, Kang Zhou*, Wen Bo Dong, Kai Shao
• Keywords: Check Function, Fitness Function, Genetic Algorithm (GA), Minimum Spanning Tree of Length Constraint Problem (MSTLCP), Mutation Operation

References

[1] T. Y. Xiao, Q. S. Zhou, F. P. Li, and et a1: Proceedings of the Chinese Society for Electrical Engineering Vol. 25 (2005), p.48.

[2] K. Zhou, X. J. Tong, W. B. Liu, and et a1: Journal of Systems Engineering and Electronics Vol. 30 (2008) p.556.

[3] K. Zhou, J. Chen: Applied Mathematics and Information Sciences Vol. 8 (2014) p.139.

[4] K. Zhou, X. J. Tong, J. Xu: Journal of Systems Engineering and Electronics Vol. 20 (2009) p.636.

[5] Z. F. Liu, S. Y. Ge, Y. X. Yu: Proceedings of the Chinese Society for Electrical Engineering Vol. 25 (2005) p.73.

[6] J. Dimitris, Bertsimas: Operations Research Vol. 40 (1992) p.574.

[7] D. A. Tran, H. Raghavendra: IEEE Transactions on Parallel and Distributed Systems Vol. 17 (2006) p.1294.

[8] H. Aytug, C. Saydam: European Journal of Operational Research Vol. 141 (2002) p.480.

[9] K. Zhou, X. J. Tong, J. Xu: Journal of Huazhong University of Science and Technology (Natural Science Edition) Vol. 33 (2005) p.59.

[10] B. Dengiz, F. Alfiparmak, A. E. Smith: IEEE Trans Vol. 1 (1997) p.179.