دانلود رایگان مقاله الگوریتم ژنتیک برای حداقل مشکل مجموعه تولید

Abstract

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.

6. Conclusions

In this paper, a new formulation of the MGS problem was developed to conceive a GA that revolves around RG-MGS, a new randomized greedy method being able to construct, in an intelligent, diversified feasible solutions for this highly constrained problem. This heuristic procedure is employed as initialization mechanism for the GA and it is the basic pillar on which the design of the crossover operators is supported. A design that was completed precisely through the knowledge acquired in the research field of GAs for continuous optimization problems [30,38,39,29]. The GA also integrates a restart operator to ensure a reliable evolution toward promising areas throughout the entire search. The proposal has proven to be a very high performing algorithm for the MGS problem, showing it to be very competitive with respect to state-of-the-art algorithms. Specifically, the empirical study reveals a clear superiority when tackling hard and large instances. The ability of the proposed GA to yield superior outcomes along with the simplicity and flexibility of this approach, allows us to conclude thatthis metaheuristic arises as a tool of choice to face this problem. Moreover, itinvites further consideration to explore other forms of evolutionary algorithms, such as the memetic algorithms [40,39], which apply a local search method to members of the GA populationafter crossover andmutationoperations, withthe aimof exploiting the best search regions identified by the global sampling done by the GA.