Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Генетические алгоритмы и их применение в моделировании технических систем.⇐ ПредыдущаяСтр 12 из 12
Генетические алгоритмы (ГА) (genetic algorithms) – большая группа методов адаптивного поиска и многопараметрической оптимизации, связанная принципами естественного отбора и генетики. В общем случае при использовании ГА задачи оптимизации имеют следующую математическую формулировку [4]: найти такое значения варьируемых параметров , которые минимизируют целевую функцию при условии, что указанные параметры удовлетворяют допустимой области , задание которой диктуется спецификой решаемой задачи. В качестве варьируемых параметров в этих случаях могут быть числовые коэффициенты регрессионной модели; число базисных функций; порядок уравнений регрессии; числовые коэффициенты , , функций принадлежности; число функций принадлежности; число слоев и число нейронов в каждом слое нейронной сети. При указанных варьируемых параметрах целевыми функциями могут быть: ошибка идентификации и прогноза в текущий или будущий момент времени; один из показателей качества процесса (функционал); ошибка обучения НС – рассогласование между выходными объекта и эталонной модели системы. Наиболее общее определение: генетические алгоритмы (ГА) – это методы случайного глобального поиска, копирующие механизмы естественной биологической эволюции. Следует отметить, что существует много различных модификаций ГА. Здесь рассмотрим элементы простейшего его варианта – стандартного. Стандартный ГА – метод стохастической оптимизации для задач дискретной оптимизации вида.
Здесь – функция пригодности (fitness function); – -мерный двоичный вектор из дискретного множества – хромосома (chromosome) или двоичная нить (string) длины . Множество – множество вершин - мерного гиперкуба с единичным ребром; – множество действительных чисел. Главное отличие стандартного ГА от традиционных методов оптимизации – на каждом шаге ГА имеет дело сразу с несколькими значениями вектора параметров , которые образуют популяцию (population) хромосом. В начале процедуры поиска создается начальная популяция, например, из двоичных хромосом: = , каждая из которых содержит битов. Такая популяция создается либо случайным образом, либо с учетом априорной информации об области нахождения оптимума в множестве .
Под двоичным вектором-хромосомой понимается двоичное кодирование исходного варьируемого параметра , физический смысл которого определяется задачей. Длина хромосомы (число битов) при таком кодировании зависит от требуемой точности нахождения оптимума параметра и должна удовлетворять условию
где , – предельные значения параметра ; – заданная погрешность определения его оптимального значения. Число членов в популяции влияет на широту фронта поиска и задается эмпирически. Вычисление последующих популяций , и т.д. на базе осуществляется путем применения трех генетических операторов: отбора (selection), кроссинговера (crossingover) и мутации (mutation). Отбор в стандартном ГА реализуется методом "колеса рулетки", при котором хромосомы-кандидаты из -го поколения выбираются для выживания в следующем, -м поколении путем использования колеса рулетки. Каждая хромосома в популяции представлена на колесе в виде сектора с шириной, пропорциональной функции пригодности . Для отбора хромосом колесо рулетки вращают раз. В результате по завершении каждого вращения выделяется одна из хромосом , которые принимаются в качестве кандидатов в следующем поколении. Перед их копированием в новую популяцию они должны подвергнуться кроссинговеру и мутации. Оператор кроссинговера (скрещивания) применяется к паре хромосом из (пусть -четное), прошедших отбор. – назначаемая вероятность выполнения кроссинговера. Далее для случайно выбранной пары хромосом определяется случайное число (место или сайт кроссинговера), и затем биты из двух выбранных хромосом меняются местами после -го бита с вероятностью . Процесс повторяется до момента, когда популяция не окажется пустой. Оператор мутации состоит в случайном изменении (на противоположное) значения каждого бита гена с вероятностью . Самым легким способом определения изменяемых бит (если это необходимо) – выбор независимого случайного числа для каждого бита хромосомы. Если , то -й бит следует изменить, в противном случае он сохраняется. После мутации хромосомы-кандидаты копируются в новую популяцию хромосом и весь процесс повторяется с вычислением функции пригодности для каждой хромосомы и применением операторов отбора, кроссинговера и мутации (рис. 5.8.) [4].
Отбор методом "колеса рулетки" позволяет претендовать на выживание хромосомам с пригодностью выше среднего. Детерминированный подход по принципу выбора хромосом с наибольшей пригодностью не применяется в соответствии с допущениями генетического поиска, согласно которым даже хромосомы с низкой пригодностью могут содержать полезную информацию. Наиболее критическим из перечисленных трех является оператор кроссинговера, так как он отвечает за смешивание информации хромосом поколение популяции, а от этого зависит глобальность получаемых результатов. Установлено эмпирически, что . Операторы отбора и кроссинговера используются для улучшения структуры хромосом. Цель оператора мутации – диверсификация, т.е. повышение разнообразия поиска и введение новых хромосом в популяцию для большей полноты исследования пространства поиска. Мутация инициирует разнообразие в популяции, позволяя просматривать больше точек в пространстве поиска и преодолевать локальные эксперименты в ходе поиска. Частое применение мутации приводит к разрушению хромосом с высокой приспособленностью в популяции, что сказывается на сходимости решения. Поэтому применение мутации обычно осуществляется с малой вероятностью: . В последнее время область применения ГА значительно расширилась. Данные методы оказываются эффективными при решении следующих задач [4]: · идентификация сложных динамических объектов; · выбор оптимальной конфигурации многоагентных робототехнических систем; · синтез оптимальных алгоритмов управления многозвенными роботами-манипуляторами; · оптимальное управление стыковкой космических аппаратов; · планирование маршрутов движения транспортных средств в условиях препятствий; · структурный синтез проектных решений, синтез расписаний и многих других. Таким образом, применение ГА охватывает не только класс традиционных задач оптимизации, но и быстро распространяется на задачи управления сложными динамическими объектами в условиях неопределенности. Нельзя не отметить, что область применения ГА существенно расширилась. Одним из таких расширений является генетическое программирование (ГП), под которым понимается применение генетической модели обучения в пространстве программ. В этом случае в качестве индивидуумов, составляющих популяцию, выступают уже не указанные выше достаточно простые линейные структуры – хромосомы, а компьютерные программы, которые, будучи исполненными, представляют собой кандидатов на решение поставленной задачи.
Вопросы для самопроверки Рекомендуемая литература
|
|||||||||||||||||||
Последнее изменение этой страницы: 2017-01-23; просмотров: 85; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.17.6.75 (0.01 с.) |