предисловие
В этой статье обобщаются несколько стратегий отбора в генетических алгоритмах, в том числе:
- Proportionate Roulette Wheel Selection
- Linear Ranking Selection
- Exponential Ranking Selection
- Tournament Selection
Для каждой стратегии отбора я использовал Python для реализации соответствующей реализации и интегрировал ее в структуру генетического алгоритма GAFT, написанную мной в виде встроенного плагина. Его можно использовать в качестве эталона для детской обуви, в которой необходимо использовать задачи оптимизации генетических алгоритмов и изучать генетические алгоритмы.
Ссылка на проект:
- GitHub: github.com/PytLab/gaft
- PyPI: pypi.python.org/pypi/gaft
Операторы выбора в генетических алгоритмах
Генетический алгоритм (ГА) представляет собой адаптивный эвристический алгоритм поиска, который имитирует принцип «выживания наиболее приспособленных» в теории эволюции Дарвина и в конечном итоге получает оптимальное решение задачи оптимизации. На следующем рисунке показан простой генетический алгоритм:
Существует множество методов отбора видов, которые необходимо гибридизовать в популяции, и выбор подходящей стратегии отбора окажет большое влияние на общую производительность генетического алгоритма. Если алгоритм отбора решит уменьшить разнообразие, это приведет к преждевременной сходимости популяции к локальному оптимуму вместо желаемого нами глобального оптимума, который является так называемым «преждевременным». Однако, если стратегия выбора слишком расходящаяся, алгоритму будет трудно сходиться к оптимальной точке. Следовательно, нам нужно сбалансировать эти две точки, чтобы заставить генетический алгоритм эффективно сходиться к глобальному оптимуму.
Плагины операторов в рамках GAFT
GAFT — это структура генетического алгоритма, которую я разработал в соответствии со своими потребностями.GAFT — структура генетического алгоритма, реализованная на Python.", "Распараллеливание структуры генетического алгоритма GAFT с использованием MPI". Платформа предоставляет интерфейс подключаемых модулей, и пользователи могут использовать настраиваемые операторы и подключаемые модули анализа «на лету» для запуска процесса генетического алгоритма в среде gaft для оптимизации целевой проблемы.
В этой части я кратко расскажу о спецификации интерфейса gaft, связанной с генетическими операторами, и о том, как писать операторы, которые можно использовать в gaft.
Генетический оператор в gaft должен наследовать встроенный базовый класс фреймворка, а затем реализовать свой собственный оператор в соответствии с интерфейсом, предоставляемым базовым классом. Определения базовых классов находятся в/gaft/plugin_interfaces/operators/В каталоге я возьму оператор выбора в качестве примера, чтобы представить интерфейс.
Базовый класс оператора выбора в gaft:GASelection, в котором экземпляр этого класса вызывается в процессе генетического алгоритмаselectметода, а затем выбрать пару видов из популяции в качестве отца и матери для получения потомства в соответствии с соответствующей стратегией отбора в операторе. Базовый класс определяется как:
class GASelection(metaclass=SelectionMeta): ''' Class for providing an interface to easily extend the behavior of selection operation. ''' def select(self, population, fitness): ''' Called when we need to select parents from a population to later breeding. :param population: The current population. :type population: GAPopulation :return parents: Two selected individuals for crossover. :type parents: Tuple of tow GAIndividual objects. ''' raise NotImplementedErrorselectПараметрами метода являются текущая популяцияpopulationи соответствующая фитнес-функцияfitness,вpopulationдолжно бытьGAPopulationобъект,fitnessТакже должен быть вызываемым объектом.
Конечно, они кажутся немного безвкусными в языке с динамической типизацией, таком как Python, но для большей стандартизации пользователей яИспользуйте метакласс Python для ограничения реализации интерфейса и типов параметров интерфейса при создании экземпляра объекта класса.. Конкретная реализация находится в/gaft/plugin_interfaces/metaclasses.py, заинтересованная детская обувь может посмотреть способ реализации.
Я опубликую метод написания конкретного пользовательского оператора вместе со стратегией выбора в следующем разделе.
различные стратегии отбора
В этом разделе я в основном суммирую четыре различные стратегии выбора и реализую их на Python в виде плагинов gaft.
Оператор отбора определяет, какие особи будут отобраны из популяции для воспроизведения новых особей в следующем поколении популяции. Его основные принципы таковы:
the better is an individual; the higher is its chance of being a parent
Оператор отбора вводит функцию пригодности в итерацию генетического алгоритма, потому что функция пригодности является важным критерием того, является ли человек «достаточно хорошим». Но процесс отбора не может полагаться исключительно на функцию приспособленности, потому что оптимальный вид в популяции не обязательно находится вблизи глобальной оптимальной точки. Следовательно, мы также должны давать относительно «хорошим» особям шанс размножаться и избегать «недоношенности».
Proportionate Roulette Wheel Selection
Эта стратегия выбора рулетки является одной из самых основных стратегий выбора.Вероятность выбора индивидуума в популяции пропорциональна значению соответствующей функции приспособленности индивидуума. Нам нужно накопить и нормализовать значения пригодности всех особей в популяции и, наконец, выбрать особей, соответствующих области, в которую попадает случайное число, подобно вращению рулетки в казино.
Вероятность выбора каждого отдельного ai равна:
Что ж, запишем этот алгоритм в виде оператора, который можно выполнить в gaft.
from random import randomfrom bisect import bisect_rightfrom itertools import accumulate from ...plugin_interfaces.operators.selection import GASelection class RouletteWheelSelection(GASelection): def __init__(self): ''' Selection operator with fitness proportionate selection(FPS) or so-called roulette-wheel selection implementation. ''' pass def select(self, population, fitness): ''' Select a pair of parent using FPS algorithm. ''' # Normalize fitness values for all individuals. fit = [fitness(indv) for indv in population.individuals] min_fit = min(fit) fit = [(i - min_fit) for i in fit] # Create roulette wheel. sum_fit = sum(fit) wheel = list(accumulate([i/sum_fit for i in fit])) # Select a father and a mother. father_idx = bisect_right(wheel, random()) father = population[father_idx] mother_idx = (father_idx + 1) % len(wheel) mother = population[mother_idx] return father, motherПроцесс в основном делится на следующие:
- наследовать
GASelectionсвоего рода - выполнить
selectметод -
selectПараметрыGAPopulationЭкземпляры и фитнес-функции - По алгоритму выберите два вида, которым необходимо размножаться и возвращаться
Tournament Selection
Алгоритм турнирного отбора является наиболее популярной стратегией отбора в генетических алгоритмах из-за эффективности выполнения алгоритма и простоты реализации. В моем реальном приложении эта стратегия действительно лучше, чем обычная рулетка. Его стратегия также очень интуитивна, то есть мы извлекаем n особей из всей популяции, позволяем им соревноваться (турнир) и извлекаем из них лучшую особь. Количество лиц, участвующих в турнире, становится размером турнира. Обычно, когда n=2, это наиболее часто используемый размер, также известный как выбор бинарного турнира.
Преимущества турнирного отбора:
- Меньшая сложность O(n)
- Легко распараллелить
- Нелегко попасть в локальный оптимум
- Нет необходимости сортировать все значения пригодности
На следующем рисунке показан процесс выбора турнира с n=3:
Вы можете начать писать собственные операторы для запуска в gaft:
from random import sample from ...plugin_interfaces.operators.selection import GASelection class TournamentSelection(GASelection): def __init__(self, tournament_size=2): ''' Selection operator using Tournament Strategy with tournament size equals to two by default. ''' self.tournament_size = tournament_size def select(self, population, fitness): ''' Select a pair of parent using Tournament strategy. ''' # Competition function. complete = lambda competitors: max(competitors, key=fitness) # Check validity of tournament size. if self.tournament_size >= len(population): msg = 'Tournament size({}) is larger than population size({})' raise ValueError(msg.format(self.tournament_size, len(population))) # Pick winners of two groups as parent. competitors_1 = sample(population.individuals, self.tournament_size) competitors_2 = sample(population.individuals, self.tournament_size) father, mother = complete(competitors_1), complete(competitors_2) return father, motherLinear Ranking Selection
Следующие две стратегии выбора основаны на сортировке.Упомянутый выше первый базовый алгоритм выбора рулетки имеет недостаток, то есть, если значение пригодности человека равно 0, вероятность быть выбранным будет равна 0, человек не сможет производить потомство. Следовательно, нам нужен алгоритм, основанный на сортировке, чтобы назначить соответствующую вероятность выбора каждому человеку.
В линейном ранжированном отборе особи в популяции сначала сортируются в соответствии со значением приспособленности, а затем всем особям присваивается порядковый номер, лучшая особь — N, вероятность быть выбранной — Pmax, наихудшая особь — порядковый номер 1, а номер наихудшей особи равен 1. Выбрана вероятность Pmin, поэтому вероятность других особей среди них может быть получена по следующей формуле:
Код реализации:
from random import randomfrom itertools import accumulatefrom bisect import bisect_right from ...plugin_interfaces.operators.selection import GASelection class LinearRankingSelection(GASelection): def __init__(self, pmin=0.1, pmax=0.9): ''' Selection operator using Linear Ranking selection method. Reference: Baker J E. Adaptive selection methods for genetic algorithms[C]//Proceedings of an International Conference on Genetic Algorithms and their applications. 1985: 101-111. ''' # Selection probabilities for the worst and best individuals. self.pmin, self.pmax = pmin, pmax def select(self, population, fitness): ''' Select a pair of parent individuals using linear ranking method. ''' # Individual number. NP = len(population) # Add rank to all individuals in population. sorted_indvs = sorted(population.individuals, key=fitness, reverse=True) # Assign selection probabilities linearly. # NOTE: Here the rank i belongs to {1, ..., N} p = lambda i: (self.pmin + (self.pmax - self.pmin)*(i-1)/(NP-1)) probabilities = [self.pmin] + [p(i) for i in range(2, NP)] + [self.pmax] # Normalize probabilities. psum = sum(probabilities) wheel = list(accumulate([p/psum for p in probabilities])) # Select parents. father_idx = bisect_right(wheel, random()) father = population[father_idx] mother_idx = (father_idx + 1) % len(wheel) mother = population[mother_idx] return father, motherExponential Ranking Selection
Подобно описанной выше стратегии выбора линейного ранжирования, в этом экспоненциальном ранжировании используется экспоненциальная форма выражения при определении вероятности выбора каждого человека, где c является основанием и удовлетворяет условию 0 Код реализации: В этой статье представлены и обобщены четыре различные стратегии выбора в генетическом алгоритме, а также кратко представлен пользовательский интерфейс оператора структуры генетического алгоритма, написанный в этой статье.Стратегии выбора в этой статье реализованы в соответствии с требованиями интерфейса.Эти операторы также помещаются в GAFT как встроенные операторы структуры GAFT и могут использоваться непосредственно для детской обуви с помощью GAFT.from random import randomfrom itertools import accumulatefrom bisect import bisect_right from ...plugin_interfaces.operators.selection import GASelection class ExponentialRankingSelection(GASelection): def __init__(self, base=0.5): ''' Selection operator using Exponential Ranking selection method. :param base: The base of exponent :type base: float in range (0.0, 1.0) ''' if not (0.0 < base < 1.0): raise ValueError('The base of exponent c must in range (0.0, 1.0)') self.base = base def select(self, population, fitness): ''' Select a pair of parent individuals using exponential ranking method. ''' # Individual number. NP = len(population) # NOTE: Here the rank i belongs to {1, ..., N} p = lambda i: self.base**(NP - i) probabilities = [p(i) for i in range(1, NP + 1)] # Normalize probabilities. psum = sum(probabilities) wheel = list(accumulate([p/psum for p in probabilities])) # Select parents. father_idx = bisect_right(wheel, random()) father = population[father_idx] mother_idx = (father_idx + 1) % len(wheel) mother = population[mother_idx] return father, motherСуммировать
Ссылаться на