Genetik alqoritmlər

9.1 Genetik alqoritmlərə giriş.

Genetik alqoritmlər (GA) — bu, təbii seçmə prosesindən ilhamlanmış və bioloji təkamül proseslərini təqlid edən optimizasiya və axtarış metodudur.

Genetik alqoritmlər mürəkkəb problemlərin həlli üçün, ənənəvi metodların səmərəsiz olduğu yerlərdə tətbiq olunur. Bu alqoritmlər həllərin inkişafı üçün seleksiya, kross-over və mutasiya mexanizmlərindən istifadə edir.

İş prinsipləri:

1. İnitializasiya:

Mümkün həllərin (xromosomların) başlanğıc populyasiyası yaradılır. Hər bir həll bir sıra kimi (bit string, simvol string və ya digər strukturlar şəklində) kodlanır.

2 Fitness function (uyğunluq funksiyası):

Populyasiyadakı hər bir həllin keyfiyyətini qiymətləndirir.

3. Qiymətləndirmə:

Hər bir həll (fərd) uyğunluq funksiyası (fitness function) vasitəsilə qiymətləndirilir, bu funksiya həllin problemi nə qədər yaxşı həll etdiyini müəyyən edir.

4. Seleksiya:

Daha yaxşı uyğunluq göstəricisinə malik həllər çoxalma üçün seçilmə şansına daha çox malikdirlər. Çox vaxt ruletka seçilməsi (roulette wheel selection), turnir seçilməsi (tournament selection) və ya sıralı seçilmə (rank selection) metodlarından istifadə edilir.

5. Kross-over:

Seçilmiş həllər (valideynlər) yeni həllərin (övladların) yaradılması üçün birləşdirilir. Kross-over bir nöqtəli, iki nöqtəli və ya çox nöqtəli ola bilər.

6. Mutasiya:

Yeni həllərə (övladlara) təsadüfi dəyişikliklər (mutasiyalar) tətbiq edilir ki, müxtəliflik yaranır. Bu, alqoritmin lokal minimumlardan qaçmasına kömək edir.

7. Əvəzləmə:

Yeni populyasiya köhnəsini əvəz edir və proses müəyyən dayandırma şərti yerinə yetirilənə qədər (məsələn, müəyyən sayda nəsil və ya müəyyən uyğunluq səviyyəsi əldə olunana qədər) davam etdirilir.

Üstünlüklər və çatışmazlıqlar:

Üstünlüklər:

• Geniş tətbiq sahəsi: Müxtəlif problemlərin, o cümlədən analitik metodların işləmədiyi problemlərin həlli üçün tətbiq edilə bilər.
• Qlobal optimizasiya: Çoxölçülü və mürəkkəb məkanlarda qlobal optimumları tapmağa qadirdir.
• Elastiklik: İstənilən uyğunluq funksiyası ilə istifadə edilə bilər.

Çatışmazlıqlar:

• Yüksək hesablanma xərcləri: Böyük populyasiyalar və mürəkkəb məsələlər üçün çoxlu hesablama resursları tələb edir.
• Parametrlərin tənzimlənməsində çətinliklər: Parametrlərin (populyasiya ölçüsü, mutasiya və kross-over ehtimalı) seçimi çətin ola bilər və performansa ciddi təsir göstərə bilər.
• Optimal həllin təminatının olmaması: Tapılan həllin qlobal olaraq optimal olacağına heç bir təminat yoxdur.

Əslində genetik alqoritm yüksək effektivlikli bir heurisikadır. Bu algoritm ən yaxşı həll tapmağa zəmanət vermir, hətta bütün məlumatlara çıxışı olsa belə. Lakin mürəkkəb vəziyyətlərdə və böyük həcmli məlumatlarda ideal həllə yaxın bir nəticəni çox tez təqdim edir.

9.2 Tətbiq nümunəsi

Genetik alqoritmin funksiyanın optimallaşdırılması üçün tətbiq nümunəsinə baxaq.

import random

# Genetik alqoritmin parametrləri
POPULATION_SIZE = 100
GENERATIONS = 1000
MUTATION_RATE = 0.01
TOURNAMENT_SIZE = 5
            
# Uyğunluq funksiyasının təyini
def fitness_function(x):
    return -x**2 + 10*x
            
# Populyasiyanın ilkinləşdirilməsi
def initialize_population(size):
    return [random.uniform(-10, 10) for _ in range(size)]
            
# Seleksiya (turnir seçimi)
def tournament_selection(population):
    tournament = random.sample(population, TOURNAMENT_SIZE)
    return max(tournament, key=fitness_function)
            
# Krossover (birtəkanlı)
def crossover(parent1, parent2):
    alpha = random.random()
    return alpha * parent1 + (1 - alpha) * parent2
            
# Mutasiya
def mutate(individual):
    if random.random() < MUTATION_RATE:
        return individual + random.gauss(0, 1)
    return individual
            
# Genetik alqoritmin əsas dövrü
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
            
# Ən yaxşı həllin çıxarılması
best_individual = max(population, key=fitness_function)
print("Ən yaxşı həll:", best_individual)
print("Funksiyanın dəyəri:", fitness_function(best_individual))
            
        

Üstünlüklər və çatışmazlıqlar

9.3 Çoxölçülü funksiyanın optimizasiyası

Tapşırıq:

Çoxölçülü funksiyanın minimal dəyərini tapmaq.

Həll:

Əvvəlki şablonu götürürük

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
# İstifadə nümunəsi:
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"Ən yaxşı həll: {best_solution}")