Optymalizacja konfiguracji algorytmu ewolucyjnego do planowania procesu montażu

• Autorzy: Jankowski T.

Warianty tytułu

EN

Optimization of the evolutionary algorithm configuration for assembly process planning

• Języki publikacji: PL

Abstrakty

PL

Jednym z pierwszych zadań, jakie należy wykonać w trakcie projektowania procesu technologicznego montażu, jest ustalenie kolejności wchodzenia poszczególnych części do procesu montażu, czyli zaplanowanie sekwencji montażowej. Problem planowania sekwencji montażu, jak większość problemów optymalizacji kombinatorycznej, należy do klasy problemów trudno rozwiązywalnych w rozsądnym czasie, co oznacza, że ich dokładne rozwiązanie za pomocą algorytmów o złożoności wielomianowej jest najprawdopodobniej niemożliwe. Przedstawiony w niniejszym artykule koncepcyjny model ewolucyjny umożliwi w opinii autora efektywne rozwiązywanie zagadnienia planowania sekwencji montażowej. Praca skupia się na przedstawieniu znaczenia właściwej konfiguracji algorytmu ewolucyjnego, na przykładzie operacji krzyżowania i różnych wersji jej realizacji. Przeprowadzono badania numeryczne wpływu wybranych sposobów realizacji operatora krzyżowania, jakie w źródłach literaturowych uznawane są za najlepsze dla kodowania permutacyjnego problemów optymalizacji kombinatorycznej, do których należy zadanie planowania sekwencji montażowej oraz zadanie testowe planowania trasy komiwojażera. Wyniki przeprowadzonych badań numerycznych pozwoliły ustalić najbardziej efektywną konfigurację operatora krzyżowania z porządkowaniem (OX) oraz wartości parametrów prawdopodobieństw krzyżowania i mutacji, dla których algorytm uzyskuje rozwiązania optymalne ze stuprocentową powtarzalnością, przy jak najniższym koszcie symulacji.

EN

One of the first steps, which should be done when designing an assembly process, is to determine the order in which the particular parts enter the assembly process, i.e. to plan the assembly sequence. As most combinatorial optimization problems, the assembly sequence-planning problem is difficult to solve in a reasonable amount of time, which means that their exact solution by means of algorithms with polynomial complexity is almost impossible. According to the author, the conceptual evolutionary model presented in this section makes possible to solve effectively the assembly sequence-planning problem. This paper emphasizes the importance of the proper configuration of the evolutionary algorithm, using the crossover operation and the different methods of conduction. Numerical studies have shown that the selective implementation effect of the crossover operator is generally considered to be the best for the permutational encoding of combinatorial optimization problems. The assembly sequence planning task, and the travelling salesman route planning test task that corresponds to the process have been carried out in this study. The numerical simulations led to determine the most effective configuration of the OX crossover operator, the values of the crossover, and mutation probability parameters for which the algorithm generates optimal solutions with one hundred per cent repeatability at the lowest simulation cost.

Słowa kluczowe

PL

algorytmy ewolucyjne; planowanie procesu; optymalizacja

EN

evolutionary algorithms; process planning; optimization

• Wydawca: Oficyna Wydawnicza Politechniki Rzeszowskiej ; Sieć Badawcza Łukasiewicz - Warszawski Instytut Technologiczny
• Czasopismo: Technologia i Automatyzacja Montażu
• Rocznik: 2014
• Tom: nr 3
• Strony: 161--164
• Opis fizyczny: Bibliogr. 9 poz., wykr.

Twórcy

autor

Jankowski T.

• Instytut Technologii Maszyn i Automatyzacji, Politechnika Wrocławska, ul. Wybrzeże Wyspiańskiego 27, 50-370 Wrocław

Bibliografia

• 1. Nowicki E.: Metoda tabu w problemach szeregowania zadań produkcyjnych. Prace Naukowe Instytutu Cybernetyki Technicznej Politechniki Wrocławskiej. Monografie nr 27, Oficyna Wydawnicza Politechniki Wrocławskiej, Wrocław 1999.
• 2. Łebkowski P.: Metody komputerowego wspomagania montażu mechanicznego w elastycznych systemach produkcyjnych. Uczelniane Wydawnictwa Naukowo- Dydaktyczne AGH, Kraków 2000.
• 3. Jankowski T.: Memetic algorithm for assembly sequence planning. Journal of Machine Engineering, vol. 8, no. 3, pp. 77–90, 2008.
• 4. Jankowski T., Jędrzejewski J.: Hybrid evolutionary optimization in efficient task planning. Sustanable production and logistics in global networks: 43rd CIRP International Conference on Manufacturing Systems, W. Sihn and P. Kuhlang, Ed., pp. 884–891, 2010.
• 5. Pawlak M.: The search for the best decision variables values of the evolution program. Materiały I. Krajowej Konferencji pt.: Algorytmy Ewolucyjne, pp. 94–105, Murzasichle, 1996.
• 6. Pawlak M.: Algorytmy ewolucyjne jako narzędzie harmonogramowania produkcji. Wydawnictwo Naukowe PWN, Warszawa 1999.
• 7. Goldberg D. E., Lingle R.: Alleles, Loci, and the {TSP}. Proceedings of the First International Conference on Genetic Algorithms, J. J. Grefenstette, Ed., pp. 154–159, Lawrence Erlbaum Associates, 1985.
• 8. Davis L.: Applying Adaptive Algorithms to Epistatic Domains. Proceedings of the International Joint Conference on Artificial Intelligence, pp. 162–164, 1985.
• 9. Oliver I. M., Smith D. J., Holland J. R. C.: A Study of Permutation Crossover Operators on the Travelling Salesman Problem. Proceedings of the Second International Conference on Genetic Algorithms, J. J. Grefenstette, Ed., pp. 224–230, Lawrence Erlbaum Associates, 1987.