Метода - случайный поиск
Cтраница 1
Методы случайного поиска отличаются от регулярных ( детерминированных) методов оптимизации намеренным введением элемента случайности. Это означает, что в одной и той же обстановке решение о направлении рабочего шага, принятое по методу случайного поиска, будет разным. Однако подобное случайное поведение является не только целесообразным, но в большом числе случаев и более эффективным, чем регулярное поведение. [1]
Методами случайного поиска, особенно при использовании алгоритмов с самообучением, могут решаться довольно сложные задачи. Наиболее эффективно использование случайных методов при большом числе регулируемых параметров. Исследования, проведенные Л. А. Растригиным [38], показали, что градиентный и случайный методы поиска имеют одинаковую эффективность при трех регулируемых параметрах. При меньшем числе параметров более эффективен регулярный поиск, при большем - случайный. Однако выбор метода поиска необходимо производить обязательно с учетом объекта регулирования и условий работы. [2]
В методе случайного поиска число требуемых вычислений целевой функции резко увеличивается с возрастанием размерности решаемой задачи. Частично эти трудности устраняются использованием переменного шага. [3]
В методе случайного поиска шаг поиска является случайным вектором в пространстве выбираемых параметров. Целесообразно, чтобы исходное распределение поисковых векторов обеспечивало равную вероятность перемещения в любом направлении. [4]
К методам случайного поиска относятся и методы статистического градиента и статистического наискорейшего спуска. Суть методов заключается в том, что из исходной точки производится несколько случайных проб, определяется приращение показателя качества и образуется векторная сумма приращений. Направление градиента выбирается по направлению вектора суммы. В остальном алгоритм соответствует алгоритмам поиска по методу градиента и методу наискорейшего спуска. [5]
В методах случайного поиска организуется случайный перебор точек множества X такой, что существует положительная вероятность выбора любого из допустимых решений. Более подробно методы случайного поиска будут изложены в главе III, посвященной методам стохастического программирования. [6]
В методах случайного поиска в этот процесс вносится элемент случайности. В методах первого порядка переход от вектора xt к вектору xt i производится с использованием первой производной от целевой функции в точке, определяемой вектором внутренних параметров xt, а в методах второго порядкас этой же целью вычисляют вторую производную в этой же точке. В задачах многомерного поиска с целевыми функциями сложного вида применение методов безусловной оптимизации первого и второго порядков нецелесообразно. Методы нулевого порядка проще программируются и требуют меньших затрат машинного времени. [7]
Алгоритмы, реализующие методы случайного поиска, обладают большей универсальностью, чем алгоритмы, основанные на регулярных поисковых процедурах, поскольку общая структура таких алгоритмов в принципе не зависит от свойств данной конкретной модели оптимизации и определяется свойствами класса моделей в целом. [8]
Наиболее часто применяются Методы случайного поиска и градиентные методы. Случайный поиск позволяет весьма эффективно отсекать локальные экстремумы и находить решение при достаточно гладких помехах. Градиентные методы сравнительно легко программируются и оказываются довольно эффективными, хотя и позволяют найти лишь локальный экстремум. Сочетание случайного поиска ( на первых шагах алгоритмов) с градиентными методами, а также применение методов крутого восхождения и перебора гребней обычно позволяют получить хороший алгоритм. [9]
К таким алгоритмам относятся методы случайного поиска, методы прямого перебора. [10]
В наиболее чистом виде метод случайного поиска применительно к задачам целочисленного линейного программирования с булевыми переменными был развит в работе Пятецкого-Шапиро, Волконского, Левиной и Поманского [25] ( см. § 1 гл. [11]
При оптимизации динамических систем метод случайного поиска уступает методу наискорейшего спуска и релаксационному методу. Действительно, если в последних изменение параметров подчинено определенной логической последовательности, то метод случайного поиска основан на простом угадывании значений параметров. Если каждый процесс решения задачи на АВМ длится несколько секунд, то такой способ минимизации приводит к перерасходу машинного времени. [12]
Во всех методах, кроме метода случайного поиска, следующие точки определяются ранее полученными значениями функции, а также вектор-градиентов или матриц Гессе. Вледствие этого указанные методы в областях, где трудно ожидать наличие экстремума, как правило, не предусматривают вычисления значений функции. Таким образом, если они вообще работают, то работают эффективно. В то же время следствием является и то, что при этих методах не исключены случаи застревания в точках, не являющихся оптимальными. Это относится как к прямым методам, так и к градиентным. [13]
Для решения задачи целесообразно использовать методы случайного поиска максимума функции многих переменных [82], обладающие большей простотой алгоритма по сравнению с существующими методами решения систем полиномов высших степеней. Кроме того, метод случайного поиска применительно к данной задаче более наглядно отражает физическую картину явлений. Достоинством этого алгоритма является простота реализации и вместе с тем достаточная надежность получаемого решения. [14]
 |
Глобальный и локальный максимумы [ IMAGE ] Принципиальная схема адаптивной АСР. [15] |
Страницы: 1 2 3 4