Параметры ГА. Генетический алгоритм плоской укладки

Данное множество циклов передается в основной блок алгоритма — блок генетических операторов (БГО), где выполняется исследование и генерация решения.

Методика кодирования и оценка качества

Эффективность работы генетических алгоритмов обратной связи во многом зависит от способа кодирования данных. С учетом специфики решаемой задачи была предложена специальная хромосома, с числом разрядов равным p + 3. Первые p разрядов хромосомы представляют собой номера циклов задействованных в текущем решении. Дополнительные три разряда используются для оценки качества получаемого решения. Разряд № p + 1 содержит информацию о ребрах не задействованных в данном решении, разряд p + 2 — ребра, задействованные один раз и разряд p + 3 — ребра, использованные дважды. Для оценки качества полученного решения вводится функция (m):

(m) = (2Nmp+3 + Nmp+2) / 2m, (1).

где Nmp+3 — число элементов в p + 3 — разряде хромосомы, Nmp+2 — соответственно число элементов в p + 2 — разряде хромосомы, а m — число ребер в исследуемом графе.

Как видно из формулы, значения которые может принимать функция оценки (m) находятся в интервале [0; 1], причем качество решения тем выше, чем больше число ребер, задействованных в оцениваемом решении (прежде всего встречающихся дважды).

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

Таким образом, целевая функция хромосомы полученного решения (H) является аддитивной функцией двух переменных:

(H) = ((m); L0) (2).

Причем (H) max, когда (m) 2m L0 0.