Кафедра ИСиТ УО ВГТУ
  • Специальности
    • Экономика электронного бизнеса
    • Информационные системы
    • Information Control Systems
  • Каталог
  • Сайт кафедры
  • Сервисы
    • GitLab
    • ownCloud
    • JupyterHub
    • JupyterHub 2
    • VNC
    • Soft
  1. ИСиТ
  2. РиОИИС
  3. Практика
  4. Лаб. работа “Генетические алгоритмы”
  • ИСиТ
    • АОС
      • Теория
        • Введение в операционные системы
        • Управление памятью
        • Управление процессами
        • Система ввода-вывода
        • Информационная безопасность
        • Виртуализация
      • Практика
    • РВПсИПП
      • Теория
        • Настройка среды разработки для PHP
        • Разработка web-приложений на базе фреймворков
        • Основы Laravel
        • Шаблоны в Laravel
        • Модели и базы данных в Laravel
        • Формы и валидация в Laravel
        • Аутентификация и авторизация в Laravel
        • Создание REST API в Laravel
        • Работа с файлами и изображениями в Laravel
        • Тестирование и отладка в Laravel
        • Введение в фреймворк Symfony
        • Маршруты и контроллеры в Symfony
        • Шаблоны и Twig в Symfony
        • Формы и валидация в Symfony
        • Доступ к базам данных в Symfony
        • Аутентификация и авторизация в Symfony
        • Сервисы и зависимости в Symfony
        • Создание REST API в Symfony
        • Работа с файлами и медиа в Symfony
        • Сравнение и выбор фреймворка
        • Развертывание веб-приложения
      • Практика
        • Лаб. работа 1 “Создание нового приложения Laravel”
        • Лаб. работа 2 “Добавление главной страницы и базовых маршрутов”
        • Лаб. работа 3 “Создание моделей, миграций и сидеров”
        • Лаб. работа 4 “Создание индексных страниц и пагинация”
        • Лаб. работа 5 “Создание форм для работы с сущностями”
        • Лаб. работа 6 “Работа с файлами (эмуляция S3-хранилища)”
        • Лаб. работа “Создание маршрутов в Laravel”
        • Лаб. работа “Работа с базами данных в Laravel”
        • Лаб. работа “Работа с формами в Laravel”
        • Лаб. работа “Аутентификация и авторизация в Laravel”
        • Лаб. работа “Работа с файлами в Laravel”
        • Лаб. работа “Тестирование и оптимизация в Laravel”
        • Лаб. работа “Создание REST API в Laravel”
        • Лаб. работа “Основы Symfony”
        • Лаб. работа “Шаблоны и представления в Symfony”
        • Лаб. работа “Работа с базами данных в Symfony”
        • Лаб. работа “Фомы и аутентификация в Symfony”
        • Лаб. работа “Сервисы и зависимости в Symfony”
        • Лаб. работа “REST API в Symfony”
        • Лаб. работа “Работа с медиа контентом в Symfony”
        • Лаб. работа “Создание и развертывание проекта”
    • ПСП
      • Теория
        • Введение
        • Протокол HTTP
        • Программирование с использованием сокетов
        • Введение в PHP
        • Работа с базами данных в PHP
        • Объектно-ориентированные возможности PHP
        • Настройка среды разработки для PHP
        • Разработка web-приложений на базе фреймворков
      • Практика
        • Программное обеспечение
        • Регистрация в JupyterHub
        • Лаб. работа “Почтовые протоколы”
        • Лаб. работа “Протокол FTP”
        • Лаб. работа “Протокол HTTP”
        • Лаб. работа “Программирование сетевых приложений с использованием сокетов”
        • Лаб. работа “Основы PHP”
        • Лаб. работа “Массивы в PHP”
        • Лаб. работа “Создание веб-приложений с использованием Slim”
    • Компьютерные сети
      • Теория
        • Введение в компьютерные сети
        • Топологии сетей
        • Кодирование и мультиплексирование
        • Стеки протоколов
        • Адресация в компьютерных сетях
        • Система доменных имен (DNS)
        • Программирование с использованием сокетов
        • Введение в PHP
        • Протокол HTTP
        • Введение в компьютерные сети
      • Практика
        • Программное обеспечение
        • Регистрация в JupyterHub
        • Лаб. работа “Почтовые протоколы”
        • Лаб. работа “Протокол FTP”
        • Лаб. работа “Протокол HTTP”
        • Лаб. работа “Программирование сетевых приложений с использованием сокетов”
        • Лаб. работа “Основы PHP”
        • Лаб работа “Массивы в PHP”
    • РиОИИС
      • Теория
        • Классификация оптимизационных задач
        • Генетические алгоритмы
        • Системы массового обслуживания
        • Теория игр
        • Машинное обучение
        • Глубокое обучение (Deep learning)
        • Основы функционального программирования
        • Основы программирования на Haskell
        • Введение в логическое программирование
        • Инференция и рассуждения в логическом программировании
        • Разработка экспертных систем
        • Интеллектуальные системы и их архитектура
        • Веб-скрэйпинг
        • Сбор данных с открытых API
      • Практика
        • JupyterHub
        • Лаб. работа “Методы одномерной оптимизации”
        • Лаб. работа “Методы многомерной оптимизации”
        • Лаб. работа “Функции в Python”
        • Лаб. работа “Рекурсия в Python”
        • Лаб. работа “Итераторы в Python”
        • Лаб. работа “Генетические алгоритмы”
        • Лаб. работа “Haskell”
        • Лаб. работа “Логическое программирование”
        • Лаб. работа “Сбор данных с помощью веб-скрейпинга”
    • КСКР
      • Практика
        • Лаб. работа “Одномерные и двумерные массивы в C#”
        • Лаб. работа “Обращение матриц в C#”
    • Системное программирование
      • Теория
        • Управление памятью в Windows
        • Файловые операции в Windows
        • Управление процессами в Windows
        • Графический интерфейс Windows
        • ОС Unix
      • Практика
        • Лаб. работа “Работа с динамической памятью в Windows”
        • Лаб. работа “Операции с файлами в Windows”
        • Лаб. работа “Управление процессами в Windows”
        • Лаб. работа “Работа с виртуальной машиной Linux”
        • Лаб. работа “Язык командного энтерпритатора Shell”
        • Лаб. работа “Работа с файлами в Linux”
        • Лаб. работа “Работа с процессами в Linux”

Содержание

  • Теоретическая часть
    • Пример: Максимизация суммы битов
    • Турнирный отбор
    • Циклический кроссовер (CX)
    • Арифметический кроссовер
    • Алгоритм арифметического кроссовера
    • Варианты арифметического кроссовера
    • Гауссова мутация
  • Самостоятельные задания
    • 1. Модификация примера
    • 2. Задача коммивояжера (TSP)
    • 3. Оптимизация функции
    • 4. Визуализация
    • 5. Усложненная задача
  • Пример ввода-вывода для задания 3
  1. ИСиТ
  2. РиОИИС
  3. Практика
  4. Лаб. работа “Генетические алгоритмы”

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

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

Бизюк Андрей

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

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)  # Минимизация через отрицание
Наверх
Лаб. работа “Итераторы в Python”
Лаб. работа “Haskell”