MINIMAL EDGE-ORDERED SPANNING TREES USING A SELF-ADAPTING GENETIC ALGORITHM WITH MULTIPLE GENOMIC REPRESENTATIONS

摘要

We consider the problem of finding minimal edge-ordered spanning trees where the edge costs are not fixed, but are time dependent. We propose using multiple genomic redundant representations in a self-adapting genetic algorithm (GA) employing various codes with different locality properties. These encoding schemes (e.g., permutation codes and prufer-like codes) either insure feasibility or require little repair after performing the operations of crossover and mutation and also ensure the feasibility of the initial randomly generated population (i.e., generation 0). The GA applied in solving this NP hard problem employs non-locality or locality representations when appropriate (i.e., the GA adapts to its current search needs) which makes the GA more efficient.