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 ); p>
mutación();
p>
sistema("pausa");
devuelve 0
}
void start()
{ p>
int i, stime
long ltime
ltime=time(NULL);
stime=(unsigned)ltime/2;
srand(stime)
for( i = 0; i lt; SUM; i) p>
{
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--) p>
{
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;
}