Quantum genetic optimization

被引：100

作者：

Malossini, Andrea ^{[1
]}

Blanzieri, Enrico ^{[1
]}

Calarco, Tommaso ^{[2
,3
,4
]}

机构：

[1] Univ Trent, Dept Informat Commun Technol, I-38050 Trento, Italy

[2] INFM, Consiglio Nazl Ric, BEC, I-38050 Trento, Italy

[3] European Ctr Theoret Studies Nucl Phys & Relateda, I-38050 Trento, Italy

[4] Harvard Univ, Inst Theoret Atom Mol & Opt Phys, Cambridge, MA 02138 USA

来源：

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION | 2008年 / 12卷 / 02期

关键词：

evolutionary computing and genetic algorithms; quantum computation;

D O I：

10.1109/TEVC.2007.905006

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

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(N log N), 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.

引用

页码：231 / 241

页数：11

共 25 条

[1]

[Anonymous], P GEN EV COMP C GECC

[2]

[Anonymous], GENETIC ALGORITHMS Q

[3]

[Anonymous], 1998, QUANTUM THEORY CONCE

[4]

Aporntewan C, 2001, IEEE C EVOL COMPUTAT, P624, DOI 10.1109/CEC.2001.934449

[5] TELEPORTING AN UNKNOWN QUANTUM STATE VIA DUAL CLASSICAL AND EINSTEIN-PODOLSKY-ROSEN CHANNELS [J].

BENNETT, CH ;

BRASSARD, G ;

CREPEAU, C ;

JOZSA, R ;

PERES, A ;

WOOTTERS, WK .

PHYSICAL REVIEW LETTERS, 1993, 70 (13) :1895-1899

[6]

Boyer M, 1998, FORTSCHR PHYS, V46, P493, DOI 10.1002/(SICI)1521-3978(199806)46:4/5<493::AID-PROP493>3.0.CO

[7]

2-P

[8]

DEGARIS H, 2003, P 5 INT C EV SYST IC, P457

[9]

DEJONG KA, 1989, PROCEEDINGS OF THE THIRD INTERNATIONAL CONFERENCE ON GENETIC ALGORITHMS, P124

[10]

Durr C., 1996, QUANTUM ALGORITHM FI

← 1 2 3 →