Impact des performances de différentes façons d'effectuer des opérations génétiques sur le génome d'un algorithme génétique multivariable

Question

J'utilise beaucoup les algorithmes génétiques dans mes recherches et j'ai rencontré une question intéressante sur la meilleure façon d'effectuer vos opérations génétiques sur un génome. Supposons que vous ayez une fonction définie par f (x, y) = a x^n + b x^n-1 + ... + c y^m + d y^m-1 ... etc. C'est juste une fonction multivariable qui est assez chère à calculer, donc vous essayez d'être aussi efficace que possible avec vos opérations génétiques.

Si vous utilisez une représentation binaire du génome, j'ai compris qu'il y a 2 façons raisonnables d'effectuer les opérations génétiques. Regardons juste la scène du crossover.

Voici le code pour une sélection de tournois vectorisé dans Matlab (pour le contexte de noms de variables)

%% Tournament Selection 
T = round(rand(2*popSize,S)*(popSize-1)+1);  % Tournaments 
[~,idx] = max(F(T),[],2);      % Index of Winners 
W = T(sub2ind(size(T),(1:2*popSize)',idx));  % Winners 

Vous avez donc 2 variables différentes qui sont en cours d'optimisation et ma question est de savoir si vous voulez diviser la opérations génétiques de sorte que vous avez un crossover appliqué à chaque variable individuellement et concaténer ensuite les tableaux de retour ensemble qui ressemblerait à ceci pour un crossover 2 points:

%% 2 Point Crossover 

Pop2 = Pop(W(1:2:end),:);     % Set Pop2 = Pop Winners 1 
P2A = Pop(W(2:2:end),:);     % Assemble Pop2 Winners 2 

% Split Pop2 for x and y genomes 
xPop2 = Pop2(:,1:genome/2); 
yPop2 = Pop2(:,genome/2 + 1:end); 

% Split P2A for x and y genomes 
xP2A = P2A(:,1:genome/2); 
yP2A = P2A(:,genome/2+2:end); 

% For x genome 
Ref = ones(popSize,1)*(1:genome/2);      % Reference Matrix 
CP = sort(round(rand(popSize,2)*(genome/2-1)+1),2); % Crossover Points 
xidx = CP(:,1)*ones(1,genome/2)<Ref & CP(:,2)*ones(1,genome/2)>Ref; % Logical Index 
xPop2(xidx) = xP2A(xidx);      % Recombine Winners 


% For y genome 
Ref = ones(popSize,1)*(1:genome/2);      % Reference Matrix 
CP = sort(round(rand(popSize,2)*(genome/2-1)+1),2); % Crossover Points 
yidx = CP(:,1)*ones(1,genome/2)<Ref & CP(:,2)*ones(1,genome/2)>Ref; % Logical Index 
yPop2(yidx) = yP2A(yidx);      % Recombine Winners 

Pop2 = horzcat(xPop2,yPop2); 
P2A = horzcat(xP2A,yP2A); 

ou traitez-vous le génome comme une opération de croisement unique d juste effectuer le croisement de 2 points comme si elle était un seul génome variables comme celui-ci:

Pop2 = Pop(W(1:2:end),:); % New Pop is Winners of old Pop 
P2A = Pop(W(2:2:end),:); % Assemble Pop2 Winners 2 
Ref = ones(popSize,1)*(1:genome); % Ones Matrix 
CP = sort(round(rand(popSize,2)*(genome-1)+1),2); % Crossover Points 
idx = CP(:,1)*ones(1,genome)<Ref&CP(:,2)*ones(1,genome)>Ref; % Index 
Pop2(idx)=P2A(idx); % Recombine Winners 

Est-ce que quelqu'un sait de toute la recherche qui a été fait qui montre la différence entre les 2 différentes façons de représenter les génomes? Je n'ai pas pu trouver quelque chose publié à ce sujet, mais c'est peut-être parce que je ne savais pas comment écrire intelligemment ma question dans google.

Merci

Answer 1

Mon principal commentaire sont les suivantes:

1. La mutation étape fortement dépend du type de problème.

2. Pour continue, non linéaire, les problèmes dynamiques, comme le Météo météorologique problème physique vous avez cité, avec des processus d'estimation et de prévision, encore un cadre GA pourrait effectuer très bien, si elle est indiquée correctement et toujours avec un accent clair sur ce que vous poursuivez avec lui. Une stratégie de mutation discrète - telle que la présentation sélective unique présentée - serait très médiocre, tout comme une recherche bruteforce non aléatoire standard. Comme vous l'avez dit, en effet, c'est l'approche la plus naïve. La performance & temps d'exécution, va exprimer ce fait de manière irréfutable. Le problème est clair - et je suppose qu'il y en a trop -, et donc, étant donné qu'il y a un système dynamique, probablement avec un certain nombre d'états, finis ou non, et une certaine continuité sur le variables, et avec ou sans un certain degré de non-linéarité, l'accent GA principal ici devrait impliquer Bayesian Estimators.Sous ce contexte, chaque gagnant ou individus -ou tout autre mot descriptif que vous souhaiteriez apply- aurait une phase de mutation ne repose pas sur un simple échange des paramètres. Ceci est juste l'explication la plus simple, plus facile, plus brillante pour GA. La meilleure façon, plus rapide et efficace d'interpréter l'étape de mutation sur ce contexte est d'appliquer un estimateur statistique capable de recueillir le gradient approprié à partir de ce système non linéaire dynamique, estimé à chaque étape. Sous Bayesian GA cadre, Les filtres à particules sont une alternative intéressante pour préparer un bon stade de la mutation. Le fait que vous utilisiez plusieurs intégrales imbriquées m'éclaire en pensant que votre problème est vraiment dynamique. Et dans ce contexte, orienter l'AG par un cadre bayésien plus statistique me fait beaucoup de sens. Rappelez-vous que les méthodes bayésiennes sont également robustes dans certaines conditions.

3. Si le problème est clairement dynamique, vous devez alors faire face à la vérité, et compte tenu de défausse GA, et de passer à une optimisation non linéaire techniques. Même, Estimation des paramètres, et Les méthodes d'identification du système fonctionneraient même mieux, si le problème peut être correctement exprimé comme un processus de recherche de paramètres à la place.

4. Par autre manière, si votre problème est en aucune façon distincte discrète -Que est, si vous ne disposez pas d'expressions de prélivraison de toute nature, ou si ces PDEs sont vraiment trivial à résoudre, ou si aucun problème physique impliquant des états - et votre problème repose principalement sur des règles expertes, des recherches de bases de données ou le traitement de grands systèmes de données et vous avez écarté - pour toute raison que vous trouvez pertinente - de ne pas avoir un modèle dynamique de ces données et seulement alors, je voudrais essayer de guider le GA comme une méthode de force brute, avec des étapes croisées au hasard entre les meilleures solutions. Un cadre discret bayésien serait même utile ici, à partir des estimations de probabilité pour chaque stade de la mutation.

Si vous avez plus d'informations, je pourrais faire cette réponse evolve ....

Meilleurs voeux, et de la chance hypfco