最佳个体保存方法
- 格式:docx
- 大小:19.62 KB
- 文档页数:3
最佳个体保存方法
最佳个体保留进化策略的基本思想是当前群体中适应度最高的个体不参与交叉运算和变异运算,而是用来替换掉本代群体中经过交叉、变异等遗传操作后所产生的适应度最低的个体。
具体操作过程:
1.找出当前群体中适应度高的个体和适应度最低的个体
2.若当前群体中最佳个体的适应度比总的迄今为止的最好个体的适应度还要高,则以当前
群体中的最佳个体作为新的迄今为止的最好个体
3.用迄今为止的最好个体替换掉当前群体中的最差个体
排序选择方法
排序选择方法的主要着眼点是个体适应度之间的大小关系,对个体适应度是否取正值或负值以及个体适应度之间的数值差异程度并无特别要求。
排序选择机制的主要思想是:对群体中的所有个体按其适应度大小进行排序,基于这个排序来分配各个体被选中的概率。
具体操作过程:
1.对群体中的所有个体按其适应度大小进行降序排序
2.根据具体求解问题,设计一个概率分配表,将各个概率值按上述排列次序分配给各个个
体
3.以各个个体所分配到的概率值作为其能够被遗传到下一代的概率,基于这些概率值用比
例选择的方法来产生下一代群体。
是指在计算每个个体的适应度后,根据适应度大小顺序对群体中个体排序,然后把事先设计好的概率表按需分配给个体,作为各自的选择概率
图1 赌轮选择流程图
程序中用一个Begin来代表当前赌轮上的指针位置,End则用来使赌轮循环转动
用summaryBE函数表示当前赌轮上的指针转过的染色体的总价值
用summaryF表示当前染色体的价值总和
用randProblem作为染色体选择的阈值。
randProb为介于[0,1]之间的随机数,选择使summaryBE/summaryF大于阈值randProd的染色体作为要选择的染色体
选择算子分为两类:一类是基于适应度的概率分配,有轮盘赌法,随机遍历抽样法等,另一类是基于排序分类,有锦标赛选择法,竞争选择,稳态复制,局部选择法,截断选择法等。
其中赌轮选择算子是最早提出的一种选择方法,比较简单,也是最常用的一种选择算子。
小生境遗传算法:将每一代个体划分为若干类,每个类中选出若干适应度较大的个体作为一个类的优秀代表组成一个种群,再在种群中以及不同种群之间通过杂交、变异产生新一代种群,同时使用某种规则完成选择操作。
规则主要有:
基于排挤机制-------算法中设置一个排挤因子,根据新生个体与排挤成员的相似性来排挤一些与排挤成员相类似的个体。
基于预选择机制-----新生子代的个体适应度超过其父代个体时,子代个体才能代替其父代个体而遗传到下一代,否则保留父代到下一代
基于共享机制等等-----通过个体之间的相似程度的共享函数来调整群体中各个个体的适应度
竞争选择法:采用适应度比例法进行选择,交叉后产生下一代,再利用最佳个体保留法将上一代的最佳个体直接保存下来,然后从新群体中淘汰一个适应度最差的个体,提高了问题求解的收敛速度,体现了遗传算法自适应环境的能力
从父代群体中任意选择一定数目的染色体,把其中适应度最高的染色体选择出来
a method of selecting an individual from a population of individuals in a genetic algorithm. Tournament selection involves running several "tournaments" among a few individuals chosen at random from the population. The winner of each tournament (the one with the best fitness) is selected for crossover. Selection pressure is easily adjusted by changing the tournament size. If the tournament size is larger, weak individuals have a smaller chance to be selected.
Tournament selection pseudo code:
choose k (the tournament size) individuals from the population at random
choose the best individual from pool/tournament with probability p
choose the second best individual with probability p*(1-p)
choose the third best individual with probability p*((1-p)^2)
and so on...
Deterministic tournament selection selects the best individual (when p=1) in any tournament. A 1-way tournament (k=1) selection is equivalent to random selection. The chosen individual can be removed from the population that the selection is made from if desired,
otherwise individuals can be selected more than once for the next generation.
Tournament selection has several benefits: it is efficient to code, works on parallel architectures and allows the selection pressure to be easily adjusted.
1、轮盘赌选择(Roulette Wheel Selection):是一种回放式随机采样方法。
每个个体进入下一代的概率等于它的适应度值与整个种群中个体适应度值和的比例。
选择误差较大。
2、随机竞争选择(Stochastic Tournament):每次按轮盘赌选择一对个体,然后让这两个个体进行竞争,适应度高的被选中,如此反复,直到选满为止。
3、最佳保留选择:首先按轮盘赌选择方法执行遗传算法的选择操作,然后将当前群体中适应度最高的个体结构完整地复制到下一代群体中。