Дисциплина «Искусственный интеллект»
Рабочая тетрадь № 6 Теоретический материал – Эволюционные методы
Задание:
Выполните по вариантам (1) соответственно реализацию генетического алгоритма в соответствии с приложенными начальными данными.
Начальные данные:
На изображении представлен граф, который, вероятно, иллюстрирует процесс скрещивания (кроссинговера) в генетическом алгоритме. Также даны значения для переменных \(x\) и \(y\), и целевая функция \(Z\).
1. Таблица значений \(x\) и \(y\):
| \(x\) | -2 | -1 | 0 | 1 |
| \(y\) | -2 | -1 | 0 | 1 |
2. Целевая функция \(Z\):
\[Z = \frac{x - 3y + 1}{3x^2 + 3y^2 + 1}\]3. Граф скрещивания:
Граф показывает, как из родительских особей (I. a, b, c) формируются потомки (II. b1, c1, b2, c2). Каждая особь представлена двумя квадратами разного цвета, что может символизировать два гена или две хромосомы. Процесс скрещивания, судя по стрелкам, происходит следующим образом:
- Особь 'a' (красный и зеленый квадраты) и особь 'b' (синий и белый квадраты) скрещиваются, образуя потомков 'b1' (синий и красный квадраты) и 'c1' (желтый и красный квадраты).
- Особь 'b' (синий и белый квадраты) и особь 'c' (желтый и бирюзовый квадраты) скрещиваются, образуя потомков 'b2' (зеленый и белый квадраты) и 'c2' (бирюзовый и белый квадраты).
Цвета квадратов, вероятно, кодируют какие-то параметры или значения, которые передаются от родителей к потомкам. Для полной реализации генетического алгоритма нам нужно:
- Определить кодировку хромосом: Что именно представляют собой цвета квадратов? Это могут быть значения \(x\) и \(y\), или какие-то другие параметры.
- Определить функцию приспособленности (фитнес-функцию): В данном случае это функция \(Z\). Цель генетического алгоритма обычно состоит в поиске таких значений \(x\) и \(y\), которые максимизируют или минимизируют \(Z\).
- Определить операторы генетического алгоритма:
- Селекция: Как выбираются родители для скрещивания? (На графе уже показаны пары).
- Кроссинговер (скрещивание): Как происходит обмен генетическим материалом? (Граф иллюстрирует этот процесс).
- Мутация: Изменяются ли гены случайным образом? (На графе не показано, но это стандартный оператор).
- Определить критерий останова: Когда алгоритм должен остановиться?
Предположения для реализации (Вариант 1):
Поскольку конкретные значения для цветов не указаны, и даны только таблицы для \(x\) и \(y\), а также функция \(Z\), можно предположить, что:
- Каждая особь (например, 'a', 'b', 'c') представляет собой пару значений \((x, y)\).
- Цвета квадратов могут быть визуальным представлением этих значений или их комбинаций.
- Задача состоит в том, чтобы, используя данные \(x\) и \(y\) из таблицы, вычислить значение \(Z\) для каждой особи и, возможно, найти наилучшую особь.
Шаги реализации генетического алгоритма (на основе предоставленных данных):
Шаг 1: Инициализация популяции.
Предположим, что начальная популяция состоит из особей 'a', 'b', 'c'. Каждая особь кодируется парой \((x, y)\). Поскольку конкретные значения для 'a', 'b', 'c' не даны, но есть таблица возможных значений для \(x\) и \(y\), мы можем выбрать их из этой таблицы. Например, пусть:
- Особь 'a': \((x_a, y_a)\)
- Особь 'b': \((x_b, y_b)\)
- Особь 'c': \((x_c, y_c)\)
Для простоты, давайте возьмем первые три пары из таблицы:
- Особь 'a': \((x=-2, y=-2)\)
- Особь 'b': \((x=-1, y=-1)\)
- Особь 'c': \((x=0, y=0)\)
Шаг 2: Вычисление приспособленности (фитнес-функции) для каждой особи.
Используем формулу \[Z = \frac{x - 3y + 1}{3x^2 + 3y^2 + 1}\]
Для особи 'a' \((x=-2, y=-2)\):
\[Z_a = \frac{(-2) - 3(-2) + 1}{3(-2)^2 + 3(-2)^2 + 1} = \frac{-2 + 6 + 1}{3(4) + 3(4) + 1} = \frac{5}{12 + 12 + 1} = \frac{5}{25} = 0.2\]Для особи 'b' \((x=-1, y=-1)\):
\[Z_b = \frac{(-1) - 3(-1) + 1}{3(-1)^2 + 3(-1)^2 + 1} = \frac{-1 + 3 + 1}{3(1) + 3(1) + 1} = \frac{3}{3 + 3 + 1} = \frac{3}{7} \approx 0.4286\]Для особи 'c' \((x=0, y=0)\):
\[Z_c = \frac{0 - 3(0) + 1}{3(0)^2 + 3(0)^2 + 1} = \frac{1}{0 + 0 + 1} = \frac{1}{1} = 1\]Шаг 3: Селекция и кроссинговер.
Граф показывает, как происходит скрещивание. Предположим, что "гены" (цвета) обмениваются. Если мы интерпретируем цвета как компоненты \((x, y)\), то кроссинговер может быть одноточечным или двухточечным. Без явного указания, как именно цвета кодируют \(x\) и \(y\), мы можем предположить, что происходит обмен значениями \(x\) или \(y\).
Давайте предположим, что верхний квадрат кодирует \(x\), а нижний квадрат кодирует \(y\). И цвета символизируют конкретные значения из таблицы.
Например, пусть:
- Красный = -2
- Синий = -1
- Желтый = 0
- Зеленый = 1
- Белый = -1 (или другое значение, если это не дублирует синий)
- Бирюзовый = 1 (или другое значение, если это не дублирует зеленый)
Это лишь предположение, так как на изображении нет явной легенды цветов. Если бы цвета кодировали значения из таблицы, то:
- Особь 'a': (Красный, Зеленый) = \((-2, 1)\)
- Особь 'b': (Синий, Белый) = \((-1, -1)\) (если белый = -1)
- Особь 'c': (Желтый, Бирюзовый) = \((0, 1)\) (если бирюзовый = 1)
Давайте пересчитаем \(Z\) с этими предположениями:
Для особи 'a' \((x=-2, y=1)\):
\[Z_a = \frac{(-2) - 3(1) + 1}{3(-2)^2 + 3(1)^2 + 1} = \frac{-2 - 3 + 1}{3(4) + 3(1) + 1} = \frac{-4}{12 + 3 + 1} = \frac{-4}{16} = -0.25\]Для особи 'b' \((x=-1, y=-1)\):
\[Z_b = \frac{(-1) - 3(-1) + 1}{3(-1)^2 + 3(-1)^2 + 1} = \frac{-1 + 3 + 1}{3(1) + 3(1) + 1} = \frac{3}{3 + 3 + 1} = \frac{3}{7} \approx 0.4286\]Для особи 'c' \((x=0, y=1)\):
\[Z_c = \frac{0 - 3(1) + 1}{3(0)^2 + 3(1)^2 + 1} = \frac{-3 + 1}{0 + 3 + 1} = \frac{-2}{4} = -0.5\]Теперь рассмотрим кроссинговер по графу:
Скрещивание 'a' и 'b':
- Особь 'a': \((x_a, y_a)\) = \((-2, 1)\)
- Особь 'b': \((x_b, y_b)\) = \((-1, -1)\)
Потомки 'b1' и 'c1'. Граф показывает, что 'b1' получает синий верхний квадрат (от 'b') и красный нижний квадрат (от 'a'). 'c1' получает желтый верхний квадрат (от 'b'?) и красный нижний квадрат (от 'a'?). Здесь есть небольшая нестыковка, так как у 'b' нет желтого квадрата. Возможно, желтый квадрат у 'c1' - это результат мутации или другого типа кроссинговера, или же цвета не напрямую соответствуют \(x\) и \(y\), а являются более абстрактными генами.
Давайте предположим, что кроссинговер происходит по принципу обмена одной из координат \((x, y)\).
Скрещивание 'a' \((-2, 1)\) и 'b' \((-1, -1)\):
Возможные потомки (одноточечный кроссинговер):
- Потомок 1: \((x_a, y_b)\) = \((-2, -1)\)
- Потомок 2: \((x_b, y_a)\) = \((-1, 1)\)
На графе показаны 4 потомка: b1, c1, b2, c2. Это может означать, что происходит несколько скрещиваний или более сложный механизм.
Если мы строго следуем цветам на графе и нашим предположениям о кодировке:
Родители:
- a: (Красный, Зеленый) = \((-2, 1)\)
- b: (Синий, Белый) = \((-1, -1)\)
- c: (Желтый, Бирюзовый) = \((0, 1)\)
Потомки от скрещивания 'a' и 'b':
- b1: (Синий, Красный) = \((-1, -2)\)
- c1: (Желтый, Красный) = \((0, -2)\) (Здесь желтый квадрат появляется из ниоткуда, если только он не был скрытым геном у 'b' или 'a', или это мутация, или ошибка в задании/интерпретации).
Потомки от скрещивания 'b' и 'c':
- b2: (Зеленый, Белый) = \((1, -1)\)
- c2: (Бирюзовый, Белый) = \((1, -1)\) (Бирюзовый и зеленый могут быть одним и тем же значением 1, или это разные значения).
Давайте предположим, что цвета кодируют значения из таблицы, и если цвет повторяется, то это то же значение. Если цвет новый (например, белый или бирюзовый), то он должен быть одним из оставшихся значений из таблицы, например, 0 или 1.
У нас есть значения: -2, -1, 0, 1.
Предположим кодировку:
- Красный = -2
- Синий = -1
- Желтый = 0
- Зеленый = 1
- Белый = -1 (как синий, или это другое значение?)
- Бирюзовый = 1 (как зеленый, или это другое значение?)
Если белый и бирюзовый - это просто другие оттенки синего и зеленого, то:
- a: \((-2, 1)\)
- b: \((-1, -1)\)
- c: \((0, 1)\)
Потомки:
- b1: (Синий, Красный) = \((-1, -2)\)
- c1: (Желтый, Красный) = \((0, -2)\)
- b2: (Зеленый, Белый) = \((1, -1)\)
- c2: (Бирюзовый, Белый) = \((1, -1)\)
Шаг 4: Вычисление приспособленности для потомков.
Для b1 \((x=-1, y=-2)\):
\[Z_{b1} = \frac{(-1) - 3(-2) + 1}{3(-1)^2 + 3(-2)^2 + 1} = \frac{-1 + 6 + 1}{3(1) + 3(4) + 1} = \frac{6}{3 + 12 + 1} = \frac{6}{16} = 0.375\]Для c1 \((x=0, y=-2)\):
\[Z_{c1} = \frac{0 - 3(-2) + 1}{3(0)^2 + 3(-2)^2 + 1} = \frac{0 + 6 + 1}{0 + 3(4) + 1} = \frac{7}{12 + 1} = \frac{7}{13} \approx 0.5385\]Для b2 \((x=1, y=-1)\):
\[Z_{b2} = \frac{1 - 3(-1) + 1}{3(1)^2 + 3(-1)^2 + 1} = \frac{1 + 3 + 1}{3(1) + 3(1) + 1} = \frac{5}{3 + 3 + 1} = \frac{5}{7} \approx 0.7143\]Для c2 \((x=1, y=-1)\):
\[Z_{c2} = \frac{1 - 3(-1) + 1}{3(1)^2 + 3(-1)^2 + 1} = \frac{1 + 3 + 1}{3(1) + 3(1) + 1} = \frac{5}{3 + 3 + 1} = \frac{5}{7} \approx 0.7143\]Сводная таблица приспособленности:
| Особь | \(x\) | \(y\) | \(Z\) |
| a | -2 | 1 | -0.25 |
| b | -1 | -1 | 0.4286 |
| c | 0 | 1 | -0.5 |
| b1 | -1 | -2 | 0.375 |
| c1 | 0 | -2 | 0.5385 |
| b2 | 1 | -1 | 0.7143 |
| c2 | 1 | -1 | 0.7143 |
Шаг 5: Формирование новой популяции (селекция следующего поколения).
Если цель - максимизировать \(Z\), то из всех особей (родителей и потомков) выбираются те, у кого \(Z\) наибольшее. В данном случае, особи b2 и c2 имеют наибольшее значение \(Z \approx 0.7143\).
Выводы:
На основе сделанных предположений о кодировке цветов и механизме кроссинговера, мы смогли выполнить один шаг генетического алгоритма. Наилучшие особи в этом поколении - b2 и c2.
Для полной реализации генетического алгоритма необходимо было бы продолжить эти шаги (селекция, кроссинговер, мутация) на протяжении нескольких поколений, пока не будет достигнут критерий останова (например, определенное количество поколений или достижение желаемого значения \(Z\)).
Важно отметить, что без четкой легенды цветов и правил кроссинговера, интерпретация графа может быть неоднозначной. Мои предположения основаны на наиболее логичном подходе к решению подобных задач в рамках генетических алгоритмов.