A Modular Genetic Algorithm Specialized on Linear Constraints

Solving multi-objective linear programming and combinatorial optimization problems with search heuristics is a common practice widely discussed in literature with hundreds of different implementations. Genetic algorithms (GAs) are considered one of the most efficient strategies owing to their modularity and ability to being easily adapted to specific problems. They are particularly well-suited for complex non-linear problems or those which generate a set of Pareto optimal alternatives in the presence of multiple objectives. In this work we present the Multi-Objective Genetic Algorithm for Structured Inputs, or MOGASI. This algorithm combines modules and operators of standard GAs with specialized routines aimed at achieving enhanced performance on specific types of constraints, in particular linear ones. MOGASI classifies variables and constraints in such way to apply specialized data handling strategies to sub-problems with different data structures. The algorithm has a classic pre-processing phase which restricts the feasible domain. Furthermore, the problem dimension is reduced by eliminating equality constraints: a subset of variables is expressed in terms of the remaining ones so that the equality can be replaced by a linear combination of the remaining variables. Usually GAs work with a set of configurations called population and they try to evolve it towards the optimal solutions. MOGASI works with two separate but communicating populations instead. The first one takes advantage of the properties of the linear constraints: it introduces specialized operators which maintain design feasibility with respect to the defined linear convex space from one generation to the next. The second population considers all linear and non-linear constraint domains. MOGASI also has a mechanism for attempting to replace, whenever possible, unfeasible individuals. It has been tested against a set of benchmarks well-known in literature. Results show its efficiency on different multi-objective optimization problems against other state-of-the-art genetic algorithms.