Sırt çantası problemi (Knapsack Problem), sınırlı kaynaklarla en yüksek faydayı sağlamayı hedefleyen karar verme süreçlerini modelleyen klasik bir kombinatoriyel optimizasyon problemidir. Adını, sabit taşıma kapasitesine sahip bir çantaya en değerli eşyaların yerleştirilmesi metaforundan alır. Bu problem, ilk kez 1957 yılında M. D. Weingartner’in çalışmalarıyla gündeme gelmiş, ardından 1960’larda George Dantzig’in doğrusal programlama üzerine yaptığı araştırmalarla matematiksel bir formülasyona kavuşturulmuştur.

Problem Tanımı

Sırt çantası problemi, farklı ağırlık ve değerlere sahip birçok eşyanın bulunduğu bir senaryoda, belirli bir kapasiteye sahip olan çantaya bu eşyaların hangilerinin yerleştirileceğine karar verilmesini içerir. Amaç, çantaya alınacak eşyaların toplam değerini maksimize ederken, toplam ağırlığın çanta kapasitesini aşmamasını sağlamaktır. Bu temel yapı, birçok gerçek dünya uygulamasında, sınırlı kaynaklarla optimum faydanın sağlanmasına yönelik çeşitli karar problemleriyle örtüşmektedir.

Matematiksel Modelleme

0/1 sırt çantası problemi aşağıdaki şekilde formüle edilebilir:

$max\displaystyle\sum_{i=1}^{n}v_ix_i$

koşuluyla: $\displaystyle\sum_{i=1}^{n}w_ix_i\leq W, x_i \in {0,1}$

Burada;

• v_i: i. eşyanın değeri,
• w_i : i. eşyanın ağırlığı,
• W: çantanın toplam kapasitesi,
• x_i, i. eşyanın seçilip seçilmediğini belirten ikili karar değişkenidir.

Çözüm Yöntemleri

Sırt çantası problemi, özellikle 0/1 türünde çözüldüğünde NP-zor (non-deterministic polynomial-time hard) olarak sınıflandırılmaktadır. Bu, problemin çözüm süresinin problem boyutuyla birlikte üstel şekilde artabileceğini ifade eder. Literatürde bu probleme yönelik çeşitli klasik çözüm yöntemleri geliştirilmiştir:

• Brute Force (Kaba Kuvvet): Tüm olası eşya kombinasyonlarını değerlendirerek en uygun sonucu bulur. Küçük boyutlu problemler için etkili olmakla birlikte, büyük veri kümelerinde hesaplama maliyeti oldukça yüksektir.
• Dinamik Programlama: Alt problemlerin çözümünü saklayarak tekrarlı hesaplamaları önler. Çözüm garantilidir ancak bellek kullanımı yoğundur.
• Greedy (Açgözlü) Yöntem: Değer/ağırlık oranı en yüksek olan eşyaları öncelikli olarak seçer. Hızlıdır ancak her zaman optimal çözüm sunmaz. Sadece kesirli knapsack problemlerinde optimal çözüm verir.
• Dallanma ve Budama (Branch and Bound): Karar ağacı üzerinde ilerleyerek olası çözümleri arar; bazı yolları eler. Karmaşık problemler için etkin olmakla birlikte, yine de zaman zaman yüksek işlem süresi gerektirir.

^{Sırt Çantası Problemi Tasviri (Yapay zeka ile oluşturulmuştur.)}

Yapay Zekâ Tabanlı Yaklaşımlar

Geleneksel yöntemler, problem boyutu arttığında performans kaybı yaşar. Bu nedenle, özellikle büyük ve karmaşık veri kümeleri içeren senaryolarda, yapay zekâ temelli sezgisel algoritmalara yönelim artmıştır. Bu bağlamda en yaygın kullanılan yöntemlerden biri genetik algoritmalardır.

Genetik Algoritmalar ve Sırt Çantası Problemi İlişkisi

Genetik algoritmalar, doğadaki evrim süreçlerinden ilham alır. En iyi çözümleri ‘doğal seçilim’ benzeri bir yaklaşımla adım adım geliştirirler. İlk olarak rastgele çözümlerle başlarlar ve bu çözümleri “çiftleştirerek”, “değiştirerek” ve “seçerek” her adımda daha iyi sonuçlar elde etmeye çalışırlar. Bu süreç, nesiller boyunca tekrarlanır ve sonunda oldukça iyi çözümler elde edilir. 2025 yılında yayımlanan bir bilimsel incelemeye göre^【1】 , sırt çantası probleminin çözümünde genetik algoritmalar birçok farklı yöntemle test edilmiş ve başarılı sonuçlar vermiştir. Özellikle çantaya hangi eşyaların alınacağı gibi kararların “1” (alındı) ve “0” (alınmadı) şeklinde kodlanması, genetik algoritmaların bu problemi çözmesini kolaylaştırmaktadır. Araştırmalarda, genetik algoritmaların sadece akademik değil, aynı zamanda lojistik, yatırım planlaması, üretim optimizasyonu gibi pek çok gerçek dünya senaryosunda da etkili şekilde kullanıldığı gösterilmiştir.

Sırt çantası problemi, her ne kadar basit bir örnekle anlatılabilse de, altında oldukça derin bir karar verme sürecini barındıran, zor bir problemdir. Günümüzde sadece kuramsal değil, çok çeşitli sektörlerdeki gerçek sorunlara çözüm üretmekte kullanılır: finansal yatırım kararlarından depo yerleşim planlamalarına, personel atamasından ulaşım optimizasyonuna kadar birçok alanda sıklıkla karşımıza çıkar.

Yapay zekâ ile birleştirilen genetik algoritmalar sayesinde bu problem artık çok daha etkili ve hızlı bir şekilde çözülebilmektedir. Üstelik sadece klasik haliyle değil, "forfeit" gibi ek zorluklar içeren karmaşık versiyonları da çözülebilmektedir. Özellikle makine öğrenmesi destekli yaklaşımlar, sadece bir çözüm üretmekle kalmayıp çözüm sürecini zamanla daha verimli hale getirmekte, öğrenen sistemler aracılığıyla yeni ve yaratıcı çözümler sunmaktadır.

Bu gelişmeler, sırt çantası probleminin hâlâ güncel ve dinamik bir araştırma konusu olduğunu, özellikle yapay zekâ tekniklerinin daha geniş bir yelpazeye uygulanabileceğini göstermektedir. Gelecekte bu problemin çözümü için daha esnek, uyarlanabilir ve sektöre özel çözümler üretilmesi beklenmektedir. Sırt çantası problemi, sadece bir algoritma konusu değil, aynı zamanda “doğru kararı sınırlı kaynaklarla nasıl alırız?” sorusunun evrensel bir karşılığıdır.

Genetik Algoritmanın Uygulanması

Yapay zekâ disiplininde geliştirilen genetik algoritmalar (GA), sırt çantası problemi gibi kombinatoriyel ve NP-zor sınıfında yer alan problemlerin çözümünde etkili ve yaygın biçimde kullanılmaktadır. Genetik algoritmalar, doğadaki biyolojik evrim süreçlerinden ilham alır; özellikle doğal seçilim, çaprazlama (crossover) ve mutasyon (mutation) gibi mekanizmaları simüle ederek çözüm uzayında dolaşırlar. Sırt çantası problemi özelinde, genetik algoritmalar aşağıdaki işlem adımlarına göre yapılandırılmaktadır:

Adım 1: Başlangıç Popülasyonunun Oluşturulması

İlk adımda, problemi temsil eden rastgele bireylerden oluşan bir popülasyon oluşturulur. Her birey, bir çözüm adayıdır ve ikili (binary) bir genetik dizilimle temsil edilir. Bu dizilimde her gen, bir eşyanın seçilip seçilmediğini gösterir:

• 1: eşya seçilmiştir (çantaya konulmuştur),
• 0: eşya seçilmemiştir.

Örneğin, [1, 0, 1, 0, 1] şeklindeki bir birey, 1., 3. ve 5. eşyaların çantaya alındığını ifade eder.

Adım 2: Uygunluk (Fitness) Fonksiyonunun Değerlendirilmesi

Her bireyin “uygunluğu”, yani çözüm kalitesi, özel bir fitness fonksiyonu ile değerlendirilir. Bu fonksiyon genellikle, çantaya alınan eşyaların toplam değerini ifade eder. Ancak, toplam ağırlığın belirlenen kapasiteyi aşıp aşmadığı da kontrol edilir:

• Kapasiteyi aşmayan çözümler doğrudan değerlendirilir,
• Kapasiteyi aşan bireyler ya elenir ya da cezalandırılır (örneğin, fitness değeri düşürülerek).

Bu sayede algoritma, geçerli çözümler üretmeye yönlendirilir.

Adım 3 : Seçilim

Seçilim aşamasında, mevcut popülasyondan yüksek fitness değerine sahip bireyler belirlenerek bir sonraki nesli oluşturacak bireylerin seçimi yapılır. Bu aşamada rulet çarkı seçimi (roulette wheel selection), turnuva seçimi (tournament selection) gibi yöntemler kullanılabilir. Amaç, iyi çözümlerin genetik bilgisini sonraki nesillere aktarmaktır.

Adım 4: Çaprazlama (Crossover)

Seçilen bireyler eşleştirilerek genetik bilgilerinin bir kısmı birbirleriyle değiş-tokuş edilir. Bu işlem, yeni bireylerin (yani yeni çözüm adaylarının) oluşturulmasını sağlar. En yaygın kullanılan çaprazlama yöntemi tek noktalı çaprazlama (single-point crossover) olup, gen dizilimi belirli bir noktadan iki ebeveyn arasında bölünerek yeni kombinasyonlar oluşturulur.

Adım 5: Mutasyon

Mutasyon, genetik çeşitliliği korumak ve yerel optimumlara sıkışmayı önlemek amacıyla uygulanır. Bu aşamada bazı bireylerde rastgele genler ters çevrilir (örneğin 0 → 1 veya 1 → 0). Mutasyon oranı düşük tutulur (genellikle %1–5 arası), çünkü yüksek mutasyon algoritmanın rastgele davranmasına neden olabilir.

Adım 6: Döngüsel İterasyon ve Durdurma Kriteri

Yukarıdaki adımlar belirli bir nesil sayısı boyunca veya durdurma kriteri sağlanana kadar tekrar edilir. Durdurma kriterleri şunlar olabilir:

• Belirli bir nesil sayısına ulaşılması,
• En iyi bireyin fitness değerinin daha fazla artmaması,
• Hesaplama süresinin sınırlandırılması.

Bu süreç sonucunda, optimal ya da optimal'e oldukça yakın bir çözüm elde edilir.

Sırt Çantası Probleminin Gerçek Dünya Uygulamaları

Sırt çantası problemi, yalnızca kuramsal bir matematiksel egzersiz değil; gerçek dünyada sınırlı kaynaklar altında en etkin kararların nasıl verilebileceğini modelleyen evrensel bir optimizasyon çerçevesidir. Temel yapısı gereği, “maksimum fayda–sınırlı kapasite” ikilemini içeren birçok sektörel kararda doğrudan karşılık bulur. Bu bağlamda, sırt çantası probleminin uygulama alanları aşağıdaki gibi özetlenebilir:

• Finans: Portföy seçimi ve yatırım planlaması süreçlerinde, sınırlı sermaye ile en yüksek getiri sağlayacak varlıkların seçimi sırt çantası problemine benzer bir yapıyla modellenir. Özellikle risk-getiri dengesinin optimize edilmesi gereken çok kriterli senaryolarda tercih edilmektedir.
• Lojistik: Araç yükleme, konteyner yerleşimi ve rota planlaması gibi süreçlerde, taşıma kapasitesinin en verimli şekilde kullanılmasını sağlamak adına sırt çantası modellemesi sıkça uygulanır. Aynı zamanda, çoklu teslimat kısıtları içeren karmaşık taşıma sistemlerinde de temel karar desteği sağlar.
• Üretim: Hammadde ve enerji gibi üretim kaynaklarının sınırlı olduğu durumlarda, üretim miktarlarını ve bileşen seçimlerini optimize etmek için bu problem yapısı kullanılır. Bu yaklaşım, özellikle kısıtlı bütçeyle maksimum üretim çıktısı hedeflendiğinde etkili olmaktadır.
• Telekomünikasyon: Frekans spektrumu tahsisi, kanal paylaşımı ve bant genişliği yönetimi gibi konularda, her kanalın kapasitesi sınırlı olduğundan, ağ performansını artıracak kombinasyonlar sırt çantası problemine benzer yapılarla değerlendirilir.
• Savunma ve Askerî Planlama: Görev yükleme, mühimmat seçimi, kaynak tahsisi ve operasyonel planlama süreçlerinde; sınırlı sayıda ekipman, zaman ve insan gücü ile azami görev başarısını elde etmeyi amaçlayan planlama kararları sırt çantası problemine dayalıdır.

Sırt çantası problemi, yalnızca soyut bir matematiksel formül değil; gerçek dünyada sınırlı kaynaklarla nasıl en etkili kararı verebileceğimizi modelleyen evrensel bir karar verme çerçevesidir. Problem, özellikle kaynak tahsisi, seçim optimizasyonu ve sınırlı kapasite altında maksimum fayda elde etme gibi temel karar süreçlerinin simülasyonu olarak çok geniş bir uygulama alanına sahiptir. Bu nedenle yalnızca teorik çalışmalarda değil; üretim, finans, lojistik ve enerji gibi birçok sektörde de doğrudan karşılık bulmaktadır.