The Gestalt heuristic: Emerging abstraction to improve combinatorial search

Nowadays, many engineering applications require the minimization of a cost function such as decreasing the delivery time or the used space, reducing the development effort, and so on. Not surprisingly, research in optimization is one of the most active fields of computer science. Metaheuristics are part of the state-of-the-art techniques for combinatorial optimization. But their success comes at the price of considerable efforts in design and development time. Can we go further and automate their preparation? Especially when time is limited, dedicated techniques are unknown or the tackled problem is not well understood? The Gestalt heuristic, a search based on meta-modeling, answers those questions. Our approach, inspired by Gestalt psychology, considers the problem representation as a key factor of the success of the metaheuristic search process. Thanks to the emergence of such representation abstraction, the metaheuristic is being assisted by constraining the search. This abstraction is mainly based on the aggregation of the representation variables. The metaheuristic operators then work with these new aggregates. By learning, the Gestalt heuristic continuously searches for the right level of abstraction. It turns out to be an engineering mechanism very much related with the intrinsic emergence concept. First, the paper introduces the approach in the practical context of combinatorial optimization. It describes one possible implementation with evolutionary algorithms. Then, several experimental studies and results are presented and discussed in order to test the suggested Gestalt heuristic implementation and its main characteristics. Finally, the heuristic is more conceptually discussed in the context of emergence. © Springer Science+Business Media B.V. 2011.SCOPUS: cp.j