Permutation flow shop scheduling problem (PFSSP), a NP-hard combinatorial optimization problem, has strong engineering background of finding the optimal processing sequence and time of jobs on machines under the constraints of resources. Recently, several approaches based on Particle Swarm Optimization (PSO) have been developed to solve the PFSSP, and the experimental results show that they are efficient. To solve this issue, a novel variant of quantum-behaved particle swarm optimization algorithm for permutation flow shop scheduling is proposed in this paper. This algorithm is a combination of quantum-behaved PSO, electoral mechanism, and a disturbance generated by Lévy flights. Inspired by the election behavior in society, an electoral and cooperative mechanism is imported to get the elite particles from the primitive sub-swarms respectively. Moreover, the character unequal hop length of Lévy flights provides a method to escape the local optima efficiently. The numerical results on the Taillard's benchmark also show it outperforms other related algorithms.
PL
Problem szeregowania zmiany przepływów magazynowych (PFSSP) jest silnie nie–wielomianowym (NP) problemem optymalizacji kombinatorycznej. Ma ważny inżynierski aspekt w wyznaczaniu optymalnej kolejności procesu i czasu pracy maszyn, wymuszonej zmianą zasobów. Ostatnio, do rozwiązania PFSSP, zastosowano szereg przybliżeń opartych o algorytm optymalizacji rojem cząstek (PSO) a wyniki praktyczne pokazują, że są to rozwiązania efektywne. W prezentowanym opracowaniu, do szeregowania przepływów magazynowych, zaproponowano nowy wariant algorytmu optymalizacji rojem cząstek z zachowaniem kwantowym (QPSO). Algorytm jest kombinacją QPSO, mechanizmu wyborczego i zakłóceń generowanych rozkładem lotów Levy’ego. Do wyłonienia cząstek elitarnych z prymitywnego pod-roju wykorzystano, inspirowany zachowaniami wyborczymi w społeczeństwie, mechanizm wyborczy i współpracy. Ponadto, unikalny charakter długości skoków lotów Levy’ego pozwala skutecznie uniknąć optimów lokalnych. Wyniki numeryczne, przeprowadzone na danych testowych Taillard’a, także wskazują na przewagę nad innymi porównywalnymi algorytmami.
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
This paper proposes a hybrid cooperative quantum particle swarm optimization (HCQPSO), hybridizing dynamic varying search area, cooperative evolution, simulated annealing and quantum particle swarm optimization (PSO) for function optimization. In the proposed HQCPSO, a technique of dynamic varying search area helps reduce the search spaces and populations of swarms, which could make the optimization more efficient. Simulated annealing is integrated in the position update to modify the trajectories of particles to avoid being trapped in the local optimum. To test the performance of HQCPSO, numerical experiments are conducted to compare the proposed algorithm with different variants of PSO. According to the experimental results, the proposed method performs better than other variants of PSO on benchmark test functions.
PL
W artykule zaproponowano hybrydowy algorytm optymalizacji PSO. Porównanie z innymi, znanymi wariantami wykazało, że zastosowane w metodzie rozwiązania, pozwalają na efektywniejsze działanie proponowanego algorytmu PSO. Wyniki eksperymentalne potwierdziły powyższą tezę.
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ć.