A new particle swarm optimization based algorithm for solving shortest-paths tree problem
This paper presents an efficient particle swarm optimization (PSO) based search algorithm for solving the single source all destination shortest paths or what is called the shortest-paths tree (SPT), commonly encountered in graph theory. A new particle encoding/decoding scheme has been devised for p...
| Main Authors: | , , |
|---|---|
| Format: | Book Section |
| Published: |
IEEE
2007
|
| Subjects: | |
| Online Access: | http://shdl.mmu.edu.my/3179/ |
| _version_ | 1848790255905275904 |
|---|---|
| author | Mohemmed, Ammar W. Sahoo, Nirod Chandra Tan, Kim Geok |
| author_facet | Mohemmed, Ammar W. Sahoo, Nirod Chandra Tan, Kim Geok |
| author_sort | Mohemmed, Ammar W. |
| building | MMU Institutional Repository |
| collection | Online Access |
| description | This paper presents an efficient particle swarm optimization (PSO) based search algorithm for solving the single source all destination shortest paths or what is called the shortest-paths tree (SPT), commonly encountered in graph theory. A new particle encoding/decoding scheme has been devised for particle-representation of the SPT parameters. This encoding/decoding exploits the sub-optimality feature of the shortest path. In the proposed algorithm, the solution, the shortest path tree, is not represented by one particle, but it is the solution that is contributed by the complete swarm population. Numerical computation results on several networks with random topologies illustrate the efficiency of the proposed PSO method for computation of shortest paths in networks. |
| first_indexed | 2025-11-14T18:09:43Z |
| format | Book Section |
| id | mmu-3179 |
| institution | Multimedia University |
| institution_category | Local University |
| last_indexed | 2025-11-14T18:09:43Z |
| publishDate | 2007 |
| publisher | IEEE |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | mmu-31792020-12-21T07:30:12Z http://shdl.mmu.edu.my/3179/ A new particle swarm optimization based algorithm for solving shortest-paths tree problem Mohemmed, Ammar W. Sahoo, Nirod Chandra Tan, Kim Geok T Technology (General) QA75.5-76.95 Electronic computers. Computer science This paper presents an efficient particle swarm optimization (PSO) based search algorithm for solving the single source all destination shortest paths or what is called the shortest-paths tree (SPT), commonly encountered in graph theory. A new particle encoding/decoding scheme has been devised for particle-representation of the SPT parameters. This encoding/decoding exploits the sub-optimality feature of the shortest path. In the proposed algorithm, the solution, the shortest path tree, is not represented by one particle, but it is the solution that is contributed by the complete swarm population. Numerical computation results on several networks with random topologies illustrate the efficiency of the proposed PSO method for computation of shortest paths in networks. IEEE 2007-09 Book Section NonPeerReviewed Mohemmed, Ammar W. and Sahoo, Nirod Chandra and Tan, Kim Geok (2007) A new particle swarm optimization based algorithm for solving shortest-paths tree problem. In: 2007 IEEE Congress on Evolutionary Computation. IEEE, pp. 3221-3225. ISBN 978-1-4244-1339-3, 978-1-4244-1340-9 http://dx.doi.org/10.1109/CEC.2007.4424884 doi:10.1109/CEC.2007.4424884 doi:10.1109/CEC.2007.4424884 |
| spellingShingle | T Technology (General) QA75.5-76.95 Electronic computers. Computer science Mohemmed, Ammar W. Sahoo, Nirod Chandra Tan, Kim Geok A new particle swarm optimization based algorithm for solving shortest-paths tree problem |
| title | A new particle swarm optimization based algorithm for solving shortest-paths tree problem |
| title_full | A new particle swarm optimization based algorithm for solving shortest-paths tree problem |
| title_fullStr | A new particle swarm optimization based algorithm for solving shortest-paths tree problem |
| title_full_unstemmed | A new particle swarm optimization based algorithm for solving shortest-paths tree problem |
| title_short | A new particle swarm optimization based algorithm for solving shortest-paths tree problem |
| title_sort | new particle swarm optimization based algorithm for solving shortest-paths tree problem |
| topic | T Technology (General) QA75.5-76.95 Electronic computers. Computer science |
| url | http://shdl.mmu.edu.my/3179/ http://shdl.mmu.edu.my/3179/ http://shdl.mmu.edu.my/3179/ |