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

Znaleziono wyników: 21

Liczba wyników na stronie
first rewind previous Strona / 2 next fast forward last
Wyniki wyszukiwania
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 2 next fast forward last
1
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.
2
Content available Business processes in a distributed surveillance system integrated through workflow
Szwed P., Chmiel W., Jędrusik S., Kadłuczka P.
Automatyka / Automatics
|
2013
|
Vol. 17, no. 1
115--126
EN
SIMPOZ project aims at building a highly configurable system for suryeillance of publie areas and objeets of a speeial importanee based on the analysis of digital images. Distributed naturę and po-tential diyersity of monitoring features, a large number of alarm signals fed by yarious sensors, the need to ensure a flexible event flow management and tailored to needs emergency response processes were motiyations to utilize workflow as a management and integration layer. Implementation of workflow processes was preceded by business modeling with ArchiMate language. The presented models of business processes reflect the specificity and characteristies of surveillance systems: reactiye character, event driven control and a large number of asynchronous data flows. Lessons learned indicate, that ArchiMate models in spite of the smaller set of dedicated behayioral constructs with respect to for example BPMN, after adopting certain modeling conyentions, allow to reach high level of expressiveness.
PL
Projekt SIMPOZ ma na celu budowę elastycznego systemu nadzoru przestrzeni publicznej i obiektów specjalnego znaczenia na podstawie analizy cyfrowych obrazów. Motywacją do wykorzystania w systemie przepływów pracy jest duże rozproszenie, potencjalna różnorodność monitorowanych własności i informacji o alarmach oraz potrzeba zapewnienia elastycznego zarządzania przepływem zdarzeń. Implementacja procesów przepływu pracy została poprzedzona etapem modelowania biznesowego, w którym wykorzystano język ArchiMate. Przedstawione modele procesów biznesowych odpowiadają specyfice i własnościom systemów nadzoru: mają reaktywny charakter, są sterowanie poprzez zdarzenia oraz obejmują dużą liczbę asynchronicznych przepływów danych. Doświadczenia wskazują, że język ArchiMate, mimo mniejszego zestawu konstrukcji służących do opisu zachowania niż np. notacja BPMN, po przyjęciu pewnych konwencji modelowania, pozwala na osiągnięcie wysokiego poziomu ekspresywności.
3
Content available System inteligentnego monitoringu przestrzeni i obiektów szczególnego znaczenia SIMPOZ
Bubliński Z., Chmiel W., Jabłoński M., Kadłuczka P., Kryjak T., Mikrut Z., Pawlik P., Tadeusiewicz R.
Pomiary Automatyka Robotyka
|
2011
|
R. 15, nr 12
69-76
PL
Celem projektu realizowanego w Katedrze Automatyki jest stworzenie wydajnego narzędzia wspomagającego proces nadzoru przestrzeni i obiektów publicznych, w oparciu o automatyczną analizę obrazów cyfrowych. Przy założeniu szeroko pojętej ogólności zagrożeń, które mają być wykrywane, konstrukcja programu do automatycznego wspomagania nadzoru nie jest zagadnieniem trywialnym, ze względu na nieprzewidywalną wielowariantowość obserwowanych sytuacji. Opracowanie efektywnego systemu wymaga rozwiązania szeregu zagadnień, skomplikowanych od strony koncepcyjnej i trudnych w realizacji algorytmicznej. Zadaniem inteligentnego systemu wspomagania monitoringu jest wskazanie obsłudze systemu sytuacji potencjalnie podejrzanych z punktu widzenia przyjętych kryteriów bezpieczeństwa. W celu przezwyciężenia pojawiających się tu trudności tworzone są algorytmy, których działanie opiera się nie tylko na przetwarzaniu i analizie obrazów, ale także na próbach automatycznego rozumienia znaczenia obserwowanych scen, czyli imitowanych komputerowo elementach ludzkiego postrzegania i toku myślenia, związanego z ocenianym obrazem.
EN
The aim of the project realized in the Department of Automatics is to create an efficient tool to support the process of surveillance of public spaces and buildings based on automated image analysis. Assuming a wide scope of applications of developed tools, the design of the program to automatically support surveillance tasks is not a trivial problem, due to unforeseen circumstances and non-predicted situation. Developing an effective surveillance system requires addressing a number of issues, that are conceptually complex and require research and implementation of advanced algorithms. The goal of an intelligent monitoring system is to identify potentially suspicious circumstances according to assumed safety criteria. In order to overcome arising here difficulties there are created algorithms whose operation is based not only on processing and analyzing images, but also on imitating a human perception and understanding of the analyzed images.
4
Content available Zastosowanie algorytmów rojowych w rozwiązywaniu zagadnień permutacyjnych
Chmiel W., Kadłuczka P., Packanik G.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2011
|
T. 15, z. 2
117-126
PL
W artykule przedstawiono wyniki badań nad zastosowaniem algorytmów rojowych w optymalizacji zagadnienia szeregowania zadań, jako przykładu AP-trudnego zagadnienia optymalizacyjnego. W oparciu o instancje testowe dla zagadnienia szeregowania zadań zaproponowane przez E. Taillarda, przeprowadzono eksperymenty obliczeniowe, porównując wyniki otrzymywane przez algorytm ptasi oraz algorytm pszczeli. Przebadano także wpływ implementacji poszczególnych elementów algorytmów, takich jak liczba, dokładność i sposób przeszukiwania otoczenia rozwiązań obiecujących, na uzyskiwane wyniki optymalizacji. Pozwoliło to na sformowanie ogólnych wniosków dotyczących własności obu algorytmów.
EN
The objective of this paper is to examine the most important properties of a multi-population genetic algorithm. These elements include: connection topology, migration size, migration interval and a method for migrant selection. A short review of the existing papers on multi-population algorithms is presented. A new diversity measure that applies to permutation encoding is introduced. The proposed measure has proved effective in helping to retain balance between population diversity and convergence. A multi-population genetic algorithm, with different parameters like type of topology, migration interval, migration size and selection method was tested against several different test instances of traveling salesman problem, that belongs to the NP-hard permutational problem class.
5
Content available Efektywność wielopopulacyjnego algorytmu ewolucyjnego dla zagadnień permutacyjnych
Filipowicz B., Chmiel W., Dudek M., Kadłuczka P.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2011
|
T. 15, z. 2
147-158
PL
W artykule przedstawiono wyniki badań najistotniejszych elementów wielopopulacyjnego algorytmu ewolucyjnego. W zastosowanym modelu wyspowym należą do nich: topologia połączeń, rozmiar i częstotliwość migracji oraz metoda selekcji migrantów. Zaproponowana miara różnorodności populacji może być wykorzystywana dla szerokiej klasy zagadnień permutacyjnych, których przykładem jest rozważane zagadnienie komiwojażera (TSP). Badania eksperymentalne przeprowadzono dla standardowych zagadnień testowych zaczerpniętych z biblioteki TSPLib95.
EN
The objective of this study is to examine the most important traits of a multi-population genetic algorithm. These elements include: connection topology, migration size, migration interval and migrant seleetion method. A review of the existing papers on multi-population algorithms is presented. A new diversity measure that applies to permutation encoding is introduced. It has proved effective in helping to retain balance between population diversity and convergence. For each trait, several algorithm configurations have been tested. Every configuration was tested against 25 different test instances, which were derived from the TSPLib95 library. Test results showed that, among the tested parameters, the most important was topology. Of the eleven topologies, a circular (ring) topology consisting of 16 islands obtained the best results. Varying of migration interval showed little correlation with the solution quality, but it did affect the convergence time. In comparison to other parameters, migration size exerts a relatively strong influence on performance. Moreover, a medium migration size proved to be reasonable. Among migrant selection methods, random selection outperformed these methods that exert selective pressure.
6
Content available Nadzorowana kategoryzacja tekstów angielskojęzycznych
Chmiel W., Kadłuczka P., Jędrusik S.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2010
|
T. 14, z. 3/2
811-826
PL
Klasyfikacja tekstów jest szybko rozwijającą się dziedziną, korzystającą zarówno z metod sztucznej inteligencji, jak i metod wyszukiwania i udostępniania informacji (IR). W obecnym czasie, duża liczba praktycznych zastosowań tego zagadnienia wiąże się np. z sortowaniem tekstów naukowych, technicznych, medycznych, patentowych, wypełnianiem hierarchicznych katalogów sieciowych, selektywnym udostępniałem dokumentów, filtracją spamu. Zagadnienie kategoryzacji tekstów, ze względu na dużą liczbę atrybutów opisujących dokumenty, duży rozmiar zbioru uczącego, a także zależności pomiędzy atrybutami, jest wyzwaniem dla współczesnych metod badawczych. W pracy przedstawiono algorytm klasyfikacji tekstu, bazujący na metodzie centroidów oraz drzewie decyzyjnym. Zaprezentowano rozbudowane badania proponowanego algorytmu.
EN
Text classification is a growing area of research at the intersection of information retrieval (IR) and machine learning. The goal of text classification systems is to attach automatically labels to previously unseen electronic documents. These labels may indicate topics discussed in the document, the relevance of the document for a given user, the mailbox or newsgroup into which the document should be filed. Text categorization presents unique challenges due to the large number of attributes present in the data set, large number of training samples, and attribute dependencies. In this paper we present a supervised classification algorithm based on centroids method and decision trees. This paper presents comprehensive computational experiments examining the efficiency of proposed classification algorithms.
7
Content available Kontur wypukły w trójwymiarowym zagadnieniu pakowania
Filipowicz B., Chmiel W., Kadłuczka P., Wala K.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2010
|
T. 14, z. 3/2
867-883
PL
W pracy przedstawiono uniwersalną metodę opisu konturu i zbioru punktów wstawienia, która może być stosowana dla szerokiej klasy zagadnień pakowania paczek do kontenera w ujęciu dwu- i trójwymiarowym, przy zadanym punkcie "centralnym". Punkt ten określa miejsce wstawienia pierwszej paczki i daje możliwość stworzenia szeregu algorytmów zachłannych działających odmiennie od tych, które rozpoczynają pakowanie od lewego, dolnego, tylnego rogu kontenera. Pozwala to w trakcie załadunku rozwiązywać dodatkowo istotny problem wyważenia kontenera.
EN
The paper presents an universal method for describing of contour and insertion points that can be applied do wide class of packing problems including two and three dimensional problems with a fixed central point. The central point speeifies a place of insertion of a first package. This gives the opportunity to create several greedy algorithms acting differently from the standard algorithm, which starts packing from the left, bottom, rear corner of the container. Moreover it allows to solve container balancing problem.
8
Content available Algorytmy heurystyczne w trójwymiarowym zagadnieniu pakowania
Chmiel W., Kadłuczka P., Wala K., Jędrusik S.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2010
|
T. 14, z. 3/2
827-840
PL
W artykule zaprezentowano zagadnienie trójwymiarowego pakowania kontenera paczkami o regularnych wymiarach, ze współczynnikiem wypełnienia kontenera jako kryterium oceny. Przebadano zarówno procedury konstrukcyjne, jak i algorytm popraw bazujący na algorytmie symulowanego wyżarzania. Stosowane w algorytmach rozwiązanie problemu pakowania jest reprezentowane w postaci czterech sekwencji liczb. W przedstawionych wynikach eksperymentów wykorzystano instancje testowe zawierające do 400 paczek.
EN
In this paper we examine the problem of optimal packing of a three-dimensional container with rectangular boxes such that the volume of the packed boxes is maximized. We investigate fast constructive procedures and an approximation algorithm based on simulated annealing. In all developed algorithms solutions are represented in a form of four sequences. Extensive computational results involving various test instances up to 400 boxes, are presented.
9
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).
10
Content available Strategia przetwarzania wiedzy w wielopopulacyjnym algorytmie ewolucyjnym
Kadłuczka P., Chmiel W., Piwowarczyk J.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2009
|
T. 13, z. 2
325-331
PL
Artykuł prezentuje koncepcję wielopopulacyjnego, samoadaptacyjnego algorytmu ewolucyjnego, wykorzystującego technologię inteligentnych agentów. Algorytm ten zastosowano dla zagadnienia komiwojażera, należącego do klasy problemów permutacyjnych NP-trudnych. Współbieżna realizacja wielu algorytmów ewolucyjnych pozwala na ich komunikację, mającą na celu udostępnienie informacji dotyczącej dotychczasowego przebiegu obliczeń, uzyskanych rozwiązań oraz oceny aktualnie wykorzystywanych elementów konstrukcyjnych algorytmu. Zróżnicowana strategia przetwarzania i stosowania wiedzy prowadzi do zróżnicowanej efektywności algorytmów i całego systemu.
EN
The paper presents intelligent agent approach to multi-population evolutionary algorithm with self-adaptation. The algorithm was used to solve traveling salesman problem that belongs to the NP-hard permutational problem class, one of the most popular optimization discrete problem. Concurrent system realization allows to exchange data, like solutions, results and parameter estimations between algorithms. The possibility to improve the algorithm and system efficiency is based on the strategy and knowledge processing diversification.
11
Wielofazowa metoda różnicowania populacji w algorytmie ewolucyjnym
Chmiel W., Kadłuczka P.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2008
|
z. 151
195-202
PL
Zastosowana w algorytmie ewolucyjnym koncepcja zmiennej w czasie strategii sukcesji ma na celu sterowanie zbieżnością algorytmu. Początkowa faza obliczeń różnicuje w większym stopniu rozwiązania w populacji niż fazy późniejsze. Prawdopodobieństwo wstawienia nowo wygenerowanego rozwiązania do populacji, zmienne w kolejnych etapach, jest uzależnione od wartości funkcji przystosowania oraz od pewnej funkcji rozkładu prawdopodobieństwa. Jako zagadnienie testowe dla zaproponowanego algorytmu przyjęto NP-trudne kwadratowe zagadnienie przydziału.
EN
This paper investigates a new advanced evolutionary algorithm for optimization of permutation problems. Implementation of varying in time strategy of succession in evolution algorithms enables controlling the population diversification. In early phases of optimization the diversification of population is greater than the later ones. During all phases the probability of adding solution to population depends on the solution fitness function and certain probability density function. The experiments were performed for standard test problems of quadratic assignment problems (QAP).
12
Content available Testowanie wsteczne modeli wartości narażonej na stratę
Jędrusik S., Paliński A., Chmiel W., Kadłuczka P.
Ekonomia Menedżerska
|
2007
|
nr 1
175-182
EN
Backtesting is an inherent element of every Risk Management System based on VaR methodology. The term "backtesting" is used to describe various statistical test designed for evaluation of VaR models quality. The results of these tests are one of the most frequently used selection criterion for VaR models. In this paper we present the results of applying Kupiec and Christoffersen tests to portfolios from Polish financial market. In the first section we present the idea of VaR. Next is devoted to the mathematical foundations of Kupiec and Christoffersen tests. The results of applying these tests to two VaR models (Random Walk and GARCH) are presented in the subsection 3.
13
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.
14
Content available Współbieżny algorytm ewolucyjny wykorzystujący mechanizm samoadaptacji
Kadłuczka P., Piwowarczyk J., Chmiel W.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2007
|
T. 11, z. 1-2
161-170
PL
W artykule zaprezentowano koncepcję wielopopulacyjnego algorytmu ewolucyjnego realizującą mechanizm samoadaptacji, wykorzystujący technologię inteligentnych agentów. Technologia ta, wkraczająca w obszary inżynierii oprogramowania, obliczeń równoległych, systemów rozproszonych i sztucznej inteligencji, znajduje coraz szersze zastosowanie. Wykorzystanie jej w konstrukcji hybrydowych metod przybliżonych należy do aktualnego nurtu badań naukowych. Współbieżna realizacja wielu algorytmów ewolucyjnych pozwala na ich wzajemną komunikację, w celu udostępnienia informacji dotyczącej nie tylko uzyskanych rozwiązań, ale oceny aktualnie wykorzystywanych elementów konstrukcyjnych algorytmu, wartości parametrów oraz dodatkowych parametrów, charakteryzujących historię przebiegu i eksploracji przestrzeni rozwiązań. W oparciu o uzyskaną informację algorytmy (wątki) mogą w zróżnicowany sposób zmodyfikować swoje dotychczasowe działanie.
EN
The paper presents intelligent agent approach to multipopulation evolutionary algorithm with self-adaptation. The approach is based on different areas as software engineering, parallel and distributed systems and artificial intelligence. This technology belongs to up to date researches in the construction of hybrid approximate methods.
15
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).
16
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.
17
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.
18
Content available remote Algorytm memetyczny do rozwiązywania uogólnionego zagadnienia podziału grafu
Kadłuczka P.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2001
|
T. 5, z. 1/2
311-318
PL
W artykule zaprezentowano algorytm memetyczny (ang. memetic algorithm - MA) dla uogólnionego zagadnienia podziału grafu (GGP). MA jest heurystyką do rozwiązywania kombinatorycznych problemów optymalizacyjnych, bazującą na populacji, bliską algorytmom genetycznym (GAs). Inspirację zaczerpnięto z pojęcia meme, które określa jednostkę informacji powielającą się samoistnie przy wymianie idei między ludźmi. MA odzwierciedla kulturową ewolucję, w odróżnieniu od biologicznej. Memetyczna ewolucja może występować w kombinacji z algorytmami genetycznymi, strategiami przeszukiwania lokalnego, takimi jak przeszukiwanie lokalnego sąsiedztwa lub symulowane wyżarzanie. Metoda ta okazała się efektywnym podejściem do rozwiązywania różnych problemów optymalizacji kombinatorycznej : TSP, QAP, NK Landscapes i innych. W artykule podjęto próbę zaadaptowania tej metody łącznie z algorytmem genetycznym dla uogólnionego zagadnienia podziału grafu. GGP polega na podziale zbioru wierzchołków nieskierowanego, ważonego grafu na m. rozłącznych podzbiorów, tzw. punktów skupienia, w celu optymalizacji funkcji celu, przy równoczesnym ograniczeniu ich rozmiaru. Zagadnienie to jest z jednej strony NP--trudne, a z drugiej modeluje wiele ważnych praktycznych sytuacji decyzyjnych (np. problemy przechowywania i przetwarzania dużych programów komputerowych w rozproszonych systemach obliczeniowych lub systemach wieloprocesorowych). Na wstępie przedstawiono model matematyczny zagadnienia, będącego uogólnieniem klasycznego zagadnienia podziału grafu (GP). Kolejny rozdział zawiera opis algorytmu memetycznego, użytych mechanizmów włączonych do bazowego algorytmu genetycznego. Następnie przedstawiono wyniki badań komputerowych powyższego algorytmu dla zadań testowych w zestawieniu z wynikami uzyskanymi za pomocą algorytmu genetycznego i hybrydowego oraz wynikające z nich wnioski.
EN
The paper considers the memtic algorithm (MA) for generalized graph partitioning problem (GGP). MAs are population based heuristic for combinatorial optimization problems closely related to genetic algorithms (GAs). They are inspired by the notion of a meme, defined as a unit of information that reproduces itself when people exchange ideas. Thus, memetic algorithms resemble the cultural evolution instead of the biological evolution. Memetic evolution can be combined with GAs, local search approaches as: the neighbour search or simulated annealing. The method was proved to be efficient while solving various combinatorial optimisation problems: TSP, QAP, NK Landscapes and other. This paper presents a new algoritm combining the MA and GA aproaches that is used for solving a generalized graph partitioning problem. GPP consists in partitioning the nodes of a weighted graph into m disjoint subsets of bounded size, such that an objective function connected with the weights of the graph edges is maximized. This a NP-hard problem that models many important practical decision problems (e.g. processing large computer programs in distributed or multiprocesor computing systems). The paper is organized as folows: first section defines the mathematiac model of the problem beinng the generalisation of the classical graph partitioning problem. Next sections describe the memetic algorithm and the mechanisms introduced to basic GA. Final section present the results of computer experiments and compares them with the results obtained by application of genetic and hybrid algorithms.
19
Zastosowanie transformacji permutacji do przestrzeni wektorowej w algorytmach ewolucyjnych
Chmiel W., Kadłuczka P.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2000
|
z. 131
37-47
PL
W pracy przedstawiono wyniki badań eksperymentalnych procesu optymalizacji realizowanego za pomocą algorytmu ewolucyjnego dla testowego zagadnienia przydziału z kwadratową funkcją celu. Opierając się na zagadnieniu porównano algorytm ewolucyjny korzystający z metod transformujących zagadnienie permutacyjne do postaci kombinacji z działającymi wyłącznie na permutacjach.
EN
This paper presents results of experimental examination of optimization process realized with the aid of genetic algorithm on the test example of quadratic assignment problem. The investigated genetic algorithm realizes original genetic search process. In this algorithm we introduce technique normally used to optimize objective functions of any kind in Cartesian space where derivatives are not available or impossible to determine.
20
Content available remote Algorytm hybrydowy z długoterminową pamięcią częstotliwościową
Chmiel W., Kadłuczka P.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
1999
|
T. 3, z. 1
59-70
PL
Artykuł prezentuje rezultaty prac nad algorytmami przybliżonymi realizującymi proces genetyczny poszukiwania, dostarczającymi rozwiązań dla zagadnień, w których zastosowanie metod dokładnych nie jest możliwe, ze względu na liczność przestrzeni rozwiązań. Zaprezentowany w artykule hybrydowy algorytm realizuje oryginalną metodę genetycznego przeszukiwania przestrzeni rozwiązań wykorzystującą "restart" algorytmu - w oparciu o tzw. długoterminową pamięć częstotliwościową. Został on stworzony dla możliwie najszerszej klasy problemów dyskretnych, należących do klasy zagadnień NP-trudnych (kwadratowy problem przypisania, zagadnienie kolorowania grafu, harmo-nogramowania, komiwojażera, podziału grafu oraz wiele innych ważnych zagadnień optymalizacji kombinatorycznej). Zastosowane ogólne metody różnicowania i intensyfikacji procesu poszukiwania rozwiązania pozwalają na lepsze przeszukiwanie przestrzeni rozwiązań, niezależnie od typu rozpatrywanego zagadnienia. Mechanizmy te, dzięki zastosowaniu pamięci długoterminowej, pozwalają zapobiec przedwczesnej zbieżności algorytmu do ekstremów lokalnych. Algorytm został przetestowany dla przykładowych zadań oraz wybranych zagadnień kombinatorycznych.
EN
The paper presents the results of computer investigation of approximate algorithm, performing evolutionary search process for problems computationally intractable with regard to size of solution space. The proposed hybrid algorithm implements a new original method of genetic search of solution space which consist in restarting the search algorithm and the use of long term frequently memory. This algorithm can be adapted to the wide instances of combinatorial optimization problems including the travelling salesman problem, quadratic assignments problem, graph coloring, production scheduling problems. The application of the universal method of diversification and intensification of search process allows the algorithm to search better the solution space, independently of a problem instance. The application of long term frequently memory in the investigated methods allows to avoid the coiwergence to local optima. The algorithm was tested for sample tasks and selected combi-natorial problems.
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ć.