KNAPSACK PAKET PROGRAMI
Urfat G. NURİYEV[1], Pınar DÜNDAR[2], Osman ŞEN[3]
ÖZET.
Ekonomide ve teknik sistemlerdeki
birçok karar (verme) problemleri Knapsack tipli problemler şeklinde
gösterilebilir. MS Windows ortamında Delphi 4.0 ve OOP teknikleri kullanılarak
bu türlü problemlerin çözümü için daha önce önermiş olduğumuz birkaç
algoritmaları içeren KnapsacK Paket Programı hazırlanmıştır.
Bu makalede KnapsacK Paket Programının imkanları ve fonksiyonları
verilmiş ve kullanımı anlatılmıştır. Paket başka algoritmalar da eklenerek
genişletilmeye açıktır.
Yapılan hesaplama denemeleri önerilmiş algoritmaların verimliliğinin
yüksek olduğunu göstermektedir. Makalede KnapsacK paket programı ile yapılan
performans testlerinin sonuçları da verilmiştir.
1.Giriş
Ekonomik ve teknik
sistemlerdeki birçok karar verme problemleri Knapsack tipli problemler şeklinde
gösterilebilir [1]. Dolayısıyla Knapsack probleminin çözüm yöntemlerinin
geliştirilmesi ve bunlar için efektif program sistemaları oluşturulması pratik
açıdan büyük önem taşımaktadır.
Bu problem
matematiksel olarak aşağıdaki gibi formalize edilir [2] :
I={1,2,...,m} ve J={1,2,...,n} olmak üzere, bi , cj
pozitif tam sayıları ve negatif olmayan aij, iÎI , jÎJ sayıları verilmiştir.
(1)
bulunması istenmektedir.
Problem çeşitli
açılardan incelenmiş ve çeşitli yönlerde genelleştirilmiştir. Sürekli olarak
problemin yeni uygulama alanları ve yeni anlamlı yorumları ortaya çıkmaktadır.
Bunun en yaygın yorumu aşağıdaki gibi verilebilir [3].
P1, P2,...,Pn
gibi n tane proje ve her Pj projesinden beklenilen kazanç cj , bu projenin gerçekleşmesi
durumunda Ki kaynağına olan
ihtiyacı aij , ayrılmış
olan Ki kaynağının kapasitesi
bi ile verilmiştir.
xj=
olmak üzere xj
(jÎJ) değişkenleri
alınarak (1) problemi elde edilir.
Bu problem,
verilen kaynak hacmini arttırmamak koşuluyla, toplam gelir maksimal olacak şekilde, verilen projeler kümesinden bir
altküme seçilmesi olarak yorumlanabilir.[UN1][UN1]
Knapsack problemi
özellikle ekonomi alanında rastlanan bir tamsayı problemidir. Uygulamada
karşılaşılan problemler yüzlerce sınırlayıcı koşuldan ve binlerce karar
değişkeninden oluşmaktadır. Bu husus büyük boyutlu problemleri çözmek için yeni
yöntemler ve efektif paket programlar kullanımını gerektirmektedir.
KnapsacK çok
sayıda kısıt ve değişkenden oluşan Kapsack modelinin çözümü amacıyla
geliştirilmiştir.
2. Problemin Çözüm Yöntemleri Üzerine
Bu problemin çözümü
için bir çok algoritma geliştirilmiştir[1]. İlk zamanlar dal - buda tekniği
kullanılarak problemin çözümüne gidilmiştir. Ancak büyük sayıda girdilerde bu
algoritmanın efektif olmadığı
görülmüştür. Problemin NP-tam sınıftan olduğu bilindikten sonra yaklaşık
yöntemlere ağırlık verilmiştir. Fakat Knapsack probleminin mutlak yaklaşım
çözümü de NP-tam sınıftandır [4]. Bundan dolayı tam çözüme yakın çözüm veren
olasılıklı yaklaşım algoritmaları kullanılır. Böyle çözümlere suboptimal çözüm denir [5]. Suboptimal
çözüm genellikle heuristik yöntemlerle yapılır [6].
Bu yöntemlerin
kalitesi, problemin özelliğinin göz önüne alınma derecesiyle, problemin tam
formalize edilmesi ile belirlenen mümkün çözümlerinin gerçek pekiştirme
kurallarının seçilme prensibine bağlılık derecesi ile ilişkilidir [7] .
[2] makalesinde çok boyutlu Boole değişkenli Knapsack Problemini çözmek için yukarıdaki prensiplere dayanan “sert kısıtlama yöntemi” önerilmiştir. Önerilen sert kısıtlama yöntemi, geçerli bilgiye göre çözüm arama sürecinde değişebilen bir esnek tarama şeması tanımlama olanağı sağlamaktadır.
[8]
çalışmasında bu yöntem geliştirilerek kendi kendini düzenleyen bir
algoritma (AS) tasarlanmıştır, öyle ki,
bu algoritma verilen problemin özelliklerine uyan bir taramayı da mümkün
kılmaktadır.
[9]
çalışmasında ise sert kısıtlama
yöntemindeki katsayıları hesaplamak için duallık prensibine dayalı bir
algoritma (AD) geliştirilmiştir.
Yapılan hesaplama denemeleri önerilmiş algoritmaların verimliliğinin yüksek olduğunu göstermektedir. Knapsack paket programı bu algoritmaları içermektedir.
Makalede KnapsacK paket programı ile yapılan performans testlerinin sonuçları da verilmiştir.
3.
Knapsack paket programı
3.1. Program hakkında ön bilgi
Program sadece
çok boyutlu Knapsack problemi için tasarlanmıştır. Buna yönelik olarak sadece
AS ve AD algoritmalarını içermektedir. Program Delphi 4.0 ile OOP ( nesneye
yönelik programlama ) teknikleri kullanılarak hazırlanmıştır. Dolayısıyla çok
boyutlu Knapsack problemi için geliştirilmiş olan diğer algoritmaların
eklenmesi de son derece kolaydır.
3.2. Programın genel görünümü
Program girdi dosyaları
üzerinden çalışmakta ve birden fazla girdi dosyasını aynı anda
görüntüleyebilmektedir. Girdiler algoritmadan bağımsız olarak oluşturulmakta ve
istenen algoritma ile sonuç elde edilebilmektedir. Çıktılar ise ortak bir
pencerede verilmektedir.
Şekil 1. Programın ana
penceresi
3. 3. Yeni girdi oluşturma
‘Dosya’ mönüsünden ‘Yeni’
seçeneği seçilerek yeni bir girdi oluşturulabilir. Oluşturulan yeni girdinin
boyutları ‘m’ ve ‘n’ veri alanlarından değiştirilebilir. Boyutlar
değiştirildiğinde değer tablolarının
boyutları da otomatik olarak değişecektir.
Probleme ait değerler
tablolardan girilir. Oluşturulan örneğin daha sonra tekrar kullanılabilmesi
için kaydedilmesi gerekir.
3.4. Girdinin kaydedilmesi
‘Dosya’ mönüsünden ‘Kaydet’
seçeneği seçilir.
Girdi yeni oluşturulmuş ise
girdiye bir isim verilmesi için kaydetme diyaloğu gelecektir. Burada girdiye
bir isim verilerek girdi belirtilen isim ile kaydedilir.Eğer girdi daha önceden
oluşturulmuş ise eski girdi dosyası girdinin son hali ile güncellenir.
3.5. Girdinin farklı bir
isim ile kaydedilmesi
Önceden oluşturulmuş bir
girdiyi farklı bir isim ile kaydetmek için ‘Dosya’ mönüsünden ‘Farklı kaydet’
seçeneği seçilir. Gelecek olan kayıt diyalogunda girdiye yeni bir isim verilir
ve girdi verilen isim ile kaydedilir.
Şekil 2. Farklı kaydet
diyaloğu
3.6. Önceden oluşturulan
girdilerin yüklenmesi
‘Dosya’ mönüsünden ‘Aç’
seçeneği seçilir. Ekrana gelen dosya açma diyaloğu kullanılarak istenen girdi
dosyası seçilir. Seçilen girdi dosyasının içeriği oluşturulacak yeni bir girdi
penceresinde görüntülenecektir.
Şekil 3. Dosya açma diyaloğu
3.7. Girdi penceresini
kapatma
Kapatılmak istenen girdi
dosyasına ait sekme seçilerek aktif hale getirilir. ‘Dosya’ mönüsünden Kapat’ seçeneği
seçilerek istenen girdi dosyası kapatılmış olur. Eğer girdi üzerinde değişiklik
yapılmış ise değişikliklerin kaydedilip kaydedilmeyeceğini soran bir mesaj
penceresi gelecektir.
3.8. Diğer seçenekler
‘Dosya’ mönüsünde ‘Hepsini
kaydet’ ve ‘Hepsini kapat’ seçenekleri de bulunmaktadır.
‘Hepsini kaydet’
seçildiğinde üzerinde değişiklik yapılmış olan
bütün girdiler kaydedilir.
‘Hepsini kapat’ seçildiğinde
açılık durumdaki bütün girdi pencereleri kapatılır. Üzerinde değişiklik
yapılmış olan girdiler için uyarı pencereleri gelecektir.
3.9. Algoritma seçimi ve problemin çözümü
Programda çözüm için
kullanılabilecek iki adet algoritma vardır. Bunlar önceki bölümlerde anlatılan
AS ve AD algoritmalarıdır.
Öncelikle çözümü araştırılan
problemin girdisi aktif duruma getirilmelidir. Sonra istenen algoritma ‘Çözüm’
mönüsünden seçilmelidir. İterasyon tamamlandığında elde edilen çözüm ve çözüm
ile ilgili bilgiler ‘Sonuçlar’ penceresinde görüntülenecektir.
Elde edilen çözüm
‘Kopyala/Yapıştır’ yöntemi ile istenen herhangi bir kelime işlemcisi ortamına
taşınabilir.
4. Hesaplama Denemesinin Sonuçları
Önerilen
algoritmanın efektifliğini değerlendirmek için IBM PC(Pentium-166)
bilgisayarında KnapsacK paket programı ile literatürden bilinen test
problemlerle [5,10-12], hesaplama denemesi yapılmıştır.
Hesaplama denemesinin sonuçlarını göstermek için
aşağıdaki işaretlemeler kullanılmıştır:
m- problemdeki koşulların
sayısı,
n- değişkenlerin sayısı,
F(a) - a algoritması ile alınmış
çözüm için amaç fonksiyonunun değeri.
Fopt - verilmiş
problem için amaç fonksiyonun optimal değeridir.
d={[Fopt-F(a)]/Fopt}.100=(1-F(a)/Fopt).100 nispi
hatadır.
Tablo 1’de 7
problem için amaç fonksiyonlarının optimal, AS ve AD algoritmaları ile alınmış değerleri
gösterilmiştir. Buradaki problemler ve onların optimal değerleri [10]
makalesinden götürülmüştür.
Tablo 1. [10]’de verilmiş
testlerle yapılmış hesaplama denemelerinin sonuçları
|
Prob. No |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
Mxn |
10x6 |
10x10 |
10x15 |
10x20 |
10x28 |
5x39 |
5x50 |
|
F(AS) |
3800 |
8319.3 |
4005 |
6110 |
12400 |
10584 |
16529 |
|
F(AD) |
3800 |
8319.3 |
4005 |
6120 |
12400 |
10547 |
16529 |
|
F opt |
3800 |
8706.1 |
4015 |
6120 |
12400 |
10618 |
16537 |
Tablo 2’de mxn=30x60
boyutlu iki test probleminin amaç fonksiyonlarının optimal ve farklı
algoritmalarla alınmış değerleri gösterilmiştir. Bu problemler ve M1, M2, M3,
M4 algoritmalarının bulduğu değerler [11] makalesinden alınmıştır.Optimal değer
ise QSB3 paketi ile hesaplanmıştır.
Tablo 2. [11] ‘de
verilmiş testlerle yapılmış hesaplama denemelerinin sonuçları
|
Test\Algo. |
Fopt |
F(AS) |
F(AD) |
F(M1) |
F(M2) |
F(M3) |
F(M4) |
|
Test 1 |
7770 |
7761 |
7761 |
7643 |
7700 |
7643 |
7700 |
|
Test 2 |
8722 |
8722 |
8709 |
8698 |
8687 |
8698 |
8685 |
Tablo 3’de 10
grup test problem için AS ve AD algoritmaları ile alınmış çözümlerin nispi
hatası gösterilmiştir. Buradaki problemler [5] makalesinde verilmiş algoritma ile
oluşturulmuştur. Bu zaman parametrelerin değerleri aşağıdaki gibi kabul
edilmiştir : L = 0, R = 3,
Q = 1.33 ve T = 1,2,..,10 ; b değeri tabloda
verilmiştir, bi = 
. Problemlerin optimal değeri ise QSB3 paketi ile hesaplanmıştır.
Tablo 3. [5]’de verilmiş
algoritma ile alınmış testlerle yapılan hesaplama
denemelerinin sonuçları.
|
Alg. |
b=0.5 |
b=0.6 |
b=0.7 |
b=0.8 |
||||
|
m x n |
AS |
AD |
AS |
AD |
AS |
AD |
AS |
AD |
|
10x10 |
2.34 |
2.12 |
0.62 |
0.51 |
1.48 |
1.36 |
0.94 |
0.84 |
|
10x15 |
0.57 |
0.61 |
1.09 |
0.94 |
0.75 |
0.62 |
0.76 |
0.68 |
|
10x20 |
1.60 |
1.24 |
1.26 |
1.15 |
0.43 |
0.38 |
1.12 |
1.02 |
|
10x25 |
0.84 |
0.46 |
0.62 |
0.54 |
0.80 |
0.66 |
0.59 |
0.46 |
|
10x30 |
1.12 |
0.89 |
0.67 |
0.48 |
0.32 |
0.28 |
0.17 |
0.24 |
|
20x10 |
0.52 |
0.62 |
2.35 |
1.87 |
1.64 |
1.42 |
0.00 |
0.16 |
|
20x15 |
2.31 |
1.81 |
0.82 |
0.76 |
0.06 |
0.12 |
0.94 |
0.84 |
|
20x20 |
2.23 |
1.96 |
1.07 |
0.98 |
1.02 |
0.88 |
0.29 |
0.35 |
|
20x25 |
1.17 |
1.22 |
0.39 |
|||||