Geri Dön

Ayrık optimizasyon problemlerinin çözümü için yeni yaklaşımların geliştirilmesi

Developing new approaches for solving discrete optimization problems

PDF İndir

  1. Tez No: 948049
  2. Yazar: AYBÜKE BABADAĞ
  3. Danışmanlar: DOÇ. DR. AHMET BABALIK
  4. Tez Türü: Doktora
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2025
  8. Dil: Türkçe
  9. Üniversite: Konya Teknik Üniversitesi
  10. Enstitü: Lisansüstü Eğitim Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 147

Özet

Optimizasyon algoritmaları, ele alınan problemin en uygun çözümünü ararlar. Çözümü aranan problem sürekli değerlerle ifade ediliyorsa bu problemler sürekli optimizasyon problemi, ayrık değerlerle ifade ediliyorsa ayrık optimizasyon problemi olarak adlandırılmaktadır. Bazı ayrık optimizasyon problemleri ikili değerlerle (0 ve 1) ifade edilir, bu tür problemler ikili optimizasyon problemleri olarak isimlendirilir. Literatürde sürekli ve ayrık optimizasyon problemlerinin çözümüne yönelik algoritmalar bulunmaktadır. Sürekli optimizasyon problemlerinin çözümü için geliştirilen algoritmalar, ayrık arama uzayına adapte edilerek ayrık optimizasyon problemlerinin çözümü için kullanılabilirler. Literatürde farklı ayrıklaştırma yöntemleri mevcuttur. Bu tez çalışması kapsamında, sıklıkla kullanılan yapısal ayrıklaştırma ve dönüşüm fonksiyonu ile ayrıklaştırma yöntemleri ele alınmıştır. Optimizasyon algoritmalarını genellikle klasik ve metasezgisel algoritmalar olarak sınıflandırmak mümkündür. Optimizasyon problemlerinin çözümü için, makul sürede kabul edilebilir çözümler üretmeleri sebebiyle metasezgisel algoritmalar daha çok tercih edilmektedir. Literatürde yer alan metasezgisel optimizasyon algoritmalarının büyük çoğunluğunu doğa esinli veya sürü zekâsına dayalı algoritmalar oluşturmaktadır. Bu tez çalışması kapsamında çözüm üretmedeki başarısı ve basit yapıda oluşu sebebiyle; çekirge optimizasyon algoritması (grasshopper optimization algorithm - GOA) ve serçe arama algoritması (sparrow search algorithm - SSA) ele alınmıştır. Çekirge optimizasyon algoritması yapısal ikilileştirme yaklaşımı ile, serçe arama algoritması ise dönüşüm fonksiyonunda adaptif eşik değeri yöntemi ile ikilileştirilmiştir. İkilileştirilen algoritmalar, kapasitesiz tesis yerleşim problemi (uncapacitated facility location problem - UFLP) ve özellik seçimi probleminin çözümüne uygulanmıştır. Özellik seçimi, Xray bagaj görüntülerinde yer alan yasaklı nesnelerin sınıflandırılması probleminde bir önişlem olarak uygulanmıştır. Önerilen modifiye ikili çekirge optimizasyon algoritmasının (modified binary grasshopper optimization algorithm - MBGOA) çözüm üretiminde, temel algoritmadan farklı olarak aday çözüm üretme mekanizması kullanılmıştır. Küresel en iyi ve diğer çözümler farklı güncelleme mekanizmaları kullanılarak güncellenmiştir. Küresel en iyi çözüm haricindeki çözümlerin güncellenmesinde, üretilen aday çözüme katkı sağlayacak komşu çözüm sayısının belirlenmesi için yeni bir parametre tanıtılmıştır. Üretilen aday çözüme, küresel en iyi çözümün dahil edilme olasılığı temel algoritmada yer alan bir parametreye göre belirlenmektedir. Önerilen algoritma, iyi bilinen Cap ve M* veri setleri üzerinde test edilip, sonuçlar literatürde yer alan diğer ikili GOA ve farklı ikili optimizasyon algoritmalarının sonuçları ile karşılaştırılmıştır. Cap veri setinde 15 problemin 13'ünde, M* veri setinde 20 problemin 10'unda tüm çalıştırmalarda optimum çözüme ulaşılmıştır. Elde edilen sonuçlar önerilen algoritmanın, UFL probleminin çözümünde karşılaştırılan algoritmalardan daha başarılı olduğunu göstermektedir. Serçe arama algoritmasına, ikilileştirilmeden önce algoritmanın başarısının arttırılması için literatürde yer alan bir çalışmadaki bazı iyileştirme mekanizmaları uygulanmıştır. Ardından algoritma, dönüşüm fonksiyonları kullanılarak ikilileştirilmiştir. Bu aşamada, önerilen adaptif eşik değeri yöntemi algoritmaya dahil edilmiştir. Çözüm vektörüne, karar değişkenlerinin yanı sıra dönüşüm fonksiyonundan gelen değerlerin 0 ve 1 değerlerine haritalanmasında belirleyici olan eşik değeri eklenmiştir. Böylece problemin ve eşik değerinin eşzamanlı olarak optimize edilmesi ve probleme en uygun eşik değerinin belirlenmesi sağlanmıştır. Önerilen yaklaşım, özellik seçimi problemine uygulanmıştır. Özellik seçimi, OPIXray veri setinde yer alan Xray bagaj görüntülerindeki yasaklı nesnelerin sınıflandırılmasında bir önişlem olarak uygulanmıştır. İlk aşamada, görüntülerdeki özellikler ResNet18 derin ağ modeli kullanılarak çıkarılmıştır. İkinci aşamada, önerilen adaptif eşik değeri yaklaşımının kullanıldığı ikili modifiye serçe arama algoritması (binary adaptive threshold modified sparrow search algoritm - binMSSA-AT) ile özellik seçimi yapılmıştır. Son aşamada seçilen özellikler KNN sınıflandırıcısı kullanılarak sınıflandırılmıştır. Elde edilen sonuçlar, literatürdeki diğer ikili optimizasyon algoritmaları ile elde edilen sonuçlarla karşılaştırılmıştır. Test doğruluğu %97,02'den %97,40'a çıkarılmış özellik sayısı 512'den yaklaşık 51 özelliğe düşürülmüştür. Elde edilen sonuçlar, algoritmanın özellik seçimindeki etkinliğini göstermektedir. Adaptif eşik değeri yaklaşımının kullanıldığı ve kullanılmadığı ikili SSA'lar özellik seçimi problemine uygulanarak elde edilen sonuçlar karşılaştırılmıştır. Sonuçlar, önerilen yeni ikilileştirme yaklaşımının, algoritmayı sadece dönüşüm fonksiyonu kullanarak ikilileştirmekten daha etkin bir yaklaşım olduğunu göstermektedir. Ayrıca, MBGOA ve binMSSA-AT algoritmaları ile, UFLP ve özellik seçimi problemlerinde elde edilen sonuçlar birbirleriyle karşılaştırılmıştır. Tez çalışması kapsamında GOA, yapısal ikilileştirme yöntemi ile, SSA ise adaptif eşik değerli dönüşüm fonksiyonu yöntemi ile ikilileştirilmiş ve ikilileştirilen algoritmalar farklı ikili problemler üzerinde test edilmiştir. İkilileştirilen her iki algoritma da ele alınan UFLP ve özellik seçimi problemlerinin çözümüne uygulanmıştır. Yapılan tüm deneysel çalışmalar neticesinde elde edilen başarılı sonuçlar, önerilen algoritmaların ve adaptif eşik değeri yaklaşımının ele alınan problemlerin çözümünde etkin, kararlı ve güçlü bir alternatif olduğunu göstermiş ve sürekli optimizasyon algoritmalarının ikilileştirilmesi ve ikili optimizasyon alanlarında literatüre kazandırılmıştır.

Özet (Çeviri)

Optimization algorithms aim to find the optimum solution for the addressed problem. The optimization problems represented with continuous values are called continuous optimization problems while the optimization problems represented with discrete values are called discrete optimization problems. Some discrete optimization problems are represented with binary values (0 and 1), and such problems are referred to as binary optimization problems. There are algorithms in the literature aimed at solving both continuous and discrete optimization problems. Algorithms developed for solving continuous optimization problems can be adapted to discrete search space for solving discrete optimization problems. There are different discretization methods in the literature. Within the scope of this thesis, the commonly used structural discretization and transfer function-based discretization methods are addressed. Generally, optimization algorithms can be classified as classical and metaheuristic algorithms. Due to their ability to provide acceptable solutions within a reasonable time, metaheuristic algorithms are commonly preferred for solving optimization problems. A substantial portion of the metaheuristic optimization algorithms in the literature are nature-inspired or based on swarm intelligence. Within the scope of this thesis, the grasshopper optimization algorithm (GOA) and the sparrow search algorithm (SSA) are addressed due to their effectiveness in producing solutions and their simple structure. The grasshopper optimization algorithm is binarized using the structural binarization approach, while the sparrow search algorithm is binarized using the transfer function method including the adaptive threshold value approach in binarization. The binarized algorithms are applied to the uncapacitated facility location problem (UFLP) and the feature selection problem. Feature selection is applied as a preprocessing step in the classification of prohibited objects in X-ray baggage images. In the proposed modified binary grasshopper optimization algorithm (MBGOA), a candidate solution generation mechanism different from the basic algorithm is used. The global best and other solutions are updated using different update mechanisms. In updating the solutions other than the global best solution, a new parameter is introduced to determine the number of neighboring solutions that will contribute to the generated candidate solution. The probability of including the global best solution in the generated candidate solution is determined according to a parameter from the basic algorithm. The proposed algorithm is tested on well-known Cap and M* datasets and the results are compared with those of other binary GOAs and different binary optimization algorithms in the literature. Optimum solutions are obtained in all runs for 13 out of 15 problems in the Cap dataset and 10 out of 20 problems in the M* dataset. The results show that the proposed algorithm is more successful than the compared algorithms in solving the UFLP. Before binarization, certain improvements from a study in the literature are applied to increase the performance of the sparrow search algorithm. Then, the algorithm is binarized using transfer functions. At this stage, the adaptive threshold value method is integrated into the algorithm. In addition to the decision variables, the threshold value, which is decisive in mapping the values obtained from the transfer function to 0 and 1, is added to the solution vector. Thus, simultaneous optimization of both the decision variables of the problem and the threshold value is achieved by determining the optimum threshold value for the problem. The proposed approach is applied to the feature selection problem. Feature selection is used as a preprocessing step in the classification of prohibited items in X-ray baggage images from the OPIXray dataset. In the first stage, features from the images are extracted using the ResNet18 deep network model. In the second stage, feature selection is performed using the binary adaptive threshold modified sparrow search algorithm (binMSSA-AT), which employs the proposed adaptive threshold value approach. In the final stage, the selected features are classified using the KNN classifier. The results are compared with those obtained from other binary optimization algorithms in literature. Test accuracy increased from 97,02% to 97,40%, and the number of selected features is reduced from 512 to approximately 51. The obtained results demonstrate the effectiveness of the algorithm in feature selection. Binary SSAs with and without the adaptive threshold value approach are applied to the feature selection problem, and the results are compared. The results show that the proposed new binarization approach is more effective than binarization using only a transfer function. Additionally, the results obtained from solving UFLP and feature selection problems using MBGOA and binMSSA-AT algorithms are compared with each other. Within the scope of the thesis, GOA is binarized using structural modifications, while SSA is binarized using transfer function with the adaptive threshold value approach. The binarized algorithms are evaluated on different binary problems. Both binarized algorithms are applied to the solution of the addressed UFLP and feature selection problems. The successful results obtained from all experimental studies demonstrate that the proposed algorithms and the adaptive threshold value approach are effective, stable, and robust alternatives for solving the addressed problems, and contributed to the literature in the fields of binarization of continuous optimization algorithms and binary optimization.

Benzer Tezler

  1. Tez No

    632725

    İnşaat projelerinde zaman-maliyet optimizasyonu; Al-anbar hastanesi örneği

    Time-cost optimization in construction projects; Case study at al-Anbar hospital

    SAAD KHALDON RASHEED AL UBAIDY

    Yüksek Lisans

    Türkçe

    Türkçe

    2020

    Mühendislik BilimleriKastamonu Üniversitesi

    Mühendislik Yönetimi Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ OĞUZHAN YAVUZ BAYRAKTAR

  2. Tez No

    357033

    Optimizasyon problemlerinin çözümü için yapay arı kolonisi algoritması tabanlı yeni yaklaşımlar

    Novel approaches based on articial bee colony algorithm to solve optimization pronlems

    MUSTAFA SERVET KIRAN

    Doktora

    Türkçe

    Türkçe

    2014

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSelçuk Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. MESUT GÜNDÜZ

  3. Tez No

    809021

    Büyük ölçekli optimizasyon problemlerinin çözümünde yeni yaklaşımlar

    New approaches to solving large-scale optimization problems

    HAVVA GÜL KOÇER

    Doktora

    Türkçe

    Türkçe

    2023

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKonya Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. SAİT ALİ UYMAZ

  4. Tez No

    287349

    Robust optimization through response surface methodology

    Response surface kullanan sağlamcı eniyileme

    SEDA EYİGÜN

    Yüksek Lisans

    İngilizce

    İngilizce

    2009

    Endüstri ve Endüstri MühendisliğiGalatasaray Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DOÇ. DR. ESRA ALBAYRAK

    YRD. DOÇ. DR. M. EBRU ANGÜN

  5. Tez No

    559913

    A decision support framework for flp in the context of industrial facilities by the use of bim

    Endüstriyel yapılar özelinde tesis yerleşimi problemlerinde bım kullanımı ile tasarımcıya yardımcı olacak bir çerçeve önerisi

    YİĞİTCAN ÜLKÜCÜ

    Yüksek Lisans

    İngilizce

    İngilizce

    2019

    Mimarlıkİstanbul Teknik Üniversitesi

    Bilişim Ana Bilim Dalı

    DOÇ. DR. SEMA ALAÇAM

Geri Dön