Share:


Testing of crossover operators for the grey pattern problem

    Alfonsas Misevičius Affiliation

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ą.


First Published Online: 21 Oct 2010


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

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

How to Cite
Misevičius, A. (2006). Testing of crossover operators for the grey pattern problem. Technological and Economic Development of Economy, 12(1), 37-43. https://doi.org/10.3846/13928619.2006.9637720
Published in Issue
Mar 31, 2006
Abstract Views
23
PDF Downloads
22