|
||||||||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Генетические алгоритмы и их применение в моделировании технических систем
Генетические алгоритмы (ГА) (genetic algorithms) – большая группа методов адаптивного поиска и многопараметрической оптимизации, связанная принципами естественного отбора и генетики. В общем случае при использовании ГА задачи оптимизации имеют следующую математическую формулировку: найти такое значения варьируемых параметров , которые минимизируют целевую функцию при условии, что указанные параметры удовлетворяют допустимой области , задание которой диктуется спецификой решаемой задачи. В качестве варьируемых параметров в этих случаях могут быть числовые коэффициенты регрессионной модели; число базисных функций; порядок уравнений регрессии; числовые коэффициенты , , функций принадлежности; число функций принадлежности; число слоев и число нейронов в каждом слое нейронной сети. При указанных варьируемых параметрах целевыми функциями могут быть: ошибка идентификации и прогноза в текущий или будущий момент времени; один из показателей качества процесса (функционал); ошибка обучения НС – рассогласование между выходными объекта и эталонной модели системы. Наиболее общее определение: генетические алгоритмы (ГА) – это методы случайного глобального поиска, копирующие механизмы естественной биологической эволюции. Следует отметить, что существует много различных модификаций ГА. Здесь рассмотрим элементы простейшего его варианта – стандартного. Стандартный ГА – метод стохастической оптимизации для задач дискретной оптимизации вида.
Здесь – функция пригодности (fitness function); – -мерный двоичный вектор из дискретного множества – хромосома (chromosome) или двоичная нить (string) длины . Множество – множество вершин - мерного гиперкуба с единичным ребром; – множество действительных чисел. Главное отличие стандартного ГА от традиционных методов оптимизации – на каждом шаге ГА имеет дело сразу с несколькими значениями вектора параметров , которые образуют популяцию (population) хромосом. В начале процедуры поиска создается начальная популяция, например, из двоичных хромосом: = , каждая из которых содержит битов. Такая популяция создается либо случайным образом, либо с учетом априорной информации об области нахождения оптимума в множестве . Под двоичным вектором-хромосомой понимается двоичное кодирование исходного варьируемого параметра , физический смысл которого определяется задачей. Длина хромосомы (число битов) при таком кодировании зависит от требуемой точности нахождения оптимума параметра и должна удовлетворять условию , где , – предельные значения параметра ; – заданная погрешность определения его оптимального значения. Число членов в популяции влияет на широту фронта поиска и задается эмпирически. Вычисление последующих популяций , и т.д. на базе осуществляется путем применения трех генетических операторов: отбора (selection), кроссинговера (crossingover) и мутации (mutation). Отбор в стандартном ГА реализуется методом «колеса рулетки», при котором хромосомы-кандидаты из -го поколения выбираются для выживания в следующем, -м поколении путем использования колеса рулетки. Каждая хромосома в популяции представлена на колесе в виде сектора с шириной, пропорциональной функции пригодности . Для отбора хромосом колесо рулетки вращают раз. В результате по завершении каждого вращения выделяется одна из хромосом , которые принимаются в качестве кандидатов в следующем поколении. Перед их копированием в новую популяцию они должны подвергнуться кроссинговеру и мутации. Оператор кроссинговера (скрещивания) применяется к паре хромосом из (пусть -четное), прошедших отбор. – назначаемая вероятность выполнения кроссинговера. Далее для случайно выбранной пары хромосом определяется случайное число (место или сайт кроссинговера), и затем биты из двух выбранных хромосом меняются местами после -го бита с вероятностью . Процесс повторяется до момента, когда популяция не окажется пустой. Оператор мутации состоит в случайном изменении (на противоположное) значения каждого бита гена с вероятностью . Самым легким способом определения изменяемых бит (если это необходимо) – выбор независимого случайного числа для каждого бита хромосомы. Если , то -й бит следует изменить, в противном случае он сохраняется. После мутации хромосомы-кандидаты копируются в новую популяцию хромосом и весь процесс повторяется с вычислением функции пригодности для каждой хромосомы и применением операторов отбора, кроссинговера и мутации (рис. 5.8.) [4]. Отбор методом «колеса рулетки» позволяет претендовать на выживание хромосомам с пригодностью выше среднего. Детерминированный подход по принципу выбора хромосом с наибольшей пригодностью не применяется в соответствии с допущениями генетического поиска, согласно которым даже хромосомы с низкой пригодностью могут содержать полезную информацию. Наиболее критическим из перечисленных трех является оператор кроссинговера, так как он отвечает за смешивание информации хромосом поколение популяции, а от этого зависит глобальность получаемых результатов. Установлено эмпирически, что . Операторы отбора и кроссинговера используются для улучшения структуры хромосом. Цель оператора мутации – диверсификация, т.е. повышение разнообразия поиска и введение новых хромосом в популяцию для большей полноты исследования пространства поиска. Мутация инициирует разнообразие в популяции, позволяя просматривать больше точек в пространстве поиска и преодолевать локальные эксперименты в ходе поиска. Частое применение мутации приводит к разрушению хромосом с высокой приспособленностью в популяции, что сказывается на сходимости решения. Поэтому применение мутации обычно осуществляется с малой вероятностью: . В последнее время область применения ГА значительно расширилась. Данные методы оказываются эффективными при решении следующих задач: · идентификация сложных динамических объектов; · выбор оптимальной конфигурации многоагентных робототехнических систем; · синтез оптимальных алгоритмов управления многозвенными роботами-манипуляторами; · оптимальное управление стыковкой космических аппаратов; · планирование маршрутов движения транспортных средств в условиях препятствий; · структурный синтез проектных решений, синтез расписаний и многих других. Таким образом, применение ГА охватывает не только класс традиционных задач оптимизации, но и быстро распространяется на задачи управления сложными динамическими объектами в условиях неопределенности. Нельзя не отметить, что область применения ГА существенно расширилась. Одним из таких расширений является генетическое программирование (ГП), под которым понимается применение генетической модели обучения в пространстве программ. В этом случае в качестве индивидуумов, составляющих популяцию, выступают уже не указанные выше достаточно простые линейные структуры – хромосомы, а компьютерные программы, которые, будучи исполненными, представляют собой кандидатов на решение поставленной задачи.
Вопросы для самопроверки 1. Нейронные сети: их место в моделировании технологических систем 2. Роль и место генетических алгоритмов в математическом моделировании технологических систем. 3. Какую математическую формулировку имеют задачи оптимизации при использовании генетических алгоритмов? 4. В чем заключается суть стандартного генетического алгоритма для задач дискретной оптимизации? 5. В чем заключается главное отличие генетического алгоритма от традиционных методов оптимизации? 6. Что такое двоичный вектор-хромосома? 7. В чем заключается отбор методом «колеса рулетки»? 8. Дайте определение операторов «кроссинговер» и «мутация». 9. Для каких задач методы оптимизации с использованием генетических алгоритмов являются наиболее эффективными?
Рекомендуемая литература
1. Аверченков, В.И. Основы математического моделирования технических систем: учеб. пособие / В.И. Аверченков, В.П. Федоров., М.Л. Хейфец – Брянск: Изд-во БГТУ, 2004. Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.012 сек.) |