Högskolan i Skövde

his.sePublications
Change search
Link to record
Permanent link

Direct link
Publications (10 of 13) Show all publications
Ng, A. H. C., Siegmund, F. & Deb, K. (2018). Reference point based evolutionary multi-objective optimization with dynamic resampling for production systems improvement. Journal of Systems and Information Technology, 20(4), 489-512
Open this publication in new window or tab >>Reference point based evolutionary multi-objective optimization with dynamic resampling for production systems improvement
2018 (English)In: Journal of Systems and Information Technology, ISSN 1328-7265, E-ISSN 1758-8847, Vol. 20, no 4, p. 489-512Article in journal (Refereed) Published
Abstract [en]

Purpose

Stochastic simulation is a popular tool among practitioners and researchers alike for quantitative analysis of systems. Recent advancement in research on formulating production systems improvement problems into multi-objective optimizations has provided the possibility to predict the optimal trade-offs between improvement costs and system performance, before making the final decision for implementation. However, the fact that stochastic simulations rely on running a large number of replications to cope with the randomness and obtain some accurate statistical estimates of the system outputs, has posed a serious issue for using this kind of multi-objective optimization in practice, especially with complex models. Therefore, the purpose of this study is to investigate the performance enhancements of a reference point based evolutionary multi-objective optimization algorithm in practical production systems improvement problems, when combined with various dynamic re-sampling mechanisms.

Design/methodology/approach

Many algorithms consider the preferences of decision makers to converge to optimal trade-off solutions faster. There also exist advanced dynamic resampling procedures to avoid wasting a multitude of simulation replications to non-optimal solutions. However, very few attempts have been made to study the advantages of combining these two approaches to further enhance the performance of computationally expensive optimizations for complex production systems. Therefore, this paper proposes some combinations of preference-based guided search with dynamic resampling mechanisms into an evolutionary multi-objective optimization algorithm to lower both the computational cost in re-sampling and the total number of simulation evaluations.

Findings

This paper shows the performance enhancements of the reference-point based algorithm, R-NSGA-II, when augmented with three different dynamic resampling mechanisms with increasing degrees of statistical sophistication, namely, time-based, distance-rank and optimal computing buffer allocation, when applied to two real-world production system improvement studies. The results have shown that the more stochasticity that the simulation models exert, the more the statistically advanced dynamic resampling mechanisms could significantly enhance the performance of the optimization process.

Originality/value

Contributions of this paper include combining decision makers’ preferences and dynamic resampling procedures; performance evaluations on two real-world production system improvement studies and illustrating statistically advanced dynamic resampling mechanism is needed for noisy models.

Place, publisher, year, edition, pages
Emerald Group Publishing Limited, 2018
Keywords
Multi-criteria decision making, Multi-objective optimization, Dynamic resampling, Production systems improvement
National Category
Computer Sciences Production Engineering, Human Work Science and Ergonomics Probability Theory and Statistics
Research subject
Production and Automation Engineering; VF-KDO
Identifiers
urn:nbn:se:his:diva-22296 (URN)10.1108/jsit-10-2017-0084 (DOI)2-s2.0-85056197722 (Scopus ID)
Projects
Blixt-Sim
Funder
Knowledge Foundation
Note

This work was partially financed by the Knowledge Foundation (KKS), Sweden, through the Blixt-Sim project (2011-2014). The authors gratefully acknowledge their provision of research funding and thank the industrial partners, Volvo Car Corporation and AB Volvo, for their collaborative supports during the project.

Available from: 2023-02-22 Created: 2023-02-22 Last updated: 2023-02-23Bibliographically approved
Siegmund, F., Ng, A. H. C. & Deb, K. (2017). A Comparative Study of Fast Adaptive Preference-Guided Evolutionary Multi-objective Optimization. In: Heike Trautmann, Rudolph Günter, Kathrin Klamroth, Oliver Schütze, Margaret Wiecek, Yaochu Jin, and Christian Grimme (Ed.), Evolutionary Multi-Criterion Optimization: 9th International Conference, EMO 2017, Münster, Germany, March 19-22, 2017, Proceedings. Paper presented at 9th International Conference, EMO 2017, Münster, Germany, March 19-22, 2017 (pp. 560-574). Springer, 10173
Open this publication in new window or tab >>A Comparative Study of Fast Adaptive Preference-Guided Evolutionary Multi-objective Optimization
2017 (English)In: Evolutionary Multi-Criterion Optimization: 9th International Conference, EMO 2017, Münster, Germany, March 19-22, 2017, Proceedings / [ed] Heike Trautmann, Rudolph Günter, Kathrin Klamroth, Oliver Schütze, Margaret Wiecek, Yaochu Jin, and Christian Grimme, Springer, 2017, Vol. 10173, p. 560-574Conference paper, Published paper (Refereed)
Abstract [en]

In Simulation-based Evolutionary Multi-objective Optimization, the number of simulation runs is very limited, since the complex simulation models require long execution times. With the help of preference information, the optimization result can be improved by guiding the optimization towards relevant areas in the objective space with, for example, the Reference Point-based NSGA-II algorithm (R-NSGA-II). Since the Pareto-relation is the primary fitness function in R-NSGA-II, the algorithm focuses on exploring the objective space with high diversity. Only after the population has converged closeto the Pareto-front does the influence of the reference point distance as secondary fitness criterion increase and the algorithm converges towards the preferred area on the Pareto-front.In this paper, we propose a set of extensions of R-NSGA-II which adaptively control the algorithm behavior, in order to converge faster towards the reference point. The adaption can be based on criteria such as elapsed optimization time or the reference point distance, or a combination thereof. In order to evaluate the performance of the adaptive extensions of R-NSGA-II, a performance metric for reference point-based EMO algorithms is used, which is based on the Hypervolume measure called the Focused Hypervolume metric. It measures convergence and diversity of the population in the preferred area around the reference point. The results are evaluated on two benchmark problems ofdifferent complexity and a simplistic production line model.

Place, publisher, year, edition, pages
Springer, 2017
Series
Lecture Notes in Computer Science (LNCS), ISSN 0302-9743, E-ISSN 1611-3349 ; 10173
Keywords
Evolutionary multi-objective optimization, Guided search, Preference-guided EMO, Reference point, Decision support, Adaptive
National Category
Computer Sciences
Research subject
Production and Automation Engineering; INF201 Virtual Production Development
Identifiers
urn:nbn:se:his:diva-13448 (URN)10.1007/978-3-319-54157-0_38 (DOI)2-s2.0-85014258475 (Scopus ID)978-3-319-54156-3 (ISBN)978-3-319-54157-0 (ISBN)
Conference
9th International Conference, EMO 2017, Münster, Germany, March 19-22, 2017
Funder
Knowledge Foundation
Available from: 2017-03-24 Created: 2017-03-24 Last updated: 2019-01-24Bibliographically approved
Siegmund, F., Ng, A. H. C. & Deb, K. (2016). A Ranking and Selection Strategy for Preference-based Evolutionary Multi-objective Optimization of Variable-Noise Problems. In: 2016 IEEE Congress on Evolutionary Computation (CEC): . Paper presented at 2016 IEEE Congress on Evolutionary Computation (IEEE CEC) held as part of the IEEE World Congress on Computational Intelligence (IEEE WCC) 2016, 24-29 July 2016, Vancouver, Canada (pp. 3035-3044). IEEE conference proceedings
Open this publication in new window or tab >>A Ranking and Selection Strategy for Preference-based Evolutionary Multi-objective Optimization of Variable-Noise Problems
2016 (English)In: 2016 IEEE Congress on Evolutionary Computation (CEC), IEEE conference proceedings, 2016, p. 3035-3044Conference paper, Published paper (Refereed)
Abstract [en]

In simulation-based Evolutionary Multi-objective Optimization the number of simulation runs is very limited, since the complex simulation models require long execution times. With the help of preference information, the optimization result can be improved by guiding the optimization towards relevant areas in the objective space, for example with the R-NSGA-II algorithm [9], which uses a reference point specified by the decision maker. When stochastic systems are simulated, the uncertainty of the objective values might degrade the optimization performance. By sampling the solutions multiple times this uncertainty can be reduced. However, resampling methods reduce the overall number of evaluated solutions which potentially worsens the optimization result. In this article, a Dynamic Resampling strategy is proposed which identifies the solutions closest to the reference point which guides the population of the Evolutionary Algorithm. We apply a single-objective Ranking and Selection resampling algorithm in the selection step of R-NSGA-II, which considers the stochastic reference point distance and its variance to identify the best solutions. We propose and evaluate different ways to integrate the sampling allocation method into the Evolutionary Algorithm. On the one hand, the Dynamic Resampling algorithm is made adaptive to support the EA selection step, and it is customized to be used in the time-constrained optimization scenario. Furthermore, it is controlled by other resampling criteria, in the same way as other hybrid DR algorithms. On the other hand, R-NSGA-II is modified to rely more on the scalar reference point distance as fitness function. The results are evaluated on a benchmark problem with variable noise landscape.

Place, publisher, year, edition, pages
IEEE conference proceedings, 2016
Keywords
Evolutionary, multi-objective optimization, preference-based, guided search, reference point, dynamic resampling, budget allocation, ranking and selection, variable noise
National Category
Information Systems Robotics
Research subject
Technology; Natural sciences; Production and Automation Engineering
Identifiers
urn:nbn:se:his:diva-13161 (URN)10.1109/CEC.2016.7744173 (DOI)000390749103029 ()2-s2.0-85008255213 (Scopus ID)978-1-5090-0623-6 (ISBN)978-1-5090-0624-3 (ISBN)978-1-5090-0622-9 (ISBN)
Conference
2016 IEEE Congress on Evolutionary Computation (IEEE CEC) held as part of the IEEE World Congress on Computational Intelligence (IEEE WCC) 2016, 24-29 July 2016, Vancouver, Canada
Funder
Knowledge Foundation
Available from: 2016-11-30 Created: 2016-11-30 Last updated: 2018-03-28Bibliographically approved
Siegmund, F. (2016). Dynamic Resampling for Preference-based Evolutionary Multi-objective Optimization of Stochastic Systems: Improving the efficiency of time-constrained optimization. (Doctoral dissertation). Skövde: Högskolan i Skövde
Open this publication in new window or tab >>Dynamic Resampling for Preference-based Evolutionary Multi-objective Optimization of Stochastic Systems: Improving the efficiency of time-constrained optimization
2016 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

In preference-based Evolutionary Multi-objective Optimization (EMO), the decision maker is looking for a diverse, but locally focused non-dominated front in a preferred area of the objective space, as close as possible to the true Pareto-front. Since solutions found outside the area of interest are considered less important or even irrelevant, the optimization can focus its efforts on the preferred area and find the solutions that the decision maker is looking for more quickly, i.e., with fewer simulation runs. This is particularly important if the available time for optimization is limited, as is the case in many real-world applications. Although previous studies in using this kind of guided-search with preference information, for example, withthe R-NSGA-II algorithm, have shown positive results, only very few of them considered the stochastic outputs of simulated systems.

In the literature, this phenomenon of stochastic evaluation functions is sometimes called noisy optimization. If an EMO algorithm is run without any countermeasure to noisy evaluation functions, the performance will deteriorate, compared to the case if the true mean objective values are known. While, in general, static resampling of solutions to reduce the uncertainty of all evaluated design solutions can allow EMO algorithms to avoid this problem, it will significantly increase the required simulation time/budget, as many samples will be wasted on candidate solutions which are inferior. In comparison, a Dynamic Resampling (DR) strategy can allow the exploration and exploitation trade-off to be optimized, since the required accuracy about objective values varies between solutions. In a dense, converged population, itis important to know the accurate objective values, whereas noisy objective values are less harmful when an algorithm is exploring the objective space, especially early in the optimization process. Therefore, a well-designed Dynamic Resampling strategy which resamples the solution carefully, according to the resampling need, can help an EMO algorithm achieve better results than a static resampling allocation.

While there are abundant studies in Simulation-based Optimization that considered Dynamic Resampling, the survey done in this study has found that there is no related work that considered how combinations of Dynamic Resampling and preference-based guided search can further enhance the performance of EMO algorithms, especially if the problems under study involve computationally expensive evaluations, like production systems simulation. The aim of this thesis is therefore to study, design and then to compare new combinations of preference-based EMO algorithms with various DR strategies, in order to improve the solution quality found by simulation-based multi-objective optimization with stochastic outputs, under a limited function evaluation or simulation budget. Specifically, based on the advantages and flexibility offered by interactive, reference point-based approaches, studies of the performance enhancements of R-NSGA-II when augmented with various DR strategies, with increasing degrees of statistical sophistication, as well as several adaptive features in terms of optimization parameters, have been made. The research results have clearly shown that optimization results can be improved, if a hybrid DR strategy is used and adaptive algorithm parameters are chosen according to the noise level and problem complexity. In the case of a limited simulation budget, the results allow the conclusions that both decision maker preferences and DR should be used at the same time to achieve the best results in simulation-based multi-objective optimization.

Abstract [sv]

Vid preferensbaserad evolutionär flermålsoptimering försöker beslutsfattaren hitta lösningar som är fokuserade kring ett valt preferensområde i målrymden och som ligger så nära den optimala Pareto-fronten som möjligt. Eftersom lösningar utanför preferensområdet anses som mindre intressanta, eller till och med oviktiga, kan optimeringen fokusera på den intressanta delen av målrymden och hitta relevanta lösningar snabbare, vilket betyder att färre lösningar behöver utvärderas. Detta är en stor fördel vid simuleringsbaserad flermålsoptimering med långa simuleringstider eftersom antalet olika konfigurationer som kan simuleras och utvärderas är mycket begränsat. Även tidigare studier som använt fokuserad flermålsoptimering styrd av användarpreferenser, t.ex. med algoritmen R-NSGA-II, har visat positiva resultat men enbart få av dessa har tagit hänsyn till det stokastiska beteendet hos de simulerade systemen.

I litteraturen kallas optimering med stokastiska utvärderingsfunktioner ibland "noisy optimization". Om en optimeringsalgoritm inte tar hänsyn till att de utvärderade målvärdena är stokastiska kommer prestandan vara lägre jämfört med om optimeringsalgoritmen har tillgång till de verkliga målvärdena. Statisk upprepad utvärdering av lösningar med syftet att reducera osäkerheten hos alla evaluerade lösningar hjälper optimeringsalgoritmer att undvika problemet, men leder samtidigt till en betydande ökning av antalet nödvändiga simuleringar och därigenom en ökning av optimeringstiden. Detta är problematiskt eftersom det innebär att många simuleringar utförs i onödan på undermåliga lösningar, där exakta målvärden inte bidrar till att förbättra optimeringens resultat. Upprepad utvärdering reducerar ovissheten och hjälper till att förbättra optimeringen, men har också ett pris. Om flera simuleringar används för varje lösning så minskar antalet olika lösningar som kan simuleras och sökrymden kan inte utforskas lika mycket, givet att det totala antalet simuleringar är begränsat. Dynamisk upprepad utvärdering kan däremot effektivisera flermålsoptimeringens avvägning mellan utforskning och exploatering av sökrymden baserat på det faktum att den nödvändiga precisionen i målvärdena varierar mellan de olika lösningarna i målrymden. I en tät och konvergerad population av lösningar är det viktigt att känna till de exakta målvärdena, medan osäkra målvärden är mindre skadliga i ett tidigt stadium i optimeringsprocessen när algoritmen utforskar målrymden. En dynamisk strategi för upprepad utvärdering med en noggrann allokering av utvärderingarna kan därför uppnå bättre resultat än en allokering som är statisk.

Trots att finns ett rikligt antal studier inom simuleringsbaserad optimering som använder sig av dynamisk upprepad utvärdering så har inga relaterade studier hittats som undersöker hur kombinationer av dynamisk upprepad utvärdering och preferensbaserad styrning kan förbättra prestandan hos algoritmer för flermålsoptimering ytterligare. Speciell avsaknad finns det av studier om optimering av problem med långa simuleringstider, som t.ex. simulering av produktionssystem. Avhandlingens mål är därför att studera, konstruera och jämföra nya kombinationer av preferensbaserade optimeringsalgoritmer och dynamiska strategier för upprepad utvärdering. Syftet är att förbättra resultatet av simuleringsbaserad flermålsoptimering som har stokastiska målvärden när antalet utvärderingar eller optimeringstiden är begränsade. Avhandlingen har speciellt fokuserat på att undersöka prestandahöjande åtgärder hos algoritmen R-NSGA-II i kombination med dynamisk upprepad utvärdering, baserad på fördelarna och flexibiliteten som interaktiva referenspunktbaserade algoritmer erbjuder. Exempel på förbättringsåtgärder är dynamiska algoritmer för upprepad utvärdering med förbättrad statistisk osäkerhetshantering och adaptiva optimeringsparametrar. Resultaten från avhandlingen visar tydligt att optimeringsresultaten kan förbättras om hybrida dynamiska algoritmer för upprepad utvärdering används och adaptiva optimeringsparametrar väljs beroende på osäkerhetsnivån och komplexiteten i optimeringsproblemet. För de fall där simuleringstiden är begränsad är slutsatsen från avhandlingen att både användarpreferenser och dynamisk upprepad utvärdering bör användas samtidigt för att uppnå de bästa resultaten i simuleringsbaserad flermålsoptimering.

Place, publisher, year, edition, pages
Skövde: Högskolan i Skövde, 2016. p. 300
Series
Dissertation Series ; 11 (2016)
Keywords
Evolutionary multi-objective optimization, simulation-based optimization, guided search, preference-based optimization, reference point, decision support, noise, stochastic systems, dynamic resampling, budget allocation, sequential sampling, hybrid, ranking and selection
National Category
Information Systems Robotics
Research subject
Natural sciences; Technology; Production and Automation Engineering
Identifiers
urn:nbn:se:his:diva-13088 (URN)978-91-982690-1-7 (ISBN)
Public defence
2016-12-12, Skövde, 13:00 (English)
Opponent
Supervisors
Funder
Knowledge FoundationVINNOVA
Available from: 2016-11-11 Created: 2016-11-10 Last updated: 2018-05-08Bibliographically approved
Siegmund, F., Ng, A. H. C. & Deb, K. (2016). Hybrid Dynamic Resampling Algorithms for Evolutionary Multi-objective Optimization of Invariant-Noise Problems. In: Giovanni Squillero, Paolo Burelli (Ed.), Applications of Evolutionary Computation: 19th European Conference, EvoApplications 2016, Porto, Portugal, March 30 – April 1, 2016, Proceedings, Part II. Paper presented at 19th European Conference, EvoApplications 2016, Porto, Portugal, March 30 – April 1, 2016 (pp. 311-326). , 9598
Open this publication in new window or tab >>Hybrid Dynamic Resampling Algorithms for Evolutionary Multi-objective Optimization of Invariant-Noise Problems
2016 (English)In: Applications of Evolutionary Computation: 19th European Conference, EvoApplications 2016, Porto, Portugal, March 30 – April 1, 2016, Proceedings, Part II / [ed] Giovanni Squillero, Paolo Burelli, 2016, Vol. 9598, p. 311-326Conference paper, Published paper (Refereed)
Abstract [en]

In Simulation-based Evolutionary Multi-objective Optimization (EMO) the available time for optimization usually is limited. Since many real-world optimization problems are stochastic models, the optimization algorithm has to employ a noise compensation technique for the objective values. This article analyzes Dynamic Resampling algorithms for handling the objective noise. Dynamic Resampling improves the objective value accuracy by spending more time to evaluate the solutions multiple times, which tightens the optimization time limit even more. This circumstance can be used to design Dynamic Resampling algorithms with a better sampling allocation strategy that uses the time limit. In our previous work, we investigated Time-based Hybrid Resampling algorithms for Preference-based EMO. In this article, we extend our studies to general EMO which aims to find a converged and diverse set of alternative solutions along the whole Pareto-front of the problem. We focus on problems with an invariant noise level, i.e. a flat noise landscape.

Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 9598
Keywords
Evolutionary multi-objective optimization, Simulationbased optimization, Noise, Dynamic resampling, Budget allocation, Hybrid
National Category
Robotics Information Systems
Research subject
Natural sciences; Technology; Production and Automation Engineering
Identifiers
urn:nbn:se:his:diva-12074 (URN)10.1007/978-3-319-31153-1_21 (DOI)000467438600021 ()2-s2.0-84962257415 (Scopus ID)978-3-319-31152-4 (ISBN)978-3-319-31153-1 (ISBN)
Conference
19th European Conference, EvoApplications 2016, Porto, Portugal, March 30 – April 1, 2016
Projects
BlixtSim, IDSS
Funder
Knowledge Foundation
Available from: 2016-03-29 Created: 2016-03-29 Last updated: 2020-02-14Bibliographically approved
Siegmund, F., Ng, A. H. C. & Deb, K. (2015). Dynamic Resampling for Preference-based Evolutionary Multi-Objective Optimization of Stochastic Systems. In: : . Paper presented at 23rd International Conference on Multiple Criteria Decision Making MCDM 2015, August 3-7, 2015, Hamburg, Germany.
Open this publication in new window or tab >>Dynamic Resampling for Preference-based Evolutionary Multi-Objective Optimization of Stochastic Systems
2015 (English)Conference paper, Oral presentation with published abstract (Refereed)
Abstract [en]

In Multi-objective Optimization many solutions have to be evaluated in order to provide the decision maker with a diverse choice of solutions along the Pareto-front. In Simulation-based Optimization the number of optimization function evaluations is usually very limited due to the long execution times of the simulation models. If preference information is available however, the available number of function evaluations can be used more effectively. The optimization can be performed as a guided, focused search which returns solutions close to interesting, preferred regions of the Pareto-front. One such algorithm for guided search is the Reference-point guided Non-dominated Sorting Genetic Algorithm II, R-NSGA-II. It is a population-based Evolutionary Algorithm that finds a set of non-dominated solutions in a single optimization run. R-NSGA-II takes reference points in the objective space provided by the decision maker and guides the optimization towards areas of the Pareto-front close the reference points.

In Simulation-based Optimization the modeled and simulated systems are often stochastic and a common method to handle objective noise is Resampling. Reliable quality assessment of system configurations by resampling requires many simulation runs. Therefore, the optimization process can benefit from Dynamic Resampling algorithms that distribute the available function evaluations among the solutions in the best possible way. Solutions can vary in their sampling need. For example, solutions with highly variable objective values have to be sampled more times to reduce their objective value standard error. Dynamic resampling algorithms assign as much samples to them as is needed to reduce the uncertainty about their objective values below a certain threshold. Another criterion the number of samples can be based on is a solution's closeness to the Pareto-front. For solutions that are close to the Pareto-front it is likely that they are member of the final result set. It is therefore important to have accurate knowledge of their objective values available, in order to be able to to tell which solutions are better than others. Usually, the distance to the Pareto-front is not known, but another criterion can be used as an indication for it instead: The elapsed optimization time. A third example of a resampling criterion can be the dominance relations between different solutions. The optimization algorithm has to determine for pairs of solutions which is the better one. Here both distances between objective vectors and the variance of the objective values have to be considered which requires a more advanced resampling technique. This is a Ranking and Selection problem.

If R-NSGA-II is applied in a scenario with a stochastic fitness function resampling algorithms have to be used to support it in the best way and avoid a performance degradation due to uncertain knowledge about the objective values of solutions. In our work we combine R-NSGA-II with several resampling algorithms that are based on the above mentioned resampling criteria or combinations thereof and evaluate which are the best criteria the sampling allocation can be based on, in which situations.

Due to the preference information R-NSGA-II has an important fitness information about the solutions at its disposal: The distance to reference points. We propose a resampling strategy that allocates more samples to solutions close to a reference point. This idea is then extended with a resampling technique that compares solutions based on their distance to the reference point. We base this algorithm on a classical Ranking and Selection algorithm, Optimal Computing Budget Allocation, and show how OCBA can be applied to support R-NSGA-II. We show the applicability of the proposed algorithms in a case study of an industrial production line for car manufacturing.

Series
COIN Report ; 2015020
Keywords
Evolutionary multi-objective optimization, guided search, preference-based optimization, reference point, dynamic resampling, budget allocation, decision support, simulation-based optimization, stochastic systems
National Category
Computer and Information Sciences Robotics
Research subject
Natural sciences; Technology; Production and Automation Engineering
Identifiers
urn:nbn:se:his:diva-11494 (URN)
Conference
23rd International Conference on Multiple Criteria Decision Making MCDM 2015, August 3-7, 2015, Hamburg, Germany
Funder
Knowledge Foundation
Available from: 2015-09-07 Created: 2015-09-07 Last updated: 2018-03-29Bibliographically approved
Siegmund, F., Ng, A. H. C. & Deb, K. (2015). Hybrid Dynamic Resampling for Guided Evolutionary Multi-Objective Optimization. In: António Gaspar-Cunha; Carlos Henggeler Antunes; Carlos Coello Coello (Ed.), Evolutionary Multi-Criterion Optimization: 8th International Conference, EMO 2015, Guimarães, Portugal, March 29 --April 1, 2015. Proceedings, Part I. Paper presented at 8th International Conference on Evolutionary Multi-Criterion Optimization, March 2015, Guimarães, Portugal (pp. 366-380). Springer International Publishing Switzerland
Open this publication in new window or tab >>Hybrid Dynamic Resampling for Guided Evolutionary Multi-Objective Optimization
2015 (English)In: Evolutionary Multi-Criterion Optimization: 8th International Conference, EMO 2015, Guimarães, Portugal, March 29 --April 1, 2015. Proceedings, Part I / [ed] António Gaspar-Cunha; Carlos Henggeler Antunes; Carlos Coello Coello, Springer International Publishing Switzerland , 2015, p. 366-380Conference paper, Published paper (Refereed)
Abstract [en]

In Guided Evolutionary Multi-objective Optimization the goal is to find a diverse, but locally focused non-dominated front in a decision maker’s area of interest, as close as possible to the true Pareto-front. The optimization can focus its efforts towards the preferred area and achieve a better result [9, 17, 7, 13]. The modeled and simulated systems are often stochastic and a common method to handle the objective noise is Resampling. The given preference information allows to define better resampling strategies which further improve the optimization result. In this paper, resampling strategies are proposed that base the sampling allocation on multiple factors, and thereby combine multiple resampling strategies proposed by the authors in [15]. These factors are, for example, the Pareto-rank of a solution and its distance to the decision maker’s area of interest. The proposed hybrid Dynamic Resampling Strategy DR2 is evaluated on the Reference point-guided NSGA-II optimization algorithm (R-NSGA-II) [9].

Place, publisher, year, edition, pages
Springer International Publishing Switzerland, 2015
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 9018
Keywords
evolutionary multi-objective optimization, guided search, reference point, dynamic resampling, budget allocation
National Category
Computer and Information Sciences Robotics
Research subject
Natural sciences; Technology; Production and Automation Engineering
Identifiers
urn:nbn:se:his:diva-10814 (URN)10.1007/978-3-319-15934-8_25 (DOI)000361702100025 ()2-s2.0-84925337390 (Scopus ID)978-3-319-15933-1 (ISBN)978-3-319-15934-8 (ISBN)
Conference
8th International Conference on Evolutionary Multi-Criterion Optimization, March 2015, Guimarães, Portugal
Projects
FFI-HSO
Funder
Knowledge FoundationVinnova
Note

Springer Cham

This study was partially funded by VINNOVA, Sweden, through the FFI-HSO project. The authors gratefully acknowledge their provision of research funding.

Available from: 2015-03-30 Created: 2015-03-30 Last updated: 2022-09-28Bibliographically approved
Deb, K., Siegmund, F. & Ng, A. H. C. (2015). R-HV: A Metric for Computing Hyper-volume for Reference Point-based EMOs. In: Bijaya Ketan Panigrahi, Ponnuthurai Nagaratnam Suganthan & Swagatam Das (Ed.), Bijaya Ketan Panigrahi, Ponnuthurai Nagaratnam Suganthan & Swagatam Das (Ed.), Swarm, Evolutionary, and Memetic Computing: 5th International Conference, SEMCCO 2014, Bhubaneswar, India, December 18-20, 2014, Revised Selected Papers. Paper presented at 5th International Conference on Swarm, Evolutionary, and Memetic Computing, 18th-20th December 2014 (SEMCCO14), Bhubaneswar, Odisha, India (pp. 98-110). Paper presented at 5th International Conference on Swarm, Evolutionary, and Memetic Computing, 18th-20th December 2014 (SEMCCO14), Bhubaneswar, Odisha, India. Springer
Open this publication in new window or tab >>R-HV: A Metric for Computing Hyper-volume for Reference Point-based EMOs
2015 (English)In: Swarm, Evolutionary, and Memetic Computing: 5th International Conference, SEMCCO 2014, Bhubaneswar, India, December 18-20, 2014, Revised Selected Papers / [ed] Bijaya Ketan Panigrahi, Ponnuthurai Nagaratnam Suganthan & Swagatam Das, Springer, 2015, p. 98-110Chapter in book (Refereed)
Abstract [en]

For evaluating performance of a multi-objective optimizationfor finding the entire efficient front, a number of metrics, such as hypervolume, inverse generational distance, etc. exists. However, for evaluatingan EMO algorithm for finding a subset of the efficient frontier, the existing metrics are inadequate. There does not exist many performancemetrics for evaluating a partial preferred efficient set. In this paper, wesuggest a metric which can be used for such purposes for both attainableand unattainable reference points. Results on a number of two-objectiveproblems reveal its working principle and its importance in assessingdifferent algorithms. The results are promising and encouraging for itsfurther use.

Place, publisher, year, edition, pages
Springer, 2015
Series
Lecture Notes in Computer Science LNCS, ISSN 0302-9743, E-ISSN 1611-3349 ; 8947
Keywords
Evolutionary multi-objective optimization, performance metric, hyper-volume, reference point
National Category
Computer and Information Sciences Robotics
Research subject
Natural sciences; Technology; Production and Automation Engineering
Identifiers
urn:nbn:se:his:diva-10464 (URN)10.1007/978-3-319-20294-5_9 (DOI)000365045900009 ()2-s2.0-84946116194 (Scopus ID)978-3-319-20293-8 (ISBN)978-3-319-20294-5 (ISBN)
Conference
5th International Conference on Swarm, Evolutionary, and Memetic Computing, 18th-20th December 2014 (SEMCCO14), Bhubaneswar, Odisha, India
Funder
VINNOVA
Available from: 2014-12-19 Created: 2014-12-19 Last updated: 2018-11-27Bibliographically approved
Siegmund, F., Ng, A. H. C. & Deb, K. (2013). A Comparative Study of Dynamic Resampling Strategies for Guided Evolutionary Multi-Objective Optimization. In: 2013 IEEE Congress on Evolutionary Computation, CEC 2013: . Paper presented at 2013 IEEE Congress on Evolutionary Computation, June 20-23, Cancún, México (pp. 1826-1835). IEEE conference proceedings
Open this publication in new window or tab >>A Comparative Study of Dynamic Resampling Strategies for Guided Evolutionary Multi-Objective Optimization
2013 (English)In: 2013 IEEE Congress on Evolutionary Computation, CEC 2013, IEEE conference proceedings, 2013, p. 1826-1835Conference paper, Published paper (Refereed)
Abstract [en]

In Evolutionary Multi-objective Optimization many solutions have to be evaluated to provide the decision maker with a diverse choice of solutions along the Pareto-front, in particular for high-dimensional optimization problems. In Simulation-based Optimization the modeled systems are complex and require long simulation times. In addition the evaluated systems are often stochastic and reliable quality assessment of system configurations by resampling requires many simulation runs. As a countermeasure for the required high number of simulation runs caused by multiple optimization objectives the optimization can be focused on interesting parts of the Pareto-front, as it is done by the Reference point-guided NSGA-II algorithm (R-NSGA-II) [9]. The number of evaluations needed for the resampling of solutions can be reduced by intelligent resampling algorithms that allocate just as much sampling budget needed in different situations during the optimization run. In this paper we propose and compare resampling algorithms that support the R-NSGA-II algorithm on optimization problems with stochastic evaluation functions. © 2013 IEEE.

Place, publisher, year, edition, pages
IEEE conference proceedings, 2013
Keywords
Evolutionary multi-objective optimization, simulation-based optimization, guided search, reference point, decision support, stochastic systems, dynamic, resampling
National Category
Engineering and Technology Computer Sciences
Research subject
Technology
Identifiers
urn:nbn:se:his:diva-8531 (URN)10.1109/CEC.2013.6557782 (DOI)000326235301106 ()2-s2.0-84881589703 (Scopus ID)978-1-4799-0453-2 (ISBN)978-1-4799-0452-5 (ISBN)978-1-4799-0454-9 (ISBN)
Conference
2013 IEEE Congress on Evolutionary Computation, June 20-23, Cancún, México
Available from: 2013-10-07 Created: 2013-10-07 Last updated: 2018-01-11Bibliographically approved
Siegmund, F., Deb, K. & Ng, A. H. C. (2013). Adaptive Guided Evolutionary Multi-Objective Optimization. In: : . Paper presented at 22nd International Conference on Multiple Criteria Decision Making 2013, 17-21 June 2013, Málaga, Spain (pp. 99).
Open this publication in new window or tab >>Adaptive Guided Evolutionary Multi-Objective Optimization
2013 (English)Conference paper, Oral presentation with published abstract (Refereed)
Abstract [en]

In Multi-objective Optimization many solutions have to be evaluated in order to provide the decision maker with a diverse Pareto-front. In Simulation-based Optimization the number of optimization function evaluations is very limited. If preference information is available however, the available function evaluations can be used more effectively by guiding the optimization towards interesting, preferred regions. One such algorithm for guided search is the Reference-point guided NSGA-II. It takes reference points provided by the decision maker and guides the optimization towards areas of the Pareto-front close to the reference points.We propose several extensions of R-NSGA-II. In the beginning of the optimization runtime the population is spread-out in the objective space while towards the end of the runtime most solutions are close to reference points. The purpose of a large population is to avoid local optima and to explore the search space which is less important when the algorithm has converged to the reference points. Therefore, we reduce the population size towards the end of the runtime. R-NSGA-II controls the objective space diversity through the epsilon parameter. We reduce the diversity in the population as it approaches the reference points. In a previous study we showed that R-NSGA-II keeps a high diversity until late in the optimization run which is caused by the Pareto-fitness. This slows down the progress towards the reference points. We constrain the Pareto-fitness to force a faster convergence. For the same reason an approach is presented that delays the use of the Pareto-fitness: Initially, the fitness is based only on reference point distance and diversity. Later, when the population has converged towards the Pareto-front, Pareto-fitness is considered as primary-, and distance as secondary fitness.

Keywords
Evolutionary multi-objective optimization, simulation-based optimization, guided search, reference point, adaptive
National Category
Computer and Information Sciences Robotics
Research subject
Natural sciences; Technology
Identifiers
urn:nbn:se:his:diva-10467 (URN)
Conference
22nd International Conference on Multiple Criteria Decision Making 2013, 17-21 June 2013, Málaga, Spain
Funder
VINNOVA
Available from: 2014-12-19 Created: 2014-12-19 Last updated: 2018-01-11Bibliographically approved
Organisations
Identifiers
ORCID iD: ORCID iD iconorcid.org/0000-0003-3432-5068

Search in DiVA

Show all publications