|
| |
|
Слаботочка Книги исследуемая схема функционирует достаточно хорошо, то поиск возможного решения, который предшествует оптимизации выбранного показателя, дает решение, близкое к оптимальному, причем при небольших откло-нениях входных переменных, ожидаемых при таких условиях, используя эту стратегию поиска оптимума, не обязательно следить за ограничениями на параметры элементов. Тогда в любом случае (при поиске возможного решения НЛП при оптимизации вероятности соответствия схемы установленным требованиям в начальный момент времени) ограничения включаются в целевую функцию, что позволяет свести исходную задачу с ограничениями к задаче оптимизации без ограничений. z.i. оплор СУЩЕСТВУЮЩИХ методов ОПТИМИЗАЦИИ Примеры, которые будут приведены в гл. 9, рассчитывались методогд Хука и Дживса- поиска по конфигурации (pattern search) Чтобы изложить основы этого метода, необходимо предварительно дать краткий обзор методов оптимизации, применяемых в настоящее время при решении инженерных задач. Для более детального знакомства с этими методами можно предложить обзорную статью Вуда (Вуд, 1965) или известную книгу по методам оптимизации (Уайлд, 1964). Напомним, что исходная задача оптимизации при наличии ограничений сводится к задаче без ограничений, которая решается методами, называемыми методами поиска. Форма функциональных зависимостей для у обычно достаточно сложна, поэтому в общем случае задачу оптимизации не удается сформулировать в виде задачи нелинейного программирования. Следовательно, приходится отказаться от таких методов решения, которые развиты в линейном и квадратичном, динамическом и геометрическом программировании (Даффиц и др., 1967), а также от метода множителей Лагранжа, т. е. всех методов, которые уже использовались при проектировании электронных систем (Хедли, 1964; Богуненко и Расщепляев, 1967), ) Название метода дано согласно русскому переводу книги Уайлд. Методы поиска gKCTpewyN]?!. М., Наука , 1966. {Прим. пер.). Существует несколько способов классификации методов поиска. Один из них предусматривает деление на такие две категории: 1) методы, применимые в случаях, когда значения функции Y и первых производных dY/dxXt можно найти в любой заданной точке л-Хь ,.., л: ; 2) методы, применимые в случаях, когда можно вычислить только значения функции У. Методы первой категории при решении рассматриваемой задачи могут оказаться весь.ма эффективными Метод наискорейшего подъема является, по-видимому, наиболее общим среди известных градиентных методов. Особенно эффективна процедура, описанная Флетчерол! и Пауэллом (1963). Она была позднее видоизменена введением разностных аппроксимаций для производных (Стюарт, 1967). Другая процедура, использованная при проектпроваппи электронных схем, была разработана Шахом, Бюхлером и Кемпторном (Уайлд, 1964). Эта процедура получила название метода параллельных касательных. Если частные производные целевой функции можно без труда точно вычислить, то один из градиентных методов будет, без со.мнения, наилучшим при решении такой задачи оптимизации. Выбор метода зависит от формы поверхности отклика, т. е. от многомерной поверхности У (n-1, х,тХ2, . . . , NXn, Wi, w2, Wp) . Очень часто поверхность отклика, исследуемая в данной задаче оптимизации, оказывается мультимодальной, т. е. имеет несколько пиков, причем нужно найти наибольший из этих пиков, называемый глобальным максимумом или глобальным оптимумом. Однако упомянутые градиентные методы обычно позволяют найти только локальный оптимум. Один из способов исследования мультимодальной поверхности отклика сводится к пробным циклам оптимизации целевой функции с выбором начала поиска в различных случайных точках. Если при каждом новом выборе начальной точки получается одинаковый конечный результат, то с достаточной степенью уверенности можно утверждать, что исследуемая поверхность унимодальна. Этот вопрос будет далее обсужден в п. 8.3.3. > Эффективность метода поиска может характеризоваться быстротой сходимости этого процесса. {Прим. пер.), 13-897 193 к сожалению, рассматриваемая в данной задаче целевая функция входных переменных (обобщенный показатель качества или вероятность соответствия схемы установленным требованиям в начальный момент времени) достаточно сложная, и ни эту функцию, ни ее производные обычно нельзя представить в замкнутой форме. Поэтому основной интерес в рамках данной главы представят методы оптимизации, классифицируемые как методы второй категории. 8.2.1. Методы поиска экстремума, требующие вычисления только значений целевой функции Методы оптимизации, требующие определения только значений целевой функции, являются достаточно общими. По сравнению с градиентными методами, различными методами линейного или нелинейного программирования эти методы поиска более грубые, однако имеют важное преимущество: они применимы к многим типам задач. Опишем три метода прямого поиска экстремума, а именно: метод случайного поиска, метод Розенброка и метод поиска по конфигурации) (последний более подробно, так как используется при решении примеров в гл. 9). Существуют и другие методы прямого поиска, но они обычно либо более примитивны, чем упомянутые, либо являются их разновидностями. 8.2.1.1. Случайный поиск Метод случайного поиска экстремума был предложен Бруксом в 1958 г. Для его иллюстрации рассмотрим двумерный случай, представленный на рис. 8.1. Прежде всего устанавливают начальные пределы поиска для входных переменных. В определенном та-ки.м образом пространстве входных переменных вычисляют значения целевой функции для случайно выбранных совокупностей значений входных переменных. Совокупность, доставляющую наибольшее (наименьшее) значение целевой функции, выбирают в качестве оптимального решения задачи максимизации (минимизации). Основное свойство метода состоит в том, что он приме- Терминология соответствует русскому переводу книги Уайлд. Методы поиска экстремума. М., Наука , 1966. (Прим. пер.). 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 [62] 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |