Книга: Технологии программирования

2.3. МЕТОДЫ СИНТЕЗА ВАРИАНТОВ РЕАЛИЗАЦИЙ ПРОГРАММ

2.3. МЕТОДЫ СИНТЕЗА ВАРИАНТОВ РЕАЛИЗАЦИЙ ПРОГРАММ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример использования метода эвристических приемов для создания алгоритмов описан в книге Д. Пойа. Укороченный фонд эвристических приемов для программирования описан в приложении 3.

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

Решение проводится в два этапа — генерации и анализа. На этапе генерации создается творческая группа из 5—15 человек (специалисты-смежники и люди "со стороны", не имеющие никакого опыта в области, к которой относится решаемая задача). Группе объясняется суть задачи, требующей решения, и проводится этап генерации идей. На этом этапе не допускается критика предлагаемых идей. Поощряется выдвижение даже сумасбродных идей. Затем группа экспертов анализирует высказанные идеи и отбирает те, которые заслуживают более тщательной проработки.

Методом мозгового штурма работают команды знатоков в популярной телепередаче: "Что? Где? Когда?" Пятьдесят секунд идет генерация идей и только десять секунд тратится на обсуждение выдвинутых идей.

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

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

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

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

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

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

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

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

Интересно отметить, что число возможных реализаций алгоритмов нелинейного программирования по этой таблице составляет N = 5*6*8*5*7*7*6 = 352800, что значительно превышает число опубликованных методов (около 2000)!

Таблица 2.2

Морфологическая таблица принципов функционирования алгоритмов нелинейного программирования

Значения классификационных признаков классификационного признака "Механизм начальной точки поиска":

признак 1.1 — из точки, указанной пользователем;

признак 1.2 — из средней точки области определения;

признак 1.3 — из точки на границе области определения;

признак 1.4 — из случайной начальной точки поиска;

признак 1.5 — начальная точка поиска не задается.

Значения классификационных признаков классификационного признака "Первичное зондирование гиперповерхности":

признак 2.1 — в виде большого числа случайных точек, зондирующих всю гиперповерхность;

признак 2.2 — поочередные спуски из ряда случайных начальных точек;

признак 2.3 — конкурирующие спуски из добавляемых случайных точек;

признак 2.4 — зондирование гиперповерхности случайными точками с выявлением и более тщательным исследованием "подозрительных областей";

признак 2.5 — сканирование всей гиперповерхности с использованием различных разверток, например Пеано;

признак 2.6 — отдельный механизм начала поиска отсутствует.

Значения классификационных признаков классификационного признака "Стратегия шагов поиска":

признак 3.1 — один шаг;

признак 3.2 — последовательные шаги до выявления экстремума;

признак 3.3 — осуществлять все шаги по одному и тому же механизму;

признак 3.4 — переключать механизмы шагов от глобального метода до локального;

признак 3.5 — переключать механизмы шагов от глобальных далее до усредненных и до локальных;

признак 3.6 — переключать механизмы шагов по эвристическим правилам;

признак 3.7 — малое количество последовательных шагов из ограниченного ряда лидирующих конкурирующих начальных точек;

признак 3.8 — шаги поиска отсутствуют.

Значения классификационных признаков классификационного признака "Направление поиска на шаге":

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

признак 4.2 — по результатам обработки небольшого числа перспективных точек, полученных на предшествующих шагах;

признак 4.3 — по результатам анализа функции, аппроксимирующей случайные точки в перспективном направлении;

признак 4.4 — зондирование гиперповерхности большим количеством случайных точек и последующим построением аппроксимирующей функции;

признак 4.5 — вдоль границы области определения целевой функции;

признак 4.6 — механизм отсутствует.

Значения классификационных признаков классификационного признака "Механизм стратегии шага поиска":

признак 5.1 — пробные точки только на расстоянии предполагаемого экстремума;

признак 5.2 — пробные точки на большем расстоянии, чем предполагаемый экстремум;

признак 5.3 — пробные точки на расстоянии, несколько меньшем, чем у предполагаемого экстремума;

признак 5.4 — объединение признаков 5.1 и 5.2;

признак 5.5 — объединение признаков 5.1, 5.2 и 5.3;

признак 5.6 — совмещение поиска направления и расстояния до экстремума;

признак 5.7 — разделение поиска направления и расстояния до экстремума.

Значения классификационных признаков классификационного признака "Механизм самообучения":

признак 6.1 — сужение границ поиска по мере продвижения к экстремуму;

признак 6.2 — постепенное повышение точности поиска;

признак 6.3 — выявление формы гиперповерхности по результатам предшествующих шагов и переход на специальный механизм уточнения экстремума;

признак 6.4 — выявление формы гиперповерхности по результатам предшествующих шагов и переход на специальный механизм продвижения вдоль оврагов;

признак 6.5 — выявление формы гиперповерхности по результатам предшествующих шагов и отказ от текущего найденного экстремума;

признак 6.6 — изменение плотности вероятности случайных точек для разных зон поиска;

признак 6.7 — механизм отсутствует.

Значения классификационных признаков классификационного признака "Механизм завершения поиска":

признак 7.1 — не выявляется направление улучшения функции на следующем шаге;

признак 7.2 — израсходован ресурс времени;

признак 7.3 — достигнуто заранее заданное значение целевой функции;

признак 7.4 — исчерпаны возможности алгоритма поиска экстремума;

признак 7.5 — выполнено заранее заданное количество шагов поиска;

признак 7.6 — нет улучшений в "дальней" и "близкой" окрестностях.

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

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

Оглавление книги