Генетический алгоритм. 
Основные понятия

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

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

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

Цель генетических алгоритмов состоит в том, чтобы:

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

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

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

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

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

Популяция есть множество элементов. Каждый элемент этой популяции, как правило, представляет собой одну или несколько хромосом или особей.

Хромосома — некоторый конечный вектор размерности, состоящий из генов — элементов хромосом .

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

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

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

Поколение — генерация, или процесс реализация одной итерации алгоритма.

Генотип (набор хромосом) каждой особи популяции описывает фенотип — его внешнее проявление. Фенотип каждого элемента оценивается при помощи «функции приспособленности», (fitness function). Эта функция используется для сравнения альтернативных решений между собой и выбора лучших. Отсюда следует, что основная задача генетических алгоритмов состоит в оптимизации целевой функции .

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