Асимптотический вероятностный генетический алгоритм решения сложных задач глобальной оптимизации

• Автор: Галушин, Павел Викторович
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Красноярск
• Количество страниц: 118 с. : ил.

Содержание
Содержание
Введение
1 Асимптотический вероятностный генетический алгоритм псевдо-булевой оптимизации
1.1 Обзор существующих методов глобальной оптимизации
1.2 Асимптотическая мутация
1.3 Асимптотическая селекция
Выводы и результаты
2 Обобщения асимптотического вероятностного генетического алгоритма
2.1 Асимптотическая турнирная селекция
2.2 АВГА и ВГА для оптимизации функций целочисленных
(не бинарных) переменных
2.3 Учёт взаимосвязей между переменными в АВГА
Выводы и результаты
3 Программная реализация предложенных методов
3.1 Программная система «Асимптотический вероятностный генетический алгоритм»
3.2 Программная система «Глобальная оптимизация локальными и эволюционными многоагентными стохастическими алгоритмами (GOLEM-SA)»
3.3 Тестирование алгоритмов, не учитывающих взаимосвязи переменных

3.4 Тестирование алгоритмов, учитывающих взаимосвязи
переменных
Выводы и результаты
4 Эвристические алгоритмы динамического составления
расписаний
4.1 Динамическое составление расписаний
4.2 Применение рыночного алгоритма для управления цехом окраски грузовиков
4.3 Применение рыночного алгоритма для управления СКШ-системой
Выводы
Заключение
Список литературы
Список публикаций автора

Введение
Актуальность. Задачи оптимизации постоянно возникают в деятельности человека, в частности, при проектировании технических и социально-экономических систем: если существует возможность выбора параметров такой системы, то их следует выбрать оптимальным с точки зрения цели функционирования системы образом. Классические методы оптимизации накладывают существенные ограничения на целевую функцию задачи оптимизации: выпуклость, аналитическое задание функции и возможность вычисления вектора градиента в любой допустимой точке.
Однако многие возникающие задачи оптимизации не укладываются в эти рамки. Развитие техники и производства привело к появлению задач оптимизации, характеризующихся такими свойствами как алгоритмическое задание целевой функции, наличие большого количества локальных экстремумов, большая размерность и различный характер параметров (задача может одновременно иметь двоичные, целочисленные и вещественные параметры).
Важным классом методов оптимизации, способных решать такие задачи оптимизации являются эволюционные алгоритмы и, в частности, генетические алгоритмы (ГА), основанные на имитации эволюционных процессов, происходящих в природе.
Дальнейшим развитием данного направления стали алгоритмы оптимизации с оценкой распределения и вероятностный генетический алгоритм (ВГА), основная идея которых заключается в интерпретации эволюционных процессов, лежащих в основе ГА, с точки зрения теории вероятностей и математической статистики. В методах этого класса вместо генетического оператора скрещивания используется процедура оценки распределения вероятностей значений переменных и последующее порождение решений с заданным распределением.

Следствие.
lim D2n = 0.
N—¥ OO ’
Оценим теперь величину <Д]у(ж) в общем случае, то есть при I > 2.
Теорема 2.2. Пусть уДг) = г* (1 — г), тогда при х > t имеет место неравенство
(2.з)
Доказательство. При х € [£; Дг] имеет место следующее равенство:
<к,ы(х)
ж* ж-№~№
Покажем, что в данном выражении модуль можно опустить. Действительно, рассмотрим разность
х х — k x(N — к) — N(x — к) k(N — х)
— — L___i
N N-k N(N — к) N(N~k)-’ ~ ~
Из этого неравенства следует
%>j,0 Кроме того, можно получить следующее выражение для x/n: х х — к к („ х — к к х — к ( к
N N — к ' N N-к) N N — к
Перемножая неравенства (2.4) для к — 0, ..t — 1, получим