Métodos heurísticos de optimización geométrica
Iluminación óptima de polígonos

Por: Adolfo Luis Fernández García-Redondo
email: aluisf@wanadoo.es

  2. Manual de manejo de la interfaz de usuario

    2.3 Método del Gradiente

 

    El proceso de introducción del polígono es el mismo que el empleado en el método de Fuerza Bruta. Elijamos el método ‘Gradiente’ pulsando sobre la marca adecuada como indica la flecha, Figura 2 Al pasar de un método a otro los puntos y los polígonos de visibilidad correspondientes son eliminados de la pantalla dejándonos tan solo el polígono que nosotros introducimos. Es el mismo efecto que si hubiésemos pulsado el botón ‘Borrar’. Vamos a mostrar dos formas distintas de aplicar este método heurístico. Por una parte si seleccionamos la opción de posicionamiento ‘Manual’ seremos nosotros los que nos encargaremos de posicionar los focos desde donde queremos que parte el proceso de búsqueda de la posición más óptima del foco. En una segunda parte delegaremos esa tarea de selección de puntos iniciales de búsqueda al ordenador que los seleccionará de forma aleatoria dentro del polígono para ello deberemos de marcar el posicionamiento ‘Automático’. Si seleccionamos esta forma, automática, nos permitirá introducir el número de puntos que deseamos que el ordenador generé como puntos de partida, no se aconseja el uso de un número elevado pues ese método heurístico conlleva el cálculo de 8 polígonos de visibilidad por cada punto generado. Fig 1

 


Fig. 1 Por cada punto generado en este método heurístico se generan ocho puntos (norte, sur, este , oeste, noroeste, noreste, sureste y suroeste)

 

 
Fig.2 Seleccionamos el método del ‘Gradiente’.

 
    Si seleccionamos el método de posicionamiento ‘Manual’ lo que debemos hacer seguidamente es pulsar sobre el botón ‘Situar focos’ , Fig. 3 ,que nos permite abandonar el modo de dibujo del polígono y entrar en el modo de ‘situación de focos’. Veremos que el botón aparece marcado en un color azulado más oscuro para indicarnos que estamos en modo de ‘situación de focos’. Ahora sólo debemos ir marcando con el botón izquierdo los puntos de arranque del método dentro del polígono.. Si no hubiésemos pulsado dicho botón y hubiésemos pulsado con el botón izquierdo del botón sobre el ‘Área de dibujo’ hubiésemos generado un nuevo vértice del polígono. En cualquier momento podemos volver a pulsar el botón ‘Situar focos’ que quedará desmarcado y volviendo a su color original lo cual nos permitirá añadir algún vértice más al polígono.

 
Fig. 3. Indica que estamos en modo de ‘situación de focos’

 


Fig. 4 Tras la pulsación de ‘Situar focos’ y selección de focos.

 
    Como se aprecia en la Fig. 4 hemos seleccionado 3 focos. Al lado de la etiqueta ‘Manual’ vemos un contador que va aumentando según vamos pulsando los distintos focos deseados. Ahora solo resta pulsar el botón ‘Calcular’ para que el proceso se inicie. En se momento veremos como los puntos se van moviendo, se va eligiendo de entre los 8 puntos el que mayor área ilumina y eso es lo que provoca el movimiento, ir hacia el mejor. Si en algún momento no se llega a obtener mejora alguna de una generación a otra eso implicará que hemos alcanzado un máximo local y no debemos seguir intentándolo con ese punto. Continuaremos así hasta que todos los puntos hayan alcanzado un máximo local. En ese momento se elegirá de entre todos los máximos locales el mejor de todos ellos y lo elegiremos como el punto óptimo de iluminación del polígono. Si en algún momento se llega a alcanzar un 100% de iluminación del polígono el algoritmo se detiene y se declara a ese punto como el óptimo de iluminación.
    El punto óptimo de iluminación será marcado en morado mientras los otros puntos serán marcados en azul. El polígono de visibilidad será dibujado en azul. Las áreas del polígono original y la iluminada serán mostradas en la parte inferior, así como el porcentaje en este caso hemos obtenido un 73,05% del área original del polígono iluminada. Fig. 5


Fig. 5. Polígono de visibilidad desde el punto óptimo encontrado
por este método heurístico

    Si marcamos la opción de ‘Muestra Pol. Visib.’ Se irán mostrando los polígonos de visbilidad de los mejores de cada generación. Fig 6. Si volviésemos a pulsar en este instante el botón de calcular se nos avisará de que debemos introducir nuevos puntos iniciales.

 

Fig. 6 Si pulsamos sobre la opción de ‘Muestra Pol. Visib.’

 

    Ahora ya sólo nos queda ver para el caso en el que usemos posicionamiento ‘Automático’. Notaremos que al pulsar sobre el método de posicionamiento ‘Automático’ el botón de ‘Situar focos’ pasa a un modo en el que no es seleccionable. Fig. 7

 

Fig. 7 Estamos en modo de posicionamiento Automático

 

    Hemos introducido un 3 en el apartado de Nº de puntos porque deseamos que sean 3 los ptos. aleatorios que sean generados. Pulsamos el botón ‘Calcular’ y dejamos que se inicie el proceso. El resultado obtenido es el que se muestra en la figura. 8

 


Fig. 8. Resultado final tras el proceso de generación con posicionamiento ‘Automático’