Optymalizacja konfiguracji algorytmu ewolucyjnego do planowania procesu montażu

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.

---

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.