Дисциплина «Искусственный интеллект»
Рабочая тетрадь № 6 Теоретический материал – Эволюционные методы
Задание:
Выполните по вариантам (1) соответственно реализацию генетического алгоритма в соответствии с приложенными начальными данными.
Анализ приложенных данных (Вариант 1):
1. Схема обмена генами (скрещивания):
На рисунке представлена визуальная схема, как из трех "родительских" хромосом (a, b, c) формируются четыре "дочерние" хромосомы (b1, c1, b2, c2). Каждая хромосома состоит из двух генов, представленных цветными квадратами (верхний и нижний).
- Родители (I):
- a: Верхний ген - зеленый, Нижний ген - красный.
- b: Верхний ген - синий, Нижний ген - белый.
- c: Верхний ген - желтый, Нижний ген - бирюзовый (голубой).
- Потомки (II) и правила их формирования:
- b1: Верхний ген от 'b' (синий), Нижний ген от 'a' (красный).
- c1: Верхний ген от 'c' (желтый), Нижний ген от 'a' (красный).
- b2: Верхний ген от 'a' (зеленый), Нижний ген от 'b' (белый).
- c2: Верхний ген от 'a' (зеленый), Нижний ген от 'c' (бирюзовый).
Эта схема является ключевой для функции скрещивания (кроссовера) в генетическом алгоритме.
2. Функция оценки качества хромосомы Z:
Качество каждой хромосомы (пары генов x и y) оценивается по следующей формуле:
\[Z = \frac{x - 3y + 1}{3x^2 + 3y^2 + 1}\]Цель алгоритма - найти такие пары (x, y), которые максимизируют значение Z.
3. Начальные данные для генов x и y:
Начальная популяция состоит из четырех хромосом, где гены x и y принимают следующие значения:
| x | -2 | -1 | 0 | 1 |
| y | -2 | -1 | 0 | 1 |
Таким образом, начальная популяция хромосом (x, y) выглядит так:
- Хромосома 1: (-2, -2)
- Хромосома 2: (-1, -1)
- Хромосома 3: (0, 0)
- Хромосома 4: (1, 1)
Требования к реализации генетического алгоритма:
Задание требует "реализацию генетического алгоритма". Это означает, что нужно написать программу (обычно на Python для таких задач), которая будет выполнять следующие этапы эволюции популяции:
- Инициализация: Создание начальной популяции из 4 хромосом с заданными генами.
- Оценка приспособленности (качества): Вычисление значения Z для каждой хромосомы в популяции.
- Отбор (селекция): Выбор "лучших" хромосом для участия в скрещивании. В условиях задачи сказано: "Последняя хромосома (с низшим качеством) выбывает из популяции". Это означает, что из 4 хромосом останутся 3 лучшие.
- Скрещивание (кроссовер): Из 3 отобранных хромосом (которые будут играть роль 'a', 'b', 'c') формируются 4 новые хромосомы (b1, c1, b2, c2) согласно приведенной схеме обмена генами. Важно правильно сопоставить 'a', 'b', 'c' с отобранными хромосомами по их качеству (например, 'a' - лучшая, 'b' - вторая лучшая, 'c' - третья лучшая).
- Формирование нового поколения: Новые 4 хромосомы заменяют старую популяцию.
- Повторение: Эти шаги повторяются заданное количество раз (в предыдущих примерах было 4 этапа эволюции).
- Вывод результатов: В конце нужно найти максимальный показатель качества хромосомы в популяции и общее качество популяции после всех этапов.
Как это переписать в тетрадь школьнику:
Заголовок: Реализация генетического алгоритма (Вариант 1)
1. Цель задания:
Написать программу, которая будет имитировать эволюцию группы "хромосом". Мы будем искать такие хромосомы, которые имеют самое высокое "качество" (значение Z), используя правила отбора и скрещивания.
2. Основные понятия:
- Хромосома: Это пара чисел (x, y), которые мы называем "генами".
- Качество (Z): Это число, которое показывает, насколько "хороша" хромосома. Чем больше Z, тем лучше. Формула для Z: \[Z = \frac{x - 3y + 1}{3x^2 + 3y^2 + 1}\]
- Популяция: Группа из 4 хромосом.
3. Начальные данные:
- Начальная популяция хромосом:
- Хромосома 1: (x=-2, y=-2)
- Хромосома 2: (x=-1, y=-1)
- Хромосома 3: (x=0, y=0)
- Хромосома 4: (x=1, y=1)
- Количество этапов эволюции: 4 этапа.
4. Правила эволюции (как работает алгоритм):
- Оценка качества: Для каждой хромосомы в популяции мы вычисляем ее качество Z.
- Отбор: Мы находим хромосому с самым низким качеством и удаляем ее из популяции. Остается 3 хромосомы.
- Скрещивание (создание нового поколения):
- Мы берем 3 оставшиеся хромосомы и называем их 'a' (лучшая), 'b' (вторая лучшая), 'c' (третья лучшая).
- Из них мы создаем 4 новые хромосомы (b1, c1, b2, c2) по следующей схеме обмена генами:
- b1: x-ген от 'b', y-ген от 'a'
- c1: x-ген от 'c', y-ген от 'a'
- b2: x-ген от 'a', y-ген от 'b'
- c2: x-ген от 'a', y-ген от 'c'
(Здесь можно нарисовать упрощенную схему с квадратами, как на рисунке, но без цветов, просто показывая стрелки от a, b, c к b1, c1, b2, c2.)
- Новая популяция: Эти 4 новые хромосомы становятся нашей новой популяцией.
- Повторение: Мы повторяем шаги 1-4 четыре раза.
5. Что нужно найти в конце:
- Максимальное качество Z, которое было достигнуто в популяции на каждом из 4 этапов.
- Общее максимальное качество Z, которое было достигнуто за все 4 этапа эволюции.
6. Пример кода (на Python):
(Здесь можно вставить код, который я предоставил ранее, с функциями `qZ`, `qSumZ`, `sorting`, `exchangeScheme`, `evoStep`, `evoSteps` и блоком запуска. Важно, чтобы функция `exchangeScheme` точно соответствовала описанной схеме скрещивания.)
# 1. Функция оценки качества хромосомы
def qZ(x, y):
denominator = 3 * x**2 + 3 * y**2 + 1
if denominator == 0:
return float('-inf')
return (x - 3 * y + 1) / denominator
# 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: [индекс_худшей, индекс_средней, индекс_лучшей]
def exchangeScheme(oldX, oldY, sortedId):
X = [0] * 4
Y = [0] * 4
# Определяем индексы родителей:
# 'a' - лучшая хромосома (индекс в oldX/oldY)
# 'b' - вторая лучшая хромосома
# 'c' - третья лучшая хромосома
a_idx = sortedId[2] # Индекс лучшей
b_idx = sortedId[1] # Индекс средней
c_idx = sortedId[0] # Индекс худшей
# Формируем потомков b1, c1, b2, c2 согласно схеме:
# b1: x-ген от 'b', y-ген от 'a'
X[0] = oldX[b_idx]
Y[0] = oldY[a_idx]
# c1: x-ген от 'c', y-ген от 'a'
X[1] = oldX[c_idx]
Y[1] = oldY[a_idx]
# b2: x-ген от 'a', y-ген от 'b'
X[2] = oldX[a_idx]
Y[2] = oldY[b_idx]
# c2: x-ген от 'a', y-ген от '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)
sorted_indices = sorting(Z_after_evo)
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("Результаты эволюции:")
all_max_Z_values = []
for i in range(len(results)):
step_max_Z = max(results[i][3])
all_max_Z_values.append(step_max_Z)
print(f'Максимальное качество на шаге {i + 1}: {step_max_Z:.5f}')
print("-" * 30)
print(f'Общее максимальное качество Z за все шаги: {max(all_max_Z_values):.5f}')
7. Ожидаемые результаты:
После запуска программы мы получим значения максимального качества Z на каждом из 4 шагов эволюции, а также общее максимальное качество Z, достигнутое за весь процесс. Эти значения покажут, как популяция "улучшалась" со временем.