Главная | Обратная связь | Поможем написать вашу работу!

Примеры генетических операторов

Выделяют два основных способа генерации новых решений:

1) путем перекомпоновки (скрещивания) двух родительских решений
(оператор скрещивания или кроссинговер сr) (рис. 4);

2) путем случайной перестройки отдельных решений (оператор мутации т) (рис. 5).

Рис. 4 Одноточечный кроссинговер Рис. 5 Оператор мутации

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

Применение оператора мутации т в процессе биологической эволюции предотвращает потерю важного генетического материала; в генетических алгоритмах т используется для выхода из локальных экстремумов. На практике при использовании ГА для решения задач оптимизации встречаются классические операторы генной мутации: изменение величины случайно выбранного гена (рис. 5). Для улучшения технологии генетического поиска оптимальных решений целесообразно применять операторы хромосомной мутации.

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

Селекция решений

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

1) случайный выбор пар;

2) предпочтительный выбор на основе функции фитнесса.

Алгоритм имитации отжига

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

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

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

Классический алгоритм имитации отжига можно описать следующим образом.

1. Запустить процесс из начальной точки w при заданной начальной температуре Т = Т _m_ах.

2. Пока T > 0, повторить L раз следующие действия:

• выбрать новое решение w ' из окрестности w;

• рассчитать изменение целевой функции Δ = E (w ') - E(w);

• если Δ <= 0, принять w = w '; в противном случае (при Δ > 0) принять, что w = w ' с вероятностью ехр(-Δ / Т) путем генерации случайного числа R из интервала (0,1) с последующим сравнением его со значением ехр(-Δ / Т); если ехр(-Δ / Т) > R, принять новое решение w = w '; в противном случае проигнорировать его.

3. Уменьшить температуру (Т < rТ) с использованием коэффициента уменьшения r, выбираемого из интервала (0,1), и вернуться к п. 2.

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

В описании алгоритма в качестве названия параметра, влияющего на вероятность увеличения значения целевой функции, используется выбранный его автором Н. Метрополисом термин "температура", хотя с формальной точки зрения приведенная модель оптимизации является только математической аналогией процесса отжига. Алгоритм имитации отжига выглядит концептуально несложным и логически обоснованным. В действительности приходится решать много фундаментальных проблем, которые влияют на его практическую применимость. Первой следует назвать проблему длительности имитации. Для повышения вероятности достижения глобального минимума длительность отжига (представляемая количеством циклов L, повторяемых при одном и том же значении температуры) должна быть достаточно большой, а коэффициент уменьшения температуры r - низким. Это увеличивает продолжительность процесса моделирования, что может дискредитировать его с позиций практической целесообразности.

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

Большое влияние на эффективность метода имитации отжига оказывает выбор таких параметров, как начальная температура T _m_ах, коэффициент уменьшения температуры r и количество циклов L, выполняемых на каждом температурном уровне.

Максимальная температура подбирается по результатам многочисленных предварительных имитационных экспериментов. На их основе строится распределение вероятности стохастических изменений текущего решения при конкретных значениях температуры (зависимость А = f /(T)). В последующем, задаваясь процентным значением допустимости изменений в качестве порогового уровня, из сформированного распределения можно найти искомую начальную температуру. Главной проблемой остается определение порогового уровня, оптимального для каждой реализации процесса имитации отжига. Для отдельных практических задач этот уровень может иметь различные значения, однако общий диапазон остается неизменным. Как правило, начальная температура подбирается так, чтобы обеспечить реализацию порядка 50% последующих случайных изменений решения. Поэтому знание предварительного распределения вероятностей таких изменений позволяет получить приблизительную оценку начальной температуры.

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

Большая часть вычислительных ресурсов расходуется на начальной стадии процесса, когда средняя скорость изменения целевой функции невелика и прогресс оптимизации минимален. Это "высокотемпературная" стадия имитационного процесса. Быстрее всего величина целевой функции уменьшается на средней стадии процесса при относительно небольшом количестве приходящихся на нее итераций. Завершающая стадия процесса имеет стабилизационный характер. На ней независимо от количества итераций прогресс оптимизации становится практически незаметным. Такое наблюдение позволяет существенно редуцировать начальную стадию отжига без снижения качества конечного результата. Модификации обычно подвергается количество циклов, выполняемых при высоких температурах, оно сокращается в случае, когда оказался выполненным весь запланированный объем изменений текущего решения. Такой подход позволяет сэкономить до 20% времени.

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

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

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

Выполнение

Пакет MatLab был создан компанией MathWorks более десяти лет назад. Работа сотен ученых и программистов направлена на постоянное расширение его возможностей и совершенствование заложенных алгоритмов. В настоящее время MatLab является мощным и универсальным средством решения задач, возникающих в различных областях человеческой деятельности. Спектр проблем, исследование которых может быть осуществлено при помощи MatLab, охватывает: матричный анализ, обработку сигналов и изображений, задачи математической физики, оптимизационные задачи, обработку и визуализацию данных, работу с картографическими изображениями, нейронные сети, нечеткую логику и многие другие. Специализированные средства собраны в пакеты, называемые ToolBox, и могут быть выборочно установлены вместе с MatLab по желанию пользователя. В состав многих ToolBox входят приложения с графическим интерфейсом пользователя, которые обеспечивают быстрый и наглядный доступ к основным функциям. Пакет Simulink, поставляемый вместе с MatLab, предназначен для интерактивного моделирования нелинейных динамических систем, состоящих из стандартных блоков. Данный пакет также дает возможность работы с нейронными сетями. Ниже рассмотрены функции, позволяющие синтезировать НС.

⇐ Предыдущая 4 5 6 7 8910 11 12 13 Следующая ⇒