On the Time Complexity of Simple Cartesian Genetic Programming | Zendy

Roman Kalkreuth | Zendy; Andre Droschinsky | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

On the Time Complexity of Simple Cartesian Genetic Programming

Author(s) -

Roman Kalkreuth,

Andre Droschinsky

Publication year - 2019

Language(s) - English

Resource type - Conference proceedings

DOI - 10.5220/0008070201720179

Subject(s) - simple (philosophy) , computer science , cartesian coordinate system , boolean function , genetic programming , theoretical computer science , time complexity , genetic algorithm , mathematical optimization , algorithm , mathematics , artificial intelligence , philosophy , epistemology , geometry

Since its introduction, Cartesian Genetic Programming has been mostly analyzed on an experimental level with boolean function problems. Consequently, there is still little theoretical understanding of Cartesian Genetic Programming. In this paper, we present a first time complexity analysis of Cartesian Genetic Programming. We introduce and analyze a simple mathematical problem and a simple logical boolean problem called SUM and AND. The results of our analysis show that simple CGP is able to solve SUM efficiently in time Θ(nlogn). However, our analysis of the AND problem shows that simple CGP is not able to solve AND efficiently.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research