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 |
0.42 |
0.27 |
0.25 |
0.25 |
0.15 |
|
20x30 |
2.08 |
2.88 |
0.61 |
0.55 |
0.39 |
0.43 |
0.16 |
0.18 |
Tablo 4’de büyük boyutlu problemler için AS ve AD algoritması
ile alınmış çözümlerin nispi hataları gösterilmiştir. Buradaki test problemleri
ve onların optimal çözümleri [12]’de verilmiş algoritma ile alınmıştır ,burada 
.
Tablo 4. [12]’de verilmiş
algoritma ile alınmış testlerle yapılan hesaplama
denemelerinin sonuçları
|
Mxn |
10x100 |
10x200 |
10x300 |
10x400 |
10x500 |
|||||
|
Prob No\Alg. |
AS |
AD |
AS |
AD |
AS |
AD |
AS |
AD |
AS |
AD |
|
1 |
0.23 |
0.18 |
0.17 |
0.15 |
0.14 |
0.12 |
0.01 |
0.01 |
0.05 |
0.04 |
|
2 |
0.23 |
0.21 |
0.13 |
0.12 |
0.05 |
0.06 |
0.07 |
0.02 |
0.03 |
0.02 |
|
3 |
0.17 |
0.16 |
0.14 |
0.16 |
0.10 |
0.03 |
0.09 |
0.06 |
0.05 |
0.01 |
|
4 |
0.29 |
0.12 |
0.18 |
0.09 |
0.12 |
0.07 |
0.09 |
0.03 |
0.04 |
0.04 |
|
5 |
0.23 |
0.22 |
0.11 |
0.08 |
0.11 |
0.05 |
0.09 |
0.05 |
0.08 |
0.03 |
|
6 |
0.28 |
0.31 |
0.10 |
0.12 |
0.02 |
0.04 |
0.05 |
0.03 |
0.06 |
0.03 |
|
7 |
0.06 |
0.17 |
0.08 |
0.06 |
0.06 |
0.02 |
0.03 |
0.04 |
0.05 |
0.05 |
|
8 |
0.24 |
0.18 |
0.11 |
0.05 |
0.08 |
0.12 |
0.13 |
0.08 |
0.03 |
0.02 |
|
9 |
0.21 |
0.16 |
0.08 |
0.06 |
0.25 |
0.13 |
0.01 |
0.01 |
0.07 |
0.04 |
|
10 |
0.38 |
0.28 |
0.04 |
0.02 |
0.11 |
0.11 |
0.03 |
0.03 |
0.05 |
0.03 |
|
d0 |
0.232 |
0.199 |
0.114 |
0.091 |
0.104 |
0.075 |
0.065 |
0.036 |
0.051 |
0.031 |
Tablo 4’den göründüğü gibi
değişkenlerin sayısı arttıkça AS ve AD algoritmalarının bulduğu çözümlerin
nispi hatası azalır.
5.
Sonuç
Rm
probleminin çözümü için bilinen heuristik algoritmalar çeşitli sıralı tarama
şemaları ile yapılır [6] .Bu durumda
tarama şeması önceden saptanır. Fakat verilen somut problemin özelliğini
tümüyle dikkate almak için, çözüm arama sürecinde o anki bilginin temel olarak
değişebilen daha esnek bir tarama şemasının elde edilmesine gereksinim
duyulmaktadır. Yukarıda verilen sert koşul yapısı bu tarama şemasını formalize
etmeye imkan verir. Bu durumda verilen problemin özelliğine uyan taramaya uyum
gerçekleştirilir. Algoritma çalıştığı zaman , her iterasyonda Rm
probleminin amaç fonksiyonunun değeri hesaplanır ve inşa edilmiş lokal optimal
planlar kümesi arasından en iyi suboptimal planın elde edilmesini sağlayan
değer seçilir. Algoritmanın çalışması
sürecinde her bir iterasyonda sert koşullar belirlenir ve uygun l(k) (k=1,2,..,) ile değiştirilerek yapay
koşulların katsayıları Rm probleminin verilerine uygun olan bir
ortalama değere yaklaştırılır.
Böylece problemin
çözümü sürecinde elde edilen o andaki bilgilerin bazında bir uyuşumun
(selforganization) yapıldığı bir algoritmanın formalize edilmesi şeması
bulunmuş olur.
Önerilen yöntem,
başka yöntemlerin bilgisayarın merkezi işlem ünitesinin(CPU) sınırlı olmasından
dolayı uygulanamayan büyük mertebeli sistemlerin çözümü için elverişlidir.
Önerilen yöntemi
uygulayan algoritma çok basit lojistik şemaya(yapıya) sahiptir.Uygulama için merkezi
işlem ünitesinin küçük hacmi yeterlidir.Algoritma yüksek hızlıdır.Bu yöntemin
yardımıyla, verilen hata ile yaklaşık çözüm kolayca bulunur.Önerilen yöntemin
farklı özelliği bunun iterasyon tipli çok adımlı bir algoritma olması ve
verilen kaynaklara(zaman, bellek,vs.) göre gerçek koşullarda kaynaklara
orantılı şekilde optimal çözüme yakın mümkün çözümleri bulmaya imkan
sağlamasıdır.
MS Windows
ortamında Delphi 4.0 ve OOP (nesneye yönelik programlama) teknikleri
kullanılarak önerilen algoritmaları içeren KnarsacK paket programı
hazırlanmıştır. Bu paket ile yapılan performans testlerinin sonuçları önerilen
algoritmaların verimliliğinin yüksek olduğunu göstermektedir.
KAYNAKLAR
1. Mertello S. and Toth P. Knapsack problems : Algorithm and computer implementation, John Wiley
& Sons, (1990), - 296p.
2. Nuriyev, U.G. A Hibrid Method for Solving the Multi-dimensional Knapsack Problem. Preprint.
IK AN USSR. No 83-43, Kiev, (1983), - 28 p. (Russian).
3. Loulou, R. and Michaeldes, E. "New Greedy-like Heuristics for the Multidimensional 0-1 Knapsack
Problem", Operations Research , Vol. 27, (1979), 1101-1114.
4. Garey,R.M., Johnson,D.S. Computers and Intractability.A Guide to the Theory of NP-Completeness.
San Francisco. W.H.Freeman and Co. (1979)- 338p.
5. Babayev D.A. Mamedov K. Sh., Mehtiev M.G. “Methods for the suboptimal solution of the
multidimensional Knapsack problem”, Computational Mathematics and Mathematical Physics,
18, N6, (1978), 1443-1453.
6. Ohlsson M., Pi H. “Study of the mean field approach to Knapsack problems”. Neural Networks. 10,
(1997), 263-271.
7. Nuriyev, U.G. ”Discrete Optimizasyon probleminin çözümü için bir matematiksel software
problemi”. Applied programming, IK AN USSR, (1982), 28-34. (Russian).
8. Nuriyev, U.G., Dündar P. “Çok boyutlu Knapsack probleminin çözümü için kendi kendini
düzenleyen bir algoritma”. Yöneylem araştırması ve Endüstri mühendisliği. XIX.Ulusal
kongresi.Ankara . (1998).
9. Nuriyev, U.G., Dündar P. “Knapsack probleminin çözümü için duallik prensibine dayanan heuristik
bir algoritma”. Yöneylem Araştırması ve Endüstri mühendisliği XX I Ulusal kongresi. KKTC,(2000)
10. Petersen C.C. “Computational Experience With Variants of the Balas Algorithm Applied to the
selection of R-D Projects”. Management Science,Vol. 13, No. 9, (1967), 736-750.
11. Senju,S.-Toyoda,Y. “An Approach to Linear Programming 0-1 Variables”. Management Science,
vol.15, No. 4, (1975), 196-207.
12. Pirianovich V.A. “Computational experiences for solution to linear integer programming problems
with local-stochastic algorithms”, Computational Mathematics and Mathematical Physics,
19, No 1, (1979), 79-87.