Archive-Based Micro Genetic Technique

The Archive-based Micro Genetic Algorithm (AMGA) is an evolutionary optimization algorithm that relies on genetic variation operators for creating new solutions. The generation scheme deployed in AMGA can be classified as generational since, during a particular iteration (generation), only solutions created before that iteration take part in the selection process. However, the algorithm generates a very small number of new solutions (it can work with just two solutions per iteration) at every iteration. Therefore, it can also be classified as an almost steady-state genetic algorithm. This attribute helps the algorithm achieve faster convergence than most generational genetic algorithms.

AMGA maintains an external archive of good solutions obtained. The external archive is updated at each iteration and provides the information about the search history of the algorithm, which is then exploited during the selection process to create the parent population.

AMGA owes its name to the fact that it works with a very small population size and uses an archive to maintain its search history. It is recommended that you use a large size for the archive (the recommended value is 500). The best results are obtained if the size of the archive is the same as the number of function evaluations allowed (i.e., the algorithm stores its complete search history). The size of the archive determines the computational complexity of the proposed algorithm; however, for computationally expensive optimization problems, the actual time taken by the algorithm is negligible. The parent population is updated using the archive, and binary tournament selection is performed on the parent population (for creating the mating population). The design of the algorithm is independent of the encoding of the variables; therefore, AMGA can work with almost any kind of encoding (so long as suitable genetic variation operators are provided to the algorithm). The algorithm uses the concept of Pareto ranking borrowed from NSGA-II and is based on a two-tier fitness mechanism. The basic flowchart of the algorithm is as follows:

  1. Begin operations.
  2. Generate the initial population.
  3. Evaluate the initial population.
  4. Update the archive (using the initial population).
  5. Repeat the following steps...
    1. Create the parent population from the archive.
    2. Create the mating pool from the parent population.
    3. Create the offspring population from the mating pool.
    4. Evaluate the offspring population.
    5. Update the archive (using the offspring population).
  6. ...until termination is reached.
  7. Report the desired number of solutions from the archive.
  8. End operations.

The flowchart for AMGA can also be perceived as a combination of ideas borrowed from NSGA-II, SPEA2, and FastPGA. The parent population is created from the archive using an environmental selection-based strategy borrowed from SPEA2. However, the size of the parent population is influenced from the dynamic population sizing approach used in the FastPGA. The creation of the mating pool uses binary tournament selection and is the same as used in NSGA-II. Any genetic variation operators can be used to create the off-spring population. The strategy used to update the elite population relies on the domination level, diversity of the solution, and the current size of the archive, and it is based on the non-dominated sorting concept borrowed from NSGA-II.

Both SPEA2 and NSGA-II can be emulated by AMGA by adjusting various parameters (and by choosing suitable diversity preservation operators). To reduce the number of function evaluations per generation, AMGA uses a small size for the mating pool. During the initial stages of the search, most solutions in the archive (or parent population) are dominated and only the best and diverse solutions are included in the mating pool. This action reduces the number of function evaluations required to reach the Pareto-optimal front. Once a small set of solutions near the Pareto-optimal front is obtained, new solutions are created from the most diverse parent solutions to fill the gaps in the Pareto-optimal front. Using an external archive that stores a large number of solutions (the recommended value is 500) provides useful information about the search space. It also tends to generate a large number of Pareto points at the end of the simulation. AMGA uses efficient diversity preservation techniques. For the case of two objectives, AMGA uses the crowding distance (borrowed from NSGA-II). For the case of more than two objectives, AMGA relies on Efficient Nearest Neighbor Search (used in vector quantization). The genetic variation operators used by AMGA are Simulated Binary Crossover (SBX) and polynomial mutation. AMGA is designed to work with real variables and constrained multi-objective problems, which cannot be solved by most gradient-based methods. It does not rely on weights to couple all the objectives, and it uses a penalty parameter-less method to handle the constraints.