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:  quadratic assignment problem
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available Optimization on permutations: related structures, problems interrelation, heuristic compositions, applications
Miatselski M.
Technical Sciences / University of Warmia and Mazury in Olsztyn
|
2018
|
nr 21(1)
37--47
EN
A heuristics based approach to practical solving theoretically intractable combinatory and network problems is discussed. Compound heuristics (heuristics compositions) are suggested to be more efficient procedures for real size problem instances. Some aspects of the heuristics compositions topic are illustrated by optimum permutation problems. We describe a uniform presentation of the chief types of the problems and their interrelations, including the relation “to be a special case of a problem”. We consider a number of algebraic structures and combinatory constructions on permutation sets and present an inclusion chain of these constructions. The chain enables us to establish and clarify many interrelations for the minimum permutation problems, with algorithmic and complexity aspects taken into account. We also concern the applications of some problems as well.
2
Content available A comparison of nature inspired algorithms for the quadratic assignment problem
Chmiel W., Kadłuczka P., Kwiecień J., Filipowicz B.
Bulletin of the Polish Academy of Sciences. Technical Sciences
|
2017
|
Vol. 65, nr 4
513--522
EN
This paper presents an application of the ant algorithm and bees algorithm in optimization of QAP problem as an example of NP-hard optimization problem. The experiments with two types of algorithms: the bees algorithm and the ant algorithm were performed for the test instances of the quadratic assignment problem from QAPLIB, designed by Burkard, Karisch and Rendl. On the basis of the experiments results, an influence of particular elements of algorithms, including neighbourhood size and neighbourhood search method, will be determined.
3
Content available remote Problem przydziału oraz sztuczna inteligencja w logistyce
Kudelska I., Radecki A.
Zeszyty Naukowe. Organizacja i Zarządzanie / Politechnika Łódzka
|
2013
|
z. 54
171--179
PL
Celem niniejszego opracowania jest przybliżenie Kwadratowego Problemu Przydziału, narzędzi Sztucznej Inteligencji - Algorytmów Genetycznych oraz ukazanie ich zastosowania w obszarze logistyki. W pierwszej części przeprowadzono analizę literaturową na temat zagadnienia QAP oraz Algorytmów Genetycznych, natomiast w podsumowaniu ukazano ich zastosowanie.
EN
The aim of this paper is to present the Quadratic Assignment Problem and tools of Artificial Intelligence - Genetic Algorithms and demonstrate their application in the area of logistics. In the first part the authors analyzed the literature on the issue of QAP and Genetic Algorithms. Whereas in summary they showed the application of these tools.
4
Content available Algorytmy stadne w optymalizacji problemów przydziału przy kwadratowym wskaźniku jakości (QAP)
Filipowicz B., Kwiecień J.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2011
|
T. 15, z. 2
159-166
PL
W artykule przedstawiono rozwiązanie kwadratowego problemu przydziału, który należy do AP-trudnych problemów optymalizacji dyskretnej, za pomocą algorytmów stadnych. Zastosowano trzy algorytmy: algorytmy mrówkowe, algorytmy optymalizacji rojem cząstek i algorytmy pszczele. Przedstawiono wyniki badań dla wybranych instancji testowych z biblioteki QAPLIB.
EN
This paper presents three swarm algorithms: ant algorithms, particle swarm optimization and bee algorithms, used for solution of quadratic assignment problem, which is a NP-hard optimization problem. The results of experiments performed for selected test problems of quadratic assignment problems from QAPLIB library have been also presented.
5
Alternatywna metoda rozwiązywania kwadratowego zagadnienia przydziału
Schiff K.
Logistyka
|
2010
|
nr 2
PL
Kwadratowy problem przydziału polega na takim umieszczeniu fabryk (obiektów) w lokalizacjach, aby całkowity koszt wyrażony jako suma iloczynów odległości między obiektami i strumieni towarów przepływających między tymi obiektami był jak najmniejszy. Artykuł ten przedstawia nowy sposób modelowania problemu przy wykorzystaniu grafów dwudzielnych i nowy sposób rozwiązania problemu, krok po kroku, polegający na znalezieniu maksymalnego dopasowania o minimalnej wadze z uwzględnieniem fizycznego umiejscowienia fabryk (obiektów) w lokalizacjach.
EN
A new method for quadratic assignment problem is presented. The problem is modeled by a bipartite graph. Hungarian method is used for finding the solution: the assignment with minimum costs is found, but this solution must take into consideration of real objects localizations.
6
Content available Ukierunkowane przeszukiwanie przestrzeni rozwiązań w algorytmach rojowych
Filipowicz B., Chmiel W., Kadłuczka P.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2009
|
T. 13, z. 2
247-255
PL
W artykule przedstawiono sposób ukierunkowania przeszukiwania przestrzeni rozwiązań, wykorzystujący warunkową wartość oczekiwaną funkcji celu rozwiązań częściowo ustalonych. Teoretyczne podstawy dotyczące wartości oczekiwanej opracowano dla szerokiej klasy zagadnień permutacyjnych, których przykładem są TSP (zagadnienie komiwojażera), czy rozważane zagadnienie testowe QAP (kwadratowe zagadnienie przydziału) - należące do NP-trudnych problemów optymalizacji dyskretnej. Zastosowanym algorytmem rojowym jest algorytm pszczeli, ale powyższe podejście może być również wykorzystane w algorytmach mrówkowych. Przedstawione wyniki badań eksperymentalnych dla standardowych zagadnień testowych zaczerpniętych z biblioteki QAPLIB wskazują na wysoką efektywność zaproponowanej metody.
EN
This paper investigates a new advanced swarm algorithm for optimization of permutation problems. The introduction in algorithms the expected value of objective function allows effective evaluation of quality of partially fixed solutions. The parameter can be used as auxiliary criterion for selection and construction of new solutions, increasing the effectiveness of designed algorithms. The experiments were performed for standard test problems of quadratic assignment problems (QAP).
7
Content available Wykorzystanie własności zagadnienia QAP w konstrukcji algorytmów ewolucyjnych
Kadłuczka P., Chmiel W.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2007
|
T. 11, z. 1-2
151-160
PL
Artykuł prezentuje wyniki prac związanych z implementacją i badaniem efektywności algorytmu ewolucyjnego, wykorzystującego specjalizowane operatory pseudogenetyczne dla kwadratowego zagadnienia przydziału. Operatory te bazują na własnościach przestrzeni rozwiązań, stosując warunkową wartość oczekiwaną funkcji celu rozwiązań częściowo ustalonych. Wprowadzenie do operatorów dodatkowej wiedzy o optymalizowanym problemie umożliwia ukierunkowanie procesu eksploracji przestrzeni rozwiązań w regiony zawierające rozwiązania o wyższej jakości.
EN
The paper presents an approach to an implementation and evaluation of evolutionary algorithm using operators exploiting peculiar properties of QAP problem. They are based on expected conditional value of objective function for partially fixed solutions. The numerical experiments were performed for standard test problems of quadratic assignment problem (QAP) from QAPLIB-A library. We compare the results of algorithms using pseudo-genetic operators which exploit some QAP problem properties with results obtained from algorithms using standard pseudo-genetic operators for permutation problems.
8
Efektywność algorytmu ewolucyjnego wykorzystującego mechanizm różnicowania
Chmiel W., Kadłuczka P., Jędrusik S.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2006
|
z. 143
33-44
PL
Artykuł prezentuje wyniki prac związanych z implementacją i badaniem efektywności algorytmu ewolucyjnego, wykorzystującego operatory różnicujące. Bazują one na warunkowej wartości oczekiwanej funkcji celu rozwiązań częściowo ustalonych. Badania testowe wykonano dla standardowych zadań testowych kwadratowego zagadnienia przydziału (QAP).
EN
The paper presents our work on implementation and evaluation of evolutionary algorithm using diversification operators. They are based on expected conditional value of objective function for partially fixed solutions. The experiments were performed for standard test problems of quadratic assignment problems (QAP).
9
Content available Warunkowa wartość oczekiwana funkcji celu w konstrukcji algorytmów przybliżonych dla zagadnień permutacyjnych
Chmiel W., Kadłuczka P.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2005
|
T. 9, z. 1-2
47-56
PL
W artykule zaprezentowano rezultaty prac nad zaawansowanymi algorytmami ewolucyjnymi stosowanymi w optymalizacji zagadnień permutacyjnych. Wprowadzenie dodatkowego parametru - warunkowej wartości oczekiwanej funkcji celu pozwala na ocenę jakości rozwiązań częściowo ustalonych. Może być on stosowany jako pomocnicze kryterium wyboru i konstrukcji nowych rozwiązań, w celu poprawy efektywności projektowanych algorytmów.
EN
This paper investigates an application of advanced evolutionary algorithms in optimization of permutation problems. The introduction of additional parameter in algorithms - the expected value of objective function - allows effective evaluation of quality of partially fixed solutions. The parameter can be used as auxiliary criterion for selection and construction of new solutions, increasing the effectiveness of designed algorithms.
10
Content available Efektywność algorytmu ewolucyjnego wykorzystującego warunkową wartość oczekiwaną funkcji celu
Kadłuczka P., Chmiel W.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2005
|
T. 9, z. 1-2
105-114
PL
Artykuł prezentuje wyniki prac związanych z implementacją i badaniem efektywności algorytmów ewolucyjnych, wykorzystujących warunkową wartość oczekiwaną funkcji celu dla częściowo ustalonych rozwiązań w optymalizacji zagadnień permutacyjnych. Jako przykład tego problemu rozważamy kwadratowe zagadnienie przydziału - QAP.
EN
The papers presents the results of our work on implementation and testing of new evolutionary algorithms for optimization of permutation problems. The algorithm flow is controlled by an additional parameter that is used for evaluation of quality of partially fixed solutions: the expected value of objective function. As an example, the quadratic assignment problem QAP is examined.
11
Content available remote Algorytmy mrówkowe dla kwadratowego zadania przydziału
Osyczka A., Adamowicz M., Łącki Ł., Matzka A., Mazgaj J.
Zagadnienia Techniczno-Ekonomiczne
|
2004
|
T. 49, z. 1-2
153-161
PL
W pracy zajęto się wykorzystaniem algorytmów mrówkowych do rozwiązania kwadratowego zadania przydziału. Omówiono ideę algorytmów mrówkowych. Sformułowano problem kwadratowego zadania przydziału oraz zaproponowano system mrówkowy do rozwiązania tego problemu. Opisano opracowany program komputerowy umożliwiający realizację trzech wersji algorytmów mrówkowych. Przedstawiono wyniki obliczeń komputerowych dla typowych zadań przydziału.
EN
In the paper ant colony algorithms are applied to solve quadratic assignment problem. First. the general idea of ant colony algorithms is presented. Then, quadratic assignment problem is formulated and the method of solution of this problem is proposed. The computer program for this method is described. Three versions of ant colony algorithms are implemented in this program. Finally, the results of typical test problems are provided.
12
Content available remote Parametry charakteryzujące własności przestrzeni rozwiązań dla problemu QAP
Chmiel W.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2003
|
T. 7, z. 3
637-648
PL
Kwadratowy problem przypisania (Quadratic Assignment Problem) generalizuje wiele istotnych zagadnień kombinatorycznych. Wśród nich można wymienić takie problemy jak problem komiwojażera (TSP), uogólniony problem podziału grafu (GGP), problem maksymalnej kliki (MCP) w grafie oraz wiele innych. Ze względu na fakt, że problem ten należy do klasy problemów NP-trudnych, otrzymanie dokładnego rozwiązania jest możliwe jedynie dla instancji o niewielkich rozmiarach (n < 25). Do rozwiązywania problemu QAP o większych rozmiarach stosuje się różnego rodzaju algorytmy przybliżone - wśród nich także algorytmy ewolucyjne. Ze względu ma duże zróżnicowanie własności przestrzeni rozwiązań, dla różnych instancji problemu QAP, różna jest jakość uzyskiwanych rozwiązań w oparciu o zastosowany algorytm ewolucyjny. W pracy przedstawiono metody oceny własności przestrzeni rozwiązań problemu QAP oraz próbę określenia na ich podstawie optymalnych wartości parametrów sterujących algorytmem ewolucyjnym. Zadanie to zrealizowano w oparciu o eksperymentalne wyniki uzyskane dla zaimplementowanego algorytmu ewolucyjnego. Dla testów wykorzystano zagadnienia testowe z biblioteki QAPLIB-A.
EN
Quadratic Assignment Problem (QAP) generalizes several essential combinatorial problems: TSP, Generalized Graph Partitioning (GGP), Maximal Clique Problem (MCP), and many others. Because QAP belongs to NP-hard combinatorial problems, exact solution is possible only for small size (n < 25) QAP problems. To solve QAP problem of large size different kinds of approximate algorithms are used - among them the evolutionary algorithms based on evolution laws. Because of a great variety of properties of solution space, the quality of solution obtained with an evolutionary algorithm is different for various instances of QAP. In this paper we present methods of estimating properties of solution space of QAP. The analysis of those properties allows us to establish a set of optimal parameters of the implemented evolutionary algorithm. This task was realized on the basis of experimental analysis of our approximate algorithm. Examples from Quadratic Assignment Problem Library (called QAPLIB-A) were used in test cases.
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ć.