Методы поиска решения

Если решение задачи неизвестно или неоднозначно, например, отсутствуют аналоги или его трудно определить в явном виде, то применяются методы поиска (вывода) решения. Большинство этих методов основано на стратегиях полного перебора, имплицитного (неявного, неполного) перебора или сокращенного (направленного) перебора на основе эвристик (эвристический поиск). Стратегия полного перебора используется при отсутствии достаточной априорной информации о задаче и сравнительно небольшой мощности множества альтернатив (до 10³ элементов при ручном счете и до 10⁹ – на ЭВМ). Имплицитный перебор включает большую группу градиентных методов, например симплекс-метод, метод минимальной стоимости (“жадный” алгоритм), динамическое программирование, -метод, метод ветвей и границ и т.п. Все они основаны на рассмотрении на каждом шаге поиска не всего пространства задачи, а некоторого его фрагмента, определяемого симметрией задачи. Эвристические методы основаны на моделировании эвристик – качественно-ситуационных способов решения задач. Эвристики – это пошаговые процедуры, которые за конечное число шагов обеспечивают удовлетворительное решение задачи путем сокращения возможных вариантов при поиске решения и использования направленного перебора. Эвристические методы применяются для решения слабо структурированных, плохо формализуемых задач, которые не могут быть описаны числовой моделью и характеризуются неточностью, неполнотой, неоднозначностью, неясностью информации. Их применение также целесообразно при жестких ресурсных ограничениях (действия в экстремальных или неизвестных ситуациях). Эвристический поиск включает системный анализ задачи; выявление ограничений, влияющих на результат (как внешних, так и внутренних); анализ возможности получения результата простыми средствами; определение особенностей, ограничений и “узких мест”, требующих использования дополнительных средств, и путей их уменьшения; моделирование задачи и возможных ситуаций для получения наилучшего решения. Эвристический поиск базируется на использовании ряда общих подходов, применяемых человеком в процессе решения задач при генерировании вариантов решений, их сравнении и выборе оптимального решения. Метод аналогии (прецедента) является наиболее общим и может предусматривать аналогию в целях и критериях, структуре и функциях, условиях функционирования, в результатах и их оценке, способах описания и моделях. Метод упрощения применяется, когда прямая аналогия затруднена из-за сложности проблемы и заключается в снятии ряда условий и ограничений, повышении “симметрии” задачи. Метод агрегирования (ассоциации, погружения) дополняет предыдущий и предусматривает применение концептуального аппарата более высокого уровня, что позволяет рассматривать решаемую задачу как часть более общей (такой подход характерен для решения так называемых некорректных задач).

Основные методы поиска решения можно разделить на три группы. Первую группу составляют стратегии поиска по состояниям. Исходная информация представляется в виде пространства ситуаций, описываемого как состояние системы и окружающей среды. Алгоритм поиска состоит в поиске пути, ведущего из начального состояния в одно из конечных (целевых состояний). К этой группе относятся методы поиска “в ширину”, поиска “в глубину”, -метод, метод ветвей и границ, метод кратчайшего пути, методы прямого и обратного поиска, а также градиентные методы, например, метод минимальной стоимости, метод динамического программирования, метод векторной оптимизации, интерактивные ЧМ-методы.

Вторую группу составляют стратегии поиска по задачам. Исходная информация представляется как задача s и множество элементов решения (подзадач), где j – число уровней решения; i – число элементов на j -м уровне. Алгоритм поиска состоит в сведении исходной задачи к более простым задачам, пока не будут получены элементарные задачи. К этой группе относятся метод ключевых операторов, метод общего решателя задач и другие.

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

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

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

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

Рассмотрим пример. Имеется схема автотранспортных перевозок между пунктами, представленная в виде графа, где пункты пронумерованы цифрами от 1 до 10 (рис.4). Требуется найти дерево, имеющее минимальную сумму расстояний. В качестве оценочной функции использована стоимость перевозки, пропорциональная расстоянию (на графе указаны расстояния в километрах).

Рис.4. Граф системы автотранспортных перевозок

Для решения задачи расположим ребра-пути в порядке возрастания стоимости. Имеем 1-3, 6-7, 5-6, 5-8, 9-10, 3-4, 7-10, 1-4, 4-7, 2-3, 3-6, 6-9, 8-9, 1-2, 2-5, 2-6, 3-8. Алгоритм работает следующим образом. Начиная с наименьшего пути, включаем последовательно ребра, имеющие меньшую стоимость из оставшихся и не образующие цикла с уже включенными ребрами. Получаем решение 1-3, 6-7, 5-6, 5-8, 9-10, 3-4 и 7-10. Следующее по стоимости ребро 1-4 исключается, так как оно образует цикл с уже включенными ребрами 1-3 и 3-4. Далее добавляются ребра 4-7 и 2-3. Видно, что все вершины достигнуты и дерево минимальной стоимости построено. Этот же метод применим и при другой интерпретации величин и отношений между ними, например аналогично можно рассмотреть схему телефонных соединений, каналов связи и т.п.

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

− случайным образом создать начальную популяцию из N объектов (структур, вариантов решения и т.п.);

− вычислить для каждого объекта показатель его работы. Если их среднее значение достаточно высокое, то прервать вычисления и считать эти объекты итоговым результатом;

− для каждого объекта подсчитать вероятность его выбора

;

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

− повторить процедуру, начиная со второго шага.

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

Рассмотрим в качестве примера, иллюстрирующего действие генетического алгоритма, задачу синтеза. Пусть требуется разработать новую перспективную модель, например автомобиль повышенной проходимости. Модель конструируется из, примерно, N = 1000 элементов, т.е. множество разнотипных элементов конструктора состоит из 1000 единиц. Каждый вариант оценивается по n критериям, например, n @ 100. Общая база знаний о предметной области насчитывает около 10000 вариантов, которые могут отличаться числом и составом элементов. Будем считать, что критерии предварительно ранжированы по важности, причем самыми важными являются функциональные критерии (группа 1), затем идут технико-экономические критерии (группа 2), эргономические (группа 3) и специальные (группа 4). Внутри групп предварительное ранжирование не проводится. Эти же группы критериев применяются и для оценки отдельных элементов конструктора. Таким образом, каждый вариант (и элемент) представлен упорядоченным набором критериев (показателей) < K 1, K 2,…, K_n >, где n @ 100. В этом наборе могут быть пропуски (нулевые позиции), т.е. не обязательно все критерии используются для оценки всех вариантов (элементов). Примем, что вес каждого варианта (элемента) определяется отношением числа критериев с максимальным значением к общему числу критериев. Элементы конструктора могут варьироваться (добавляться и удаляться). Нужно определить наилучшее решение. Конечно, такая задача может быть решена методом перебора, однако это потребует больших затрат времени. Кроме того, если учесть, что множество элементов конструктора может пополняться, то трудоемкость задачи еще более возрастает. Выбор решения зависит также от соответствия (адекватности) условий задачи применяемому методу выбора. Влияет на результат соотношение весов критериев и пополнение множества альтернатив (элементов).

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

Операция кроссинговера в основном будет применяться при отборе вариантов. Наряду с традиционным перекрещиванием дополним ее операциями пересечения и объединения множеств-популяций, как предельными случаями операции кроссинговера.

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

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

В данной задаче, говоря языком биологии, популяция состоит из 10000 вариантов решений, каждый из которых оценивается по n критериям, например, n = 100. В действительности на элементном уровне приходится решать несколько задач разной размерности: на уровне подсистем N @ 10, на уровне составляющих подсистем – модулей N @ 100 и на уровне элементов N @ 1000, но в нашем случае это не имеет значения.

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

Для отбора методов к популяции, элементами которой являются разновидности методов, применяется генетический алгоритм. Метод считается применимым, если его информационные запросы I_M соответствуютусловиям задачи I ₀, т.е. I_M Í I ₀. Выделяются элементы метода и элементы условий задачи. У каждого метода имеются особые запросы (условия применимости), которые должны содержаться в условиях задачи. Операция кроссинговера при отборе методов мало пригодна, хотя и может использоваться для получения комбинаций методов. Так как «популяция» методов малочисленна (несколько десятков методов), то основной для их трансформации и выбора является операция изменения (мутации), которая применяется, если не выполнены информационные запросы метода. Тогда этот метод отбрасывается (трансформируется) и заменяется другим, пока условия применимости какого-то метода не совпадут с условиями задачи. При этом метод представляется в виде совокупности элементов, составляющих информационный запрос метода (условия применимости). Если имеется много методов, для которых выполнены условия применимости, то исследуется структура методов, и они трансформируются с помощью операций изменения и кроссинговера. Определяется пересечение методов по элементам информационного запроса. Те условия, которые являются общими для методов, образуют типовые элементы (ядро) запроса. Ядро запроса проверяется на соответствие условиям задачи. Если соответствие отсутствует, то применяется операция изменения и происходит их замена другими. Методы ранжируются по их соответствию условиям задачи, точнее, по числу особых условий их применения (по типовым элементам запроса). Например, для метода аддитивной свертки важность критериев должна плавно убывать, для применения метода главного критерия один из критериев должен быть значительно важнее остальных, для метода пороговых критериев должны быть заданы пороговые значения критериев, для метода расстояния должно быть известно «идеальное» решение и т.п. Предварительное ранжирование методов осуществляет ЛПР по ряду критериев, которые учитывают предпочтения ЛПР, степень соответствия условиям задачи (информационный запрос), точность, сложность, надежность, время и т.п. (общее число критериев n @ 10). Вес метода определяется отношением числа критериев с максимальным (наилучшим) значением к общему числу критериев при прочих равных условиях, т.е. при соответствии информационного запроса метода условиям задачи (этот критерий является основным). Остальная процедура выбора предпочтительного метода осуществляется аналогично отбору вариантов, изложенному выше. Для повышения достоверности расчетов часто целесообразно применять несколько методов с близкими оценками, поэтому наряду с кроссинговером, изменением и перестановкой следует использовать операцию объединения, которая позволяет получать комбинированные методы выбора вариантов. Об использовании операции пересечения было сказано выше.

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