Genetic algorithmic approach for multi objective weighted spanning tree

Ace p.

Can't find what you are looking for? Order a tailor-made document!

Let's try

Thesis Format .pdf

Genetic algorithmic approach for multi objective weighted spanning tree

Download

Read an extract

Reader
Abstract
Contents
Extract

Abstract

The minimum weight spanning tree is a well known problem in the networking area, having a wide range of applications. In this paper, a new approach for dealing with multi objective weighted spanning tree is proposed. The proposed method uses Genetic Algorithm to generate non dominated spanning trees from a given multiple objective network. Network optimization problem is the problem of determining the optimum solution of a network with respect to the given optimization criteria. If the number of criteria to be optimized is one, then the problem is called Single Objective Network Optimization Problem and if it is more than one, then it is called Multiple Objective Network optimization Problem.

Keywords: Optimization, Spanning tree, Minimum weight spanning tree (MWST), Multi Objective, Pareto Minimum, Genetic algorithm.

Abstract
Introduction
Terminologies
1. Relation of dominance
2. Non dominated or pareto minimum spanning tree
The proposed method
Genetic algorithm for multi objective weighted spanning tree
Conclusion
Bibliography

Extract

[...] STEP Crossover STEP Mutation STEP Replace the parent chromosomes by their corresponding off-springs got from step 5 and step 6 to get the new population. STEP Terminality test. If k = max_gen then stop, otherwise let k = k + 1 and go to step CONCLUSION: For finding out the minimum weight spanning tree using Prim's algorithm, step1 of this algorithm require O(n3) elementary operations. Step 4 of this algorithm requires constant multiple of O(n2) elementary operations to decode pop_size chromosomes and to find Pareto minimum value. The algorithm [...]

[...] GENETIC ALGORITHM FOR MULTI OBJECTIVE WEIGHTED SPANNING TREE STEP Convert the given multi objective network into single objective and find the minimum weight spanning tree by Prims algorithm. Find the multi objective value for the spanning tree and assign it as fitness value. The set STj ( j = .µ ) Store the value of Pareto minimum weighted spanning trees in the set STj ( j = .µ ) STEP Set the population size as pop_size mutation rate Rm, crossover rate Rc, maximum number of generation as max_gen and let k = 0. [...]

pdf