No Cover Image

Journal article 329 views 105 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, Pages: 1 - 46

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: 1530-9304
Published: MIT Press
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>SCS</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/><journalNumber/><paginationStart>1</paginationStart><paginationEnd>46</paginationEnd><publisher>MIT Press</publisher><placeOfPublication/><isbnPrint/><isbnElectronic/><issnPrint/><issnElectronic>1530-9304</issnElectronic><keywords>Bound constraint, algorithmic behaviour</keywords><publishedDay>0</publishedDay><publishedMonth>0</publishedMonth><publishedYear>0</publishedYear><publishedDate>0001-01-01</publishedDate><doi>10.1162/evco_a_00333</doi><url>http://dx.doi.org/10.1162/evco_a_00333</url><notes/><college>COLLEGE NANME</college><department>Computer Science</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>SCS</DepartmentCode><institution>Swansea University</institution><apcterm>Other</apcterm><funders/><projectreference/><lastEdited>2023-09-21T15:42:05.4642153</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 SCS 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 1 46 MIT Press 1530-9304 Bound constraint, algorithmic behaviour 0 0 0 0001-01-01 10.1162/evco_a_00333 http://dx.doi.org/10.1162/evco_a_00333 COLLEGE NANME Computer Science COLLEGE CODE SCS Swansea University Other 2023-09-21T15:42:05.4642153 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_start_page 1
institution Swansea University
issn 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
url http://dx.doi.org/10.1162/evco_a_00333
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 0001-01-01T15:42:03Z
_version_ 1777658572142804992
score 11.01753

Similar Items