Dudas 2DMP con HC
Me llegó este correo. Las respuestas les pueden servir. Salu2!
Pregunta:
Buenas,
tengo unas dudas en cuanto a la función objetivo que planteaste en tus diapos:
Deben tomar en consideración:
– Prohibir atravesar obstáculos.
– Favorecer caminos más cortos.
– Favorecer caminos que “terminen” más cerca del punto final.
supongo que uno puede modelar el problema como uno quiera, y yo lo pensé usando como movimiento el cambiar un 0 por 1 de alguna celda adyacente a la posición actual, pero el problema con eso es que no sé como cumplir la segunda condición (Favorecer caminos más cortos). Es necesario cumplir con esas y sólo esas condiciones? o me recomiendas usar otro método?
Respuesta:
Algo que puedes hacer es ignorar los caminos más cortos en un comienzo, aceptando cualquier solución que termine “cerca” del objetivo, o en el objetivo.
Posteriormente, si encuentras otras soluciones con el mismo fitness de la mejor solución que has encontrado hasta ahora, y esta tiene un camino más corto que ese óptimo local, entonces reemplaza tu óptimo local por esta nueva solución. Así, a medida que encuentras soluciones a la larga vas a favorecer las más cortas, sin penalizar las que lleguen más lejos.
Pregunta:
Otra cosa, a mi me tocó HC w/restart + FI, mi problema es cómo genero las soluciones aleatorias, mando al robot a una posición random en el tablero? o tengo que partir siempre desde la posición de abajo a la derecha?
Respuesta:
Es obligatorio llegar desde abajo derecha hasta arriba izq. Tomando la definición de HC académica, suena raro poder obtener una solución distinta con los restarts.
Tienes que cambiar el modelamiento. Una posibilidad es:
-De manera random, o con backtracking intentar desplazarte por el mapa sin chocar hasta que llegues al objetivo.
-Con esa sol. inicial entonces selecciona 2 puntos random, onda 2 coordenadas al azar.
-Aplica HC para llegar de u a de esascoorde adas a la otra.
-Si es que encuentras un camino más corto entre esas coords que el original, entonces actualiza tu sol inicial acortando el camino entre esas coordenadas.
-Vuelve a seleccioar 2 coords al azar.
Otra posibilidad, más fácil, es samplear el mapa, onda dividirlo en sub grillas.
-Luego, seleccionas en cada iteración una grilla cercana al azar.
-Luego, aplicas HC para llegar lo más cerca posible a esa grilla, (a cualquier celda de esa grilla).
-Vuelves a seleccionar otra grilla, etc
Salu2!
