Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Efficiency of Different Encoding Schemes in Swarm Intelligence for Solving Discrete Assignment Problems: A Comparative Study
Blekinge Institute of Technology, Faculty of Computing, Department of Software Engineering.
2019 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

Background

Solving problems classified as either NP-complete or NP-hard has long been an active topic in the research community, and has brought about many new algorithms for approximating an optimal solution (basically the best possible solution). A fundamental aspect to consider when developing such an algorithm is how to represent the given solution. Finding the right encoding scheme is key for any algorithm to function as efficiently as possible. That being said, there appears to be a lack of research studies that offer a comprehensive comparison of these encoding schemes.

Objectives

This study sets out to provide an extensive comparative analysis of five already existing encoding schemes for a population-based meta-heuristic algorithm, with focus on two discrete combinatorial problems: the 1/0 knapsack problem and task scheduling problem. The most popular scheme of these will also be defined and determined by reviewing the literature.

Methods

The encoding schemes were implemented and incorporated into a recently proposed algorithm, known as the Coyote Optimization Algorithm. Their difference in performance were then compared through several experiments.On top of that, the popularity of said schemes were measured by their number of occurrences among a set of surveyed research studies (on the topic knapsack-problem).

Conclusions

When compared to the real-valued encoding scheme, we found that both qubits (smallest unit in quantum computing) and complex numbers were more efficient for solving the 1/0 knapsack problem, due to their broader search-space.Our chosen variant of the quantum-inspired encoding scheme contributed to a slightly better result than its complex-valued counterpart. The binary- and boolean encoding schemes worked great in conjunction with a repair function for the knapsack problem, to the extent that their produced solutions converged at a faster rate than the rest.Interestingly enough, the real-valued encoding scheme was by far the more popular choice of them all (as far as the knapsack problem is concerned), which we attribute to its generally simple and convenient implementation; and the fact that it has been around for longer. Finally, we saw that the matrix-based encoding scheme contributed to a faster convergence rate for approximate solutions to the task scheduling problem when the hardware for each resource differed greatly in computing capacity. On the other hand, the SPV (small position value) decoder for both the real-valued and complex-valued encoding schemes were more advantageous when the resources had near to identical computing power, as it is more suitable for distributing tasks equally.

Place, publisher, year, edition, pages
2019.
National Category
Software Engineering Computer Sciences
Identifiers
URN: urn:nbn:se:bth-18588OAI: oai:DiVA.org:bth-18588DiVA, id: diva2:1350992
Subject / course
PA1445 Kandidatkurs i Programvaruteknik
Educational program
PAGIP International Software Engineering
Supervisors
Examiners
Available from: 2019-09-19 Created: 2019-09-12 Last updated: 2019-09-20Bibliographically approved

Open Access in DiVA

BTH2019Pettersson(462 kB)17 downloads
File information
File name FULLTEXT01.pdfFile size 462 kBChecksum SHA-512
0e1be93f20b83761701356f48cf80245debbaa329af1ede897e36abfebcb032b38f6e929751aed8865d0bdd008a3ed69a3f39c6ef3519515472a09cd8edca51a
Type fulltextMimetype application/pdf

By organisation
Department of Software Engineering
Software EngineeringComputer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 17 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 34 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf