El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Algoritmes Genètics

Següent ►
►

Els algoritmes genètics (AG) són tècniques d'optimització inspirades en els processos de selecció natural i evolució biològica. Aquestes tècniques són especialment útils per resoldre problemes complexos on les tècniques tradicionals d'optimització poden no ser eficients.

Conceptes Bàsics

  1. Representació de la Solució

  • Cromosoma: Una possible solució al problema, sovint representada com una cadena de bits, números o altres estructures.
  • Gen: Cada element d'un cromosoma que representa una característica de la solució.

  1. Població

  • Població: Un conjunt de cromosomes (solucions) que evoluciona amb el temps.
  • Generació: Cada iteració del procés evolutiu.

  1. Funció de Fitness

  • Fitness: Una funció que avalua la qualitat de cada cromosoma (solució). Les solucions amb un valor de fitness més alt són més propenses a ser seleccionades per a la reproducció.

  1. Operadors Genètics

  • Selecció: El procés de seleccionar cromosomes per a la reproducció basat en el seu fitness.
  • Crossover (Recombinació): Un operador que combina dos cromosomes per crear un o més descendents.
  • Mutació: Un operador que altera aleatòriament un o més gens d'un cromosoma per introduir variabilitat.

Procés d'un Algoritme Genètic

  1. Inicialització: Crear una població inicial de cromosomes de manera aleatòria.
  2. Avaluació: Calcular el fitness de cada cromosoma en la població.
  3. Selecció: Seleccionar cromosomes per a la reproducció basant-se en el seu fitness.
  4. Crossover: Aplicar l'operador de crossover per crear nous cromosomes (descendents).
  5. Mutació: Aplicar l'operador de mutació per introduir variabilitat.
  6. Reemplaçament: Crear una nova generació reemplaçant part o tota la població antiga amb els nous cromosomes.
  7. Termini: Repetir els passos 2-6 fins que es compleixi un criteri de terminació (nombre de generacions, temps, o fitness desitjat).

Exemple Pràctic

Problema: Maximització d'una Funció Simple

Suposem que volem maximitzar la funció \( f(x) = x^2 \) on \( x \) és un enter entre 0 i 31.

Representació

  • Cromosoma: Una cadena binària de 5 bits que representa un valor de \( x \).
  • Gen: Cada bit de la cadena.

Funció de Fitness

  • Fitness: \( f(x) = x^2 \)

Inicialització

import random

def inicialitzar_poblacio(tamany_poblacio, longitud_cromosoma):
    poblacio = []
    for _ in range(tamany_poblacio):
        cromosoma = ''.join(random.choice('01') for _ in range(longitud_cromosoma))
        poblacio.append(cromosoma)
    return poblacio

poblacio = inicialitzar_poblacio(10, 5)
print("Població inicial:", poblacio)

Avaluació

def calcular_fitness(cromosoma):
    x = int(cromosoma, 2)
    return x ** 2

fitness_poblacio = [calcular_fitness(c) for c in poblacio]
print("Fitness de la població:", fitness_poblacio)

Selecció

def seleccio(poblacio, fitness_poblacio):
    total_fitness = sum(fitness_poblacio)
    probabilitats = [f / total_fitness for f in fitness_poblacio]
    pares = random.choices(poblacio, weights=probabilitats, k=2)
    return pares

pares = seleccio(poblacio, fitness_poblacio)
print("Pares seleccionats:", pares)

Crossover

def crossover(pare1, pare2):
    punt_crossover = random.randint(1, len(pare1) - 1)
    fill1 = pare1[:punt_crossover] + pare2[punt_crossover:]
    fill2 = pare2[:punt_crossover] + pare1[punt_crossover:]
    return fill1, fill2

fill1, fill2 = crossover(pares[0], pares[1])
print("Descendents:", fill1, fill2)

Mutació

def mutacio(cromosoma, taxa_mutacio=0.01):
    cromosoma_mutat = ''.join(
        bit if random.random() > taxa_mutacio else '1' if bit == '0' else '0'
        for bit in cromosoma
    )
    return cromosoma_mutat

fill1 = mutacio(fill1)
fill2 = mutacio(fill2)
print("Descendents després de la mutació:", fill1, fill2)

Reemplaçament

def reemplaçament(poblacio, nous_descendents):
    nova_poblacio = poblacio[:-len(nous_descendents)] + nous_descendents
    return nova_poblacio

poblacio = reemplaçament(poblacio, [fill1, fill2])
print("Nova població:", poblacio)

Termini

Aquest procés es repeteix fins que es compleixi un criteri de terminació, com ara un nombre fix de generacions.

Exercici Pràctic

Problema

Implementa un algoritme genètic per trobar el màxim de la funció \( f(x) = x^2 \) on \( x \) és un enter entre 0 i 31. Utilitza una població inicial de 10 cromosomes, una taxa de mutació del 1%, i executa l'algoritme durant 20 generacions.

Solució

import random

def inicialitzar_poblacio(tamany_poblacio, longitud_cromosoma):
    poblacio = []
    for _ in range(tamany_poblacio):
        cromosoma = ''.join(random.choice('01') for _ in range(longitud_cromosoma))
        poblacio.append(cromosoma)
    return poblacio

def calcular_fitness(cromosoma):
    x = int(cromosoma, 2)
    return x ** 2

def seleccio(poblacio, fitness_poblacio):
    total_fitness = sum(fitness_poblacio)
    probabilitats = [f / total_fitness for f in fitness_poblacio]
    pares = random.choices(poblacio, weights=probabilitats, k=2)
    return pares

def crossover(pare1, pare2):
    punt_crossover = random.randint(1, len(pare1) - 1)
    fill1 = pare1[:punt_crossover] + pare2[punt_crossover:]
    fill2 = pare2[:punt_crossover] + pare1[punt_crossover:]
    return fill1, fill2

def mutacio(cromosoma, taxa_mutacio=0.01):
    cromosoma_mutat = ''.join(
        bit if random.random() > taxa_mutacio else '1' if bit == '0' else '0'
        for bit in cromosoma
    )
    return cromosoma_mutat

def reemplaçament(poblacio, nous_descendents):
    nova_poblacio = poblacio[:-len(nous_descendents)] + nous_descendents
    return nova_poblacio

# Paràmetres
tamany_poblacio = 10
longitud_cromosoma = 5
taxa_mutacio = 0.01
generacions = 20

# Inicialització
poblacio = inicialitzar_poblacio(tamany_poblacio, longitud_cromosoma)

for generacio in range(generacions):
    fitness_poblacio = [calcular_fitness(c) for c in poblacio]
    nova_poblacio = []
    while len(nova_poblacio) < tamany_poblacio:
        pares = seleccio(poblacio, fitness_poblacio)
        fill1, fill2 = crossover(pares[0], pares[1])
        fill1 = mutacio(fill1, taxa_mutacio)
        fill2 = mutacio(fill2, taxa_mutacio)
        nova_poblacio.extend([fill1, fill2])
    poblacio = nova_poblacio[:tamany_poblacio]

# Resultat final
fitness_poblacio = [calcular_fitness(c) for c in poblacio]
millor_solucio = poblacio[fitness_poblacio.index(max(fitness_poblacio))]
print("Millor solució:", millor_solucio, "amb fitness:", max(fitness_poblacio))

Resum

Els algoritmes genètics són una poderosa eina d'optimització basada en els principis de l'evolució natural. A través de la selecció, el crossover i la mutació, aquests algoritmes poden trobar solucions òptimes o quasi òptimes per a problemes complexos. En aquest tema, hem explorat els conceptes bàsics, el procés d'un algoritme genètic i hem implementat un exemple pràctic per maximitzar una funció simple.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2024. Tots els drets reservats