Red de conocimiento informático - Consumibles informáticos - Programa de algoritmo genético para puntuaciones altas

Programa de algoritmo genético para puntuaciones altas

Como algoritmo de optimización rápido y eficaz, el algoritmo genético se ha utilizado ampliamente en muchos campos, como el control industrial, la toma de decisiones económicas y la planificación del transporte. Su característica es que es diferente del método tradicional de búsqueda y optimización pero simula el proceso de evolución biológica en la naturaleza. A través de la mutación, recombinación cruzada y recombinación de genes, el conjunto evoluciona. A través de la evolución continua, finalmente se obtiene el grupo óptimo. , es decir, la solución óptima.

El siguiente es un ejemplo específico, que Xiaoke adaptó y optimizó en función de los programas de otras personas. Aquí primero debemos establecer un modelo matemático, es decir, una fórmula matemática que describa el problema. El modelado matemático es un curso que requiere una habilidad matemática considerable. La habilidad matemática de una persona a menudo determina el nivel de trabajo que realiza. El siguiente programa consiste en encontrar el valor mínimo del polinomio y=x^6-10x^5-26x^4 344x^3 193x^2-1846x-1680 en el intervalo, y el error no supera 0,001. Para este polinomio complejo, primero puede usar matlab para dibujar la curva aproximada de la función, confirmar que el valor mínimo de la función está aproximadamente entre y luego usar este programa para encontrar la solución exacta.

El programa se ha ejecutado bajo Dev-c y los resultados son correctos.

Si tienes alguna duda envíame un mensaje.

#include lt;stdio.hgt;

#include lt;stdlib.hgt

#include lt;math.hgt; p>#include lt; time.hgt;

#define SUM 20 /* Total*** número de cromosomas*/

#define MAXloop 1200 /* Número máximo de bucles* /

#define error 0.01 /* Si la diferencia entre los dos valores óptimos es menor que este número, el resultado se considera sin cambios*/

#define crossp 0.7 /* Probabilidad de cruce*/

p>

#define mp 0.04 /* Probabilidad de mutación*/

struct gen /* Definir estructura cromosómica*/

{

int info;

doble idoneidad;

};

struct gen gen_group[SUM]; cromosomas*/

struct gen gen_new[SUM];

struct gen gen_result; /* registra el cromosoma óptimo*/

int result_unchange_time; el valor óptimo no ha cambiado bajo la premisa de error. El número de ciclos*/

struct log /* forma una lista vinculada para registrar la aptitud óptima producida por cada ciclo*/

{

doble idoneidad ;

struct log *next;

}llog, *head, *end

int log_num; * Longitud de la lista enlazada*/

void start(); /*Función de inicialización*/

evaluación void(int flag); /*Función de clasificación y evaluación de condición física*/

void cross(); / *Función cruzada*/

void selección(); /*Función de selección*/

int record(); solución y determinar si el ciclo ha terminado*/

voidmutation(); /*mutation function*/

void showresult(int /*show result*/

int randsign(double p) ; /*Genera un número aleatorio 0, 1 con probabilidad p, p representa la probabilidad de generar un valor 1*/

int randbit(int i, int j). ); /*Generar un entero aleatorio entre i, j* /

int randnum(); /*Generar aleatoriamente un cromosoma compuesto de 14 bits (genes)*/

int conversionD2B (doble x); /*Codificación*/

doble conversiónB2D(int x); /*decodificación*/

int createmask(int a); /p>

int main()

{

int i, bandera

bandera=0

iniciar(;

evaluación(

0 );

for( i = 0 ; i lt; MAXloop ; i )

{

cruz(); ( 1 );

selección();

if( registro() == 1 )

{

bandera = 1;

romper;

}

mutación();

}

mostrar resultado( bandera

mutación();

p>

sistema("pausa");

devuelve 0

}

void start()

{

int i, stime

long ltime

ltime=time(NULL);

stime=(unsigned)ltime/2;

srand(stime)

for( i = 0; i lt; SUM; i)

{

gen_group[i ].info = randnum();

}

gen_result.suitability=1000; p>result_unchange_time=0;

head=end =(struct log *)malloc(sizeof(llog));

if(head==NULL)

{

printf("\n¡No hay suficiente memoria! \n"); -gt; siguiente = NULL;

log_num = 1;

}

evaluación nula (bandera int)

{

int i, j, k;

struct gen *genp;

int gentinfo;

doble idoneidad

doble x;

if( bandera == 0 )

genp = gen_group;

else genp = gen_new

for(i = 0; i lt; SUM; i)/* Calcular la correspondencia de cada valor de expresión cromosómica*/

{

x = conversionB2D( genp[i].info ); /p>

genp[i].idoneidad = x*( x*(x*(x*(x*(x-10)-26) 344) 193)-1846)-1680

}

for(i = 0; i lt; SUM - 1; i)/* Ordenar por valor de expresión*/

{ k=i; p>for(j = i 1; j lt; SUM ; j )

if( genp[i].idoneidad gt; genp[j].idoneidad ) k=j

if( k!=i )

{

gentinfo = genp[i].info

genp[i].info = genp[k]. información;

genp[k].info = gentinfo;

gentsuitability = genp[i].idoneidad

genp[i].idoneidad = genp[ k].idoneidad;

genp[k].idoneidad = gentidoneidad

}

}

}

void cross()

{

int i, j, k

int máscara1, máscara2

int a[ SUMA];

for(i = 0; i lt; SUMA; i) a[i] = 0;

k = 0; i = 0; i lt; SUMA; i)

{

if( a[i] == 0)

{

for( ; ; )/* Encuentra aleatoriamente un conjunto de cromosomas no cruzados para cruzar con a[i]*/

{

j = randbit(i 1 , SUM - 1)

if( a[j] == 0) romper

}

if(randsign(crossp) == 1)

{

máscara1 = createmask(randbit(0, 14-1));

máscara2 = ~máscara1

gen_new[k]. (gen_group[i].info) amp; (gen_group[j].info) amp; gen_group[j].info) amp; máscara1

k = k 2;

}

else

{

gen_new[k].info=gen_group[i].info

gen_new[k 1].info=gen_group[j].info

k =k; 2;

}

a[i] = a[j] = 1

}

}

}

selección nula()

{

int i, j, k

j = 0 < /p; >

i = SUMA/2-1;

if(gen_group[i].suitability lt; gen_new[i].suitability)

{

for(j = 1; j lt; SUM / 2; j)

{

if(gen_group[i j].idoneidad g

t; gen_new[i-j].suitability)

romper

}

}

else

if; (gen_group[i].suitabilitygt; gen_new[i].suitability)

{

for(j=-1;jgt;-SUM/2;j--)

{

for(j=-1;jgt;-SUM/2;j--)

{ p>

{

if(gen_group[i j].suitabilitylt;=gen_new[i-j].suitability)

break

}

}

for(k=j;klt;SUM/2 1;k)

{

gen_group[i k].info = gen_new [i-k].info

<; p>gen_group[i k].suitability = gen_new[i-k].suitability

}

}

int record()

{

doble x;

struct log *r;

r=(struct log *)malloc( sizeof(llog)); p>if(r==NULL)

{

printf("\n¡No hay suficiente memoria!\n"); (0);

}

r-gt; siguiente = NULL;

end-gt; idoneidad = gen_group[0]. >

end-gt; siguiente = r;

end = r;

log_num

x = gen_result.suitability - gen_group[0]. idoneidad;

if(x lt; 0)x = -x;

if(x lt; error)

{

result_unchange_time

if(result_unchange_time gt; = 20)return 1;

}

else

{

gen_result.info = gen_group[0].info;

gen_result.suitability = gen_group[0].suitability

result_unchange_time=0

}

return 0;

}

mutación nula()

{

int i, j, k, m;

doble x;

doble gmp;

int gentinfo;

doble idoneidad; gmp; p>

gmp = 1 - pow(1 - mp, 11);/* La probabilidad de mutación de todo el cromosoma cuando la probabilidad de mutación del gen es mp*/

for(i

= 0; i lt; SUMA; i)

{

if(randsign(gmp) == 1)

{

j = randbit(0, 14);

m = 1 lt;

gen_group[i].info = gen_group[i].info^m; p>

p>

x = conversionB2D(gen_group[i].info

gen_group[i].idoneidad = x*(x*(x*(x*(x*); (x-10) -26) 344) 193)-1846)-1680;

}

}

for(i = 0; i lt; SUMA - 1; i )

{ k=i;

for(j = i 1; j lt; SUMA; j)

if(gen_group[ i].idoneidad gt ; gen_group[j].idoneidad) k=j;

if(k!=i)

{

gentinfo = gen_group[ i].info;

gen_group[i].info = gen_group[k].info;

gen_group[k].info = gentinfo; = gen_group[i] .idoneidad;

gen_group[i].idoneidad = gen_group[k].idoneidad

gen_group[k].idoneidad = gentidoneidad

}

p>

}

}

void showresult(int flag)/* Mostrar resultados de búsqueda y liberar memoria*/

{

int i, j;

struct log *logprint, *logfree

ARCHIVO *logf; if(flag == 0)

printf("Se alcanzó el número máximo de búsquedas, ¡la búsqueda falló!"); /p>

printf("Cuando el valor f La expresión alcanza el valor mínimo f\n", conversionB2D(gen_result.info), gen_result.suitability

printf("El proceso de convergencia es registrado en el archivo log.txt");

if((logf = fopen("log.txt" , "w ")) == NULL)

{

printf("No se puede crear/abrir el archivo");

exit(1);

}

logprint=head;

for(i = 0; i lt; log_num; i = i 5)/* Mostrar el proceso de convergencia*/

{

for(j = 0; (j lt; 5) amperio;

((i j) lt; log_num-1); j)

{

fprintf(logf, "20f", logprint-gt; idoneidad

); logprint=logprint-gt;

}

fprintf(logf, "\n\n"); }

for(i = 0; ilt; log_num; i)/* Liberar memoria*/

{

logfree=head; p>head=head-gt;

libre(logfree);

}

fclose(logf); ();

}

int randsign(double p)/* Devuelve 1 según la probabilidad p */

{

if ( rand() gt; (p * 32768))

devuelve 0;

de lo contrario devuelve 1

}

int randbit; ( int i, int j)/* Genera un número aleatorio entre i y j*/

{

int a, l

l = j -; i 1;

a = i rand() * l / 32768

devuelve a

}

int randnum ()

{

int x

x = rand() / 2;

devuelve x; }

doble conversiónB2D(int x)

{

doble y

y = x

y = (y - 8192) / 1000;

return y

}

int conversionD2B(doble x)

{

int g;

g = (x * 1000) 8192;

devuelve g

}

int createmask(int a)

{

int máscara

máscara=(1 lt; lt; a) -

volver máscara;

}