This paper presents a parallel evolutionary program for natural language parsing.
The implementation follows an island model, in which, after a number of generations,
demes exchange some individuals in a round-robin manner. The population is composed
of potential parsings for a sentence, and the fitness function evaluates the appropriateness
of the parsing according to a given stochastic grammar. Both the fitness function and the
genetic operators, which require that the result of their application still corresponds to the
words in the input sentence, are expensive enough to make the evolutionary program
appropriate for a coarse grain parallel model and its distributed implementation.
The system has been implemented in a parallel machine using the PVM (Parallel
Virtual Machine) software. The paper describes the study of the parameters in the parallel
evolutionary program, such as the number of individuals to be exchanged between demes,
and the number of generations between exchanges. Different parameters of the algorithm,
such as population size, and crossover and mutation rates, have also been tested.