基于遗传算法的随机优化搜索.ppt

基于遗传算法的随机优化搜索
基本概念
基本遗传算法
遗传算法应用举例
遗传算法的特点与优势
基本概念
1. 个体与种群
●个体就是模拟生物个体而对问题中的对象
(一般就是问题的解)的一种称呼,一个个
体也就是搜索空间中的一个点。
●种群(population)就是模拟生物种群而由若
干个体组成的群体, 它一般是整个搜索空间
的一个很小的子集。
2. 适应度与适应度函数
●适应度(fitness)就是借鉴生物个体对环境的
适应程度,而对问题中的个体对象所设计的
表征其优劣的一种测度。
●适应度函数(fitness function)就是问题中的
全体个体与其适应度之间的一个对应关系。
它一般是一个实值函数。该函数就是遗传算
法中指导搜索的评价函数。
3. 染色体与基因
染色体(chromosome)就是问题中个体的某种字符串形式的编码表示。字符串中的字符也就称为基因(gene)。
例如:
个体染色体
9 ---- 1001
(2,5,6)---- 010 101 110
4. 遗传操作
亦称遗传算子(ic operator),就是关于染色体的运算。遗传算法中有三种遗传操作:
●选择-复制(selection-reproduction)
●交叉(crossover,亦称交换、交配或杂交)
●变异(mutation,亦称突变)
选择-复制通常做法是:对于一个规模为N的种群S,按每个染色体xi∈S的选择概率P(xi)所决定的选中机会, 分N次从S中随机选定N个染色体, 并进行复制。
这里的选择概率P(xi)的计算公式为
交叉就是互换两个染色体某些位上的基因。
s1′=01000101, s2′=10011011
可以看做是原染色体s1和s2的子代染色体。
例如, 设染色体 s1=01001011, s2=10010101, 交换其后4位基因, 即
变异就是改变染色体某个(些)位上的基因。
例如, 设染色体 s=11001101
将其第三位上的0变为1, 即
s=11001101 →11101101= s′。
s′也可以看做是原染色体s的子代染色体。
基本遗传算法
遗传算法基本流程框图
生成初始种群
计算适应度
选择-复制
交叉
变异
生成新一代种群
终止?
结束
算法中的一些控制参数:
■种群规模
■最大换代数
■交叉率(crossover rate)就是参加交叉运算的染色体个数占全体染色体总数的比例,记为Pc,~。
■变异率(mutation rate)是指发生变异的基因位数所占全体染色体的基因总位数的比例,记为Pm,~。