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.
[...] 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. [...]
using our reader.
By continuing to browse, you agree that Oboolo.com may use cookies or equivalent technology to store and / or access information on your device. This personal information (such as your browsing data and your IP address) may be used to present you with personalized content; to measure advertising and content performance, and to learn more about your use of the site. You can configure your choices to accept cookies or not, or to oppose them when the legitimate interest is used. You can also change your preferences at any time by clicking on the "Cookie settings" link at the bottom of the page of this site. For more information, see our Privacy Policy