Prolog - necesito ayuda con este ejercicio el inciso d

   
Vista:

necesito ayuda con este ejercicio el inciso d

Publicado por dayami (1 intervención) el 02/06/2009 21:07:43
El problema de la optimización de propósito general consiste en encontrar los valores óptimos de una determinada función a la cuál no se le exige el cumplimiento de ninguna característica específica, como podría ser que fuera una función lineal (como lo exige el método SIMPLES que se imparte en Investigación de Operaciones). Existen muchos métodos para este tipo de problemas entre los que están: los Algoritmos Genéticos, las Estrategias Evolutivas, los Escaladores de Colinas, la Búsqueda limitada por umbral, etc. Asuma que solo se trabajarán con funciones de 6 variables, y cada variable toma valores entre 0 y 9. Para todos estos métodos, suponga que existe una predicado llamado “funcion” que, dada una lista que representa un vector de soluciones, devuelve un valor de evaluación que se corresponde con la función que se desea maximizar. Por ejemplo, la función “producto” podría implementarse así:

funcion([], 1).
funcion([X|L], P):- funcion(L, P1), P is P1*X.

a) Implemente el método de optimización conocido como Algoritmo Genético que se inspira en el proceso evolutivo basado en la reproducción sexual. En este método se generan aleatoriamente un grupo de soluciones (asuma que son 50). Luego, de ellas se toma el 20% mejor (o sea, las 10 con mayor valor para la función a optimizar) y las combina utilizando el operador de cruzamiento para generar 40 soluciones nuevas. Para ello, repite 20 veces el siguiente proceso: Toma dos soluciones aleatoriamente entre las 10 mejores y realiza el cruzamiento. El cruzamiento produce dos nuevas soluciones tomando una sublista de una y otra sublista de la otra, de manera aleatoria. Por ejemplo, el cruzamiento de dos padres como los siguientes puede producir los siguientes hijos H1 y H2: cruzamiento([1,1,4,5,6,7], [2,3,1,1,1,1], H1, H2), produce: H1 = [1,1,1,1,1,1] y H2 = [2,3,4,5,6,7]. Esto se corresponde con el cruzamiento después de la variable número 2. Podría haberse escogido aleatoriamente otro punto de cruce que se correspondiera con las variables: 1, 3, 4 ó 5. Cuando se han generado las 40 soluciones nuevas estas, junto a las 10 mejores, forman lo que se llama “nueva generación”. Ahora, esta nueva generación de 50 soluciones vuelve a pasar por todo el proceso nuevamente: Se escogen las 10 mejores, se cruzan, etc. Permita que el usuario pueda seleccionar el número de generaciones que desea. Al final, devuelva la mejor solución encontrada durante toda la evolución.

b) Implemente el método de optimización conocido como Estrategias de Evolución que se inspira en el proceso evolutivo basado en reproducción asexual. En este método se generan aleatoriamente un grupo de soluciones (asuma que son 50). Luego de ellas se toma el 20% mejor (o sea, las 10 con mayor valor para la función a optimizar) y produce 40 soluciones nuevas aplicando el operador de mutación. Para ello, para cada una de las soluciones escogidas produce 4 mutaciones de manera aleatoria. La mutación consiste en cambiar el valor de algunas de las variables por alguno de los otros valores posible. Por ejemplo, la mutación de una solución como la siguiente puede producir el H1 que se indica a continuación: mutacion([1,1,1,1,1,1], H) produce: H1 = [1,1,1,5,1,1]. Esto se corresponde con la mutación de la cuarta variable (escogida aleatoriamente) al valor 5 (también escogido aleatoriamente). Cuando se han generado las 40 soluciones nuevas estas, junto a las 10 mejores, forman lo que se llama “nueva generación”. Ahora, esta nueva generación de 50 soluciones vuelve a pasar por todo el proceso nuevamente: Se escogen las 10 mejores, se cruzan, etc. Permita que el usuario pueda seleccionar el número de generaciones que desea. Al final, devuelva la mejor solución encontrada durante toda la evolución.
c) Implemente el método de optimización conocido como Escalador de Colinas de Mejor Ascenso (Best Hill Climbing). En este método se genera todas las soluciones vecinas a una solución inicial que se toma aleatoriamente. Por ejemplo, para la solución [1,2,3,4,5,6] las soluciones vecinas serían las que se diferencian de ella en un valor de 1 en una de las variables, en este caso podrían ser: [0,2,3,4,5,6], [2,2,3,4,5,6], [1,1,3,4,5,6], [1,3,3,4,5,6], [1,2,2,4,5,6], [1,2,4,4,5,6], ..., [1,2,3,4,5,7], etc. Luego, de ellas se toma la mejor. Si la nueva solución es mejor (según la evaluación) que la actual se asume como nueva solución para el próximo paso. Este proceso se repite por un número de iteraciones que el usuario fija y se devuelve la mejor solución encontrada. Si entre las soluciones posibles a escoger ninguna es mejor que la actual el proceso también se detiene.

d) Implemente el método de optimización conocido como Escalador de Colinas de Primer Ascenso (First Hill Climbing). En este método se genera aleatoriamente soluciones vecinas (una cada vez) a una solución inicial, que se toma aleatoriamente. Por ejemplo, para la solución [1,2,3,4,5,6] las soluciones vecinas serían las que se diferencian de ella en un valor de 1 en una de las variables, en este caso podrían ser: [0,2,3,4,5,6], [2,2,3,4,5,6], [1,1,3,4,5,6], [1,3,3,4,5,6], [1,2,2,4,5,6], [1,2,4,4,5,6], ..., [1,2,3,4,5,7], etc. Cuando se genera una nueva solución, si esta es mejor o igual (según la evaluación) que la actual se asume como nueva solución para el próximo paso, no generándose aleatoriamente más soluciones vecinas. Este proceso se repite por un número de iteraciones que el usuario fija y se devuelve la mejor solución encontrada. Si entre las soluciones posibles a escoger ninguna es mejor o igual que la actual el proceso también se detiene.
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder
información
Otras secciones de LWP con contenido de Prolog
- Código fuente de Prolog
- Cursos de Prolog
- Temas de Prolog
información
Códigos de Prolog
- Tateti o tres en ralla
- Ejercicios resueltos
- Resolver Sudokus

RE:necesito ayuda

Publicado por Soraya Mojenas Perez (1 intervención) el 21/10/2009 17:04:28
Una respuesta me sera muy util para continuar con mi trabajo
Estoy buscando una ayudita para resolver el problema de los algoritmos Metaheurísticos basados en un punto,especificamente el Escalador de Colinas. La implementación del algoritmo es para aplicar al problema One Max que a continuacion se muestra
Recocido Simulado
One-Max: Tiene como objetivo maximizar el número de unos en una cadena, el problema original es para cadenas binarias[29], pero se trato para cadenas de enteros. Formalmente, se describe como: una cadena x = {x1, x2,..., xn}, xi toma valores de 0 a 9, y maximiza la siguiente ecuación:
One-Max (Cadena) = Cantidad de unos que hay en una cadena.
Para definir el problema solamente se necesita decidir el tamaño n de la cadena, dado el valor de n el óptimo se encuentra cuando el número de unos en la cadena es n, es decir, el máximo de la función es la longitud de la cadena. La cantidad de variables se corresponde con la longitud de la cadena. Ejemplo: One-Max (3 1 1 0 1 0 2 1 3 0 4 0 1 1 1 0 1 0 0 1) = 9, n = 20, hay 9 posiciones ocupadas por "1".
Sin mas saludos a la comunidad de programadores
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar