Skip to main content
main-content
Top

Hint

Swipe to navigate through the articles of this issue

01-06-2015 | Regular Research Paper | Issue 2/2015

Memetic Computing 2/2015

Quantum-Inspired Evolutionary Algorithm for difficult knapsack problems

Journal:
Memetic Computing > Issue 2/2015
Authors:
C. Patvardhan, Sulabh Bansal, Anand Srivastav

Abstract

Quantum Inspired Evolutionary Algorithms (QIEAs) are Evolutionary Algorithms which use concepts and principles of quantum computing. The 0/1 knapsack problem (KP) is a well known combinatorial optimization problem that has been typically used to validate the performance of QIEAs. However, there are some variants of KPs called difficult knapsack problems (DKPs) that are known to be more difficult to solve. QIEAs have not yet been fully explored for solving these. In this work, an improved QIEA, called QIEA-PSA is presented. A novel method to initialize the qubit individuals based on heuristic information for the KP instance and a method for size reduction for each new generation are introduced in the presented QIEA-PSA. Experiments are carried out for several types of DKPs that are much larger in size than those attempted hitherto. QIEA-PSA provides much better solutions than QIEA with much lesser computation times. Even a serial implementation of QIEA-PSA competes favorably on the same problem instances with a parallel implementation of an exact algorithm given recently in literature. A comparison is made which shows QIEA-PSA outperforms a recently applied population based search technique to solve benchmark KP instances. The ideas used for developing QIEA-PSA are general and may be utilized with advantage on other problems.

Please log in to get access to this content

To get access to this content you need the following product:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Maschinenbau + Werkstoffe​​​​​​​




Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb




Testen Sie jetzt 30 Tage kostenlos.

Literature
About this article

Other articles of this Issue 2/2015

Memetic Computing 2/2015 Go to the issue

Editorial

Editorial

Premium Partner

    Image Credits