Bu makalede, yapay
zeka tekniklerinden, genetik algoritma kullanarak bir sayfada yer alan makaleleri
iki sütunda gösterme işlemini, en az satırda en çok makale özeti olacak şekilde
optimize edeceğiz. Genetik algoritma, bir çözümün en iyisini bulmak için özellikle
çok fazla ihtimalin karşılaştırılması gerekiyorsa, kullanılabilen bir "meta-heuristic"
yoptimizasyon yöntemidir ve her zaman en iyiyi bulmayı vaadetmediği halde, hep
en iyiye yakın çözümlerden birini elde etmemizi sağlar.
1.Giriş
Optimizasyon, hayatın
hemen her alanında gerekliliği kaçınılmaz bir kavram olup, kazancı maksimize
veya kaybı minimize etmeyi hedefler. Bu amaç için bir çok yöntem kullanılabilir.
Şayet kullanılan yöntem(veya algoritma) parametreleri belli bir probleme her
uygulanışında aynı sonucu veriyorsa, bu tür yöntemlere deterministik yöntemler
denir. Deterministik yöntemler, genellikle en iyi bir tek çözüm için kodlanırlar.
Deterministik yaklaşımlar
her durum için, kaynaklar nedeniyle mümkün olmayabilir. Örneğin bir satranç
oyunu yazarken, bir taşın bir hamlesinin oyunun sonucuna etkisini denetlemek
gerkir. Bu amaç için oluşturulan oyun ağacı(game tree) bu karmaşıklığa örnek
verilebilir. Böyle bir oyun ağacında, ortalama olarak en iyi hamleyi seçmek
için hamle başına (35^50^)^2 olasılığı denemek gerekir. (Satranç için Game Tree
ile ilgili Internetten araştırma yaparak formülün kaynağını bulabilirsiniz).
Alfa-Beta budaması, min-max arama benzeri olasılık azaltma yöntemleri ile bu
sayı belli oranlarda azaltılsa bile bu türden bir deterministik programı, şu
anda sıradan bir PCde çalıştırmak olası değildir. Bu tür durumlarda bir yaklaşım
olarak deterministik olmayan(non-deterministik) yöntemlerin kullanımı ele alınabilir.
Deterministik olmayan
yaklaşımlar, aynı durum için farklı çalışmalarında aynı sonucu garanti etmeyen
yöntem veya algoritmalardır. Yani bir satranç oyununda aynı pozisyon için program
ilk çalışmasında A7 karesine oynamayı çözüm olarak verdiği halde, sonraki denemede
A3ü uygun çözüm olarak verebilir.
Meta Sezgisel(meta-heuristic)
yöntemler deterministik olmayan yöntemlerin bir alt grubudur ve en iyi çözümü
garanti etmemekle birlikte, denenmesi gereken ihtimallerin çok fazla olduğu
durumlarda, daha az deneme ile "iyi" bir çözüm önermek amacıyla kullanılırlar.
Genetik algoritma, 1970li yıllarda John Holland tarafından ortaya atılmış,
1989 yılında David E. Goldbergin yayınladığı, uygulanabilirliğin çeşitli alanlarda
gösterildiği bir kitap ile popülerlik kazanmıştır.
Problem
Bizim bu makalede
ele alacağımız problemin, deterministik yöntemlerle çok basit bir çözümü olmasına
rağmen, genetik algoritmayı kavratması açısından basit bir örnek olduğu için,
genetik algoritma ile ele alacağız.
Özet olarak problem
şu, Elimizde 2n kadar makale var. Ama bu makaleleri iki sütunda göstermek istiyoruz.
Bu durumda ikisi eşit olmayan makaleler, aynı satıra geldiğinde belli bir boşluk
oluşacaktır(Şekil 1). Bu nedenle de bu boşlukları azaltacak bir yöntemi genetik
algoritma ile hesaplamayı ele alacağız. Sorun ve çözümü şekil.1 ve şekil.2 de
görülmekte.
Şekil 1 : Rasgele veya uzunluk dışında bir unsura göre sıralanmış,
örneğin yayına giriş tarihi, makale yerleşimi. Boşluklar turuncu ile gösterilmiştir.
Şekil 2 :Yerleşimdeki boşlukların optimize edilmiş hali. Birbirine
yakın sayıda satır kaplayan makaleler yan yana getirilerek çözüm elde edilmiştir.
Elimizdeki makale
sayısını 100 olarak düşünürsek, olasılıklar üstünden ilerlediğimizde, 100 makalenin
100! Farklı şekilde dizilebileceğini görürüz. Genetik algoritmayı, rastgele
sıralanmış makalelerden başlamak üzere, genetik operatörler yardımıyla en iyiye
yakın dizilişleri elde etmek için kullanacağız. Bu olasılıkları denemeye göre
oldukça kolay bir deterministik çözümü ayrıca, makalenin en sonunda sizlerle
paylaşacağım.
Genetik Algoritmaya
Hızlı Bir Bakış
Genetik Algoritmadan
burada kısaca bahsedeceğim. Daha geniş bilgi için, Internetten arama yapabilirsiniz.
Konunun daha iyi anlaşılması için terimlerle birlikte genetik algoritmayı tanımaya
çalışalım.
Çözümün her bir
parçasına gen denir. Aslında çözüm, aynı genlerin farklı dizilişlerinden
en iyi olanı seçmektir. Bizim örneğimizde, yerleştirilmesi gereken her makale
bir gendir. Genlerden her birinden eksiksiz-fazlasız sadece bir adet bulunduran
her bir yapıya birey(veya kromozom) denir. Örnek durum için
iki farklı birey, şekil.1 ve şekil.2de görülmektedir. Bu iki durum için, gen
sayısı 4 diye düşünebiliriz. Dikkat edilirse, bireyler arasında değişen tek
şey, genlerin sırasıdır. Her bir bireyin gen sıralarındaki bu farklılıklarının
çözüm üstündeki etkisini yansıtacak tek bir fonksiyon bulunur. Bu fonkisyon
probleme bağlıdır ve bireyin çözüme yaklaşmasını ifade edecek bir hesaplamadan
ibarettir. Bu fonksiyona uygunluk fonksiyonu(fitness function) denmektedir.
Bu fonksiyondan elde edilen sonuca da birey uygunluk değeri
denmektedir. Birden fazla bireyden oluşmuş bireyler topluluğuna populasyon
denir. Literatürde, iyi bir çözüm için, genetik algoritmanın 100 ile
300 bireyden oluşan bir populasyon ile çalıştırılması önerilmektedir.
Herhangi bireyde,
genlerin dizilişlerinde bir kurala bağlı olmaksızın, nedensiz ve düşük ihtimallerle
meydana gelen değişikliğe mutasyon denmektedir. Çaprazlama
, populasyonda yer alan iki bireyin karşılıklı ama rastgele bir veya
daha fazla noktadan bölünüp bu parçaların birleşmesi sonucunda ortaya çıkan
ve her iki bireyden de farklı olan iki birey üretmeye verilen addır. Bu işlemin
sonucunda, her iki bireyde de tekrarlayan ve dolayısıyla da eksik kalan genler
olabilir. Bu nedenle bir tamirat yapmak gerekecektir.
Nesil (Jenerasyon),
popülasyondan çaprazlama, mutasyon ve elitizm gibi yöntemlerle elde edilen ve
onun yerini alan yeni birey topluluğuna verilen addır. Elitizm ,
bir popülasyondaki en iyi n bireyin, yeni popülasyona hiç bir işleme
tabi tutulmadan, kontenjandan aktarılmasıdır. Bu kontenjana elitizm kriteri
denir. Burada amaç, bir önceki neslin kazanımını korumaktır. Ancak çok fazla
bir sayı verilirse egemen birey sorunu başlar ve en iyi başka bir bireyin türetilmesi
zorlaşır.
Genetik algoritmanın
kaç nesil veya hangi doğruluk değerine kadar devam ettirileceği problemi çözen
kişiye kalmış bir seçimdir. Basitçe problem şu şekilde uygulanır:
- Rasgele veya
bir kurala bağlı olarak bir başlangıç popülasyonu oluşturulur.
- Bu popülasyondan
elitizm, çaprazlama ve mutasyon sonucunda yeni popülasyon oluşturulur
- Elitizm yapılacaksa,
oluşturulmuş pülasyon için uygunluk değerleri hesaplanır ve en iyi n değer
kontenjandan yeni nesle aktarılır. Burada n parametrik olabilir.
- Çaprazlamaya
girecek bireyler, rastgele veya Rulet Tekerleği ile seçilebilir. Biz rastgele
seçtik. Rulet tekerleği için Internetten arama yapabilirsiniz.
- Çaprazlama
tek noktadan böldükten sonra veya birden fazla noktadan böldükten sonra,
karşılıklı genleri değiştirerek yapılabilir.
- Çaprazlama
sonucunda doğan yeni iki bireyden her ikiside veya sadece bir tanesi veya
belli bir doğruluk değerinin üstündeki bireyler alınabilir.
- Mutasyon işlemi
için verilen oran dahilinde bireyler mutasyona tabi tutulur.
- 2 nolu işleme,
belli bir nesil sayısı kadar veya en iyi bireyin belli bir uygunluk değerine
kadar devam edilir.
- Bu işlemlerden
sonra en iyi birey çözüm olarak alınır.
Gerçekleme
Yukarıda özet olarak
geçilen genetik algoritma, makale özetlerinin yerleşim planlarını optimize etme
sorununa adapte edilirken, kullanılan araç ve yöntemleri bu bölümde ele alacağız.
Dil olarak C#, veritabanı olarak taşınabilirliğindeki kolaylık nedeniyle MS
Access ve ortam olarak da ASP.NET sayfalarını kullanacağız. Buradaki istatistikler,
Intel Centrino 1.6 GHz işlemci ve 512MB RAM üstünde, Windows XP Professional
işletim sistemi üstündeki deneyleri yansıtmaktadır.
Veritabanı
Veritabanı olarak
MS Access kullanacağız. Bu, herhangi bir sitedeki makalelerin tutulduğu temel
tablo olabilir. icerikKOD sütununda her bir makaleye ait tekil kod
tutulmaktadır. baslik, Her bir makalenin başlığını tutan sütundur.
Spot , her bir makaleye ait özetlerin yer aldığı sütundur. baslangicTarihi
, makalelerin yayına giriş tarihini, durum makalenin yayında olup
olmadığını, son olarak bitisTarihi de makalenin yayından kalkacağı
tarihi göstermektedir.
Diğer sütunlar,
buradaki problemin bir parçası olmamasına rağmen bir içerik yönetim sisteminde
bulunması gereklilik arzettiğinden burada da yer almaktadır. icerik,
makalelerin içeriğini göstermektedir. kategoriKOD , her bir makalenin
hangi kategori altında çıkacağını göstermektedir.
Şekil 3 : Probleme uygun örnek veritabanı tasarımı
Amacımız, şu anda
yayında olan makalelerden, yayın tarihine göre baştan 2n adedini seçip, düzgün
bir şekilde sayfaya iki sütun halinde en az yer kaplayacak şekilde yerleştirmeyi
sağlamaktır.
Bu tasarım ve içerisine
eklenmiş 50 kadar makale bilgisinden sonra, veri katmanı ile işimiz bitti. Şimdi
iş katmanını kodlayalım:
Şekil 4 :Kullanacağımız birimlerin UML Class diyagramı
Gen Yapısı
Karşılaştırmaların
hızlı olması açısından, gen bilgileri stack türü bir değişken ile gerçekleştirilmiştir.
Yapıyı şu şekilde oluşturalım:
Şekil 5 : Gen structının yapısı
Genler, her bir
makaleye ait bilgileri tutmaktadır. Her bir bireyde, bu genlerden, sayfaya yerleşecek
makale sayısı kadar bulunacaktır.
Birey Sınıfı
Birey sınıfını
özet olarak şu şekilde kodlayalım. Detaylar için ekteki kodları gözden geçirebilirsiniz.
Burada, özellik ve metodları özet olarak ele alacağım. Öncelikle, Birey sınıfı,
IComparable arayüzünü gerçeklemektedir. Çünkü, birazdan kodlayacağımız, Populasyon
sınıfının ArrayList bir özelliğinde, bireyler tutulmakta ve bu bireyler, yeri
geldiğinde ArrayList.Sort() metodu yardımıyla, uygunluk(fitness) değerlerine
göre sıralanmaktadır. Bu sıralama için, birey sınıfının IComparable arayüzünü
gerçeklemesi(CompareTo metodunun gerçeklenmesi) gerekmektedir
Şekil 6 : Birey sınıfının özet bir görünümü
Uzunluk özelliğinde,
bireydeki gen sayısı tutulmaktadır. gecerliDogruluk özelliği, çözüme
uygunluk derecesini tutmaktadır ve default değer olarak 100 verilmiştir. Boş
geçen her bir satır için, bir puanlık ceza verilmektedir(uygunluk hesaplaması
bu şekilde kurgulanmıştır). bireyGenleri dizisinde, herhangi bir bireye
ait genlerin dizilişleri tutulacaktır. caprazlanacakBirey, bir Birey sınıfını
işaret etmekte olup, çaprazlama aşamasında, dışarıdan gelen nesneyi tutmak üzere
kodlanmıştır. yeniBirey1, çaprazlamanın sonucunda elde edilen yeni bireyi, yeniBirey2
de aynı çaprazlamadan çıkan ikinci bireyi göstermektedir.
CaprazlanacakBirey
, sadece yazılabilir bir özellik olup, dışarıdan gelen bir Birey nesnesini,
private değişkene aktarmaktadır. GecerliDogruluk da okunabilir bir
özellik(property) olup, bireye ait geçerli uygunluk değerini vermektedir.
YeniBirey1 ve YeniBirey2
özellikleri de birer sadece okunabilir özellik olup, çaprazlamadan sonra oluşan
bireylerin okunmasını sağlamak amacıyla ekledik.
Bunların dışında,
birey sınıfına ait iki adet yapıcı metod bulunmakta. Bunlardan biri boş bir
birey türetirken, diğeri, başlangıç aşamasında kullanılmak üzere yazılmış bir
aşırı yükleme ve dışarıdan bireye ait genleri alarak işe başlamakta.
GenleriTanimla
metodu, boş bir bireyin genlerini gen havuzundan rasgele seçip bütün genleri
bir defa barındıran birey haline getirmek için kullanılmaktadır. Bu nedenle,
Birey sınıfının kendisine özel bir metoddur.
BireyCaprazla metodu
dışarıdan da çağrılabilmektedir. Ancak bu metod çağrılmadan önce, CaprazlanacakBirey
özelliği ile, eldeki birey nesnesine, çaprazlanacağı bireyin atanması gerekir.
Mutasyon metodu,
belirtilen mutasyon oranı olasılığında bir rastgele sayı üretip, elde edilen
sayının aralığına bakarak rasgele iki genin sıralarını değiştirip değiştirmeyeceğine
karar vermek üzere kodladığımız herkese açık bir metoddur.
Son olarak GenTamircisi
metodu, genlerin mutasyon sonucunda bozulmaları halini denetleyip, her şeye
rağmen her genden birey başına sadece bir adet kullanıldığını ve eksik gen bulunmadığını
garanti etmek üzere oluşturulmuş bir metoddur.
Burada, özellikle
ele alınması gereken bir metod olarak RandomSayiUretici metodunu ele almakta
fayda var. Çünkü Web uygulamaları, belli bir çekirdek değer ile başladıklarından
her bir istek geldiğinde aynı rastsal sayıyı üretirler. Bunu önlemek için, Birey
sınıfının bu metodunda bir rasgele sayı üreticisi temel kütüphane(base library)den
türetilmiş ve http response buffera kaydedilerek durumunu her bir istek için
koruması sağlanmıştır. Böylelikle, her seferinde aynı çekirdek değer ile başlayan
rastsal sayıların üretimini engellemiş olduk.
Popülasyon Sınıfı
Kodlayacağımız
en kapsamlı sınıf olan Populasyon sınıfına bir göz atalım:
Herkes tarafından
erişilebilir bir genHavuzu adında gen dizisinden oluşuyor. Bu dizi, sınıfın
özel GenHavuzu() adlı metodu tarafından veritabanına bağlanılarak doldurulmakta.
Bir nevi Nuhun gemisi diyebileceğimiz bu dizinin amacı, her genden bir adet
bulundurarak, eksik genin tespitini kolaylaştırmak.
mutasyonIhtimali
değeri bir float değer olup, %1 başlangıç değeri ile tanımlı ve bir bireyin
mutasyona uğrama ihtimalini tayin etmek için kullanılmakta.
bireySayisi özel
değişkeninde, popülasyonun bulunduracağı birey sayısı tutulmakta. IterasyonSayisi
ise, genetik algoritmanın kaç adım çalıştırılacağını göstermekte ve 10 başlangıç
değeri ile tanımlı.
Şekil 7 : Populasyon sınıfının özet bir görünümü
YeniPopulasyon,
asıl genlerin değişimini ve bireylerin gelişimini sağlayan bir metod. Bu metoda,
sırayla bütün bireyler için doğruluk değeri hesaplanmakta, ardından en iyi bireyler
elitizm kriteri dahilinde yeni nesile aktarılmakta. Ardından kalan kontenjan,
rastgele seçilen iki bireyin çaprazlanması ile elde edilen iki yeni birey her
seferinde aktarılarak yeni nesil oluşturulmakta ve son olarak da nesil mutasyona
tabi tutulmaktadır. Bütün bu işlemler, iterasyon sayısı kadar tekrarlanmaktadır.
EnIyiBirey metodu,
eldeki popülasyonu, ceza puanına göre sıralayarak en az ceza alan bireyi döndürmektedir.
ASP.NET Ortamına
Dair Bazı Düzenlemeler
ASP.NET ortamında,
daha uygun bir bağlantı ifadesi için, Access veritabanının yolu Server.MapPath
ile çekilip, Global.ConnStr adı ile erişime hazır hale getirilmektedir.
Yine ASP.NET uygulamasının
CodeBehind sayfasından, bir adet Populasyon nesnesi nüshalandırılmakta ve bu
nüsha üstünden, genetik algoritma çalıştırıldıktan sonra en iyi birey, yine
bu arka plandaki derlenmiş dosya tarafından, bir döngü içerisinde,( en iyi bireye
ait gen dizisi) HTML ortamına yazdırılmaktadır.
Şekil 8 : Mükemmel olmasa da iyi bir yerleşim planı elde edilmektedir.
Sonuç
Her ne kadar, deterministik
yöntemlerle rahat bir şekilde çözülebilecek bir sorunu ele almış olsak da, neticede
genetik algoritmanın bu konuda ne kadar başarılı olduğu görülmektedir. Olayın
kötü tarafı, genetik algoritma gibi meta-sezgisel yaklaşımların bir iterasyon
mantığı dahilinde iyileştirmede bulunması ve burada kullanılan sunucu taraflı
programlamanın da iterasyonlara karşı zayıf bir platform olması en azından bugünkü
kaynaklarla bu tekniğin pratikte pek uygulanabilir olmadığını göstermektedir.
Başta söz verdiğim
üzere, deterministik çözüme yer verelim; makale özetlerini uzunluklarına göre
sıraladıktan sonra, mod 2ye bağlı olarak ikişerli yan yana koyduğumuz zaman
çok iyi bir çözümü elde edebiliriz. Ancak bu yöntem örneğin güncel makalelerin
daha üstte çıkmaya meyilli olduğu bir esnek çözüme müsaade etmez.
Şekil 9 : Uzunluklarına göre sıralanmış makaleler
Şekil 10 : Makalelerin Deterministik yaklaşım ile sıradan mod
2 ile ikili sütunlanmış hali
Şekil 11 : Eşit uzunluktaki makaleleri yan yana getirmeyi azamiye
çıkararak elde edilmiş bir diğer deterministik optimizasyon her zaman olmasa
da bazı durumlarda aynı sonucu vermekte.
Uygulama
Projesi
Kaynaklar
[1] "Web Newspaper
Layout Optimization Using Simulated Annealing" Gonzalez, J.; Rojas, I.; Pomares,
H.; Salmeron, M.; Merelo, J.J.; IEEE Transactions on Systems, Man and Cybernetics,
Part B, Volume: 32 , Issue: 5 , Oct. 2002 - Pages:686 – 691
Makale:
Genetik Algoritma Kullanarak Makale Yerleşimi Optimizasyonu C#, Visual C# ve .NET Yaşar Gözüdeli
|