Recently I presented a conference paper in ISCC 2021, it is on the Service Function Chain Embedding problem; find it in IEEEexplore or here. The problem is handled efficiently using a genetic algorithm. Here are a few empirical remarks about how to design efficient and effective GAs which I gained from working on this paper.
The issue with designing GAs is that their operation is not sufficiently explained and the efficiency of any GA design is case dependent. Any innovation applied on a GA implementation may work well on a problem and fail on many others.
At first there is the population generation. The objective of a GA is to approximate the goal solution of a problem among all the possible solutions in the solution space of the problem. So, from the members of the population we have to be able to generate the goal solution by applying the genetic procedures on the population. Then the initial population will have to be directed to the part of the solution space that contains the goal and for this reason we have examine whether it is more efficient to generate the population heuristically instead of a randomized generation which is the common practice.
Preserving original chromosomes and best solutions. The procedures of crossover and mutation were originally designed so as to affect the members of the initial population. During crossover, the parent chromosomes generate offspring that may replace them in the population. Also during mutation the genotype of a chromosome is affected and this results the replacement of the original solution that the chromosome represents by a new solution that the mutated chromosome represents. Moreover, the randomized operations of the GA may reject or replace a good solution.
Having these in mind, my proposition is to preserve the best solution generated during a generation regardless of how the new population will be formed. Also the generation of new offspring and new mutated chromosomes should not replace the previous ones. Add the new chromosomes in the population along with the older ones and let the selection procedure decide which will survive in the next generation.
Premature convergence. There are many reasons for the premature convergence of the population in an undesirable solution. One technique of limiting this phenomenon and achieving a more stable behavior for the algorithm is the multiple execution of the algorithm and the further procedure of all the outputs. The outputted solutions from all the executions maybe combined so as to generate a probably better solution (this was my approach) or you may just pick the best one for the final output.
Parameter tuning. GAs are multiparametric algorithms and the values of these parameters determine their performance; the parameters are the number of generations, population size, crossover and mutation probabilities. There are two ways to determine the best valuations for these parameters. Either by extensive experimentation or by using an optimization procedure like the one described in my earlier post.
