[APDIO] Palestras do SEOOR - Centro ALGORITMI - UMinho (02.03.2012, 16h00)

[Cláudio Alves <claudio@dps.uminho.pt>]

Convidam-se os interessados a participar na próxima palestra do SEOOR - Grupo de Engenharia de  Sistemas, Optimização e Investigação Operacional do Centro de Investigação ALGORITMI da Universidade do Minho.

 

ORADOR:

Said Hanafi

Laboratoire d'Automatique, de Mécanique et d'Informatique Industrielles et Humaines

Université de Valenciennes et du Hainaut-Cambrèsis,

Le Mont Houy, 59313 Valenciennes Cedex France

 

TÍTULO: On the convergence of Tabu Search

 

DATA  : 2 de Março (6ªf), 16h00

LOCAL : Anfiteatro EEII.024 (Edifício da Escola de Engenharia - Gualtar)

 

RESUMO:

Many optimization techniques (both heuristic and exact) for solving combinatorial and nonlinear problems are iterative neighborhood search procedures, i.e., they start with an initial solution (feasible or infeasible) and repeatedly construct new solutions from current solutions by moves defined by reference to a neighborhood structure. The process continues to generate a trajectory of "neighboring solutions" until a certain stopping criterion is satisfied. The adaptive memory approach of Tabu Search (TS) generates a neighborhood trajectory by including a mechanism that forbids the search to revisit solutions already encountered, unless the intervening trajectory is modified (see Glover and Laguna, 1997).  The main goal of memory structures in TS is not simply to forbid cycling, however. In fact, the choice of a given neighborhood and a decision criterion for selecting moves with TS can force some solutions to be revisited before exploring other new ones.  Within this context, a proposal of Glover (1990) identifies a simple rule for revisiting solutions that is conjectured to have implications for finiteness in zero-one integer programming and optimal set membership problems. Hanafi (1998) proved Glover's conjecture under the assumption that the graph of the neighborhood space is connected and symmetric.

 

In this presentation, we provide new proofs that yield specific bounds establishing the finite convergence of tabu search, specifically for certain TS algorithms based on recency memory or frequency memory. Our results distinguish between symmetric and asymmetric neighborhood structures and provide insights into the sequences of solutions generated by the search. The outcomes disclose interesting contrasts between TS trajectories and those generated by the more rigid rules underlying tree search methods. Based on these findings, we also give designs for more efficient forms of convergent tabu search, and provide special rules that create a new type of tree search. This work is the first to provide explicit convergence bounds for methods based on such forms of memory.  The finiteness of these methods suggests an important distinction between their underlying ideas and the rationale that gives rise to "infinite time" convergence results for certain randomized procedures such as annealing.

-------

 

Saudações cordiais,

 

Cláudio Alves

DPS, EEng, UMinho