Solving Large Binary Quadratic Programming Problems by Effective Genetic Local Search Algorithm
Solving Large Binary Quadratic Programming Problems by Effective Genetic Local Search Algorithm
复制标题
通过有效的遗传局部搜索算法解决大型二元二次规划问题
DOI：
--
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
H. Narihisa
中科院分区：
文献类型：
--
作者：
K. Katayama;M. Tani;H. Narihisa
将遗传算法与局部搜索技术相结合，提出了一种求解无约束二次规划问题的遗传局部搜索算法。一种有效的局部搜索算法，它是Merz等人的BQP的k-opt局部搜索的变体，的描述，和性能的GLS与变异的局部搜索启发式证明了几个大规模的问题的例子。我们的计算结果表明，GLS是能够频繁地找到最知名的解决方案，相对较短的运行时间，显然我们得到的平均解值优于以前的强大的启发式方法，特别是对于2,500个变量的大型问题实例。
A genetic local search (GLS) algorithm, which is a combination technique of genetic algorithm and local search, for the unconstrained binary quadratic programming problem (BQP) is presented. An effective local search algorithm, which is a variant of the k-opt local search for the BQP by Merz et al., is described, and the performance of the GLS with the variant local search heuristic is demonstrated on several large-scale problem instances. Our computational results indicate that the GLS is able to frequently find the best-known solution with a relatively short running time and obviously our average solution values obtained are better than previous powerful heuristic approaches especially for the large problem instances of 2,500 variables.