Grant: Discovery Grants Program - Individual

Combinatorial optimization problems arise in many real-life situations, such as manufacturing systems/production scheduling, fleet management and logistics, VLSI design, communication networks, resource assignment, game industry and bioinformatics. A common theme in these applications is the search for a "best" configuration of a set of variables to achieve certain goals, given a set of often conflicting constraints. A major difficulty in such searches arises from the potentially huge and complex search space. The use of computational techniques that employ heuristics to adequately address the search space and make the actual computation tractable within reasonable time is important. The primary objective of this research is to employ AI technology to develop algorithms and programs for practical combinatorial optimization problems. Specifically Genetic Algorithms (GAs) and Ant-system optimization will be investigated. GAs are inspired by population genetics and the Darwinian evolutionary theory of natural selection. An ant-based system is defined as a population of interacting artificial ant agents that is able to optimize some global objective/s through collaborative search of a solution space. The research on GAs is active and extensive. These algorithms can be applied to not only combinatorial optimization problems, but also to other areas, such as image analysis, handwriting recognization, data analysis and classification, natural language processing, and computational biology.