Multiobjective Optimization in a Quantum Adiabatic Computer

被引:7
作者
Baran, Benjamin [1 ]
Villagra, Marcos [1 ]
机构
[1] Univ Nacl Asunci, NIDTEC, Campus Univ, San Lorenzo 2619, Paraguay
关键词
multiobjective optimization; quantum adiabatic computing; combinatorial optimization;
D O I
10.1016/j.entcs.2016.12.003
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
In this work we propose what we consider the first quantum algorithm for multiobjective combinatorial optimization, at least to the best of our knowledge. The proposed algorithm is based on the adiabatic algorithm of Farhi et al. and it is constructed by mapping a multiobjective combinatorial optimization problem into a Hamiltonian using a convex combination among objectives. We present mathematical properties of the eigenspectrum of the associated Hamiltonian and prove that the quantum adiabatic algorithm can find Pareto-optimal solutions provided certain convex combinations of objectives are used and the underlying multiobjective problem meets certain restrictions.
引用
收藏
页码:27 / 38
页数:12
相关论文
共 50 条
[41]   Multiobjective Optimization for Nurse Scheduling [J].
Yin, Peng-Yeng ;
Chao, Chih-Chiang ;
Chiang, Ya-Tzu .
ADVANCES IN SWARM INTELLIGENCE, PT II, 2011, 6729 :66-73
[42]   Multiobjective optimization based on reputation [J].
Jiang, Siwei ;
Zhang, Jie ;
Ong, Yew-Soon .
INFORMATION SCIENCES, 2014, 286 :125-146
[43]   Multiobjective optimization of a steering linkage [J].
Sleesongsom, S. ;
Bureerat, S. .
JOURNAL OF MECHANICAL SCIENCE AND TECHNOLOGY, 2016, 30 (08) :3681-3691
[44]   Multiobjective optimization of AMR systems [J].
Bouchekara, H. R. E. H. ;
Kedous-Lebouc, A. ;
Yonnet, J. P. ;
Chillet, C. .
INTERNATIONAL JOURNAL OF REFRIGERATION-REVUE INTERNATIONALE DU FROID, 2014, 37 :63-71
[45]   Covers and approximations in multiobjective optimization [J].
Daniel Vanderpooten ;
Lakmali Weerasena ;
Margaret M. Wiecek .
Journal of Global Optimization, 2017, 67 :601-619
[46]   Multiobjective variable mesh optimization [J].
Salgueiro, Yamisleydi ;
Toro, Jorge L. ;
Bello, Rafael ;
Falcon, Rafael .
ANNALS OF OPERATIONS RESEARCH, 2017, 258 (02) :869-893
[47]   Decomposition of a Multiobjective Optimization Problem into a Number of Simple Multiobjective Subproblems [J].
Liu, Hai-Lin ;
Gu, Fangqing ;
Zhang, Qingfu .
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2014, 18 (03) :450-455
[48]   On multiobjective optimization in portfolio management [J].
Ahmed, E ;
El-Alem, M .
APPLIED MATHEMATICS AND COMPUTATION, 2005, 167 (01) :616-621
[49]   Multiobjective optimization of combinatorial libraries [J].
D.K. Agrafiotis .
Molecular Diversity, 2000, 5 :209-230
[50]   Evolutionary Multiobjective Optimization of Winglets [J].
Teixeira, Mateus A. M. ;
Goulart, Fillipe ;
Campelo, Felipe .
GECCO'16: PROCEEDINGS OF THE 2016 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, 2016, :1021-1028