Разработка и исследование вероятностных эволюционных алгоритмов для моделирования и оптимизации сложных систем
Диссертация - Менеджмент
Другие диссертации по предмету Менеджмент
тму находить решение быстрее, чем МИВЕР (показано в численных экспериментах).
Попробуем проанализировать работу ГА с точки зрения теории псевдобулевой оптимизации, рассмотрим основные шаги ГА.
Инициализация. Если априорная информация о пространстве поиска отсутствует, то начальная популяция решений формируется случайно - точки распределяются равномерно в бинаризованном пространстве поиска, т.е. .
Оператор скрещивания - генетический оператор поиска, посредством которого из выбранных индивидов (родительские особи) получаются новые (потомки). Решение, представленное бинарным вектором является вершиной n-мерного гиперкуба в булевом пространстве. Оператор скрещивания будет генерировать точки из некоторого подмножества, размерность которого определяется числом совпадающих бит в соответствующих позициях родительских особей. Легко показать, что одноточечное или двухточечное скрещивание не может получить все точки полученного подпространства, равномерное - может.
Для примера рассмотрим действие оператора скрещивание при и родителях и . Потомок может унаследовать любые гены родителей, т.е. решение, полученное при скрещивании может содержать 0 или 1 в любой позиции. Однако, при применении одноточечного скрещивания будут получены решения: , , .
В общем случае, если даны и , где и , то с помощью равномерного скрещивания можно получить различных точек. При одноточечном скрещивании мы имеем эффективных точек разрыва, разрыв в остальных точках не даст новых точек. При каждом эффективном скрещивании мы получим 2 потомка, т.е. при одноточечном скрещивании можно получить всего новых точек.
Очевидно, что равномерное скрещивание является наиболее полным оператором, который в частном случае может получить и одноточечное, и многоточечное скрещивание. Т.о., с точки зрения широты охвата пространства поиска (разнообразия популяции) равномерное скрещивание предпочтительней. Исключением могут быть те случаи, когда известны свойства оптимизируемого функционала, и точечное скрещивание использует эти свойства.
Попробуем сформулировать равномерное скрещивание в негенетических терминах. Пусть для формирования потомка используется родителей (), где - размер популяции. Им соответствует статистика , где .
При статистика совпадает с . Потомок формируется в соответствии со статистикой . Такой оператор поиска соответствует теории генетических алгоритмов, содержит в себе свойства оператора скрещивания и имеет математически ясную формулировку.
Оператор мутации - оператор широкого поиска, т.к. в результате его применения возможно появление решений вне данной статистики. Если компонента вектора вероятностей обращается в 0 или 1, то поиск по компоненте вектора решения прекращается. Мутация предотвращает появление предельных значений компонент вектора вероятностей.
Оператор селекции - оператор, который каждому решению (в зависимости от качества решения) ставит вероятность быть отобранным. Наиболее приспособленные индивиды с большей вероятностью переходят в следующее поколение. На этом шаге происходит получение апостериорной информации о поисковом пространстве. В результате статистика меняется, компоненты вектора вероятностей смещаются в сторону распределения единичных компонент наиболее приспособленных решений.
1.4.1Общая схема вероятностного генетического алгоритма
Попробуем сформулировать в негенетических терминах алгоритм, имеющий общую с генетическим алгоритмом схему, сохраняющий свойства генетических операторов. Такой вероятностный генетический алгоритм (ВГА) применимо к задаче (2) имеет следующую схему:
1.Случайным образом формируются векторов . Вычисляется распределение , . Вычисляются соответствующие значения оптимизируемого функционала .
.На k-м шаге в соответствии с распределением формируются векторов .
.Случайным образом формируются новые решения: с вероятностью компоненты векторов меняются на противоположные.
.Вычисляются соответствующие значения функционала .
.Выбираются векторов из в соответствии с конкретным правилом отбора.
.Пересчитывается распределениеединичных компонент .
.Если не выполняется условие остановки, то , , повторить шаги 2 - 6.
Если априорная информация о пространстве поиска отсутствует, . На шаге 2 выполняется поиск в соответствии с имеющейся статистикой, аналогичный скрещиванию в ГА. На шаге 3 происходит поиск вне имеющейся статистики - оператор мутации. На шаге 5 происходит получение апостериорной информации, и происходит пересчет распределения вероятностей единичных компонент.
1.4.2Исследование работоспособности на тестовых задачах
Предложенный ВГА был реализован в программной системе ProbGA и апробирован на функциях 1-15. Результаты работы ВГА были сравнены с результатами работы стандартного ГА (таблица 3). Использовались следующие настройки: размер популяции - 50, максимальное число итераций - 50, число прогонов алгоритма - 50, мутация - высокая, селекция - ранговая.
Из таблицы видно, что ВГА превосходит обычный ГА: ВГА победил в 11 из 15 случаев (Ф3, Ф4, Ф6-Ф11,Ф13-Ф15), на Ф12 одинаково эффективен с ГА. В тех случаях, когда ВГА оказывается эффективней, разница в надежности существенная, когда побеждает обыкновенный ГА - ВГА проигрывает не значительно.
Обычный ГА выигрывает на функциях Ф1, Ф2 (многоэкстремальные функции одной переменной) и Ф5 (унимодальная, овражн