Составители:
Рубрика:
149
лютного нуля, она может как повышаться, так и понижаться. За
счет удержания температуры процесса вблизи от значения, соответ"
ствующего уровню термического равновесия, удается обходить ло"
вушки локальных максимумов. Метод имитации отжига представ"
ляет собой алгоритмический аналог физического процесса управляе"
мого охлаждения. Предложенный Н. Метрополисом в 1953 г. и дорабо"
танный многочисленными последователями, он в настоящее время счи"
тается одним из немногих алгоритмов, позволяющих практически на"
ходить глобальный минимум функции нескольких переменных.
В описании алгоритма в качестве названия параметра, влияюще"
го на вероятность увеличения значения целевой функции, использу"
ется термин «температура», хотя с формальной точки зрения приве"
денная модель оптимизации является только математической ана"
логией процесса отжига. Алгоритм имитации отжига выглядит кон"
цептуально несложным и логически обоснованным. В действитель"
ности приходится решать много фундаментальных проблем, кото"
рые влияют на его практическую применимость. Основной следует
назвать проблему длительности имитации. Для повышения вероят"
ности достижения глобального минимума длительность отжига (пред"
ставляемая количеством циклов, повторяемых при одном и том же
значении температуры) должна быть достаточно большой, а коэф"
фициент уменьшения температуры – низким. Это увеличивает про"
должительность процесса моделирования, что может дискредитиро"
вать его с позиций практической целесообразности.
Метод имитационного отжига исключает большинство недостат"
ков метода подъема на холм: решение не зависит от начальной точки
и обычно является близким к оптимальной точке. Это достигается
введением вероятности р замены текущей точки новой точкой: р = 1,
если новая точка обеспечивает лучшее значение целевой функции;
однако p > 0 в противоположной ситуации. В последнем случае веро"
ятность р зависит от значений целевой функции для текущей и но"
вой точек и управляющего параметра температуры. Во время работы
метода температура понижается ступенями, и алгоритм завершает"
ся при некотором малом значении температуры.
Отличия ГА от традиционных методов поиска состоят в следующем:
– для поиска оптимума используют несколько точек одновремен"
но, а не переходят от точки к точке, как это делается в традиционных
методах, что позволяет избежать опасности попадания в локальный
экстремум целевой функции, если она не является унимодальной, т. е.
имеет несколько таких экстремумов. Использование нескольких то"
чек одновременно значительно снижает такую возможность;
Страницы
- « первая
- ‹ предыдущая
- …
- 147
- 148
- 149
- 150
- 151
- …
- следующая ›
- последняя »
