Більшість метаевристик, такі як еволюційні алгоритми, рій частинок, мурашина колонія, дозволяють досліджувати весь простір пошуку, але менш ефективні при вивченні його окремих невеликих ділянок. У методі оптимізації роєм часток якість локального пошуку можна поліпшити, використовуючи менші значення інерційного коефіцієнта w, однак це знижує ймовірність локалізації глобального рішення і викликає передчасну збіжність алгоритму. Тому локальний пошук краще здійснювати із застосуванням спеціально призначених для цього методів (градієнтний пошук, ньютонівські і квазіньютоновські методи). Одержуваний при такому способі гібридний алгоритм називається меметичним.
Одним з найбільш популярних і ефективних методів локального пошуку, що не вимагає обчислення похідних цільової функції є алгоритм Нелдера-Міда або, як його ще називають, метод деформованого багатогранника. Даний пошуковий алгоритм при своїй роботі використовує чотири основні операції: відображення, розтягнення, стиснення і редукцію симплекса.
Кількість вершин в багатограннику зазвичай вибирається на одиницю більше за розмірність простору пошуку. На кожній ітерації методу проводиться сортування наявних вершин за значенням функції, що оптимізується, і найгірша в сенсі значення цільової функції вершина відбивається через центр ваги інших вершин багатогранника. Якщо отримана після відображення точка буде краще всіх інших наявних в симплекс вершин, то багатогранник розтягується в напрямку цього перспективного напрямку пошуку. При невдалому відображенні проводиться його стиснення. У разі невдачі, це може означати, що пошук йде поблизу оптимальної точки і поточний багатогранник занадто великий для пошуку, координати всіх його точок, крім найкращої, перераховуються таким чином, що багатогранник стискається у напрямку до точки з мінімальним значенням функції. Дана операція називається редукцією симплекса.
Параметрами алгоритму Нелдера-Міда є коефіцієнти відображення, стиснення і розтягування, які зазвичай вибираються рівними 1, 0.5, 2 відповідно.
Перейти до розв'язання задачі: