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

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

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

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

Алгоритм

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

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

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

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

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

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

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

Примітки

1. Storn, Rainer and Price, Kenneth. Differential Evolution - A Simple and Efficient Adaptive Scheme for Global Optimization over Continuous Spaces, [ 24 квітня 2005 у Wayback Machine.] Technical Report TR-95-012 , ICSI, March 1995.
2. Storn, Rainer and Price, Kenneth. 10/01 - DE-Storn-Price-1997.pdf Differential Evolution - A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces. ^{[недоступне посилання з липня 2019]} (1997)
3. K. Price, R. Storn, J. Lampinen. Differential Evolution: A Practical Approach to Global Optimization. Springer, 2005.
4. . Архів оригіналу за 13 травня 2013. Процитовано 7 березня 2010.
5. . Архів оригіналу за 14 березня 2022. Процитовано 16 березня 2022.

Посилання

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