交通网络优化中粘贴模型运算能力的应用研究-东篱科研大数据发现系统（DRDS）

位置：立项数据库 > 立项详情页

交通网络优化中粘贴模型运算能力的应用研究

项目名称：交通网络优化中粘贴模型运算能力的应用研究
项目类别：面上项目
批准号：61179032
申请代码：F010406
项目来源：国家自然科学基金
研究期限：2012-01-01-2015-12-31

项目负责人：周康
依托单位：武汉工业学院
批准年度：2011

中文摘要：

本项目基于粘贴DNA计算模型的计算机理，利用"算法技巧的改进、DNA计算模型的集成、数学机理、运算能力和算法优化"相结合的方法研究粘贴DNA计算模型的运算能力，并对以车辆路径安排为核心的交通网络优化问题的求解方法进行设计，用于实现粘贴DNA计算算法。利用对算法技巧从优化DNA编码结构到调整生化实验次序等的改进来优化粘贴DNA计算算法；同时，利用对粘贴DNA计算模型和Aldeman-Lipton 模型、质粒DNA计算模型进行集成的手段达到对DNA计算算法的优化，使其复杂性较其他算法得到明显地改善。本项目采用的扩展粘贴DNA计算模型运算能力的研究方法同样适用于对其他DNA计算模型的应用研究，其研究成果将为交通网络优化领域中的NP-完全问题能快速地寻找到全局最优解提供可能。

中文主题词：交通网络优化；DNA计算；粘贴模型；模拟DNA算法；智能优化算法

英文摘要：

transportation network optimization；DNA computing；sticker model；simulation DNA algorithm；intelligent optimization algorithm

英文主题词： transportation network optimization；DNA computing；sticker model；simulation DNA algorithm；intelligent optimization algorithm

结论摘要：

交通网络优化中的很多问题是NP完全问题，例如车辆路径问题（VRP）、交通网络布局问题等，如何更好地寻求这些问题的最优解是交通网络优化领域的研究热点和研究难点。本课题的研究内容是从智能优化算法、DNA计算、模拟DNA算法等3种不同角度对交通网络优化问题展开了研究。本课题的研究成果及其科学意义为（1）基于粘贴模型首次提出了模拟DNA算法(SDA)；为了充分挖掘粘贴模型的运算能力，通过对网络优化领域中典型案例的应用研究，揭示了SDA的数学理论机理和运算机制，为SDA的进一步应用奠定了理论基础。（2）在交通网络优化DNA计算的应用中，首先，通过提出可置换基变量闭环DNA编码首次基于DNA计算模型解决了交通运输网络优化问题（一个线性规划问题）；然后，基于粘贴模型，通过设计不同的DNA编码技术和不同的生化实验组合操作技术分别解决了所有生成树问题和最小生成树问题，其中所有生成树问题和最小生成树问题是交通网络的布局的基础性的优化问题。其研究意义是将DNA计算的应用首次拓展到连续型的优化问题； DNA编码不存放可能解的信息，只存放网络的信息，极大地减少了初始DNA编码的种类，解决了DNA计算的“空间爆炸”问题，是DNA计算新的计算模式。（3）在交通网络优化的智能优化算法应用中，首先，采用多种智能优化算法深入研究了VRP，这些算法是人工蜂群（ABC）算法、人工鱼群算法（AFSA）、禁忌搜索（TS）算法、萤火虫（GSO）算法以及这些算法的融合；其次，分别采用遗传算法和粒子群算法对交通网络布局问题探索了最佳计算模式。其研究意义是从计算规模、计算效率、计算精度等方面对智能优化算法进行了改进；获得了一些智能优化算法的实用的理论成果，例如随机Prem算法构造初始种群以及换树算子在操作算子中的应用；也得到了一些优秀实验结果，部分实验结果更新了数据库网站给出算例的最优解。（4）本项目还开发了《公共交通网络仿真系统平台》，该软件系统可以仿真不同规模、不同繁华程度的交通网络数据，为科研工作者提供了不同类型和不同规模的测试数据。

成果综合统计