一种基于DNA分子计算解决不平衡分配问题的并行生物优化算法。
A Parallel Biological Optimization Algorithm to Solve the Unbalanced Assignment Problem Based on DNA Molecular Computing.
作者信息
Wang Zhaocai, Pu Jun, Cao Liling, Tan Jian
机构信息
College of Information, Shanghai Ocean University, Shanghai 201306, China.
Center for Finance and Accounting Research of University of International Business and Economics, Beijing 100029, China.
出版信息
Int J Mol Sci. 2015 Oct 23;16(10):25338-52. doi: 10.3390/ijms161025338.
The unbalanced assignment problem (UAP) is to optimally resolve the problem of assigning n jobs to m individuals (m < n), such that minimum cost or maximum profit obtained. It is a vitally important Non-deterministic Polynomial (NP) complete problem in operation management and applied mathematics, having numerous real life applications. In this paper, we present a new parallel DNA algorithm for solving the unbalanced assignment problem using DNA molecular operations. We reasonably design flexible-length DNA strands representing different jobs and individuals, take appropriate steps, and get the solutions of the UAP in the proper length range and O(mn) time. We extend the application of DNA molecular operations and simultaneity to simplify the complexity of the computation.
非平衡分配问题（UAP）是要最优地解决将n项工作分配给m个人（m < n）的问题，以便获得最小成本或最大利润。它是运营管理和应用数学中一个极其重要的非确定性多项式（NP）完全问题，有许多实际应用。在本文中，我们提出了一种新的并行DNA算法，用于使用DNA分子操作来解决非平衡分配问题。我们合理设计代表不同工作和个人的可变长度DNA链，采取适当步骤，并在适当的长度范围内和O(mn)时间内得到UAP的解。我们扩展了DNA分子操作的应用并同时简化了计算的复杂性。
Zotero 插件