A small outlook at genetic algorithms

Genetic algorithms are a type of feature optimization algorithms. They are designed to either minimize or maximize the fitness of something of our choice.

Genetic algorithms are particularly good at solving problems of factorial complexity, like the shipping problem or other optimization problems in particular.

A genetic algorithm is generally composed of the following:

• a generator: it creates elements of the "population"
• a fitness function: it rates the success of an element of the population
• a crossover function: it takes 2 or more elements of the populations and creates a new element of the population
• a mutation function: it mutates randomly genes from the population

Example

In pseudocode, it would look like:

type element = array of genes
population = array of element

repeat(1000) {
    while(population.size < upper limit) {
        population << generator();
    }
    
    sort population by decreasing fitness
    
    while(population.size > lower limit) {
        pop last element of population
    }
    
    for each A and B : 2 consecutive elements of population {
        population << crossover(A, B)
    }
    
    for each A : in population {
        population << mutation(A)
    }
}

sort population by decreasing fitness

the first element of population has the best genes

Here is an implementation in C++:

struct knapsack_element {
	uint64_t weight;
	uint64_t value;
};

std::vector<knapsack_element> optimize(std::vector<knapsack_element> realm, auto knapsack_scorer) {
	constexpr size_t pop_minimum = 1000;
	constexpr size_t pop_cull_number = 750;
	constexpr size_t generation_cap = 200;
	
	std::vector<std::deque<bool>> population;
	std::random_device dev;
	std::mt19937_64 rand_impl(dev());
	const auto rand_bit = [&]() -> bool { return rand_impl() & 1; };
	const auto rand_mutate = [&]() -> bool { return std::uniform_int_distribution<int>{0, 20}(rand_impl) == 0; };
	const auto population_increment = [&]() {
		population.emplace_back();
		while (population.back().size() != realm.size()) {
			population.back().emplace_back(rand_bit());
		}
	};
	const auto make_sack = [&](const std::deque<bool>& chromosome) {
		std::vector<knapsack_element> sack;
		for(
			auto [left, right] = std::pair{chromosome.begin(), realm.begin()};
			left != chromosome.end() && right != realm.end();
			std::advance(left, 1), std::advance(right, 1)
		) {
			if(*left) {
				sack.emplace_back(*right);
			}
		}
		return sack;
	};
	const auto scorer = [&](const std::deque<bool>& chromosome) {
		return knapsack_scorer(make_sack(chromosome));
	};
	
	for(size_t cnt = 0;cnt < generation_cap;++cnt){
		// Initialize the population
		while (population.size() < pop_minimum) {
			population_increment();
		}
		
		std::ranges::sort(population, std::ranges::greater{}, scorer);
		// Check for early termination
		if(scorer(population[0]) == scorer(population[population.size()/4])) {
			break;
		}
		
		// Cull the worst fits
		if(population.size() > pop_cull_number) {
			population.resize(pop_cull_number);
		}
		
		// Reproduce
		{
			std::vector<std::deque<bool>> babies;
			for (
				auto [left, right] = std::pair{population.begin(), ++population.begin()};
				left != population.end() && right != population.end();
				std::advance(left, 2), std::advance(right, 2)
				) {
				babies.emplace_back();
				for (size_t idx = 0; idx != realm.size(); idx++) {
					if (rand_bit()) {
						babies.back().emplace_back((*left)[idx]);
					} else {
						babies.back().emplace_back((*right)[idx]);
					}
				}
			}
			std::copy(babies.begin(), babies.end(), std::back_inserter(population));
		}
		
		// Mutation phase
		for (auto &member: population) {
			if (rand_mutate()) {
				for (auto &elem: member) {
					if (rand_mutate()) {
						elem = rand_bit();
					}
				}
			}
		}
	}
	
	return make_sack(population.front());
}

Use Right-click on the image and Open the image in another tab to read more easily. Diagrams are cursed.

Here, the "chromosomes" are binary values: either we ship an item, or we do not. On
production line, for example, the chromosomes could be which machine and what time do we start the production, and the fitness function would evaluate if the production is possible (machines are not used during the same timespan) and the total time to minimize (which is like maximizing max_time - time_taken).

Depending on the type of chromosomes, the cross-over should not change, but the mutation function will change. Also, in the example above, we mutate in place, but mutating in new children tends to give better results for more sophisticated problems.

Identifying if the problem is appropriate to solve with genetic algorithms

Do not solve problems that can be solved deterministically in a reasonable amount of time. Genetic algorithms will not provide a perfect solution, but one with heuristically a good fitting to the scoring method used.

The problem needs to have:

• at least one dimension to it that never changes in size: for the shipping problem, it is the list of items that can be shipped.
• a metric that can measure gradual improvements and progress, if your success is binary, then genetic algorithms are a bad candidate
• A solution domain that is not too restrained: at least some bad solutions must be findable by random trial and error
• a representation that is not too broad in the other dimentions, that is more for having a comfortable runtime than anything else

If the solution domain is too restrained, known dumb solutions can be put in the population. These will serve as nucleation points for better solutions. This can make otherwise too restrictive solution domains solvable. For example, in the algorithm stated above, too many elements in the list of pickable elements compared to the transportable weight could make the randomness function probabilistically only make unacceptable sets by default. Adding some sets with for example only one element in them by default could shorten the time to a solution by several orders of magnitude.

How to implement

The pipeline of a generation of a genetic algorithm is the following:

1. if the population is too small, add random elements
2. sort by decreasing fitness
3. crossover the population
4. mutate the population
5. sort by decreasing fitness
6. cull the least fitting

Chromosome handling

First, we need to find what shape of chromosomes could fit our problem. The chromosomes are a set of variable associated with each element of the set to optimize one by one^[1].

Chromosomes must be able to be handled by several function:

• The generator function:
  • It must be able to create random but never invalid chromosomes, even dumb ones
• The solver function
  • That will generate a solution
  • Solutions can be bad solutions and those must be handled correctly
  • Solutions are what is rated by the fitness function
• The mutation
  • The mutation function transforms or randomizes values in a chromosome
  • Mutations should be random, a 1 : 20 mutation ratio seems to work very well in general
• Copyability
  • For implementation of the crossover function
• Optionally an internal crossover, slicing bits of a chromosome into another can be used for very complex chromosomes, adding an extra crossover step

Notice the lack of mention of the fitness function, that is a secret tool that we will use later.

Rating and solution handling

Solutions generated from chromosomes need to be rated. We do that with a rating function. For a chromosome set x, with a solver function S, and with a rating function for its solution R, we define its fitness function F with F : x → R(S(x)).

The reason for this separation is to be able to change only the rating function, allowing it to be tuned to the final user with a business-behaviour border, allowing users to configure their optimal behaviour independently of implementation of the business logic of the genetic optimizer.

Conclusions

This was one of the simplest machine learning/optimizing algorithms. If there are algorithms that make you confused or you want more details, ask me on Telegram (@QNeko), or follow me on the Fediverse Archivist@social.linux.pizza

---

1. Sometimes we associate n² chromosomes for n elements, matching elements with each other element like a graph adjacency matrix, but most of the time, n is too big to do that comfortably. ↩︎