Plenary Lecture
Quantum-Inspired Multi-Objective Evolutionary Algorithms for Decision Making: Analyzing the State-Of-The-Art
Associate Professor Jerzy Balicki
Faculty of Electronics, Telecommunications and Informatics
Gdańsk University of Technology
POLAND
E-mail: balicki@eti.pg.gda.pl
Abstract: Over the past decade, multi-objective evolutionary algorithms have been the most commonly used meta-heuristic approaches for decision making support. However, they consume a lot of time to calculate the representative set of efficient solutions. To avoid this disadvantage, some improvements have been introduced.
Especially, some quantum-based algorithms seem to be very promising and prospective [2, 4]. However, there are not widely available quantum computers and the quantum-inspired algorithms are simulated on classical computers to achieve the quantum effect. In such a way quantum-inspired algorithms can be used for a computer decision aid, too [3, 6].
Kim J., Kim J.-H., and Han have been proposed probably the first quantum-inspired multiobjective evolutionary algorithm called QMEA for Multiobjective 0/1 Knapsack Problems in 2006 [5]. To improve the quality of the nondominated set as well as the diversity of population, QMEA develops some principles of quantum computing such as uncertainty, superposition, and interference. Experimental results show that QMEA finds solutions close to the Pareto-optimal front while maintaining a better spread of nondominated set.
QMEA is based on NSGA-II that is a strong elitist method with mechanisms to maintain diversity efficiently using nondominated sorting and crowding distance assignment. It is even more powerful if the elitism is further strengthened and the solutions are spread out by quantum mechanism.
Moreover, Talbi, Batouche, and Draao have been considered a Quantum-Inspired Evolutionary Algorithm QEA for multiobjective image segmentation [7].
Decision making by the AQMEA (Adaptive Quantum-based Multi-criterion Evolutionary Algorithm) has been considered for distributed computer systems, too [1]. Evolutionary computing with Q-bit chromosomes has been proofed to characterize by the enhanced population diversity than other representations, since individuals represent a linear superposition of states probabilistically.
In this paper, multi-criterion, evolutionary and quantum decision making supported by the Adaptive Quantum-based Multi-criterion Evolutionary Algorithm (AQMEA) has been considered. AQMEA has been developed to the task assignment problem and to underwater vehicle planning. Moreover, the other algorithms like QMEA and QEA have been discussed.
[1] Balicki J.: An Adaptive Quantum-based Multi-objective Evolutionary Algorithm for Efficient Task Assignment in Distributed Systems, Proc. of The WSEAS Int. Conf. on Computers, July 22-26, 2009, Rodos Island, Greece, WSEAS Press, pp. 417-422
[2] Deutsch, D.: Quantum Theory, the Church-Turing principle and the universal quantum computer, in Proceedings of the Royal Society of London A, vol. 400, 97-117 (1985)
[3] Dicarlo, L, et al.: Demonstration of two-qubit algorithms with a superconducting quantum processor. Nature, 460 (7252): 240–4, (2009)
[4] Han K.–H. and Kim J.–H., Genetic quantum algorithm and its application to combinatorial optimization problem, in Proc. Congress on Evolutionary Computation, vol. 2, La Jolla, CA, July 2000, 1354-1360 (2000)
[5] Kim, J., Kim, J.-H., and Han, K.-H.: Quantum-inspired Multiobjective Evolutionary Algorithm for Multiobjective 0/1 Knapsack Problems, IEEE Congress on Evolutionary Computation Vancouver, Canada, July 16-21, 9151-9156, (2006)
[6] Shor, P.: Algorithms for quantum computation: discrete logarithms and factoring, in Proc. 35th Annual Symposium on Foundations of Computer Science, IEEE Press, November (1994)
[7] Talbi, H., Batouche, M., Draao, A.:. A Quantum-Inspired Evolutionary Algorithm for Multiobjective Image Segmentation, International Journal of Mathematical, Physical and Engineering Sciences, Vol. 1, No. 2, 109-114, (2007)
Brief Biography of the Speaker: Jerzy M. Balicki is an associative professor at the Faculty of Electronics, Telecommunications and Informatics, Gdansk University of Technology 11/12 G. Narutowicza Street, 80-233 Gdańsk, Poland (e-mail: Balicki@eti.pg.gda.pl, http://www.eti.pg.gda.pl/katedry/kask/pracownicy/Jerzy.Balicki/). He received the M.Sc. and Ph.D. degrees in Computer Science from University of Military Technology, Warsaw, Poland in 1982 and 1987, respectively. Then, he achieved habilitation D.Sc. from Technical University of Poznan in 2001.He was as a university professor at Naval University of Gdynia from 2002 to 2010, and then at Gdansk University of Technology, Poland. He is an author of three books and more than 170 scientific papers related to artificial intelligence, distributed computer systems, quantum computations and decision support systems.