3

我在研究中经常使用遗传算法，并且遇到了一个有趣的问题，即如何最好地在基因组上执行遗传操作。假设您有一个由 f(x,y) = a x^n + b x^n-1 + ... + c y^m + d y^m-1 ... 等定义的函数。它只是一个多变量计算起来有些昂贵的函数，因此您正在尝试尽可能高效地进行遗传操作。

如果您使用的是基因组的二进制表示，我发现有两种合理的方法可以执行遗传操作。让我们只看交叉阶段。

这是 Matlab 中矢量化锦标赛选择的代码（用于变量名称的上下文）

%% 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

因此，您有 2 个不同的变量正在优化，我的问题是您是否要拆分遗传操作，以便将交叉分别应用于每个变量，然后将数组重新连接在一起，这对于 2 点来说看起来像这样交叉：

%% 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);

或者您是否将基因组视为单个交叉操作，并且只执行 2 点交叉，就好像它只是一个像这样的单个变量基因组：

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

有谁知道已经进行的任何研究表明两种不同的基因组表示方式的差异？我还没有找到任何关于它的发布，但这可能只是因为我不知道如何在谷歌中智能地表达我的问题。

谢谢

4

1 回答 1

2

我的主要评论如下：

  1. 突变阶段很大程度上取决于问题类型。

  2. 对于连续的、非线性的、动态的问题，例如您引用的天气气象物理问题，通过估计和预测过程，如果表述得当并且始终明确关注您所追求的， GA框架仍然可以很好地执行和他一起。一个离散的突变策略——比如提出的单一选择性交叉——会表现得很差，就像标准的非引导、随机、蛮力搜索一样。正如你所说，这确实是最天真的方法。性能和执行时间，将毫无疑问地表达这一事实。

  3. 明确问题是物理问题——我假设太多了——因此，假设存在一个动态系统，可能具有一定数量的状态，无论是否有限，并且给定变量具有一定的连续性，并且具有或如果没有一些非线性度，这里的主要 GA 重点应该涉及贝叶斯估计器。在这种情况下，每个获胜者或个人- 或您希望应用的任何其他描述性词 - 都会有一个突变阶段，而不是基于简单的参数交换。这只是对GA最简单、更容易、更闪亮的解释。解释突变的更好、更快、更有效的方法在这种情况下，stage 等于应用一个统计估计器，该统计估计器能够从这个动态非线性系统中收集适当的梯度，在每个阶段进行估计。在贝叶斯 GA框架下，粒子过滤器是一个有趣的替代方案，用于准备一个好的突变阶段。

  4. 您使用多个嵌套积分的事实启发我认为您的问题是真正动态的。在这种情况下，通过更具统计性的贝叶斯框架来指导 GA 让我很有意义。请记住，贝叶斯方法在某些条件下也是稳健的。

  5. 如果问题显然是动态的，那么您应该面对事实，并考虑丢弃GA并转向非线性优化技术。甚至 ，如果问题可以适当地表示为参数搜索过程，参数估计和系统识别方法甚至会表现得更好。

  6. 换句话说，如果你的问题是不可区分的离散的——也就是说，如果你没有任何类型的 PDE 表达式，或者如果这些 PDE 真的很容易解决，或者显然没有任何涉及状态的物理过程- 你的问题主要是基于专家规则、数据库查找或处理大型数据系统，而你已经丢弃 - 出于任何你认为相关的原因 - 没有来自这些数据的动态模型 - 然后，只有这样，我才会尝试引导GA作为一种蛮力方法，在更好的解决方案之间具有随机交叉阶段。从每个突变阶段的概率估计来看，离散贝叶斯框架甚至在这里很有用。

如果您有更多信息，我可以做出这个答案evolve....

最良好的祝愿，好运 hypfco

于 2015-04-18T06:41:12.723 回答