GENETIC
ALGORITHM
BY : GROUP 1
In this document:
1. Introduction
2. How GAs work
3. The TSP as an example
4. Business application
5. Advantages of GA systems
6. Some issues related to GA based systems
Social Media Policy: Guidance For Responsible Online Conduct
September 30, 2023
Introduction:
Genetic Algorithm
History of Genetic Algorithms (GAs) 1954: Nils Aall
Barricelli began simulating evolution using automata
playing a card game.
Early 1970s: John Holland popularized Genetic Algorithms
as an optimization method.
Present: Widely applied across industries—used by
Fortune 500 companies for complex problems like
scheduling, data fitting, trend spotting, and budgeting.
Social Media Policy: Guidance For Responsible Online Conduct
September 30, 2023
Definition of Genetic
Algorithms (GAs)
1. Genetic Algorithms (GAs) are search-based optimization techniques
inspired by Genetics and Natural Selection.
2. Used to find optimal or near-optimal solutions to complex problems
that would otherwise take a lifetime to solve.
3. GAs are part of the broader field of Evolutionary Computation.
How GAs work
Social Media Policy: Guidance For Responsible Online Conduct
September 30, 2023
The ABC of
Transparency and Authenticity:
1 2
Initialization: Fitness Evaluation:
Start with a group of random solutions. Check how good each solution is by
These solutions can be thought of as using a fitness function. This
"individuals" in a population. Each function scores each solution based
solution is often represented as a string on how well it solves the problem. A
of numbers or letters. higher score means a better
solution.
Social Media Policy: Guidance For Responsible Online Conduct
September 30, 2023
How GAs Works?
3 4
Selection: Crossover (Recombination):
Choose pairs of solutions based on Combine pairs of selected solutions to
their scores. Solutions that score create new solutions, called
higher have a better chance of being "offspring." This means mixing parts of
selected. This is similar to nature, each parent solution to make a new
where stronger individuals have a one. It’s like how children inherit traits
higher chance of reproducing. from their parents.
How GAs Works?
5
Mutation:
Make small random changes to some of the new solutions. This helps keep the
population diverse and allows the algorithm to explore new possibilities. It’s like
how random changes in genes can lead to new traits in living things.
6
Replacement:
Replace the old group of solutions with the new ones. Sometimes, the best
solutions from the old group are kept to ensure that good solutions are not lost.
7
Termination:
Repeat the process of evaluating, selecting, crossing over, and mutating until a stopping
point is reached. This could be after a set number of generations or when a solution is
good enough
TSP
Date: September 30, 2023
Prepared by: Henrietta Mitchell
Legal Disclaimer: This presentation is for informational purposes only.
What is TSP?
TSP - Travelling Salesman Problem
The TSP aims to find the shortest route visiting all cities once, returning
to the start. A classic NP-Hard optimization problem.
it is computationally very difficult to solve optimally for a large number
of locations due to the combinatorial explosion of possible routes and its
NP-hard nature.
it is computationally very difficult to solve optimally for a large number
of locations due to the combinatorial explosion of possible routes and its
NP-hard nature.
Social Media Policy: Guidance For Responsible Online Conduct
September 30, 2023
why is TSP NP-Complete?
THE TRAVELLING SALESMAN PROBLEM (TSP) IS NP-COMPLETE
BECAUSE IS SATISFIES TWO KEY CONDITIONS:
1. NP (Non-deterministic polynomial time) 2. NP-Hard
Social Media Policy: Guidance For Responsible Online Conduct
September 30, 2023
The application of genetic algorithm to
involve TSP involves several key step:
1 Initial Population
2 Fitness Evaluation
3 Selection
4 Crossover and Mutation
5 Iteration
Business
Applications of GA
Business Appliction of GA
Genetic algorithms (GAs) are used in business for optimization and decision-
making. Key applications include:
Finance: Portfolio optimization, stock market prediction
Supply Chain: Route optimization, inventory management
Marketing: Customer segmentation, targeted advertising
Manufacturing: Production scheduling, quality control
Human Resource: Employee scheduling, candidate selection
Telecommunication: Network optimization, load balancing
Artificial Intelligence & Machine Learning: Hyperparameter tuning,
feature selection
E-commerce: Dynamic pricing, personalized recommendations
Real Estate: Land-use planning, price prediction
Social Media Policy: Guidance For Responsible Online Conduct
September 30, 2023
Advantages of
Genetic Algorithm
(GA) Systems
Social Media Policy: Guidance For Responsible Online Conduct
September 30, 2023
Advantages of Genetic Algorithm (GA)
Systems
Solves Complex Problems: Useful when no direct algorithm or heuristic exists
Minimal Expert Input Needed: No need to formulate an explicit solution—just
recognize a good one.
Alternative to Traditional Methods: Works where expert systems or optimization
techniques fail.
Near-Optimal Solutions: Does not guarantee perfection but finds very good
solutions efficiently.
Predictable Computation Time: Determined by population size, evaluation speed,
and generations.
Simplicity & Modularity: Easy to integrate into other systems.
Enhances AI Systems: Helps in neural network optimization, rule-based systems,
and business intelligence.
Some issues related
to GA based
systems
Some issues related to GA
based systems
-Level of explainability •Capability to explain why a particular
solution was arrived at is practically nil
•The system does not know what a fitness value really means
-Scalability
•Moderately scalable Accommodates increased number of
variables by increasing the length of the chromosome
Social Media Policy: Guidance For Responsible Online Conduct
September 30, 2023
Some issues related to GA based systems
(cont'd)
-Data requirements
In general, GA do not require extensive access to data but some applications may need it to evaluate solutions
This makes the quality and quantity of data is important
-Local Maxima
Local maxima are regions that hold good solutions relative to regions around them, but which do not necessarily
contain the best overall solutions
The region(s) that contain the best solutions are called global maxima
-Premature convergence
A GA is said to have converged prematurely if it explores a local maximum extensively
It may be then dominated by very similar solutions within the region
Most significant factor leading to such convergence is a mutation rate which is too slow
Some issues related to GA based systems
(cont'd)
Mutation interference
Finding a mutation rate which allows the GA to converge but which also
allows adequate exploration of the solution space is essential for
satisfactory performance
Mutation interference occurs when mutation rates in a GA are too high,
and as a result:
Solutions are frequently or drastically mutated
The algorithm never manages to explore any region of the space
thoroughly
Thank you.
Social Media Policy: Guidance For Responsible Online Conduct
September 30, 2023
