Оптимизация функций
Материал из Википедии — свободной энциклопедии
 |
Эта статья должна быть полностью переписана. На странице обсуждения могут быть пояснения. |
|
Эта статья или раздел нуждается в переработке. Пожалуйста, улучшите её в соответствии с правилами написания статей. |
На самом деле правильнее будет сказать "Поиск значений".
В первую очередь поиск минимума и максимума функции. Именно для задач поиска экстремумов функции и были разработаны генетических алгоритмов (далее ГА).
Методами ГА (теоретически) можно приближенно найти любой экстремум. В реальности получается найти подходящее решение для задач с размерностью в пределах 1000 (но тут многое зависит от самой задачи, её нелинейности, от скорости вычисления функции - чем ниже нелинейность и чем выше скорость вычисления, тем бОльшую размерность мы можем себе позволить).
1. Для нахождения экстремума функции все неизвестные в нашей функции кодируются "генами" (один ген - одна переменная).
2. Запускается генетический алгоритм.
3. ГА создает начальную популяцию особей и вычисляет значения функции, которые соответсвуют этим особям.
3. Среди наиболее удачных вариантов выбираются лучшие, производится их "скрещивание" и небольшая мутация. После этого вычисляется значения функции этих вариантов.
4. Пункт 3 повторяется до тех пор, пока значение функции нас неудовлетворяет.
Для задачи с размерностью 1000 нужно (ориентировочно) 5-10 миллионов вычислений функции. Исходя из этого можно попытаться определить время работы ГА.
Первое важное замечание: если у функции имеется несколько экстремумов, то классический ГА найдет один из них.
Второе важное замечение: ГА может не найти абсолютный минимум (максимум) функции, а найти один из локальных минимумов (такое случается при неудачно заданных параметрах ГА, недостаточном времени работы).
