A Novel Experimental Analysis of the Minimum Cost Flow Problem

Abstract

In the GA approach the parameters that influence its performance include population size, crossover rate and mutation rate. Genetic algorithms are suitable for traversing large search spaces since they can do this relatively fast and because the mutation operator diverts the method away from local optima, which will tend to become more common as the search space increases in size. GA’s are based in concept on natural genetic and evolutionary mechanisms working on populations of solutions in contrast to other search techniques that work on a single solution. An important aspect of GA’s is that although they do not require any prior knowledge or any space limitations such as smoothness, convexity or unimodality of the function to be optimized, they exhibit very good performance in most applications. The minimum cost flow problem is formulated as genetic algorithm and simulated annealing. This paper shows genetic algorithms and simulated annealing are much easier to implement for solving transportation problems compared with constructing mathematical programming formulations. Finally, a new empirical study for the effect of parameters on the rate of convergence of the GA and SA are demonstrated.