A GENETIC ALGORITHM WITH GREEDY CROSSOVER AND ELITISM FOR CAPACITY PLANNING

Lev Kazakovtsev, Elena Kovlovskaya, Ivan Rozhnov, Olga Patsuk

DOI Number
https://doi.org/10.22190/FUMI220731068K
First page
993
Last page
1006

Abstract


We propose a modification to the genetic algorithm with greedy agglomerative crossover operator for the problem of scheduling product types at the facilities of the metal or plastic production factory where the goal is to minimize the number of switchings of the product type of the production lines. Similar algorithms with greedy agglomerative crossover for location problems do not use any elitism in the population. For the considered problem which may also be classified as a location problem, elitism in the population implemened in the form of tournament selection plays a positive role.  The article also discusses the dependence of the efficiency of the evolutionary algorithm on the size of the population.   As our experiments show, the introduction of elitism into such an algorithm enables us to increase both the rate of convergence of the algorithm and the accuracy of the solution. A special aspect chooses an individual with the best value of the objective function.

Keywords

genetic algorithm, greedy crossover, location problem.

Full Text:

PDF

References


E. B. Patsuk and L. A. Kazakovtsev: Formal model of dynamic scheduling of the educational center. Economics and management of management systems. 28 (2018), 182.

L. A. Kazakovtsev, M. N. Gudyma, D. V. Stashkov, A. A. Stupin and N. N. Dzhioeva: Evolutionary algorithms with a heterogeneous population for clustering and placement problems. Monograph. Scientific and Publishing Center ”Relevance”. Moscow, (2017), 196.

L. Kazakovtsev, I. Rozhnov, I. Nasyrov and V. Orlov: Self-adjusting genetic algorithm with greedy agglomerative crossover for continuous p-median problems. In: Mathematical Optimization Theory and Operations Research: Recent Trends. MOTOR 2021. Communications in Computer and Information Science, 1476 (2021), 184-200. Springer, Cham. doi.org/10.1007/978-3-030-86433-0-13.

O. V. Patsuk: Investment activity of the region. Bulletin of SibGAU named after academician M. F. Reshetnev. 3(43) (2012), 184-189.

A. A. Lazarev and E. R. Gafarov: Schedule theory. Tasks and algorithms. Economics. MOSCOW STATE UNIVERSITY, Moscow, (2011), 220.

E. G. Coffman: Schedule Theory and Computing Machines. Publishing Center ”Academy”, Moscow, (2010), 156.

A. Kapoor: Hands-On Artificial Intelligence for IoT. Packt Publishing, Mumbai, (2019), 267.

L. Kazakovtsev, I. Rozhnov, G. Shkaberina and V. Orlov: K-Means Genetic Algorithms with Greedy Genetic Operators. Mathematical Problems in Engineering. 2020 (2020), ArticleID 8839763. doi.org/10.1155/2020/8839763.

L. Kazakovtsev, I. Rozhnov, A. Popov and E. Tovbis: Self-Adjusting Variable Neighborhood Search Algorithm for Near-Optimal k-Means Clustering. Computation. 8(4) (2020), ArticleID 90. doi.org/10.3390/computation8040090.

L. A. Kazakovtsev and A. N. Antamoshkin: Algorithm for scheduling. Bulletin of KrasGAU. 4(103) (2015), 215-219.

L. A. Kazakovtsev., M. N. Guyma and A. N. Antamoshkin: Genetic Algorithm with Greedy Heuristic for Capacity Planning. International Congress on Ultra Modern Telecommunications and Control Systems and Workshops. 4 (2014), 607-613.

A. V. Eremeev and Yu. B. Kovalenko: The task of compiling schedules with the grouping of machines by technology. Discrete analysis and research of operations. 18 (2011), 54-79.

E. A. Beltz: Optimizing the location of enterprises taking into account the minimum permissible distances. Bulletin of Omsk University. 4 (2012), 13-16.

Yu. A. Kochetov: Comparison of metaheuristics for solving the two-level problem of enterprise placement and factory pricing. Discrete analysis and research of operations. 3 (123) (2015), 36-54.

A. V. Panteleev: Application of evolutionary methods of global optimization in problems of optimal control of deterministic systems. MAI Publishing House, Moscow. (2013), 128.

S. Gonzalez-Martin, A. Ferrer, A. Juan and D. Riera: Solving non-smooth arc routing problems throughout biased- randomized heuristics. Computer-based Modeling and Optimization in Transportation, Springer International Publishing. (2014), 451.

B. A. Bozkaya: Genetic Algorithm for the p-Median Problem. Facility Location Applications and Theory. 7 (2002), 179-232.

N. S. Grigorvea: The task of compiling maximum time offset schedules for parallel processors. MAI Publishing House, Moscow. (2016), 246.

I. H. Sigal and A. P. Ivanova: Introduction to applied discrete programming: models and computational algorithms. 2nd edition, supplemented and corrected, FIZMATLIT,Moscow, (2007), 140.

D. Kirszenblat: Dubins networks: Thesis. Melbourne Department of Mathematics and Statistics of the University of Melbourne. 2 (2011), 56-89.

L. A. Kazakovtsev and A.N. Antamoshkin: Genetic algorithm with fast greedy heuristic for clustering and location problems. Informatica. 38 (2014), 229–240.

A. Antamoshkin and I. Masich: Pseudo-Boolean Optimization in Case of an Unconnected Feasible Set. In: ”Models and Algorithms for Global Optimization”, Optimization and Its Applications. 4 (2007), 111–122.

G. N. Dubin and A. A. Korbut: FBehavior on average of greedy algorithms for the minimization problem about the rant - general distributions of coefficients. Journal of Computational Mathematics and Mathematical Physics. 48 (2008), 1556-1579.

I. L. Vasiliev: New lower grades for the problem of placement with client preferences. Journal of Computational Mathematics and Mathematical Physics. 6 (2009), 1055-1097.

R. A. Neidorf, V. G. Kobak and D. V. Titov: Comparative analysis of the effectiveness of tournament selection of a genetic algorithm for solving homogeneous distributive problems. Bulletin of the Don State Technical. un-ta. 3 (2009), 410-432.

L. Kazakovtsev, I. Rozhnov and G. Shkaberina: Self-Configuring (1 + 1)-Evolutionary Algorithm for the Continuous p-Median Problem with Agglomerative Mutation. Algorithms. 14 (2021), 130. https://doi.org/10.3390/a14050130.

L. Kazakovtsev, D. Stashkov, M. Gudyma and V. Kazakovtsev: Algorithms with Greedy Heuristic Procedures for Mixture Probability Distribution Separation. Yugoslav Journal of Operations Research. 29(1) (2019), 51-67. https://doi.org/10.2298/YJOR171107030K.




DOI: https://doi.org/10.22190/FUMI220731068K

Refbacks

  • There are currently no refbacks.




© University of Niš | Created on November, 2013
ISSN 0352-9665 (Print)
ISSN 2406-047X (Online)