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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

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

Алгоритм[ред.ред. код]

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

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

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

Примітки[ред.ред. код]

Посилання[ред.ред. код]