0000000000255776
AUTHOR
Noureddine Bouhmala
Stochastic Learning for SAT- Encoded Graph Coloring Problems
The graph coloring problem (GCP) is a widely studied combinatorial optimization problem due to its numerous applications in many areas, including time tabling, frequency assignment, and register allocation. The need for more efficient algorithms has led to the development of several GC solvers. In this paper, the authors introduce a team of Finite Learning Automata, combined with the random walk algorithm, using Boolean satisfiability encoding for the GCP. The authors present an experimental analysis of the new algorithm’s performance compared to the random walk technique, using a benchmark set containing SAT-encoding graph coloring test sets.
Solving Graph Coloring Problems Using Learning Automata
The graph coloring problem (GCP) is a widely studied combinatorial optimization problem with numerous applications, including time tabling, frequency assignment, and register allocation. The growing need for more efficient algorithms has led to the development of several GCP solvers. In this paper, we introduce the first GCP solver that is based on Learning Automata (LA). We enhance traditional Random Walk with LA-based learning capability, encoding the GCP as a Boolean satisfiability problem (SAT). Extensive experiments demonstrate that the LA significantly improve the performance of RW, thus laying the foundation for novel LA-based solutions to the GCP.
Crowd Models for Emergency Evacuation: A Review Targeting Human-Centered Sensing
Emergency evacuation of crowds is a fascinating phenomenon that has attracted researchers from various fields. Better understanding of this class of crowd behavior opens up for improving evacuation policies and smarter design of buildings, increasing safety. Recently, a new class of disruptive technology has appeared: Human-centered sensing which allows crowd behavior to be monitored in real-time, and provides the basis for real-time crowd control. The question then becomes: to what degree can previous crowd models incorporate this development, and what areas need further research? In this paper, we provide a survey that describes some widely used crowd models and discuss their advantages a…
Using Learning Automata to Enhance Local-Search Based SAT Solvers with Learning Capability
In this work, we have introduced a new approach based on combining Learning Automata with Random Walk and GSAT w/Random Walk. In order to get a comprehensive overview of the new algorithms' performance, we used a set of benchmark problems containing different problems from various domains. In these benchmark problems, both RW and GSATRW suffers from stagnation behaviour which directly affects their performance. This phenomenon is, however, only observed for LA-GSATRW on the largest problem instances. Finally, the
Comparing Different Crowd Emergency Evacuation Models Based on Human Centered Sensing Criteria
Emergency evacuation of crowds is a fascinating phenomenon that has attracted researchers from various fields. Better understanding of this class of crowd behavior opens up for improving evacuation policies and smarter design of buildings, increasing safety. Recently, a new class of disruptive technology has appeared: Human-centered sensing which allows crowd behavior to be monitored in real-time, and provides the basis for real-time crowd control. The question then becomes: to what degree can previous crowd models incorporate this development, and what areas need further research? In this paper, the authors provide a survey that describes some widely used crowd models and discuss the advan…
Towards Multilevel Ant Colony Optimisation for the Euclidean Symmetric Traveling Salesman Problem
Ant Colony Optimization ACO metaheuristic is one of the best known examples of swarm intelligence systems in which researchers study the foraging behavior of bees, ants and other social insects in order to solve combinatorial optimization problems. In this paper, a multilevel Ant Colony Optimization MLV-ACO for solving the traveling salesman problem is proposed, by using a multilevel process operating in a coarse-to-fine strategy. This strategy involves recursive coarsening to create a hierarchy of increasingly smaller and coarser versions of the original problem. The heart of the approach is grouping the variables that are part of the problem into clusters, which is repeated until the size…
Combining finite learning automata with GSAT for the satisfiability problem
A large number of problems that occur in knowledge-representation, learning, very large scale integration technology (VLSI-design), and other areas of artificial intelligence, are essentially satisfiability problems. The satisfiability problem refers to the task of finding a satisfying assignment that makes a Boolean expression evaluate to True. The growing need for more efficient and scalable algorithms has led to the development of a large number of SAT solvers. This paper reports the first approach that combines finite learning automata with the greedy satisfiability algorithm (GSAT). In brief, we introduce a new algorithm that integrates finite learning automata and traditional GSAT use…