Начальная реализация генетического алгоритма

В последнее время я заинтересовался генетическими алгоритмами и пытался написать простой код генетического алгоритма как новичок, чтобы понять его. Я взял функцию f(x)=x^2 и хотел минимизировать ее по домену {0,1,....31}. Теперь я знаю, что оптимальное значение равно 31, но я хотел реализовать его с помощью GA, поэтому написал код. Я хочу знать, (i) близок ли мой код к тому, что делает GA, (ii) если это достойный код для начинающих, какие улучшения можно сделать в нем, (iii) поскольку в этой задаче я знаю, что значение должно быть 31, но когда мой ГА остановится?, (iv) разве алгоритм на самом деле не зависит от генерации случайных чисел, поэтому я могу случайно получить решение только в первой итерации и, следовательно, иногда может вводить в заблуждение, так что все параметры надо проверять. Вот мой грубый код (простите меня за это, это моя первая попытка)

%Maximize the function f(x)=x^2;
% Using GA in the domain [0,31];

% We take 4 initial candidates as solutions only 5 bits
x=rand(1,20);
A=(x<0.5);


% Checking for randomness
A=reshape(A,4,[]) ;

B_DEC=bi2de(A,'left-msb');
Y=B_DEC.^2;
%FIT=B_dec./sum(B_dec(:))% Fitness function
for loop=1:3


    [~,index]=sort(Y,'descend');
    B_DEC=B_DEC(index)   ; % Sorting the values
    FIT=B_DEC./sum(B_DEC(:));


    MATING_POOL(1:2)=B_DEC(1,:);
    MATING_POOL(3:4)=B_DEC(2:3,:);
    MATING_POOL=de2bi(MATING_POOL,'left-msb');

    CHOOSE=randi([3,4]);
    C=(rand(1,5)<0.5);
    ind=find(C>0);

    New(1,ind)=MATING_POOL(1,ind);
    ind=find(C<=0);
    New(1,ind)=MATING_POOL(CHOOSE,ind);


    C=(rand(1,5)<0.5)
    ind=find(C>0);

    New(2,ind)=MATING_POOL(CHOOSE,ind);
    ind=find(C<=0);
    New(2,ind)=MATING_POOL(1,ind);


    if mod(CHOOSE,4)==3
        C=(rand(1,5)<0.5);
        ind=find(C>0);

        New(3,ind)=MATING_POOL(2,ind);
        ind=find(C<=0);
        New(3,ind)=MATING_POOL(4,ind);


        C=(rand(1,5)<0.5);
        ind=find(C>0);

        New(4,ind)=MATING_POOL(4,ind);
        ind=find(C<=0);
        New(4,ind)=MATING_POOL(2,ind);

    else
        C=(rand(1,5)<0.5);
        ind=find(C>0);

        New(3,ind)=MATING_POOL(2,ind);
        ind=find(C<=0);
        New(3,ind)=MATING_POOL(3,ind);


        C=(rand(1,5)<0.5)
        ind=find(C>0);

        New(4,ind)=MATING_POOL(3,ind);
        ind=find(C<=0);
        New(4,ind)=MATING_POOL(2,ind);
    end

    B_dec=bi2de(New,'left-msb');

    Y=B_DEC.^2;
end

matlab mathematical-optimization genetic-algorithm genetic-programming
person USERNEW    schedule 21.04.2020    source источник

Ответы (1)


arrow_upward
0
arrow_downward

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

  • Ваша популяция не закодирована генетически. Вы не определили генетический перевод вашего генотипа (генетического представления) в фенотип (функция, в которую транслируется генетически закодированный генотип). Примером может быть следующее: давайте повторно используем ваше генетическое пространство поиска, описанное как целые числа в диапазоне [0; 31]. Ваше генетическое кодирование — это перевод генотипа (в данном случае целого числа) в функцию, например: f(a) = ax^2 - a.
  • Хотя ваша фитнес-функция возвращает значение, которое можно интерпретировать как фитнес-функцию, не является ли она законной фитнес-функцией в том смысле, что входные данные для вашей фитнес-функции не являются функцией. В качестве примера можно привести правильную функцию пригодности при повторном использовании приведенного выше генетического кодирования вычисления среднеквадратичной ошибки между f (a) и x ^ 3 + x ^ 2 для x между [0; 10]
  • Другой фундаментальной концепцией ГА является определенный способ мутации генотипа или скрещивания двух генотипов. Примером мутации ГА является добавление случайного значения между -5 и 5. Примером кроссовера между двумя генотипами является среднее значение обоих.
  • Генетические алгоритмы обычно представляют собой метод оптимизации на основе популяции, поэтому вам необходимо определить несколько генотипов, сравнить их пригодность, выборочно вывести (мутировать и скрестить) подходящие и удалить низкоэффективные в каждом поколении.
  • И чтобы ответить на 2 ваших конкретных вопроса: GA так же безграничен, как и его пространство поиска генотипа. Поскольку пространство поиска генотипа в вашем примере ограничено, ГА останавливается, когда пространство поиска исчерпано. ГА также часто в значительной степени основаны на случайности. Поэтому лучшее решение можно найти в первом поколении.

Бесстыдная вилка, если вы хотите прочитать о некоторых фундаментальных концепциях нейроэволюции (которая в основном представляет собой генетические алгоритмы с ограничением, что все генотипы преобразуются в искусственные нейронные сети): https://towardsdatascience.com/9068f532f7f7

person PaulOnStackoverflow    schedule 21.04.2020