1.1.1 Пример
Задача:
Пусть дана начальная популяция из четырех хромосом с двумя генами x и y. Показатель качества хромосомы оценивается функцией Z. При равном качестве хромосом предпочтение отдается хромосоме с большим номером. На каждом этапе хромосома a с высшим качеством порождает четыре новых хромосомы b1, c1, b2, c2, обмениваясь генами с двумя хромосомами b и c более низкого качества по указанной схеме:
(Здесь приводится схема обмена генами, аналогичная той, что была в предыдущем задании. Она показывает, как из хромосом a, b, c формируются новые хромосомы b1, c1, b2, c2. Важно отметить, что в данном контексте a, b, c - это "родители", а b1, c1, b2, c2 - "потомки".)
Последняя хромосома (с низшим качеством) выбывает из популяции. Найти максимальный показатель качества хромосомы в популяции и общее качество популяции после четырех этапов эволюции.
Решение:
Потребуется несколько функций для реализации алгоритма. Напишем их.
1. Функция оценки качества хромосомы qZ(x,y):
Эта функция вычисляет показатель качества Z для данной хромосомы с генами x и y.
# функция качества хромосомы
def qZ(x, y):
return (x - 3 * y + 1) / (3 * x ** 2 + 3 * y ** 2 + 1)
(Эта функция соответствует формуле, которую мы уже разбирали в предыдущем задании: \[Z = \frac{x - 3y + 1}{3x^2 + 3y^2 + 1}\])
2. Функция оценки суммарного качества хромосом qSumZ(Z):
Эта функция, вероятно, должна суммировать качества всех хромосом в популяции. Однако, в примере кода она просто возвращает `sum(Z)`, что предполагает, что `Z` уже является списком или массивом качеств.
# сумма качества хромосом
def qSumZ(Z):
return sum(Z)
3. Функция обмена хромосомами exchangeScheme(oldX, oldY, sortedId):
Эта функция реализует схему обмена генами для создания нового поколения хромосом. Она принимает старые гены (oldX, oldY) и отсортированные индексы (sortedId), которые, вероятно, указывают на порядок хромосом по качеству.
def exchangeScheme(oldX, oldY, sortedId):
X = [0 for i in range(4)] # Создаем новый список для генов X
Y = [0 for i in range(4)] # Создаем новый список для генов Y
# Заполнение новых хромосом на основе схемы обмена
# Предполагается, что sortedId[0] - это индекс хромосомы с лучшим качеством (a)
# sortedId[1] и sortedId[2] - это индексы хромосом b и c
# (хотя в коде используется sortedId[2] дважды для Y[0] и Y[1], что может быть ошибкой или особенностью схемы)
# Новые хромосомы b1, c1, b2, c2 формируются из a, b, c
# (согласно схеме на рисунке, где a, b, c - родители, а b1, c1, b2, c2 - потомки)
# X[2] и X[3] получают гены от хромосомы с индексом sortedId[2]
X[2] = oldX[sortedId[2]]
X[3] = oldX[sortedId[2]]
# X[0] и X[1] получают гены от хромосомы с индексом sortedId[0]
X[0] = oldX[sortedId[0]]
X[1] = oldX[sortedId[1]] # Здесь, вероятно, должна быть sortedId[1]
# Y[0] и Y[1] получают гены от хромосомы с индексом sortedId[2]
Y[0] = oldY[sortedId[2]]
Y[1] = oldY[sortedId[2]]
# Y[2] и Y[3] получают гены от хромосомы с индексом sortedId[0]
Y[2] = oldY[sortedId[0]]
Y[3] = oldY[sortedId[1]] # Здесь, вероятно, должна быть sortedId[1]
return X, Y # Возвращаем новые списки генов X и Y
(Примечание: В коде есть небольшая неточность или особенность в использовании `sortedId[2]` для `X[2], X[3], Y[0], Y[1]`. Обычно для обмена генами используются разные "родители". Если `sortedId` отсортирован по качеству от лучшего к худшему, то `sortedId[0]` - лучший, `sortedId[1]` - второй лучший, `sortedId[2]` - третий лучший. Схема на рисунке показывает, что хромосома 'a' (лучшая) обменивается генами с 'b' и 'c' (более низкого качества). Возможно, `sortedId[0]` соответствует 'a', `sortedId[1]` - 'b', `sortedId[2]` - 'c'.)
4. Функция сортировки массива качества sorting(Z):
Эта функция сортирует массив качеств Z и возвращает индексы хромосом в порядке возрастания качества (от худшего к лучшему).
def sorting(Z):
# sortedId будет содержать индексы хромосом, отсортированные по их качеству Z[k]
# key=lambda k: Z[k] указывает, что сортировка происходит по значению элемента Z с индексом k
sortedId = sorted(range(len(Z)), key=lambda k: Z[k])
return sortedId
5. Функция для шага эволюции evoStep(X, Y, Z):
Эта функция реализует один шаг эволюции: находит хромосому с наименьшим качеством и удаляет ее из популяции.
# шаг эволюции
def evoStep(X, Y, Z):
# Находим хромосому с минимальным качеством и ее индекс
# min((value, id) for (id, value) in enumerate(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. Конечная функция для выполнения нескольких шагов эволюции evoSteps(X, Y, stepsNum=4):
Эта функция объединяет все предыдущие шаги для проведения полной эволюции популяции в течение заданного количества шагов.
# шаги эволюции (конечная функция), по умолчанию 4 шага
def evoSteps(X, Y, stepsNum = 4):
results = [] # Список для хранения результатов каждого шага
for i in range(stepsNum): # Цикл по количеству шагов эволюции
# 1. Вычисляем качество Z для текущей популяции
arrZ = [qZ(x_val, Y[idx]) for idx, x_val in enumerate(X)]
# 2. Выполняем шаг эволюции (удаляем худшую хромосому)
X, Y, Z = evoStep(X, Y, arrZ) # Z здесь - это arrZ после удаления худшего
# 3. Сортируем оставшиеся хромосомы по качеству
sorted_indices = sorting(Z)
# 4. Создаем новое поколение хромосом через обмен генами
# (Здесь есть логическая нестыковка: exchangeScheme принимает oldX, oldY, sortedId,
# но в данном контексте X, Y уже являются результатом evoStep, т.е. имеют 3 элемента.
# А exchangeScheme ожидает 4 элемента и создает 4 новых.
# Это означает, что после evoStep популяция уменьшается до 3 хромосом,
# а exchangeScheme снова создает 4. Это соответствует задаче, где "порождает четыре новых хромосомы".)
X, Y = exchangeScheme(X, Y, sorted_indices)
# 5. Снова вычисляем качество Z для нового поколения (4 хромосомы)
current_Z = [qZ(x_val, Y[idx]) for idx, x_val in enumerate(X)]
# 6. Сохраняем результаты текущего шага:
# [новые X, новые Y, суммарное качество, список качеств Z]
results.append([X, Y, qSumZ(current_Z), current_Z])
return X, Y, results # Возвращаем финальные 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)
Запишем их в требуемом виде и воспользуемся написанной функцией evoSteps.
# объявление массивов хромосом X = [-2, -1, 0, 1] Y = [-2, -1, 0, 1] # Реализация алгоритма final_X, final_Y, results = evoSteps(X, Y)
Теперь, выведем полученные значения для показателя качества хромосомы в популяции и общее качество популяции после четырех этапов эволюции.
Для этого, воспользуемся циклом по значениям переменной results.
for i in range(len(results)):
# Выводим максимальное качество хромосомы на каждом шаге
# results[i][3] - это список качеств Z для текущего шага
print(f'max_ {i + 1}_step: {max(results[i][3])}')
qualityArrZ = []
for i in range(len(results)):
# Собираем все значения Z из всех шагов для поиска общего максимального Z
qualityArrZ.extend(results[i][3])
# Выводим общее максимальное качество Z за все шаги
print(f'max Z: {max(qualityArrZ)}')
Пошаговое выполнение (для понимания, что происходит):
Начальная популяция:
- (x=-2, y=-2) -> Z = 0.2
- (x=-1, y=-1) -> Z = 3/7 ≈ 0.42857
- (x=0, y=0) -> Z = 1
- (x=1, y=1) -> Z = -1/7 ≈ -0.14286
Список Z: [0.2, 0.42857, 1, -0.14286]
Отсортированные индексы (по возрастанию Z): [3, 0, 1, 2] (т.е. Z[3] - худшее, Z[2] - лучшее)
Шаг 1:
1. Вычисляем Z: [0.2, 0.42857, 1, -0.14286]
2. evoStep: Удаляем худшую хромосому (x=1, y=1, Z=-0.14286).
Остаются:
- (x=-2, y=-2) -> Z = 0.2
- (x=-1, y=-1) -> Z = 3/7 ≈ 0.42857
- (x=0, y=0) -> Z = 1
Новые X: [-2, -1, 0], Y: [-2, -1, 0], Z: [0.2, 0.42857, 1]
3. sorting(Z): Отсортированные индексы для оставшихся 3 хромосом: [0, 1, 2] (т.е. Z[0] - худшее, Z[2] - лучшее)
4. exchangeScheme(X, Y, sorted_indices):
Здесь `sorted_indices` будет [0, 1, 2].
`oldX` = [-2, -1, 0], `oldY` = [-2, -1, 0]
`sortedId[0]` = 0 (индекс лучшей хромосомы в текущей популяции, т.е. (0,0) с Z=1)
`sortedId[1]` = 1 (индекс второй хромосомы, т.е. (-1,-1) с Z=0.42857)
`sortedId[2]` = 2 (индекс третьей хромосомы, т.е. (-2,-2) с Z=0.2)
(Внимание: здесь есть расхождение с тем, как я интерпретировал `sortedId` ранее. Если `sortedId` отсортирован по возрастанию качества, то `sortedId[0]` - худший, `sortedId[1]` - второй худший, `sortedId[2]` - лучший. В коде `exchangeScheme` используется `sortedId[0]` и `sortedId[1]` для получения генов, что может означать, что они берутся от лучших хромосом. Давайте предположим, что `sortedId[0]` - это индекс лучшей хромосомы, `sortedId[1]` - второй лучшей, `sortedId[2]` - третьей лучшей, как это обычно бывает в генетических алгоритмах, когда мы выбираем "родителей".)
Если `sortedId` отсортирован по возрастанию Z, то `sortedId[0]` - это индекс худшей хромосомы, `sortedId[1]` - второй худшей, `sortedId[2]` - лучшей.
Тогда:
`oldX[sortedId[2]]` = `oldX[2]` = 0
`oldX[sortedId[0]]` = `oldX[0]` = -2
`oldX[sortedId[1]]` = `oldX[1]` = -1
`oldY[sortedId[2]]` = `oldY[2]` = 0
`oldY[sortedId[0]]` = `oldY[0]` = -2
`oldY[sortedId[1]]` = `oldY[1]` = -1
Новые X: [oldX[0], oldX[1], oldX[2], oldX[2]] = [-2, -1, 0, 0]
Новые Y: [oldY[2], oldY[2], oldY[0], oldY[1]] = [0, 0, -2, -1]
Новая популяция (X, Y):
- (-2, 0)
- (-1, 0)
- (0, -2)
- (0, -1)
5. Вычисляем Z для нового поколения:
- Для (-2, 0): \(Z = \frac{-2 - 3(0) + 1}{3(-2)^2 + 3(0)^2 + 1} = \frac{-1}{12 + 1} = \frac{-1}{13} \approx -0.0769\)
- Для (-1, 0): \(Z = \frac{-1 - 3(0) + 1}{3(-1)^2 + 3(0)^2 + 1} = \frac{0}{3 + 1} = 0\)
- Для (0, -2): \(Z = \frac{0 - 3(-2) + 1}{3(0)^2 + 3(-2)^2 + 1} = \frac{7}{12 + 1} = \frac{7}{13} \approx 0.53846\)
- Для (0, -1): \(Z = \frac{0 - 3(-1) + 1}{3(0)^2 + 3(-1)^2 + 1} = \frac{4}{3 + 1} = \frac{4}{4} = 1\)
Максимальное Z на шаге 1: 1
Далее процесс повторяется 4 раза. В конце будут выведены максимальные Z для каждого шага и общее максимальное Z за все шаги.
Ожидаемый вывод программы:
max_ 1_step: 1
max_ 2_step: (неизвестно без полного прогона)
max_ 3_step: (неизвестно без полного прогона)
max_ 4_step: (неизвестно без полного прогона)
max Z: (общее максимальное Z за все шаги)
(Для получения точных числовых результатов необходимо запустить этот код. Я не могу выполнить код, но могу объяснить его логику.)
Выводы для школьника:
Эта задача демонстрирует, как работает простой генетический алгоритм:
- Оценка качества: Каждая "особь" (хромосома) оценивается по некоторому "качеству" (функция Z).
- Отбор: Худшие особи удаляются из популяции (функция evoStep).
- Размножение/Обмен генами: Оставшиеся (лучшие) особи "размножаются", создавая новое поколение, обмениваясь генами (функция exchangeScheme).
- Эволюция: Эти шаги повторяются, и популяция постепенно "эволюционирует", улучшая свое среднее и максимальное качество.
Цель такого алгоритма - найти наилучшие комбинации генов (x, y), которые дают максимальное значение Z.