Calendario¶
- 24/05/2022: presentazione progetto su algoritmi di approssimazione
- 25/05/2022: laboratorio / ricevimento
- 30/05/2022: laboratorio / ricevimento
⏰ Circa una settimana di tempo per il progetto¶
✏️ Assumiamo gli stessi gruppi del primo semestre, in caso di cambiamenti, avvisare entro il 22/05/2022¶
Algoritmi di approssimazione¶
Abbiamo visto che ci sono problemi (NP-hard / NP-complete) per cui è improbabile che ci possano essere algoritmi esatti e efficienti che li risolvano.
In questi casi se vogliamo una soluzione esatta dobbiamo rinunciare all'efficienza dell'algoritmo risolutivo.
Se vogliamo un algoritmo efficiente, dobbiamo "sacrificare" la qualità della soluzione.
In altri termini, puntiamo a sviluppare algoritmi efficienti che approssimino abbastanza bene la soluzione del problema.
Quando proponiamo problemi di questo tipo sul judge, neanche noi in genere abbiamo a disposizione una soluzione ottima su un determinato input. Calcoliamo il vostro punteggio considerando come si piazza la vostra soluzione rispetto ad un upper bound e un lower bound.
Strategie risolutive¶
Prendiamo un problema intrattabile d'esempio e vediamo alcune strategie per approssimarne al meglio la soluzione
Traveling salesman problem¶
Dato un insieme di città, e note le distanze tra ciascuna coppia di esse, trovare il tragitto di minima percorrenza che un commesso viaggiatore deve seguire per visitare tutte le città una ed una sola volta e ritornare alla città di partenza.
Non esistono algoritmi efficienti per la risoluzione del TSP, l'unico metodo di risoluzione è rappresentato dall'enumerazione totale, ovvero nell'elaborazione di tutti i possibili cammini sul grafo per la successiva scelta di quello migliore.
Tuttavia, la complessità dell'operazione la rende impraticabile per grafi di dimensioni comuni nei problemi reali: in un grafo di n nodi, bisognerà calcolare, nel caso peggiore in cui ogni nodo è connesso con tutti gli altri, $n!$ (n fattoriale) possibili cammini, il che implica una complessità più che esponenziale.
È stato dimostrato che TSP è un problema NP-hard, e la versione decisionale del problema ("dati i pesi e un numero $x$, decidere se ci sia una soluzione migliore di $x$") è NP-complete. Il problema rimane NP-hard anche in molte sue versioni ridotte, come nel caso in cui le città siano in un piano con distanze euclidee.
Generiamo il nostro insieme di città¶
def generate_points(N):
points = [(0,0)]
points.extend([(random.random(), random.random())
for _ in range(N-1)])
return points
cities = generate_points(10)
fig, ax = plt.subplots()
ax.scatter(*zip(*cities))
fig.set_size_inches(4, 3)
plt.show()
Alcune funzioni utili¶
def get_euclidean_distance(a, b):
return math.sqrt((a[0]-b[0])**2 + (a[1]-b[1])**2)
def get_distance_tour(tour):
res = 0
for i in range(1, len(tour)):
res += get_euclidean_distance(tour[i], tour[i-1])
return res
Un primo approccio...¶
Proviamo a generare un tour a caso. So la città da cui devo partire (che sarà la stessa in cui devo tornare) e mi muovo a caso tra le città, evitando di tornare in una già visitata.
def get_random_tour(cities):
tour = list(cities[1:])
random.shuffle(tour)
tour.insert(0, (0,0))
tour.append((0,0))
return tour
tour = get_random_tour(cities)
distance = get_distance_tour(tour)
print(f"La lunghezza di questo tour random è: {distance:.2f}")
anim = animation.FuncAnimation(fig, animate, init_func=init,
frames=range(1, len(tour)+1),
interval=1000, blit=False,
fargs=('tour', tour))
HTML(anim.to_html5_video())
La lunghezza di questo tour random è: 5.35
Non un granché¶
Effettivamente non è una grande idea quella di muovermi a caso, però ho ottenuto una soluzione valida! Mi servirà come baseline.
Baseline: è un punto di partenza, generalmente la soluzione più semplice che avete. Serve inanzitutto a consegnare un progetto valido e prendere i primi punti, e soprattutto a valutare le successive migliorie che andrete ad apportare all'algoritmo. Se partite dalla soluzione più complicata che avete, come fate a sapere come siete messi rispetto alle soluzioni più semplici?
distance = 0
N = 100
for _ in range(N):
tour = get_random_tour(cities)
distance += get_distance_tour(tour)
print(f"Con {N} tour casuali ottengo una media di: {distance/N:.2f}")
Con 100 tour casuali ottengo una media di: 5.28
Let's get greedy¶
Proviamo con qualcosa di più sofisticato del random, ma ancora molto semplice: parto dalla città base, mi sposto sempre nella città più vicina che non ho ancora mai visitato.
def get_greedy_tour(cities):
tour = [(0,0)]
to_visit = set(cities) - {(0,0)}
while len(to_visit) > 0:
last = tour[-1]
min_dist = 1000000000
dist_from_last = lambda x : get_euclidean_distance(last, x)
next_c = min(to_visit, key=dist_from_last)
tour.append(next_c)
to_visit.remove(next_c)
tour.append((0,0))
return tour
tour = get_greedy_tour(cities)
distance = get_distance_tour(tour)
print(f"La lunghezza di questo tour greedy è: {distance:.2f}")
anim = animation.FuncAnimation(fig, animate, init_func=init,
frames=range(1, len(tour)+1), interval=1000, blit=False,
fargs=('tour', tour))
HTML(anim.to_html5_video())
La lunghezza di questo tour greedy è: 3.00
Questa soluzione è poco lungimirante: posso prendere decisioni decisamente sbagliate all'inizio e finire in soluzioni poco interessanti. Tuttavia, in media tende a non comportarsi così male.
Soluzioni di questo tipo sono in genere molto semplici da scrivere, molto veloci da eseguire, e molto "flessibili" (le scelte greedy possono essere più o meno complicate). Tendono ad essere le soluzioni che portano punti ai progetti.
Bonus: per alcuni problemi e alcuni input esistono algoritmi greedy con garanzie di approssimazione!
A volte possiamo calcolare la soluzione ottima¶
E' importante fare attenzione sia al problema che stiamo trattando, sia al dataset che abbiamo in input. Quanto è grande? Per input molto piccoli potremmo essere in grado di calcolare la soluzione ottima (branch and bound o enumerazione).
NB: branch and bound può sfruttare un algoritmo greedy per tagliare i rami inutili
def get_optimal_tour(cities):
min_dist = 10000000000
tour = []
for perm in itertools.permutations(cities[1:]):
perm = [(0, 0)] + list(perm) + [(0, 0)]
perm_dist = get_distance_tour(perm)
if perm_dist < min_dist:
tour = perm
min_dist = perm_dist
return tour
tour = get_optimal_tour(cities)
distance = get_distance_tour(tour)
print(f"La lunghezza del tour ottimale è: {distance:.2f}")
anim = animation.FuncAnimation(fig, animate, init_func=init,
frames=range(1, len(tour)+1), interval=1000, blit=False,
fargs=('tour', tour))
HTML(anim.to_html5_video())
La lunghezza del tour ottimale è: 2.92
Ricerca locale¶
Piccolo esempio di ricerca locale..
- parto da una soluzione valida
- la perturbo un attimo (ottenendo ancora una soluzione valida):
- se ottengo una soluzione migliore allora la tengo
- altrimenti torno indietro alla soluzione di partenza.
Con questa tecnica stiamo "exploitando" i minimi locali, ovvero stiamo scavando per scendere verso un minimo locale. Più le perturbazioni sono piccole, più sto "scavando" di fino. Più le perturbazioni sono grandi, più sto "esplorando", magari perché voglio scappare da un minimo locale e cercarne uno migliore. Esistono tecniche adattive che scelgono il salto migliore in base al landscape di soluzioni circostante il punto che sto visitando.
Ricerca locale in TSP¶
In TSP l'idea è partire da un tour e scambiare due nodi per ottenere ancora un percorso valido. Qui partirò da una soluzione random, ma nulla mi vieta di partire da una soluzione greedy per migliorarla.
def local_search(tour, N):
dist = get_distance_tour(tour)
res = []
for _ in range(N):
i, j = random.sample(range(1, len(tour) - 1), 2)
new_tour = list(tour)
res.append((tour, i, j, dist))
new_tour[i], new_tour[j] = new_tour[j], new_tour[i]
new_dist = get_distance_tour(new_tour)
if new_dist < dist:
dist = new_dist
tour = new_tour
res.append((tour, -1, -1, dist))
return res
N = 20
tour = get_random_tour(cities)
res = local_search(tour, N)
anim = animation.FuncAnimation(fig, animate2, init_func=init2,
frames=N*2, interval=1000, blit=False,
fargs=(res))
HTML(anim.to_html5_video())
Algoritmi genetici 🧬¶
Gli algoritmi genetici permettono di valutare diverse soluzioni di partenza (come se fossero diversi individui biologici) e ricombinandole (analogamente alla riproduzione biologica sessuata) ed introducendo elementi di disordine (analogamente alle mutazioni genetiche casuali) producono nuove soluzioni (nuovi individui) che vengono valutate scegliendo le migliori (selezione ambientale) nel tentativo di convergere verso soluzioni "di ottimo".
Ognuna di queste fasi di ricombinazione e selezione si chiama generazione.
Data la natura intrinsecamente casuale dell'algoritmo genetico, non vi è modo di sapere a priori se sarà effettivamente in grado di trovare una soluzione accettabile al problema considerato. Se si otterrà un risultato soddisfacente, non è detto che si capisca perché abbia funzionato. Questo tipo di algoritmi sono detti meta euristiche, non sono specifici per risolvere un problema ma sono una black box che ottimizza funzioni di costo, basta mappare il problema in questo framework.
NB: Gli algoritmi genetici sono un altro modo di risolvere il trade-off tra exploitation ed exploration dei minimi locali, come abbiamo visto prima.
Design di algoritmi genetici¶
- Generare una popolazione random di partenza
- Valutare la fitness di ogni genoma
- Generare il mating pool (strategia per selezionare i genomi da "accoppiare")
- Ogni genoma nel mating pool viene accoppiato con tutti (o anche no, esistono diverse strategie) gli altri genomi del mating pool
- Ogni accoppiamento prevede crossover (combinazione di due genomi, ottenendo soluzione valida) e probabilità di mutazione (scambio random di geni)
- E' stata creata una nuova popolazione: costituirà la generazione seguente
Approfondimento: nel caso del TSP, il crossover si chiama ordered crossover. La mutazione è un semplice random swap dei nodi con una certa probabilità.
def mutation(tour, p):
i, j = random.sample(range(1, len(tour)-1), 2)
new_tour = list(tour)
new_tour[i], new_tour[j] = new_tour[j], new_tour[i]
return new_tour if random.random() < p else tour
def cross_over(a, b):
crossover = [None] * len(a)
crossover[0] = crossover[-1] = (0, 0)
i1, i2 = sorted(random.sample(range(1, len(a)-1), 2))
for index in range(i1, i2):
crossover[index] = a[index]
b_index = 0
for index in range(1, len(a)-1):
if crossover[index] is None:
while b[b_index] in crossover:
b_index += 1
crossover[index] = b[b_index]
b_index += 1
return crossover
def GA(pop_size=100, num_gen=20, p_mutation=0.25, best_genomes=10):
# initial population
pop = []
for _ in range(pop_size):
r = get_random_tour(cities)
d = get_distance_tour(r)
pop.append((d, r))
# plot the best of each generation
bests = []
for g in range(1, num_gen+1):
pop.sort()
bests.append(pop[0])
mating_pool = pop[:best_genomes]
# combine the solutions in the mating pool
new_pop = []
for i in range(best_genomes):
for j in range(best_genomes):
if i == j:
new_pop.append(mating_pool[i][1])
else:
new_pop.append(cross_over(mating_pool[i][1],
mating_pool[j][1]))
# apply mutations
for i in range(len(new_pop)):
new_pop[i] = mutation(new_pop[i], p_mutation)
new_pop[i] = (get_distance_tour(new_pop[i]), new_pop[i])
pop = new_pop
bests.append(pop[0])
return bests
plt.title("GA")
opt = get_distance_tour(get_optimal_tour(cities))
opt = [opt for _ in range(len(bests))]
plt.plot(range(len(bests)), y, label="fitness")
plt.plot(range(len(bests)), opt, label="ottimo", color='red')
plt.legend()
plt.show()
anim = animation.FuncAnimation(fig, animate3, init_func=init3,
frames=20, interval=1000, blit=False,
fargs=(bests))
HTML(anim.to_html5_video())
Note finali¶
- Abbiamo visto una serie di tecniche più o meno raffinate per risolvere TSP
- E' importante sviluppare una baseline e procedere per miglioramenti successivi (capiamo meglio che scelte migliorano la qualità delle soluzioni e cosa no)
- E' conveniente partire da una soluzione semplice di tipo greedy perché è facile da scrivere e garantisce punti
- Una soluzione greedy può essere migliorata con raffinamenti successivi, ad esempio con local search
- Esistono strategie più sofisticate (algoritmi genetici) ma possono essere difficili da implementare e in laboratorio si ha poco tempo d'esecuzione a disposizione per ogni input