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

У його базовому вигляді алгоритм можна описати таким чином. Спочатку генерується деяка множина векторів, так зване покоління. Під векторами розуміються точки ${\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}}$.

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

• Опис і реалізації методу на сайті одного із його авторів.
• S. Luke. Essentials of Metaheuristics. Розділ 3.4.