Локальные оптимумы

Если программа заменяет случайно выбранную позицию в пробном решении, то может встретиться решение, которое она не может улучшить, но которое при этом не будет наилучшим из возможных решений. Например, рассмотрим список инвестиций, приведенный в табл. 8.5.

Предположим, что алгоритм случайно выбрал позиции A и B в качестве начального решения. Его стоимость будет равно 90 миллионам долларов, и оно принесет 17 миллионов прибыли.

Если программа удалит позиции A и B, то стоимость решения будет все еще настолько велика, что программа сможет добавить всего лишь одну позицию к решению. Так как наибольшую прибыль приносят позиции A и B, то замена их другими позициями уменьшит суммарную прибыль. Случайное удаление одной позиции из этого решения никогда не приведет к улучшению решения.

Наилучшее решение содержит позиции C, D и E. Его полная стоимость равно 98 миллионам долларов и суммарная прибыль составляет 18 миллионов долларов. Чтобы найти это решение, алгоритму бы понадобилось удалить из решения сразу обе позиции A и B и затем добавить на их место новые позиции.

Решения такого типа, для которых небольшие изменения решения не могут улучшить его, называются локальным оптимумом (local optimum). Можно использовать два способа для того, чтобы программа не застревала в локальном оптимуме, и могла найти глобальный оптимум (global optimum).

@Таблица 8.5. Возможные инвестиции

=============213

Во‑первых, можно изменить программу так, чтобы она удаляла более одной позиции во время случайных изменений. В этом примере, программа могла бы найти правильное решение, если бы она одновременно удаляла бы по две случайно выбранных позиции. Тем не менее, для задач большего размера, удаления двух позиций может быть недостаточно. Программе может понадобиться удалять три, четыре, или больше позиций.

Второй, более простой способ заключается в том, чтобы делать больше попыток, начиная с разных начальных решений. Некоторые из начальных решений будут приводить к локальным оптимумам, но одно из них позволит достичь глобального оптимума.

Программа Heur демонстрирует три стратегии последовательных приближений. При выборе метода Fixed 1 (Фиксированный 1) делается N попыток. Во время каждой попытки выбирается случайно решение, которое программа затем пытается улучшить за 2 * N попыток, случайно удаляя по одной позиции.

При выборе эвристики Fixed 2 (Фиксированный 2)делается всего одна попытка. При этом программа выбирает случайное решение и пытается улучшить его, случайным образом удаляя по одной позиции до тех пор, пока в течение N последовательных изменений не будет никаких улучшений.

При выборе эвристики No Changes 1 (Без изменений 1) программа выполняет попытки до тех пор, пока после N последовательных попыток не будет никаких улучшений. Во время каждой попытки программа выбирает случайное решение и затем пытается улучшить его, случайным образом удаляя по одной позиции до тех пор, пока в течение N последовательных изменений не будет никаких улучшений.

При выборе эвристики No Changes 2 (Без изменений 2)делается одна попытка. При этом программа выбирает случайное решение и пытается улучшить его, случайным образом удаляя по две позиции до тех пор, пока в течение N последовательных изменений не будет никаких улучшений.

Названия эвристик и их описания приведены в табл. 8.6.