Tuning Tabu Search Strategies via Visual Diagnosis >mic2005

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 