Maximización del Valor de un Número Binario

Este es un sencillo problema que trata de maximizar el valor entero de una cadena binaria.

Así pues, se trata de, teniendo una cadena binaria de longitud $L$, obtener una cadena tal que su valor entero sea máximo. Este es un problema parecido al típico problema de maximizar el número de valores ``1'' que hay en una cadena binaria, en el sentido de que la cadena $10101$ será una solución mejor que la cadena $10100$. Sin embargo, en el problema que nos atañe, la cadena $10000$ será una mejor solución que la cadena $01111$ a pesar de tener ésta otra más valores a ``1''.

Para resolver este problema se ha desarrollado un programa cuyo algoritmo principal es un algoritmo genético simple (clase eoSGA).

La clase a la que pertenecen los individuos es eoBin, lo cual significa que los individuos serán cadenas de bits de longitud $L$ (como en un AG).

Como operadores de transformación se ha hecho uso de los operadores de mutación (eoBinMutation) y de cruce (eoBinCrossover).

La condición de parada del programa se estableció mediante el uso de un terminador (clase eoGenContinue) que controla el número de iteraciones que se harán.

Por último, la función de evaluación viene dada por una función que transforma una cadena binaria en número entero, de forma que, implementando dicha función, como una clase descendiente de eoEvalFunc ya tendremos el programa listo para utilizarlo.

En las tablas y podemos ver los resultados obtenidos al resolver este problema utilizando las versiones secuencial y paralelas (con las diferentes estrategias de migración) del programa desarrollado.

Tabla: Resultados (media y desviación estándard) para el problema del mayor número binario utilizando la versión secuencial del programa desarrollado.

p=100 / g=100	Tiempo
65399.4 $\pm$ 137.4	0.18 $\pm$ 0.02
p=400 / g=100	Tiempo
65528.8 $\pm$ 7.6	0.47 $\pm$ 0.03
p=800 / g=100	Tiempo
65533.0 $\pm$ 2.8	1.13 $\pm$ 0.01
p=1600 / g=100	Tiempo
65534.6 $\pm$ 0.9	3.42 $\pm$ 0.05

Tabla: Resultados (media y desviación estándard) para el problema del mayor número binario utilizando la versión paralela (con diferentes estrategias de migración) del programa desarrollado.

Migración	4 proc.	Tiempo	8 proc.	Tiempo	16 proc.	Tiempo
Simple	65513.0 $\pm$ 23.5	0.27 $\pm$ 0.02	65527.8 $\pm$ 8.9	0.46 $\pm$ 0.08	65530.2 $\pm$ 2.9	0.72 $\pm$ 0.06
Estrella	65535	0.38 $\pm$ 0.05	65535	0.61 $\pm$ 0.06	65535	0.97 $\pm$ 0.05
Broadcast	65535	0.35 $\pm$ 0.04	65535	0.58 $\pm$ 0.09	65535	1.3 $\pm$ 0.2
Anillo	65535	0.41 $\pm$ 0.05	65535	0.55 $\pm$ 0.09	65535	0.84 $\pm$ 0.07