Дисциплина «Искусственный интеллект»
Рабочая тетрадь № 6 Теоретический материал – Эволюционные методы
Задание:
Выполните по вариантам (1) соответственно реализацию генетического алгоритма в соответствии с приложенными начальными данными.
Анализ приложенных данных:
1. Схема обмена генами (визуализация хромосом):
На рисунке представлена та же схема обмена, что и в предыдущих заданиях, но теперь хромосомы изображены цветными квадратами вместо серых/черных/белых. Это просто визуальное представление, суть алгоритма остается прежней.
- Группа I (родители):
- a: верхний квадрат зеленый, нижний квадрат красный.
- b: верхний квадрат синий, нижний квадрат белый.
- c: верхний квадрат желтый, нижний квадрат бирюзовый (голубой).
- Группа II (потомки):
- b1: верхний квадрат синий, нижний квадрат красный.
- c1: верхний квадрат желтый, нижний квадрат красный.
- b2: верхний квадрат зеленый, нижний квадрат белый.
- c2: верхний квадрат зеленый, нижний квадрат бирюзовый (голубой).
Стрелки показывают, как гены (цвета квадратов) передаются от родителей к потомкам:
- Из 'a' (зеленый/красный) гены передаются в b1 (красный) и b2 (зеленый).
- Из 'b' (синий/белый) гены передаются в b1 (синий) и b2 (белый).
- Из 'c' (желтый/бирюзовый) гены передаются в c1 (желтый) и c2 (бирюзовый).
(Важно отметить, что в предыдущем задании схема была немного другой, там стрелки шли от потомков к родителям, а в описании задачи говорилось, что 'a' порождает 'b1, c1, b2, c2', обмениваясь генами с 'b' и 'c'. Здесь же стрелки идут от родителей к потомкам, что более логично для процесса размножения. Это может означать, что функция `exchangeScheme` должна быть адаптирована под эту новую визуальную схему, если она отличается от предыдущей.)
2. Функция оценки качества хромосомы Z:
Формула осталась прежней:
\[Z = \frac{x - 3y + 1}{3x^2 + 3y^2 + 1}\]3. Начальные данные для генов x и y:
Таблица значений x и y также осталась прежней:
| x | -2 | -1 | 0 | 1 |
| y | -2 | -1 | 0 | 1 |
Это означает, что начальная популяция состоит из 4 хромосом с парами генов:
- Хромосома 1: (x=-2, y=-2)
- Хромосома 2: (x=-1, y=-1)
- Хромосома 3: (x=0, y=0)
- Хромосома 4: (x=1, y=1)
Требования к выполнению:
Задание требует "реализацию генетического алгоритма". Это означает, что нужно написать код (скорее всего, на Python, как в примере из предыдущего задания), который будет выполнять следующие шаги:
- Инициализация популяции: Создать начальную популяцию хромосом с заданными генами (x, y).
- Оценка качества: Для каждой хромосомы в популяции вычислить ее качество Z с помощью заданной формулы.
- Отбор: Выбрать лучшие хромосомы для "размножения" и удалить худшие. В предыдущем примере удалялась одна хромосома с наименьшим качеством.
- Скрещивание (обмен генами): Из оставшихся хромосом создать новое поколение, используя схему обмена генами. Здесь нужно внимательно посмотреть на новую схему с цветными квадратами и убедиться, что функция `exchangeScheme` правильно ее реализует.
- Повторение: Повторять шаги 2-4 заданное количество раз (в предыдущем примере - 4 шага эволюции).
- Вывод результатов: В конце вывести максимальное качество хромосомы в популяции и общее качество популяции после всех этапов эволюции.
Как это переписать в тетрадь школьнику:
Заголовок: Реализация генетического алгоритма
1. Цель задания:
Написать программу, которая имитирует эволюцию популяции хромосом. Качество хромосом будет улучшаться со временем за счет отбора лучших и обмена генами.
2. Основные компоненты алгоритма:
- Хромосома: Представлена двумя генами (x, y).
- Качество хромосомы (Z): Вычисляется по формуле: \[Z = \frac{x - 3y + 1}{3x^2 + 3y^2 + 1}\]
- Начальная популяция:
- Хромосома 1: (x=-2, y=-2)
- Хромосома 2: (x=-1, y=-1)
- Хромосома 3: (x=0, y=0)
- Хромосома 4: (x=1, y=1)
- Схема обмена генами: (Здесь можно нарисовать упрощенную схему с цветными квадратами или описать словами, как гены передаются от родителей к потомкам, например: "Верхний ген b1 берется от b, нижний ген b1 берется от a" и т.д.)
3. Шаги генетического алгоритма:
- Оценка: Для каждой хромосомы в популяции вычисляем ее качество Z.
- Отбор: Удаляем хромосому с самым низким качеством.
- Скрещивание: Из оставшихся хромосом создаем новое поколение (4 хромосомы), обмениваясь генами по заданной схеме.
- Повторение: Повторяем шаги 1-3 несколько раз (например, 4 раза, как в предыдущем примере).
4. Программный код (на языке Python):
(Здесь нужно переписать код из предыдущего примера, убедившись, что функция `exchangeScheme` соответствует новой схеме с цветными квадратами, если она отличается от предыдущей интерпретации. Если схема та же, то код можно использовать без изменений.)
Пример кода (как в предыдущем задании, с учетом возможных уточнений для `exchangeScheme`):
# 1. Функция оценки качества хромосомы
def qZ(x, y):
return (x - 3 * y + 1) / (3 * x ** 2 + 3 * y ** 2 + 1)
# 2. Функция для суммирования качеств
def qSumZ(Z):
return sum(Z)
# 3. Функция сортировки (возвращает индексы от худшего к лучшему)
def sorting(Z):
sortedId = sorted(range(len(Z)), key=lambda k: Z[k])
return sortedId
# 4. Функция обмена генами (нужно проверить соответствие схеме с цветными квадратами)
# Предположим, что sortedId[0] - индекс худшей, sortedId[1] - второй худшей, sortedId[2] - лучшей
# И что родители 'a', 'b', 'c' соответствуют лучшим трем хромосомам после отбора.
# Если в популяции 3 хромосомы после evoStep, то sortedId[2] - лучшая, sortedId[1] - средняя, sortedId[0] - худшая.
# В предыдущем примере кода exchangeScheme использовала sortedId[0], sortedId[1], sortedId[2]
# для получения генов. Если sortedId отсортирован по возрастанию Z, то:
# sortedId[0] - индекс хромосомы с наименьшим Z
# sortedId[1] - индекс хромосомы со средним Z
# sortedId[2] - индекс хромосомы с наибольшим Z
#
# Давайте переинтерпретируем exchangeScheme, чтобы она соответствовала схеме:
# Родители: a (лучшая), b (средняя), c (худшая)
# Потомки: b1, c1, b2, c2
#
# Из схемы с цветными квадратами:
# b1: верхний от b, нижний от a
# c1: верхний от c, нижний от a
# b2: верхний от a, нижний от b
# c2: верхний от a, нижний от c
#
# Если sortedId = [индекс_худшей, индекс_средней, индекс_лучшей]
# Тогда:
# a_idx = sortedId[2] (индекс лучшей)
# b_idx = sortedId[1] (индекс средней)
# c_idx = sortedId[0] (индекс худшей)
#
def exchangeScheme(oldX, oldY, sortedId):
X = [0] * 4
Y = [0] * 4
# Определяем индексы родителей
a_idx = sortedId[2] # Лучшая хромосома
b_idx = sortedId[1] # Средняя хромосома
c_idx = sortedId[0] # Худшая хромосома
# Формируем потомков b1, c1, b2, c2
# b1: верхний от b, нижний от a
X[0] = oldX[b_idx]
Y[0] = oldY[a_idx]
# c1: верхний от c, нижний от a
X[1] = oldX[c_idx]
Y[1] = oldY[a_idx]
# b2: верхний от a, нижний от b
X[2] = oldX[a_idx]
Y[2] = oldY[b_idx]
# c2: верхний от a, нижний от c
X[3] = oldX[a_idx]
Y[3] = oldY[c_idx]
return X, Y
# 5. Функция для шага эволюции (удаление худшей)
def evoStep(X, Y, Z):
minVal, minId = min((value, id) for (id, value) in enumerate(Z))
X_copy = X[:]
Y_copy = Y[:]
Z_copy = Z[:]
X_copy.pop(minId)
Y_copy.pop(minId)
Z_copy.pop(minId)
return X_copy, Y_copy, Z_copy
# 6. Конечная функция для выполнения нескольких шагов эволюции
def evoSteps(X, Y, stepsNum = 4):
results = []
for i in range(stepsNum):
arrZ = [qZ(x_val, Y[idx]) for idx, x_val in enumerate(X)]
# Удаляем худшую хромосому
X_after_evo, Y_after_evo, Z_after_evo = evoStep(X, Y, arrZ)
# Сортируем оставшиеся 3 хромосомы по качеству
sorted_indices = sorting(Z_after_evo)
# Создаем новое поколение из 4 хромосом
X, Y = exchangeScheme(X_after_evo, Y_after_evo, sorted_indices)
# Вычисляем качество нового поколения
current_Z = [qZ(x_val, Y[idx]) for idx, x_val in enumerate(X)]
results.append([X, Y, qSumZ(current_Z), current_Z])
return X, Y, results
# Начальные данные
initial_X = [-2, -1, 0, 1]
initial_Y = [-2, -1, 0, 1]
# Запуск алгоритма
final_X, final_Y, results = evoSteps(initial_X, initial_Y)
# Вывод результатов
print("Результаты эволюции:")
for i in range(len(results)):
print(f'Максимальное качество на шаге {i + 1}: {max(results[i][3]):.5f}')
qualityArrZ_all_steps = []
for i in range(len(results)):
qualityArrZ_all_steps.extend(results[i][3])
print(f'Общее максимальное качество Z за все шаги: {max(qualityArrZ_all_steps):.5f}')
5. Ожидаемые результаты:
Программа выведет максимальное качество хромосомы на каждом из 4 шагов эволюции, а также общее максимальное качество, достигнутое за весь процесс.
(Для получения конкретных числовых результатов, этот код нужно запустить.)