三值重力搜索算法解决图平面化问题：一种新方法

"基于三值重力搜索算法的图平面化问题优化" 本文主要介绍了一种新的优化算法——三值重力搜索算法（Triple-Valued Gravitational Search Algorithm, TGSA），该算法应用于解决图平面化问题（Graph Planarization Problem, GPP）。图平面化是图论领域的一个核心问题，它涉及到将一个无向图绘制在平面上，使得没有任何边交叉。由于其复杂性，GPP被归类为一个NP难题。 TGSA采用三值编码方案，这是其区别于传统二进制编码算法的一大创新。通过这种编码方式，算法能更好地处理搜索空间的复杂性。同时，它利用单行路由表示方法将搜索空间量化为三角超立方体，这有助于简化问题的表示和解决过程。 在TGSA中，算法的运行机制受到引力定律的启发，各个代理（即搜索个体）在引力的作用下逐渐向全局最优位置移动。代理的位置更新规则基于两个关键指标：一是速度指数，该指数反映了代理当前的速度状态；二是人口指数，它基于整个种群的累积信息，有助于算法从全局视角进行决策。 实验部分，作者们选取了21个基准实例对TGSA进行了测试，结果显示TGSA能够有效地找到最大平面子图，并将生成的边嵌入到平面中，解决了GPP。特别地，TGSA的独特之处在于它能够找到GPP的多个最佳解决方案，而不仅仅是单一解，这为问题的求解提供了更多可能性。 与传统的元启发式方法比较，TGSA在解决方案的质量上表现出优越性，而且在合理的计算时间内就能得出结果。这些比较进一步证实了TGSA在解决GPP时的高效性和准确性。 这篇研究论文提出了一个新颖的优化算法——TGSA，它在图平面化问题上展示了强大的求解能力，不仅能够找到高质量的解决方案，还能找到多种最优解，为图论和优化领域提供了一个有价值的工具。通过引入三值编码和引力搜索机制，TGSA为解决NP难题提供了一个新的视角和策略。