Genetik Algoritma

Genetik algoritma, Holland (1975) tarafından önerilen ve Goldberg (1989) tarafından geniş kitleye yayılan popülasyon-tabanlı bir metaheuristiktir. Algoritma birden çok aday çözümü (birey) eş zamanlı tutar; her birey kromozom olarak kodlanır (ikili, tamsayı, permütasyon veya gerçek-değerli). Her iterasyonda üç temel operatör uygulanır: seçim (selection — rulet tekerleği, turnuva veya rank-tabanlı), çaprazlama (crossover — tek-nokta, çok-nokta, uniform, PMX veya OX permütasyon-için), ve mutasyon (bit-flip, swap, inversiyon). Uygunluk fonksiyonu (fitness) amaç fonksiyonundan türetilir ve seçim baskısını yönlendirir. Elitizm en iyi bireyleri korur; çeşitlilik koruma mekanizmaları (niching, crowding) erken yakınsamayı engeller. Yakınsama teorisi schema theorem (Holland 1975) üzerine kuruludur ancak No Free Lunch (Wolpert ve Macready 1997) hiçbir metaheuristiğin her problem üzerinde üstün olmadığını söyler. Çok amaçlı uzantı NSGA-II (Deb Pratap Agarwal Meyarivan 2002) Pareto-cephesi yaklaştırma için endüstri standardıdır. Permütasyon problemlerinde (TSP, scheduling) özel operatörler gerekir. Genetik algoritma global optimum garantisi vermez; iyi çözümleri makul sürede üretir ve karma tamsayı, kombinatoryal, siyah-kutu problemlerde tercih edilir. Referanslar: Goldberg (1989), Eiben ve Smith (2015).