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

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

Бизюк Андрей

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

12 ноября 2025 г.

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

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

  • Многомерной оптимизации с большим количеством локальных экстремумов
  • Комбинаторных задач (TSP, расписания, размещение)
  • Задач с непрерывными и дискретными переменными
  • Сложных целевых функций, где невозможно вычислить градиент

Преимущества ГА: - Не требуют знания градиента целевой функции - Работают с любыми типами представлений решений - Способны находить глобальные оптимумы - Легко параллелизуются

Недостатки ГА: - Могут быть медленнее градиентных методов на гладких функциях - Требуют тонкой настройки параметров - Не гарантируют нахождение точного оптимума

Сравнение с другими методами оптимизации

Метод Преимущества Недостатки Лучше всего для
Градиентный спуск Быстрая сходимость, точность Требует градиента, застревает в локальных минимумах Гладкие, выпуклые функции
Случайный поиск Простота, не требует градиента Медленная сходимость, случайность Малоразмерные пространства
Генетические алгоритмы Глобальный поиск, универсальность Медленнее на простых задачах, параметры Сложные, многомодальные функции

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

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

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

Критерии остановки генетических алгоритмов

1. Фиксированное число поколений

Простейший подход - остановка после заданного числа поколений. Плюсы: Простота, предсказуемое время выполнения Минусы: Может остановиться преждевременно или работать лишнее время

2. Достижение целевого значения

Остановка при достижении заданного порога приспособленности. Формула: if best_fitness >= target_fitness: stop

3. Стагнация популяции

Остановка при отсутствии улучшений в течение N поколений.

def check_stagnation(fitness_history, stagnation_threshold=50):
    if len(fitness_history) < stagnation_threshold:
        return False
    
    recent_best = max(fitness_history[-stagnation_threshold:])
    overall_best = max(fitness_history)
    
    return recent_best < overall_best * 0.999  # 0.1% improvement threshold

4. Сходимость популяции

Остановка при достижении однородности популяции.

def check_convergence(population, convergence_threshold=0.95):
    unique_individuals = len(set(tuple(ind) for ind in population))
    total_individuals = len(population)
    
    return unique_individuals / total_individuals < (1 - convergence_threshold)

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

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

import random
import matplotlib.pyplot as plt
from typing import List, Tuple, Callable
import numpy as np

class GeneticAlgorithm:
    """
    Улучшенная реализация генетического алгоритма для максимизации суммы битов.
    """
    
    def __init__(self, 
                 population_size: int = 50,
                 chromosome_length: int = 8,
                 mutation_rate: float = 0.1,
                 crossover_rate: float = 0.8,
                 generations: int = 100):
        """
        Инициализация параметров генетического алгоритма.
        
        Args:
            population_size: Размер популяции (должен быть четным)
            chromosome_length: Длина хромосомы в битах
            mutation_rate: Вероятность мутации для каждого гена
            crossover_rate: Вероятность кроссовера
            generations: Количество поколений
        """
        self.population_size = population_size if population_size % 2 == 0 else population_size + 1
        self.chromosome_length = chromosome_length
        self.mutation_rate = max(0.0, min(1.0, mutation_rate))
        self.crossover_rate = max(0.0, min(1.0, crossover_rate))
        self.generations = max(1, generations)
        
        self.population = []
        self.fitness_history = []
        self.best_fitness_history = []
        
    def create_individual(self) -> List[int]:
        """Создание случайной особи."""
        return [random.randint(0, 1) for _ in range(self.chromosome_length)]
    
    def fitness(self, individual: List[int]) -> float:
        """
        Функция приспособленности - сумма битов.
        
        Args:
            individual: Хромосома особи
            
        Returns:
            Значение приспособленности
        """
        return float(sum(individual))
    
    def roulette_wheel_selection(self, population: List[List[int]], fitnesses: List[float]) -> List[int]:
        """
        Селекция методом рулетки с исправленной логикой.
        
        Args:
            population: Популяция особей
            fitnesses: Значения приспособленности
            
        Returns:
            Выбранная особь
        """
        total_fitness = sum(fitnesses)
        
        # Обработка случая, когда все особи имеют нулевую приспособленность
        if total_fitness == 0:
            return random.choice(population)
        
        # Нормализация вероятностей
        probabilities = [f / total_fitness for f in fitnesses]
        
        # Кумулятивные вероятности
        cumulative = np.cumsum(probabilities)
        
        # Случайный выбор
        r = random.random()
        
        # Бинарный поиск для эффективности
        left, right = 0, len(cumulative) - 1
        while left < right:
            mid = (left + right) // 2
            if cumulative[mid] < r:
                left = mid + 1
            else:
                right = mid
                
        return population[left]
    
    def tournament_selection(self, population: List[List[int]], fitnesses: List[float], 
                           tournament_size: int = 3) -> List[int]:
        """
        Турнирная селекция.
        
        Args:
            population: Популяция особей
            fitnesses: Значения приспособленности
            tournament_size: Размер турнира
            
        Returns:
            Выбранная особь
        """
        tournament_indices = random.sample(range(len(population)), tournament_size)
        tournament_fitnesses = [fitnesses[i] for i in tournament_indices]
        winner_index = tournament_indices[np.argmax(tournament_fitnesses)]
        
        return population[winner_index]
    
    def single_point_crossover(self, parent1: List[int], parent2: List[int]) -> Tuple[List[int], List[int]]:
        """
        Одноточечный кроссовер.
        
        Args:
            parent1, parent2: Родительские особи
            
        Returns:
            Два потомка
        """
        if random.random() < self.crossover_rate:
            point = random.randint(1, self.chromosome_length - 1)
            child1 = parent1[:point] + parent2[point:]
            child2 = parent2[:point] + parent1[point:]
            return child1, child2
        
        return parent1.copy(), parent2.copy()
    
    def mutate(self, individual: List[int]) -> List[int]:
        """
        Мутация битовой строки.
        
        Args:
            individual: Хромосома особи
            
        Returns:
            Мутированная особь
        """
        mutated = individual.copy()
        for i in range(self.chromosome_length):
            if random.random() < self.mutation_rate:
                mutated[i] = 1 - mutated[i]
        return mutated
    
    def evolve(self, selection_method: str = "tournament") -> Tuple[List[int], float, List[float], List[float]]:
        """
        Основной цикл эволюции.
        
        Args:
            selection_method: Метод селекции ("roulette" или "tournament")
            
        Returns:
            Лучшая особь, её приспособленность, история средней и лучшей приспособленности
        """
        # Инициализация популяции
        self.population = [self.create_individual() for _ in range(self.population_size)]
        
        self.fitness_history = []
        self.best_fitness_history = []
        
        selection_func = (self.roulette_wheel_selection if selection_method == "roulette" 
                         else self.tournament_selection)
        
        for generation in range(self.generations):
            # Оценка приспособленности
            fitnesses = [self.fitness(ind) for ind in self.population]
            
            # Сохранение статистики
            avg_fitness = sum(fitnesses) / len(fitnesses)
            best_fitness = max(fitnesses)
            
            self.fitness_history.append(avg_fitness)
            self.best_fitness_history.append(best_fitness)
            
            # Вывод прогресса каждые 10 поколений
            if generation % 10 == 0:
                print(f"Поколение {generation}: Средняя приспособленность = {avg_fitness:.2f}, "
                      f"Лучшая = {best_fitness:.2f}")
            
            # Формирование нового поколения
            new_population = []
            
            while len(new_population) < self.population_size:
                # Селекция родителей
                parent1 = selection_func(self.population, fitnesses)
                parent2 = selection_func(self.population, fitnesses)
                
                # Кроссовер
                child1, child2 = self.single_point_crossover(parent1, parent2)
                
                # Мутация и добавление в новую популяцию
                new_population.extend([self.mutate(child1), self.mutate(child2)])
            
            # Обновление популяции (обрезаем лишние особи)
            self.population = new_population[:self.population_size]
        
        # Финальная оценка
        final_fitnesses = [self.fitness(ind) for ind in self.population]
        best_index = np.argmax(final_fitnesses)
        
        return (self.population[best_index], 
                final_fitnesses[best_index],
                self.fitness_history,
                self.best_fitness_history)
    
    def plot_convergence(self):
        """Построение графика сходимости."""
        plt.figure(figsize=(10, 6))
        plt.plot(self.fitness_history, label='Средняя приспособленность', alpha=0.7)
        plt.plot(self.best_fitness_history, label='Лучшая приспособленность', linewidth=2)
        plt.xlabel('Поколение')
        plt.ylabel('Приспособленность')
        plt.title('Сходимость генетического алгоритма')
        plt.legend()
        plt.grid(True, alpha=0.3)
        plt.show()

# Пример использования
if __name__ == "__main__":
    # Создание и запуск алгоритма
    ga = GeneticAlgorithm(population_size=50, 
                         chromosome_length=8,
                         mutation_rate=0.1,
                         crossover_rate=0.8,
                         generations=100)
    
    best_individual, best_fitness, avg_history, best_history = ga.evolve()
    
    print(f"\nРезультат:")
    print(f"Лучшая особь: {best_individual}")
    print(f"Приспособленность: {best_fitness}")
    print(f"Теоретический максимум: {ga.chromosome_length}")
    
    # Построение графика
    ga.plot_convergence()

Практические советы по настройке генетических алгоритмов

1. Представление решений

  • Бинарное кодирование для задач с дискретными переменными
  • Вещественное кодирование для непрерывных задач
  • Перестановки для комбинаторных задач (TSP, расписания)
  • Деревья для структурных задач

2. Размер популяции

  • Малые популяции (20-50): Быстрая сходимость, риск застревания в локальном оптимуме
  • Средние популяции (50-200): Баланс между скоростью и качеством
  • Большие популяции (200+): Медленная сходимость, лучший глобальный поиск

3. Вероятность кроссовера

  • Высокая (0.7-0.9): Быстрый обмен информацией, хорошо для начала поиска
  • Средняя (0.5-0.7): Баланс между исследованием и использованием
  • Низкая (0.1-0.5): Консервативный поиск, сохранение хороших решений

4. Вероятность мутации

  • Высокая (>0.1): Поддержание разнообразия, случайный поиск
  • Средняя (0.01-0.1): Стандартный выбор для большинства задач
  • Низкая (<0.01): Точная настройка, финальная стадия поиска

5. Критерии остановки (в порядке важности)

  1. Достижение целевого значения (если известно)
  2. Стагнация (нет улучшений в течение 50-100 поколений)
  3. Ограничение по времени (для реальных приложений)
  4. Максимальное число поколений (запасной вариант)

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

Турнирный отбор (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. Систематический анализ параметров

Цель: Понять влияние параметров на сходимость алгоритма.

Конкретные задачи: 1. Исследуйте влияние размера популяции (10, 30, 50, 100) 2. Проанализируйте влияние вероятности мутации (0.01, 0.05, 0.1, 0.2) 3. Изучите влияние вероятности кроссовера (0.5, 0.7, 0.8, 0.9) 4. Сравните методы селекции (рулетка vs турнир)

Формат отчета: - Таблица с параметрами и результатами - Графики сходимости для разных параметров - Выводы о влиянии каждого параметра - Рекомендации по выбору параметров

Критерии оценки: - Систематичность исследования - Качество визуализации результатов - Обоснованность выводов

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

Цель: Реализовать ГА для решения задачи коммивояжера.

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

Формат отчета: - Код решения с комментариями - Графики лучших маршрутов для разных поколений - Анализ сходимости алгоритма - Сравнение с жадным алгоритмом

Подсказки:

# Пример создания случайных городов
import numpy as np
cities = [(np.random.uniform(0, 100), np.random.uniform(0, 100)) for _ in range(10)]

# Функция расстояния между городами
def distance(city1, city2):
    return np.sqrt((city1[0] - city2[0])**2 + (city1[1] - city2[1])**2)

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

Цель: Найти минимум функции с использованием ГА.

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

Формат отчета: - Реализации с бинарным и вещественным представлением - Графики сходимости для обоих подходов - Таблица сравнения точности и скорости сходимости - Выводы о выборе представления

Подсказки для вещественного представления:

# Пример особи с вещественными генами
individual = [random.uniform(-5, 5), random.uniform(-5, 5)]

# Арифметический кроссовер
def arithmetic_crossover(parent1, parent2, alpha=0.5):
    child1 = alpha * parent1 + (1 - alpha) * parent2
    child2 = (1 - alpha) * parent1 + alpha * parent2
    return child1, child2

# Гауссова мутация
def gaussian_mutation(gene, sigma=0.1):
    return gene + random.gauss(0, sigma)

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

Цель: Проанализировать поведение ГА через визуализацию.

Конкретные задачи: - Добавьте график изменения максимальной и средней приспособленности популяции по поколениям. - Визуализируйте разнообразие популяции (количество уникальных особей). - Постройте график зависимости между разнообразием и приспособленностью. - Создайте анимацию эволюции популяции (опционально).

Формат отчета: - Код визуализации - Графики для разных параметров алгоритма - Анализ связи между разнообразием и качеством решения - Рекомендации по поддержанию разнообразия

5. Улучшенные методы скрещивания

Цель: Реализовать и сравнить различные методы скрещивания.

Конкретные задачи: - Реализуйте многоточечный кроссовер (2 или 3 точки) для задачи максимизации суммы битов. - Сравните эффективность с одноточечным кроссовером. - Реализуйте равномерный кроссовер (Uniform Crossover). - Проанализируйте влияние типа кроссовера на сходимость.

Формат отчета: - Реализации всех методов кроссовера - Таблица сравнения результатов - Графики сходимости для разных методов - Выводы о применимости каждого метода

Пример многоточечного кроссовера:

def multi_point_crossover(parent1, parent2, num_points=2):
    if random.random() < crossover_rate:
        points = sorted(random.sample(range(1, len(parent1)), num_points))
        # Чередуем сегменты между родителями
        child1, child2 = [], []
        for i in range(len(parent1)):
            if (i // (len(parent1) // (num_points + 1))) % 2 == 0:
                child1.append(parent1[i])
                child2.append(parent2[i])
            else:
                child1.append(parent2[i])
                child2.append(parent1[i])
        return child1, child2
    return parent1.copy(), parent2.copy()

6. Адаптивные параметры (усложненное задание)

Цель: Реализовать ГА с адаптивными параметрами.

Конкретные задачи: - Реализуйте механизм адаптации вероятности мутации на основе разнообразия популяции. - Адаптируйте вероятность кроссовера на основе скорости сходимости. - Сравните адаптивный ГА с фиксированными параметрами. - Проанализируйте динамику изменения параметров.

Формат отчета: - Код адаптивного ГА - Графики изменения параметров во времени - Сравнение результатов с фиксированными параметрами - Выводы об эффективности адаптации

Подсказки:

def adapt_parameters(mutation_rate, crossover_rate, diversity, stagnation_generations):
    # Адаптация мутации
    if diversity < 0.1:
        new_mutation_rate = min(0.5, mutation_rate * 1.1)
    elif diversity > 0.5:
        new_mutation_rate = max(0.01, mutation_rate * 0.9)
    else:
        new_mutation_rate = mutation_rate
    
    # Адаптация кроссовера
    if stagnation_generations > 10:
        new_crossover_rate = max(0.5, crossover_rate * 0.95)
    else:
        new_crossover_rate = crossover_rate
    
    return new_mutation_rate, new_crossover_rate

Пример ввода-вывода для задания 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)  # Минимизация через отрицание

Рекомендации по выполнению работы

  1. Начните с базового примера и убедитесь, что он работает корректно.
  2. Используйте контрольные точки для сохранения промежуточных результатов.
  3. Документируйте свои эксперименты в виде комментариев или отдельного файла.
  4. Сравнивайте результаты с теоретическими ожиданиями.
  5. Не забывайте о визуализации - графики помогают лучше понять поведение алгоритма.

Полезные ресурсы

Наверх