A Genetic Algorithm for Optimization Over a Simplex

Several combinatorial optimization problems require the minimization of a function over the standard n-dimensional simplex x1 +x2 +. . .+xn, x ≥ 0. Due to the high complexity of these problems, it is a common practice to solve them using metaheuristics, such as evolutionary algorithms. In this paper, we present a genetic algorithm based on a new chromosome representation that allows the direct generation of feasible solutions. With this representation, the solution space is discretized into hypercubes, and each hypercube is associated to an unique integer number that is stored in binary form to simplify the definition of the crossover and mutation operators. As an example, we use our approach to find the efficient frontier of some cardinality constrained portfolio optimization problems. Our experiments show that the new representation gives better results than the chromosomes built using the Cartesian coordinates on Rn.