Optimizes a user defined fitness function using a tailored genetic algorithm.

The type double function is imsls_d_genetic_algorithm.

Function imsls_f_genetic_algorithm optimizes a user defined fitness function by evolving an initial population using a tailored genetic algorithm that searches for the fittest individual. It returns a pointer to a clone of the fittest individual in the last generation. Memory allocated to this data structure can be released using imsls_f_ga_free_individual.

Genetic algorithms search for the optimum individual in a population. This is defined as the individual with the highest fitness. Function imsls_f_genetic_algorithm returns the fittest individual in the last generation. Mathematically, this is equivalent to finding the values of the phenotypes that maximize a user provided fitness function. Although there are no requirements that the fitness function be non-negative, in general, convergence to optimum fitness is faster when values of the fitness function are non-negative. Constraints can be applied by incorporating a penalty function within the fitness calculation. Phenotypes can consist of any combination of nominal, binary, integer and real values. Integer and real values must be encoded into a binary representation. This procedure provides for either Base-2 or Gray encoding. However, users can supply other encodings within the fitness function.

The function imsls_f_genetic_algorithm uses the population data structure and fitness with simulated genetic processes of reproduction to search for the optimum individual, i.e. settings of phenotype values. Genetic algorithms have been successfully applied to a wide variety of optimization and search problems, see Holland (1975) and Goldberg (1985).

There are many refinements to the basic genetic algorithm originally described by Holland (1975). His basic algorithm begins with an initial population of n individuals, a fitness function, and probabilities for crossover and mutation of p_xover and p_mutation respectively. The initial population is transformed from one generation to the next using the following steps:

By default Holland’s approach to these steps are used. However, many variations of these can be selected using optional arguments.

The initial population can be generated automatically using imsls_f_ga_random population or it can be created by first creating individuals using imsls_f_ga_individual and then a population for those individuals using imsls_f_ga_population.

By default Holland’s roulette wheel with replacement is used for selecting the mating pool. The optional argument IMSLS_SELECTION_MODEL allows users to select alternate selection methods including remainder, tournament and stochastic universal selection. Default crossover and mutation probabilities are p_xover= 0.8 and p_mutation= 0.005. These defaults can be changed using the optional arguments IMSLS_CROSSOVER_PROB and IMSLS_MUTATION_PROB.

In the original algorithm only a single crossover point was randomly selected. The optional argument IMSLS_CROSSOVERS allows users to designate any number of crossover points.

Standard crossover proceeds by combining the genes from both parents in the order found in those parents. Inversion crossover inverts this order for one of the parents. Inversion crossover is selected using the optional argument IMSLS_INVERT_CROSSOVER.

For certain problems, such as the traveling salesman problem, standard crossover can produce infeasible individuals. One approach is to assign zero fitness to those solutions, but this can be very inefficient. Partially matched crossover is an approach that ensures individuals are feasible for a certain class of problems. If the problem is best represented using nominal phenotypes with values
0, 1, …, n_nominal-1 where all values must appear once and only once in the chromosome, then partially matched crossover preserves that condition. Partially matched crossover is selected using the optional argument IMSLS_PMX_CROSSOVER.

One issue with some applications of genetic algorithms is premature convergence or convergence to false local solutions. This can occur when dominant individuals within early generations take over the population prematurely reducing population diversity. One approach to this problem is fitness scaling. This implementation allows users to use either linear or sigma fitness scaling. By default, no scaling is used. However, the optional arguments IMSLS_LINEAR_SCALING and IMSLS_SIGMA_SCALING allow users to have fitness values automatically scaled before selection.

The genetic algorithm is stopped when any one of the stopping criteria is met. The algorithm is stopped when the number of generations exceeds max_generations or when the maximum fitness exceeds max_fitness. By default max_generations= 100; this can be changed using IMSLS_MAX_GENERATIONS. By default max_fitness is imsls_f_machine(7); this can be changed using IMSLS_MAX_FITNESS.

On some platforms, imsls_f_genetic_algorithm can evaluate the user-supplied function fitness in parallel. This is done only if the function imsls_omp_options is called to flag user-defined functions as thread-safe. A function is thread-safe if there are no dependencies between calls. Such dependencies are usually the result of writing to global or static variables.

De Jong (1975) examined the performance of a genetic algorithm for finding the maximum of a multivariate function. This is an example of optimizing a variation of De Jong’s R2 function:

where

Since there were only two real phenotypes and the function is easily calculated, the phenotypes were encoded using discretization with 65,536 values over the interval [-2.048, 2.048]. By default, encoding and decoding is done within imsls_f_genetic_algorithm. This allows the fitness function to calculate individual fitness using the real phenotypes instead of the chromosome. Both the chromosome and its phenotype representation are available within the Imsls_f_individual data structure argument.

The default selection algorithm IMSLS_ROULETTE_WITH was used, but the number of crossover probability was set to 0.6. The genetic algorithm was more efficient using a lower crossover probability and Gray encoding instead of the defaults 0.7 and Base-2 encoding. Each generation consisted of 40 individuals.

In this example, the print level is set to IMSLS_FINAL in order to print the optimum solution. The generation statistics are requested using the IMSLS_GENERATIONS_STATS option, and the last population is requested using the IMSLS_LAST_GENERATION option.

Although the maximum number of generations is set to 100 using the IMSLS_GENERATIONS option, the genetic algorithm halted after 26 generations when the maximum population fitness exceeded 3999.999.

The traveling salesman problem creates a problem for traditional crossover. In this problem, the objective is to find the shortest route while traveling to each city once. In this example, there are eight cities, labeled using the letters a-h, with distances ranging from 17 to 113 miles.

Traditional crossover would create unfeasible routes; that is some routes after crossover would not visit every city once. Some would not be visited and others would be visited more than once.

Partially matched crossover (PMX) preserves the feasibility of a route. In the general sense, PMX assumes that the nominal phenotypes consists of a string of numbers from zero to n_nominal-1, with each number appearing once and only once in that string. Partially matched crossover uses two crossover points within the nominal portion of the chromosome and swaps the middle segment between the parents. The first and third segments are manipulated to ensure the resulting offspring is feasible.

This program produced the following output. Since the print level was set to IMSLS_FINAL, the optimum solution was printed. The generation statistics were requested using the IMSLS_GENERATIONS_STATS option, and the last population was requested using the IMSLS_LAST_GENERATION option.

The maximum number of generations was set to 10. The genetic algorithm found the optimum route after evaluating the fitness of 550 routes in 10 generations. Generation zero is the initial generation provided to the algorithm and is not counted towards the maximum generation count.

This example uses the N-Queens problem to illustrate the use of a fitness function with parameters in implementing a genetic algorithm. The N-Queens problem is derived from chess. The genetic algorithm provides an efficient search for a valid solution. For this problem the chess board consists of N rows and N columns. The objective is to place N queens on this board with no conflicts. A conflict occurs when one queen can move and capture another. Since queens can move diagonally, vertically and horizontally this problem is challenging when N becomes large.

One solution for N = 4 is displayed in the following table. A valid solution must place every queen in a different row and column. The problem is to ensure the queens are not in conflict because of lying on the same diagonal.

Similar to the traveling salesman problem, the N-Queens problem can be expressed using N nominal phenotypes with values 0, 1, …, N-1. The value of the i-th phenotype represents the row number for the queen in the i-th column. This ensures that any arrangement of the phenotype values represents a board with N queens, each placed in a different row and column.

The solution for N queens displayed above can be represented by the phenotype values {1, 3, 0, 2}. The search looks for arrangements that also do not place queens on the same diagonal. Two queens fall on the same diagonal if the absolute value of the difference between their row numbers equals the absolute value of the difference between their column numbers.

This example uses this representation with a fitness function equal to (N – C) where C equals the number of conflict among the queens. With this fitness, a solution to the N-Queens has a fitness of N.

This program produced the following solution to the N-Queens problem with N=50 queens. Notice that some of the minimum fitness values are negative. This alters the random selection of the fittest parents, but if these values are few and small, then the effect is not enough to halt the genetic algorithm.

For 50 queens there are over 1064 ways of placing queens ensuring each is in its own row and column. An exhaustive search of these possible solutions to find a arrangement without diagonal conflicts would be time consuming. The genetic algorithm search found a solution in only 568 generations, requiring 284,500 function evaluations.