When dealing with extremely hard global optimization problems, i.e. problems with a large number of variables and a huge number of local optima, heuristic procedures are the only possible choice. In this situation, lacking any possibility of guaranteeing global optimality for most problem instances, it is quite difficult to establish rules for discriminating among different algorithms. We think that in order to judge the quality of new global optimization methods, different criteria might be adopted like, e.g.: 1. efficiency – measured in terms of the computational effort necessary to obtain the putative global optimum 2. robustness – measured in terms of “percentage of successes”, i.e. of the number of times the algorithm, re-started with different seeds or starting points, is able to end up at the putative global optimum 3. discovery capability – measured in terms of the possibility that an algorithm discovers, for the first time, a putative optimum for a given problem which is better than the best known up to now. Of course the third criterion cannot be considered as a compulsory one, as it might be the case that, for a given problem, the best known putative global optimum is indeed the global one, so that no algorithm will ever be able to discover a better one. In this paper we present a computational framework based on a population-based stochastic method in which different candidate solutions for a single problem are maintained in a population which evolves in such a way as to guarantee a sufficient diversity among solutions. This diversity enforcement is obtained through the definition of a dissimilarity measure whose definition is dependent on the specific problem class. We show in the paper that, for some well known and particularly hard test classes, the proposed method satisfies the above criteria, in that it is both much more efficient and robust when compared with other published approaches. Moreover, for the very hard problem of determining the minimum energy conformation of a cluster of particles which interact through short-range Morse potential, our approach was able to discover four new putative optima.

A population based approach for hard global optimization problems based on dissimilarity measures

GROSSO, Andrea Cesare;LOCATELLI, Marco;
2007

Abstract

When dealing with extremely hard global optimization problems, i.e. problems with a large number of variables and a huge number of local optima, heuristic procedures are the only possible choice. In this situation, lacking any possibility of guaranteeing global optimality for most problem instances, it is quite difficult to establish rules for discriminating among different algorithms. We think that in order to judge the quality of new global optimization methods, different criteria might be adopted like, e.g.: 1. efficiency – measured in terms of the computational effort necessary to obtain the putative global optimum 2. robustness – measured in terms of “percentage of successes”, i.e. of the number of times the algorithm, re-started with different seeds or starting points, is able to end up at the putative global optimum 3. discovery capability – measured in terms of the possibility that an algorithm discovers, for the first time, a putative optimum for a given problem which is better than the best known up to now. Of course the third criterion cannot be considered as a compulsory one, as it might be the case that, for a given problem, the best known putative global optimum is indeed the global one, so that no algorithm will ever be able to discover a better one. In this paper we present a computational framework based on a population-based stochastic method in which different candidate solutions for a single problem are maintained in a population which evolves in such a way as to guarantee a sufficient diversity among solutions. This diversity enforcement is obtained through the definition of a dissimilarity measure whose definition is dependent on the specific problem class. We show in the paper that, for some well known and particularly hard test classes, the proposed method satisfies the above criteria, in that it is both much more efficient and robust when compared with other published approaches. Moreover, for the very hard problem of determining the minimum energy conformation of a cluster of particles which interact through short-range Morse potential, our approach was able to discover four new putative optima.
110
373
404
A. GROSSO; M. LOCATELLI; F. SCHOEN
File in questo prodotto:
File Dimensione Formato  
MathProg2007.pdf

Accesso riservato

Tipo di file: POSTPRINT (VERSIONE FINALE DELL’AUTORE)
Dimensione 529.59 kB
Formato Adobe PDF
529.59 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2318/35608
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 55
  • ???jsp.display-item.citation.isi??? 47
social impact