geneticalgorithm2.selections

  1from typing import Callable, Dict, List
  2
  3import math
  4import random
  5import numpy as np
  6
  7from .utils.aliases import array1D, TypeAlias
  8
  9SelectionFunc: TypeAlias = Callable[[array1D, int], array1D]
 10"""
 11Function (scores, count to select) -> indexes of selected
 12"""
 13
 14
 15#region UTILS
 16
 17def inverse_scores(scores: array1D) -> array1D:
 18    """
 19    inverses scores (min values become to max)
 20    """
 21    minobj = scores[0]
 22    normobj = scores - minobj if minobj < 0 else scores
 23
 24    return (np.amax(normobj) + 1) - normobj
 25
 26
 27def roulette(scores: array1D, parents_count: int) -> array1D:
 28    """simplest roulette selector for which the highest score means more preferred"""
 29
 30    sum_normobj = np.sum(scores)
 31    prob = scores / sum_normobj
 32    cumprob = np.cumsum(prob)
 33
 34    parents_indexes = np.array(
 35        [
 36            index if index < cumprob.size else np.random.randint(0, index - 1)
 37            for index in (
 38                np.searchsorted(cumprob, np.random.random())
 39                for _ in range(parents_count)
 40            )
 41        ]
 42    )
 43
 44    return parents_indexes
 45
 46
 47#endregion
 48
 49class Selection:
 50    """
 51    Selections functions static class
 52    
 53    Selection function selects the population subset according to scores and its own rules
 54    """
 55
 56    @staticmethod
 57    def selections_dict() -> Dict[str, SelectionFunc]:
 58        return {
 59            n: getattr(Selection, n)()
 60            for n in (
 61                'fully_random',
 62                'roulette',
 63                'stochastic',
 64                'sigma_scaling',
 65                'ranking',
 66                'linear_ranking',
 67                'tournament',
 68            )
 69        }
 70
 71    @staticmethod
 72    def fully_random() -> SelectionFunc:
 73        """returns the selector of fully random parents (for tests purposes)"""
 74        
 75        def func(scores: array1D, parents_count: int):
 76            indexes = np.arange(parents_count)
 77            return np.random.choice(indexes, parents_count, replace=False)
 78        
 79        return func
 80
 81    @staticmethod
 82    def roulette() -> SelectionFunc:
 83        
 84        def func(scores: array1D, parents_count: int):
 85            return roulette(inverse_scores(scores), parents_count)
 86        
 87        return func
 88
 89    @staticmethod
 90    def stochastic() -> SelectionFunc:
 91        
 92        def func(scores: np.ndarray, parents_count: int):
 93            f = inverse_scores(scores)
 94            
 95            fN: float = 1.0 / parents_count
 96            k: int = 0
 97            acc: float = 0.0
 98            parents: List[int] = []
 99            r: float = random.random() * fN
100            
101            while len(parents) < parents_count:
102                
103                acc += f[k]
104                
105                while acc > r:
106                    parents.append(k)
107                    if len(parents) == parents_count: 
108                        break
109                    r += fN
110                
111                k += 1
112            
113            return np.array(parents[:parents_count])
114        
115        return func
116
117    @staticmethod
118    def sigma_scaling(epsilon: float = 0.01, is_noisy: bool = False) -> SelectionFunc:
119        
120        def func(scores: array1D, parents_count):
121            f = inverse_scores(scores)
122            
123            sigma = np.std(f, ddof = 1) if is_noisy else np.std(f)
124            average = np.mean(f)
125            
126            if sigma == 0:
127                f = 1
128            else:
129                f = np.maximum(epsilon, 1 + (f - average)/(2*sigma))
130            
131            return roulette(f, parents_count)
132        
133        return func
134
135    @staticmethod
136    def ranking() -> SelectionFunc:
137        
138        def func(scores: array1D, parents_count: int):
139            return roulette(1 + np.arange(parents_count)[::-1], parents_count)
140        
141        return func
142
143    @staticmethod
144    def linear_ranking(selection_pressure: float = 1.5) -> SelectionFunc:
145        
146        assert 1 <= selection_pressure <= 2, f"selection_pressure should be in (1, 2), but got {selection_pressure}"
147        
148        def func(scores: array1D, parents_count: int):
149            tmp = parents_count * (parents_count-1)
150            alpha = (2 * parents_count - selection_pressure * (parents_count + 1)) / tmp
151            beta = 2 * (selection_pressure - 1) / tmp
152
153            a = -2 * alpha - beta
154            b = (2 * alpha + beta) ** 2
155            c = 8 * beta
156            d = 2 * beta
157            
158            indexes = np.arange(parents_count)
159            
160            return np.array(
161                [
162                    indexes[-round((a + math.sqrt(b + c * random.random())) / d)]
163                    for _ in range(parents_count)
164                ]
165            )
166
167        return func
168
169    @staticmethod
170    def tournament(tau: int = 2) -> SelectionFunc:
171
172        # NOTE
173        # this code really does tournament selection
174        # because scores are always sorted
175        
176        def func(scores: array1D, parents_count: int):
177            
178            indexes = np.arange(parents_count)
179            
180            return np.array(
181                [
182                    np.min(np.random.choice(indexes, tau, replace=False))
183                    for _ in range(parents_count)
184                ]
185            )
186        
187        return func
188    
189    
190