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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

i = 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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