Neighborhood Cultivation Genetic Algorithm (NCGA)

In the Neighborhood Cultivation Genetic Algorithm (NCGA) technique, each objective parameter is treated separately. Standard genetic operation of mutation and crossover are performed on the designs. The crossover process is based on the “neighborhood cultivation” mechanism, where the crossover is performed mostly between individuals with values close to one of the objectives. By the end of the optimization run, a pareto set is constructed where each design has the “best” combination of objective values, and improving one objective is impossible without sacrificing one or more of the other objectives.

Related Topics
Optimization References

The Vector Evaluated Genetic Algorithm (VEGA), proposed by J. D. Schaffer (1985), has been perceived as the pioneering research of the application of Genetic Algorithms (GA) to multi-objective optimization problems. However, in this early multi-objective Genetic Algorithm, the fundamental algorithm was a simple expansion of the single-objective Genetic Algorithm. The idea of Pareto optimality was not explicitly included.

The first multi-objective Genetic Algorithm that adopted the idea of Pareto optimality explicitly was the Multi-Objective Genetic Algorithm (MOGA), proposed by C. M. Fonseca and P. J. Fleming (1993). In the remainder of this section, this algorithm is referred to as “Fonseca’s MOGA,” to distinguish it from the generic designation of Multi-Objective Genetic Algorithm.

In Fonseca’s MOGA the dominating relation of solutions is defined by means of “Pareto-ranking,” which is an ordering that is based on Pareto optimality. To avoid solutions that create a narrow range in the objective space, it performs niching based on sharing distance, giving lower fitness to a solution close to other solutions.

Although Fonseca’s MOGA was the first multi-objective Genetic Algorithm that adopted the idea of Pareto optimality explicitly, problems were reported. In the calculation of fitness with niching, as mentioned previously, the algorithm sometimes generated irrational fitness values, such as solutions on the Pareto front that had lower fitness because of niching.

Non-dominated Sorting Genetic Algorithm (NSGA), proposed by N. Srinivas and K. Deb (1994), resolved the problems found in MOGA and was based on Pareto optimality. The main features in NSGA were as follows:

  • ranks solutions with non-dominated sorting, and

  • ensures that solutions in lower rank have lower fitness.

This means that solutions on the Pareto front will have the highest fitness value. It is similar to Fonseca’s MOGA in that it performs niching based on the sharing distance.

The Strength Pareto Evolutionarily Algorithm (SPEA), proposed by E. Zitzler and L.Thiele (1999), was a pioneer of the current multi-objective Genetic Algorithms. Elitism of the single objective Genetic Algorithms was initially introduced in the multi-objective Genetic Algorithms with NCGA. In multi-objective Genetic Algorithms since SPEA, whole populations consist of two sub-populations. One is for preserving elite individuals, while the other is for performing genetic operators to generate children for optimum solution search. The latter population has the same role as the population in MOGA and NSGA, which were proposed in the mid-1990s. The former population was called the “Pareto Archive” or “Archive.” SPEA also introduced the original mechanism that could keep diversity and extension of solutions archived. This mechanism was called “clustering.” It ranks solutions based on both Pareto optimality and the idea that crowding level and ranking value are equal to fitness in SPEA.

The Neighborhood Cultivation Genetic Algorithm (NCGA) is based on SPEA2, and a good way to examine NCGA is to compare it to SPEA2. NCGA differs from SPEA2 in the following ways:

  • introduces the idea of “neighborhood cultivation” in crossover, and

  • modifies the selection method of extracting Q t+1 from P t+1

The term “neighborhood cultivation” means that the individuals to be crossed over must be within a certain range of the objective space. The idea comes from research for improving the searching performance of the multi-objective Genetic Algorithm by means of dividing populations into sub-populations and sending each sub-population onto distributed CPUs in a network environment. In the divided population of such multi-objective Genetic Algorithms, a division is decided by one of the element objectives. Genetic operators are applied in each divided sub-population. Consequently, in the divided model, crossover operations are performed between neighbors, which are grouped by the division based on an objective. From a series of numeric research on this divided population model, it was concluded that crossover with similar individuals would produce better results than that of greatly differing individuals. The “neighborhood cultivation” is the crossover operation that performs the crossover with similar individuals. When the number of objective functions is p, individuals are sorted according to one of those objective functions, and crossover is performed by two adjoined pairs. The objective function of each generation that is used for sorting is changed. However, with complete sorting there is a danger of loss of diversity in the solution. Therefore, around 5% of the disturbance is applied on sorted individuals before the crossover operation.

The method of selecting the search population Q(t+1) from the Pareto archive P(t+1) in NCGA involves copying the archive P(t+1) of N individuals onto Q. On the other hand, the Non-dominated Sorting Genetic Algorithm (NSGA-II) and SPEA2 select individuals by binary tournament selection with repetition. For more information about these two algorithms, see Non-dominated Sorting Genetic Algorithm (NSGA-II). This difference relates to the standpoint of whether to put the selection pressure onto elites. The disadvantage of this option is that the selection pressure can result in lost diversity and lead to a danger of being trapped in a local optimum.

A research group tested NCGA and compared it with NSGA-II and SPEA2 with numerous test functions, including an element knapsack problem. They concluded that, when the following are true, NCGA provides better results than NSGA-II or SPEA2:

  • when objective functions have a multiple peak landscape, and

  • when the number of design variables is large (0).