Информационных технологий и программирования




Скачать 282.5 Kb.
НазваниеИнформационных технологий и программирования
страница4/6
Дата публикации23.06.2013
Размер282.5 Kb.
ТипПояснительная записка
lit-yaz.ru > Информатика > Пояснительная записка
1   2   3   4   5   6
^

Глава 2. Применение генетического программирования для построения управляющих автоматов

2.1. Эволюционные вычисления


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

История эволюционных вычислений началась с разработки ряда различных независимых моделей. Основными из них были генетические алгоритмы и классификационные системы Холланда, опубликованные в начале 60-х годов, эволюционные стратегии Рехенберга и эволюционное программирование, предложенное группой ученых (Фогель, Оуэнс и Уолш).

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

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

Таким образом, эволюция – это процесс постоянной оптимизации приспособленности популяции. Естественный отбор здесь гарантирует, что наиболее приспособленные особи дадут достаточно большое потомство, а благодаря генетическому наследованию, который включает в себя возможность мутации, часть этого потомства не только сохранит высокую приспособленность родителей, но будет обладать и некоторыми новыми свойствами.
^

2.1.1. Эволюционные алгоритмы


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

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

Схема работы эволюционного алгоритма представлена на рис. 5. Первый шаг – это генерация начальной популяции особей, т.е. некоторого набора решений задачи. Обычно это происходит случайным образом. Затем начинается моделирование эволюционного процесса, который можно разделить на три основных этапа:

  • селекция особей, имеющих наибольшее значение функции приспособленности;

  • применение операции кроссовера к отобраным индивидам;

  • мутации некоторых особей популяции.

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

  • нахождение глобального, либо локального решения задачи;

  • исчерпание числа поколений, отпущенных на эволюцию;

  • исчерпание времени, отпущенного на эволюцию.

Создание начальной популяции

Отбор

Размножение

Мутации

к новому поколению

критерий остановки

Ответ


Рис. . Принципиальная схема работы эволюционного алгоритма




^

2.1.2. Генетические алгоритмы


В 1975 г. вышла основополагающая книга Дж.Холланда «Адаптация в естественных и искусственных системах», в которой был предложен генетический алгоритм, исследованный в дальнейшем учениками и коллегами Дж.Холланда в Мичиганском университете. В этой работе ученый впервые ввел термин «генетический алгоритм» и предложил схему классического генетического алгоритма (canonical GA).

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

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

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

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

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

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

Итоговым решением задачи может служить наиболее приспособленная особь последнего поколения.
1   2   3   4   5   6

Похожие:

Информационных технологий и программирования iconКафедра информационных технологий Краткая инструкция
На экзамены выносятся три вопроса по разным базовым областям специальности: основы информационных технологий (теория систем, дискретная...

Информационных технологий и программирования iconИнформационных технологий и программирования
Применение генетических алгоритмов для построения управляющих автоматов 14

Информационных технологий и программирования iconИнформационных технологий и программирования
Класс StatusEvent 11 Глава Применение генетических алгоритмов для построения управляющих автоматов 12

Информационных технологий и программирования iconКонтрольная работа не является рефератом или распечаткой материалов...
Интернет и использованию информационных технологий для поиска и обработки информации

Информационных технологий и программирования iconУчебная программа курса или дисциплины «Основы программирования»
В частности, в курсе рассматриваются основные конструкции языков программирования, анализируются основные типы и структуры данных,...

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

Информационных технологий и программирования iconТема : «Достижение устойчивых изменений в работе школы по применению...
Необходим качественно усовершенствованный и активный переход на новый уровень в использовании компьютерной техники и информационных...

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

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

Информационных технологий и программирования iconВэй Чуньлэй Применение информационных технологий в исследованиях...
Применение информационных технологий в исследованиях по Исследованию состава биологически активных соединений кемпферии галанга и...



Образовательный материал



При копировании материала укажите ссылку © 2013
контакты
lit-yaz.ru
главная страница