8.1 Search Algorithms, Representation, Fitness and Fitness Landscape Flashcards
NP-Hard Problems -Recap
❑It is a class of problems that can not be solved in the ‘traditional’ way
❑Typically these problems:
❑Have a “best known” computational complexity in exponential time, e.g.O(n) = 2n
❑E.g. 21=2, 210=1024, 295= 39,614,081,257,132,168,796,771,975,168
❑They have no direct analytical solution
❑Thus, we may have to approximate a solution to them
Definition of a Search Problem
❑For some problems, we need to search for a solution from a (usually) very large number of possibilities
❑Search problems, i.e. searching for the answer in some solution space
❑The solution spaces for many everyday problems can be very, very large, too large to search exhaustively
❑Search algorithms to guide the search…
❑The search algorithm may not find the optimal solution to the problem
❑It will give a good solution in reasonable time
❑We often need special search algorithms known as heuristics
What is a Heuristic?
❑A heuristic is a “rule of thumb” or some loose set of guidelines
❑That may find a solution (but not guaranteed)
❑E.g. getting out of a maze by keeping your hand against the maze wall
❑Usage of domain knowledge in the search process speeds up the search process
❑In Artificial Intelligence these are used to improve the performance of methods, in our case, search methods
❑Expert knowledge
❑Common sense
❑We will look into specific methods later..
Search Problems
❑Many problems can be thought of as searching through candidate solutions to find one that is optimal
❑Systematically search through potential solutions without considering all of them…
❑We need some way to evaluate the fitness of the candidate solutions
❑Optimal = the fittest = the best etc…
❑Need to compare solutions and see which of the solutions are better or worst…
❑Alsosome sense of the adjacency (similarity) of solutions (or neighbourhood)
Fitness
❑In order to search for a solution we must be able to compare potential solutions
❑E.g. Is solution s1 better than solution s2?
❑Thus we have the concept of fitness
❑We must derive a function (the fitness / objective function) that maps a solution to a value that rates how good the solution solves the problem in hand
❑We either try and maximiseor minimisethe fitness
❑A slight change in solution quality should result in a corresponding change in the fitness
❑Solution quality goes down →Fitness goes down (decreases)
❑Solution quality goes up →Fitness goes up (increases
Representation
❑When we are trying to solve a search-based problem we need a way to represent a potential solution
❑This is usually a mathematical and/or data structure-based way of describing the solution to a problem
❑A good representation:
❑There should be a one-to-one mapping
❑No redundancy
❑No ambiguities
❑All potential solutions should be represented
