Выбор метода решения задачи оптимального проектирования

Методы случайного поиска отличаются от детерминированных тем, что оптимизируемые параметры в процессе поиска минимума функции качества определяются с элементом случайности. Эти методы эффективны при большом числе переменных и сложных целевых функций (например, при наличии локальных экстремумов), но вообще стохастические методы являются универсальными, применимыми к любым задачам. В свою очередь детерминированные методы могут применяться только в хорошо изученном случае. При решении реальных задач оптимизации такая хорошо изученная ситуация наблюдается не всегда. Большинство детерминированных методов носит эвристический характер. К ним относятся релаксационный метод, метод конфигураций, метод Розенброка, симплексный метод, метод деформируемого многогранника и т. д.

Несмотря на сравнительно малое количество необходимых вычислений целевой функции, детерминистские методы имеют некоторые существенные ограничения, свойственные для этой группы методов. В случае мультимодальной целевой функции, они часто не в состоянии найти глобальный оптимум. Чтобы увеличить вероятность нахождения решения – глобального оптимума, необходимо повторить процедуру оптимизации несколько раз из различных стартовых точек. К тому же, детерминистские методы чувствительны к гладкости поверхности целевой функции, которую нельзя все время гарантировать в случае использования численных моделей. Если поверхность целевой функции гладкая, (рисунок 1.4), то детерминистским методам оптимизации нет альтернативы.

Рис. 1.4 – Поверхность гладкой целевой функции

Но если поверхность целевой функции (рисунок 1.5) имеет множество экстремумов, то детерминистский алгоритм может найти локальный, а не глобальный оптимум. В таком случае более предпочтительно провести в начале глобальный поиск области глобального оптимума, используя стохастическую оптимизацию, а затем сам оптимум с применением детерминистских алгоритмов.

Рис. 1.5 – Поверхность многоэкстремальной целевой функции

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

Планирование машинных экспериментов с моделями систем

1.4.1 Методы планирования экспериментов

Машинный эксперимент с моделью системы S при ее исследовании и проектировании проводится с целью получения информации о характеристиках процесса функционирования рассматриваемого объекта. Эта информация может быть получена как для анализа характеристик, так и для их оптимизации при заданных ограничениях, т. е. для синтеза структуры, алгоритмов и параметров системы S. В зависимости от поставленных целей моделирования системы S на ЭВМ имеются различные подходы к организации имитационного эксперимента с машинной моделью Мм. Основная задача планирования машинных экспериментов — получение необходимой информации об исследуемой системе S при ограничениях на ресурсы (затраты машинного времени, памяти и т. п.). К числу частных задач, решаемых при планировании машинных экспериментов, относятся задачи уменьшения затрат машинного времени на моделирование, увеличения точности и достоверности результатов моделирования, проверки адекватности модели и т. д.

Машинный эксперимент. Эффективность машинных экспериментов с моделями Мм существенно зависит от выбора плана эксперимента, так как именно план определяет объем и порядок проведения вычислений на ЭВМ, приемы накопления и статистической обработки результатов моделирования системы S. Поэтому основная задача планирования машинных экспериментов с моделью Мм формулируется следующим образом: необходимо получить информацию об объекте моделирования, заданном в виде моделирующего алгоритма (программы), при минимальных или ограниченных затратах машинных ресурсов на реализацию процесса моделирования.

Таким образом, при машинном моделировании рационально планировать и проектировать не только саму модель Мм системы S, но и процесс ее использования, т. е. проведение с ней экспериментов с использованием инструментальной ЭВМ.

К настоящему времени в физике, биологии и т. д. сложилась теория планирования экспериментов, в которой разработаны достаточно мощные математические методы, позволяющие повысить эффективность таких экспериментов. Но перенос этих результатов на область машинных экспериментов с моделями Мм может иметь место только с учетом специфики моделирования систем на ЭВМ. Несмотря на то что цели экспериментального моделирования на ЭВМ и проведения натурных экспериментов совпадают, между этими двумя видами экспериментов существуют различия, поэтому для планирования эксперимента наиболее важное значение имеет следующее: 1) простота повторения условий эксперимента на ЭВМ с моделью Мм системы S; 2) возможность управления экспериментом с моделью Мм, включая его прерывание и возобновление; 3) легкость варьирования условий проведения эксперимента (воздействий внешней среды Е); 4) наличие корреляции между последовательностью точек в процессе моделирования; 5) трудности, связанные с определением интервала моделирования (0,Т).

Преимуществом машинных экспериментов перед натурным является возможность полного воспроизведения условий эксперимента с моделью исследуемой системы S. Сравнивать две альтернативы возможно при одинаковых условиях, что достигается, например, выбором одной и той же последовательности случайных чисел для каждой из альтернатив. Существенным достоинством перед натурными является простота прерывания и возобновления машинных экспериментов, что позволяет применять последовательные и эвристические приемы планирования, которые могут оказаться нереализуемыми в экспериментах с реальными объектами. При работе с машинной моделью Мм всегда возможно прерывание эксперимента на время, необходимое для анализа результатов и принятия решений об его дальнейшем ходе (например, о необходимости изменения значений параметров модели Мм).

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

Основные понятия планирования экспериментов. Рассмотрим основные понятия теории планирования экспериментов. В связи с тем что математические методы планирования экспериментов основаны на кибернетическом представлении процесса проведения эксперимента, наиболее подходящей моделью последнего является абстрактная схема, называемая «черным ящиком». При таком кибернетическом подходе различают входные и выходные переменные: В зависимости от того, какую роль играет каждая переменная в проводимом эксперименте, она может являться либо фактором, либо реакцией. Пусть, например, имеют место только две переменные: х и у. Тогда если цель эксперимента — изучение влияния переменной х на переменную у, то x — фактор, а у — реакция. В экспериментах с машинными моделями Мм системы S фактор является экзогенной или управляемой (входной) переменной, а реакция — эндогенной (выходной) переменной.

Каждый фактор , , , может принимать в эксперименте одно из нескольких значений, называемых уровнями. Фиксированный набор уровней факторов определяет одно из возможных состояний рассматриваемой системы. Одновременно этот набор представляет собой условия проведения одного из возможных экспериментов.

Каждому фиксированному набору уровней факторов соответствует определенная точка в многомерном пространстве, называемом факторным пространством.

Существует вполне определенная связь между уровнями факторов и реакцией (откликом) системы, которую можно представить в виде соотношения:

Функцию , связывающую реакцию с факторами, называют функцией реакции, а геометрический образ, соответствующий функции реакции,— поверхностью реакции. Исследователю заранее не известен вид зависимостей , , поэтому используют прибли­женные соотношения:

Зависимости , находятся по данным эксперимента. Последний необходимо поставить так, чтобы при минимальных затратах ресурсов (например, минимальном числе испытаний), варьируя по специально сформулированным правилам значения входных переменных, построить математическую модель системы и оценить ее характеристики.

При планировании экспериментов необходимо определить основные свойства факторов. Факторы при проведении экспериментов могут быть управляемыми и неуправляемыми, наблюдаемыми и ненаблюдаемыми, изучаемыми и неизучаемыми, количественными и качественными, фиксированными и случайными.

Фактор называется управляемым, если его уровни целенаправленно выбираются исследователем в процессе эксперимента. При машинной реализации модели Мм исследователь принимает решения, управляя изменением в допустимых пределах различных факторов.

Фактор называется наблюдаемым, если его значения наблюдаются и регистрируются. Обычно в машинном эксперименте с моделью Мм наблюдаемые факторы совпадают с управляемыми, так как нерационально управлять фактором, не наблюдая его. Но неуправляемый фактор также можно наблюдать. Например, на этапе проектирования конкретной системы S нельзя управлять заданными воздействиями внешней среды Е, но можно наблюдать их в машинном эксперименте. Наблюдаемые неуправляемые факторы получили название сопутствующих. Обычно при машинном эксперименте с моделью Мм число сопутствующих факторов велико, поэтому рационально учитывать влияние лишь тех из них, которые наиболее существенно воздействуют на интересующую исследователя реакцию.

Фактор относится к изучаемым, если он включен в модель Мм для изучения свойств системы S, а не для вспомогательных целей, например для увеличения точности эксперимента.

Фактор будет количественным, если его значения — числовые величины, влияющие на реакцию, а в противном случае фактор называется качественным. Например, в модели системы, формализуемой в виде схемы массового обслуживания (Q-схемы), количественными факторами являются интенсивности входящих потоков заявок, интенсивности потоков обслуживания, емкости накопителей, количество обслуживающих каналов и т. д., а качественными факторами — дисциплины постановки в очередь, выбора из очереди, обслуживания заявок каналами и т. д. Качественным факторам в отличие от количественных не соответствует числовая шкала. Однако и для них можно построить условную порядковую шкалу, с помощью которой производится кодирование, устанавливая соответствие между условиями качественного фактора и числами натурального ряда.

Фактор называется фиксированным, если в эксперименте исследуются все интересующие экспериментатора значения фактора, а если экспериментатор исследует только некоторую случайную выборку из совокупности интересующих значений факторов, то фактор называется случайным. На основании случайных факторов могут быть сделаны вероятностные выводы и о тех значениях факторов, которые в эксперименте не исследовались.

В машинных экспериментах с моделями Мм не бывает неуправляемых или ненаблюдаемых факторов применительно к исследуемой системе S. В качестве воздействий внешней среды Е, т. е. неуправляемых и ненаблюдаемых факторов, в машинной имитационной модели выступают стохастические экзогенные переменные. Если имитационная модель сформулирована, то все факторы определены и нельзя во время проведения данного эксперимента (испытания) с моделью Мм вводить дополнительные факторы.

Как уже отмечалось, каждый фактор может принимать в испытании одно или несколько значений, называемых уровнями, причем фактор будет управляемым, если его уровни целенаправленно выбираются экспериментатором. Для полного определения фактора необходимо указать последовательность операций, с помощью которых устанавливаются его конкретные уровни. Такое определение фактора называется операциональным и обеспечивает однозначность понимания фактора.

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

1.4.2 Стратегическое планирование машинных экспериментов с моделями

Применяя системный подход к проблеме планирования машинных экспериментов с моделями систем, можно выделить две составляющие планирования: стратегическое и тактическое планирование.

Стратегическое планирование ставит своей целью решение задачи получения необходимой информации о системе S с помощью модели Мм, реализованной на ЭВМ, с учетом ограничений на ресурсы, имеющиеся в распоряжении экспериментатора. По своей сути стратегическое планирование аналогично внешнему проектированию при создании системы S, только здесь в качестве объекта выступает процесс моделирования системы.

Тактическое планирование представляет собой определение способа проведения каждой серии испытаний машинной модели Мм, предусмотренных планом эксперимента. Для тактического планирования также имеется аналогия с внутренним проектированием системы S, но опять в качестве объекта рассматривается процесс работы с моделью Мм.

Этапы стратегического планирования. Применяя системный подход к проблеме стратегического планирования машинных экспериментов, можно выделить следующие этапы: 1) построение структурной модели; 2) построение функциональной модели. При этом структурная модель выбирается исходя из того, что должно быть сделано, а функциональная — из того, что может быть сделано.

Структурная модель плана эксперимента характеризуется числом факторов и числом уровней для каждого фактора. Число элементов эксперимента

где k — число факторов эксперимента;

— число уровней i-го фактора, .

При этом под элементом понимается структурный блок эксперимента, определяемый как простейший эксперимент в случае одного фактора и одного уровня, т. е. , , .

Вопрос о виде и числе необходимых факторов следует рассматривать с различных точек зрения, причем основной является цель проводимого машинного эксперимента, т. е. в первую очередь решается вопрос о тех реакциях, которые надо оценить в результате эксперимента с машинной моделью Мм системы S. При этом надо найти наиболее существенные факторы, так как из опыта известно, что для большинства систем 20% факторов определяют 80% свойств системы S, а остальные 80% факторов определяют лишь 20% ее свойств.

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

Анализ результатов существенно упрощается, если уровни равноотстоят друг от друга, т. е. ортогональное разбиение упрощает определение коэффициентов аппроксимации. Можно получить значительные аналитические упрощения, если принять число уровней всех факторов одинаковым. Тогда структурная модель будет симметричной и примет вид:

, где ; .

Функциональная модель плана эксперимента определяет количество элементов структурной модели Nф, т. е. необходимое число различных информационных точек. При этом функциональная модель может быть полной и неполной. Функциональная модель называется полной, если в оценке реакции участвуют все элементы, т. е. Nф=Nс, и неполной, если число реакций меньше числа элементов, т. е. Nф<Nс. Основная цель построения функциональной модели — нахождение компромисса между необходимыми действиями при машинном эксперименте (исходя из структурной модели) и ограниченными ресурсами на решение задачи методом моделирования.

Тактическое планирование машинных экспериментов с моделями

Тактическое планирование эксперимента с машинной моделью Мм системы S связано с вопросами эффективного использования выделенных для эксперимента машинных ресурсов и определением конкретных способов проведения испытаний модели Мм, намеченных планом эксперимента, построенным при стратегическом планировании. Тактическое планирование машинного эксперимента связано прежде всего с решением следующих проблем: 1) определения начальных условий и их влияния на достижение установившегося результата при моделировании; 2) обеспечения точности и достоверности результатов моделирования; 3) уменьшения дисперсии оценок характеристик процесса функционирования моделируемых систем; 4) выбора правил автоматической остановки имитационного эксперимента с моделями систем.

Проблема определения начальных условий и их влияния на достижение установившегося результата при моделировании. Первая проблема при проведении машинного эксперимента возникает вследствие искусственного характера процесса функционирования модели Мм, которая в отличие от реальной системы S работает эпизодически, т. е. только когда экспериментатор запускает машинную модель и проводит наблюдения. Поэтому всякий раз, когда начинается очередной прогон модели процесса функционирования системы S, требуется определенное время для достижения условий равновесия, которые соответствуют условиям функционирования реальной системы. Таким образом, начальный период работы машинной модели Мм искажается из-за влияния начальных условий запуска модели. Для решения этой проблемы либо исключается из рассмотрения информация о модели Мм, полученная в начальной части периода моделирования (О, Т), либо начальные условия выбираются так, чтобы сократить время достижения установившегося режима. Все эти приемы позволяют только уменьшить, но не свести к нулю время переходного процесса при проведении машинного эксперимента с моделью Мм.

Проблема обеспечения точности и достоверности результатов мо­делирования. Решение второй проблемы тактического планирования машинного эксперимента связано с оценкой точности и достоверности результатов моделирования (при конкретном методе реализации модели, например, методе статистического моделирования на ЭВМ) при заданном числе реализаций (объеме выборки) или с необходимостью оценки необходимого числа реализаций при заданных точности и достоверности результатов моделирования системы S.

Как уже отмечалось, статистическое моделирование системы S — это эксперимент с машинной моделью Мм. Обработка результатов подобного имитационного эксперимента принципиально не может дать точных значений показателя эффективности Е системы S; в лучшем случае можно получить только некоторую оценку Е такого показателя. При этом экономические вопросы затрат людских и машинных ресурсов, обосновывающие целесообразность статистического моделирования вообще, оказываются тесно связанными с вопросами точности и достоверности оценки показателя эффективности Е системы S на ее модели Мм.

Проблема выбора правил автоматической остановки имитацион­ного эксперимента с моделями системы. И наконец, последней из проблем, возникающих при тактическом планировании имитационных экспериментов, рассмотрим проблему выбора правил автоматической остановки имитационного эксперимента. Простейший способ решения проблемы — задание требуемого количества реализаций N (или длины интервала моделирования Т). Однако такой детерминированный подход неэффективен, так как в его основе лежат достаточно грубые предположения о распределении выходных переменных, которые на этапе тактического планирования являются неизвестными. Другой способ — задание доверительных интервалов для выходных переменных и остановка прогона машинной модели Мм при достижении заданного доверительного интервала, что позволяет теоретически приблизить время прогона к оптимальному. При практической реализации введение в модель Мм правил остановки и операций вычисления доверительных интервалов увеличивает машинное время, необходимое для получения одной выборочной точки при статистическом моделировании.

Правила автоматической остановки могут быть включены в машинную модель такими способами: 1) путем двухэтапного проведения прогона, когда сначала делается пробный прогон из N* реализаций, позволяющий оценить необходимое количество реализаций N (причем если N* N, то прогон можно закончить, в противном случае необходимо набрать еще N—N* реализаций); 2) путем использования последовательного анализа для определения минимально необходимого количества реализаций N, которое рассматривается при этом как случайная величина, зависящая от результатов N — 1 предыдущих реализаций (наблюдений, испытаний) машинного эксперимента.

Рассмотрим особенности последовательного планирования машинных экспериментов, построенных на последовательном анализе. В последовательном анализе объем выборки не фиксирован, а после i-го наблюдения принимается одно из следующих решений: принять данную гипотезу, отвергнуть гипотезу, продолжить испытания, т. е. повторить наблюдения еще раз. Благодаря такому подходу можно объем выборки существенно уменьшить по сравнению со способами остановки, использующими фиксированный объем выборки. Таким образом, последовательное планирование машинного эксперимента позволяет минимизировать объем выборки в эксперименте, необходимой для получения требуемой при исследовании системы S информации. Построив критерий, можно на каждом шаге решать вопрос либо о принятии нулевой гипотезы Hо, либо о принятии альтернативной гипотезы Н1 либо о продолжении машинного эксперимента. Последовательное планирование машинного эксперимента использует принцип максимального правдоподобия и последовательные проверки статистических гипотез.