Genetic Algorithm Finding the Shortest Path in Networks

In the field of engineering, solving a problem is not enough. The solution found must be the best possible solution. In other words, one must find the optimal solution to the problem. Optimization seeks to improve the performance towards some optimal point or points. Normally single objective optimization is carried out but many optimization problems have conflicting objectives. Use of GAs is considered as most appropriate method for multi objective optimization problems. Genetic Algorithms are search algorithms based on the mechanism of natural selection. Genetic Algorithm (GA) has the ability to manipulate multiple parameters concurrently; their use of parallelism allow them to produce multiple equally good solutions to the same problem. Optimization in network routing by considering multiple QoS parameters such as end-to-end delay, energy consumption, bandwidth, video conferencing, voice-over-IP, end-to-end delay, jitter, packet loss ratio, hop count etc. is a complex research is...

2011

In Internet Routing, the static shortest path (SP) problem has been addressed using well known intelligent optimization techniques like artificial neural networks, genetic algorithms (GAs) and particle swarm optimization. Advancement in wireless communication lead more and more mobile wireless networks, such as mobile networks [mobile ad hoc networks (MANETs)] and wireless sensor networks. Dynamic nature of the network is the main characteristic of MANET. Therefore, the SP routing problem in MANET turns into dynamic optimization problem (DOP). Here the nodes ae made aware of the environmental condition, thereby making it intelligent, which goes as the input for GA. The implementation then uses GAs with immigrants and memory schemes to solve the dynamic SP routing problem (DSPRP) in MANETS. In our paper, once the network topology changes, the optimal solutions in the new environment can be searched using the new immigrants or the useful information stored in the memory. Results shows GA with new immigrants shows better convergence result than GA with memory scheme.

The single source shortest path problem is one of the most studied problems in algorithmic graph theory. Single Source Shortest Path is the problem in which we have to find shortest paths from a source vertex v to all other vertices in the graph. And we incorporate this problem in the wired network for finding the reliable route between the nodes of wired network. A number of algorithms have been proposed for this problem. Most of the algorithms for this problem have evolved around the Dijkstra's algorithm. This paper gives the description of a genetic algorithm with best suitable selection method that can be used to find an optimal and reliable route between nodes of a wired network so that the average end to end time of routing packets from one node to the other node can be minimized. In this paper, we are going to do comparative analysis of the selection methods of Genetic Algorithm to solve this problem which is an optimization algorithm based on evolutionary ideas of natural selection and genetics.

2011

The demand for different levels of Quality of Service (QoS) in IP networks is growing, mainly to attend multimedia applications. However, not only indicators of quality have conflicting features, but also the problem of determining routes covered by more than two QoS constraints is NP-complete (Nondeterministic Polynomial Time Complete). This work proposes an algorithm to optimize multiple Quality of Service indices of Multi Protocol Label Switching (MPLS) IP networks. Such an approach aims at minimizing the network cost and the amount of simultaneous requests rejection, as well as performing load balancing among routes. The proposed algorithm, the Variable Neighborhood Multiobjective Genetic Algorithm (VN-MGA), is a Genetic Algorithm based on the Elitist Non-Dominated Sorted Genetic Algorithm (NSGA-II), with a particular feature that different parts of a solution are encoded differently, at Level 1 and Level 2. In order to improve results, both representations are needed. At Level 1, the first part of the solution is encoded by considering as decision variables the arrows that form the routes to be followed by each request (whilst the second part of the solution is kept constant), whereas at Level 2, the second part of the solution is encoded by considering the sequence of requests as decision variables, and first part is kept constant. Pareto-fronts obtained by VN-MGA dominate fronts obtained by fixed-neighborhood encoding schemes. Besides potential benefits of the proposed approach application to packet routing optimization in MPLS networks, this work raises the theoretical issue of the systematic application of variable encodings, which allow variable neighborhood searches, as operators inside general evolutionary computation algorithms.

2014

In this paper, we surveyed the implementations of genetic algorithm within networks, whether it is computer network, transportation network, and other fields that have networking context. Their feasibilities are discussed along with our suggestions for potential improvements. Genetic algorithm can also be an alternative to other optimization methods/algorithms. In some cases, it even outperforms other methods. However, the choice of genetic algorithm might be influenced by some concerns, such as execution time and problem size. Generally, genetic algorithm process will accomplish according to its parameters sizes. Finally, the success stories prove the applicability, adaptability, and scalability of genetic algorithm, specifically for almost-any network optimization.

Recent development in communication has given rise to new challenges in open Networks. Network Planning is a challenging issue when there are multiple networks in distributed environment. In this paper, we have discussed different Network Planning schemes based on Genetic Algorithms and its variations. These schemes are implemented by many researchers to make feasible selection of a network from the population of networks to improve the efficiency, cost, time delay, prediction quality, coverage and connectivity of networks.

IEEJ Transactions on Electronics, Information and Systems

Non-member Shiho Motegi (Toshiba Corporation) Non-member Shoichi Yokoyama (Yamagata University) High-speed transmission rates bring forward their specific issues influencing the network design. To cope with high-speed networks the routing algorithms should give a fast decision. The conventional routing algorithms of slow-speed networks are generally inapplicable for high-speed networks. The traffic control methods for high-speed networks must be adaptive, flexible, and intelligent for efficient network management. The intelligent routing algorithms based on Genetic Algorithms (GA), Neural Networks (NN), and Fuzzy Theory (FT) can prove to be efficient in high speed networks. In this paper, we propose a new adaptive routing method called ARGA (Adaptive Routing using GA). In the ARGA method, the network is modeled by a tree and the tree is reduced in the part where there are the same routes. In the reduced tree model, the tree junctions are represented by individual genes. By using a novel gene coding method, the chromosomes have the same length, which results in easy genetic operations and a fast routing can be achieved. Performance evaluation via simulations show that the ARGA method has a faster routing decision compared with the Genetic Load Balancing Routing (GLBR) method.

International Journal of Electrical and Computer Engineering (IJECE), 2023

The shortest path problem has many different versions. In this manuscript, we proposed a muti-constrained optimization method to find the shortest path in a computer network. In general, a genetic algorithm is one of the common heuristic algorithms. In this paper, we employed the genetic algorithm to find the solution of the shortest path multi-constrained problem. The proposed algorithm finds the best route for network packets with minimum total cost, delay, and hop count constrained with limited bandwidth. The new algorithm was implemented on four different capacity networks with random network parameters, the results showed that the shortest path under constraints can be found in a reasonable time. The experimental results showed that the algorithm always found the shortest path with minimal constraints.

Proceedings of the First International Conference on Advances in Computer and Information Technology, 2012

The field of Networks has gained an important part of the interest of researchers and has become very popular in the last few years. The network must operate without fixed infrastructure and can survive rapid changes in the topology. It can be studied formally as a graph in which the set of edges varies in time. I propose a new adaptive and dynamic routing algorithm for networks inspired by the genetic algorithm (GAR) in combination with network delay analysis. Using GAR we can find, if not the shortest, at least a very good path between the source and the destination. There are several algorithms for the shortest path (SP) problem: one of them is the Dijkstra algorithm. Since these algorithms can solve SP problems in polynomial time, they are efficient in fixed infrastructure wireless or wired networks. However, they exhibit unacceptably high computational complexity for real-time communications involving rapidly changing network topologies. It is anticipated that genetic algorithm GA can efficiently and dynamically give consistent better solutions regardless of: The network topology, The change in the network, removing any node, or link from the network, The volume of the network (if there are many paths).

2006

OSPFOSPF is the most common intra-domain routing protocol in Wide Area Networks. Thus, optimizing OSPF weights will produce tools for traffic engineering with Quality of Service constraints, without changing the network management model. Evolutionary Algorithms (EAs) provide a valuable tool to face this NP-hard problem, allowing flexible cost functions with several metrics of the network behavior. A novel framework is proposed that enriches current models for network congestion with delay constraints, setting the basis for EAs that allocate OSPF weights, guided by a bi-objective cost function. The results show that EAs make an efficient method, outperforming common heuristics and achieving effective network behavior under unfavorable scenarios.