Optimizasyon problemlerinin çözümünde hesaplama maliyetinin azaltılması
Reduction of computational cost on the solution of optimization problems
Yazar: FATİH YAMAN
Danışman: DOÇ. DR. ASIM EGEMEN YILMAZ
Ankara Üniversitesi / Fen Bilimleri Enstitüsü / Elektrik-Elektronik Mühendisliği Ana Bilim Dalı
Derece: Doktora, 2014
Konu: Elektrik ve Elektronik Mühendisliği = Electrical and Electronics Engineering

Özet:
Optimizasyon problemlerinin maliyet etkin biçimde çözümü önemli bir husustur. Sezgisel yöntemler optimizasyon problemlerinin çözümü için etkili yöntemlerdir ancak özellikle çok boyutlu problemler için söz konusu algoritmalar yüksek hesaplama maliyetine sahiptir. Bunun temel nedenlerinden birisi, algoritmanın deneme-yanılma sürecinde yapılan ve sonuca doğrudan katkı sağlamayan çok fazla sayıdaki uygunluk fonksiyonu hesaplamasıdır. Bu tez çalışmasında, ara değer bulma/kestirim yöntemlerinin sezgisel algoritmalara iki farklı şekilde dâhil edildiği yeni bir yaklaşım önerilmiştir. Bunlardan birisi, değer kestirim yöntemi kullanarak arama ajanlarının uygunluk fonksiyonu değerlerinin düşük hesaplama maliyeti ile tahmin edilmesidir. Ayrıca bu yöntem çok amaçlı optimizasyon problemlerine de uygulanmıştır. Diğer yaklaşım ise, seçim, çaprazlama ve mutasyon gibi genetik operatörlere ilave olarak yerel fakat etkili bir arama operatörünün kullanılmasıdır. Bu yaklaşımların etkinliği, radyal baz fonksiyonu tabanlı kestirim tekniğinin, temel sezgisel yöntemlerden birisi olan genetik algoritmalara katılması suretiyle analiz edilmiştir. Performans iki test fonksiyon seti aracılığıyla değerlendirilmiştir. Sonuçlardan, klasik genetik algoritmalarla kıyaslandığında, test fonksiyonlarının çoğunluğu için uygunluk fonksiyonu hesaplama sayısının büyük oranda düştüğü ve çözüm doğruluğunun arttığı görülmüştür. Belirtilen yaklaşımlara ilave olarak, tezde yeni bir arama algoritması önerilmiştir. Bu yöntemde, radyal baz fonksiyonu tabanlı değer kestirimi vasıtasıyla, her bir arama ajanı için uygunluk fonksiyonu değeri tahmin edilmiştir. Global optimuma daha iyi bir yakınsama sağlamak için, aynı zamanda alfa-beta filtresi de arama algoritmasına dâhil edilmiştir.

Abstract:
Solution of optimization problems in a cost-effective manner is an important issue. Heuristic methods are efficient methods for this purpose, but they have high computational cost especially for large dimensional problems. One of the main reasons for this is nothing but the excessive fitness function calculations throughout the trial-error process, which do not directly contribute to the solution.  In this thesis, a new approach is proposed by incorporating interpolation/approximation methods to heuristics in two ways. One of them is to use approximation method to estimate of fitness function values of search agents with a low computational cost. This method is applied to multi-objective optimization problems also. Other approach is to use a local but an effective search operator in addition to genetic operators such as the selection, recombination and mutation. The efficiencies of these approaches are analyzed by incorporating the radial basis function based interpolation technique to one of the major heuristics, genetic algorithm. The performance is evaluated via two benchmark function sets. It is observed that the number of fitness function evaluations decreases dramatically (compared to conventional genetic algorithms) for most benchmark functions and the solution accuracy is improved for majority of the test cases. In addition to proposed approaches, a new search algorithm is proposed in the thesis. In this method, the fitness function value estimation for each search agent is obtained by Radial Basis Function based approximation. In order to achieve better convergence to the global optimum, the alpha-beta filter is also integrated to the search algorithm.