Эвристическое программирование

Определение оптимальных решений в некоторых сложных задачах может содержать запрещенные или нереализуемые значения и количества, например, времени и стоимости. Часто оптимальное решение может быть даже невозможным.

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

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

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

Эвристическое программирование – это подход с использованием эвристикдля достижения осуществимых и приемлемых решений некоторых сложных задач.

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

Эвристическое мышление включает поиск, обучение, оценку, суждение и затем снова поиск, переобучение и переоценку как процесс исследования и апробирования.

3.2.7. Компьютерное моделирование

Компьютерное моделирование – это метод решения задачи анализа или синтеза сложной системы на основе использования ее компьютерной модели. Суть компьютерного моделирования заключена в получении количественных и качественных результатов на основе имеющейся модели.

Под компьютерной моделью понимают:

- условный образ объекта или некоторой системы, описанный с помощью взаимосвязанных компьютерных таблиц, блок-схем, диаграмм, графиков, рисунков, анимационных фрагментов, гипертекстов и т.д.
и отображающий структуру и взаимосвязи между элементами объекта – структурно-функциональная модель;

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

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

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

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

Компьютерное моделирование – эффективный метод решения задач анализа и синтеза сложных систем. Его методологической основой является системный анализ (в то время, как у моделирования на ЭВМ – те или иные разделы теории математических моделей). Именно поэтому в ряде источников наряду с термином «компьютерное» используется термин системного моделирования, а саму технологию системного моделирования призваны осваивать системные аналитики.

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

В процессе построения имитационной модели выделяется три уровня ее представления: концептуальная модель, формализованное или алгоритмическое описание, программа-имитатор.

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

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

Общепризнанными являются следующие преимущества языков и систем моделирования по сравнению с универсальными языками и системами программирования:

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

Это упрощает программирование программы-имитатора, позволяет автоматизировать выявление, диагностику ошибок в программах.

Автоматизация стандартных функций моделирования (функций управляющей программы):

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

– языки моделирования, как правило, содержат встроенные датчики случайных чисел, генераторы случайных чисел и других типовых воздействий;

– в языках моделирования автоматизирован сбор стандартной статистики и других результатов моделирования. Имеются средства автоматизации выдачи этих результатов в табличной или графической форме;

– управление процессом моделирования (анализ ошибочных ситуаций и т.д.);

– языки моделирования имеют средства, упрощающие программирова­ние имитационных экспериментов (в частности, автоматизирующие установку начального состояния и перезапуск модели), и другие интерактивные и технологические возможности, используемые при проведении имитационных исследований.

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

Множество языков моделирования можно разделить на две группы:

1) методоориентированные – языки моделирования, поддерживающие определенный класс формализованных или алгоритмических описаний;

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

– Simulap, Simflex – управление материальными потоками в производственной системе;

– MAST – моделирование гибких производственных систем (применяется блочная концепция структуризации);

– TOMAS – технологическая подготовка производственных систем (используемые формальные схемы);

– SIRE – календарное планирование производственных процессов
(сети с очередями);

– COMNET – телекоммуникации;

– MEDMODEL – медицинское обслуживание.

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

Язык моделирования предоставляется пользователем как часть системы моделирования. Система моделирования – это совокупность языковых и программных средств, включающая:

- собственно язык моделирования;

- язык управления системой моделирования – язык команд интерактив­ного взаимодействия с пользователем;

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

Проблемно-ориентированные системы моделирования включают также средства разработки языков конечного пользователя.

3.2.8. Оценка вариантов решения по заданным критериям

Оценка возможных вариантов решений необходима для всех типов задач и систем и предшествует окончательному выбору решения. Для анализа альтернатив могут использоваться различные методы:

- традиционные (однокритериальные или балльные);

- многокритериальные;

- методы нечеткой логики.

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

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

1. Принцип свертки критериев – применяется при «оптимизации» многих критериев одним координирующим центром (задача много­крите­риаль­ной оптимизации). Для каждого из критериев (целевых функций)
f₁ (x),..., f_n (x) экспертным путем назначаются «веса» (числа):

n

α₁,..., α_n: α_1≥0, ∑ = 1,

i = 1

причем αi показывает «важность или значимость» критерия f_i. Далее решение х* из множества допустимых решений Х выбирается так, что максимизировать (или минимизировать) свертку критериев:

2. Принцип минимакса – применяется при столкновении интересов противоборствующих сторон (антагонистический конфликт). Каждое ЛПР сначала для каждой своей стратегии (альтернативы) вычисляет «гарантированный» результат, затем окончательно выбирает среди стратегий ту, которая дает лучший результат. Такое действие не дает ЛПР «максимального выигрыша», однако, является единственно разумным принципом оптимальности в условиях антагонистического конфликта. В частности, исключен всякий риск.

3. Принцип равновесия по Нэшу – это обобщение принципа минимакса, когда во взаимодействии участвует много сторон, каждая из которых преследует свою цель (прямого противостояния нет). Пусть число ЛПР
(участников неантагонистического конфликта) есть n. Набор выбранных стратегий (ситуация) (х₁*, х₂*,..., х_n*) называется равновесным, если одностороннее отклонение любого ЛПР от этой ситуации может привести разве лишь к уменьшению его же «выигрыша». В ситуации равновесия по Нэшу участники не получают максимального «выигрыша», но они вынуждены придерживаться ее.

4. Принцип оптимальности по Парето – данный принцип предполагает в качестве оптимальных те ситуации [наборы стратегий (х₁*, х₂*,..., х_n*)],
в которых улучшение «выигрыша» отдельного участника невозможно без ухудшения «выигрышей» остальных участников. Этот принцип предъявляет более слабые (чем принцип равновесия по Нэшу) требования к понятию оптимальности. Поэтому по этому принципу оптимальные ситуации существуют почти всегда.

3.2.9. Использование нечеткой логики для оценки возможных решений

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

После того как процедура оценки вариантов решений проведена, возможны три варианта:

- переход к согласованию критериев (если не удалось ранжировать варианты);

- переход к анализу последствий принятия решений (если предложенные варианты удовлетворяют экспертов или лиц, принимающих решения);

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

3.2.10. Согласование критериев оценки

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

- «переговорные» − без использования вычислительной техники;

- человеко-машинные − опирающиеся на компьютерные процедуры.

Компьютерные процедуры,
применяемые на практике для согласования критериев

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

2. Метод уступок. Сущность метода – нахождение компромисса, определяющего «плату» за потерю показателей по какому-либо критерию или части критериев за счет выигрыша по другому критерию или другим критериям.
3. Метод согласования решения по главному критерию. В некоторых случаях задачу с несколькими показателями качества удается свести к задаче с одним-единственным показателем. Этот показатель стремятся обратить в экстремум, а по остальным вводят ограничения. Тогда проблема согласования сводится к нахождению компромисса по главному критерию и согласованию ограничений для всех остальных.

4. Метод согласования решения при лексикографическом упорядочении. В тех случаях, когда может быть определена важность критериев, упорядочение можно проводить сначала по самому важному критерию, а если по нему равными окажутся несколько вариантов, то проводится упорядочение по следующему по важности критерию и т.д.

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

Получение исходных данных

При получении исходных данных решаются следующие задачи:

- сбор и постоянное обновление информации о параметрах внешней среды и состоянии организации;

- хранение полученной информации, обеспечивающее возможность анализа предыстории;

- передача получаемой или хранимой информации для анализа и обработки;

- представление получаемой или хранимой информации в виде, удобном для обработки.

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

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

Системы оперативной обработки транзакций (online transaction processing − OLTP) позволяют накапливать большие объемы данных, ежедневно поступающих, например, из пунктов продаж. Приложения OLTP, как правило, автоматизируют структурированные, повторяющиеся задачи обработки данных, такие как ввод заказов и банковские транзакции. Эти подробные, актуальные данные из различных независимых точек ввода объединяются в одном месте, откуда аналитики смогут извлечь затем значимую информацию. Агрегированные данные применяются для принятия каждодневных бизнес-решений.

Решение ЗПР

На этом этапе производится математическая обработка исходной информации, ее уточнение и модификация в случае необходимости.

3.4.1. Классификация задач принятия решений

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

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

<T, A, K, X, F, G, D>,

где Т – постановка задачи (например, выбрать лучшую альтернативу или упорядочить весь набор);

А – множество допустимых альтернативных вариантов;

К – множество критериев выбора;

Х – множество методов измерения предпочтений (например, использование различных шкал);

F – отображение множества допустимых альтернатив в множество критериальных оценок (исходы);

G – система предпочтений эксперта;

D – решающее правило.

Рассмотрим традиционные классификации.

1. По виду отображения F. Отображение может иметь детерминированный характер, вероятностный или неопределенный вид, в соответствии с которым задачи принятия решений можно разделить на задачи в условиях риска и в условиях неопределенности.

2. Мощность множества К. Множество критериев выбора может содержать один критерий или несколько. В соответствии с этим ЗПР можно разделить на задачи со скалярным критерием и задачи с векторным критерием (многокритериальное принятие решений).

3. Тип системы G. Предпочтения могут формироваться одним ЛПР или коллективом, в зависимости от этого ЗПР можно разделить на задачи индивидуального принятия решений и задачи коллективного принятия решений.

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

1) задача хорошо формализована, то есть имеется адекватная математическая модель реального объекта;

2) существует некоторая единственная целевая функция (критерий оптимизации), позволяющая судить о качестве рассматриваемых альтернативных вариантов;

3) имеется возможность количественной оценки значений целевой функции;

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

Задачи в условиях риска. В тех случаях, когда возможные исходы можно описать с помощью некоторого вероятностного распределения, получаем ЗПР в условиях риска. Для построения распределения вероятностей необходимо либо иметь в распоряжении статистические данные, либо привлекать знания экспертов. Обычно для решения задач этого типа применяются методы теории одномерной или многомерной полезности. Эти задачи занимают промежуточное положение между задачами принятия решений в условиях неопределенности и определенности.

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

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

⇐ Предыдущая12345678910Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: