goto:encode

Türkçe karakterlerin UTF8 karşılıklarını harcoded olarak girdim geçenlerde. İki tane harf için kendim kod yazmaya üşendim...
php5'de encode_utf8() diye bir fonksiyon varmış. Ne işe yaradığını tam anlamadım, adına bakınca tam hayat kurtaran, ihtiyacım olan şey gibi duruyor ama; Input, sadece ISO-8859-1 string'i alıyor, UTF8 geri gönderiyor. Lan zaten ISO-8859-1 kodları UTF8 içinde aynen bulunmuyor mu? Ne gerek var buna?
Neyse işte bahane bunlar tabi, sonumun goto kullanan şu arkadaş gibi olmasından korkuyorum:

Sevgili Günlük

Bugün Onur tam gün şirketteydi. Çok eğlendik. Keşke her gün gelse...
Ama o çok eğlenmedi sanırım. Çünkü linux kurdurmadılar galiba bilgisayarına.

Paralel Tepe Tırmanma ile Traveling Salesman

TSP yapısı gereği sadece son durumla ilgilenen, geçilen ara adımların önemsiz olduğu bir problem. Mesela satrançta ara adımların tek tek önemi vardır, çünkü rakip de sizin yaptığınıza göre bir hamle yapacaktır. Dolayısıyla TSP gibi bir problemde "bir adet durum tut, bu durumu en iyi hale getirmeye çalış" mantığı benimsenebilir.

Bu mantığın bir adım ilerisi "k adet durumu tut ve en iyi hale getirmeye çalış" mantığıdır. Paralel Tepe Tırmanma (Local Beam Search) bu mantıkla çalışır. O durumun iyiliği, aynı genetik algoritmadaki gibi bir fitness fonksiyonu ile ölçülür. Genetik Algoritma için belirlediğimiz fonksiyon burada da geçerli. (Rotanın toplam uzunluğu; kısaysa iyi, uzunsa kötü)

Paralel Tepe Tırmanma ile TSP genel adımları:

1. K adet rasgele rota oluştur. Aynı rotanın iki kez oluşmadığından emin ol.
2. Bu aşamada yukarıdaki rota kümesinde rasgele swap'lar (iki şehrin yerini değiştirmek) yapılarak yeni oluşan rotalar listeye eklenecek. Burada farklı yöntemler kullanılabilir. Ben 1. adımda oluşturduğumuz her rota için, ardışık komşuların yerlerini değiştirerek yeni rotalar oluşturdum.
3. Bu rotalar fitness değerlerine göre sıralanarak en iyi K tanesi seçilir.
4. İstenen döngü sayısına ulaşılıncaya veya istenen düşüklükte fitness değeri elde edilene kadar 2. adımdan devam edilir.

20 şehirli haritada K=100 için 200'lü döngü içerisinde çalıştırılınca 9 sn. gibi bir sürede, Genetik Algoritma'nın 28 sn.'de ulaştığı sonuca ulaşılabiliyor.

K=50 için 200'lü döngüde çalıştırıldığında 2 sn. sonunda yine GA'nın 28 sn.'de verdiğinden daha iyi bir sonuç alınıyor.

K değeri şehir sayısına bağlı olarak, iterasyon sayısı da K değerine bağlı olarak doğru seçildiğinde oldukça hızlı sonuç alınabiliyor.

Oyun Fikri: Fuzzy Zeppelin or "Reckless Shadows Taller Than Our Soul"

İsim iğrenç evet, yazdığım class'lara bile isim veremeyen bir adamım. Değiştiririz bir ara...

Arcade Space Shooter
(Star Craft, teknolojisi hayvan olan ırkın zeplinleri vardı)

Bir ana gemi olacak, zeplin tarzında bir şey adı "Soul" :S
Ve Minion savaş gemileri. "Shadow"'lar. Hilal şeklinde olurlarsa üç tane belli bir açı ile yan yana geldiğinde achievement veririz, oyun satışları da artar belki.
Ana geminin bir savaş gücü olmayacak.
Küçük gemiler; asıl savaşan bunlar. İlk hedeflerini biz belirleriz, otomatik saldırırlar, (hala yakıt-bombaları kaldıysa, ölmedilerse) bir süre devriye gezerler, geri dönüş rotasında filan çevrelerindeki düşmanlara da saldırırlar.
Kontroller
WASD Mothership
NUMPAD Minion'ların doğrultuları/ilk fırlatıldıkları yön.
Space, shift vs.: bütün gemileri geri çağır, atom bombası?
Ana Gemi
Savaşma gücü yok.
HP
ReGen: Patlayan küçük gemilerin yerine yenilerinin gelme zamanı
Slot: Gemi veya gemi grubu sayısı
Speed?
Küçük Gemiler
HP
Attack Power
Speed
Range?
Perception/Radar Range, ilk doğrultularını biz belirledikten sonra bu radar range içindeki düşmanları görüp, yön değiştirebilirler.
Ammo: Bombası bitene kadar düşman arar.



Başka fikri olan?

Genetik Algoritma ile Traveling Salesman

Program "pure" genetik algoritma üzerinde çalıştığından, 2-opt, greedy vs. bir heuristic kullanan genetik algoritmaya göre daha yavaş sonuca ulaşır. Bu algoritmanın genel adımları şöyle:

1. Tüm şehirlerden bir kez geçilen bir "rota" oluştur. Bu işlemi genetik algoritma X nüfus üzerinde çalışacaksa X kez tekrarla. Tabii aynı rotanın 2 kez olmaması için gerekli önlemleri de almak gerek. Bu rota bizim kromozomumuz olacak.
2. Rulet tekeri yöntemi veya sıralama seçimi kullanarak 2 rotayı ebeveyn olarak seç. Kısaca daha iyi durumdaki yollara daha yüksek olasılık vererek 2 adet rota seçilecek.
3. Seçilen ebeveyn kromozomlar özel bir yöntemle çaprazlanacak. Normal çaprazlama TSP'de işe yaramıyor çünkü bir kromozomda aynı şehir iki kez bulunmamalı. Keyword: Order-based crossover
4. Oluşan çocukların küçük bir ihtimal mutasyona uğrama şansı var. Mutasyon işlemi random iki şehrin yerinin değiştirilmesi şeklinde olabilir.
5. Çocuklar en kötü iki rota yerine geçiyor. Böylece her jenerasyonda nüfusun iyiye gitmesi sağlanmaya çalışılıyor.

Burada bir rotanın iyi mi kötü mü olduğu değerlendirilirken (fitness function) o rotanın toplam uzunluğu dikkate alınıyor. Uzunsa kötü, kısaysa iyi. 20 şehir içeren bir haritada bu algoritma çalıştırılırken iyi bir sonuç alabilmek için 100000 nüfusun 1000 jenerasyon boyunca yaşaması gerekiyor. 28 saniye sürüyor çalışması. Multi-threaded kodlanırsa düşer tabii bu süre. Bir de benim dandik kodlamış olma ihtimalim var :)

Mutasyonu yüzde 10 yapınca, yüzde 5'e göre sonuç kötüleşiyor. Yani mutasyon olayını abartmamak gerekiyor.

Burada önemli bir faktör, heuristic kullanılsaydı daha az nüfus ve daha kısa bir jenerasyon süresi sonunda aynı veya daha iyi bir sonuca ulaşmak mümkündür.

Sonraki yazı Paralel Tepe Tırmanma (Local Beam Search) ile çözümü anlatacak.