{"id":3390,"date":"2025-06-29T12:07:34","date_gmt":"2025-06-29T10:07:34","guid":{"rendered":"https:\/\/neuraldesigner.com\/blog\/genetic_algorithms_for_feature_selection\/"},"modified":"2025-12-16T13:00:28","modified_gmt":"2025-12-16T12:00:28","slug":"genetic_algorithms_for_feature_selection","status":"publish","type":"blog","link":"https:\/\/www.neuraldesigner.com\/blog\/genetic_algorithms_for_feature_selection\/","title":{"rendered":"Genetic algorithms for feature selection in machine learning"},"content":{"rendered":"\t\t
\n\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

Many typical machine learning applications, from customer targeting<\/a> to\u00a0medical diagnosis<\/a>, arise from complex relationships between features (also called input variables<\/a>\u00a0or characteristics).\u00a0Feature selection or <\/span>input selection<\/a> algorithms (such as genetic algorithms) search for the most relevant inputs for a <\/span>model<\/a>.<\/span><\/p>

Feature selection techniques help identify and remove unneeded, irrelevant, and redundant features. Indeed, those variables do not contribute to or decrease the accuracy of the predictive model.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t

\n\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t

Contents<\/h3>
  1. Feature selection<\/a>.<\/li>
  2. Genetic algorithms<\/a>.<\/li>
  3. Initialization operator<\/a>.<\/li>
  4. Fitness assignment operator<\/a>.<\/li>
  5. Selection operator<\/a>.<\/li>
  6. Crossover operator<\/a>.<\/li>
  7. Mutation operator<\/a>.<\/li>
  8. Process and results<\/a>.<\/li>
  9. Conclusions<\/a>.<\/li><\/ol>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t
    \n\t\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\t

    Feature selection<\/h2>

    Mathematically, we formulate inputs selection<\/a> as a combinatorial optimization problem.<\/p>

    The objective function<\/em> is the predictive model’s generalization performance, represented by the error term<\/a> on the selection instances<\/a> of a\u00a0data set<\/a>.<\/p>

    The design variables<\/em> are the inclusion (1) or the exclusion (0) of the input variables<\/a>\u00a0in the neural network<\/a>.<\/p>

    A wide selection of features would evaluate 2N<\/sup> different combinations, where N is the number of features.<\/p>

    This process requires lots of computational work, and it becomes impracticable if the number of features is significant.
    Therefore, we need intelligent methods to select features in practice.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t

    \n\t\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\t

    Genetic algorithms<\/h2>

    One of the most advanced algorithms for feature selection<\/a>\u00a0is the genetic algorithm<\/a>.<\/p>

    The genetic algorithm is a stochastic method for function optimization based on natural genetics and biological evolution.<\/p>

    In nature, organisms’ genes tend to evolve over successive generations to better adapt to the environment. The genetic algorithm is a heuristic optimization method inspired by the procedures of natural evolution.<\/p>

    Genetic algorithms operate on a population of individuals to produce better and better approximations.<\/p>

    The algorithm creates a new population every generation by selecting individuals according to their fitness level in the problem domain. These individuals are then recombined together using operators borrowed from natural genetics. The offspring might also undergo mutation.<\/p>

    A state diagram for the feature selection<\/a> process with the genetic algorithm is depicted next.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t

    \n\t\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\t

    \"Genetic<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t

    \n\t\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\t

    This process leads to the evolution of populations better suited to their environment than the individuals who originated it.<\/p>

    In our case, each individual in the population represents a\u00a0neural network<\/a>.<\/p>

    Genes here are binary values, representing the inclusion or not of particular features in the model. The number of genes is the total number of input variables<\/a> in the\u00a0data set<\/a>.<\/p>

    The number of individuals, or population size<\/em>, must be chosen for each application. The default value for the population size is 10 N, where N is the number of features. This number must be a multiple of 4.<\/p>

    Next, we describe the operators and the corresponding parameters used by the genetic algorithm in detail.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t

    \n\t\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\t

    1. Initialization operator<\/h2>

    The first step is to create and initialize the individuals in the population. Since the genetic algorithm is a stochastic optimization method, we randomly initialize the genes of all individuals.<\/p>

    To illustrate this operator, consider a predictive model represented by a neural network<\/a>\u00a0with 6 possible features. If we generate four individuals, we have four different neural networks with random features.<\/p>

    The next figure illustrates this population.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t

    \n\t\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\t

    \"Genetic<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t

    \n\t\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\t

    As we can see, each individual is represented by 6 binary genes. Each positive gen means that the corresponding feature is included in the\u00a0neural network<\/a>.<\/p>

    Another way to activate columns is according to their correlation with the target variable. In this way, we create a probability
    distribution. This distribution is similar to the one created in the selection operator.<\/p>

    This initialization operator causes variables more likely to be the correct ones to be activated at first.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t

    \n\t\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\t

    2. Fitness assignment operator<\/h2>

    After the initialization<\/a>, we need to assign a fitness value to each population member.<\/p>

    We train each neural network<\/a>\u00a0with the\u00a0training instances<\/a> and then evaluate their\u00a0error<\/a> with the\u00a0selection instances<\/a>.<\/p>

    A significant selection error means low fitness. Individuals with higher fitness or lesser selection error are more likely to be selected for recombination.<\/p>

    The most used method for fitness assignment is known as a rank-based fitness assignment<\/em>.<\/p>

    With this method, the\u00a0selection errors<\/a>\u00a0of all the individuals are sorted.<\/p>

    Then, the fitness assigned to each individual only depends on its position in the individual’s rank and not on the actual selection error.<\/p>

    The fitness value assigned to each individual with the rank-based method is:<\/p>

    $$\\Phi(i) = R(i) \\qquad where \\quad i = 1,…,N.$$<\/p>

    Here, the parameter R(i) is the rank of individual i. We can then calculate the probability of being selected based on the fitness assigned to each individual. The probability of each individual to be selected it can be calculated with the following expression:<\/p>

    $$\\displaystyle P_i=\\dfrac{R(i)}{\\sum_{j=1}^N j}$$<\/p>

    The following table depicts the selection error, the rank, and the corresponding probability of being selected (fitness) of each individual in our example.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t

    \n\t\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\t

    \u00a0<\/p>
    \u00a0<\/th>Selection error<\/th>Rank<\/th>Probability<\/th><\/tr>
    Individual 1<\/th>0.9<\/td>1<\/td>0.1<\/td><\/tr>
    Individual 2<\/th>0.6<\/td>3<\/td>0.3<\/td><\/tr>
    Individual 3<\/th>0.7<\/td>2<\/td>0.2<\/td><\/tr>
    Individual 4<\/th>0.5<\/td>4<\/td>0.4<\/td><\/tr><\/tbody><\/table>

    \u00a0<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t

    \n\t\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\t

    We can plot the above fitness values in a pie chart. Here, the area for each individual in the pie is proportional to its fitness.
    The following picture shows the fitness pie.<\/p>

    \"Genetic<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t

    \n\t\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\t

    As we can see, the fittest individual (#4) is the one who has the most significant area (40%). Conversely, the least fitted individual (#1) has the smallest area (10%).<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t

    \n\t\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\t
    <\/section>

    3. Selection operator<\/h2>

    After a fitness assignment<\/a> has been performed, the selection operator chooses the individuals that recombine for the next generation.<\/p>

    The individuals most likely to survive are those more fitted to the environment. Therefore, the selection operator selects the individuals according to their fitness level. The number of selected individuals is N\/2, being N the population size.<\/p>

    Elitist selection<\/em> makes the fittest individuals survive directly for the next generation. The elitism size controls the number of directly selected individuals, and it is usually set to a small value (1,2,…).<\/p>

    One of the most used selection methods is the roulette wheel<\/em>. This method places all the individuals on a roulette, with areas proportional to their fitness, as we saw above. Then, it turns the roulette and selects the individuals at random. The corresponding individual is selected for recombination.<\/p>

    The following figure illustrates the selection process for our example.<\/p>

    \"Genetic<\/p><\/section>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t

    \n\t\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\t

    In this case,\u00a0neural network<\/a>\u00a0#4 has been selected by elitism, and #3 has been selected by the roulette wheel. Note that, although individual #2 has more fitness than #3, it has not been selected due to the stochastic nature of the genetic algorithm.<\/p>

    Here, the number of selected individuals is half of the population size.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t

    \n\t\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\t

    4. Crossover operator<\/h3><\/section>

    Once the selection operator<\/a> has chosen half of the population, the crossover operator recombines the selected individuals to generate a new population.<\/p>

    This operator picks two individuals randomly from the previously selected and combines their features to get four offspring for the new population until the new population is the same size as the old one.<\/p>

    The uniform crossover<\/em> method decides whether each offspring’s features come from one parent or another.<\/p>

    The following figure illustrates the uniform crossover method for our example.<\/p>

    \"Genetic<\/p><\/section>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t

    \n\t\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\t

    Here we have generated four offspring from two parents. Some features of each\u00a0neural network<\/a> correspond to one ancestor and others to the other.<\/p>

    In this case, the parents are directly replaced by the offspring. In this way, the population size remains constant.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t

    \n\t\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\t

    5. Mutation operator<\/h3><\/section>

    The crossover operator<\/a> can generate offspring that are very similar to the parents. This might cause a new generation with low diversity.<\/p>

    The mutation operator solves this problem by randomly changing the value of some features in the offspring.<\/p>

    We generate a random number between 0 and 1 to decide if a feature is mutated. If the random number is lower than the mutation rate value, the operator flips that variable.<\/p>

    A standard value for the mutation rate is $dfrac{1}{m}$, where $m$ is the number of features. We mutate one feature of each individual (statistically) with that value.<\/p>

    The following image shows the mutation of one offspring of the new generation.<\/p>

    \"Genetic<\/p><\/section>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t

    \n\t\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\t

    As we can see, the fourth input of the\u00a0neural network<\/a>\u00a0has been mutated.<\/p>

    At this point, we have a new population.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t

    \n\t\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\t

    Process and results<\/h3><\/section>

    The whole\u00a0fitness assignment<\/a>,\u00a0selection<\/a>,\u00a0recombination<\/a>, and mutation<\/a>\u00a0process is repeated until a stopping criterion is satisfied.
    Each generation will likely adapt more to the environment than the old one.<\/p>

    This chart shows the typical behavior of the mean selection error<\/a>\u00a0and the best selection error<\/a>\u00a0through generations. The example used is Breast Cancer Mortality example<\/a> available in the blog.<\/p>

    \"Genetic<\/p><\/section>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t

    \n\t\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\t

    As we can see, the mean selection error at each generation converges to a minimum value.<\/p>

    The solution to this process is the best individual ever. This corresponds to the\u00a0neural network<\/a>\u00a0with the smallest\u00a0selection error<\/a>\u00a0among all those we have analyzed.<\/p>

    In our example, the best individual is the following:<\/p>

    \"Genetic<\/p>

    The above\u00a0neural network<\/a>\u00a0is the selected one for our application.<\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t

    \n\t\t\t\t\t
    \n\t\t\t\t
    \n\t\t\t\t\t\t\t\t\t

    Conclusions<\/h3><\/section>

    Input selection<\/a>\u00a0is becoming a critical topic in machine learning. Many data sets<\/a> contain many features<\/a>, so we need to select the most useful ones to be included in the neural network<\/a>.<\/p>

    One of the most advanced methods to do that is the\u00a0genetic algorithm<\/a>.<\/p>

    Some advantages of genetic algorithms are the following:<\/p>