Packing equal disks in a unit square is a classical geometrical problem which arises in many industrial and scientific fields. Finding optimal solutions has been proved to be NP-hard, therefore, only local optimal solutions can be identified. We tackle this problem by means of the optimization Immune Algorithm (optIA), which has been proved to be among the best derivative-free optimization algorithms. In particular, OPTIA is used to pack up to 150 disks in a unit square. Experimental results show that the immune algorithm is able to locate the putative global optimum for all the instances. Moreover, a comparison with the Covariance Matrix Adaptation Evolution Strategy (CMA-ES) shows that OPTIA is more robust.

Packing equal disks in a unit square: an immunological optimization approach

V. Cutello;PAVONE, MARIO FRANCESCO
;
NICOSIA, GIUSEPPE
2015-01-01

Abstract

Packing equal disks in a unit square is a classical geometrical problem which arises in many industrial and scientific fields. Finding optimal solutions has been proved to be NP-hard, therefore, only local optimal solutions can be identified. We tackle this problem by means of the optimization Immune Algorithm (optIA), which has been proved to be among the best derivative-free optimization algorithms. In particular, OPTIA is used to pack up to 150 disks in a unit square. Experimental results show that the immune algorithm is able to locate the putative global optimum for all the instances. Moreover, a comparison with the Covariance Matrix Adaptation Evolution Strategy (CMA-ES) shows that OPTIA is more robust.
2015
978-1-5090-0298-6
Immune system; Optimization; square disk packing
File in questo prodotto:
File Dimensione Formato  
pavone-icsi3-2015.pdf

solo gestori archivio

Tipologia: Versione Editoriale (PDF)
Dimensione 215.66 kB
Formato Adobe PDF
215.66 kB Adobe PDF   Visualizza/Apri

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: https://hdl.handle.net/20.500.11769/71416
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? ND
social impact