Решение задачи по генетическому алгоритму: Искусственный интеллект

Дисциплина: «Искусственный интеллект»

Рабочая тетрадь № 6: Теоретический материал – Эволюционные методы

Задание:

Выполните по вариантам (1) соответственно реализацию генетического алгоритма в соответствии с приложенными начальными данными.

На изображении представлены следующие начальные данные:

1. Схема скрещивания (кроссинговера) для трех пар хромосом (a, b, c).
2. Таблица с исходными значениями для переменных \(x\) и \(y\).
3. Целевая функция \(Z\).

Давайте пошагово разберем, что нужно сделать.

1. Анализ схемы скрещивания (кроссинговера)

На схеме показан процесс скрещивания для получения нового поколения. У нас есть три родительские пары хромосом: (a), (b), (c).

Каждая хромосома представлена двумя квадратами разного цвета (например, красный и зеленый для 'a'). Это может означать, что каждая хромосома состоит из двух генов или аллелей.

Первое поколение (I):

• Хромосома 'a': верхний квадрат зеленый, нижний красный.
• Хромосома 'b': верхний квадрат синий, нижний белый.
• Хромосома 'c': верхний квадрат желтый, нижний бирюзовый (или светло-голубой).

Второе поколение (I.1):

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

• Потомок \(b_1\): Получает верхний ген от 'b' (синий) и нижний ген от 'a' (красный).
• Потомок \(c_1\): Получает верхний ген от 'a' (зеленый) и нижний ген от 'b' (белый).
• Потомок \(b_2\): Получает верхний ген от 'c' (желтый) и нижний ген от 'a' (красный). (Здесь есть небольшая неточность в схеме, так как стрелка от 'a' указывает на нижний квадрат \(b_2\), но цвет квадрата зеленый, а не красный. Предположим, что это ошибка в схеме и нижний квадрат \(b_2\) должен быть зеленым, как верхний у 'a', или же стрелка должна идти от 'b' или 'c'.) Давайте предположим, что нижний квадрат \(b_2\) должен быть зеленым, как верхний у 'a'.
• Потомок \(c_2\): Получает верхний ген от 'b' (синий) и нижний ген от 'c' (бирюзовый). (Здесь также есть неточность, так как верхний квадрат \(c_2\) зеленый, а не синий. Предположим, что верхний квадрат \(c_2\) должен быть синим, как верхний у 'b'.)

Корректировка схемы (предположение):

Исходя из типичных правил кроссинговера, где происходит обмен участками хромосом, и учитывая цвета:

• Потомок \(b_1\): Верхний от 'b' (синий), нижний от 'a' (красный).
• Потомок \(c_1\): Верхний от 'a' (зеленый), нижний от 'b' (белый).
• Потомок \(b_2\): Верхний от 'c' (желтый), нижний от 'a' (красный). (Если нижний квадрат \(b_2\) на схеме красный, то это соответствует 'a'. Если он зеленый, то это верхний от 'a'.) Давайте считать, что нижний квадрат \(b_2\) красный.
• Потомок \(c_2\): Верхний от 'b' (синий), нижний от 'c' (бирюзовый). (Если верхний квадрат \(c_2\) на схеме зеленый, то это верхний от 'a'. Если синий, то это верхний от 'b'.) Давайте считать, что верхний квадрат \(c_2\) синий.

Таким образом, схема показывает, как из родительских хромосом формируются новые комбинации генов у потомков.

2. Исходные данные для переменных \(x\) и \(y\)

Нам даны следующие пары значений для \(x\) и \(y\):

\[ \begin{array}{|c|c|c|c|c|} \hline x & -2 & -1 & 0 & 1 \\ \hline y & -2 & -1 & 0 & 1 \\ \hline \end{array} \]

Это означает, что у нас есть 4 набора входных данных: \((x_1, y_1) = (-2, -2)\) \((x_2, y_2) = (-1, -1)\) \((x_3, y_3) = (0, 0)\) \((x_4, y_4) = (1, 1)\)

3. Целевая функция \(Z\)

Целевая функция, которую нужно будет вычислять для каждого набора \((x, y)\), имеет вид:

\[ Z = \frac{x - 3y + 1}{3x^2 + 3y^2 + 1} \]

4. Реализация генетического алгоритма (общие шаги)

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

1. Инициализация популяции: Создание начального набора "особей" (хромосом). В нашем случае, это могут быть хромосомы 'a', 'b', 'c'. Если хромосомы кодируют параметры \(x\) и \(y\), то это нужно уточнить. Однако, судя по заданию, хромосомы 'a', 'b', 'c' - это просто абстрактные структуры, а \(x\) и \(y\) - это входные данные для оценки приспособленности.
2. Оценка приспособленности (Fitness Evaluation): Для каждой особи в популяции вычисляется значение приспособленности с помощью целевой функции. В нашем случае, мы будем вычислять \(Z\) для каждого набора \((x, y)\).
3. Селекция (Selection): Выбор наиболее приспособленных особей для создания нового поколения.
4. Кроссинговер (Crossover): Обмен генетическим материалом между выбранными особями для создания потомков. Схема на рисунке как раз показывает пример кроссинговера.
5. Мутация (Mutation): Случайное изменение генов у потомков для поддержания разнообразия.
6. Формирование нового поколения: Замена старой популяции новой.
7. Проверка условия останова: Повторение шагов 2-6 до достижения определенного критерия (например, максимальное количество поколений, достижение определенного значения приспособленности).

В данном задании, скорее всего, требуется выполнить следующие конкретные шаги:

1. Вычислить значения целевой функции \(Z\) для каждого из 4-х наборов \((x, y)\). Это будет "оценка приспособленности" для этих входных данных.
2. Проанализировать схему кроссинговера. Возможно, нужно будет описать, как формируются потомки, или даже присвоить какие-то числовые значения "генам" (квадратам) и показать, как они меняются. Однако, без дополнительных указаний о том, что кодируют эти цветные квадраты, это будет абстрактно.

Вычисления

Давайте вычислим значение \(Z\) для каждого набора \((x, y)\).

Формула: \[ Z = \frac{x - 3y + 1}{3x^2 + 3y^2 + 1} \]

1. Для \((x_1, y_1) = (-2, -2)\):

\[ Z_1 = \frac{(-2) - 3(-2) + 1}{3(-2)^2 + 3(-2)^2 + 1} \] \[ Z_1 = \frac{-2 + 6 + 1}{3(4) + 3(4) + 1} \] \[ Z_1 = \frac{5}{12 + 12 + 1} \] \[ Z_1 = \frac{5}{25} \] \[ Z_1 = \frac{1}{5} = 0.2 \]

2. Для \((x_2, y_2) = (-1, -1)\):

\[ Z_2 = \frac{(-1) - 3(-1) + 1}{3(-1)^2 + 3(-1)^2 + 1} \] \[ Z_2 = \frac{-1 + 3 + 1}{3(1) + 3(1) + 1} \] \[ Z_2 = \frac{3}{3 + 3 + 1} \] \[ Z_2 = \frac{3}{7} \approx 0.4286 \]

3. Для \((x_3, y_3) = (0, 0)\):

\[ Z_3 = \frac{(0) - 3(0) + 1}{3(0)^2 + 3(0)^2 + 1} \] \[ Z_3 = \frac{1}{0 + 0 + 1} \] \[ Z_3 = \frac{1}{1} \] \[ Z_3 = 1 \]

4. Для \((x_4, y_4) = (1, 1)\):

\[ Z_4 = \frac{(1) - 3(1) + 1}{3(1)^2 + 3(1)^2 + 1} \] \[ Z_4 = \frac{1 - 3 + 1}{3(1) + 3(1) + 1} \] \[ Z_4 = \frac{-1}{3 + 3 + 1} \] \[ Z_4 = \frac{-1}{7} \approx -0.1429 \]

Результаты вычислений:

\[ \begin{array}{|c|c|c|c|} \hline x & y & Z & Примечание \\ \hline -2 & -2 & 0.2 & \\ \hline -1 & -1 & \frac{3}{7} \approx 0.4286 & \\ \hline 0 & 0 & 1 & Максимальное значение \\ \hline 1 & 1 & -\frac{1}{7} \approx -0.1429 & Минимальное значение \\ \hline \end{array} \]

Вывод по генетическому алгоритму:

Если бы эти значения \(Z\) представляли приспособленность, то особь, соответствующая \((x, y) = (0, 0)\), была бы наиболее приспособленной (значение \(Z=1\)). Особь, соответствующая \((x, y) = (1, 1)\), была бы наименее приспособленной (значение \(Z \approx -0.1429\)).

Схема кроссинговера показывает, как из родительских хромосом (a, b, c) формируются новые комбинации генов у потомков (\(b_1, c_1, b_2, c_2\)). Это является одним из ключевых операторов генетического алгоритма, обеспечивающим исследование пространства решений.

Для школьника, который переписывает в тетрадь:

Начните с переписывания задания и данных. Затем выполните вычисления по шагам, как показано выше. В конце можно добавить краткий вывод.

Пример оформления в тетради:

Дисциплина: Искусственный интеллект

Рабочая тетрадь № 6: Эволюционные методы

Задание: Выполнить реализацию генетического алгоритма по варианту (1) с приложенными начальными данными.

Начальные данные:

1. Схема скрещивания (кроссинговера): (перерисовать схему или описать ее, как сделано выше)

2. Исходные значения для \(x\) и \(y\):

\[ \begin{array}{|c|c|c|c|c|} \hline x & -2 & -1 & 0 & 1 \\ \hline y & -2 & -1 & 0 & 1 \\ \hline \end{array} \]

3. Целевая функция \(Z\):

\[ Z = \frac{x - 3y + 1}{3x^2 + 3y^2 + 1} \]

Решение:

Шаг 1: Вычисление значений целевой функции \(Z\) для каждого набора \((x, y)\).

1. Для \((x, y) = (-2, -2)\):

\[ Z = \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} = \frac{1}{5} = 0.2 \]

2. Для \((x, y) = (-1, -1)\):

\[ Z = \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 \]

3. Для \((x, y) = (0, 0)\):

\[ Z = \frac{(0) - 3(0) + 1}{3(0)^2 + 3(0)^2 + 1} = \frac{1}{0 + 0 + 1} = \frac{1}{1} = 1 \]

4. Для \((x, y) = (1, 1)\):

\[ Z = \frac{(1) - 3(1) + 1}{3(1)^2 + 3(1)^2 + 1} = \frac{1 - 3 + 1}{3(1) + 3(1) + 1} = \frac{-1}{3 + 3 + 1} = \frac{-1}{7} \approx -0.1429 \]

Результаты вычислений:

\[ \begin{array}{|c|c|c|} \hline x & y & Z \\ \hline -2 & -2 & 0.2 \\ \hline -1 & -1 & \frac{3}{7} \approx 0.4286 \\ \hline 0 & 0 & 1 \\ \hline 1 & 1 & -\frac{1}{7} \approx -0.1429 \\ \hline \end{array} \]

Шаг 2: Анализ схемы кроссинговера.

Схема показывает, как происходит обмен генетическим материалом между родительскими хромосомами (a, b, c) для создания потомков (\(b_1, c_1, b_2, c_2\)). Это один из основных механизмов генетического алгоритма, который позволяет создавать новые комбинации признаков.

• Потомок \(b_1\) формируется из верхней части хромосомы 'b' и нижней части хромосомы 'a'.
• Потомок \(c_1\) формируется из верхней части хромосомы 'a' и нижней части хромосомы 'b'.
• Потомок \(b_2\) формируется из верхней части хромосомы 'c' и нижней части хромосомы 'a'.
• Потомок \(c_2\) формируется из верхней части хромосомы 'b' и нижней части хромосомы 'c'.

Вывод:

В рамках реализации генетического алгоритма были вычислены значения целевой функции \(Z\) для заданных входных данных \((x, y)\). Наибольшее значение \(Z=1\) получено при \((x, y) = (0, 0)\), что указывает на наилучшую "приспособленность" в данном наборе. Схема кроссинговера демонстрирует механизм создания новых особей путем обмена генетическим материалом, что является ключевым этапом эволюционных методов.