Computazione evolutiva interattiva

Con il termine computazione evolutiva interattiva ci si riferisce a tutti gli approcci che inglobano una valutazione umana all'interno di un algoritmo di computazione evolutiva.[1] Nella formulazione più semplice possibile, un algoritmo di computazione evolutiva interattiva usa un giudizio soggettivo come propria funzione obiettivo. In una definizione più ampia, esso integra un qualsiasi tipo di interfaccia uomo-macchina all'interno di un algoritmo di computazione evolutiva. In linea generale, si situa l'inizio di tale campo di ricerca agli studi di Richard Dawkins sui cosiddetti biomorfi nel 1986.[2]

CategorizzazioneModifica

È possibile categorizzare gli algoritmi di computazione evolutiva interattiva a seconda del loro algoritmo di computazione evolutiva di partenza. Esistono quindi algoritmi genetici interattivi,[3] strategie evolutive interattive,[4] algoritmi di programmazione genetica interattivi,[5] e così via. Una seconda possibile categorizzazione riguarda invece la modalità in cui la valutazione umana è integrata nell'algoritmo stesso:

  • Essa può sostituire completamente la valutazione della funzione obiettivo dell'algoritmo, come nel lavoro già citato di Richard Dawkins.[2] In questo caso, l'utente giudica le soluzioni trovate dall'algoritmo, valutandole esplicitamente con un voto numerico, o implicitamente scegliendo quelle che ritiene migliori.
  • Nel contesto di problemi di ottimizzazione multi-obiettivo, l'utente può guidare la ricerca del fronte di pareto esprimendo le sue preferenze sulle soluzioni trovate.[6] In questo caso si parla di ottimizzazione multiobiettivo interattiva.
  • Infine, l'utente può agire sugli altri elementi del processo di ricerca, ad esempio sulla creazione di nuovi vincoli,[7] sulla formulazione del problema da risolvere,[8] o sulla combinazione delle soluzioni risultanti.[9]

Problematiche e linee di ricercaModifica

La problematica maggiore nell'utilizzo di algoritmi di programmazione evolutiva interattiva si presenta quando l'utente rimpiazza la funzione obiettivo, e riguarda l'affaticamento dell'utente stesso, il quale è tenuto ad esprimere un giudizio su una grande quantità di possibili ipotesi.[1] Una seconda problematica è invece data dal fatto che, in molti campi, un utente non è in grado di discernere soluzioni molto simili fra loro. In questo caso, l'algoritmo non ricerca il punto ottimale nello spazio delle possibili soluzioni, ma una più vasta regione tale per cui l'utente non è in grado di distinguere le soluzioni in essa contenute. Hideyuki Takagi descrive così questo problema:

«Per esempio, si supponga di voler trovare il prossimo modello della Toyota Camry o dell'Honda Accord. L'obiettivo non è determinare un singolo punto [...] ma determinare diversi modelli di automobili che posseggano un effetto simile sulla base dei modelli precedenti.»

(Hideyuki Takagi, Interactive Evolutionary Computation: Fusion of the Capabilities of EC Optimization and Human Evaluation)

La maggior parte delle linee di ricerca sulla computazione evolutiva interattiva sono originate da questi problemi: ad esempio, come scegliere una scala di giudizio ottimale, o come predire i giudizi dell'utente stesso.[10]

ApplicazioniModifica

Gli algoritmi di computazione evolutiva interattiva trovano numerose applicazioni in settori dove non è possibile esprimere una funzione obiettivo in forma analitica.[1] Tra questi, possiamo ricordare:

NoteModifica

  1. ^ a b c Takagi.
  2. ^ a b Dawking.
  3. ^ Kim, H. S., & Cho, S. B. (2000). Application of interactive genetic algorithm to fashion design. Engineering applications of artificial intelligence, 13(6), pp. 635-644.
  4. ^ Herdy, M. (1997). Evolutionary optimization based on subjective selection-Evolving blends of coffee. In 5th European Congress on Intelligent Techniques and soft computing pp. 640-4.
  5. ^ Tokui, N., & Iba, H. (2000). Music composition with interactive evolutionary computation. In Proceedings of the 3rd international conference on generative art, 17(2), pp. 215-226.
  6. ^ Branke et al.
  7. ^ Inoue, T., Furuhashi, T., Fujii, M., Maeda, H., & Takaba, M. (1999). Development of nurse scheduling support system using interactive EA. In Proceedings of the 1999 IEEE International Conference on Systems, Man, and Cybernetics, 1999, Vol. 5, pp. 533-537.
  8. ^ Louis, S. J., & Tang, R. (1999). Interactive genetic algorithms for the traveling salesman problem. Archiviato il 5 marzo 2016 in Internet Archive. In Genetic and Evolutionary Computation Conference(ICGA-99), Vol. 1, pp. 1043-1048.
  9. ^ Levine, D., Facello, M., Hallstrom, P., Reeder, G., Walenz, B., & Stevens, F. (1997). Stalk: An interactive system for virtual molecular docking. Computing in Science and Engineering, 4(2), pp. 55-65.
  10. ^ Ohsaki, M., & Takagi, H. (1998, October). Improvement of presenting interface by predicting the evaluation order to reduce the burden of human interactive EC operators. In Systems, Man, and Cybernetics, 1998. 1998 IEEE International Conference on (Vol. 2, pp. 1284-1289). IEEE.
  11. ^ Cho, S. B. (2002). Towards creative evolutionary systems with interactive genetic algorithm. Applied Intelligence, 16(2), 129-138.
  12. ^ Takagi, H., & Ohsaki, M. (1999). IEC-based hearing aid fitting. In Systems, Man, and Cybernetics, 1999. IEEE SMC'99 Conference Proceedings. 1999 IEEE International Conference on (Vol. 3, pp. 657-662). IEEE.
  13. ^ Cho, S. B. (2004). Emotional image and musical information retrieval with interactive genetic algorithm. Proceedings of the IEEE, 92(4), 702-711.
  14. ^ Cagnoni, S., Dobrzeniecki, A. B., Poli, R., & Yanch, J. C. (1999). Genetic algorithm-based interactive segmentation of 3D medical images. Image and Vision Computing, 17(12), 881-895.

BibliografiaModifica