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

Znaleziono wyników: 7

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

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
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.
2
Content available remote Methods of using the Quadratic Assignment Problem solution
Kudelska I.
LogForum
|
2012
|
Vol. 8, no. 3
177--189
EN
Background: Quadratic assignment problem (QAP) is one of the most interesting of combinatorial optimization. Was presented by Koopman and Beckamanna in 1957, as a mathematical model of the location of indivisible tasks. This problem belongs to the class NP-hard issues. This forces the application to the solution already approximate methods for tasks with a small size (over 30). Even though it is much harder than other combinatorial optimization problems, it enjoys wide interest because it models the important class of decision problems. Material and methods: The discussion was an artificial intelligence tool that allowed to solve the problem QAP, among others are: genetic algorithms, Tabu Search, Branch and Bound. Results and conclusions: QAP did not arise directly as a model for certain actions, but he found its application in many areas. Examples of applications of the problem is: arrangement of buildings on the campus of the university, layout design of electronic components in systems with large scale integration (VLSI), design a hospital, arrangement of keys on the keyboard.
PL
Wstęp: Kwadratowy Problem Przydziału (QAP) jest jednym z najciekawszych zagadnień optymalizacji kombinatorycznej. Został przedstawiony przez Koopmana i Beckamanna w roku 1957, jako matematyczny model lokalizacji niepodzielnych zadań. Problem ten należy do klasy zagadnień NP.-trudnych. Wymusza to stosowanie do jego rozwiązania metod przybliżonych już dla zadań o niewielkim rozmiarze (powyżej 30). Mimo że jest ono znacznie trudniejsze niż inne zagadnienia optymalizacji kombinatorycznej, to cieszy się powszechnym zainteresowaniem, ponieważ modeluje ważną klasę problemów decyzyjnych. Metody: Dyskusji poddano narzędzia sztucznej inteligencji, które pozwoliły rozwiązać problem QAP, między innymi są to: algorytmy genetyczne, Tabu Search, Branch and Bound Wyniki i wnioski: Sam problem bezpośrednio nie powstał jako model pewnych działań, jednak znalazł on swoje zastosowanie w wielu dziedzinach. Przykładowymi zastosowaniami problemu jest: rozmieszczenie budynków na kampusie uczelnianym, projektowanie rozmieszczenia elementów elektronicznych w układach o wielkiej skali integracji (VLSI), projekt szpitala, rozmieszczenie klawiszy na klawiaturze.
3
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).
4
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.
5
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.
6
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.
7
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ć.