Genetik Algoritmalar
Genetik Algoritmalar evrimsel hesaplamanın bir parçasıdır. Bu alan Yapay Zekâ’nın hızla gelişen bir dalıdır. Genetik algoritmalar Darwin’ in evrim teorisinden etkilenerek geliştirilmiştir. Basitçe açıklayacak olursak problemler evrimsel bir süreç kullanılarak bu süreç sonunda en iyi sonucu veren çözüme erişmeye çalışmaktadır. Başka bir ifadeyle çözüm evrimleşmektedir.
Evrimsel hesaplama 1960’larda I.Rechenberg’in Evrim Stratejileri (“Evolutionsstrategie”) adlı çalışmasında tanıtılmıştır. Daha sonra fikri diğer araştırmacılar tarafından geliştirilmiştir. Genetik algoritmalar John Holland tarafından icat edilmiş ve öğrencileri ve iş arkadaşları tarafından geliştirilmiştir. 1992 yılında John Koza, genetik algoritmaları kullanarak programları evrimleştirerek belli işleri yapmakta kullandı. Bu yönteme “genetik programlama” adını verdi. LISP dilinde programlar Ayrıştırma Ağaçları” (“Parse Tree”) şeklinde ifade edildiği için LISP diliyle geliştirilmiştir. Ayrıştırma Ağaçları genetik algoritmaların çalıştığı temel nesnedir.
Biyolojik Altyapı
Kromozom: Tüm yaşayan organizmalar hücrelerden oluşur. Her hücrede aynı kromozom kümeleri bulunur. Kromozomlar DNA dizileri olup, tüm organizmanın örneği olarak hizmet ederler. Bir kromozom gen adı verilen DNA bloklarından oluşur. Her gen belirli bir proteini kodlar. Basitçe, her genin, örneğin göz rengi gibi bir özelliği kodladığı söylenebilir. Bir özellik için olası ayarlar, (Örn. Mavi, Yeşil) alel olarak adlandırılır. Her gen kromozom üzerinde kendine ait bir konuma sahiptir. Bu konuma yörünge (“locus”) adı verilir.
Tüm genetik malzeme kümesine (tüm kromozomlar) genom adı verilir. Genom üzerindeki belli gen kümelerine genotip adı verilir. Genotipler, doğumdan sonra gelişmeyle fenotiplere - canlının göz rengi, zekâ v.b. fiziksel ve zihinsel özellikleri- dönüşür.
Tekrar Üretim: Tekrar üretim sırasında, yeniden birleşme (veya çaprazlama) ilk önce ortaya çıkar. Atalardan gelen genler yepyeni bir kromozom üretmek için bir araya gelirler. Bu yeni yaratılmış nesil daha sonra mutasyona uğrayabilir. Mutasyon DNA elemanlarının değişmesidir. Bu değişimler genellikle atalardan gen kopyalanması sırasındaki hatalardan kaynaklanır. Bir organizmanın uygunluğu (“fitness”) organizmanın yaşamındaki başarısıyla (hayatta kalma) ölçülür.
Arama Uzayı
Eğer bir problemi çözüyorsak, genellikle çözümler arasındaki en iyi olanını arıyoruz demektir. Mümkün tüm çözümlerin uzayına (istenen çözümün aralarından bulunduğu çözümler kümesi) arama uzayı (durum uzayı) adı verilir. Arama uzayındaki her nokta bir olası çözümü temsil eder. Her olası çözüm değeri (uygunluğu) ile problem için “işaretlenebilir”. Genetik algoritmalar yardımıyla arama uzayındaki olası çözümler arasından en iyi çözümü araştırırız.
Çözümü aramak, arama uzayında aşırı noktaları (azami veya asgari) aramak ile aynı anlamdadır. Zaman zaman arama uzayı iyi tanımlanmış olabilir, ama bu arama uzayında sadece bir kaç noktayı biliyor olabiliriz. GA kullanma sürecinde, çözüm bulma süreci diğer noktaları (olası çözümleri) evrim sürdükçe üretir.
Sorun, arama çok karmaşık olabilir. Nereden başlanacağı veya nereye bakılacağı bilinemeyebilir. Uygun çözümün bulunması için birçok yöntem vardır, fakat bu yöntemler en iyi çözümü üretmeyebilir. Bu yöntemlerin bazıları, tepe tırmanma (“hill climbing”), yasak arama (“tabu search”), benzetimli tavlama (“simulated annealing”) ve genetik algoritmalardır. Bu yöntemler sonucu bulunan çözümler genellikle iyi çözümler olarak kabul edilir, çünkü sık sık en iyiyi bulmak ve ispatlamak mümkün değildir.
NP-Zor (“NP-Hard”) Problemler: “Geleneksel” yolla çözülemeyecek problem sınıfına bir örnek NP (“Non-deterministic Polynomial Time”) problemlerdir.
Hızlı (Çokterimli) algoritmaların uygulanabildiği birçok görev vardır. Ancak algoritmik olarak çözülemeyen bazı problemler de vardır.
Çözüm bulmanın çok zor olduğu önemli problemler vardır, fakat çözüm bulununca bu çözümü kontrol etmek kolaydır. Bu gerçek “NP-Complete” Problemleri ortaya çıkarır. NP Nondeterministic Polynomial anlamına gelir ve bunun anlamı çözüm (Nondeterministic algoritma yardımıyla) “tahmin” edilebilir ve kontrol edilebilir.
NP Problemlere örnek olarak tatmin problemini, gezgin satıcı problemini veya sırt çantası problemini verebiliriz. Daha fazla örnek için “A Compendium of NP Optimization Problems” sitesi incelenebilir.
1.Bölüm
2.Bölüm
3.Bölüm
4.Bölüm
Hiç yorum yok:
Yorum Gönder