A * algorithm is a searching algorithm that searches for the shortest path between the initial and the final state. f(n) =g(n) + h(n) g(n) = Actual cost from Start node to n node h(n) = Estimation Cost from n to Goal node.

A * algorithm is a searching algorithm that searches for the shortest path between the initial and the final state.
f(n) =g(n) + h(n)
g(n) = Actual cost from Start node to n node
h(n) = Estimation Cost from n to Goal node.
Time complexity = O(Node + Edges) = O(bd)
Space complexity = O(bd)

1. Intelligent Systems Course No. CS 6109 / CE 7205

2. Objective Complexity in Optimization Problems Solution Strategies for Optimization Problems Heuristic vs Metaheuristic Methods Metaheuristic Methods Search Techniques Hill Climbing Evolutionary Algorithms Genetic Algorithm (Phases of Genetic Algorithm)

3. Complexity in Optimization Problems Optimization problems of today are becoming increasingly Complex . Conventional methods consumes too much time to solve these problems. Some examples are: Airline Scheduling problems Financial Portfolio Models Electric Power and Gas Distribution Class Scheduling Problems Media Selection, Sales Territory Realignment Supply Chain Design in Multiple Industries Cutting Stock Problem in Paper, Metals and Clothing Industries.

4. Solution Strategies for Optimization Problems In heuristic and metaheuristic methods, we make a trade-off between solution quality and computational time. Solution quality is sometimes compromised to get a quick solution. Methods to Solve Optimization Problem Nature of Solution Linear or Non-Linear Programming Exact Solution Branch-and-Bound Exact Solution Heuristic Methods Inexact, Near-Optimal Solution Metaheuristic Methods Inexact, Near-Optimal Solution

5. Heuristic vs Metaheuristic Methods Heuristic Methods Metaheuristic Methods Nature Deterministic Randomization + Heuristic Type Algorithmic, Iterative Nature Inspired, Iterative Example Subtour Reversal or Nearest Neighborhood in Travelling Salesman Problems Genetic Algorithm for Traveling Salesman Problems Nature of Solution Inexact, Near-Optimal Solution Inexact, Near-Optimal Solution

6. Metaheuristic Methods Meta: A bove or Beyond; Heuristic: to find A metaheuristic : Guides a subordinate heuristic in an iterative manner are guided random search techniques explores and exploits the search space includes methods to avoid getting trapped in local optima uses search experience intelligently to guide further search. Finds Near-Optimal solutions .

7. Search Te chniques …….

8. Hill Climbing Start from a random point in the search space Identify all its neighboring points Move to the point with the best functional value Repeat last two steps till all neighboring points are of lower functional value. The peak is reached.

9. Hill Climbing What happens if we do hill climbing from a random point B rather then from A ? Do we reach the global maximum? Or are we going to reach the local maximum?

10. Hill Climbing Simulated Annealing is a variant of the hill climbing method However, it allows downhill moves as well Additionally, it explores the search space in such a manner that the starting point does not influence much the final solution.

11. Evolutionary Algorithms An evolutionary algorithm is an evolutionary AI-based computer application that solves problems by employing processes that mimic the behaviors of living things. As such, it uses mechanisms that are typically associated with biological evolution , such as reproduction , mutation and recombination .  Evolutionary algorithms function in a Darwinian -like natural selection process; the weakest solutions are eliminated while stronger , more viable options are retained and re-evaluated in the next evolution—with the goal being to arrive at optimal actions to achieve the desired outcomes.

12. Genetic Algorithm Genetic Algorithm – Holland 1975 Coding of a solution – Chromosome Fitness function – Related to objective function Generation of Initial population Selection of Parent chromosomes for Reproduction Crossover and Mutation to obtain offspring Stopping rules.

13. Genetic Algorithm Genetic Algorithm are intelligent search technique maintain a population of candidate solution for a given problem and search the solution space by applying variation operators . Nature Genetic Algorithm Environment Optimization Problem Individuals Feasible Solution Individual’s Adaptation Solution Quality Population Species Set of Feasible Solutions Selection, Recombination and Reproduction Variation Operators

14. What is Genetic Algorithm A genetic algorithm (or GA) is a search technique used in computing to find true or approximate solutions to optimization and search problems. Genetic algorithms are a particular class of evolutionary algorithms that use techniques inspired by evolutionary biology such as inheritance , mutation , selection , and crossover (also called recombination). Traditionally, solutions are represented in binary as strings of 0s and 1s , but other encodings are also possible.

15. What is Genetic Algorithm The evolution usually starts from a population of randomly generated individuals and happens in generations. In each generation, the fitness of every individual in the population is evaluated, multiple individuals are selected from the current population (based on their fitness ), and modified (recombined and possibly mutated ) to form a new population.

16. What is Genetic Algorithm The new population is then used in the next iteration of the algorithm. Commonly, the algorithm terminates when either a maximum number of generations has been produced , or a satisfactory fitness level has been reached for the population. If the algorithm has terminated due to a maximum number of generations, a satisfactory solution may or may not have been reached.

17. Benefits of GA Easy to understand and modular in structure – separate from application Supports multi-objective optimization Good for noisy environments Solution is obtained all the time – solution quality improves with additional knowledge gained Inherently parallel , easily distributed Easy to exploit previous or alternative solutions Flexible building blocks for hybrid applications.

18. Use Genetic Algorithm Alternate solution are too slow or overly complicated . Need an exploratory tool to examine new approaches Problem is similar to one that has already been successfully solved by using GA. Want to hybridize with an existing solution Benefits of the GA technology meet key problem requirements Near-optimal solution will suffice Adequate computational power is available The problem does converge to an optimal solution

19. Application of Genetic Algorithm Domain Signal Processing Application Types Control Gas pipeline, pole balancing, missile evasion, pursuit Deign Semiconductor layout, Aircraft Design, keyboard configuration, communication networks Scheduling Manufacturing, Facility Scheduling, Resource Allocation Robotics Trajectory Planning Machine Learning Designing Neural Networks, Improving classification algorithms, classifier systems Signal Processing Filter Design Game Playing Poker, Checker, Combinatorial Optimization Set covering, traveling salesman, routing, bin packing, graph coloring and partitioning

20. Phases of Genetic Algorithm Five phases are considered in genetic algorithm.

21. Chromosome Encoding Binary Encoding Real Encoding Permutation Encoding Value Encoding Tree Encoding ( Huffman encoding)

22. Phases of Genetic Algorithm Initial Population The process begins with a set of individuals which is called a Population . the problem you want to solve. An individual is characterized by a set of parameters (variables) known as Genes. Genes are joined into a string to form a Chromosome (solution).

23. Phases of Genetic Algorithm Fitness Function It determines how fit an individual is (the ability of an individual to compete with other individuals). It gives a fitness score to each individual. The probability that an individual will be selected for reproduction is based on its fitness score. Selection based on their fitness scores.

24. Phases of Genetic Algorithm Crossover For each pair, a crossover point is chosen at random from within the genes. For example, consider the crossover point to be 3 as shown in figure.

25. Mutation Some of the bits in the bit string can be flipped. Phases of Genetic Algorithm

26. Flowchart for GA Initialization Fitness Selection Crossover Mutation

27. Example 1 We toss a fair coin 60 times and get the following initial population : S1 = 1111 0101 01 S2 = 0111 0001 01 S3 = 1110 1101 01 S4 = 0100 0100 11 S5 = 1110 1111 01 S6 = 0100 1100 00

28. Example 1 Fitness is calculated on the basis of number of 1’s S1 = 1111 0101 01 f(S1)=7 S2 = 0111 0001 01 f(S2)=5 S3 = 1110 1101 01 f(S3)=7 S4 = 0100 0100 11 f(S4)=4 S5 = 1110 1111 01 f(S5)=8 S6 = 0100 1100 00 f(S6)=3 Total Fitness 34

29. Example 1 Selection is on the basis of highest number of 1’s. Chromosome having highest number of 1’s place first S1’ = 1110 1111 01 f(S1’) = 8 S2’ = 1111 0101 01 f(S2’) = 7 S3’ = 1110 1101 01 f(S3’) = 7 S4’ = 0111 0001 01 f(S4’) = 5 S5’ = 0100 0100 11 f(S5’) = 4 S6’ = 0100 1100 00 f(S6’) = 3

30. Example 1 Crossover Suppose that we decide to actually perform crossover only for couples (S1`, S2`) and (S5`, S6`). For each pair, we randomly extract a crossover point, for instance 2 for the first and 5 for the second . Pair 1 Pair 2

31. Example 1 Chromosomes after crossover: S1’’= 1111 0101 01 S2’’= 1110 1111 01 S3’’ = 1110 1101 01 S4’’ = 0111 0001 01 S5’’= 0100 0100 00 S6’’= 0100 1100 11

32. Example 1 Chromosomes after mutations:

33. Example 1 After mutation, recalculate the fitness.

34. Summary Meta-heuristic is a higher level of technique used to search solution of a complex problem/data that is too large to be completely sampled. Evolutionary Algorithm helps in finding optimal solution for a complex problem.

35. Query Regarding Lecture Email: [email protected]

36. Thanks Email: [email protected]