Уже довольно давно я занимаюсь исследованием алгоритмов нахождения глобального минимума функций от многих переменных.

Среди наиболее извесных являются градиентные методы, имитации отжига, генетические алгоритмы (далее ГА).

Коротко о преимуществах и недостатках.

1. Градиентные методы имеют очень хорошую скорость нахождения локального минимума, в котором и застревают. Данные методы (почти) не подходят для поиска глобального минимума.

2. Метод имитации отжига в какой-то степени напоминает блуждание броуновской частицы. Этот алгоритм очень неплохо ловит глобальный минимум при правильно настроенном параметре охлаждения.

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

Из всех упомянутых алгоритмов я использую комбинацию ГА и отжиг.

В начале августа 2009 года я наткнулся в сети на статью "Алгоритм пчел для оптимизации функции", в которой данный алгоритм преподносится как хороший. Короткое описание алгоритма пчел. Берется некий рой пчел, который выпускается на поле. Первый раз они летят в случайные места. После того, как они "возвращаются" они приносят информацию о значении функции в данной точке. Из всех точек выбираются несколько наиболее перспективных участков. На следующий день пчелы посылаются именно на эти участки, но каждая пчела с небольшим случайным смещением. Такие вылеты повторяются много раз. После каждого раза лучшие участки запоминаются. В данном месте есть тонкость: если два участка слишком близко находятся, то запоминается только лучший из них.

Казалось бы все просто, но есть несколько нюансов. Нужно определить следующие параметры: число областей, которые запоминаются, число пчел, радиус случайного поиска. Дополнительно к этому нужно определить каким образом мы будем считать области одинаковыми? Также нужно постепенно уменьшать радиус поиска (для более точного определения минимума) - это еще одна переменная. Таким образом набирается около 6 переменных, из которых 3-4 можно попытаться определить заранее в вычислительных экспериментах.

Короткий итог: алгоритм пчел похож на генетические алгоритмы, в котором выключено скрещивание. Итог второй: алгоритм пчел похож на алгоритм имитации отжига, но у пчел имеется несколько решений для улучшения, а у отжига только одно (два). Таким образом на сложных задачах (теоретически) алгоритм пчел будет уступать ГА, но выигрывать у отжига.

За один день неспеша я написал программу, которая ищет по данному алгоритму минимум функции от 18 переменных.

Вид функции

result:=10;
for I := 0 to 17 do if (x[i]<0) or (x[i]>1) then x[i]:=random; {проверка на границы 0..1}
for I := 0 to 17-3 do begin
  result:=result+sin(x[i]*i+x[i+1]+2*x[i+2])*sqr(x[i]);
end;

Как можно увидеть незначительное изменение одного из x[i] влечет за собой изменение трех слагаемых в функции.

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

На графике слева можно увидеть результаты нескольких запусков алгоритма пчел на тестовой функции. Вертикальный масштаб логарифмический. По горизонтали число вычислений функции (200 тысяч). Как видно из тестовых прогонов лучшее, что смог найти данный алгоритм в моем исполнении лежит около 0,89, но бывают случаи, когда алгоритм застревает на значении 1.5. Все запуски были осуществлены при одинаковых параметрах (50 участков и 90 пчел).

А вот на этом графике можно увидеть результаты нескольких запусков ГА на той же тестовой функции. Вертикальный масштаб логарифмический. По горизонтали число вычислений функции (200 тысяч). Как видно из тестовых прогонов лучшее, что смог найти ГА лежит около 0,35, но бывают случаи, когда алгоритм застревает на значении 0.8. Все запуски были осуществлены при одинаковых параметрах (50 хромосом ). Все остальные параметры были оставлены по умолчанию и специально под данную функцию не подгонялись (была включена адаптация мутации и поиск локальных минимумов алгоритмом имитации отжига)

Как мы можем видеть, алгоритм пчел показал существенно худшие результаты. Если я настройками этого алгоритма добиваюсь более быстрого спуска, то вероятность застрять в локальном минимуме увеличивается многократно. Вообще данный алгоритм показал себя неустойчивым и очень зависящим от настроечных коэффициентов (изменение одного из коэффициентов с 3,45 до 4,0 приводило к тому, что алгоритм сразу стабильно застревал в локальном минимуме).

Если будут читательские отклики, то данная тема будет продолжена.

Дата последней модификации страницы: 11.08.2009

Что еще есть у Владимира Чаплинского... (Back)