Среди множества проблем, которые возникают перед исследователями как в области теории, так и в многочисленных практических приложениях значительную долю составляют так называемые оптимизационные проблемы. Понятие оптимальности, по-видимому, знакомо почти каждому и вошло в практику большинства предметных областей. С оптимизационной проблемой мы сталкиваемся каждый раз, когда возникает необходимость выбора из некоторого множества возможных решений наилучшего по определенным критериями и, как правило, удовлетворяющего заданным условиям и ограничениям. Само понятие оптимальности получает совершенно строгое толкование в математических теориях, однако в других областях оно может интерпретироваться скорее содержательно. Тем не менее различие между строгим и содержательным понятиями оптимальности, как правило, очень незначительно.
Существуют классы оптимизационных задач, решение которых удается находить с помощью достаточно эффективных методов, вполне приемлемых по трудоемкости. Вместе с тем имеются и такие классы оптимизационных задач (так называемые NP- полные задачи), решение которых невозможно найти без полного перебора вариантов. В частности, к числу последних относятся многие разновидности задач многокритериальной оптимизации. Известно, что при большой размерности этих задач реализация перебора вариантов практически невозможна из-за чрезвычайно больших временных затрат.
В этой ситуации альтернативным походом к решению упомянутых задач является применение методов, базирующихся на методологии эволюционных вычислений. Предлагаемое пособие содержит изложение основ эволюционных вычислений и их приложений к решению различных проблем, включая проблемы экономики, прогнозирования финансовых рынков, инвестиций, бизнеса, комбинаторной оптимизации, сложных задач в различных технических разработках и т.п. Эффективность различных методов в рамках эволюционного подхода подтверждается многочисленными данными, касающимися достигаемым реальным эффектом. При этом хотя объем вычислений может оказаться большим, но скорость, с которой он растет при увеличении размерности задачи, обычно меньше, чем у остальных известных методов. Отметим, что после того как компьютерные системы стали достаточно быстродействующими и недорогими, эволюционные методы превратились в важный инструмент поиска близких к оптимальным решений задач, которые до этого считались неразрешимыми.
Основной целью учебного пособия является систематическое изложение перспективного направления в области теории и практики искусственного интеллекта. Пособие рассчитано на студентов и аспирантов вузов, обучающихся по направлениям, связанным с прикладной информатикой и математикой, компьютерными и программными системами, с интеллектуальными системами обработки информации.
Освоение представленного в пособии материала предполагает знакомство читателя с математикой и информатикой в объеме первых двух курсов технического вуза, основами дискретной математики и методов оптимизации.
В настоящее время оформилось и успешно развивается новое направление в теории и практике искусственного интеллекта – эволюционные вычисления (ЭВ). Этот термин обычно используется для общего описания алгоритмов поиска, оптимизации или обучения, основанных на некоторых формализованных принципах естественного эволюционного отбора. Особенности идей эволюции и самоорганизации заключаются в том, что они являются плодотворными и полезность их применения не только для биологических систем перманентно подтверждается. Эти идеи в настоящее время с успехом используются при разработке многих технических и, в особенности, программных систем.
Высокая согласованность и эффективность работы элементов биологических систем приводила целый ряд исследователей к естественной мысли о возможности использования принципов биологической эволюции для оптимизации важных для приложений систем, природа которых отлична от биологической. Так, в 1966 году Фогель Л., Оуенс С. и Уолш М. в [1] подобную идею использовали для построения схемы эволюции логических автоматов, решающих задачи прогноза. В 1975 году была опубликована основополагающая работа Дж. Холланда [2], в которой был предложен генетический алгоритм, развивающий ту же идею. Д.Гольдберг, ученик Дж. Холланда, в работе [3] , выполненной в Мичиганском университете, успешно развил и расширил области его применения.
В 60-х годах прошлого века в Германии Рохенберг И., Швефель Г.-П., и др. [4] начали разработку так назывемой эволюционной стратегии. Перечисленные работы послужили толчком и основой развития прикладного направления, которое можно назвать эволюционными алгоритмами. К их числу, помимо упомянутых генетических алгоритмов и эволюционных стратегий, относятся также эволюционное программирование, ориентированное на оптимизацию функций без использования рекомбинаций, и генетическое программирование, использующее эволюционные идеи для оптимизации компьютерных программ. Основополагающая работа по эволюционному программированию принадлежит Дж. Коза [5] из Массачусетского технологического института.
Отметим, что аналогичные исследования успешно проводились отечественными учеными еще в Советском Союзе. Так, значительный вклад в развитие указанных направлений внесли Ивахненко А.Г. [6], Цыпкин Я.З. [7], Расстригин Л.А. [8] и др. В настоящее время исследования по ЭВ активно ведутся Букатовой [9,10], Курейчиком В.М. [11,12,13], их сотрудниками и учениками, а также многими другими исследователями.
Учебное пособие состоит из пяти частей.
В первой части "Основы генетических алгоритмов" (разделы пособия 1-5) изложены идейная сторона простых генетических алгоритмов, их математические основы, подробно описаны примеры построения генетических алгоритмов для решения конкретных задач комбинаторной оптимзации и, наконец, представлены современные модификации и обобщения этих алгоритмов.
Во второй части "Генетическое программирование и машинное обучение" (разделы 6-7) описана концепция компьютерного синтеза программ (с различными структурами их представления – линейными, древовидными, графоподобными) с использованием генетических алгоритмов. Изложены два основных подхода при машинном обучении - Мичиганский и Питтсбургский.
В третьей части "Вероятностные генетические алгоритмы"(раздел 8) приведен другой – вероятностный подход в эволюционных вычислениях, где популяция представляется вектором вероятностей.
В четвертой части "Эволюционные стратегии" (раздел 9) представлена оригинальная парадигма, основанная на эволюции популяции потенциальных решений. Ее принципиалное отличие состоит в том, что генетические операторы используются здесь на уровне фенотипа, а не генотипа, как это было в генетических алгоритмах.
В пятой части "Эволюционное программирование" (раздел 10) содержится описание основанного Фогелем Л.Дж. гибкого подхода в эволюционных вычислениях. В нем форма представления потенциального решения и генетические операторы адаптируются к решаемой проблемы в достаточно широких пределах. В частности, в качестве особи в процессе эволюции Фогелем используются конечные автоматы и целью эволюции является способность решения задач прогнозирования.
В шестой части "Роевой интеллект" (разделы 11-12) описаны принципы и методы оптимизации, базирующиеся на коллективном поведении децентрализованных самоорганизующихся систем. Такие системы представляются, например, в виде графа, содержащего множество вершин (агентов), локально взаимодействующих между собой и с окружающей средой. Имеющиеся экспериментальные данные подверждают эффективность роевого интеллекта (муравьиных, пчелиных, роевых и т.п. алгоритмов) для решения многих оптимизационных задач.
Заканчивая введение заметим, что в пособии представлены не все аспекты быстро развивающихся эволюционных вычислений. Мы ограничились здесь расмотрением только наиболее важных и принципиальных с нашей точки зрения моментов эволюционных вычислений, хотя по этому поводу могут быть и другие мнения.
В этом разделе описывается концепция простого генетического алгоритма (ГА), ориентированного на решение различных оптимизационных задач. Вводятся и содержательно описываются понятия, используемые в теории и приложениях ГА. Приводится фундаментальная теорема ГА и излагается теория схем, составляющие теоретическую базу ГА. Обсуждаются концептуальные вопросы, касающиеся преимуществ и недостатков ГА.
Основы теории генетических алгоритмов сформулированы Дж. Г.Холландом в основополагающей работе [2] и в дальнейшем были развиты рядом других исследователей. Наиболее известной и часто цитируемой в настоящее время является монография Д.Голдберга [3], где систематически изложены основные результаты и области практического применения ГА.
ГА используют принципы и терминологию, заимствованные у биологической науки – генетики. В ГА каждая особь представляет потенциальное решение некоторой проблемы. В классическом ГА особь кодируется строкой двоичных символов – хромосомой, каждый бит которой называется геном. Множество особей – потенциальных решений составляет популяцию. Поиск оптимального или субоптимального решения проблемы выполняется в процессе эволюции популяции, т.е. последовательного преобразования одного конечного множества решений в другое с помощью генетических операторов репродукции, кроссинговера и мутации. ЭВ используют механизмы естественной эволюции, основанные на следующих принципах:
Эти три принципа составляют ядро ЭВ. Используя их, популяция (множество решений данной проблемы) эволюционирует от поколения к поколению.
Эволюцию искусственной популяции – поиск множества решений некоторой проблемы, формально можно описать в виде алгоритма, который представлен на рис.1.1.
ГА получает множество параметров оптимизационной проблемы и кодирует их последовательностями конечной длины в некотором конечном алфавите (в простейшем случае в двоичном алфавите "0" и "1").
Предварительно
Генетические алгоритмы – это не просто случайный поиск, они эффективно используют информацию, накопленную в процессе эволюции.
В процессе поиска решения необходимо соблюдать баланс между "эксплуатацией" полученных на текущий момент лучших решений и расширением пространства поиска. Различные методы поиска решают эту проблему по-разному.
Например, градиентные методы практически основаны только на использовании лучших текущих решений, что повышает скорость сходимости с одной стороны, но порождает проблему локальных экстремумов с другой. В полярном подходе случайные методы поиска используют все пространство поиска, но имеют низкую скорость сходимости. В ГА предпринята попытка объединить преимущества этих двух противоположных подходов. При этом операторы репродукции и кроссинговера делают поиск направленным. Широту поиска обеспечивает то, что процесс ведется на множестве решений – популяции и используется оператор мутации.
(рис 1.1) Простой генетический алгоритм
В отличие от других методов оптимизации ГА оптимизируют различные области пространства решений одновременно и более приспособлены к нахождению новых областей с лучшими значениями целевой функции за счет объединения квазиоптимальных решений из разных популяций.
Упомянутые
Рассматриваемый ниже пример заимствован из популярной монографии Голдберга [3] и состоит в поиске целочисленного значения (для простоты) $$x$$ на отрезке от [0,31], при котором функции $$y=x^2$$ принимает максимальное значение.
(рис 1.2) Пример функции
Начальный этап работы ГА для данного примера приведен в верхней таблице (репродукция) рис.1.3 Здесь особи начальной популяции (двоичные коды значений переменных $$x$$- столбец 2) сгенерированы случайным образом. Двоичный код значения х называется хромосомой (она представляет генотип). Популяция образует множество потенциальных решений данной проблемы. В третьем столбце представлены их десятичные значения (фенотип). Далее на этом примере проиллюстрируем работу трех основных
Репродукция – это процесс, в котором хромосомы копируются в промежуточную популяцию для дальнейшего "размножения" согласно их значениям целевой (фитнесс-) функции. При этом хромосомы с лучшими значениями целевой функции имеют большую вероятность попадания одного или более потомков в следующее поколение.
Очевидно, оператор репродукции (ОР) является искусственной версией естественной селекции – выживания сильнейших по Ч. Дарвину. Этот оператор представляется в алгоритмической форме различными способами (подробнее различные варианты ОР будут рассмотрены далее). Самый простой (и популярный) метод реализации ОР – построение колеса рулетки, в которой каждая хромосома имеет сектор, пропорциональный по площади значению ее целевой функции. Для нашего примера "колесо рулетки" имеет вид, представленный на рис.1.4.
Для селекции хромосом используется случайный поиск на основе колеса рулетки. При этом колесо рулетки вращается и после останова ее указатель определяет хромосому для селекции в промежуточную популяцию (родительский пул).
(рис 1.3) Эволюция популяции
Очевидно, что хромосома, которой соответствует больший сектор рулетки, имеет большую вероятность попасть в следующее поколение. В результате выполнения оператора репродукции формируется промежуточная популяция, хромосомы которой будут использованы для построения поколения с помощью операторов скрещивания.
В нашем примере выбираем хромосомы для промежуточной популяции, вращая колесо рулетки 4 раза, что соответствует мощности начальной популяции. Величину $$\frac{f(x_i)}{\sum f(x_j)}$$ обозначим как $$P(x_i)$$, тогда ожидаемое количество копий i-ой хромосомы определяется значением $$M=P(x_i)*N$$, где N-мощность популяции. Число копий хромосомы, переходящих в следующее поколение, иногда определяется и так: $$\tilde M=\frac{f(x_i)}{\bar f(x)}$$, где $$\bar f(x)$$- среднее значение хромосомы в популяции.
(рис 1.4) Колесо рулетки
Расчетные числа копий хромосом по приведенной формуле следующие: хромосома 1 - 0,56; хромосома 2 - 1,97; хромосома 3 – 0,22; хромосома 4 – 1,23. В результате, в промежуточную популяцию 1-я хромосома попадает в одном экземпляре, 2-я – в двух, 3-я – совсем не попадает, 4-я – в одном экземпляре. Полученная промежуточная популяция является исходной для дальнейшего выполнения операторов кроссинговера и мутации.
Одноточечный или простой оператор кросинговера (ОК) с заданной вероятностью $$P_c$$ выполняется в три этапа:
1-й этап. Две хромосомы (родители) выбираются случайно (или одним из методов, рассмотренных далее) из промежуточной популяции, сформированной при помощи оператора репродукции (ОР).
2-й этап. Случайно выбирается точка скрещивания - число $$k$$ из диапазона $$[1,n-1]$$, где $$n$$– длина хромосомы (число бит в двоичном коде).
Две новых хромосомы A', B' (потомки) формируются из A и B путем обмена подстрок после точки скрещивания:
$$A'=a_1 a_2\dots a_k\ b_{k+1}\dots b_L\\B'=b_1 b_2\dots b_k\ a_{k+1}\dots a_L$$Например, рассмотрим выполнение кроссинговера для хромосом 1 и 2 из промежуточной популяции:
$$A=0\ 1\ 1\ 0\ 1\\B=1\ 1\ 0\ 0\ 0\\1\le k\le 4, k=4\\A'=0\ 1\ 1\ 0\ 0\\B'=1\ 1\ 0\ 0\ 1\\$$Следует отметить, что ОК выполняется с заданной вероятностью $$P_c$$ (отобранные два родителя не обязательно производят потомков). Обычно величина вероятности полагается равной $$P_c\approx 0,5$$.
Таким образом, операторы репродукции и скрещивания очень просты – они выполняют копирование особей и частичный обмен частей хромосом. Продолжение нашего примера представлено на рис.1.3 во второй таблице (кроссинговер).
Сравнение с предыдущей таблицей показывает, что в промежуточной популяции после скрещивания улучшились все показатели популяции (среднее и максимальное значения целевой функции - ЦФ).
Далее согласно
Оператор мутации (ОМ) выполняется в два этапа:
1-й этап. В хромосоме $$A=a_1 a_2\dots a_L$$ случайным образом выбирается $$k$$-ая позиция (бит) $$(1\le k\le n)$$.
2-й этап. Производится инверсия значения гена в $$k$$-й позиции: $$a'_k=\bar a_k$$
Например, для хромосомы 11011 выбирается $$k=3$$ и после инверсии значения третьего бита получается новая хромосома – 11111. Продолжение нашего примера представлено в третьей таблице (мутация) рис.1.3 образом, в результате применения
В данном случае, поскольку пример искусственно подобран, мы нашли оптимальное решение за одну итерацию. В общем случае ГА работает до тех пор, пока не будет выполнен критерий окончания процесса поиска и в последнем полученном поколении определяется лучшая особь, которая и принимается в качестве решения задачи.
В предыдущем примере мы рассматривали только целочисленные решения. Обобщим ГА на случай вещественных чисел на примере функции $$f(x)=(1,85-x)*\cos(3,5x-0,5)$$, представленной на рис.1.5 [14]. Рассматривается та же задача: необходимо найти вещественное $$x\in [-10,+10]$$, которое максимизирует $$f(x)$$, т.е. такое $$x_0$$, для которого $$f(x_0)\ge f(x)$$ для всех $$x\in [-10,+10]$$.
(рис 1.5) Пример функции с популяцией особей в начале эволюции
Для решения этой задачи с помощью ГА будем использовать представления вещественного решения (хромосомы) в виде двоичного вектора [15], который применяется в классическом простом ГА. Его длина зависит от требуемой точности решения, которую в данном случае положим, например, равной 3 знакам после запятой.
Поскольку отрезок области решения имеет длину 20, для достижения заданной точности отрезок $$[a,c]=[-10,+10]$$ должен быть разбит на равные части (маленькие отрезки), число которых должно быть не менее 20*1000. В качестве двоичного представления используем двоичный код номера (маленького) отрезка. Этот код позволяет определить соответствующее ему вещественное число, если известны границы области решения. Отсюда следует, что двоичный вектор для кодирования вещественного решения должен иметь 15 бит, поскольку $$16384=2^{14}<20000\le2^{15}=32768$$
Отсюда следует, что для обеспечения необходимой точности требуется разбить отрезок [-10,+10] на 32768 частей. Отображение из двоичного представления $$(b_{14} b_{13}\dots b_0)\ (b_i\in \{0,1\}$$ в вещественное число из отрезка $$[a,c]=[-10,+10]$$ выполняется в два шага.
Очевидно, при данном двоичном представлении вещественных чисел можно использовать классический
(рис 1.6) Начальная "конденсация" особей популяции в окрестностях экстремумов
(рис 1.7) "Конденсация" особей в окрестностях экстремумов
(рис 1.8) Положение особей популяции в конце эволюции
Для сокращения длины хромосом иногда применяют логарифмическое кодирование, при котором первый бит $$(a)$$ кодовой последовательности используется для знака показательной функции, второй бит $$(b)$$ – для знака степени этой функции, и остальные биты $$(str)$$ представляют значение самой степени [16]. Таким образом, двоичный код $$<a\ b\ str>$$ представляет вещественное число $$(-1)^a e^{(-1)^b [str]_{10}}$$. Здесь $$[str]_{10}$$ означает десятичное число, представленное двоичным кодом $$str$$.
Например, двоичный код $$<10101>$$ представляет вещественное число $$(-1)^0 e^{(-1)^1 [101]_{10}} =e^{-6}=0,002478752$$. Следует отметить, что при таком кодировании пять битов позволяет кодировать вещественные числа из интервала $$[-e^7,e^7]$$, что значительно больше, чем это позволяет, например, метод кодирования, представленный ранее.
Рассмотренное двоичное представление вещественного числа имеет существенный недостаток: расстояние между вещественными числами (на числовой оси) часто не соответствует расстоянию (по Хеммингу) между их двоичными представлениями. Поэтому желательно получить двоичное представление, где близкие расстояния между хромосомами (двоичными представлениями) соответствовали близким расстояниям в проблемной области (в данном случае расстоянию на числовой оси) [3,14,15]. Это можно сделать, например, с помощью кода Грея. В таблице 1.1 приведен для примера код Грея для 4-х битовых слов.
| Двоичный код | Код Грея |
|---|---|
| 0000 | 0000 |
| 0001 | 0001 |
| 0010 | 0011 |
| 0011 | 0010 |
| 0100 | 0110 |
| 0101 | 0111 |
| 0110 | 0101 |
| 0111 | 0100 |
| 1000 | 1100 |
| 1001 | 1101 |
| 1010 | 1111 |
| 1011 | 1110 |
| 1100 | 1010 |
| 1101 | 1011 |
| 1110 | 1001 |
| 1111 | 1000 |
Заметим, что в коде Грея соседние двоичные слова отличаются на один бит (расстояние по Хеммингу равно 1).
Рассмотрим алгоритмы преобразования двоичного числа $$\bar b=<b_1,\dots,b_m>$$ в код Грея $$\bar g=<g_1,\dots,g_m>$$ и наоборот.
(рис 1.9) Преобразование в код Грея
Здесь параметр m определяет разрядность двоичного числа. Существует и другая, матричная, процедура преобразования в код Грея. Например, для $$m=4$$ матрицы
$$A=\left[\begin{matrix}1000\\1100\\0110\\0011\end{matrix}\right] \mbox{и}\quad A^{-1}=\left[\begin{matrix}1000\\1100\\1110\\1111\end{matrix}\right]$$позволяют выполнять следующие преобразования:
$$\bar g=A\cdot\bar b\ \mbox{и}\ \bar b=A^{-1}\bar g$$где умножение матриц выполняются в арифметике по mod 2.
Отметим, что применение кода Грея прежде всего оправдано при использовании операторов мутации.
Определение соответствующей
В ГА используются четыре основных метода для учета накладываемых ограничений при решении оптимизационных задач. Вероятно, простейшим способом является метод отклонения (отбрасывания), где недопустимые хромосомы (не удовлетворяющие ограничениям) исключаются из дальнейшей эволюции. Второй метод основан на использовании процедуры восстановления, которая преобразует полученное недопустимое решение в допустимое. Другой альтернативой является применение проблемно-ориентированных
Рассмотренные методы не строят недопустимых решений. Но это не всегда дает хорошие результаты. Например, в том случае, когда оптимальные решения лежат на границе допустимой области, указанные методы могут давать неоптимальные решения. Одним из возможных вариантов преодоления этой проблемы является выполнение процедуры восстановления только для некоторого подмножества решений (например, 10% особей).
Для решения оптимизационных задач со сложными ограничениями иногда позволяют вести поиск решения и в недопустимых областях. Реализуется это подход часто с помощью метода штрафных функций, что позволяет расширить пространство поиска решений. Следует отметить, что часто недопустимая точка, близкая к оптимальному решению, содержит больше полезной информации, чем допустимая точка, далекая от оптимума. С другой стороны, построение штрафных функций является достаточно сложной проблемой, которая сильно зависит от решаемой задачи. Обычно нет априорной информации о расстоянии до оптимальных точек, есть только расстояние до границы области допустимых решений. Поэтому, как правило, штрафные функции используют расстояние до границ допустимой области. Штрафы, основанные на нарушении отдельных ограничений, работают обычно не очень хорошо.
Разработаны два основных способа построения штрафных функций со штрафным термом: аддитивная и мультипликативная формы. В первой форме функция представляется в виде $$g(x)=f(x)+p(x)$$, где при максимизации для допустимых точек $$p(x)=0$$ и в противном случае $$p(x)<0$$. Максимум значения $$p(x)$$ по абсолютной величине не может быть больше, чем минимальное значение $$f(x)$$ по абсолютной величине для любой генерации, чтобы избежать отрицательных фитнесс-значений. Мультипликативная форма представляет функцию в виде $$g(x)=f(x)\cdot p(x)$$, где при максимизации $$p(x)=1$$ для допустимых точек и $$0\le p(x)<1$$ в противном случае.
При этом штрафной терм должен изменяться не только в зависимости от степени нарушения ограничения, но и от номера поколения ГА. Наряду с нарушением ограничения, штрафной терм обычно содержит штрафные коэффициенты (по одному для каждого ограничения). На практике большую роль играют значения этих коэффициентов. Маленькие значения коэффициентов могут привести к недопустимым значениям решения, в то время как большие значения полностью отвергают недопустимые подпространства. В среднем абсолютные значения целевой и штрафной функции должны быть соизмеримы. При таком подходе параметры штрафной функции можно включить в параметры ГА, что позволяет разработать адаптивный метод, где значения коэффициентов регулируются в процессе поиска решения.
В целом на выбор (построение)
В ГА
Для некоторых задач оценку значений
(рис 1.10) Схема взаимодействия объектной модели с ГА.
Теоретические основы ГА составляют двоичное стринговое представление решений (хромосом) и понятие
В простом ГА основная идея заключается в объединении хромосом со значениями целевой функции (ЦФ) выше среднего. Например, пусть 1 в хромосоме соответствует наличию признака, способствующего выживанию (значение целевой функции больше среднего). Допустим, что имеются подстринги вида 11*** и **111. Тогда, применяя к ним ОК можно получить хромосому 11111 с признаками, способствующими наилучшим значениям
Не все
Обозначим через $$m(H,t)$$– число стрингов, содержащихся в популяции $$A(t)$$($$t$$ – шаг итерации или время), которые отображаются (покрываются)
Пусть $$f(H)$$ означает среднее значение
Напомним, что в процессе репродукции хромосомы копируются в промежуточную популяцию согласно их значениям
После репродукции мы ожидаем на следующем шаге получить m(H,t+1) двоичных стрингов, отображаемых
Это обусловлено тем, что:
Мы можем переписать эту формулу с учетом обозначения $$\overline{f(x)}=\frac{\sum_{j=1}^N f(x_j)}{N}$$ и получим следующее выражение для числа особей, покрываемых
Другими словами,
Предположим, что схема $$H$$ имеет значение выше среднего
Начиная с $$t=0$$ и предполагая, что $$c$$– величина постоянная, получаем следующее выражение числа особей промежуточной популяции, покрываемых
Это равенство описывает геометрическую прогрессию. Очевидно, что при $$c>0$$
Далее рассмотрим влияние оператора кроссинговера на число особей в популяции, покрываемых
Рассмотрим конкретный стринг $$А=011|1000$$ длины $$n=7$$ и две
Здесь символ "|" , как обычно, обозначает точку кроссинговера $$k=3$$.
Очевидно, что
Очевидно, что эта же
Аналогично,
Если ОК выполняется посредством случайного выбора, например, с вероятностью $$P_c$$, то вероятность выживания
Очевидно, что это выражение уменьшается при $$P_c\to 1$$. Теперь мы можем асимптотически оценить совместный эффект операторов репродукции и кроссинговера. При независимости выполнения OP и OK можно получить следующее выражение:
$$m(H,t+1)\ge m(H,t)\frac{f(H)}{\bar f}[1-P_c\frac{L(H)}{n-1}]$$Таким образом, число
Видно, что
Далее рассмотрим влияние оператора мутации на число особей в популяции, покрываемых
Напомним, что оператор мутации (ОМ) есть случайное изменение элемента в стринге с вероятностью $$P_m$$. Очевидно, что для того чтобы
Из этого следует, что
Этот важный результат известен как
Теорема 1.1.
На основании приведенных результатов была выдвинута гипотеза о строительных блоках.
Гипотеза 1.1. Генетический алгоритм стремится достичь близкого к оптимальному результата за счет комбинирования хороших
Такие
Несмотря на то, что для доказательства этой гипотезы были предприняты значительные усилия, строгого доказательства получено не было, и в большинстве нетривиальных приложений опираются на эмпирические результаты.
Далее проиллюстрируем приведенные результаты. Вернемся к примеру Голдберга определения $$\mbox{max}\ f(x)=x^2$$. В дополнение к имеющимся таблицам рис 1.3 пусть имеется 3 конкретные
Рассмотрим сначала
| Схема | Перед репродукцией | Представители стрингов | Среднее значение ЦФ схемы $$f(H)$$ |
|---|---|---|---|
| $$H_1$$ | 1**** | 2,4 | 469 |
| $$H_2$$ | *10** | 2,3 | 320 |
| $$H_3$$ | 1***0 | 2 | 576 |
Проверим, соответствует ли это число фундаментальной теореме
| Схема | После репродукции | После всех операторов | ||||
|---|---|---|---|---|---|---|
| Ожидаемое число стрингов | Действительное число стрингов | Представители стрингов | Ожидаемое число стрингов | Действительное число стрингов | Представители стрингов | |
| $$H_1$$ | 3,20 | 3 | 2, 3, 4 | 3,20 | 3 | 2, 3, 4 |
| $$H_2$$ | 2,18 | 2 | 2, 3 | 1,64 | 2 | 2, 3 |
| $$H_3$$ | 1,97 | 2 | 2, 3 | 0,0 | 1 | 4 |
Сравнивая это число с реальным числом копий 3, видим, что округление рассчитанного значения копий 3,2 дает их реальное число 3. Дальнейший анализ показывает, что в данном случае ОК не оказывает влияние на число стрингов, покрываемых
Рассмотрим теперь
Заметим, что для конкретной
Для
В соответствие с полученными результатами видно, что важнейшим аспектом является кодирование особей, которое должно обеспечить построение
Следующий простой пример показывает важность построения генома с учетом теорем
Рассмотрим поиск максимума (для простоты при целочисленных значениях $$x$$ и $$y$$) функции $$f(x,y)=x^2-y+17$$. Можно показать, что максимум $$f=66$$ достигается при значениях $$x=(111)_2=(7)_{10}$$ и $$y=(0000)_2=(0)_{10}$$. Пусть $$x=x_2x_1x_0$$ и $$y= y_3y_2y_1y_0$$, где $$x_i,y_j\in \{0,1\}$$. Рассмотрим различное строение геномов. В первом случае пусть генотип представляет $$y_3x_2y_2x_1y_1x_0y_0$$, во втором генотип определим как $$y_3y_2y_1y_0\ x_2x_1x_0$$. Отметим, что в первом случае старшие разряды $$x$$ и $$y$$ расположены в генотипе близко, а во втором варианте наоборот – достаточно далеко. Поскольку желательна короткая определенная длина, генетический алгоритм с геномом, в котором старшие разряды расположены близко, должен быть лучше по сравнению с геномом, где эти разряды стоят далеко друг от друга. Для первого случая $$\frac{L(H)}{1-n}=\frac{1}{6}$$ для
Эффективность ГА зависит от ряда параметров, к которым относятся: мощность популяции, структура представления решения, вид генетических операторов кроссинговера и мутации, вероятности кроссинговера и мутации $$P_c$$ и $$P_m$$ и т.п..
Мощность популяции $$N$$ является важнейшим параметром ГА, который критичен во многих приложениях. Чем больше $$N$$, тем больше разнообразие потенциальных решений (при хорошей
На разных этапах работы ГА оптимальное значение $$N$$ может быть различным. На начальном этапе $$N$$ должно быть большим, а на заключительном $$N$$ можно уменьшить. Большую роль играют также вид
Для оптимизации, особенно мультимодальных функций, наиболее существенными являются две характеристики ГА:
Баланс между этими характеристиками ГА в значительной степени определяется значениями вероятности $$P_c$$ и $$P_m$$, типом используемых
Основным преимуществом ГА является их концептуальная простота. Рассмотрим снова блок-схему ГА, представленную на рис.1.1 Основными шагами алгоритма являются: инициализация, оценка качества решения с помощью
ГА могут быть использованы при решении любой проблемы, которая может быть сформулирована как задача оптимизации. Они требуют разработки (или выбора) структуры данных для представления потенциального решения, показателя качества для оценки потенциального решения и
Реальные задачи оптимизации часто:
Целевые функции для реальных проблем часто мультимодальны и градиентные методы сходятся быстро к локальным экстремумам, которые могут давать неудовлетворительные решения. Для простых задач, где поверхность отклика, например, является строго выпуклой, генетические алгоритмы проигрывают классическим по эффективности. Эксперименты показали, что для мультимодальных функций ГА дают лучшие результаты. В случае нелинейных ограничений классические методы даже при выпуклой поверхности могут давать некорректные результаты. Напротив, эволюционные методы могут непосредственно учитывать произвольные линейные и нелинейные ограничения.
При решении конкретной проблемы всегда целесообразно учесть в алгоритме проблемно-ориентированные априорные знания [17]. Специализированные алгоритмы, учитывающие такую информацию (но имеющие ограниченную область применения), как правило, существенно превосходят по характеристикам неспециализированные методы. Эволюционные алгоритмы по своей структуре легче позволяют учитывать априорные знания. Это может быть выражено, например, в виде специальной структуры данных для представления решений или специальных проблемно-ориентированных
Генетические алгоритмы могут комбинироваться с другими более традиционными методами. Известны работы, где на первом этапе оптимизации используются генетические алгоритмы совместно с градиентным методом, который применяется на заключительном этапе, когда уже найдена "зона интереса". Эти алгоритмы могут применяться совместно и параллельно. Отметим, что начальная популяция потенциальных решений может быть получена путем применения, например, жадных алгоритмов, а не эволюционных методов. Генетические алгоритмы часто используются для оптимизации и обучения искусственных нейронных сетей или нечетких продукционных систем. В этом случае часто удается преодолеть ограничения, связанные с традиционными подходами.
Эволюция является высоко параллельным процессом, поскольку популяция состоит из множества особей, которые развиваются параллельно. Это позволяет расширить возможности применения эволюционных вычислений для решения все более сложных задач. Отметим, что основные вычислительные ресурсы в генетических алгоритмах используются при оценке значений
Традиционные методы оптимизации неустойчивы к динамическим изменениям окружающей среды и часто требуют полного рестарта при таких изменениях для получения адекватного решения. Напротив, эволюционные алгоритмы могут быть использованы для адаптации потенциальных решений к изменившимся условиям. Полученная на момент изменения популяция дает базис для дальнейшего улучшения решений и в большинстве случаев нет необходимости проводить случайную реинициализацию.
Большинство классических методов требуют начальной установки соответствующих параметров алгоритмов. Это также относится и к генетическим алгоритмам, которые зависят от множества параметров, таких как мощность популяции, вероятности кроссинговера и мутации, шаг мутации и т.п. Однако в эволюционных алгоритмах легче ввести самоадаптацию, когда в процессе поиска решения указанные параметры оптимизируются.
Возможно, самым большим преимуществом генетических алгоритмов является их способность исследовать проблемы, для которых нет экспертов и соответствующего опыта решений. Следует отметить, что экспертные оценки достаточно часто используются при решении трудно формализуемых задач, но они иногда дают менее адекватные решения, чем автоматизированные методы. Существуют определенные проблемы с получением знаний у экспертов: они могут не согласиться на это, могут быть неквалифицированными, могут быть несовместимыми и просто ошибаться.
Исследования по искусственному интеллекту в настоящее время дали ряд интересных результатов, каждый из которых позволяет эффективно решать свой класс задач (например, хорошо играть в шахматы, или распознавать изображения символов и т.п.). Но большинство этих узких приложений требуют участия человека. Эти методы могут эффективно решать некоторые сложные проблемы, требующие высокого быстродействия, но они не могут конкурировать с человеческим интеллектом - "Они решают проблемы, но они не решают проблему как решать проблемы". Напротив, эволюционные алгоритмы дают метод решения проблемы, как решать проблемы при отсутствии экспертов (человеческого опыта) [17].
Естественно ГА не свободны от недостатков. К ним можно отнести прежде всего следующие. Конфигурация ГА для решения сложных реальных задач не очевидна. Для решения конкретной задачи необходимо выбрать или разработать представление (кодирование) потенциального решения. Существует также проблема определения
Возникает естественный вопрос – существует ли некоторый лучший эволюционный алгоритм, который дает всегда лучшие результаты при решении всевозможных проблем? Например, можно ли выбрать
NFL теорема. Для любой пары алгоритмов $$a_1$$ и $$a_2$$ имеет место равенство $$\sum_f P(d_m^y|f,m,a_1)=\sum_f P(d_m^y|f,m,a_2).$$
Таким образом, сумма условных вероятностей посещения в пространстве решений каждой точки $$d_m$$ одинакова для множества всевозможных целевых функций независимо от используемого алгоритма. Из этого результата непосредственно следует, что при любой мере $$\Phi(d_m^y)$$ производительности (характеристик сложности) алгоритма в среднем для всевозможных целевых функций $$f$$ вероятность $$P(\Phi(d_m^y)|f,m,a)$$ не зависит от алгоритма $$a$$. Другими словами, не существует лучшего алгоритма (эволюционного или любого другого) для решения всех проблем. Если алгоритм выигрывает по своим характеристикам при решении некоторого класса задач, то это неминуемо компенсируется проигрышем (худшими характеристиками) для остальных задач.
Эта теорема вызвала оживленную дискуссию у специалистов по эволюционным вычислениям и некоторое неприятие. Дело в том, что в семидесятых годах были предприняты значительные усилия по поиску лучших значений параметров и
Каждому эволюционному алгоритму присуще некоторое представление, которое позволяет манипулировать с потенциальными решениями. NFL теорема утверждает, что не существует лучшего эволюционного алгоритма для решения всех проблем.
Для того чтобы разрабатываемый алгоритм решал поставленную задачу лучше, чем случайный поиск (который с точки зрения NFL теоремы является просто другим алгоритмом) необходимо в нем использовать (отразить) структуру (априорные знания) этой проблемы. Из этого следует, что такой алгоритм может не соответствовать структуре другой проблемы (и покажет для нее плохие результаты). Следует отметить, что недостаточно просто указать, что проблема имеет некоторую структуру - такая структура должна соответствовать разрабатываемому алгоритму. Более того, структура должна быть определена. Недостаточно, как это иногда бывает, сказать "Мы имеем дело с реальными проблемами, а не с всевозможными, поэтому NFL теорема не применима". Что значит структура реальной проблемы? Очевидно, что формальное описание такой структуры проблематично. Например, реальные проблемы нашего времени и столетней давности могут сильно отличаться. Следует отметить, что простое сужение области возможных проблем без идентификации соответствия между рассматриваемым множеством проблем и алгоритмом недостаточно для получения преимущества данного метода решения этих проблем по сравнению с другими.
NFL-теорема подтверждает, что разные алгоритмы имеют различную эффективность при решении разных задач. Например, классические методы оптимизации, как правило, более эффективны при решении линейных, квадратичных, строго выпуклых, унимодальных, разделяемых и других специальных классов проблем. С другой стороны, генетические алгоритмы часто успешно решают задачи там, где классические методы не работают – там, где целевые функции терпят разрывы, не дифференцируемы, мультимодальны (имеют много экстремумов), зашумлены и т.п. Обычно их эффективность и устойчивость выше там, где целевые функции имеют сложный (не стандартный) вид, что более характерно для решения реальных практических задач. Конечно, лучшим способом подтверждения эффективности алгоритма является доказательство его сходимости и оценки вычислительной сложности. Но, как правило, это возможно только в случае упрощенной постановки задачи. Другой альтернативой является проверка алгоритмов на тестовых задачах (benchmarks) данной проблемной области. К сожалению, в настоящее время не существует согласованного каталога таких задач для оценки старых или новых алгоритмов решения, хотя для многих типовых задач они уже сложились и широко используются.
Выполните программную реализацию простого ГА на одном из языков программирования для поиска экстремума заданной по варианту функции одной переменной (табл. 1.5).
Вид экстремума:
| Вариант | Вид экстремума |
|---|---|
| $$\le 15$$ | Максимум |
| $$> 15$$ | Минимум |
| Вариант | Вид функции | Промежуток поиска решения |
|---|---|---|
| 1 | $$(1,85-x)*\cos(3,5x-0,5)$$ | $$x\in [-10,10]$$ |
| 2 | $$\cos(\exp(x))/\sin(\ln(x))$$ | $$x\in [2,4]$$ |
| 3 | $$\sin(x)/x^2$$ | $$x\in [3.1,20]$$ |
| 4 | $$\sin(2x)/x^2$$ | $$x\in [-20,-3.1]$$ |
| 5 | $$\cos(2x)/x^2$$ | $$x\in [-20,-2.3]$$ |
| 6 | $$(x-1)\cos(3x-15)$$ | $$x\in [-10,10]$$ |
| 7 | $$\ln(x)\cos(3x-15)$$ | $$x\in [1,10]$$ |
| 8 | $$\cos(3x-15)/|x|=0$$ | $$x\in [-10,-0.3),(0.3,10]\\x\in[-0.3,0.3]$$ |
| 9 | $$\cos(3x-15)*x$$ | $$x\in [-9.6,9.1]$$ |
| 10 | $$\sin(x)/(1+\exp(-x))$$ | $$x\in [0.5,10]$$ |
| 11 | $$\cos(x)/ (1+\exp(-x)$$ | $$x\in [0.5,10]$$ |
| 12 | $$(\exp(x)-\exp(-x))\cos(x)/(\exp(x)+\exp(-x))$$ | $$x\in [-5,5]$$ |
| 13 | $$(\exp(-x)-\exp(x))\cos(x)/(\exp(x)+\exp(-x))$$ | $$x\in [-5,5]$$ |
| 14 | $$\cos(x-0,5)/|x|$$ | $$x\in [-10,0),(0,10],\min$$ |
| 15 | $$\cos(2x)/|x-2|$$ | $$x\in [-10,2),(2,10],\max$$ |
Среди множества проблем, которые возникают перед исследователями как в области теории, так и в многочисленных практических приложениях значительную долю составляют так называемые оптимизационные проблемы. Понятие оптимальности, по-видимому, знакомо почти каждому и вошло в практику большинства предметных областей. С оптимизационной проблемой мы сталкиваемся каждый раз, когда возникает необходимость выбора из некоторого множества возможных решений наилучшего по определенным критериями и, как правило, удовлетворяющего заданным условиям и ограничениям. Само понятие оптимальности получает совершенно строгое толкование в математических теориях, однако в других областях оно может интерпретироваться скорее содержательно. Тем не менее различие между строгим и содержательным понятиями оптимальности, как правило, очень незначительно.
Существуют классы оптимизационных задач, решение которых удается находить с помощью достаточно эффективных методов, вполне приемлемых по трудоемкости. Вместе с тем имеются и такие классы оптимизационных задач (так называемые NP- полные задачи), решение которых невозможно найти без полного перебора вариантов. В частности, к числу последних относятся многие разновидности задач многокритериальной оптимизации. Известно, что при большой размерности этих задач реализация перебора вариантов практически невозможна из-за чрезвычайно больших временных затрат.
В этой ситуации альтернативным походом к решению упомянутых задач является применение методов, базирующихся на методологии эволюционных вычислений. Предлагаемое пособие содержит изложение основ эволюционных вычислений и их приложений к решению различных проблем, включая проблемы экономики, прогнозирования финансовых рынков, инвестиций, бизнеса, комбинаторной оптимизации, сложных задач в различных технических разработках и т.п. Эффективность различных методов в рамках эволюционного подхода подтверждается многочисленными данными, касающимися достигаемым реальным эффектом. При этом хотя объем вычислений может оказаться большим, но скорость, с которой он растет при увеличении размерности задачи, обычно меньше, чем у остальных известных методов. Отметим, что после того как компьютерные системы стали достаточно быстродействующими и недорогими, эволюционные методы превратились в важный инструмент поиска близких к оптимальным решений задач, которые до этого считались неразрешимыми.
Основной целью учебного пособия является систематическое изложение перспективного направления в области теории и практики искусственного интеллекта. Пособие рассчитано на студентов и аспирантов вузов, обучающихся по направлениям, связанным с прикладной информатикой и математикой, компьютерными и программными системами, с интеллектуальными системами обработки информации.
Освоение представленного в пособии материала предполагает знакомство читателя с математикой и информатикой в объеме первых двух курсов технического вуза, основами дискретной математики и методов оптимизации.
В настоящее время оформилось и успешно развивается новое направление в теории и практике искусственного интеллекта – эволюционные вычисления (ЭВ). Этот термин обычно используется для общего описания алгоритмов поиска, оптимизации или обучения, основанных на некоторых формализованных принципах естественного эволюционного отбора. Особенности идей эволюции и самоорганизации заключаются в том, что они являются плодотворными и полезность их применения не только для биологических систем перманентно подтверждается. Эти идеи в настоящее время с успехом используются при разработке многих технических и, в особенности, программных систем.
Высокая согласованность и эффективность работы элементов биологических систем приводила целый ряд исследователей к естественной мысли о возможности использования принципов биологической эволюции для оптимизации важных для приложений систем, природа которых отлична от биологической. Так, в 1966 году Фогель Л., Оуенс С. и Уолш М. в [1] подобную идею использовали для построения схемы эволюции логических автоматов, решающих задачи прогноза. В 1975 году была опубликована основополагающая работа Дж. Холланда [2], в которой был предложен генетический алгоритм, развивающий ту же идею. Д.Гольдберг, ученик Дж. Холланда, в работе [3] , выполненной в Мичиганском университете, успешно развил и расширил области его применения.
В 60-х годах прошлого века в Германии Рохенберг И., Швефель Г.-П., и др. [4] начали разработку так назывемой эволюционной стратегии. Перечисленные работы послужили толчком и основой развития прикладного направления, которое можно назвать эволюционными алгоритмами. К их числу, помимо упомянутых генетических алгоритмов и эволюционных стратегий, относятся также эволюционное программирование, ориентированное на оптимизацию функций без использования рекомбинаций, и генетическое программирование, использующее эволюционные идеи для оптимизации компьютерных программ. Основополагающая работа по эволюционному программированию принадлежит Дж. Коза [5] из Массачусетского технологического института.
Отметим, что аналогичные исследования успешно проводились отечественными учеными еще в Советском Союзе. Так, значительный вклад в развитие указанных направлений внесли Ивахненко А.Г. [6], Цыпкин Я.З. [7], Расстригин Л.А. [8] и др. В настоящее время исследования по ЭВ активно ведутся Букатовой [9,10], Курейчиком В.М. [11,12,13], их сотрудниками и учениками, а также многими другими исследователями.
Учебное пособие состоит из пяти частей.
В первой части "Основы генетических алгоритмов" (разделы пособия 1-5) изложены идейная сторона простых генетических алгоритмов, их математические основы, подробно описаны примеры построения генетических алгоритмов для решения конкретных задач комбинаторной оптимзации и, наконец, представлены современные модификации и обобщения этих алгоритмов.
Во второй части "Генетическое программирование и машинное обучение" (разделы 6-7) описана концепция компьютерного синтеза программ (с различными структурами их представления – линейными, древовидными, графоподобными) с использованием генетических алгоритмов. Изложены два основных подхода при машинном обучении - Мичиганский и Питтсбургский.
В третьей части "Вероятностные генетические алгоритмы"(раздел 8) приведен другой – вероятностный подход в эволюционных вычислениях, где популяция представляется вектором вероятностей.
В четвертой части "Эволюционные стратегии" (раздел 9) представлена оригинальная парадигма, основанная на эволюции популяции потенциальных решений. Ее принципиалное отличие состоит в том, что генетические операторы используются здесь на уровне фенотипа, а не генотипа, как это было в генетических алгоритмах.
В пятой части "Эволюционное программирование" (раздел 10) содержится описание основанного Фогелем Л.Дж. гибкого подхода в эволюционных вычислениях. В нем форма представления потенциального решения и генетические операторы адаптируются к решаемой проблемы в достаточно широких пределах. В частности, в качестве особи в процессе эволюции Фогелем используются конечные автоматы и целью эволюции является способность решения задач прогнозирования.
В шестой части "Роевой интеллект" (разделы 11-12) описаны принципы и методы оптимизации, базирующиеся на коллективном поведении децентрализованных самоорганизующихся систем. Такие системы представляются, например, в виде графа, содержащего множество вершин (агентов), локально взаимодействующих между собой и с окружающей средой. Имеющиеся экспериментальные данные подверждают эффективность роевого интеллекта (муравьиных, пчелиных, роевых и т.п. алгоритмов) для решения многих оптимизационных задач.
Заканчивая введение заметим, что в пособии представлены не все аспекты быстро развивающихся эволюционных вычислений. Мы ограничились здесь расмотрением только наиболее важных и принципиальных с нашей точки зрения моментов эволюционных вычислений, хотя по этому поводу могут быть и другие мнения.
В этом разделе описывается концепция простого генетического алгоритма (ГА), ориентированного на решение различных оптимизационных задач. Вводятся и содержательно описываются понятия, используемые в теории и приложениях ГА. Приводится фундаментальная теорема ГА и излагается теория схем, составляющие теоретическую базу ГА. Обсуждаются концептуальные вопросы, касающиеся преимуществ и недостатков ГА.
Основы теории генетических алгоритмов сформулированы Дж. Г.Холландом в основополагающей работе [2] и в дальнейшем были развиты рядом других исследователей. Наиболее известной и часто цитируемой в настоящее время является монография Д.Голдберга [3], где систематически изложены основные результаты и области практического применения ГА.
ГА используют принципы и терминологию, заимствованные у биологической науки – генетики. В ГА каждая особь представляет потенциальное решение некоторой проблемы. В классическом ГА особь кодируется строкой двоичных символов – хромосомой, каждый бит которой называется геном. Множество особей – потенциальных решений составляет популяцию. Поиск оптимального или субоптимального решения проблемы выполняется в процессе эволюции популяции, т.е. последовательного преобразования одного конечного множества решений в другое с помощью генетических операторов репродукции, кроссинговера и мутации. ЭВ используют механизмы естественной эволюции, основанные на следующих принципах:
Эти три принципа составляют ядро ЭВ. Используя их, популяция (множество решений данной проблемы) эволюционирует от поколения к поколению.
Эволюцию искусственной популяции – поиск множества решений некоторой проблемы, формально можно описать в виде алгоритма, который представлен на рис.1.1.
ГА получает множество параметров оптимизационной проблемы и кодирует их последовательностями конечной длины в некотором конечном алфавите (в простейшем случае в двоичном алфавите "0" и "1").
Предварительно
Генетические алгоритмы – это не просто случайный поиск, они эффективно используют информацию, накопленную в процессе эволюции.
В процессе поиска решения необходимо соблюдать баланс между "эксплуатацией" полученных на текущий момент лучших решений и расширением пространства поиска. Различные методы поиска решают эту проблему по-разному.
Например, градиентные методы практически основаны только на использовании лучших текущих решений, что повышает скорость сходимости с одной стороны, но порождает проблему локальных экстремумов с другой. В полярном подходе случайные методы поиска используют все пространство поиска, но имеют низкую скорость сходимости. В ГА предпринята попытка объединить преимущества этих двух противоположных подходов. При этом операторы репродукции и кроссинговера делают поиск направленным. Широту поиска обеспечивает то, что процесс ведется на множестве решений – популяции и используется оператор мутации.
(рис 1.1) Простой генетический алгоритм
В отличие от других методов оптимизации ГА оптимизируют различные области пространства решений одновременно и более приспособлены к нахождению новых областей с лучшими значениями целевой функции за счет объединения квазиоптимальных решений из разных популяций.
Упомянутые
Рассматриваемый ниже пример заимствован из популярной монографии Голдберга [3] и состоит в поиске целочисленного значения (для простоты) $$x$$ на отрезке от [0,31], при котором функции $$y=x^2$$ принимает максимальное значение.
(рис 1.2) Пример функции
Начальный этап работы ГА для данного примера приведен в верхней таблице (репродукция) рис.1.3 Здесь особи начальной популяции (двоичные коды значений переменных $$x$$- столбец 2) сгенерированы случайным образом. Двоичный код значения х называется хромосомой (она представляет генотип). Популяция образует множество потенциальных решений данной проблемы. В третьем столбце представлены их десятичные значения (фенотип). Далее на этом примере проиллюстрируем работу трех основных
Репродукция – это процесс, в котором хромосомы копируются в промежуточную популяцию для дальнейшего "размножения" согласно их значениям целевой (фитнесс-) функции. При этом хромосомы с лучшими значениями целевой функции имеют большую вероятность попадания одного или более потомков в следующее поколение.
Очевидно, оператор репродукции (ОР) является искусственной версией естественной селекции – выживания сильнейших по Ч. Дарвину. Этот оператор представляется в алгоритмической форме различными способами (подробнее различные варианты ОР будут рассмотрены далее). Самый простой (и популярный) метод реализации ОР – построение колеса рулетки, в которой каждая хромосома имеет сектор, пропорциональный по площади значению ее целевой функции. Для нашего примера "колесо рулетки" имеет вид, представленный на рис.1.4.
Для селекции хромосом используется случайный поиск на основе колеса рулетки. При этом колесо рулетки вращается и после останова ее указатель определяет хромосому для селекции в промежуточную популяцию (родительский пул).
(рис 1.3) Эволюция популяции
Очевидно, что хромосома, которой соответствует больший сектор рулетки, имеет большую вероятность попасть в следующее поколение. В результате выполнения оператора репродукции формируется промежуточная популяция, хромосомы которой будут использованы для построения поколения с помощью операторов скрещивания.
В нашем примере выбираем хромосомы для промежуточной популяции, вращая колесо рулетки 4 раза, что соответствует мощности начальной популяции. Величину $$\frac{f(x_i)}{\sum f(x_j)}$$ обозначим как $$P(x_i)$$, тогда ожидаемое количество копий i-ой хромосомы определяется значением $$M=P(x_i)*N$$, где N-мощность популяции. Число копий хромосомы, переходящих в следующее поколение, иногда определяется и так: $$\tilde M=\frac{f(x_i)}{\bar f(x)}$$, где $$\bar f(x)$$- среднее значение хромосомы в популяции.
(рис 1.4) Колесо рулетки
Расчетные числа копий хромосом по приведенной формуле следующие: хромосома 1 - 0,56; хромосома 2 - 1,97; хромосома 3 – 0,22; хромосома 4 – 1,23. В результате, в промежуточную популяцию 1-я хромосома попадает в одном экземпляре, 2-я – в двух, 3-я – совсем не попадает, 4-я – в одном экземпляре. Полученная промежуточная популяция является исходной для дальнейшего выполнения операторов кроссинговера и мутации.
Одноточечный или простой оператор кросинговера (ОК) с заданной вероятностью $$P_c$$ выполняется в три этапа:
1-й этап. Две хромосомы (родители) выбираются случайно (или одним из методов, рассмотренных далее) из промежуточной популяции, сформированной при помощи оператора репродукции (ОР).
2-й этап. Случайно выбирается точка скрещивания - число $$k$$ из диапазона $$[1,n-1]$$, где $$n$$– длина хромосомы (число бит в двоичном коде).
Две новых хромосомы A', B' (потомки) формируются из A и B путем обмена подстрок после точки скрещивания:
$$A'=a_1 a_2\dots a_k\ b_{k+1}\dots b_L\\B'=b_1 b_2\dots b_k\ a_{k+1}\dots a_L$$Например, рассмотрим выполнение кроссинговера для хромосом 1 и 2 из промежуточной популяции:
$$A=0\ 1\ 1\ 0\ 1\\B=1\ 1\ 0\ 0\ 0\\1\le k\le 4, k=4\\A'=0\ 1\ 1\ 0\ 0\\B'=1\ 1\ 0\ 0\ 1\\$$Следует отметить, что ОК выполняется с заданной вероятностью $$P_c$$ (отобранные два родителя не обязательно производят потомков). Обычно величина вероятности полагается равной $$P_c\approx 0,5$$.
Таким образом, операторы репродукции и скрещивания очень просты – они выполняют копирование особей и частичный обмен частей хромосом. Продолжение нашего примера представлено на рис.1.3 во второй таблице (кроссинговер).
Сравнение с предыдущей таблицей показывает, что в промежуточной популяции после скрещивания улучшились все показатели популяции (среднее и максимальное значения целевой функции - ЦФ).
Далее согласно
Оператор мутации (ОМ) выполняется в два этапа:
1-й этап. В хромосоме $$A=a_1 a_2\dots a_L$$ случайным образом выбирается $$k$$-ая позиция (бит) $$(1\le k\le n)$$.
2-й этап. Производится инверсия значения гена в $$k$$-й позиции: $$a'_k=\bar a_k$$
Например, для хромосомы 11011 выбирается $$k=3$$ и после инверсии значения третьего бита получается новая хромосома – 11111. Продолжение нашего примера представлено в третьей таблице (мутация) рис.1.3 образом, в результате применения
В данном случае, поскольку пример искусственно подобран, мы нашли оптимальное решение за одну итерацию. В общем случае ГА работает до тех пор, пока не будет выполнен критерий окончания процесса поиска и в последнем полученном поколении определяется лучшая особь, которая и принимается в качестве решения задачи.
В предыдущем примере мы рассматривали только целочисленные решения. Обобщим ГА на случай вещественных чисел на примере функции $$f(x)=(1,85-x)*\cos(3,5x-0,5)$$, представленной на рис.1.5 [14]. Рассматривается та же задача: необходимо найти вещественное $$x\in [-10,+10]$$, которое максимизирует $$f(x)$$, т.е. такое $$x_0$$, для которого $$f(x_0)\ge f(x)$$ для всех $$x\in [-10,+10]$$.
(рис 1.5) Пример функции с популяцией особей в начале эволюции
Для решения этой задачи с помощью ГА будем использовать представления вещественного решения (хромосомы) в виде двоичного вектора [15], который применяется в классическом простом ГА. Его длина зависит от требуемой точности решения, которую в данном случае положим, например, равной 3 знакам после запятой.
Поскольку отрезок области решения имеет длину 20, для достижения заданной точности отрезок $$[a,c]=[-10,+10]$$ должен быть разбит на равные части (маленькие отрезки), число которых должно быть не менее 20*1000. В качестве двоичного представления используем двоичный код номера (маленького) отрезка. Этот код позволяет определить соответствующее ему вещественное число, если известны границы области решения. Отсюда следует, что двоичный вектор для кодирования вещественного решения должен иметь 15 бит, поскольку $$16384=2^{14}<20000\le2^{15}=32768$$
Отсюда следует, что для обеспечения необходимой точности требуется разбить отрезок [-10,+10] на 32768 частей. Отображение из двоичного представления $$(b_{14} b_{13}\dots b_0)\ (b_i\in \{0,1\}$$ в вещественное число из отрезка $$[a,c]=[-10,+10]$$ выполняется в два шага.
Очевидно, при данном двоичном представлении вещественных чисел можно использовать классический
(рис 1.6) Начальная "конденсация" особей популяции в окрестностях экстремумов
(рис 1.7) "Конденсация" особей в окрестностях экстремумов
(рис 1.8) Положение особей популяции в конце эволюции
Для сокращения длины хромосом иногда применяют логарифмическое кодирование, при котором первый бит $$(a)$$ кодовой последовательности используется для знака показательной функции, второй бит $$(b)$$ – для знака степени этой функции, и остальные биты $$(str)$$ представляют значение самой степени [16]. Таким образом, двоичный код $$<a\ b\ str>$$ представляет вещественное число $$(-1)^a e^{(-1)^b [str]_{10}}$$. Здесь $$[str]_{10}$$ означает десятичное число, представленное двоичным кодом $$str$$.
Например, двоичный код $$<10101>$$ представляет вещественное число $$(-1)^0 e^{(-1)^1 [101]_{10}} =e^{-6}=0,002478752$$. Следует отметить, что при таком кодировании пять битов позволяет кодировать вещественные числа из интервала $$[-e^7,e^7]$$, что значительно больше, чем это позволяет, например, метод кодирования, представленный ранее.
Рассмотренное двоичное представление вещественного числа имеет существенный недостаток: расстояние между вещественными числами (на числовой оси) часто не соответствует расстоянию (по Хеммингу) между их двоичными представлениями. Поэтому желательно получить двоичное представление, где близкие расстояния между хромосомами (двоичными представлениями) соответствовали близким расстояниям в проблемной области (в данном случае расстоянию на числовой оси) [3,14,15]. Это можно сделать, например, с помощью кода Грея. В таблице 1.1 приведен для примера код Грея для 4-х битовых слов.
| Двоичный код | Код Грея |
|---|---|
| 0000 | 0000 |
| 0001 | 0001 |
| 0010 | 0011 |
| 0011 | 0010 |
| 0100 | 0110 |
| 0101 | 0111 |
| 0110 | 0101 |
| 0111 | 0100 |
| 1000 | 1100 |
| 1001 | 1101 |
| 1010 | 1111 |
| 1011 | 1110 |
| 1100 | 1010 |
| 1101 | 1011 |
| 1110 | 1001 |
| 1111 | 1000 |
Заметим, что в коде Грея соседние двоичные слова отличаются на один бит (расстояние по Хеммингу равно 1).
Рассмотрим алгоритмы преобразования двоичного числа $$\bar b=<b_1,\dots,b_m>$$ в код Грея $$\bar g=<g_1,\dots,g_m>$$ и наоборот.
(рис 1.9) Преобразование в код Грея
Здесь параметр m определяет разрядность двоичного числа. Существует и другая, матричная, процедура преобразования в код Грея. Например, для $$m=4$$ матрицы
$$A=\left[\begin{matrix}1000\\1100\\0110\\0011\end{matrix}\right] \mbox{и}\quad A^{-1}=\left[\begin{matrix}1000\\1100\\1110\\1111\end{matrix}\right]$$позволяют выполнять следующие преобразования:
$$\bar g=A\cdot\bar b\ \mbox{и}\ \bar b=A^{-1}\bar g$$где умножение матриц выполняются в арифметике по mod 2.
Отметим, что применение кода Грея прежде всего оправдано при использовании операторов мутации.
Определение соответствующей
В ГА используются четыре основных метода для учета накладываемых ограничений при решении оптимизационных задач. Вероятно, простейшим способом является метод отклонения (отбрасывания), где недопустимые хромосомы (не удовлетворяющие ограничениям) исключаются из дальнейшей эволюции. Второй метод основан на использовании процедуры восстановления, которая преобразует полученное недопустимое решение в допустимое. Другой альтернативой является применение проблемно-ориентированных
Рассмотренные методы не строят недопустимых решений. Но это не всегда дает хорошие результаты. Например, в том случае, когда оптимальные решения лежат на границе допустимой области, указанные методы могут давать неоптимальные решения. Одним из возможных вариантов преодоления этой проблемы является выполнение процедуры восстановления только для некоторого подмножества решений (например, 10% особей).
Для решения оптимизационных задач со сложными ограничениями иногда позволяют вести поиск решения и в недопустимых областях. Реализуется это подход часто с помощью метода штрафных функций, что позволяет расширить пространство поиска решений. Следует отметить, что часто недопустимая точка, близкая к оптимальному решению, содержит больше полезной информации, чем допустимая точка, далекая от оптимума. С другой стороны, построение штрафных функций является достаточно сложной проблемой, которая сильно зависит от решаемой задачи. Обычно нет априорной информации о расстоянии до оптимальных точек, есть только расстояние до границы области допустимых решений. Поэтому, как правило, штрафные функции используют расстояние до границ допустимой области. Штрафы, основанные на нарушении отдельных ограничений, работают обычно не очень хорошо.
Разработаны два основных способа построения штрафных функций со штрафным термом: аддитивная и мультипликативная формы. В первой форме функция представляется в виде $$g(x)=f(x)+p(x)$$, где при максимизации для допустимых точек $$p(x)=0$$ и в противном случае $$p(x)<0$$. Максимум значения $$p(x)$$ по абсолютной величине не может быть больше, чем минимальное значение $$f(x)$$ по абсолютной величине для любой генерации, чтобы избежать отрицательных фитнесс-значений. Мультипликативная форма представляет функцию в виде $$g(x)=f(x)\cdot p(x)$$, где при максимизации $$p(x)=1$$ для допустимых точек и $$0\le p(x)<1$$ в противном случае.
При этом штрафной терм должен изменяться не только в зависимости от степени нарушения ограничения, но и от номера поколения ГА. Наряду с нарушением ограничения, штрафной терм обычно содержит штрафные коэффициенты (по одному для каждого ограничения). На практике большую роль играют значения этих коэффициентов. Маленькие значения коэффициентов могут привести к недопустимым значениям решения, в то время как большие значения полностью отвергают недопустимые подпространства. В среднем абсолютные значения целевой и штрафной функции должны быть соизмеримы. При таком подходе параметры штрафной функции можно включить в параметры ГА, что позволяет разработать адаптивный метод, где значения коэффициентов регулируются в процессе поиска решения.
В целом на выбор (построение)
В ГА
Для некоторых задач оценку значений
(рис 1.10) Схема взаимодействия объектной модели с ГА.
Теоретические основы ГА составляют двоичное стринговое представление решений (хромосом) и понятие
В простом ГА основная идея заключается в объединении хромосом со значениями целевой функции (ЦФ) выше среднего. Например, пусть 1 в хромосоме соответствует наличию признака, способствующего выживанию (значение целевой функции больше среднего). Допустим, что имеются подстринги вида 11*** и **111. Тогда, применяя к ним ОК можно получить хромосому 11111 с признаками, способствующими наилучшим значениям
Не все
Обозначим через $$m(H,t)$$– число стрингов, содержащихся в популяции $$A(t)$$($$t$$ – шаг итерации или время), которые отображаются (покрываются)
Пусть $$f(H)$$ означает среднее значение
Напомним, что в процессе репродукции хромосомы копируются в промежуточную популяцию согласно их значениям
После репродукции мы ожидаем на следующем шаге получить m(H,t+1) двоичных стрингов, отображаемых
Это обусловлено тем, что:
Мы можем переписать эту формулу с учетом обозначения $$\overline{f(x)}=\frac{\sum_{j=1}^N f(x_j)}{N}$$ и получим следующее выражение для числа особей, покрываемых
Другими словами,
Предположим, что схема $$H$$ имеет значение выше среднего
Начиная с $$t=0$$ и предполагая, что $$c$$– величина постоянная, получаем следующее выражение числа особей промежуточной популяции, покрываемых
Это равенство описывает геометрическую прогрессию. Очевидно, что при $$c>0$$
Далее рассмотрим влияние оператора кроссинговера на число особей в популяции, покрываемых
Рассмотрим конкретный стринг $$А=011|1000$$ длины $$n=7$$ и две
Здесь символ "|" , как обычно, обозначает точку кроссинговера $$k=3$$.
Очевидно, что
Очевидно, что эта же
Аналогично,
Если ОК выполняется посредством случайного выбора, например, с вероятностью $$P_c$$, то вероятность выживания
Очевидно, что это выражение уменьшается при $$P_c\to 1$$. Теперь мы можем асимптотически оценить совместный эффект операторов репродукции и кроссинговера. При независимости выполнения OP и OK можно получить следующее выражение:
$$m(H,t+1)\ge m(H,t)\frac{f(H)}{\bar f}[1-P_c\frac{L(H)}{n-1}]$$Таким образом, число
Видно, что
Далее рассмотрим влияние оператора мутации на число особей в популяции, покрываемых
Напомним, что оператор мутации (ОМ) есть случайное изменение элемента в стринге с вероятностью $$P_m$$. Очевидно, что для того чтобы
Из этого следует, что
Этот важный результат известен как
Теорема 1.1.
На основании приведенных результатов была выдвинута гипотеза о строительных блоках.
Гипотеза 1.1. Генетический алгоритм стремится достичь близкого к оптимальному результата за счет комбинирования хороших
Такие
Несмотря на то, что для доказательства этой гипотезы были предприняты значительные усилия, строгого доказательства получено не было, и в большинстве нетривиальных приложений опираются на эмпирические результаты.
Далее проиллюстрируем приведенные результаты. Вернемся к примеру Голдберга определения $$\mbox{max}\ f(x)=x^2$$. В дополнение к имеющимся таблицам рис 1.3 пусть имеется 3 конкретные
Рассмотрим сначала
| Схема | Перед репродукцией | Представители стрингов | Среднее значение ЦФ схемы $$f(H)$$ |
|---|---|---|---|
| $$H_1$$ | 1**** | 2,4 | 469 |
| $$H_2$$ | *10** | 2,3 | 320 |
| $$H_3$$ | 1***0 | 2 | 576 |
Проверим, соответствует ли это число фундаментальной теореме
| Схема | После репродукции | После всех операторов | ||||
|---|---|---|---|---|---|---|
| Ожидаемое число стрингов | Действительное число стрингов | Представители стрингов | Ожидаемое число стрингов | Действительное число стрингов | Представители стрингов | |
| $$H_1$$ | 3,20 | 3 | 2, 3, 4 | 3,20 | 3 | 2, 3, 4 |
| $$H_2$$ | 2,18 | 2 | 2, 3 | 1,64 | 2 | 2, 3 |
| $$H_3$$ | 1,97 | 2 | 2, 3 | 0,0 | 1 | 4 |
Сравнивая это число с реальным числом копий 3, видим, что округление рассчитанного значения копий 3,2 дает их реальное число 3. Дальнейший анализ показывает, что в данном случае ОК не оказывает влияние на число стрингов, покрываемых
Рассмотрим теперь
Заметим, что для конкретной
Для
В соответствие с полученными результатами видно, что важнейшим аспектом является кодирование особей, которое должно обеспечить построение
Следующий простой пример показывает важность построения генома с учетом теорем
Рассмотрим поиск максимума (для простоты при целочисленных значениях $$x$$ и $$y$$) функции $$f(x,y)=x^2-y+17$$. Можно показать, что максимум $$f=66$$ достигается при значениях $$x=(111)_2=(7)_{10}$$ и $$y=(0000)_2=(0)_{10}$$. Пусть $$x=x_2x_1x_0$$ и $$y= y_3y_2y_1y_0$$, где $$x_i,y_j\in \{0,1\}$$. Рассмотрим различное строение геномов. В первом случае пусть генотип представляет $$y_3x_2y_2x_1y_1x_0y_0$$, во втором генотип определим как $$y_3y_2y_1y_0\ x_2x_1x_0$$. Отметим, что в первом случае старшие разряды $$x$$ и $$y$$ расположены в генотипе близко, а во втором варианте наоборот – достаточно далеко. Поскольку желательна короткая определенная длина, генетический алгоритм с геномом, в котором старшие разряды расположены близко, должен быть лучше по сравнению с геномом, где эти разряды стоят далеко друг от друга. Для первого случая $$\frac{L(H)}{1-n}=\frac{1}{6}$$ для
Эффективность ГА зависит от ряда параметров, к которым относятся: мощность популяции, структура представления решения, вид генетических операторов кроссинговера и мутации, вероятности кроссинговера и мутации $$P_c$$ и $$P_m$$ и т.п..
Мощность популяции $$N$$ является важнейшим параметром ГА, который критичен во многих приложениях. Чем больше $$N$$, тем больше разнообразие потенциальных решений (при хорошей
На разных этапах работы ГА оптимальное значение $$N$$ может быть различным. На начальном этапе $$N$$ должно быть большим, а на заключительном $$N$$ можно уменьшить. Большую роль играют также вид
Для оптимизации, особенно мультимодальных функций, наиболее существенными являются две характеристики ГА:
Баланс между этими характеристиками ГА в значительной степени определяется значениями вероятности $$P_c$$ и $$P_m$$, типом используемых
Основным преимуществом ГА является их концептуальная простота. Рассмотрим снова блок-схему ГА, представленную на рис.1.1 Основными шагами алгоритма являются: инициализация, оценка качества решения с помощью
ГА могут быть использованы при решении любой проблемы, которая может быть сформулирована как задача оптимизации. Они требуют разработки (или выбора) структуры данных для представления потенциального решения, показателя качества для оценки потенциального решения и
Реальные задачи оптимизации часто:
Целевые функции для реальных проблем часто мультимодальны и градиентные методы сходятся быстро к локальным экстремумам, которые могут давать неудовлетворительные решения. Для простых задач, где поверхность отклика, например, является строго выпуклой, генетические алгоритмы проигрывают классическим по эффективности. Эксперименты показали, что для мультимодальных функций ГА дают лучшие результаты. В случае нелинейных ограничений классические методы даже при выпуклой поверхности могут давать некорректные результаты. Напротив, эволюционные методы могут непосредственно учитывать произвольные линейные и нелинейные ограничения.
При решении конкретной проблемы всегда целесообразно учесть в алгоритме проблемно-ориентированные априорные знания [17]. Специализированные алгоритмы, учитывающие такую информацию (но имеющие ограниченную область применения), как правило, существенно превосходят по характеристикам неспециализированные методы. Эволюционные алгоритмы по своей структуре легче позволяют учитывать априорные знания. Это может быть выражено, например, в виде специальной структуры данных для представления решений или специальных проблемно-ориентированных
Генетические алгоритмы могут комбинироваться с другими более традиционными методами. Известны работы, где на первом этапе оптимизации используются генетические алгоритмы совместно с градиентным методом, который применяется на заключительном этапе, когда уже найдена "зона интереса". Эти алгоритмы могут применяться совместно и параллельно. Отметим, что начальная популяция потенциальных решений может быть получена путем применения, например, жадных алгоритмов, а не эволюционных методов. Генетические алгоритмы часто используются для оптимизации и обучения искусственных нейронных сетей или нечетких продукционных систем. В этом случае часто удается преодолеть ограничения, связанные с традиционными подходами.
Эволюция является высоко параллельным процессом, поскольку популяция состоит из множества особей, которые развиваются параллельно. Это позволяет расширить возможности применения эволюционных вычислений для решения все более сложных задач. Отметим, что основные вычислительные ресурсы в генетических алгоритмах используются при оценке значений
Традиционные методы оптимизации неустойчивы к динамическим изменениям окружающей среды и часто требуют полного рестарта при таких изменениях для получения адекватного решения. Напротив, эволюционные алгоритмы могут быть использованы для адаптации потенциальных решений к изменившимся условиям. Полученная на момент изменения популяция дает базис для дальнейшего улучшения решений и в большинстве случаев нет необходимости проводить случайную реинициализацию.
Большинство классических методов требуют начальной установки соответствующих параметров алгоритмов. Это также относится и к генетическим алгоритмам, которые зависят от множества параметров, таких как мощность популяции, вероятности кроссинговера и мутации, шаг мутации и т.п. Однако в эволюционных алгоритмах легче ввести самоадаптацию, когда в процессе поиска решения указанные параметры оптимизируются.
Возможно, самым большим преимуществом генетических алгоритмов является их способность исследовать проблемы, для которых нет экспертов и соответствующего опыта решений. Следует отметить, что экспертные оценки достаточно часто используются при решении трудно формализуемых задач, но они иногда дают менее адекватные решения, чем автоматизированные методы. Существуют определенные проблемы с получением знаний у экспертов: они могут не согласиться на это, могут быть неквалифицированными, могут быть несовместимыми и просто ошибаться.
Исследования по искусственному интеллекту в настоящее время дали ряд интересных результатов, каждый из которых позволяет эффективно решать свой класс задач (например, хорошо играть в шахматы, или распознавать изображения символов и т.п.). Но большинство этих узких приложений требуют участия человека. Эти методы могут эффективно решать некоторые сложные проблемы, требующие высокого быстродействия, но они не могут конкурировать с человеческим интеллектом - "Они решают проблемы, но они не решают проблему как решать проблемы". Напротив, эволюционные алгоритмы дают метод решения проблемы, как решать проблемы при отсутствии экспертов (человеческого опыта) [17].
Естественно ГА не свободны от недостатков. К ним можно отнести прежде всего следующие. Конфигурация ГА для решения сложных реальных задач не очевидна. Для решения конкретной задачи необходимо выбрать или разработать представление (кодирование) потенциального решения. Существует также проблема определения
Возникает естественный вопрос – существует ли некоторый лучший эволюционный алгоритм, который дает всегда лучшие результаты при решении всевозможных проблем? Например, можно ли выбрать
NFL теорема. Для любой пары алгоритмов $$a_1$$ и $$a_2$$ имеет место равенство $$\sum_f P(d_m^y|f,m,a_1)=\sum_f P(d_m^y|f,m,a_2).$$
Таким образом, сумма условных вероятностей посещения в пространстве решений каждой точки $$d_m$$ одинакова для множества всевозможных целевых функций независимо от используемого алгоритма. Из этого результата непосредственно следует, что при любой мере $$\Phi(d_m^y)$$ производительности (характеристик сложности) алгоритма в среднем для всевозможных целевых функций $$f$$ вероятность $$P(\Phi(d_m^y)|f,m,a)$$ не зависит от алгоритма $$a$$. Другими словами, не существует лучшего алгоритма (эволюционного или любого другого) для решения всех проблем. Если алгоритм выигрывает по своим характеристикам при решении некоторого класса задач, то это неминуемо компенсируется проигрышем (худшими характеристиками) для остальных задач.
Эта теорема вызвала оживленную дискуссию у специалистов по эволюционным вычислениям и некоторое неприятие. Дело в том, что в семидесятых годах были предприняты значительные усилия по поиску лучших значений параметров и
Каждому эволюционному алгоритму присуще некоторое представление, которое позволяет манипулировать с потенциальными решениями. NFL теорема утверждает, что не существует лучшего эволюционного алгоритма для решения всех проблем.
Для того чтобы разрабатываемый алгоритм решал поставленную задачу лучше, чем случайный поиск (который с точки зрения NFL теоремы является просто другим алгоритмом) необходимо в нем использовать (отразить) структуру (априорные знания) этой проблемы. Из этого следует, что такой алгоритм может не соответствовать структуре другой проблемы (и покажет для нее плохие результаты). Следует отметить, что недостаточно просто указать, что проблема имеет некоторую структуру - такая структура должна соответствовать разрабатываемому алгоритму. Более того, структура должна быть определена. Недостаточно, как это иногда бывает, сказать "Мы имеем дело с реальными проблемами, а не с всевозможными, поэтому NFL теорема не применима". Что значит структура реальной проблемы? Очевидно, что формальное описание такой структуры проблематично. Например, реальные проблемы нашего времени и столетней давности могут сильно отличаться. Следует отметить, что простое сужение области возможных проблем без идентификации соответствия между рассматриваемым множеством проблем и алгоритмом недостаточно для получения преимущества данного метода решения этих проблем по сравнению с другими.
NFL-теорема подтверждает, что разные алгоритмы имеют различную эффективность при решении разных задач. Например, классические методы оптимизации, как правило, более эффективны при решении линейных, квадратичных, строго выпуклых, унимодальных, разделяемых и других специальных классов проблем. С другой стороны, генетические алгоритмы часто успешно решают задачи там, где классические методы не работают – там, где целевые функции терпят разрывы, не дифференцируемы, мультимодальны (имеют много экстремумов), зашумлены и т.п. Обычно их эффективность и устойчивость выше там, где целевые функции имеют сложный (не стандартный) вид, что более характерно для решения реальных практических задач. Конечно, лучшим способом подтверждения эффективности алгоритма является доказательство его сходимости и оценки вычислительной сложности. Но, как правило, это возможно только в случае упрощенной постановки задачи. Другой альтернативой является проверка алгоритмов на тестовых задачах (benchmarks) данной проблемной области. К сожалению, в настоящее время не существует согласованного каталога таких задач для оценки старых или новых алгоритмов решения, хотя для многих типовых задач они уже сложились и широко используются.
Выполните программную реализацию простого ГА на одном из языков программирования для поиска экстремума заданной по варианту функции одной переменной (табл. 1.5).
Вид экстремума:
| Вариант | Вид экстремума |
|---|---|
| $$\le 15$$ | Максимум |
| $$> 15$$ | Минимум |
| Вариант | Вид функции | Промежуток поиска решения |
|---|---|---|
| 1 | $$(1,85-x)*\cos(3,5x-0,5)$$ | $$x\in [-10,10]$$ |
| 2 | $$\cos(\exp(x))/\sin(\ln(x))$$ | $$x\in [2,4]$$ |
| 3 | $$\sin(x)/x^2$$ | $$x\in [3.1,20]$$ |
| 4 | $$\sin(2x)/x^2$$ | $$x\in [-20,-3.1]$$ |
| 5 | $$\cos(2x)/x^2$$ | $$x\in [-20,-2.3]$$ |
| 6 | $$(x-1)\cos(3x-15)$$ | $$x\in [-10,10]$$ |
| 7 | $$\ln(x)\cos(3x-15)$$ | $$x\in [1,10]$$ |
| 8 | $$\cos(3x-15)/|x|=0$$ | $$x\in [-10,-0.3),(0.3,10]\\x\in[-0.3,0.3]$$ |
| 9 | $$\cos(3x-15)*x$$ | $$x\in [-9.6,9.1]$$ |
| 10 | $$\sin(x)/(1+\exp(-x))$$ | $$x\in [0.5,10]$$ |
| 11 | $$\cos(x)/ (1+\exp(-x)$$ | $$x\in [0.5,10]$$ |
| 12 | $$(\exp(x)-\exp(-x))\cos(x)/(\exp(x)+\exp(-x))$$ | $$x\in [-5,5]$$ |
| 13 | $$(\exp(-x)-\exp(x))\cos(x)/(\exp(x)+\exp(-x))$$ | $$x\in [-5,5]$$ |
| 14 | $$\cos(x-0,5)/|x|$$ | $$x\in [-10,0),(0,10],\min$$ |
| 15 | $$\cos(2x)/|x-2|$$ | $$x\in [-10,2),(2,10],\max$$ |
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.