کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
494549 | 862799 | 2016 | 11 صفحه PDF | دانلود رایگان |
• We propose a novel formulation for the MGS problem based on multiple knapsack.
• The so-conceived MGS problem is solved by a novel GA.
• The GA embeds an intelligent construction method and specialized crossover operators.
• We perform a thorough comparison with regards to state-of-the-art algorithms.
• The proposal proves to be very competitive, specially for large and hard instances.
Given a set of positive integers S, the minimum generating set problem consists in finding a set of positive integers T with a minimum cardinality such that every element of S can be expressed as the sum of a subset of elements in T. It constitutes a natural problem in combinatorial number theory and is related to some real-world problems, such as planning radiation therapies.We present a new formulation to this problem (based on the terminology for the multiple knapsack problem) that is used to design an evolutionary approach whose performance is driven by three search strategies; a novel random greedy heuristic scheme that is employed to construct initial solutions, a specialized crossover operator inspired by real-parameter crossovers and a restart mechanism that is incorporated to avoid premature convergence. Computational results for problem instances involving up to 100,000 elements show that our innovative genetic algorithm is a very attractive alternative to the existing approaches.
Figure optionsDownload as PowerPoint slide
Journal: Applied Soft Computing - Volume 48, November 2016, Pages 254–264