Geri Dön

İkili ölüm oyunu optimizasyon algoritmasının küme birleşimli sırt çantası problemine uygulanması

Implementation of binary battle royale optimization algorithm to set union knapsack problem

PDF İndir

  1. Tez No: 946458
  2. Yazar: GÜLŞEN ORUCOVA BÜYÜKÖZ
  3. Danışmanlar: DOÇ. DR. HÜSEYİN HAKLI
  4. Tez Türü: Yüksek Lisans
  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: Necmettin Erbakan Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 61

Özet

Klasik çözüm yöntemlerinin yetersiz kaldığı ya da yüksek hesaplama maliyeti gerektirdiği durumlarda, optimizasyon teknikleri ön plana çıkmaktadır. Optimizasyon, belirli kısıtlar altında bir hedef fonksiyonun en iyi değerinin bulunmasını amaçlar. Hesaplama karmaşıklığı kuramı kapsamında NP-zor (Non-deterministic Polynomial-time hard) olarak sınıflandırılan problemler, çözüm süresinin problem boyutuyla birlikte üstel olarak arttığı ve polinom zamanda çözümün genellikle mümkün olmadığı yapılar sunar. Bu nedenle, kesin çözüm yöntemlerinin uygulanabilir olmadığı durumlarda yaklaşık, sezgisel (heuristic), meta-sezgisel (metaheuristic) algoritmalar gibi alternatif yaklaşımlar geliştirilerek bu problemlere etkin çözümler üretilmektedir. Bu tür problemlerin çözümü, yalnızca teorik bilgisayar bilimi açısından değil, aynı zamanda üretim planlaması, ağ optimizasyonu, kaynak yönetimi ve yapay zekâ gibi birçok uygulamalı alanda da kritik öneme sahiptir. Etkin çözüm yöntemleri hem hesaplama süresini azaltmakta hem de karmaşık sistemlerin verimli şekilde yönetilmesini mümkün kılmaktadır. Bu tez çalışmasında, NP-zor sınıfında yer alan Küme Birleşimli Sırt Çantası Problemi (Set-Union Knapsack Problem-SUKP) için Ölüm Oyunu Optimizasyon (Battle Royale Optimization-BRO) algoritmasının ikili (binary) versiyonları önerilmiştir ve performansları karşılaştırılarak analiz edilmiştir. BRO algoritması sürekli arama uzayı için tasarlanmış bir meta-sezgisel algoritma olduğundan, ikili yapıdaki SUKP problemlerine doğrudan uygulanamamaktadır. Bu nedenle BRO algoritmasını ikili arama uzayına adapte edebilmek için iki farklı yaklaşımı önerilmiştir. İlk yaklaşımda, BRO'nun temel işleyişine müdahale edilmeden, aday çözümlerin ikili yapıya dönüştürülmesi için 25 farklı transfer fonksiyonu (S, V, U, T, Z, O-şekilli ve Hiperbolik tanjant) kullanılmıştır. Bu yöntemde, algoritmanın arama dinamikleri korunarak, uygunluk hesaplanması öncesinde sürekli çözümler ikili yapıya dönüştürülmüştür. Önerilen algoritma 30 SUKP problemine uygulanmış elde edilen sonuçlar analiz edilmiştir. Sonuçlar O-şekilli TF'den olan O2-TF'nin en etkili çözümleri elde ettiğini göstermiştir. İkinci yaklaşımda, BRO algoritmasının arama uzayı doğrudan ikili forma taşınmıştır. Çözüm çeşitliliği sağlamak için Mutasyon, arama uzayını daraltmak için ise etiket oranı gibi yeni bileşenler eklenerek algoritmanın temel adımları modifiye edilmiştir ve BROBin olarak adlandırılmıştır. Önerilen her iki yöntemde de arama uzayının dışında kalan geçersiz çözümleri onarmak onarım (repair) algoritması ve var olan çözümleri iyileştirme için iyileştirme (improvement) algoritması kullanılmıştır. BROBin algoritması 30 SUKP problemi üzerinde test edilmiştir. En iyi performans gösteren transfer fonksiyonu O2 ile BROBin algoritmasının çıktıları karşılaştırılarak değerlendirilmiştir. Deneysel bulgular, BROBin'in 30 SUKP probleminin tamamında daha etkili yaklaşımlar ürettiğini göstermiştir. Bu tez çalışması, BRO algoritmasının ikili optimizasyon problemlerine uyarlanabilirliğini ortaya koyan çalışmalardan biri olması açısından önem taşımaktadır. Elde edilen sonuçlar, SUKP gibi karmaşık kombinatoryal problemlerin çözümünde meta-sezgisel yöntemlerin etkinliğini artırmak için arama uzayı adaptasyonu ve operatör modifikasyonlarının etkili rol oynadığını vurgulamaktadır.

Özet (Çeviri)

In cases where classical solution methods are insufficient or entail high computational costs, optimization techniques come to the forefront. Optimization aims to find the best value of an objective function under a set of constraints. Within the framework of computational complexity theory, problems classified as NP-hard (Non-deterministic Polynomial-time hard) exhibit a solution time that increases exponentially with problem size, making polynomial-time solutions generally infeasible. Therefore, in situations where exact solution methods are not applicable, alternative approaches such as approximate algorithms, heuristic, and metaheuristic techniques have been developed to provide effective solutions. Solving such problems is critically important not only from a theoretical computer science perspective but also in many applied domains such as production planning, network optimization, resource management, and artificial intelligence. Efficient solution strategies reduce computational time and enable the effective management of complex systems. This thesis proposes binary versions of the Battle Royale Optimization (BRO) algorithm to solve the Set-Union Knapsack Problem (SUKP), which belongs to the NP-hard class. Since the BRO algorithm was originally designed for continuous search spaces, it cannot be directly applied to binary SUKP problems. Therefore, two different approaches are proposed to adapt the BRO algorithm to the binary search space. In the first approach, 25 different transfer functions (S, V, U, T, Z, O-shaped and Hyperbolic tangent) were used to transform candidate solutions into binary structure without interfering with the basic operation of BRO. In this method, the search dynamics of the algorithm are preserved and the continuous solutions are converted to binary structure before the fitness calculation. The proposed algorithm has been applied to 30 SUKP problems and the results obtained have been analysed. The results show that O2-TF, which is one of the O-shaped TFs, obtains the most efficient solutions. In the second approach, the search space of the BRO algorithm is moved directly to binary form. The basic steps of the algorithm are modified by adding new components such as mutation to provide solution diversity and labelling ratio to narrow the search space, and the algorithm is called BROBin. In both proposed methods, repair algorithm is used to repair infeasible solutions outside the search space and improvement algorithm is used to improve feasible solutions. The BROBin algorithm has been tested on 30 SUKP problems. The outputs of the BROBin algorithm were evaluated by comparing the best performing transfer function O2 with the outputs of the BROBin algorithm. The experimental results show that BROBin produces more efficient approximations for all the 30 SUKP problems. This thesis is important as it is one of the studies that demonstrate the adaptability of the BRO algorithm to binary optimization problems. The results obtained emphasise that search space adaptation and operator modifications play an effective role in improving the effectiveness of meta-heuristics in solving complex combinatorial problems such as the SUKP.

Benzer Tezler

  1. Tez No

    827860

    Derin öğrenme ve büyük veri analitiği yöntemleriKullanarak Covid-19 yayılımının ileriye dönük tahmini

    Forecasting the spread of covid-19 using deep learning and big data analytics methods

    CYLAS KIGANDA

    Yüksek Lisans

    İngilizce

    İngilizce

    2023

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolGazi Üniversitesi

    Bilgisayar Bilimleri Ana Bilim Dalı

    PROF. DR. MUHAMMET ALİ AKCAYOL

  2. Tez No

    716515

    Ölüm oyunu optimizasyonu algoritması kullanarak ikili tank sıvı seviye sistemi için FPTID+FF denetleyicisi tasarımı

    FPTID+FF controller design for coupled tank liquid level system using battle royale optimization algorithm

    ALİ KIVANÇ ŞAHİN

    Yüksek Lisans

    Türkçe

    Türkçe

    2022

    Elektrik ve Elektronik MühendisliğiKaradeniz Teknik Üniversitesi

    Elektrik-Elektronik Mühendisliği Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ OĞUZHAN ÇAKIR

  3. Tez No

    674595

    A serious game using virtual reality and augmented reality in a driving license test

    Sürücü sınavlarında artırılmış gerçeklik ve sanal gerçeklik kullanan ciddi oyun

    TUĞÇE AVŞAR

    Yüksek Lisans

    İngilizce

    İngilizce

    2021

    Bilim ve Teknolojiİstanbul Teknik Üniversitesi

    Oyun ve Etkileşim Teknolojileri Ana Bilim Dalı

    PROF. DR. HATİCE KÖSE

  4. Tez No

    776518

    Generation of plasmid-based eukaryotic model to investigate biology of Crimean-Congo hemorrhagic fever virus nucleoprotein and glycoproteins

    Kırım Kongo kanamalı ateşi virüsü nükleoproteinin ve glikoproteinlerinin biyolojisinin çalışılmasında plazmit temelli ökaryotik model oluşturulması

    NESİBE SELMA ÇETİN

    Doktora

    İngilizce

    İngilizce

    2023

    BiyoteknolojiBezm-i Alem Vakıf Üniversitesi

    Biyoteknoloji Ana Bilim Dalı

    PROF. DR. MEHMET ZİYA DOYMAZ

  5. Tez No

    633519

    Subjectification of the liminal other in contemporary British drama: Sarah Kane's Cleansed, Anthony Neilson's The Wonderful World of Dissocia and Marina Carr's Portia Coughlan

    Çağdaş İngiliz Tiyatrosu'nda eşiksel ötekinin özneleştirilmesi: Sarah Kane'in Cleansed, Anthony Neilson'ın The Wonderful World of Dissocia ve Marina Carr'ın Portia Coughlan başlıklı oyunları

    ONUR KARAKÖSE

    Yüksek Lisans

    İngilizce

    İngilizce

    2020

    Batı Dilleri ve EdebiyatıAnkara Üniversitesi

    Batı Dilleri ve Edebiyatları Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ NİSA HARİKA GÜZEL KÖŞKER

Geri Dön