SIMULATION MODEL OF A CONTROLLED GENETIC ALGORITHM BASED ON PETRI NETS

Petrosov D.A.

Abstract


When the genetic algorithm is operating while solving the problems in various subject areas, the problem of changing the order of actuation and parameters of the algorithm operator functioning appears. It is related with the fact that in operation the evolution procedure may come across the population hitting the local extremum, fading, etc. The way out of the current situation can be the increase of damaging capability of the operator. The damaging capability can be increased by changing the parameters of operator functioning, types of operators and actuation order. When high damaging capability of operators is applied, situations are possible when the time for solution search is considerably increased, since dispersion of values of the target function for population individuals grows up significantly. In this case, it is reasonable to decrease the damaging capability thus leading to a more detailed investigation of the search space. Since this procedure is required to be performed directly in the process of solution search, the development of new models and methods of genetic algorithm control is needed. In this work it is proposed to apply the neural network approach to solving the problem of evolution procedure control. For this purpose it is required to carry out adaptation of both the genetic algorithm and artificial neural networks. It is proposed to apply the Petri net theory as the main mathematical apparatus to describe the controlled genetic algorithm. The paper presents the imitation model of the evolution procedure based on the Petri net theory that allows for performing the variation of parameters of operator functioning during the search of solutions.

Keywords


simulation modeling; artificial neural networks; genetic algorithms; intelligent systems of decision support; system analysis; Petri net theory

Full Text

Введение В настоящее время генетические алгоритмы получили широкое распространение как интеллектуальное инструментальное средство для систем поддержки принятия решений в различных предметных областях. Данная эволюционная процедура относится к эвристическим алгоритмам, которые базируются на механизмах, схожих с природными механизмами естественного отбора: наследование, мутации, отбор и скрещивание. При использовании генетического алгоритма возникает задача его адаптации к решаемой задаче, а данная процедура является сложной и связана с подбором типов операторов и параметрами их функционирования [1-3]. В интеллектуальных системах поддержки принятия решений такого рода настройки выполняются экспертами, которые должны владеть знаниями в области эволюционных процедур и предметной области (рис. 1). Однако выполненная адаптация может терять свою актуальность ввиду изменений в элементной базе и критериях поиска. Это связано с затуханием генетического алгоритма, а также потерей времени из-за попадания популяции в локальные экстремумы. В этом случае классическим выходом из сложившейся ситуации является изменение параметров функционирования операторов с привлечением экспертов и перезапуск процедуры поиска. Данный подход не позволяет эволюционной процедуре адаптироваться к синтезу решений и является трудоемким. Поэтому целесообразно разрабатывать методы, которые позволят управлять генетическим алгоритмом непосредственно в процессе поиска решений и в промежутках между ними. Для этого предлагается использовать математический аппарат искусственных нейронных сетей как средство управления интеллектуальным методом в системах поддержки принятия решений. Рис. 1. Пример использования генетического алгоритма Основной раздел В работе предлагается использовать искусственные нейронные сети для управления генетическим алгоритмом. Для этого требуется модернизировать его работу (рис. 2). Нейронная сеть должна выполнять задачу изменения параметров работы операторов на основе анализа состояния генетического алгоритма. Так как данный математический аппарат хорошо зарекомендовал себя в распознавании образов, то целесообразно представлять состояние генетического алгоритма в графическом виде [4, 5] и на его основе принимать решение об изменении параметров работы операторов. Рис. 2. Модернизированная работа генетического алгоритма с применением искусственных нейронных сетей в качестве средства управления параметрами операторов На рис. 3 показан пример подготовленного изображения, которое состоит из двух частей: · в верхней части графика - минимальное значение целевой функции; · в нижней - количество особей с минимальным значением целевой функции. Данный рисунок позволяет нейронной сети оценить состояние популяции. Как видно из рисунка, в генетическом алгоритме наметилась тенденция схождения, так как количество особей с минимальным значением функции, равным нулю, растет, и вмешательство в процесс не требуется. На рис. 4 показано изображение, на основании которого нейронная сеть должна принять решение об изменении параметров работы операторов генетического алгоритма. Рис. 3. Пример подготовленного изображения для нейронной сети (тенденция к схождению) Рис. 4. Пример подготовленного изображения для нейронной сети (затухание генетического алгоритма) Тенденция затухания может определяться сетью на основании того, что количество особей с минимальным значением функции приспособленности, отличным от нуля, растет, а само минимальное значение фитнес-функции не изменяется при обработке большого количества популяций. Таким образом, можно говорить о возможности анализа состояния популяции в процессе поиска решений и построить модель управляемого с помощью нейросетевого подхода генетического алгоритма. При решении задачи управления генетическим алгоритмом в процессе синтеза решений целесообразно рассмотреть работу операторов: , где Sel - оператор отбора; Cross - оператор скрещивания; Mut - оператор мутации; Red - оператор редукции. Каждый оператор имеет разные параметры функционирования. Под параметрами операторов будем понимать следующее. Оператор Sel: · турнирный отбор; · рулеточный отбор; · комбинированный (на основе турнирного и рулеточного) и т. д. Оператор Cross: · одноточечный; · двухточечный; · многоточечный и т. д. Оператор Mut: · однопозиционная мутация; · многопозиционная мутация; · вероятность срабатывания оператора мутации и т. д. Оператор Red: · оставить в популяции определенное количество особей со значением функции приспособленности не ниже заданного порога; · оставить все особи в популяции не зависимо от значения целевой функции и т. д. В зависимости от выбранного параметра работы оператора изменяется его разрушающая способность, то есть способность изменять бинарную строку хромосомы, что в свою очередь влияет на движение популяции в пространстве решений. В этом случае операторы можно представить в следующем виде: , где - i-й параметр функционирования оператора Sel; , где - j-й параметр функционирования оператора Cross; , где - k-й параметр функционирования оператора Mut; , где - o-й параметр функционирования оператора Red. Тогда генетический алгоритм можно представить как комбинацию параметров его операторов: . В качестве инструментального имитационного моделирования генетического алгоритма и искусственных нейронных сетей предлагается использование теории сетей Петри. Сеть Петри - это двудольный ориентированный граф, состоящий из вершин двух типов - позиций и переходов, соединенных между собой дугами. , где P - позиции, T - переходы, L - отношение между вершинами, соответствующее дугам графа. Также используется маркировка сети - функция M, которая каждой позиции ставит в соответствие целое неотрицательное число. Маркировку можно характеризовать вектором , где n - число позиций в сети. В графическом отображении маркировке M соответствует число меток в позициях сети Петри [6-8]. При создании имитационной модели управляемого генетического алгоритма на основе сетей Петри будем использовать вложенные сети Петри, в которых метка верхнего уровня сама является сетью Петри. Переходы верхнего уровня моделируют работу операторов эволюционной процедуры, а позиции служат для хранения меток, которые в свою очередь являются моделями особей популяции. Тогда имитационную модель генетического алгоритма можно представить следующим образом: , где P - позиции сети; T - переходы сети; L - соединительные дуги; M0 - начальная маркировка сети. Позиции требуется разделить на два типа: позиции для хранения популяции и позиции для управления параметрами работы операторов. , где позиции для хранения популяции: - множество позиций для хранения популяции особей в слое Sel; - множество позиций для хранения популяции особей в слое Cross; - множество позиций для хранения популяции особей в слое Mut; - множество позиций для хранения популяции особей в слое Red. Позиции для управления параметрами работы операторов: - множество позиций для подключения требуемого перехода (оператора с определенным параметром функционирования) в слое Sel; - множество позиций для подключения требуемого перехода (оператора с определенным параметром функционирования) в слое Cross; - множество позиций для подключения требуемого перехода (оператора с определенным параметром функционирования) в слое Mut; - множество позиций для подключения требуемого перехода (оператора с определенным параметром функционирования) в слое Red. Переходы Т могут моделируют работу операторов с различными параметрами функционирования. , где - переходы, моделирующие работу оператора Sel с определенным параметром функционирования R; - переходы, моделирующие работу оператора Cross в подключенном слое S с определенным параметром функционирования J; - переходы, моделирующие работу оператора Mut в подключенном слое J с определенным параметром функционирования M; - переходы, моделирующие работу оператора Red с определенным параметром функционирования U. Кроме позиций и переходов в имитационной модели генетического алгоритма на основе сетей Петри требуется определить соединительные дуги L. , где - включенные дуги, по которым проходят метки (достигается за счет «возбуждения» перехода путем помещения метки от управляющей нейронной сети в соответствующую позицию управления); - выключенные дуги (соединенные с позицией управления в которой отсутствуют метки). Значение М0 соответствует начальной маркировке разрабатываемой модели на основе сетей Петри. На рис. 5 показана разработанная имитационная модель генетического алгоритма на основе вложенных сетей Петри с возможностью управления параметрами функционирования операторов. Управление происходит следующим образом: · Модель искусственной нейронной сети на основе информационных сетей Петри [9, 10] подключается к представленной на выделенные позиции управления (в начале работы подключены переходы с функциями оператора, определенные экспертом на рис. 5 это , , , . Для подключения используется разное число меток, так как количество переходов в слоях разное). · Вводятся критерии поиска. · Выполняется запуск модели. · Модель нейронной сети анализирует состояние популяции и генетического алгоритма. · Модель нейронной сети помещает метки в управляющие позиции, тем самым активирую требуемый переход с параметром работы оператора (увеличивая или уменьшая разрушительную способность оператора). · Модель работает до выполнения условия останова. Таким образом, получена имитационная модель управляемого генетического алгоритма на основе теории сетей Петри. Рис. 5. Имитационная модель управляемого генетического алгоритма с резервом позиций для соединения с моделью искусственной нейронной сети Анализ результатов Как видно из приведенной имитационной модели, существует возможность создания управляемого генетического алгоритма. Предложенная модель позволяет выполнять адаптацию и настройку эволюционной процедуры непосредственно в процессе поиска решений при решении различных классов задач. Для этого требуется провести исследование различные состояния генетического алгоритма с применением средств имитационного моделирования и ряда вычислительных экспериментов. Полученные данные могут быть использованы для создания алфавита на основе предложенного подхода по анализу состояния популяции, что позволит повысить быстродействие интеллектуальных систем поддержки принятия решений и качество полученных результатов. Применение единого математического аппарата теории сетей Петри для описания работы эволюционных процедур: генетического алгоритма и искусственных нейронных сетей, что позволяет применять свойство параллелизма, которым обладают оба интеллектуальных алгоритма. Данный подход позволяет использовать технологию GPGPU (General-purpose computing for graphics processing units, неспециализированные вычисления на графических процессорах) [11, 12], что в свою очередь позволит повысить быстродействие интеллектуальных систем поддержки принятия решений, не только применяя новые математическое модели, но и за счет минимальных финансовых вложениях в аппаратную часть вычислительных систем. Выводы Основным результатом данной работы является создание имитационной модели управляемого генетического алгоритма с применением теории сетей Петри. Управление достигается за счет изменения параметров функционирования или изменения типов операторов генетического алгоритма: увеличивая или уменьшая их разрушающую способность. Для этого в имитационной модели выделены переходы и управляющие позиции. В работе приведены примеры изображений, на основе которых искусственная нейронная сеть может принять решение об изменении параметров работы эволюционной процедуры или о невмешательстве. Предлагается создание управляемого генетического алгоритма, направленного на решения задач в различных предметных областях. При использование единого математического аппарата теории сетей Петри возможно создание моделей, которые будут обладать свойством параллелизма, что даст возможность использовать технологии параллельного программирования.

Galleys

PDF (Русский)
References References

Evolutionary synthesis of large discrete systems with dynamic structure / D.A. Petrosov, V.A. Lomazov, A.I. Dobrunova et al. // Biosciences Biotechnology Research Asia. 2015. Vol. 12. No. 3. Pp. 2971-2981.

Интеллектуальные подходы к созданию советующей системы управления вращающейся цементной печью обжига клинкера / А. Г. Бажанов, А. С. Копылов, В. А. Порхало и др. // Цемент и его применение. 2013. № 3. С. 77-80.

О применении эволюционных алгоритмов при анализе больших данных / К. Ю. Брестер, В. В. Становов, О. Э. Семенкина, Е. С. Семенкин // Искусственный интеллект и принятие решений. 2017. № 3. С. 82-93.

Положение модели искусственной нейронной сети в медицинских экспертных системах / Ю. А. Волчек, О. Н. Шишко, О. С. Спиридонова, Т. В. Мохорт // Juvenis scientia. 2017. № 9.

Манжула В. Г., Федяшов Д. С. Нейронные сети Кохонена и нечеткие нейронные сети в интеллектуальном анализе данных // Фундаментальные исследования. 2011. № 4. С. 108-114.

Lomazova I. A., Popova-Zeugmann L. Controlling Petri Net Behavior using Priorities for Transitions // Fundamenta Informaticae. 2016. Vol. 143. No. 1-2. Pp. 101-112.

Lomazova I. A. Resource Equivalences in Petri Nets, in: Application and Theory of Petri Nets and Concurrency // 38th International Conference, PETRI NETS 2017, Zaragoza, Spain, June 25-30, 2017, Proceedings / Ed. By W. van der Aalst, E. Best. Vol. 10258: Lecture Notes in Computer Science. Switzerland : Springer, 2017. Pp. 19-34.

Петросов Д. А., Игнатенко В. А. Применение информационных сетей Петри для моделирования нейронной сети в задаче управления адаптированным генетическим алгоритмом при решении задач структурно-параметрического синтеза дискретных систем // Успехи современной науки и образования. 2016. Т. 5. № 12. С. 138-141.

Там же.

Игнатенко В. А., Магергут В. З. Информационная сеть Петри как инструмент для параллельной обработки алгоритмов управления // Научные ведомости БелГУ. История, Политология, Экономика, Информатика. 2011. № 19. С. 119-126.

Lomazova I. A. Resource Equivalences in Petri Nets, in: Application and Theory of Petri Nets and Concurrency // 38th International Conference, PETRI NETS 2017, Zaragoza, Spain, June 25-30, 2017, Proceedings / Ed. By W. van der Aalst, E. Best. Vol. 10258: Lecture Notes in Computer Science. Switzerland : Springer, 2017. Pp. 19-34.

Петросов Д. А., Игнатенко В. А. Применение информационных сетей Петри для моделирования нейронной сети в задаче управления адаптированным генетическим алгоритмом при решении задач структурно-параметрического синтеза дискретных систем // Успехи современной науки и образования. 2016. Т. 5. № 12. С. 138-141.




DOI: http://dx.doi.org/10.22213/2410-9304-2019-1-63-70

Article Metrics

Metrics Loading ...

Metrics powered by PLOS ALM

Refbacks

  • There are currently no refbacks.


Copyright (c) 2019 Петросов Д.А.

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

ISSN 1813-7911