Opstee Optimizer^® Genetic Algorithm

Genetic algorithms are modeled after the biological processes of natural selection, and have been used to find good solutions to problems that have many many possible solutions. For example, in the classic Traveling Salesperson Problem, the challenge is to find the shortest distance that would be required for a salesperson to visit each city in her territory and return home. Using the textbook example, we'll assume that each city is connected to every other city. A 10 city tour has about 181,000 possible solutions, and a 20 city tour has about 10,000,000,000,000,000 (10¹⁶) solutions! Instead of testing each possible route (the brute force approach), which becomes computationally impossible for even modestly large numbers of cities, genetic algorithms allow you to create a number of random routes (the parent set), select the shortest routes from that random set, and then cross-over the parents to produce a set of child routes (Figure 1). The shortest routes are then selected from this new pool of parent and child routes, and the process is repeated until the user stops the process or the algorithm converges on a shortest route.

Figure 1: Cross-over works by combining parts of one solution with a parts of another to create two new solutions.

Why does this work? Consider that one route may contain a partial route within it that is a very good solution for visiting a particular subset of cities whereas another route may contain partial route within it that is a very good solution for visiting a different subset of cities. By crossing-over these two routes, one of the offspring will now contain both of these short routes, and will consequently be shorter overall than either of the parent routes.

We designed the Optsee Optimizer™ genetic algorithm specifically to find optimized sets of choices based on your constraints. It works by creating an initial set of parent portfolios that meet your constraints, and then combining these parent portfolios in such a way to create a generation of child portfolios. The best combined set of parent and child portfolios are then selected and used to create the next generation of portfolios. The Optsee Optimizer™ also uses some additional processing to improve individual portfolios during the optimization process. This process continues until the user-specified optimization parameters are satisfied and/or the process converges to a single optimized result (i.e., the identical result is obtained after 3 or more generations).

Steps 1 to 4 below illustrate how this works:

Step 1: An initial set of random portfolios is created to form the parent population. Portfolios that do not meet the constraint criteria are eliminated.

Step 2: Pairs of individual portfolios in the parent population are crossed-over to create new portfolios. The new population now consists of both the original parent portfolios and the new child portfolios. Child portfolios that do not meet the constraint criteria are eliminated.

Step 3: The population is ranked by fitness (highest optimized parameter).

Step 4: The least fit portfolios are eliminated, and the remaining population becomes the parent population for the next generation.

It is important to note that because a genetic algorithm is based initially on random inputs, it will usually find different optimized solutions each time it is run depending on both the random inputs and the optimization parameters. Even optimizations performed using identical parameters will often converge on a different result. Thus, while the optimizer has been designed to find good outcomes, there is no way to tell if it has found a single "best" outcome. This is why it is useful to initially run the optimizer several times using small numbers of parents (1000 - 10,000) to get a feel for how difficult it is to find portfolios that meet your constraints. The more difficult it is to find portfolios that meet your constraints, the more parents you should use in your optimization.

The Optsee Optimizer™ form (Figure 2) lets you easily set the parameters for the optimization such as the initial number of parents (up to 250,000), the number of generations to test (up to 100), the number of consecutive repeating identical results that indicate the optimizer has converged on a final result (up to 25), and the percentage of mutations used in each generation (up to 45%).

Figure 2: The Optsee Optimizer™ Form: This example is set to run 5,000 parents for 12 generations and add 15% mutations after each generation. The optimization will stop after 5 consecutive identical results indicate convergence. The portfolio is being optimized against 4 constraints including maximum (not more than) average time to market and minimum (not less than) reward.

Mutations are new portfolios that are created using the same random input algorithm as the initial parents, and are used to add diversity to the population, and prevent premature convergence before a higher optimization is found. In the illustrations above, the mutated portfolios would be added after cross-over has finished (Step 2), but before the population is ranked by fitness (Step 3). This ensures the survival of only mutations that meet the minimum fitness criteria of that generation.

Constraints can be based on the sum total of a particular attribute, such as the total cost for all projects, or on an average of the attribute (=sum total/number of choices) , such as the average number of employees per project. Constraints are set as not-to-exceed (maximum constraint) by default. You can also set them to be not-less-than (minimum constraint).