研究算法
研究一个问题的算法(例:遗传算法)
| 生物类问题求解思维如下! |
|---|
| 遗传算法(求解NPC问题) |
| 蚁群算法 |
| 蜂群算法 |
可求解问题与难求解问题与不可计算问题
| P类问题 | 多项式问题,计算机在有限时间可求解问题 |
|---|---|
| NP类问题 | 非确定性多项式问题=难求解问题,只可以判断一个解是否正确 |
| NPC问题 | 完全非确定多项式问题=NP问题的所有可能答案都能在一定时间内进行验证对错的问题 |
- NPC=NP-complete
- 计算复杂性=问题本身复杂性
- 算法复杂性=代码运行复杂性
| NPC问题求解 |
|---|
| 精确解 >> 穷举法 |
| 近似解 >> 例:贪心法 |
遗传算法的缘起
| 生物进化基本观点 ( 优胜劣汰 + 遗传与进化 ) |
|---|
| 1:遗传信息都包含在染色体中,染色体决定生物性状 |
| 2:染色体由基因的规律排列组成,遗传与进化过程发生在染色体上 |
| 3:生物的繁殖过程由基因的复制过程完成 |
| 4. 通过同源染色体之间的交叉或染色体的变异会产生新的物种,使生物呈现新的性状 |
| 5. 对环境适应性好的基因或染色体经常比适应性差的基因或染色体有更好的机会遗传给下一代. |
| 生物学基本概念 |
|---|
| 种群 |
| 个体 |
| 染色体 |
| 基因 |
| 适应度 |
| 选择 |
| 复制=基因传递 |
| 交配=染色体杂交 |
| 染色体突变 |
计算学科的遗传算法
| Min F(X)=X2-19X+20 ,其中X=1,…,64之间的整数 |
|---|
| 生物学概念 | 计算学科概念 |
|---|---|
| 种群 | 解>>>>>>>>>>>>>>>>>若干可能解的集合 |
| 个体 | 表现解>>一个可能解的表现型,例:十进制的X |
| 染色体 | 编码解>>一个可能解的基因型,例:二进制的X |
| 基因 | 基因>>>>>>>>二进制编解码的某一位0/1数 |
| 适应度 | 适应度>>>>>>>>>一个解接近最优解的量度 |
| 选择 | 选择>>>>>>>根据适应度选择出来的部分解 |
| 复制 | 复制>>>>将一个解从解集复制到另一个解集 |
| 交配 | 交叉>>两个可能解的编码通过交换某些编码位形成新的可能解的遗传操作 |
| 突变 | 变异>>随机改变一个可能解的编码的某些片段,产生一个新的可能解的遗传操作 |
| 遗传算法求解过程的模拟 |
|---|
遗传算法为什么能解NPC问题
| 基于概率论的随机搜索如下! |
|---|
| 导向型随机搜索>>>>随机选择的可能解与前一可能解相比,更偏向于满意解(缺点:如果初始解很差,则效率很低) |
| 导向性群体搜索>>>>多条路径下的最优 |
| 遗传算法的适用条件 | 已知解的表现型与基因型(知道解的10进制范围与2进制描述) + 告知适应度的计算方法(能判断可能解与精确解的适应度关系) |
|---|
遗传算法解决具体应用问题实例
| 一维的集覆盖问题(问题的解是由一维的X1~X6组成) + 目标问题函数 |
|---|
| 二维集覆盖问题(问题的解由二维的X1~X6与T1-T6组成) |
| "会议室"租用问题 | 使T1…T6讲座全部被安排的最低消费组合方式 |
|---|---|
| "航班机组成员"选择问题 | 使T1…T6航班全部被安排的最低费用方式 |
算法设计要点与解的编码
| 基础 |
|---|
| 可能解的形式>>解的表现型与基因型 |
| 怎样产生待判定的可能解>>(交叉 + 变异 + 随机) |
| 产生多少个待判定的可能解>>(解集的规模(根据问题而定) + 进化的代数 + 随机) |
| 怎样判断一个解是否为所求解>>(适应度 + 选择标准 + 满意解) |
| 遗传算法设计要点 |
|---|
| 1:实际问题分析>>>解的形式 + 解的约束范围 + 解的空间 |
| 2:问题解的编码规则与解码规则 |
| 3:初始种群的规模大小(初始解集规模大小)与生成规则设计 |
| 4:遗传规则的设计>>>交叉 + 变异 |
| 5:繁衍种群的策略设计>>保留多少个可行解 |
| 6:种群个体适应度函数设计 |
| 7:优质个体选择方法设计 |
| 8:终止条件与最终解>>进化到什么程度结束 |
| 以二维集覆盖问题的解的编码为例 |
|---|
| 可行解 |
| 行优先编码 |
| 列优先编码 |
策略选择的多样性=如何产生可能解(以交叉为例)
| 交叉(交叉起始点随机) |
|---|
| 2个解交叉一个二进制位 |
| 2个解交叉一段二进制位 |
| 2个解交叉多段二进制位=多段交叉的间隔相等 + 多端交叉的间隔距离不等 |
策略选择的随机性(交叉起点的随机性)
| 随机(根据概率模型来确定如何进行随机) |
|---|
| 个体的配对>>随机 |
| 两个染色体交叉点位置的选择>>随机 |
| 多段交叉中交叉点之间的距离>>随机 |
| 交叉后产生的解选择哪些>>随机 |