Ütemezési feladatokra alkalmazott genetikus algoritmus keresztező operátorainak vizsgálata

Examination of the crossover of genetic algorithm applied to scheduling tasks

Simon, Pál

Bitay, Enikő

Máté, Márton

Erdélyi Múzeum-Egyesület

2013-11-22T11:50:28Z

2013-11-22T11:50:28Z

2013

2014

ütemezés

Utazó ügynök probléma

genetikus algoritmus

keresztező operátor

scheduling

Travelling salesman problem

genetic algorithm

crossover

A gyártásütemezési feladatok összetett sorrend előállítási feladatok, amelyek megoldásának előállítása napjainkban is nehéz feladat. Ezeket a feladatokat az Utazó ügynök problémával jól lehet modellezni, amely egy NP-nehéz probléma és nem oldhatók meg optimálisan ésszerű időn belül. Nem optimális, de elfogadható megoldást lehet elérni elfogadható időn belül mesterséges intelligencia módszerekkel. Egy ilyen módszer a genetikus algoritmus. Ezt a módszert már régóta alkalmazzák az Utazó ügynök probléma megoldására. Az algoritmus egyik legfontosabb része az egyedek keresztezése, amely nagymértékben befolyásolja a hatékonyságát. Több keresztező operátort is kifejlesztettek napjainkra. Ezek mindegyike hasonló jellemzőkkel rendelkezik, mint például a keresztezni kívánt egyedekben lévő rész sorrendek pozícióinak és a sorrendjének megőrzése. Ebben a cikkben ezekre a jellemzőkre szeretnék rávilágítani. Majd egy olyan operátort mutatok be, amely nem rendelkezik ezekkel a jellemzőkkel, ezáltal hatékonyabbá teszi az algoritmust. Ezt a hatékonyság növekedést teszteredmények bemutatásával támasztom alá.

Production scheduling problems are complex order design tasks, whose solution is still a difficult task nowadays. These tasks are usually modelled with the Travelling Salesman Problem. This is an NP-hard problem and can’t be solved optimally within a reasonable time. Acceptable but not optimal solution provided by artificial intelligence procedures within a reasonable period of time. Such process is the genetic algorithm. This algorithm has been used for a long time to solve the travelling salesman problem. A key part of the algorithm is the crossover operator, that affecting the efficiency. Over time, many crossing operators were developed. Each of these has similar characteristics such as maintaining the position and the order of the subsequence. In this article I show the disadvantage of these characteristics. Then I present an operator that does not have these characteristics and thus it makes the algorithm more efficient. To support this increased efficiency I will present some test results.

127-134 old.

magyar

article

PDF

application/pdf

http://hdl.handle.net/10598/28089

Erdélyi Múzeum-Egyesület

Műszaki Tudományos Ülésszak - MTÜ - 2013 - eBook

2013

Erdélyi Múzeum-Egyesület