sapiСистемный анализ и прикладная информатика«System analysis and applied information science»2309-49232414-0481Belarusian National Technical University10.21122/2309-4923-2018-3-9-16sapi-220Research ArticleСистемный анализSystem analysisОПРЕДЕЛЕНИЕ РАЗМЕРА ПОПУЛЯЦИИ ГЕНЕТИЧЕСКОГО АЛГОРИТМА ДЛЯ ЗАДАЧ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ В САПРDETERMINING THE SIZE OF THE POPULATION OF THE GENETIC ALGORITHM FOR THE PROBLEMS OF DISCRETE OPTIMIZATION IN CADФроловВ. B.FrolovV. V.

Доктор технических наук, доцент, профессор кафедры теоретической и прикладной информатики

vvicfrol@rambler.ruХарьковский национальный университет имени В. Н. КаразинаУкраинаV. N. Karazin Kharkiv National UniversityUkraine20182910201803916Copyright © Фролов В.B., 20182018Фролов В.B.Frolov V.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://sapi.bntu.by/jour/article/view/220

Предлагается метод определения размера популяции. Общий подход для определения размера популяции вытекает из утверждения, что хромосомы популяции должны содержать максимальное количество различных значений, которые покрывают большую часть области поиска. В основе метода лежит регрессионная модель, которая позволяет определить размер популяции в зависимости от допустимого количества значений независимой переменной. Регрессионная модель получена в результате обработки данных имитационного моделирования при формировании популяции для целевой функции с одной переменной. Задача решается для генетического алгоритма, где генотип представлен хромосомой в двоичном коде, а фенотип десятичным целочисленным кодом значений независимых переменных. Это позволяет моделировать формирование популяции без привязки к конкретным значениям переменных. Модель была получена для диапазона мощностей опорных множеств от 12 до 52, и позволяет прогнозировать размер популяции за границами этого диапазона. Основная область использования данного метода – это задачи дискретной оптимизации с целевыми функциями нескольких переменных, где области допустимых значений конечны и имеют небольшую размерность.

 

A method for determining the size of a population is proposed. The general approach for determining the size of a population follows from the statement that the chromosomes of a population must contain the maximum number of different values that cover most of the search area. The method is based on the regression model, which allows you to determine the size of the population, depending on the permissible number of values of the independent variable. The regression model is obtained as a result of processing simulation data in the formation of a population for a single-variable objective function. The problem is solved for a genetic algorithm, where the genotype is represented by a chromosome in binary code, and the phenotype by a decimal integer code of values of independent variables. This allows you to model the formation of a population without reference to specific values of variables. The model was obtained for the power range of the reference sets from 12 to 52, and allows to predict the size of the population beyond the limits of this range. The main area of use of this method is discrete optimization problems with objective functions of several variables, where the ranges of admissible values are finite and have a small dimension.

популяциягенетический алгоритмСАПРгенотипфенотипхромосомаpopulationgenetic algorithmCADgenotypephenotypechromosomeReferencesЕмельянов В. В., Курейчик В. В., Курейчик В. М. Теория и практика эволюционного моделирования. – М.: ФИЗМАТЛИТ, 2003. – 432 с.Emel’janov V. V., Kurejchik V. V., Kurejchik V. M. Teorija i praktika jevoljucionno-go modelirovanija. – M.: FIZMATLIT, 2003. – 432 s.Цой Ю. Р. Нейроэволюционный алгоритм и программные средства для обработки изображений. [Электронный ресурс]: дис. на соискание ученой степени канд. техн. наук: спец. 05.13.01 – Системный анализ, управление и обработка информации (отрасль: информация и информационные системы) / Ю. Р Цой. – Томск, 2007. – 209 с. – Режим доступа: http://qai.narod.ru/Dissertation/tsoy_phd.thesis.zip (дата обращения: 27.12.2017).Coj Ju. R. Nejrojevoljucionnyj algoritm i programmnye sredstva dlja obrabotki izobrazhenij. [Jelektronnyj resurs]: dis. na soiskanie uchenoj stepeni kand. tehn. nauk: spec. 05.13.01 – Sistemnyj analiz, upravlenie i obrabotka informacii (otrasl’: informacija i informacionnye sistemy) / Ju. R Coj. – Tomsk, 2007. – 209 s. – Rezhim dostupa: http://qai.narod.ru/Dissertation/tsoy_phd.thesis.zip (data obrashhenija: 27.12.2017).Чипига А. Ф., Петров Ю. Ю. Оценка выбора размера популяции в простом генетическом алгоритме. [Электронный ресурс] // Информационное противодействие угрозам терроризма. – 2005г. – № 5. – С. 26–29. – Режим доступа: https://elibrary.ru/item.asp?id=9572194 (дата обращения: 23.03.2018).Chipiga A. F., Petrov Ju. Ju. Ocenka vybora razmera populjacii v prostom geneti-cheskom algoritme. [Jelektronnyj resurs] // Informacionnoe protivodejstvie ugrozam terrorizma. – 2005 g. – № 5. – S. 26–29. – Rezhim dostupa: https://elibrary.ru/item.asp?id9572194 (data obrashhenija: 23.03.2018).Семёнычев Е. В., Куркин Е. И., Данилова А. А. Выбор параметров генетических алгоритмов в задачах параметрической идентификации нелинейных моделей динамики // Вестник самарского муниципального института управления. – 2013г. – № 1(24). – С. 130–140. – Режим доступа: https://elibrary.ru/item.asp?id19024835 (дата обращения: 27.12.2017).Semjonychev E. V., Kurkin E. I., Danilova A. A. Vybor parametrov genetiche-skih algoritmov v zadachah parametricheskoj identifi nelinejnyh modelej dina-miki // Vestnik samarskogo municipal’nogo instituta upravlenija. – 2013 g. – № 1(24). – S. 130–140. – Rezhim dostupa: https://elibrary.ru/download/elibrary_19024835_95315377.pdf (data obrashhenija: 27.12.2017).Жеребцова О. В., Зубьяк Д. Р. Генетический алгоритм и его свойства для решения задачи поиска пустой прямоугольной области максимальной площади // Вестник Волжского университета им. В. Н. Татищева. – 2011г. – № 17. – С. 160–164. – Режим доступа: https://elibrary.ru/item.asp?id=16858033 (дата обращения: 23.03.2018).Zherebcova O. V., Zub’jak D. R. Geneticheskij algoritm i ego svojstva dlja reshenija zadachi poiska pustoj prjamougol’noj oblasti maksimal’noj ploshhadi // Vestnik Volzh-skogo universiteta im. V. N. Tatishheva. – 2011 g. – № 17. – S. 160–164.– Rezhim dostupa: https://elibrary.ru/item.asp?id= 16858033 (data obrashhenija: 23.03.2018).Мухамедиева Д. Т. Анализ особенностей генетических алгоритмов // Проблемы вычислительной и прикладной математики. – 2015г. – № 1(1). – Режим доступа: https://elibrary.ru/item.asp?id=25625477 (дата обращения: 23.03.2018).Muhamedieva D. T. Analiz osobennostej geneticheskih algoritmov // Problemy vychislitel’noj i prikladnoj matematiki. – 2015 g. – № 1(1). – Rezhim dostupa: https:// elibrary.ru/item.asp? id= 25625477 (data obrashhenija: 23.03.2018).Сапрыкин А. Н., Акинина К. Д., Сапрыкина Е. Н. Нахождение оптимального числа полезных особей в популяции и конвергируемых поколений генетического алгоритма оптимизации простых многоэкстремальных функций // ACTUALSCIENCE. – 2016г. – № 11. – Том 2. – С. 168–169. – Режим доступа: https://elibrary.ru/item.asp?id=27542766 (дата обращения: 23.03.2018).Saprykin A. N., Akinina K. D., Saprykina E. N. Nahozhdenie optimal’nogo chisla poleznyh osobej v populjacii i konvergiruemyh pokolenij geneticheskogo algoritma op-timizacii prostyh mnogojekstremal’nyh funkcij // ACTUALSCIENCE. – 2016 g. – № 11. – Tom 2. – S.168–169. – Rezhim dostupa: https://elibrary.ru/item.asp?id27542766 (data obra-shhenija: 23.03.2018).Сапрыкин А. Н., Акинина К. Д. Основные характеристики генетического алгоритма компоновки блоков электронно-вычислительных средств // Информационные технологии, межвузовский сборник научных трудов. – Рязань: Рязанский государственный радиотехнический университет. – 2017. – С. 128–132. – Режим доступа: https://elibrary.ru/item.asp?id=30470701 (дата обращения: 24.03.2018).Saprykin A. N., Akinina K. D. Osnovnye harakteristiki geneticheskogo algorit-ma komponovki blokov jelektronno-vychislitel’nyh sredstv // Informacionnye tehnolo-gii, mezhvuzovskij sbornik nauchnyh trudov. – Rjazan’: Rjazanskij gosudarstvennyj radio-tehnicheskij universitet. – 2017. – S. 128–132. – Rezhim dostupa: https://elibrary.ru/item.asp?id=30470701 (data obrashhenija: 24.03.2018).Сапрыкин А. Н., Акинина К. Д., Сапрыкина Е. Н. Оптимальное число конвергируемых поколений и полезных особей при варьирующихся значениях вероятности мутации генетического алгоритма на малых пространствах поиска // Современные технологии в науке и образовании – СТНО-2017 Сборник трудов II международной научно-технической и научно-методической конференции Том. 4. – Рязань: Рязанский государственный радиотехнический университет. – 2017. – С. 248–252. – Режим доступа: https://elibrary.ru/item.asp?id=29875353 (дата обращения: 24.03.2018).Saprykin A. N., Akinina K. D., Saprykina E. N. Optimal’noe chislo konvergiru-emyh pokolenij i poleznyh osobej pri var’irujushhihsja znachenijah verojatnosti mutacii geneticheskogo algoritma na malyh prostranstvah poiska // Sovremennye tehnologii v nauke i obrazovanii – STNO-2017 Sbornik trudov II mezhdunarodnoj nauchno-tehnicheskoj i nauchno-metodicheskoj konferencii Tom. 4. – Rjazan’: Rjazanskij gosudar-stvennyj radiotehnicheskij universitet. – 2017. – S. 248–252. – Rezhim dostupa: https://elibrary.ru/item.asp?id=29875353 (data obrashhenija: 24.03.2018).Федоренко К. В., Оловянников А. Л. Исследование основных параметров генетического алгоритма применительно к задаче поиска оптимального маршрута // Вестник Государственного университета морского и речного флота имени адмирала С. О. Макарова. – 2017. – Т. 9. – № 4. – С. 714–723. – Режим доступа: https://elibrary.ru/item.asp?id=29922476 (дата обращения: 24.03.2018).Fedorenko K. V., Olovjannikov A. L. Issledovanie osnovnyh parametrov geneti-cheskogo algoritma primenitel’no k zadache poiska optimal’nogo marshruta // Vestnik Gosudarstvennogo universiteta morskogo i rechnogo flota imeni admirala S. O. Makaro-va. – 2017. – T. 9. – № 4. – S. 714–723. – Rezhim dostupa: https://elibrary.ru/item.asp id=29922476 (data obrashhenija: 24.03.2018).Фролов В. В. Особенности реализации генетического алгоритма для проектирования технологических систем механической обработки // Восточно-Европейский журнал передовых технологий. – 2012. – № 3/9(57). – С. 60–64.Frolov V. V. Osobennosti realizacii geneticheskogo algoritma dlja proektiro-vanija tehnologicheskih sistem mehanicheskoj obrabotki // Vostochno-Evropejskij zhurnal peredovyh tehnologij. – 2012. – № 3/9(57). – S.60–64.

The authors declare that there are no conflicts of interest present.