Введение в ГА и Генетическое Программирование

Путь: АИ, ГА, Нейронные сети » Генетические алгоритмы » Введение

Введение в ГА и Генетическое Программирование

	Перевод Кантор И.А. e-mail: algolist@mail.ru web: iliakan@gmail.com Генетические алгоритмы представляют собой новое направление в алгоритмике. Они способны не только решать и сокращать перебор в сложных задачах, но и легко адаптироваться к изменению проблемы. Вначале ГА-функция генерирует определенное количество возможных решений, а затем вычисляет для каждого 'уровень выживаемости' (fitness) - близость к истине. Эти решения дают потомство. Те что 'сильнее', то есть больше подходят, имеет больший шанс к воспроизводству, а 'слабые' постепенно отмирают. Идет эволюция. Процесс повторяется до тех пор, пока не найдено решение, или не получено достаточное к нему приближение. Правильно запрограммированные генетические алгоритмы могут быть просто суперэффективны.
Схема генетического алгоритма.

	Генерация случайного начального состояния. Первое поколение создается из произвольно выбранных решений (хромосом). Это отличается от стандартных методов, когда начальное состояние всегда одно и то же. Вычисление коэффициента выживаемости (fitness). Каждому решению (хромосоме) сопоставляется некое численное значение, зависящее от его близости к ответу. Воспроизводство. Хромосомы, имеющие большую выживамость (fitness), попадают к потомкам (которые затем могут мутировать) с большей вероятностью. Потомок, результат слияния 'отца' и 'матери', является комбинацей их ген. Этот процесс называется 'кроссиннговер' (crossing over). Cледующее поколение. Если новое поколение содержит решение, достаточно близкое к ответу, то задача решена. В противоположном случае оно проходит через тот же процесс. Это продолжается до достижения решения. Пример ГА: Решение Диофантова Уравнения.

Пример ГА: Решение Диофантова Уравнения.