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

Описание основных операторов ГА

КРАТКАЯ СПРАВКА

Решение оптимизационных задач с помощью генетических алгоритмов

Появление генетических алгоритмов (ГА) можно отнести к концу шестидесятых – началу семидесятых годов, когда они были впервые описаны в работе Дж. Холланда "Адаптация в природе и искусственных системах". Их общий смысл сводится к моделированию процесса эволюции. Как и в природе, задача алгоритма - отбор наиболее пригодных особей для дальнейшего участия в процессе воспроизводства и, таким образом, нахождение наиболее пригодного индивидуума-решения. Методы ГА эффективны при решении задач оптимизации, задач управления сложными динамическими объектами в условиях неопределенности.

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

J (x) ® min (max),

у которой вектор x = (x ₁, x ₂, …, x_m) имеет достаточно большую размерность.

Приведем некоторые понятия и определения из теории ГА. Все ГА работают на основе начальной информации, в качестве которой выступает популяция p = { p (0), p (1),…, p (n)} – множество элементов p (i), , именуемых особями или хромосомами. В задаче минимизации (4.26) особь p (i) – это вектор x ⁱ , т.е. p (i) = x ⁱ.

Особи состоят из генов x. Обычно размер популяции n не превышает 5. Каждый ген характеризуется величиной и позицией в особи. Геном x может быть двоичное (0,1) или вещественное число. Двоичный ген меняет свое значение с 1 на 0, и наоборот. Вещественный ген может быть подвергнут случайному изменению – мутированию в соответствии с формулой

, (1)

где – верхний и нижний пределы числа x; a – случайное число, изменяющееся в пределах [0,1].

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

Рассмотрим основные принципы работы ГА, предназначенного для минимизации многомерной целевой функции J (p) и состоящего из операторов: создания исходной популяции, отбора, скрещивания, мутации и редукции.

Исходная популяция формируется из нулевой особи, содержащей m начальных значений переменных, именуемых генами

p (0)

С помощью операции (1) определяется количество генов h = Ran (1, m), подлежащих мутации, т.е. h раз вычисляется номер k = Ran (1, m) мутируемого гена

.

Таким образом формируется первая особь исходной популяции (например, для h = 3, k = 2, 10, 15)

p (1)

Аналогичным путем определяется количество h номеров генов k и проводится их мутация для получения второй p (2) и третьей p (3) особей исходной популяции p (j) j = 1, 2, 3.

Оператор отбора вычисляет соответствующие критерии J (p (j)), j = 1,2,3, и выбирает два критерия (например, J (p (1)) и J (p (3)) с минимальными значениями и соответственно две особи p (1) и p (3), именуемые родителями.

Оператор скрещивания передает потомкам свойства родителей.

Вначале определяется целое число m = Ran (1, m) – точка разбиения строки на две подстроки, а затем строки обмениваются элементами подстрок, находящимися после разбиения, т.е. начиная с m + 1 и до m- го элемента. Таким образом образуются две новые особи (строки) или два потомка, наследующие свойства родителей

Родители Потомки

Дата добавления: 2015-04-25