Citeseer/An Evolutionary Path Relinking Approach for the Quadratic Multiple Knapsack Problem (2015) 10.1.1.707.4961

Ссылки сюда (1) →

«An Evolutionary Path Relinking Approach for the Quadratic Multiple Knapsack Problem (2015) 10.1.1.707.4961»^{скачать}

« The quadratic multiple knapsack problem (QMKP) is a challenging combinato- rial optimization problem with numerous applications. In this paper, we propose the first evolutionary path relinking approach (EPR) for solving the QMKP ap- proximately. This approach combines advanced features both from the path relinking (PR) method and the responsive threshold search algorithm. Thanks to the tunneling property which allows a controlled exploration of infeasible regions, the proposed EPR algorithm is able to identify very high quality so- lutions. Experimental studies on the set of 60 well-known benchmarks and a new set of 30 large-sized instances show that EPR outperforms several state-of- the-art algorithms. In particular, it discovers 10 improved results (new lower bounds) and matches the best known result for the remaining 50 cases. More significantly, EPR demonstrates remarkable efficacy on the 30 new larger in- stances by easily dominating the current best performing algorithms across the whole instance set. Key components of the algorithm are analyzed to shed lights on their impact on the proposed approach. …»

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.