Генетический алгоритм: оптимальное решение не найдено в самых базовых математических вычислениях

Question

Я реализую генетический алгоритм в C # WinForms, чтобы найти оптимальное решение очень простого математического уравнения. Слово «простой» здесь означает, что уравнение должно иметь следующие качества:

• Только состоит из целых положительных чисел
• Конечным результатом уравнения должно быть положительное число, меньшее 1001
• Допускается минимум от 2 переменных до максимум 7 переменных
• Коэффициенты каждой переменной должны быть от 1 до 10 (нижняя граница и верхняя граница включительно)
• Значения переменных от 0 до 500
• Допускается только добавление

Я думал, что смогу найти оптимальное решение с таким «простым» уравнением, можно сказать. Однако я всегда получаю только решение, очень близкое к оптимальному. Чтобы оценить, является ли решение оптимальным, я использую следующую формулу:

f(x) = absolute((sum_of_all_variables) - equation_result)

Например, у меня есть следующее уравнение:

1a + 1b = 12

Если a равно 2 и b равно 3, то f(x) указанного лица будет abs(2 + 3 - 12) = 7. Мой код останавливается, когда f(x) достигает 0 или я генерировал 50 поколений.

Моя текущая частота мутаций составляет 50%, а моя текущая частота кроссовера составляет 25%. Используемый метод выбора - выбор колеса рулетки. Метод мутации - это случайная мутация, т. Е. Я просто выбираю случайный ген из своего пула генов, чтобы изменить его значение, до 50% генов меняются за поколение.

Мои ожидания : код выдает решение (индивидуальное) со значением f(x), равным 0, что является одним из оптимальных доступных решений.

Текущий результат : код дает решение, которое почти оптимально. Один из распространенных шаблонов, который я обнаружил, заключается в том, что решения, которые являются почти оптимальными, часто воспроизводятся именно в следующем поколении. Мое предположение о проблеме сейчас :

Я думаю, что это как-то связано с тем, как я делаю свои кроссоверы. Что я делаю для кроссовера:

• Назначьте случайное значение каждому человеку
• Если указанное случайное значение меньше скорости кроссовера, сохраните данные этого индивидуума для последующего использования для кроссовера
• После сбора всех подлежащих пересечению лиц я случайным образом выбираю точку пересечения для каждого индивидуума
• Я думаю, что это проблема : я делаю кроссовер на первом человеке со вторым человеком в списке «подлежащий пересечению», объединяя гены из первого человека и второго человека, который должен быть кроссовером Затем перейдите ко второму человеку и третьему лицу и так далее. Последний человек будет пересечен с первым человеком.

Однако, как я уже сказал, это не дает оптимального результата. Это проблема с моей логикой или это ожидаемое поведение генетического алгоритма в этом простом математическом уравнении?

Методы кроссовера, которые я использую для справки (я использую C # WinForms для отображения данных в ListView):

private static void Crossover(List<Chromosome> chromosomes, Random seed)
{            
    List<int> crossoverChromosome = new List<int>();

    for (int i = 0; i < 50; i++)
    {
        decimal randomedValue = RandomizeValue(seed);            
        if (randomedValue < Population.CrossoverRate) crossoverChromosome.Add(i);                
    }

    for (int i = 0; i < crossoverChromosome.Count; i++)
    {
        int crossoverPoint = seed.Next(0, chromosomes[0].GeneValues.Count);
        chromosomes[crossoverChromosome[i]] = chromosomes[crossoverChromosome[i]].MixChromosome(chromosomes[crossoverChromosome[(i + 1) % crossoverChromosome.Count]], crossoverPoint);
    }
}

private static decimal RandomizeValue(Random seed)
{
    return Math.Round((decimal)seed.NextDouble(), 5);
}

public Chromosome MixChromosome(Chromosome mixture, int crossoverPoint)
{
    List<Gene> newGenes = new List<Gene>();
    newGenes.AddRange(this.GetGenes(0, crossoverPoint));
    newGenes.AddRange(mixture.GetGenes(crossoverPoint, this.GeneValues.Count));

    return new Chromosome(DesiredValue, OperatorData, newGenes); // Ignore the DesiredValue and Operator Data, it has nothing to do with crossover
}

private List<Gene> GetGenes(int firstIndex, int lastIndex)
{
    List<Gene> slicedGenes = new List<Gene>();

    for (int i = firstIndex; i < lastIndex; i++)
    {
        slicedGenes.Add(Genes[i].CloneGene());
    }

    return slicedGenes;
}

Я только тщательно протестировал уравнения с двумя переменными.

EDIT

Дополнительная информация:

• Я не пользуюсь элитарностью
• Начальная численность населения = 50 особей
• Численность населения на поколение = 50 особей

10 повторений по уравнению 1a + 1b = 10 дает следующие наилучшие значения пригодности после 50 поколений:

• Первый повтор: 24
• Второй повтор: 11
• Третий повтор: 42
• Четвертый повтор: 13
• Пятый перезапуск: 5
• Шестой повтор: 19
• Седьмой перезапуск: 7
• Восьмой повтор: 1
• Девятый повтор: 6
• Десятый повтор: 29
• Дополнительная информация о каждом повторном запуске: хромосома, которая дает наилучшее значение пригодности за 50 поколений, часто повторяется в популяции. Например, при восьмом повторном запуске я нахожу много случаев с хромосомой значение a 4 и значение b 7.

Answer 1

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

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

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

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

Один из распространенных способов сделать это - использовать фитнес-пропорциональный отбор , который выберет особей для случайного размножения, но на основе значений пригодности. Так что особи с высокой приспособленностью (те, которые приводят к результату, близкому к правильному в вашем примере) имеют более высокий шанс воспроизведения .

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

Пример реализации Fitness-Proportional-Selection может выглядеть так (к сожалению, это java-код и нет C #, но они очень похожи ...):

import java.util.concurrent.ThreadLocalRandom;

import com.google.common.annotations.VisibleForTesting;

/**
 * A selector that randomly chooses pairs to be selected for reproduction based on their probability to be selected.
 */
public class FitnessProportionalSelector implements Selector {

    /**
     * Select pairs of parents (by index) that are combined to build the next generation.
     * 
     * @param selectionProbability
     *        The probability to be selected for every DNA in the current population (sums up to 1).
     * 
     * @param numPairs
     *        The number of pairs needed (or the number of individuals needed in the next generation).
     * 
     * @return Returns an int-array of size [numPairs * 2] including the pairs that are to be combined to create the next population (a pair is on
     *         position [i, i+1] for i % 2 = 0).
     */
    @Override
    public int[] select(double[] selectionProbability, int numPairs) {
        double[] summedProbabilities = Selector.toSummedProbabilities(selectionProbability);
        int[] selectionPairs = new int[numPairs * 2];
        double chosenProbability;

        for (int i = 0; i < numPairs * 2; i++) {
            chosenProbability = getRandomNumber();
            selectionPairs[i] = Selector.getSelectedIndexByBisectionSearch(summedProbabilities, chosenProbability);
        }

        return selectionPairs;
    }

    @Override
    public String toString() {
        return "FitnessProportionalSelector []";
    }

    @VisibleForTesting
    /*private*/ double getRandomNumber() {
        return ThreadLocalRandom.current().nextDouble();
    }
}

Или решение для Stochastically-Distributed-Selection (также в java):

import java.util.concurrent.ThreadLocalRandom;

import com.google.common.annotations.VisibleForTesting;

/**
 * A selector that chooses the pairs to be reproduced by a stochastically distributed selection method.
 * 
 * The selection probability is proportional to the given probability, but it's ensured, that individuals with a probability above average are chosen
 * at least once.
 */
public class StochasticallyDistributedSelector implements Selector {

    /**
     * Select pairs of parents (by index) that are combined to build the next generation.
     * 
     * @param selectionProbability
     *        The probability to be selected for every DNA in the current population (sums up to 1).
     * 
     * @param numPairs
     *        The number of pairs needed (or the number of individuals needed in the next generation).
     * 
     * @return Returns an int-array of size [numPairs * 2] including the pairs that are to be combined to create the next population (a pair is on
     *         position [i, i+1] for i % 2 = 0).
     */
    @Override
    public int[] select(double[] selectionProbability, int numPairs) {
        double[] summedProbability = Selector.toSummedProbabilities(selectionProbability);
        int[] selectedPairs = new int[2 * numPairs];
        double startPoint = getRandomNumber();
        double addedAverage = 1d / (2d * numPairs);
        double stochasticallySelectedProbability;

        for (int i = 0; i < numPairs * 2; i++) {
            //select the pairs stochastically
            stochasticallySelectedProbability = startPoint + i * addedAverage;
            stochasticallySelectedProbability %= 1;
            selectedPairs[i] = Selector.getSelectedIndexByBisectionSearch(summedProbability, stochasticallySelectedProbability);
        }

        //shuffle the pairs to distribute them stochastically
        shuffle(selectedPairs);

        return selectedPairs;
    }

    @VisibleForTesting
    /*private*/ void shuffle(int[] selectedPairs) {
        //shuffle the selected pairs in place
        int swapIndex;
        int tmp;
        for (int i = selectedPairs.length - 1; i > 0; i--) {
            swapIndex = (int) (getRandomNumber() * (i + 1));

            tmp = selectedPairs[i];
            selectedPairs[i] = selectedPairs[swapIndex];
            selectedPairs[swapIndex] = tmp;
        }
    }

    @VisibleForTesting
    /*private*/ double getRandomNumber() {
        return ThreadLocalRandom.current().nextDouble();
    }

    @Override
    public String toString() {
        return "StochasticallyDistributedSelector []";
    }
}

Я взял эти примеры кодов из проекта генетического оптимизатора , который я создал для своей магистерской работы . Если вы хотите взглянуть на него, вы можете найти его в моем аккаунте на github

Некоторые дальнейшие улучшения :

• попробуйте использовать среднеквадратическую ошибку вместо абсолютного значения (f (x) = абсолютное ((sum_of_all_variables) - уравнение_результата))
• использование давления выбора - еще один хороший способ выбрать правильных особей для размножения (и получить параметры для схождения); вы можете найти решение в проекте github в пакете генетический_оптимизатор.selection, если вам нужны примеры.
• элитарность здесь очень полезна, чтобы не потерять лучшее решение, которое у вас уже есть (по крайней мере, если вы не оставите его в популяции, сохраните его, чтобы вернуть его после расчета)