Просмотр исходного текста страницы Citeseer/An Evolutionary Path Relinking Approach for the Quadratic Multiple Knapsack Problem (2015) 10.1.1.707.4961

{{checked|}}
{{citeseerlink|citeseer/An Evolutionary Path Relinking Approach for the Quadratic Multiple Knapsack Problem (2015) 10.1.1.707.4961|<html>
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.
</html>}}
{{enddiv}}

[[Категория:CiteSeerArticles]]