Genetic Algorithm

Genetic algorithms emulate natural selection to solve optimization problems. They generate candidate solutions,
evaluate fitness, and evolve better solutions over generations.
Simple Genetic Algorithm

START

Mutation

NO
Converge Evaluate REPRODUCTION
? Fitness

SELECTION

YES
Select Crossover
STOP Mate

• Fitness Evaluation: Each solution (individual) is rated or scored based on how good it is at solving the
problem. This is like giving each individual a grade based on how well it works.
• Selection: Better solutions are more likely to be chosen for reproduction.
• Crossover: Selected solutions exchange information to create new solutions. This is like mixing traits between
parents to create offspring in biology.
1
 • Mutation: Random changes are introduced to maintain diversity in the population.

CONVERGENCE CRITERIA / TERMINATION STEP

❖ There is no one way to end the algorithm. The simplest approach is to run the search for a set number of
generations – the longer you can run it, the better.
❖ Another approach is to end the algorithm after a certain number of generations pass with no improvement in the
fitness of the best individual in the population

ENCODING SCHEMES
❖ Different coding schemes are used to represent individuals (the possible solutions) in numerical terms.
❖ One of the most used schemes is binary encoding, where the solution is converted in a string of 0s and 1s.
❖ Often times, an analogy is drawn between these numbers (bits, bytes, etc) with genes, chromosomes, etc.
❖ The set of all such encoded individuals forms a population. In general, the population is typically large.
❖ Each chromosome is a bit sequence of zeros and ones and is expressed by binary sequence. Every bit in this
array has a property of the solution.

Chromosome POPULATION
Gene

2
 ❖ This encoding is used in problems involving complex numbers such as real. Binary coding is very difficult for
such problems. Each chromosome is a sequence of values. These values are related to the problem; they can
be real numbers, characters, or complex objects.
❖ Tree encoding is often used to create programs and expressions in genetic programming. In tree coding,
each chromosome consists of a tree structure that includes objects and Inter-object operations. Tree
structure is used in languages such as Lisp and Prolog.

FITNESS & EVALUATION

Evaluation function Absolute measure of the individual.
Fitness function Value of individual relative to the rest of the population.
❖ The key is that the fitness of an individual should represent the value of the individual relative to the rest of the
population, so that the best individual has the highest fitness.
❖ The key to the selection process is that it should be probabilistically weighted so that higher fitness individuals
have a higher probability of being selected. Other than these specifications, the method of selection is open to
interpretation.

SELECTION

3
Chromosomes are chosen from within the population for crossover, to be parents. There are many ways to
choose the best chromosomes. Roulette wheel selection, tournament selection, ranking selection and
steady state selection are some of these.
Roulette Wheel Selection

• The fitness values of all individuals in the community are summed and the probability of each individual
being selected is the ratio of the fitness value to that total value.
• The pointer is fixed, and the wheel is given a roll. The region where the pointer points when the wheel stops
gives the selected individual.
• The better the chromosomes, the more likely they are to be selected. In this method, the highest fitness
value is not guaranteed to be selected but there is a greater chance of being selected.
• Roulette wheel selection can cause problems if the fitness values are very different. For example, if the
fitness value of the best chromosome is 90% of the roulette wheel, the chances of other chromosomes
being selected are lower.

Tournament Selection

A random sequence is selected from the entire generation at one time. They will be in the tournament. In a
tournament, whichever is better wins.

4
The random selection of chromosomes creates the possibility of co-selection of chromosomes with a low
fitness value. In this case, chromosomes can be selected for the next generation, which is better than the rest of
the population, even if they are mediocre. Thus, diversity in the population can be maintained.

Rank Selection

Here, all the individuals are given ranks in the opposite sense that is, the least fit is given the first rank and the
fittest is given the last rank. Now we find percentage based on the (rank/total) and plot a pie chart. This solves
the problem of dominance which occurs in Roulette Wheel.
CROSSOVER
❖ Single Point Crossover
➢ Two parents are randomly selected from the population, and genes from the start to a certain point
are swapped keeping all other genes the same, this way two new offsprings are created.

5
❖ Double Point Crossover
➢ Two parents are randomly selected from the population, and genes from the start to a certain point
are swapped keeping all other genes the same, this way two new offsprings are created.

❖ Multi-Point Crossover
➢ Two parents are randomly selected from the population, and genes between some ranges are
swapped keeping all other genes the same, this way two new offsprings are created.

6
MUTATION
❖ Mutation probability is a parameter in a genetic algorithm that determines the likelihood that an
individual will undergo the mutation process.
❖ For every gene we define a mutation probability, depending on which we change the values of the
chromosome, and bring about mutation accordingly.

7
Rapidly exploring Random Trees (RRT and RRT*)
Tree is a subset of a graph.
A graph could have several (>2) edges per vertex, but for a tree, there will be exactly 2 (or 1 if start or end) edges per vertex.
If there are more than two edges, then we select the one which gives the shortest path and ignore (eliminate) the other.

RRT
1. Focusses only on finding a path from start to end and not on finding the shortest path.
2. At any given point a new vertex is added. If the vertex is within the threshold range of any pre-existing node, then the
path between those two edges is constructed.
3. Every time a new vertex (node) is added, it checks the distance between every pre-existing node and the shortest path
is selected.
4. It keeps adding new nodes, until a new node coincides with the position of the goal (obviously considering the
threshold condition also).
5. Assume of course that the path does not cross an obstacle.

8
9
10
RRT*
Works mostly like RRT, but slightly different.
1. Instead of choosing the closest pre-existing node, it checks for all possible nodes in a particular radius.
2. While maintaining the tree structure, it sort of permutes and finds which nodes will form a shorter path overall rather than
just between the two nodes (new and closest).
3. It changes the pre-existing edges as well to optimize the path length.
4. The algorithm dynamically modifies the tree structure, altering pre-existing edges to create shortcuts and improve path
efficiency.

11
A* Algorithm
A* combines the advantages of Dijkstra's algorithm (which guarantees the shortest path) and greedy best-first search
(which is fast but may not always find the shortest path).

1. Heuristic Function:
• A key component of the A* algorithm is the heuristic function, denoted as (h(n)), which estimates the cost from
the current node to the goal node.
• The heuristic function helps guide the search towards the goal efficiently by providing an informed guess about
the cost to reach the goal.
• The heuristic function must satisfy the following properties:
• Admissibility:

(h(n)) must never overestimate the cost to reach the goal from node (n).

• Consistency (or monotonicity):

For every node (n) and its successor (n') with cost (c(n, n')), the heuristic satisfies (h(n) <= h(n') + c(n, n')).

Intuition about the Heuristic Function

12
 We think of the heuristic function as a guess made by our smart guide about how close you are to the exit based on
where you currently are in the maze. This guess helps guide your path towards the exit without blindly wandering
around.

• At one extreme, if h(n) is 0, then only g(n) plays a role, and A* turns into Dijkstra’s Algorithm, which is guaranteed to find
the shortest path.
• If h(n) is always lower than (or equal to) the cost of moving from n to the goal, then A* is guaranteed to find the shortest
path. The lower h(n) is, the more node A* expands, making it slower.
• If h(n) is exactly equal to the cost of moving from n to the goal, then A* will only follow the best path and never expand
anything else, making it very fast. Although you can’t make this happen in all cases, you can make it exact in some special
cases. It’s nice to know that given perfect information, A* will behave perfectly.
• If h(n) is sometimes greater than the cost of moving from n to the goal, then A* is not guaranteed to find the shortest path,
but it can run faster.
• At the other extreme, if h(n) is very high relative to g(n), then only h(n) plays a role, and A* turns into Greedy Best-First
Search.

2. A* Algorithm Procedure:

13
• Initialize open and closed lists. Start from the initial node.
• Calculate the (f(n)) value for each node, where (f(n) = g(n) + h(n)), (g(n)) is the cost from the start node to node
(n), and (h(n)) is the heuristic estimate from node (n) to the goal.
• Add the initial node to the open list.
• Repeat until the open list is empty or the goal node is reached:
• Select the node with the lowest (f(n)) value from the open list. This node becomes the current node.
• If the current node is the goal node, terminate the search.
• Otherwise, expand the current node by generating its successor nodes.
14
 • For each successor node:
• If it is not in the open list, calculate its (f(n)) value and add it to the open list.
• If it is already in the open list and has a lower (f(n)) value, update its (f(n)) value.
• Move the current node to the closed list.

3. Mathematical Understanding:
• Let (n) be a node in the graph.
• (g(n)) represents the actual cost from the start node to node (n).
• (h(n)) represents the estimated cost from node (n) to the goal node.
• (f(n) = g(n) + h(n)) represents the total estimated cost from the start node to the goal node passing through node
(n).
• A* selects the node with the lowest (f(n)) value at each iteration, ensuring optimality by considering both the
actual cost (g(n)) and the estimated cost (h(n)).

4. Example:
- Consider a grid-based map where each cell represents a node.

- The cost of moving from one cell to its neighbor is predefined.

- The heuristic function (h(n)) can be the Euclidean distance or Manhattan distance from node (n) to the goal node.
- A* algorithm will efficiently explore the grid, considering both the actual cost and the heuristic estimate to find the
shortest path from the start node to the goal node.

15
5. Applications:
- A* algorithm is widely used in various applications such as robotics, video games, route planning, and artificial
intelligence.
- It efficiently finds the shortest path in a graph while considering the estimated cost to reach the goal node, making it
suitable for real-time applications.

By following the principles of A* algorithm and utilizing an appropriate heuristic function, it becomes possible to
efficiently find the shortest path in various scenarios.

16
 TCP/IP
1. Transmission Control Protocol and Internet Protocol
2. Set of rules, which support network communication and ensure that data is transferred from and to the correct user.

Internet Receiver's TCP

Breaks messages Responsible for
Sender's TCP into packets and Join the packets to
transferring packets
sends it to IP Protocol retrieve the data.

3. Layered network—

17
APPLICATION LAYER
• The Application Layer is the topmost layer of the TCP/IP model and is responsible for providing network services
to user applications.
• Protocols operating at this layer include HTTP (Hypertext Transfer Protocol), FTP (File Transfer Protocol), SMTP
(Simple Mail Transfer Protocol), and DNS (Domain Name System).
• Handles high-level communication functions such as file transfer, email, and web browsing.
•
TRANSFER LAYER

18
 • The Transport Layer ensures reliable communication between devices by handling end-to-end delivery of data
packets. It provides services such as segmentation, error detection, flow control, and congestion control.
• TCP (Transmission Control Protocol) operates at this layer and offers connection-oriented communication with
guaranteed delivery and sequencing of data.
• UDP (User Datagram Protocol) is another protocol at this layer, offering connectionless communication with
minimal overhead.

INTERNET LAYER
• The Internet Layer is responsible for addressing and routing packets across interconnected networks. It handles
the logical addressing of devices and determines the best path for packet delivery.
• IPv4 and IPv6 are the main protocols used at this layer, providing unique IP addresses to devices and enabling
global communication over the Internet.
NETWORK LAYER
• The Link Layer deals with the physical transmission of data frames over the network medium. It defines protocols
and technologies for local network communication.
• Ethernet is the most common protocol at this layer, used for wired LANs, while Wi-Fi (IEEE 802.11) is used for
wireless communication.

19