An improved genetic algorithm for dynamic shortest path problems

Xuezhi Zhu; Wenjian Luo; Tao Zhu

doi:10.1109/CEC.2014.6900496

An improved genetic algorithm for dynamic shortest path problems

Xuezhi Zhu
, Wenjian Luo^*
, Tao Zhu

^*Corresponding author for this work

University of Science and Technology of China

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

20 Scopus citations

Abstract

The Shortest Path (SP) problems are conventional combinatorial optimization problems. There are many deterministic algorithms for solving the shortest path problems in static topologies. However, in dynamic topologies, these deterministic algorithms are not efficient due to the necessity of restart. In this paper, an improved Genetic Algorithm (GA) with four local search operators for Dynamic Shortest Path (DSP) problems is proposed. The local search operators are inspired by Dijkstra's Algorithm and carried out when the topology changes to generate local shortest path trees, which are used to promote the performance of the individuals in the population. The experimental results show that the proposed algorithm could obtain the solutions which adapt to new environments rapidly and produce high-quality solutions after environmental changes.

Original language	English
Title of host publication	Proceedings of the 2014 IEEE Congress on Evolutionary Computation, CEC 2014
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	2093-2100
Number of pages	8
ISBN (Electronic)	9781479914883
DOIs	https://doi.org/10.1109/CEC.2014.6900496
State	Published - 16 Sep 2014
Externally published	Yes
Event	2014 IEEE Congress on Evolutionary Computation, CEC 2014 - Beijing, China Duration: 6 Jul 2014 → 11 Jul 2014

Publication series

Name	Proceedings of the 2014 IEEE Congress on Evolutionary Computation, CEC 2014

Conference

Conference	2014 IEEE Congress on Evolutionary Computation, CEC 2014
Country/Territory	China
City	Beijing
Period	6/07/14 → 11/07/14

Access to Document

10.1109/CEC.2014.6900496

Cite this

Zhu, X., Luo, W., & Zhu, T. (2014). An improved genetic algorithm for dynamic shortest path problems. In Proceedings of the 2014 IEEE Congress on Evolutionary Computation, CEC 2014 (pp. 2093-2100). Article 6900496 (Proceedings of the 2014 IEEE Congress on Evolutionary Computation, CEC 2014). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CEC.2014.6900496

@inproceedings{eb0d7abac16340f5baf605ae1d6b7b11,

title = "An improved genetic algorithm for dynamic shortest path problems",

abstract = "The Shortest Path (SP) problems are conventional combinatorial optimization problems. There are many deterministic algorithms for solving the shortest path problems in static topologies. However, in dynamic topologies, these deterministic algorithms are not efficient due to the necessity of restart. In this paper, an improved Genetic Algorithm (GA) with four local search operators for Dynamic Shortest Path (DSP) problems is proposed. The local search operators are inspired by Dijkstra's Algorithm and carried out when the topology changes to generate local shortest path trees, which are used to promote the performance of the individuals in the population. The experimental results show that the proposed algorithm could obtain the solutions which adapt to new environments rapidly and produce high-quality solutions after environmental changes.",

author = "Xuezhi Zhu and Wenjian Luo and Tao Zhu",

note = "Publisher Copyright: {\textcopyright} 2014 IEEE.; 2014 IEEE Congress on Evolutionary Computation, CEC 2014 ; Conference date: 06-07-2014 Through 11-07-2014",

year = "2014",

month = sep,

day = "16",

doi = "10.1109/CEC.2014.6900496",

language = "英语",

series = "Proceedings of the 2014 IEEE Congress on Evolutionary Computation, CEC 2014",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "2093--2100",

booktitle = "Proceedings of the 2014 IEEE Congress on Evolutionary Computation, CEC 2014",

address = "美国",

}

Zhu, X, Luo, W & Zhu, T 2014, An improved genetic algorithm for dynamic shortest path problems. in Proceedings of the 2014 IEEE Congress on Evolutionary Computation, CEC 2014., 6900496, Proceedings of the 2014 IEEE Congress on Evolutionary Computation, CEC 2014, Institute of Electrical and Electronics Engineers Inc., pp. 2093-2100, 2014 IEEE Congress on Evolutionary Computation, CEC 2014, Beijing, China, 6/07/14. https://doi.org/10.1109/CEC.2014.6900496

An improved genetic algorithm for dynamic shortest path problems. / Zhu, Xuezhi; Luo, Wenjian; Zhu, Tao.
Proceedings of the 2014 IEEE Congress on Evolutionary Computation, CEC 2014. Institute of Electrical and Electronics Engineers Inc., 2014. p. 2093-2100 6900496 (Proceedings of the 2014 IEEE Congress on Evolutionary Computation, CEC 2014).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - An improved genetic algorithm for dynamic shortest path problems

AU - Zhu, Xuezhi

AU - Luo, Wenjian

AU - Zhu, Tao

PY - 2014/9/16

Y1 - 2014/9/16

N2 - The Shortest Path (SP) problems are conventional combinatorial optimization problems. There are many deterministic algorithms for solving the shortest path problems in static topologies. However, in dynamic topologies, these deterministic algorithms are not efficient due to the necessity of restart. In this paper, an improved Genetic Algorithm (GA) with four local search operators for Dynamic Shortest Path (DSP) problems is proposed. The local search operators are inspired by Dijkstra's Algorithm and carried out when the topology changes to generate local shortest path trees, which are used to promote the performance of the individuals in the population. The experimental results show that the proposed algorithm could obtain the solutions which adapt to new environments rapidly and produce high-quality solutions after environmental changes.

AB - The Shortest Path (SP) problems are conventional combinatorial optimization problems. There are many deterministic algorithms for solving the shortest path problems in static topologies. However, in dynamic topologies, these deterministic algorithms are not efficient due to the necessity of restart. In this paper, an improved Genetic Algorithm (GA) with four local search operators for Dynamic Shortest Path (DSP) problems is proposed. The local search operators are inspired by Dijkstra's Algorithm and carried out when the topology changes to generate local shortest path trees, which are used to promote the performance of the individuals in the population. The experimental results show that the proposed algorithm could obtain the solutions which adapt to new environments rapidly and produce high-quality solutions after environmental changes.

UR - https://www.scopus.com/pages/publications/84908592906

U2 - 10.1109/CEC.2014.6900496

DO - 10.1109/CEC.2014.6900496

M3 - 会议稿件

AN - SCOPUS:84908592906

T3 - Proceedings of the 2014 IEEE Congress on Evolutionary Computation, CEC 2014

SP - 2093

EP - 2100

BT - Proceedings of the 2014 IEEE Congress on Evolutionary Computation, CEC 2014

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2014 IEEE Congress on Evolutionary Computation, CEC 2014

Y2 - 6 July 2014 through 11 July 2014

ER -

An improved genetic algorithm for dynamic shortest path problems

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this