Ttrata de calcular la siguiente función (típico ejemplo):
Maximizar f(x1, x2) = 21.5 + x1 sin(4πx1) + x2 sin(20πx2)
Sujeto a:
-3.0 <- x1 <- 12.1
4.1 <- x2 <- 5.8
Este script está basado en la solución que Willian Talada aporta en “A Genetic Algorithm Sample in T-SQL" para el problema del robot y las latas que plantea Melanie Mitchell en su libro “Complexity: A Guided Tour”, 2009
Para convertir los valores binarios a base 10, el algoritmo utiliza una simple función definida
de usuario llamada ConvertFromBase
/* Función que convierte cualquier base a base 10 http://dpatrickcaldwell.blogspot.com/2009/05/converting-hexadecimal-or-binary-to.html*/ CREATE FUNCTION ConvertFromBase ( @value AS VARCHAR(MAX), @base AS BIGINT ) RETURNS BIGINT AS BEGIN -- just some variables DECLARE @characters CHAR(36), @result BIGINT, @index SMALLINT; -- initialize our charater set, our result, and the index SELECT @characters = '0123456789abcdefghijklmnopqrstuvwxyz', @result = 0, @index = 0; -- make sure we can make the base conversion. there can't -- be a base 1, but you could support greater than base 36 -- if you add characters to the @charater string IF @base < 2 OR @base > 36 RETURN NULL; -- while we have characters to convert, convert them and -- prepend them to the result. we start on the far right -- and move to the left until we run out of digits. the -- conversion is the standard (base ^ index) * digit WHILE @index < LEN(@value) SELECT @result = @result + POWER(@base, @index) * (CHARINDEX (SUBSTRING(@value, LEN(@value) - @index, 1) , @characters) - 1 ), @index = @index + 1; -- return the result RETURN @result; END
Debido a las particularidades del lenguaje T-SQL, para simplificar elegí la selección
elitista (sólo los dos mejores) como mecanismo para obtener los distintos padres.
El resultado final son dos listas: una que incluye todos los padres, con todos los detalles y otra
con el valor- número de generación más alto
SET nocount on
-- declarar tabla variable que albergará resultados
DECLARE @results table (secuencia int identity, NumGeneracion int, DNA varchar(33), x1 float, x2 float, valor float)
DECLARE
@i int,
@dna varchar(33), -- hijo que estará siendo testeado
@loop int,
@dna1 varchar(33), -- mejor hijo
@dna2 varchar(33), -- segundo mejor hijo
@Poblacion int, -- Población que se está evaluando
@k1 int,
@k2 int,
@NumGeneraciones int,
@NumDescendencias int
-- Número de generaciones a evaluar
SET @NumGeneraciones = 1000 -- generaciones
SET @NumDescendencias = 1000 -- descendencias
-- Test rápido
--SET @NumGeneraciones = 100
--SET @NumDescENDencias = 100
-- generar primera población
SET @loop = @NumDescENDencias
SET @Poblacion = 1
WHILE @loop > 0
BEGIN
SET @dna=''
SET @i=0
WHILE @i < 33 -- ya que el cromosoma tendrá una longitud de 33 bits
BEGIN
SET @dna = @dna + CAST(CAST(RAND() * 2 as int) as varchar(1)) -- generamos uno a uno cada bit
SET @i = @i+1
END
-- Una vez generado el cromosoma, pasamos a calcular x1, x2 y el valor de f
DECLARE @valor float
DECLARE @var1 dec
DECLARE @x1 float
DECLARE @x2 float
DECLARE @var2 dec
SET @var1 = CAST(SUBSTRING(@dna, 1, 18)as dec) -- extraemos 18 primeros bits
SET @var2 = CAST (SUBSTRING (@dna,19,15)as dec) -- extraemos restantes 15
-- Convertimos a decimal. Usamos Función personal (código adjunto)
SET @x1= CAST( dbo.convertfromBase(@var1,2)as float)
SET @x2= CAST( dbo.convertfromBase(@var2,2)as float)
SET @x1 = -3+( @x1 * 0.00005760 )
SET @x2 = 4.1+( @x2 * 0.0000518)
SET @valor = (SELECT 21.5 +( @x1 *sin(4*3.14159*@x1))+(@x2* SIN(20*3.14159*@x2)))
INSERT INTO @results (NumGeneracion, DNA, x1, x2, valor) SELECT @Poblacion, @dna, @x1, @x2,@valor
SET @loop = @loop -1
END
--Loop Generaciones
WHILE @Poblacion <= @NumGeneraciones
BEGIN
--Aplicamos una selección elitista: salvamos los mejores padres
SELECT @k1 = secuencia FROM @results WHERE NumGeneracion=@Poblacion AND valor = (SELECT max(valor) FROM @results
WHERE NumGeneracion=@Poblacion)
SELECT @k2 = secuencia FROM @results WHERE NumGeneracion=@Poblacion AND secuencia <> @k1 AND valor = (SELECT
max(valor) FROM @results WHERE NumGeneracion=@Poblacion AND secuencia <> @k1)
SELECT @dna1 = DNA FROM @results WHERE NumGeneracion=@Poblacion AND valor = (SELECT max(valor) FROM @results WHERE
NumGeneracion=@Poblacion)
SELECT @dna2 = DNA FROM @results WHERE NumGeneracion=@Poblacion AND DNA <> @dna1 AND valor = (SELECT max(valor) FROM
@results WHERE NumGeneracion=@Poblacion AND DNA <> @dna1)
-- Borramos el resto
DELETE FROM @results
WHERE NumGeneracion = @Poblacion
AND secuencia not in (@k1, @k2)
SET @Poblacion = @Poblacion + 1
-- hijos loop
SET @loop = @NumDescendencias
WHILE @loop > 0
BEGIN
-- aproximadamente mitad padre1 -mitad padre2
SET @i = CAST(RAND()* 33 as int)+1
SET @dna = left(@dna1,@i) + right(@dna2, 33 - @i)
-- + 5 mutaciones
SET @dna=STUFF(@dna,CAST(RAND()* 33 as int)+1,1, CAST(CAST(RAND() * 2 as int) as varchar(1)))
SET @dna=STUFF(@dna,CAST(RAND()* 33 as int)+1,1, CAST(CAST(RAND() * 2 as int) as varchar(1)))
SET @dna=STUFF(@dna,CAST(RAND()* 33 as int)+1,1, CAST(CAST(RAND() * 2 as int) as varchar(1)))
SET @dna=STUFF(@dna,CAST(RAND()* 33 as int)+1,1, CAST(CAST(RAND() * 2 as int) as varchar(1)))
SET @dna=STUFF(@dna,CAST(RAND()* 33 as int)+1,1, CAST(CAST(RAND() * 2 as int) as varchar(1)))
-- hijos nuevos y salvar resultados
SET @var1 = CAST(SUBSTRING(@dna, 1, 18)as dec)
SET @var2 = CAST (SUBSTRING (@dna,19,15)as dec)
SET @x1= CAST( dbo.convertFrombase(@var1,2)as float)
SET @x2= CAST( dbo.convertFrombase(@var2,2)as float)
SET @x1 = -3+( @x1 * 0.00005760 )
SET @x2 = 4.1+( @x2 * 0.0000518)
--21.5 + x1 sin(4πx1) + x2 sin(20πx2)
SET @valor = (SELECT 21.5 +( @x1 *sin(4*3.14159*@x1))+(@x2* sin(20*3.14159*@x2)))
INSERT INTO @results (NumGeneracion, DNA, x1, x2, valor) SELECT @Poblacion, @dna, @x1, @x2,@valor
SET @loop = @loop - 1
END
END
-- Sumario
SELECT *
FROM @results
WHERE NumGeneracion <= @NumGeneraciones
ORDER BY NumGeneracion asc, valor desc
-- Resultado Final
SELECT NumGeneracion,(valor)
FROM @results
WHERE valor in (SELECT max(valor) FROM @results)
ORDER BY NumGeneracion DESC
No hay comentarios:
Publicar un comentario