Вивчайте Відбір, Кросовер і Мутація

Стратегії відбору

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

Відбір рулеткою: Кожній особині призначається ймовірність відбору, пропорційна її пристосованості. Уявіть колесо, де розмір кожного сектора відповідає рівню пристосованості; особини з вищою пристосованістю мають більший шанс бути обраними;
Турнірний відбір: Випадковим чином обирається група (турнір) особин, і найкраща серед них стає батьківською. Цей метод простий та ефективний, а розмір турніру дозволяє контролювати тиск відбору;
Ранговий відбір: Особини впорядковуються за рівнем пристосованості, і ймовірності відбору призначаються на основі рангу, а не абсолютної пристосованості. Це допомагає уникнути домінування кількох особин з високою пристосованістю, особливо у задачах із великими відмінностями у пристосованості.


              1234567891011121314151617
            
import random

def tournament_selection(population, fitnesses, tournament_size=3):
    """
    Selects one individual from the population using tournament selection.
    """
    # Randomly pick tournament_size individuals
    selected_indices = random.sample(range(len(population)), tournament_size)
    # Find the one with the highest fitness
    best_index = max(selected_indices, key=lambda idx: fitnesses[idx])
    return population[best_index]

# Example usage
population = [[0,1,1,0], [1,0,0,1], [1,1,0,0], [0,0,1,1]]
fitnesses = [3, 2, 5, 4]
parent = tournament_selection(population, fitnesses, tournament_size=2)
print("Selected parent:", parent)

Оператори кросинговеру

Після відбору генетичні алгоритми використовують кросинговер для створення нових особин шляхом комбінування інформації від двох батьків. Кросинговер забезпечує варіативність і дозволяє алгоритму досліджувати нові комбінації ознак у популяції.

Поширені типи кросинговеру:

Одноточковий кросинговер: Випадковим чином обирається точка кросинговеру. Перша частина одного з батьків поєднується з рештою іншого.
Двоточковий кросинговер: Випадковим чином обираються дві точки. Сегмент між ними обмінюється між батьками для створення нащадків.
Уніформний кросинговер: Кожен ген нащадка випадково обирається з одного з двох батьків з однаковою ймовірністю.


              12345678910111213141516171819
            
import random

def single_point_crossover(parent1, parent2):
    """
    Performs single-point crossover between two parents.
    """
    if len(parent1) != len(parent2):
        raise ValueError("Parents must be of the same length")
    point = random.randint(1, len(parent1) - 1)
    child1 = parent1[:point] + parent2[point:]
    child2 = parent2[:point] + parent1[point:]
    return child1, child2

# Example usage
p1 = [1, 0, 1, 0, 1]
p2 = [0, 1, 0, 1, 0]
offspring1, offspring2 = single_point_crossover(p1, p2)
print("Offspring 1:", offspring1)
print("Offspring 2:", offspring2)

Роль мутації

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

Чому мутація важлива

Запобігає передчасній конвергенції: мутація гарантує, що популяція не стане надто однорідною, уникаючи субоптимальної конвергенції;
Підтримує різноманітність: завдяки випадковим змінам мутація зберігає широкий спектр генетичної варіативності для майбутніх поколінь;
Дозволяє уникати локальних оптимумів: невеликі випадкові зміни дозволяють алгоритму досліджувати нові області простору пошуку, які можуть привести до кращих рішень;
Баланс із кросовером: якщо кросовер комбінує наявні ознаки, мутація додає нові, забезпечуючи появу нових можливостей у алгоритмі.

Разом ці властивості роблять мутацію необхідною для стійкого та адаптивного процесу пошуку.

Поширені оператори мутації

Різні типи подання задачі потребують різних технік мутації. Два найпоширеніші оператори:

Бітова мутація (bit-flip): для бінарних подань — змінює біт з 0 на 1 або з 1 на 0, вводячи невеликі контрольовані зміни;
Мутація перестановкою (swap): для перестановочних подань (наприклад, задачі впорядкування) — міняє місцями два елементи в індивіді для створення нової конфігурації.


              1234567891011121314151617181920
            
import random

def bit_flip_mutation(individual, mutation_rate=0.1):
    """
    Performs bit-flip mutation on a binary list.
    """
    mutated = []
    for gene in individual:
        if random.random() < mutation_rate:
            mutated.append(1 - gene)  # Flip bit
        else:
            mutated.append(gene)
    return mutated

# Example usage
original = [1, 0, 1, 1, 0]
mutated = bit_flip_mutation(original, mutation_rate=0.5)
print("Original:", original)
print("Mutated:", mutated)

Все було зрозуміло?

Дякуємо за ваш відгук!

Секція 2. Розділ 2

Запитати АІ

Запитайте про що завгодно або спробуйте одне із запропонованих запитань, щоб почати наш чат

Awesome!

Completion rate improved to 6.25

Свайпніть щоб показати меню