Solución del problema de la mochila usando un algoritmo genético simple




descargar 14.51 Kb.
títuloSolución del problema de la mochila usando un algoritmo genético simple
fecha de publicación01.02.2016
tamaño14.51 Kb.
tipoSolución
b.se-todo.com > Documentos > Solución


SOLUCIÓN DEL PROBLEMA DE LA MOCHILA USANDO UN ALGORITMO GENÉTICO SIMPLE

EL ALGORITMO GENÉTICO

El algoritmo usado en la solución del problema de la mochila es un algoritmo genético simple, usando el esquema de selección proporcional.

El problema

El problema a resolver, como ya se mencionó, es el problema de la mochila. Específicamente, se requiere saber la cantidad de cada tipo de elemento (8 en el ejemplo) que se puede llevar en la mochila, la cual resiste un peso representado por la variable pesoMaximo. Cada elemento posee un peso (variable peso{20,10,15,50,30,25,35,40}) y provee una cierta utilidad (variable utilidad{10,4,8,22,16,13,17,20}). Se considera que una solución es mejor que otra - suponiendo que las dos son válidas; es decir, que cumplen la restricción de peso- , si la primera provee mayor utilidad que la segunda.

Representación de las soluciones

Cada solución se representa como un entero de 32 bits. Para el ejemplo de la mochila, se tienen 8 tipos de elementos que pueden ser llevados en la mochila. El número de cada uno de estos es representado por 4 bits y puede ser máximo 15 (2 a la 4 = 16, entre 0 y 15 elementos).

Cálculo de la Aptitud

Cada tipo de elemento provee una utilidad. La aptitud de una solución se calcula multiplicando el número de cierto tipo de elemento por su utilidad y luego sumando dichos productos. La aptitud es la función objetivo en el algoritmo genético.

Población Inicial (Generación 0)

La población inicial es un grupo de 64 soluciones (números enteros válidos), cada una de las cuales es escogida aleatoriamente.

Método de Selección

El método utilizado para la selección de las soluciones es el esquema de selección proporcional. Este criterio asigna a cada solución el número de descendientes que puede generar, de acuerdo a su aptitud y la aptitud media de la población. Así, una solución con mayor aptitud podrá tener un mayor número de descendientes.

Método de Recombinación

Se tienen dos soluciones de la población inicial a cruzar, A y B. A se recombina de acuerdo al número de descendientes que el método de selección le asignó. B es seleccionada al azar, dándole la oportunidad a aquellas soluciones que por su aptitud, no podrían reproducirse.

Como ya se había mencionado, todas las soluciones están formadas de ocho partes, cada una de las cuales representa el valor de un parámetro – en este caso, la cantidad de un tipo de elemento.

La nueva solución, producto del cruce, se obtiene tomando cada una de las partes de la solución de sus predecesores y se elige una de ellas. Cada una tiene igual probabilidad de ser elegida como parte de la nueva solución.

Método de Mutación

Luego de obtener la nueva solución, producto de un cruce, existe la probabilidad de cambiarle un bit; esto depende del factor de mutación (variable FactorMutacion), que en este caso corresponde al 0.1%.

Poblaciones de las Siguientes Generaciones

A partir de los cruces hechos entre las soluciones de la población actual se escogen las 64 mejores; es decir, las que tengan mejor aptitud.

Resultados

Si se ejecuta el modelo computacional para el problema de la mochila para una partida de 1000 generaciones, la solución que se obtiene converge después de la 4 generación como se aprecia en la siguiente gráfica.

Si ejecutamos varias veces el programa que implementa el algoritmo genético, obtenemos soluciones similares, cercanas a la solución óptima, la cual para el caso descrito es 266. En la siguiente tabla y gráfico se puede apreciar la solución obtenida en 10 partidas diferentes – con poblaciones iniciales distintas - :

No de Partida

Solución

1

265

2

264

3

264

4

263

5

264

6

263

7

265

8

264

9

263

10

265

VARIACIONES

Variando el número de Generaciones de cada Partida

Variando el Factor de Mutación


similar:

Solución del problema de la mochila usando un algoritmo genético simple iconRjustifica el plan o estrategia que usa para resolver un problema...

Solución del problema de la mochila usando un algoritmo genético simple iconSolución: La probabilidad de ser heterocigotos en un cruzamiento...

Solución del problema de la mochila usando un algoritmo genético simple iconSolución: La probabilidad de ser heterocigotos en un cruzamiento...

Solución del problema de la mochila usando un algoritmo genético simple iconEl problema del conocimiento esta vinculado al problema de la verdad

Solución del problema de la mochila usando un algoritmo genético simple iconEl problema del conocimiento esta vinculado al problema de la verdad

Solución del problema de la mochila usando un algoritmo genético simple iconUsando el glosario del libro de texto define los siguientes significados

Solución del problema de la mochila usando un algoritmo genético simple iconRemocion de arsenico (III) del agua usando oxido de titanio (IV) como medio adsorbente

Solución del problema de la mochila usando un algoritmo genético simple iconTaller de algoritmo

Solución del problema de la mochila usando un algoritmo genético simple iconEscribió: «Para resolver un problema referente a números o relaciones...
«Para resolver un problema referente a números o relaciones abstractas de cantidades basta con traducir dicho problema, del inglés...

Solución del problema de la mochila usando un algoritmo genético simple iconEl algoritmo de una raíz cuadrada




Todos los derechos reservados. Copyright © 2019
contactos
b.se-todo.com