Please enable JavaScript.

Coggle requires JavaScript to display documents.

Search Heuristics, Decision Theory - Coggle Diagram

- - - - For a given neighbourhood function N, a solution s is a local optimum if it has a better objective function value than all its neighbours
    - - Neighbourhoods for permutation problems
        
        Order-based
        
        k-Opt
        
        In the k-Opt move operator, k "edges" are removed from the permutation and replaced with k other "edges"
        
        Exchange operator
        
        Inversion operator
        
        Position-based
        
        Insertion operator
      - Single bit complementation
        
        Each neighbour is generated by complementing (changing 0 > 1 or 0 > 1) a single bit of s
        An n-dimensional binary vector will yield n neighbours.
    - - Compromise between size of the neighbourhood adopted and the computational complexity required to explore it...
        Large neighbourhoods may improve quality of solutions solutions obtained, but required additional computational time to generate and evaluate.
      - Search strategies
        
        Restricted problem
        
        If computation is too complicated, apply algorithm to a section of the problem at a time.
        
        Original problem
        
        Heuristic search in large neighbourhoods
        
        Variable depth
        
        Ejection chains
        
        Cyclic operator
        
        Exact search in large neighbourhoods
        
        Shortest path programming: Dynasearch
        
        Bipartite matching: Assignment
  - - - May cause a large number of metaheuristic iterations before convergence is observed. May be hard to achieve in highly restrictive problems. May be lead to diversity of final solutions.
    - - Use heuristic methods to methods to generate several solutions and select best. Very fast and easy to achieve. Not necessarily better than random generation. Premature convergence may result.
    - - An attempt to address trade-off between greedy algorithm and random generation.
  - - - Best improvement
        
        The best neighbour is selected. This means that the neighbourhood is generated exhaustively. This may be prohibitively time-consuming for large neighbourhoods, in which case neighbourhoods may be truncated.
      - First improvement
        
        The first improving neighbour encountered is selected from the neighbourhood. The neighbourhood is typically only considered partially, and this is done in an deterministic way.
      - Random selection
        
        An improving neighbour is randomly selected from the neighbourhood. This may be done very rapidly, but may result in in convergence to poor local optima or an excessive number of iterations.
    - - Easy to design and implement
      - Returns fairly good solutions very quickly
      - Typically converges to local optima that are not globally optimal
      - Very sensitive to choice of initial solution
      - Works well if there are not too many local optima in search space, or if relative qualities if local optima are similar
    - - Change landscape of the problem
        
        Change objective function of data input
        
        Use different neighbourhoods
      - Accept non-improving solutions
        
        Simulated annealing
        
        Algorithm
        see template
        
        Simulated annealing based on principles of statistical mechanics whereby an annealing process involves heating and then slowly cooling a material in a bid to maximise the strength of its crystalline molecular structure
        
        SA is an iterative, stochastic algorithm that occasionally allows for the worsening of a solution. It contains a mechanism to escape from local optima so as to delay premature convergence.
        
        SA is a memoryless algorithm.
        During each iteration, a random neighbouring solution s' of the current solution s is generated by applying a stochastic move operator
        
        Moves leading to an objective function improvement are always accepted.
        
        Moves leading to an objective function degradation of delta E are accepted with a probability that depends on the current temperature and the value of delta E
        
        Move acceptance
        
        The acceptance probability for worsening solutions is:
        
        As the algorithm progresses, the probability that such moves are accepted decreases so as to promote more diversification early in the search, and more intensification later.
        This is achieved by decreasing the temperature according to a cooling schedule as the search progresses.
        
        The cooling schedule involves keeping the temperature constant over a certain number of iterations (an epoch), until a temperature decreasing criterion, called the equilibrium condition is met.
        The temperature is decreased and held constant over the next epoch.
        
        This process is repeated until some search termination criterion is met.
        
        Escaping local optima
        
        The ease of escaping local optima depends on T and delta E.
        Probabilities of accepting worsening solutions decrease alongside the temperature.
        Large degradations should not be accepted too easily (smaller probability).
        
        Initial temperature choices
        
        Accept all
        
        The starting temperature is chosen high enough to accept all neighbours during the initial phase of the search. The main drawback is its high computational cost.
        
        Acceptance deviation
        
        The starting temperature is chosen so that the probability of accepting solutions which degrade the objective function by 3*sigma is P (sigma is determined as the SD of obj. functions value degradations experienced preliminary experiments in which all worsening solutions were accepted.
        
        Rule of thumb: P >= 80%
        
        Acceptance ratio
        
        The starting temperature is chosen so that the acceptance ratio of solutions is greater than some predetermined value a0.
        A rule of thumb is having a0 between 40% and 50%.
        
        Cooling schedule
        
        Epoch length
        
        Static paradigm
        
        The number of moves per temperature remains static during the search and is determined before the search starts.
        
        Adaptive paradigm
        
        Epoch length is determined by the search characteristics, for instance, terminating an epoch if a pre-determined nr of worsening moves have been accepted at that temperature.
        
        Popular cooling schedules
        
        Linear schedule
        Temperature is lowered at a linear rate by beta, the cooling parameter.
        T <- T - beta
        
        Geometric schedule
        T <- Tbeta
        
        Logarithmic schedule
        T i <- T0/log i
        
        Very slow cooling
        T <- T/(1+beta*T)
        
        Non-monotonic schedule
        Reheating is possible
        
        Adaptive schedules
        The cooling schedule is dynamic and depends on information gained during the search.
        
        Popular search termination criteria
        
        Reaching a final, predetermined low temperature
        
        Reaching a predetermined number of iterations without improvement of the best solution encountered
        
        Achieving a small number of move acceptances over a pre-specified successive number of epochs. (Use counter).
        
        Similar methods
        
        Threshold accepting algorithms
        
        Record-to-record algorithms
        
        Great deluge algorithms
        
        Demon algorithms
        
        Tabu search
        
        Working of algorithm
        see template
        
        Tabu search behaves like a local search, but will accept non-improving solutions to escape from local optima when all neighbours are non-improving.
        Usually, entire neighbourhood is searched deterministically. When a better neighbour is found, it replaces the current solution.
        When a local optimum is reached, the search carries on by selecting a neighbour worse than the current solution.
        The best solution in the neighbourhood is always selected as the new current solution, even if it does not improve upon the current solution.
        This approach may generate cycles... :(
        
        Avoiding cycles
        
        Neighbours that have been recently visited are ignored - for this reason, the short term trajectory is memorised.
        A short-term memory of the moves recently applied is maintained (the tabu list) and undoing the moves in this list is not allowed,
        Storing all the moves is time- and memory-consuming... so the tabu list is usually restricted to contain a pre-specified max. nr. of tabu moves.
        Acceptance criteria will allow the undoing of the moves on the tabu list, for instance if the move could improve on the incumbent.
        
        Types of memory
        
        Short-term memory
        
        Toe prevent cycling
        The tabu list of moves that may not be undone during the next iteration.
        
        Medium-term memory
        
        For intensification:
        The best solutions encountered during the search are stored. The idea is to give priority to attributes of the set of elite solutions, usually in a weighted probability manner.
        The search is based on these attributes.
        More info in slides & textbook
        
        Long-term memory
        
        For diversification:
        Information on visited solutions are stored. It is used to explore unvisited areas in the search space.
        More info in slides & textbook
        
        Tabu list size
        
        During each iteration, the last move is reflected in the list, whereas the oldest move is removed from the list
        The smaller the list, the more likely it is that cycling will occur
        Larger lists will cause many restrictions and encourage diversification of the search
        A compromise must be found that suits the fitness landscape structure of the problem instance
        
        Determining the size
        
        Static
        
        A static value is associated with the tabu list.
        It may depend on the size of the problem instance and the size of the neighbourhood. There is no optimal value and is determined empirically.
        
        Dynamic
        
        A variable size may be specified. The size changes during the search without using any information on the search history.
        
        Adaptive
        
        The tabu list size is updated based on the search history. For instance, being updated based on the search performance during previous iterations.
      - Iterate with different solutions
        
        Multistart local search
        
        A local search is launched k times, where k is a parameter. k initial solutions are generated beforehand - one for each of the local searches.
        (Successive initial solutions are chosen randomly and are thus unrelated to local optima encountered during the search).
        The best solution returned by these local searches (the incumbent) is recorded and updated as necessary as the searches progress.
        Upon termination of all k searches, the incumbent solution is returned
        Example
        
        Iterative local search, GRASP
        
        Iterative local search improves on local search by successively perturbing the local optima according to some perturbation method and taking this perturbation as the next initial solution if it satisfies some acceptance criterion,
        If perturbation is not accepted, another perturbation is performed. The process is repeated until some stopping criterion is met, e.g. max nr of perturbations have been performed
        
        Size of perturbation?
        
        A too small perturbation my generate cycles during the search (probability of exploring other basins my be low). Small perturbations may result in faster searches than large perturbations.
        
        A too large perturbation may erase the information about the search memory (rendering useless the good properties of good optima skipped).
        
        The optimal perturbation size depends on the fitness landscape and must not exceed the correlation length
        
        Perturbation size
        
        Static
        
        Size is fixed before starting the search.
        
        Dynamic
        
        Size is selected dynamically without taking into account the search history
        
        Adaptive
        
        Size is adapted during the search based on information about the fitness landscape and the search history.
        
        Acceptance criteria
        
        Intensification vs diversification
        
        The extreme in terms of intensification is to accept only improving solutions (better objective function values)
        The extreme in terms of diversification is to accept any solution without regard to its quality.
        
        Probabilistic criteria
        for instance, accepting all improving solutions, but worsening solutions only with some probability.
        
        Deterministic criteria
        For instance threshold testing - accepting any solution which is no worse by some margin than the local optimum of the previous search.
- - - - A set of initial candidate solutions (population) is required.
      - The algorithms work iteratively, applying a procedure to generate a new population during a generation phase of each iteration, and replacing the current population by some subset of the union of the current and new population during a replacement phase
        The process is repeated until some stopping criterion is met.
      - Elements of the history of the search stored in a memory are used during the generation & replacement phases.
      - See template
    - - Evolution-based
        
        Population members are selected and reproduction takes place using variation operators acting directly on solution representations.
      - Blackboard-based
        
        Population members participate in the construction of a shared memory. This is the main input when generating the new population of solutions.
    - - New solutions are selected from the union of the current population and the new generated population to replace the current population.
        This can involve selecting the entire generated population as the new population.
        Newer strategies combine the best solutions from the current and new populations to replace the current population.
  - - - Random generation
        
        Feasible population members are generated according to random distribution, independently.
      - Parallel diversification
        
        The search space is partitioned into regions, and feasible population members are generated in paralel within a subset of smaller regions.
      - Sequential diversification
        
        Feasible members are generated in sequence such that diversity is optimised.
      - Hybrid initialisation
        
        A combination of random, parallel & sequential
      - Heuristic initialisation
        
        A (meta)heuristic is repeatedly used to initialise the population.
  - - - The search termination criteria is decided a priori (for intance, a fixed number of iterations is performed.
    - - The search criteria is guided by the progress of the search ( for instance, looking at how many iterations pass without observing certain improvements.
  - - - Components
        
        Solution representation
        
        Population initialisation
        
        Objective function = fitness function
        
        Selection strategy - selecting parents to partake in reproduction
        
        Reproduction strategy - mutation and crossover operators to generate new candidate solutions
        
        Stopping criteria
        
        Replacement strategy - survival of the fittest to exist in the next generation
        
        See template
      - Selection strategies
        
        2 main classes
        
        Proportional fitness assignment
        
        Absolute fitness values are associated with individuals.
        
        roulette wheel selection
        
        stochastic universal sampling
        
        tournament selection
        
        Rank-based fitness assignment
        
        Relative fitness values are associated with individuals after having sorted individuals in ascending order of fitness
        
        rank-based selection
        
        Objective = to ensure that the fitter an individual, the higher its chance of being selected to fulfil the role of parent.
        This will drive the population towards fitter solutions over time.
        The worst solutions should still have some chance of being selected - this could lead to useful genetic material.
      - Reproduction operators
        
        Crossover operator
        (lecture 8 for more info)
        
        Binary operator which combines the genetic information of two parents to produce two offspring.
        2 characteristics should be satisfied: heritability (pure recombination / respectful / assorting) & validity
        Should exhibit elements of diversification & intensification
        
        Continuous crossover operators
        
        Intermediate crossover
        
        Geometric crossover
        
        Simplex crossover
        
        Simulated binary crossover
        
        Parent-centric crossover operator
        
        Binary crossover examples
        
        Uniform crossover
        
        1-point crossover
        
        2-point crossover
        
        Permutation crossover examples
        
        Order crossover
        
        Partially mapped crossover
        
        2-point crossover
        
        Mutation operator
        
        Unary operator which alters the composition of a single candidate solution at a time (to increase diversity of population.)
        Mutations are small changes made to a small selection of individuals
        Mutation operator must have 3 characteristics: ergodicity, validity, locality
      - Replacement strategies
        
        General replacement
        
        The offspring population replaces the entire parent population
        
        Steady-state replacement
        
        During each generation, only one offspring is generated and it replaces the worst individual of the parent population.
        
        Elitism
        
        Selecting the best individuals from combined parent and offspring populations, keeping population size constant - can lead to faster (but sometimes premature) convergence.
        Necessary to keep some poor solutions to maintain diversity.
- - - - choose action that results in largest reward in worst case scenario
    - - choose action that yields largest reward in best case scenario
    - - select action that yields largest expected reward
    - - choose action that minimises the largest regret/lost opportunity
- - - - Identify the most favourable outcome and the least favourable outcome.
        Then, for all other outcomes, ask decision maker for a probability such that the decision maker is indifferent between definitely receiving reward i and receiving the best outcome with that probability.
        Having these probabilities, reconstruct lotteries to consist only of best and worst outcomes.
        Lotteries are then ranked according to the probability of receiving the best outcome.
    - - Complete ordering
      - Continuity
      - Independence
      - Unequal probability
      - Compound lottery
  - - - The expected utility of a simple lottery is the sum of the probability of the reward * the utility of the reward
      - Lottery 1 is preferred to Lottery 2 if and only if the expected utility for lottery 1 is higher than that of lottery 2
      - The decision maker is indifferent between two lotteries only if their expected utilities are equal.
    - - a decision maker is...
        
        risk-averse if
        
        RP(L) > 0 for any nondegenerate (More than one outcome) lottery
        
        and only if u(x) is strictly concave, i.e. u''(x) < 0
        
        risk-neutral if
        
        RP(L) = 0
        
        u(x) is linear
        
        risk-seeking if
        
        RP(L) < 0
        
        u(x) is strictly convex, i.e. u''(x) > 0
    - - The certainty equivalent of a lottery L, written CE(L), is the value for which the decision maker is indifferent between the lottery and receiving a certain pay-off of CE(L).
    - - The risk premium of a lottery L, written RP(L), is defined as the difference between the expected value and certainty equivalent of the lottery
        RP(L) = EV(L) - CE(L)
    - - u(x) = 1 - exp(-x/R)
        R = risk tolerance
        measures how much risk a decision maker is willing to make.
        The smaller the risk tolerance, the more u(x) bends away from being linear (becomes more concave... more risk averse)
      - R is approximately the monetary value such that the decision maker is indifferent between:
        1) obtaining no payoff at all, and
        2) obtaining a payoff of R, or losing R/2, depending on the flip of a fair coin.
- - - - Attribute 1 is utility independent (ui) of attribute 2 if preferences for lotteries involving different levels of attribute 1 do not depend on the level of attribute 2.
    - - If attribute 1 is ui of attribute 2, and attribute 2 is ui of attribute 1, then they are mutually utlity independent
      - Attributes 1 & 2 are mui if and only if the decision maker's utility function u(x1,x2) is a multilinear function of the form:
        u(x1, x2) = k1.u1(x1) + k2.u2(x2) + k3.u1(x1).u2(x2)
    - - A decision maker's utility function exhibits additive independence if the decision maker is indifferent between:
        1) 50% chance of receiving either of the best outcomes & 50% chance of receiving either of the worst outcomes
        2) 50% chance of receiving any combination of the best and worst outcomes.
      - Additive independence implies that k3 = 0
      - u(x1, x2) = k1.u1(x1) + k2.u2(x2)
  - - - Pairwise comparison matrix
        
        A pairwise comparison matrix A is formed.
        Each entry a_ij denotes, on a scale from 1 to 9, how much more important objective i is than objective j
      - The weight vector
        
        For a less than consistent decision maker, w (the principal eigen vector of A) is estimated as w_max:
        1) For each of A's columns - divide each entry in column i by the sum of the entries in that column (column entries should now sum to 1)
        2) Estimate the i-the entry of w_max as the average of the entries in row i of the new, normalised matrix.
    - - 1) compute column vector AwT
      - 2) Compute 1/n (sum(i-th column entry/ i-th weight))
      - 3) calculate consistency index CI = ([2] - n)/(n-1)
      - 4) Find RI for n from table
      - 5) If CI/RI < 0.1, then the degree of consistency is satisfactory
    - - 1) Construct a pairwise comparison matrix for the alternatives against each other for a particular objective
      - 2) Use the method as before to estimate the weight vector associated with this matrix for the given objective
      - Repeat for each objective in turn