УДК 519.6

Звонков В.Б.

ОБЗОР ВОЗНИКНОВЕНИЯ, РАЗВИТИЯ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ И НЕКОТОРЫХ МОДИФИКАЦИЙ

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Сибирский государственный аэрокосмический университет имени академика М.Ф. Решетнева», Россия, г. Красноярск

Данная работа посвящена литературному обзору работ по возникновению и развитию генетических алгоритмов, а также актуальным модификациям для различных классов задач, в том числе разработанных автором настоящей статьи.

Ключевые слова: генетический алгоритм, безусловная, условная, однокритериальная, многокритериальная оптимизация, обучение искусственной нейронной сети.

This paper is devoted the literary review of scientific works associated with creating, developing genetic algorithms and also actual modifications for various classes of problems including developed by the author of this article.

Keywords: genetic algorithm, unconstrained, constrained, one-criterion, multi-objective optimization, training of artificial neural network.

В настоящей работе автором был выполнен краткий литературный обзор возникновения и развития генетических алгоритмов с периода 1975 года по настоящее время. Выполненный литературный обзор доказывает актуальность данного направления исследований, а также применимость модификаций эволюционных алгоритмов к различным классам задач: функциональная оптимизация и оптимизация запросов в базах данных, синтез и оптимизация систем управления и вычислительных систем, составление расписаний, задачи классификации, многокритериальные задачи, транспортные задачи, задача коммивояжера, раскраска графов, настройка и обучение искусственных нейронных сетей с помощью ЭВМ, теория игр и игровое моделирование, биоинформатика, искусственная жизнь и т.д.

В статье приводится описание основных идей функционирования стандартного генетического алгоритма, а также разработанных модификаций эволюционных алгоритмов, в том числе разработанных автором статьи.

Самонастраивающийся генетический алгоритм, разработанный для класса задач однокритериальной оптимизации обеспечивает автоматическую настройку параметров генетического алгоритма в ходе решения оптимизационной задачи с использованием всех возможных комбинаций настраиваемых параметров. Выбор настроек осуществляется стохастическим образом в соответствии с полученным дискретным распределением вероятностей настроек в процессе решения задачи оптимизации, без использования априорной информации об эффективности операторов генетического алгоритма и свойствах задачи.

В классическом генетическом алгоритме отсутствует схема учета ограничений задачи оптимизации. Устранить данный недостаток можно несколькими способами: добавление в стандартный генетический алгоритм механизмов учета ограничений в виде штрафных функций (статические, динамические, адаптивные, смертельные штрафы) или специализированных генетических операторов (лечение, поведенческая память).

Для решения задач класса многокритериальной оптимизации была разработана адаптивная гибридная стохастическая процедура, использующая основные идеи процедуры самонастройки, метода учета многокритериальности задачи SPEA, процедур «лечения» индивидов и процедуры дальнейшего использования улучшенных индивидов.

Также в статье показана целесообразность и возможность использования разработанных модификаций эволюционных алгоритмов для задачи обучения искусственной нейронной сети (модель персептрона Розенблатта).

Приоритетным направлением дальнейших исследований обозначена разработка и апробация эволюционных алгоритмов, полностью автоматизирующих выбор структуры искусственной нейронной сети и настройку ее параметров.