Metaheurísticas evolutivas para o problema de roteamento de unidades móveis de pistoneio

This paper presents metaheuristic strategies based on the framework of evolutionary algorithms (Genetic and Memetic) with the addition of Technical Vocabulary Building for solving the Problem of Optimizing the Use of Multiple Mobile Units Recovery of Oil (MRO units). Because it is an NP-hard problem, a mathematical model is formulated for the problem, allowing the construction of test instances that are used to validate the evolutionary metaheuristics developed

Algoritomos transgenéticos aplicados ao problema da árvore geradora biobjetivo

The Multiobjective Spanning Tree is a NP-hard Combinatorial Optimization problem whose application arises in several areas, especially networks design. In this work, we propose a solution to the biobjective version of the problem through a Transgenetic Algorithm named ATIS-NP. The Computational Transgenetic is a metaheuristic technique from Evolutionary Computation whose inspiration relies in the conception of cooperation (and not competition) as the factor of main influence to evolution. The algorithm outlined is the evolution of a work that has already yielded two other transgenetic algorithms. In this sense, the algorithms previously developed are also presented. This research also comprises an experimental analysis with the aim of obtaining information related to the performance of ATIS-NP when compared to other approaches. Thus, ATIS-NP is compared to the algorithms previously implemented and to other transgenetic already presented for the problem under consideration. The computational experiments also address the comparison to two recent approaches from literature that present good results, a GRASP and a genetic algorithms. The efficiency of the method described is evaluated with basis in metrics of solution quality and computational time spent. Considering the problem is within the context of Multiobjective Optimization, quality indicators are adopted to infer the criteria of solution quality. Statistical tests evaluate the significance of results obtained from computational experiments

Uma análise experimental de algoritmos exatos aplicados ao problema da árvore geradora multiobjetivo

The Multiobjective Spanning Tree Problem is NP-hard and models applications in several areas. This research presents an experimental analysis of different strategies used in the literature to develop exact algorithms to solve the problem. Initially, the algorithms are classified according to the approaches used to solve the problem. Features of two or more approaches can be found in some of those algorithms. The approaches investigated here are: the two-stage method, branch-and-bound, k-best and the preference-based approach. The main contribution of this research lies in the fact that no research was presented to date reporting a systematic experimental analysis of exact algorithms for the Multiobjective Spanning Tree Problem. Therefore, this work can be a basis for other research that deal with the same problem. The computational experiments compare the performance of algorithms regarding processing time, efficiency based on the number of objectives and number of solutions found in a controlled time interval. The analysis of the algorithms was performed for known instances of the problem, as well as instances obtained from a generator commonly used in the literature

Distribuição de derivados de petróleo por redes de polidutos: uma abordagem através de algoritmos evolucionários híbridos para um problema triobjetivo

An important problem faced by the oil industry is to distribute multiple oil products through pipelines. Distribution is done in a network composed of refineries (source nodes), storage parks (intermediate nodes), and terminals (demand nodes) interconnected by a set of pipelines transporting oil and derivatives between adjacent areas. Constraints related to storage limits, delivery time, sources availability, sending and receiving limits, among others, must be satisfied. Some researchers deal with this problem under a discrete viewpoint in which the flow in the network is seen as batches sending. Usually, there is no separation device between batches of different products and the losses due to interfaces may be significant. Minimizing delivery time is a typical objective adopted by engineers when scheduling products sending in pipeline networks. However, costs incurred due to losses in interfaces cannot be disregarded. The cost also depends on pumping expenses, which are mostly due to the electricity cost. Since industrial electricity tariff varies over the day, pumping at different time periods have different cost. This work presents an experimental investigation of computational methods designed to deal with the problem of distributing oil derivatives in networks considering three minimization objectives simultaneously: delivery time, losses due to interfaces and electricity cost. The problem is NP-hard and is addressed with hybrid evolutionary algorithms. Hybridizations are mainly focused on Transgenetic Algorithms and classical multi-objective evolutionary algorithm architectures such as MOEA/D, NSGA2 and SPEA2. Three architectures named MOTA/D, NSTA and SPETA are applied to the problem. An experimental study compares the algorithms on thirty test cases. To analyse the results obtained with the algorithms Pareto-compliant quality indicators are used and the significance of the results evaluated with non-parametric statistical tests.

SERS-barcoded colloidal gold NP assemblies as imaging agents for use in biodiagnostics

There is a growing need for new biodiagnostics that combine high throughput with enhanced spatial resolution and sensitivity. Gold nanoparticle (NP) assemblies with sub-10 nm particle spacing have the benefits of improving detection sensitivity via Surface enhanced Raman scattering (SERS) and being of potential use in biomedicine due to their colloidal stability. A promising and versatile approach to form solution-stable NP assemblies involves the use of multi-branched molecular linkers which allows tailoring of the assembly size, hot-spot density and interparticle distance. We have shown that linkers with multiple anchoring end-groups can be successfully employed as a linker to assemble gold NPs into dimers, linear NP chains and clustered NP assemblies. These NP assemblies with diameters of 30-120 nm are stable in solution and perform better as SERS substrates compared with single gold NPs, due to an increased hot-spot density. Thus, tailored gold NP assemblies are potential candidates for use as biomedical imaging agents. We observed that the hot-spot density and in-turn the SERS enhancement is a function of the linker polymer concentration and polymer architecture. New deep Raman techniques like Spatially Offset Raman Spectroscopy (SORS) have emerged that allow detection from beneath diffusely scattering opaque materials, including biological media such as animal tissue. We have been able to demonstrate that the gold NP assemblies could be detected from within both proteinaceous and high lipid containing animal tissue by employing a SORS technique with a backscattered geometry.

Border basis detection is NP-complete

Border basis detection (BBD) is described as follows: given a set of generators of an ideal, decide whether that set of generators is a border basis of the ideal with respect to some order ideal. The motivation for this problem comes from a similar problem related to Grobner bases termed as Grobner basis detection (GBD) which was proposed by Gritzmann and Sturmfels (1993). GBD was shown to be NP-hard by Sturmfels and Wiegelmann (1996). In this paper, we investigate the computational complexity of BBD and show that it is NP-complete.

Complejos proteicos elipsoidales NP: Octámero y su relación con el ensamblaje de nucleosomas

Se caracterizan los complejos entre la nucleoplasmina, una chaperona nuclear, y el octámero de histonas y se ve su papel en el ensamblaje de nucleosomas.

NP难问题的算法和实验性研究

NP难是计算机科学中的一个重要概念和核心问题，自从它的提出到现在， 人们已经得到了很多重要的理论结果。直观上讲，一个问题一旦被证明是NP难 的就意味着我们很难找到该问题的一个多项式时间的有效算法。但从实用的角 度讲，对于应用中遇到的问题，单单是证明它很难（是NP难的）是不够的，如何 在合理的时间内求解实际问题也是必须解决的现实问题。本文主要侧重于NP难 问题的算法和实验性研究，研究对象主要是可满足性问题、图的顶点染色、图 的子图匹配等NP难问题，以及可满足性模理论的解空间计算和体积估算等扩展 问题。 围绕几个著名的问题，本文的主要工作如下： 针对图染色问题，日本研究人员提出了一种通过组合小图单元得到大的难 实例的方法。他们通过试错的方式手工找到了7个小图单元。我们提出了一种新 的构造算法来系统地生成这类小图单元，用我们的算法生成的难图染色实例， 主流的图染色工具需要指数时间才能求解；在一些专门求解色数比较小的图的 图染色工具上我们的算法生成的实例更难求解。针对皇后图染色问题，我们利 用模型查找工具SEM来对这类问题进行求解，在求解过程中提出了新的变量选 择策略，发现比简单地使用可满足性问题工具和图染色工具效果要好。 针对语义Web推理中的关键问题RDF蕴含关系的判定问题，我们利用从子 图同构问题到可满足性问题的编码方案，把它转化为命题逻辑公式的可满足性 判定问题，并采用了启发式的方法对编码过程进行必要的化简得到较少的布尔 公式，然后再利用高效的可满足性问题工具来求解。这种转化为可满足性问题 的方法，是跟RDF简单蕴含的模型论语义结合比较自然的一个方法。在小规模 实例上，这种方法的效果也很好。 针对布尔和数值混合约束的公式，即可满足性模理论（线性理论）公式的 体积计算这一新问题，我们首先给出一个直接计算体积的方法，然后提出一个 改进的算法，并研究了如何通过引入可满足性模理论中的技术来尝试对该算法 进一步地改进。我们实现了工具并做了实验。在一个实际的程序实例上，我们 还就“热门路径”问题做了实例研究和探讨。 体积计算是一个有广泛应用背景的经典难题（#P难的），但以前的方法要 么只能处理线性约束，要么只具有理论价值（不够实用）；针对含非线性约束的 体积计算问题我们提出了实用的算法，并设计了相应的工具，在低维实例有很 好的逼近效果。

纯公钥模型下对NP语言的高效并发零知识证明系统

提出了一种从3轮公开掷币的对任何NP语言的诚实验证者零知识证明系统到纯公钥模型下4轮f轮最优）对同一语言的具有并发合理性的并发零知识证明系统．该转化方法有如下优点：1）它只引起D（1）（常数个）额外的模指数运算，相比DiCrescenzo等人在ICALP05上提出的需要qn）个额外的模指数运算的转化方法孩系统在效率上有着本质上的提高，而所需的困难性假设不变；2）在离散对数假设下，该转化方法产生一个完美零知识证明系统．注意到DiCrescenzo等人提出的系统只具有计算零知识性质．该转化方法依赖于一个特殊的对承诺中的离散对数的3轮诚实验证者零知识的证明系统．构造了两个基于不同承诺方案的只需要常数个模指数运算的系统这种系统可能有着独立价值．