Bilal Saim

Sezgisel Optimizasyon Algoritmaları (Heuristic algorithms)

Yöneylem araştırmaları belirli bir soruna yönelik en uygun çözümün bulunmasını içeren yöntemler bütünüdür.

Yöneylem araştırmaları belirli bir soruna yönelik en uygun çözümün bulunmasını içeren yöntemler bütünüdür. Dünyanın gerçek karmaşık sorunlarına matematiksel modelleme, algoritma ve istatistik gibi bilimsel yöntemleri kullanan bir bilim alanıdır. Soruna en uygun çözümün bulunmasını optimizasyondur. En uygun çözümün bulunması istenen sorunlar ise Optimizasyon Problemleridir. Genelde NP-Karmaşıklık(NP-Complete), Karar Problemleri(Decision Problems) gibi problemlerin çözümünde kullanılır.

Optimizasyon problemleri uygunluk fonksiyonumuzun minimum veya maksimum yapmaktır. Yani bir şirketteki verimliliği arttırmak maksimuma optimizasyon yapmakken, şirketteki bir işin süresini azaltmak minimuma optimizasyon yapmaktır. Aslında günlük hayatımızda optimizasyon durumuyla bir çok kez yüzleşiriz. Örneğin ben bu makaleyi yazarken aynı açıklamayı verecek daha kısa cümleler kurmaya çalışmam minimuma optimizasyon yaparken, bugün daha fazla ve verimli nasıl çalışırım sorusuna yanıt ararken ise maksimuma optimizasyon yapmaktır. Optimizasyon problemleri matematiksel modeldeki karar değişkenlerin yapısına göre kesikli (discrete) veya sürekli (continuous) optimizasyon olarak ayrılır. Bazı yerlerde kesikli optimizasyonu kombinatoryal (combinatorial) adıyla görebilirsiniz. Kesikli optimizasyon değişkenleri kısıtlı bir küme içerir. Örneğin meşhur Gezgin Satıcı Problemi (Travelling Salesman Problem) kesikli optimizasyonla çözülür. Sürekli optimizasyon problemleri değişkenlerinde kısıtlama olmayan problemlerdir.

Sezgisel Optimizasyon Algoritmaları ise yöneylem araştırmalarının içinde kendine Optimizasyon Problemlerine çözüm bulmak için yer bulur. Çözülmesi istenilen gerçek hayattaki bir sorunun ilk önce bir matematiksel modele dökülmesi gerekir. Böylece bulunan bu matematiksel formülü kıstas olarak kullanarak en iyi çözümü kısa sürede bulmayı hedefler. Sezgisel Optimizasyon Algoritmaları en mükemmel çözümü bulmayı garanti etmez. Algoritma ne kadar kısa sürede ne derece iyi çözüme ulaşıyorsa o kadar etkili kabul edilir.

A.Örnek Algoritmalar

A.1 - Genetik Algoritmaları (Genetic Algorithms)

Genetik algoritmaları evrim algoritmalarının alt kategorisidir. Mutasyon, çarprazlama, seçilim gibi özellikleriyle evrim teoreminden esinlenmiştir. 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, çizelgeleme problemleri, sosyal ve ekonomik planlama problemleri gibi bir çok farklı alanda kullanılırlar.

 

A.2 - Sürü Zekası (Swarm Intelligence)

Sürü algoritmaları doğada sürülerin hareketlerinden esinlenerek oluşturulmuş arama algoritmalarıdır. Sürü bireyleri birbirleriyle etkileşim halinde belli bir soruna çözüm getirirler. Bir çok sürü algoritması mevcuttur. Bunlardan meşhurları Parçacık Sürü Algoritması(Particle Swarn Optimization), Yapay Arı Kolonisi(Articial Bee Colony), Karınca Kolonisi(Ant Colony), Ateş Böceği Algoritması (Firefly Algorithm)

A.3 - Tabu Araması (Tabu Search)

Çözüme götüren adımlarda tekrarlı hareket yapılmasını önlemek üzere bir sonraki adımlarda tekrarın yasaklanmasıdır. Böylece en iyi çözüme ulaşmada çözümlerin araştırılması için bölgesel araştırma yapılır.

A.4 – Benzetmeli Tavlama (Simulated Annealing)

Benzetmeli tavlama algoritması büyük bir arama uzayı olan bir fonksiyon için en uygunun makul bir yaklaşımını verebilir. Yer yinelemede olasılıksal olarak mevcut durumda kalma veya başka duruma yönelme arasında karar verir. Böylece sistemi düşük enerjiye yönlendirir. Elektronik devre tasarımı, görüntü işleme, yol bulma problemleri, seyahat problemleri gibi problemlerin çözümlerinde yaygın kullanılır.

 

A.5 - Yapay Sinir Ağları [YSA] (Artificial Neural Networks [ANNs])

Yapay sinir ağları elde edilen eğitim verilerinden yeni örnekleri kategori eden, örüntü(pattern recognition) tanıma ve makina öğrenmesinde gayet işlevsel modellerdir. Hayvanların beyinlerindeki nöron işleyişini esinlenerek geliştirilmiştir. Konuşma analizi, görüntü işleme, gibi bir çok alanda kullanılır.

 

A.6 – Destekçi Vektör Makinesi (Support Vector Machines)

Destekçi Vektör Makinesi eğitim verilerini yapay zeka ile kullarak örüntü tanıyan ve verileri analiz eden modellerdir. Bu algoritmalar regresyon analizi ve sınıflandırma amaçlı kullanılırlar. Örnek veriler kullanılarak, algoritma yeni örnekleri gruplar halinde sıralayacaktır. Bu SVM'ler, makine öğrenmesinde, sistemlerin veriden öğrendiği yapay zekanın bir alt kümesidir ve yeni örnekleri analiz etmeden önce eğitim verileri gerektirir.

 

B.Örnek Problemler

B.1 – Gezgin Satıcı Problemi (Traveling Salesmen Problem)

Birbiriyle uzaklıkları verilen şehirler arasında gezgin satıcı tüm şehirlere bir kere uğramak koşuluyla en düşük mesafenin çözülmesi problemidir.

B.2 – N-Vezir Problemi (N-Queen Problem)

Bir santranç tahtasına N kadar veziri bir birlerine saldırı noktaları olmayacak şekilde tahtaya dizilmesi problemidir.

 

C.Çalışma Mantığı

Çalışma mantıklarından biraz bahsedelim. Sezgisel Optimizasyon Algoritmalarıyla bildiğiniz üzere elimizde var olan probleme arama uzayından en iyi çözümü en kısa sürede bulmayı hedefler. Şimdi probleme gelelim. Diyelim ki biz hacmi 500 olan bir kutuya 3 farklı hacime sahip şekilleri yerleştireceğiz. Söz gelimi formüller yazalım. İlk cisim bir en alt uzunluğunun karesi kadar, ikinci cisimde aynı şekilde, son cisim küpü kadar alan kaplıyor olsun. Biz x12+ x22+ x32=500 gibi bir matematiksel model çıkarabiliriz ve problemindeki x1, x2 ve x3 değerlerini arama uzayında bulmaya çalıyoruz. Arama uzayı x1 , x2 , x3 parametre değerlerinin maksimum ve minimum alabileceği değer aralığını ifade ediyor. Elimizdeki problemin denkleminde kullanacağımız parametrelerin bir limitini oluşturmak çözüme ulaşmayı hızlandıracaktır. Eğer limit oluşturulmazsa tüm parametreler için sonsuz sayıda bir küme ortaya çıkacak. Arama uzayı ne kadar kısıtlıysa o kadar hızlı sonuca gideriz. Arama uzayını kısıtlamak için her bir parametrenin alabileceği en küçük ve en büyük değerleri belirlemeliyiz. Böylece daha hızlı bir şekilde çözüme yaklaşabiliriz. Tabi daha iyi çözüm olabilecek değerleri arama uzayının dışında bırakmamaya gayret edip dikkatlice arama uzayı belirlenmelidir. Sizde elinizdeki probleme göre parametre değer aralıklarını belirlemelisiniz. Ben problemimde x1 , x2 , x3 için -30 ile 30 arasındaki değerlerin bir çözüm üretebileceğini düşünerek bu limiti belirledim. Ayrıca problemi çözerken kutuda hiç yer kalmayacak şekilde uygunluk fonksiyonumuzu formülüze ettiğimizi düşünelim. Bu durumda kutudaki kalan yerin minimize edilmesi anlamını taşır. Başlangıç olarak rastgele çözüm kümeleri oluşturularak bu oluşan çözüm kümelerin uygunluk değerleri bulunur. Rastgele 3 çözüm kümesi oluşturalım:

1-) x1 =10, x2 =15, x3 =-6

2-) x1 =-25, x2 =29, x3 =10

3-) x1 =10, x2 =10, x3 =4.

Şimdi bu çözüm kümelerinin uygunluk değerlerini hesaplamalıyız. Uygunluk değerinden kasıt parametreler denkleme konularak problemin çözümüne uygunlukları bakılır. Değerleri yerine koyarak 500 den yani problemimizin eşitliğinden çıkartarak sonucun 500 den ne kadar uzak olduğunu kontrol edeceğim. 500 den büyük veya küçük biz net uzaklığı almamız gerektiği için mutlak değer kullanmalıyız. Burada uygunluk değerinin daha indirgenebilir olması için 0 ile 1 arasında olacak şekilde formülüze etmeniz yararınıza olacaktır. Ben 1/(1+Sonuç) olarak formülüze ettim.

1-) 102+152+-63 = 500 à|500-109| = 391 = 1/(1+391) = 0.0025

2-) -252+292-103 = 500 à |500-466| = 34 = 1/(1+34) = 0.028

3-) 102+102+43 = 500 à |500-264| = 236 = 1/(1+236) = 0.0042

Bu değerler bulunduktan sonra arama algoritmaları kendilerine özel işlemler uygulayarak bu sonuçlardan daha iyi çözüm kümelerine ulaşmayı hedefler. Burada oluşturduğumuz formülden dolayı en iyi çözüm kümesinde 1 değeri döndürür.

Sezgisel Optimizasyon Algoritmalarının çoğunun çalışma mantığını anlamanız için yukarıdaki örneği verdim. Çözüm kümelerini başlangıçta arama uzayında rastgele belirledik. Benim kurguladığım matematik fonksiyon tamamen örnek amaçlıydı. Ayrıca sezgisel optimizasyon algoritmalarının performansını test etmek için matematik fonksiyonlar mevcut. “Optimizasyon için Test Fonksiyonları” adlı makalede inceleyebilirsiniz.

Sonraki yazılarımda arama algoritma örneklerine bakarak anlatılanları pekiştirebilirsiniz.

Sezgisel optimizasyon algoritmalarına örnek olarak;

Genetik Algoritma (Genetic Algorithm)(GA)

Karınca Kolonisi Optimizasyonu (Ant Colony Optimization)(ACO)

Parçacık Sürü Optimizasyonu (Particle Swarm Optimization)(PSO)

Yapay Arı Kolonisi (Artificial Bee Colony)(ABC)

Diferansiyel Gelişim Algoritması (Differential Evolution Algorithm) (DEA)

Benzetim Tavlama (Simulated Annealing)(SA)

Yerçekimi Arama Algoritması (Gravity Search Algorithm)(GSA)

Gaz Brownian Hareketi Optimizasyonu( Gases Brownian Motion Optimization) (GBMO)

Isı Transferi Arama (Heat transfer search)(HTS)

Elektromanyetik Alan Optimizasyonu (Electromagnetic Field Optimization) (EFO)

Optikten Esinlenen Optimizasyon (Optic Inspired Optimization)(OIO)

Ağırlıklı Süperpozisyon Çekimi (Weighted Superposition Attraction (WSA)

Orman Optimizasyonu Algoritması (Forest Optimization Algorithm)(FOA)

Kasırga Temelli Optimizasyon Algoritması (Hurricane Based Optimization Algorithm)

Ateş Böceği Algoritması (Firefly algorithm) (FA)

Ağaç-Tohum Algoritması(Tree-Seed Algorithm)(TSA)

Bu makaleyi paylaş

Bilal Saim

Bilal Saim kişisel blog sitesi. Yazılımcı, gençlik çalışanı, gezgin.

Related posts

Yorum yap


Bu sayfa 0,3873 sn de hazırlandı