Imperative genetic programming

Fajfar, Iztok (author), Rojec, Žiga (author), Bürmen, Arpad (author), Kunaver, Matevž (author), Tuma, Tadej (author), Tomažič, Sašo (author), Puhan, Janez (author)

Genetic programming (GP) has a long-standing tradition in the evolution of computer programs, predominantly utilizing tree and linear paradigms, each with distinct advantages and limitations. Despite the rapid growth of the GP field, there have been disproportionately few attempts to evolve ’real’ Turing-like imperative programs (as contrasted with functional programming) from the ground up. Existing research focuses mainly on specific special cases where the structure of the solution is partly known. This paper explores the potential of integrating tree and linear GP paradigms to develop an encoding scheme that universally supports genetic operators without constraints and consistently generates syntactically correct Python programs from scratch. By blending the symmetrical structure of tree-based representations with the inherent asymmetry of linear sequences, we created a versatile environment for program evolution. Our approach was rigorously tested on 35 problems characterized by varying Halstead complexity metrics, to delineate the approach’s boundaries. While expected brute-force program solutions were observed, our method yielded more sophisticated strategies, such as optimizing a program by restricting the division trials to the values up to the square root of the number when counting its proper divisors. Despite the recent groundbreaking advancements in large language models, we assert that the GP field warrants continued research. GP embodies a fundamentally different computational paradigm, crucial for advancing our understanding of natural evolutionary processes.

• Language: English
• Keywords: evolutionary agorithms, tree genetic programming, linear genetic programming, imperative programming
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FE - Faculty of Electrical Engineering
• Publication status: Published
• Publication version: Version of Record
• Year: 2024
• Number of pages: 19 str.
• Numbering: Vol. 16, iss. 9, art. 1146
• PID: 20.500.12556/RUL-161550
• UDC: 004.42
• ISSN on article: 2073-8994
• DOI: 10.3390/sym16091146
• COBISS.SI-ID: 207066371
• Publication date in RUL: 12.09.2024

Record is a part of a journal

• Title: Symmetry
• Shortened title: Symmetry
• Publisher: Molecular Diversity Preservation International
• ISSN: 2073-8994
• COBISS.SI-ID: 517592345

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.

Secondary language

• Language: Slovenian
• Keywords: evolucijski algoritmi, drevesno genetsko programiranje, linearno genetsko programiranje, imperativno programiranje

Projects

• Funder: ARIS - Slovenian Research and Innovation Agency
• Project number: P2-0246
• Name: ICT4QoL - Informacijsko komunikacijske tehnologije za kakovostno življenje