论文部分内容阅读
搜索与优化问题是一类具有非常古老的研究历史和非常广泛的应用,同时非常难于求解的问题。在机械、化工、管理、计算机、经济、生物、军事等领域中存在大量的搜索与优化问题。搜索与优化问题的研究具有重要的理论意义与现实意义。演化计算是计算机模拟大自然的演化过程,特别是生物的进化过程,来求解复杂问题的一类计算模型。演化计算具有自学习、自组织、自适应的特征和简单、通用、鲁棒性强、适于并行处理的优点。在并行搜索、联想记忆、模式识别、知识自动获取等方面得到了广泛的应用。结合几个经典的搜索与优化问题,本文对遗传算法、粒子群优化算法、模拟退火算法等演化计算方法作了较为系统的研究与讨论。提出了用演化计算方法求解搜索与优化问题的一些新思想、新算法。并利用这些新思想、新算法对一些经典搜索与优化问题求解。本文涉及的搜索与优化问题包括:多元函数优化问题、凸n边形最小四边形包围问题、TSP问题、动态TSP问题、混合整数非性函数规划(MINLP)问题、足球机器人动作选择问题。关于凸n边形最小四边形包围问题,本文提出了包围凸n边形的最小面积的四边形的一些性质,并且分别对于每条性质从理论上加以证明。利用这些特点与性质,对该问题的可行解空间进行排除与简化;利用粒子群优化算法,设计了一个求解包围凸n边形的最小四边形的算法。关于TSP问题,本文根据现实世界中的一些实际运用与要求,本文提出了动态TSP问题。对于动态TSP问题的性质进行了归纳与总结。设计了一种专门用于解决TSP问题、动态TSP问题的一种数据结构,该数据结构可以使TSP回路中的路径修改操作简化,降低了问题的计算复杂性。根据动态TSP问题的特点,将N-OPT算法(2-OPT、3-OPT算法)和遗传算法结合起来,设计并实现了一种解决动态TSP问题的方案。通过实验,对该方案的效率、解的质量等方面对做出了评价与比较。关于混合整数非性函数规划(MINLP)问题,本文改进了粒子群优化算法(PSO)。提出了“备用粒子库”的概念与模型,提出了一种新的粒子迁移策略,改进了粒子速度更新策略,不但提高了算法对于MINLP问题的求解效率,还大大增加了算法搜索的全局性,使之成为一种解决MINLP问题的新算法。通过实验,将该方案用于国内外经典的MINLP问题的求解,对该方案的效率、解的质量等方面对做出了评价与比较。实验表明,新算法精确度好、收敛快。<WP=7>关于足球机器人动作选择问题,本文提出了一个基于粒子群优化的足球机器人的动作选择算法。该算法给出了一个足球机器人的动作集合,根据赛场的情况为机器人分配角色与任务,然后利用粒子群优化算法为足球机器人选择合适的动作。实验表明,应用新算法的机器人动作灵活、效果好。