浅论一种基于免疫思想的单亲遗传算法及其应用研究

《浅论一种基于免疫思想的单亲遗传算法及其应用研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、长沙交通学院硕士学位论文一种基于免疫思想的单亲遗传算法及其应用研究姓名：袁松贵申请学位级别：硕士专业：计算机应用技术指导教师：傅明20030501摘要单亲遗传算法采用序号编码．取消了交叉算子，代之阻隐含交叉算子功能的基因换位等遗传算子，简化了遗传操作，并且不要求初始群体具有多样性．但当群体进化到一定代数时，个体浓度过高，无法很好地保持个体多样性，不能有效地避免劣质个体重复繁衍，因此仍存在“准早熟收敛”和容易陷入局部最优的缺点。单亲遗传算法的上述不足，本文从生物免疫系统中获得一些启示，利用免疫系统的特征。将它和单亲遗传算法相结合，提出一种基于免疫思想的改进的单亲遗传算法，本文

2、称之为IPGA(Immune—ParthenoGenetiCA190rithm)，该算法将单亲遗传算法同生物免疫系统中的记忆机制、浓度机制及多样性保持策略相结合，既保留了单亲遗传算法随机全局并行搜索的特点．又在很大程度上避免“准早熟收敛”。本文主要做了以下几个方面的工作：1．研究了免疫算法的生物学基础，分析了免疫算法的进化机理；2．深化了单亲遗传算法的基本概念，改进了适合于PGA的几种遗传算子，并给出了PGA的两种典型运行步骤；3．将免疫思想引入单亲遗传算法，提出了一种新的生物优化算法一一免疫单亲遗传算法(IPGA)；4．研究了抗体群体规模、抗体浓度阈值以及记忆库规模等参数

3、对IPGA的影响，并讨论了IPGA的收敛性；5．研究了IPGA在组合优化问题中的应用，提出了利用基于浓度的群体更新机制来改善群体的多样性：6．开发了运用IPGA求解CTSP问题的仿真软件，并验证了IPGA的可行性和有效性。仿真结果表明，将免疫思想引入单亲遗传算法是合理的、有效的，在求解中国TSP问题时。搜索到了比以前报告更优的解，且收敛速度有所提高．．并在一定程度上避免了“准早熟收敛”现象的发生。这说明基于免疫思想的单亲遗传算法(IPGA)是求解组合优化问题的有力工具．可以应用于生产调度、资源规划、列车调度、网络通信中的路由问题等生产过程组合优化问题，具有一定的现实和经济意

4、义。关键词：免疫系统免疫算法单亲遗传算法组合优化中国旅行商问题ABSTRACTPartheno—geneticA190rithm(PGA)usestheordinalstringsandrepealsthectosSOVeroperatorsofTGA，whileintroducessomeparticulargeneticoperatorssuchasthegeneexchangeoperators．Theseparticulargeneticoperatorshayethesamefunctionasthecrossoveroperators．Thegeneticope

5、rationofPGAismoresimpleanditsinitialpopulationneednotbevaried．ButwhenthepopuIatiorlevolvestocertaingeneration。theCOncentrationofindividualissohighthattheindividualdiversitycan’tbemaintainedverYwellandthei11feriorindividualreproducesrepeat．So．PGAcan’tpreventhalf-prematureconvergenceandiseas

6、ycometo10calconvergence．InordertoovercomethedisadvantagesofPGA。thispapergetsc1uefrombiologyimmunesystem，andpresentsanewPGAbasedonimmunetheorywhichcalledIPGA(Immune～ParthenoGeneticA1norithm)。Themainfunctionssuch8sthememoryandrecognitionofaDtigenandtheadjustmentofantibodyareinvolredinthisalg

7、orithm．IPGAnotonlYreservesthetraitsofgIobaljuxtaposesearchofPGA．butalsopreventshalf—prematureconvergenceandenbancesthecapabilityandefficiencyof910balsearch．Themainresearchworkinthispapercanbesummarizedasfollows：(1)Reseatchthebiologyfoundationandanalysetheev01u