Introducció
Els algoritmes d'optimització són fonamentals en el camp de la intel·ligència artificial (IA) i el machine learning (ML). Aquests algoritmes s'utilitzen per trobar la millor solució possible (o una solució prou bona) a un problema donat, sovint en un espai de solucions molt gran. L'objectiu és maximitzar o minimitzar una funció objectiu, que pot representar qualsevol cosa, des de la precisió d'un model predictiu fins a la minimització de costos en un problema logístic.
Conceptes Clau
- Funció Objectiu: La funció que es vol optimitzar. Pot ser una funció de cost que es vol minimitzar o una funció de benefici que es vol maximitzar.
- Espai de Cerca: L'espai de totes les possibles solucions. Pot ser finit o infinit, discret o continu.
- Convergència: El procés d'arribar a una solució òptima o prou bona.
- Optimització Global vs. Local: La optimització global busca la millor solució en tot l'espai de cerca, mentre que la optimització local pot trobar només la millor solució en una regió específica de l'espai de cerca.
Tipus d'Algoritmes d'Optimització
- Algoritmes de Gradient
Els algoritmes de gradient són àmpliament utilitzats en el camp del machine learning, especialment en l'entrenament de xarxes neuronals.
Gradient Descent (Descens del Gradient)
El Gradient Descent és un mètode iteratiu per trobar el mínim d'una funció. Es basa en moure's en la direcció oposada al gradient de la funció objectiu.
Pseudocodi:
def gradient_descent(f, grad_f, x0, learning_rate, max_iter):
x = x0
for i in range(max_iter):
gradient = grad_f(x)
x = x - learning_rate * gradient
return xExplicació:
f: Funció objectiu.grad_f: Gradient de la funció objectiu.x0: Punt inicial.learning_rate: Taxa d'aprenentatge.max_iter: Nombre màxim d'iteracions.
Variants del Gradient Descent
- Stochastic Gradient Descent (SGD): Actualitza els paràmetres utilitzant un sol exemple de dades a cada iteració.
- Mini-batch Gradient Descent: Utilitza un petit lot de dades a cada iteració.
- Momentum: Afegeix un terme de moment per accelerar la convergència.
- Algoritmes Evolutius
Els algoritmes evolutius s'inspiren en els processos de selecció natural i evolució biològica.
Algoritmes Genètics
Els algoritmes genètics utilitzen operadors com la selecció, el creuament i la mutació per evolucionar una població de solucions.
Pseudocodi:
def genetic_algorithm(population, fitness_fn, mutation_rate, generations):
for generation in range(generations):
population = selection(population, fitness_fn)
population = crossover(population)
population = mutation(population, mutation_rate)
return best_solution(population, fitness_fn)Explicació:
population: Població inicial de solucions.fitness_fn: Funció de fitness que avalua la qualitat de les solucions.mutation_rate: Taxa de mutació.generations: Nombre de generacions.
- Algoritmes de Recuit Simulat (Simulated Annealing)
El recuit simulat és un mètode probabilístic per trobar una aproximació de l'òptim global d'una funció.
Pseudocodi:
def simulated_annealing(f, x0, initial_temp, cooling_rate, max_iter):
x = x0
temp = initial_temp
for i in range(max_iter):
new_x = neighbor(x)
delta_f = f(new_x) - f(x)
if delta_f < 0 or random() < exp(-delta_f / temp):
x = new_x
temp *= cooling_rate
return xExplicació:
f: Funció objectiu.x0: Punt inicial.initial_temp: Temperatura inicial.cooling_rate: Taxa de refredament.max_iter: Nombre màxim d'iteracions.
Exercicis Pràctics
Exercici 1: Implementació del Gradient Descent
Objectiu: Implementar el Gradient Descent per minimitzar la funció \( f(x) = x^2 + 4x + 4 \).
Solució:
def f(x):
return x**2 + 4*x + 4
def grad_f(x):
return 2*x + 4
x0 = 10 # Punt inicial
learning_rate = 0.1
max_iter = 100
x_min = gradient_descent(f, grad_f, x0, learning_rate, max_iter)
print(f"El mínim de la funció es troba a x = {x_min}")Exercici 2: Algoritme Genètic per a l'Optimització
Objectiu: Implementar un algoritme genètic per maximitzar la funció \( f(x) = -x^2 + 4x \).
Solució:
import random
def fitness_fn(x):
return -x**2 + 4*x
def selection(population, fitness_fn):
return sorted(population, key=fitness_fn, reverse=True)[:len(population)//2]
def crossover(population):
offspring = []
for i in range(len(population)//2):
parent1 = population[i]
parent2 = population[len(population)//2 + i]
child = (parent1 + parent2) / 2
offspring.append(child)
return population + offspring
def mutation(population, mutation_rate):
for i in range(len(population)):
if random.random() < mutation_rate:
population[i] += random.uniform(-1, 1)
return population
def genetic_algorithm(population, fitness_fn, mutation_rate, generations):
for generation in range(generations):
population = selection(population, fitness_fn)
population = crossover(population)
population = mutation(population, mutation_rate)
return max(population, key=fitness_fn)
population = [random.uniform(-10, 10) for _ in range(10)]
mutation_rate = 0.1
generations = 50
best_solution = genetic_algorithm(population, fitness_fn, mutation_rate, generations)
print(f"La millor solució trobada és x = {best_solution}")Conclusió
Els algoritmes d'optimització són eines poderoses en la IA i el ML, permetent trobar solucions òptimes en espais de cerca complexos. Hem explorat diversos tipus d'algoritmes, incloent el Gradient Descent, els Algoritmes Genètics i el Recuit Simulat, i hem proporcionat exemples pràctics per il·lustrar el seu funcionament. Aquests coneixements són fonamentals per abordar problemes reals en la IA i el ML, i per desenvolupar models eficients i efectius.
Fonaments d'Intel·ligència Artificial (IA)
Mòdul 1: Introducció a la Intel·ligència Artificial
Mòdul 2: Principis Bàsics de la IA
Mòdul 3: Algoritmes en IA
Mòdul 4: Aprenentatge Automàtic (Machine Learning)
- Conceptes Bàsics de Machine Learning
- Tipus d'Aprenentatge Automàtic
- Algoritmes de Machine Learning
- Avaluació i Validació de Models
Mòdul 5: Xarxes Neuronals i Deep Learning
- Introducció a les Xarxes Neuronals
- Arquitectura de Xarxes Neuronals
- Deep Learning i les seves Aplicacions