Метод перекрестной энтропии (Cross-Entropy Method)

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

ВОЛГОГРАДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

(ВолгГТУ)

ФАКУЛЬТЕТ ЭЛЕКТРОНИКИ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ

Кафедра «Системы автоматизированного проектирования и поискового конструирования»

Реферат по дисциплине «Методы оптимизации»

Тема: «Метод перекрестной энтропии (Cross-Entropy Method)»

Выполнил:

Студент группы ----------

----------------

Проверила:

----------------

Волгоград 2021 г.

Оглавление

1.        Алгоритм перекрестной энтропии        3

1.1.        Принцип работы алгоритма        3

1.2.        Описание алгоритма        4

2.   Плюсы и минусы алгоритма        5

2.1.        Плюсы        5

2.2.        Минусы        5

3.        Код (Python)        5

1. Метод перекрестной энтропии. Определение

Метод перекрестной энтропии (CE) является популярным стохастическим методом оптимизации благодаря своей простоте и эффективности. Разработанный для моделирования редких событий, где вероятность наступления целевого события относительно мала, CE-метод опирается на достаточное количество вызовов целевой функции для точной оценки оптимальных параметров нормального распределения.                                 Метод EC может быть применен к любой комбинаторной задаче оптимизации, где наблюдения зашумлены, как задача коммивояжера ,            квадратичная оптимизация, проблема выравнивания последовательностей    ДНК, максимальное отсечение проблемы и проблемы  распределения памяти, а также непрерывная оптимизация и проблемы со многими локальными         экстремумами .

1. Принцип работы алгоритма

Впервые данный метод был предложен Рубенштейном в 1997 году. Изначально он был разработан для решения задач комбинаторной оптимизации, хотя позже был применен и для оптимизации непрерывных функций. Основная особенность метода заключается в апробировании точек исследуемого на оптимум пространства и аппроксимации распределения хороших точек (обычно нормальным законом). На каждом шаге алгоритма в соответствии с текущим распределением генерируются случайные точки, которые впоследствии участвуют в корректировке распределения. По ходу выполнения алгоритма, распределение становится все более «чистым» и устоявшимся, что впоследствии позволяет выбрать приближенное решение задачи оптимизации.
         Тот же алгоритм CE можно использовать для оптимизации и оценки. Рассмотрим задачу максимизации функции , например, чтобы использовать кросс-энтропию, мы должны сначала рассмотреть связанную стохастическую проблему оценки для данного уровня и семейство параметрических распределений вероятностей , например одномерное нормальное распределение , параметрами которого являются среднее значение и дисперсия (как здесь). Таким образом, для заданного, цель состоит в том, чтобы определить , чтобы количество было минимальным. Это делается с использованием выборочной версии (стохастический аналог) задачи минимизации расходимости KL, как и ранее на шаге 3. Оказывается, что для этого выбора распределения параметрами, которые минимизируют стохастическую версию проблемы, являются среднее значение и эмпирическая дисперсия. из элитного образца , который состоит из розыгрышей которого значение функции балла . Наихудший из элементов элитного образца используется в качестве параметра уровня в следующей итерации. Это дает следующий стохастический алгоритм решения этой проблемы.[pic 1]