The surface-based DNA computing is one of the methods of DNA computing which uses DNA strands immobilized on a solid surface. In this paper, we applied surface-based DNA computing for solving the dominating set proble...The surface-based DNA computing is one of the methods of DNA computing which uses DNA strands immobilized on a solid surface. In this paper, we applied surface-based DNA computing for solving the dominating set problem. At first step, surface-based DNA solution space was constructed by using appropriate DNA strands. Then, by application of a DNA parallel algorithm, dominating set problem was resolved in polynomial time.展开更多
The minimum weight dominating set problem （MWDSP） is an NP-hard problem with a lot of real-world applications. Several heuristic algorithms have been presented to produce good quality solutions. However, the solutio...The minimum weight dominating set problem （MWDSP） is an NP-hard problem with a lot of real-world applications. Several heuristic algorithms have been presented to produce good quality solutions. However, the solution time of them grows very quickly as the size of the instance increases. In this paper, we propose a binary particle swarm optimization （FBPSO） for solving the MWDSP approximately. Based on the characteristic of MWDSP, this approach designs a new position updating rule to guide the search to a promising area. An iterated greedy tabu search is used to enhance the solution quality quickly. In addition, several stochastic strategies are employed to diversify the search and prevent premature convergence. These methods maintain a good balance between the exploration and the exploitation. Experimental studies on 106 groups of 1 060 instances show that FBPSO is able to identify near optimal solutions in a short running time. The average deviation between the solutions obtained by FBPSO and the best known solutions is 0.441%. Moreover, the average solution time of FBPSO is much less than that of other existing algorithms. In particular, with the increasing of instance size, the solution time of FBPSO grows much more slowly than that of other existing algorithms.展开更多
二次分配问题QAP(quadratic assignment problem)的变种问题是当前的研究热点.实际应用中存在一类不能用QAP及其现有变种描述的问题,该类问题在QAP问题的基础上增加了额外的约束条件:将设备分为黑白两色,其中白色设备要求与至少一个黑...二次分配问题QAP(quadratic assignment problem)的变种问题是当前的研究热点.实际应用中存在一类不能用QAP及其现有变种描述的问题,该类问题在QAP问题的基础上增加了额外的约束条件:将设备分为黑白两色,其中白色设备要求与至少一个黑色设备的距离不超过预定阈值.文章将之定义为黑白二次分配问题BWQAP(Black and White QAP).文章首先分析了它的计算复杂性,指出该问题是NP-难解问题,不存在ε-近似度的多项式时间近似算法(ε>0).同时证明了其可行解的存在性与黑白图上的支配集问题等价,也属于NP-难解问题.为了能在可接受的时间内得到大规模实例质量可接受的近似解,提出了一种求解BWQAP的启发式算法GFO.该算法利用QAP现有算法得到初始解,然后利用局部搜索策略完成解的可行化和优化.大量实验表明,该启发式算法能够有效地求解BWQAP问题的实例.展开更多
针对城市环境的车联网VANETSs(vehicular ad hoc networks)的非安全应用,多数路由协议采用贪婪技术,旨在降低端到端传输时延。然而,贪婪技术易引发局部最大化问题以及数据拥塞,增加端到端传输时延。因此,提出基于稳定支配集路由协议S-CD...针对城市环境的车联网VANETSs(vehicular ad hoc networks)的非安全应用,多数路由协议采用贪婪技术,旨在降低端到端传输时延。然而,贪婪技术易引发局部最大化问题以及数据拥塞,增加端到端传输时延。因此,提出基于稳定支配集路由协议S-CDSR(stable CDS based routing)。S-CDSR协议属于分布式路由,在数据传输前,计算整条路由路径的端到端传输时延,在每条路段上建立稳定的主干节点,在十字路口,利用桥节点连接路段上的主干节点,桥节点依据路径时延信息计算路段的权值,具有最低权值的路段被选择为转发数据的路径。仿真结果表明,S-CDSR协议能够降低端到端传输时延,提高数据包传输率。与ICAR协议相比,S-CDSR协议的端到端传输时延下降了43%。展开更多
文摘The surface-based DNA computing is one of the methods of DNA computing which uses DNA strands immobilized on a solid surface. In this paper, we applied surface-based DNA computing for solving the dominating set problem. At first step, surface-based DNA solution space was constructed by using appropriate DNA strands. Then, by application of a DNA parallel algorithm, dominating set problem was resolved in polynomial time.
基金This work is supported partially by the National Natural Science Foundation of China under Grant No. 11301255, the Natural Science Foundation of Fujian Province of China under Grant No. 2016J01025, and the Program for New Century Excellent Talents in Fujian Province University.
文摘The minimum weight dominating set problem （MWDSP） is an NP-hard problem with a lot of real-world applications. Several heuristic algorithms have been presented to produce good quality solutions. However, the solution time of them grows very quickly as the size of the instance increases. In this paper, we propose a binary particle swarm optimization （FBPSO） for solving the MWDSP approximately. Based on the characteristic of MWDSP, this approach designs a new position updating rule to guide the search to a promising area. An iterated greedy tabu search is used to enhance the solution quality quickly. In addition, several stochastic strategies are employed to diversify the search and prevent premature convergence. These methods maintain a good balance between the exploration and the exploitation. Experimental studies on 106 groups of 1 060 instances show that FBPSO is able to identify near optimal solutions in a short running time. The average deviation between the solutions obtained by FBPSO and the best known solutions is 0.441%. Moreover, the average solution time of FBPSO is much less than that of other existing algorithms. In particular, with the increasing of instance size, the solution time of FBPSO grows much more slowly than that of other existing algorithms.
文摘二次分配问题QAP(quadratic assignment problem)的变种问题是当前的研究热点.实际应用中存在一类不能用QAP及其现有变种描述的问题,该类问题在QAP问题的基础上增加了额外的约束条件:将设备分为黑白两色,其中白色设备要求与至少一个黑色设备的距离不超过预定阈值.文章将之定义为黑白二次分配问题BWQAP(Black and White QAP).文章首先分析了它的计算复杂性,指出该问题是NP-难解问题,不存在ε-近似度的多项式时间近似算法(ε>0).同时证明了其可行解的存在性与黑白图上的支配集问题等价,也属于NP-难解问题.为了能在可接受的时间内得到大规模实例质量可接受的近似解,提出了一种求解BWQAP的启发式算法GFO.该算法利用QAP现有算法得到初始解,然后利用局部搜索策略完成解的可行化和优化.大量实验表明,该启发式算法能够有效地求解BWQAP问题的实例.
基金Supported by National Natural Science Foundation of China(11061023)Youth Foundation of Jiangxi Educational Committee(GJJ10086)Natural Science Foundation of Jiangxi Province(2010GZS0145)
文摘针对城市环境的车联网VANETSs(vehicular ad hoc networks)的非安全应用,多数路由协议采用贪婪技术,旨在降低端到端传输时延。然而,贪婪技术易引发局部最大化问题以及数据拥塞,增加端到端传输时延。因此,提出基于稳定支配集路由协议S-CDSR(stable CDS based routing)。S-CDSR协议属于分布式路由,在数据传输前,计算整条路由路径的端到端传输时延,在每条路段上建立稳定的主干节点,在十字路口,利用桥节点连接路段上的主干节点,桥节点依据路径时延信息计算路段的权值,具有最低权值的路段被选择为转发数据的路径。仿真结果表明,S-CDSR协议能够降低端到端传输时延,提高数据包传输率。与ICAR协议相比,S-CDSR协议的端到端传输时延下降了43%。
