Генетические алгоритмы (ГА)

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

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

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

Количество методов скрещивания достаточно велико, от полностью случайного до турнирного. Чисто случайное спаривание осуществляется среди наиболее приспособленных хромосом, взвешенно–случайные методы используют информацию о текущем значении , например, при отборе по принципу рулетки вероятность скрещивания конкретной хромосомы пропорциональна величине ее функции приспособленности . Процесс скрещивания основан на рассечении пары хромосом на 2 части с последующим обменом этих частей в хромосомах родителей (рис. 3.2). Место рассечения выбирается случайным образом, количество новых потомков равно количеству отбракованных в результате селекции, допускается перенос в очередное поколение некоторых хромосом (из числа хорошо приспособленных) вообще без скрещивания.

Последняя генетическая операция – мутация – обеспечивает защиту от слишком быстрого завершения алгоритма в точке, далекой от глобального экстремума. При двоичном кодировании мутация состоит в инверсии случайно выбранных битов, при использовании десятичных цифр – в замене некоторых компонентов случайно выбранными значениями. Необходимо помнить, что случайные мутации приводят к повреждению уже частично приспособленных векторов, поэтому обычно мутации подвергается не более (1…5)% элементов всей популяции хромосом.

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