ОПРЕДЕЛЕНИЕ РАЗМЕРА ПОПУЛЯЦИИ ГЕНЕТИЧЕСКОГО АЛГОРИТМА ДЛЯ ЗАДАЧ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ В САПР
https://doi.org/10.21122/2309-4923-2018-3-9-16
Аннотация
Предлагается метод определения размера популяции. Общий подход для определения размера популяции вытекает из утверждения, что хромосомы популяции должны содержать максимальное количество различных значений, которые покрывают большую часть области поиска. В основе метода лежит регрессионная модель, которая позволяет определить размер популяции в зависимости от допустимого количества значений независимой переменной. Регрессионная модель получена в результате обработки данных имитационного моделирования при формировании популяции для целевой функции с одной переменной. Задача решается для генетического алгоритма, где генотип представлен хромосомой в двоичном коде, а фенотип десятичным целочисленным кодом значений независимых переменных. Это позволяет моделировать формирование популяции без привязки к конкретным значениям переменных. Модель была получена для диапазона мощностей опорных множеств от 12 до 52, и позволяет прогнозировать размер популяции за границами этого диапазона. Основная область использования данного метода – это задачи дискретной оптимизации с целевыми функциями нескольких переменных, где области допустимых значений конечны и имеют небольшую размерность.
Об авторе
В. B. Фролов
Харьковский национальный университет имени В. Н. Каразина
Украина
Доктор технических наук, доцент, профессор кафедры теоретической и прикладной информатики
Украина
Доктор технических наук, доцент, профессор кафедры теоретической и прикладной информатики
Список литературы
1. Емельянов В. В., Курейчик В. В., Курейчик В. М. Теория и практика эволюционного моделирования. – М.: ФИЗМАТЛИТ, 2003. – 432 с.
2. Цой Ю. Р. Нейроэволюционный алгоритм и программные средства для обработки изображений. [Электронный ресурс]: дис. на соискание ученой степени канд. техн. наук: спец. 05.13.01 – Системный анализ, управление и обработка информации (отрасль: информация и информационные системы) / Ю. Р Цой. – Томск, 2007. – 209 с. – Режим доступа: http://qai.narod.ru/Dissertation/tsoy_phd.thesis.zip (дата обращения: 27.12.2017).
3. Чипига А. Ф., Петров Ю. Ю. Оценка выбора размера популяции в простом генетическом алгоритме. [Электронный ресурс] // Информационное противодействие угрозам терроризма. – 2005г. – № 5. – С. 26–29. – Режим доступа: https://elibrary.ru/item.asp?id=9572194 (дата обращения: 23.03.2018).
4. Семёнычев Е. В., Куркин Е. И., Данилова А. А. Выбор параметров генетических алгоритмов в задачах параметрической идентификации нелинейных моделей динамики // Вестник самарского муниципального института управления. – 2013г. – № 1(24). – С. 130–140. – Режим доступа: https://elibrary.ru/item.asp?id19024835 (дата обращения: 27.12.2017).
5. Жеребцова О. В., Зубьяк Д. Р. Генетический алгоритм и его свойства для решения задачи поиска пустой прямоугольной области максимальной площади // Вестник Волжского университета им. В. Н. Татищева. – 2011г. – № 17. – С. 160–164. – Режим доступа: https://elibrary.ru/item.asp?id=16858033 (дата обращения: 23.03.2018).
6. Мухамедиева Д. Т. Анализ особенностей генетических алгоритмов // Проблемы вычислительной и прикладной математики. – 2015г. – № 1(1). – Режим доступа: https://elibrary.ru/item.asp?id=25625477 (дата обращения: 23.03.2018).
7. Сапрыкин А. Н., Акинина К. Д., Сапрыкина Е. Н. Нахождение оптимального числа полезных особей в популяции и конвергируемых поколений генетического алгоритма оптимизации простых многоэкстремальных функций // ACTUALSCIENCE. – 2016г. – № 11. – Том 2. – С. 168–169. – Режим доступа: https://elibrary.ru/item.asp?id=27542766 (дата обращения: 23.03.2018).
8. Сапрыкин А. Н., Акинина К. Д. Основные характеристики генетического алгоритма компоновки блоков электронно-вычислительных средств // Информационные технологии, межвузовский сборник научных трудов. – Рязань: Рязанский государственный радиотехнический университет. – 2017. – С. 128–132. – Режим доступа: https://elibrary.ru/item.asp?id=30470701 (дата обращения: 24.03.2018).
9. Сапрыкин А. Н., Акинина К. Д., Сапрыкина Е. Н. Оптимальное число конвергируемых поколений и полезных особей при варьирующихся значениях вероятности мутации генетического алгоритма на малых пространствах поиска // Современные технологии в науке и образовании – СТНО-2017 Сборник трудов II международной научно-технической и научно-методической конференции Том. 4. – Рязань: Рязанский государственный радиотехнический университет. – 2017. – С. 248–252. – Режим доступа: https://elibrary.ru/item.asp?id=29875353 (дата обращения: 24.03.2018).
10. Федоренко К. В., Оловянников А. Л. Исследование основных параметров генетического алгоритма применительно к задаче поиска оптимального маршрута // Вестник Государственного университета морского и речного флота имени адмирала С. О. Макарова. – 2017. – Т. 9. – № 4. – С. 714–723. – Режим доступа: https://elibrary.ru/item.asp?id=29922476 (дата обращения: 24.03.2018).
11. Фролов В. В. Особенности реализации генетического алгоритма для проектирования технологических систем механической обработки // Восточно-Европейский журнал передовых технологий. – 2012. – № 3/9(57). – С. 60–64.
Рецензия
Для цитирования:
Фролов В.B. ОПРЕДЕЛЕНИЕ РАЗМЕРА ПОПУЛЯЦИИ ГЕНЕТИЧЕСКОГО АЛГОРИТМА ДЛЯ ЗАДАЧ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ В САПР. Системный анализ и прикладная информатика. 2018;(3):9-16. https://doi.org/10.21122/2309-4923-2018-3-9-16
For citation:
Frolov V.V. DETERMINING THE SIZE OF THE POPULATION OF THE GENETIC ALGORITHM FOR THE PROBLEMS OF DISCRETE OPTIMIZATION IN CAD. «System analysis and applied information science». 2018;(3):9-16. (In Russ.) https://doi.org/10.21122/2309-4923-2018-3-9-16
Просмотров:
1941
Послать статью по эл. почте 