Efektywność operatorów krzyżowania w algorytmie genetycznym dla problemu szeregowania zadań w systemie przepływowym

W pracy przedstawiono wyniki badań operatorów krzyżowania w algorytmie genetycznym dla problemu szeregowania zadań w systemie przepływowym przy kryterium minimalizacji długości uszeregowania. Praca składa się z trzech części. W pierwszej omówiono znane z literatury operatory krzyżowania, stosowane w problemach kolejnościowych, oraz przedstawiono nowy operator opracowany przez autorów. W drugiej części zaprezentowano szczegółowe wyniki badań efektywności tych operatorów. Badania wykonano dla losowo wygenerowanych problemów o rozmiarach n x M ={20x10, 50x20, 100x20, 200 x 10, 200 x 20, 500 x 20}, każdorazowo po 50 przykładów. Następnie zbadano, czy różnice pomiędzy wynikami otrzymywanymi przez poszczególne operatory są istotne. W tym celu dla każdego rozmiaru problemu obliczono dla poszczególnych operatorów względną odległość od najlepszego rozwiązania Amin i tak otrzymano średnie poddano testowi statystycznemu. Wyniki badań omówione w części trzeciej wykazały, że dzięki starannemu doborowi elementów algorytmu genetycznego można osiągnąć istotną poprawę działania algorytmu.

---

This paper presents a comparison of genetic algorithm crossover operators for the flowshop problem. Paper is divided into three parts. In part one, the crossover operators known from literature and a new operator designed by authors have been described. In the second part detailed results of the effectiveness of these operators have been presented. lnvestigations were done for the problems of sizes of n x M = {20 x 10, 50 x 20, 100 x 20, 200 x 10, 200 x 20, 500 x 20}, every time for 50 problems for each size. Af-terwards the results were examined whether they differed considerably. Relative distances from the best solution Amin for each size of the problem were calculated and means got in such way were tested statistically. The results, discussed in part three, have been shown that thanks to accurate choice of genetic algorithm components it is possible tomkake a real improvement of algorithm performance.