рекомендации

понедельник, 4 мая 2020 г.

Введение в генетические алгоритмы с примерами


Генетический алгоритм - это эвристика поиска, основанная на теории естественной эволюции Чарльза Дарвина. Этот алгоритм отражает процесс естественного отбора, при котором наиболее подходящие особи отбираются для размножения, чтобы произвести потомство следующего поколения.


Понятие естественного отбора

Процесс естественного отбора начинается с отбора наиболее приспособленных особей из популяции. Они производят потомство, которое наследует характеристики родителей и будет добавлено к следующему поколению. Если родители лучше приспособлены, их дети будут лучше родителей и имеют больше шансов выжить. Этот процесс продолжает повторяться, и в конце, будет найдено поколение с самыми подходящими особями.


Это понятие может быть применено к проблеме поиска. Мы рассматриваем набор решений для проблемы и выбираем из них набор лучших.

В генетическом алгоритме рассматриваются пять фаз.
  1. Начальная популяция (Initial population)
  2. Функция пригодности (Fitness function)
  3. Отбор (Selection)
  4. Скрещивание (Crossover)
  5. Мутация (Mutation)

Начальная популяция

Процесс начинается с набора особей, который называется населением. Каждая особь - это решение проблемы, которую вы хотите решить.

Особь характеризуется набором параметров (переменных), известных как гены. Гены объединяются в цепочку, образуя хромосому (решение).

В генетическом алгоритме набор генов индивида представлен строкой в алфавитном порядке. Обычно используются двоичные значения (строка из 1 и 0). Мы говорим, что кодируем гены в хромосоме.


Популяция, хромосомы и гены

Функция пригодности

Функция пригодности определяет, насколько индивид подходит к решению (способность индивида конкурировать с другими индивидами). Это дает оценку пригодности для каждого индивида. Вероятность того, что индивид будет выбран для размножения, основана на его оценке пригодности.

Отбор

Идея фазы отбора состоит в том, чтобы отобрать наиболее подходящих индивидов и позволить им передать свои гены следующему поколению.

Две пары индивидуумов (родители) выбираются на основе их показателей пригодности. Индивиды с высокой пригодностью имеют больше шансов быть выбранными для размножения.

Скрещивание

Скрещивание является наиболее значимой фазой в генетическом алгоритме. Для каждой пары родителей, которые должны быть спарены, точка скрещивания выбирается из генов случайным образом.

Например, точка скрещивания может быть равна 3, как показано ниже.


Точка скрещивания

Потомки создаются путем обмена генами родителей между собой, пока не будет достигнута точка скрещивания.


Обмен генами среди родителей

Новое потомство добавляется к населению.


Новое потомство

Мутация

У определенных новых потомков некоторые из их генов могут подвергаться мутации с низкой вероятностью. Это подразумевает, что некоторые биты в битовой строке могут быть перевернуты.


Мутация: до и после

Мутация происходит для поддержания разнообразия в популяции и предотвращения преждевременной конвергенции.

Завершение

Алгоритм заканчивается, если популяция сошлась (не производит потомство, которое значительно отличается от предыдущего поколения). Далее говорят, что генетический алгоритм предоставил множество решений нашей проблемы.

Комментарии

Население имеет фиксированный размер. Когда формируются новые поколения, индивиды с наименьшей пригодностью умирают, предоставляя место для нового потомства.

Последовательность этапов повторяется, чтобы произвести индивидов в каждом новом поколении, которые лучше, чем в предыдущем поколении.

Псевдокод:

START
Generate the initial population
Compute fitness
REPEAT
    Selection
    Crossover
    Mutation
    Compute fitness
UNTIL population has converged
STOP

Пример реализации в Java

Ниже приведен пример реализации генетического алгоритма на Java. Не стесняйтесь поиграть с кодом.

Дан набор из 5 генов, каждый ген может содержать одно из двоичных значений 0 и 1.

Значение пригодности рассчитывается как число единиц, присутствующих в геноме. Если есть пять единиц, то он имеет максимальную пригодность. Если нет единиц, то у него минимальная пригодность.

Этот генетический алгоритм пытается максимизировать  функцию пригодности, чтобы обеспечить популяцию, состоящую из наиболее приспособленных индивидуумов, то есть индивидуумов с пятью единицами.

Примечание. В этом примере после скрещивания и мутации наименее приспособленная особь заменяется на новое наиболее приспособленное потомство.

import java.util.Random;

/**
 *
 * @author Vijini
 */

//Main class
public class SimpleDemoGA {

    Population population = new Population();
    Individual fittest;
    Individual secondFittest;
    int generationCount = 0;

    public static void main(String[] args) {

        Random rn = new Random();

        SimpleDemoGA demo = new SimpleDemoGA();

        //Initialize population
        demo.population.initializePopulation(10);

        //Calculate fitness of each individual
        demo.population.calculateFitness();

        System.out.println("Generation: " + demo.generationCount + " Fittest: " + demo.population.fittest);

        //While population gets an individual with maximum fitness
        while (demo.population.fittest < 5) {
            ++demo.generationCount;

            //Do selection
            demo.selection();

            //Do crossover
            demo.crossover();

            //Do mutation under a random probability
            if (rn.nextInt()%7 < 5) {
                demo.mutation();
            }

            //Add fittest offspring to population
            demo.addFittestOffspring();

            //Calculate new fitness value
            demo.population.calculateFitness();

            System.out.println("Generation: " + demo.generationCount + " Fittest: " + demo.population.fittest);
        }

        System.out.println("\nSolution found in generation " + demo.generationCount);
        System.out.println("Fitness: "+demo.population.getFittest().fitness);
        System.out.print("Genes: ");
        for (int i = 0; i < 5; i++) {
            System.out.print(demo.population.getFittest().genes[i]);
        }

        System.out.println("");

    }

    //Selection
    void selection() {

        //Select the most fittest individual
        fittest = population.getFittest();

        //Select the second most fittest individual
        secondFittest = population.getSecondFittest();
    }

    //Crossover
    void crossover() {
        Random rn = new Random();

        //Select a random crossover point
        int crossOverPoint = rn.nextInt(population.individuals[0].geneLength);

        //Swap values among parents
        for (int i = 0; i < crossOverPoint; i++) {
            int temp = fittest.genes[i];
            fittest.genes[i] = secondFittest.genes[i];
            secondFittest.genes[i] = temp;

        }

    }

    //Mutation
    void mutation() {
        Random rn = new Random();

        //Select a random mutation point
        int mutationPoint = rn.nextInt(population.individuals[0].geneLength);

        //Flip values at the mutation point
        if (fittest.genes[mutationPoint] == 0) {
            fittest.genes[mutationPoint] = 1;
        } else {
            fittest.genes[mutationPoint] = 0;
        }

        mutationPoint = rn.nextInt(population.individuals[0].geneLength);

        if (secondFittest.genes[mutationPoint] == 0) {
            secondFittest.genes[mutationPoint] = 1;
        } else {
            secondFittest.genes[mutationPoint] = 0;
        }
    }

    //Get fittest offspring
    Individual getFittestOffspring() {
        if (fittest.fitness > secondFittest.fitness) {
            return fittest;
        }
        return secondFittest;
    }


    //Replace least fittest individual from most fittest offspring
    void addFittestOffspring() {

        //Update fitness values of offspring
        fittest.calcFitness();
        secondFittest.calcFitness();

        //Get index of least fit individual
        int leastFittestIndex = population.getLeastFittestIndex();

        //Replace least fittest individual from most fittest offspring
        population.individuals[leastFittestIndex] = getFittestOffspring();
    }

}


//Individual class
class Individual {

    int fitness = 0;
    int[] genes = new int[5];
    int geneLength = 5;

    public Individual() {
        Random rn = new Random();

        //Set genes randomly for each individual
        for (int i = 0; i < genes.length; i++) {
            genes[i] = Math.abs(rn.nextInt() % 2);
        }

        fitness = 0;
    }

    //Calculate fitness
    public void calcFitness() {

        fitness = 0;
        for (int i = 0; i < 5; i++) {
            if (genes[i] == 1) {
                ++fitness;
            }
        }
    }

}

//Population class
class Population {

    int popSize = 10;
    Individual[] individuals = new Individual[10];
    int fittest = 0;

    //Initialize population
    public void initializePopulation(int size) {
        for (int i = 0; i < individuals.length; i++) {
            individuals[i] = new Individual();
        }
    }

    //Get the fittest individual
    public Individual getFittest() {
        int maxFit = Integer.MIN_VALUE;
        int maxFitIndex = 0;
        for (int i = 0; i < individuals.length; i++) {
            if (maxFit <= individuals[i].fitness) {
                maxFit = individuals[i].fitness;
                maxFitIndex = i;
            }
        }
        fittest = individuals[maxFitIndex].fitness;
        return individuals[maxFitIndex];
    }

    //Get the second most fittest individual
    public Individual getSecondFittest() {
        int maxFit1 = 0;
        int maxFit2 = 0;
        for (int i = 0; i < individuals.length; i++) {
            if (individuals[i].fitness > individuals[maxFit1].fitness) {
                maxFit2 = maxFit1;
                maxFit1 = i;
            } else if (individuals[i].fitness > individuals[maxFit2].fitness) {
                maxFit2 = i;
            }
        }
        return individuals[maxFit2];
    }

    //Get index of least fittest individual
    public int getLeastFittestIndex() {
        int minFitVal = Integer.MAX_VALUE;
        int minFitIndex = 0;
        for (int i = 0; i < individuals.length; i++) {
            if (minFitVal >= individuals[i].fitness) {
                minFitVal = individuals[i].fitness;
                minFitIndex = i;
            }
        }
        return minFitIndex;
    }

    //Calculate fitness of each individual
    public void calculateFitness() {

        for (int i = 0; i < individuals.length; i++) {
            individuals[i].calcFitness();
        }
        getFittest();
    }

}

Пример вывода, где наиболее подходящее решение найдено в 32-м поколении:


Комментариев нет:

Отправка комментария