– 交换任意排列的随机两个位置 – 反转排列的一段 – 移动排列的一段
遗传算法
遗传算法
• 种群(Population)：生物的进化以群体的形 式进行，这样的一个群体称为种群 • 个体：组成种群的单个生物 • 基因(Gene)：一个遗传因子 • 染色体(Chromosome)：包含一组的基因
遗传算法
解决0/1背包问题
• 如何解决产生不合法的基因的问题
– 对不合法的解直接剔除
• 如何解决产生不够充分利用空间的问题
– 使用惩罚函数
• 一个很方便的办法
– 贪心修改/随机修改基因
元启发式搜索算法
算法的定义
• 一个基于直观或经验构造的算法，在可接 受的花费（指计算时间和空间）下给出待 解决组合优化问题每一个实例的一个可行 解，该可行解与最优解的偏离程度不一定 事先可以预计 • 元启发式算法：启发式算法的改进，随机 方法与局部搜索算法相结合
算法的特性
• • • • • 应用范围广 很少的花费(计算时间 占用空间) 算法最后得到一个可行解 期待一个较优解 甚至是最优解 易于维护 易于调整 易于理解
• 生存竞争，适者生存：对环境适应度高的、 牛X的个体参与繁殖的机会比较多，后代就 会越来越多；适应度低的个体参与繁殖的 机会比较少，后代就会越来越少 • 遗传与变异：新个体会遗传父母双方各一 部分的基因，同时有一定的概率发生基因 变异
算法流程
• 随机产生一个种群 • While (繁殖代数不够) {
Infrnd2
• 65 12 13 25 36 56
• 样例给奶牛的编号 1 2 3 5 6 4 • 8
模拟退火算法
• 模拟退火算法是爬山法的改进
– 如果新解比现行解优 直接转移 – 如果新解不比现行解优 按照一定的概率转移
• 这样会让算法更不容易陷入局部最优 • 同样可以并行计算多个解
算法基本流程
算法的难点
• 根据问题选择相应的算法
– 模拟退火 – 遗传算法 – 其他适用算法
• 需要实验和调整
– 核心的估价函数 – 由现行解生成新解的方式 – 其他算法相关的参数
模拟退火算法
爬山法
• • • • 从一个解开始不断选取最优的解转移 本质是一个贪心算法 容易看出会陷入局部最优 多次选取随机的初始解不断迭代转移
• 变异：
– 随机修改某个位置 – 按照一定的概率强制修改某个位置
选择代码
• R <- Random() • i <- 0 • While S < R Do
– i <- i + 1 – S <- S + H(i)/Sum{H(i)}
• End While • Return i
解决0/1ห้องสมุดไป่ตู้包问题
• • • • 背包问题是NPC问题 编码：0/1编码 交叉：XOR运算 变异：NOT运算
• While (温度T大于零) {
– 根据当前解生成新解 – 根据估价函数估价新解 – 如果估价变优
• 直接转移到新解 • 否则 按照exp(估价差 估价差dH/k*温度 温度T)的概率转移 估价差 温度
– 退火 T乘以退火系数r (0<r<1)
• }
解决TSP问题
• 编码：用一个排列代替一个解 • 估价：直接用花费当估价即可 • 转移：
– 每次选择 选择两个解生交叉 交叉生成新解 选择 交叉 – 对新解执行变异 变异
• } • 从历史上所有个体中选取最好的
几个操作
• 选择：采取类似轮盘赌比例选择方法
– 优秀的个体被选择的概率就大 反之则小 – P(A)=H(A)/Sum{H(A)}
• 交叉：
– 交换两个个体的某段基因 – 或者利用位运算交叉对应的基因
爬山法
• 经典问题
– TSP
• 两个实际可以解决的问题
– Infrnd2 – Park
Infrnd2
• 现在有N头奶牛，每个奶牛有一个编号，编 号都是在1到N之间的而且是唯一的。你知 道某些奶牛之间的朋友关系，而每一对朋 友之间的distance就是他们编号的差，现在 你需要最小化所有的朋友关系distance的总 和，当然也就是给奶牛们编号。