Methods of automatic programming involving semantic approaches

A research project funded by National Science Centre, Poland under grant number DEC-2012/07/N/ST6/03066. The project started on 10th July 2013 and ended on 9th July 2016.

Research project objectives

The proposed research project concerns automatic induction of computer programs from examples. The main part of research will be focused on genetic programming, which is the leading paradigm in this field. Therefore the project will combine the ideas from fields of machine learning, evolutionary computation and other branches of computational intelligence.

The aim of the research is the development of consistent set of algorithms for the automatic induction of programs from examples, and the clarification of semantic phenomena occurring during the programming process. For the purpose of the automatic programming, the semantics is often defined as a collection of output values of program executed on a given set of input values. The use of semantics defined in that way, paves the way to the better control over process of automatic programming, than the ordinary methods based only on manipulation of program syntax do. The reason for this is, by far, a confusing and complicated relation between (even marginal) changes in source code of program and a predicted changes of the output of the program.

The use of semantics of program is a new, currently poorly studied, trend in this domain, and the newest papers in this scope indicate its very great potential. The increased interest in this subject is particularly noticeable in the environment involved in the genetic programming. Genetic programming is a faction of evolutionary computation algorithms, in which a population of computer programs is evolved. Therefore a new, semantic-aware genetic operators for genetic programming and other heuristic methods will be proposed.

Research methodology

The scope of the research carried out in the project is separated into two groups. The first of them is closely related to the theoretical characteristics of analyzed phenomena and problems, on the other hand, the second is related to experimental analysis of addressed issues and algorithms developed during the work on first part of project.

In the theoretical part, the research is focused on the development of method of description of program behavior, in the way, that is robust and simultaneously simple to use in the algorithms of automatic programming from examples. The second important element of this analysis is an explanation of relation between changes in source code of program and their influence on the behavior of particular modules of the program. The analysis will also cover the work on understanding a way, how the geometric changes in program propagate themselves to the other parts of the program. The other tasks are related to the finding out how to direct these changes in a desired way and how to influence a size of the changes.

Algorithms of operators for genetic programming and fast heuristics, developed thanks to the theoretical analysis, will find their application in the second part of the project. In this part, an implementation of developed algorithms and a series of computational experiments are planned. The experiments are aimed at meticulous analysis of properties of the algorithms and an experimental confirmation of correctness of theoretical issues developed in the first part. The analysis of results will include comparison of efficiency of new and currently existing algorithms, and work on understanding phenomena occurring in a program during its creation. To evaluate achieved solutions, it is planned to make use of performance measures such as mean square error, size of generated programs, probability of finding optimum and time complexity. The significance of achieved differences will be verified using statistical tests.

Impact of the research project on the development of science, civilization and society

It is expected that the conducted research will contribute to the significant development of the automatic programming, which is the field of artificial intelligence. Thanks to the new methods of production of programs, there are expected the significant improvement of quality of programs and shortened time of the induction process. Consequently the programs built in that way should be able to solve even more complex tasks. The research is also focused on the explanation of phenomena occurring during the construction of program. It is expected, that the understanding of these phenomena will have noticeable impact on the development of systems that are autonomic or self-adapting to the changes in the environment.

Developed algorithms and formalisms and achieved results may easily become an inspiration to the other researchers, dealing with the related subject, what consequently should result in general development of this field of study, not without the influence to the development of the economy. The experimental software will be a side effect of carried out research. The software could become  a prototype of the other bigger system.

Publications

Tomasz P. Pawlak, Geometric Semantic Genetic Programming is Overkill, EuroGP 2016, Lecture Notes in Computer Science 9594:246-260, Springer, 2016.

Tomasz P. Pawlak, Krzysztof Krawiec, Semantic Geometric Initialization, EuroGP 2016, Lecture Notes in Computer Science 9594:261-277, Springer, 2016.

Tomasz P. Pawlak, Krzysztof Krawiec, Progress Properties and Fitness Bounds for Geometric Semantic Search Operators, Genetic Programming and Evolvable Machines 17(1):5-23, Springer, 2016.

Tomasz P. Pawlak, Competent Algorithms for Geometric Semantic Genetic Programming, PhD Thesis, Poznan University of Technology, 2015.

Tomasz P. Pawlak, Bartosz Wieloch, Krzysztof Krawiec, Review and Comparative Analysis of Geometric Semantic Crossovers, Genetic Programming and Evolvable Machines 16(3):351-386, Springer, 2015.

Tomasz P. Pawlak, Bartosz Wieloch, Krzysztof Krawiec, Semantic Backpropagation for Designing Search Operators in Genetic Programming, IEEE Transactions on Evolutionary Computation 19(3):326-340, IEEE Press, 2015.

Tomasz P. Pawlak, Combining Semantically-Effective and Geometric Crossover Operators for Genetic Programming, PPSN XIII, Lecture Notes in Computer Science 8672:454-464, Springer, 2014.

Tomasz P. Pawlak, Krzysztof Krawiec, Guarantees of Progress for Geometric Semantic Genetic Programming, Workshop on Semantic Methods in Genetic Programming, PPSN XIII, 2014.