Как Вы уже знаете, существуют задачи, для которых доказано отсутствие общего алгоритма решения (например, задача о разрешимости Диофантова множества). В то же время можно сказать, что, если бы мы обладали бесконечным запасом времени и соответствующими ресурсами, то мы могли бы найти решение любой задачи. Здесь имеется в виду не конструирование нового знания на основании имеющегося (вывод новых теорем из аксиом и уже выведенных теорем), а, прежде всего, "тупой" перебор вариантов.
Еще в XVII столетии великий Лейбниц пытался раскрыть тайну "Всеобщего Искусства Изобретения". Он утверждал, что одной из двух частей этого искусства является
Однако прежде чем перейти к рассмотрению улучшенных переборных алгоритмов (улучшенных потому, что для простого перебора у нас в запасе нет вечности), я бы отметил еще один
Прежде всего, упомяну, что отнюдь не все ученые признают наличие эволюции. Многие религиозные течения (например, свидетели Иеговы) считают учение об эволюции живой природы ошибочным. Я не хочу сейчас вдаваться в полемику относительно доказательств за и против по одной простой причине. Даже если я не прав в своих взглядах, объясняя эволюционные алгоритмы как аналоги процессов, происходящих в живой природе, никто не сможет сказать, что эти алгоритмы неверны. Несмотря ни на что, они находят огромное применение в современной науке и технике и показывают подчас просто поразительные результаты.
Основные принципы эволюционной теории заложил Чарльз Дарвин в своей самой революционной работе — "Происхождение видов". Самым важным его выводом был вывод об основной направляющей силе эволюции — ею признавался естественный отбор. Другими словами — выживает сильнейший (в широком смысле этого слова). Забегая вперед, замечу, что любой эволюционный алгоритм имеет такой шаг, как выделение самых сильных (полезных) особей. Вторым, не менее важным выводом Дарвина был вывод об изменчивости организмов. Аналогом данного закона у всех алгоритмов является шаг генерации новых экземпляров искомых объектов (решений, структур, особей, алгоритмов).
Именно отбор наилучших объектов является ключевой эвристикой всех эволюционных методов, позволяющих зачастую уменьшить время поиска решения на несколько порядков по сравнению со случайным поиском. Если попытаться выразить эту эвристику на естественном языке, то скажем: сложно получить самое лучшее решение, модифицируя плохое. Скорее всего, оно получится из нескольких лучших на данный момент.
Из основных особенностей эволюционных алгоритмов можно отметить их некоторую сложность в
Описанный в разделе алгоритмов распознавания образов метод группового учета аргументов так же относится к разряду эволюционных. Его можно представить как следующий цикл:
F лучших, где F — ширина отбора (Как мы видим, налицо все признаки эволюционного алгоритма — отбор (селекция) и генерация нового поколения.
Для начала представим себе целевую функцию от многих переменных, у которой необходимо найти
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 |
Очень важно понять, за счет чего ГА на несколько порядков превосходит по быстроте случайный поиск во многих задачах. Дело здесь, видимо, в том, что большинство систем имеют довольно независимые подсистемы. Вследствие этого, при обмене генетическим материалом часто может встретиться ситуация, когда от каждого из родителей берутся гены, соответствующие наиболее удачному варианту определенной подсистемы (остальные "уродцы" постепенно вымирают). Другими словами, ГА позволяет накапливать удачные решения для систем, состоящих из относительно независимых подсистем (таковы большинство современных сложных технических систем и все известные живые организмы). Соответственно, можно предсказать, и когда ГА скорее всего даст сбой (или, по крайней мере, не покажет особых преимуществ перед
Данные, которые закодированы в генотипе, могут представлять собой команды какой-либо виртуальной машины. В таком случае мы говорим об эволюционном или генетическом программировании. В простейшей ситуации мы можем ничего не менять в
Каждый настоящий изобретатель, каждый творчески работающий конструктор не просто ищет новое, улучшенное ТР, а стремится найти самое эффективное, самое рациональное, лучшее из лучших решений. И такие решения некоторым изобретателям удавалось находить. Это, например, конструкция книги, карандаша, гвоздя, брюк, велосипеда, трансформатора переменного тока, паровой машины и многих других ТО. Такие конструкции в первую очередь характеризуются тем, что они сотни или десятки лет массово производятся и используются без изменения, если не считать мелких усовершенствований.
Наивысшее достижение инженерного творчества заключаются в нахождении глобально оптимальных принципов действия и структур ТО.
Постановка задачи параметрической оптимизации. Прежде чем рассматривать постановку задачи поиска оптимального ТР для заданного физического принципа действия, разберем задачу более низкого уровня, которую называют задачей поиска оптимальных значений параметров для заданного ТР или сокращенно — задачей параметрической оптимизации. Эти задачи неизбежно приходится решать при поиске оптимального ТР, а кроме того, они имеют и самостоятельное значение.
Любое отдельное ТР, как правило, можно описать единым набором переменных (изменяемых параметров)
Х = (x1, ..., xn), (1)
которые могут изменять свои значения в некотором гиперпараллелепипеде
$$a_i\le x_i\le b_i$$ , i = l, ..., n, (2)
где для расширения области поиска не рекомендуется накладывать жестких ограничений на ai, bi.
Математическая модель проектируемого изделия ставит в соответствие каждому набору значений (1) некоторый критерий качества (функцию цели) f(х) и накладывает на переменные (1) дополнительные ограничения, представляемые чаще всего в виде системы нелинейных неравенств
$$g_i (X) \ge 0, j = 1,...,m$$,
Тогда задача поиска оптимальных параметров ТР состоит в нахождении такого набора (1), который удовлетворяет неравенствам (2) и (3) и обеспечивает глобальный D область допустимых решений, удовлетворяющих неравенствам (2), (3), получим задачу n -мерном пространстве:
найти точку $$X* \in D$$, такую, что
$$F(X^*)=\min\limits_{X\in D}F(X)$$
Часто в задачах параметрической оптимизации на переменные или часть из них наложены условия целочисленности или дискретности. В этом случае область поиска D становится заведомо многосвязной, а сама задача с математической точки зрения — многоэкстремальной.
Следует еще заметить, что задачи поиска оптимальных значений параметров в подавляющем большинстве случаев представляют собой многопараметрические многоэкстремальные задачи, в которых функциональные ограничения (3) "вырезают" замысловатые
Постановка задачи структурной оптимизации. Среди задач поиска оптимальных ТР рассмотрим только подкласс, называемый задачами поиска оптимальных многоэлементных структур ТО, или коротко — задач структурной оптимизации.
Строгое определение понятия структуры ТО дать затруднительно, поэтому укажем лишь некоторые инженерные и математические свойства, которые связаны с этим понятием.
С инженерной точки зрения, разные структуры рассматриваемого класса ТО отличаются числом элементов, самими элементами, их компоновкой, характером соединения между элементами и т. д. Понятие структуры в большой мере аналогично понятию технического решения, данному в п. 3 лек. 1, однако имеются различия, которые вызывают необходимость введения этого дополнительного понятия. Во-первых, в рамках заданного физического принципа действия, как правило, существует более широкое множество ТР по сравнению с множеством, которое можно формально описать при постановке и решений задачи структурной оптимизации. Во-вторых, между отдельными ТР подразумеваются более существенные различия по конструктивным признакам, чем различия между отдельными структурами, иногда формально отличающимися значениями несущественных дискретных переменных. Например, на рис. 10.1 показаны две фермы моста с решеткой в виде равнобедренных треугольников, которые имеют одинаковые ТР, но разные структуры. Короче говоря, для заданного физического принципа действия множества возможных ТР и множество возможных структур (для рассматриваемой задачи структурной оптимизации) пересекаются, но, как правило, не совпадают.
При этом одно ТР можно представить несколькими близкими структурами.
С математической точки зрения два варианта ТО будут иметь различную структуру, если соответствующие им задачи параметрической оптимизации по одному и тому же критерию качества и при условии выбора оптимальных параметров каждого элемента структуры имеют различные наборы переменных (1) и функции (3), т. е. для различных структур существуют различные задачи параметрической оптимизации. Под критерием качества также подразумевается физико-технический, экономический или другой показатель (масса, точность, мощность, стоимость и т. п.), по значению которого из любых двух структур можно выбрать лучшую.
(рис 10.1) Пример различных структур при одинаковом ТР
Постановку задач структурной оптимизации обычно начинают с определения набора переменных по следующей методике.
S0, которые в состоянии оценить существующая математическая модель в рассматриваемом классе ТО.Просматривают и анализируют методы преобразования структур. Дополняют множество S0 подмножествами новых структур, которые можно синтезировать и оценить с помощью существующей или доработанной математической модели. В результате строится расширенное множество рассматриваемых структур S и описывающий его набор переменных, который обозначим вектором А. Пусть, например, задача структурной оптимизации допускает следующий набор А:
$$(k,L,i,j, \bar y_1, ... , \bar y_k, \bar z_1, ... , \bar z_{L}, \bar v_{1l}, ... , \bar v_{kL} , \bar w)$$
где k — число элементов в структуре;
L — число способов соединения элементов;
$$\bar y_i$$ — вектор, описывающий геометрические, физические и другие свойства i -го элемента;
i — номер элемента (1, ..., k),
$$\bar z_j$$ — вектор, описывающий геометрические, физич
еские и другие свойства j -го способа соединения:
j — номер способа соединения (1,...,L) ;
$$\bar v_{ij}$$ — вектор, характеризующий положение i-го элемента в пространстве при j -м способе соединения (i = 1, ..., k, j = l, ..., L) ;
$$\bar w$$ — другие переменные.
А выделяют вектор А' независимых переменных, которыми можно варьировать при поиске оптимальных структур. Для зависимых переменных задают алгоритм их определения через независимые переменные.А' разделяют на вектор переменных A'S, обеспечивающих изменение структуры, и вектор переменных А'P, с помощью которых ставят и решают задачи параметрической оптимизации для заданной структуры. Вектор А'P состоит из набора общих переменных А'0, которые присутствуют при изменении любой структуры, и набора переменных А'C, изменяющихся при переходе от структуры к структуре. При решении задачи параметрической оптимизации для заданной структуры используется только определенная часть переменных из набора Ас.Так, если в задаче структурной оптимизации с указанным набором переменных структура определяется способом соединения, то можно считать, что A'S есть одна переменная
$$j, А'_C = \{\bar y'_1 , ...,\bar y'_k , \bar w' ), А'_C = \{А'_{C1}, …, A'_{CL})$$
где $$А'_{CJ,} = \{\bar z'_j ,\bar v'_{kj} ,..., \bar v'_{ki} \}$$ — собственные переменные j -й структуры; штрих означает, что среди соответствующих переменных выбраны независимые.
Допустим, имеется алгоритм выбора из множества S подмножества всех допустимых структур {Si,..., Sm}, у которых существует хотя бы один набор значений параметров, удовлетворяющих заданным ограничениям. Допустим также, что для любой структуры SJ (j = 1, ..., m) можно решить задачу параметрической оптимизации, т. е. задать пространство переменных
$$\overline{X}_j=(x_1^j,K,x_{nj}^j)$$ , j = 1, …, m,(6)
и по единому критерию качества найти допустимые оптимальные параметры структуры SJ. Оптимальные значения параметров структуры SJ будем обозначать через $$X^*_J$$.
Тогда задаче структурной оптимизации можно дать следующую формулировку.
Имеется m nJ -мерных параллелепипедов
$$a_i^j \le x_i^j \le b_i^j$$ , i = 1, …, nJ, j = 1, …, m,(7)
как с непрерывным, так и с дискретным характером изменения переменных . Для каждого из параллелепипедов задана по единому критерию качества целевая функция
$$f=f'(\overline{X}_j)$$ , j = 1, …, m,(8)
и система ограничений
$$g'_r(\overline{X}_j) \ge 0$$ , r = 1, …, pJ, j = 1, …, m, (9)
Требуется найти точку $$\overline{X}^{ullet}_i$$, принадлежащую $$j^*$$ -му параллелепипеду, для которой
$$\left{ \begin{aligned} g_r^{j^{ullet}}(\overline{X}^{ullet}_{J^{ullet}})\ge 0, r=1,K,p_j^{ullet};\\ f^{j^{ullet}}(\overline{X}^{ullet}_{J^{ullet}})= \min f^j(\overline{X}^{ullet}_{J}), \end{aligned} \right\}.$$Таким образом, задача структурной оптимизации состоит в нахождении глобально-оптимальной структуры и глобально-оптимальных значений переменных внутри этой структуры, т. е. эту задачу можно назвать также задачей структурно-параметрической оптимизации.
К задачам структурной оптимизации относится задача выбора оптимальной компоновки ТО.
Отметим некоторые особенности задач структурной оптимизации. Во-первых, почти всегда в этих задачах одновременно присутствуют и дискретные, и непрерывные переменные, т. е. задачи структурной оптимизации в общем случае относятся к смешанным задачам
Алгоритм поиска глобально-оптимального решения можно использовать для решения задач как параметрической, так и структурной оптимизации. Укрупненная блок-схема алгоритма включает четыре процедуры:
Приведем основные рекомендации построения процедур СДС и ШЛП.
В некоторых случаях построение процедуры СДС можно свести к предварительному составлению набора допустимых структур, из которого выбирают структуры при каждом обращении к процедуре СДС. Если суть этой процедуры состоит в выборе по возможности допустимого набора переменных структурной оптимизации, то представляется полезным включать в нее правила выбора переменных, основанные на эвристических соображениях, аналитических и экспериментальных исследованиях, изучении опыта проектирования и эксплуатации аналогичных TО. Для некоторых сложных или малоизученных задач проектирования трудно построить процедуру СДС, обеспечивающую получение допустимых структур. В этом случае в процедуру целесообразно включать операции преобразования недопустимых структур в допустимые. Набор таких операций можно составить из подходящих эвристических приемов (для задач, связанных с техническими объектами, сборники таких приемов можно найти в соответствующей литературе, в которой решение изобретательских задач рассматривается более подробно). Преобразование недопустимых структур в допустимые можно также решать как задачу оптимизации. В диалоговом режиме работы санкцию процедуры СДС может взять на себя проектировщик.
В целом по процедуре СДС можно дать следующие рекомендации, направленные на повышение вероятности выбора допустимых структур и снижение объема вычислений по оценке недопустимых:
Процедуры ШЛП включают обычно способы изменения переменных, ориентированные на решение задач как структурной, так и параметрической оптимизации. Приведенные рекомендации по построению процедур СДС можно использовать и при построении способов локального изменения дискретных переменных. Для изменения непрерывных переменных, как правило, применяют различные алгоритмы локального поиска. Ниже указаны наиболее предпочтительные (о ГА смотри замечание ниже).
В качестве процедуры глобального поиска применяется алгоритм конкурирующих точек. В основе этого алгоритма лежит принцип эволюции популяции живых организмов, находящихся в ограниченном пространстве, например, на острове. В такой популяции резко обостряется конкуренция между отдельными особями. В связи с этим в основу алгоритма конкурирующих точек положены следующие положения:
Конкуренция позволяет за счет отсева решений, спускающихся в локальные
Алгоритм конкурирующих точек — один из наиболее простых и эффективных по сравнению с другими распространенными алгоритмами поиска глобального
Для удобства изложения алгоритма решение будем называть также точкой (в многомерном пространстве поиска) и независимо от того, решается ли задача параметрической оптимизации (1)—(4) или задача структурной оптимизации (6)—(9), будем обозначать его X.
Алгоритм конкурирующих точек в общем виде включает следующие операции.
По процедуре СДС синтезируется $$l(l=\eta + \lambda_0)$$ точек $$\overline{X}_j (j=1,...,l)$$, в которых определяется значение минимизируемой функции (критерия сравнения). Из этих $$l$$ точек отбирается $$\eta$$ точек, имеющих наилучшие значения критерия, которые в дальнейшем называются основными. Запоминается наихудшее значение критерия основных точек $$\phi_0$$. При этом считается, что совершен нулевой глобальный (групповой) шаг поиска (t = 0).
Таким образом, на t -м групповом шаге поиска имеем основные точки
$$\overline{X}_1^t,\overline{X}_2^t,K,\overline{X}_{\eta}^t$$
и, соответственно, невозрастающую последовательность чисел
$$\phi_0,\phi_1,...,\phi_t$$
Каждая основная точка делает шаг локального поиска, в результате чего точки (10) переходят в новую последовательность
$$\overline{X}_1^{t+1},\overline{X}_2^{t+1},K,\overline{X}_{\eta}^{t+1}$$
Синтезируется $$\lambda_{t+1}$$ дополнительных допустимых точек, каждой из которых разрешается сделать t+1 шагов локального поиска при условии, что после каждого шага с номером $$\tau (0 \le \tau \le t)$$ ее критерий не хуже, чем соответствующий член последовательности (11). При нарушении этого условия точка исключается и не участвует в дальнейшем поиске глобального t+1 шаг локального поиска:
$$\overline{X}_1^{t+1},\overline{X}_2^{t+1},K,\overline{X}_{q}^{t+1}$$
Среди точек (12) и (13) отбирается $$\eta$$ точек с лучшими критериями:
$$\overline{X}_1^{t+1},\overline{X}_2^{t+1},K,\overline{X}_{\eta}^{t+1}$$
которые являются основными на t+1 -м групповом шаге поиска. Значение худшего критерия точек из последовательности (14) дополняет последовательность (11) числом $$\phi_{t+1}$$.
Цикл по пп. 2—4 повторяется до нахождения глобального Т групповых шагов.
Считая параметры $$\lambda_i$$ независимыми от i, будем иметь только два настраиваемых параметра алгоритма; $$\eta$$ — число основных точек и $$\lambda$$ — число дополнительных точек.
Проведенные исследования позволяют рекомендовать следующие оптимальные значения этих параметров: $$\eta = 2…3$$, $$\lambda = 12…18$$. Для простоты реализации алгоритма можно брать постоянные значения $$\eta$$ и $$\lambda$$.
В качестве процедуры ШЛП рекомендуется использовать следующие алгоритмы поиска локального
Рекомендуемый алгоритм случайного поиска в подпространствах можно записать в виде следующих рекуррентных выражений:
$$\overline{X}_{i+1}=\overline{X}_{i}+\Delta \overline{X}_{i+1}$$ ;
$$\overline{X}_{i}=\overline{X}_{i-h}$$ при $$[ f(\overline{X}_{i-1})<f(\overline{X}_{i}) ] \vee [g(\overline{X}_{i})<0]$$.
Здесь h — число последовательно неудачных шагов поиска; $$\Delta \overline{X}_{i+1}$$ определяется по формуле:
где a —максимальная величина рабочего шага поиска;
$$\overline{\zeta}_{i+1}$$ — вектор случайных чисел; $$\Delta \overline{X}_{i-1},\Delta \overline{X}_{i},\Delta \overline{X}_{i+1}$$ — векторы приращений на (i-1)-, i-, (i+1) -м шагах поиска; $$\overline{X}_{i},\overline{X}_{i+1},\overline{X}_{i+h}$$ — векторы, описанные по формуле (1); $$f(\overline{X}_{i-1}),f(\overline{X}_{i}),f(\overline{X}_{i+1})$$ — значения критериев качества после осуществления на (i-1)-, i-, (i+1) -го шагов поиска.
Вектор случайных чисел
$$\overline{\zeta}_{i+1}=(0,K,0,\zeta^{i+1}_k,K,\zeta^{i+1}_L,0,K,0)$$
$$\overline{\zeta}^{i+1}_{k}=\overline{\zeta}^{i+1}_{k+1}=\Lambda =\overline{\zeta}^{i+1}_{L}=\psi $$
где $$\psi$$ — случайное равномерно распределенное число, выбираемое из интервала [-1, 1] ; k и L —случайные целые числа, распределенные на отрезке [1, n] и упорядоченные соотношением $$k\le L$$.
Имеются и другие модификации этого алгоритма, которые могут оказаться более эффективными.
Как можно заметить, ГА представляет собой смешанный алгоритм как для поиска глобального
Интересно также отметить общие стороны ГА и алгоритма случайного поиска в подпространствах. Оба эти алгоритма при поиске оптимума изменяют не все возможные переменные, а только часть их. Это, казалось бы, мелкое усовершенствование ведет к поразительным результатам — эти алгоритмы в среднем дают трудоемкость нахождения решения на порядок ниже, чем метод сопряженных градиентов, и на два порядка ниже, чем метод случайного поиска по всему пространству переменных. Другими словами, эти алгоритмы используют одно из свойств нашего мира — независимость различных подсистем объектов.
Возвращаясь к основному вопросу данных лекций — интеллектуальным задачам, скажем, что данные алгоритмы ведут себя как опытные инженеры при поиске неисправностей (очень интеллектуальная по всем параметрам задача), и соблюдают заповедь — "никогда не трогать все сразу, только по очереди".
Как Вы уже знаете, существуют задачи, для которых доказано отсутствие общего алгоритма решения (например, задача о разрешимости Диофантова множества). В то же время можно сказать, что, если бы мы обладали бесконечным запасом времени и соответствующими ресурсами, то мы могли бы найти решение любой задачи. Здесь имеется в виду не конструирование нового знания на основании имеющегося (вывод новых теорем из аксиом и уже выведенных теорем), а, прежде всего, "тупой" перебор вариантов.
Еще в XVII столетии великий Лейбниц пытался раскрыть тайну "Всеобщего Искусства Изобретения". Он утверждал, что одной из двух частей этого искусства является
Однако прежде чем перейти к рассмотрению улучшенных переборных алгоритмов (улучшенных потому, что для простого перебора у нас в запасе нет вечности), я бы отметил еще один
Прежде всего, упомяну, что отнюдь не все ученые признают наличие эволюции. Многие религиозные течения (например, свидетели Иеговы) считают учение об эволюции живой природы ошибочным. Я не хочу сейчас вдаваться в полемику относительно доказательств за и против по одной простой причине. Даже если я не прав в своих взглядах, объясняя эволюционные алгоритмы как аналоги процессов, происходящих в живой природе, никто не сможет сказать, что эти алгоритмы неверны. Несмотря ни на что, они находят огромное применение в современной науке и технике и показывают подчас просто поразительные результаты.
Основные принципы эволюционной теории заложил Чарльз Дарвин в своей самой революционной работе — "Происхождение видов". Самым важным его выводом был вывод об основной направляющей силе эволюции — ею признавался естественный отбор. Другими словами — выживает сильнейший (в широком смысле этого слова). Забегая вперед, замечу, что любой эволюционный алгоритм имеет такой шаг, как выделение самых сильных (полезных) особей. Вторым, не менее важным выводом Дарвина был вывод об изменчивости организмов. Аналогом данного закона у всех алгоритмов является шаг генерации новых экземпляров искомых объектов (решений, структур, особей, алгоритмов).
Именно отбор наилучших объектов является ключевой эвристикой всех эволюционных методов, позволяющих зачастую уменьшить время поиска решения на несколько порядков по сравнению со случайным поиском. Если попытаться выразить эту эвристику на естественном языке, то скажем: сложно получить самое лучшее решение, модифицируя плохое. Скорее всего, оно получится из нескольких лучших на данный момент.
Из основных особенностей эволюционных алгоритмов можно отметить их некоторую сложность в
Описанный в разделе алгоритмов распознавания образов метод группового учета аргументов так же относится к разряду эволюционных. Его можно представить как следующий цикл:
F лучших, где F — ширина отбора (Как мы видим, налицо все признаки эволюционного алгоритма — отбор (селекция) и генерация нового поколения.
Для начала представим себе целевую функцию от многих переменных, у которой необходимо найти
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 |
Очень важно понять, за счет чего ГА на несколько порядков превосходит по быстроте случайный поиск во многих задачах. Дело здесь, видимо, в том, что большинство систем имеют довольно независимые подсистемы. Вследствие этого, при обмене генетическим материалом часто может встретиться ситуация, когда от каждого из родителей берутся гены, соответствующие наиболее удачному варианту определенной подсистемы (остальные "уродцы" постепенно вымирают). Другими словами, ГА позволяет накапливать удачные решения для систем, состоящих из относительно независимых подсистем (таковы большинство современных сложных технических систем и все известные живые организмы). Соответственно, можно предсказать, и когда ГА скорее всего даст сбой (или, по крайней мере, не покажет особых преимуществ перед
Данные, которые закодированы в генотипе, могут представлять собой команды какой-либо виртуальной машины. В таком случае мы говорим об эволюционном или генетическом программировании. В простейшей ситуации мы можем ничего не менять в
Каждый настоящий изобретатель, каждый творчески работающий конструктор не просто ищет новое, улучшенное ТР, а стремится найти самое эффективное, самое рациональное, лучшее из лучших решений. И такие решения некоторым изобретателям удавалось находить. Это, например, конструкция книги, карандаша, гвоздя, брюк, велосипеда, трансформатора переменного тока, паровой машины и многих других ТО. Такие конструкции в первую очередь характеризуются тем, что они сотни или десятки лет массово производятся и используются без изменения, если не считать мелких усовершенствований.
Наивысшее достижение инженерного творчества заключаются в нахождении глобально оптимальных принципов действия и структур ТО.
Постановка задачи параметрической оптимизации. Прежде чем рассматривать постановку задачи поиска оптимального ТР для заданного физического принципа действия, разберем задачу более низкого уровня, которую называют задачей поиска оптимальных значений параметров для заданного ТР или сокращенно — задачей параметрической оптимизации. Эти задачи неизбежно приходится решать при поиске оптимального ТР, а кроме того, они имеют и самостоятельное значение.
Любое отдельное ТР, как правило, можно описать единым набором переменных (изменяемых параметров)
Х = (x1, ..., xn), (1)
которые могут изменять свои значения в некотором гиперпараллелепипеде
$$a_i\le x_i\le b_i$$ , i = l, ..., n, (2)
где для расширения области поиска не рекомендуется накладывать жестких ограничений на ai, bi.
Математическая модель проектируемого изделия ставит в соответствие каждому набору значений (1) некоторый критерий качества (функцию цели) f(х) и накладывает на переменные (1) дополнительные ограничения, представляемые чаще всего в виде системы нелинейных неравенств
$$g_i (X) \ge 0, j = 1,...,m$$,
Тогда задача поиска оптимальных параметров ТР состоит в нахождении такого набора (1), который удовлетворяет неравенствам (2) и (3) и обеспечивает глобальный D область допустимых решений, удовлетворяющих неравенствам (2), (3), получим задачу n -мерном пространстве:
найти точку $$X* \in D$$, такую, что
$$F(X^*)=\min\limits_{X\in D}F(X)$$
Часто в задачах параметрической оптимизации на переменные или часть из них наложены условия целочисленности или дискретности. В этом случае область поиска D становится заведомо многосвязной, а сама задача с математической точки зрения — многоэкстремальной.
Следует еще заметить, что задачи поиска оптимальных значений параметров в подавляющем большинстве случаев представляют собой многопараметрические многоэкстремальные задачи, в которых функциональные ограничения (3) "вырезают" замысловатые
Постановка задачи структурной оптимизации. Среди задач поиска оптимальных ТР рассмотрим только подкласс, называемый задачами поиска оптимальных многоэлементных структур ТО, или коротко — задач структурной оптимизации.
Строгое определение понятия структуры ТО дать затруднительно, поэтому укажем лишь некоторые инженерные и математические свойства, которые связаны с этим понятием.
С инженерной точки зрения, разные структуры рассматриваемого класса ТО отличаются числом элементов, самими элементами, их компоновкой, характером соединения между элементами и т. д. Понятие структуры в большой мере аналогично понятию технического решения, данному в п. 3 лек. 1, однако имеются различия, которые вызывают необходимость введения этого дополнительного понятия. Во-первых, в рамках заданного физического принципа действия, как правило, существует более широкое множество ТР по сравнению с множеством, которое можно формально описать при постановке и решений задачи структурной оптимизации. Во-вторых, между отдельными ТР подразумеваются более существенные различия по конструктивным признакам, чем различия между отдельными структурами, иногда формально отличающимися значениями несущественных дискретных переменных. Например, на рис. 10.1 показаны две фермы моста с решеткой в виде равнобедренных треугольников, которые имеют одинаковые ТР, но разные структуры. Короче говоря, для заданного физического принципа действия множества возможных ТР и множество возможных структур (для рассматриваемой задачи структурной оптимизации) пересекаются, но, как правило, не совпадают.
При этом одно ТР можно представить несколькими близкими структурами.
С математической точки зрения два варианта ТО будут иметь различную структуру, если соответствующие им задачи параметрической оптимизации по одному и тому же критерию качества и при условии выбора оптимальных параметров каждого элемента структуры имеют различные наборы переменных (1) и функции (3), т. е. для различных структур существуют различные задачи параметрической оптимизации. Под критерием качества также подразумевается физико-технический, экономический или другой показатель (масса, точность, мощность, стоимость и т. п.), по значению которого из любых двух структур можно выбрать лучшую.(рис 10.1) Пример различных структур при одинаковом ТР
Постановку задач структурной оптимизации обычно начинают с определения набора переменных по следующей методике.
S0, которые в состоянии оценить существующая математическая модель в рассматриваемом классе ТО.Просматривают и анализируют методы преобразования структур. Дополняют множество S0 подмножествами новых структур, которые можно синтезировать и оценить с помощью существующей или доработанной математической модели. В результате строится расширенное множество рассматриваемых структур S и описывающий его набор переменных, который обозначим вектором А. Пусть, например, задача структурной оптимизации допускает следующий набор А:
$$(k,L,i,j, \bar y_1, ... , \bar y_k, \bar z_1, ... , \bar z_{L}, \bar v_{1l}, ... , \bar v_{kL} , \bar w)$$
где k — число элементов в структуре;
L — число способов соединения элементов;
$$\bar y_i$$ — вектор, описывающий геометрические, физические и другие свойства i -го элемента;
i — номер элемента (1, ..., k),
$$\bar z_j$$ — вектор, описывающий геометрические, физич
еские и другие свойства j -го способа соединения:
j — номер способа соединения (1,...,L) ;
$$\bar v_{ij}$$ — вектор, характеризующий положение i-го элемента в пространстве при j -м способе соединения (i = 1, ..., k, j = l, ..., L) ;
$$\bar w$$ — другие переменные.
А выделяют вектор А' независимых переменных, которыми можно варьировать при поиске оптимальных структур. Для зависимых переменных задают алгоритм их определения через независимые переменные.А' разделяют на вектор переменных A'S, обеспечивающих изменение структуры, и вектор переменных А'P, с помощью которых ставят и решают задачи параметрической оптимизации для заданной структуры. Вектор А'P состоит из набора общих переменных А'0, которые присутствуют при изменении любой структуры, и набора переменных А'C, изменяющихся при переходе от структуры к структуре. При решении задачи параметрической оптимизации для заданной структуры используется только определенная часть переменных из набора Ас.Так, если в задаче структурной оптимизации с указанным набором переменных структура определяется способом соединения, то можно считать, что A'S есть одна переменная
$$j, А'_C = \{\bar y'_1 , ...,\bar y'_k , \bar w' ), А'_C = \{А'_{C1}, …, A'_{CL})$$
где $$А'_{CJ,} = \{\bar z'_j ,\bar v'_{kj} ,..., \bar v'_{ki} \}$$ — собственные переменные j -й структуры; штрих означает, что среди соответствующих переменных выбраны независимые.
Допустим, имеется алгоритм выбора из множества S подмножества всех допустимых структур {Si,..., Sm}, у которых существует хотя бы один набор значений параметров, удовлетворяющих заданным ограничениям. Допустим также, что для любой структуры SJ (j = 1, ..., m) можно решить задачу параметрической оптимизации, т. е. задать пространство переменных
$$\overline{X}_j=(x_1^j,K,x_{nj}^j)$$ , j = 1, …, m,(6)
и по единому критерию качества найти допустимые оптимальные параметры структуры SJ. Оптимальные значения параметров структуры SJ будем обозначать через $$X^*_J$$.
Тогда задаче структурной оптимизации можно дать следующую формулировку.
Имеется m nJ -мерных параллелепипедов
$$a_i^j \le x_i^j \le b_i^j$$ , i = 1, …, nJ, j = 1, …, m,(7)
как с непрерывным, так и с дискретным характером изменения переменных . Для каждого из параллелепипедов задана по единому критерию качества целевая функция
$$f=f'(\overline{X}_j)$$ , j = 1, …, m,(8)
и система ограничений
$$g'_r(\overline{X}_j) \ge 0$$ , r = 1, …, pJ, j = 1, …, m, (9)
Требуется найти точку $$\overline{X}^{ullet}_i$$, принадлежащую $$j^*$$ -му параллелепипеду, для которой
$$\left{ \begin{aligned} g_r^{j^{ullet}}(\overline{X}^{ullet}_{J^{ullet}})\ge 0, r=1,K,p_j^{ullet};\\ f^{j^{ullet}}(\overline{X}^{ullet}_{J^{ullet}})= \min f^j(\overline{X}^{ullet}_{J}), \end{aligned} \right\}.$$Таким образом, задача структурной оптимизации состоит в нахождении глобально-оптимальной структуры и глобально-оптимальных значений переменных внутри этой структуры, т. е. эту задачу можно назвать также задачей структурно-параметрической оптимизации.
К задачам структурной оптимизации относится задача выбора оптимальной компоновки ТО.
Отметим некоторые особенности задач структурной оптимизации. Во-первых, почти всегда в этих задачах одновременно присутствуют и дискретные, и непрерывные переменные, т. е. задачи структурной оптимизации в общем случае относятся к смешанным задачам
Алгоритм поиска глобально-оптимального решения можно использовать для решения задач как параметрической, так и структурной оптимизации. Укрупненная блок-схема алгоритма включает четыре процедуры:
Приведем основные рекомендации построения процедур СДС и ШЛП.
В некоторых случаях построение процедуры СДС можно свести к предварительному составлению набора допустимых структур, из которого выбирают структуры при каждом обращении к процедуре СДС. Если суть этой процедуры состоит в выборе по возможности допустимого набора переменных структурной оптимизации, то представляется полезным включать в нее правила выбора переменных, основанные на эвристических соображениях, аналитических и экспериментальных исследованиях, изучении опыта проектирования и эксплуатации аналогичных TО. Для некоторых сложных или малоизученных задач проектирования трудно построить процедуру СДС, обеспечивающую получение допустимых структур. В этом случае в процедуру целесообразно включать операции преобразования недопустимых структур в допустимые. Набор таких операций можно составить из подходящих эвристических приемов (для задач, связанных с техническими объектами, сборники таких приемов можно найти в соответствующей литературе, в которой решение изобретательских задач рассматривается более подробно). Преобразование недопустимых структур в допустимые можно также решать как задачу оптимизации. В диалоговом режиме работы санкцию процедуры СДС может взять на себя проектировщик.
В целом по процедуре СДС можно дать следующие рекомендации, направленные на повышение вероятности выбора допустимых структур и снижение объема вычислений по оценке недопустимых:
Процедуры ШЛП включают обычно способы изменения переменных, ориентированные на решение задач как структурной, так и параметрической оптимизации. Приведенные рекомендации по построению процедур СДС можно использовать и при построении способов локального изменения дискретных переменных. Для изменения непрерывных переменных, как правило, применяют различные алгоритмы локального поиска. Ниже указаны наиболее предпочтительные (о ГА смотри замечание ниже).
В качестве процедуры глобального поиска применяется алгоритм конкурирующих точек. В основе этого алгоритма лежит принцип эволюции популяции живых организмов, находящихся в ограниченном пространстве, например, на острове. В такой популяции резко обостряется конкуренция между отдельными особями. В связи с этим в основу алгоритма конкурирующих точек положены следующие положения:
Конкуренция позволяет за счет отсева решений, спускающихся в локальные
Алгоритм конкурирующих точек — один из наиболее простых и эффективных по сравнению с другими распространенными алгоритмами поиска глобального
Для удобства изложения алгоритма решение будем называть также точкой (в многомерном пространстве поиска) и независимо от того, решается ли задача параметрической оптимизации (1)—(4) или задача структурной оптимизации (6)—(9), будем обозначать его X.
Алгоритм конкурирующих точек в общем виде включает следующие операции.
По процедуре СДС синтезируется $$l(l=\eta + \lambda_0)$$ точек $$\overline{X}_j (j=1,...,l)$$, в которых определяется значение минимизируемой функции (критерия сравнения). Из этих $$l$$ точек отбирается $$\eta$$ точек, имеющих наилучшие значения критерия, которые в дальнейшем называются основными. Запоминается наихудшее значение критерия основных точек $$\phi_0$$. При этом считается, что совершен нулевой глобальный (групповой) шаг поиска (t = 0).
Таким образом, на t -м групповом шаге поиска имеем основные точки
$$\overline{X}_1^t,\overline{X}_2^t,K,\overline{X}_{\eta}^t$$
и, соответственно, невозрастающую последовательность чисел
$$\phi_0,\phi_1,...,\phi_t$$
Каждая основная точка делает шаг локального поиска, в результате чего точки (10) переходят в новую последовательность
$$\overline{X}_1^{t+1},\overline{X}_2^{t+1},K,\overline{X}_{\eta}^{t+1}$$
Синтезируется $$\lambda_{t+1}$$ дополнительных допустимых точек, каждой из которых разрешается сделать t+1 шагов локального поиска при условии, что после каждого шага с номером $$\tau (0 \le \tau \le t)$$ ее критерий не хуже, чем соответствующий член последовательности (11). При нарушении этого условия точка исключается и не участвует в дальнейшем поиске глобального t+1 шаг локального поиска:
$$\overline{X}_1^{t+1},\overline{X}_2^{t+1},K,\overline{X}_{q}^{t+1}$$
Среди точек (12) и (13) отбирается $$\eta$$ точек с лучшими критериями:
$$\overline{X}_1^{t+1},\overline{X}_2^{t+1},K,\overline{X}_{\eta}^{t+1}$$
которые являются основными на t+1 -м групповом шаге поиска. Значение худшего критерия точек из последовательности (14) дополняет последовательность (11) числом $$\phi_{t+1}$$.
Цикл по пп. 2—4 повторяется до нахождения глобального Т групповых шагов.
Считая параметры $$\lambda_i$$ независимыми от i, будем иметь только два настраиваемых параметра алгоритма; $$\eta$$ — число основных точек и $$\lambda$$ — число дополнительных точек.
Проведенные исследования позволяют рекомендовать следующие оптимальные значения этих параметров: $$\eta = 2…3$$, $$\lambda = 12…18$$. Для простоты реализации алгоритма можно брать постоянные значения $$\eta$$ и $$\lambda$$.
В качестве процедуры ШЛП рекомендуется использовать следующие алгоритмы поиска локального
Рекомендуемый алгоритм случайного поиска в подпространствах можно записать в виде следующих рекуррентных выражений:
$$\overline{X}_{i+1}=\overline{X}_{i}+\Delta \overline{X}_{i+1}$$ ;
$$\overline{X}_{i}=\overline{X}_{i-h}$$ при $$[ f(\overline{X}_{i-1})<f(\overline{X}_{i}) ] \vee [g(\overline{X}_{i})<0]$$.
Здесь h — число последовательно неудачных шагов поиска; $$\Delta \overline{X}_{i+1}$$ определяется по формуле:
где a —максимальная величина рабочего шага поиска;
$$\overline{\zeta}_{i+1}$$ — вектор случайных чисел; $$\Delta \overline{X}_{i-1},\Delta \overline{X}_{i},\Delta \overline{X}_{i+1}$$ — векторы приращений на (i-1)-, i-, (i+1) -м шагах поиска; $$\overline{X}_{i},\overline{X}_{i+1},\overline{X}_{i+h}$$ — векторы, описанные по формуле (1); $$f(\overline{X}_{i-1}),f(\overline{X}_{i}),f(\overline{X}_{i+1})$$ — значения критериев качества после осуществления на (i-1)-, i-, (i+1) -го шагов поиска.
Вектор случайных чисел
$$\overline{\zeta}_{i+1}=(0,K,0,\zeta^{i+1}_k,K,\zeta^{i+1}_L,0,K,0)$$
$$\overline{\zeta}^{i+1}_{k}=\overline{\zeta}^{i+1}_{k+1}=\Lambda =\overline{\zeta}^{i+1}_{L}=\psi $$
где $$\psi$$ — случайное равномерно распределенное число, выбираемое из интервала [-1, 1] ; k и L —случайные целые числа, распределенные на отрезке [1, n] и упорядоченные соотношением $$k\le L$$.
Имеются и другие модификации этого алгоритма, которые могут оказаться более эффективными.
Как можно заметить, ГА представляет собой смешанный алгоритм как для поиска глобального
Интересно также отметить общие стороны ГА и алгоритма случайного поиска в подпространствах. Оба эти алгоритма при поиске оптимума изменяют не все возможные переменные, а только часть их. Это, казалось бы, мелкое усовершенствование ведет к поразительным результатам — эти алгоритмы в среднем дают трудоемкость нахождения решения на порядок ниже, чем метод сопряженных градиентов, и на два порядка ниже, чем метод случайного поиска по всему пространству переменных. Другими словами, эти алгоритмы используют одно из свойств нашего мира — независимость различных подсистем объектов.
Возвращаясь к основному вопросу данных лекций — интеллектуальным задачам, скажем, что данные алгоритмы ведут себя как опытные инженеры при поиске неисправностей (очень интеллектуальная по всем параметрам задача), и соблюдают заповедь — "никогда не трогать все сразу, только по очереди".
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.