Efficient Computation of Shortest Paths in Networks Using Particle Swarm Optimization and Noising Metaheuristics
This paper presents a novel hybrid algorithm based on particle swarm optimization (PSO) and noising metaheuristics for solving the single-source shortest-path problem (SPP) commonly encountered in graph theory. This hybrid search process combines PSO for iteratively finding a population of better so...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
HINDAWI PUBLISHING CORPORATION
2007
|
| Subjects: | |
| Online Access: | http://shdl.mmu.edu.my/3156/ http://shdl.mmu.edu.my/3156/1/1167.pdf |
| _version_ | 1848790249334898688 |
|---|---|
| author | Mohemmed, Ammar W. Sahoo, Nirod Chandra |
| author_facet | Mohemmed, Ammar W. Sahoo, Nirod Chandra |
| author_sort | Mohemmed, Ammar W. |
| building | MMU Institutional Repository |
| collection | Online Access |
| description | This paper presents a novel hybrid algorithm based on particle swarm optimization (PSO) and noising metaheuristics for solving the single-source shortest-path problem (SPP) commonly encountered in graph theory. This hybrid search process combines PSO for iteratively finding a population of better solutions and noising method for diversifying the search scheme to solve this problem. A new encoding/decoding scheme based on heuristics has been devised for representing the SPP parameters as a particle in PSO. Noising-method-based metaheuristics ( noisy local search) have been incorporated in order to enhance the overall search effciency. In particular, an iteration of the proposed hybrid algorithm consists of a standard PSO iteration and few trials of noising scheme applied to each better/improved particle for local search, where the neighborhood of each such particle is noisily explored with an elementary transformation of the particle so as to escape possible local minima and to diversify the search. Simulation results on several networks with random topologies are used to illustrate the effciency of the proposed hybrid algorithm for shortest-path computation. The proposed algorithm can be used as a platform for solving other NP-hard SPPs.
Copyright (c) 2007 A. W. Mohemmed and N. C. Sahoo. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. |
| first_indexed | 2025-11-14T18:09:37Z |
| format | Article |
| id | mmu-3156 |
| institution | Multimedia University |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-14T18:09:37Z |
| publishDate | 2007 |
| publisher | HINDAWI PUBLISHING CORPORATION |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | mmu-31562014-03-03T04:36:56Z http://shdl.mmu.edu.my/3156/ Efficient Computation of Shortest Paths in Networks Using Particle Swarm Optimization and Noising Metaheuristics Mohemmed, Ammar W. Sahoo, Nirod Chandra T Technology (General) QA75.5-76.95 Electronic computers. Computer science This paper presents a novel hybrid algorithm based on particle swarm optimization (PSO) and noising metaheuristics for solving the single-source shortest-path problem (SPP) commonly encountered in graph theory. This hybrid search process combines PSO for iteratively finding a population of better solutions and noising method for diversifying the search scheme to solve this problem. A new encoding/decoding scheme based on heuristics has been devised for representing the SPP parameters as a particle in PSO. Noising-method-based metaheuristics ( noisy local search) have been incorporated in order to enhance the overall search effciency. In particular, an iteration of the proposed hybrid algorithm consists of a standard PSO iteration and few trials of noising scheme applied to each better/improved particle for local search, where the neighborhood of each such particle is noisily explored with an elementary transformation of the particle so as to escape possible local minima and to diversify the search. Simulation results on several networks with random topologies are used to illustrate the effciency of the proposed hybrid algorithm for shortest-path computation. The proposed algorithm can be used as a platform for solving other NP-hard SPPs. Copyright (c) 2007 A. W. Mohemmed and N. C. Sahoo. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. HINDAWI PUBLISHING CORPORATION 2007 Article NonPeerReviewed text en http://shdl.mmu.edu.my/3156/1/1167.pdf Mohemmed, Ammar W. and Sahoo, Nirod Chandra (2007) Efficient Computation of Shortest Paths in Networks Using Particle Swarm Optimization and Noising Metaheuristics. Discrete Dynamics in Nature and Society, 2007. p. 1. ISSN 1026-0226 http://dx.doi.org/10.1155/2007/27383 doi:10.1155/2007/27383 doi:10.1155/2007/27383 |
| spellingShingle | T Technology (General) QA75.5-76.95 Electronic computers. Computer science Mohemmed, Ammar W. Sahoo, Nirod Chandra Efficient Computation of Shortest Paths in Networks Using Particle Swarm Optimization and Noising Metaheuristics |
| title | Efficient Computation of Shortest Paths in Networks Using Particle Swarm Optimization and Noising Metaheuristics |
| title_full | Efficient Computation of Shortest Paths in Networks Using Particle Swarm Optimization and Noising Metaheuristics |
| title_fullStr | Efficient Computation of Shortest Paths in Networks Using Particle Swarm Optimization and Noising Metaheuristics |
| title_full_unstemmed | Efficient Computation of Shortest Paths in Networks Using Particle Swarm Optimization and Noising Metaheuristics |
| title_short | Efficient Computation of Shortest Paths in Networks Using Particle Swarm Optimization and Noising Metaheuristics |
| title_sort | efficient computation of shortest paths in networks using particle swarm optimization and noising metaheuristics |
| topic | T Technology (General) QA75.5-76.95 Electronic computers. Computer science |
| url | http://shdl.mmu.edu.my/3156/ http://shdl.mmu.edu.my/3156/ http://shdl.mmu.edu.my/3156/ http://shdl.mmu.edu.my/3156/1/1167.pdf |