PPT On Tabu Search
Download
Tabu Search Presentation Transcript:
1.Tabu Search
2.INTRODUCTION
3.Background of TS
TS was first proposed by Glover (1986) and was also developed by Hansen (1986)
TS has its roots in methods that cross boundaries of feasibility and local optimality
Examples of such methods include use of surrogate constraints and cutting plane approaches
Tabu search (TS) is a neighborhood search method which employs "intelligent" search and flexible memory technique to avoid being trapped at local optimum.
Tabu Search (TS) is a metaheuristic that guides a local heuristic search procedure to explore the solution space beyond local optimality
4.Basic notions of TS
The word tabu (or taboo) comes from Tongan, a language of Polynesia, where it indicates things that cannot be touched because they are scared
Now it also means “a prohibition imposed by social custom”
In TS, tabu status of forbidden elements shift according to time and circumstance, based on an evolving memory
5.Basic notions of TS (cont.)
Tabu status can be overruled for a preferrable alternative
Hence TS uses adaptive (flexible) memory
TS also uses responsive exploration, i.e. exploitation of good solutions and exploration of new promising regions
6.PRINCIPAL TABU SEARCH FEATURES
Tabu search is based on the premise that problem solving, in order to qualify as intelligent, must incorporate adaptive memory and responsive exploration. The use of adaptive memory contrasts with "memoryless" designs, such as those inspired by metaphors of physics and biology, and with "rigid memory" designs, such as those exemplified by branch and bound and its AI-related cousins. The emphasis on responsive exploration (and hence purpose) in tabu search, whether in a deterministic or probabilistic implementation, derives from the supposition that a bad strategic choice can yield more information than a good random choice.
7.Main Features
TS emulates the human problem solving process.
It takes advantage of search history.
The historical record is usually maintained for the characteristics of the moves applied, rather than the solutions visited.
Recent moved are classified as tabus to restrict the search space.
TS is a variable neighborhood method.
Tabu restrictions are not inviolable under all circumstances.
Several types of memories are used, both short term and long term, in order to improve the exploration quality.
8.PRINCIPAL TABU SEARCH FEATURES (Contd…)Adaptive Memory
Selectivity (including strategic forgetting)
Abstraction and decomposition (through explicit and attributive memory)
Timing:
recency of events
frequency of events
differentiation between short term and long term
Quality and impact:
relative attractiveness of alternative choices
magnitude of changes in structure or constraining
relationships
Context:
regional interdependence
structural interdependence
sequential interdependence
9.PRINCIPAL TABU SEARCH FEATURES (Contd…)
Responsive Exploration
Strategically imposed restraints and inducements
(tabu conditions and aspiration levels)
Concentrated focus on good regions and good solution features
(intensification processes)
Characterizing and exploring promising new regions
(diversification processes)
Non-montonic search patterns
(strategic oscillation)
Integrating and extending solutions
(path relinking)
10.Parameters of Tabu Search:
Local search procedure
Neighborhood structure
Aspiration conditions
Form of tabu moves
Addition of a tabu move
Maximum size of tabu list
Stopping rule
Download
Tabu Search Presentation Transcript:
1.Tabu Search
2.INTRODUCTION
3.Background of TS
TS was first proposed by Glover (1986) and was also developed by Hansen (1986)
TS has its roots in methods that cross boundaries of feasibility and local optimality
Examples of such methods include use of surrogate constraints and cutting plane approaches
Tabu search (TS) is a neighborhood search method which employs "intelligent" search and flexible memory technique to avoid being trapped at local optimum.
Tabu Search (TS) is a metaheuristic that guides a local heuristic search procedure to explore the solution space beyond local optimality
4.Basic notions of TS
The word tabu (or taboo) comes from Tongan, a language of Polynesia, where it indicates things that cannot be touched because they are scared
Now it also means “a prohibition imposed by social custom”
In TS, tabu status of forbidden elements shift according to time and circumstance, based on an evolving memory
5.Basic notions of TS (cont.)
Tabu status can be overruled for a preferrable alternative
Hence TS uses adaptive (flexible) memory
TS also uses responsive exploration, i.e. exploitation of good solutions and exploration of new promising regions
6.PRINCIPAL TABU SEARCH FEATURES
Tabu search is based on the premise that problem solving, in order to qualify as intelligent, must incorporate adaptive memory and responsive exploration. The use of adaptive memory contrasts with "memoryless" designs, such as those inspired by metaphors of physics and biology, and with "rigid memory" designs, such as those exemplified by branch and bound and its AI-related cousins. The emphasis on responsive exploration (and hence purpose) in tabu search, whether in a deterministic or probabilistic implementation, derives from the supposition that a bad strategic choice can yield more information than a good random choice.
7.Main Features
TS emulates the human problem solving process.
It takes advantage of search history.
The historical record is usually maintained for the characteristics of the moves applied, rather than the solutions visited.
Recent moved are classified as tabus to restrict the search space.
TS is a variable neighborhood method.
Tabu restrictions are not inviolable under all circumstances.
Several types of memories are used, both short term and long term, in order to improve the exploration quality.
8.PRINCIPAL TABU SEARCH FEATURES (Contd…)Adaptive Memory
Selectivity (including strategic forgetting)
Abstraction and decomposition (through explicit and attributive memory)
Timing:
recency of events
frequency of events
differentiation between short term and long term
Quality and impact:
relative attractiveness of alternative choices
magnitude of changes in structure or constraining
relationships
Context:
regional interdependence
structural interdependence
sequential interdependence
9.PRINCIPAL TABU SEARCH FEATURES (Contd…)
Responsive Exploration
Strategically imposed restraints and inducements
(tabu conditions and aspiration levels)
Concentrated focus on good regions and good solution features
(intensification processes)
Characterizing and exploring promising new regions
(diversification processes)
Non-montonic search patterns
(strategic oscillation)
Integrating and extending solutions
(path relinking)
10.Parameters of Tabu Search:
Local search procedure
Neighborhood structure
Aspiration conditions
Form of tabu moves
Addition of a tabu move
Maximum size of tabu list
Stopping rule
No comments:
Post a Comment