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...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2007-01-01
|
| Series: | Discrete Dynamics in Nature and Society |
| Online Access: | http://dx.doi.org/10.1155/2007/27383 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832545334468804608 |
|---|---|
| author | Ammar W. Mohemmed Nirod Chandra Sahoo |
| author_facet | Ammar W. Mohemmed Nirod Chandra Sahoo |
| author_sort | Ammar W. Mohemmed |
| collection | DOAJ |
| 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 efficiency. 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 efficiency of the proposed hybrid algorithm for
shortest-path computation. The proposed algorithm can be used as a platform for solving other NP-hard SPPs. |
| format | Article |
| id | doaj-art-d206dc8c3b554cc69495933096c94272 |
| institution | Kabale University |
| issn | 1026-0226 1607-887X |
| language | English |
| publishDate | 2007-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Discrete Dynamics in Nature and Society |
| spelling | doaj-art-d206dc8c3b554cc69495933096c942722025-02-03T07:26:13ZengWileyDiscrete Dynamics in Nature and Society1026-02261607-887X2007-01-01200710.1155/2007/2738327383Efficient Computation of Shortest Paths in Networks Using Particle Swarm Optimization and Noising MetaheuristicsAmmar W. Mohemmed0Nirod Chandra Sahoo1Faculty of Engineering and Technology, Multimedia University, Jalan Ayer Keroh Lama, Melaka 75450, MalaysiaFaculty of Engineering and Technology, Multimedia University, Jalan Ayer Keroh Lama, Melaka 75450, MalaysiaThis 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 efficiency. 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 efficiency of the proposed hybrid algorithm for shortest-path computation. The proposed algorithm can be used as a platform for solving other NP-hard SPPs.http://dx.doi.org/10.1155/2007/27383 |
| spellingShingle | Ammar W. Mohemmed Nirod Chandra Sahoo Efficient Computation of Shortest Paths in Networks Using Particle Swarm Optimization and Noising Metaheuristics Discrete Dynamics in Nature and Society |
| 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 |
| url | http://dx.doi.org/10.1155/2007/27383 |
| work_keys_str_mv | AT ammarwmohemmed efficientcomputationofshortestpathsinnetworksusingparticleswarmoptimizationandnoisingmetaheuristics AT nirodchandrasahoo efficientcomputationofshortestpathsinnetworksusingparticleswarmoptimizationandnoisingmetaheuristics |