El algoritmo genético puede optimizar los menús jerárquicos
FORMULACIÓN DEL PROBLEMA
ALGORITMO GENÉTICO
EXPERIMENTOS NUMÉRICOS
CONCLUSIÓN
Descripción general
Formulación
Notación
Tiempo de selección
Tiempo de señalización y tiempo de búsqueda / decisión
Similitud funcional
Granularidad del menú
Función objetiva
Problema de optimizacion
El problema de optimización de los menús jerárquicos se puede considerar como uno que trata de colocar elementos de menú en los nodos de un árbol.
El problema es minimizar el tiempo de recorrido medio con respecto a las frecuencias de búsqueda dadas de diferentes elementos del menú.
I = número de nivel, i = número de orden en hermanos , vl i = nodo de un árbol, M = (V, E) = arbol, V = {vl i} = nodos, E = {eij} = bordes, nodos hojas = nodos terminales, función genérica = Pi, nodos terminales = gi, nodos intermedios = gi o G, conjunto de si = S, n = número total de elementos, li = un elemento del menú
El tiempo de selección de un elemento/nodo del menú en el nivel jerárquico se puede expresar mediante la búsqueda/decisión tiempo y el tiempo de señalamiento.
El tiempo de apuntamiento se puede expresar utilizando la ley de Fitts.
Representamos la similitud funcional del elemento lx y ly usando
una función s(lx, ly) que toma un valor entre 0 y 1.
El menú granularidad de un nodo se define como el total de
número de descendientes.
El problema es minimizar la siguiente función objetiva: f = Tavg + αPs + βPg, donde α y β son constantes que controlan la preferencia de la semejanza funcional y la granularidad del menú.
Cuando se proporcionan elementos de menú que se colocan como hijos de un nodo V. El problema es encontrar la mejor asignación de elementos de menú a los nodos de un árbol que minimice la Ecuación.
El algoritmo genético (GA) es una técnica de búsqueda utilizada en computación para encontrar soluciones exactas o aproximadas a problemas de optimización y búsqueda. GA es un algoritmo metaheurístico que utiliza técnicas inspiradas en la biología evolutiva como herencia, mutación, selección y cruzamiento
Estrategia básica y representación cromosómica
Otras configuraciones de GA
Usamos una GA en estado estacionario, el tamaño de la población es 100, la tasa de mutación es un intercambio por cromosoma. La selección del torneo de tamaño dos se utiliza como método de selección.
Un algoritmo que coloca los elementos de un menú uno por uno
en un noto utilizable puede encontrar una buena solución.
Datos experimentales
Señalar el tiempo y el tiempo de decisión
Datos de frecuencia de uso
Similitud funcional
Resultados
Calculamos el índice de dificultad.
Esto nos dio 28 grupos de índices de dificultad.
Recopilamos datos de frecuencia.
Había 129 nodos terminales en los datos.
Asignamos de tres a cinco palabras a cada función genérica de acuerdo con el manual del usuario del teléfono objetivo
El algoritmo propuesto puede generar un menú con un tiempo medio de selección mas corto. Además, limitar el número de teclas utilizables nos dio mejores menús.
Propusimos un algoritmo basado en GA para minimizar el tiempo medio de selección de elementos del menú que consideran el tiempo de movimiento y el tiempo de decisión. Los resultados preliminares mostraron que el algoritmo puede generar una mejor estructura de menú.