Ottimizzazione di un problema di knpasack modificato

RAM

8. Altri componenti.

Figura 9 – Elenco degli elementi per il componente “Processori” su foglio Excel

3.2 Espressione dell’utilità dei componenti in base alle prestazioni

In questo paragrafo vedremo come, per ogni elemento dei componenti presi in esame, siamo giunti ad un valore di utilità

soggettivo effettuando le dovute ricerche e cercando di vestire i panni del profilo di utilizzatore considerato. In linea

generale, abbiamo valutato l’utilità come media pesata dei valori delle caratteristiche del componente, normalizzando i

valori della caratteristica del componente rispetto al suo valore migliore e pesandolo rispetto a , essendo il

k i , ,

peso della caratteristica dell’i-esimo componente, con:

k-esima ∑ 1 ∀ 1,2, … , (4)

,

Vediamo nel dettaglio come sono stati scelti tali pesi per ognuno dei componenti considerati.

Figura 10 – Esempio di calcolo di utilità per il componente “Processori” su foglio Excel 13

Ottimizzazione di un problema di knapsack modificato con algoritmo genetico

C. Scimeca, R. Scimeca

Capitolo 3 – Applicazione reale: scelta dei componenti di un PC

3.2.1 Processori e Case 5

La lista di processori comprende 199 elementi, ai quali sono associate le seguenti caratteristiche : frequenza, numero di

L’utilità è dunque calcolata sulla base di frequenza e n° di core. La caratteristica più importante è la frequenza,

core. U CPU

poiché esprime in maniera diretta la potenza di calcolo del processore, mentre il n° di core riduce ulteriormente i tempi

di calcolo permettendo di processare in parallelo più task. Pertanto abbiamo assegnato rispettivamente pesi 0.6 e 0.4.

Il è la parte che racchiude tutte le componenti interne. Con 99 dati, sono state calcolate le utilità in base al numero

case

di slot da 3,5” disponibili (i.e. quelli che alloggiano i dischi) e sulla potenza dell’alimentatore integrato (se presente) con

pesi 0.85 e 0.15. Tale scelta è stata motivata dal fatto che spesso l’alimentatore integrato è un vantaggio a ci si potrebbe

trovare ad averne uno sottodimensionato.

3.2.2 Scheda madre

La lista delle schede madre consta di 116 elementi ai quali sono associate le seguenti caratteristiche: slot R.A.M.

e L’utilità è calcolata sulla base di quanti slot R.A.M. sono disponibili

disponibili quantità di R.A.M. massima supportata.

al fine di garantire un ciclo di vita esteso alla macchina (i.e. con un eventuale futuro upgrade) e sulla quantità massima di

R.A.M. installabile (per lo stesso motivo di cui sopra). In particolare sono stati scelti rispettivamente i pesi 0.3 e 0.7.

3.2.3 Scheda video e Alimentatore

Per la scheda video si dispone di 198 dati e l’utilità associata è stata calcolata a partire della velocità del processore grafico

e sulla dimensione della memoria video dedicata con pesi 0,55 e 0,45. L’utilità dell’alimentatore è valutata invece sulla

base di una sola caratteristica, i Watts forniti, a cui pertanto è associato un peso unitario.

3.2.4 Disco rigido

Per tale categoria si sono scelti soltanto dischi tradizionali (i.e. magnetici). Sono disponibili 199 modelli, a ognuno dei

quali è associata la (in r.p.m.), la espressa in Gb e la L’utilità sintetizza i valori delle

velocità capacità cache.

caratteristiche rispettivamente con i pesi 0.5, 0.3 e 02.

3.2.5 Random Access Memory

Le caratteristiche associate ad ognuno dei 199 elementi presenti in lista sono: (in Mhz) e (in GB). I

velocità dimensione

pesi associati a velocità e dimensione sono rispettivamente 0.35 e 0.65. Tali scelte sono motivate dal fatto che, se la

5 Naturalmente il prezzo del componente è escluso dalla media pesata. 14

Ottimizzazione di un problema di knapsack modificato con algoritmo genetico

C. Scimeca, R. Scimeca

Capitolo 3 – Applicazione reale: scelta dei componenti di un PC

R.A.M. viene sovraccaricata, il computer utilizzerà una parte di memoria dell’hard (la molto più lenta,

disk swap),

causando un drastico calo delle prestazioni. Pertanto in tali condizioni la velocità della R.A.M. è ininfluente.

3.2.6 Altri componenti

Tra le altre componenti sono presenti molte altre parti che servono a completare quasi del tutto la lista dei componenti di

cui necessita un calcolatore elettronico. Per essi la descrizione è molto più breve:

Con 99 dati, l’utilità è calcolata sulla base del rapporto risoluzione/grandezza.

Monitor.

o Si dispone di 72 modelli a disposizione, l’utilità è basata su e con pesi pari

Speakers. configuration total wattage

o a 0.5 ciascuno.

L’utilità dei 90 differenti modelli è basata unicamente sulla capacità.

Ups.

o

Naturalmente l’algoritmo potrebbe estendersi ad numero di componenti maggiore (si ricordi che nell’applicazione del

Capitolo 2 si è posto mentre in questo caso sono in totale 10).

n_components=50,

3.3 Adattamento del modello e dell’algoritmo

3.3.1 Parametri scelti e generazione della popolazione iniziale

Naturalmente in questo caso i dati non vanno generati, ma bisogna piuttosto prendere in input i dati collezionati. Il primo

problema che sorge allora nell’adattare l’algoritmo del Capitolo 2 a questa applicazione è il fatto che il parametro n_el

non è costante per ogni componente, ma è piuttosto un vettore (n_components), dove (i) è pari al numero di dati

n_el n_el

che si dispone per l’i-esimo componente. Questo ha delle implicazioni dirette sulla generazione della popolazione iniziale.

max (qui si è scelto

Innanzitutto bisogna scegliere come dimensione della popolazione un valore che sia più alto di

di porre = 240, a fronte di = 199).

pop n_el_max

Figura 11 – Scelta dei parametri e importazione dei dati da file di testo .txt 15

Ottimizzazione di un problema di knapsack modificato con algoritmo genetico

C. Scimeca, R. Scimeca

Capitolo 3 – Applicazione reale: scelta dei componenti di un PC

Si ricorda che ciò che si vuole ottenere con una opportuna generazione della popolazione iniziale è fare in modo che tutti

gli elementi di ogni componente siano inizialmente presenti almeno una volta in un cromosoma e, solamente dopo,

eventualmente esclusi per lasciare spazio solo agli elementi migliori. Il seguente screenshot mostra come ci si è riusciti.

Figura 12 – Generazione della popolazione iniziale nell’algoritmo applicativo

In breve, ciò che si è fatto è riempire la popolazione per colonna con un numero progressivo pari all’indice di riga fino

alla riga poi con numeri random compresi tra 1 ed dopodiché si riempiono le righe da +1 sino

n_el(j), n_el(j); n_el_max

a con valori random (sempre compresi tra 1 ed ed infine si mischiano i geni trovati esattamente come prima,

pop n_el(j))

ma con un numero di scambi più elevato data la maggiore dimensione di n_el_max.

3.3.2 Frontiere, crossover e mutazione

Una volta generata correttamente la popolazione iniziale, il calcolo delle frontiere ed il crossover non richiedono ulteriori

accorgimenti. Infatti le operazioni necessarie per l’assegnazione delle frontiere sono esattamente le stesse di prima, mentre

per il tipo di crossover scelto (trasferimento di blocchi di geni) non può in alcun modo prevedere la generazione di

soluzioni non ammissibili. Anche in questo caso si è utilizzata la (3) per la scelta del parametro (in Figura 11 può

n_gen

vedersi come = =120).

n_gen pop/2

Anche per quanto riguarda la mutazione non vi sono grandi stravolgimenti. Tuttavia un piccolo accorgimento è necessario:

dopo aver selezionato i cloni (o gli individui troppo simili) da mutare, è necessario generare al suo posto un cromosoma

16

Ottimizzazione di un problema di knapsack modificato con algoritmo genetico

C. Scimeca, R. Scimeca

Capitolo 3 – Applicazione reale: scelta dei componenti di un PC

casuale; questo significa che per ogni – esimo gene bisogna fare attenzione al fatto che il numero estratto debba esser

j

compreso tra 1 ed In figura vediamo questa modifica opportunamente evidenziata.

n_el(j). Figura 13 – Processo di mutazione nell’algoritmo applicativo

3.4 Risultati

Con i dati collezionati, effettuando il con un numero di iterazioni pari ad = 500, i risultati ottenuti sono quelli

run iter

mostrati di seguito (Figura 15). Anche in questo caso si osserva un incremento dei valori medio, massimo e minimo delle

prestazioni ed un decremento di quelli di costo. Questa volta non si presenta affatto il problema della popolazione clonata:

si ottengono invece ben 36 soluzioni ottime (ovvero cromosomi della popolazione finale appartenenti all’ottimo

paretiano). Le soluzioni, come può vedersi dal grafico a pagina successiva, sono abbastanza diversificate: questo rende

l’insieme delle soluzioni in grado di soddisfare le preferenze/esigenze del particolare utilizzatore dell’algoritmo.

Mostriamo, a titolo di esempio, 3 soluzioni molto distanti tra loro nella frontiera di Pareto, rispettivamente la prima con

utilità e costo relativamente bassi, la seconda con prestazioni superlative ma elevato costo e la terza con costo complessivo

ed utilità “intermedi” (i valori possono leggersi in Figura 14 a pagina successiva). Naturalmente il valore letto nel gene

rappresenta un numero identificativo del particolare elemento scelto di quel componente, e pertanto poi andrà selezionato

il modello corrispondente nella lista:

1. Soluzione n°9, con cromosoma [29-58-68-15-97-84-164-48-57-59], a cui corrispondono i seguenti modelli:

Processore “Athlon II X2 240”, Case “Apex TM-302-3”, Scheda M. “ASRock X99 Extreme 6/ac”, Scheda V. “MSI

17

Ottimizzazione di un problema di knapsack modificato con algoritmo genetico

C. Scimeca, R. Scimeca

Capitolo 3 – Applicazione reale: scelta dei componenti di un PC

GT 710 1 GD3H LP”, PowerSupp. “Pure Power L8 500W”, Storage “Toshiba DT01ACA300”, RAM “G.Skill

TridentZ Series”, Monitor “Acer S220HQLAbd”, Speakers “Gear Head SP2000URED”, UPS “CyberPower

CP600LCD”.

2. Soluzione n°16, a cui corrisponde il valore più alto di utilità trovato (per veri “spendaccioni”!), con cromosoma [18-

30-80-116-94-150-58-95-21-66].

3. Soluzione n°11, con cromosoma [44-34-39-143-59-22-176-29-26-63].

Scheda Scheda

N° Costo Utilità Processore Case PowerSupp. Storage RAM Monitor Speakers Ups

M V

1 1.003,99 € 3,81801 15 34 39 15 120 90 110 33 71 49

2 933,34 € 3,21263 26 98 91 143 91 148 110 33 71 49

3 2.891,38 € 5,89899 44 89 46 54 106 111 38 92 26 90

4 2.636,40 € 5,