his.sePublications
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
Optimal Computing Budget Allocation for Noisy Hypervolume-Based Multi-Objective Evolutionary Optimization
Karlsruhe Institute of Technology, Tyskland. (Institut für Angewandte Informatik und Formale Beschreibungsverfahren (AIFB), Effiziente Algorithmen)
2011 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

In recent years more and more studies have been published that use the hypervolume asa component of multi-objective evolutionary algorithms. Previously the hypervolume wasused as a metric to measure the quality of the result of evolutionary optimization. Recentlyseveral hypervolume-based evolutionary algorithms have been established that show goodperformance. They use hypervolume-fitness to measure the value of individual solutions.The reason for the popularity of hypervolume-based fitness assessment is its capabilityto cope with high-dimensional objective spaces. Conventional Pareto-dominance-basedmulti-objective evolutionary optimization suffers from major performance degradationwhen problems with more than three objectives are optimized. This is due to the fact thatin high-dimensional objective spaces almost all solutions are mutually non-dominating andselection based on Pareto-dominance is not effective. For optimization problems that areaffected by “noise”, as for example real-world simulation problems, the objective functionhas to be evaluated several times to measure the expected objective function values of asolution. Since functions of real-world problems often are computationally expensiveand since the optimization time is limited the available function evaluations have tobe distributed efficiently between the individual solutions. Many sampling algorithmsfor this purpose have been published. The goal of this thesis is to formulate samplingalgorithms that allocate the available function evaluations to the solutions based on theirhypervolume-fitness values and to integrate the sampling algorithms into hypervolume-based evolutionary algorithms. Challenges that arise in this context are the estimationof the variance of hypervolume-fitness values and the sampling of solutions that appearto have a low fitness value according to their sample mean and which without furthersampling cannot escape from this situation. Another challenge is the high computationalcomplexity of hypervolume-fitness values. In high-dimensional scenarios the fitness valueshave to be estimated by approximation algorithms. As a result of this thesis it canbe stated that accurate hypervolume-variance estimation is hard to achieve and thatsampling algorithms which use auxiliary variance values and which determine the samplingbudget only approximatively show best overall performance if they are used together withadvanced hypervolume-based evolutionary algorithms.

Place, publisher, year, edition, pages
2011. , 88 p.
Keyword [en]
evolutionary optimization, multi-objective, noise, hypervolume, sampling
National Category
Computer Science
Identifiers
URN: urn:nbn:se:his:diva-7261OAI: oai:DiVA.org:his-7261DiVA: diva2:606319
Subject / course
Computer Science
Educational program
Informatics - Master's Programme
Uppsok
Technology
Supervisors
Examiners
Available from: 2013-03-05 Created: 2013-02-19 Last updated: 2013-03-05Bibliographically approved

Open Access in DiVA

No full text

Computer Science

Search outside of DiVA

GoogleGoogle Scholar

Total: 24 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