PL
 |
EN
Ograniczanie wyników
Czasopisma help
  1. 4 Fundamenta Informaticae
  2. 1 Annals of Computer Science and Information Systems
  3. 1 Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
  4. 1 Bulletin of the Polish Academy of Sciences. Technical Sciences
  5. 1 Czasopismo Techniczne. Automatyka
Więcej...
Autorzy help
  1. 2 Aho I.
  2. 2 Guze S.
  3. 2 Pieńkosz K.
  4. 1 Baltazar B.
  5. 1 Błażewicz J.
Więcej...
Lata help
  1. 1 2021
  2. 3 2018
  3. 1 2016
  4. 1 2014
  5. 1 2013
Więcej...
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 19

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last
Wyniki wyszukiwania
Wyszukiwano:
w słowach kluczowych:  knapsack problem
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available remote InterCriteria Analyzis of Hybrid Ant Colony Optimization Algorithm for Multiple Knapsack Problem
Fidanova Stefka, Ganzha Maria, Roeva Olympia
Annals of Computer Science and Information Systems
|
2021
|
Vol. 25
173--180
EN
The local search procedure is a method for hybridization and improvement of the main algorithm, when complex problems are solved. It helps to avoid local optimums and to find faster the global one. In this paper we apply InterCriteria analysis (ICrA) on hybrid Ant Colony Optimization (ACO) algorithm for Multiple Knapsack Problem (MKP). The aim is to study the algorithm behavior comparing with traditional ACO algorithm. Based on the obtained numerical results and on the ICrA approach the efficiency and effectiveness of the proposed local search procedure are confirmed.
2
Content available Review of Methods and Algorithms for Modelling Transportation Networks Based on Graph Theory
Guze S.
Zeszyty Naukowe Akademii Morskiej w Gdyni
|
2018
|
nr 107
25--39
EN
One of the best ways of modelling a transport network is to use a graph with vertices and edges. They represent nodes and arcs of such network respectively. Graph theory gives dozens of parameters or characteristics, including a connectivity, spanning trees or the different types of domination number and problems related to it. The main aim of the paper is to show graph theory methods and algorithms helpful in modelling and optimization of a transportation network. Firstly, the descriptions of basic notations in graph theory are introduced. Next, the concepts of domination, bondage number, edge-subdivision and their implementations to the transportation network description and modeling are proposed. Moreover, the algorithms for finding spanning tree or maximal flow in networks are presented. Finally, the possible usage of distinguishing concepts to exemplary transportation network is shown. The conclusions and future directions of work are presented at the end of the paper.
PL
Jednym z najlepszych sposobów modelowania sieci transportowej jest użycie grafu z wierzchołkami i krawędziami. Reprezentują one odpowiednio węzły i łuki takiej sieci. Teoria grafów daje możliwość użycia dziesiątek parametrów lub charakterystyk, w tym spójności, drzew spinających lub różnych typów liczb dominowania i związanych z tym problemów. Głównym celem artykułu jest przedstawienie metod i algorytmów teorii grafów pomocnych w modelowaniu i optymalizacji sieci transportowej. Po pierwsze, wprowadzono opisy podstawowych pojęć w teorii grafów. Następnie zaprezentowano koncepcje domino­wania, liczby zniewolenia czy podziału krawędzi grafu oraz ich implementacji do opisu i modelowania sieci transportowej. Ponadto przedstawiono algorytmy do wyszukiwa­nia drzewa opinającego i maksymalnego przepływu w sieciach. Wreszcie pokazano możliwe sposoby wykorzystania wyróżnionych koncepcji do przykładu sieci transportowej. Na zakoń­czenia przedstawiono wnioski i przyszłe kierunki prac.
3
Content available remote A software program for optimal 1D cutting suport
Pacek M., Horla D.
Studia z Automatyki i Informatyki
|
2018
|
T. 43
95--107
EN
The paper summarizes the procedure of solving 1D optimal cutting problems, giving details of coding it using dynamic programming, knapsack problem formulation and column generation approach. Finally, the software program for optimal 1D cutting support is described, which is the open code version enabling researchers to extent its capabilities. The paper ends by giving solutions to stated problems and the description of the GUI of the program. At the end of the paper, the reference to the other paper of the authors discussing the effectiveness of the proposed solution is given, tightly connected with this paper.
PL
W artykule przedstawiono procedurę rozwiązywania zadania optymalizacji docinania 1D, włączając szczegóły zakodowania algorytmu przy użyciu programowania dynamicznego, formalizmu zadania plecakowego oraz metody generowania kolumn. W końcu, opisano program wspomagania optymalnego docinania, w postaci programu w otwartym kodzie co pozwoli badaczom na jego dalsze rozwijanie. Artykuł zawiera rozwiązania przykładowych zadań optymalizacji, jak i też opis interfejsu użytkownika. Zawarto również odnośnik do drugiego artykułu autorów, przedstawiającego efektywność zastosowanych metod.
4
Content available remote Optymalizacja wypełnienia przestrzeni ładunkowej z wykorzystaniem algorytmów mrówkowych
Świątnicki Z.
Gospodarka Materiałowa i Logistyka
|
2018
|
nr 12
1201--1211, CD
PL
Artykuł poświęcony jest problemowi wykorzystania przestrzeni ładunkowej. Zastosowano do tego celu algorytmy mrówkowe. Zbudowano model optymalizacyjny oparty na problemie plecakowym. Wybrano 8 różnych algorytmów mrówkowych. Przedstawiono i omówiono uzyskane wyniki zastosowania algorytmów mrówkowych do rozwiązywania problemu plecakowego.
EN
The article is devoted to the optimization problem of cargo space. Formal algorithms have been used for this purpose. An optimization model based on a knapsack problem was built. 8 different ant algorithms were selected. The results of the application of ant algorithms for solving the knapsack problem are presented and discussed.
5
Content available Combinatorial approaches to the capital-budgeting problem
Pichugina O.
ECONTECHMOD : An International Quarterly Journal on Economics of Technology and Modelling Processes
|
2016
|
Vol. 5, No 4
29--36
EN
Optimization approaches, combinatorial and continuous, to a capital-budgeting problem (CBP) are presented. This NP-hard problem, traditionally modelled as a linear binary problem, is represented as a biquadratic over an intersection of a sphere and a supersphere. This allows applying nonlinear optimization to it. Also, the method of combinatorial and surface cuttings (MCSC) is adopted to (CBP). For the single constrained version (1CBP), new combinatorial models are introduced based on joint analysis of the constraint, objective function, and feasible region. Equivalence of (1CBP) to the multichoice knapsack problem (MCKP) is shown. Peculiarities of Branch&Bound techniques to (1CBP) are described.
6
Content available Application of the knapsack problem to reliability multi-criteria optimization
Guze S.
Journal of Polish Safety and Reliability Association
|
2014
|
Vol. 5, No. 1
85--90
EN
The main aim of the paper is to translate reliability problems to the knapsack optimization problem. The review of the known methods of multi-criteria optimization is done. Particularly, the SPEA algorithm is presented. Furthermore, the 0-1 knapsack problem solution by SPEA algorithm is introduced and used to the reliability optimization of exemplary parallel-series system.
7
Content available remote Ant colony optimization algorithm for the 0-1 knapsack problem
Schiff K.
Czasopismo Techniczne. Automatyka
|
2013
|
R. 110, z. 3-AC
39--52
EN
This article describes a new ant colony optimisation algorithm for the discrete knapsack problem with a new heuristic pattern, based on the ratio of the square of the profit coefficient to the square of the weight coefficient of the original problem. This new heuristic is used in order to choose objects that should be packed into the knapsack. This pattern was compared with two used in ant algorithms and which have been presented in the literature on the subject of ant colony optimisation algorithms for the 0-1 Knapsack Problem. The two other patterns are based on the ratio of the profit coefficient to the weight coefficient multiplied respectively by the total and the current knapsack load capacity. Results of tests under a width range of ant algorithm parameters such as the number of cycles, the number of ants, the evaporation rate, and the load knapsack capacity are shown and discussed.
PL
W artykule przedstawiono algorytm mrówkowy dla dyskretnego problemu plecakowego z nową heurystyką wyboru obiektów i został on porównany z dwoma innymi algorytmami spotkanymi w literaturze przedmiotu pod względem uzyskiwanego całkowitego zysku z załadowanych do plecaka przedmiotów. Nowa heurystyka wyboru została wyrażona poprzez stosunek kwadratu zysku do kwadratu wagi wybranego przedmiotu, gdy dwie znane już heurystyki to stosunek zysku do wagi odpowiednio pomnożony przez całkowitą i bieżącą ładowność plecaka. W artykule przedstawiono wyniki przeprowadzonych testów dla szerokiego zakresu parametrów algorytmów mrówkowych takich jak: współczynnik parowania, liczba cykli, liczba mrówek, ładowności plecaka jak i dla różnej liczby dostępnych przedmiotów do załadunku.
8
Content available Application of the Bee Swarm Optimization BSO to the Knapsack Problem
Sotelo-Figueroa M. A., Baltazar B., Carpio J. M.
Journal of Automation Mobile Robotics and Intelligent Systems
|
2011
|
Vol. 5, No. 1
101-114
EN
Swarm Intelligence is the part of Artificial Intelligence based on study of actions of individuals in various decentralized systems. The optimization algorithms which are inspired from intelligent behavior of honey bees are among the most recently introduced population based techniques. In this paper, a novel hybrid algorithm based in Bees Algorithm and Particle Swarm Optimization is applied to the Knapsack Problem. The Bee Algorithm is a new population-based search algorithm inspired by the natural foraging behavior of honey bees, it performs a kind of exploitative neighborhood search combined with random explorative search to scan the solution, but the results obtained with this algorithm in the Knapsack Problem are not very good. Although the combination of BA and PSO is given by BSO, Bee Swarm Optimization, this algorithm uses the velocity vector and the collective memories of PSO and the search based on the BA and the results are much better. We use the Greedy Algorithm, which it's an approximate algorithm, to compare the results from these metaheuristics and thus be able to tell which is which gives better results.
9
Content available Zastosowanie przykładowego algorytmu stadnego w optymalizacji kombinatorycznej
Filipowicz B., Kwiecień J.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2010
|
T. 14, z. 3/2
885-891
PL
Algorytmy metaheurystyczne inspirowane naturą znajdują szerokie zastosowanie w problemach optymalizacji kombinatorycznej. Do tej klasy metod należy algorytm optymalizacji rojem cząstek oparty na zachowaniach stada ptaków. W artykule przedstawiono zastosowanie binarnego algorytmu optymalizacji rojem cząstek do rozwiązania wielowymiarowego problemu plecakowego. Zaprezentowano również wyniki eksperymentów dla wybranych instancji testowych.
EN
Nature-inspired metaheuristic algorithms are successfully applied to combinatorial optimization problems. They incorporate particle swarm optimization inspired by the behaviors of bird flocks. This paper presents the applying of binary particle swarm optimization to the multidimensional knapsack problem. The results of computational experiments for standard test problems have been also presented.
10
Content available remote The Knapsack-Lightening problem and its application to scheduling HRT tasks
Nawrocki J.R., Complak W., Błażewicz J., Kopczyńska S., Maćkowiak M.
Bulletin of the Polish Academy of Sciences. Technical Sciences
|
2009
|
Vol. 57, nr 1
71-77
EN
In hard real-time systems timeliness is as important as functional correctness. Such systems contain so called hard real-time tasks (HRT tasks) which must be finished by a given deadline. One of the methods of scheduling of HRT tasks is periodic loading introduced by Schweitzer, Dror, and Trudeau. The paper presents an extension to that method which allows for deterministic utilization of cache memory in hard real-time systems. It is based on a new version of the Knapsack problem named Knapsack-Lightening. In the paper the Knapsack-Lightening problem is defined, its complexity is analyzed, and an exact algorithm along with two heuristics are presented. More-over the application of the Knapsack-Lightening problem to scheduling HRT tasks is described.
11
Content available remote Heurystyczne algorytmy ograniczonej alokacji zasobu
Pieńkosz K.
Przegląd Elektrotechniczny
|
2008
|
R. 84, nr 9
89-92
PL
W komórkach żywych organizmów zachodzi wiele procesów biochemicznych podlegających skomplikowanym mechanizmom regulacji. Jednym z nich jest proces produkcji cząsteczek mRNA, zachodzący w jądrze komórkowym. Z praktycznego punktu widzenia jest to proces dyskretny. W niektórych przypadkach może być on jednak opisywany modelami ciągłymi. W niniejszej pracy pokazane są warunki, w jakich zarówno opis dyskretny, jak i ciągły prowadzą do takich samych jakościowo wyników.
EN
In the paper a variant of the continuous knapsack problem is considered in which no more than a specified number of variables are allowed to be positive. Two heuristic algorithms are proposed to solve the problem. Some results of the worst-case performance analysis for these algorithms are provided.
12
Content available remote Computational Complexity of Simple P Systems
Ciobanu G., Resios A.
Fundamenta Informaticae
|
2008
|
Vol. 87, nr 1
49-59
EN
This paper introduces a new class of membrane systems called simple P systems, and studies their computational complexity. We start by presenting the knapsack problem and its time complexity. Then we study the computational complexity of simple P systems by considering the allocation of resources enabling the parallel application of the rules. We show that the decision version of the resource allocation problem for simple P systems is NP-complete, by using the knapsack problem.
13
Content available remote A Quantum-Inspired Evolutionary Algorithm Based on P systems for Knapsack Problem
Zhang G-X., Gheorghe M., Wu C-Z.
Fundamenta Informaticae
|
2008
|
Vol. 87, nr 1
93-116
EN
This paper introduces an evolutionary algorithm which uses the concepts and principles of the quantum-inspired evolutionary approach and the hierarchical arrangement of the compartments of a P system. The P system framework is also used to formally specify this evolutionary algorithm. Extensive experiments are conducted on a well-known combinatorial optimization problem, the knapsack problem, to test the effectiveness of the approach. These experimental results show that this evolutionary algorithm performs better than quantum-inspired evolutionary algorithms, for certain arrangements of the compartments of the P system structure utilized.
14
Content available Optimization Of Operating Tasks Assigned For Engine Room Staff
Kamiński P.
Journal of Polish CIMAC
|
2007
|
Vol. 2, no 1
223-230
EN
The present work shows the two approaches to the problem according to the situation in which the engineer is made to take certain decisions. In formulation of the two most substantial operating states of a ship like lay time in port and sea voyage, knapsack algorithms and task scheduling algorithms were applied. For both approaches was formulated objective function, decision variables and constrains.
15
Właściwości rozwiązań problemu plecakowego z ograniczoną podzielnością elementów
Pieńkosz K.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2006
|
z. 144
189-195
PL
W pracy jest rozpatrywany wariant problemu plecakowego, w którym dopuszcza się podział elementów podczas pakowania przy zastrzeżeniu, że waga umieszczanych w plecaku fragmentów nie może być mniejsza niż zadany parametr [beta]. Analizowane są właściwości rozwiązań optymalnych takiego problemu. Sformułowano warunki opłacalności pakowania poszczególnych elementów, co w wielu przypadkach umożliwia znaczącą redukcję wymiaru rozpatrywanego zadania.
EN
In the paper the semi-continuous variant of the knapsack problem is considered in which items may be fragmented into smaller pieces while putting them into the knapsack. Fragmentation is however subjected to the restriction that the weight of each piece cannot be smaller than the given parameter [beta]. In the paper the properties of the semi-continuous knapsack problem are investigated. It is shown how the optimal values of some variables may be fixed in advance and thus the size of the problem may be reduced.
16
Content available The influence of some controlling parameters on the efficiency of an immune algorithm
Kimaczyńska A., Kimaczyński S., Rohatyński R.
Diagnostyka
|
2006
|
nr 2(38)
61-64
EN
In the paper the influence of the probability of the mutation and size of population on the efficiency of the immune algorithm is considered. The influence was investigated on a simple knapsack problem example. A remarkable lack of the results repeatability was observed. To quantitative description of this phenomenon statistical measures were applied. The best combinations of the parameter values of the immune algorithm were found by means of the full plan of numerical experiments.
PL
W artykule opisano badania wpływu prawdopodobieństwa mutacji i liczebności populacji na skuteczność algorytmu immunologicznego. Jako przykładowe zadanie systemu immunologicznego wybrano problem plecakowy. Zaobserwowano brak powtarzalności wyników. Do opisu tego zjawiska zastosowano ujęcie statystyczne. Doświadczalnie określono najlepszą kombinację wartości parametrów algorytmu immunologicznego.
17
Problem optymalnego doboru firm inwestujących w danym regionie jako informatyczny binarny problem plecakowy
Rybarski J., Tadeusiewicz R.
Informatyka Teoretyczna i Stosowana
|
2005
|
R. 5, nr 9
187--193
PL
Zagadnienie doboru optymalnego koszyka firm inwestujących w danym regionie będzie w najbliższym czasie jednym z najbardziej palących problemów, z jakimi będą musieli zmierzyć się pracownicy administracji publicznej. Nie ulega wątpliwości, że proces podejmowania decyzji powinien być tu wspomagany komputerowo, gdyż liczba czynników, argumentów, parametrów i okoliczności, jakie trzeba wziąć pod uwagę, wybierając inwestorów, zdecydowanie przekracza ludzkie możliwości oceny sytuacji i wy-boru optymalnej decyzji. W tej sytuacji autorzy prezentowanej pracy podjęli próbę zdefiniowania zadań, jakie powinien spełniać system komputerowy wytwarzający niezbędną wiedzę decyzyjną oraz wspomagający proces podejmowania decyzji, a także zaproponowali sposób podejścia do jego rozwiązania. Ten ostatni opracowano, wykorzystując analogię, jaka istnieje pomiędzy rozważanym problemem doboru optymalnego "koszyka inwestorów" a jednym z klasycznych problemów informatyki, jakim jest tak zwany "problem plecakowy" (ang. knapsack problem). Autorzy zwrócili także uwagę na problem optymalizacji tak postawionego zadania oraz wynikające z tego powodu wymagania, jakie muszą być posta-wione przed twórcami wcześniej wspomnianego systemu komputerowego wspomagającego proces podejmowania decyzji.
EN
The problem of selection optimal collection of the company's interested in investing in the certain region will be the most important problem, which will have to be solved by public governance in the nearest future. There is no doubt, that this kind of decision process should be rod by computers systems because of the huge numbers of factors, arguments, parameters and facts (which have to be taken into considera-tion during process of choosing investor) which are beyond human intellectual power. In this situation the authors defined requirement which the computer decision support system have to meet and show the method of solution problem under consideration. The solution is proposed on the base of analogy which exist between presented decision problem and one of the classical optimization problem, known as "knapsack problem". Authors pay attention to the optimization of decision process and show the requirements which must been taken into account by designers and developers of above-mentioned computer rod decision system
18
Content available remote New Polynomial-time Instances to Various Knapsack-type Problems
Aho I.
Fundamenta Informaticae
|
2002
|
Vol. 53, nr 3,4
199-228
EN
We describe a special case of the interactive knapsack optimization problem (motivated by the load clipping problem) solvable in polynomial time. Given an instance parameterized by k, the solution can be found in polynomial time, where the polynomial has degree k. In the interactive knapsack problem, k is connected to the length induced by an item. A similar construction solves a special case of the 0-1 multi-dimensional knapsack and the 0-1 linear integer programming problems in polynomial time. In these problems the parameter determines the width of the restriction matrix, which is a band matrix. We extend the 0-1 multi-dimensional knapsack solution to 0-n multi-dimensional knapsack problems (and to 0-n IP problems). Our algorithms are based on the (resource bounded) shortest path search: we represent restrictions efficiently in a form of a graph such that each feasible solution has a path between given source and target vertices.
19
Content available remote Interactive knapsacks
Aho I.
Fundamenta Informaticae
|
2000
|
Vol. 44, Nr 1,2
1-23
EN
The interactive knapsack problems are generalizations of the classical knapsack problem. Three different new NP-complete problems, interactive knapsack heuristic decision problem (IKHD), interactive knapsack decision problem (IKD) and multidimensional cloned knapsack decision problem (MDCS), are presented for the interactive knapsack models. IKD and MDCS are shown to be strongly NP-complete. By using interactive knapsacks we can model many planning and scheduling problems in an innovative way. Possible application areas include electricity management, single and multiprocessor scheduling, and packing and tiling problems. As a by-product we show that the longest weight-constrained path problem is NP-complete.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.