[IDEA] How to implement Evolutionary Algorithms

[light-weaver]

• What is the current behavior? The implementation of EAs in desdeo-emo is modular... in theory. While the genetic operators have been implemented as separate classes, the algorithms themselves are still monolithic and the operators are not easily interchangeable.Moreover, we have realised that certain assumptions we made about the structure of EAs and their underlying components are not always valid. In practice, this means that we can never be sure about what inputs a certain operator is expecting. This makes it difficult to implement these operators in a plug-and-play fashion.

• Describe the solution you'd like The end goal is us to be able to implement EAs like this:

def BasicEA(
    problem,  # The problem to be solved. Contains information about decision variables (among other things)
    evaluator,  # The evaluator (may be needed in case the problem class cannot evaluate solutions, true rn for some cases)
    generator,  # The initial population generator
    selector,  # The selection operator
    crossover,  # The crossover operator
    mutation,  # The mutation operator
    terminator,  # The termination condition
):
    population = generator.do()
    targets, constraints = evaluator.do(population)
    while not terminator.do():
        offspring = crossover.do(parents)
        offspring = mutation.do(offspring)
        offspring_targets, offspring_constraints = evaluator.do(offspring)
        population, targets, constraints = selector.do(
            (population, targets, constraints), 
            (offspring, offspring_targets, offspring_constraints))
    return population

The goal here would be to implement operators as separate classes that can be easily swapped out. However, as stated, these operators may need information as input that we are not providing in this basic example. One way to enable the communication of this information is through a publisher-subscriber (ish) pattern. Let there be a publisher that has access to the changes in the state of all operators in the EA. Let the operators be subscribers to this publisher. The operators can then subscribe to relevant information (messages) from the publisher whenever the publisher recieves these messages. How does the publisher get these messages? The subscribers are responsible for sending messages to the publisher (making them an author/content creator in this metaphor I guess). Whenever an operator changes its state, by having its do method called, it sends a message to the publisher. The message goes in the form of a dictionary. For example, the the termination operator, if it is counting the number of generations as a termination condition, could send:

{
    "current_generation": 5
    "max_generations": 100
}

whenever the do method is called. The publisher then sends the messages {"current_generation": 5} and {"max_generations": 100} to all entities that have subscribed to these messages. The entities can be other operators who can use this information to make internal changes. For example, a self-adaptive mutation operator could use the information to change its mutation rate. RVEA's selector can use the information to adapt the reference vectors or change the penalty function. These entities can also be unassociated with the EA, like a logger that logs the state of the EA at every generation. Note that no subscriber needs to know where the message is originating from. No "content creator" needs to know who is consuming the message. This makes the implementation of operators easier and more modular. The connections are made using the publisher, which is available to the programmer to mess around with.

• What is the motivation/use case for changing the behavior? This implementation would make it easier to implement new operators and to experiment with different combinations of operators. It enables automatic algorithm configuration and hyperparameter tuning. It also makes it easier to check the inner workings of the algorithm and to debug it.

• Describe alternatives you've considered The actual publisher-subscriber pattern maintains a disconnect between the subscribers and the message senders. Here, the subscribers are also the message senders. So it's not a true publisher-subscriber pattern. However, it isn't possible to implement a true publisher-subscriber pattern. I have looked into other patterns as well, like the observer pattern, but they don't fit the use case as well as this one does. There are other messaging protocols as well, like the actor model, but they are too complex for this use case.