Wyniki wyszukiwania - BazTech

1

Multi-swarm that learns

Trojanowski K.

Control and Cybernetics

|

2010

|

Vol. 39, no 2

359-375

EN

This paper studies particle swarm optimization approach enriched by two versions of an extension aimed at gathering information during the optimization process. Application of these extensions, called memory mechanisms, increases computational cost, but it is spent to a benefit by incorporating the knowledge about the problem into the algorithm and this way improving its search abilities. The first mechanism is based on the idea of storing explicit solutions while the second one applies one-pass clustering algorithm to build clusters containing search experiences. The main disadvantage of the former mechanism is lack of good rules for identification of outdated solutions among the remembered ones and as a consequence unlimited growth of the memory structures as the optimization process goes. The latter mechanism uses other form of knowledge representation and thus allows us to control the amount of allocated resources more efficiently than the former one. Both mechanisms have been experimentally verified and their advantages and disadvantages in application for different types of optimized environments are discussed.

2

On Some Properties of Quantum Particles in Multi-Swarms for Dynamic Optimization

Trojanowski K.

Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk

|

2009

|

Nr 1016

1-60

EN

This paper studies properties of a multi-swarm system based on a concept of physical quantum particles (mQSO). Quantum particles differ from the classic ones in the way they move. As opposed to the classic view on a particle movement, where motion is controlled by linear kinematic laws, quantum particles change their location according to random distributions. The procedure of generating a new location for the quantum particle is similar to mutation operator widely used in evolutionary computation with real-valued representation. In this paper we study a set of new distributions of candidates for the quantum particle location, and we show different features of these distributions. The distributions considered in this paper are divided into two classes: those with a limited range of the new location coordinates and those without such limitations. They are tested on different types of dynamic optimization problems. Experimental verification has been based on a number of testing environments and two main versions of the algorithm: with and without mechanisms protecting against stagnation caused by convergence of sub-swarms during the search process. The experimental results show the advantages of the distribution class, in which the candidates are spread out in the entire search space, and indicate the positive and negative aspects of application of anti-convergence mechanisms.

PL

W niniejszym raporcie studiowane są właściwości systemów wielorojowych opartych na idei cząsteczek kwantowych (mQSO). W przeciwieństwie do klasycznego podejścia do ruchu cząsteczki, w którym przemieszczanie kontrolowane jest przez liniowe prawa kinematyki, kwantowe cząsteczki zmieniają swoje położenie wykorzystując rozkłady losowe. Tutaj badamy pewien zbiór nowych rozkładów kandydatów na nowe położenie cząsteczki kwantowej i demonstrujemy ich różne właściwości. Rozkłady rozpatrywane poniżej można podzielić na dwie klasy: z ograniczonym obszarem możliwych nowych położeń cząsteczki, oraz pozostałe z nieograniczonym obszarem tych położeń. Wszystkie zostały testowane na różnych typach zadań dynamicznych. Eksperymentalna weryfikacja została oparta na pewnej liczbie zadań testowych, a także na dwóch głównych wersjach algorytmu: uzwględniającego i nieuwzględniającego mechanizmy chroniące przeciwko stagnacji powodowanej przez zbieganie zbioru rozwiązań algorytmu do niewielkich obszarów dziedziny w trakcie poszukiwań. Wyniki eksperymentów wskazują przewagę tej klasy rozkładów, w której kandydaci na nowe położenie cząsteczki mogą należeć do całego zbioru poszukiwań. Wyniki pokazują też pozytywne i negatywne aspekty stosowania mechanizmów anty-zbieżnosci.

3

Multi-Swarm That Learn

Trojanowski K.

Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk

|

2009

|

Nr 1015

1-24

EN

In this paper a dynamic optimization with particle swarm approach using two different memory mechanisms is studied. One of them is based on the idea of storing explicit solutions in memory structures while the other applies one-pass clustering algorithm to build clusters containing search experiences. Both mechanisms have been experimentally verified and their advantages and disadvantages in application for different types of testing environments have been discussed.

PL

Artykuł zawiera wyniki badań dwóch mechanizmów pamięciowych stosowanych w roju cząsteczek do optymalizacji dynamicznej. Jeden z nich jest oparty na zasadzie gromadzenie gotowych rozwiązań w strukturach pamięci, natomiast drugi stosuje jednoprzejściowy algorytm do budowy klastrów, w których mogłyby być przechowywane doświadczenia zdobywane w trakcie procesu szukania. Obydwa mechanizmy zostały zweryfikowane w badaniach eksperymentalnych a ich wady i zalety objawiające się w zastosowaniach do różnych typów zadań zostały omówione.

4

Properties of Quantum Particles in Multi-Swarms for Dynamic Optimization

Trojanowski K.

Fundamenta Informaticae

|

2009

|

Vol. 95, nr 2/3

349-380

EN

This paper studies properties of a multi-swarm system based on a concept of physical quantum particles (mQSO). Quantum particles differ from the classic ones in the way they move. As opposed to the classic view of particle movement, where motion is controlled by linear kinematic laws, quantum particles change their location according to random distributions. The procedure for generating a new location for the quantum particle is similar to mutation operators widely used in evolutionary computation with real-valued representation. In this paper we study a set of new distributions of candidates for quantum particle location, and we show different features of these distributions. The distributions considered in this paper are divided into two classes: those with a limited range of the new location coordinates and those without such limitations. They are tested on different types of dynamic optimization problems. Experimental verification has been based on a number of testing environments and two main versions of the algorithm: with and without mechanisms protecting against stagnation caused by convergence of sub-swarms during the search process. The experimental results show the advantages of the distribution class, in which the candidates are spread out in the entire search space, and indicate the positive and negative aspects of application of anti-convergence mechanisms.

5

A Multi-swarm Approach to Multi-objective Flexible Job-shop Scheduling Problems

Liu H., Abraham A., Wang Z.

Fundamenta Informaticae

|

2009

|

Vol. 95, nr 4

465-489

EN

Swarm Intelligence (SI) is an innovative distributed intelligent paradigm whereby the collective behaviors of unsophisticated individuals interacting locally with their environment cause coherent functional global patterns to emerge. In this paper, we model the scheduling problem for the multi-objective Flexible Job-shop Scheduling Problems (FJSP) and attempt to formulate and solve the problem using a Multi Particle Swarm Optimization (MPSO) approach. MPSO consists of multi-swarms of particles, which searches for the operation order update and machine selection. All the swarms search the optima synergistically and maintain the balance between diversity of particles and search space. We theoretically prove that the multi-swarm synergetic optimization algorithm converges with a probability of 1 towards the global optima. The details of the implementation for the multi-objective FJSP and the corresponding computational experiments are reported. The results indicate that the proposed algorithm is an efficient approach for the multi-objective FJSP, especially for large scale problems.