Ga for shortest_path

Apr 26, 2020Download as PPT, PDF0 likes108 views

This document describes a genetic algorithm for finding the shortest path or tour in the traveling salesman problem (TSP). It introduces genetic algorithms and describes how they are applied to the TSP. The fitness measure calculates the total distance of a tour. Selection uses steady-state selection and crossover uses partially mapped crossover. Mutation uses swap mutation. The overall procedure initializes a population randomly, evaluates fitness, performs crossover and mutation, selects the next generation, and iterates until stopping criteria is met, outputting the best solution found. Experimental results on problem sizes of 10, 20, and 30 cities show the best and average tours found.

GENETIC ALGORITHM
FOR
FINDING THE SHORTEST PATH
Dr. Baljit Singh Khehra
Professor, CSE Department
BBSB Engineering College, Fatehgarh Sahib

Introduction of Genetic Algorithms
• GA is a computer algorithm that searches for good
solutions to a problem among a large number of possible
solutions.
• GAs are based on the mechanism of natural genetics and
natural selection.
• In GAs, maintain a population of some feasible solutions
for given problem.This population undergoes evolution in
a form of natural selection. In each generation relatively
good solutions reproduce and relatively bad solutions die,
to be replaced by the offspring of the good.

Problem Description
•In TSP, to find shortest Hamiltonian cycle in
complete graph.
Permutation Problem.
NP-Hard Problem.

Fitness Measure
Step 1: Traverse the cities according to the sequence in a
tour
Step 2: Calculate d(ci, ci+1) using equation
d(ci, ci+1) = (x-s)2 + (y-t)2
and find the total distance in the tour
n
Total distance = S d (ci, ci+1) + d (cn,c1)
i=1
Step3: Calculate the fitness of the chromosome in the
population using the equation fit (tk) = 1/Total
distance

Selection Method
• Steady-state selection mechanism is used in this
algorithm.
• In steady-state selection, two chromosomes
from population are selected for crossover.
• The offspring so obtained replace the least fit
chromosome in the existing population.

Partially Mapped crossover
Step 1:Two chromosomes as parent P1 and P2 are
aligned, and two crossover sites are picked
uniformly at random along the chromosomes.
Step 2:Each element between the two crossover
points in the alternate parent is mapped to
the position held by this element in the
first parent.
Step3:The remaining elements are inherited from
the parent without any conflict.

Partially Mapped crossover
Step 4:If conflict occurs, then for the first child:
(a) Find the position of the element,where
conflict occurs, in the second parent.
Pick the element from that position in
the first parent and place it that position
where conflict occur in the first child.
(b) For the second child, parent roles
reversed.

Swap Mutation Operator
Step 1: Randomly choose one tour and randomly
select two mutation points.
Step 2: Interchange the cities at these two
points.

Overall Procedure of GA to Solve TSP
Step 1: Setting the parameter
Set the parameter: number of cities n, population
size pop_size, crossover probability pc, mutation
probability pm, and maximum generation maxgen.
Let generation gen = 0, maxeval = 0
Step 2: Initialization
Generate pop_size chromosomes (tours) randomly.

Overall Procedure of GA to Solve TSP
Step 3: Evaluate
Step 3.1: Calculate the fitness value of each chromosome .
Step 3.2: if maxeval < max{fit(tk)}
Then
bestsol = findbest {fit(tk)}
and maxeval = max {fit (tk)}

Overall Procedure of GA to Solve TSP
Step 4: Crossover
Perform the crossover PMX on
chromosomes selected with probability pc.
Step 5: Mutation
Perform the swap mutation on
chromosomes selected with probability pm.

Overall Procedure of GA to Solve TSP
Step 6: Selection
Select pop_size chromosomes from the parents
and offspring for the next generation by steady
state selection method.
Step 7: Stop testing
If gen = maxgen , then output bestsol and stop
Else
gen = gen + 1 and return to step 3

Problem Size GA
10
20
30
BEST AVG
56.47
58.81
64.15
45.36
52.89
55.91
Experimental Results

Performance of the Experiment
Performance of the experiment when n=20:
The size of the solution space:
20! / (20*2) = 60822550204416000
The number of the particles:18
The number of the iterations of the algorithm:2600
The size of the search space: 46800
Search space/solution space: 7.6945E-11%

This document discusses using a genetic algorithm to solve the travelling salesman problem. It begins with an introduction to the travelling salesman problem as an NP-complete problem to find the shortest route visiting each city once. It then provides an overview of genetic algorithms and their use of evolutionary concepts like selection of the fittest to find approximate solutions. The document outlines the genetic algorithm process including encoding routes as chromosomes, calculating fitness, selecting parents for crossover and mutation to create new offspring, and repeating until an optimal solution is found. It provides details of the genetic algorithm implementation for the travelling salesman problem.

Geneticalgorithms 100403002207-phpapp02Amna Saeed

��

This document provides an introduction to genetic algorithms. It discusses that genetic algorithms are inspired by Darwinian evolution and use processes like selection, crossover and mutation to evolve solutions to problems. It also provides examples of how genetic algorithms can be used for optimization problems and classification in data mining. The key steps of a genetic algorithm including initializing a population, evaluating fitness, selection, crossover and mutation are outlined.

1582997627872.pdfAbhilashJain25

��

Traveling Salesman Problem (TSP) is a kind of NPHard problem which cant be solved in polynomial time for asymptotically large values of n. In this paper a balanced combination of Genetic algorithm and Simulated Annealing is used. To improve the performance of finding optimal solution from huge search space, we have incorporated the use of tournament and rank as selection operator. And Inver-over operator Mechanism for crossover and mutation . To illustrate it more clearly an implementation in C++ (4.9.9.2) has been done. Index Terms—Genetic Algorithm (GA) , Simulated Annealing (SA) , Inver-over operator , Lin-Kernighan algorithm , selection operator , crossover operator , mutation operator.

Genetic algorithmgarima931

��

AN IMPROVED ITERATIVE METHOD FOR SOLVING GENERAL SYSTEM OF EQUATIONS VIA GENE...Zac Darcy

��

Various algorithms are known for solving linear system of equations. Iteration methods for solving the large sparse linear systems are recommended. But in the case of general n× m matrices the classic iterative algorithms are not applicable except for a few cases. The algorithm presented here is based on the minimization of residual of solution and has some genetic characteristics which require using Genetic Algorithms. Therefore, this algorithm is best applicable for construction of parallel algorithms. In this paper, we describe a sequential version of proposed algorithm and present its theoretical analysis. Moreover we show some numerical results of the sequential algorithm and supply an improved algorithm and compare the two algorithms.

An Improved Iterative Method for Solving General System of Equations via Gene...Zac Darcy

��

An Improved Iterative Method for Solving General System of Equations via Gene...Zac Darcy

��

An Improved Iterative Method for Solving General System of Equations via Gene...Zac Darcy

��

An Improved Iterative Method for Solving General System of Equations via Gene...Zac Darcy

��

Particle Swarm OptimizationQasimRehman

��

This document discusses particle swarm optimization (PSO), which is an optimization technique inspired by swarm intelligence and the social behavior of bird flocking or fish schooling. PSO uses a population of candidate solutions called particles that fly through the problem hyperspace, with each particle adjusting its position based on its own experience and the experience of neighboring particles. The algorithm iteratively improves the particles' positions to locate the best solution based on fitness evaluations.

GABPN genetic algorithm based back propogation networknew.pptxravikumarfulwaria

��

Genetic AlgorithmJagadish Mohanty

��

Genetic algorithms are heuristic search methods inspired by natural selection that can be used to find optimized solutions to problems. They work by generating an initial random population of solutions and then applying genetic operations like selection, crossover and mutation to produce new solutions over multiple generations. The fittest solutions survive and weaker ones die out, causing the overall population to become better adapted to the problem being solved. Genetic algorithms are well-suited for searching large, complex datasets and problems with multimodal or n-dimensional search spaces.

Quantum inspired evolutionary algorithm for solving multiple travelling sales...eSAT Publishing House

��

IJRET : International Journal of Research in Engineering and Technology is an international peer reviewed, online journal published by eSAT Publishing House for the enhancement of research in various disciplines of Engineering and Technology. The aim and scope of the journal is to provide an academic medium and an important reference for the advancement and dissemination of research results that support high-level learning, teaching and research in the fields of Engineering and Technology. We bring together Scientists, Academician, Field Engineers, Scholars and Students of related fields of Engineering and Technology

Genetic AlgorithmSHIMI S L

��

Genetic algorithms are a type of evolutionary algorithm that mimics natural selection. They operate on a population of potential solutions applying operators like selection, crossover and mutation to produce the next generation. The algorithm iterates until a termination condition is met, such as a solution being found or a maximum number of generations being produced. Genetic algorithms are useful for optimization and search problems as they can handle large, complex search spaces. However, they require properly defining the fitness function and tuning various parameters like population size, mutation rate and crossover rate.

Genetic algorithmsguest9938738

��

An Implementational approach to genetic algorithms for TSPSougata Das

��

This document summarizes a research paper that proposes using a genetic algorithm to solve the travelling salesman problem (TSP) as applied to water distribution network optimization. The genetic algorithm aims to find Pareto optimal solutions by evolving two populations that optimize the objectives of minimizing cost and maximizing profit of water distribution routes. The algorithm uses techniques like selection, crossover and mutation over generations to evolve solutions toward the Pareto front. It represents solutions as ordered lists of cities and evaluates fitness based on multiple criteria to maintain genetic diversity.

Genetic algorithmJari Abbas

��

BGA.pptxShubhamKamble942039

��

The document discusses binary genetic algorithms. It begins by motivating GAs as able to find good enough solutions fast enough compared to traditional methods. It then describes GAs as optimization techniques based on genetics and natural selection. The key steps of a binary GA are described as population initialization, fitness calculation, selection, crossover, mutation, and termination. Example applications like the travelling salesman problem are provided. Advantages include not requiring derivatives, always finding an answer, and being faster than traditional methods. Limitations include high computational cost of fitness calculations and potential lack of convergence to the optimal solution.

Genetic algorithm optimization technique.pptxsridharece1

��

10.1.1.34.7361Rahmat Fauzi

��

1) The document presents an approach to solving the inverse kinematics problem of robotic manipulators using genetic algorithms. 2) Genetic algorithms are applied by encoding joint angles into chromosomes and evaluating fitness based on end-effector position and orientation accuracy. 3) The approach handles redundancies and singularities effectively and can compute motions for manipulators to follow specified end-effector paths.

Genetic AlgorithmsKarthik Sankar

��

This document provides an introduction to genetic algorithms. It explains that genetic algorithms are inspired by Darwinian evolution and use processes like selection, crossover and mutation to iteratively improve a population of potential solutions. It discusses how genetic algorithms can be used for optimization problems and classification in data mining. Examples of genetic algorithm applications like the traveling salesman problem are also presented to illustrate genetic algorithm concepts and processes.

D0353027043inventionjournals

��

International Journal of Engineering and Science Invention (IJESI) is an international journal intended for professionals and researchers in all fields of computer science and electronics. IJESI publishes research articles and reviews within the whole field Engineering Science and Technology, new teaching methods, assessment, validation and the impact of new technologies and it will continue to provide information on the latest trends and developments in this ever-expanding subject. The publications of papers are selected through double peer reviewed to ensure originality, relevance, and readability. The articles published in our journal can be accessed online.

Pso notesDarshan Sharma

��

Particle swarm optimization is a technique for finding the best solution to a problem within a search space, inspired by bird flocking behavior. It initializes a population of random particles representing potential solutions and updates their positions based on their own experience and the experiences of neighboring particles. Over iterations, the population is guided toward better solutions as particles emulate the most successful neighbors. Compared to genetic algorithms, particle swarm optimization uses a one-way information sharing mechanism to guide the population toward the best found solution. The key parameters that can be adjusted include the number of particles, their maximum velocity, and learning factors that balance how much particles rely on their own experience versus the experiences of neighbors.

53564379-Ant-Colony-Optimization.pptAhmedSalimJAlJawadi

��

The document discusses ant colony optimization (ACO), which is an algorithm inspired by how ants find food. It describes how ants deposit pheromones to mark shorter paths, reinforcing them. The ACO algorithm simulates this process, with "ants" probabilistically building solutions and updating pheromones. It provides pseudocode and discusses applications to problems like the traveling salesman problem. ACO shows good performance on distributed, combinatorial optimization problems.

F0422052058ijceronline

��

Optimization Using Evolutionary Computing Techniques Siksha 'O' Anusandhan (Deemed to be University )

��

The document discusses various optimization techniques including evolutionary computing techniques such as particle swarm optimization and genetic algorithms. It provides an overview of the goal of optimization problems and discusses black-box optimization approaches. Evolutionary algorithms and swarm intelligence techniques that are inspired by nature are also introduced. The document then focuses on particle swarm optimization, providing details on the concepts, mathematical equations, components and steps involved in PSO. It also discusses genetic algorithms at a high level.

Muzammil Adulrahman ppt on travelling salesman Problem Based On Mutation Gene...Petroleum Training Institute

��

Particle Swarm OptimizationStelios Petrakis

��

Particle swarm optimization is a population-based stochastic optimization technique inspired by bird flocking or fish schooling. It works by having a population of candidate solutions, called particles, and moving these particles around in the search space according to simple mathematical formulae over the particle's position and velocity. Each particle keeps track of its coordinates in the problem space which are associated with the best solution that particle has achieved so far. The main idea is that hope flies along with the flock.

Ann 3DrBaljitSinghKhehra

��

This document describes the ART1 neural network model, an unsupervised learning algorithm. ART1 performs clustering of binary input patterns. It has two layers of units (F1 and F2) with adaptive weights between them. The vigilance parameter ρ controls the level of similarity for patterns to be assigned to the same cluster. During training, an input is presented and the most active F2 unit is selected as the winner. Weights are updated only if the input and winner activation are sufficiently similar as determined by ρ. Otherwise, the network resets and searches for a better match. This continues until all patterns are clustered.

Deep learningDrBaljitSinghKhehra

��

The document discusses deep learning and convolutional neural networks. It provides details on concepts like convolution, activation maps, pooling, and the general architecture of CNNs. CNNs are made up of repeating sequences of convolutional layers and pooling layers, followed by fully connected layers at the end. Convolutional layers apply filters to input images or feature maps from previous layers to extract features. Pooling layers reduce the spatial size to make representations more manageable.

More Related Content

Similar to Ga for shortest_path (20)

An Improved Iterative Method for Solving General System of Equations via Gene...Zac Darcy

��

Particle Swarm OptimizationQasimRehman

��

GABPN genetic algorithm based back propogation networknew.pptxravikumarfulwaria

��

Genetic AlgorithmJagadish Mohanty

��

Quantum inspired evolutionary algorithm for solving multiple travelling sales...eSAT Publishing House

��

Genetic AlgorithmSHIMI S L

��

Genetic algorithmsguest9938738

��

An Implementational approach to genetic algorithms for TSPSougata Das

��

Genetic algorithmJari Abbas

��

BGA.pptxShubhamKamble942039

��

Genetic algorithm optimization technique.pptxsridharece1

��

10.1.1.34.7361Rahmat Fauzi

��

Genetic AlgorithmsKarthik Sankar

��

D0353027043inventionjournals

��

Pso notesDarshan Sharma

��

53564379-Ant-Colony-Optimization.pptAhmedSalimJAlJawadi

��

F0422052058ijceronline

��

Optimization Using Evolutionary Computing Techniques Siksha 'O' Anusandhan (Deemed to be University )

��

Muzammil Adulrahman ppt on travelling salesman Problem Based On Mutation Gene...Petroleum Training Institute

��

Particle Swarm OptimizationStelios Petrakis

��

An Improved Iterative Method for Solving General System of Equations via Gene...Zac Darcy

��

Particle Swarm OptimizationQasimRehman

��

GABPN genetic algorithm based back propogation networknew.pptxravikumarfulwaria

��

Genetic AlgorithmJagadish Mohanty

��

Quantum inspired evolutionary algorithm for solving multiple travelling sales...eSAT Publishing House

��

Genetic AlgorithmSHIMI S L

��

Genetic algorithmsguest9938738

��

An Implementational approach to genetic algorithms for TSPSougata Das

��

Genetic algorithmJari Abbas

��

BGA.pptxShubhamKamble942039

��

Genetic algorithm optimization technique.pptxsridharece1

��

10.1.1.34.7361Rahmat Fauzi

��

Genetic AlgorithmsKarthik Sankar

��

D0353027043inventionjournals

��

Pso notesDarshan Sharma

��

53564379-Ant-Colony-Optimization.pptAhmedSalimJAlJawadi

��

F0422052058ijceronline

��

Optimization Using Evolutionary Computing Techniques Siksha 'O' Anusandhan (Deemed to be University )

��

Muzammil Adulrahman ppt on travelling salesman Problem Based On Mutation Gene...Petroleum Training Institute

��

Particle Swarm OptimizationStelios Petrakis

��

More from DrBaljitSinghKhehra (6)

Ann 3DrBaljitSinghKhehra

��

Deep learningDrBaljitSinghKhehra

��

Back propagation DrBaljitSinghKhehra

��

This document describes the backpropagation algorithm for training multilayer artificial neural networks (ANNs). It discusses the key aspects of the backpropagation algorithm including: the initialization of weights and biases, feedforward propagation, backpropagation of error to calculate weight updates, and updating weights and biases. It provides pseudocode for the backpropagation training algorithm and discusses factors that affect learning like learning rate and momentum. It also gives an example of using backpropagation for load forecasting in power systems, showing the network architecture, training algorithm, and results.

Artificial Neural Networks-Supervised Learning ModelsDrBaljitSinghKhehra

��

The document discusses soft computing and artificial neural networks. It provides an overview of soft computing techniques including artificial neural networks (ANNs), fuzzy logic, and evolutionary computing. It then focuses on ANNs, describing their biological inspiration from neurons in the brain. The basic components of ANNs are discussed including network architecture, learning algorithms, and activation functions. Specific ANN models are then summarized, such as the perceptron, ADALINE, and their learning rules. Applications of ANNs are also briefly mentioned.

Artificial Neural Networks-Supervised Learning ModelsDrBaljitSinghKhehra

��

The document discusses artificial neural networks (ANNs) and summarizes key information about soft computing techniques, ANNs, and some specific ANN models including perceptrons, ADALINE, and MADALINE. It defines soft computing as a collection of computational techniques including neural networks, fuzzy logic, and evolutionary computing. ANNs are modeled after the human brain and consist of interconnected neurons that can learn from examples. Perceptrons, ADALINE, and MADALINE are early ANN models that use different learning rules to update weights and biases.

Artificial Neural Networks-Supervised Learning ModelsDrBaljitSinghKhehra

��

The document discusses artificial neural networks (ANNs) and summarizes key information about ANNs and related topics. It defines soft computing as a field that aims to build intelligent machines using techniques like ANNs, fuzzy logic, and evolutionary computing. ANNs are modeled after biological neural networks and consist of interconnected nodes that can learn from data. Early ANN models like the perceptron, ADALINE, and MADALINE are described along with their learning rules and architectures. Applications of ANNs in various domains are also listed.

Ann 3DrBaljitSinghKhehra

��

Deep learningDrBaljitSinghKhehra

��

Back propagation DrBaljitSinghKhehra

��

Artificial Neural Networks-Supervised Learning ModelsDrBaljitSinghKhehra

��

Artificial Neural Networks-Supervised Learning ModelsDrBaljitSinghKhehra

��

Artificial Neural Networks-Supervised Learning ModelsDrBaljitSinghKhehra

��

Recently uploaded (20)

Comprehensive Hematology Overview: Blood Physiology, Disorders, and Diagnosticsrdiasolatorio

��

Steve Nickel In God I Trust 03.23.2025.pptxFamilyWorshipCenterD

��

Supporting innovations at scale through relevant funding mechanisms and marketsFrancois Stepman

��

11-13 March 2025. Brussels. Conference on ´Boosting agrifood research and innovation cooperation for impact at scale Extract of Day 2 How to support innovation at scale for productive, inclusive and sustainable food system transformation and potential contribution of research Session 2: Supporting innovations at scale through relevant funding mechanisms and markets: Elise Juguet, Horus Development Finance

1. Critical thinking to write down .pptxhibahassan160702

��

Front-End Specialization Certification: A Journey with Style!ShubhamSharma2528

��

The Global NARS Consortium (GNC) supported by: Transforming the Agri-Food Sys...Francois Stepman

��

11-13 March 2025. Brussels. Conference on ´Boosting agrifood research and innovation cooperation for impact at scale Day 3: GFAiR, innovating and operationalising agile impact partnership at scale Global Forum on Agricultural Research and Innovation (GFAiR) and AgriCord presented and discussed the Global NARS Consortium (GNC) with (funding) partners. With the participation of EC DG INTPA, APAARI, EFARD, FARA, sub-regional R&I Organisations and NARS in Africa, and CGIAR. Ravi Khetarpal, Executive Secretary of APAARI

Shadows of Tet story created by me for a worklucasczaffari

��

Attitude Presentation on people behavioursAbrar Ali Shah

��

A Resilient Caribbean: Catalysing our TransformationCaribbean Development Bank

��

Present Continuous Tense kelas 8 kurikulum k13agustinusgudipun

��

FACEBOOK-AS-ONLINE-BUSINESS-PLATFORM.pptxestenzomaria08

��

Building Resilience to Climate Change and Disasters in the CaribbeanCaribbean Development Bank

��

Réunion à Paris sur ECCE unesco 2006RdM-RoW Blog story

��

Video Skills for Authors: Mastering Your On-Camera PresencePaula Rizzo

��

Hosted by Jane Friedman - March 21, 2025 Video can connect you with readers like no other medium, and leveraging video helps you expand your reach. Join Paula Rizzo, Emmy Award-winning TV producer and bestselling author, in this free session where you'll learn how to create captivating videos, excel in media interviews, and harness the power of video to boost your book's visibility and success. Learn from a seasoned professional and take your video skills to the next level. We'll cover: — Crafting Engaging Videos: produce videos that capture attention and hold it, making your message memorable. — Having On-Camera Confidence: deliver compelling and persuasive media interviews that resonate with your audience in podcasts, on television, radio and anywhere online. — Creating Newsworthy Content: Structure your stories to appeal to both the media and your readers. — Production Best Practices: Get the inside scoop on what works (and what doesn't) in video production. — Leveraging Video for Marketing: Drive book sales, attract media attention, and grow your audience. paularizzo.com/10q-Jane - for free download "10 Questions Every Author Needs to Answer In the Media"

Raspberry-Pi-as-a-Web-Server-Complete.pptxSaqibAwan37

��

SMALL-BUSINESS: the impacts of small business enterprisesestenzomaria08

��

Book Presentation - Hacking Home Devices I: PoCs & Hacks Just for FunGerard Fuguet

��

The official presentation of my first book: “Hacking Home Devices I: PoCs & Hacks Just for Fun” Published under 0xWord editorial. Was presented in Barcelona, in the library of my hometown (Sant Just Desvern). The event was scheduled on 2025-03-12 and started at 19:00h About the book: This book explores creative and surprising ways to “hack” home devices for fun, with proofs of concepts (PoCs) and ingenious hacks. It's a practical guide for hackers and enthusiasts, curious about computing (IT) who want to experiment with home technology in a safe and entertaining way. The town council made it public in the following links (under Catalan language): https://web.archive.org/web/20250226080308/https://biblioteca.santjust.net/presentacio-del-llibre-hacking-home-devices-de-gerard-fuguet/ https://www.radiodesvern.com/news/presentacio-a-can-ginestar-del-llibre-sobre-hacks-domestics-creatius-de-gerard-fuguet The book (under Spanish language) is available online at: https://0xword.com/es/libros/238-hacking-home-devices-i-pocs-hacks-just-for-fun.html

2025-03-23 FATC 04 Mary, Martha, Lazarus & Mary Magdalene (shared slides).pptxDale Wells

��

Rebirth: Innovate, Transform and Thrive for a Resilient FutureCaribbean Development Bank

��

Regional Economic Performance and Prospects: Progress Towards a Resilient FutureCaribbean Development Bank

��

Comprehensive Hematology Overview: Blood Physiology, Disorders, and Diagnosticsrdiasolatorio

��

Steve Nickel In God I Trust 03.23.2025.pptxFamilyWorshipCenterD

��

Supporting innovations at scale through relevant funding mechanisms and marketsFrancois Stepman

��

1. Critical thinking to write down .pptxhibahassan160702

��

Front-End Specialization Certification: A Journey with Style!ShubhamSharma2528

��

The Global NARS Consortium (GNC) supported by: Transforming the Agri-Food Sys...Francois Stepman

��

Shadows of Tet story created by me for a worklucasczaffari

��

Attitude Presentation on people behavioursAbrar Ali Shah

��

A Resilient Caribbean: Catalysing our TransformationCaribbean Development Bank

��

Present Continuous Tense kelas 8 kurikulum k13agustinusgudipun

��

FACEBOOK-AS-ONLINE-BUSINESS-PLATFORM.pptxestenzomaria08

��

Building Resilience to Climate Change and Disasters in the CaribbeanCaribbean Development Bank

��

Réunion à Paris sur ECCE unesco 2006RdM-RoW Blog story

��

Video Skills for Authors: Mastering Your On-Camera PresencePaula Rizzo

��

Raspberry-Pi-as-a-Web-Server-Complete.pptxSaqibAwan37

��

SMALL-BUSINESS: the impacts of small business enterprisesestenzomaria08

��

Book Presentation - Hacking Home Devices I: PoCs & Hacks Just for FunGerard Fuguet

��

2025-03-23 FATC 04 Mary, Martha, Lazarus & Mary Magdalene (shared slides).pptxDale Wells

��

Rebirth: Innovate, Transform and Thrive for a Resilient FutureCaribbean Development Bank

��

Regional Economic Performance and Prospects: Progress Towards a Resilient FutureCaribbean Development Bank

��

Ga for shortest_path

1. GENETIC ALGORITHM FOR FINDING THE SHORTEST PATH Dr. Baljit Singh Khehra Professor, CSE Department BBSB Engineering College, Fatehgarh Sahib

2. Introduction of Genetic Algorithms • GA is a computer algorithm that searches for good solutions to a problem among a large number of possible solutions. • GAs are based on the mechanism of natural genetics and natural selection. • In GAs, maintain a population of some feasible solutions for given problem.This population undergoes evolution in a form of natural selection. In each generation relatively good solutions reproduce and relatively bad solutions die, to be replaced by the offspring of the good.

3. Problem Description •In TSP, to find shortest Hamiltonian cycle in complete graph. Permutation Problem. NP-Hard Problem.

4. Fitness Measure Step 1: Traverse the cities according to the sequence in a tour Step 2: Calculate d(ci, ci+1) using equation d(ci, ci+1) = (x-s)2 + (y-t)2 and find the total distance in the tour n Total distance = S d (ci, ci+1) + d (cn,c1) i=1 Step3: Calculate the fitness of the chromosome in the population using the equation fit (tk) = 1/Total distance

5. Selection Method • Steady-state selection mechanism is used in this algorithm. • In steady-state selection, two chromosomes from population are selected for crossover. • The offspring so obtained replace the least fit chromosome in the existing population.

6. Partially Mapped crossover Step 1:Two chromosomes as parent P1 and P2 are aligned, and two crossover sites are picked uniformly at random along the chromosomes. Step 2:Each element between the two crossover points in the alternate parent is mapped to the position held by this element in the first parent. Step3:The remaining elements are inherited from the parent without any conflict.

7. Partially Mapped crossover Step 4:If conflict occurs, then for the first child: (a) Find the position of the element,where conflict occurs, in the second parent. Pick the element from that position in the first parent and place it that position where conflict occur in the first child. (b) For the second child, parent roles reversed.

8. Swap Mutation Operator Step 1: Randomly choose one tour and randomly select two mutation points. Step 2: Interchange the cities at these two points.

9. Overall Procedure of GA to Solve TSP Step 1: Setting the parameter Set the parameter: number of cities n, population size pop_size, crossover probability pc, mutation probability pm, and maximum generation maxgen. Let generation gen = 0, maxeval = 0 Step 2: Initialization Generate pop_size chromosomes (tours) randomly.

10. Overall Procedure of GA to Solve TSP Step 3: Evaluate Step 3.1: Calculate the fitness value of each chromosome . Step 3.2: if maxeval < max{fit(tk)} Then bestsol = findbest {fit(tk)} and maxeval = max {fit (tk)}

11. Overall Procedure of GA to Solve TSP Step 4: Crossover Perform the crossover PMX on chromosomes selected with probability pc. Step 5: Mutation Perform the swap mutation on chromosomes selected with probability pm.

12. Overall Procedure of GA to Solve TSP Step 6: Selection Select pop_size chromosomes from the parents and offspring for the next generation by steady state selection method. Step 7: Stop testing If gen = maxgen , then output bestsol and stop Else gen = gen + 1 and return to step 3

13. Experimental Results

14. The best tour after 2600 iterations

15. Problem Size GA 10 20 30 BEST AVG 56.47 58.81 64.15 45.36 52.89 55.91 Experimental Results

16. Performance of the Experiment Performance of the experiment when n=20: The size of the solution space: 20! / (20*2) = 60822550204416000 The number of the particles:18 The number of the iterations of the algorithm:2600 The size of the search space: 46800 Search space/solution space: 7.6945E-11%

17. Thanks

�ݺ�ߣ

Ga for shortest_path

Recommended

More Related Content

Similar to Ga for shortest_path (20)

More from DrBaljitSinghKhehra (6)

Recently uploaded (20)

Ga for shortest_path