Genetic algorithms for binary quadratic programming
Genetic algorithms for binary quadratic programming
复制标题
DOI：
--
复制
发表时间：
1999-07
期刊：
影响因子：
--
通讯作者：
P. Merz;Bernd Freisleben
中科院分区：
文献类型：
--
作者：
P. Merz;Bernd Freisleben
本文提出了求解无约束二元二次规划问题的遗传算法。结果表明，对于小问题，一个简单的遗传算法与均匀交叉是足够的，以找到最佳或最好的解决方案在短时间内，而与大量的变量（n ≥ 200），它是必要的，以达到高质量的解决方案，结合局部搜索。一个混合遗传算法，结合本地搜索进行测试，对40个问题的实例，包含n = 200和n = 2500之间的大小。计算机实验结果表明，该方法对小实例的性能可与禁忌搜索等算法相媲美，对大实例的性能优于禁忌搜索和模拟退火算法，具有上级的性能。可以为14个大问题实例找到新的最佳解决方案。
In this paper, genetic algorithms for the unconstrained binary quadratic programming problem (BQP) are presented. It is shown that for small problems a simple genetic algorithm with uniform crossover is sufficient to find optimum or best-known solutions in short time, while for problems with a high number of variables (n ≥ 200) it is essential to incorporate local search to arrive at high-quality solutions. A hybrid genetic algorithm incorporating local search is tested on 40 problem instances of sizes containing between n = 200 and n = 2500. The results of the computer experiments show that the approach is comparable to alternative heuristics such as tabu search for small instances and superior to tabu search and simulated annealing for large instances. New best solutions could be found for 14 large problem instances.