рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Работа генетического алгоритма

Работа генетического алгоритма - раздел Компьютеры, Искусственный интеллект Представим Себе Искусственный Мир, Населенный Множеством Существ (Особей...


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

Рис. 2. Блок-схема генетического алгоритма

, то полученный мир будет подчиняться законам эволюции. Заметим, что, в соответствии с нашим определением приспособленности, целью этой искусственной эволюции будет как раз создание наилучших решений. Очевидно, эволюция — бесконечный процесс, в ходе которого приспособленность особей постепенно повышается. Принудительно остановив этот процесс через достаточно долгое время после его начала и выбрав наиболее приспособленную особь в текущем поколении, мы получим не абсолютно точный, но близкий к оптимальному ответ. Такова, вкратце, идея генетического алгоритма. Перейдем теперь к точным определениям и опишем работу генетического алгоритма более детально.
Для того чтобы говорить о генетическом наследовании, нужно снабдить наши существа хромосомами. В генетическом алгоритме хромосома — это некоторый числовой вектор, соответствующий подбираемому параметру, а набор хромосом данной особи определяет решение задачи. Какие именно векторы следует рассматривать в конкретной задаче, решает сам пользователь. Каждая из позиций вектора хромосомы называется ген.
Определим теперь понятия, соответствующие мутации и кроссинговеру в генетическом алгоритме.
Мутация — это преобразование хромосомы, случайно изменяющее одну или несколько ее позиций (генов). Наиболее распространенный вид мутаций — случайное изменение только одного из генов хромосомы.
Кроссинговер (в литературе по генетическим алгоритмам также употребляется название кроссовер или скрещивание) — это операция, при которой из двух хромосом порождается одна или несколько новых хромосом. В простейшем случае кроссинговер в генетическом алгоритме реализуется так же, как и в биологии (см. рис. 1). При этом хромосомы разрезаются в случайной точке и обмениваются частями между собой. Например, если хромосомы (1, 2, 3, 4, 5) и (0, 0, 0, 0, 0) разрезать между третьим и четвертым генами и обменять их части, то получатся потомки (1, 2, 3, 0, 0) и (0, 0, 0, 4, 5).
Блок-схема генетического алгоритма изображена на рис. 2. Вначале генерируется начальная популяция особей (индивидуумов), т. е. некоторый набор решений задачи. Как правило, это делается случайным образом. Затем мы должны смоделировать размножение внутри этой популяции. Для этого случайно отбираются несколько пар индивидуумов, производится скрещивание между хромосомами в каждой паре, а полученные новые хромосомы помещаются в популяцию нового поколения. В генетическом алгоритме сохраняется основной принцип естественного отбора — чем приспособленнее индивидуум (чем больше соответствующее ему значение целевой функции), тем с большей вероятностью он будет участвовать в скрещивании. Теперь моделируются мутации — в нескольких случайно выбранных особях нового поколения изменяются некоторые гены. Затем старая популяция частично или полностью уничтожается и мы переходим к рассмотрению следующего поколения. Популяция следующего поколения в большинстве реализаций генетических алгоритмов содержит столько же особей, сколько начальная, но в силу отбора приспособленность в ней в среднем выше. Теперь описанные процессы отбора, скрещивания и мутации повторяются уже для этой популяции и т. д.
В каждом следующем поколении мы будем наблюдать возникновение совершенно новых решений нашей задачи. Среди них будут как плохие, так и хорошие, но благодаря отбору число хороших решений будет возрастать. Заметим, что в природе не бывает абсолютных гарантий, и даже самый приспособленный тигр может погибнуть от ружейного выстрела, не оставив потомства. Имитируя эволюцию на компьютере, мы можем избегать подобных нежелательных событий и всегда сохранять жизнь лучшему из индивидуумов текущего поколения — такая методика называется “стратегией элитизма”.

– Конец работы –

Эта тема принадлежит разделу:

Искусственный интеллект

На сайте allrefs.net читайте: "Цель преподавания дисциплины искусственный интеллект"

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Работа генетического алгоритма

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

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

Терминология
Термин интеллект (intelligence) происходит от латинского intellectus — что означает ум, рассудок, разум; мыслительные способности человека. Соответственно искусственный интеллект (artificial intell

Философские аспекты проблемы систем ИИ (возможность существования, безопасность, полезность).
С курсом "Основы проектирования систем ИИ" сложилась ситуация, которая роднит его с коммунизмом — изучается то, чего еще нет. И если этого не будет в течение ближайших 100 лет, то очень м

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

Искусственный нейрон
Искусственный нейрон имитирует в первом приближении свойства биологического нейрона. На вход искусственного нейрона поступает некоторое множество сигналов, каждый из которых является выходом другог

Активационные функции
Сигнал NET далее, как правило, преобразуется активационной функцией F и дает выходной нейронный сигнал OUT. Активационная функция может быть обычной линейной функцией OUT =K(

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

Неформальные (семантические) модели представления знаний.
1. Сетевые модели (Семантические сети). В основе моделей этого типа лежит конструкция, названная семантической сетью. Сетевые модели формально можно задать в виде H

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

Подготовительный этап
1. Четкое определение задач проектируемой системы (сужение поля знаний): определение, что на входе и выходе; определение режима работ, консультации, обучение и др. 2. Выбор экспертов: опре

Основной этап
1. "Накачка" поля знаний: а) в зависимости от предметной области выбор способа интервьюирования; б) протоколирование мыслей вслух или запись на магнитофон рассуждении эксперта (аналитик п

Способы формализации задач. Представление задач в пространстве состояний
Типичным представителем класса задач, для которых подходит представление (формализация) в пространстве состояний, является головоломка, известная как игра в пятнадцать. В ней используется пятнадцат

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

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

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

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

Альфа-бета процедура
Минимаксная процедура организована таким образом, что процесс построения частичного дерева игры отделен от процесса оценивания вершин. Такое разделение приводит к тому, что в целом минимаксная проц

Тимофей Струнков
В этой статье мы продолжим тему имитации биологических процессов и познакомим

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

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

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

Применение генетических алгоритмов
Чтобы использовать генетический алгоритм для решения практических задач, необходимо рассматривать более сложные варианты введенных выше понятий. Поясним это на примере задачи коммивояжера для

Понятие образа
Образ, класс — классификационная группировка в системе классификации, объединяющая (выделяющая) определенную группу объектов по некоторому признаку. Образное восприятие мира — одно из зага

Геометрический и структурный подходы.
Каждый раз, когда сталкиваются с незнакомыми задачами, появляется естественное желание представить их в виде некоторой легко понимаемой модели, которая позволяла бы осмыслить задачу в таких термина

Гипотеза компактности
Если предположить, что в процессе обучения пространство признаков формируется исходя из задуманной классификации, то тогда можно надеяться, что задание пространства признаков само по себе задает св

Обучение и самообучение. Адаптация и обучение
Все картинки, представленные на Рис. 1, характеризуют задачу обучения. В каждой из этих задач задается несколько примеров (обучающая последовательность) правильно решенных задач. Если бы удалось по

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги