Gen algoritm Shilova

Генетические алгоритмы. Поиск экстремума функции

Наталья Шилова,

кандидат физико-математических наук, заведующая кафедрой прикладной математики

[e-mail]

Основные понятия

Экстремум (лат. extremum — крайний) в

математике - максимальное или минимальное

значение функции на заданном множестве. Точка, в которой достигается экстремум, называется точкой экстремума. Соответственно, если достигается минимум — точка экстремума называется точкой минимума, а если максимум — точкой

максимума.

Разделяют два понятия – глобальный и

условный экстремум.

Необходимое условие экстремума Иллюстрация

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

х0 – экстремум, когда или F‘(х0) = 0,

или F‘(х0) = 0 – не существует.

Примеры

• Элементарная	• Функция сложной
функция	конструкции
y(x) = x4-2x2+5

Формальное определение

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

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

В основе генетических алгоритмов лежат генетика и хромосомная теория эволюции организмов.

«Теория» классической генетики

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

•Все признаки организма определяются наборами генов;

•Гены - это элементарные единицы наследственной информации, которые находятся в хромосомах;

•Гены могут изменяться – мутировать;

•Мутации отдельных генов приводят к изменению отдельных элементарных признаков организма, или фенов.

Суть генетического алгоритма

Генетический алгоритм – это поисковый алгоритм,

основанный на природных механизмах селекции и генетики

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

Другими словами, генетические алгоритмы используют информацию, накопленную в процессе эволюции.

Зачем нужны генетические алгоритмы?

Генетические алгоритмы применяются для решения следующих задач:

1.Оптимизация функции (поиск экстремума).

2.Задачи на графах (задача коммивояжера).

3.Настройка и обучение искусственной нейронной сети.

4.Составление расписания.

5.Игровые стратегии.

6.Биоинформатика и др.

Ключевые работы

Принцип работы генетического алгоритма