OptiGen Library

Category Intelligent Software>Genetic Algorithm Systems/Tools

Abstract The OptiGen Library is an object-oriented (OO) programming interface incorporating many advanced optimization techniques into one single package.

The OptiGen Library combines the power of single- and multi-objective genetic algorithms, advanced attribute selection algorithms, and other optimization strategies such as simulated annealing into a common object-oriented interface. They can be used to quickly and easily add advanced optimization techniques to your applications.

The OptiGen Library includes extensive on-line help documenting the APIs as well as genetic algorithm theory. In addition, there are multiple examples with corresponding source code that can be pulled from in order to get up and running faster. Product(s) features include:

Solution & Population Based Metaheuristics --

What are Genetic Algorithms - Genetic algorithms are general-purpose search algorithms based upon the principles of evolution observed in nature. It is the most popular type of Evolutionary Algorithm that includes genetic algorithm, genetic programming, evolutionary programming, and evolution strategy.

Genetic algorithms combine selection, crossover, and mutation operators with the goal of finding the best solution to Single-Objective Optimization problems or Pareto-Optimal Front to Multi-Objective Optimization problems. Genetic algorithms evolve until a specified termination criterion is met.

Genetic algorithms in general can be classified into two (2) categories: Single-Objective genetic algorithms and Multi-Objective algorithms. The implemented algorithms in this library include GenerationalGA and SteadyStateGA for Single-Objective Optimization as well as NonDominatedSortingGA for Multi-Objective Optimization.

A solution to a problem is called a chromosome. A chromosome is made up of a collection of genes which are simply the parameters to be optimized as well as collections of constraints and Objectives for Multi-Objective Optimization problems.

A genetic algorithm creates an initial population (a collection of chromosomes), evaluates this population, and then evolves the population through multiple generations (using the genetic operators discussed above...) in the search for a good solution for the problem at hand.

Simulated Annealing - Simulated annealing is a generic probabilistic metaheuristic searching for the global optimal of a given objective function in a large search space.

Mutation Operators --

A mutation is a genetic operator that alters one or more gene values in a chromosome from its initial state. This can result in entirely new gene values being added to the gene pool. With these new gene values, the genetic algorithm may be able to arrive at a better solution than was previously possible.

Mutation is an important part of the genetic search as help, which helps to prevent the population from stagnating at any local optima. Mutation occurs during evolution according to a user-definable mutation probability. This probability should usually be set fairly low (0.01 is a good first choice). If it is set to high, the search will turn into a primitive random search.

OptiGen Library includes the following types of Mutation:

Flip Bit - A mutation operator that simply inverts the value of the chosen gene (0 goes to 1 and 1 goes to 0). This mutation operator can only be used for binary genes.

Boundary - A mutation operator that replaces the value of the chosen gene with either the upper or lower bound for that gene (chosen randomly). This mutation operator can only be used for integer and float genes.

Non-Uniform - A mutation operator that increases the probability that the amount of the mutation will be close to 0 as the generation number increases. This mutation operator keeps the population from stagnating in the early stages of the evolution then allows the genetic algorithm to fine tune the solution in the later stages of evolution. This mutation operator can only be used for integer and float genes.

Uniform - A mutation operator that replaces the value of the chosen gene with a uniform random value selected between the user-specified upper and lower bounds for that gene. This mutation operator can only be used for integer and float genes.

Gaussian - A mutation operator that adds a unit Gaussian distributed random value to the chosen gene. The new gene value is clipped if it falls outside of the user-specified lower or upper bounds for that gene. This mutation operator can only be used for integer and float genes.

Selection Operators --

Selection is a genetic operator that chooses a chromosome from the current generation’s population for inclusion in the next generation’s population. Before making it into the next generation’s population, selected chromosomes may undergo crossover and / or mutation (depending upon the probability of crossover and mutation) in which case the offspring chromosome(s) are actually the ones that make it into the next generation’s population.

OptiGen Library includes the following types of Selection:

Roulette - A selection operator in which the chance of a chromosome getting selected is proportional to its fitness (or rank). This is where the concept of survival of the fittest comes into play.

Tournament - A selection operator which uses roulette selection N times to produce a tournament subset of chromosomes. The best chromosome in this subset is then chosen as the selected chromosome. This method of selection applies addition selective pressure over plain roulette selection.

Top Percent - A selection operator which randomly selects a chromosome from the top N percent of the population as specified by the user.

Best - A selection operator which selects the best chromosome (as determined by fitness). If there are two (2) or more chromosomes with the same best fitness, one of them is chosen randomly.

Random - A selection operator which randomly selects a chromosome from the population.

Constraint Dominate - Solution x is said to Constrain-Dominate if any of the following conditions are true:

1) Solution x is feasible and solution y is Not.

2) Solution x and y are both feasible but solution x has a smaller constraint violation.

3) Solution x and y are feasible and solution x dominate solution y in the usual sense.

Multi-Objective Optimization --

Multi-Objective Optimization is used to search Pareto-Optimal Front or Pareto-Frontier so that none of the solutions in Pareto Frontier would be dominated by other solutions. Multi-Objective Optimization can be further classified into constrained Multi-Objective Optimization and unconstrained Multi-Objective Optimization. The implemented Multi-Objective algorithm can be both constrained and unconstrained.

Crossover operators --

Crossover is a genetic operator that combines (mates) two chromosomes (parents) to produce a new chromosome (offspring). The idea behind crossover is that the new chromosome may be better than both of the parents if it takes the best characteristics from each of the parents. Crossover occurs during evolution according to a user-definable crossover probability.

OptiGen Library includes the following types of Crossover:

One Point - A crossover operator that randomly selects a crossover point within a chromosome then interchanges the two parent chromosomes at this point to produce two new offspring.

Two Point - A crossover operator that randomly selects two crossover points within a chromosome then interchanges the two parent chromosomes between these points to produce two new offspring.

Uniform - A crossover operator that decides (with some probability - known as the mixing ratio) which parent will contribute each of the gene values in the offspring chromosomes. This allows the parent chromosomes to be mixed at the gene level rather than the segment level (as with one and two point crossover). For some problems, this additional flexibility outweighs the disadvantage of destroying building blocks.

Arithmetic - A crossover operator that linearly combines two parent chromosome vectors to produce two new offspring.

Heuristic - A crossover operator that uses the fitness values of the two parent chromosomes to determine the direction of the search.

Termination Methods --

Termination is the criterion by which the genetic algorithm decides whether to continue searching or stop the search. Each of the enabled termination criterion is checked after each generation to see if it is time to stop.

OptiGen Library includes the following types of Termination:

Generation Number - A termination method, that stops the evolution when the user-specified max number of evolutions has been run. This termination method is always active.

Evolution Time - A termination method, that stops the evolution when the elapsed evolution time exceeds the user-specified max evolution time. By default, the evolution is Not stopped until the evolution of the current generation has completed, but this behavior can be changed so that the evolution can be stopped within a generation.

Fitness Threshold - A termination method that stops the evolution when the best fitness in the current population becomes less than the user-specified fitness threshold and the objective is set to minimize the fitness. This termination method also stops the evolution when the best fitness in the current population becomes greater than the user-specified fitness threshold when the objective is to maximize the fitness.

Fitness Convergence - A termination method that stops the evolution when the fitness is deemed as converged. Two filters of different lengths are used to smooth the best fitness across the generations. When the smoothed best fitness from the long filter is less than a user-specified percentage away from the smoothed best fitness from the short filter, the fitness is deemed as converged and the evolution terminates.

Population Convergence - A termination method that stops the evolution when the population is deemed as converged. The population is deemed as converged when the average fitness across the current population is less than a user-specified percentage away from the best fitness of the current population.

Gene Convergence - A termination method that stops the evolution when a user-specified percentage of the genes that make up a chromosome are deemed as converged. A gene is deemed as converged when the average value of that gene across all of the chromosomes in the current population is less than a user-specified percentage away from the maximum gene value across the chromosomes.

HyperVolume Convergence - HyperVolume Convergence is a termination method for Multi-Objective Optimization in which the optimal solution set is measured by HyperVolume of the Pareto-Optimal Front. Evolution is stopped when the HyperVolume stabilizes.

Greedy Search & Back Elimination - Greedy Search is a termination method for AttributeSelection. When the Greedy Search algorithm is used, the evolution terminates immediately when adding a single input to the previous input set does Not improve the fitness.

When Back Elimination is used, the evolution terminates when removing a single input from the previous input collection leads to a worse fitness. A variation of the Greedy Search and Back Elimination is also implemented that keeps an elite pool with the size defined as EliteSize. When all solutions in the elite pool are checked using the above criteria, the search is terminated.

System Requirements

The OptiGen Library is available in three (3) different versions, each of which includes support for 32-bit and 64-bit operating systems:

1) OptiGen Library for C++ is a C++ library compiled for use from Visual C++ versions VC6, VS2003, VS2005, VS2008, and VS2010 Beta 2.

2) OptiGen Library for .NET is a .NET component using .NET Framework 3.5.

3) OptiGen Library for COM is an ActiveX component which can be used from languages capable of calling ActiveX components, such as Visual Basic and VBA in Microsoft Office products.

Contact manufacturer for further detail.

Manufacturer

Manufacturer Web Site NeuroDimension, Inc.

Price Contact manufacturer.

G6G Abstract Number 20039R

G6G Manufacturer Number 101916