基于局部搜索策略的若干组合优化问题求解算法研究

发布时间：2018-06-09 06:10

本文选题：组合优化问题 + 局部搜索算法　；参考：《东北师范大学》2017年博士论文

【摘要】：组合优化问题是计算机科学与运筹学的一个重要分支,主要是通过对数学方法的研究去寻找离散事件的最优分组、编排、筛选或次序等。组合优化问题在信息技术、交通运输、通信网络、经济管理等领域有着重要的应用。求解组合优化问题的算法包括精确算法和启发式算法,精确算法能够求出问题的最优解,但是随着问题规模逐渐增大,求解这些问题最优解所需的计算量与存储空间呈指数增长,会带来所谓的“组合爆炸”现象,使得在现有的计算能力下,使用精确算法求得最优解几乎变得不可能。在这种情况下,一些启发式算法应运而生,如局部搜索算法、松弛算法等。对于难解问题实例,局部搜索算法可以在合理的时间内找到近似最优解或最优解。同时局部搜索算法具有简单、高效、容易并行等优点。局部搜索算法很容易实现,对于优化问题,只要定义好解空间的邻居结构,就可以用局部搜索算法来求解。目前已有很多研究表明了局部搜索算法的高效性,尤其在求解NP难问题的较大实例,局部搜索算法有很大的潜力。由于很多局部搜索算法都加入了随机策略,不同随机种子的运行就可实现并行。本论文中,我们对局部搜索算法进行研究,并根据具体问题的特点设计高效的算法。具体来说,我们选择最小加权顶点覆盖问题、最小有容量支配集问题和最小连通支配集问题作为研究对象,设计高效的局部搜索算法。本文的主要研究工作和贡献如下:(1)提出基于动态打分策略和加权格局检测策略的局部搜索算法(DLSWCC)求解最小加权顶点覆盖问题。在DLSWCC算法中,动态打分策略在搜索陷入局部最优时更新边的权值,进而改变顶点的分数,从而使搜索跳出局部最优并向更优的方向进行;加权格局检测策略考虑了每个顶点的环境信息,用来减少局部搜索中的循环问题;结合以上两个策略我们提出了顶点选择方法,确定在局部搜索过程中加入或移出候选解的顶点。我们在大量的标准实例上对DLSWCC算法进行了测试,实验结果表明DLSWCC算法要优于现有最优算法。(2)提出基于顶点惩罚策略和两种模式的被支配顶点选择策略的局部搜索算法(LS_PD)求解最小有容量支配集问题。在LS_PD算法中,顶点惩罚策略在搜索陷入局部最优时增加当前未被支配顶点的罚值,罚值的改变会影响顶点的分数,使得算法跳出局部最优;两种模式的被支配顶点选择策略以的概率随机选择加入候选解的顶点支配哪些顶点,以1-的概率贪心选择;同时用强化策略来提高每个顶点容量的利用率,从而提高算法的性能。我们在固定容量和变化容量的一般图及UDG图上对LS_PD算法进行了对比实验。实验结果表明,无论是一般图还是UDG图,LS_PD算法都具有较高性能。(3)提出基于候选顶点集合和解的连接元素集合的GRASP算法求解最小连通支配集问题。在GRASP算法中,在构造初始候选解时,加入候选顶点集合中的顶点不会破坏候选解的连通性;在搜索过程中,加入解的连接元素集合中的顶点会使不连通的候选解变为连通;此外,我们还使用评估函数定义了每个顶点的分数,禁忌策略来避免局部搜索重复访问以前搜索过的解。我们将GRASP算法与现有最优启发式算法和精确算法进行对比。实验结果表明GRASP算法在LPRNMR实例和随机实例上效果很好,在MLSTP实例上只有少数稀疏图效果不是很好。
[Abstract]:Combinatorial optimization is an important branch of computer science and operational research. It is mainly through the study of mathematical methods to find the optimal grouping, arrangement, selection and order of discrete events. The combinatorial optimization problem has an important application in the fields of information technology, transportation, communication network, economic management and so on. The algorithm includes the exact algorithm and the heuristic algorithm, and the exact algorithm can find the optimal solution of the problem. However, as the scale of the problem is increasing, the amount of computation and storage space for solving the optimal solutions of these problems is increasing exponentially, which will bring the so-called "combination explosion" phenomenon, making the exact algorithm under the existing computing power. In this case, some heuristic algorithms have come into being, such as local search algorithm, relaxation algorithm and so on. In the case of difficult problem, local search algorithm can find the approximate optimal solution or the optimal solution in a reasonable time. Meanwhile, the local search algorithm has the advantages of simple, efficient and easy to parallel. The local search algorithm is easy to implement. As long as the neighbor structure of the solution space is defined, the local search algorithm can be used to solve the problem. At present, many studies have shown the efficiency of the local search algorithm. In particular, the local search algorithm has great potential to solve the problem of NP difficult problem. In this paper, we study local search algorithms and design efficient algorithms based on the characteristics of the specific problems. In this paper, we choose the minimum weighted vertex cover problem, the smallest capacity domination set problem and the minimum connected dominating set question. The main research work and contribution of this paper are as follows: (1) a local search algorithm (DLSWCC) based on dynamic scoring strategy and weighted pattern detection strategy (DLSWCC) is proposed to solve the minimum weighted vertex cover problem. In the DLSWCC algorithm, the dynamic scoring strategy is updated when the search is in the local optimum. The weight of the edge changes the score of the vertex, thus making the search out of the local optimal and in the better direction. The weighted pattern detection strategy takes into account the environmental information of each vertex, and uses it to reduce the circulation problem in the local search. In combination with the above two strategies, we propose a vertex selection method to determine the addition of the local search process to the local search process. We enter or remove the vertices of the candidate solutions. We test the DLSWCC algorithm on a large number of standard instances. The experimental results show that the DLSWCC algorithm is superior to the existing optimal algorithm. (2) the local search algorithm (LS_PD) is proposed to solve the minimum capacity dominating set problem based on the vertex penalty strategy and the two patterns of the dominant vertex selection strategy (LS_PD). In the LS_PD algorithm, the vertex penalty strategy increases the penalty value of the current non dominated vertex when searching for local optimal. The change of penalty will affect the points of the vertex and make the algorithm jump out of the local optimal. The probability random selection of the two modes of the dominant vertex selection strategy is the vertex dominated by the candidate solution and the probability of 1- Greedy choice; at the same time using the strengthening strategy to improve the utilization of each vertex capacity, and thus improve the performance of the algorithm. We compare the LS_PD algorithm with the general diagram of the fixed capacity and the change capacity and the UDG diagram. The experimental results show that both the general and the UDG diagram, the LS_PD algorithm has high performance. (3) proposed based on the weather condition. In the GRASP algorithm, the vertices in the set of candidate vertices will not destroy the connectivity of the candidate solutions in the construction of the initial candidate solutions in the GRASP algorithm. In the search process, the vertices of the join element set in the solution will change the disconnected candidate solutions. In addition, we also use the evaluation function to define the scores of each vertex, the tabu strategy to avoid the repeated access to the previously searched solutions. We compare the GRASP algorithm with the existing optimal heuristic algorithm and the exact algorithm. The experimental results show that the GRASP algorithm has a good effect on the LPRNMR instance and the random instance, in M Only a few sparse graphs on LSTP instances are not very effective.
【学位授予单位】：东北师范大学
【学位级别】：博士
【学位授予年份】：2017
【分类号】：O22

【参考文献】