Study on modified Whitley model with different number and various methods of forming elite individuals

Introduction. A comparative analysis of the modified Whitley model solutions through different methods of forming elite individuals is presented. The algorithms of Kron and Plotnikov-Zverev are used in the study for the formation of elite individuals. The work objectives are the development of the modified Whitley model involving the Kron’s and PlotnikovZverev’s algorithms to form elite individuals, as well as a software tool for solving the scheduling theory problem. It was necessary to obtain the best solution to this problem with various initial data followed by processing the results and identifying a modification of the Whitley model. The distribution problem which implies the search for the optimal distribution of work to the processors with the minimization of the maximum execution time is described.

Materials and Methods. All the algorithms implemented under the development of the software tool for solving the optimization scheduling problem are considered. The following algorithms are presented: the modified Whitley model, the application of the elitism strategy, the Kron’s algorithm, the Plotnikov-Zverev’s algorithm.

Research Results. A software tool is developed. It was applied to conduct a computational experiment with various initial data using one, two, three, and four elite individuals. The experiment was carried out for the most common data sets with a different number of elite individuals. Each Whitley model modification was launched a hundred times with each set of the source data. The comparative analysis of the results shows how the application of the considered elitism strategies in the developed modifications of the genetic algorithm (Whitley model) affects the accuracy of the solution to the homogeneous minimax problem with a different number of elite individuals.

Discussion and Conclusions. The best results of the algorithms are determined; the utilization of elitism in the modified Whitley model when solving a homogeneous minimax problem of scheduling theory is estimated. The algorithm results are compared for one, two, three and four elite individuals.

1. Cormen, T., et al. Algoritmy: postroenie i analiz. [Algorithms: construction and analysis.] Moscow: Vil'yams, 2013, 1328 p. (in Russian).

2. Gladkov, L.A., Kureychik, V.V., Kureychik, V.M. Geneticheskie algoritmy. [Genetic algorithms.] Moscow: Fizmatlit, 2006, 320 p. (in Russian).

3. Emelyanov, V.V., Kureychik, V.V., Kureychik, V.M. Teoriya i praktika evolyutsionnogo modelirovaniya. [Theory and practice of evolutionary modeling.]. Moscow: Fizmatlit, 2003, 432 p. (in Russian).

4. Chernishev, Y.O., Poluyan, A.Y. Adaptivnyy geneticheskiy algoritm dlya resheniya zadach optimizatsii na osnove strategii elitizma. [Adaptive genetic algorithm for the decision of problems of optimization on the basis of strategy of elite.] Izvestiya SFedU. Engineering Sciences, 2008, no. 4 (81), pp. 36–39 (in Russian).

5. Whitley, D. A genetic algorithm tutorial. Computer science department, Colorado State University. Available at: https://www.cs.colostate.edu/pubserv/pubs/Whitley-genitor-MiscPubs-tutorial.pdf (accessed: 20.10.2017).

6. Panteleev, A.V., Metlitskaya, D.V., Aleshina, E.A. Metody global'noy optimizatsii. Metaevristicheskie strategii i algoritmy. [Methods of global optimization. Meta-heuristic strategies and algorithms.] Moscow: Vuzovskaya kniga, 2013, 244 p. (in Russian).

7. Panteleev, A.V. Primenenie evolyutsionnykh metodov global'noy optimizatsii v zadachakh optimal'nogo upravleniya determinirovannymi sistemami. [Application of evolutionary methods of global optimization in problems of optimal control of determined systems]. Moscow: MAI Publ. House, 2013, 160 p. (in Russian).

8. Kobak, V.G., Titov, D.V., Zolotykh, O.A. Issledovanie algoritma Krona i ego modifikatsii pri razlichnykh iskhodnykh dannykh. [Investigation of Krohn’s algorithm and its modification for various basic data.] Vestnik of DSTU, 2012, no. 8 (69), pp. 62–67 (in Russian).

9. Kobak, V.G., Zolotykh, O.A., Gushchin, A.Y. Ispol'zovanie algoritma Krona dlya formirovaniya elit pri reshenii odnorodnoy minimaksnoy zadachi model'yu Goldberga. [Application of the Krohn’s algorithm for elite formation in solving homogeneous minimax problem by Goldberg model.] Symbol of Science, 2016, no. 4–3(16), pp. 79– 83 (in Russian).

10. Kobak, V.G., Krasniy, D.G., Neydorf, R.A. Perspektivnye algoritmy resheniya neodnorodnoy raspredelitel'noy zadachi teorii raspisaniy. [Perspective algorithms of the decision of a non-uniform distributive problem of the theory of schedules.] Izvestiya SFedU. Engineering Sciences, 2008, no. 9 (86), pp. 152–156 (in Russian).