Intézeti szeminárium

Egy evolúciós heurisztikát mutatok be az egy dimenziós offline ládapakolási
problémára. E problémánál a tárgyakat azonos kapacitású ládákba kell pakolni.
Minden tárgynak súlya van és a ládák kapacitását nem szabad túllépni. A cél
a használt ládák számának minimalizálása.

Algoritmusom hibrid evolúciós algoritmus. Egy egyed egy megoldást ír le a
hozzá tartozó ládákkal és tartalmukkal.  Az algoritmus rekombináció művelet
nélkül dolgozik, két új mutáció műveletet alkalmaz és helyi kereső eljárásokkal
javítja a megoldásokat. A mutáció műveletek egy relatív-pár frekvencia mátrix
alapján működnek. A frekvencia mátrix minden tárgy pár esetén becsült
valószínűséget ad arra, hogy egy ládába kerülhetnek. A mátrix révén a
tárgyakat a tárgyak diszjunkt részhalmazaiba tudjuk válogatni; esetünkben e
részhalmazok  lesznek a ládák a tárgyakkal.

Az algoritmust az irodalomban jól ismert benchmark teszthalmazokon teszteltem.
1615 példából csak 4 esetben nem találta meg az optimális megoldást.
Algoritmusom korábbi evolúciós algoritmusokkal, valamint state-of-art
módszerekkel hasonlítottam össze. Algoritmusom értékes eredményt ért el a
Hard28 teszt halmazon; minden példánál megtalálta az optimális megoldást.