Immagina di essere un musicista improvvisatore che sta cercando di creare un brano musicale. Potresti cominciare a suonare lo strumento in modo esplorativo, suonando accordi e melodie spontanee, cercando di captare un’idea o un tema. Una volta trovato un tema o una melodia che suona bene, inizieresti a svilupparla, aggiungendo variazioni, esplorando diverse dinamiche e ritmi finché non raggiungo un’armonia soddisfacente.

L’improvvisazione musicale opera attraverso un processo di esplorazione, valutazione, adattamento e ottimizzazione, cercando di creare un’armonia.

Si può parlare di armonia nel campo dell’intelligenza artificiale?
La risposta è affermativa se impieghiamo gli algoritmi di Harmony Search.

Gli algoritmi di ricerca dell’Armonia (Harmony Search Algorithms) sono una classe di algoritmi ispirati dal concetto di ricerca dell’armonia nella musica. Questa tecnica è stata proposta per la prima volta nel 2001 da Zong Woo Geem, Joong Hoon Kim e G. V. Loganathan.

L’idea di base degli algoritmi di ricerca dell’Armonia è di emulare il processo di derivazione delle soluzioni migliori perseguendo lo scopo dell’armonia musicale. Le soluzioni candidate sono trattate come “note musicali” che possono essere combinate per creare una “melodia” armoniosa. Questa melodia rappresenta un insieme di soluzioni che vengono esplorate per trovare la migliore.

L’armonia musicale comporta una combinazione bilanciata e piacevole delle note. Allo stesso modo, gli algoritmi Harmony Search, cercano di creare una combinazione equilibrata e ottimale delle soluzioni che conduca alla soluzione migliore del problema.

In pratica si tratta di algoritmi ottimizzazione basati su popolazione simili a quelli genetici e PSO (particle swarm optimization).
Leggi anche i seguenti articoli:

Gli algoritmi genetici: La selezione della soluzione più adatta

Volare verso la soluzione del problema: gli algoritmi Particle Swarm Optimization (PSO)

L’algoritmo Harmony Search si basa su questi principali componenti e processi:

La memoria delle soluzioni
La funzione obiettivo
La produzione della nuova soluzione
L’aggiornamento della memoria

La memoria è costituita dall’insieme delle soluzioni migliori trovate fino a quel momento. La funzione obiettivo stabilisce il valore da assegnare ad ogni soluzione. La produzione della nuova soluzione avviene combinando le soluzioni nella memoria in modo casuale o mediante regole specifiche definite a partire da certi vincoli. Infine, l’aggiornamento della memoria riguarda l’aggiornamento delle soluzioni mantenute nella memoria in base alla qualità delle soluzioni prodotte. Tale qualità viene misurata mediante la funzione obiettivo. Le soluzioni che sono considerate migliori sono mantenute nella memoria, mentre quelle meno promettenti vengono scartate. Questo processo di selezione può essere paragonato all’armonia musicale, in cui le note che si combinano bene e creano una melodia armoniosa vengono mantenute, mentre quelle che contrastano o non si adattano vengono eliminate.

Gli algoritmi di Ricerca dell’Armonia sono stati applicati con successo in diversi problemi di ottimizzazione, come l’ottimizzazione di parametri, l‘ottimizzazione di reti neurali artificiali o l’ottimizzazione di sistemi di controllo. Possono essere utilizzati anche in combinazione con altri algoritmi di ottimizzazione per migliorare le prestazioni.

Gli algoritmi di search armony possono essere applicati a una vasta gamma di problemi di ottimizzazione in diversi settori. Ecco alcuni esempi di problemi che possono essere risolti utilizzando questo tipo di algoritmo:

1. Ottimizzazione dei parametri di modelli matematici complessi, come modelli di simulazione di sistemi fisici, sistemi di controllo o modelli di previsione.
2. Problemi di pianificazione e scheduling, come l’assegnazione ottimale di risorse o l’organizzazione efficiente di attività in uno specifico orario.
3. Problemi di routing e logistica, come il calcolo dei percorsi più efficienti per veicoli o l’ottimizzazione dei flussi di merci in una rete di trasporto.
4. Problemi di progettazione, come l’ottimizzazione dei parametri di un prodotto o la configurazione di un sistema complesso, come ad esempio l’ottimizzazione delle frequenze nei sistemi di comunicazione.
5. Problemi di taglio e imballaggio, come il taglio ottimale di pannelli di legno o l’organizzazione efficiente degli oggetti all’interno di un contenitore.
6. Ottimizzazione delle risorse energetiche, come la gestione ottimale dell’approvvigionamento e della distribuzione di energia elettrica in una rete energetica.
7. Problemi di clustering e classificazione, come il raggruppamento ottimale di dati in cluster coerenti o la classificazione di oggetti in diverse categorie.

Schema dell’algoritmo

Inizializzazione:

• Definizione della dimensione della memoria (popolazione) e generazione di soluzioni iniziali casuali o vincolate
• Definizione della funzione obiettivo
• Valutazione della qualità di ogni soluzione in base alla funzione obiettivo.

Ripetizione fino a raggiungere un criterio di stop:

• Combinazione delle soluzioni presenti nella memoria in modo casuale o seguendo regole specifiche per generare una nuova soluzione candidata.
• Valutazione della nuova soluzione candidata utilizzando la funzione obiettivo per determinarne la qualità.
• Aggiornamento della memoria tenendo conto della nuova soluzione candidata in base alla sua qualità e rispetto alle soluzioni presenti nella memoria.
• Utilizzo di una strategia di selezione, ad esempio mantenendo le soluzioni migliori o rimuovendo quelle peggiori.
• Considerazione di eventuali vincoli specifici del problema.
• Controllo se è stato raggiunto un criterio di stop, come il numero massimo di iterazioni o il raggiungimento di una soluzione soddisfacente.

Restituzione delle soluzioni migliori:

• Restituzione delle soluzioni migliori trovate durante l’esecuzione dell’algoritmo come risultato finale.

Esempio: assegnazione di compiti al personale in azienda

Qui mostriamo un esempio semplicissimo di codice Python che implementa l’algoritmo di search armony per risolvere un problema di pianificazione e scheduling o semplicemente di assegnazione di compiti al personale in azienda. L’esempio considera l’allocazione di risorse per diverse attività, cercando di massimizzare l’utilizzo delle risorse soggette a determinati vincoli.

Le soluzioni sono listate in memoria come dizionari con i seguenti indici: activities, resources e fitness

solution = {“resources”: [], “activities”: [], “fitness”: 0}

I vincoli max_activities_per_resource e max_resources_per_activity rappresentano il numero massimo di attività che possono essere assegnate a una risorsa e il numero massimo di risorse che possono essere assegnate a un’attività, rispettivamente.

La funzione generate_solution() genera soluzioni casuali nel rispetto dei vincoli indicati sopra

La funzione obiettivo calculate_fitness(), in questo caso, per semplicità si limita a penalizzare le soluzioni che implicano due risorse per l’attività E e a premiare le soluzioni che prevedono che la risorsa R1 svolga l’attività C o D

In casi più complessi sarà necessario definire una funzione obiettivo più articolata. Per esempio si può definire una funzione che confronta le competenze richieste per un’attività con le competenze possedute da una risorsa. Se le competenze necessarie sono presenti nella risorsa, la funzione restituirà un valore di compatibilità elevato, altrimenti un valore basso.

In altri casi si può definire una funzione che considera l’agenda o la disponibilità delle risorse e valuta se sono disponibili per svolgere un’attività in un determinato periodo di tempo. In questo caso, una risorsa disponibile riceverà un punteggio di compatibilità elevato, mentre una risorsa occupata o non disponibile riceverà un punteggio basso.

Una funzione di compatibilità basata sull’esperienza è una funzione che considera l’esperienza delle risorse in relazione alle attività specifiche. Ad esempio, se una risorsa ha un’esperienza significativa nel compiere determinate attività, potrebbe ricevere un punteggio di compatibilità più elevato rispetto a una risorsa meno esperta.

La funzione può valutare la capacità o la disponibilità delle risorse per svolgere un’attività specifica in termini di tempo, risorse fisiche o altre limitazioni. Ad esempio, se un’attività richiede l’uso di una risorsa hardware specifica, la funzione di compatibilità verificherà se la risorsa è disponibile e può essere assegnata a tale attività.

Queste sono solo alcune possibili funzioni di compatibilità che possono essere utilizzate per definire le relazioni tra risorse e attività. La scelta della funzione dipenderà dalle specifiche del problema, dai vincoli e dalle caratteristiche delle risorse e delle attività considerate. È importante adattare la funzione di compatibilità in base alle tue esigenze specifiche per ottenere una corretta valutazione delle relazioni tra risorse e attività nel contesto del problema di pianificazione delle risorse che stai affrontando.

Codice python

import random

# Definizione delle variabili
num_solution = 50
num_iterations = 1000

# Definizione delle risorse e delle attività
resources = ["R1", "R2", "R3"]
activities = ["A", "B", "C", "D", "E"]

# Definizione dei vincoli
max_activities_per_resource = 2
max_resources_per_activity = 2

def generate_solution(resources, activities, max_activities_per_resource):
    solution = {"resources": [], "activities": [], "fitness": 0}

    activity_count = {activity: 0 for activity in activities} #dizionario contatore su ogni attività
    resource_count = {resource: 0 for resource in resources} #dizionario contatore su ogni risorsa

    for _ in range(len(activities)):
        random.shuffle(resources)
        for resource in resources:
            if resource_count[resource] < max_activities_per_resource:
                random.shuffle(activities)
                for activity in activities:
                    if activity_count[activity] < max_resources_per_activity:
                        solution["resources"].append(resource)
                        solution["activities"].append(activity)
                        resource_count[resource] += 1
                        activity_count[activity] += 1
                        break
                break
    
    return solution


def calculate_fitness(solution):
    fitness = 0

    for resource, activity in zip(solution["resources"], solution["activities"]):
        if activity == 'E' and resource in ('R1', 'R2'):
            fitness -= 1

        if resource == 'R1' and activity in ('C', 'D'):
            fitness += 1
            
    solution["fitness"] = fitness

    return fitness

# Inizializzazione della memoria
memory = []
for _ in range(num_solution):
    solution = generate_solution(resources, activities, max_activities_per_resource)
    solution["fitness"] = calculate_fitness(solution)
    memory.append(solution)

# Algoritmo di Ricerca dell'Armonia
for _ in range(num_iterations):
    new_solution = generate_solution(resources, activities, max_activities_per_resource)
    new_solution["fitness"] = calculate_fitness(new_solution)

    memory.append(new_solution)
    memory = sorted(memory, key=lambda x: x["fitness"], reverse=True)[:num_solution]

# Restituzione della soluzione migliore
best_solution = max(memory, key=lambda x: x["fitness"])
print("Migliore soluzione: ", best_solution)

Spiegazione del codice

CLICCA SULL’IMMAGINE PER INGRANDIRLA

Il problema della pianificazione dell’assegnazione dei posti letto in un ospedale

Il problema della pianificazione dell’ammissione dei pazienti è un compito complesso che richiede l’assegnazione dei pazienti ai letti delle stanze dell’ospedale, tenendo conto delle loro esigenze mediche e delle loro preferenze. Per risolvere questo problema, viene presentata una soluzione utilizzando l’algoritmo di ricerca dell’armonia.

Questo problema viene trattato in questo studio a cui rimandiamo il lettore
Harmony Search Algorithm for Patient Admission Scheduling Problem

Il problema implica l’assegnazione dei pazienti ai letti delle stanze dell’ospedale. Ci sono diversi vincoli da considerare, come l’equipaggiamento medico nella stanza e l’esperienza medica del personale nella stanza del paziente. Questi vincoli sono classificati in rigidi (hard) e flessibili (soft). La soddisfazione dei vincoli rigidi è necessaria per una soluzione fattibile, mentre le violazioni dei vincoli flessibili dovrebbero essere ridotte al minimo.

La qualità della soluzione viene misurata dalla somma delle violazioni dei vincoli flessibili.

Il problema coinvolge diversi input, come pazienti, stanze, reparti e fasce orarie. Ogni paziente ha attributi specifici, come richieste di trattamento, genere, preferenza della stanza, età e classe. Ogni paziente viene assegnato a un letto in una stanza per un periodo specifico durante il trattamento pianificato. Ogni stanza ha caratteristiche diverse, come l’equipaggiamento medico, la capacità e il reparto di appartenenza. Il reparto ha specializzazioni diverse a diversi livelli di competenza.

La funzione obiettivo consiste nel rispettare i vincoli rigidi e ridurre al minimo le violazioni dei vincoli flessibili, mantenendo al contempo le preferenze mediche o personali dei pazienti. I vincoli rigidi includono l’assegnazione di un solo paziente a un letto in una data fascia oraria, le date di ammissione e dimissione predefinite, la continuità delle visite dei pazienti e la capacità massima delle stanze. I vincoli flessibili includono il rispetto delle politiche di genere delle stanze, l’adempimento delle proprietà richieste e preferite delle stanze per il paziente, la presenza della specializzazione necessaria nel reparto, la corrispondenza tra l’età del paziente e i limiti dell’età del reparto, la riduzione dei trasferimenti tra le stanze e il mantenimento delle preferenze della stanza dei pazienti.

Per semplificare il calcolo della funzione obiettivo, sono state adottate delle fasi di pre-elaborazione. Vengono utilizzate penalizzazioni per le violazioni dei vincoli flessibili, che sono combinate in una matrice di penalità paziente-stanza. Questa matrice viene calcolata una volta leggendo il file di input e include anche le politiche di genere delle stanze.

Mostriamo di seguito un codice python incompleto. L’algoritmo lascia indefinita la funzione obiettivo e la funzione che genera la soluzione casuale vincolata.

Una qualsiasi soluzione è data da una combinazione: paziente (p), stanza (r), fascia oraria (t)
Il paziente può essere maschio o femmina (m/f).

i vincoli rigidi riguardano l’assegnazione garantita di una stanza ad un paziente e il non superamento della capienza della stanza. I vincoli flessibili riguardano il genere e i trasferimenti.

la soluzione casuale generata mediante la funzione generate_random_solution(), quindi deve sottostare ai vincoli rigidi mentre la funzione calculate_fitness() attribuirà un valore alle soluzioni in base ai vincoli flessibili che riguardano il genere dei pazienti. In particolare si premiano le soluzioni che associano alla stessa stanza solo pazienti dello stesso genere e che implicano un minor numero di traserimenti.

Nello studio indicato è esposto un modo per formulare matematicamente i vincoli rigidi e flessibili che permettono al programmatore volenteroso di creare le funzioni mancanti.

Codice da completare

import random

# Definizione dei parametri di PAS e HSA
PAS_parameters = ...  # Inizializzare con i valori tratti dal dataset
HMCR = ...  # Harmonic Memory Consideration Rate
PAR = ...  # Pitch Adjustment Rate
NI = ...  # Numero massimo di improvvisazioni
HMS = ...  # Dimensione della memoria armonica


# Definizione della funzione obiettivo
def calculate_fitness(solution):
    # Calcolo della fitness della soluzione
    fitness = ...
    ...

Premi e penalizzazioni associate ai vincoli flessibili

  return fitness

# Definizione della funzione per generare una soluzione casuale rispettando i vincoli
def generate_random_solution():

    solution =

Generazione della soluzione che rispetti i vincoli rigidi

return solution

# Inizializzazione della memoria armonica HM
HM = []
for _ in range(HMS):
    # Generazione casuale di una soluzione rispettando i vincoli
    solution = generate_random_solution()
    # Calcolo della fitness della soluzione
    fitness = calculate_fitness(solution)
    # Aggiunta della soluzione alla memoria armonica
    HM.append((solution, fitness))
# Ordinamento della memoria armonica in ordine ascendente
HM.sort(key=lambda x: x[1])

# Numero di pazienti
Patients = ...  # Inizializzare con il numero di pazienti

# Iterazione finché non viene raggiunto il numero massimo di improvvisazioni NI
improvisation_count = 0
while improvisation_count < NI:
    # Improvvisazione di una nuova soluzione x'
    x_prime = []
    for j in range(Patients):
        if random.random() <= HMCR:  # Memory consideration
            random_index = random.randint(0, HMS-1)
            random_solution = HM[random_index][0]
            x_prime_j = random_solution[j]
            if x_prime_j is None:  # If no value found in memory for patient j
                x_prime_j = random.choice(Xj)
                if random.random() <= PAR:  # Pitch adjustment
                    x_prime_j = adjust_pitch(x_prime_j)
        else:  # Random consideration
            x_prime_j = random.choice(Xj)

        x_prime.append(x_prime_j)

    # Calcolo della fitness della nuova soluzione
    fitness = calculate_fitness(x_prime)

    # Aggiornamento della memoria armonica HM
    if fitness < HM[-1][1]:  # If new solution is better than worst solution in HM
        HM[-1] = (x_prime, fitness)
        HM.sort(key=lambda x: x[1]) 

    # Incremento del contatore delle improvvisazioni
    improvisation_count += 1

# Soluzione finale
best_solution = HM[0][0]