Метод глобального поиска

Для более детального исследования множества допустимых решений (выделение глобального экстремума) метод ЛП,-поиска может быть дополнен, например, исследованием специально сконструированной функции, представляющей собой свертку частных критериев в один глобальный. [c.54]

С точки зрения конечной цели поиска первый подход более естествен и предпочтителен, так как не требует избыточной информации о локальных оптимумах. Однако известно, что методы поиска глобального оптимума (методы перебора и динамического программирования) имеют на практике ограниченное применение из-за большого машиносчетного времени. Поэтому при решении практических задач часто более эффективными оказываются алгоритмы, включающие в себя поиск локальных оптимумов. Обобщения по использованию методов локального поиска для решения задач глобальной оптимизации даны в [71]. [c.133]

В общем случае достаточно эффективным оказывается применение алгоритмов с комбинацией методов статистических испытаний (Монте-Карло) и покоординатного поиска. Для ограничений достаточно общего вида (7.22) путем введения соответствующих масштабов строится многомерный куб. В этом кубе путем статистических испытаний с определенной вероятностью находится аппроксимирующая управляющая функция, которая принимается за начальное приближение к глобальному оптимуму. Принимая полученное решение за начальное, методом покоординатного поиска находится ближайший локальный оптимум. Если начальное решение находится в сфере притяжения глобального оптимума, то полученное после покоординатного поиска решение можно считать окончательным. При наличии овражных ситуаций можно использовать специальные приемы, например поворот координатных осей. [c.217]

Наиболее распространенным приемом, позволяющим отстроиться от локальности направленных методов поиска, является организация алгоритмов, в которых на первом этапе применяется пассивный поиск, а в дальнейшем — один из методов направленного поиска. Такое комби нирование методов оптимизации позволяет вести направленный обзор области поиска из нескольких начальных точек (как это показано в примере на рис. 5.21), которые могут формироваться методами сканирования или статистических испытаний. Важно отметить, что начальные точки должны находиться в области допустимых значений параметров. Схема организации комбинированного алгоритма поисковой оптимизации, дающего возможность определять приближения к глобальному экстремуму функции цели, представлена на рис. 5.28. [c.164]

Так, методы пассивного поиска в результате равномерного просмотра всей области допустимых значений параметров позволяют определить приближение к точке глобального экстремума. Однако за этот бездумный сплошной просмотр приходится платить весьма большими затратами на поиск. Поэтому на практике в основном эти методы находят применение для первоначального изучения области поиска при невысоких требованиях к точности и, в частности, для организации входа изображающей точки в допустимую область при реализации методов направленного поиска. [c.170]

Оптимизация термодинамических параметров в моделях первого уровня ПТУ обеих схем по тем же соображениям, что и в моделях отдельных агрегатов, осуществлялась методом прямого поиска с самообучением глобального экстремума функции многих переменных [81]. Поиск глобального максимума эффективного КПД проводился с точностью фиксации локальных экстремумов 0,05 % полезная электрическая мощность установок принималась равной 30 кВт. [c.164]

Все эти методы предполагают, что область, в которой находится экстремум, уже получена, т. е. предварительно должна быть решена задача поиска глобального экстремума. Для поиска глобального экстремума можно использовать метод случайного поиска. Этот метод заключается в том, что значения варьируемых параметров задаются в виде случайных величин с помощью датчика случайных чисел. Центры группирования экстремальных значений принимаются за предполагаемые области глобального экстремума. Случайный поиск может быть использован и для непосредственного решения задач нелинейного программирования. В этом случае используются методы направленного случайного поиска, использующие результаты предыдущего шага [99]. [c.197]

Основная особенность оптимизации проектных решений заключается в том, что вни.мание конструктора, главным образом, должно быть сосредоточено на выборе метода синтеза возможных решений. И только после того, как множество возможных решений сформировано либо найден эффективный алгоритм формирования возможных решений, приступают к выбору метода поиска оптимального решения. По существу все методы оптимизации относятся к поиску оптимума на дискретном множестве возможных решений. В отдельных случаях, когда множество возможных решений представляется какой-либо структурой определенного класса, могут применяться известные методы оптимизации (например, методы оптимизации на сетях, комбинаторные методы). В остальных случаях единственной альтернативой методу глобального перебора служит тот или иной метод ограниченного перебора возможных вариантов проектных решений. [c.592]

Методы поиска экстремума классифицируются по следующим признакам в зависимости от характера экстремума существуют методы условной и безусловной, локальной и глобальной оптимизации по числу переменных проектирования различают методы одномерного и многомерного поиска, а по характеру информации о виде целевой функции — методы нулевого, первого и второго порядков, причем в методах первого порядка используют градиент целевой функции, поэтому эти методы называются градиентными, в методах второго порядка применяют вторые производные, а в методах нулевого порядка производные не используют. [c.281]

Блок формирования задачи по своему содержанию аналогичен соответствующему блоку для алгоритмов локального поиска (рис. 5.7,а). Блок выбора начальных точек включает методы перебора (обычно метод Монте-Карло). Число перебираемых точек N фиксируется заранее. Выше указывалось, что с ростом М увеличивается вероятность отыскания глобального оптимума. Однако реализация соответствующего количества локальных поисков может оказаться очень трудоемкой даже для мощных современных ЭВМ. В таких случаях из N начальных точек производится отбор приемлемого числа точек, что требует включения в рассматриваемый блок также правил отбора. [c.134]

Такой же результат получается и при поиске методом упорядоченного перебора, если число дискретных значений переменных одинаково. Следовательно, время поиска глобального оптимума методами динамического программирования и упорядоченного перебора можно считать практически одинаковым. В этом смысле динамическое программирование так же, как и прямой перебор, применимо лишь при малом числе переменных и может рассматриваться в качестве одного из способов организации упорядоченного перебора. [c.255]

Время поиска существенно уменьшается при стремлении к локальному оптимуму. В этом случае соотношение (П.43) принципиально сохраняет свою силу, однако значения N существенно уменьшаются и не являются постоянными. Количество расчетов Но на каждом этапе определяется принятым методом одномерной оптимизации и начальной точкой, с которой начинается поиск на данном этапе. Поэтому N изменяется при повторной оптимизации на данном этапе. На основе стратегии динамического программирования построены алгоритмы локальной оптимизации, обеспечивающие значительно меньшее время поиска по сравнению с глобальной оптимизацией [4, 8]. [c.255]

При описании комплексной целевой функции нелинейными зависимостями от внутренних параметров задача оптимизации решается методами линейного программирования если же целевая функция является линейной функцией от внутренних параметров, то имеет место задача линейного программирования. В общем случае целевая функция может иметь несколько экстремумов, отличающихся по абсолютной величине. В зависимости от типа экстремума, в котором заканчивается поиск оптимального решения, различают методы поиска локального и глобального экстремума. Если на значение определяемых параметров наложены некоторые ограничения, то решение задачи синтеза механизмов осуществляется методами условной оптимизации. В противном случае (при отсутствии ограничений) при синтезе механизмов для поиска значений определяемых параметров используют методы безусловной оптимизации. [c.316]

При использовании направленных методов поиска оптимальных параметров возникает ряд проблем, связанный с наличием так называемых локальных экстремумов целевой функции. На рис. IV.2.4 изображена целевая функция одного параметра г. Точки А и С являются локальными минимумами целевой функции, а точка В — глобальным минимумом. [c.154]

Для того, чтобы быть уверенным в том, что в результате применения метода Гаусса—Зейделя или метода наискорейшего спуска получен глобальный, а не локальный минимум целевой функции, приходится неоднократно повторять процедуру поиска, начиная его из различных начальных точек в пространстве параметров. [c.154]

Генетические алгоритмы и методы отжига. Генетические алгоритмы относятся к наиболее универсальным подходам к решению сложных задач структурного синтеза и подробно обсуждаются далее. Методы отжига можно рассматривать как реализацию идеи повышения вероятности определения глобального экстремума в других статистических методах оптимизации, таких, как генетические или локальные методы поиска, [c.208]

Комбинированный поиск. Направленный поиск обычно приводит к отысканию лишь локального минимума. Случайный поиск более подходит к отысканию глобального минимума, так как при нем просматривается вся область изменения параметров. Однако он дает слишком большой объем вычислений, и поэтому часто применяют комбинированные методы, при которых случайным поиском просматривают и сравнивают значения целевой функции в отдельных частях (районах) области изменения параметров и затем направленным поиском находят локальные минимумы для тех частей области, где ожидается получение глобального минимума. При нахождении локального минимума следует иметь в виду два возможных случая его расположения. [c.148]

Обозначим через у = f t) трендовую кривую, описываемую нелинейным уравнением с неизвестными коэффициентами (t = 1, 2, k, где k — число коэффициентов). Исходя из требований метода наименьших квадратов, необходимо определить неизвестные коэффициенты так, чтобы достигался минимум остаточной суммы квадратов (2.1). Для определения минимума функционала (2.1) можно использовать метод поиска глобального экстремума [38]. [c.33]

Рис. 5.7. Блок-схема программы поиска глобального экстремума методом Ч -преобразования

Кроме получения глобального экстремума, этот метод позволил представить полную картину распределения расчетных затрат во всей области изменения оптимизируемых переменных. По вышеизложенной методике была разработана специальная программа, в которую вошли подпрограммы теплового, гидравлического, аэродинамического расчета и расчет суммарных затрат, а также подпрограмма поиска экстремума. Следует отметить, что результаты теплового расчета, т, е. расход топлива, скорости сред, непосредственно использовались в расчете функционала. Оптимизация водогрейных котлов проведена при различных режимах работы основного и пикового, при различных нагрузках, климатических условиях и ценах на жидкое топливо (от 10 до 20 руб/т). [c.61]

Несмотря на многообразие численных методов поиска, применение любого из них в САПР не гарантирует нахождение глобального, т. е, абсолютного, экстремума. Для детерминированных методов это связано с тем, что [c.120]

Целью двух отмеченных поисков является определение вида приближенного выражения (7-Л6) н коэффициентов йг и bk, дающих истинный (глобальный) минимум суммы (7-32). Наиболее важной задачей рассматриваемого метода является нахождение оптимального пути поиска минимума. [c.304]

Подавляющее большинство методов решения задачи безусловной минимизации в действительности являются методами поиска точки локального минимума. Чтобы найти точку глобального минимума, на практике ее местоположение приближенно определяют из анализа решаемой задачи, а затем применяют один из методов поиска локального минимума. [c.141]

В зависимости от числа экстремумов различают задачи одно- и многоэкстремальные. Если метод ориентирован на определение какого-либо локального экстремума, то такой метод относится к локальным методам. Если же результатом является глобальный экстремум, то метод называют методом глобального поиска. Удовлетворительные по вычислительной эффективности методы глобального поиска для общего случая отсутствуют, и потому на практике в САПР используют методы поиска локальных экстремумов. [c.158]

Метод случайного перебора (случайных испытаний или Монте-Карло) применяется на начальной стадии поиска. Число случайных испытаний и диапазон изменения переменных при этом считается фиксированым. С помощью метода Монте-Карло решаются две основные задачи отыскание начальной точки, принадлежащей допустимой области поиска или отыскание в начальном приближении глобального оптимального решения. Уточнение этого решения достигается сужением диапазона изменения переменных вокруг найденного решения. Эту процедуру можно повторить неоднократно. Если при заданном числе испытаний не удает-ся найти ни одной точки в допустимой области, то это число постепенно увеличивается. Невозможность отыскания допусти.мой точки за приемлемое число испытаний указывает на очень узкий (щелевидный) характер допустимой области, что практически встречается очень редко. В этом случае необходимо отказаться от использования метода Монте-Карло вообще и перейти к следующему методу — покоординатного поиска. [c.147]

На первом этапе используются методы случайного или детерминированного поиска. Они состоят в том, что в пространстве допустимых параметров берутся точек и для каждой из них вычисляется значение функции качества. Выбираются, таким образом, JV конкретных вариантов исследуемой конструкции и прямым перебором этих вариантов находится наилучший при этом считается, что он находится поблизости от искомого оптимального варианта (вблизи глобального экстремума). В методах случайного поиска, называемых также методами Монте-Карло, N пробных точек в пространстве параметров выбираются случайным образом [77, 267]. В методах детерминированного поиска точек заполняют исследуемое пространство параметров в определенном смысле равномерно [285]. Опыт показывает, что при небольшом числе испытаний N более эффективны методы детермиийровапиого поиска. Один из таких методов, так называемый метод ЛП-иоиска, оказался эффективным при решении многих задач динамики машин [22, 146]. [c.270]

Простейшим но структуре алгоритмом глобального поиска является независимый поиск (методы Монте-Карло), оенованный на случайном переборе точек в ограниченном пространстве Gp варьируемых параметров [51, 90]. Характерной особенностью методов Монте-Карло является постоянная в течение всего поиска нлот-пость распределепия зондирующих точек. Поэтому для решения этими методами задач оптимизации машинных агрегатов с многомерными векторами Р варьируемых параметров обычно необходимо выполнить значительное число проб. Выгодным для задач динамического синтеза машинных агрегатов свойством метода случайного поиска е равномерным распределением пробных точек является возможность одновременного онределения нескольких оптимальных решений, соответствующих различным критериям эффективности. Это свойство независимого глобального поиска особенно важно для задач параметрической оптимизации машинных агрегатов, оперирующих с неприводимыми к единой мере локальными критериями эффективности. Такая ситуация характерна для параметрического синтеза динамических моделей машинных агрегатов по критериям эффективности, отражающим, ианример, общую несущую способность силовой цепи по разнородным факторам динамической нагругкепности ее отдельных звеньев (передаточного механизма п рабочей машины). Аналогичная ситуация возникает также при оптимизации характеристик управляемых систем машинных агрегатов по критериям устойчивости и качества регулирования. [c.274]

Для указанных выше задач в результате однократного выполнения процедуры независимого случайного поиска для исследуемой системы определяется в общем случае несколько частных оптимальных решений, отвечающих различным критериям эффективности. Полученные решения обеспечивают необходимую информационную основу для применения неформальных методов на заключительной стадии синтеза многокритериальных задач с непормализуемыми локальными критериями эффективности. При независимом глобальном поиске в качестве пробных точек, помимо независимых случайных точек, можно использовать некоторые равномерные раснределения псевдослучайных чисел ЛП-ноиск [90], ПЛП-ноиск [87]. Иа основе указанных методов могут достаточно эффективно решаться различные оптимизационные задачи динамики машинных агрегатов [28]. [c.274]

Возможность существования особых точек (седловых, типа гребней и оврагов и т. д.), разрывности функционала и изменений переменных условных экстремумов на границах допустимых областей, многосвязности, многоэкстремальности функционала, ограничений типа неравенств, дискретность переменных и т. д. — все это приводит к практической непригодности аналитических методов оптимизации теплоэнергетических установок. Применение ЭВМ. и численных методов нелинейного программирования позволяет в основном преодолеть эти затруднения. При малом числе оптимизируемых переменных и при узких пределах их изменения отыскание глобального экстремума практически обеспечивает метод сплошного перебора на ЭВМ вариантов путем обхода в определенном порядке узлов многомерной сетки в пространстве независимых переменных и вычисление в каждой точке значений функций ограничений и функционала. При этом отбрасываются те точки, в которых ограничения не выполняются, а среди точек, для которых ограничения справедливы, выбирается точка с наименьшим (или наибольшим) значением функционала. При оптимизации по большому числу параметров применяются методы направленного поиска оптимума градиентные, наискорейшего спуска, покоординатного спуска (Л. 21]. [c.57]

Задача оптимизации сложной теплоэнергетической установки является многоэкстремальной, имеющей ряд локальных экстремумов. Для поиска среди них глобального экстремума используются комбинации методов случайного поиска с методами направленного поиска. По существу это заключается в том, что спуск производится из разных подобластей с последующим анализом кривых, соединяющих экстремальные и особые точки. Наличие ограничений превращает задачу поиска безусловного экстремума в задачу условного экстремума (возможность нахождения условного экстремума на границе). [c.58]

Использование нелинейных математических моделей и методов математического моделирования а ЭВМ позволяет решить задачу оптимизации для реальных сложных схем турбоустановок с учетом технических ограничений типа неравенств. В то же время наличие ступеней проточной части турбины при определении места отборов пара приводит к дискретности переменных, что вызывает серьезные трудности в реализации поиска глобального оптимума даже на ЭВМ с высоким быстродействием. Поэтому при оптимизации сложных схем прибегают к идеализации проточной части, не рассматривая ее дискретности. Тем самым большинство дискретных оптимизируемых переменных становится непрерывным, и это появоляет применять наиболее эффективные градиентные методы направленного поиска. [c.59]

Задача оптимизации парогенератора (4.55). .. (4.64) относится к классу задач нелинейного программирования. Анализ уравнений, используемых для расчета а также системы ограничений, формирующих область допустимых значений независимых переменных, показывает, что первые и вторые частные производные целевой функции могут иметь разрывы, а она сама — быть многоэкстремальной. Область допустимых значений оптимизируемых параметров может оказаться несвязной. В этих условиях в соответствии с рекомендациями [106] для решения задачи следует использовать методы прямого поиска, в которых процедура построения оптимизирующей последовательности основана только на информации о значениях целевой функции. Задача (4.55). .. (4.64), а также ряд других задач оптимизации отдельных агрегатов теплоэнергетического оборудования и ПТУ в целом, приведенных в последующих главах, решены методом прямого поиска с самообучением глобального экстремума функции многих переменных [81]. [c.82]

Одним из первых возникает вопрос о направлении поиска корня. В случае глобального поиска по К направление целиком определяется продолжением решения (11.19). Для глобального поиска по п используется метод наискорейшего спуска, который устанавливает шаг поиска Н, если он не превышает Ятач- в противном случае шаг определяется на основании адаптивной модели [115, 242] [c.85]

В соответствии с делением экстремумов на локальные и глобальные различают методы локального и глобального поиска. Большинство известных методов относится к методам локального поиска, попытки определения глобального экстремума обычно сопровождаются резким увеличением объема вычислений. Достаточным условием того, что найденный максимум глобальный, является вогнутость целевой функции в пространстве WA, т. е. отрицательная полуопределенность матрицы Гессе. Однако в задачах схемотехнического проектирования указанные условия использовать не удается, так как отсутствуют возможности для исследования вогнутости целевых функций во всей допустимой области. [c.155]

Рассматриваемые методы являются методами поиска локальных экстремумов. Это основные методы в САПР, так как методов глобальной оптимизации, обеспечивающих нахождение глобального экстремума с приемлемыми потерями на поиск, для задачи математического программирования общего вида (3.3) не существует. В САПР поиск глобального экстремума осуществляется путем локальной оптимизации из нескольких исходных точек, выбираемых случайным образом в пределах области, задаваемой прямыми ограничениями. В многоэкстремальных задачах возможно получение нескольких локальных экстремумов, из которых выбирается наилучший. Вероятность определения глобального экстремума при подобном подходе тем меньше, чем меньше объем области притяжения глобального экстремума. Малый объем этой области, как правило, свидетельствует и о низкой стабильности выходных параметров в точке экстремума, следовательно, глобальный экстремум может оказаться малополезным. Поэтому оптимизация на основе небольшого числа вариантов локального поиска является достаточной. [c.71]

Применение метода случайного поиска в программе оптимизатор позволяет не останавливаться в процессе оптимизации на первых локальных минимумах функции качества, а находить значение глобального минимума [3.15]. Если характеристики АС удо-влетворяют предъявленным требованиям, то сложность схемы фильтров снижается и ищется новое оптимальное решение. Цикл продолжается до тех пор, пока оптимизируемые характеристики не выйдут за допустимые границы, затем совершается обратный < шаг в сторону усложнения схемы, и этот вариант считается оп- [c.95]

Вообщ,е задачи условной оптимизации более сложны, чем задачи безусловной оптимизации. Для их решения используют специально разработанные методы программирования с ограничениями. Одним из таких методов, которые относятся к методам поиска глобального экстремума, является метод сканирования, состоящий в том, что допустимая область поиска, определяемая системой ограничений, разбивается на к подобластей, в центре каждой из которых определяется значение целевой функции. Если целевая функция зависит от п параметров, необходимо выполнить вариантов расчета. Для надежного определения глобального минимума необходимо увеличивать число к подобластей, что приводит к большим затратам машинного времени. [c.319]

Методы локальной оптимизации. Эти методы успешно используются для поиска локальных экстремумов в метризованных пространствах. К сожалению, велика вероятность застревания текущей точки на траектории поиска вдали от глобального экстремума. Чтобы уменьшить эту вероятность, применяют поиск с запретами (tabu sear h), в котором запрещается переход в некоторые точки, в том числе в точки, пройденные на нескольких последних итерациях поиска. Спуск происходит в лучшую из пройденных на очередной итерации точек, даже если эта точка хуже результата предьщущей итерации. Тем самым облегчается выход из локальных экстремумов. [c.208]

Прежде всего изложенные методы, как детерминированные, так и случайные, являются по существу локальными, т. е. они обеспечивают (с заданной точностью) попадание в точку локального экстремума, в зоне притяжения которого находится начальная точка поиска В то же время, как показывает анализ, критерии качества при оптимизации параметров теплообменных аппаратов являются сложными и, главное, многоэкстремальными функциями оптимизируемых параметров. Таким образом, для решения поставленной задачи необходим метод, который бы позволял находить глобальный экстремум функции качества. [c.202]

Метод поиска глобального экстремума функции качества при линейных ограничениях. Для оптимизации параметров теплообменных аппаратов весьма эффективным оказался метод поиска глобального экстремума, разработанный в Институте систем управления АН ГрузССР [5.41]. [c.203]

В рассматриваемой экстремальной задаче функционал является нелинейной функцией независимых переменных. Поэтому задача относится к задачам нелинейного программирования. Вышерассмотренные градиентные методы оптимизации оказались непригодными для поиска глобального экстремума, так как часть переменных (я, ан, и 2г) дискретна и, кроме того, имеются локальные экстремумы. Поскольку время расчета данносо функционала иа ЭВМ БЭСМ-4 составляет не более 1 с и число оптимизируемых переменных в данной задаче невелико, то эффективным при реализации на ЭВМ оказался метод последовательного обхода с полным перебором узлов многомерной сетки, получаемой путем деления интервала изменения каждой независимой переменной на дискретное число отрезков Д. В каждом узле рассчитывалось значение функционала, при этом отбрасывались из расчета узлы, не удовлетворявшие вышеприведенным ограничениям, налагаемым на зависимые и независимые переменные. Минимальное значение функционала соответствует тлобальному экстремуму в окрестности с точностью Д. [c.61]

В настоящее время разработано больщое число методов поиска экстремума нелинейных функций многих переменных. Некоторые из них реализованы в виде стандартных подпрограмм, большинство которых имеется в математическом обеспечении ЕС ЭВМ. Для оптимизации параметров ТЭС ПП может быть рекомендован, например, пакет программ MIN 0G, реализующий метод Хука — Дживса нулевого порядка. В математическом обеспечении ЭВМ серии СМ стандартные программы поиска глобального экстремума нелинейной функции пока отсутствуют, и поэтому при работе на ЭВМ данной серии используют специализированные пакеты научных программ, например DIPLEX. [c.244]

Процедура поиска удовлетворяющей комбинации параметров — процесс весьма сложный. Обыкновенные поисковые процедуры не ведут к цели из-за многорежим-ности, благодаря которой все критерии оптимальности для ударно-вибрационных систем имеют большое число локальных экстремумов. Поэтому, планируя машинный эксперимент на АВМ, следует применять поисковые процедуры, основанные на методах планирования экспериментов, которые при минимальной трудоемкости позволяют найти глобальный экстремум (см. гл. V). [c.178]

Во многих случаях задача оптимизации, особенно это относится к задачам нелинейного программирования, решается в несколько этапов. На каждом этапе используется свой метод оптимизации. Например, сначалй используется метод поиска области глобального экстремума. Далее с помощью одного из поисковых методов область, в которой находится экстремальная точка, уменьшается. Если эффективность поисковых методов вблизи оптимума падает, необходимо использовать более точный метод оптимизации. [c.198]

Глобальный экстремум целевых функций многих переменных определяется методом статистических испытаний. Если параметры Xi, Xz,. .., Хи разыгрываются по равномерному закону, то такой метод называют слепым поиском. В этом случае каждый раз запоминаются вычисленные значе-НИЯ целевой функции в точках х = /и 4, 4). После некоторого числа испытаний выбирается несколько областей изменения параметров, в которых значения целевой функции были наибольшими. В дальнейшем границы этих областей уточняются с помощью слепого поиска и используются в качестве исходных для методов одноэкстремальной оптимизации. [c.214]

Энциклопедия по машиностроению XXL

Оборудование, материаловедение, механика и ...