多目标进化算法及其在制造系统中的应用研究

《多目标进化算法及其在制造系统中的应用研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、上海交通大学博士学位论文多目标进化算法及其在制造系统中的应用研究摘要很多现实问题常要求同时优化多个相互竞争或冲突的目标。用进化算法求解多目标优化问题具有传统多目标优化方法(如加权法)不可比拟的优势：一方面，进化算法不需要决策者的偏好信息即可同时优化多个目标；另一方面，其并行机制使算法运行一次就能得到问题的Pareto最优集或近似最优集。有关多目标进化算法的研究不仅具有理论价值而且具有实际意义，本文针对多目标进化算法及其在制造系统中的应用展开研究，主要内容和成果如下：提出了混合微调多目标Memetie算法(HybridFine．TunedMulti．objectiveMemeticAlgor

2、ithm，HFMOMA)，该方法将局部搜索与进化重组(交叉和变异)相结合以改善算法的全局搜索能力。为了扩展搜索空间，HFMOMA在局部搜索阶段采用模拟退火(SA)算法优化每个随机线性加权函数；在重组阶段，算法采用Pareto法实现交叉和变异，并通过一种基于网格的局部扰动(Grid．basedLocalPerturbation，GBLP)增强算法的探索能力。而且，为了改善算法的鲁棒性，HFMOMA的优化进程可根据在线反馈的改善率进行动态自适应调整。通过求解多目标0／1背包问题实例，与其它几种多目标进化算法的比较说明，HFMOMA能够找到更接近Pareto最优前端且多样性更好的近似集。设计了一

3、种基于模拟退火的多目标Memetic算法(SimulatedAnnealingBasedMulti-objectiveMemeticAlgorithm，SAMOMA)，‘并应用于流水车间调度问题。SAMOMA的创新之处在于将SA实现的局部搜索与进化算子以及一种基于网格密度的选择机制相结合以增强算法的全局搜索能力，而且整个优化过程采用Pareto占优关系评价解的适应值并计算SA中的接收概率。仿真计算的结果比较说明，SAMOMA在求解多目标流水车间调度问题时较其它几种基于SA的多目标进化算法具有更快的收敛速度，并能产生分布更均匀的近似集。其次，本文探讨了基于动态周期加权函数的多目标进化算法以及

4、蚁群算法在多目标流水车间调度问题中的应用。提出用一种多目标Memetic算法(Multi—objectiveMemeticalgorithm，摘要MOMA)求解准时制生产方式下混流装配线的多目标调度问题。MOMA的特点一是设计了基于贪婪算法的局部搜索，并在局部和重组阶段均采用基于网格密度的选择机制改善算法的开发(Exploitation)与探索(Exploration)能力。实例仿真说明，MOMA较枚举法搜索速度更快；与一种求解相同问题算例效果较好的多目标遗传算法相比，MOMA的搜索效率更高，特别在求解大规模问题时表现出明显的优势。针对半导体制造企业内部的供应链管理，研究了半导体制造中Bi

5、n分配计划和多工厂产能规划的多目标优化。提出了Bin分配计划的转运问题模型，该模型的优点是较传统建模方法减少了变量，从而可提高求解速度。对于Bin分配决策问题的多目标优化，本文开发了一种基于字典排序法的启发式方法，与线性规划求解问题实例的仿真结果比较说明，该启发式方法能够求解得到满意解，并不需要确定权重系数。对于多目标多工厂产能分配计划问题，本文建立了两阶段求解模型，并提出了用基于SA的多目标进化算法进行求解。实验表明用进化算法求解半导体制造中的多目标产能分配问题是可行的。最后总结了全文并展望了未来的研究方向。本文研究工作受到国家自然科学基金(No．60174009)和英特尔／大学研究基金

6、的资助。关键词：多目标进化算法，Memetic算法，模拟退火，网格密度，流水车间调度，混流装配线，半导体制造，Bin分配计划，多工厂产能分配Ⅱ上海交通大学博士学位论文ABSTRACTManyreal-worldproblemsoftenrequiresimultaneouslyoptimizemultiplecompetitiveorconflictingobjectives．Evolutionaryalgodthrnshaveincomparableadvantagesovertraditionalmethods，e．g．theweighted-sumapproach,insolving

7、multi—objectiveproblems．Ononehand，theevolutionaryalgorithmsCanoptimizesimultaneouslymultiplecriteriawithouttheconsiderationofthedecisionmaker’Spreferenceinformation．Ontheotherhand，theparallelmechanismmakestheevol