Many real-world optimization problems are difficult to solve because, in part, they have an exponential number of possible solutions---exhaustively looking at each one to find the best solution is not feasible. The class of NP-complete problems fall into this category. We can, however, collect all possible solutions onto a hyper-surface, where each point corresponds to a unique solution. We can then design a computer algorithm that explores this hyper-surface, searching for the globally best solution. Unfortunately, this search process is not trivial because the hyper-surface often contains numerous local optima. The only hope of finding a reasonably good solution is to conduct a heuristic search.
The field of evolutionary computation (EC) involves the study and development of algorithms that simulate Darwinian evolution to conduct a search. There are a number of fundamental algorithms such as genetic algorithm, the evolution strategy, and differential evolution. Search, however, is not the only application area. For example, artificial immune systems are used to detect behavioral changes in fault tolerant systems.
The above figure shows a canonical EC algorithm. Each individual in the population represents a unique solution to the optimization problem. After randomly generating an initial population, the "variation" block creates a number of offspring (new solutions) via stochastic operators. All individuals are then evaluated for fitness (solution quality). Finally, the "selection" block chooses the highly fit individuals to be parents in the next generation. Selection may be deterministic or stochastic, but spawning offspring is strictly stochastic. The algorithm continues running until either a fixed number of generations have been produced or an acceptable solution has been found.
These algorithms are ideally suited for finding good solutions to combinatorial problems, multi-attribute problems and real-valued parameter problems. Application areas include drug design, control system design, game theory, scheduling problems, evolvable hardware and all varieties of NP-complete and NP-hard problems.
The Computational Intelligence Society in the IEEE supports and sponsors many activities in the evolutionary computation community. Indeed, they oversee a number of publications including the IEEE Transactions on Evolutionary Computation and the IEEE Computational Intelligence Magazine. It is an organization well worth joining. Click here for more information.
EC Journals & Magazine:
Back to main page