Egy heurisztikus módszer a kvadratikus hozzárendelési probléma közelítő megoldásához

Absztrakt

Tanulmányunkban egy evolúciós algoritmust ismertetünk a kvadratikus hozzárendelési probléma megoldására. Az algoritmus működése három, egymás utáni fázisra bontható: egy előkészítő, valamint két különböző helyi kereső fázisra. Az első fázisban a kezdő populáció minőségét javítja. A második fázisban egy helyi kereső eljárással felváltva javít minden megoldást (egyedet), és közben periodikusan újabb megoldásokat generál a meglévők környezetében. A harmadik fázisban a helyi kereső eljárással folytatja a megoldások javítását, és közben a legrosszabb megoldásokat periodikusan újakra cseréli. Az algoritmust a QAPLIB könyvtár lól ismert tesztfeladatival ellenőriztük. Az algoritmus a feladatok 98%-nál megtalálta a legjobb ismert megoldásokat, vagy a legjobb ismeret megoldás 1%-os környezetébe került.