No Cover Image

Journal article 413 views 142 downloads

The Importance of Being Constrained: Dealing with Infeasible Solutions in Differential Evolution and Beyond

Anna V. Kononova, Diederick Vermetten, Fabio Caraffini Orcid Logo, Madalina-A. Mitran, Daniela Zaharie

Evolutionary Computation, Volume: 32, Issue: 1, Pages: 3 - 48

Swansea University Author: Fabio Caraffini Orcid Logo

Check full text

DOI (Published version): 10.1162/evco_a_00333

Abstract

We argue that results produced by a heuristic optimisation algorithm cannot be considered reproducible unless the algorithm fully specifies what should be done with solutions generated outside the domain, even in the case of simple bound constraints. Currently, in the field of heuristic optimisation...

Full description

Published in: Evolutionary Computation
ISSN: 1063-6560 1530-9304
Published: MIT Press 2024
Online Access: Check full text

URI: https://cronfa.swan.ac.uk/Record/cronfa63489
Tags: Add Tag
No Tags, Be the first to tag this record!
first_indexed 2023-05-17T13:09:50Z
last_indexed 2023-05-17T13:09:50Z
id cronfa63489
recordtype SURis
fullrecord <?xml version="1.0" encoding="utf-8"?><rfc1807 xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xsd="http://www.w3.org/2001/XMLSchema"><bib-version>v2</bib-version><id>63489</id><entry>2023-05-17</entry><title>The Importance of Being Constrained: Dealing with Infeasible Solutions in Differential Evolution and Beyond</title><swanseaauthors><author><sid>d0b8d4e63d512d4d67a02a23dd20dfdb</sid><ORCID>0000-0001-9199-7368</ORCID><firstname>Fabio</firstname><surname>Caraffini</surname><name>Fabio Caraffini</name><active>true</active><ethesisStudent>false</ethesisStudent></author></swanseaauthors><date>2023-05-17</date><deptcode>MACS</deptcode><abstract>We argue that results produced by a heuristic optimisation algorithm cannot be considered reproducible unless the algorithm fully specifies what should be done with solutions generated outside the domain, even in the case of simple bound constraints. Currently, in the field of heuristic optimisation, such specification is rarely mentioned or investigated due to the assumed triviality or insignificance of this question. Here, we demonstrate that, at least in algorithms based on Differential Evolution, this choice induces notably different behaviours in terms of performance, disruptiveness and population diversity. This is shown theoretically (where possible) for standard Differential Evolution in the absence of selection pressure and experimentally for the standard and state-of-the-art Differential Evolution variants, on a special test function and the BBOB benchmarking suite, respectively. Moreover, we demonstrate that the importance of this choice quickly grows with problem's dimensionality. Differential Evolution is not at all special in this regard - there is no reason to presume that other heuristic optimisers are not equally affected by the aforementioned algorithmic choice. Thus, we urge the heuristic optimisation community to formalise and adopt the idea of a new algorithmic component in heuristic optimisers, which we refer to as the strategy of dealing with infeasible solutions. This component needs to be consistently: (a) specified in algorithmic descriptions to guarantee reproducibility of results, (b) studied to better understand its impact on an algorithm's performance in a wider sense (i.e. convergence time, robustness, etc.) and (c) included in the (automatic) design of algorithms. All of these should be done even for problems with bound constraints.</abstract><type>Journal Article</type><journal>Evolutionary Computation</journal><volume>32</volume><journalNumber>1</journalNumber><paginationStart>3</paginationStart><paginationEnd>48</paginationEnd><publisher>MIT Press</publisher><placeOfPublication/><isbnPrint/><isbnElectronic/><issnPrint>1063-6560</issnPrint><issnElectronic>1530-9304</issnElectronic><keywords>Bound constraint, algorithmic behaviour</keywords><publishedDay>1</publishedDay><publishedMonth>3</publishedMonth><publishedYear>2024</publishedYear><publishedDate>2024-03-01</publishedDate><doi>10.1162/evco_a_00333</doi><url/><notes/><college>COLLEGE NANME</college><department>Mathematics and Computer Science School</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>MACS</DepartmentCode><institution>Swansea University</institution><apcterm>Not Required</apcterm><funders/><projectreference/><lastEdited>2024-09-16T14:15:31.6765695</lastEdited><Created>2023-05-17T13:53:08.4604735</Created><path><level id="1">Faculty of Science and Engineering</level><level id="2">School of Mathematics and Computer Science - Computer Science</level></path><authors><author><firstname>Anna V.</firstname><surname>Kononova</surname><order>1</order></author><author><firstname>Diederick</firstname><surname>Vermetten</surname><order>2</order></author><author><firstname>Fabio</firstname><surname>Caraffini</surname><orcid>0000-0001-9199-7368</orcid><order>3</order></author><author><firstname>Madalina-A.</firstname><surname>Mitran</surname><order>4</order></author><author><firstname>Daniela</firstname><surname>Zaharie</surname><order>5</order></author></authors><documents><document><filename>63489__27496__ad61a67d8f504d95aec29df33d272687.pdf</filename><originalFilename>ECJ_TIOBR.pdf</originalFilename><uploaded>2023-05-17T13:55:51.2889972</uploaded><type>Output</type><contentLength>32161566</contentLength><contentType>application/pdf</contentType><version>Accepted Manuscript</version><cronfaStatus>true</cronfaStatus><copyrightCorrect>false</copyrightCorrect><language>English</language></document></documents><OutputDurs><OutputDur><Id>188</Id><IsDataAvailableOnline>true</IsDataAvailableOnline><DataNotAvailableOnlineReasonId xsi:nil="true"/><DurUrl>10.5281/zenodo.7115488</DurUrl><IsDurRestrictions>false</IsDurRestrictions><DurRestrictionReasonId xsi:nil="true"/><DurEmbargoDate xsi:nil="true"/></OutputDur></OutputDurs></rfc1807>
spelling v2 63489 2023-05-17 The Importance of Being Constrained: Dealing with Infeasible Solutions in Differential Evolution and Beyond d0b8d4e63d512d4d67a02a23dd20dfdb 0000-0001-9199-7368 Fabio Caraffini Fabio Caraffini true false 2023-05-17 MACS We argue that results produced by a heuristic optimisation algorithm cannot be considered reproducible unless the algorithm fully specifies what should be done with solutions generated outside the domain, even in the case of simple bound constraints. Currently, in the field of heuristic optimisation, such specification is rarely mentioned or investigated due to the assumed triviality or insignificance of this question. Here, we demonstrate that, at least in algorithms based on Differential Evolution, this choice induces notably different behaviours in terms of performance, disruptiveness and population diversity. This is shown theoretically (where possible) for standard Differential Evolution in the absence of selection pressure and experimentally for the standard and state-of-the-art Differential Evolution variants, on a special test function and the BBOB benchmarking suite, respectively. Moreover, we demonstrate that the importance of this choice quickly grows with problem's dimensionality. Differential Evolution is not at all special in this regard - there is no reason to presume that other heuristic optimisers are not equally affected by the aforementioned algorithmic choice. Thus, we urge the heuristic optimisation community to formalise and adopt the idea of a new algorithmic component in heuristic optimisers, which we refer to as the strategy of dealing with infeasible solutions. This component needs to be consistently: (a) specified in algorithmic descriptions to guarantee reproducibility of results, (b) studied to better understand its impact on an algorithm's performance in a wider sense (i.e. convergence time, robustness, etc.) and (c) included in the (automatic) design of algorithms. All of these should be done even for problems with bound constraints. Journal Article Evolutionary Computation 32 1 3 48 MIT Press 1063-6560 1530-9304 Bound constraint, algorithmic behaviour 1 3 2024 2024-03-01 10.1162/evco_a_00333 COLLEGE NANME Mathematics and Computer Science School COLLEGE CODE MACS Swansea University Not Required 2024-09-16T14:15:31.6765695 2023-05-17T13:53:08.4604735 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science Anna V. Kononova 1 Diederick Vermetten 2 Fabio Caraffini 0000-0001-9199-7368 3 Madalina-A. Mitran 4 Daniela Zaharie 5 63489__27496__ad61a67d8f504d95aec29df33d272687.pdf ECJ_TIOBR.pdf 2023-05-17T13:55:51.2889972 Output 32161566 application/pdf Accepted Manuscript true false English 188 true 10.5281/zenodo.7115488 false
title The Importance of Being Constrained: Dealing with Infeasible Solutions in Differential Evolution and Beyond
spellingShingle The Importance of Being Constrained: Dealing with Infeasible Solutions in Differential Evolution and Beyond
Fabio Caraffini
title_short The Importance of Being Constrained: Dealing with Infeasible Solutions in Differential Evolution and Beyond
title_full The Importance of Being Constrained: Dealing with Infeasible Solutions in Differential Evolution and Beyond
title_fullStr The Importance of Being Constrained: Dealing with Infeasible Solutions in Differential Evolution and Beyond
title_full_unstemmed The Importance of Being Constrained: Dealing with Infeasible Solutions in Differential Evolution and Beyond
title_sort The Importance of Being Constrained: Dealing with Infeasible Solutions in Differential Evolution and Beyond
author_id_str_mv d0b8d4e63d512d4d67a02a23dd20dfdb
author_id_fullname_str_mv d0b8d4e63d512d4d67a02a23dd20dfdb_***_Fabio Caraffini
author Fabio Caraffini
author2 Anna V. Kononova
Diederick Vermetten
Fabio Caraffini
Madalina-A. Mitran
Daniela Zaharie
format Journal article
container_title Evolutionary Computation
container_volume 32
container_issue 1
container_start_page 3
publishDate 2024
institution Swansea University
issn 1063-6560
1530-9304
doi_str_mv 10.1162/evco_a_00333
publisher MIT Press
college_str Faculty of Science and Engineering
hierarchytype
hierarchy_top_id facultyofscienceandengineering
hierarchy_top_title Faculty of Science and Engineering
hierarchy_parent_id facultyofscienceandengineering
hierarchy_parent_title Faculty of Science and Engineering
department_str School of Mathematics and Computer Science - Computer Science{{{_:::_}}}Faculty of Science and Engineering{{{_:::_}}}School of Mathematics and Computer Science - Computer Science
document_store_str 1
active_str 0
description We argue that results produced by a heuristic optimisation algorithm cannot be considered reproducible unless the algorithm fully specifies what should be done with solutions generated outside the domain, even in the case of simple bound constraints. Currently, in the field of heuristic optimisation, such specification is rarely mentioned or investigated due to the assumed triviality or insignificance of this question. Here, we demonstrate that, at least in algorithms based on Differential Evolution, this choice induces notably different behaviours in terms of performance, disruptiveness and population diversity. This is shown theoretically (where possible) for standard Differential Evolution in the absence of selection pressure and experimentally for the standard and state-of-the-art Differential Evolution variants, on a special test function and the BBOB benchmarking suite, respectively. Moreover, we demonstrate that the importance of this choice quickly grows with problem's dimensionality. Differential Evolution is not at all special in this regard - there is no reason to presume that other heuristic optimisers are not equally affected by the aforementioned algorithmic choice. Thus, we urge the heuristic optimisation community to formalise and adopt the idea of a new algorithmic component in heuristic optimisers, which we refer to as the strategy of dealing with infeasible solutions. This component needs to be consistently: (a) specified in algorithmic descriptions to guarantee reproducibility of results, (b) studied to better understand its impact on an algorithm's performance in a wider sense (i.e. convergence time, robustness, etc.) and (c) included in the (automatic) design of algorithms. All of these should be done even for problems with bound constraints.
published_date 2024-03-01T14:15:31Z
_version_ 1810358632307490816
score 11.035634

Similar Items