Обзор методов поиска новых технических решений

Содержание

 

 

 

Введение

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1.Статистические методы поиска

 

 

1.1.Статистические методы или методы случайного поиска получили достаточно широкое распространение при построении оптимальных решений в различных приложениях. Это объясняется в первую очередь тем, что с ростом размерности задач резко снижается эффективность регулярных методов поиска (детерминированных), так называемое “проклятие размерности”. Во-вторых, зачастую информация об оптимизируемом объекте слишком мала для того, чтобы можно было применить детерминированные методы. Статистические алгоритмы часто используют при поиске оптимального решения в системах управления, когда отклик можно получить только при задании управляющих воздействий на входах системы. В таких ситуациях статистические алгоритмы могут оказаться значительно эффективнее детерминированных.

 

Рис. 1

 

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

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

Статистические алгоритмы обладают рядом достоинств:

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

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

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

 

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

 

Рис. 2

 

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

Вероятность попадания в эту окрестность при одном испытании равна . Вероятность не попадания равна .

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

.

Опираясь на заданную точность , , величину , можно определить и, задаваясь вероятностью , посмотреть, как меняется требуемое количество экспериментов в зависимости от и (см. табл.).

Таблица

	0.8	0.9	0.95	0.99	0.999
0.1	16	22	29	444	66
0.025	64	91	119	182	273
0.01	161	230	299	459	688
0.005	322	460	598	919	1379
0.001	1609	2302	2995	4603	6905

 

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

Рис.3

 

Различают направленный и ненаправленный случайный поиск:

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

 

 

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

Алгоритм поиска можно записать в следущем рекуррентном виде;

 

 

 

(1)

 

 

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

 

1.4.Локальный случайный поиск с пересчетом. Этот поиска отличается от предыдущего тем, что система не возвращается при неудачном шаге назад в исходное состояние, а делает “пересчитанный” случайный шаг в новое состояние, при котором учитывается исходное состояние.

Алгоритм поиска записывается в виде следующей рекуррентной формулы:

 

Рис.4

 

Рис.5

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

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

 

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

В соответствии с методом из исходного состояния делается m случайных пробных шагов

В полученных смещенных точках , где j=1, 2,…, m, производится вычисление значений функции качества и запоминается состояние, которое привело к минимальному значению:

 

 (2)

 

Далее производится рабочий шаг в этом выбранном направлении:

 

                                 (3)

 

Где случайный единичный вектор наилучшей пробы.

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

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

 

            (4)

 

В соответствии c (4) система сделает рабочий шаг вдоль наилучшей пробы только тогда, когда минимальное значение из всех проб не превышает исходного значения . Если это условие не выполняется, тогда повторяется цикл из m пробных шагов.

 

1.6.Локальный случайный поиск статистическому градиенту. Данный метод поиска используется в тех случаях, когда функцию качества J (x) нельзя представить в регулярном виде и она определяется в зависимости от регулярных параметров а также от случайных параметров ). Такая ситуация возможна, например, при поиске экстремума в условиях действия помех.

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

При наличии случайных параметров ) регулярную функцию качества J (x) представим в виде случайной функции

 

),                               (5)

 

где x= —— вектор состояний поиска; =),— вектор случайных помех.

Зная вероятностные характеристики параметров , например плотность распределения p(), можно усреднить функцию H (x,) по этим параметрам и перейти вновь к осредненной регулярной функции качества

                         (6)

Или

                                         (7)

 

где — математическое ожидание.

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

При поиске экстремума дифференцируемой функции качества J(x) все n частных производных i=1,2,…, n, должны обращаться одновременно в нуль, т. е.

 

grad J(x)=0                                                           (8)

 

В результате замены J(x) на условия экстремума принимают следующий вид:

 

grad =0                                       (9)

 

или, учитывая линейность операций, можно записать

 

         (10)

 

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

 

.                          (11)

 

Таким образом, при отсутствии точного знания функции качества J(x) следует заменить ее стохастической оценкой и далее оперировать с этой оценкой при поиске точки экстремума .

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

Пусть

 

,                                          (12)

 

где -скалярная функция от параметра состояния x.

 

Функцию можно представить в виде суммы регулярной составляющей f(x) и случайной составляющей е, причем математическое ожидание М () — 0, т. е. случайная составляющая центрирована.

В результате поиска определяют корень регулярной составляющей f(x), т. е.

 

                                         (13)

 

в соответствии с процедурой

                                      (14)