Please enable JavaScript.
Coggle requires JavaScript to display documents.
Genetic Algorithm Can Optimize Hierarchical Menus - Coggle Diagram
Genetic Algorithm Can Optimize Hierarchical Menus
Introdución
Los menús jerárquicos son uno de los controles principales para emitir comandos en GUI.
El rendimiento del menú depende de muchos factores: estructura, diseño, colores, etc.
Se desarrollaron algoritmos de optimización para minimizar la búsqueda prevista en tiempos de acuerdo con las frecuencias de búsqueda
Formulación del problema
El problema de optimización de los menús jerárquicos se puede considerar como uno que se ocupa de colocar elementos de menú en los nodos.
El problema es minimizar el tiempo medio de recorrido con respecto a las frecuencias de búsqueda dadas de diferentes elementos del menú.
Se usa esta métrica para evitar colocar elementos con poca similitud en el mismo submenú
Granularidad del menú
Similitud Funcional
Formulación
Nodos intermedios
Nodos terminales
Funciones genéricas
No puede tener hijos
Granularidad del menú
El total del número de nodos descendientes
Es la suma de los nodos
Tiempo
El tiempo de selección de un elemento de menú - nodo de jerarquía.
Se puede expresar mediante la búsqueda/ decisión
Problema de optimización
El problema es encontrar la mejor asignación de elementos de menú a los nodos de un árbol que minimice la ecuación
Similitud Funcional
Usando una función que toma valor entre 0 y 1
Algoritmo Genético
Es una técnica de búsqueda utilizada en computación para encontrar soluciones exactas o aproximadas de optimización y problemas de búsqueda.
GA es un algoritmo metaheurístico que utiliza técnicas inspiradas en la biología evolutiva como la herencia
Técnica de búsqueda utilizada para encontrar soluciones exactas o aproximadas a problemas de optimización y búsqueda.
Estrategia básica y representación de cromosomas
Un cromosoma del AG es una secuencia de li; i,e.., es decir, un cromosoma puede representarse como una permutación de números
De acuerdo con la permutación, asigne uno a uno los elementos del menú li a un nodo utilizable que tenga el menor numero de nodos.
Si se asigna una función genérica a un nodo este no puede tener hijos y el nodo que esta debajo del nodo asignado se marca como inutilizable
Otras configuraciones de AG
Utilizamos un operador de cruce que no genera un cromosoma inválido.
Utilizamos la mutación de intercambio como operador de mutación
Los operadores de cruce y mutación no generan cromosomas inválidos.
Experimentos numéricos
Resultados
Caso 1
Uso típico
La anchura máxima W fue de 16
Caso 2
Amplitud Limitada
Se fijó la amplitud (W) en 12,9 y 6
Datos experimentales
Tiempo de señalización y tiempo de decisión
Índice de dificultad para los pares de teclas de 24 x 24
tpi= 192+63 log2(Ai/Wi +1)(ms)
Datos de frecuencia de uso
El primer autor registró el uso diario de cada función durante dos meses.
Se generan los datos de frecuencia de uso a partir del registro
129 nodos terminales en los daatos
Similitud funcional
Se asigna de tres a cinco palabras a cada función genética de acuerdo con el manual de usuario del teléfono objetivo
Discusión y trabajo duro
Los experimentes muestran que el algoritmo propuesto puede generar mejores jerarquías de menús para el teléfono objetivo.
Los resultados preliminares son prometedores se aplicará el algoritmo a una mayor variedad.