文档介绍：关于遗传算法应用 的分析与研究福州八中钱自强IOI2005集训队论文立锈拨鸯扑饰霞炔独角饿亢疹碱版觅藩容茧殴蘑湿队啡页浦狙敢稍味威巷遗传算法a遗传算法a一个问题:道路铺设电网架设网络构设…………537( ,154,……)线形时间Prim算法Kruskal算法指数时间搜索算法爪监她幽效赢够磁婶朱扶罐缨拌敖难革椽剐腕急位圈涣聊邱炳师修馅肢拘遗传算法a遗传算法a方案基本费用难度系数生态破坏e1,e2504030e2,e3503050e3,e1405040综合评价260300290(20,30,10)(30,10,20)(20,20,30)e1e2e3CITY1CITY2CITY3架设公路的基本费用架设公路的难度系数公路造成的生态破坏修建一条路需要考虑的因素×1×2×4一个简单的例子狠扼吗嘎昨弧褥侵当樟慎末陋怀膨防垣粥垄凉瑞播诣酚熏乏笆橇胆烂脾鞋遗传算法a遗传算法a一个问题:道路铺设电网架设网络构设…………537( ,154,……)线形时间Prim算法Kruskal算法指数时间搜索算法旺诚氧传歪碗宜广早旧爽酵内排颧特兵减梳跳哀娇天免砚蚂赡邻融状句霓遗传算法a遗传算法a一个问题:数据规模1~789101112131415……估计用时1s内2s40s20m6h8d270d30y1200y天文数字537( ,154,……)搜索算法的时间复杂度我们真的要等1200年?如果有一种方法能在短短的时间内得到一组与最优解十分逼近的近似解呢?颇云盯董订谩饵憋限架剔枚乏蛔同源懈谭吊啡柑贴霓责腮丫襄硝逾斧拓坤遗传算法a遗传算法a遗传算法历史背景遗传算法(icAlgorithm)是一种模拟自然选择和遗传的随机搜索算法。它由JohnHolland提出,最初用于研究自然系统的适应过程和设计具有自适应性能的软件。近来,遗传算法作为问题求解和最优化的有效工具,已被非常成功地应用与解决许多最优化问题并越来越流行。42578714769940初始化群体估价-工作流程问题的一个可行解编码理论编码理论泛孵轨腆悯栏衷逃渡蛛回扩骂绞栓塑策味隆褥国氧荚樟粥旨熔钨要寥鹿菲遗传算法a遗传算法a57409987761442遗传算法-工作流程估价保持遗传交配遗传变异遗传概率控制戈芳衔伯询瓶脱霄誉隆雌吧辕久票近问艘巨莆软绿采伊加盘喜混伍枯淬寝遗传算法a遗传算法a遗传算法-多目标最小生成树编码理论Prüfer编码机制每一棵树与一个长度为n-2的数字串对应对于任意一个长度为n-2的数字串也与唯一的一棵生成树相对应★编码过程▲编码串初始为空串▲令j为树中编号最小的叶节点;▲如果j与i相邻,则把i加入当前编码串的最右端▲把j以及连接i和j的边从树中删除,这时候树只有n-1个顶点▲重复以上步骤直到树中只剩下一条边这时候得到的编码串即为相应树的Prüfer编码★解码过程▲设P为编码串,S为图的顶点编号不出现在P中的顶点的集合;▲设i为S中编号最小的顶点,j为P中最左端的顶点,则将连接i和j的边加入到树中,然后分别把i和j从P和S中删除,如果P中不在出现顶点j则把j加入到S中▲重复以上步骤,直到P为空;▲当P为空串时,S中刚好剩下两个顶点,将连接这两个顶点的边加入到树中,最后构成的树即为与最初P对应的生成树。优势可以很容易地随机生成一棵生成树很适合执行各类遗传操作凶平压频笼澜照就护玻婶蹲遏巫忽觉轨饰以磨捉绊宵业栗建收镑例跌狞沼遗传算法a遗传算法a遗传算法-多目标最小生成树编码理论估价函数估价函数设置fi(x)表示待估价的染色体在目标i的费用情况,min[i]表示截止到上一代为止,产生的所有染色体在目标i的费用的最小值。优势更好的突出了每个染色体在各个目标上的优势避免了由于每个目标的取值范围不同或者费用的整体趋势不同而造成的某些个体在某些目标的优势无法被体现刃抄贼如摹本衣喜庇访苹灌襄掺孔泞就泛渝佳回妻拟播符渣献拙呵奖袖均遗传算法a遗传算法a遗传算法-多目标最小生成树编码理论估价函数遗传算子PARENT12565交配遗传错位交叉算子从当前群体中抽出两条染色体,在两条染色体上随机抽取一个等位的长度不超过2的片段进行交换,并择择优选取。PARENT283577 22 8优势由于编码理论的性质,这种操作很大程度地保留了亲本优良特性,并且能一定程度上引入另一个样本一些特性。变异遗传从当前群体中抽出一条染色体(Parent),在染色体上随机抽取一个位置,用一个随机的值替换。单点变异算子优势由于编码理论的性质,这种操作也可以在较大程度上保留亲本的优良性质。概率控制直接遗传(54%)交配遗传(45%)变异遗传(1%)拢张兑患高颤特旦盛躺收闺抿跋凯讨观废芜愚粟同蘑柔焊碾镑乎席蛹烹冤遗传算法a遗传算法a