Optimizasyon Algoritmaları

Bir önceki yazımda optimizasyondan bahsetmiştim. Bu yazımda ise optimizasyonu çözmek için geliştirilen algoritmaların birkaç tanesinden bahsedeceğim.

Optimizasyon algoritmaları Kesin Metotlar(Exact Methods) ve Yaklaşık Metotlar(Approximation Methods)

1. Kesin Metotlar: Problemin global optimum cevabını bulan metot ya da algoritmalardır.
   Ör: Doğrusal Programlama, Dinamik Programlama

a) Doğrusal Programlama: Bir optimizasyon modeli eğer sürekli değişkenlereve tek bir doğrusal amaç fonksiyonuna sahipse ve tüm kısıtlamaları doğrusal eşitlik veya eşitsizliklerden oluşuyorsa, doğrusal (lineer) program olarak adlandırılır. Başka bir deyişle, modelin tek-amaçlı fonksiyonu ve tüm kısıtlamaları, süreklilik gösteren karar değişkenlerinden oluşmalıdır. Doğrusal (lineer) programlamadaki doğrusal (lineer) sözcüğü, modeldeki tüm matematiksel fonksiyonların doğrusal (lineer) olması gerektiğini belirtir.Fazla matematiksel olmayan terimler ile, bir seri doğrusal eşitlik veya eşitsizlik şeklinde ifade edilmiş koşullara bağlı olarak (en küçük maliyet veya en büyük kâr gibi) en iyi sonuca varılmasıdır.( https://ipfs.io/ipfs/QmT5NvUtoM5nWFfrQdVrFtvGfKFmG7AHE8P34isapyhCxX/wiki/Do%C4%9Frusal_programlama.html)

Matris notasyonu kullanılarak:

Burada
c amaç fonksiyonu katsayılarını (1xn) kapsayan vektördür ve T-üstü transpoz notasyonu olup
x değişkenleri kapsayan bir (1xn) vektördür.
A bir (mxn) katsayılar matrisidir.
b (mx1) sol-tarafta olan sabit değerler vektörüdür.

Doğrusal programlama problemlerini çözmek için algoritmalar geliştirilmiştir. Simpleks ve Karmarkar algoritmaları doğrusal programlama problemlerini çözmek için geliştirilmiştir.

b)Dinamik programlama: Karmaşık bir problemi tekrarlanan alt problemlere bölerek, her bir alt problemi yalnız bir kere çözüp daha sonra bu çözümü kaydederek karmaşık problemin çözümünde kullanma yöntemidir. Bir alt problem çözüldükten sonra tekrar çözülmesi gerektiğinde daha önce kaydedilen çözüm kullanılarak zaman kazanılır, ancak alt problemlerin kaydedileceği daha fazla alana gereksinim duyulur. Yani dinamik programlama algoritmaları alandan ödün verilerek zamandan kazanılmasını sağlar.

Matematiksel formulu şöyledir:Vn(y)
Burada:
V- değer fonksiyonudur
n- i zamanında 1 den n’e kadar olan süre
y- durumu temsil ediyor

Dinamik programlama problemini çözmek için en çok kullanılan algoritma Djikstra algoritmasıdır. Djikstra algoritmasında verilen bir yol probleminde en kısa turun bulunması hedeflenmektedir.

2. Yaklaşık Metotlar:

Kesin metotlar ile çözümü çok zor olan ya da çok zaman alan optimizasyon problemlerinin cevabını hızlı bir şekilde global optimumdan feragat ederek bulmaya yarayan metotlardır.
Ör: Sezgisel ve Metasezgisel Yöntemler

Yaklaşık metotlarla çözülen optimizasyon problemleri için geliştirilmiş bir çok algoritma vardır. Bu algoritmalar sürekli ve ayrık problemleri çözmek için kullanılmaktadır. Bu algoritmalardan birkaç tanesi şunlardır:

a) Parçacık Sürü Optimizasyon Algoritması(Particle Swarm Optimization-PSO):

PSO ekosistemin kökenini, özellikle de balık davranışları ve gruplandırılmış kuş uçuşları gibi sürüler halinde yaşayan hayvanların davranışlarından esinlenerek önerilmiştir. Sürü halinde yaşayan hayvanların gıda kaynağına doğru giderken yaptıkları hareketlerden esinlenerek bu algoritma geliştirilmiştir. Parçacıkların hepsi kendilerinin en iyi(personal best) ve sürünün en iyi(gbest) çözümüne göre güncellenmektedirler.

PSO’nun akış diyagramı:

PSO sürekli optimizasyon problemleri için önerilmiş olsa da ayrık optimizasyon problemlerinin çözümlerinde de kullanılır.

b)Genetik Algoritma(Genetic Algorithm-GA): GA optimizasyon problemlerinin çözümünde çok tercih edilen bir algoritmadır. Sürekli ve ayrık optimizasyon problemlerinde başarılı sonuçlar elde etmiştir.

GA ise evrimsel biyolojide kromozomların gen yapısındaki rastgele değişimlerden elde edilen türler arasında en uygun olanın hayatta kalmasını taklit etmeye dayanmaktadır.

GA da önce başlangıç populasyonu seçilmektedir. Ondan sonra populasyondaki bireyler çaprazlama ve mutasyona uğramaktadırlar. Bu işlemlerden sonra ise en iyi çözüm bulunur.
GA’nın akış diyagramı:

c) Karınca Koloni Algoritması( Ant Colony Optimization Algorithm-ACO): Ayrık optimizasyon problemlerini çözmek için önerilmiştir. Ayrık optimizasyon problemleri için başarılı çözümler elde etmiştir. Son zamanlarda sürekli optimizasyon problemlerine de uygulanmaktadır.
ACO karınca kolonisi hareketlerinden esinlenerek önerilmiştir. Karıncalar geçtikleri yolda feromon denilen bir koku salgılarlar.Karıncalar yollarındaki zengin miktardaki feromonlara göre hareket eder ve diğer karıncalar takip edilir ve daha yüksek miktarda feromon alacak daha kısa bir yol seçme eğiliminde olurlar. ACO da bu hareketleri taklit ederek problem için başarılı çözüm elde etmeye çalışmaktadır.

ACO’nun akış diyagramı:

Bu optimizasyon algoritmaları sadece teorik problemleri değil gerçek hayat problemlerini çözmktedir. Yapay zekanın popularitesinin artması ile birlikte özellikle yaklaşık metotlar için önerilen algoritmalar artmaktadır. Algoritmaların artmasıyla beraber problemlerin çözümünde daha iyi sonuçlar elde edilmektedir. Yukarıda bahsettiğim ve literatürde var olan diğer algoritmalar çoğunluka C#,Python ve MATLAB programlama dilleri ile kodlanmaktadır.

Kaynaklar:

1)https://tr.wikipedia.org/wiki/Do%C4%9Frusal_programlama
2)https://en.wikipedia.org/wiki/Dynamic_programming
3)https://tr.wikipedia.org/wiki/Dinamik_programlama
4 )Karınca Kolonisi ve Yapay Arı Kolonisi Algoritması Kullanarak Yazılım Proje Takvimi Uygulamasının Gerçekleştirilmesi Nurhan GÜL *,a , Nursal ARICIb
5)https://www.slideserve.com/hanzila/optimizasyon-teknikleri
6 )https://www.muhendisbeyinler.net/parcacik-suru-optimizasyonu/