Coverage for moptipy / algorithms / modules / selections / tournament_without_repl.py: 100%

1""" 

2Tournament selection without replacement in the tournaments. 

3 

4For each slot in the destination, a tournament with 

5:attr:`~moptipy.algorithms.modules.selections.\ 

6tournament_without_repl.TournamentWithoutReplacement.size` 

7randomly chosen participating solutions is conducted. The solution with 

8the best fitness wins and is copied to the destination. 

9 

10The tournaments are without replacement, following the algorithm by Goldberg, 

11Korg, and Deb. This means that a solution can only take part in another 

12tournament after all other solutions have joined one. In other words, we are 

13drawing solutions without replacement. This means that if we have `m` 

14solutions and want to select `n` from them by conducting tournaments of size 

15`s`, each solution will take part in at least `floor(s*n / m)` tournaments and 

16in at most `ceil(s*n / m)` ones. 

17 

18We implement this drawing of unique random indices as a partial Fisher-Yates 

19shuffle. The indices used to choose the tournament contestants from are in an 

20array forming a permutation. Initially, `unused=m` indices. Whenever we draw 

21one new index from the permutation, we do so from a random position from 

22`0..unused-1`, swap it to position `unused-1` and decrement `unused` by one. 

23Once `unused` reaches `0`, we reset it to `m`. This is different from the 

24originally proposed implementation of tournament selection without repetition 

25in that it does not first permutate all the indices. It will be better in 

26cases where only a few small tournaments are conducted, e.g., during mating 

27selection. It will be slower when many large tournaments are conducted, e.g., 

28during survival selection. 

29 

30Tournament selection with replacement is implemented in 

31:mod:`moptipy.algorithms.modules.selections.tournament_with_repl`. 

32 

331. David Edward Goldberg and Bradley Korb and Kalyanmoy Deb. Messy Genetic 

34 Algorithms: Motivation, Analysis, and First Results. *Complex Systems* 

35 3(5):493-530. 1989. 

36 https://wpmedia.wolfram.com/uploads/sites/13/2018/02/03-5-5.pdf 

372. Kumara Sastry and David Edward Goldberg. Modeling Tournament Selection with 

38 Replacement using Apparent Added Noise. In Lee Spector, Erik D. Goodman, 

39 Annie Wu, William Benjamin Langdon, and Hans-Michael Voigt, eds., 

40 *Proceedings of the 3rd Annual Conference on Genetic and Evolutionary 

41 Computation (GECCO'01)*, July 7-11, 2001, San Francisco, CA, USA, page 781. 

42 San Francisco, CA, United States: Morgan Kaufmann Publishers Inc. 

43 ISBN: 978-1-55860-774-3. https://dl.acm.org/doi/pdf/10.5555/2955239.2955378 

443. Peter J. B. Hancock. An Empirical Comparison of Selection Methods in 

45 Evolutionary Algorithms. In Terence Claus Fogarty, editor, *Selected Papers 

46 from the AISB Workshop on Evolutionary Computing (AISB EC'94),* April 

47 11-13, 1994, Leeds, UK, volume 865 of Lecture Notes in Computer Science, 

48 pages 80-94, Berlin/Heidelberg, Germany: Springer, ISBN: 978-3-540-58483-4. 

49 https://dx.doi.org/10.1007/3-540-58483-8_7. Conference organized by the 

50 Society for the Study of Artificial Intelligence and Simulation of 

51 Behaviour (AISB). 

524. Uday Kumar Chakraborty and Kalyanmoy Deb and Mandira Chakraborty. Analysis 

53 of Selection Algorithms: A Markov Chain Approach. *Evolutionary 

54 Computation,* 4(2):133-167. Summer 1996. Cambridge, MA, USA: MIT Press. 

55 doi:10.1162/evco.1996.4.2.133. 

56 https://dl.acm.org/doi/pdf/10.1162/evco.1996.4.2.133 

575. Tobias Blickle and Lothar Thiele. A Comparison of Selection Schemes used in 

58 Genetic Algorithms. Second edition, December 1995. TIK-Report 11 from the 

59 Eidgenössische Technische Hochschule (ETH) Zürich, Department of Electrical 

60 Engineering, Computer Engineering and Networks Laboratory (TIK), Zürich, 

61 Switzerland. ftp://ftp.tik.ee.ethz.ch/pub/publications/TIK-Report11.ps 

626. Sir Ronald Aylmer Fisher and Frank Yates. *Statistical Tables for 

63 Biological, Agricultural and Medical Research.* Sixth Edition, March 1963. 

64 London, UK: Oliver & Boyd. ISBN: 0-02-844720-4. https://digital.library.\ 

65adelaide.edu.au/dspace/bitstream/2440/10701/1/stat_tab.pdf 

66""" 

67 

68from math import inf 

69from typing import Any, Callable, Final 

70 

71from numpy import empty, ndarray 

72from numpy.random import Generator 

73from pycommons.types import check_int_range 

74 

75from moptipy.algorithms.modules.selection import FitnessRecord, Selection 

76from moptipy.utils.logger import KeyValueLogSection 

77from moptipy.utils.nputils import DEFAULT_INT, fill_in_canonical_permutation 

78 

79 

80# start book 

81class TournamentWithoutReplacement(Selection): 

82 """Tournament selection without replacement in the tournament.""" 

83 

84# end book 

85 def __init__(self, size: int = 2) -> None: 

86 """ 

87 Create the tournament selection method. 

88 

89 :param size: the size of the tournaments 

90 """ 

91 super().__init__() 

92 #: the tournament size 

93 self.size: Final[int] = check_int_range(size, "tournament size", 1) 

94 #: the cache for the array 

95 self.__perm: ndarray = empty(0, DEFAULT_INT) 

96 

97# start book 

98 def select(self, source: list[FitnessRecord], 

99 dest: Callable[[FitnessRecord], Any], 

100 n: int, random: Generator) -> None: 

101 """ 

102 Perform deterministic best selection without replacement. 

103 

104 :param source: the list with the records to select from 

105 :param dest: the destination collector to invoke for each selected 

106 record 

107 :param n: the number of records to select 

108 :param random: the random number generator 

109 """ 

110 size: Final[int] = self.size # the tournament size 

111 m: Final[int] = len(source) # number of elements to select from 

112 perm: ndarray = self.__perm # get the base permutation 

113 if len(perm) != m: # -book 

114 self.__perm = perm = empty(m, DEFAULT_INT) # -book 

115 fill_in_canonical_permutation(perm) # -book 

116 r0i = random.integers # fast call to random int from 0..(i-1) 

117 u: int = m # the number u of available (unused) indices = m 

118 for _ in range(n): # conduct n tournaments 

119 best: FitnessRecord | None = None # best competitor 

120 best_fitness: int | float = inf # best fitness, initial infinite 

121 for __ in range(size): # perform one tournament 

122 if u == 0: # if we have used all indices in perm 

123 u = m # then we again at the end 

124 i = r0i(u) # get random integer in 0..u-1 

125 u -= 1 # decrease number of unused indices 

126 chosen = perm[i] # get the index of the chosen element 

127 perm[u], perm[i] = chosen, perm[u] # swap to the end 

128 rec = source[chosen] # get contestant record 

129 rec_fitness = rec.fitness # get its fitness 

130 if rec_fitness <= best_fitness: # if better or equal... 

131 best = rec # ... rec becomes the new best record 

132 best_fitness = rec_fitness # and remember fitness 

133 dest(best) # at end of the tournament, send best to dest 

134 # end book 

135 

136 def __str__(self): 

137 """ 

138 Get the name of the tournament selection algorithm. 

139 

140 :return: the name of the tournament selection algorithm 

141 """ 

142 return f"tour{self.size}" 

143 

144 def initialize(self) -> None: 

145 """Initialize this selection algorithm.""" 

146 super().initialize() 

147 fill_in_canonical_permutation(self.__perm) 

148 

149 def log_parameters_to(self, logger: KeyValueLogSection) -> None: 

150 """ 

151 Log the parameters of the algorithm to a logger. 

152 

153 :param logger: the logger for the parameters 

154 """ 

155 super().log_parameters_to(logger) 

156 logger.key_value("size", self.size)