Труды КНЦ вып.29 (ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ вып. 3/2015(29))

Следует отметить, что ГА - это целый класс алгоритмов, направленных на решение разнообразных задач комбинаторной оптимизации. Примерами различных ГА могут являться следующие алгоритмы [2]: • канонический ГА; • генитор; • метод прерывистого равновесия; • гибридный алгоритм; • СНС; • ГА с нефиксированным размером популяции. Имитация отжига Алгоритм имитации отжига (simulated annealing) основывается на понятии тепловой энергии, введенной С. Кирпатриком. Автор алгоритма использовал «тепловой шум» для выхода из одних локальных минимумов и для повышения вероятности попадания в более глубокие. При решении сложных задач, когда финансовые затраты на решение задачи оптимизации аналогичны энергии шарика, перемещающегося по поверхности, поиск более дешевых решений разумно начинать в ситуации с высоким уровнем «теплового шума», а в дальнейшем постепенно уменьшать его; этот процесс Кирпатрик назвал «имитацией отжига» [3]. Огромным преимуществом метода отжига является свойство избегать ловушек в локальных минимумах оптимизируемой функции, и продолжить поиск глобального минимума. Это достигается за счет принятия не только изменений параметров, приводящих к уменьшению значения функции, но и некоторых изменений, увеличивающих ее значение, в зависимости от температуры Т характеристики моделируемого процесса. Чем выше темпе­ ратура, тем большие ухудшающие изменения допустимы, и больше их вероятность. Еще одним преимуществом является то, что даже в условиях нехватки вычислительных ресурсов для нахождения глобального минимума, метод отжига, как правило, выдает неплохое решение (один из локальных минимумов). Метод служит для поиска глобального минимума некоторой функции fix ), заданной для х из некоторого пространства S. дискретного или непрерывного. Элементы множества S представляют собой состояния воображаемой физической системы (энергетические уровни), а значение функции / в этих точках используется как энергия системы E= fix ). В каждый момент предполагается заданной температура системы Т, как правило, уменьшающаяся с течением времени. После попадания в состояние х при температуре Т, следующее состояние системы выбирается в соответствии с заданным порождающим семейством вероятностных распределений g(x,T), которое при фиксированных х и Т задает случайный элемент G(x,T) со значениями в пространстве S. После генерации нового состояния x' = G(x,7), система с вероятностью h(AE; Т) переходит к следующему шагу в состояние х', в противном случае процесс генерации х' повторяется. Здесь АЕ обозначает приращение функции энергии fix') -fix). Величина h(AE; Т) называется вероят­ ностью принятия нового состояния. 63