Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



Генетический алгоритм




Читайте также:
  1. Алгоритм RSA
  2. Алгоритм виконання часткового технологічного процесу
  3. Алгоритм выборки сообщений из очереди потока
  4. Алгоритм выполнения манипуляции
  5. Алгоритм выполнения манипуляции
  6. Алгоритм выполнения манипуляции
  7. Алгоритм вычисления выражений в обратной польской записи
  8. Алгоритм Дейкстры
  9. Алгоритм загрузки операционной системы
  10. Алгоритм Замельсона и Бауэра перевода выражений в ПОЛИЗ

Идея генетических алгоритмов предложена Джоном Холландом в 60-х годах, а результаты первых исследований обобщены в его монографии «Адаптация в природных и искусственных системах» [24], а также в диссертации его аспиранта Кеннета Де Йонга [32].

Как уже говорилось выше, ГА используют для работы эволюционные принципы наследственности, изменчивости и естественного отбора. Общая схема ГА представлена на рис. 5.1 [34].

 

 

Рис. 5.1. Общая схема генетического алгоритма

 

Генетический алгоритм работает с популяцией особей, в хромосоме (генотип) каждой из которых закодировано возможное решение задачи (фенотип). В начале работы алгоритма популяция формируется случайным образом (блок «Формирование начальной популяции» на рис. 5.1). Для того чтобы оценить качество закодированных решений используют функцию приспособленности, которая необходима для вычисления приспособленности каждой особи (блок «Оценивание популяции»). По результатам оценивания особей наиболее приспособленные из них выбираются (блок «Селекция») для скрещивания. В результате скрещивания выбранных особей посредством применения генетического оператора кроссинговера создается потомство, генетическая информация которого формируется в результате обмена хромосомной информацией между родительскими особями (блок «Скрещивание»). Созданные потомки формируют новую популяцию, причем часть потомков мутирует (используется генетический оператор мутации), что выражается в случайном изменении их генотипов (блок «Мутация»). Этап, включающий последовательность «Оценивание популяции» – «Селекция» – «Скрещивание» – «Мутация», называется поколением. Эволюция популяции состоит из последовательности таких поколений.

Длительность эволюции может определяться следующими факторами:

- нахождение решения в результате эволюционного поиска;

- ограниченность количества поколений;

- ограниченность количества вычислений функции приспособленности (целевой функции);

- вырождение популяции, когда степень разнородности хромосом в популяции становится меньше допустимого значения.


Дата добавления: 2014-12-23; просмотров: 12; Нарушение авторских прав







lektsii.com - Лекции.Ком - 2014-2021 год. (0.012 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты