Testing of crossover operators for the grey pattern problem

Abstract

Recently genetic algorithms (GAs) are a great success in solving combinatorial optimization problems. In this paper the performance issues related to the genetic search in the context of the grey pattern problem (GPP) are discussed. The main attention is paid to the investigation of the solution recombination, i.e. crossover operators, which play an important role developing robust genetic algorithms. We implemented seven crossover operators within the hybrid genetic algorithm (HGA) framework, and carried out the extensive experiments in order to test the influence of the recombination operators on the genetic search process. The results obtained from the experimentation with GPP test instances (benchmarks) demonstrate promising efficiency of so‐called multiple parent crossover which is based on a special type of recombination of several solutions‐parents.

Kryžminimo (krosoverio) operatorių tyrimas sprendžiant „pilkų šablonų“ sudarymo uždavinį

Santrauka. Pastaraisiais metais pasiektas didelis progresas sprendžiant kombinatorinio optimizavimo uždavinius genetiniais algoritmais (GA). Šiame straipsnyje nagrinėjami GA efektyvumo klausimai „pilkų šablonų“ sudarymo (formavimo) uždavinio kontekste. Daugiausia dėmesio skiriama sprendinių kryžminimo (krosoverio) operatoriams, atliekantiems svarbų vaidmenį genetiniuose algoritmuose, tirti. Realizuoti septyni skirtingi kryžminimo algoritmai, kurie įtraukti į hibridinio genetinio algoritmo sudėtį, išbandyti sprendžiant minėtą uždavinį. Eksperimentinių tyrimų tikslas ñ nustatyti kryžminimo operatorių įtaką GA gaunamiems sprendiniams. Eksperimentų, atliktų su įvairiais „pilkų šablonų“ sudarymo uždavinio testiniais pavyzdžiais (duomenimis), rezultatai liudija labai aukštą kai kurių kryžminimo procedūrų efektyvumo laipsnį. Tai visų pirma pasakytina apie vadinamąjį „daugelio tėvų“  kryžminimą, kuris pagrįstas netrivialaus kelių sprendinių-tėvų požymių kombinavimu, naudojant algoritmą.

Reikšminiai žodžiai: kombinatorinis optimizavimas, euristiniai algoritmai, genetiniai algoritmai, kryžminimo (krosoverio) operatoriai, „pilkų šablonų“ sudarymo uždavinys.

First Published Online: 21 Oct 2010

Keyword : combinatorial optimization, heuristic algorithms, genetic algorithms, crossover operators, grey pattern problem