The fitness function serves as the primary mechanism linking the Genetic Algorithm to the real-world problem it is solving. It acts as the “environment” that evaluates each candidate solution, determining which individuals are “fit” and thus more likely to survive, reproduce, and pass their genetic material to the next generation. It is the sole guide for the evolutionary search.

The fitness function is a procedure that takes a candidate solution (a chromosome) as input and returns a single numerical value—a quantitative measure of that solution’s suitability.

Characteristics of a Fitness Function

An effective fitness function should possess two essential characteristics:

• It must be fast to compute. The fitness of every individual is calculated in every generation, so a slow function can render the entire GA process impractically slow.
• It must quantitatively measure the fitness of a solution, providing a clear, numerical basis for comparing different candidate solutions.

While the fitness function and the objective function are often the same, they can differ. For complex problems with multiple objectives or constraints, a designer might create a custom fitness function that combines these factors into a single score. In cases where direct calculation is computationally prohibitive, fitness approximation techniques may be used to estimate a solution’s quality.

Example: Fitness Calculation for the 0/1 Knapsack Problem

Let’s consider the 0/1 Knapsack problem, where a solution is represented by a binary string. A simple sum of profits for picked items is insufficient, as it does not account for the knapsack’s weight constraint. A robust fitness function must handle constraint violations. One common approach is to apply a penalty:

1. Input: A binary chromosome (e.g., [1, 0, 1, 0, …]).
2. Process: The function calculates the total profit and total weight of all items marked with a 1.
3. Calculation:
   • If the total weight is within the knapsack’s capacity, the fitness is equal to the total profit.
   • If the total weight exceeds the capacity, the fitness is the total profit minus a significant penalty. The penalty is often proportional to how much the weight limit was exceeded, ensuring that infeasible solutions are always less fit than feasible ones.
4. Output: The final calculated fitness value.

Once every individual in the population has been assigned a fitness score, the GA can proceed to the next crucial step: selecting the best individuals to serve as parents for the next generation.