Genetic algorithm (GA) is one of the alternative approaches for solving the shortest path routing problem. In previous work, we have developed a coarse-grained parallel GA-based shortest path routing algorithm. With p...Genetic algorithm (GA) is one of the alternative approaches for solving the shortest path routing problem. In previous work, we have developed a coarse-grained parallel GA-based shortest path routing algorithm. With parallel GA, there is a GA operator called migration, where a chromosome is taken from one sub-population to replace a chromosome in another sub-population. Which chromosome to be taken and replaced is subjected to the migration strategy used. There are four different migration strategies that can be employed: best replace worst, best replace random, random replace worst, and random replace random. In this paper, we are going to evaluate the effect of different migration strategies on the parallel GA-based routing algorithm that has been developed in the previous work. Theoretically, the migration strategy best replace worst should perform better than the other strategies. However, result from simulation shows that even though the migration strategy best replace worst performs better most of the time, there are situations when one of the other strategies can perform just as well, or sometimes better.展开更多
Based on their "Theorem 2", an O(δ)-time algorithm of searching for the shortest path between each pair of nodes in a double loop network was proposed by K.Mukhopadyaya, et al.(1995). While, unfortunately, ...Based on their "Theorem 2", an O(δ)-time algorithm of searching for the shortest path between each pair of nodes in a double loop network was proposed by K.Mukhopadyaya, et al.(1995). While, unfortunately, it will be proved that both "Theorem 2" and its proof are in error. A new and more faster O(△)-time, △≤δ, algorithm will be presented in this paper.展开更多
A shortest path routing algorithm based on transient chaotic neural network is proposed in this paper. Gam-pared with previous models adopting Hopfield neural network, this algorithm has a higher ability to overcome t...A shortest path routing algorithm based on transient chaotic neural network is proposed in this paper. Gam-pared with previous models adopting Hopfield neural network, this algorithm has a higher ability to overcome the local minimum, and achieves a better performance. By introducing a special post-processing technique for the output matrixes, our algorithm can obtain an optimal solution with a high probability even for the paths that need more hops in large-size networks.展开更多
文摘Genetic algorithm (GA) is one of the alternative approaches for solving the shortest path routing problem. In previous work, we have developed a coarse-grained parallel GA-based shortest path routing algorithm. With parallel GA, there is a GA operator called migration, where a chromosome is taken from one sub-population to replace a chromosome in another sub-population. Which chromosome to be taken and replaced is subjected to the migration strategy used. There are four different migration strategies that can be employed: best replace worst, best replace random, random replace worst, and random replace random. In this paper, we are going to evaluate the effect of different migration strategies on the parallel GA-based routing algorithm that has been developed in the previous work. Theoretically, the migration strategy best replace worst should perform better than the other strategies. However, result from simulation shows that even though the migration strategy best replace worst performs better most of the time, there are situations when one of the other strategies can perform just as well, or sometimes better.
基金Supported by the National Natural Science Foundation of China(No.69772035)
文摘Based on their "Theorem 2", an O(δ)-time algorithm of searching for the shortest path between each pair of nodes in a double loop network was proposed by K.Mukhopadyaya, et al.(1995). While, unfortunately, it will be proved that both "Theorem 2" and its proof are in error. A new and more faster O(△)-time, △≤δ, algorithm will be presented in this paper.
文摘A shortest path routing algorithm based on transient chaotic neural network is proposed in this paper. Gam-pared with previous models adopting Hopfield neural network, this algorithm has a higher ability to overcome the local minimum, and achieves a better performance. By introducing a special post-processing technique for the output matrixes, our algorithm can obtain an optimal solution with a high probability even for the paths that need more hops in large-size networks.
