Описание генетического алгоритмам

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

Отличия ИНС от машин с архитектурой фон Неймана

Вычислительные системы, основанные на искусственных нейронных сетях, обладают рядом качеств, которые отсутствуют в машинах с архитектурой фон Неймана (но присущи мозгу человека):

· Массовый параллелизм;

· Распределённое представление информации и вычисления;

· Способность к обучению и обобщению;

· Адаптивность;

· Свойство контекстуальной обработки информации;

· Толерантность к ошибкам;

· Низкое энергопотребление.

57. Какая теорема лежит в основе генетических алгоритмов, и что она доказывает? [вверх]

«Отцом-основателем» генетических алгоритмов считается Джон Холланд, книга которого «Адаптация в естественных и искусственных системах» (1975) является основополагающим трудом в этой области исследований. Ему же принадлежит доказательство теоремы схем (Теорема схем, или теорема шаблонов — основная теорема теории генетических алгоритмов, дающая обоснование их эффективности.)

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

J (x)→ min (max), где вектор x = (x ₁, x ₂, …, x_m)

Генетический алгоритм (англ. genetic algorithm) — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию.

Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.

Задача формализуется таким образом, чтобы её решение могло быть закодировано в виде вектора («генотипа») генов. Где каждый ген может быть битом, числом или неким другим объектом. В классических реализациях ГА предполагается, что генотип имеет фиксированную длину. Однако существуют вариации ГА, свободные от этого ограничения.

Некоторым, обычно случайным, образом создаётся множество генотипов начальной популяции. Они оцениваются с использованием «функции приспособленности», в результате чего с каждым генотипом ассоциируется определённое значение («приспособленность»), которое определяет насколько хорошо фенотип им описываемый решает поставленную задачу.

Из полученного множества решений («поколения») с учётом значения «приспособленности» выбираются решения (обычно лучшие особи имеют большую вероятность быть выбранными), к которым применяются «генетические операторы» (в большинстве случаев «скрещивание» — crossover и «мутация» — mutation), результатом чего является получение новых решений. Для них также вычисляется значение приспособленности, и затем производится отбор («селекция») лучших решений в следующее поколение.

58. Дайте определение понятию «эволюционные алгоритмы». [вверх]

Дата добавления: 2015-04-23