Yazan : Şadi Evren ŞEKER
Genetik programlama, yapay zeka çalışmaları altında kabul edilebilecek ve doğal süreçlerin ve mutasyon gibi genetik fonksiyonların bilgisayar problemlerine uygulanması ile sonuç elde etmeyi hedefleyen yaklaşımın adıdır. Belirli bir hedef fonksiyonun sonuca ulaşması için bilgisayar programlarının nasıl çalışması gerektiğini bulmayı hedefleyen makine öğrenmesi (machine learning) yaklaşımıdır denilebilir. Genetik algoritmaların (genetic algorithms) bir alt kolu olarak görülebilir.
Genetik programlama, bir ağaç üzerindeki farklı fonksiyonları, ağacın yapraklarında bulunan değerlere uygular. Hedef fonksiyon için (fitness function) en verimli fonksiyon dağılımını bulabilmek için ağacın düğümlerindeki fonksiyonların sırlaması ve içeriği ile ilgili değişikliklere gider.
Tarihsel Süreç
1954 yılında özellikle ikinci dünya savaşı sırasındaki çalışmalardan elde edilen ivme ile genetik algoritmaların simülasyon alanına uygulanması ile ilk uygulamaları başlamıştır. 1960 ve 1970’li yıllarda bir iyileştirme (optimisation) tekniği olarak uygulanmaya başlamıştır.
1964 yılında Fogel tarafından sonlu durum makinelerinin (finite state machine) analizi için genetik programlama yaklaşımının uygulandığı bilinmektedir. Bu uygulamalar, yöntemin markov karar süreçleri (markov decision process) gibi problemlere uygulanması fikrini doğurmuş ve 1985 yılında Cramer tarafından ilk modern uygulamaya benzeyen ağaç yaklaşımı getirilmiştir [1]. Bu yaklaşımın ardından Koza tarafından çalışma karmaşık iyileştirme problemleri ve arama problemlerine uygulanır hale getirilmiştir [2]. Koza’nın bir öğrencisi olan Giavelli tarafından bu yaklaşım daha sonra DNA zincirleri üzerine de genişletilmiştir [3].
1990’lı yıllara gelindiğinde o dönemki bilgisayarlar için hala hesaplama süresi (computation time) yoğun olduğundan genetik programlama sadece basit problemlere uygulanabilir haldeydi. Günümüzde ise CPU hızlarının artması ve quantum hesaplama (quantum computing) gibi işlem hızını arttırıcı yeniliklerle birlikte yöntem yeniden güncellik kazanmıştır [4].
Programın Temsili
Genetik programlama, bir programın hafızada ağaç yapısında tutulması temeline dayalıdır [5]. Ağaçlar özyineli (recursive) fonksiyonlar tarafından işlenmesi kolay yapılar olarak kabul edilir. Dolayısıyla tasarımı itibariyle özyineli olan diller (örn. Lisp gibi) bu yapıyı kolayca bünyesine alıp çözümleyebilir.
Genetik programlamanın özyineli olmayan halinden de bahsedilebilir. Doğrusal genetik programlama (linear genetic programming) olarak geçen bu yönteme göre yapı emirli programlama dillerine (imperative programming languages) uygun hale getirilmiştir. Örneğin açık kaynak kodlu olarak geliştirilen micro GP olarak isimlendirilen dil bu şekilde özyineli olarak verilen genetik programlama problemlerini çözümlemeden önce doğrusal hale getirmektedir [7].
Genetik programlamada evrimsel algoritmaların (evolutionary algorithms) temel fonksiyonları olan mutasyon ve çaprazlama (crossover) kullanılmaktadır.
Ayrıca genetik programlamanın özel bir uygulaması olan üst-genetik programlama (meta genetic programming) kavramından da bahsetmekte yarar vardır. Bu yaklaşımda bir programcı tarafından ön tanımlı bilgilerin girilmesi yerine, çaprazlama, mutasyon ve kromozom gibi değerlerin de algoritmanın kendisi tarafından evirilmesi ön görülmüştür.
Örnek
Örnek olarak aşağıda iki farklı denklemin üzerinde uygulanan çaprazlama görselleştirilmiştir [8]:
Resim kaynağı: geneticprogramming.com
Kaynaklar
[1] PROCEEDINGS OF AN INTERNATIONAL CONFERENCE ON GENETIC ALGORITHMS AND THEIR APPLICATIONS, A Representation for the Adaptive Generation of Simple Sequential Programs, Nichael Lynn Cramer
[2] Genetik Programlama web sayfası : genetic-programming.com
[3] The Genetic Coding of Behavioral Attributes in Cellular Automata. Artificial Life at Stanford 1994 Stanford, California, 94305-3079 USA.
[4] 36 Human-Competitive Results Produced by Genetic Programming, http://www.genetic-programming.com/humancompetitive.html, tarama 25 Ocak 2015
[5] Cramer, 1985, PROCEEDINGS OF AN INTERNATIONAL CONFERENCE ON GENETIC ALGORITHMS AND THEIR APPLICATIONS, A Representation for the Adaptive Generation of Simple Sequential Programs, Nichael Lynn Cramer
[6] Gentic Programming – An Introduction on On the automatic evolution of computer programs and its application Wolfgang Banzhaf, Peter Nordin, Robert E. Keller, Frank D. Francone, dpunkt, Heidelberg and Morgan Kaufmann, San Francisco, 1997
[7] MicroGP sayfası Source Forge : http://ugp3.sourceforge.net, tarama 26 Ocak 2015
[8] http://www.geneticprogramming.com/Tutorial/, tarama 25 Ocak 2015