Stochastic Local Searches * performance depends strongly on parameters/tuning * tuning can be time-intensive * limited understanding of how performance depends on parameters (lots of experience required) * many algorithms leave important implementation choices to user

Stochastic Local Methods

• Simulated Annealing
• Tabu Search
• Iterated Local Search
• Evolutionary algorithms
• Ant Colony Optimization

Simulated Annealing

• Parameterized local search extension

• Features

  • Solution generation:

  • Acceptance criterion: better solutions always accepted, worse accepted with probability:

    ~exp((g(s)-g(s')) / T)

  • Annealing: slowly decrease T

• Parameters
  • Cooling schedule
  • Initial temperature T₀
  • Number of iterations at each iteration
  • Stopping criterion
• Use a 'cooling schedule' to converge on solution
• easy to implement
• good performance but long run time
• parallelizing:
  • coarse-grained: independent parallel runs
  • fine-grained: parallel evaluation of moves

Tabu Search

• Parameterized local search extension
• Short term and long term memory implementations
• Performs well even with just short term memory
• May require time-intensive fine-tuning
• Simple implementations using short term memory (store attributes of tl most recently visited solutions)
• Tries to avoid cycles in search using memory
• Don't necessarily move to solutions that are better than the current one
• Parameters
  • tl: tabu list length / tabu tenure: choice of this parameter critical for performance
  • Stopping criteria: all neighboring solutions are tabu | max iterations exceeded | number of iterations w/o improvement
  • Aspiration criteria: can override tabu status to help avoid marking previously unseen solutions as tabu
• Features:
  • Single trajectory
  • Memory: short/long term
  • Attributes: store specific attributes of solution rather than complete solution
  • Solutions which contain tabu attributes are forbidden
  • At each step move to best neighboring solution even if not better than the current one.
• Long term features:
  • Long term memory: often based on some measure of frequency (e.g. frequency of local search moves)
  • Intensification strategies: focus on search areas of search space by restarting around elite solutions or locking certain attributes.
  • Diversification strategies: move towards previously unexplored regions
• exponential run-time distributions (QAP)
• cooperative approaches [Crainic et al.]

Iterated Local Search

• Hybrid strategy
• build chain of local minima
• reduce search space to the space of local minima
• Some of best TSP solutions based on ILS
• Few parameters
• Easy to implement
• Highly effective
• Related to Variable Neighborhood Search
• Features:
  • Limited memory
  • Multiple neighborhoods
• Parameters
  • Initial solution
  • Solution modification: too strong (random restart), too weak (stuck in local minima). e.g. non-sequential 4-opt move (double-bridge move)
  • Acceptance criterion: strength of bias towards best found solutions. e.g. apply solution modification to best solutions since start of algorithm.
  • Local search technique: effectiveness vs. speed. 2-opt, 3-opt, Lin-Kernighan, Helsguan LK

Evolutionary algorithms

• Hybrid strategy
• Only discussed genetic algorithms
• Features
  • Population
  • Limited memory: e.g. passing of information from parents to children
  • Limited multiple neighborhoods
• Parameters/representation
  • Solution representation: binary vs. problem-specific
  • Fitness function
  • Mutation operator: background vs. driving search
  • Crossover operator: parent selection scheme, problem-specific vs. general purpose crossover, passing of information from parents to children
  • Stopping criteria: fixed number of generations, population convergence.
• fine-grained and coarse-grained parallelization implementations

Ant Colony Optimization

• Hybrid strategy
• Features
  • Population: multiple ants
  • Limited memory: pheromone trails left on edges
  • Solution construction: define solution components, ants construction solutions by iteratively adding components.
  • Pheromone evaporation
  • Probability of selecting solution component probabilistically based on utility(solution) * pheromone(transition)
• coarse-grained parallelization more successful than fine-grained
• Good performance demonstrated with protein-folding

Performance measurement

Two measures * search space ruggedness * linear correlation between solution fitness and distance to global optima (fitness-distance correlation)

Asymptotic behavior

• complete: for each problem instance P there is a time bound t_max(P) for the time required to find a solution
• probabilistic approximate completeness (PAC Property): for each soluble problem instance a solution is found with probability -> 1 as run-time -> inf.
• essential incompleteness: for some soluble problem instances, the probability for finding a solution is strictly smaller < 1 for run-time -> inf.

Cannot use t test: exponential, not normal distributions

Estimating optimum solutions qualities:

• use quasi-solutions (based on running stochastic alg. and making bold assumption), or use known solutions from running complete algorithms.

Applications

• SAT
• MAX-SAT
• TSP
• Scheduling
• Time-tabling
• Protein-folding