Книга 1 Киев „Корнійчук 2009 Кононюк Анатолий Ефимович


О качестве прождаемых рекомендаций



страница31/33
Дата18.05.2019
Размер5.66 Mb.
ТипКнига
1   ...   25   26   27   28   29   30   31   32   33

2.9.5. О качестве прождаемых рекомендаций

Отметим два характерных критических замечания в адрес метода вариантного синтеза:

I. Если набор фрагментов и законы комбинирования заданы, то тем самым все возможные варианты уже предопределены составите­лем программы. Возникае вопрос, где же здесь автоматизированное консультирование? Возражение вызвано смешением понятий «способ задания множе­ства рекомендаций» и «нахождение рекомендации данного множества, обла­дающая определенными свойствами». Если говорить строго, то по этому поводу А. Чёрчем еще в 30-е годы в теории алгоритмов доказано, что существуют перечислимые, но не разрешимые множе­ства. Другими словами, на языке более известных понятий можно утверждать, что любое написанное в ближайшие годы стихотворение должно состоять из известных слов, набор которых ограничен и которые соединены не менее известными правилами грамматики. Однако от этого в общем верного утверждения еще очень далеко до создания конкретного хорошего стихотворения. Точно так же в нашем случае в программу вводятся лишь словарь, грамматика, семантика и критерий отбора по качеству. Каких-либо конкретных правил «как сделать хорошо» в программу не вводят. Более того, можно совершенно не знать этих правил.

С чисто практической точки зрения, когда число вариантов рекомендаций возрастает до сотен и тысяч, а характеристики каждой проблемы выявляются лишь в результате расчета, человек уже не в силах достаточно быстро не только назвать наилучшую рекомендацию, но даже хотя бы перечислить без ошибок все возможные варианты. В этом случае перед ним стоит трудная задача и ответ он воспринимает как но­вую для себя информацию независимо от того, кто его получил, — человек-консултант или программа. Понятие «новое» не абсолютно и в зависимости от точки зрения может трактоваться по-разному. Если в классе достаточно сложных проблем условиться считать, как это принято в системе патентования, что новый и полезный — это такой объект, который, отвечая практическим запросам, отлигчается от созданных ранее, и притом в лучшую сторону, то за про­граммой вправе признать возможность создания нового.

II. Программа использует лишь жестко заданный, ограниченный набор фрагментов и способов их соединения, а человек, используя свои интеллектуальные способности, может расширить этот набор, поэтому рекомендации, порожденные программой, будут всегда примитивнее и хуже рекомендаций, сформированных консультантом. Это замечание отно­сится yжe к практической ценности метода вариантного синтеза, и по его поводу рассмотрим три момента.

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

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

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

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

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



2.10. Оптимальность при нескольких критериях

2.10.1. Целевые функции заказчика

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



2.10.2. Оптимальность по Парето

На рис. 2.15 показано некоторое множество рекомендаций.

Рекомендации изображены в виде точек на плоскости характеристик, важных для заказчика — времени задержки Т и аппаратурных затрат Q.

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




Рис. 2.15. Сравнение рекомендаций по двум характеристикам.

1, 2, 3, 4 — рекомендации, оптимальные по Парето.


Аналогично рекомендация 6 хуже рекомендации 3. Тем более плохими будут рекомендации 7—10, покольку для каждой из них найдется другая рекомендация, которая лучше данной и по Т, и по Q сразу. Рекомендации 1—4 образуют группу рекомендаций, не сравнимых между собой по Т и Q: в любой паре одна рекомендация лучше другой по одной характеристике, но хуже по другой. Такая группа рекомендаций, в которой невозможно, переходя от одной рекомендации к другой, улучшать значение одной характеристи­ки, не ухудшая при этом значения никакой другой, называется груп­пой рекомендаций, оптимальных по Парето или просто «группой Парето». Эти рекомендации образуют группу своего рода «лучших представителей» всего множества рекомендаций. Все остальные заведомо хуже тех, что вошли в группу Парето. Среди рекомендаций, оптимальных по Парето (рис. 2.15), можно выделить две характерные точки: 1 —самая «быстрая» рекомендация и 4 — самая «дешевая». Группу Парето можно выделить не только при двух, но и при любом большем числе характеристик, важно только, чтобы для каждой характерней в отдельности были определены направления «хорошо» и «плохо». Так, для трех характеристик — Т, Q и потребляемой мощности Р все множество рекомендаций образует трехмерное объемное «облако». Не претендуя на строгость, можно считать, что в группу Парето войдут рекомендации, лежащие в пограничном слое «облака», обращеннем к началу координат. Многомерные задачи в данном случае принциально не отличаются от двумерных, поэтому в дальнейшем для удобства графической иллюстрации будут рассматривать прострнства двух характеристик.

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

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

2. Еще встречаются иногда в некоторых КЗ требования типа «сформировать рекомендации по разработке логического узла, обеспечивающего минимальную вре­менную задержку при минимальных аппаратурных затратах». Из рис. 2.15 ясно, что подобные формулировки бессмысленны.

3. Широко распространены формулировки КЗ, в которых задаются граничные значения по всем характеристикам: Т≤ТКЗ, QQКЗ. При этом, поскольку заказчику, как правило, не известно положение области Парето, вероятность того, что значения характе­ристик, указанные в КЗ, попадут прямо в нее, очень мала. Скорей всего, требования КЗ попадут или левее и ниже границы Парето (точка А на рис. 2.15), где реализуемых рекомендаций не существует вообще (требования КЗ завышены, невыполнимы), или правее и выше этой границы в зону плохих рекомендаций (точка В рис. 2.15: требования КЗ занижены, КЗ допускает формирование не лучших рекомендаций). Подобная форма задания часто оправдана при работе с человеком-консультантом, но при работе с программой автоматического синтеза рациональнее задавать в КЗ ограничения не по абсолютно всем характеристикам, а по всем, кроме одной, и при этом потребовать, минимизации значения этой последней характеристики. Так, при двух характеристиках Т и Q возможны два варианта задания: Т≤ТКЗ, при этом минимизировать Q, и QQКЗ, при этом минимизировать Т. При такой формулировке задания программа будет выдавать рекомендации, наилучшие из возможных при использовании данных принципов и фрагментов. Нетрудно заметить (рис. 2.15), что эти рекомендации всегда принадлежат группе Парето. Не составляют исключения и экстре­мальные формулировки КЗ, требующие формирования рекомендаций с ми­нимально возможными значениями Т или Q.

4. На этапах начального консультирования и при выполнении иссле­довательских работ распространены КЗ, где требуется минимизировать некоторую функцию от внешних характеристик, например



Ц1=WiT+W2Q; Ц2 = TQ.

Рекомендации, отвечающие этим требованиям, также входят в состав оптимальных по Парето.

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

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

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

Заметим, что для каждого конкретного сочетания запретов заказчика на значения внутренних параметров множество Парето будет свое. Это замечание, во-первых, отвечает на распространенный вопрос — зачем нужна программная система автоматизированного синтеза Нельзя ли один раз составить список рекомендаций, оптимальных по Парето, и снабдить им всех потенциальных заказчиков? Во-вторых, из этого замечания следует, что программа синтеза, построен­ная на основе целенаправленного алгоритма, выводящего в опреде­лимую область пространства рекомендаций, годится только для жестко заданного набора значений параметров (базовых фрагментов). Если часть из них заказчик запретит или в систему будут введены новые фрагменты, то «хорошей» станет уже другая область, и для выхода в нее нужно будет создавать новый алгоритм. В противоположность этому метод перебора универсален по отношению к любой комбинации дополнений или запретов на значения любых параметров.



2.11. Методы сокращенного перебора

2.11.1. Влияние запрещенных ветвей

Вернемся к вопросу об объеме перебора при вариантном синте­зе. Опасение, что расход машинного времени при полном переборе вариантов может выйти за рамки разумно допустимых пределов, действительно обоснованно. В связи с этим прежде всего обратим внимание на то, что дерево синтеза имеет запрещенные ветви, отче­го реальный объем перебора оказывается значительно меньше распространенной его оценки, представляющей произведение чисел зна­чений всех параметров. Так, если рекомендация описывается восемью па­раметрами, каждый из которых имеет по шесть значений, то число мыслимых сочетаний значений параметров составляет 68, что превы­шает 1,6·106. Перебор такого числа вариантов часто лежит за пределами возможностей финансирования консультирования проблем. В то же время, если из-за физических ограничений на сочетае­мость некоторых значений параметров при каждом просмотре гнезда в среднем половина значений параметров не привлекается к формированию рекомендаций, число вариантов будет уже 38, т. е. около 6,5·103.

При синтезе рекомендаций это соответствует примерно 5 мин. работы современного компьютера. Если к тому же заказчик по каким-то своим соображениям запретит применение 1/3 заложенных в систему фрагментов, то число вариантов сократится более чем в 25 раз и упадет до 28=256, а машинное время — до нескольких секунд. К сожалению, оценить реальный объем перебора невозможно, не выполнив предварительно значительной работы по формулировке условий применимости различных значений параметров, т. е. не заполнив весь морфологический ящик.

2.11.2. Сокращение перебора и априорные сведения

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

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

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

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

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



2.11.4. Эвристики

Квалифицированный консультант, помня результаты сделанных

прежде попыток, знает много частных рекомендаций, относящихся

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

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

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

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

2.11.5. Текущие оценки

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

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

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





Поделитесь с Вашими друзьями:
1   ...   25   26   27   28   29   30   31   32   33


База данных защищена авторским правом ©vossta.ru 2019
обратиться к администрации

    Главная страница