Автор: Сотник С.Л.

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

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

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

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

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

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

Эволюция

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

Основные принципы эволюционной теории заложил Чарльз Дарвин в своей самой ре-волюционной работе — "Происхождение видов". Самым важным его выводом был вывод об основной направляющей силе эволюции — ею признавался естественный отбор. Другими сло-вами — выживает сильнейший (в широком смысле этого слова). Забегая вперед, замечу, что любой эволюционный алгоритм имеет такой шаг, как выделение самых сильных (полезных) особей. Вторым, не менее важным выводом Дарвина был вывод об изменчивости организмов. Аналогом данного закона у всех алгоритмов является шаг генерации новых экземпляров иско-мых объектов (решений, структур, особей, алгоритмов).

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

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

МГУА

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

1. Берем самый последний слой классификаторов.

2. Генерируем из них по определенным правилам новый слой классификаторов (кото-рые теперь сами становятся последним слоем).

3. Отбираем из них F лучших, где F-ширина отбора (селекции).

4. Если не выполняется условие прекращения селекции (наступление вырождения – инцухта), переходим на п. 1.

5. Самый лучший классификатор объявляется искомым решением задачи идентифи-кации.

Как мы видим, налицо все признаки эволюционного алгоритма — отбор (селекция) и генерация нового поколения.

Генетический алгоритм (ГА)

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

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

f(x1, x2, x3, …, xN)

Для того чтобы заработал ГА, нам необходимо представить независимые переменные в виде хромосом. Как это делается?

Как создать хромосомы?

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

• в двоичном формате;
• в формате с плавающей запятой.

В случае если мы используем двоичное кодирование, мы используем N бит для каждого параметра, причем N может быть различным для каждого параметра. Если параметр может из-меняться между минимальным значением MIN и максимальным MAX, используем следующие формулы для преобразования:

r = g*(MAX – MIN) / (2^N – 1) + MIN.
g = (r – MIN) / (MAX – MIN) * (2^N – 1)

где g – целочисленные двоичные гены, r – эквивалент генов в формате с плавающей запятой.

Хромосомы в формате с плавающей запятой, создаются при помощи размещения зако-дированных параметров один за другим.

Если сравнивать эти два способа представления, то более хорошие результаты дает ва-риант представления в двоичном формате (особенно, при использовании кодов Грея). Правда, в этом случае мы вынуждены мириться с постоянным кодированием/декодированием параметров.

Как работает генетический алгоритм?

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

Репродукция состоит из четырех шагов:

• селекции

и трех генетических операторов (порядок применения не важен)

• кроссовер
• мутация
• инверсия

Роль и значение селекции мы уже рассмотрели в обзоре эволюционных алгоритмов.

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

001100101110010|11000 --------> 00110010111001011100
110101101101000|11100

Мутация представляет собой случайное изменение хромосомы (обычно простым изме-нением состояния одного из битов на противоположное). Данный оператор позволяет более бы-стро находить ГА локальные экстремумы с одной стороны, и позволяет "перескочить" на другой локальный экстремум с другой.

00110010111001011000 --------> 00110010111001111000

Инверсия инвертирует (изменяет) порядок бит в хромосоме путем циклической пере-становки (случайное количество раз). Многие модификации ГА обходятся без данного генети-ческого оператора.

00110010111001011000 --------> 11000001100101110010

Очень важно понять, за счет чего ГА на несколько порядков превосходит по быстроте случайный поиск во многих задачах? Дело здесь видимо в том, что большинство систем имеют довольно независимые подсистемы. Вследствие этого, при обмене генетическим материалом часто может встретиться ситуация, когда от каждого из родителей берутся гены, соответствую-щие наиболее удачному варианту определенной подсистемы (остальные "уродцы" постепенно вымирают). Другими словами, ГА позволяет накапливать удачные решения для систем, состоя-щих из относительно независимых подсистем (большинство современных сложных технических систем, и все известные живые организмы). Соответственно можно предсказать и когда ГА ско-рее всего даст сбой (или, по крайней мере, не покажет особых преимуществ перед методом Монте-Карло) — системы, которые сложно разбить на подсистемы (узлы, модули), а так же в случае неудачного порядка расположения генов (рядом расположены параметры, относящиеся к различным подсистемам), при котором преимущества обмена генет ическим материалом сводят-ся к нулю. Последнее замечание несколько ослабляется в системах с диплоидным (двойным) генетическим набором.

Эволюционное (генетическое) программирование

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

Автоматический синтез технических решений

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

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

Поиск оптимальных структур

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

Любое отдельное ТР, как правило, можно описать единым набором переменных (изме-няемых параметров)

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

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

Постановка задачи структурной оптимизации. Среди задач поиска оптимальных ТР рас-смотрим только подкласс, называемый задачами поиска оптимальных многоэлементных струк-тур ТО или коротко — задач структурной оптимизации.

Строгое определение понятия структуры ТО дать затруднительно, поэтому укажем лишь некоторые инженерные и математические свойства, которые связаны с этим понятием.

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

При этом одно ТР можно представить несколькими близкими структурами.

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

w - другие переменные.

3. Из вектора А выделяют вектор А' независимых переменных, которыми можно варьи-ровать при поиске оптимальных структур. Для зависимых переменных задают алгоритм их оп-ределения через независимые переменные.

4. Вектор А' разделяют на вектор переменных A'S, обеспечивающих изменение структу-ры, и вектор переменных А'P, с помощью которых ставят и решают задачи параметрической оптимизации для заданной структуры. Вектор А'P состоит из набора общих переменных А'0, ко-торые присутствуют при изменении любой структуры, и набора переменных А'C, изменяющихся при переходе от структуры к структуре. При решении задачи параметрической оптимизации для заданной структуры используется только определенная часть переменных из набора Ас.

Так, если в задаче структурной оптимизации с указанным набором переменных струк-тура определяется способом соединения, то можно считать, что A'S есть одна переменная

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

К задачам структурной оптимизации относится задача выбора оптимальной компоновки ТО.

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

Алгоритм поиска глобального экстремума

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

1) синтез допустимой структуры (СДС), обеспечивающий выбор допустимого решения из любой подобласти всей области поиска;

2) шаг локального поиска (ШЛП), обеспечивающий переход от одного решения к дру-гому допустимому решению, как правило, той же структуры, но с улучшенным значением кри-терия; под шагом локального поиска можно понимать некоторый условный шаг по какому-либо алгоритму поиска локального экстремума (например, одна итерация по методу наискорейшего спуска);

3) глобальный поиск, управляющий работой процедур СДС и ШЛП;

4) проверка условий прекращения поиска, определяющая конец решения задачи

Приведем основные рекомендации построения процедур СДС и ШЛП.

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

В целом по процедуре СДС можно дать следующие рекомендации, направленные на повышение вероятности выбора допустимых структур и снижение объема вычислений по оцен-ке недопустимых:

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

ограничения следует проверять не после построения структуры в целом, а по возможно-сти в процессе построения, что позволяет сократить лишнюю работу по ненужным построениям и в ряде случаев сразу внести поправки по устранению дефектов структуры;

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

Процедуры ШЛП включают обычно способы изменения переменных, ориентированные на решение задач как структурной, так и параметрической оптимизации. Приведенные рекомен-дации по построению процедур СДС можно использовать и при построении способов локально-го изменения дискретных переменных. Для изменения непрерывных переменных, как правило, применяют различные алгоритмы локального поиска. Ниже указаны наиболее предпочтитель-ные (о ГА смотри замечание ниже).

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

поиск глобального экстремума осуществляется несколькими конкурирующими реше-ниями (точками);

условия конкуренции одинаковых для всех решений;
в определенные моменты некоторые "худшие" решения бракуются (уничтожаются);

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

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

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

Для удобства изложения алгоритма решение будем называть также точкой (в много-мерном пространстве поиска) и независимо от того, решается ли задача параметрической опти-мизации (1)—(4) или задача структурной оптимизации (6)—(9), будем обозначать его X.

Алгоритм конкурирующих точек

В качестве процедуры ШЛП рекомендуется использовать следующие алгоритмы поиска локального экстремума:

• алгоритм случайного поиска в подпространствах;
• алгоритм случайного поиска с выбором по наилучшей пробе;
• алгоритм сопряженных градиентов;
• алгоритм Нельдера-Мида.

Алгоритм случайного поиска в подпространствах

Рекомендуемый алгоритм случайного поиска в подпространствах можно записать в ви-де следующих рекуррентных выражений:

Некоторые замечания относительно использования ГА

Как можно заметить, ГА представляет собой смешанный алгоритм как для поиска гло-бального экстремума, так и для поиска локального. Это дает нам возможность упростить схему поиска глобально-оптимальных структур за счет использования в ней ГА как в качестве алго-ритма СДС, так и в качестве алгоритма ШЛП. Какие плюсы и минусы данной схемы? Плюсы — простота реализации, универсальность. Минусы — по сравнению со специальными алгоритма-ми СДС, которые будут давать нам гораздо больше жизнеспособных экземпляров, очень уменьшится скорость работы алгоритма. Таким образом, ГА предпочтительно использовать в следующих случаях: простые случаи, в которых программирование специального метода будет продолжаться гораздо дольше, чем поиск решения даже медленным методом; сложный случай, когда мы даже не знаем, с какой стороны подойти к задаче.

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

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

Автоматизированный синтез физических принципов действия

Фонд физико-технических эффектов

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

Главная трудность состоит в том, что инженер обычно знает до 200, а достаточно сво-бодно использует не более 100 ФТЭ, хотя в научно-технической литературе их описано более 3000. Кроме того, в связи с возрастающими темпами развития науки и техники, число ФТЭ по-стоянно увеличивается. Таким образом, в наше время у разработчиков новой техники существу-ет очень большой и возрастающий дефицит информации, необходимой для решения задач по-иска новых ФПД.

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

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

Третий уровень описания совместно с информацией второго уровня дает более подроб-ное описание ФТЭ, объем которого обычно составляет 5—10 машинописных страниц.