OPTIMAL SEQUENCED MATROID BASES SOLVED BY GA'S WITH FEASIBLE SEARCH SPACE INCLUDING APPLICATIONS

摘要

We consider an extension to the optimal matroid base problem whereby the matroid element costs are not fixed, but are time dependent. We propose a genetic algorithm (GA) approach to solve the optimal sequenced matroid base problem (OSMBP) by employing efficient codes which are suffixed by a standard permutation code. These novel encoding schemes insure feasibility after performing the classical operations of crossover and mutation and also ensure the feasibility of the initial randomly generated population (i.e., generation 0). This class of problems, where costs are not fixed but are time dependent, embrace non-locality which actually makes the GAs more efficient. A variety of practical matroid applications with time dependent costs will also be presented.