Não apresentarei os princípios detalhados e definições específicas de algoritmos genéticos aqui. Se você quiser saber, pode usar o Baidu para aprender. Aqui, apresentarei brevemente sua compreensão dos algoritmos genéticos. Este artigo usa regras binárias para a codificação de genes.
Ideias de algoritmo:
O algoritmo genético refere -se à teoria da evolução de Darwin e acredita que as espécies estão se desenvolvendo em uma direção positiva (sobrevivência do mais apto), portanto, pode -se considerar que, após álgebra suficiente, o valor máximo obtido é muito próximo do valor máximo real.
Etapas do algoritmo:
Parte do gene da implementação do algoritmo
1. População individual (aqui considerada cromossomos), em indivíduos, adicionamos dois atributos a esse indivíduo, a aptidão (valor da função) correspondente ao gene e gene do indivíduo.
classe pública Cromossomia {private boolean [] gene; // sequência de genes Pontuação dupla privada; // Pontuação de função correspondente} 2. Gere seqüências de genes aleatoriamente. Se cada posição do gene é 0 ou 1, essa é uma maneira completamente aleatória de alcançá -lo.
cromossomo public (int size) {if (size <= 0) {return; } initGenesize (tamanho); for (int i = 0; i <tamanho; i ++) {gene [i] = math.random ()> = 0,5; }} private void initgenesize (int size) {if (size <= 0) {return; } gene = novo booleano [tamanho]; } 3. Converta o gene no valor correspondente, por exemplo, o número correspondente a 101 é 5 e as operações de bit são usadas aqui para implementá -lo.
public int getNum () {if (gene == null) {return 0; } int num = 0; para (bool bool: gene) {num << = 1; if (bool) {num += 1; }} retornar num; } 4. Se ocorrer uma mutação genética, a localização da mutação é completamente implementada de maneira aleatória. O princípio da mutação é mudar de 1 para 0 e 0 para 1.
mutação pública void (int num) {// Permitir mutação int size = gene.length; for (int i = 0; i <num; i ++) {// Procure por localização de mutação int em = ((int) (math.random () * size)) tamanho; // o valor após a mutação boolean bool =! Gene [at]; gene [at] = bool; }} 5. Os genes de clonagem são usados para produzir a próxima geração. Esta etapa é copiar os genes existentes.
clone do cromossomo estático público (cromossomo final c) {if (c == null || c.Gene == null) {return null; } Cópia do cromossomo = new cromossomo (); copy.initgenesize (c.gene.length); for (int i = 0; i <c.Gene.Length; i ++) {copy.Gene [i] = c.Gene [i]; } Retornar cópia; } 6. Ambos os pais produzem a próxima geração e aqui dois indivíduos produzem dois descendentes individuais. Qual gene específico é diferente do aluno, é completamente aleatório.
Lista estática pública <Cromossome> genético (cromossomo P1, cromossomo p2) {if (p1 == null || p2 == null) {// existe um dos cromossomos que está vazio e não produz a próxima geração retorna nulo; } if (p1.gene == null || p2.Gene == null) {// Existe um dos cromossomos que não possui sequência genética e não produz a próxima geração retorna nulo; } if (p1.gene.length! = p2.gene.length) {// O comprimento da sequência do gene cromossomo não produz o retorno da próxima geração; } Cromossomo c1 = clone (p1); Cromossomo c2 = clone (p2); // Crie posições de swap cruzado aleatoriamente int size = c1.gene.length; int a = ((int) (math.random () * tamanho)) tamanho; int b = ((int) (math.random () * tamanho)) tamanho; int min = a> b? B: A; int max = a> b? A: B; // genes cromex em posições para (int i = min; i <= max; i ++) {boolean t = c1.gene [i]; c1.gene [i] = c2.Gene [i]; c2.Gene [i] = t; } List <Cromossome> list = new ArrayList <Cromossome> (); list.add (C1); list.add (c2); lista de retorno; } Algoritmo genético de implementação de algoritmo
1. Para algoritmos genéticos, precisamos ter populações correspondentes e algumas constantes que precisamos definir: número da população, comprimento do gene, número de mutações genéticas, taxa de mutação genética etc. Para detalhes, consulte o seguinte código:
Classe abstrata pública genéticaGorithm {Lista privada <Cromossome> população = novo ArrayList <Cromossomos> (); // População privada int popSize = 100; // Número da população Private int genesize; // Comprimento máximo privado int maxiternum = 500; // iteração privada máxima = 0,01; comprimento assíncrono privado int geração = 1; // Quantas gerações são atualmente herdadas? BestScore; // Melhor pontuação privada dupla piorScore; // Pior pontuação Totalscore duplo privado; // Pontuação total PRIVADO DUPLEAGEGAGESCORE; // Pontuação média dupla privada x; // registra o melhor valor X na população histórica dupla particular y; // registra o melhor valor y na população histórica privada int genei; // álgebra onde xy está localizado} 2. Inicialize a população. No início do algoritmo genético, precisamos inicializar uma população original, que é a primeira geração original.
private void init () {for (int i = 0; i <popsize; i ++) {população = new ArrayList <Cromossome> (); Cromossomo chro = novo cromossomo (genesize); população.Add (CHRO); } cacultescore (); } 3. Depois que a população inicial existe, precisamos calcular a aptidão da população, bem como a melhor aptidão, a pior aptidão e fitness, etc.
private vazio cacultescore () {setchromosomoscore (população.get (0)); BestScore = População.get (0) .getScore (); piorscore = população.get (0) .getScore (); totalScore = 0; para (cromossomo chro: população) {setchromosomoscore (CHRO); if (chro.getScore ()> BestScore) {// Defina o melhor valor do gene BestScore = chro.getScore (); if (y <bestscore) {x = changex (chro); y = BestScore; genei = geração; }} if (chro.getScore () <piorscore) {// Defina o pior valor do gene piorScore = chro.getScore (); } totalsCore += chro.getScore (); } médiaCore = TotalScore / PopSize; // O valor médio causado por problemas de precisão é maior que o melhor valor, defina o valor médio como o melhor valor médioCore = médioCore> BestScore? BestScore: MédiaCore; } 4. Ao calcular a aptidão individual, precisamos calcular o valor y correspondente com base no gene. Aqui, definimos dois métodos abstratos para implementar a implementação específica pela implementação da classe.
private void setChromosomescore (cromossomo chro) {if (chro == null) {return; } duplo x = alteração (CHRO); duplo y = caculado (x); Chro.SetScore (Y); } / ** * @param chro * @return * @description: converta binário para o correspondente x * / public abstrato duplo changex (cromossomo chro); / ** * @param x * @return * @description: calcule o valor y com base em x y = f (x) */ public abstrato duplo caculado (duplo x); 5. Depois de calcular a aptidão da população, precisamos usar o método de jogo de plataforma giratória para selecionar indivíduos que podem produzir a próxima geração. Há uma condição aqui que somente se a aptidão do indivíduo não for menor que a aptidão média, a próxima geração nascerá (a sobrevivência mais apta).
cromossomo privado getParentChromOsoma () {Slice duplo = Math.random () * TotalScore; soma dupla = 0; para (cromossomo chro: população) {sum += chro.getScore (); // Vá para a posição correspondente e a aptidão não é menor que a aptidão média se (soma> slice && chro.getScore ()> = médiacore) {return chro; }} retornar nulo; } 6. Depois de selecionar indivíduos que podem produzir a próxima geração, você deve acasalar para produzir a próxima geração.
private void evolve () {list <Cromossome> ChildPopulation = new ArrayList <Cromossome> (); // gera a população da próxima geração enquanto (ChildPopulation.size () <PopSize) {cromossomo p1 = getParentChromossoma (); Cromossomo p2 = getParentChromOsomo (); Lista <Cromossome> crianças = cromossomo.genético (p1, p2); if (crianças! }}} // Substitua a população antiga por uma nova lista da população <Cromossome> t = população; População = População da criança; t.clear (); t = nulo; // mutação genética mutação (); // Calcule a aptidão da nova população cacultescore (); } 7. As mutações genéticas podem ocorrer durante o processo de produção da próxima geração.
Mutation privado void () {for (cromossomo chro: população) {if (math.random () <mutationrate) {// mutação gene ocorre int mutationNum = (int) (math.random () * maxmuationNum); chro.mutação (mutationnum); }}} 8. Repita as etapas acima uma a uma.
public void caculte () {// inicializa a geração da população = 1; init (); while (geração <maxiternum) {// popular evolução genética (); imprimir(); geração ++; }}Escreva classes de implementação
Como a classe do algoritmo genético acima é uma classe abstrata, precisamos escrever uma classe de implementação para um caso específico, assumindo que calculamos o valor máximo de y = 100 log (x) em [6,106].
1. Assumimos que o comprimento do gene é 24 (o comprimento do gene é determinado pelo comprimento efetivo do resultado necessário); portanto, o máximo binário correspondente é 1 << 24. Fazemos as seguintes configurações
classe pública genéticagorithmtest estende o GeneticGorithm {public static final int num = 1 << 24; public geneticGorithMTest () {super (24); }} 2. Implemente o método abstrato do valor x
@Override public Double Changex (cromossomo Chro) {// TODO Método Gerado Auto-Gerado Stub Return ((1.0 * chro.getnum () / num) * 100) + 6; } 3. Implemente o método abstrato de Y
@Override Public Double Caculatey (duplo x) {// TODO Method Auto -Gerated Stub Return 100 - Math.log (x); }Resultados de execução
Pensando em algoritmos genéticos
Eu li muitas apresentações aos algoritmos genéticos. As soluções ideais mencionadas acima são os mais valores da última geração. Eu tenho uma pergunta. Por que sei que os mais valores entre todas as bandas acima, ou seja, os valores XY no programa, por que não posso usar os valores XY como o valor final do resultado do algoritmo genético?
Código completo
1. Classe cromossômica
/ ***@Descrição: cromossomo genético*/ pacote com.lulei.genetic.algorithm; importar java.util.arraylist; importar java.util.list; classe pública cromossomo {private boolean [] gene; // sequência de genes de pontuação dupla privada; // Função correspondente Pontuação pública dupla getScore () {Return Score; } public void setScore (pontuação dupla) {this.score = score; } / *** Tamanho @param* Sequência genética gerada aleatoriamente* / public cromossomo (int size) {if (size <= 0) {return; } initGenesize (tamanho); for (int i = 0; i <tamanho; i ++) {gene [i] = math.random ()> = 0,5; }} / *** Gere um novo gene* / public cromossomo () {} / *** @param c* @return* @description: clonagem gene* / clone do cromossomo estático público (cromossomo final c) {if (c == null |* c.Gene == null) {retorn null; } Cópia do cromossomo = new cromossomo (); copy.initgenesize (c.gene.length); for (int i = 0; i <c.Gene.Length; i ++) {copy.Gene [i] = c.Gene [i]; } Retornar cópia; } / *** @param tamanho* @Description: Inicialize o comprimento do gene* / private void initgenesize (int size) {if (size <= 0) {return; } gene = novo booleano [tamanho]; } /** * @param c1 * @param c2 * @description: geração genética para produzir a próxima geração * /list estática pública <Cromossomem> genética (cromossomo p1, cromossomo p2) {if (p1 == null || p2 = null) {// é o próximo a um dos cromossos que é o que é necessário, o que é necessário, o que é necessário, o que é necessário, o que é necessário, o que é necessário, o que é necessário, o que é necessário, o que é necessário, o que é necessário, o que é necessário, o que é necessário, o que é necessário, o que é necessário, o que é necessário, o que é necessário, o que é necessário, o que é necessário, o que é necessário, o que é necessário, o que é necessário, o próximo a; } if (p1.gene == null || p2.gene == null) {// existe um dos cromossomos que não possui sequência genética e não produz o retorno da próxima geração; } if (p1.gene.length! = p2.gene.length) {// O comprimento da sequência do gene cromossomo não produz o retorno da próxima geração; } Cromossomo c1 = clone (p1); Cromossomo c2 = clone (p2); // Crie posições de swap cruzado aleatoriamente int size = c1.gene.length; int a = ((int) (math.random () * tamanho)) tamanho; int b = ((int) (math.random () * tamanho)) tamanho; int min = a> b? B: A; int max = a> b? A: B; // genes cromex em posições para (int i = min; i <= max; i ++) {boolean t = c1.gene [i]; c1.gene [i] = c2.Gene [i]; c2.Gene [i] = t; } List <Cromossome> list = new ArrayList <Cromossome> (); list.add (C1); list.add (c2); lista de retorno; } /*** @param num* @Description: A variação ocorre nas posições num do gene num* /public void mutação (int num) {// permitir mutação int size = gene.length; for (int i = 0; i <num; i ++) {// Pesquise a posição de mutação int em = ((int) (math.random () * size)) tamanho; // o valor após a mutação boolean bool =! Gene [at]; gene [at] = bool; }} / *** @return* @description: converta genes em números correspondentes* / public int getNum () {if (gene == null) {return 0; } int num = 0; para (bool bool: gene) {num << = 1; if (bool) {num += 1; }} retornar num; }} 2
/ ** *@Descrição: */ package com.lulei.genetic.algorithm; importar java.util.arraylist; importar java.util.list; Classe abstrata pública GeneticGorithm {Private List <Cromossome> População = novo ArrayList <Cromossome> (); private int popSize = 100; // número popular privado int genesize; // comprimento máximo do gene privado int maxiternum = 500; // Número máximo de iterações Private duplo rate mutação = 0,01; // probabilidade de mutação gene privada Int maxmuationNum = 3; // // variação máxima Atualmente? Private Double BestScore; // Melhor pontuação dupla privada piorScore; // Pior pontuação Totalscore duplo privado; // Total de pontuação dupla privada Média dupla; // Pontuação média dupla privada x; // registra o melhor valor X na população histórica dupla particular y; // registra o melhor valor y na população histórica privada int genei; // álgebra onde xy está localizado público genéticogorithm (int genesize) {this.genesize = genesize; } public void caculte () {// inicialize a geração da população = 1; init (); while (geração <maxiternum) {// popular evolução genética (); imprimir(); geração ++; }} / *** @description: resultado de saída* / private void print () { System.out.println("--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- System.Println (a pior aptidão é: "Pior. @Description: População inicial*/ privado Init () {para (int i = 0; i <POPSIZE; Void privado Evolve () {List <Cromossome> População de crianças = novo Arraylist <Cromossome> (); Cromossomo.genético (p2); cacultescore (); CHRO.GETSCORE () = Média) {Retorne Chro; (Cromossomo Chro: População) {Setchromosomescore (CHRO); // Defina o pior valor do gene = chro.getScore (); Mutation () {for (cromossomo chro: população) {if (math.random () <mutationrate) {// a mutação do gene ocorre int mutationnum = (int) (math.random () * maxmuationnum); setchomosomescores (cromossomo Chro) {if (chro == null) {return; x * @return * @description: calcule o valor Y = f (x) */ public abstrente caculado (duplo x); Genesize; getBestsCore () {Retorno BestScore; 3. Classe GeneticGorithmtest
/ ** *@Descrição: */ package com.lulei.genetic.algorithm; classe pública genéticagorithmtest estende o GeneticGorithm {public static final int num = 1 << 24; public geneticGorithMTest () {super (24); } @Override Public Double Changex (cromossomo chro) {// TODO Método Gerado Auto-Gerado Stub Return ((1.0 * chro.getnum () / num) * 100) + 6; } @Override Caculado duplo público (duplo x) {// TODO Método Gerado Auto -Gerado Stub Return 100 - Math.log (x); } public static void main (string [] args) {geneticGorithMTest test = new GenethGorithmTest (); test.caculte (); }}O acima é uma introdução detalhada ao algoritmo genético Java. Espero que seja útil para todos aprenderem o algoritmo genético Java.