OPTIMIZATION OF NEWSPAPER DISPLAY ADVERTISING LAYOUT: USING A GENETIC ALGORITHM WITH A NOVEL REARRANGEMENT STEP

T his thesis is a report of an investigation into the use of genetic algorithms for optimal placement of display advertising in newspapers. Advertisement placement is a constrained optimization problem which like bin packing and stock cutting problems may be attacked as an exercise in reordering. The goal is to distribute a set of advertisements to a set of pages, and then arrange each page so that the free space is consolidated and amenable to use for other content. A population consisting of a set of layout chromosomes was evolved using the genetic operators of order crossover, mutation and inversion. Each layout chromosome was a list of genes; each gene a pair, consisting of an advertisement number and a mode. Each layout chromosome was first decoded by distributing the genes to a set of page chromosomes. These were in turn either decoded into a page layout directly – using both the order information and the mode, or further adapted by a period of evolution (called individual page evolution) using the same genetic operators and only then decoded into a page layout. In order for the adaptation due to individual page evolution to be transmitted to the population of layout chromosomes, a reverse transcription operator called the Lamarck operator served to produce revised layout chromosomes from the resulting page chromosomes after each period of evolution. A fitness function was devised for individual pages which scored layouts on a number of criteria. The fitness of a layout was the sum of the fitnesses of each individual pages, penalized for constraint violation. Tested against data drawn from a suburban daily newspaper, the system produced plausible layouts in general, although it was unable to match the layout of the published paper. The Lamarck operator was shown to increase the rate of convergence of the genetic algorithm even without individual page evolution. Individual page evolution in turn was shown to both further increase the convergence rate of the algorithm and to produce better layouts. The conclusion was drawn that the system is capable of discovering good solutions to some problems, but that further work is required on the fitness function and mutation operators