Search intensity versus search diversity: a false trade off?

Autor(es)

Linhares, Alexandre ^{[1, 2, 3]} ; Yanasse, Horacio Hideki ^[2]

Afiliação do(s) autor(es)

^[1] EBAPE FGV, BR-22257970 Rio De Janeiro - Brazil

^[2] LAC INPE, Brazilian Inst Space Res, BR-12227010 Sao Jose Dos Campos, SP - Brazil

^[3] Club Rome, CH-8001 Zurich - Switzerland

• Tipo de documento: Artigo Científico
• Fonte: APPLIED INTELLIGENCE; v. 32, n. 3, p. 279-291, JUN 2010.
• Citações Web of Science: 8

Resumo

An implicit tenet of modern search heuristics is that there is a mutually exclusive balance between two desirable goals: search diversity (or distribution), i.e., search through a maximum number of distinct areas, and, search intensity, i.e., a maximum search exploitation within each specific area. We claim that the hypothesis that these goals are mutually exclusive is false in parallel systems. We argue that it is possible to devise methods that exhibit high search intensity and high search diversity during the whole algorithmic execution. It is considered how distance metrics, i.e., functions for measuring diversity (given by the minimum number of local search steps between two solutions) and coordination policies, i.e., mechanisms for directing and redirecting search processes based on the information acquired by the distance metrics, can be used together to integrate a framework for the development of advanced collective search methods that present such desiderata of search intensity and search diversity under simultaneous coexistence. The presented model also avoids the undesirable occurrence of a problem we refer to as the `ergometric bike phenomenon'. Finally, this work is one of the very few analysis accomplished on a level of meta-meta-heuristics, because all arguments are independent of specific problems handled (such as scheduling, planning, etc.), of specific solution methods (such as genetic algorithms, simulated annealing, tabu search, etc.) and of specific neighborhood or genetic operators (2-opt, crossover, etc.). (AU)

• Processo FAPESP: 97/12785-8 - Conexões entre o sequenciamento de padrões de corte e o layout de circuitos integrados
• Beneficiário: Alexandre Linhares
• Modalidade de apoio: Bolsas no Brasil - Doutorado