Лаб. работа “Генетические алгоритмы”

Разработка и оптимизация интеллектуальных информационных систем
Практика
Автор

Бизюк Андрей

Дата публикации

12 марта 2025 г.

Теоретическая часть

Генетические алгоритмы (ГА) — это методы оптимизации, вдохновленные естественным отбором. Основные этапы:

  1. Инициализация популяции: Создание начального набора решений (особей).
  2. Оценка приспособленности: Расчет качества каждой особи с помощью функции приспособленности.
  3. Селекция: Выбор лучших особей для размножения.
  4. Кроссовер (Скрещивание): Обмен генетическим материалом между родителями.
  5. Мутация: Случайное изменение генов для поддержания разнообразия.

Пример: Максимизация суммы битов

Задача: Найти битовую строку длины 8 с максимальной суммой битов.

import random

# Параметры алгоритма
POP_SIZE = 50
GENES_LENGTH = 8
MUTATION_RATE = 0.1
CROSSOVER_RATE = 0.8
GENERATIONS = 100

# 1. Инициализация популяции
def create_individual():
    return [random.randint(0, 1) for _ in range(GENES_LENGTH)]

population = [create_individual() for _ in range(POP_SIZE)]

# 2. Функция приспособленности
def fitness(individual):
    return sum(individual)

# 3. Селекция (метод рулетки)
def select_parent(population, fitnesses):
    total = sum(fitnesses)
    pick = random.uniform(0, total)
    current = 0
    for i, ind in enumerate(population):
        current += fitnesses[i]
        if current > pick:
            return ind
    return population[-1]

# 4. Одноточечный кроссовер
def crossover(parent1, parent2):
    if random.random() < CROSSOVER_RATE:
        point = random.randint(1, GENES_LENGTH - 1)
        return parent1[:point] + parent2[point:], parent2[:point] + parent1[point:]
    return parent1, parent2

# 5. Мутация
def mutate(individual):
    for i in range(len(individual)):
        if random.random() < MUTATION_RATE:
            individual[i] = 1 - individual[i]
    return individual

# Основной цикл
for gen in range(GENERATIONS):
    # Оценка приспособленности
    fitnesses = [fitness(ind) for ind in population]
    
    # Формирование нового поколения
    new_population = []
    while len(new_population) < POP_SIZE:
        # Селекция
        parent1 = select_parent(population, fitnesses)
        parent2 = select_parent(population, fitnesses)
        
        # Кроссовер
        child1, child2 = crossover(parent1, parent2)
        
        # Мутация
        new_population.extend([mutate(child1), mutate(child2)])
    
    population = new_population[:POP_SIZE]

# Результат
best_individual = max(population, key=fitness)
print("Лучшая особь:", best_individual, "Сумма:", fitness(best_individual))

Турнирный отбор

Турнирный отбор (Tournament Selection) — это один из методов селекции в генетических алгоритмах, который выбирает особи для скрещивания путем проведения мини-соревнований между случайно выбранными кандидатами.

Алгоритм турнирного отбора

  1. Выбираем случайную подгруппу (турнир) из популяции размером k.
  2. Оцениваем приспособленность (fitness) каждой особи в этой подгруппе.
  3. Выбираем лучшую (или с вероятностью, пропорциональной приспособленности).
  4. Повторяем процесс, пока не будет отобрано нужное количество особей.

Преимущества и недостатки

Плюсы:

  • Простота реализации.
  • Гибкость: размер турнира (k) позволяет балансировать между случайностью и жадностью.
  • Эффективность даже при небольшом количестве вызовов функции приспособленности.

Минусы:

  • При большом k популяция быстро сойдется к лучшему решению (может снизить разнообразие).
  • Маленькие турниры могут увеличить случайность выбора.

Циклический кроссовер (CX)

Циклический кроссовер (Cycle Crossover, CX) — это один из методов скрещивания, используемый в генетических алгоритмах для комбинирования характеристик двух родительских решений с сохранением перестановочной структуры.

Алгоритм циклического кроссовера

  1. Выбираем две родительские особи (родителя 1 и родителя 2).
  2. Определяем первый элемент потомка 1, который совпадает с первым элементом родителя 1.
  3. Ищем индекс этого элемента в родителе 2, затем берем значение с этим индексом из родителя 1.
  4. Повторяем процесс, пока не вернемся к начальному элементу. Это и есть цикл.
  5. Значения, попавшие в цикл, копируются в потомка 1 с позиций родителя 1, а оставшиеся элементы берутся из родителя 2.
  6. Второй потомок строится аналогично, но с обменом ролей родителей.

Пример работы CX

Рассмотрим двух родителей:

Родитель 1: [1, 2, 3, 4, 5, 6]  
Родитель 2: [4, 5, 6, 1, 2, 3]
  1. Начинаем с первого элемента: 1 (из родителя 1).
  2. В родителе 2 этот элемент находится в позиции 3. Там у родителя 1 стоит 4.
  3. 4 в родителе 2 на позиции 0, а там у родителя 1 — 1 (возвращаемся к началу).
  4. Получаем цикл (1 → 4).

Заполняем потомка 1:

Потомок 1: [1, X, X, 4, X, X]  
Потомок 2: [4, X, X, 1, X, X]

Оставшиеся элементы берём из второго родителя:

Потомок 1: [1, 5, 6, 4, 2, 3]  
Потомок 2: [4, 2, 3, 1, 5, 6]

Арифметический кроссовер

Арифметический кроссовер (Arithmetic Crossover) — это метод скрещивания, используемый в генетических алгоритмах для вещественных (нецелых) представлений решений. Он основан на линейной комбинации родителей, что позволяет создавать промежуточные значения и способствует плавному поиску в пространстве решений.

Алгоритм арифметического кроссовера

  1. Берем двух родителей — векторы вещественных чисел.

  2. Создаем потомков с помощью линейной комбинации их значений:

    \[ offspring_1 = \alpha \cdot parent_1 + (1 - \alpha) \cdot parent_2 \]

    \[ offspring_2 = (1 - \alpha) \cdot parent_1 + \alpha \cdot parent_2 \]

    где \(\alpha\) — случайный коэффициент из диапазона \([0,1]\).

  3. Повторяем процесс для всех элементов вектора (если применяем покомпонентный кроссовер).

Варианты арифметического кроссовера

🔹 Однородный (uniform): одно \(\alpha\) для всех элементов вектора.
🔹 Покомпонентный (per-gene): каждое значение \(\alpha\) выбирается отдельно для каждой координаты.

Гауссова мутация

Гауссова мутация (Gaussian Mutation) — это метод мутации, применяемый в генетических алгоритмах для работы с вещественными числами. Она основана на добавлении случайного шума, сгенерированного из нормального (гауссовского) распределения.

Как работает Гауссова мутация?

  1. Выбираем ген(ы), который(е) подвергнется мутации.

  2. Добавляем случайное значение из нормального распределения:

    \[ x' = x + \mathcal{N}(\mu, \sigma) \]

    где \(\mathcal{N}(\mu, \sigma)\) — случайное число из нормального распределения со средним \(\mu = 0\) и стандартным отклонением \(\sigma\).

  3. Ограничиваем значения (если у параметров есть допустимый диапазон, например, [0,1]).

Параметры мутации

🔹 \(\sigma\) (стандартное отклонение) — определяет силу мутации.
🔹 Вероятность мутации \(P_m\) — вероятность того, что ген мутирует.

Плюсы и минусы

Плюсы:
✔ Плавная и контролируемая мутация.
✔ Хорошо работает в задачах оптимизации.
✔ Позволяет исследовать пространство решений.

Минусы:
✖ Требует подбора \(\sigma\) — слишком большое значение приведет к хаотическим изменениям.
✖ Может неэффективно работать в дискретных задачах.

Самостоятельные задания

1. Модификация примера

  • Измените параметры POP_SIZE, MUTATION_RATE и CROSSOVER_RATE. Проанализируйте, как это влияет на скорость сходимости алгоритма.
  • Реализуйте турнирную селекцию вместо селекции методом рулетки.

2. Задача коммивояжера (TSP)

  • Реализуйте ГА для решения TSP. Каждая особь — порядок посещения городов.
  • Функция приспособленности: общая длина маршрута.
  • Используйте циклический кроссовер для сохранения допустимых маршрутов.

3. Оптимизация функции

  • Найти минимум функции \(f(x, y) = x^2 + y^2\) в диапазоне \(x, y \in [-5, 5]\).
  • Представление особи: вещественные числа или битовая строка (например, 16 бит на переменную).
  • Реализуйте арифметический кроссовер и гауссову мутацию.

4. Визуализация

  • Добавьте график изменения максимальной и средней приспособленности популяции по поколениям (используйте matplotlib).

5. Усложненная задача

  • Реализуйте многоточечный кроссовер (2 или 3 точки) для задачи максимизации суммы битов. Сравните эффективность с одноточечным.

Пример ввода-вывода для задания 3

# Пример особи (битовое представление):
individual = [0, 1, 0, 1, ..., 1]  # 16 бит для x, 16 бит для y

# Декодирование в вещественные числа:
def decode(bits):
    x = int(''.join(map(str, bits[:16])), 2) / (2**16 - 1) * 10 - 5
    y = int(''.join(map(str, bits[16:])), 2) / (2**16 - 1) * 10 - 5
    return x, y

# Функция приспособленности:
def fitness(individual):
    x, y = decode(individual)
    return - (x**2 + y**2)  # Минимизация через отрицание
Наверх