Research Article
A Quantum Differential Evolutionary Algorithm for the Independent Set Problem
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 58 - Issue 14 |
| Published: November 2012 |
| Authors: Omar Kettani, Faycal Ramdani, Benaissa Tadili |
10.5120/9353-3685
|
Omar Kettani, Faycal Ramdani, Benaissa Tadili . A Quantum Differential Evolutionary Algorithm for the Independent Set Problem. International Journal of Computer Applications. 58, 14 (November 2012), 39-42. DOI=10.5120/9353-3685
@article{ 10.5120/9353-3685,
author = { Omar Kettani,Faycal Ramdani,Benaissa Tadili },
title = { A Quantum Differential Evolutionary Algorithm for the Independent Set Problem },
journal = { International Journal of Computer Applications },
year = { 2012 },
volume = { 58 },
number = { 14 },
pages = { 39-42 },
doi = { 10.5120/9353-3685 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2012
%A Omar Kettani
%A Faycal Ramdani
%A Benaissa Tadili
%T A Quantum Differential Evolutionary Algorithm for the Independent Set Problem%T
%J International Journal of Computer Applications
%V 58
%N 14
%P 39-42
%R 10.5120/9353-3685
%I Foundation of Computer Science (FCS), NY, USA
Abstract
The Independent Set problem consists to find a maximum cardinality subset of vertices of a given graph such that no two vertices are adjacent. In this paper, we propose a quantum evolutionary algorithm which uses a differential operator to update the quantum angles of the superposition state of Q-bits for solving this problem. Simulation results on some graph examples show that this approach is effective.
References
- M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the theory NP-completeness, San Francisco:Freeman (1979).
- R. Mosca, "Polynomial algorithms for the maximum stable set problem on particular classes of P5-free graphs,"Information Processing Letters,61, 1997, pp. 137-143.
- A. Brandstädt, C. T. Hoàng, V. B. Le, "Stability number of bull-and chair-free graphs revisited," Discrete Appl. Math. 131 (2003) 39–50.
- P. Benioff, The computer as a physical system: a microscopic quantum mechanical hamiltonian model of computers as represented by Turing machines, J. Stat. Phys. 22 (1980) 563–591.
- B. Jiao, X. Gu and G. Xu, "An Improved Quantum Differential Algorithm for Stochastic Flow Shop Scheduling Problem". In Proc. IEEE International Conference on Control and Automation 2009,pp. 1235-1240.
- A. Draa , S. Meshoul, H. Talbi and M. Batouche, "A Quantum-Inspired Differential Evolution Algorithm for Solving the N-Queens Problem". The International Arab Journal of Information Technology,Vol. 7, No. 1, 2010 pp. 21-27.
- K. H. Han, J. H. Kim, "Quantum-inspired evolutionary algorithm for a class of combinatorial optimization," IEEE Trans. Evolut. Comput. ,6(6) (2002) 580–593.
- Javidi and Saeed Mehrabi, "On Evolutionary Algorithms for Maximum Independent Set Problem" Journal of Artificial Intelligence: Theory and Application (Vol. 1-2010/Iss. 2), pp. 54-59.
- Giandomenico, M, et al. "A New Approach to the Stable Set Problem Based on Ellipsoids," Integer Programming andCombinatorial Optimization, Springer 2011, pp. 223-234.
- PM Pardalos, OA Prokopyev, S Busygin "continuous approaches for solving discrete optimization problems. " Handbook on modelling for discrete optimization, 2006 – Springer
- http://www. mathworks. com
- Grötzsch H. , "Ein Dreifarbensatz für dreikreisfreie Netz auf der Kugel," Z. Martin-Luther-Univ. , 1958.
- Herschel A. S. , Sir Wm. , "Hamilton's Icosian Game," Quart. J. Pure Applied Math.
- Petersen J. , Die Theorie der regulären Graphen, Acta Math. , 1891.
- Ramsey F. P. , On a problem of formal logic, Proc. London Math. Soc. , 1930.
Index Terms
Keywords