论文标题
一种遗传算法，用于将周期直线嵌入到给定的一组点上的简单多边形内
A genetic algorithm for straight-line embedding of a cycle onto a given set of points inside simple polygons
论文作者
论文摘要
在本文中，我们研究了将n个顶点嵌入到一个简单多边形内的N点集中的问题。问题的目的是，必须在没有弯曲的情况下嵌入周期，并且不会与自身和多边形相交。这个问题是一个开放问题的特殊情况，即找到A（S，X，T） - 简单的Hamiltonian路径在一个简单的多边形内部，该路径不会与多边形的侧面相交。在本文中检查了问题的复杂性，但已证明类似的问题是NP综合的。我们已经根据遗传算法提出了一种元启发式算法，该算法用于直线嵌入，并在简单多边形内部的一组点集中，与最小的交叉点数量的循环嵌入。所提出的遗传算法的效率是由于突变操作的定义，如果循环的嵌入式边缘之间存在相交，则将其除去。实验结果表明，使用此突变操作的算法版本的结果比仅使用通常的两点突变操作的版本要高得多。
In this paper, we have examined the problem of embedding a cycle of n vertices onto a given set of n points inside a simple polygon. The goal of the problem is that the cycle must be embedded without bends and does not intersect itself and the polygon. This problem is a special case of the open problem of finding a (s, X, t) - simple Hamiltonian path inside a simple polygon that does not intersect itself and the sides of the polygon. The complexity of the problem is examined in this paper is open, but it has been proved that similar problems are NP-complete. We have presented a metaheuristic algorithm based on a genetic algorithm for straight-line embedding of a cycle with the minimum numbers of intersections, onto a given set of points inside simple polygons. The efficiency of the proposed genetic algorithm is due to the definition of the mutation operation, which removes it if there is an intersection between the embedded edges of the cycle. The experimental results show that the results of the version of the algorithm that uses this mutation operation are much more efficient than the version that uses only the usual two-points mutation operation.
