Multitask Knowledge Transfer in Genetic Algorithms

The previous article discussed transferring knowledge from one completed problem to a new problem. However, such sequential transfer of knowledge requires that there exist completed problems. But there could be times when we have to solve multiple problems and it is not practical to complete those problems one-by-one so that we can transfer the knowledge sequentially. In such cases, problems exchanging their knowledge with one another simultaneously becomes beneficial.

An example of such a scenario is finding the fastest path, the shortest path, and the most energy-efficient path between two nodes in a network. These are similar problems, so the knowledge synthesized while solving one problem may help the other two problems. However, here knowledge transfer has to be omnidirectional instead of being just sequential. How can we accomplish this? It turns out, we only need to make small modifications to the Adaptive Memetic Transfer Optimizer (AMTO) we learned about in the previous article. We call this new algorithm based on AMTO Adaptive Memetic Multitask Optimizer (AM-MTO).

Adaptive Memetic Multitask Optimizer

In sequential knowledge transfer, we use optimal populations from previous problems. However, in multitask scenarios, we can only make use of intermediate populations. Such populations will be diverse and spread across the search space. However, some individuals in those populations will be closer to the optimal location than others. Instead of building the probability distribution from the whole population, we build a probability distribution from a cluster of individuals who show high fitness. This way we can make sure tasks transfer only useful knowledge.

Initialize the population pg (g denotes the generation and it is 0 at the beginning)
Repeat

    If transfer interval elapsed

        Encode individuals

        Build probability distributions using fittest individuals from populations from other problems and probability distribution of individuals in pg by learning the weight values

        Sample new individuals from this probability population

        Decode individuals to produce offspring population o

else

        For each individual i in pg

        Calculate the fitness fi

        Select parents q from pg based on fi

        Perform crossover and mutations on q to produce offspring population o.

      Select who will make it to the next generation pg=g+1 from o, q (irrelevant if transfer interval elapsed), and (pg – q)

Until the termination condition is met

Thus, AM-MTO helps us transfer knowledge simultaneously among similar problems. Now that we have discussed how we can use optimal populations from other similar problems as memes, let’s also discuss the prospect of using Artificial Neural Networks as memes.

Artificial Neural Networks as memes

In the concluding chapter of Memetic Computation, Abhishek Gupta proposes the use of Artificial Neural Networks (ANNs) as memes. In EAs, we generally represent individuals using a low-level encoding scheme. To borrow the example the book uses, let’s use the classic knapsack problem. We have objects with different weight and profit values, and we need to fill the knapsack with objects such that we maximize the profit while ensuring we don’t violate the weight constraint. In such a case, a typical encoding would be an array of binary bits with each bit specifying if the object should be included or not.

This can be unsustainable when the number of objects increases. If there are 200 objects, then we need a 200-bit array. To mitigate such issues, the book proposes the use of ANN. We first build a simple ANN that takes the profit and weight of an object as the input and outputs a confidence value. Then, we feed the profit and weight of every object to the ANN to get their confidence values. Next, we add objects to the knapsack in the descending order of their confidence values until the knapsack is full. Then we calculate the total profit of the objects in the knapsack to compute the solution’s fitness score.

To improve fitness, we need to evolve the synaptic weights of the ANN. This is what the EA tries to accomplish. We start with random synaptic weights and evolve them until we maximize the profit. In other words, we get the EA to tune the ANN. The major advantage here is that we replace binary-bit arrays with synaptic weight arrays as individuals. Since the neurons we need in an ANN are generally less than the number of objects, this results in dimensionality reduction. We can then use the ANN we train as a meme to solve another problem.

Summary

This ends the series of articles on memetic computation, so let’s summarize what we have learned. Memetic computation makes use of the concept of memes introduced by Richard Dawkins to further enhance EAs. While exploiting genetic evolution for optimization, we can make use of memes, i.e., knowledge and ideas to produce more optimal solutions faster. In Canonical Memetic Algorithms, this knowledge comes from expert humans who choose which knowledge to apply using their own experience. We can render this human intervention redundant by selecting the right knowledge using data. Automatons take this a step further by extracting knowledge from past solutions, paving the way for complete automation. We can improve this further by exchanging knowledge between multiple similar simultaneous problems. Finally, Artificial Neural Networks offer a promising landscape for dimensionality reduction while serving as an option for modelling memes, which can be used to solve other similar problems.