Optimozacion
Publicado por Lisbet (2 intervenciones) el 12/06/2007 04:56:19
Necesito encontrar la solucion a este problema en prolog :
10- 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.
Si no se puede encontrar la solucion a todos los incisos por lo menos a uno o algunos de ellos.
10- 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.
Si no se puede encontrar la solucion a todos los incisos por lo menos a uno o algunos de ellos.
Valora esta pregunta
0