Please enable JavaScript.
Coggle requires JavaScript to display documents.
El algoritmo genético puede optimizar los menús jerárquicos, Integrantes:…
El algoritmo genético puede optimizar los menús jerárquicos
Formulación del problema
Descripción general
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.
No podemos organizar arbitrariamente el menú simplemente por eficiencia. Debemos respetar las relaciones semánticas entre los elementos.
Formulación
Notación
Hay dos tipos de elementos en el menú o nodos en el árbol. Un tipo son los nodos terminales que corresponden a funciones genéricas y el otro son los nodos intermedios. Los nodos terminales no pueden tener hijos.
Elementos que corresponden a la funciones genéricas son menores que N, y algunos elementos/nodos son elementos/nodos intermedios que tienen submenú(s) como un hijo o hijos.
Tiempo de selección
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.
Tiempo de señalización y tiempo de búsqueda / decisión
Suponemos que el tiempo de búsqueda/decisión en un nivel l nodo que tiene n elementos puede ser expresado como reportado por Cockburn.
Similitud funcional
Representamos la similitud funcional del elemento lx y ly usando una función s(lx, ly) que toma un valor entre 0 y 1.
Granularidad del menú
El menú granularidad de un nodo se define como el total de número de descendientes.
Función objetiva
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ú.
Problema de optimización
Cuando los elementos del menú que se colocan como hijos de un nodo V se dan, la ubicación que minimiza el tiempo de apunte promedio es sencillo. Por tanto, el problema es encontrar la mejor asignación de elementos de menú a los nodos de un árbol que minimiza la ecuación.
Algoritmo Genético
Descripción general
El algoritmo genético (GA) es una técnica de búsqueda utilizada en la informática para encontrar soluciones exactas o aproximadas a la 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, la selección y el cruce.
Estrategia básica y representación cromosómica
Debido a que en estudios anteriores demostraron que la amplitud era preferible a la profundidad, utilizamos una especie de búsqueda en amplitud como el núcleo del GA propuesto.
Un algoritmo que coloca los elementos de un menú uno por uno en un noto utilizable puede encontrar una buena solución.
Experimentos Numéricos
Datos experimentales
Datos de frecuencia de uso
Recopilamos datos de frecuencia de uso de la siguiente manera. El primer autor registró el uso diario de cada función durante dos meses, y generamos los datos de frecuencia de uso del registro. Había 129 nodos terminales en los datos.
Similitud funcional
Asignamos de tres a cinco palabras a cada función genérica de acuerdo con el manual del usuario.
Resultados
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. Esto se debe en parte a que el tiempo de búsqueda/decisión es proporcional a log2(n), donde n es el número de elementos.
Conclusión
Propusimos un algoritmo basado en GA para minimizar el tiempo medio de selección de los elementos del menú que consideran el tiempo de movimiento y tiempo de decisión.
Los resultados preliminares mostraron que el algoritmo puede generar una mejor estructura del menú. El objetivo del algoritmo propuesto no se limita a los teléfonos y se puede aplicar a otros tipos de menús.
Integrantes:
Kevin Guzmán, Juan Fernando Polanco