TY - GEN
T1 - Improving Time and Memory Efficiency of Genetic Algorithms by Storing Populations as Minimum Spanning Trees of Patches
AU - Buzdalov, Maxim
N1 - Publisher Copyright:
© 2023 Copyright held by the owner/author(s). Publication rights licensed to ACM.
PY - 2023/7/15
Y1 - 2023/7/15
N2 - 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.
AB - 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.
KW - genetic algorithms
KW - minimum spanning tree
KW - performance
KW - population-based algorithms
UR - http://www.scopus.com/inward/record.url?scp=85169019167&partnerID=8YFLogxK
U2 - 10.1145/3583133.3596388
DO - 10.1145/3583133.3596388
M3 - Conference Proceeding (Non-Journal item)
AN - SCOPUS:85169019167
T3 - GECCO 2023 Companion - Proceedings of the 2023 Genetic and Evolutionary Computation Conference Companion
SP - 1873
EP - 1881
BT - GECCO 2023 Companion - Proceedings of the 2023 Genetic and Evolutionary Computation Conference Companion
PB - Association for Computing Machinery
T2 - 2023 Genetic and Evolutionary Computation Conference Companion, GECCO 2023 Companion
Y2 - 15 July 2023 through 19 July 2023
ER -