PL
 |
EN
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 12

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last
Wyniki wyszukiwania
Wyszukiwano:
w słowach kluczowych:  problem plecakowy
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 Appraisal of genetic algorithm and its application in 0-1 knapsack problem
Okwu Modestus, Otanocha Omonigho B., Omoregbee Henry O., Edward Bright A.
Journal of Mechanical and Energy Engineering
|
2020
|
Vol. 4, No 1
39--46
EN
A lot of uncertainties and complexities exist in real life problem. Unfortunately, the world approaches such intricate realistic life problems using traditional methods which has failed to offer robust solutions. In recent times, researchers look beyond classical techniques. There is a model shift from the use of classical techniques to the use of standardized intelligent biological systems or evolutionary biology. Genetic Algorithm (GA) has been recognized as a prospective technique capable of handling uncertainties and providing optimized solutions in diverse area, especially in homes, offices, stores and industrial operations. This research is focused on the appraisal of GA and its application in real life problem. The scenario considered is the application of GA in 0-1 knapsack problem. From the solution of the GA model, it was observed that there is no combination that would give the exact weight or capacity the 35 kg bag can carry but the possible range from the solution model is 34 kg and 36 kg. Since the weight of the bag is 35 kg, the feasible or near optimal solution weight of items the bag can carry would be 34 kg at benefit of 16. Additional load beyond 34 kg could lead to warping of the bag.
3
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.
4
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.
5
Content available 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.
6
Poszukiwanie rozwiązań problemu plecakowego z wykorzystaniem algorytmu genetycznego
Handzel Z., Gajer M.
Elektronika : konstrukcje, technologie, zastosowania
|
2014
|
Vol. 55, nr 2
45-46
PL
Tematyka artykułu dotyczy wykorzystania techniki obliczeniowej opartej na zastosowaniu algorytmów genetycznych na potrzeby rozwiązania zagadnienia plecakowego. W artykule zaproponowano wykorzystanie binarnego sposobu kodowania rozwiązań na materiale genetycznym ewoluujących osobników. Szerzej omówiono zagadnienia związane z obliczaniem wartości funkcji dopasowania i realizacją operacji selekcji turniejowej.
EN
The topic of the paper is about using computational technique based on genetic algorithms for the purpose of rucksack problem solution. In the paper we propose to use binary system of coding of the solutions on the genetic material of evolving individuals. We discuss in detail the issues related to calculating the values of fitness function and realizations of tournament selection.
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 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.
9
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.
10
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.
11
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.
12
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
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ć.