Title
GA performance distributions and randomly generated binary constraint satisfaction problems
Author
Faculty/Department
Faculty of Sciences. Mathematics and Computer Science
Publication type
article
Publication
Amsterdam ,
Subject
Computer. Automation
Source (journal)
Theoretical computer science. - Amsterdam
Volume/pages
287(2002) :1 , p. 167-185
ISSN
0304-3975
ISI
000178322200009
Carrier
E
Target language
English (eng)
Full text (Publishers DOI)
Affiliation
University of Antwerp
Abstract
We investigate the variable performance of a genetic algorithm (GA) on randomly generated binary constraint satisfaction problem instances which occur near the phase transition from soluble to non-soluble. We first carry out a conventional landscape analysis and observe, next to a number of common features related to the interaction structure, important differences between the instances, such as the number of solutions, the quality of the paths to the solutions, and the lengths and extent of the neutral paths for mutation. We then split the dynamics of the GA into two phases: the ascent towards the high fitness region, and from this high fitness region to a solution. To gain further information about the GA's behavior in the first phase, we construct two models based on the much simpler fully separable functions, and try to match instances which show a similar performance distribution. Although far from exact, this technique of comparing with analog search problems gives a hint about the landscape elements that are responsible for the GA's slow ascent. (C) 2002 Elsevier Science B.V. All rights reserved.
Full text (open access)
https://repository.uantwerpen.be/docman/irua/58f030/4628.pdf
E-info
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000178322200009&DestLinkType=RelatedRecords&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000178322200009&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000178322200009&DestLinkType=CitingArticles&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
Handle