Graph-theoretic measure for active iGAs: interaction sizing and parallel evaluation ensemble
Pages 985 - 992
Abstract
Since their inception, active interactive genetic algorithms have successfully combat user evaluation fatigue induced by repetitive evaluation. Their success originates on building models of the user preferences based on partial-order graphs to create a numeric synthetic fitness. Active interactive genetic algorithms can easily reduce up to seven times the number of evaluations required from the user by optimizing such a synthetic fitness. However, despite basic understanding of the underlying mechanisms there is still a lack of principled understanding of what properties make a partial ordering graph a successful model of user preferences. Also, there has been little research conducted about how to integrate together the contributions of different users to successfully capitalize on parallelized evaluation schemes. This paper addresses both issues describing: (1) what properties make a partial-order graph successful and accurate, and (2) how partial-order graphs obtained from different users can be merged meaningfully.
References
[1]
Alías, F., Llorà, X., Formiga, L., Sastry, K., and D.E., G. Efficient interactive weight tuning for TTS synthesis: reducing user fatigue by improving user consistency. In Proceedings of ICASSP (Toulouse, France, May 2006), vol. I, pp. 865--868.
[2]
Alm, C. O., and Llorà, X. Evolving emotional prosody. In Proceedings of the Ninth International Conference on Spoken Language Processing (INTERSPEECH 2006) (2006), p. paper 1741.
[3]
Caldwell, C., and Johnston, V. S. Tracking a criminal suspect through face-space with a genetic algorithm. In Proceedings of the Fourth International Conference on Genetic Algorithms (1991), Morgan Kaufmann, pp. 416--421.
[4]
Clark, J., and Holton, D. A. A First Look at Graph Theory. World Scientific, 1991.
[5]
Coello-Coello, C. A. An updated survey of GA-Based Multiobjective Optimization Techniques. Technical report lania-rd-09-08, Laboratorio Nacional de Informática Avanzada (LANIA), Xalapa, Veracruz, México, December, 1998.
[6]
Cristianini, N., and Shawe-Taylor, J. An Introduction to Support Vector Machines. Cambridge Press, 2000.
[7]
Dawkins, R. The blind watchmaker. New York: W. W. Norton, 1986.
[8]
Deb, K., Agrawal, S., Pratab, A., and Meyarivan, T. A Fast Elitist Non-Dominated Sorting Genetic Algorithm for Multi-Objective Optimization: NSGA-II. KanGAL report 200001, Indian Institute of Technology, 2000.
[9]
Formiga, L., and Alías, F. Extracting user Preferences by GTM for aiGA Weight Tuning in Unit Selection Text-to-Speech Synthesis. Lecture Notes in Computer Science, 4507 (June 2007), 654--651.
[10]
Goldberg, D. E. Genetic algorithms in search, optimization, and machine learning. Adison-Wesley, 1989.
[11]
Goldberg, D. E. The design of innovation: Lessons from and for competent genetic algorithms. Kluwe Academic Publisher, 2002.
[12]
Goldberg, D. E., Korb, B., and Deb, K. Messy genetic algorithms: Motivation, analysis, and first results. Complex Systems 3, 5 (1989), 493--530.
[13]
Harary, F. Graph Theory. Addison-Wesley Publishing Company, 1971.
[14]
Harik, G., Lobo, F., and Goldberg, D. E. The compact genetic algorithm. Proceedings of the IEEE International Conference on Evolutionary Computation (1998), 523--528. (Also IlliGAL Report No. 97006).
[15]
Llorà, X., Goldberg, D. E., Ohsawa, Y., Matsumura, N., Washida, Y., Tamura, H., Yoshikawa, M., Welge, M., Auvil, L., Searsmith, D., Ohnishi, K., and Chao, C.-J. Innovation and Creativity Support via Chance Discovery, Genetic Algorithms, and Data Mining. Journal of New Mathematics and Natural Computation 2, 1 (2006), 85--100.
[16]
Llorà, X., Sastry, K., Alıas, F., Goldberg, D. E., and Welge, M. Analyzing active interactive genetic algorithms using visual analytics. In GECCO '06: Proceedings of the 8th annual conference on Genetic and evolutionary computation (New York, NY, USA, 2006), ACM, pp. 1417--1418.
[17]
Llorà, X., Sastry, K., Goldberg, D. E., Gupta, A., and Lakshmi, L. Combating user fatigue in iGAs: Partial ordering, support vector machines, and synthetic fitness. In Proceedings of Genetic and Evolutionary Computation Conference 2005 (GECCO'05) (Washington DC, USA, June 2005), ACM, pp. 1363--1370.
[18]
Mitchell, T. M. Machine Learning. McGraw Hill, 1997.
[19]
Sastry, K. Evaluation-relaxation schemes for genetic and evolutionary algorithms. Master's thesis, University of Illinois at Urbana-Champaign, General Engineering Department, Urbana, IL, 2001. (Also IlliGAL Report No. 2002004).
[20]
Shawe-Taylor, J., and Cristianini, N. Kernel Methods for Patter Analysis. Cambridge Press, 2004.
[21]
Takagi, H. Interactive evolutionary computation: Fusion of the capabilities of ec optimization and human evaluation. In Proceedings of the IEEE (September 2001), vol. 89, pp. 1275--1296.
[22]
Witten, I. H., and Frank, E. Data Mining: practical machine learning tools and techniques with java implementations. Morgan Kaufmann, 2000.
Index Terms
- Graph-theoretic measure for active iGAs: interaction sizing and parallel evaluation ensemble
Recommendations
On the ensemble of optimal dominating and locating-dominating codes in a graph
Let G be a simple, undirected graph with vertex set V. For every v V , we denote by N ( v ) the set of neighbours of v, and let N v ] = N ( v ) { v } . A set C V is said to be a dominating code in G if the sets N v ] C , v V , are all nonempty. A set C ...
A Note on the Inducibility of $$4$$4-Vertex Graphs
There is much recent interest in understanding the density at which constant size graphs can appear in a very large graph. Specifically, the inducibility of a graph $$H$$H is its extremal density, as an induced subgraph of $$G$$G, where $$|G| \...
Smaller Universal Targets for Homomorphisms of Edge-Colored Graphs
Computing and CombinatoricsAbstractFor a graph G, the density of G, denoted D(G), is the maximum ratio of the number of edges to the number of vertices ranging over all subgraphs of G. For a class of graphs, the value is the supremum of densities of graphs in . A k-edge-colored ...
Comments
Information & Contributors
Information
Published In
July 2008
1814 pages
Copyright © 2008 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 12 July 2008
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
Acceptance Rates
Overall Acceptance Rate 1,669 of 4,410 submissions, 38%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 123Total Downloads
- Downloads (Last 12 months)1
- Downloads (Last 6 weeks)0
Reflects downloads up to 08 Mar 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in