Начальная реализация алгоритма Geneti c - PullRequest
Новая
       95

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

1 голос
/ 21 апреля 2020

В последнее время меня интересовали алгоритмы Geneti c, и я пытался написать простой код алгоритма Geneti c для начинающих, чтобы понять его. Я взял функцию f(x)=x^2 и хотел минимизировать ее для домена {0,1,....31}. Теперь я знаю, что оптимальным значением является 31, но я хотел реализовать его с помощью GA, поэтому я написал код. Я sh знаю, что (i) мой код даже близок к тому, что делает GA, (ii) если это достойный код уровня новичка, что все улучшения могут быть сделаны в этом, (iii) так как в этой задаче я знаю что значение должно быть 31, но когда мой GA останавливается ?, (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

1 Ответ

0 голосов
/ 22 апреля 2020

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

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

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

...