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

Znaleziono wyników: 24

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

help Ogranicz wyniki do:
first rewind previous Strona / 2 next fast forward last
1
Content available Tabu search for the RNA partial degradation problem
Rybarczyk A., Hertz A., Kasprzak M., Blazewicz J.
International Journal of Applied Mathematics and Computer Science
|
2017
|
Vol. 27, no. 2
401--415
EN
In recent years, a growing interest has been observed in research on RNA (ribonucleic acid), primarily due to the discovery of the role of RNA molecules in biological systems. They not only serve as templates in protein synthesis or as adapters in the translation process, but also influence and are involved in the regulation of gene expression. The RNA degradation process is now heavily studied as a potential source of such riboregulators. In this paper, we consider the so-called RNA partial degradation problem (RNA PDP). By solving this combinatorial problem, one can reconstruct a given RNA molecule, having as input the results of the biochemical analysis of its degradation, which possibly contain errors (false negatives or false positives). From the computational point of view the RNA PDP is strongly NP-hard. Hence, there is a need for developing algorithms that construct good suboptimal solutions. We propose a heuristic approach, in which two tabu search algorithms cooperate, in order to reconstruct an RNA molecule. Computational tests clearly demonstrate that the proposed approach fits well the biological problem and allows to achieve near-optimal results. The algorithm is freely available at http://www.cs.put.poznan.pl/arybarczyk/tabusearch.php.
2
Content available A support vector machine with the tabu search algorithm for freeway incident detection
Yao B., Hu P., Zhang M., Jin M.
International Journal of Applied Mathematics and Computer Science
|
2014
|
Vol. 24, no. 2
397--404
EN
Automated Incident Detection (AID) is an important part of Advanced Traffic Management and Information Systems (ATMISs). An automated incident detection system can effectively provide information on an incident, which can help initiate the required measure to reduce the influence of the incident. To accurately detect incidents in expressways, a Support Vector Machine (SVM) is used in this paper. Since the selection of optimal parameters for the SVM can improve prediction accuracy, the tabu search algorithm is employed to optimize the SVM parameters. The proposed model is evaluated with data for two freeways in China. The results show that the tabu search algorithm can effectively provide better parameter values for the SVM, and SVM models outperform Artificial Neural Networks (ANNs) in freeway incident detection.
3
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.
4
Content available Weryfikacja poprawności działania algorytmu tabu search w elastycznym modelu szeregowania zadań w systemach pomiarowo - sterujących
Powroźnik P.
Pomiary Automatyka Kontrola
|
2010
|
R. 56, nr 11
1345-1347
PL
W artykule przedstawiono ideę zastosowania algorytmu tabu search do wyznaczenia okresu zadań w elastycznym modelu szeregowania zadań. Wyniki przeprowadzonych symulacji dowodzą przydatność algorytmu w doborze parametrów czasowych w elastycznym modelu szeregowania zadań. Rozdział pierwszy zawiera tło zastosowania teorii szeregowania zadań w systemach pomiarowo - sterujących. Rozdział drugi wprowadza czytelnika do zastosowania elastycznego modelu szeregowania zadań w systemach pomiarowo - sterujących. Rozdział ten zawiera krótki przegląd literaturowy prezentowanej tematyki [1, 2, 3]. Rozdział trzeci przedstawia ideę zastosowania wybranego algorytmu heurystycznego tabu serach w elastycznym modelu szeregowania zadań w systemach pomiarowo - sterujących. Rysunek pierwszy przedstawia schemat blokowy szeregowania zadań przy zastosowaniu algorytmu tabu search. Rozdział czwarty zawiera wyniki z przeprowadzonych symulacji zastosowania algorytmu tabu search w elastycznym modelu szeregowania zadań w systemach pomiarowo - sterujących. Podsumowanie zawiera najważniejsze wnioski wynikające ze stosowania omawianego algorytmu w elastycznym modelu szeregowania zadań w systemach pomiarowo - sterujących.
EN
In this paper use of a tabu search algorithm for elastic task model scheduling is presented. The results of simulations confirm usefulness of this method for assigning the time parameters in elastic task model scheduling. In the first section, the background of application of task model scheduling to control and measurement systems is outlined. The second section deals with introduction to using the elastic task model scheduling for control and measurement systems. This section provides a brief literature review of the presented subjects [1, 2, 3]. The third section presents an idea of applying the selected tabu search heuristic algorithm to the elastic task model scheduling in control and measurement systems. The block diagram of the elastic task model scheduling with use of the tabu search algorithm is shown in Fig. 1. The fourth section contains the results of simulations carried out for the elastic task model scheduling with use of the tabu search algorithm in control and measurement systems. At the end there are presented the main conclusions drawn from using the tabu search algorithm for assigning the task time parameters in the elastic task model scheduling in control and measurement systems.
5
Content available Harmonogramowanie robót budowlanych z zastosowaniem algorytmu Tabu Search z rozmytymi czasami wykonania zadań
Rogalska M., Bożejko W., Hejducki Z., Wodecki M.
Przegląd Budowlany
|
2009
|
R. 80, nr 7-8
76-80
PL
Praca ta stanowi kontynuację studiów różnych autorów nad zagadnieniami związanymi z uwzględnieniem niepewności w harmonogramowaniu robót budowlanych. Jednym ze sposobów reprezentowania niepewności jest zastosowanie elementów teorii zbiorów rozmytych, umożliwiających oszacowanie czasów wykonania prac oraz cyklu realizacji kompleksu robót.
EN
This paper continues the authors' work on issues relating to taking account of uncertainties in the scheduling of construction works. One way of representing uncertainty is to use elements of the theory of fuzzy sets, which make it possible to estimate work completion times and the execution cycle for a comprehensive series of works.
6
Content available Zagadnienie przepływowe z ograniczeniami "bez magazynowania". Algorytm tabu search z multiruchami
Grabowski J., Pempera J.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2005
|
T. 9, z. 1-2
95-104
PL
Dla zagadnienia przepływowego z ograniczeniami "bez magazynowania" przedstawiono w pracy model grafowy, własności problemu oraz algorytm oparty na technice tabu search. W proponowanym algorytmie wykorzystano idee bloków zadań oraz zastosowano całkowicie nowe pojęcie nazywane multiruchem. Wysoką skuteczność algorytmu potwierdzają wyniki badań eksperymentalnych dokonane na literaturowych danych testowych, w których aż dla 96 instancji spośród 120 uzyskano nowe rozwiązania referencyjne.
EN
The paper deal with flow-shop scheduling problem with no store constrains and the makespan criterion. Some properties, models of the problem and algorithm based on the taboo search method have been presented and discussed. In the proposed algorithm, the blocks of jobs ideas and new mechanism called multimove are used. The high efficiency of proposed mechanism confirm the results of the computation experiment, where for 96 over 120 instances are obtained new references solution.
7
Content available remote Zagadnienie kolejnościowe przepływowe z ograniczoną dostępnością maszyn
Grabowski J., Pempera J.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2003
|
T. 7, z. 1-2
113-119
PL
W pracy przedstawiono klasyczne przepływowe zagadnienie szeregowania zadań z kryterium minimalizacji zakończenia wszystkich zadań, w którym maszyny są dostępne w określonych terminach czasowych. Przedstawiono model zagadnienia wykorzystujący elementy teorii grafów oraz zaproponowano algorytmy konstrukcyjne i lokalnego przeszukiwania. Algorytmy te były testowane na trudnych problemach zaczerpniętych z literatury. Uzyskane wyniki porównano z rezultatami algorytmów zaproponowanych przez Błażewicza.
EN
The paper deal with the classical flowshop scheduling problem with makespan criterion where machines for processing are available in given time intervals. There are presented the graph model and the constructive and local search heuristics. The algorithms are tested on difficult test problem taken from literature. The computational results are compared with the results given by the algorithms proposed by Blazewicz.
8
Content available remote Warianty algorytmu Tabu Search w zastosowaniu do układania harmonogramów zajęć szkolnych
Piwakowski K., Szyfelbein D.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2003
|
T. 7, z. 1-2
229-236
PL
W niniejszej pracy przedstawiono warianty adaptacji przeszukiwania tabu wraz z wynikami eksperymentów obliczeniowych do układania szkolnych harmonogramów zajęć. W modelu teoretycznym uwzględniono zarówno ograniczenia krytyczne, np. konflikty czasowe uczestników zajęć (nauczyciele i uczniowie) oraz brak przerw w zajęciach (eliminacja okienek) wybranych uczestników, jak również niekrytyczne składniki funkcji celu, np. równomierne rozłożenie zajęć w tygodniu i możliwie mała rozpiętość czasowa harmonogramu w każdym dniu.
EN
In this paper we present variants of tabu search implementation for computing school timetables together with computational results. In the theoretical model critical conditions as for example participant's time conflicts and consecutive class's schedule, as well as not critical conditions as for example even distribution of lessons and short span in each day are considered.
9
Content available remote A new local search optimization algorithm for the job-shop problem
Grabowski J., Wodecki M.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2003
|
T. 7, z. 1-2
121-128
EN
This paper deals with a classic job-shop scheduling problem with makespan criterion. We present some new theoretical properties of the problem associated with the blocks, moves and neighbourhood structure, and algorithm based on a tabu search approach. Computational experiments are given and compared with the results yielded by the best algorithms discussed in the literature. These results show that the algorithm proposed solves the job-shop instances with high accuracy in a very short time.
PL
W referacie przedstawimy algorytm tabu oparty na idei bloków z drogi krytycznej, dla rozwiązywania ogólnego problemu szeregowania (ang. job-shop problem). Szacowanie wartości funkcji celu rozwiązań z otoczenia (bez konieczności dokładnego ich liczenia), znacznie przyspiesza zbieżność i skraca czas działania algorytmu. Przedstawimy pewne metody (perturbacje) pozwalające na bardzo szybką zmianę badanych obszarów zbioru rozwiązań dopuszczalnych oraz nowy sposób realizacji listy tabu, który zapobiega powstawaniu cykli w algorytmie (generowaniu tych samych rozwiązań po pewnej liczbie kroków algorytmu). Przeprowdzone eksperymenty obliczeniowe wskazują jednoznacznie, że wyżej przedstawione idee znacznie przyspieszają oraz poprawiają wyniki algorytmu.
10
Metaheurystyka tabu w optymalizacji wielorzędowego rozmieszczenia maszyn
Homel T., Wala K.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2002
|
z. 136
85-96
PL
W artykule rozważany jest problem wielorzędowego rozmieszczenia maszyn w hali produkcyjnej. Zaprezentowano oryginalny model, gdzie rozwiązanie jest sformalizowane w postaci permutacji numerów maszyn oraz zaproponowano algorytmy oparte na metaheurystyce tabu. Przedstawiono wyniki badań komputerowych, które ilustrują przydatność modelu i algorytmów dla praktyki projektowej.
EN
In this paper the many-row machine layout problem in manufacturing cell is considered. We present the original model of the machine layout problem of permutation optimization type and propose algorithms based on tabu search metaheuristic. Results of computing experiments illustrate the use of the proposed model and algorithms for the real project problems.
11
Algorytmy tabu Search dla problemów szeregowania zadań na jednej maszynie z ograniczoną dostępnością
Formanowicz P.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2002
|
z. 134
115-126
PL
W pracy zaprezentowano algorytmy oparte na metodzie tabu dla problemów szeregowania zadań niepodzielnych na jednej maszynie z okresami niedostępności i kryterium minimalizacji długości uszeregowania, sumy czasów zakończeni zadań oraz maksymalnego opóźnienia. Jakość zaprezentowanych algorytmów przebadano w obszernym eksperymencie obliczeniowym.
EN
In the paper algorithms based on tabu search method for scheduling non-preemptable tasks on a single machine with limited availability have been presented. The criterion functions to be minimized are the makespan, the total completion time, and the maximum lateness. The quality of the algorithms has been examined in an extensive computational experiment.
12
Algorytm tabu search ze zmiennym czasem pamięci krótkoterminowej
Chmiel W.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2002
|
z. 136
21-32
PL
W pracy przedstawiono wyniki badań eksperymentalnych procesu optymalizacji zagadnienia przydziału z kwadratową funkcją celu realizowanego za pomocą algorytmu ewolucyjnego, w którym zastosowano operator oparty na Tabu Search. Zastosowano w nim zmienny czas pamięci krótkoterminowej, zależny od wartości oczekiwanej częściowego rozwiązania.
EN
This paper presents results of experimental examination of optimization process realized on the example of quadratic assignment problem, with the aid of evolution algorithm, where an operator based on Tabu Search is used. This algorithm uses flexible time of short-memory depending on conditional expectation of fitness function for partial solution.
13
Algorytm tabu dla problemu gniazdowego z operacjami wielomaszynowymi nierównocześnie wykorzystującymi maszyny
Makuchowski M., Nowicki E.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2002
|
z. 134
287-297
PL
W pracy rozważa się problem gniazdowy z operacjami wielomaszynowymi, nierównocześnie wykorzystującymi maszyny. Przedstawia się jego model permutacyjno-grafowy. Następnie prezentuje się algorytm przybliżony typu tabu zwracając szczególną uwagę na definicję sąsiedztwa oraz atrybuty zapisywane na listę tabu. Przeprowadza się badania eksperymentalne zaproponowanego algorytmu na przykładach testowych powszechnie stosowanych w literaturze.
EN
The paper discusses the job shop multimachine operations problem with non-simultaneously used machines. Its permutation-graph model is shown. The algorithm based on a tabu search technique with a specific neighborhood definition and suitable attributes written to taboo list is presented. Moreover, the algorithm is examined on well-known literature examples.
14
Algorytm tabu dla problemu gniazdowego z czasami transportu
Nowicki E.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2002
|
z. 134
327-337
PL
W pracy przedstawia się szybki aproksymacyjny algorytm, minimalizujący moment wykonania wszystkich zadań, dla problemu gniazdowego z transportem. Algorytm bazuje na technice tabu ze specyficzną definicją sąsiedztwa. Przeprowadzone eksperymenty obliczeniowe pokazują, że algorytm znajduje mniejsze wartości kryterium niż najlepsze aktualnie algorytmy aproksymacyjne.
EN
A fast approximation algorithm for a problem of finding the minimum makespan in a job shop with transportation times is presented. The algorithm is based on a tabu search technique with a specific neighborhood definition. Computational experiments show that the algorithm finds shorter makespans that the best approximations approaches.
15
Content available remote Nowy algorytm lokalnej optymalizacji dla zagadnienia kolejnościowego przepływowego
Bożejko W., Grabowski J., Pempera J.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2001
|
T. 5, z. 1/2
77-85
PL
W pracy przedstawiono klasyczne przepływowe zagadnienie szeregowania z kryterium minimalizacji terminu zakończenia wykonywania wszystkich zadań. Przedstawiono nowe własności zagadnienia oraz nowy rodzaj ruchu, którego wykonanie przesuwa jednocześnie co najmniej jedno zadanie w danej permutacji. Ruchy tego rodzaju mogą być stosowane w dowolnych algorytmach lokalnej optymalizacji szeregowania zadań. W niniejszej pracy zastosowano je do algorytmu opartego na technice tabu search. Przeprowadzono eksperymenty obliczeniowe a uzyskane rezultaty porównano z wynikami aktualnie najlepszych na świecie algorytmów opracowanych przez Nowickiego i Smutnickiego oraz Grabowskiego i Pemperę.
EN
The paper deals with the classic flow-shop scheduling problem with the makespan criterion. There are presented and discussed some new properties associated with the blocks and new definition of the move, by using of which at least one job is moved in a given permutation. This move can be applied in any local search algorithms. The algorithm based on tabu search approach is presented. Computational experiments are provided and compared with the results given by the best algorithms proposed by Nowicki & Smutnicki and Grabowski & Pempera.
16
Zastosowanie techniki Tabu do harmonogramowania elastycznych gniazd produkcyjnych z czasami transportu i przezbrojeń
Nowicki E.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2000
|
z. 129
295-304
PL
W pracy przedstawia się szybki aproksymacyjny algorytm, minimalizujący moment wykonania wszystkich zadań, dla problemu gniazdowego z maszynami równoległymi, czasami transportu i czasami przezbrojeń. Algorytm jest oparty na technice Tabu ze specyficzną definicją sąsiedztwa. Specjalna metoda implementacji istotnie zwiększa prędkość algorytmu.
EN
A fast approximation algorithm for a problem of finding the minimum makespan in a job shop with parallel machines, transport times and setup times is presented. The algorithm is based on a Tabu search technique with a specific neighborhood definition. A special method of implementation increases the speed of the algorithm significantly.
17
Zagadnienie szeregowania wyrobów w przepływowych procesach montażowych. Algorytm ewolucyjny
Grabowski J., Marchewka A.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2000
|
z. 129
83-90
PL
W pracy przedstawia się zagadnienie szeregowania wyrobów w przepływowym procesie produkcyjnym. Proces montażu oraz proces produkcyjny są rozpatrywane jednocześnie. Jednoczesne rozpatrywanie obu procesów wymusza zamodelowanie struktury wyrobu za pomocą grafu - drzewa.
EN
This paper deals with a algorithm for the flow-shop scheduling problem where the jobs are presented by a graph-tree. Such problem appears in a production, when several elements are assembled into one job.
18
Porównanie technik aproksymacyjnych: tabu search, ewolucyjnej i sieci neuronowej na przykładzie problemu szeregowania zadań z zasobami na pojedynczej maszynie
Janiak A., Marek M.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2000
|
z. 129
157-166
PL
W pracy porównano trzy algorytmy metaheurystyczne: tabu search, genetyczny, sieć neuronową dla problemu szeregowania zadań na jednej maszynie z zadanymi terminami dostępności i czasami realizacji zależnymi od ilości przydzielonego zasobu. Przyjętym kryterium jest minimalizacja maksymalnej nietenninowości. Podano wyniki przeprowadzonych eksperymentów numerycznych.
EN
The paper deals with a single machine scheduling problem with given release dates and processing times dependent on resources. Considered criterion is the maximum lateness minimization. To solve the problem three metaheuristic algorithms are presented and compared.
19
Nowe algorytmy tabu search dla szeregowania zadań z kryterium minimalno kosztowym
Grabowski J., Pempera J.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2000
|
z. 129
91-99
PL
W niniejszej pracy przedstawia się szereg algorytmów opartych na technice przeszukiwania z zabronieniami (tabu search) dla zagadnienia szeregowania zadań na jednej maszynie z kryterium minimalizacji sumy kosztów zadań wykonywanych nieterminowo. Zaprezentowano szereg nowych technik realizacji zabronienia (tabu) ruchów podczas przeszukiwania rozwiązań sąsiednich. Przedstawiono wyniki obliczeniowe oraz rezultaty porównań algorytmów.
EN
This paper presents a collection of heuristics for the single machine total weighted tardiness problem. The algorithms considered are based on the insert approach and different sophisticated tabu techniques. The computation results and discussions of the performance of algorithms are presented.
20
Content available remote Nowy algorytm tabu search dla zagadnienia kolejnościowego przepływowego
Grabowski J., Pempera J.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
1999
|
T. 3, z. 1
125-133
PL
W pracy przedstawiono klasyczne przepływowe zagadnienie szeregowania z kryterium minimalizacji terminu zakończenia wykonywania wszystkich zadań. Przedstawiono nowe własności zagadnienia, które zastosowane do algorytmu opartego na technice tabu search doprowadziły do istotnego ograniczenia zbioru rozwiązań sąsiednich. Przeprowadzono eksperymenty obliczeniowe a uzyskane rezultaty porównano z wynikami aktualnie najlepszego na świecie algorytmu opracowanego przez Nowickiego i Smutnickiego.
EN
The paper deal with the classic flow-shop scheduling problem with the makespan criterion. There are presented and discussed some new properties associated with the blocks. These properties allow us to further significant reduction of the neighbourhood sizes, which can be applied in local search algorithms. The algorithm based on tabu search approach is presented. Computational experiments (up to 500, jobs and 20 machines) are provided and compared with the results given by the best algorithm proposed by Nowicki and Smutnicki.
first rewind previous Strona / 2 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ć.