назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [ 30 ] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42]


30

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

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

Четвертое семейство методов многомерной оптимизации образуют квази-ньтоновы, или методы с переменной метрикой variable metric methods. Туда входят алгоритмы Дэвидсона-Флет-чера-Пауэла (DiP) и Бройдена-Флетчера-Голдфарба-Шанно (ВЛ]г8). Подобно conjugate gradient methods, они требуют вычисления частных производных первого порядка, обычно быстро приводят к экстремуму, однако эти алгоритмы требуют большей памяти (порядка tf). Вместе с тем они уравновешивают достогшства conjugate gradient methods тем, что дольше известны, шире используются и лучше документально обеспечены.

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

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

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

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

Естественный отбор

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

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

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

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



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

Поэтому, когда мы спращиваем «Какой из кандидатов наиболее приспособлен?», мы сталкиваемся с парадоксальным ответом «Тот, который является победителем».

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

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

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

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

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

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

Алгоритм содержит следующие основные шаги:

Длина гена. Вы должны задать длину гена. Ген - это двоичное представление члена популяции вариантов решений. Каждый член этой популяции характеризуется значением каждой переменной (т. е. значением /для каждого сценарного спектра). Так, если мы принимаем длину гена в двенадцать раз больше количества сценарных спектров, то каждой переменной (т. е. значению j) у нас будет соответствовать по двенадцать бит. Двенадцати битов достаточно для представления величины в интервале от О до 4095. Последнее число представляется в виде:

2° + 2 + 2 + ... + 2" = 4095

Возводим 2 в степень О и прибавляем 2 в следующей степени, пока не дойдем до степени, равной количеству битов минус 1 (т. е. 11, в данном случае). Если имеется, скажем, три сценарных спектра и на каждый из них мы используем длину в двенадцать битов, то длина гена каждого варианта решения есть 12 * 3 = 36 бит. То есть ген в данном случае - это строка из 36 двоичных битов.



Обратите внимание, что данный способ кодирования двоичных строк подходит только для целых величин. Но мы можем приспособить его и для чисел с плавающей запятой с помощью некоторого постоянного делителя. Так, если мы выберем постоянный делитель равным, скажем, 1000, то сможем представлять числа от 0/1000 до 4095/1000, или от О до 4,095, с точностью до 0,001.

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

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

Задание целевой функции. Битовые строки декодируются в свои десятичные эквиваленты, которые используются для задания целевой функции. (Например, при наличии двух сценарных спектров целевая функция дает нам величину координаты Z, или высоту трехмерного изображения, в предположении, что величины / соответствующих сценарных спектров - это координаты X и Y.) Это проделывается для всех вариантов решений, и значения целевой функции для них сохраняются. (Важно: значения целевой функции должны быть неотрицательными!)

Репродуцирование

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

Случайный отбор по приспособленности. Теперь ранжированные целевые функции упорядочиваются следующим образом. Если, скажем, у первой целевой функции коэффициент приспособленности равен 0,05, у второй - 0,1, а у третьей - 0,08, то они

следующим образом включаются в схему отбора (образуются интервалы):

первый вариант О - 0,05;

второй вариант 0,05 - 0,15;

третий вариант 0,15 - 0,23.

И так продолжают далее, пока верхняя граница последнего варианта не окажется на 1,0.

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

Кроссовер*. Последовательно формируется каждый бит ребенка - нового варианта решения популяции. Начинают с копирования первого бита первого родителя в первый бит ребенка. Одновременно с этим вы должны генерировать случайное число. Если это случайное число оказывается меньше или равно вероятности кроссовера, деленной на длину гена, то переключаемся на копирование битов от другого родителя. Так, если у нас три сценарных спектра с двенадцатью битами для каждой переменной, то длина гена равна тридцати шести. Если используемая нами вероятность кроссовера равна 0,6, то для переключения на копирование кода другого родителя в последующих битах, генерируемое при каждом бите случайное число должно быть меньше 0,6/36, или 0,01667. Это продолжается до тех пор, пока все биты не будут скопированы в коде ребенка. Данную операцию нужно проделать для всех новых членов популяции.

Обычно вероятности кроссовера находятся в интервале от 0,6 до 0,9. Так, вероятность кроссовера 0,9 означает, что шансы возникновения кроссовера у ребенка будут равны 90% , в среднем; то есть 10% шансов будет за то, что ребенок будет точной копией одного из родителей.

Мутация. Попутно с копированием каждого бита родителя в бит ребенка генерируется второе случайное число. Если это

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

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [ 30 ] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42]