The complexity of the selection procedure of a genetic algorithm that requires reordering, if we restrict the class of the possible fitness functions to varying fitness functions, is O(NlogN), where N is the size of the population. The quantum genetic optimization algorithm (QGOA) exploits the power of quantum computation in order to speed up genetic procedures. In QGOA, the classical fitness evaluation and selection procedures are replaced by a single quantum procedure. While the quantum and classical genetic algorithms use the same number of generations, the QGOA requires fewer operations to identify the high-fitness subpopulation at each generation. We show that the complexity of our QGOA is O(1) in terms of number of oracle calls in the selection procedure. Such theoretical results are confirmed by the simulations of the algorithm.

Quantum genetic optimization / Malossini, Andrea; Blanzieri, Enrico; T., Calarco. - In: IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION. - ISSN 1089-778X. - STAMPA. - 12:2(2008), pp. 231-241. [10.1109/TEVC.2007.905006]

Quantum genetic optimization

Malossini, Andrea;Blanzieri, Enrico;
2008

Abstract

The complexity of the selection procedure of a genetic algorithm that requires reordering, if we restrict the class of the possible fitness functions to varying fitness functions, is O(NlogN), where N is the size of the population. The quantum genetic optimization algorithm (QGOA) exploits the power of quantum computation in order to speed up genetic procedures. In QGOA, the classical fitness evaluation and selection procedures are replaced by a single quantum procedure. While the quantum and classical genetic algorithms use the same number of generations, the QGOA requires fewer operations to identify the high-fitness subpopulation at each generation. We show that the complexity of our QGOA is O(1) in terms of number of oracle calls in the selection procedure. Such theoretical results are confirmed by the simulations of the algorithm.
2
Malossini, Andrea; Blanzieri, Enrico; T., Calarco
Quantum genetic optimization / Malossini, Andrea; Blanzieri, Enrico; T., Calarco. - In: IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION. - ISSN 1089-778X. - STAMPA. - 12:2(2008), pp. 231-241. [10.1109/TEVC.2007.905006]
File in questo prodotto:
File Dimensione Formato  
IEEEevolcomp2008.pdf

Solo gestori archivio

Tipologia: Post-print referato (Refereed author’s manuscript)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 709.65 kB
Formato Adobe PDF
709.65 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: http://hdl.handle.net/11572/69182
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 96
  • ???jsp.display-item.citation.isi??? 73
social impact