Генетичні алгоритми

9.1 Вступ до генетичних алгоритмів.

Генетичні алгоритми (GA) — це метод оптимізації та пошуку, натхненний процесом природного відбору, який імітує біологічні еволюційні процеси.

Генетичні алгоритми застосовуються для розв'язання складних задач, де традиційні методи можуть бути неефективними. Ці алгоритми використовують механізми селекції, схрещування (кросовер) та мутацій для еволюції рішень.

Принципи роботи:

1. Ініціалізація:

Створюється початкова популяція можливих рішень (хромосом). Кожне рішення кодується у вигляді рядка (бітовий рядок, рядок символів чи інші структури).

2. Функція пристосованості (fitness function):

Оцінює якість кожного рішення в популяції.

3. Оцінка:

Кожне рішення (індивід) оцінюється за допомогою функції пристосованості (fitness function), яка визначає, наскільки добре рішення розв'язує задачу.

4. Селекція:

Рішення з кращою пристосованістю мають більше шансів бути обраними для відтворення. Часто використовуються методи, такі як рулетковий відбір (roulette wheel selection), турнірний відбір (tournament selection) та відбір за ранжируванням (rank selection).

5. Схрещування (кросовер):

Обрані рішення (батьки) комбінуються для створення нових рішень (нащадків). Кросовер може бути одноточковим, двоточковим або багатоточковим.

6. Мутація:

Випадкові зміни в нових рішеннях (мутації) застосовуються для введення різноманіття. Це допомагає алгоритму уникати локальних мінімумів.

7. Заміна:

Нова популяція замінює стару, і процес повторюється до тих пір, поки не буде виконано умову зупинки (наприклад, досягнення певної кількості поколінь або досягнення певної пристосованості).

Переваги та недоліки

Переваги:

• Широкий спектр застосування: Можуть застосовуватися для розв'язання різноманітних задач, включаючи ті, де аналітичні методи не працюють.
• Глобальна оптимізація: Здатні знаходити глобальні оптимуми в багатовимірних і складних просторах.
• Гнучкість: Можуть використовуватися з будь-якою функцією пристосованості.

Недоліки:

• Високі обчислювальні витрати: Потребують значних обчислювальних ресурсів, особливо для великих популяцій та складних задач.
• Труднощі з налаштуванням параметрів: Підбір параметрів (розмір популяції, ймовірність мутації та кросовера) може бути складним і сильно впливати на продуктивність.
• Відсутність гарантії оптимального рішення: Немає гарантії, що знайдене рішення буде глобально оптимальним.

Фактично генетичний алгоритм є високоефективною евристикою. Він не гарантує що знайде найкраще рішення, навіть якщо у нього є доступ до всіх даних. Але для складних ситуацій та величезних обсягів даних він дуже швидко видає рішення наближене до ідеального.

9.2 Приклад застосування

Розглянемо приклад застосування генетичного алгоритму для оптимізації функції.

import random

# Параметри генетичного алгоритму
POPULATION_SIZE = 100
GENERATIONS = 1000
MUTATION_RATE = 0.01
TOURNAMENT_SIZE = 5
            
# Визначення функції пристосованості
def fitness_function(x):
    return -x**2 + 10*x
            
# Ініціалізація популяції
def initialize_population(size):
    return [random.uniform(-10, 10) for _ in range(size)]
            
# Селекція (турнірний відбір)
def tournament_selection(population):
    tournament = random.sample(population, TOURNAMENT_SIZE)
    return max(tournament, key=fitness_function)
            
# Кросовер (одноточковий)
def crossover(parent1, parent2):
    alpha = random.random()
    return alpha * parent1 + (1 - alpha) * parent2
            
# Мутація
def mutate(individual):
    if random.random() < MUTATION_RATE:
        return individual + random.gauss(0, 1)
    return individual
            
# Основний цикл генетичного алгоритму
population = initialize_population(POPULATION_SIZE)
            
for generation in range(GENERATIONS):
    new_population = []
    for _ in range(POPULATION_SIZE):
        parent1 = tournament_selection(population)
        parent2 = tournament_selection(population)
        offspring = crossover(parent1, parent2)
        offspring = mutate(offspring)
        new_population.append(offspring)
    population = new_population
            
# Вивід найкращого рішення
best_individual = max(population, key=fitness_function)
print("Найкраще рішення:", best_individual)
print("Значення функції:", fitness_function(best_individual))
            
        

Переваги та недоліки

9.3 Оптимізація багатовимірної функції

Задача:

Знайти мінімальне значення багатовимірної функції.

Рішення:

Беремо попередній шаблон

import numpy as np

def fitness_function(x):
    return np.sum(x ** 2)
            
def create_individual(dim):
    return np.random.uniform(-10, 10, dim)
            
def create_population(pop_size, dim):
return np.array([create_individual(dim) for _ in range(pop_size)])
            
def select_individuals(population, fitness, num_parents):
    parents = np.empty((num_parents, population.shape[1]))
    for parent_num in range(num_parents):
        min_fitness_idx = np.where(fitness == np.min(fitness))
        min_fitness_idx = min_fitness_idx[0][0]
        parents[parent_num, :] = population[min_fitness_idx, :]
        fitness[min_fitness_idx] = float('inf')
    return parents
            
def crossover(parents, offspring_size):
    offspring = np.empty(offspring_size)
    crossover_point = np.uint8(offspring_size[1] / 2)
    for k in range(offspring_size[0]):
        parent1_idx = k % parents.shape[0]
        parent2_idx = (k + 1) % parents.shape[0]
        offspring[k, 0:crossover_point] = parents[parent1_idx, 0:crossover_point]
        offspring[k, crossover_point:] = parents[parent2_idx, crossover_point:]
    return offspring
            
def mutate(offspring, mutation_rate):
    for idx in range(offspring.shape[0]):
        if np.random.rand() < mutation_rate:
            random_value = np.random.uniform(-1.0, 1.0, 1)
            offspring[idx, 4] = offspring[idx, 4] + random_value
    return offspring
            
def genetic_algorithm(dim, pop_size, num_parents, mutation_rate, num_generations):
    population = create_population(pop_size, dim)
    for generation in range(num_generations):
        fitness = np.array([fitness_function(ind) for ind in population])
        parents = select_individuals(population, fitness, num_parents)
        offspring_crossover = crossover(parents, (pop_size - parents.shape[0], dim))
        offspring_mutation = mutate(offspring_crossover, mutation_rate)
        population[0:parents.shape[0], :] = parents
        population[parents.shape[0]:, :] = offspring_mutation
    best_solution = population[np.argmin(fitness)]
    return best_solution
# Приклад використання:
dim = 10
pop_size = 100
num_parents = 20
mutation_rate = 0.01
num_generations = 1000
best_solution = genetic_algorithm(dim, pop_size, num_parents, mutation_rate, num_generations)
print(f"Найкраще рішення: {best_solution}")