Competent Algorithms for Geometric Semantic Genetic Programming
[ 1 ] Instytut Informatyki, Wydział Informatyki, Politechnika Poznańska | [ D ] phd student
[ 1 ] Instytut Informatyki, Wydział Informatyki, Politechnika Poznańska | [ P ] employee
PL Kompetentne algorytmy dla geometrycznego semantycznego programowania genetycznego
english
- automatic programming
- program induction
- evolutionary computation
- program inversion
- theory
- automatyczne programowanie
- indukcja programu
- obliczenia ewolucyjne
- odwracanie programu
- teoria
EN Genetic Programming is a machine learning technique for automatic induction of programs from examples, where each consists of program input and a target output. We embrace notions of semantics, semantic distance, neutrality, effectiveness, geometry under the common conceptual framework. We show that if fitness function is a metric, fitness landscape spanned over a space of all programs is a cone with the optimal program in the apex. We derive progress bounds of geometric operators for different combinations of fitness functions and semantic distances. We present a literature review of existing semantic methods. We propose an algorithm for semantic backpropagation and competent algorithms for population initialization, selection, mutation and crossover that are approximately geometric and effective. We find the optimal proportions of competent algorithms and compare them to the other methods in terms of fitness, generalization, geometry, effectiveness, size of created programs and time costs. The competent algorithms achieve better performance than the other methods in symbolic regression and not worse than the best other one in Boolean domain.
PL Programowanie Genetyczne jest techniką uczenia maszynowego dla automatycznej indukcji programów z przykładów, składających się z wejścia programu i docelowego wyjścia. Pojęcia semantyki, odległości semantycznej, neutralności, efektywności i geometryczności objęto wspólnymi ramami koncepcyjnymi. Pokazano, że jeśli funkcja dopasowania jest metryką, krajobraz dopasowania jest stożkiem z optymalnym programem w wierzchołku. Wywiedziono ograniczenia postępu geometrycznych operatorów dla różnych kombinacji funkcji dopasowania i odległości semantycznej. Zaprezentowano przegląd literatury istniejących metod semantycznych. Zaproponowano algorytm wstecznej propagacji semantyki oraz kompetentne algorytmy dla inicjacji, selekcji, mutacji i krzyżowania, które są w przybliżeniu geometryczne i efektywne. Znaleziono optymalne proporcje kompetentnych algorytmów i porównano je z innymi metodami w kategoriach dopasowania, generalizacji, geometryczności, efektywności, rozmiaru tworzonych programów i kosztów obliczeniowych. Algorytmy kompetentne mają lepsze osiągi od pozostałych metod w regresji symbolicznej, i nie gorsze niż najlepsza inna metoda w dziedzinie Boolowskiej.
174
computer sciences and computer science
computer science
DrOIN 1723
public
Jarosław Arabas
Warszawa, Polska
31.08.2015
polish
public
Andrzej Obuchowicz
Zielona Góra, Polska
31.08.2015
polish
public
dissertation
Poznań, Polska
21.09.2015
Rada Wydziału Informatyki Politechniki Poznańskiej
doktor nauk technicznych w dyscyplinie: informatyka, w specjalności: sztuczna inteligencja