poster

A multi-start quantum-inspired evolutionary algorithm for solving combinatorial optimization problems

Authors:

Parvaz Mahdabi,

Saeed Jalili,

Mahdi AbadiAuthors Info & Claims

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

Pages 613 - 614

https://doi.org/10.1145/1389095.1389218

Published: 12 July 2008 Publication History

Get Access

Abstract

Quantum-inspired evolutionary algorithms (QIEAs), as a subset of evolutionary computation, are based on the principles of quantum computing such as quantum bits and quantum superposition. In this paper, we propose a multi-start quantum-inspired evolutionary algorithm, called MSQIEA. To improve the performance of the algorithm, a multi-measurement operator and a new strategy for updating the rotation angle is proposed. When Q-bit individuals start to converge to their final states, the best solution is stored and all Q-bits in each Q-bit individual are reinitialized. We compare the effectiveness of MSQIEA with a popular quantum-inspired evolutionary algorithm, called QEA, for solving 0-1 knapsack problem. The experimental results show that MSQIEA outperforms QEA and finds a solution with higher profit.

References

[1]

Han, K.-H. and Kim, J.--H. 2002. Quantum-inspired evolutionary algorithm for a class of combinatorial optimization. IEEE T. Evolut. Comput. 6, 6 (Dec. 2002), 580--593.

Digital Library

Google Scholar

[2]

Han, K.-H. and Kim, J.-H. 2004. Quantum-inspired evolutionary algorithms with a new termination criterion, Hµ gate, and two-phase scheme. IEEE T. Evolut. Comput. 8, 2 (April 2004), 156--169.

Digital Library

Google Scholar

[3]

Zhang, G. and Rong, H. 2007. Real-observation quantum-inspired evolutionary algorithm for a class of numerical optimization Problems. In Proceedings of the International Conference on Computational Science (Beijing, China, May 27 -- 30, 2007). ICCS '07, LNCS 4490, 989--996.

Digital Library

Google Scholar

Cited By

View all

Bansal SPatvardhan C(2021)A Generalized Parallel Quantum Inspired Evolutionary Algorithm Framework for Hard Subset Selection ProblemsResearch Anthology on Advancements in Quantum Technology10.4018/978-1-7998-8593-1.ch003(51-92)Online publication date: 2021
https://doi.org/10.4018/978-1-7998-8593-1.ch003
Bansal SPatvardhan C(2019)A Generalized Parallel Quantum Inspired Evolutionary Algorithm Framework for Hard Subset Selection ProblemsInternational Journal of Applied Evolutionary Computation10.4018/IJAEC.201910010110:4(1-38)Online publication date: Oct-2019
https://doi.org/10.4018/IJAEC.2019100101
Patvardhan CBansal SSrivastav A(2017)Towards the right amount of randomness in quantum-inspired evolutionary algorithmsSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-015-1880-521:7(1765-1784)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1007/s00500-015-1880-5
Show More Cited By

Index Terms

A multi-start quantum-inspired evolutionary algorithm for solving combinatorial optimization problems
1. Computing methodologies
  1. Artificial intelligence
    1. Control methods
    2. Search methodologies
2. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques
      1. Dynamic programming

Recommendations

A novel quantum-inspired evolutionary algorithm for solving combinatorial optimization problems
GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation

In this paper, we propose a novel quantum-inspired evolutionary algorithm, called NQEA, for solving combinatorial optimization problems. NQEA uses a new Q-bit update operator to increase the balance between the exploration and exploitation of the search ...
Superior exploration-exploitation balance with quantum-inspired hadamard walks
GECCO '10: Proceedings of the 12th annual conference companion on Genetic and evolutionary computation

This paper extends the analogies employed in the development of quantum-inspired evolutionary algorithms by proposing quantum-inspired Hadamard walks, called QHW. A novel quantum-inspired evolutionary algorithm, called HQEA, for solving combinatorial ...
A quantum-inspired Tabu search algorithm for solving combinatorial optimization problems

In this study, we propose a novel quantum-inspired evolutionary algorithm (QEA), called quantum inspired Tabu search (QTS). QTS is based on the classical Tabu search and characteristics of quantum computation, such as superposition. The process of qubit ...

Comments

Information & Contributors

Information

Published In

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

July 2008

1814 pages

ISBN:9781605581309

DOI:10.1145/1389095

Conference Chair:
Conor Ryan
University of Limerick, Ireland
,
Editor:
Maarten Keijzer
Chordiant Software International B.V., The Netherlands

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Poster

Conference

GECCO08

Sponsor:

GECCO08: Genetic and Evolutionary Computation Conference

July 12 - 16, 2008

GA, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
208
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Bansal SPatvardhan C(2021)A Generalized Parallel Quantum Inspired Evolutionary Algorithm Framework for Hard Subset Selection ProblemsResearch Anthology on Advancements in Quantum Technology10.4018/978-1-7998-8593-1.ch003(51-92)Online publication date: 2021
https://doi.org/10.4018/978-1-7998-8593-1.ch003
Bansal SPatvardhan C(2019)A Generalized Parallel Quantum Inspired Evolutionary Algorithm Framework for Hard Subset Selection ProblemsInternational Journal of Applied Evolutionary Computation10.4018/IJAEC.201910010110:4(1-38)Online publication date: Oct-2019
https://doi.org/10.4018/IJAEC.2019100101
Patvardhan CBansal SSrivastav A(2017)Towards the right amount of randomness in quantum-inspired evolutionary algorithmsSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-015-1880-521:7(1765-1784)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1007/s00500-015-1880-5
Patvardhan CBansal SSrivastav A(2015)Quantum-Inspired Evolutionary Algorithm for difficult knapsack problemsMemetic Computing10.1007/s12293-015-0162-17:2(135-155)Online publication date: 21-Apr-2015
https://doi.org/10.1007/s12293-015-0162-1
Chao HChou YChen CChiu C(2012)Classical and quantum-inspired electromagnetism-like mechanism and its applicationsIET Control Theory & Applications10.1049/iet-cta.2011.03826:10(1424-1433)Online publication date: 5-Jul-2012
https://doi.org/10.1049/iet-cta.2011.0382
Montemanni RMahdabi P(2011)A Linear Programming-based Evolutionary Algorithm for the Minimum Power Broadcast Problem in Wireless Sensor NetworksJournal of Mathematical Modelling and Algorithms10.1007/s10852-010-9146-910:2(145-162)Online publication date: 1-Jun-2011
https://dl.acm.org/doi/10.1007/s10852-010-9146-9
Chang CChen CFan CChao HChou Y(2010)Quantum-Inspired Electromagnetism-Like Mechanism for Solving 0/1 Knapsack Problem2010 2nd International Conference on Information Technology Convergence and Services10.1109/ITCS.2010.5581278(1-6)Online publication date: Aug-2010
https://doi.org/10.1109/ITCS.2010.5581278
Yao-Hsin Chou Chih-Cheng Chang Chia-Hui Chiu Fang-Jhu Lin Yi-Jyuan Yang Zan-Ya Peng (2010)Classical and quantum-inspired electromagnetism-like mechanism for solving 0/1 knapsack problems2010 IEEE International Conference on Systems, Man and Cybernetics10.1109/ICSMC.2010.5642288(3211-3218)Online publication date: Oct-2010
https://doi.org/10.1109/ICSMC.2010.5642288
Mahdabi PAbadi MJalili SRothlauf F(2009)A novel quantum-inspired evolutionary algorithm for solving combinatorial optimization problemsProceedings of the 11th Annual conference on Genetic and evolutionary computation10.1145/1569901.1570172(1807-1808)Online publication date: 8-Jul-2009
https://dl.acm.org/doi/10.1145/1569901.1570172
de Pinho AVellasco Mda Cruz A(2009)A new model for credit approval problems: A quantum-inspired neuro-evolutionary algorithm with binary-real representation2009 World Congress on Nature & Biologically Inspired Computing (NaBIC)10.1109/NABIC.2009.5393327(445-450)Online publication date: Dec-2009
https://doi.org/10.1109/NABIC.2009.5393327

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

A novel quantum-inspired evolutionary algorithm for solving combinatorial optimization problems

Superior exploration-exploitation balance with quantum-inspired hadamard walks

A quantum-inspired Tabu search algorithm for solving combinatorial optimization problems

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations