Ocena podobieństwa drzew strategii generowanych za pomocą programowania genetycznego

• Autorzy: Lach E. , Hetman M.

Warianty tytułu

EN

The similarity measure for strategy trees generated by means of genetic programming

• Języki publikacji: PL

Abstrakty

PL

W pracy zaprezentowano nowy algorytm oceny stopnia podobieństwa drzew strategii, opisujących zachowanie trójwymiarowych postaci wirtualnych. Algorytm został użyty w trakcie automatycznego generowania strategii postaci, za pomocą programowania genetycznego w celu otrzymania bardziej zróżnicowanych populacji strategii z większą liczbą dostępnych ścieżek poszukiwań.

EN

The paper proposes new algorithm for measuring a similarity of strategy trees, describing behaviors of the three-dimensional virtual characters. The obtain measure is used in automatic generation of characters’ strategies by means of genetic programming. The aim of the algorithm is to create more diversified populations with many different paths to explore.

Słowa kluczowe

PL

programowanie genetyczne; uczenie maszynowe; animacja behawioralna; porównywanie drzew

EN

genetic programming; machine learning; behavioral animation; tree comparison

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Studia Informatica
• Rocznik: 2013
• Tom: Vol. 34, nr 1
• Strony: 75--89
• Opis fizyczny: Bibliogr. 11 poz.

Twórcy

autor

Lach E.

• Politechnika Śląska, Instytut Informatyki, ul. Akademicka 16, 44-100 Gliwice, Polska

autor

Hetman M.

• Politechnika Śląska, Instytut Informatyki, ul. Akademicka 16, 44-100 Gliwice, Polska

Bibliografia

• 1. Zhang K., Shasha D.: Simple fast algorithms for the editing distance between trees and related problems. SIAM Journal on Computing, Vol. 18, No. 6, Philadelphia 1989.
• 2. Touzet H.: Comparing similar ordered trees in linear-time. Journal of Discrete Algorithms, Elsevier Science Publishers, Vol. 5, No. 4, Amsterdam 2007.
• 3. Jiang T., Wang L., Zhang K.: Alignment of trees—an alternative to tree. Theoretical Computer Science, Elsevier, Vol 143, No. 1, 1995.
• 4. Nierman A., Jagadish H. V.: Evaluating Structural Similarity in XML Documents. ACM-SIGMOD Intl. Workshop on Web and Databases, Madison 2002.
• 5. Neamtiu I., Foster J. S., Hicks M.: Understanding source code evolution using abstract syntax tree matching. ACM SIGSOFT Software Engineering Notes, Vol 30, No. 4, New York 2005.
• 6. Lach E., Chaja T.: Składowe oceny animacji wirtualnych postaci ludzkich. Studia Informatica, Wyd. Pol. Śląskiej, Vol. 33, No. 1 (104), Gliwice 2012.
• 7. Hamming R. W.: Error detecting and error correcting codes. Bell System Technical Journal 29, 1950.
• 8. Levenshtein V. I.: Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Doklady, Vol. 10, No. 8, 1966.
• 9. Koza J.R.: On the programming of computers by means of natural selection. MIT Press, 1996.
• 10. Lach E.: fACT – animation framework for generation of virtual characters. International Conference on Information Technology, 2008.
• 11. Gagné Ch., Parizeau M.: Genericity in Evolutionary Computation Software Tools: Principles and Case Study. International Journal on Artificial Intelligence Tools, Vol. 15, No. 2, 2006.