matlab-genetic-toolbox-2

Jan 15, 2016 · matlab 算法  ·
分享到:

MatLab遗传算法工具箱（Sheffield）源码解析（2）

适应度计算函数

目标函数与适应度函数

目标函数和适应度函数是GA算法中非常重要的两个概念。目标函数（objective function），是衡量一个种群的个体好坏的判别式。通常，目标函数是我们需要解决的问题。例如在$f(x)=\frac{sin(10\pi x)}{x}$,$f(x)$就是目标函数，我们可以直接通过目标函数判断某个个体的好坏，比如求$min_{f(x)}$,适应度最好的个体就是使$f(x)$最小的个体。

但是，$f(x)$的值域是不确定的，在一个函数中很大的值在另一个函数中有可能只是沧海一粟，绝对值的比较在GA算法中意义不太，而且直接用目标函数的值去进行“选择”操作也不太好操作，因此需要将$f(x)$的值做一些规划与变换，将$f(x)$的值由绝对值转换成相对值，即$F(x)=g(f(x))$,$F(x)$表示相对的适应度，这个变化的函数$g(\cdot )$，我们称之为适应函数(fitness function)。GA Manual中的解释为：

The fitness function, is normally used to transform the objective function value into a measure of relative fitness.$^{[1]}$

matlab的Sheffield工具箱中，适应度计算函数共有一下两个：

1% Fitness assignment
2%   ranking - rank-based fitness assignment
3%   scaling - proportional fitness-scaling

Scaling

适应函数,原理是将本来不可限制的值域映射到一个指定的范围中。最简单的适应函数就是按比例归一化，将值域映射到(0,1)上。公式表达为

$F(x_i) =\frac{f(x_i)}{\sum_{i=1}^{N_{ind}} f(x_i)}$

其中，$N_{ind}$是种群的数量，$x_i$是每一个基因的表现性（即二进制编码对应目标函数定义域的值）。这种适应函数直观容易理解，每一个个体繁殖的概率和它的适应能力成正比。换一个通用的表达式：

$F(x)=af(x)+b$

其中，a是缩放因子，我们如果求目标最大值，则a为正；反之，a为负。b为偏移量，用来保证$F(x)$非负。但是这种适应函数对于负数无能为力，同时容易快速收敛（这会降低找到全局最优的概率）。因为在完全线性的变换中，一旦一个种群在早期出现一个明显优秀的个体，那么根据繁殖概率正比于适应能力，这个个体将主导种群的繁衍，如果这个个体是一个局部最优，这种线性变化能以跳出局部最优的限制。scaling函数就是这种使用$F(x)=af(x)+b$的适应函数，这个变换的优点明显：简单易用。scaling函数的参数计算有些难以理解的地方，也不推荐使用，这里按下不表。

Ranking

线性适应函数

于是，有很多人提出了其他的适应函数。在GA工具箱中，大体分为线性和非线性两类。线性适应函数形如：，Baker$^{[2]}$提出了基于限定范围和划分等级的适应函数（大概是这个意思）。首先，选定一个MAX值，用来决定对最好个体的偏好（这个值在文献也有被翻译为压差，selective pressure），然后规定了以下几个值：

  • $MIN = 2.0 - MAX$
  • $INC = (MAX -MIN)/N_{ind} = 2.0 * (MAX-1.0)/N_{ind}$
  • $LOW = INC / 2.0$

MAX通常取在[1.1,2.0]之间，MIN表示下界。将[MIN,MAX]划分成$N_{ind}$份，INC表示相邻两个等级之间差距，LOW表示选择的次数？？。因此，可以将目标函数做如下变化：

$F(x_i) = MIN + 2(MAX-1.0)\frac {x_i-1}{N_{ind}-1}$ 可以看出后面一项是INC的变形，分成$N_{ind}-1$份是因为包括了上下边界。

这个式子中最重要的${x_i}$，这个是将$N_{ind}$个个体按照排序（从大到小，或者从小到大，根据求最大还是最小值）之后，在排序中的位置。

非线性适应函数

非线性函数使用的是指数分割的方法。

适应值的分配

我们如果不考虑多种群的场景，函数中适应值的分配很简单，按照目标值大小分配适应值。

实现代码

 1function FitnV = cxranking(ObjV, RFun, SUBPOP)
 2
 3    %Identify the vector size (Nind)
 4    [Nind,~] = size(ObjV);
 5
 6    %第二个参数的处理
 7    if nargin < 2, RFun = [] ;end %仅有一个参数，后面会有默认赋值
 8    if nargin > 1 % 不合理RFun的处理
 9        if isnan(RFun), RFun = [];end
10    end
11    % numel函数返回的是矩阵中元素的个数,增强性能
12    if numel(RFun) == 2 % RFun 为1行2列的向量
13        if RFun(2) == 1, NonLin = 1; %判断线性还是非线性
14        elseif RFun(2) == 0, NonLin = 0;
15        else error('Parameter for ranking method must be 0 or 1');
16        end
17        RFun = RFun(1);
18        if isnan(RFun), RFun = 2; end
19    elseif numel(RFun) >2, % RFun是一个列向量，列向量和ObjV对应 
20        if numel(RFun) ~= Nind, error('ObjV and RFun disagree'); end
21    end
22
23    %第三个参数分组的处理
24    if nargin < 3,  SUBPOP = 1; end
25    if nargin > 2,
26      if isempty(SUBPOP), SUBPOP = 1;
27      elseif isnan(SUBPOP), SUBPOP = 1;
28      elseif length(SUBPOP) ~= 1, error('SUBPOP must be a scalar'); 
29      end
30    end    
31    %分组必须能够整除总数
32    if (Nind/SUBPOP) ~= fix(Nind/SUBPOP), error('ObjV and SUBPOP disagree'); end
33    Nind = Nind/SUBPOP;  % Compute 
34
35    % Check ranking function and use default values if necessary
36    if isempty(RFun)       %为空的时候，采用默认值
37        % 默认值：selective pressure： 2，线性
38        RFun = 2* [0:Nind-1]'/(Nind-1);
39    elseif numel(RFun) == 1  %RFun在之前已经处理过，变成一个标量
40        if NonLin == 1 
41            %非线性处理,指数分割
42            if RFun(1) < 1, error('Selective pressure must be greater than 1');
43            elseif RFun(1) > Nind-2, error('Selective pressure too big'); 
44            end
45            Root1 = roots([RFun(1)-Nind [RFun(1)*ones(1,Nind-1)]]);
46            %指数分割
47            RFun = (abs(Root1(1)) * ones(Nind,1)) .^ [(0:Nind-1)'];
48            RFun = RFun / sum(RFun) * Nind;
49        else
50            %线性处理
51            % linear ranking with SP between 1 and 2
52            if (RFun(1) < 1 || RFun(1) > 2),
53                error('Selective pressure for linear ranking must be between 1 and 2');
54             end
55             RFun = 2-RFun + 2*(RFun-1)*[0:Nind-1]'/(Nind-1);
56        end
57    end
58    
59       FitnV = [];
60
61       %子群处理
62% loop over all subpopulations
63for irun = 1:SUBPOP,
64   % Copy objective values of actual subpopulation
65      ObjVSub = ObjV((irun-1)*Nind+1:irun*Nind);
66   % Sort does not handle NaN values as required. So, find those...
67      NaNix = isnan(ObjVSub);
68      Validix = find(~NaNix);
69   % ... and sort only numeric values (smaller is better).
70      [~,ix] = sort(-ObjVSub(Validix));
71
72   % Now build indexing vector assuming NaN are worse than numbers,
73   % (including Inf!)...
74      ix = [find(NaNix) ; Validix(ix)];
75   % ... and obtain a sorted version of ObjV
76      Sorted = ObjVSub(ix);
77
78   % Assign fitness according to RFun.
79      i = 1;
80      FitnVSub = zeros(Nind,1);
81      for j = [find(Sorted(1:Nind-1) ~= Sorted(2:Nind)); Nind]',
82         FitnVSub(i:j) = sum(RFun(i:j)) * ones(j-i+1,1) / (j-i+1);
83         i =j+1;
84      end
85
86   % Finally, return unsorted vector.
87      [~,uix] = sort(ix);
88      FitnVSub = FitnVSub(uix);
89
90   % Add FitnVSub to FitnV
91      FitnV = [FitnV; FitnVSub];
92end
93
94
95% End of function

未完成：多种群

参考文献

[1] K. A. De Jong, Analysis of the Behaviour of a Class of Genetic Adaptive Systems, PhD Thesis, Dept. of Computer and Communication Sciences, University of Michigan, Ann Arbor, 1975.

[2] J. E. Baker, “Adaptive Selection Methods for Genetic Algorithms”, Proc. ICGA 1, pp. 101-111, 1985.