Сочетание градиентных и непрерывных генетических алгоритмов
Современный уровень технического прогресса характеризуется созданием и функционированием сложных технических систем (СТС). Сейчас все чаще при поиске оптимального решения в сложных технических системах приходится решать неформализованные задачи — с множеством вариантов, среди которых необходимо найти нужный. При решении сложных оптимизационных задач управления в СТС основной целью является поиск «лучшего» решения по сравнению с полученным ранее или заданным в качестве начального. Это связано с тем, что для сложной системы часто нужно найти хоть какое-нибудь удовлетворительное решение, а проблема достижения оптимума отходит на второй план.
Классические градиентные методы оптимизации благодаря своей детерминированности непригодны для поиска глобального экстремума многоходовой целевой функции, но имеют большую скорость нахождения локальных экстремумов. Эволюционные методы имеют элементы случайности, поэтому значительно более пригодные для поиска всех экстремумов как локальных, так и глобального, хотя и не гарантируют полного успеха. Но не детерминированность в генетических алгоритмах приводит к значительно большему времени вычислений (но гораздо меньшему, чем в случае прямого перебора).
Для преодоления этих недостатков предлагается объединить стохастические признаки эволюционных стратегий и детерминированность градиентных методов. Основная идея метода — это применение градиентных направлений целевой функции в точках родительской пары для оценки их пригодности к скрещиванию и определения координат точки-потомка.
Предложенный подход представляет собой сочетание градиентных и непрерывных генетических алгоритмов и позволяет избежать недостатков обоих методов.
Его суть состоит в применении градиентной процедуры скрещивания. Рассмотрим двумерный случай (рис. 1).
1. На пространстве поиска выбирают равномерную сетку начальных значений параметров (нулевое «поколение» точек) в количестве равном N. Для этих точек рассчитывают градиенты.
2. Следующее поколение точек находят попарным «скрещиванием» градиентов. Для двумерного случая этим поколением будет пересечение двух лучей, исходящих из каждой пары точек по направлениям градиентов.
3. Количество пересечений будет равно C^2 по основе N. Из них сразу исключают точки за пределами диапазона поиска, точки, возникшей на пересечении градиентных прямых в направлениях, противоположных градиентам, а также близко расположеных точек (заменяют на одну). Численность следующего поколения выбирают из оставшихся точек, а также из предыдущего поколения. Общее количество нового поколения не должно превышать N. Выбор точек следующего поколения происходит на основе приоритетов.
4. На каждой итерации (на каждом поколении) для лучших «представителей» применяют обычные градиентные методы поиска экстремумов.
Рис.1. Процедура градиентного скрещивания
Этот подход также позволяет получить неравномерную сетку значений целевой функции, похожую на сетку с адаптивным шагом, поскольку для каждого поколения вычисляется значение целевой функции как критерия «жизнеспособности» точки.
Было предложено сочетание градиентного и генетического алгоритмов. Это позволило нивелировать недостатки каждого из них: сложность нахождения глобального экстремума для градиентного алгоритма и большое время вычислений при генетическом алгоритме. Предложенный метод имеет такие преимущества: возможность найти все экстремумы и значительно повысить скорость их нахождения.
Классические градиентные методы оптимизации благодаря своей детерминированности непригодны для поиска глобального экстремума многоходовой целевой функции, но имеют большую скорость нахождения локальных экстремумов. Эволюционные методы имеют элементы случайности, поэтому значительно более пригодные для поиска всех экстремумов как локальных, так и глобального, хотя и не гарантируют полного успеха. Но не детерминированность в генетических алгоритмах приводит к значительно большему времени вычислений (но гораздо меньшему, чем в случае прямого перебора).
Для преодоления этих недостатков предлагается объединить стохастические признаки эволюционных стратегий и детерминированность градиентных методов. Основная идея метода — это применение градиентных направлений целевой функции в точках родительской пары для оценки их пригодности к скрещиванию и определения координат точки-потомка.
Предложенный подход представляет собой сочетание градиентных и непрерывных генетических алгоритмов и позволяет избежать недостатков обоих методов.
Его суть состоит в применении градиентной процедуры скрещивания. Рассмотрим двумерный случай (рис. 1).
1. На пространстве поиска выбирают равномерную сетку начальных значений параметров (нулевое «поколение» точек) в количестве равном N. Для этих точек рассчитывают градиенты.
2. Следующее поколение точек находят попарным «скрещиванием» градиентов. Для двумерного случая этим поколением будет пересечение двух лучей, исходящих из каждой пары точек по направлениям градиентов.
3. Количество пересечений будет равно C^2 по основе N. Из них сразу исключают точки за пределами диапазона поиска, точки, возникшей на пересечении градиентных прямых в направлениях, противоположных градиентам, а также близко расположеных точек (заменяют на одну). Численность следующего поколения выбирают из оставшихся точек, а также из предыдущего поколения. Общее количество нового поколения не должно превышать N. Выбор точек следующего поколения происходит на основе приоритетов.
4. На каждой итерации (на каждом поколении) для лучших «представителей» применяют обычные градиентные методы поиска экстремумов.
Рис.1. Процедура градиентного скрещивания
Этот подход также позволяет получить неравномерную сетку значений целевой функции, похожую на сетку с адаптивным шагом, поскольку для каждого поколения вычисляется значение целевой функции как критерия «жизнеспособности» точки.
Было предложено сочетание градиентного и генетического алгоритмов. Это позволило нивелировать недостатки каждого из них: сложность нахождения глобального экстремума для градиентного алгоритма и большое время вычислений при генетическом алгоритме. Предложенный метод имеет такие преимущества: возможность найти все экстремумы и значительно повысить скорость их нахождения.
0 комментариев