Диференціальна еволюція

Диференціальна еволюція (англ. differential evolution) — метод багатовимірної математичної оптимізації, що відноситься до класу стохастичних алгоритмів оптимізації (тобто працює з використанням випадкових чисел) і використовує деякі ідеї генетичних алгоритмів.

Це прямий метод оптимізації, тобто він вимагає тільки можливості обчислювати значення цільової функцій, але не її похідних. Метод диференціальної еволюції призначений для знаходження глобального мінімуму (або максимуму) недиференційованих, нелінійних, мультимодальних (що мають, можливо, велику кількість локальних екстремумів) функцій від багатьох змінних. Метод простий у реалізації та використання (містить мало керуючих параметрів, що потребують підбору), легко розпаралелюється.

Метод диференціальної еволюції був розроблений Рейнером Сторно і Кеннетом Прайсом, вперше опублікований ними в 1995 році і розроблений в подальшому в їх пізніших роботах.

Алгоритм

У його базовому вигляді алгоритм можна описати таким чином. Спочатку генерується деяка множина векторів, так зване покоління. Під векторами розуміються точки $n$-вимірного простору, в якому визначена цільова функція $f(x)$, яку потрібно мінімізувати. На кожній ітерації алгоритм генерує нове покоління векторів, випадковим чином комбінуючи вектори з попереднього покоління. Число векторів в кожному поколінні одне й те саме і є одним з параметрів методу.

Нове покоління векторів генерується в такий спосіб. Для кожного вектора $x_{i}$ зі старого покоління вибираються три різних випадкових вектори $v_{1}$, $v_{2}$, $v_{3}$ серед векторів старого покоління, за винятком самого вектора $x_{i}$, і генерується так званий мутантний вектор за формулою:

$v=v_{1}+F\cdot (v_{2}-v_{3}),$

де $F$ — один з параметрів методу, деяка позитивна дійсна константа в інтервалі [0, 2].

Над мутантним вектором $v$ виконується операція «схрещування» (англ. crossover), яка полягає в тому, що деякі його координати заміщаються відповідними координатами з початкового вектора $x_{i}$ (кожна координата заміщається з деякою ймовірністю, яка також є ще одним з параметрів цього методу). Отриманий після схрещування вектор називається пробним вектором(англ. trial vector). Якщо він виявляється кращим за вектор $x_{i}$ (тобто значення цільової функції стало меншим), то в новому поколінні вектор $x_{i}$ замінюється на пробний вектор, а в іншому разі — залишається $x_{i}$.

Приклади практичних застосувань

Пошукова система Яндекс використовує метод диференціальної еволюції для поліпшення своїх алгоритмів ранжування.

Посилання

• Опис і реалізації методу на сайті одного із його авторів. [Архівовано 1 грудня 2005 у Wayback Machine.]
• S. Luke. Essentials of Metaheuristics. [Архівовано 22 листопада 2009 у Wayback Machine.] Розділ 3.4.