Branch-and-bound (BnB) and memetic algorithms represent two very different approaches for tackling combinatorial optimization problems. However, these approaches are compatible. In this correspondence, a hybrid model that combines these two techniques is considered. To be precise, it is based on the interleaved execution of both approaches. Since the requirements of time and memory in BnB techniques are generally conflicting, a truncated exact search, namely, beam search, has opted to be carried out. Therefore, the resulting hybrid algorithm has a heuristic nature. The multidimensional 0-1 knapsack problem and the shortest common supersequence problem have been chosen as benchmarks. As will be shown, the hybrid algorithm can produce better results in both problems at the same computational cost, especially for large problem instances
Real-time strategy games offer a wide variety of fundamental AI research challenges. Most of these challenges have applications outside the game domain. This paper provides a review on computational intelligence in real-time strategy games (RTS). It starts with challenges in real-time strategy games, then it reviews different tasks to overcome this challenges. Later, it describes the techniques used to solve this challenges and it makes a relationship between techniques and tasks. Finally, it presents a set of different frameworks used as test-beds for the techniques employed. This paper is intended to be a starting point for future researchers on this topic.