Genetik Algoritmalar
 

Genetik Algoritmalar

Genetik algoritmalar, doðada gözlemlenen evrimsel sürece benzer bir þekilde çalýþan arama ve eniyileme yöntemidir. Karmaþýk çok boyutlu arama uzayýnda en iyinin hayatta kalmasý ilkesine göre bütünsel en iyi çözümü arar.
Genetik algoritmalarýn temel ilkeleri ilk kez Michigan Üniversitesi'nde John Holland tarafýndan ortaya atýlmýþtýr. Holland 1975 yýlýnda yaptýðý çalýþmalarý “Adaptation in Natural and Artificial Systems” adlý kitabýnda bir araya getirmiþtir. Ýlk olarak Holland evrim yasalarýný genetik algoritmalar içinde eniyileme problemleri için kullanmýþtýr.
Genetik algoritmalar problemlere tek bir çözüm üretmek yerine farklý çözümlerden oluþan bir çözüm kümesi üretir. Böylelikle, arama uzayýnda ayný anda birçok nokta deðerlendirilmekte ve sonuçta bütünsel çözüme ulaþma olasýlýðý yükselmektedir. Çözüm kümesindeki çözümler birbirinden tamamen baðýmsýzdýr. Her biri çok boyutlu uzay üzerinde bir vektördür.
Genetik algoritmalar problemlerin çözümü için evrimsel süreci bilgisayar ortamýnda taklit ederler. Diðer eniyileme yöntemlerinde olduðu gibi çözüm için tek bir yapýnýn geliþtirilmesi yerine, böyle yapýlardan meydana gelen bir küme oluþtururlar. Problem için olasý pekçok çözümü temsil eden bu küme genetik algoritma terminolojisinde nüfus adýný alýr. Nüfuslar vektör, kromozom veya birey adý verilen sayý dizilerinden oluþur. Birey içindeki her bir elemana gen adý verilir. Nüfustaki bireyler evrimsel süreç içinde genetik algoritma iþlemcileri tarafýndan belirlenirler.
Problemin bireyler içindeki gösterimi problemden probleme deðiþiklik gösterir. Genetik algoritmalarýn problemin çözümündeki baþarýsýna karar vermedeki en önemli faktör, problemin çözümünü temsil eden bireylerin gösterimidir. Nüfus içindeki her bireyin problem için çözüm olup olmayacaðýna karar veren bir uygunluk fonksiyonu vardýr. Uygunluk fonksiyonundan dönen deðere göre yüksek deðere sahip olan bireylere, nüfustaki diðer bireyler ile çoðalmalarý için fýrsat verilir. Bu bireyler çaprazlama iþlemi sonunda çocuk adý verilen yeni bireyler üretirler. Çocuk kendisini meydana getiren ebeveynlerin (anne, baba) özelliklerini taþýr. Yeni bireyler üretilirken düþük uygunluk deðerine sahip bireyler daha az seçileceðinden bu bireyler bir süre sonra nüfus dýþýnda býrakýlýrlar. Yeni nüfus, bir önceki nüfusta yer alan uygunluðu yüksek bireylerin bir araya gelip çoðalmalarýyla oluþur. Ayný zamanda bu nüfus önceki nüfusun uygunluðu yüksek bireylerinin sahip olduðu özelliklerin büyük bir kýsmýný içerir. Böylelikle, pek çok nesil aracýlýðýyla iyi özellikler nüfus içersinde yayýlýrlar ve genetik iþlemler aracýlýðýyla da diðer iyi özelliklerle birleþirler. Uygunluk deðeri yüksek olan ne kadar çok birey bir araya gelip, yeni bireyler oluþturursa arama uzayý içerisinde o kadar iyi bir çalýþma alaný elde edilir. Probleme ait en iyi çözümün bulunabilmesi için;

• Bireylerin gösterimi doðru bir þekilde yapýlmalý,
• Uygunluk fonksiyonu etkin bir þekilde oluþturulmalý,
• Doðru genetik iþlemciler seçilmeli.

Bu durumda çözüm kümesi problem için bir noktada birleþecektir. Genetik algoritmalar, diðer eniyileme yöntemleri kullanýlýrken büyük zorluklarla karþýlaþýlan, oldukça büyük arama uzayýna sahip problemlerin çözümünde baþarý göstermektedir. Bir problemin bütünsel en iyi çözümünü bulmak için garanti vermezler. Ancak problemlere makul bir süre içinde, kabul edilebilir, iyi çözümler bulurlar. Genetik algoritmalarýn asýl amacý, hiçbir çözüm tekniði bulunmayan problemlere çözüm aramaktýr. Kendilerine has çözüm teknikleri olan özel problemlerin çözümü için mutlak sonucun hýzý ve kesinliði açýsýndan genetik algoritmalar kullanýlmazlar. Genetik algoritmalar ancak;

• Arama uzayýnýn büyük ve karmaþýk olduðu,
• Mevcut bilgiyle sýnýrlý arama uzayýnda çözümün zor olduðu,
• Problemin belirli bir matematiksel modelle ifade edilemediði,
• Geleneksel eniyileme yöntemlerinden istenen sonucun alýnmadýðý alanlarda etkili ve kullanýþlýdýr.

Genetik algoritmalar parametre ve sistem tanýlama, kontrol sistemleri, robot uygulamalarý, görüntü ve ses tanýma, mühendislik tasarýmlarý, planlama, yapay zeka uygulamalarý, uzman sistemler, fonksiyon ve kombinasyonel eniyileme problemleri að tasarým problemleri, yol bulma problemleri, sosyal ve ekonomik planlama problemleri için diðer eniyileme yöntemlerinin yanýnda baþarýlý sonuçlar vermektedir.

Diðer yöntemlerden farký

1. Genetik algoritmalar problemlerin çözümünü parametrelerin deðerleriyle deðil, kodlarýyla arar. Parametreler kodlanabildiði sürece çözüm üretilebilir. Bu sebeple genetik algoritmalar ne yaptýðý konusunda bilgi içermez, nasýl yaptýðýný bilir.
2. Genetik algoritmalar aramaya tek bir noktadan deðil, noktalar kümesinden baþlar. Bu nedenle çoðunlukla yerel en iyi çözümde sýkýþýp kalmazlar.
3. Genetik algoritmalar türev yerine uygunluk fonksiyonunun deðerini kullanýr. Bu deðerin kullanýlmasý ayrýca yardýmcý bir bilginin kullanýlmasýný gerektirmez.
4. Genetik algoritmalar gerekirci kurallarý deðil olasýlýksal kurallarý kullanýr.

GENETÝK ALGORÝTMA

Ýnsanýn genetik yapýsý dört harfle betimlediðimiz dört yapý taþýnýn milyarlarca kere yan yana gelmesinden oluþuyor. Yani bunu dört harfli alfabe ile yazýlmýþ bir kitaba benzetmek mümkün. Ama bu kitabýn çok geniþ bir mesajý var. Yani beþ yüz bin A4 kaðýdýna yazarsanýz tutuyor. Eðer o monokülü tek baþýna uzatýrsan bir buçuk metreyi aþan bir uzunluða sahip. Ýþte ama iki mikron çapýnda bir çekirdeðin içine giriyor ve bunun üzerinde asýl önemli olan yaklaþýk 100 bin gen dediðimiz anlaþýlabilir mesaj var. Yani bunar bizim gözümüzün renginden tabiki çevresel faktörleri de göz önüne alarak boyumuzun ne kadar olacaðýna, kiþiliðimizden, bir þeker yediðimiz zaman pankreasýmýzýn, karaciðerimizin nasýl çalýþacaðýna kadar yaþamýmýzýn bütün özelliklerini kotluyorlar. Ýþte bir çok, daha doðrusu bütün hastalýklarýn temelindeki buradaki genler yatýyor. Canlýnýn yaþamýndaki bütün olaylarýn da temelinde yattýðý gibi. Þimdi bunlar çözülmeye baþlanýlacak. Artýk kanser cerrahisi yerine bir süre sonra kanser gen terapisi alýnacak. Kanser genetik bir hastalýk. Bir çok kalýtsal hastalýðýn çözümü, tedavisi bulunacak.

Genetik Algoritmalar

Genel Bilgiler

Modern bilimde veri kümeleri arasýndaki iliþkileri, tecrübelerden de faydalanarak belirlemek, üzerinde çokça çalýþýlan ve araþtýrýlan bir taslaktýr. Günümüzdeki araþtýrma konularý ve problemleri eskiye nazaran çok daha karýþýktýr. Bu karýþýklýk problemi etkileyen parametre sayýsýnýn fazlalýðýndan ve problemin çözüm kümesinin boyutunun büyümesinden kaynaklanmaktadýr. Bundan dolayý elinizdeki verilerin analizi ve sonucu bu verilerden kestirme yöntemlerinin önemi araþtýrmacýlar için gittikçe artmaktadýr. Faydalý iyi bir veri analiz yöntemi þu kriterlere göre deðerlendirilebilir. Ýyi tahmin veya sonucu kestirmeye yönelik olmalý, sistemin içindeki her bir mekanizmanýn analiz edilebilmesi ve sonuçlarýn mümkün olabilecek çözüm uzayý kümesinde olmasýdýr. Bu tür problemlerdeki çözüm kümesinin büyüklüðü bir taraftan elde edilen çözümün deðerlendirilmesinde zorluk çýkarýrken diðer taraftan lineer yöntemlerin uygulanmasýný imkansýz kýlacaktýr.
Geçmiþte araþtýrmacýlar tarafýndan çalýþýlan, parametreler arasýndaki iliþkiler, genelde deneme yoluyla, zor olan örneklerde karmaþýk veya sabit olmayan iliþkiler için yapýlmýþ; fakat parametre sayýsý artýnca çözümsüzlük veya elde edilen çözümü deðerlendirememe problemini getirmiþtir. Ýstatistiksel yöntemler, araþtýrmacýlara iliþkileri bulmada faydalý olan ilk araçlardandýr. Ýstatistiksel yöntemlerde:

1) Verinin normal toplandýðý,
2) Verinin eþitlik iliþkisinin belirli bir formda olmasý (ör: lineer, quadratic, veya polinomsal),
3) Deðiþkenlerin baðýmsýz olmasý gerekir.

Eðer problem bu kriterleri saðlarsa, istatistiksel yöntem iliþkileri bulmada faydalý olabilir. Oysa gerçek hayatta problemler bu kriterleri nadiren saðlarlar.
Modern sonuç kestirme veya sonuç geliþtirme algoritmalarý bu kriterlerle sýnýrlandýrýlamazlar. Neural network (Yapay sinir aðlarý) veya Artificial intelligence (Yapay zeka) teknikleri karmaþýk iliþkileri kapsamayabilir; fakat mekanizmanýn önemli iliþkilerini tanýmlayabilen güçlü tahmin modelleridir. Buna raðmen, diðer bir teknik Genetik Algoritma ve Genetik Programlama teknikleri çok daha güçlüdürler ve karýþýk çözüm uzayýný daha da geniþ bulabilirler. Baðýmsýz olan veri ve parametreler ile mekanizmanýn iliþkilerini bulmada baþarýlý örnekleri vardýr.
Genetik Algoritma, biyolojik bir sistemin, çevresine adaptasyonunda kullandýðý metodun örneklendirilmesidir. Bilgisayarda, bu tür çok parametreli optimum bulma problemlerine ve makine öðrenme problemlerine çözüm modeli olarak alýnabilir.
Doðal adaptasyondan esinlenen GA’ nýn basit olarak iskeleti:

a) Bireyin bulunduðu ortamda hayatta kalmak için, kendi kendisini deðiþtirerek ortama uygun hale gelmesi,
b) Bu adaptasyon boyunca, yeni üretilecek nesillere, bu özellikler ile birlikte mümkün olabilecek daha çok deðiþim aktarýlarak, bireylerin daha çok uyumlu hale getirilmesi olarak özetlenebilir.

Mühendislikte, bilimde, ekonomide, finansmanda v.s. deki problemleri çözmede kullanýlan arama teknikleri, hesap-temelli ve direkt arama teknikleri olarak sýnýflandýrýlabilir. Eðer problemler sayýsal veya analitik olarak iyi tanýmlanabiliyorsa veya çözüm uzayý küçük ve tek ise, hesap temelli arama tekniði daha iyi çalýþýr. Buna raðmen hesap-temelli teknik mühendislik optimizasyolarýn da gittikçe artan optimum bulma fonksiyonlarýnda oldukça zayýf kalýr. Sadece fonksiyon bilgisi gerekli olan Doðrudan arama tekniði, hesap-temelli teknikten daha kýsa sürede iþler ve daha etkilidir. Doðrudan arama tekniðinin esas problemi, ulaþýlabilen bilgisayar zamaný ile optimal çözümün kesinliði arasýndaki baðýntýdýr (Genetic Algorithms in Search, Optimization, and Machine Learning, Goldberg, 1989).

Genetik Algoritmanýn Tarihçesi

Michigan Üniversitesinde psikoloji ve bilgisayar bilimi uzmaný olan John Holland bu konuda ilk çalýþmalarý yapan kiþidir. Mekanik öðrenme (machine learning) konusunda çalýþan Holland, Darwin’in evrim kuramýnda etkilenerek canlýlarda yaþanan genetik süreci bilgisayar ortamýnda gerçekleþtirmeyi düþündü. Tek bir mekanik yapýnýn öðrenme yeteneðini geliþtirmek yerine böyle yapýlarda oluþan bir topluluðun çoðalma, çiftleþme, mutasyon, vb. genetik süreçlerden geçerek baþarýlý (öðrenebilen) yeni bireyler oluþturabildiðini gördü. Araþtýrmalarýný, arama ve optimumu bulma için, doðal seçme ve genetik evrimden yola çýkarak yapmýþtýr. Ýþlem boyunca, biyolojik sistemde bireyin bulunduðu çevreye uyum saðlayýp daha uygun hale gelmesi örnek alýnarak, optimum bulma ve makine öðrenme problemlerinde, bilgisayar yazýlýmý modellenmiþtir.
Çalýþmalarýnýn sonucunu açýkladýðýný kitabýnýn 1975’te yayýnlanmasýndan sonra geliþtirdiði yöntemin adý Genetik Algoritmalar (ya da kýsaca GA) olarak yerleþti. Ancak 1985 yýlýnda Holland’ýn öðrencisi olarak doktorasýný veren David E. Goldberg adlý inþaat mühendisi 1989 da konusunda bir klasik sayýlan kitabýný yayýnlayana dek genetik algoritmalarýn pek pratik yararý olmayan bir araþtýrma konusu olduðu düþünülüyordu. Ýlk olarak Hollanda’ da makine öðrenme sistemlerine yardýmcý olarak kullanýlmýþ daha sonra De Jong Goldberg ve diðerleri tarafýndan analiz edilmiþtir. Goldberg, GA’nýn çok sayýda kollara ayrýlmýþ gaz borularýnda, gaz akýþýný düzenlemek ve kontrol etmek için uygulamasýný tanýmlamýþtýr. Ayrýca kendisinin kullandýðý makine öðrenmesi, nesne tanýma, görüntü iþleme ve iþlemsel arama gibi alanlarda kullanýldýðýný vurgulamýþtýr.
Goldberg’in gaz boru hatlarýnýn denetimi üzerine yaptýðý doktora tezi ona sadece 1985 National Science Foundation Genç Araþtýrmacý ödülünü kazandýrmakla kalmadý, genetik algoritmalarýn pratik kullanýmýnýn da olabilirliðini kanýtladý. Ayrýca kitabýnda genetik algoritmalara dayalý tam 83 uygulamaya yer vererek GA’nýn dünyanýn her yerinde çeþitli konularda kullanýlmakta olduðunu gösterdi.

Kuramsal Temeller

Genetik Algoritmanýn Tanýmý

Genetik algoritma, doðadaki evrim mekanizmasýný örnek alan bir arama metodudur ve bir veri grubundan özel bir veriyi bulmak için kullanýlýr. Genetik algoritmalar 1970’lerin baþýnda John Holland tarafýndan ortaya atýlmýþtýr. Genetik Algoritmalar, Evrimsel Genetik ve Darwin’in Doðal seleksiyonuna benzerlik kurularak geliþtirilmiþ “iteratif ”, ihtimali bir arama metodudur.
Genetik algoritmalar doðada geçerli olan en iyinin yaþamasý kuralýna dayanarak sürekli iyileþen çözümler üretir. Bunun için “iyi”nin ne olduðunu belirleyen bir uygunluk (fitness) fonksiyonu ve yeni çözümler üretmek için yeniden kopyalamadeðiþtirme (mutation) gibi operatörleri kullanýr. Genetik algoritmalarýn bir diðer önemli özelliði de bir grup çözümle uðraþmasýdýr. Bu sayede çok sayýda çözümün içinden iyileri seçilip kötüleri elenebilir.
Genetik algoritmalarý diðer algoritmalardan ayýran en önemli özelliklerden biri de seçmedir. Genetik algoritmalarda çözümün uygunluðu onun seçilme þansýný arttýrýr ancak bunu garanti etmez. Seçim de ilk grubun oluþturulmasý gibi rasgeledir ancak bu rasgele seçimde seçilme olasýlýklarýný çözümlerin uygunluðu belirler.
Genetik Algoritmalarý (GA) diðer metodlardan ayýran noktalar þu þekilde sýralanabilir:
(recombination),

• GA , sadece bir arama noktasý deðil , bir grup arama noktasý (adaylar ) üzerinde çalýþýr. Yani arama uzayýnda , yerel deðil global arama yaparak sonuca ulaþmaya çalýþýr. Bir tek yerden deðil bir grup çözüm içinden arama yapar.
• GA , arama uzayýnda bireylerin uygunluk deðerini bulmak için sadece “amaç - uygunluk fonksiyonu” (objective-fitness function ) ister. Böylelikle sonuca ulaþmak için türev ve diferansiyel iþlemler gibi baþka bilgi ve kabul kullanmaya gerek duymaz.
• Bireyleri seçme ve birleþtirme aþamalarýnda deterministik kurallar deðil “ olasýlýk kurallarý” kullanýr.
• Diðer metodlarda olduðu gibi doðrudan parametreler üzerinde çalýþmaz. Genetik Algoritmalar, optimize edilecek parametreleri kodlar ve parametreler üzerinde deðil, bu kodlar üzerinde iþlem yapar. Parametrelerin kodlarýyla uðraþýr. Bu kodlamanýn amacý, orjinal optimizasyon problemini kombinezonsal bir probleme çevirmektir.
• Genetik algoritma ne yaptýðý konusunda bilgi içermez, nasýl yaptýðýný bilir. Bu nedenle kör bir arama metotudur.
• Olasýlýk kurallarýna göre çalýþýrlar. Programýn ne kadar iyi çalýþtýðý önceden kesin olarak belirlenemez. Ama olasýklýkla hesaplanabilir.
• GA, kombinezonsal bir atama mekanizmasýdýr.

Genetik Algoritmalar, yeni bir nesil oluþturabilmek için 3 aþamadan geçer:

1. Eski nesildeki her bir bireyin uygunluk deðerini hesaplama.
2. Bireyleri, uygunluk deðerini göz önüne alarak (uygunluk fonksiyonu ) kullanýlarak seçme.
3. Þeçilen bireyleri, çaprazlama (crossover), mutasyon (mutation) gibi genetik operatörler kullanarak uyuþturma.

Algoritmik bakýþ açýsýndan bu aþamalar, mevcut çözümleri lokal olarak deðiþtirip birleþtirmek olarak görülebilir.
Genetik Algoritmalar; baþlangýçta bilinmeyen bir arama uzayýndan topladýðý bilgileri yýðýp, daha sonraki aramalarý alt arama uzaylarýna yönlendirmek için kullanýlýr.

Kodlama Yöntemleri

Kodlama planý Genetik algoritmanýn önemli bir kýsmýný teþkil eder. Çünkü bu plan bilginin çerçevesini þiddetle sýnýrlayabilir. Öyle ki probleme özgü bilginin bir kromozomsal gösterimiyle temsili saðlanýr. Kromozom genellikle, problemdeki deðiþkenlerin belli bir düzende sýralanmasýdýr. Kromozomu oluþturmak için sýralanmýþ her bir deðiþkene “gen” adý verilir. Buna göre bir gen kendi baþýna anlamlý genetik bilgiyi taþýyan en küçük genetik yapýdýr. Mesela; 101 bit dizisi bir noktanýn x-koordinatýnýn ikilik düzende kodlandýðý gen olabilir. Ayný þekilde bir kromozom ise Bir ya da daha fazla genin bir araya gelmesiyle oluþan ve problemin çözümü için gerekli tüm bilgiyi üzerinde taþýyan genetik yapý olarak tanýmlanabilir. Örnek vermek gerekirse; 100011101111 x1, y1, x2, y2 koordinatlarýndan oluþan iki noktanýn konumu hakkýnda bize bilgi verecektir.
Bu parametreleri kodlarken dikkat edilmesi gereken en önemli noktalardan biri ise kodlamanýn nasýl yapýldýðýdýr. Örnek olarak kimi zaman bir parametrenin doðrusal ya da logaritmik kodlanmasý GA performansýnda önemli farka yol açar.
Kodlamanýn diðer önemli bir hususu ise kodlama gösteriminin nasýl yapýldýðýdýr. Bu da yeterince açýk olmamakla birlikte GA performansýný etkileyen bir noktadýr. Bu konu sonradan anlatýlacaktýr.

Uygunluk Teknikleri

Baþlangýç topluluðu bir kez oluþturulduktan sonra evrim baþlar. Genetik algoritma bireylerin uygunluk ve iyiliklerine göre ayrýlýp fark edilmesine gerek duyar. Uygunluk, topluluktaki bir kýsým bireyin problemi nasýl çözeceði için iyi bir ölçüdür. O problem parametrelerini kodlamayla ölçülür ve uygunluk fonksiyonuna giriþ olarak kullanýlýr. Yüksek ihtimalle uygun olan bu üyeler tekrar üreme, çaprazlama ve mutasyon operatörleriyle seçilirler.
Bazý problemler için bireyin uygunluðu, bireyden elde edilen sonuç ile tahmin edilen sonuç arasýndaki hatadan bulunabilir. Daha iyi bireylerde bu hata sýfýra yakýn olur. Bu hata genellikle, giriþin tekrar sunulacak kombinezonlarýnýn ortalamasý veya toplamýyla hesaplanýr (deðerler deðiþkenlerden baðýmsýzdýr). Beklenen ve üretilen deðer arasýndaki korelasyon etkeni, uygunluk deðerini hesaplamak için kullanýlabilir. (Koza 1994).
Objektif fonksiyonu (Deðerlendirme fonksiyonu) her bir kromozomun durumunu deðerlendirmek için mekanizmayý saðlayan ana bir kaynaktýr. Bu GA ve sistem arasýnda önemli bir baðlantýdýr. Fonksiyon giriþ olarak kodu çözülmüþ þekilde kromozom (Phenotype) alýr ve kromozomun performansýna bir ölçü olarak bir objektif deðer üretir. Bu diðer kromozomlar için de yapýldýktan sonra yapýldýktan sonra bu deðerler kullanýlarak, uygun deðerler uygunluk fonksiyonuyla hesaplanýp belli bir düzende planlanýr. Bu planlamayý saðlayan ve uygunluk teknikleri olarak bilinen birçok yöntem vardýr. Çoðu ortak kullanýlan bu yöntemler þunlardýr:

1. Pencereleme

Populasyonda en kötü kromozomun objektif deðerinin Vw olduðunu kabul edersek her bir kromozomun i ve en kötü kromozomu arasýnda farkla orantýlý bir uygunluk deðeri fi atanabilir. Bu durum matematiksel olarak þu þekilde ifade edilebilir:
Burada Vi kromozom i ‘nin objektif deðeri ve c ise uygunluðun negatif çýkmamasýný saðlayacak kadar büyük bir sayýdýr. Eðer bir maksimizasyon problemiyle karþýlaþýlýrsa denklemde pozitif iþaret kabul edilir. Diðer yandan minimizasyon gerekliyse negatif iþaret kabul edilir.

2. Lineer Normalizasyon

Objektif fonksiyonun maksimize veya minimize durumuna göre kromozomlar objektif deðerin artma veya azalma düzenine göre sýralanýr. En iyi kromozoma rastgele en iyi bir uygunluk fbest atanarak sýralanmýþ düzende diðer kromozomlarýn uyguluðu lineer bir fonksiyonla bulunur:


Burada d eksilme oranýdýr. Bu teknik populasyonun ortalama objektif deðerini ortalama uygunluk içerisinde ayrýntýlarýyla planlamayý saðlar.
Bu iki teknikten baþka kullanýcýnýn kendisinin belirleyeceði baþka yöntemler de mevcuttur.

Genetik Operatörler

Kullanýlan genetik operatörler, varolan nesil (population) üzerine uygulanan iþlemlerdir. Bu iþlemlerin amacý, daha iyi özelliðe sahip yeni nesiller üretmek ve arama algoritmasýnýn alanýný geniþletmektir.
3 tip genetik operatör vardýr:

1. Seleksiyon (Selection / Reproduction)
2. Çaprazlama (Crossover)
3. Mutasyon (Mutation)

1. Seleksiyon (Selection / Reproduction)

Yeniden üretme operatörü, hazýr topluluktan uygun olan bireylerin seçilmesi ve bunlarýn sonraki topluluða kopyalanarak hayatta kalmalarýyla ilgilidir. Seçim modeli, tabiatýn hayatta kalabilmek için uygunluk mekanizmasý modelidir. Yeniden üretme iþleminde, bireyler onlarýn uygunluk fonksiyonlarýna göre kopya edilirler. Uygunluk fonksiyonu, mümkün olduðu kadar yükseltilmesi gereken bazý faydalý ve iyi ölçülerdir. Topluluk uzayýndaki her bir bireyin uygunluklarý baz alýnarak ne kadar sayýda kopyasýnýn olacaðýna karar verilir. En iyi bireylerden daha fazla kopya alýnýr, en kötü bireylerden kopya alýnmaz. Bu hayatta kalmak için uygunluk stratejisinin GA ya saðladýðý avantajdýr.

1.1. Rulet Tekerleði Seçimi

GA tarafýndan üretilen döllerin sayýsýný belirlemede birkaç yol vardýr. Birbirine yakýn parametrelerden kaçýnmak için uygun bir seçim metodu kullanýlmalýdýr. Tekrar üretme baþlangýcýnda basit bir yöntem “roulette wheel selection” (rulet tekerleðiyle seçim)'e göre bireylerin uygunluk deðerlerini bir rulet tekerleðinde hazýrlar. Rasgele tekerleðin döndürülmesinden sonra, bireyin bir sonraki nesil için seçilmesi, tekerlek üzerinde kapladýðý alanla doðrudan baðlantýlýdýr. Bu yöntem düþük uygunluða sahip bireylere de seçilme hakký verir.

Fi: i. Eleman için uygunluk deðeri
N: Birey sayýsý

Ebeveynler uygunluklarýna göre seçilirler. Kromozomlar ne kadar iyiyse, o kadar seçilme þanslarý fazladýr. Þöyle bir rulet tekerleði düþünün.

Sonra bir bilye atýlýr ve kromozomu seçer. Daha fazla uygunluðu olan kromozomlar daha çok seçilecektir. Bu aþaðýdaki algoritmayla simule edilebilir:
1. [Sum] Populasyondaki tüm kromozom uygunluklarý toplamýný hesapla – toplam S.
2. [Select] (0,S) – r aralýðýndan rastgele bir sayý üret.
3. [Loop] Populasyon boyunca git ve uygunluklarý 0’dan toplam s ‘e kadar topla. Eðer toplam s , r ‘den büyükse dur ve olduðun yerdeki kromozomu geri gönder.
Tabii ki 1. basamak her populasyon için bir kez performe edilir.

1.2 Rank Seçimi

Yukarýdaki seçim eðer uygunluklar çok fazla deðiþiyorsa bazý problemlere yol açacaktýr. Mesela en iyi kromozom uygunluðu tüm rulet tekerleðinin %90’ý ise diðer kromozomlarýn seçilme þanslarý çok az olacaktýr. Rank seçimi önce populasyonu sýralar ve daha sonra her kromozom uygunluðu bu sýralamadan sonra alýr. En kötüsü 1 uygunluðunu alacak, ikinci en kötü 2 ve en iyisi N uygunluk deðerini alacak ki N de populasyondaki kromozom sayýsýdýr.
Sayýlarý düzenlemek için uygunluklarý deðiþtirdikten sonra durumun nasýl deðiþtiðini aþaðýdaki þekilde görebilirsiniz:

Bundan sonra her kromozomun seçilme hakký olacaktýr. Fakat bu metod daha yavaþ gibidir, çünkü en iyi kromozomlar diðerlerinden fazla deðiþiklik göstermez.

1.3 Steady-State Seçimi (Kararlý Hal)

Bu yerine geçme yöntemleri olarak da adlandýrýlabilirler. Bu ebeveynleri seçmek için kýsmi bir metod deðildir. Bu seçimin ana fikri kromozomlarýn büyük kýsmý bir sonraki nesilde hayatta kalmak zorundadýr.
O zaman GA þu þekilde çalýþýr. Yeni çocuklar oluþturmak için her nesilde güzel iyi uygunluklu birkaç kromozom seçilir. Sonra kötü düþük uygunluklu bazý kromozomlar atýlýr ve yeni çocuk onun yerine yerleþtirilir. Populasyonun geri kalan kýsmý yeni nesilde hayattadýr. Yani kýsaca bu yöntemde alt populasyon oluþturulduktan sonra uygunluklar hesaplanýr, en kötü kromozomlar yerlerini baþlangýç populasyonundaki en iyi kromozomlara terk eder.

1.4 Elitizm

Bu da yerine geçme metodu olarak bilinir. Elitizm fikriyle zaten daha önce tanýþýlmýþtý. Mutasyon ve çaprazlamalarla yeni nesil oluþtururken en iyi kromozomu seçmek için büyük bir þansa sahip oluruz.
Elitizm en iyi kromozomu ya da birkaç en iyi kromozomlarý yeni nesile kopyalama metodunun adýdýr. Gerisi klasik yolla yapýlýr. Elitizm çok hýzlý bir þekilde GA’ nýn performansýný arttýrýr çünkü en iyi bulunan çözümü kaybetmeyi önler.
Ayrýca Musbaka ve Oranlama yöntemleri de vardýr.

2. Çaprazlama (Crossover)

Amaç, ana (parent) kromozom genlerinin yerini deðiþtirerek çocuk (child) kromozomlar üretmek ve böylece varolan uygunluk deðeri yüksek olan kromozomlardan, uygunluk deðeri daha yüksek olan kromozomlar elde etmektir. Burada önemli olan bir konuda , çaprazlama noktasýnýn çaprazlamadan elde edilecek çocuk kromozomlarýn uygunluk deðerleri üzerindeki etkisidir. Bu iþlem yapýlýrken her zaman sonuçlar önceden tahmin edilemez. Bu yüzden geliþigüzel yapýlan deðiþikliklerde sonucun mükemmelliðe doðru gitmesi için belirli kriterler bulmak için çalýþýlýr. Kromozomlardaki genlerin yapýsý ve etkileri araþtýrýlarak, bu genlere yapýlan müdahalelerle bireye bazý iyi özellikler kazandýrýlabilir. Çaprazlamadan elde edilecek çocuk kromozomlarýn uygunluk deðeri bir önceki ana kromozomlardan daha yüksek olmayabilir.
Tablo 1.'de biyolojik çaprazlamaya bir örnek verilmiþtir:

Benzer þekilde GA, çaprazlama iþlemini uygunluk deðerlerine göre seçilmiþ iki ebeveyn bireyden, iyi özellikte yeni bireyler elde etmek için kullanýr. Çaprazlama rasgele seçilmiþ iki çift katarýn içindeki alt küme bilgilerin deðiþtirilmesi iþlemdir. Kendi içindeki bilgilerini 1. Pozisyondan itibaren, katarýn uzunluðunun bir eksik pozisyonuna kadar, aradaki bilgi kýsmen karþýlýklý bireyler arasýnda yer deðiþtirilir.
Eðer iki bireyin problemin çözümünde bazý etkileri var ise onlarýn bir parçalarý faydalý, iyi veya uygun nitelenebilecek bilgi taþýmaktadýr. Çaprazlama belki problemin çözümünde, bu faydalý bilgileri birleþtirerek, daha çok etkili yeni bireyler üretecektir. Tablo 2.'de ikili kodda verilmiþ bir katarda, örnek 2 bitlik bir çaprazlama iþlemi verilmiþtir.


Çaprazlamadan baþka tersinme denilen bir üreme yöntemi daha vardýr. Holland bunu tanýmlayarak kromozom uzunluðu çok olan bireylerde çaprazlama yerine bunun kullanýlmasýný performans açýsýndan önermiþtir. Tersinme (inversion) bir kromozomu oluþturan genlerden ardýþýk bir grubun kendi içerisinde birbirleriyle yer deðiþtirerek ters dizilmeleridir. Örneðin:011110101 kromozomu (her genin bir bit olduðu varsayýmý ile) 5. ve 8. Gen kromozomlarý arasýnda tersindiðinde ortaya 011101011 kromozomu çýkar.
Tersinme genellikle kromozom uzunluðu fazla olan populasyonlara uygulanýr.

3. Mutasyon (Mutation)

Amaç, varolan bir kromozomun genlerinin bir ya da birkaçýnýn yerlerini deðiþtirerek yeni kromozom oluþturmaktýr. Yeniden ve sürekli yeni nesil üretimi sonucunda belirli bir süre sonra nesildeki kromozomlar birbirlerini tekrarlama konumuna gelebilir ve bunun sonucunda farklý kromozom üretimi durabilir veya çok azalabilir. Ýþte bu nedenle nesildeki kromozomlarýnýn çeþitliðini artýrmak için kromozomlardan bazýlarý mutasyona uðratýlýr. Açýklandýðý gibi mutasyonun birinci maksadý bir populasyonun içindeki deðiþimi tanýmlamaktýr. Mutasyon populasyonlarda çok önemlidir. Öyle ki burada ilk populasyon mümkün olan tüm alt çözümlerin küçük bir alt kümesi olabilir ve ilk populasyondaki tüm kromozomlarýn önemli biti sýfýr olabilir. Halbuki o bitin problemin çözümü için 1 olmasý gerekebilir ve bunu da çaprazlama düzeltemeyebilir. Bu durumda o bit için mutasyon kaçýnýlmazdýr. Genellikle önerilen mutasyon oraný 0.005/bit/generasyondur. Bu iþlem çaprazlamadan sonra gelir. Mutasyonun yapýlýp yapýlmayacaðýný bir olasýlýk testi belirler. Örneðin yeni neslin ortalama uygunluðu £ Eski neslin ortalama uygunluðu ise; x. Kromozomun y. Bitini deðiþtir denilebilir. Bu yeni çocuðu rast gele deðiþtirir. Ýkili kodlama için rast gele seçilmiþ bitlerden 0’larý 1, 1’leri 0 yaparýz.
Tablo 3. bit katarýnda hazýrlanmýþ bir mutasyon operatörünü göstermektedir:

Genetik Algoritmalarýn Çalýþma Prensibi

Genetik algoritmanýn çalýþmasýný þöyle özetleyebiliriz:


Ýþlemleri adým adým açýklamak gerekirse:

Adým-1.
Bu adýma toplumda bulunacak birey sayýsýný belirleyerek baþlanmaktadýr. Kullanýlacak sayý için bir standart yoktur. Genel olarak önerilen 100-300 aralýðýnda bir büyüklüktür. Büyüklük seçiminde yapýlan iþlemlerin karmaþýklýðý ve aramanýn derinliði önemlidir. Toplum bu iþlemden sonra rasgele oluþturulur.Kromozomun temsil ettiði çözüm hakkýnda bilgiyi herhangi bir yollla içermesi gerekir. En çok kullanýlan kodlama ikili stringtir.

Tablo 2. Ýkili kodlama

Her kromozom bir ikili stringe sahiptir. Bu stringteki her bit çözümün belli karakteristiðini temsil eder, veya tüm string bir sayýyý temsil eder. Tabiki bir çok kodlama yolu vardýr. Bu daha çok çözülen probleme baðlýdýr. Mesela tam sayý veya reel sayý olarak kodlanabilir, bazen de bazý permutasyonlarý kodlamak kullanýþlý olabilir.

1. Permutasyon kodlama

Düzenleme problemlerinde kullanýlýr. Satýcý gezici problemi veya Task Ordering Probleminde. Burada her kromozom sayýlarý bir sýrada temsil eden bir sayýlar stringidir.

Tablo 3. Permutasyon kodlamalý kromozom örnekleri

Permutasyon kodlama sadece ordering problemleri için kullanýþlýdýr.

2. Deðer kodlama

Reel sayýlar gibi komplike deðerlerin kullanýldýðý problemlerde direk deðer kodlanmasý kullanýlabilir. Bu tip problemler için ikili kodlama iþi çok zordur.

Bu bazý özel problemler için çok iyidir. Diðer taraftan bu tip kodlama için probleme özel yeni bazý mutasyon ve çaprazlamalar geliþtirmek lazýmdýr.

3. Aðaç kodlama

Bu, geliþen deðiþen programlar veya ifadeler için kullanýlýr (Genetik programlama). Aðaç kodlamada her her kromozom bazý nesnelerin, mesela fonksiyonlar ya da programlama dilindeki komutlar gibi, bir aðacýdýr þeklinde verilebilir.

LISP programlama dili bunu çok kullanýr

Adým-2.
Kromozomlarýn ne kadar iyi olduðunu bulan fonksiyona uygunlukfonksiyonu denir. Bu fonksiyon iþletilerek kromozomlarýn uygunluklarýnýn bulunmasýna ise hesaplama (evaluation) adý verilir. Bu fonksiyon genetik algoritmanýn beynini oluþturmaktadýr. Genetik algoritmada probleme özel çalýþan tek kýsým bu fonksiyondur. Uygunluk fonksiyonu kromozomlarý problemin parametreleri haline getirerek onlarýn bir bakýma þifresini çözmektedir (decoding), sonra bu parametrelere göre hesaplamayý yaparak kromozomlarýn uygunluðunu bulur. Çoðu zaman genetik algoritmanýn baþarýsý bu fonksiyonun verimli ve hassas olmasýna baðlý olmaktadýr.

Adým-3.
Kromozomlarýn eþlenmesi kromozomlarýn uygunluk deðerlerine göre yapýlýr. Bu seçimi yapmak için rulet tekerleði seçimi (roulette wheel selection) , turnuva seçimi (Tournament Selection) gibi seçme yöntemleri vardýr. Örnek olarak bu çalýþmada kullanýlan rulet tekerleði seçimi aþaðýda açýklanmýþtýr:

1- Tüm bireylerin uygunluk deðerleri bir tabloya yazýlýr.
2- Bu deðerler toplanýr.
3- Tüm bireylerin uygunluk deðerleri toplama bölünerek [0,1] aralýðýnda sayýlar elde edilir. Bu sayýlar bireylerin seçilme olasýlýklarýdýr. Sayýlarýn hepsi bir tabloda tutulur.
4- Seçilme olasýlýklarýný tuttuðumuz tablodaki sayýlar birbirine eklenerek rasgele bir sayýya kadar ilerlenir. Bu sayýya ulaþýldýðýnda yada geçildiðinde son eklenen sayýnýn ait olduðu çözüm seçilmiþ olur.

Bu yönteme rulet tekerleði seçimi ismi, bir daireyi, çözümlerin uygunluklarýna göre dilimleyip çevirdiðimizde olacaklarýn benzeþimi olduðu için verilmiþtir.
Rulet tekerleði seçimi çözümlerin uygunluk deðerlerinin negatif olmamasýný gerektirir. Çünkü olasýlýklar negatif olursa bu çözümlerin seçilme þansý yoktur. Çoðunluðunun uygunluk deðeri negatif olan bir toplumda yeni nesiller belli noktalara takýlýp kalabilir.

Ýkili kodlamada çaprazlama

Gen takasý (crossover) genetik algoritmanýn motoru kabul edilir. Basitçe olay iki ebeveyn kromozomun arasýnda belirlenen parçalarýn takasýdýr.
Tek noktalý Ýki noktalý
Düzenli
Aritmetik

Ýkili kodlamada mutasyon

Permutasyon kodlamada çaprazlama

Tek noktalý çaprazlamada bir nokta seçilir ilk ebeveynden bu permutasyonun kopyalandýðý noktaya kadar,sonra ikinci ebeveyn okunur ve sayý çocukta hala yoksa o eklenir.

Permutasyon kodlamada mutasyon

Deðer kodlamada çaprazlama
Ýkili kodlamadaki tüm çaprazlamalar kullanýlabilir.

Deðer kodlamada mutasyon
Reel deðer kodlama için seçilen deðere küçük bir sayý eklenir ya da çýkarýlýr.

Aðaç kodlamada çaprazlama

Seçilen düðümler deðiþtirilir. Operatorlar sayýlar deðiþtirilir. Gen takasý toplumda çeþitliliði saðlar. Ýyi özelliklerin bir araya gelmesini kolaylaþtýrarak en iyiye yaklaþmayý saðlar. Deðiþtirme kromozomun bir parçasýnýn dýþarýdan deðiþtirilmesi þeklinde tanýmlanýr. Deðiþtirme görünüþte genetik algoritmanýn dayanak noktasýdýr, ancak etkisi bir çözüm üzerindedir. Bu da yalnýz baþýna baþarýlý olmasýný zorlaþtýrýr. Ýkilik dizilerde deðiþtirme rasgele bir bit’in deðiþtirilmesiyle saðlanabilir. Çok düþük bir deðiþtirme olasýlýðý toplumda bazý özelliklerin kaybolmasýna neden olabilir. Bu da en iyi sonuçlarýn bulunmasýna engeldir. Ancak yüksek bir deðiþtirme olasýlýðý da eldeki çözümleri bozarak sonuca ulaþmayý zorlaþtýrýr. Gen takasý ve deðiþtirmenin olasýlýklarý için kesin bir sayý yoktur. Deðiþtirme (mutasyon) olasýlýðý 0.01-0.001, gen takasý (cross-over) olasýlýðý 0.5-1.0 aralýðýnda tavsiye edilir.

Adým-4.
Eski kromozomlar çýkartýlarak sabit büyüklükte bir toplum saðlanýr.

Adým-5.
Tüm kromozomlar yeniden hesaplanarak yeni toplumunun baþarýsý bulunur.

Adým-6.
Genetik algoritma defalarca çalýþtýrýlarak çok sayýda toplum oluþturulup hesaplanýr.

Adým-7.
Toplumlarýn hesaplanmasý sýrasýnda en iyi bireyler saklandýðý için o ana kadar bulunmuþ en iyi çözüm çözümdür. Genetik algoritmanýn yaptýðý iþleri temelini akýþ diyagramý olarak Þekil 9'de görebiliriz:

Basit bir genetik algoritma, L uzunluðundaki homojen bir çubuðun momentinin 0 (sýfýr) olduðu noktayý bulmak için kurabiliriz.

L uzunluðuna baðlý olarak ara uzunluk x1 ve x2 0 ile 255 cm arasýnda iþaretsiz bir tamsayý alýnacaktýr. F(x)=x1.m1-x2.m2 minimum deðeri, ayný zamanda uygunluk fonksiyonudur. Dolayýsýyla özgül kütleleri ayný olduðundan, doðrudan uzunluklara baðlý olacaktýr. Yani uygunluk fonksiyonunu daha basit bir þekilde F(x)=x1-x2=0 olarak verebiliriz. Burada x2=L-x1 olduðundan F(x1)=2.x1-L=0 alýnabilir. Örnek basit seçildiðinden sonucun matematik bilgisine göre 127.5 cm olacaðý açýkça görülmektedir. 0 ile 255 arasýndaki sayýlarý gösterebilmek için 8 bit uzunluðunda bir bilgiye ihtiyacýmýz vardýr.

0................ 00000000
255............ 11111111

Ýlk olarak baþlangýç topluluðu bu sayýlar arasýndan rasgele olarak seçilebilir. Bunun için 8 birey oluþturulsun (N=8). Bunlar {0, 40, 80, 120, 160, 200, 220, 255} alýnýrsa:

0................ 00000000
40.............. 00101000
80.............. 01010000
120............ 01111000
160............ 10100000
200............ 11001000
220............ 11011100
255.............11111111

Deðerleri baþlangýç topluluðu olarak belirlenir. Bireylerin uygunluk deðerleri, sayýnýn ondalýk karþýlýðýnýn uygunluk fonksiyonuna verdiði cevapla bulunabilir. Uygunluk deðeri sayýnýn alabileceði deðerler ile orantýlý olursa, bunun için max uygunluk deðeri olarak 255 ve minimum olarak ta 0 uygunluk deðeri alýnmalýdýr. Eðer elde edilen uygunluk deðeri 255 ten çýkarýlýrsa max uygunluða 255 sayýsýnýn karþýlýk düþtüðü görülebilir.
Örnek:

x=00000000 için F(x)=255-ABS(255–0)=0
x=00101000 için F(x)=255-ABS(255–80)=80 þeklinde belirlenebilir.

Bireylerin uygunluk deðerlerinin rulete yansýmasýndan kaç adet kopya oluþturulacaðý veya hiç kopya alýnmayacaðý belirlenir. Yukarýdaki tabloya göre 80,120 ve 160 sayýlarýndan 2 þer kopya alýnacaktýr. 0 ve 255 sayýlarýndan hiç kopya alýnmayacak ve diðer sayýlardan 1 er kopya alýnacaktýr. Buna göre çaprazlama operatörü yardýmýyla yeni bireyler üretmeden önce baþlangýç topluluðu tekrar oluþturulmalýdýr.

Yukarýdaki iþlemlerde, bir nesilden diðer nesle kromozomlar aktarýlýrken, uygun kromozomlarýn iyi özellikleri tekrar üreme adýmýnda kullanýlarak en iyi kromozomlar elde edilebilir. Elle yapýlabilecek bu örnekte üç nesil sonra çözüm olabilecek bireylerin çözüm uzayýný yeterince daraltarak birbirlerine daha çok benzeyecekleri görülecektir.

Genetik Algoritmalarýn Kullanýlma Nedenleri

Öncelikle niye diðer yöntemlerin kullanýlmadýðý belirtilmelidir. Denklem en iyilemesinde (optimization);

1. Türev-Ýntegral hesabýna (calculus) dayananlar
2. Numaralamaya (enumeration) dayananlar
3. Rastgele aramalar (random searches)

olmak üzere üç tip çözümden bahsedilir.
Genetik algoritmalarýn yeri Þekil 1.'de görülebilir.


Türev-Ýntegral hesaplamalarýna dayanan hesaplama yöntemleri çok derinlemesine çalýþýlmýþtýr. Bu yöntemler fonksiyonun türevinin köklerinin fonksiyonun en küçük ve en büyük deðer veren noktalarý olmasýndan yararlanýr. Gerçek problemler için sýfýr veren noktalarý bulmak da ayrý bir problemdir.
Diðer bir yöntem ise alýnan bir noktadan sadece yukarý ilerleyerek en iyi sonucu bulmayý hedefler. Tepe týrmanma (hill climbing) denen bu yöntem fonksiyon grafiðinin tepelerini týrmanýr. Ancak çok sayýda dönme noktasý içeren bir fonksiyonda çok sayýda tepe oluþur. Hangi tepenin en iyi çözüm olduðunu bilenemez. Numaralama yöntemleri ise oldukça alýþýlagelmiþtir. Sürekli olan gerçel sayý aralýklarý belli sayýda parçaya ayrýlarak parçalar denenir. Ancak problemler böyle çözmek için büyük olabilir. Bu yöntemin biraz daha geliþtirilmiþ þekli Dinamik Programlamayla (dynamic programming) oluþturulur. Parçalar arasýndan iyi görünenler seçilir. Bu parçalar parçalara ayrýlarak iþlem tekrarlanýr. Bu yöntem de tepe týrmanma yöntemi gibi yanlýþ tepeleri araþtýrabilir. Dinamik Programlama tepelerin olmadýðý aralýklarda baþarýlý ve hýzlýdýr.
En iyilemenin;

• Bir iþin daha iyi yapýlmasý
• En doðru þekilde yapýlmasý

olmak üzere iki amacý vardýr.
Günümüzde rasgele aramalarýn kullanýmý artmaktadýr. Bu tip aramalar en iyilemenin daha iyi yapma amacýný saðlamakta daha baþarýlýdýrlar. Ýnsanlarýn bilgisayarlardan genel beklentisi mükemmellik olduðu için bu tip aramalar baþarýsýz görünebilir. Genetik algoritmalar klasik yöntemlerin çok uzun zamanda yapacaklarý iþlemleri kýsa bir zamanda çok net olmasa da yeterli bir doðrulukla yapabilir.

Genetik Algoritmalarýn Farklarý

1. Genetik algoritma parametrelerin kodlarýyla uðraþýr. Parametreler kodlanabildiði sürece fark etmez.
2. Genetik algoritma bir tek yerden deðil, bir grup çözüm içinden arama yapar.
3. Genetik algoritma ne yaptýðý konusunda bilgi içermez, nasýl yaptýðýný bilir. Bu nedenle bir kör arama (blind search) metodudur.
4. Genetik algoritmalar olasýlýk kurallarýna göre çalýþýr. Programýn ne kadar iyi çalýþacaðý önceden kesin olarak belirlenemez. Ama olasýlýkla hesaplanabilir.

Þema Teorisi (Schemata Theorem)

Genetik algoritmalarda oluþan baþarýlý bireyler incelenirse, bu bireyler arasýndaki benzerlikler bulunabilir. Bu benzerliklerden yola çýkarak þemalar oluþturulabilir. Ýkilik dizi kodlamasý için aþaðýdaki yöntem önerilebilir.
0, 1 ve # (‘#’ o konumda 0 veya 1 olmasýnýn önemsiz olduðunu gösterir).
Örnek olarak ikinci ve dördüncü bitleri 1, altýncý biti 0 olan çözümlerin baþarýlý olduðu bir toplumda þu þema oluþturulabilir:

#1#1#0

Tablo 1. Þema

Bu þemaya uygun aþaðýdaki ikilik diziler yazýlabilir:

010100, 010110, 011100, 011110, 110100, 110110, 111100, 111110.

Görüldüðü gibi þemalarýn katýlmasý ikilik dizilerle gösterilen arama aralýðýný büyütmektedir. Arama aralýðýnýn büyümesinin sonucun bulunmasýný zorlaþtýrmasý beklenir ancak durum böyle deðildir. Seçilim ve yeniden kopyalama ile iyi özellikler daha çok bir araya gelerek daha iyi deðerlere sahip þemalara uygun çözümler elde edilir.
Genetik algoritma kendi içinde sanal olarak þemalarý oluþturur. Toplumun bireyleri incelenerek bu þemalar ortaya çýkarýlabilir. Genetik algoritmalar þemalarý oluþturmak için toplum üyelerinin kodlarý dýþýnda bir bilgi tutmaz. Genetik algoritmalarýn bu özelliðine içsel paralellik (implicit parallelism) denir. Her nesilde, iyiyi belirleyen þemalardaki belirsiz yada önemsiz elemanlar azalýr. Böylece genetik algoritmalar sonuca doðru belli kalýplar içinde ilerler.

GA’nýn Performansýný Etkileyen Nedenler

Kromozom sayýsý
Kromozom sayýsýný arttýrmak çalýþma zamanýný arttýrýrken azaltmak da kromozom çeþitliliðini yok eder.
Mutasyon Oraný
Kromozomlar birbirine benzemeye baþladýðýnda hala çözüm noktalarýnýn uzaðýnda bulunuyorsa mutasyon iþlemi GA’nýn sýkýþtýðý yerden kurtulmak için tek yoludur. Ancak yüksek bir deðer vermek GA’yý kararlý bir noktaya ulaþmaktan alýkoyacaktýr.
Kaç Noktalý Çaprazlama Yapýlacaðý
Normal olarak çaprazlama tek noktada gerçekleþtirilmekle beraber yapýlan araþtýrmalar bazý problemlerde çok noktalý çaprazlamanýn çok yararlý olduðunu göstermiþtir.
Çaprazlamanýn sonucu elde edilen bireylerin nasýl deðerlendirileceði
Elde edilen iki bireyin birden kullanýlýp kullanýlamayacaðý bazen önemli olmaktadýr.
Nesillerin birbirinden ayrýk olup olmadýðý
Normal olarak her nesil tümüyle bir önceki nesle baðlý olarak yaratýlýr. Bazý durumlarda yeni nesli eski nesille birlikte yeni neslin o ana kadar elde edilen bireyleri ile yaratmak yararlý olabilir.
Parametre kodlanmasýnýn nasýl yapýldýðý
Kodlananýn nasýl yapýldýðý en önemli noktalardan biridir. Örnek vermek gerekirse kimi zaman bir parametrenin doðrusal yada logaritmik kodlanmasý GA’nýn performansýnda önemli bir farka yol açabilir.
Kodlama gösteriminin nasýl yapýldýðý
Bu da nasýl olduðu yeterince açýk olmamakla beraber GA’nýn performansýný etkileyen bir noktadýr. Ýkilik düzen, kayan nokta aritmetiði ya da gray kodu ile gösterim en yaygýn yöntemlerdir.
Baþarý deðerlendirmesinin nasýl yapýldýðý
Akýllýca yazýlmamýþ bir deðerlendirme iþlevi çalýþma zamanýný uzatabileceði gibi çözüme hiçbir zaman ulaþmamasýna neden olabilir.

Genetik operatörlerin þema üzerine etkileri

1. Çoðalmanýn etkisi

2. Çaprazlamanýn etkisi

3. Mutasyonun etkisi

GA Nasýl Çalýþýyor?

Gördüðümüz gibi GA'nýn iþleyiþi çok basittir fakat bu kadar basit olan yöntemin, en zor problemleri nasýl çözdüðünün anlaþýlmasý da o kadar zordur. Bu da GA’nýn en karmaþýk ve bilim adamlarýnýn yýllardýr çözmeye çalýþtýklarý en önemli sorulardan biridir.
GA’nýn bu yönünü biraz açýklayalým; GA, çözüm(ler) bulmak için taranmasý gereken parametre uzayýnýn çok büyük olduðu durumlarda bu arama iþlemi, için en akýlcý yöntemdir. Evrimin her sürecinde edinilen bilgi sonra ki nesillere aktarýlarak taramanýn daha uygun bölgelerde gezmesi saðlandýðý gibi deðiþim iþlemi yardýmýyla yerel çözüm noktalarýna sýkýþýp kalma olasýlýðý da azaltýlýyor. Ayrýca GA’nýn paralel iþlem yapýlan bilgisayarlarda kullanýlmaya elveriþli yapýsý da zaman alýcý problemlerin çözümü için çekici bir seçenek olmasýný saðlamaktadýr.

Örnek:

Fonksiyon Maksimizasyonu
Amacýmýz genetik algoritmanýn bilgisayarda nasýl çalýþacaðýný kaðýt üzerinde açýklayýcý þekilde anlatmaktýr.
Amaç
f(x)=x² , x Î[0,31] þeklinde verilen bir fonksiyonun, verilen aralýkta maksimizasyonu yapýlmasý istenmektedir.

Adým 1:
Ýlk olarak x sayýsýnýn kodlanmasý iþlemi yapýlmalýdýr. x’in 0 ve 1'lerden oluþan 2 tabanýndaki gösterilimi kullanýlacaktýr. Dolayýsýyla x, 5 bit uzunluðunda bir kodla (string) temsil edilecektir. Öyle ki 0: “00000” ve 31: “11111” olacaktýr.

Adým 2:
Toplumun birey sayýsý n:4 olarak seçilmiþtir. Toplumu oluþturan dört birey, her biri 5 bit uzunluðunda birer kromozomla temsil edildiði için toplam 20 kere yazý tura atmak suretiyle belirlenmiþtir. Elde edilen birey kromozomlarý aþaðýdadýr.

Birey 1: 01101, x = 13 , x² = 169
Birey 2: 11000, x = 24 , x² = 576
Birey 3: 01000, x = 8 , x² = 64
Birey 4: 10011, x = 19 , x² = 361

Adým 3:
Yukarýda belirlenen bireyler için f(x)=x², bireylerin uygunluk deðerlerini verir. Dört bireyin toplam uygunluk deðerleri “169+576+64+361=1170” dir. Dolayýsýyla her bir bireyin rulet tekerleðinde kaplayacaðý alan þu þekilde hesaplanýr.

Birey 1: 169/1170=0.14 : %14
Birey 2: 576/1170=0.49 : %49
Birey 3: 64/1170=0.06 : %6
Birey 4: 361/1170=0.31 : %31

Bu deðerler, rulet tekerleðinin her çevriliþinde hangi olasýlýkla hangi bireyin seçileceðini belirtir, yani 0.14 olasýlýkla 1 numaralý birey seçilecektir. Rulet tekerleði ve bireylerin tekerlek üzerindeki daðýlýmlarý Þekil 1.'de gösterilmiþtir:

Adým 4:
Toplumda ki birey sayýsýnýn sabit kaldýðý varsayýldýðýndan dolayý, rulet tekerleði 4 kere çevrilerek çiftleþme havuzu oluþturulacaktýr. Rulet tekerleði döndürülmüþ ve þu sonuçlar elde edilmiþtir.

Birey 1 : 1 kere
Birey 2 : 2 kere
Birey 3 : 0 kere
Birey 4 : 1 kere

Bunun sonucunda elde edilen çiftleþme havuzunda þu þekildedir;

Aday 1 : 01101 (Birey 1)
Aday 2 : 11000 (Birey 2)
Aday 3 : 11000 (Birey 2)
Aday 4 : 10011 (Birey 4)

Adým 5:
Çiftleþme havuzu belirlendikten sonra iki aþamalý çaprazlama uygulanýr. Ýlk aþamada adaylar çiftleþmek üzere rasgele olarak eþlenirler. Her ikili grup için bir kere zar atýlarak çaprazlaþmanýn oluþacaðý nokta belirlenir. rasgele eþleþtirme yapýlmýþ ve bunun sonucunca ( Aday 1, Aday 2) ve (Aday 3, Aday 4) ikili gruplarý oluþmuþtur. Çaprazlaþma noktalarýca zar atýlarak 1. Grup için k=4 ve 2. Grup içinde k=2 olarak belirlenmiþtir. Bu aþamadan sonra çaprazlaþma gerçekleþtirilmiþ ve þu sonuçlar oluþmuþtur; ( çaprazlaþma noktalarý “/” ile belirtilmiþtir.)

Çiftleþme grubu 1: (k=4)

Aday 1 : 0110/1 oluþan Birey 1 : 01100
Aday 2 : 1100/0 oluþan Birey 2 : 11001

Çiftleþme grubu 2 : (k=2)

Aday 3 : 11/000 oluþan Birey 3 : 11011
Aday 4 : 10/011 oluþan Birey 4 : 10000

Adým 6:
Son aþama olan mutasyon bitler düzeyinde uygulanýr. Bu örnekte her bir bit için (toplam 20 bit var) mutasyon olma olasýlýðý 0.01 olarak seçilmiþtir. Dolayýsýyla her bir bit için aðýrlýklý yazý/tura (mutasyon olasýlýðýna göre) atýlarak hangi bitlerin mutasyona uðrayacaðý belirlenir. Bu iþlem yapýlmýþ ve sonuçta oluþan birey 3’ün 2 numaralý bitinde mutasyon olacaðý ortaya çýkmýþtýr.

Oluþan Birey 3 : 11011

Mutasyon sonucu oluþan Birey 3 : 10011

Bu adýmýn tamamlanmasýyla bir sonraki kuþaðý oluþturacak toplumun bireyleri
belirlenmiþ olur. Yeni toplum þu þekildedir;

Birey 1 : 01100, x=12, x²=144
Birey 2 : 11001, x=25, x²=625
Birey 3 : 10011, x=19, x²=361
Birey 4 : 10000, x=16, x²=256

3 temel operatörden oluþan genetik algoritma her aþamada yeni oluþan kuþaða uygulanarak bir sonraki kuþak elde edilecektir. Yukarýdaki örnekte tek bir iterasyon yapýlmýþ ve baþlangýç toplumundan bir sonraki kuþak oluþturulmuþtur ancak genetik algoritmanýn çalýþmasýnýn tam olarak gözlenebilmesi için tek bir iterasyon yeterli deðildir. Yukarýdaki iþlemlerde her þey çok fazla rasgele gibi görünse de, uygunluk deðeri yüksek olan bireylerin seçilme ve çiftleþme olasýlýklarý yüksek olduðu için kuþaklar ilerledikçe toplumu oluþturan bireylerin uygunluk deðerlerinin ortalamasýnýn da arttýðý gözlenecektir. Bunun için ise tek bir iterasyon yeterli deðildir.

GENETÝK ALGORÝTMALAR

Genetik Algoritma Kavramý

Genetik algoritmalar, karmaþýk düzenli problemlerin çözümünü gerçekleþtirmek amacýyla, kromozomlarýn yeni diziler üretme esasýný temel alan, sezgisel bir araþtýma yöntemidir. Genetik algoritmalar, matematiksel fonksiyonlarýn global optimizasyonunu hedeflerler. Genetik algoritmalarý diðer araþtýrma yöntemlerinden ayýran özellik Ýse, bir çözüm seti ile baþlandýktan sonra, geliþtirme için biyolojik evrimi esas alan bir prosesin kullanýlmasýdýr. Bu prosesin sonunda da en iyi kromozoma ulaþma amaçlanmaktadýr.Problemle ilgili parametreler, genler halinde bir araya gelerek kromozomu oluþturmakta; en iyi kromozoma ulaþma ise, genlerin kromozom içindeki diziliþini deðiþtirerek; yani, yeni nesiller yaratýlarak gerçekleþtirilmektedir. Genetik algoritmalarýn, problem çözümünde uygulanabilmeleri için, problemin çözüm uzayý olarak, her bir problemin mümkün çözümlerinden olan yapýlardan (ya da organizmalardan) oluþan bir popülasyon ortaya konmaktadýr. Ýlk neslin oluþmasý için, öncelikle belirli bir sayýda organizma seçildikten sonra, yeni bir neslin yaratýlmasý için, mevcut nesilden seçilen aiie'lere bazý genetik oparatörler uygulanýr. Burada "iyi çocuklar iyi aileden doðar" fikrine uygun olarak, mevcut nesil içinde yüksek uygunluk deðerine sahip organizmalarýn aile olarak seçilme þanslarý da doðal olarak yüksektir.

Genetik algoritmalarýn özellikleri

Çeþitli problemlerin çözümünde kullanýlan genetik algoritmlar, aþaðýdaki özellikleri taþýrlar.
a) Uygun çözümler için bir veya daha fazla "popülasyon" mümkündür.
b) Önceden bilinen çoklu çözümlerin özelliklerini bir araya getirerek, yeni uygun çözümler üreten bir mekanizmaya sahiptir.
c) Önceden bilinen bir çözümün düzenini rast gele (tesadüfi) bir þekilde deðiþtirerek, yeni uygun bir çözüm üreten bir mekanizmaya sahiptir.
d) Popülasyon içinden, öncelik vererek, ayrý çözümleri seçen bir mekanizmaya sahiptir.
e) Popülasyon içinden bazý çözümleri dýþarý çýkaran bir mekanizmaya sahiptir.

Genetik algoritmalarýn sahip olmasý gereken koþullar

Genetik algoritmalarýn etkin bir þekilde kullanýlabilmeleri için, aþaðýdaki koþullarýn saðlanmasý gerekmektedir.
a) Araþtýrma uzayý parametreleri, ikili (0-1) sistemde veya alfabetik bir þekilde kodlanarak belirli bir uzunlukta kromozom-gen düzeni oluþturulmalýdýr.
b) Uygun çözüm sayýsýný azaltmak için problemin amacý doðrultusunda bir uygunluk fonksiyonu kullanýlmalýdýr.
c) Paralel ve global araþtýrmaya imkân saðlanmasý açýsýndan, araþtýrma uzayý içindeki her nokta taranmalýdýr.
d) Bir araþtýrma uzayýndan diðerine bir geliþme saðlanabilmesi için, olasýlýklý geçiþ (deðiþim) kuralý kullanýlmalýdýr.

Genetik Operatörler

Genetik algoritmalardaki kromozom yapýlarýn kopyalanmasý iþleminde üç temel operatör kullanýlmaktadýr. 

Yeniden üretim (reproduction)
Her bireyi, bir nesilden diðerine aynen kopyalama iþlemidir. Uygunluk derecesi yüksek olan kromozomlar üþütün nitelikli çocuk üretiminde kullanýlmak üzere bu yöntemle çoðaltýlýrlar.

Çapraz deðiþim (crossover)
Ýki veya daha fazla kromozomdan (aile'den), yeni bir kromozom (çocuk) meydana getirme iþlemidir. Burada da amaç, daha iyi niteliklere sahip çocuklara ulaþmaktýr.

Dahili deðiþim (mutation)
Kromozom yapýsý içinde deðiþikler yapma iþlemidir. Mustasyon iþlemi ile yeni uygun çözümler elde edilmeye çalýþýlýr.

Nümerik Kodlama

Problemdeki parametreleri temsil eden, kromozom yapýsý içindeki genlerin diziliþinin gösterimi, daha çok ikili sistem (0-1 sistemi) veya diðer rakamlarýn da kullanýlmasýyla gerçekleþtirilmektedir. Rakamlarýn ikili sistem dýþýnda kullanýmýnda, problemin paremetreleri gereði, sýralý veya sýrasýz rakamlarýn birer defa kullanýmýnýn yanýsýra, ayný rakamlarýn birden çok kullanýmýna da rastlanmaktadýr.

Çapraz deðiþim uygulamalarý

Çapraz deðiþim ile ilgili olarak rastlanýlan ilk uygulama þeklinde, önce kromozom yapý üzerinde rast gele bir ayrým noktasý belirlenmektedir. Kromozonlar, çapraz deðiþim iþleminde bu ayrým noktasý öncesindeki gen yapýsýný aynen korurlarken, ayrým noktasý sonrasýndaki gen yapýsýný ise karþýlýklý olarak deðiþtirmektedirler. Takip eden örnekte de görüleceði gibi, ayrým sonrasý genleri (1100) ve (1010) karþýlýklý olarak yer deðiþtirmiþ.

Bazý uygulamalarda ise, iki ayrým noktasý kullanýlmaktadýr. Ayrým noktalarýnýn belirlenmesi ve karþýlýklý deðiþtirilecek parçalarýn belirlenme iþlemleri yine rast gele olmaktadýr. Takip eden örnekte, iki ayrým noktasý arasýndaki (001) ve (011) genleri karþýlýklý yer deðiþtirmiþtir

Bazý çapraz deðiþim uygulamalarýnda, ailedeki kalýtsal özelliklerin çocuða taþýndýðý durumlara ratslanmaktadýr. Tahip eden örnekte ile iþaretlenen kalýtsal özelliklerin, çocuk (A)'ya ne þekilde taþýndýðý gösterilrnektedir.

Bazý uygulamalarda, çapraz deðiþimin hemen arkasýnda bir onarma iþlemine ihtiyaç olmaktadýr. Bunu, takip eden örnekte görebiliriz.

iki ayrým arasýndaki genler karþýlýklý deðiþtirildiðinde, elde edilen sonucun uygun olmadýðý açýkça gözükmektedir. Takip eden örnekteki onarma
iþleminde, birinci sýradaki genler karþýlýklý deðiþtirilerek uygunluk saðlanmýþtýr.

Görüldüðü gibi çapraz deðiþimle ilgili çok çeþitli uygulamalar söz konusudur. Burada önemli olan uygunluk derecesi yüksek olan aileleri bir araya getirerek, uygunluk derecesi daha yüksek çocuklar elde etmeye çalýþmaktýr. Bu arada, uygunsuz olan sonuçlarýn ortaya çýkmasý durumunda, onarým iþlemi uygulanmalýdýr.

Dahili deðiþim (mutasyon) uygulamalarý

Kromozom yapýsý üzerindeki dahili deðiþim, genellikle rast gele bir þekilde belirlenen bir gen'in deðiþtirilmesiyle gerçekleþtirilmektedir. Yani, 1 ise O'la veya 0 ise 1'le deðiþtirilmektedir.
Ýkili sistem yerine, problemin paremetreleri gereði, sýralý veya sýrasýz rakamlarýn birer defa ya da ayný rakamlarýn birden çok kullanýmýnýn söz konusu olduðu durumlarda, rast gele belirlenmiþ herhangi bir gene ait rakam, yine rast gele belirlenmiþ diðer rakamla yer deðiþtirmektedir. Takip eden örnekte ise, kromozomda ile iþaretlenmiþ gen rast gele bir þekilde belirlenerek deðiþtirilmiþ, böylelikle mutasyon iþlemi tamamlanrnýþtýr.

Bazen de kromozom üzerinde iki gen rast gele seçilerek, karþýlýklý olarak yer deðiþtirmeleri saðlanýr. Takip eden örnekte, 3. ve 8. sýradaki genler rast gele seçilerek, yerleri deðiþtirilmiþtir.

Bazý uygulamalarda ise, rast gele seçilen gen bulunduðu sýradan alýnarak, yine rast gele olarak belirlenen baþka bir sýradan yapýya dahil edilir.
Takip eden örnekte de gösterildiði gibi, 7. Sýrada bulunan gen (2), sýrasýndan çýkarýlarak 1. Sýradan tekrar yapýya dahil edilmiþtir.

Alfabetik Kodlama

Prablemdeki parametreleri temsil eden, kromozom yapýsý içindeki genlerin diziliþinin gösterimi, alfabetik sembollerin kullanýlmasýyla da gerçekleþtirilmektedir. Bu gösterim þeklinde, rakamlarla gösterim þeklinde de olduðu gibi, sýralý veya sýrasýz harflerin birer defa ya da birden çok kullanýmýna rastlanmaktadýr.
Çapraz deðiþim ile ilgili uygulamalar incelendiðinde, en çok rastlaný- lanlarýn, takip eden dört örnekteki gibi olduðu görülecektir.
Takip eden örnekte, tek ayrým noktasýnýn söz konusu olmasý durumundaki çapraz deðiþim gösterilmektedir. Görüldüðü gibi, Aile (1)'den alman (ABC) genleri, Çocuk'ta ayný sýrada ve ayný pozisyonda yer alýrken; (EHDGH) genleri ise, Aile (2)'den alýnarak yine ayný sýra ile sýralanmaktadýr.

iki ayrým noktasýnýn olmasý durumunda, takip eden örnekte de görüldüðü gibi, Aile (1)'den alýnan (AB) ve (GH) genleri ayný pozisyonda Çocukta da yer alýrken; Aile (2)'den alýnan diðer genler (EDCF) de ayný sýra içersinde Çocuk'ta da yer almaktadýr.

Yine iki ayrým noktasýnýn olmasý durumunda, ancak bu defa Aile (1)'den alýnan (CDEF) genleri ayný pozisyonda olmak üzere Çocuk'ta yer alýrken; Aile (2)'den alýnan diðer genler de ayný sýrada Çocuk'ta yer almaktadýr.

Takip eden örnekte ise, Aile (1)'den rast gele seçilen iþaretli genler, Çocuk'ta kalýtýmsal olarak ayýn pozisyonlarda yer alýrken; Aile (2)’den alýnan diðer genler (ADGF) de, kalan pozisyonlarý yine ayný sýrada doldurmuþtur.

Dahili deðiþim (mutasyon) uygulamalarý

Dahili deðiþim (mutasyon) ile ilgili uygulamalar incelendiðinde, en çok rastlanýîanlarýn, genellikle takip eden dört örnekte gösterildiði gibi olduðu görülecektir. Takip eden ilk örnekte, rast gele seçilen iki komþu genin, karþýlýklý olarak deðiþtirilmesiyle mutasyon gerçekleþtirilmektedir.

Takip eden diðer örnekte de gösterildiði gibi rast gele seçilen iki gen, karþýlýklý olarak da deðiþtirilebilmektedir.

ilk iki örneðin özel bir durumu olarak nitelendirebileceðimiz üçüncü örnekte, üç gen rast gele seçilerek, yine rast gele sýrada yeniden sýralanmaktadýr.

Takip eden bu son örnekte ise, rast gele geçilen bir gen, yine rast gele bir þekilde seçilen poziyonda araya sokulmakta; deðer genler ise ok istikametinde kaydýrýlmaktadýr.

Deðerlendirme

Yeniden üretim (reproduction), çapraz deðiþim (crossover) ve dahili deðiþim ya da mutasyon (mutitation) aþamalarýnýn her tamamlanýþýnda,
sonuçlarýn öncekilerle karþýlaþtýrýlmasý gerekmektedir. Buradaki amaç en iyi kromozomu elde etmek; baþka bir ifade ile, en iyi çözüme ulaþmaktýr. Bu nedenle, her çevrimde elde edilen yeni kromozomlarýn uygunluk dereceleri belirlenerek, sýralamaya dahil edilirler. En iyiler "Aile" görevi ile yeni nesil üretimine devam ederek, daha iyi nitelikli "çocuk" elde edilmesine çalýþýrlar. Bu süreç, amaç gerçekleþinceye kadar devam eder.

Genetik Algoritmalarýn Kullaným Alanlarý
Genetik algoritmalar, özellikle 1985 yýlýndan sonra, gittikçe artan bir ilgiyle geniþ bir kullaným alanýna sahip olmaya baþlamýþtýr. Bu kýsýmda özellikle son yýllarda gerçekleþtirilen genetik algoritma uygulamalarý tanýtýlmaya çalýþýlmýþtýr.

GA'lann doðrusal olmayan tam sayýlý programlamada kullanýmý
Bu konuda yapýlan çalýþmalara, Yokota ve arkadaþlarýnýn, 1995 yýlýnda yayýnlanan iki makalesinde rastlan maktadýr. Bu çalýþmalarda, optimum sistem güvenilirliði ile ilgili doðrusal olmayan tam sayýlý programlama problemi, aralýk katsayýlarý kullanýlmadan; doðrudan, amaç fonksiyonunun doðrusal olmama durumu da korunarak, genetik algoritmalarýn kullanýlmasýyla çözülmüþtür.

GA'larýn Hücresel imalat problemlerinde kullanýmý

Bu konuda yapýlan çalýþmalardan bir tanesinde (1996), Joines ve arkadaþlarý (Culbreth & King), hücresel imalat tasarýmý probleminin çözümünde, tam sayýlý programlama ve genetik algoritmalarý beraberce kullanmýþlardý r(JolneS). Hwang ve arkadaþý (Sun) ise yine 1996 yýlýnda yayýnlanan makalede, hücre oluþumu probleminin çözümü için, genetik algoritma tabanlý, iki fazlý sezgisel bir çözüm önermiþlerdir.

GA'lann motaj hattý dengeleme problemlerinde kullanýmý
Bu konuda, Gen ve Tsujimura ile arkadaþlarýnýn Gerçekleþtirdikleri çalýþmalarla ilgili olarak 1995 yýlýnda yayýnlanan makalelerinde; her bir iþ istasyonundaki toplam iþlem zamanlarýný minimize etmeyi hedefleyen genetik algoritma amaç fonksiyonu ile bulanýk küme mantýðý beraberce kullanýlarak, montaj hattý dengeleme problemlerinin çözümü gerçekleþti rilmiþtir.

GA'lann yerleþim (layout) problemlerinde kullanýmý
Yerleþim konusunda çalýþma yapan Cheng ve arkadaþlarýnýn (Gen & Tosowa) 1995 yýlýnda yayýnlanan makalelerinde, makinalarýn dairesel olarak yerleþtirildiði ve malzeme hareketinin tek bir yöne doðru gerçekleþtirildiði durum ile ilgili problemin, genetik algoritmalar ile sezgisel bir yöntem kullanarak çözülebileceðini göstermiþlerdir(Cheng). Yerleþim konusundaki bir diðer çalýþma ise Gen ve arkadaþlarý tarafýndan 1995 yýlýndaki makalelerinde sunulmuþtur. Bu makalede, makinalar arasý toplam taþýma maliyetlerinin minimize edilmesinin hedeflendiði, çok hatlý makine yerleþim problemi, bulanýk küme mantýðý ile genetik algoritmalar kullanýlarak çözülmüþtür.

GA'lann atama problemlerinde kullanýmý
Bu konuda araþtýrma yapan Chu & Beasly, 1996 yýlýnda yayýnlanan makalelerinde, minimum maliyetli atamanýn hedeflendiði problem için genetik algoritmalarýn kullanýldýðý bir çözüm önermiþlerdir(Chu). Bu konudaki diðer bir çalýþma da, Tate ve Smith tarafýndan 1994 yýlýnda yayýnlanan makalelerinde sunulmuþtur. Bu çalýþmada, kuadratik atama probleminin çözümü genetik algoritmalar ile gerçekleþtirilmiþtir(Tate). Yine bu konudaki baþka bir çalýþmada, Zhao ve arkadaþlarý 1995 yýlýnda yayýnlanan makalelerinde, iþ istasyonu atama problemi (ve robot seçimi) için genetik algoritmalarý kuilanmýþlardýr.

GAÝarýn sýralama problemlerinde kullanýmý
Bu konuda yapýlan çalýþmalarda, Reeves 1994 yýlýnda yayýnlanan makalesinde, genetik algoritmalarý n-adet iþ ve m-adet makine'nin söz konusu olduðu akýþ atölyesi sýralama probleminin özümünde kullanýlmasýný tanýtmýþtýr. Bir baþka çalýþmada ise, Yip-Hoi ve Dutta, 1996 yýlýnda yayýnlanan makalede, bir tezgahýn iki farklý talaþ kaldýrma iþlemi yapabilmesi durumunda, proses planlamadaki sýralama probleminin çözümü için genetik algoritmalarý kullanmýþlardýr. Kim ve arkadaþlarýnýn (Hyun & Kim), karýþýk model montaj hatlarýndaki sýralama problemi için, 1996 yýlýnda yayýnlanan makalelerinde, önerdikleri genetik algoritmalar yaklaþýmý, büyük çaplý sýralama problemlerinin çözümünde, makul bir hesaplama süresi içinde optimuma yakýn sonuçlar verrnektedir. Yine ayný konuda gerçekleþtirilen bir diðer çalýþmada da, Leu ve arkadaþlarý (Matheson & Rees) tarafýndan gerçekleþtirilmiþtir. Bu araþtýrma ile ilgili olarak 1996 yýlýnda yayýnlanan makalede, kullanýlan yapay zeka tabanlý genetik algoritma yöntemi ile iyi bir sonuç elde edildiði vurgulanmaktadýr. Bir baþka çalýþmada ise Rubin ve Ragatz, tek makina-n-adet iþ, sýralama probleminin çözümü için 1994 yýlýnda yayýnlanan makalelerinde, önerdikleri genetik algoritmalar yaklaþýmýnýn, dai- sýnýr algoritmasý kadar iyi sonuç vermese de, kullanýmýný tavsiye etmektedirler. Bir diðer çalýþmada ise Usher ve Bovvden, 1996 yýlýnda yayýnlanan makalelerinde, bilgisayarla bütünleþik proses planlamada operasyon sýralama pobieminin çözümü için genetik algoritmalarýn kullanýlmasý ile iyi bir performans saðladýklarýný vurgulamaktadýrlar.

GA’larýn çizelgeleme problemlerinde kullanýmý
Bu konuda yapýlan çalýþmalarda, Chen ve arkadaþlarýnýn (Nepalli & Aljaber) 1996 yýlýnda yayýnlanan makalelerinde, akýþ atölyesi çizelgeleme probleminin çözümü için genetik algoritmalar esaslý sezgisel bir yöntem önerilmiþtir. Yine bu makaledeki uygulamada, genitik algoritmalarýn çizelgeleme problemlerinde kullanýmýnýn (daha da geliþtirilebilir) iyi sonuçlar verdiði vurgulanmaktadýr. Bir baþka çalýþmada ise, Murata ve arkadaþlarý (ishibuchi & Tanaka) 1996 yýlýnda yayýnlanan bir makalelerinde, akýþ atölyesi çizelgeleme probleminin çözümü için iki hibrit genetik algoritma önerilmiþtir. Ayný ekibin bir baþka makalesinde ise, bu defa çok- amaçlý genetik algoritmalarý, akýþ atölyesi çizelgeleme probleminin çözümü için önermektedirler. Çok-amaçlý genetik algoritmalarýn; tek-amaçlý genetik algoritmalardan ve Schaffer'in önerdiði VEGA’dan (Vector Evaluated Genetic Algorithm) daha iyi sonuç verdiði vurgulanmaktadýr. Çizelgeleme konusunda yapýlan bir baþka çalýþmada ise, Sakawa ve arkadaþlarý (Kato & Mori) 1996 yýlýnda yayýnlanan makalelerinde, uygulanan genetik algoritmalarýn, çözümü istenen probleme uygun olmasý gerektiðini belirterek; esnekliðin göz önüne alýndýðý, uygun bir genetik algoritmayý, bir iþleme merkezindeki çizelgeleme problemi için önermiþlerdir. Croce ve arkadaþlarýnýn (Tadei & Volta) yaptýðý çalýþma ise, sipariþ atölyesi çizelgeleme probleminin çözümü ile ilgilidir. 1994 yýlýnda yayýnlanan makalelerinde önerdikleri genetik algoritmanýn, gerek önceki GA uygulamalarý gerekse de diðer bazý sezgisel yöntemlere üstünlüðü vurgulanmaktadýr. Bir diðer araþtýrmada, Sikora tarafýndan yapýlan çalýþma 1996 yýlýnda yayýnlanan makalesinde tanýtýlmýþtýr. Bu çalýþmada, parti hacmi ve sýralama kararlarýný beraberce içeren bir çizelgeleme problemi üzerinde durulmuþtur. Önerilen genetik algoritma ile bu zor problemin çözümü gerçekleþtiril-
miþtir.

GA'lann diðer kullaným alanlarý
Bu makalede tanýtma imkaný bulunamayan daha bir çok konuda da, genetik algoritmalarýn kullanýmýna rastlanmaktadýr. Bunlar, bilgisayarla bütünleþik tasarým, gezgin-satýcý problemi, tamir-bakým politikasý, tahmin yöntemleri, daðýtým ve transport poblemleri, Araç-rota problemleri, Paketleme problemleri ve vb. gibi konulardýr.

Genetik Çeþitliliði Göz Ardý Eden Algoritmalar!

Yapýlan araþtýrmalara göre algoritmalarýn, insanlar arasýndaki çeþitliliði görmezden gelen veri tabanlarýna dayalý bir nitelik taþýdýðý saptandý. Ýlgili araþtýrma baðlamýnda, Google aramalarýnda karþýlaþtýðý sonuçlarýn aðýrlýklý olarak 'beyaz' renk yönünde olmasý üzerine 'World White Web Project' adlý siteyi kuran grafik tasarýmcýsý Johanna Burai, konuyla ilgili farkýndalýðýn giderek arttýðýný belirtiyor. Söz konusu farkýndalýðýn en iyi örneðini ise algoritmalarda adaletin saðlanmasý amacýyla kurulan Algorithmic Justice League (AJL) oluþturuyor.

Google ise yöneltilen eleþtiriler baðlamýnda görsel arama sonuçlarýnýn kendi deðerlerinden tamamen baðýmsýz olduðunu belirterek, ilgili sonuçlarýn internet içeriðinde hangi görsellerin yaygýn kullanýldýðý ve bunlarýn nasýl tanýmlandýklarý ile ilgili bir sunum olduðunu belirtiyor.

Öte yandan Massachusetts Institute of Technology'de (MIT) doktora öðrencisi olan Joy Buolamwini, yüz tanýma programýný kullanan yapay zekanýn ten rengi nedeniyle kendisini tanýmadýðýný, bu noktada beyaz maske kullanmak zorunda kaldýðýný belirtiyor. Sýnýrlarý geniþleten Buolamwini'ye göre obeziteli, aþýrý kilolu bireylerde söz konusu algoritmalarýn nasýl çalýþtýðý da ayrý bir araþtýrma konusu. Ayrýca cilt kanserini tanýyan bir algoritmanýn siyah tene sahip bireylerde çalýþýp çalýþmadýðý da yine araþtýrmacýlar tarafýndan AJL'ye danýþýlmýþ.

Algoritmalardaki bir baþka sorunun teknoloji endüstrisinde çalýþanlar içindeki etnik çeþitlilik eksikliði olduðunu belirten Buolamwini, dev teknoloji þirketlerine ait her yýl yayýnlanan çeþitlilik raporlarýnýn da bu tezi desteklediðini öne sürüyor.

Dev Teknoloji Þirketlerinin Yayýnladýðý Çeþitlilik Raporlarý!

• Ocak 2016'da paylaþýlan Google'ýn son raporuna göre þirketin teknik departmanýnda çalýþanlarýn sadece yüzde 19'unun kadýn olduðu, yüzde 1'inin de siyahlardan oluþtuðu belirtiliyor.
• Eylül 2016'da Microsoft tarafýndan yayýnlanan rapora göre çalýþanlarýn yüzde 17.5'inin kadýn ve yüzde 2.7'sinin siyah veya Afrikalý ve Amerikalý olduðu belirtiliyor.
• Haziran 2016'da Facebook'un yayýnladýðý rapora göre ise departmanýn yüzde 17'sinin kadýn ve yüzde 1'inin de siyahlardan oluþtuðu belirtiliyor.

Söz konusu genetik algoritmalara yönelik yapýlan araþtýrmalar, suça eðilimde siyah tene sahip bireylerin beyaz tene sahip bireylere oranla daha yüksek bir orana sahip olduðunu da gösteriyor. Araþtýrmacýlara göre algoritmalardaki taraflýlýðýn kesin bir doðru olarak algýlanmamasý için çözüm odaklý bazý kriterler gerekli.

Önerilen Çözüm Odaklý Kriterler!

• Algoritmalarý eðitmek, geliþtirmek adýna çeþitli veri tabanlarýnýn üretilmesi.
• Program ve yazýlým satýcýlarý arasýnda ilgili alýþkanlýðýn yaygýn hale getirilmesi.
• Karar verme sürecindeki ön yargýlara dair, kullanýcýlarý bilgilendirecek nitelikte algoritmalarýn kurulmasý.

Kaynak: BBC Bilim / Science (15 Nisan 2017)

Kalp Krizi Riskini Tahmin Edebilen Algoritma!

Retina taramasýyla kalp krizi riskini tahmin eden bir algoritma geliþtirildi. Google ve bilimsel araþtýrmalar yapan Verily Life Sciences'ýn geliþtirdiði yapay zeka algoritmasý, retina fotoðrafýndan bir kiþinin 5 yýl içinde kalp krizi ve inme gibi büyük bir kardiyovasküler rahatsýzlýk geçirme olasýlýðýný doðru tahmin edebiliyor.

Yayýmlanan araþtýrma doðrultusunda algoritmanýn öncelikle göz taramasýyla kiþinin yaþý, sigara tiryakisi olup olmadýðý ve kan basýncýyla ilgili tahminlerde bulunduðu belirtildi.Ýlgili faktörleri deðerlendirmede baþarýlý olan algoritmanýn, kardiyovasküler rahatsýzlýk geçirenlerin de aralarýnda bulunduðu 284 bin 335 hastanýn saðlýk verilerini ve retina fotoðraflarýný inceleyerek, kardiyovasküler riskleri tespit etmesi için geliþtirildiði bildirildi.

Bu baðlamda söz konusu algoritmanýn, iki retina görüntüsünden hangisinin büyük bir kardiyovasküler rahatsýzlýk geçirebileceðine iliþkin %70 gibi bir isabet oranýyla tahminde bulunduðu gözlendi.

Kaynak: AA Bilim Teknoloji / Nature Biomedical Engineering (22 Þubat 2018)