No presentaré los principios detallados y las definiciones específicas de algoritmos genéticos aquí. Si quieres saber, puedes usar Baidu para aprenderlo. Aquí presentaré brevemente su comprensión de los algoritmos genéticos. Este artículo utiliza reglas binarias para la codificación de genes.
Ideas de algoritmo:
El algoritmo genético se refiere a la teoría de la evolución de Darwin y cree que las especies se están desarrollando en una dirección positiva (supervivencia del más apto), por lo que se puede considerar que después de suficiente álgebra, el valor máximo obtenido está muy cerca del valor máximo real.
Pasos de algoritmo:
Parte de implementación del algoritmo
1. Población individual (aquí considerada cromosomas), en individuos, agregamos dos atributos a este individuo, la aptitud física (valor de la función) correspondiente al gen y el gen del individuo.
cromosoma de clase pública {gene boolean [] privado [] gen; // secuencia genética puntuación doble privada; // puntaje de función correspondiente} 2. Genere secuencias genéticas al azar. Si cada posición del gen es 0 o 1, esta es una forma completamente aleatoria de lograrlo.
cromosoma público (intize int) {if (size <= 0) {return; } InitGeneesize (tamaño); para (int i = 0; i <size; i ++) {gen [i] = math.random ()> = 0.5; }} private void initGeneesize (int size) {if (size <= 0) {return; } gen = new Boolean [tamaño]; } 3. Convierta el gen en el valor correspondiente, por ejemplo, el número correspondiente a 101 es 5, y las operaciones de bit se usan aquí para implementarlo.
public int getNum () {if (gen == null) {return 0; } int num = 0; para (boolean bool: gen) {num << = 1; if (bool) {num += 1; }} return num; } 4. Si se produce una mutación genética, la ubicación de la mutación se implementa completamente de manera aleatoria. El principio de mutación es cambiar de 1 a 0 y 0 a 1.
Mutación publicitaria public (int num) {// Permitir mutación int size = gen.length; for (int i = 0; i <num; i ++) {// busca ubicación de mutación int at = ((int) (math.random () * size)) % tamaño; // el valor después de la mutación boolean bool =! Gen [at]; gen [at] = bool; }} 5. Los genes de clonación se usan para producir la próxima generación. Este paso es copiar los genes existentes.
clon del cromosoma estático público (cromosoma final c) {if (c == null || c.gene == null) {return null; } Cromosoma copy = new Chromosome (); copy.initGeneSize (C.Gene.length); for (int i = 0; i <c.gene.length; i ++) {copy.gene [i] = c.Gene [i]; } return Copy; } 6. Ambos padres producen la próxima generación, y aquí dos individuos producen dos descendientes individuales. Qué gen específico es diferente del estudiante, es completamente aleatorio.
Lista estática pública <Cromosome> Genetic (cromosoma P1, cromosoma p2) {if (p1 == null || p2 == null) {// Hay uno de los cromosomas que está vacío y no produce la próxima generación de retorno nulo; } if (p1.gene == null || p2.gene == null) {// Hay uno de los cromosomas que no tiene secuencia genética y no produce el retorno de la próxima generación nulo; } if (p1.gene.length! = p2.gene.length) {// La longitud de la secuencia del gen cromosoma no produce el retorno de la próxima generación nulo; } Cromosoma C1 = clon (p1); Cromosomas C2 = clon (P2); // Crear posiciones de intercambio cruzado aleatoriamente int size = c1.gene.length; int a = ((int) (math.random () * tamaño)) % tamaño; int b = ((int) (math.random () * tamaño)) % tamaño; int min = a> b? B: A; int max = a> b? A: B; // genes cromex en posiciones para (int i = min; i <= max; i ++) {boolean t = c1.gene [i]; c1.Gene [i] = C2.Gene [i]; C2.Gene [i] = t; } List <Chromosome> list = new ArrayList <Chromosome> (); list.add (C1); list.add (C2); lista de devolución; } Algoritmo de implementación algoritmo genético
1. Para los algoritmos genéticos, necesitamos tener poblaciones correspondientes y algunas constantes que necesitamos establecer: número de población, longitud del gen, número de mutaciones genéticas, tasa de mutación génica, etc. Para más detalles, consulte el siguiente código:
Public Abstract Class Geneticalgorithm {Lista privada <Cromosome> POBLACION = new ArrayList <Chromosome> (); // Población privada int Popsize = 100; // Número de población private int genesize; // Longitud máxima de longitud privada int maxiternum = 500; // Máxima iteración Doble Mutación Mutación = 0.01; // Probabilidad de Gene Mutation Private Private MAXMUTACIÓN MAXMUTACIÓN Longitud asíncrona Private int generation = 1; // ¿A cuántas generaciones se heredan actualmente? bestscore; // Mejor puntaje Private Doble peor de peor; // peor puntaje Private Doble Totalscore; // Total Puntuación Private Double promedios de doble; // Puntuación promedio de puntaje Privado Doble X; // registra el mejor valor x en la población histórica Doble y Doble Y; // Registre el mejor valor Y en la población histórica private int genei; // álgebra donde se encuentra xy} 2. Inicializar la población. Al comienzo del algoritmo genético, necesitamos inicializar una población original, que es la primera generación original.
private void init () {for (int i = 0; i <popsize; i ++) {población = new ArrayList <Chromosome> (); Cromosoma chro = nuevo cromosoma (genesize); población.add (chro); } CACULTESCORE (); } 3. Después de que existe la población inicial, necesitamos calcular la aptitud de la población, así como la mejor aptitud física, la peor aptitud y el estado físico promedio, etc.
privado void cacUtescore () {setChromosomescore (población.get (0)); bestScore = POBLACIÓN.GET (0) .getScore (); peorscore = población.get (0) .getScore (); TotalScore = 0; para (cromosoma chro: población) {setChromosomescore (chro); if (chro.getscore ()> bestscore) {// Establezca el mejor valor del gen bestscore = chro.getscore (); if (y <bestscore) {x = Changex (chro); y = bestscore; geni = generación; }} if (chro.getscore () <peorscore) {// Establezca el peor valor género peorscore = chro.getscore (); } totalScore += chro.getscore (); } promeGaScore = TotalScore / Popsize; // El valor promedio causado por problemas de precisión es mayor que el mejor valor, establece el valor promedio en el mejor valor promedResCore = promeAgsCore> bestscore? BestScore: promedios de promedio; } 4. Al calcular la aptitud individual, necesitamos calcular el valor Y correspondiente en función del gen. Aquí establecemos dos métodos abstractos para implementar la implementación específica mediante la implementación de la clase.
privado void setChromosomescore (cromosoma chro) {if (chro == null) {return; } doble x = Changex (chro); doble y = caculado (x); chro.setscore (y); } / ** * @param chro * @return * @Description: convertir binario en la X * / public abstract de doble cambio (cromosoma chro); / ** * @param x * @return * @Description: calcule el valor y basado en x y = f (x) */ public abstract doble caculate (doble x); 5. Después de calcular la aptitud de la población, necesitamos usar el método de juego de giro para seleccionar individuos que puedan producir la próxima generación. Aquí hay una condición de que solo si la aptitud física del individuo no es menor que la aptitud promedio, la próxima generación nacerá (el más apto sobrevive).
cromosoma privado getParentChromosome () {double slice = math.random () * totalScore; doble suma = 0; para (cromosoma chro: población) {sum += chro.getscore (); // vaya a la posición correspondiente y la aptitud no es menor que la aptitud de fitness promedio if (sum> slice && chro.getscore ()> = promeAgsCore) {return chro; }} return null; } 6. Después de seleccionar individuos que puedan producir la próxima generación, debe aparearse para producir la próxima generación.
Private void evolucione () {list <Chromosome> ChildPoperation = new ArrayList <Chromosome> (); // Generar la población de la próxima generación mientras (ChildPoperation.Size () <Popsize) {cromosoma p1 = getparentChomosome (); Cromosoma p2 = getparentChromosome (); Lista <cromosoma> niños = cromosoma.genético (P1, P2); if (children! = null) {para (cromosoma chro: niños) {childPoperation.add (chro); }}} // Reemplazar la población antigua con la nueva lista de población <cromosoma> t = población; población = población infantil; T.Clear (); t = nulo; // Mutación de mutación del gen (); // Calcule la aptitud de la nueva población Cacultescore (); } 7. Las mutaciones genéticas pueden ocurrir durante el proceso de producción de la próxima generación.
Mutación vacía privada () {para (cromosoma chro: población) {if (math.random () <mutationRate) {// La mutación del gen ocurre int mutationNum = (int) (math.random () * maxMutationNum); chro.Mutation (MutationNum); }}} 8. Repita los pasos anteriores uno por uno.
public void caculte () {// Inicializar la generación de población = 1; init (); while (generación <maxiternum) {// evolución genética popular (); imprimir(); generación ++; }}Escribir clases de implementación
Dado que la clase del algoritmo genético anterior es una clase abstracta, necesitamos escribir una clase de implementación para un caso específico, suponiendo que calculemos el valor máximo de y = 100 log (x) en [6,106].
1. Suponemos que la longitud del gen es 24 (la longitud del gen está determinada por la longitud efectiva del resultado requerido), por lo que el máximo binario correspondiente es 1 << 24. Hacemos la siguiente configuración
clase pública genéticagorithmtest extiende genéticogorithm {public static final int num = 1 << 24; público genéticogorithmtest () {super (24); }} 2. Implementar el método abstracto del valor x
@Override public Double Changex (Chromosome Chro) {// TODO Auto Generado Método STUB Return ((1.0 * chro.getNum () / num) * 100) + 6; } 3. Implementar el método abstracto de Y
@Override public Double Caculate (Double X) {// TODO Método Generado automático return 100 - Math.log (x); }Resultados de ejecución
Pensando en algoritmos genéticos
He leído muchas presentaciones a los algoritmos genéticos. Las soluciones óptimas mencionadas anteriormente son la mayor cantidad de valores de la última generación. Tengo una pregunta. ¿Por qué sé que la mayor cantidad de valores entre todas las bandas anteriores, es decir, los valores XY en el programa, por qué no puedo usar los valores XY como el valor de resultado final del algoritmo genético?
Código completo
1. Clase cromosómica
/ ***@Descripción: cromosoma genético*/ paquete com.lulei.genetic.algorithm; import java.util.arrayList; import java.util.list; cromosoma de clase pública {gene boolean [] privado [] gen; // secuencia de genes puntaje doble privado; // puntaje de función correspondiente public double getScore () {return stork; } public void setScore (doble puntaje) {this.score = stork; } / *** @param size* secuencia de genes generada aleatoriamente* / pública cromosoma (int tamaño) {if (size <= 0) {return; } InitGeneesize (tamaño); para (int i = 0; i <size; i ++) {gen [i] = math.random ()> = 0.5; }} / *** Genere un nuevo gen* / public cromosoma () {} / *** @param c* @return* @Description: cloning gen* / public static cromosome clon (cromosoma final c) {if (c == null || c.gene == null) {return null; } Cromosoma copy = new Chromosome (); copy.initGeneSize (C.Gene.length); for (int i = 0; i <c.gene.length; i ++) {copy.gene [i] = c.Gene [i]; } return Copy; } / *** @param size* @Description: inicializar la longitud del gen* / private void initGeneesize (int size) {if (size <= 0) {return; } gen = new Boolean [tamaño]; } /** * @param c1 * @param c2 * @description: generación genética para producir la próxima generación * /public static list <Chromosome> genetic (cromosoma p1, cromosoma p2) {if (p1 == null || p2 == null) {// hay uno de los cromosomas que está vacío y no produce el null null; } if (p1.gene == null || p2.gene == null) {// Hay uno de los cromosomas que no tiene secuencia genética, y no produce la próxima generación de retorno nulo; } if (p1.gene.length! = p2.gene.length) {// La longitud de la secuencia del gen cromosoma no produce el retorno de la próxima generación nulo; } Cromosoma C1 = clon (p1); Cromosomas C2 = clon (P2); // Crear posiciones de intercambio cruzado aleatoriamente int size = c1.gene.length; int a = ((int) (math.random () * tamaño)) % tamaño; int b = ((int) (math.random () * tamaño)) % tamaño; int min = a> b? B: A; int max = a> b? A: B; // genes cromex en posiciones para (int i = min; i <= max; i ++) {boolean t = c1.gene [i]; c1.Gene [i] = C2.Gene [i]; C2.Gene [i] = t; } List <Chromosome> list = new ArrayList <Chromosome> (); list.add (C1); list.add (C2); lista de devolución; } /*** @param num* @description: la variación ocurre en las posiciones num de gen num* /public void mutation (int num) {// permitir la mutación int size = gen.length; for (int i = 0; i <num; i ++) {// buscar posición de mutación int at = ((int) (math.random () * tamaño)) % tamaño; // el valor después de la mutación boolean bool =! Gen [at]; gen [at] = bool; }} / *** @return* @Description: convierte los genes en números correspondientes* / public int getNum () {if (gene == null) {return 0; } int num = 0; para (boolean bool: gen) {num << = 1; if (bool) {num += 1; }} return num; }} 2. Clase de Genética del Goritmo
/ ** *@Descripción: */ paquete com.lulei.genetic.algorithm; import java.util.arrayList; import java.util.list; Public Abstract Class Geneticalgorithm {Lista privada <Cromosome> POBLACIÓN = New ArrayList <Chromosome> (); private int popsize = 100; // número popular int genesize; // longitud de gen máxima privada int maxiternum = 500; // Número máximo de iteraciones Mutación doble privada MutationRate = 0.01; // Probabilidad de mutación génica int maxMutationNum = 3;//máximo variante de longitud asíncrona intenuada privada intencion = 1; // ¿cuántas generaciones son actualmente inheritadas actualmente? Private Double BestScore; // Mejor puntaje Private Doble peor Peor; // Peor puntaje Private Doble Totalscore; // Total Puntuación Private Double promedios de doble; // Puntuación promedio Doble privado X; // registra el mejor valor x en la población histórica Doble y Doble Y; // registra el mejor valor Y en la población histórica private int genei; // álgebra donde xy se encuentra público genéticogoritmo (int genesize) {this.genesize = genesize; } public void caculte () {// Inicializar la generación de población = 1; init (); while (generación <maxiternum) {// evolución genética popular (); imprimir(); generación ++; }} / *** @Description: resultado de salida* / private void print () { System.out.println("--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- System.out.println ("La peor aptitud es:" + peorcore); @Description: Inicializar la población*/ privado init () {para (int i = 0; i <Popsize; i ++) {población = nuevo ArrayList <Chromosome> () Void Void Evolve () {List <Chromosome> ChildPoperation = New ArrayList <Chromosome> (); P2); @return * @description: el método de ruleta selecciona cromosomas que pueden heredar la próxima generación */ cromosoma privado getParentChromosome () {Double slice = Math.random () * TotalScore; {return chro; setChromosScore (chro); Chro.getScore (); Chro: Población) {if (Math.random () <mutationRate) {// La mutación del gen ocurre int mutationNum = (int) (math.random () * maxMutationNum) chro) {if (chro == null) {return; Y valor basado en x y = f (x) */ abstracto público doble cacleado (doble x); setmaxiternum (int maxiternum) {this.maxiternum = maxiternum; {return bestscore; 3. Clase genéticagorithmtest
/ ** *@Descripción: */ paquete com.lulei.genetic.algorithm; clase pública genéticagorithmtest extiende genéticogorithm {public static final int num = 1 << 24; público genéticogorithmtest () {super (24); } @Override public Double Changex (Chromosome Chro) {// TODO Auto Generado de método return ((1.0 * chro.getNum () / num) * 100) + 6; } @Override public Double Caculate (Double X) {// TODO Método Generado automático return 100 - Math.log (x); } public static void main (string [] args) {geneticalgorithmtest test = new GeneticGorithMTest (); test.caculte (); }}Lo anterior es una introducción detallada al algoritmo genético de Java. Espero que sea útil para todos aprender algoritmo genético Java.