Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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
Effects of Different Worker Heuristics in Marriage in Honey Bees Optimization: As Applied to the Graph Coloring Problem
KTH, School of Electrical Engineering and Computer Science (EECS).
KTH, School of Electrical Engineering and Computer Science (EECS).
2018 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesisAlternative title
Effekter av olika arbetsheuristiker i Marriage In Honey Bees Optimization : Applicerat på Graffärgningsproblemet (Swedish)
Abstract [en]

Marriage in Honey Bees Optimization (MBO) is an interesting meta-heuristic inspired by the mating process of honey bees, where worker bees are collectively responsible for raising the next generation of the colony. In MBO, worker bees are represented by heuristics that are used to navigate the search space. This thesis investigates the effects of three worker heuristics in different combinations, in an implementation of MBO applied to the Graph Coloring Problem (GCP). GCP was chosen due to its application to real life problems, for instance scheduling. The worker heuristics included were a greedy algorithm, GREEDYRECOLOR, and the two tabu searches PARTIALCOL and TABUCOL. The different combinations were tested on known GCP benchmarks. MBO was found to utilize the strengths of each worker available where needed. Including GREEDYRECOLOR was not useful on average. PARTIALCOL was found to be the best overall worker. However, there were indications that using both PARTIALCOL and TABUCOL might be beneficial.

Abstract [sv]

Marriage in Honey Bees Optimization (MBO) är en intressant meta-heuristik inspirerad av honungsbiets parningsritual, där arbetsbin tillsammans är ansvariga för att föda upp kolonins nästa generation. I MBO representeras arbetsbin av heuristiker som används för att navigera ett problems lösningsrum. Denna uppsats undersöker effekterna av att använda tre heuristiker i olika kombinationer i en MBO applicerat på Graffärgningsproblemet (GCP). GCP valdes för dess applicerbarhet på verkliga problem, så som schemaläggning. Heuristikerna som användes var en girig algoritm, GREEDYRECOLOR, samt de två tabusökningsheuristikerna PARTIALCOL och TABUCOL. Alla olika kombinationer testades på kända probleminstanser av GCP. Resultaten visade att MBO använder sig av heuristikernas individuella styrkor. Att inkludera GREEDYRECOLOR var inte gångbart i genomsnitt. Den bästa heuristiken överlag visade sig vara PARTIALCOL. Dock fanns indikationer på att använda PARTIALCOL tillsammans med TABUCOL kan vara fördelaktigt.

Place, publisher, year, edition, pages
2018.
Series
TRITA-EECS-EX ; 2018:228
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-229681OAI: oai:DiVA.org:kth-229681DiVA, id: diva2:1213992
Subject / course
Computer Science
Educational program
Master of Science in Engineering - Computer Science and Technology
Supervisors
Examiners
Available from: 2018-08-03 Created: 2018-06-05 Last updated: 2018-08-03Bibliographically approved

Open Access in DiVA

fulltext(599 kB)4 downloads
File information
File name FULLTEXT01.pdfFile size 599 kBChecksum SHA-512
db2a0b10531da08afdc26976aba4632b1074bdc2c87e4de4d4c1b2c56c29684d0cfb254941806ca198e66c4c83fac9b304af9739c666c9adcd308b4ea81980a0
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Li, LisaVyth, Jakob
By organisation
School of Electrical Engineering and Computer Science (EECS)
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 4 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: 28 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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