经典算法之遗传算法.ppt

遗传算法的改进 共享（sharing,1987）机制 共享函数的值越大，表明个体之间越相似，记为Sh(dij)，dij为两个个体i和j之间的距离； σshare是niche的半径，由使用者给定。 基于小生境技术的遗传算法 遗传算法的改进 共享（sharing,1987）机制 共享法将个体的适应度降低，即适应度值fi除以一个niche计数mi： 在距离为σshare的范围内的个体彼此削减适应度，这些个体将收敛在一个niche内，避免了整个种群的收敛。 基于小生境技术的遗传算法 谢谢！ * 基本遗传算法 常用选择方法 局部选择法（local selection） (1)线形邻集 遗传操作——选择 在局部选择法中，每个个体处于一个约束环境中，称为局部邻域(而其他选择方法中视整个种群为个体之邻域)，个体仅与其邻近个体产生交互，该邻域的定义由种群的分布结构给出。邻域可被当作潜在的交配伙伴。 首先均匀随机地选择一半交配种群，选择方法可以是随机遍历方法也可以是截断选择方法，然后对每个被选个体定义其局部邻域，在邻域内部选择交配伙伴。 基本遗传算法 常用选择方法 局部选择法（local selection） (2)两对角邻集 遗传操作——选择 基本遗传算法 常用选择方法 局部选择法（local selection） (2)两对角邻集 遗传操作——选择 基本遗传算法 常用选择方法 截断选择法（truncation selection） 个体按适应度排列，只有优秀个体能够成为父个体，参数为截断阀值（被选作父个体的百分比）。 遗传操作——选择 截断阀值 1％ 10％ 20％ 40％ 50％ 80％ 选择强度 2.66 1.76 1.2 0.97 0.8 0.34 基本遗传算法 常用选择方法 锦标赛选择法（tournament selection） 随机从种群中挑选一定数目个体，其中最好的个体作为父个体，此过程重复进行完成个体的选择。 遗传操作——选择 竞赛规模 1 2 3 5 10 30 选择强度 0 0.56 0.85 1.15 1.53 2.04 基本遗传算法 实值重组 离散重组 子个体的每个变量可以按等概率随机地挑选父个体。 5 遗传操作——交叉/基因重组 父个体1 12 25 5 父个体2 123 4 34 子个体1 123 4 5 子个体2 12 4 34 基本遗传算法 实值重组 中间重组 子个体＝父个体1＋α×（父个体2－父个体1） α是比例因子，由[-d,1+d]上均匀分布地随机数产生。 一般取d=0.25。 子代的每个变量均产生一个α 。 遗传操作——交叉/基因重组 基本遗传算法 实值重组 中间重组示例 遗传操作——交叉/基因重组 父个体1 12 25 5 父个体2 123 4 34 子个体1 子个体2 α值样本1 0.5 1.1 -0.1 α值样本2 0.1 0.8 0.5 12＋0.5×（123－12）=67.5 67.5 25＋1.1×（4－25）=1.9 1.9 2.1 12＋0.1×（123－12）=23.1 23.1 8.2 19.5 基本遗传算法 实值重组 中间重组 遗传操作——交叉/基因重组 基本遗传算法 实值重组 线性重组 遗传操作——交叉/基因重组 父个体1 12 25 5 父个体2 123 4 34 子个体1 子个体2 α值样本1 0.5 α值样本2 0.1 12＋0.5×（123－12）=67.5 67.5 25＋0.5×（4－25）=14.5 14.5 19.5 12＋0.1×（123－12）=23.1 23.1 22.9 7.9 基本遗传算法 实值重组 线性重组 遗传操作——交叉/基因重组 基本遗传算法 二进制交叉 单点交叉 遗传操作——交叉/基因重组 基本遗传算法 二进制交叉 多点交叉 遗传操作——交叉/基因重组 基本遗传算法 实值变异 一般采用： 二进制变异 6 遗传操作——变异 4.2 基本遗传算法 运行程序 4.2.7 算法的设计与实现