Multitask Linear Genetic Programming with Shared Individuals and its Application to Dynamic Job Shop Scheduling

Multitask genetic programming methods have been applied to various domains, such as classification, regression, and combinatorial optimization problems. Most existing multitask genetic programming methods are designed based on tree-based structures, which are not good at reusing building blocks since each sub-tree passes its outputs to only one parent. It may limit the design and performance of knowledge sharing in multitask optimization. Different from tree-based genetic programming, building blocks in linear genetic programming can be easily reused by more than one parent. Besides, existing multitask genetic programming methods always allocate each individual to a specific task and have to duplicate genetic materials from task to task in knowledge transfer, which is inefficient and often produces redundancy. Contrarily, it is natural for a linear genetic programming individual to produce multiple distinct outputs, which enables each linear genetic programming individual to solve multiple tasks simultaneously. With this in mind, we propose a new multitask linear genetic programming method that transfers knowledge via multi-output individuals (i.e., shared individuals among tasks). By integrating different solutions into one multi-output individual, the proposed method efficiently reuses common knowledge among tasks and maintains distinct behaviors for each task. The empirical results show that the proposed method has a significantly better test performance than state-of-the-art multitask genetic programming methods. Further analyses verify that the new knowledge transfer mechanism can adjust the transfer rate automatically and thus improves its effectiveness.