Нейрокомпьютерные системы



              

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


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

w
, содержащие оптимизированные переменные:
w = [w_1,w_2, \ldots, w_n]^T
. При этом выполняются операции трех видов: селекция, скрещивание и мутация.

На начальной стадии выполнения генетического алгоритма случайным образом инициализируется определенная популяция хромосом (векторов

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

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

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

F(w) = - E(w)
, где
E(w)

- ее целевая функция.

Процесс скрещивания основан на рассечении пары хромосом на две части с последующим обменом этих частей в хромосомах родителей (рис. 1). Место рассечения также выбирается случайным образом. Количество новых потомков равно количеству отбракованных в результате селекции (размер популяции остается неизменным). Признается допустимым перенос в очередное поколение некоторых случайно выбранных хромосом вообще без скрещивания.

Процесс скрещивания

Рис. 1.  Процесс скрещивания

Последняя генетическая операция - это мутация. При двоичном кодировании мутация состоит в инверсии случайно выбранных битов.


Содержание  Назад  Вперед