Развитие методов решения задач интеллектуального управления

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

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

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

Еще один подход к редукции сложных формализованных задач, применяемый к более широкому классу систем, чем в линейном программировании, предложили в начале 70-х годов ХХ-го века М. Месарович, Д. Мако и И. Такахара, использовавших для этого понятие «иерархия слоев принятия решений». Суть подхода состоит в том, что сложная проблема разбивается на семейство последовательно расположенных более простых подпроблем, так, что решение всех подпроблем позволяет решить исходную проблему.

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

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

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

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

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

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