10.3 Эвристическое программирование
Эвристическое программирование – методы решения задач, опирающиеся на опыт принятия решений. Применительно к задачам управления эвристическое программирование (эвристические методы) реализуется следующим образом:
- использование интуитивного метода – метод решения может вытекать из практики прошлых действий, которая себя оправдала в большинстве случаев;
- заданием экспертного варианта – задача управления облегчается, если специалист предлагает опорный вариант решения задачи; вблизи его можно проверить изменение критерия эффективности при варьировании отдельных параметров;
- заменой одной задачи на другую – в этом случае модель не будет строго отражать существо рассматриваемой ситуации, но для выработки решения можно использовать алгоритм решения выбранной задачи;
- сужением области исследования – поиск оптимального варианта может упроститься, если ввести дополнительные ограничивающие условия.
Этот метод принятия оптимального решения, основанный на «здравом смысле», применяется, по существу, наряду с любым другим способом выбора наилучшего варианта действий их возможных. Однако особое значение он имеет при отсутствии полной уверенности, что перечень возможных вариантов действий выявлен с исчерпывающей полнотой, а решаемая проблема определена слабо или полностью не определена. /21/
Если перечень возможных вариантов действий определен нечетко, то интуитивный метод получения приемлемого решения применяется по некоторому эвристическому алгоритму (рис.6.6). Примерная последовательность действий в этом случае может быть следующей:
- определяется главная цель действий;
- устанавливается тип главной цели действий;
- интуитивно выбирается некоторый вариант действий для достижения цели. При удачном выборе варианта действий главная цель достигается;
- если выбор варианта неудачен, то так же проверяется второй способ действий, затем, если нужно, — третий и т.д., пока не будет найден способ, позволяющий достичь главной цели;
- если все возможные варианты проверены, а достижение главной цели не гарантируется, то из нее выделяются частные цели, которые классифицируются по типам. Для их достижения выбираются соответствующие способы действий так, как при поиске способа достижения главной цели;
- если какие-то частные цели не могут быть достигнуты ни одним из проанализированных вариантов, то каждую из них делят на частные цели более низкого класса, для которых вновь отыскиваются способы достижения. Этот процесс следует продолжать до тех пор, пока не будет найден способ достижения главной цели или не будет установлено, что все частные цели или значимая часть главной цели действий могут быть достигнуты. Эвристический алгоритм, изображенный на рис.6.6, одинаков для поиска способа действий как для достижения главной цели, так и частной цели любого уровня, стоящей перед ЛПР. |21|
Рис.6.6 Примерный порядок действий при выборе лучшего варианта
эвристическим способом
Эвристическое программирование не является строгим методом решения управленческих задач. При составлении эвристической программы используется опыт специалистов в данной области, формализуемой в виде правил, эмпирических зависимостей, вычислительных алгоритмов.
Эвристическое программирование дает возможность найти решение в тех случаях, когда классические методы оптимизации бессильны. Методы эвристического программирования применяют в задачах большой размерности, в ситуациях с малым резервом времени /13/, а также при решении слабоструктурированных задач, не выраженных количественно в явной форме.
Эвристическое программирование
Эвристическое программирование – методы решения задач, опирающиеся на опыт принятия решений. Применительно к задачам управления эвристическое программирование (эвристические методы) реализуется следующим образом:
· использование интуитивного метода – метод решения может вытекать из практики прошлых действий, которая себя оправдала в большинстве случаев;
· заданием экспертного варианта – задача управления облегчается, если специалист предлагает опорный вариант решения задачи; вблизи его можно проверить изменение критерия эффективности при варьировании отдельных параметров;
· заменой одной задачи на другую – в этом случае модель не будет строго отражать существо рассматриваемой ситуации, но для выработки решения можно использовать алгоритм решения выбранной задачи;
· сужением области исследования – поиск оптимального варианта может упроститься, если ввести дополнительные ограничивающие условия.
Этот методпринятия оптимального решения, основанный на «здравом смысле», применяется, по существу, наряду с любым другим способом выбора наилучшего варианта действий их возможных. Однако особое значение он имеет при отсутствии полной уверенности, что перечень возможных вариантов действий выявлен с исчерпывающей полнотой, а решаемая проблема определена слабо или полностью не определена. /21/
Если перечень возможных вариантов действий определен нечетко, то интуитивный метод получения приемлемого решения применяется по некоторому эвристическому алгоритму (рис.6.6). Примерная последовательность действий в этом случае может быть следующей:
· определяется главная цель действий;
· устанавливается тип главной цели действий;
· интуитивно выбирается некоторый вариант действий для достижения цели. При удачном выборе варианта действий главная цель достигается;
· если выбор варианта неудачен, то так же проверяется второй способ действий, затем, если нужно, — третий и т.д., пока не будет найден способ, позволяющий достичь главной цели;
· если все возможные варианты проверены, а достижение главной цели не гарантируется, то из нее выделяются частные цели, которые классифицируются по типам. Для их достижения выбираются соответствующие способы действий так, как при поиске способа достижения главной цели;
· если какие-то частные цели не могут быть достигнуты ни одним из проанализированных вариантов, то каждую из них делят на частные цели более низкого класса, для которых вновь отыскиваются способы достижения. Этот процесс следует продолжать до тех пор, пока не будет найден способ достижения главной цели или не будет установлено, что все частные цели или значимая часть главной цели действий могут быть достигнуты. Эвристический алгоритм, изображенный на рис.6.6, одинаков для поиска способа действий как для достижения главной цели, так и частной цели любого уровня, стоящей перед ЛПР. |21|
Рис.6.6 Примерный порядок действий при выборе лучшего варианта
эвристическим способом
Эвристическое программирование не является строгим методом решения управленческих задач. При составлении эвристической программы используется опыт специалистов в данной области, формализуемой в виде правил, эмпирических зависимостей, вычислительных алгоритмов.
Эвристическое программирование дает возможность найти решение в тех случаях, когда классические методы оптимизации бессильны. Методы эвристического программирования применяют в задачах большой размерности, в ситуациях с малым резервом времени /13/, а также при решении слабоструктурированных задач, не выраженных количественно в явной форме.
Глава 11. Реализация принятых решений
Эвристические алгоритмы
Древнегреческое слово «эвристика» (еиркжсо — «отыскиваю, открываю») имеет много близких, но различных значений и способов употребления в современном языке. В литературе можно, среди прочих, найти следующие толкования этого понятия.
Эвристические методы — специальные методы решения задач, которые обычно противопоставляются формальным методам решения, опирающимся на точные математические модели. Использование эвристических методов не гарантирует, что получаемые решения являются наилучшими, неудачная эвристика может привести и к получению наихудшего результата. В то же время известно множество удачных эвристик (для решения конкретных задач), обеспечивающих [1] получение приемлемых решений за допустимую цену.
Эвристическая деятельность — организация процесса продуктивного творческого мышления. В этом смысле эвристика понимается как совокупность присущих человеку механизмов решения творческих задач. Эти механизмы универсальны по своему характеру и не зависят от конкретной решаемой проблемы 1 .
Эвристическое программирование — способ написания программ, при котором программист не кодирует готовый математический метод решения, а пытается формализовать тот интуитивно понимаемый метод решения задачи, которым, но его мнению, пользуется человек при решении подобных задач. Как и эвристические методы, эвристические программы не дают абсолютной гарантии достижения поставленной цели и оптимальности получаемого результата.
В нашем случае мы понимаем термин «эвристика» в более узком смысле.
Эвристика — эмпирическое [2] [3] правило, упрощающее или ограничивающее перебор вариантов при поиске решения в конкретной предметной области.
Более того, поскольку здесь мы рассматриваем совершенно конкретный способ поиска решения в данной предметной области — поиск на графе для системы продукций, мы можем еще более конкретизировать определение.
Эвристика — набор правил выбора очередного узла для раскрытия, который должен, по мнению автора эвристики, вести к решению проблемы.
К сожалению, эвристика опирается на догадки и интуицию, а не на точные знания, эвристика использует доступную, но ограниченную информацию, такую, как описание множества текущих открытых узлов, и не может гарантировать, что выбор действительно наилучший. Эвристика — это лишь предложение для выбора следующего шага, основывающееся на опыте и здравом смысле.
Алгоритм, использующий эвристики, называется эвристическим алгоритмом.
Эвристики уменьшают вычислительные затраты на применение правил за счет того, что сокращают общее количество применений правил. Но применение самих эвристик также требует каких-то вычислений и привносит свои затраты. Кроме того, манипуляции с графом поиска, особенно если он велик, также требуют затрат (см. рис. 2.5).
На самом деле, нас интересует общая сумма, складывающаяся из затрат на применение правил, затрат на проверку и раскрытие узлов и затрат на эвристику. Точнее говоря, мы хотим минимизировать среднее значение этой суммы по всем случаям применения эвристического алгоритма.
Чтобы поставить задачу точно, необходимо дать определения и ввести обозначения, что мы и делаем далее.
- [1] Подчеркнем еще раз тот факт, что мы можем даже не вполне понимать, как работаетта или иная «удачная» эвристика и почему она обеспечивает «приемлемость» решения. Всеэто, в некоторой степени, сродни волшебству, но волшебству конкретному, действующему,а потому — полезному.
- [2] Эврика! (буквально — я нашел!), согласно преданию, восклицание Архимеда при открытии им основного закона гидростатики. В переносном смысле это выражение радости, удовлетворения при решении какой-либо сложной задачи или возникновении новой идеи.
- [3] Это слово в определении является чрезвычайно важным. Оно подчеркивает тот факт,что правило не является формально обоснованным, оно обеспечивает «упрощение» и «ограничение» по чьему-то мнению и вовсе не обязательно.