返回
类型 基础研究 预答辩日期 2018-03-15
开始(开题)日期 2016-06-17 论文结束日期 2018-01-18
地点 东南大学九龙湖校区计算机楼213 论文选题来源 国家自然科学基金项目     论文字数 10 (万字)
题目 复杂组合优化问题的智能搜索方法
主题词 最短路,学习效应,双目标,混合等待流水调度,迭代贪心
摘要 组合优化问题广泛存在于交通运输、网络规划、物流配送、云计算、大数据、生产制造等诸多领域。求解多约束、多目标、复杂组合优化问题的智能搜索方法是提高企业效率、优化资源成本、改善用户体验、节省消耗能源等诸多方面的核心技术。本文考虑了求解组合优化问题的两种搜索方法:简单构造式搜索和迭代构造式搜索。结合不同问题场景,依据具体问题特性,对不同的搜索方法进行了相关研究。论文的主要工作体现在: (1) 针对基于位置学习效应的最短路径不满足最优子结构、无法直接使用传统 A* 系列算法求解的问题,提出了基于学习效应最短路径的启发式精确性搜索 AA* 算法,保留潜在最优解的子路径,形成搜索图;证明了算法的可采纳性;结合问题具体特性,重新定义了启发函数的单调性和一致性;比较了所提 AA* 算法中启发函数与A* 算法中启发函数单调性/一致性之间的关系;分析并证明了在满足单调性和一致性的前提下启发函数大小对搜索效率影响的相关性质;通过仿真实验验证了所提算法的有效性。 (2) 针对求出双目标最短路径问题所有非支配解花费时间长(尤其是大规模问题)、非支配解数量随着问题规模增加急剧增加的问题,提出了一种增量式、用户驱动的迭代构造启发式搜索算法 UDBA*,通过充分利用之前的搜索信息避免重复搜索,在很短时间内快速得到勾画 pareto 前沿面的部分分布均匀的非支配解,以满足用户决策需求;证明了所提算法的可采纳性;分析了启发函数的单调性和一致性对搜索效率的影响;通过仿真实验验证了所提算法的有效性。 (3) 针对更加一般化的、等待和无等待约束同时存在的混合等待流水调度问题,建立了数学模型;设计了一种最大完工时间的快速计算方法;提出了一种改进迭代贪心算法,通过抽取工件数量动态自适应变化策略以及结合模拟退火思想提高搜索多样性,构造可变邻域搜索增加搜索力度;通过在修正的Taillard benchmark标准测试例上的实验验证了所提算法的有效性。
英文题目 Intelligent search methods for complicated combinatorial optimization problems
英文主题词 Shortest path problem, learning effects, biobjecitve optimization, hybrid wait flowshop scheduling, iteration greedy
英文摘要 Complicated combinatorial optimization problems widely exist in communication and transportation, network planning, logistics distribution, cloud computing, big data, manufacturing and so on. Intelligent search methods for complicated combinatorial optimization problems with multi-constraint and multi-objective are the key of improving enterprise’s efficiency, optimization of resource cost, improving user experience, energy saving. Two search methods for combinatorial optimization problems are considered: simple construction search and iterated construction search. According to different applications, properties are analyzed, and different search methods are studied. The main work of this paper is as follows: (1) The shortest path problem with position-based learning effects is considered. Because the suboptimal structure is not satisfied for this problem, traditional series of A* algorithm can not be used. A heuristic accurate search method is proposed for the problem. In the process of search, potential optimal subpaths are saved and the search graph is finally constructed. The admissibility is analyzed and proved. Monotonicity and consistency of the heuristic functions of AA* are redefined and the corresponding properties are analyzed. Consistency/monotonicity relationships between the heuristic functions of AA* and those of A* are explored. Their impacts on efficiency of searching procedures are theoretically analyzed and experimentally evaluated. (2) The bi-objective shortest path problem is considered. It maybe cost very long time, especially for large size problems. At the same time, the number of nondominated solutions increases quickly. An incremental user-driven biobjective A* algorithm is proposed for user-driven biobjective shortest path problems. It makes use of the previous results to avoid repeated search. Some uniformly distributed nondominated solution paths which can image the Pareto front in general can be got in a short time to satisfy user’s decision requirement. The admissibility of the proposed algorithm is analyzed and proved. The influence of consistency/monotonicity on the search efficiency is explored. Experimental results show that the proposed algorithm is effective and efficient. (3) Themixedno-waitflowshopproblemwithbothwaitandno-waitconstraintsarewidespread in real-life applications. The problem can be regarded as a generalization of the traditional permutation flowshop and the no-wait flowshop. This scheduling setting with makespan minimization is studied for the first time. A mathematical model is proposed firstly and then a speed-up makespan calculation procedure is designed. By introducing avarying number of destructed jobs, a modified iterated greedy algorithm is proposed for the considered problem. To further improve the intensification and efficiency of the proposal, insertion is performed on some neighbor jobs of the best position in a sequence during the initialization, solution construction and reconstruction phases. For improving the diversification of search, the number of jobs in destruction phase is self-adaptive changed, and the idea of simulated algorithm is adopted. New neighborhood structures are used in VND (Variable Neighborhood Decent) to improve the intensification of search. After calibrating parameters and components, the proposal is compared with five existing algorithms for similar problems on adapted Taillard benchmark instances. Experimental results show that the proposal always obtains the best performance among the compared methods.
学术讨论
主办单位时间地点报告人报告主题
东南大学计算机科学与工程学院 2017.5.10 东南大学 王亚敏 Iterated Greedy algorithm for mixed no-wait flowshop problem
东南大学计算机科学与工程学院 2015.10.29 东南大学 陈龙 Resource Renting for Instance-Intensive Workflow Applications in Cloud
东南大学计算机科学与工程学院 2015.7.14 东南大学 胡苇 Coupling Scheduler for MapReduce
东南大学计算机科学与工程学院 2017.7.7 东南大学 王佳 Energy-aware Task Scheduling of MapReduce Cluster with dynamic slots
东南大学计算机科学与工程学院 2016.5.18 东南大学 王亚敏 Review of A* algorithm
东南大学计算机科学与工程学院 2016.10.20 东南大学 王亚敏 Optimization of makespan for no-wait flowshop scheduling problem using efficient matheuristics
东南大学计算机科学与工程学院 2017.3.15 东南大学 王亚敏 Decomposition A Star algorithm for Bi-objective Shortest Path Problem
东南大学计算机科学与工程学院 2016.6.15 东南大学 陈龙 Review of DOCKER
     
学术会议
会议名称时间地点本人报告本人报告题目
2013 IEEE International Conference on Systems, Man, and Cybernetics 2013.10 英国曼彻斯特 Shuffled Frog Leaping Algorithm for a Bi-objective No-idle Permutation Flow Shop
智慧城市学术交流会 2014.9 江苏扬州大学 基于位置学习效应最短路径的启发式算法
复杂调度与智能优化研讨会 2016.5 聊城大学 混合流水调度优化
     
代表作
论文名称
An Exact Algorithm for the Shortest Path Problem With Position-Based Learning Effects
 
答辩委员会组成信息
姓名职称导师类别工作单位是否主席备注
秦小麟 正高 教授 博导 南京航空航天大学 计算机科学与技术
周晓峰 正高 教授 博导 河海大学
蒋嶷川 正高 教授 博导 东南大学
李必信 正高 教授 博导 东南大学
王红兵 正高 教授 博导 东南大学
      
答辩秘书信息
姓名职称工作单位备注
朱夏 副高 副教授 东南大学