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

第4章基于遗传算法的随机优化搜索 基本概念 基本遗传算法 遗传算法应用举例 遗传算法的特点与优势 基本概念 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, 按每个染色体 x i∈S 的选择概率 P(x i) 所决定的选中机会, 分N 次从 S 中随机选定 N 个染色体, 并进行复制。??? Nj j iixf xfxP 1)( )()(这里的选择概率 P(x i)的计算公式为交叉就是互换两个染色体某些位上的基因。 s 1′=01000101, s 2′=10011011 可以看做是原染色体 s 1和s 2的子代染色体。 例如, 设染色体 s 1 =01001011, s 2 =10010101, 交换其后 4位基因, 即变异就是改变染色体某个(些)位上的基因。例如, 设染色体 s =11001101 将其第三位上的 0变为 1, 即 s =11 0 01101 → 11 1 01101= s′。 s′也可以看做是原染色体 s的子代染色体。 基本遗传算法遗传算法基本流程框图生成初始种群计算适应度选择-复制交叉变异生成新一代种群终止?结束算法中的一些控制参数: ■种群规模■最大换代数■交叉率(crossover rate) 就是参加交叉运算的染色体个数占全体染色体总数的比例, 记为 P c, 取值范围一般为 ~ 。■变异率(mutation rate) 是指发生变异的基因位数所占全体染色体的基因总位数的比例, 记为 P m,取值范围一般为 ~ 。