Abstract:
Proc. Assoc. Advmt. Anim. Breed. Genet. Voll2 SELECTING MATING PAIRS WITH GENETIC ALGORITHMS B. J. Haye.?, R. K. Shepherd' and S. Newman* `Department of Maths and Computing, Central Queensland University, Rockhampton, QLD 4702, Australia. `Meat Quality CRC, Tropical Beef Centre, Rockhampton, QLD 4702 SUMMARY Mate selection is of potential value in increasing progeny merit in a number of animal breeding scenarios. The effkiency of selecting mates using a genetic algorithm was assessed. Genetic algorithms (GAS) are search procedures based on the principles of natural genetics and natural selection, using simple elements of genetics such as reproduction, crossover and mutation. The GA found the optimal solution in every case, and efficiency of the GA increased with increasing mating set sizes. GAS will be a valuable tool in solving mate selection problems which include issues such as connection between herds, parameter estimation and inbreeding in future generations, where the value of matings made depends on the value of other matings made. Keywords: Mate selection, genetic algorithm. INTRODUCTION The issues of selection and mate allocation need to be simultaneously considered (mate selection) in a number of animal breeding scenarios: 1. Where the pattern of mate allocation is expected to a#ect the mean merit of progeny. This occurs when there is interaction between males and females in their expected breeding values. If heterosis dependent 2. Where progeny. is important, both expected merit of progeny and breeding value in the broad sense are on the breeds of mates allocated (Kinghom 1987). the pattern of mate allocation is expected to aflect the pattern of variance among the Kinghom and Shepherd (1994) used an exchange algorithm for mate selection so as to increase the predicted standard deviation of EBVs in the next generation. 3. Where the pattern of relationships among progeny is aficted. This impacts on longer term inbreeding and genetic links between fixed effect groups (Kinghom and Shepherd 1994). Figure 1 shows a hypothetical example of a mate selection problem. Female Candidates Male Candidates 1911 Figure 1. Expected progeny merit for matings between 3 male and 3 female candidates. 108 Proc. Assoc. Advmt. Anim. Breed. Genet. Voll2 The objective here is to maximise total progeny merit through optimal allocation of males to females. Expected progeny merit differs with each mating, and the problem becomes which mating pairs to select to maximise total progeny merit. If males are only allowed to mate once, optimal mate selections in this example are: for one mating (sire 3, dam 3: value 8), for two matings (2,1:7), (3,3:8) summing to 15, and for three matings (2,1:7), (1,2:6), (3,3:8) summing to 21. The objective of this paper is to assess the capabilities of Genetic Algorithms in selecting mating pairs. A fixed array of progeny merit is used. As the value of any mating does not depend on what other matings are made, the optimal mating set for comparison with the GA can be found by applying the linear programming (LP) transportation model, with addition of a dummy male to `mate' with unselected females, and vice versa (Jansen and Wilton 1985). GENETIC ALGORITHMS Genetic Algorithms (GAS) are search procedures based on the principles of natural genetics and natural selection, with an underlying emphasis on natural evolution (Goldberg 1989). Simple elements of biological genetics, namely reproduction, crossover and mutation are adapted in GAS to simulate a biological evolution process which can be effectively utilised as a search procedure which is applicable across a spectrum of optimisation problems (Dhingra and Lee 1994). Each generation of solutions breeds a new generation of solutions with the selection of breeding solutions based on an objective criterion function which mimics fitness. Genetic algorithms must have the following five components (Michalewicz 1994): - a genetic representation (chromosome) of a feasible solution to the problem, - a randomly generated initial population of feasible individuals (solutions) for the problem, - an objective criterion function which numerically evaluates individuals (solutions) and is analogous to fitness of the individual, - a method of selection of individuals (solutions) for breeding based on their fitness, - genetic operators like crossover and mutation that determine the offspring (solutions) of the next generation. - values for various parameters that the GA uses (population size, mutation rate, etc) A small example shows how a GA for mate selection operates. Two mating pairs are to be chosen from 3 male and 3 female candidates (Figure 1). First, an initial population of chromosomes (of mating sets) is randomly created. If the population size of the GA is 4, then this might be: (Table 1): 109 Proc. Assoc. Advmt. Anim. Breed. Genet. Vol12 Table 1. Possible chromosomes (mating set solutions) and their fitness Chromosome Number -1 2 3 Chromosome 0,2,0) (0,2,3) (0,192) Fitness 5 10 10 The number at the i* locus in a chromosome gives the identity of the male candidate mated to female candidate i. For example, (0,1,2) means that the two mating sets are (2,l) and (3,2) where the order is (dam, sire). The fitness of each of these chromosomes is assessed using an evaluation function, in this case the merit of the progeny (Figure 1). To breed a new generation of chromosomes, two chromosomes (`parents') are selected for breeding with the probability of selection proportional to their fitness. In this case say chromosomes 4 and 3 are selected. The two chromosomes are crossed at a random point along the chromosome, for example, between the second and third locus. Parents: (1,073) (0,192) Offspring: (1,0,2) (0,1,3) The mutation operator is used according to the mutation rate (eg. say lo%, where 10% of loci will be mutated). After applying mutation , say to the third locus in the first chromosome, the 2 is mutated to 3. After mutation the offspring may become: Offspring after mutation: (1,0,3) fitness: 11 (0,1,3) fitness: 15 This process of selection, crossover and mutation is used to breed each generation of 4 candidate chromosomes (mating sets). After a number of generations the GA is stopped and the best mating set over all generations determined. The efficiency of the GA was evaluated for increasing mating set sizes. Equal numbers of male and female candidates were simulated, with an independent, randomly chosen value assigned as predicted progeny merit from each possible progeny pair, as in Figure 1. Single pair mating was assumed in this paper, though the genetic algorithm can handle any fixed or variable mating ratios. Population size used for the GA was 5 when 4 and 5 candidates of each sex were available for mating and 30 when 10 and 20 candidates of each sex were available. Mutation rate used was 110 Proc. Assoc. Advmt. Anim. Breed. Genet. Vol12 variable, and increased to a maximum of 0.4 as genetic diversity in the population (of mating set solutions) was lost (this helps to prevent premature convergence). RESULTS AND DISCUSSION As mating set sizes increase, computational demand for the GA increases dramatically. Table 2 shows the efficiency of the GA in terms of evaluation efficiency and the number of generations required to fmd the optimal solution (as found by the LP) averaged over 100 replications. Evaluation efficiency is the number of mating sets evaluated by the GA divided by the total number of mating sets. Smaller numbers represent greater evaluation efficiencies. Table 2. Performance of the genetic algorithm applied to single-pair mating No of candidates of each sex to be allocated 4 5 10 20 AThe GA may revisit old solutions. GA generations required to find the optimal solution (* s.e.) 7.68 f 0.69 29.53 f 2.51 1132.24 f 11.32 104778.21 f 20.40 Evaluation efficiency 1.60-`= 1.23 0.0094 0.000072 Table 2 shows that the genetic algorithm always found the optimal solution, though the number of generations required to do so increased rapidly as the number of candidates of each sex available for mating increased. Evaluation efficiency improved with larger mating set sizes. GAS may be useful in situations where maximum total progeny merit with a large number of mating pairs is desired, such as in the pig industry (where attention to inbreeding potentially means that me pattern of mate allocation affects mean progeny merit). This is in contrast to linear Genetic algorithms are dynamic optimisation techniques. programming (LP) techniques, which require that each variable in evaluation of the objective function remain constant between generations. Genetic algorithm techniques for mate selection will be valuable in situations where the value of one mating depends on what other matings are made in the past, present, and in the future. Static techniques such as LPs cannot be applied here. This is the situation where animal breeding issues such as connection, parameter estimation and inbreeding in future generations are important. Kinghom and Shepherd (1990) pointed out that inclusion of such issues in an objective function, which describes net economic gain as a function of selection and mate selections, can actually set up a breeding program design through use of an appropriate mate selection algorithm. The dynamic nature of genetic algorithms make them potential candidates for this task. Designs will emerge (after considerable input initially) which place appropriate economic emphasis on the issues of importance included in the evaluation/fitness criterion. 111 Proc. Assoc. Advmt. Anim. Breed Genet. Voll2 Dhingara, A. K. and Lee, B. H. (1994) ht. J. Nwneric. Meth. E&g. 3714059. Goldberg, D. E. (1989) 'Genetic algorithms in search, optimization, and Addison-Wesley, Reading, MA. Jansen, G. B. andWil&m, J. W. (1985) J# Dairy&i. 68:1302. Kinghorn,.B. P. (li987) J Anim. Breed. Genet. 104:12. Kinghorn, B. P and Shepherd, R K. (1990) Proc. 4th World Congr. G&ret. Edinburgh, XV,.pp. 7-17. Kinghom, B. P and Shepherd, R. K. (1994) Proc. 5th World Cangr. Genet. Edinburgh, XVII, pp. 255-261. Michalewicz, Z. (1994) `%&m&c algorithms + da&vs@&ares = evolution Springer-Verlag, New York. machine learning'. Appl. Live&. Prod., Appi. Liwst, Prod., progmms' 2nd ad. 112