Improving Time and Memory Efficiency of Genetic Algorithms by Storing Populations as Minimum Spanning Trees of Patches

Maxim Buzdalov*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference Proceeding (Non-Journal item)

Abstract

In many applications of evolutionary algorithms the computational cost of applying operators and storing populations is comparable to the cost of fitness evaluation. Furthermore, by knowing what exactly has changed in an individual by an operator, it is possible to recompute fitness value much more efficiently than from scratch. The associated time and memory improvements have been available for simple evolutionary algorithms, few specific genetic algorithms and in the context of gray-box optimization, but not for all algorithms, and the main reason is that it is difficult to achieve in algorithms using large arbitrarily structured populations. This paper makes a first step towards improving this situation. We show that storing the population as a minimum spanning tree, where vertices correspond to individuals but only contain meta-information about them, and edges store structural differences, or patches, between the individuals, is a viable alternative to the straightforward implementation. Our experiments suggest that significant, even asymptotic, improvements — including execution of crossover operators! — can be achieved in terms of both memory usage and computational costs.

Original languageEnglish
Title of host publicationGECCO 2023 Companion - Proceedings of the 2023 Genetic and Evolutionary Computation Conference Companion
PublisherAssociation for Computing Machinery
Pages1873-1881
Number of pages9
ISBN (Electronic)9798400701207
DOIs
Publication statusPublished - 15 Jul 2023
Event2023 Genetic and Evolutionary Computation Conference Companion, GECCO 2023 Companion - Lisbon, Portugal
Duration: 15 Jul 202319 Jul 2023

Publication series

NameGECCO 2023 Companion - Proceedings of the 2023 Genetic and Evolutionary Computation Conference Companion

Conference

Conference2023 Genetic and Evolutionary Computation Conference Companion, GECCO 2023 Companion
Country/TerritoryPortugal
CityLisbon
Period15 Jul 202319 Jul 2023

Keywords

  • genetic algorithms
  • minimum spanning tree
  • performance
  • population-based algorithms

Fingerprint

Dive into the research topics of 'Improving Time and Memory Efficiency of Genetic Algorithms by Storing Populations as Minimum Spanning Trees of Patches'. Together they form a unique fingerprint.

Cite this