CASE STUDY 2022:

GENETIC ALGORITHMS
COMPUTER SCIENCE
PAPER 3 HL
CASE STUDY 2022

• D:\New_CS_grade12\2022 CASE STUDY\CASE STUDY 2022.pdf

Important link:-

https://arxiv.org/pdf/1909.06447.pdf
Time complexity

In computer science, the time complexity is the computational complexity that describes the amount of computer
time it takes to run an algorithm.

In computer science, best, worst, and average cases of a given algorithm express what the resource usage

is at least, at most and on average, respectively. Usually the resource being considered is running time, i.e. 
time complexity, but could also be memory or other resource. Best case is the function which performs the
minimum number of steps on input data of n elements. Worst case is the function which performs the maximum
number of steps on input data of size n. Average case is the function which performs an average number of
steps on input data of n elements.

https://www.mygreatlearning.com/blog/why-is-time-complexity-essential/
Polynomial-Time Algorithms

A polynomial-time algorithm is an algorithm whose execution time is either given by a polynomial on the size of the input, or
can be bounded by such a polynomial. Problems that can be solved by a polynomial-time algorithm are
called tractable problems.

For example, most algorithms on arrays can use the array size, n, as the input size. To find the largest element in an array
requires a single pass through the array, so the algorithm for doing this is O(n), or linear time.
Sorting algorithms usually require either O(n log n) or O(n2) time. Bubble sort takes linear time in the best case, but O(n 2) time
in the average and worst cases. Heapsort takes O(n log n) time in all cases. Quicksort takes O(n log n) time on average, but
O(n2) time in the worst case.

Regarding O(n log n) time, note that

•The base of the logarithms is irrelevant, since the difference is a constant factor, which we ignore; and
•Although n log n is not, strictly speaking, a polynomial, the size of n log n is bounded by n2, which is a polynomial.
Probably all the programming tasks you are familiar with have polynomial-time solutions. This is not because all practical
problems have polynomial-time solutions. Rather, it is because your courses and your day-to-day work have avoided problems
for which there is no known practical solution.
BRUTE FORCE APPROACH

• What is brute force approach in algorithm?

• A Brute Force Algorithm is the straightforward approach to a problem i.e., the
first approach that comes to our mind on seeing the problem. More technically it
is just like iterating every possibility available to solve that problem. For Example:
If there is a lock of 4-digit PIN
WHAT IS BRUTE FORCE ATTACK?

• A brute force attack, also known as an exhaustive search, is a cryptographic

hack that relies on guessing possible combinations of a targeted password
until the correct password is discovered. The longer the password, the more
combinations that will need to be tested.
GENETIC ALGORITHM

• https://youtu.be/1i8muvzZkPw
• https://youtu.be/3GAfjE_ChRI
• https://www.tutorialspoint.com/genetic_algorithms/genetic_algorithms_fundamentals.htm
GENETIC ALGORITHM

• Genetic algorithm, in artificial intelligence, a type of evolutionary computer algorithm in which

symbols (often called “genes” or “chromosomes”) representing possible solutions are “bred.”
• This “breeding” of symbols typically includes the use of a mechanism analogous to the crossing-over
process in genetic recombination and an adjustable mutation rate.
• A fitness function is used on each generation of algorithms to gradually improve the solutions in 
analogy to the process of natural selection. The process of evolving the genetic algorithms and
automating the selection is known as genetic programming.
Reference: https://www.britannica.com/technology/genetic-algorithm
*mutation is genetic operator used to maintain genetic diversity from one generation of a population to
next.
WHERE GENETIC ALGORITHM IS USED?

• Genetic algorithms are used in the traveling salesman problem to establish an

efficient plan that reduces the time and cost of travel. It is also applied in other
fields such as economics, multimodal optimization, aircraft design, and DNA
analysis.
COMBINATORIAL OPTIMIZATION

•  Combinatorial optimization is a topic that consists of finding an optimal

object from a finite set of objects.
COMPUTATIONAL INTRACTABILITY

• Dictionary Definition of intractable: “difficult to treat or work.”

• Computer Science: problem is intractable if a computer has difficulty solving it

• this means that we cannot normally expect efficient algorithms for these problems, they must
nevertheless be solved. Scheduling problems, for example, must routinely be solved by transportation
companies, sports schedulers, computer hardware, etc. Approaches to solving intractable problems
often involve approximation, heuristics, and/or the use of exponential algorithms such as integer
programming
• Reference : https://www.cpp.edu/~ftang/courses/CS331/notes/P%20and%20NP.pdf
CONVERGENCE IN ALGORITHM

• An iterative algorithm is said to converge when as the iterations proceed the

output gets closer and closer to a specific value.
• Full convergence might be seen in genetic algorithms (a type of evolutionary
computation) using only crossover (a way of combining individuals to make new
offspring).
GENETIC ALGORITHMS (GA)

• Genetic algorithms (GA) are search algorithms based on the principles of natural selection and
genetics
• GA tries to explore the fittest individual by producing generations iteratively
• GA evolves a population of initial individuals to a population of high quality individuals, where
each individual represents a solution of the problem to be solved
• During each generation, three basic genetic operators are sequentially applied to each individual
with certain probabilities, i.e. selection, crossover and mutation
• [Selection operator ] Selection operation is to select elitist individuals as parents in current
population, which can generate offspring. Fitness values are used as criteria to judge whether
individuals are elitist.
• [Crossover operator] With a crossover probability cross over the parents to form a new offspring
(children). If no crossover was performed, offspring is an exact copy of parents.
• [Mutation operator] With a mutation probability mutate new offspring at each locus (position in
chromosome).
• Implementation details vary considerably, but a standard genetic algorithm includes
the following steps:
• Page 4 and 5 from case study
 GENETIC ALGORITHM GENERAL STEPS

• [Start] Generate random population of n chromosomes (suitable

solutions for the problem).
• 2. [Fitness] Evaluate the fitness f(x) of each chromosome x in
• the population. c. [Mutation] With a mutation probability mutate new
offspring at each locus (position in chromosome).
• 3. [New population] Create a new population by repeating d. [Accepting] Place new offspring in a new
• following steps until the new population is complete population.
4. [Replace] Use new generated population for a
• a. [Selection] Select two parent chromosomes from a further run
• population according to their fitness (the better fitness, the
of algorithm.
5. [Test] If the end condition is satisfied, stop, and
• bigger chance to be selected). return the
best solution in current population.
• b. [Crossover] With a crossover probability cross over the
6. [Loop] Go to step 2.
• parents to form a new offspring (children). If no crossover }
• was performed, offspring is an exact copy of parents.
IMPORTANT TERMINOLOGIES

• In GA, the search space(Search space is space of all feasible solutions (the set of solutions among
which the desired solution resides)
consists of strings, each of which representing a candidate solution to the problem and are termed as
chromosomes.
• The objective function value of each chromosome is called its fitness value.
• Population is a set of chromosomes along with their associated fitness.
• Generations are populations generated in an iteration of the GA
FITNESS FUNCTION

• A fitness function is used to assign a fitness value to each tour. Individual tours are sorted according
to their fitness.
• The highest fitness value is assigned to the shortest tour.

• Fitness function is the important parameter of a genetic algorithm that defines the fitness of each chromosome
where the values of genetic parameters are adapted as the genetic evolution progresses.
• At every generation, fitness value of each chromosome is calculated using fitness function. If fitness of two
chromosomes is equal, then the mutation rate is increased, in order to help the genetic evolution get out of issues
like local maxima or local minima whichever is applicable.
• TSP is a minimization problem; we consider fitness function calculates cost (or value) of the tour
represented by a chromosome.
As you probably know, we should always accomplish a proper balance between exploration and exploitation ability of
the searching/optimiser algorithm.

Exploration means searching search space as much as possible,

while exploitation means concentrating on one point (hopefully the global optimum).

In GA, mutation operators are mostly used to provide exploration and cross-over operators are widely used to lead
population to converge on one the good solutions find so far (exploitation).

Consequently, while cross-over tries to converge to a specific point in landscape, mutation does its best to avoid
convergence and explore more areas.
Obviously, we prefer to explore much more in the beginning of the search process (to ensure the population coverage
and diversity).
On the other hand, we prefer more exploitations at the end of search process to ensure the convergence of the
population to the global optimum.
There is just an exception; when population converges to a local optimum, we should (if we can) increase the
population diversity to explore other areas.
According to the above facts, too high mutation rate increases the probability of searching more areas in search
space, however, prevents population to converge to any optimum solution.
On the other hand, too small mutation rate may result to premature convergence (falling to local optima instead of
global optimum).In other words, too high mutation rate reduces the search ability of GA to a simple random walk
while a too small GA (without any other facilities such as niching or crowd-avoiding to preserve diversity) almost
always fails to a local optimum.
As Larry Raisanen mentioned, the best value of mutation rate is very problem specific. You can try several values
in linear or bidirectional manner. Remember, as Colin Reeves wrote, this value also depends on the nature and
implementation of the algorithm.In my opinion,

however, there is no constant best mutation rate for most of the real world problems. As I mentioned before,
searching algorithm demands different exploration-exploitation ability in different stage of the search process.
Hence, a more dynamic mutation rate, as Paulo Gaspar proposed, is more preferred. I believe you can find more
complex methods which adaptively tune the mutation rate according to the problem and the state of the current
population comparing with the previous ones.
Local maxima are a major problem not just for genetic algorithms, but any optimization technique that sets out to find
the global optimum.
A genetic algorithm works nicely in the exploration stage, with each of the individuals discovering pieces of the solution
and combining them together.
However when a locally optimal point is achieved by a particular individual, it manages to hold the lead for a number of
iterations and all individuals start looking alike.
The leader survives through generations, and contributes in many crossovers, distributing its genes to every other
candidate. The distant explorers are outperformed and gradually eliminated.
Finally, progress comes to a halt when diversity ceases to exist.

optimization algorithms sometimes return a local minimum—a point where the function value is
smaller than at nearby points, but possibly greater than at a distant point in the search
space. The genetic algorithm can sometimes overcome this deficiency with the right settings.
THE TRAVELING SALESMAN PROBLEM (TSP)

• The traveling salesman problem (TSP) is perhaps the most well known combinatorial optimization
problem(is a topic that consists of finding an optimal object from a finite set of
objects.).
• TSP is to find a routing of a salesman who starts from a home location, visits a prescribed set of
cities and returns to the original location in such a way that the total distance travelled is minimum
and each city is visited exactly once.
Tournament Selection

In tournament selection, every individual in the population is paired at random with another.

The fitness values of each pair are compared.

The fitter individual of the pair moves on to the next round‟, while the other is disqualified.

This continues until there are a number of winners equal to the desired number of parents. Then this last group
of winners is paired as the parents for new individuals.
Elitism
It is a method where each individual is assigned a fitness value via the fitness function.

Using these scores, a percentage of the best, most fit individuals are used as parents.
To start, select individuals from the population as the parents.

Then, each member of the population after that is compared one by one to each of the parents.

If a member of the population is found to be more fit than an existing parent,

that parent is swapped out with that member.
This continues until all the members have been compared against the existing parents.
Then the original members of the population that were initially selected as parents are compared to the current set of parents to
ensure that the fittest individuals are chosen as parents and a more fit individual was not replaced prematurely.