Введение к работе
Актуальность. Задачи оптимизации постоянно возникают в деятельности человека, в частности, при проектировании технических и социально-экономических систем: если существует возможность выбора параметров такой системы, то их следует выбрать оптимальным с точки зрения цели функционирования системы образом. Классические методы оптимизации накладывают существенные ограничения на целевую функцию задачи оптимизации: выпуклость, аналитическое задание функции и возможность вычисления вектора градиента в любой допустимой точке. Однако многие возникающие задачи оптимизации не укладываются в эти рамки. Развитие техники и производства привело к появлению задач оптимизации, характеризующихся такими свойствами как алгоритмическое задание целевой функции, наличие большого количества локальных экстремумов, большая размерность и различный характер параметров (задача может одновременно иметь двоичные, целочисленные и вещественные параметры).
Важным классом методов оптимизации, способных решать такие задачи оптимизации являются эволюционные алгоритмы и, в частности, генетические алгоритмы (ГА), основанные на имитации эволюционных процессов, происходящих в природе. Дальнейшим развитием данного направления стали алгоритмы оптимизации с оценкой распределения и вероятностный генетический алгоритм (ВГА), основная идея которых заключается в интерпретации эволюционных процессов, лежащих в основе ГА, с точки зрения теории вероятностей и математической статистики. В методах этого класса вместо генетического оператора скрещивания используется процедура оценивания распределения вероятностей значений переменных и порождения решений с заданным распределением.
Однако существующие эволюционные методы оптимизации имеют большое количество настраиваемых параметров, что затрудняет их использование специалистами в прикладных областях, не являющимися экспертами в эволюционных методах оптимизации. Ситуацию ещё более усугубляет использование биологической терминологии при описании эволюционных алгоритмов. Кроме того, многие эволюционные алгоритмы (в частности, генетический алгоритм) определены так, что их программные реализации оказываются плохо приспособленными для современных ЭВМ (с конвейерной архитектурой и аппаратной многопоточностью).
Таким образом, разработка и исследование эволюционных алгоритмов, имеющих меньшее число настраиваемых параметров, имеющих ясную интерпретацию в терминах теории вероятности и эффективно использующих особенности архитектуры ЭВМ, является актуальной научно-технической задачей.
Целью работы является повышение эффективности решения сложных задач оптимизации эволюционными алгоритмами. Для достижения поставленной цели необходимо решить следующие задачи:
-
Выполнить обзор существующих методов глобальной оптимизации.
-
Разработать модификации существующих эволюционных алгоритмов, превосходящие существующие по быстродействию и эффективности.
-
Реализовать предложенные методы в виде программных систем.
-
Применить разработанные методы для решения практических задач оптимизации и сравнить с существующими методами по критериям эффективности и быстродействия.
Методы исследования. При выполнении диссертационной работы использовались методы теории оптимизации, теории вероятностей и математической статистики, системного анализа и исследования операций, теории эволюционных алгоритмов, дифференциального и интегрального исчисления, дискретной математики, методика создания прикладных интеллектуальных систем.
Научная новизна результатов диссертационной работы состоит в следующем:
-
Предложен новый асимптотический вероятностный генетический алгоритм (АВГА) псевдо-булевой оптимизации, превосходящий известные аналоги (ГА, ВГА и другие) по быстродействию и эффективности использования аппаратных средств ЭВМ, но не уступающий им по надёжности решения задач оптимизации.
-
Предложен новый способ учёта взаимосвязи между переменными, позволяющий повысить эффективность ВГА и АВГА.
-
Предложены модификации ГА, ВГА и АВГА, позволяющие эффективно решать задачи оптимизации с целочисленными переменными.
-
Предложена модификация рыночного алгоритма динамического составления расписаний, основанная на идее регуляризации функции предложения и позволяющая уменьшить время выполнения работ.
Теоретическая значимость результатов диссертационного исследования состоит в том, что разработаны, исследованы и апробированы новые эволюционные алгоритмы глобальной оптимизации, превосходящие существующие аналоги по эффективности и быстродействию.
Практическая значимость. Разработанные в ходе исследования алгоритмы реализованы в виде программ «Асимптотический вероятностный генетический алгоритм (APGA)» и «Глобальная оптимизация локальными и эволюционными мультиагентными стохастическими алгоритмами (GOLEM-SA)», зарегистрированных в Роспатенте (№2012612374, №2011611158). Данные программные системы позволяют пользователям, не являющимся экспертами в эволюционной оптимизации, эффективно решать сложные практические задачи глобальной оптимизации. Они прошли апробацию на ряде практических задач и продемонстрировали превосходство над существующими аналогами по надёжности и быстродействию.
Реализация результатов работы. Результаты работы вошли в отчёты по НИР № 2.1.1./2710 «Математическое моделирование инвестиционного развития региональных экономических систем» АВЦП «Развитие научного потенциала высшей школы (2009–2010 годы)», НК-136П/3 «Автоматизированная система решения сложных задач глобальной оптимизации многоагентными стохастическими алгоритмами» по направлению «Обработка, хранение, передача и защита информации» в рамках мероприятия 1.2.2 и НК-409П/49 «Разработка устойчивого гибридного генетического алгоритма для определения кристаллических структур химических соединений из данных порошковой дифракции» по направлению «Физические методы исследования химических соединений» в рамках мероприятия 1.2.1 Федеральной целевой программы «Научные и научно-педагогические кадры инновационной России на 2009–2013 годы». В 2011 году по результатам исследования диссертанту присуждена Государственная премия Красноярского края в области системного анализа.
Основные защищаемые положения:
-
Асимптотический вероятностный генетический алгоритм (АВГА) псевдо-булевой оптимизации превосходит наиболее часто используемые эволюционные алгоритмы оптимизации по эффективности, быстродействию и затратам памяти.
-
Модификации ВГА и АВГА, предназначенные для решения задач дискретной оптимизации, превосходят по эффективности свои аналоги, использующие бинарное кодирование решений.
-
Учёт взаимосвязи переменных задачи оптимизации в ВГА и АВГА позволяет повысить эффективность этих алгоритмов.
-
АВГА позволяет эффективно решать задачу настройки параметров рыночного алгоритма динамического составления расписания.
-
Регуляризация функции предложения позволяет повысить эффективность рыночного алгоритма динамического составления расписаний.
Публикации. По теме диссертации опубликовано тринадцать работ, в том числе пять в изданиях из перечня ВАК.
Апробация результатов работы. Результаты работы были представлены на Всероссийской научно-практической конференции «Актуальные проблемы авиации и космонавтики», Международных научно-практических конференциях «Решетневские чтения» (Красноярск, СибГАУ, 2005, 2006, 2009), на 11-й Международной конференции «Natural Computations» в Шанхае (КНР, 2011), на Международных конференциях «Distributed Computing and Artificial Intelligence» и «Hybrid Artificial Intelligence Systems» в Саламанке (Испания, 2012).
Структура работы. Диссертация состоит из введения, четырёх глав, заключения, списка литературы.
