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

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




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

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, выбираемого из интервала (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, предназначен для интерак­тивного моделирования нелинейных динамических систем, состоящих из стандартных блоков. Данный пакет также дает возможность работы с нейронными сетями. Ниже рассмотрены функции, позволяющие синтезировать НС.

Поделиться:





Читайте также:

Q Приведите, пожалуйста примеры нарушений выполнения этой пробы при различных видах афазий.
Q Приведите, пожалуйста, примеры подобных нарушений внимания. Наиболее показательные примеры, на наш взгляд, относятся к сфере интеллектуальной деятельности и памяти.
Ассемблер в системе команд 8-разрядного МП. Типы ассемблеров. Требования к полям записи программ на ассемблере. Примеры программирования на ассемблере.
Биохимические методы при генетических исследованиях
Более подробно о пилот-волнах и морфогенетических полях
Более сложные примеры соединений
Виды и примеры экономических задач оптимизации и управления
Возможность исследования физиологических и генетических основ рассудочной деятельности.
Возможные комбинации генетических родителей будущего
Вопрос 46. Гомогенно-каталитические процессы. Кислотно-основной катализ. Ферментативный катализ. Примеры.






Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...