Improved Genetic Algorithm For QoS Routing

With the network transmission and switching technology maturing, more andmore real-time applications come out, such as video conference and VOIP, etc. Theynot only require a feasible path for transmission network, but also require a certainquality of service. Therefore, efficient QoS support is becoming more and moreimportant, IETF puts forward a lot of mechanism models and services to meet thedemand for QoS, and QoS routing is one of the most important technologies.Multi-constraint QoSR as a multi-constraint optimization path has been proved to bean NPC difficulty and it is difficult to be solved under traditional algorithm.Genetic algorithm is a class of optimization search algorithm, it is a veryimportant form of evolutionary computation and it is born with parallel computingability and global optimization ability. In this paper, aiming at multi-constraint QoSRoptimization problem, the stages of the genetic algorithm are studied and put forwardthe corresponding improvement. At last, the simulation results confirm the efficiencyof the algorithm.The subject research mainly in the following aspects:(1) This paper researches the QoS routing and genetic algorithm for the relevanttheoretical studies, analyzes in detail the advantages and disadvantages of geneticalgorithm to deal with the problem of QoSR optimization, summarizes the relevantimproved genetic hybrid optimization algorithm and analyzes the correspondingimprovements.(2) For QoSR problem complexity, this paper proposes a layered and centralizednetwork architecture, simplifies the large network and lays the foundation for theQoSR routing calculation.(3) Combining with the characteristics of QoSR problem model and theadvantages and disadvantages of genetic algorithm, this paper proposes an improvedgenetic algorithm. In the IMGA algorithm, the improved aspects in specific:①Inorder to avoid the random error generated by the punishment, this paper puts forwardan improved fitness evaluation function with penalty policy, and transforms themultiple objectives QoSR into a single objective optimization problem effectively.②In order to reduce the error selection stage, this paper designs a multi-round rouletteselection operator by increasing the number of disks.③Analyzingthe individualcharacteristics of QoSR model, this paper proposes a crossover operator based onsimilarity to adjust adaptively crossover probability.④Combining with the codecharacteristics of QoSR problem, this paper proposes a mutation operator based onnode connectivity in order to reduce the risk of generating invalid solution.⑤Theexternal elite population keeps the best individual in the parent and recoils theoffspring generating to improve the convergence speed and shorten the response time of QoSR problem effectively.(4) Combining with the advantages of artificial bee colony algorithm, this paperproposes a combination of improved genetic algorithm that the observed bee/scoutbee mechanisms are used for the local optimization in external elite population inparallel with the main genetic evolution to improve the convergence speed andshorten the response time of QoSR.(5) The improved algorithm in this paper are applied to solve QoSR in Salamarandomly generated topology to verify the broad applicability of the algorithms and tobe compared with algorithms based on the related literature to show its effectiveness.