Tuning Tabu Search Strategies via Visual Diagnosis >mic2005



Yüklə 0,89 Mb.
tarix30.10.2018
ölçüsü0,89 Mb.
#76091


Tuning Tabu Search Strategies via Visual Diagnosis

  • >MIC2005<

  • 6th Metaheuristics International Conference

  • August 22-26, 2005. Vienna, Austria


Outline

  • Introduction (The Problem)

    • Metaheuristics Tuning Problem (illustrated using Tabu Search)
  • Visual Diagnosis Tuning (The Methodology)

    • Human + Computer
    • {Cause – Action – Outcome} tuple
  • V-MDF (Visualizer for MDF) (The Tool)

    • Distance Radar
    • V-MDF Architecture
    • Experimental Results
  • Questions & Answers



Introduction: Tuning Problem

  • Characteristics of a practical metaheuristic:

    • Delivers high quality solutions for any future instances.
    • Run in reasonable running time.
    • Can be developed within tight development time.
  • The need for a proper tuning.

  • Taxonomy of Tuning Problem:

    • Static versus Dynamic
    • Three levels of complexity
  • Tuning is complex… (illustrated using Tabu Search)



Tuning Tabu Search

  • Level-1 Tuning Problem (Static)

  • (Calibrating Parameter Values)

  • Setting the length of Tabu tenure:

    • By Guessing ??
    • By Trial and Error ??
    • By using past experience as a rough guide ??


Tuning Tabu Search

  • Level-2 Tuning Problem (Static)

  • (Choosing the best Configuration)

  • Choices of Local Neighborhood:

    • 2-opt ??
    • 3-opt ??
    • Very Large Scale Neighborhood (VLSN) ??
  • Choices of Tabu List:

    • Tabu moves ??
    • Tabu attributes ??
    • Tabu solutions ??


Tuning Tabu Search

  • Level-3 Tuning Problem (Dynamic)

  • (Tuning Search Strategies)

  • Choices of Search Strategies:

    • Intensification ??
    • Diversification ??
    • Hybridization ??
  • Example:

    • Reactive Tabu Search (Battiti & Tecchiolli, 1994)
  • When and How to apply these strategies ??



Conventional Solution

  • Tuning: bottleneck in rapid development process (Adenso-Diaz & Laguna, 2005)



Automated Tuning Methods

  • Tool to automatically and systematically search for the best:

  • Set of parameter values (level-1)

  • Configuration (level-2)

  • Pros:

  • Relieves the burden of tuning from human.

  • Cons:

  • Treat metaheuristic as a black box.

    • Does not provide room for innovations…
  • Difficult to address level-3 Tuning Problem (for Dynamic Metaheuristic)

  • Probably slow

    • if the number of possible configurations is high.
  • Examples:

  • CALIBRA (Adenso-Diaz & Laguna, 2005)

  • F-Race (Birattari, 2004)



Non-Automated Tuning Methods

  • Tool which allow human to diagnose the metaheuristic

  • Pros:

  • Make level-3 Tuning Problem for Dynamic Metaheuristic easier

  • Provide room for innovations

  • Cons:

  • Human still need to do the job…

  • Inconsistent results

  • Examples:

  • Statistical Analysis, e.g.:

    • Fitness Landscape Analysis (Fonlupt et al, 1997)
    • Fitness Distance Correlation Analysis (Merz, 2000)
  • Human-Guided Tabu Search (Klau et al, 2002)

  • Visualization of Search (Kadluczka et al, 2004)

  • V-MDF (This work)



Visual Diagnosis Tuning The methodology for solving Tuning Problem



Visual Diagnosis Tuning

  • Idea: Combine human intelligence and computer to produce good search strategies quickly.

  • Basic methodology of Visual Diagnosis Tuning:

    • {Cause-Action-Outcome} tuple:
      • Diagnose incidents in search trajectory. (Cause)
      • Steer the search if necessary. (Action)
      • Instantly observe the impact of the his action. (Outcome)
    • Example:
      • {passive searching – greedy random restart – arrive in good region}
        • Possibly an effective strategy
      • {solution cycling – decrease tabu tenure – solution cycling}
        • Possibly an ineffective strategy


V-MDF: Distance Radar

  • Diagnose incidents in search trajectory

    • Visualizing search trajectory is difficult!
      • Search space is large!
  • A special generic visualizer is needed: Distance Radar

    • Using the concept of “distance”
      • Example: Distance between two binary encoded solutions: hamming distance. A = 110010 B = 100011 Distance = 2 bit flips.


V-MDF: Distance Radar

  • Main ideas of Distance Radar:

    • Record elite solutions along the search trajectory.
      • Distance w.r.t Current solution
      • Recency w.r.t Current iteration
      • Objective Value w.r.t Current best objective value
    • Current solution  current position.
    • Elite solutions (Local Optimal)  anchor points.
    • Approximate Tabu Search trajectory with these information.


V-MDF: Radar A



V-MDF: Radar B



V-MDF: Distance Radar



V-MDF: Remedial Actions



V-MDF: Overall Architecture



Experiment using V-MDF

  • Task:

    • Tune a Tabu Search implementation for solving an NP-hard Military Transport Planning (MTP) problem.
  • Knowledge base of rules after training.

  • Poor rules are discarded…

  • Good rules form the final metaheuristic algorithm



Experiment using V-MDF

  • The results of a training instance (minimizing problem)



Experiment using V-MDF

  • Tabu Search results



Summary

  • The Tuning Problem. (The Problem)

    • Taxonomy of tuning problems:
      • Static vs Dynamic & 3 levels of complexity.
    • Current tuning methods:
      • Automated vs Non-automated
  • Visual Diagnosis Tuning (The Methodology)

    • {Cause-Action-Outcome}.
  • Visualizer for MDF (V-MDF) (The Tool)

    • Distance Radar and its usage.
    • Overview of V-MDF
    • Generic (not restricted to one problem).
    • Useful especially for new problems.


Questions & Answers Thank you for your attention 



Yüklə 0,89 Mb.

Dostları ilə paylaş:




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©genderi.org 2022
rəhbərliyinə müraciət

    Ana səhifə