1 / 15
文档名称:

遗传算法a.ppt

格式:ppt   大小:507KB   页数:15页
下载后只包含 1 个 PPT 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

遗传算法a.ppt

上传人:drp539601 2019/1/26 文件大小:507 KB

下载得到文件列表

遗传算法a.ppt

相关文档

文档介绍

文档介绍:关于遗传算法应用 的分析与研究福州八中钱自强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

最近更新

从高硫多金属金精矿中提取金银铜试验研究 2页

从解析几何的产生谈教改的一点想法 2页

从米糠油下脚中提取植物甾醇的方法 2页

从生产型转向经营服务型管理初探 2页

深圳市标准房屋租赁合同 7页

从控制论看磁悬浮技术与有源控制的同步发展 2页

深圳出租房租赁合同 6页

深入解析合同相对性:法治百科普法词条——合.. 6页

润滑油购销合同 6页

介绍目前我国染料中间体产品标准中所采用的分.. 2页

介绍两种使用旧废料制造钎杆的方法 2页

介绍一种新刊物——《铀与金经济技术简讯》 2页

介电法在监测玻璃钢固化程度中的应用 2页

人血清载脂蛋白CII酶联免疫测定法的研究 2页

人白细胞γ-干扰素诱生条件的探讨 2页

人才类型理论及其在管理科学中的应用 2页

海上物流服务合同规范 7页

人体跖骨疲劳强度实验研究与骨折断口分析 2页

亭下水库伪鱼腥藻昼夜垂直变化初步研究 2页

产L-白氨酸突变株的选育及发酵条件的研究 2页

法律顾问合作合同书范本 6页

交互效应面板数据模型的理论与应用研究 2页

油工劳务分包合同五份样本 7页

井式电阻炉炉口溢气损失的理论计算方法探讨 2页

井下作业小修填砂施工技术的研究与应用探究 2页

五十铃N系列轻型载货汽车充电指示电路故障浅析.. 2页

云锡井下氡析出的特征和控制方法 2页

云南鹤庆新华村生态环境设计研究 2页

云南省七个少数民族的肤纹参数及聚类分析 2页

云南农村低压电网电压质量分析与改进措施 2页