Un algoritmo genetico è un approccio corretto a questo problema?

3

Sto provando a calcolare un insieme di elementi che producono il massimo danno in uscita in un videogioco. Ci sono circa 50 articoli diversi, tra cui puoi scegliere 6. Esistono tutti i tipi di condizioni che ogni articolo crea. Sto scrivendo una piccola app in javascript che calcola il tuo danno in base agli articoli. Potrei utilizzare un algoritmo genetico per scoprire quali combinazioni di articoli sono le più forti? O la forza bruta è accettabile per questa dimensione di un problema? O c'è un altro modo?

    
posta Shawn 15.04.2011 - 02:40
fonte

5 risposte

7

Ci sono 50 elementi, di cui puoi avere 6 alla volta, il che significa che hai 50 * 49 * 48 * 47 * 46 * 45 = 11,441,304,000 combinazioni uniche di elementi (penso che la mia matematica sia giusta). Poiché nikie indica di seguito nei commenti, se l'ordine degli articoli non ha importanza (probabilmente no), questo il numero è ridotto a combinazioni 50 * 49 * 48 * 47 * 46 * 45 / (1 * 2 * 3 * 4 * 5 * 6) = 15,890,700 , un importo molto gestibile. Questo potrebbe essere un po 'troppo per la forza bruta ogni volta , ma d'altra parte, se gli elementi non cambiano, è possibile eseguire questo calcolo una volta e memorizzarlo da qualche parte ( localStorage , qualunque sia) .

L'algoritmo genetico sembra eccessivo, dato che penso che ci vorrà troppo tempo per darti un set ideale rispetto alla forza bruta. Supponendo che non è possibile eseguirlo una volta e memorizzarlo, vorrei capire se c'è un modo per ottimizzare l'ordine degli articoli prima di eseguire la query e sfoltire alcune delle combinazioni deboli e ottenere quel numero un po 'prima di eseguirlo il tuo algoritmo.

    
risposta data 15.04.2011 - 02:53
fonte
4

L'IT dipende da quali sono gli elementi e le altre variabili del tuo problema, ma puoi probabilmente fare un buon uso dell'euristica qui.

Fondamentalmente, c'è probabilmente un modo per escludere alcuni elementi subito perché la loro distribuzione delle statistiche non corrisponde al tuo personaggio. Quindi puoi probabilmente fare cose del tipo "La statistica più importante è il danno (per esempio), iniziamo calcolando il set di articoli che massimizza questa statistica, quindi vediamo se scambiamo elementi di questo set con altri non precedentemente conservati per vedere se c'è un miglioramento nel rendimento generale ".

Ci sono molti modi per affrontare questo tipo di problema, ma qui gli algoritmi genetici sembrano un po 'eccessivo. Vuoi condividere più informazioni specifiche per il tuo problema? Forse possiamo aiutarti meglio allora!

In realtà, il modo in cui probabilmente mi avvicinerei sarebbe precalcolare un "punteggio" per ogni oggetto, quindi ordinarli e selezionare i 6 punteggi più alti.

Lascio comunque il resto della mia risposta come riferimento.

    
risposta data 15.04.2011 - 04:09
fonte
1

un GA è un approccio, se la forza bruta non è pratica

permutazioni di euristiche e calcolo / simulazione degli effetti possono anche essere praticabili; c'è un buon precedente per questo approccio in l'uso di Doug Lenat di Eurisko per progettare navi per i tornei Traveller

    
risposta data 15.04.2011 - 05:32
fonte
0

Penso che la domanda abbia bisogno di spiegazioni in più. Se tutto ciò che conta è scegliere 6 elementi su 50 che causano il massimo danno, quindi se si ordinano gli elementi in ordine decrescente di capacità di danno e si scelgono i primi 6, ciò avverrà. Tuttavia, sospetto che ci sia una maggiore complessità associata alla scelta di questi 6 articoli, ad esempio un costo associato a ciascun articolo scelto. In tal caso, sembra un problema con lo zaino e può essere rapidamente ridotto utilizzando la programmazione dinamica, per la dimensione del problema che hai descritto. Il problema dello zaino è il seguente: qual è l'insieme ottimale di elementi (su un totale di 50) da trasportare in uno zaino per massimizzare i benefici (nel tuo caso, danno) e rimanere sotto un certo costo (forse punti totali disponibili per scegliere gli oggetti ). Nel tuo caso - se questo numero supera i 6, puoi eliminare il minimo danno causando oggetti fino a raggiungere esattamente 6 articoli. Nota, questa sarà una soluzione ottimale.

    
risposta data 28.02.2014 - 06:30
fonte
-1

Se un algoritmo genetico è adatto dipende dalle caratteristiche degli oggetti. Se oggetti simili hanno un danno simile, sarebbe più adatto che se ci fossero oggetti che improvvisamente alterano il danno, ma sono solo leggermente diversi dagli altri con un danno molto inferiore / superiore. Ad esempio, in genere STR aumenterà il tuo danno, che probabilmente l'algoritmo inizierà a favorire quegli oggetti con un danno elevato, ma potrebbe non trovare mai una soluzione con quel timone brillante funky che non dà alcun danno, ma aggiunge metà della tua intelligenza moltiplicata per la tua destrezza per te forza.

Prova ad immaginare lo spazio della soluzione e in che modo l'algoritmo "viaggerà" da queste parti. Ho paura che sia altamente possibile rimanere bloccati con una soluzione lontana dall'ottimo.

    
risposta data 15.04.2011 - 10:46
fonte

Leggi altre domande sui tag