对遗传算法的定义有了初步的了解后，咱们再看一下遗传算法的基本算法
其中，P_co是染色体的交叉率，P_mut是染色体的变异率，theta是适应度的阈值。
总结来说：遗传算法的基本步骤如下:
使用遗传算法需要决定的运行参数有:编码串长度、种群大小、交叉和变异概率。编码串长度由优化问题所要求的求解精度决定。种群大小表示种群中所含个体的数量,种群较小时,可提高遗传算法的运算速度,但却降低了群体的多样性,可能找不出最优解;种群较大时,又会增加计算量,使遗传算法的运行效率降低。一般取种群数目为20～100。交叉概率控制着交叉操作的频率,由于交叉操作是遗传算法中产生新个体的主要方法,所以交叉概率通常应取较大值;但若过大的话,又可能破坏群体的优良模式。一般取0.4～0.99。变异概率也是影响新个体产生的一个因素,变异概率小,产生新个体少;变异概率太大,又会使遗传算法变成随机搜索。一般取变异概率为0.0001～0.1。遗传算法常采用的收敛判据有:规定遗传代数;连续几次得到的最优个体的适应值没有变化或变化很小等。
编码：
遗传算法不对优化问题的实际决策变量进行操作,所以应用遗传算法首要的问题是通过编码将决策变量表示成串结构数据。这里我们采用最常用的二进制编码方案,即用二进制数构成的符号串来表示一个个体,用下面的encoding 函数来实现编码并产生初始种群:
function [bin2gen ,bits] =encoding(min2var ,max2var ,scale2var ,popsize)
bits = ceil (log2((max2var2min2var)./scale2var) ) ;
bin2gen = randint (popsize ,sum(bits) ) ;
在上面的代码中, 首先根据各决策变量的下界(min2var)、上界(max2var)及其搜索精度scale2var来确定表示各决策变量的二进制串的长度bits,然后随机产生一个种群大小为popsize的初始种群bin2gen。编码后的实际搜索精度为scale2dec = (max2var2min2var) / (2^bits-1) ,该精度会在解码时用到。
解码
编码后的个体构成的种群bin2gen 必须经过解码,以转换成原问题空间的决策变量构成的种群var2gen ,方能计算相应的适应值。我们用下面的代码实现。
function [ var2gen ,fitness ] = decoding (funname ,bin2gen ,bits ,min2var ,max2var)
num2var = length(bits);
popsize = size (bin2gen ,1);
scale2dec = (max2var2min2var)./(2.^bits-1);
bits = cumsum(bits);
bits = [0 bits] ;
for i = 1 :num2var
bin2var{i} = bin2gen( : ,bits(i) + 1 :bits(i + 1) ) ;
var{i} = sum(ones (popsize ,1)*2.^(size(bin2var{i},2)-1:-1:0).*bin2var{i} ,2).*scale2dec (i) + min2var (i) ;
end
var2gen = [var{1 , :} ] ;
for i = 1 :popsize
fitness (i) = eval ( [funname ,’(var2gen(i , :) ) ’]) ;
end
解码函数的关键在于先由二进制数求得对应的十进制数D ,并根据下式求得实际决策变量值X:
X= D ×scale2dec + min2var
选择
选择过程是利用解码后求得的各个体适应值大小,淘汰一些较差的个体而选出一些比较优良的个体,以进行下一步的交叉和变异操作。选择算子的程序如下:
function [ evo2gen ,best2indiv ,max2fitness ] = selection ( old2gen ,fit2
ness)
popsize = length(fitness) ;
[max2fitness ,index1 ] = max (fitness) ;
[min2fitness , index2 ] =min(fitness) ;
best2indiv = old2gen(index1 , :) ;
index = [1 :popsize ] ; index(index1) = 0 ; index(index2) = 0 ;
index = nonzeros(index) ;
evo2gen = old2gen(index , :) ;
evo2fitness = fitness(index , :) ;
evo2popsize = popsize22 ;
ps = evo2fitness/ sum(evo2fitness) ;
pscum= cumsum(ps) ;
r = rand(1 ,evo2popsize) ;
selected = sum( pscum*ones (1 ,evo2popsize) < ones (evo2pop-size ,1)*r) + 1 ;
evo2gen = evo2gen(selected , :) ;
在该算子中,采用了最优保存策略和比例选择法相结合的思路,即首先找出当前群体中适应值最高和最低的个体,将最佳个体best2indiv 保留并用其替换掉最差个体。为保证当前最佳个体不被交叉、变异操作所被坏,允许其不参与交叉和变异而直接进入下一代。然后将剩下的个体evo2gen 按比例选择法进行操作。所谓比例选择法,也叫赌轮算法,是指个体被选中的概率与该个体的适应值大小成正比。将这两种方法相结合的目的是:在遗传操作中,不仅能不断提高群体的平均适应值,而且能保证最佳个体的适应值不减小。
交叉
下面采用单点交叉的方法来实现交叉算子,即按选择概率PC 在两两配对的个体编码串cpairs 中随机设置一个交叉点cpoints ,然后在该点相互交换两个配对个体的部分基因,从而形成两个新的个体。交叉算子的程序如下:
function new_gen = crossover (old_gen ,pc)
[ nouse ,mating] = sort (rand(size (old_gen ,1) ,1) ) ;
mat_gen = old_gen(mating,:) ;
pairs = size (mat_gen ,1) / 2 ;
bits = size (mat_gen ,2) ;
cpairs = rand(pairs ,1) < pc ;
cpoints = randint (pairs ,1 ,[1 ,bits]) ;
cpoints = cpairs.*cpoints ;
for i = 1 :pairs
new_gen( [2*i-1 2*i],:) = [mat_gen([2*i-1 2*i] ,1 :cpoints(i)) mat2gen([2*i 2*i-1 ] ,cpoints (i) + 1 :bits) ] ;
end
变异
对于二进制的基因串而言,变异操作就是按照变
异概率pm随机选择变异点mpoints ,在变异点处将其位
取反即可。变异算子的实现过程如下:
function new2gen = mutation (old2gen ,pm)
mpoints = find(rand(size (old2gen) ) < pm) ;
new2gen = old2gen ;
new2gen(mpoints) = 12old2gen(mpoints) ;
从上面的代码可以发现，其实遗传算法并不复杂，总共也就那么几步，因此，关键的是我们如何理解GA并应用于实际问题中。
以下是遗传算法的一些要点：
- 遗传算法研究的问题是搜索候选假设空间并确定最佳假设（简单说就是找到最优结果）
- 最佳假设被定义为使适应度最优的假设:
- 遗传算法具有以下的共同结构：
- 算法的每一次迭代以3种方式产生新一代群体
- 遗传算法执行一种随机的、并行柱状的搜索，根据适应度函数发现好的假设
- 遗传算法中的假设常常被表示成二进制位串，这便于用变异和交叉遗传算子来操作
- 把if-then规则编码成位串
- 首先使用位串描述单个属性的值约束
- 比如考虑属性Outlook，它的值可以取以下3个中的任一个：Sunny、Overcast、Rain，因此一个明显的方法是使用一个长度为3的位串，每位对应一个可能值，若某位为1，表示这个属性可以取对应的值
- 多个属性约束的合取可以很容易地表示为对应位串的连接
- 整个规则表示可以通过把描述规则前件和后件的位串连接起来
- 首先使用位串描述单个属性的值约束
- 适应度函数定义了候选假设的排序准则
- 如果学习任务是分类的规则，那么适应度函数中会有一项用来评价每个规则对训练样例集合的分类精度，也可包含其他的准则，比如规则的复杂度和一般性
- 选择假设的概率计算方法
- 适应度比例选择（或称轮盘赌选择），选择某假设的概率是通过这个假设的适应度与当前群体中其他成员的适应度的比值得到的
- 锦标赛选择，先从当前群体中随机选取两个假设，再按照事先定义的概率p选择适应度较高的假设，按照概率1-p选择适应度较低的假设
- 排序选择，当前群体中的假设按适应度排序，某假设的概率与它在排序列表中的位置成比例，而不是与适应度成比例