Given a graph whose vertex set is partitioned, the partition coloring problem (PCP) requires the selection of one vertex from each partite set, such that the subgraph induced by the set of the selected vertices has the minimum chromatic number. Motivated by the routing and wavelength assignment problem for optical networks, PCP has been used to model many other real-world applications, such as dichotomy-based constraint encoding and scheduling problems. Solving PCP for large graphs is still a challenge since it is NP-complete. In this article, we first propose a key concept called a partition independent set (PIS) and design an efficient algorithm called FastPIS to find a maximum PIS. By applying FastPIS with a simple coloring procedure, we can obtain a high-quality initial solution for PCP. Moreover, we propose a reduction rule based on another novel concept called an ℓ-clustering-degree bound ordered set (ℓ-CDBOS), by which the scale of the working graph can be iteratively reduced. Based on these techniques, we develop an efficient method called HotPGC for solving PCP. The proposed algorithm is evaluated on benchmark graphs, and computational results show that HotPGC achieves highly competitive performance, compared with the state-of-the-art algorithms. The influence of the proposed reduction rule on the efficiency of HotPGC is also analyzed.

Metaheuristic algorithms (MH) and machine learning (ML) are important components of artificial intelligence (AI). The synergy between MH’s optimization search capabilities and ML’s data analysis strengths has proven to be highly effective, providing a powerful combination for delivering high-quality solutions across diverse fields. Particularly in real-world applications such as autonomous driving and healthcare, the integration of MH and ML can significantly enhance the intelligence level and decision-making efficiency of systems, addressing the urgent societal and industrial demands for high-efficiency and high-precision solutions. This paper clarifies the logic behind the surge in research on MH-ML hybrid algorithms and addresses the gaps in current reviews regarding their timeliness and breadth of perspective. We begin by elucidating the fundamental concepts underpinning MH and ML, followed by a comprehensive classification framework that categorizes and synthesizes the latest research findings systematically. The paper concludes with an exploration of the challenges inherent in MH-ML hybrid algorithms and proposes future research directions. The analysis of the collected literature demonstrates that the integration of MH and ML generally enhances the performance of algorithms in specific problems. Despite progress from simple combinations to deeper integrations, challenges such as theoretical lag and interpretability remain. Future research will focus on solving these challenges by exploring further integration, using open-source tools, and adapting across diverse domains to expand the use of MH-ML hybrid algorithms.

The minimum vertex cover (MVC) problem is a canonical NP-hard combinatorial optimization problem aiming to find the smallest set of vertices such that every edge has at least one endpoint in the set. This problem has extensive applications in cybersecurity, scheduling, and monitoring link failures in wireless sensor networks (WSNs). Numerous local search algorithms have been proposed to obtain “good” vertex coverage. However, due to the NP-hard nature, it is challenging to efficiently solve the MVC problem, especially on large graphs. In this paper, we propose an efficient local search algorithm for MVC called TIVC, which is based on two main ideas: a 3-improvements (TI) framework with a tiny perturbation and edge selection strategy. We conducted experiments on real-world large instances of a massive graph benchmark. Compared with three state-of-the-art MVC algorithms, TIVC shows superior performance in accuracy and possesses a remarkable ability to identify significantly smaller vertex covers on many graphs.

Intelligent agents and multi-agent systems are increasingly used in complex scenarios, such as controlling groups of drones and non-player characters in video games. In these applications, multi-agent navigation and obstacle avoidance are foundational functions. However, problems become more challenging with the increased complexity of the environment and the dynamic decision-making interactions among agents. The Multi-Agent Deep Deterministic Policy Gradient (MADDPG) algorithm is a classical multi-agent reinforcement learning algorithm successfully used to improve agents’ performance. However, it ignores the temporal message hidden in agents’ interaction with the environment and needs to be more efficient in scenarios with many agents due to its training technique. To address the limitations of MADDPG, we propose to explore modified algorithms of MADDPG for multi-agent navigation and obstacle avoidance. By combining MADDPG with Long Short-Term Memory (LSTM), we obtain the MADDPG-LSTMactor algorithm, which leverages continuous observations over time as input for the policy network, enabling the LSTM layer to capture hidden temporal patterns. Moreover, by simplifying the input of the critic network, we obtain the MADDPG-L algorithm for efficiency improvement in scenarios with many agents. Experimental results demonstrate that these algorithms outperform existing networks in the OpenAI multi-agent particle environment. We also conducted a comparative study of the LSTM-based approach with Transformer and self-attention models in the task of multi-agent navigation and obstacle avoidance. The results reveal that Transformer and self-attention do not consistently outperform LSTM. The LSTM-based model exhibits a favorable tradeoff across varying sequence lengths. Overall, this work addresses the limitations of MADDPG in multi-agent navigation and obstacle avoidance tasks, providing insights for developing intelligent agents and multi-agent systems.

DeoxyriboNucleic Acid (DNA) encryption is a new encryption method that appeared along with the research of DNA nanotechnology in recent years. Due to the complexity of biology in DNA nanotechnology, DNA encryption brings in an additional difficulty in deciphering and, thus, can enhance information security. As a new approach in DNA nanotechnology, DNA strand displacement has particular advantages such as being enzyme free and self-assembly. However, the existing research on DNA-strand-displacement-based encryption has mostly stayed at a theoretical or simulation stage. To this end, this paper proposes a new DNA-strand-displacement-based encryption framework. This encryption framework involves three main strategies. The first strategy was a tri-phase conversion from plaintext to DNA sequences according to a Huffman-coding-based transformation rule, which enhances the concealment of the information. The second strategy was the development of DNA strand displacement molecular modules, which produce the initial key for information encryption. The third strategy was a cyclic-shift-based operation to extend the initial key long enough, and thus increase the deciphering difficulty. The results of simulation and biological experiments demonstrated the feasibility of our scheme for encryption. The approach was further validated in terms of the key sensitivity, key space, and statistic characteristic. Our encryption framework provides a potential way to realize DNA-strand-displacement-based encryption via biological experiments and promotes the research on DNA-strand-displacement-based encryption.