Оптимизация на основе биогеографии

на основе биогеографии ( BBO ) — это эволюционный алгоритм (EA), который оптимизирует функцию Оптимизация путем стохастического и итеративного улучшения возможных решений с учетом заданной меры качества или функции приспособленности . BBO принадлежит к классу метаэвристик , поскольку включает множество вариаций, не делает никаких предположений относительно проблемы и, следовательно, может применяться к широкому классу задач.

BBO обычно используется для оптимизации многомерных вещественных функций, но он не использует градиент функции, а это означает, что он не требует, чтобы функция была дифференцируемой, как того требуют классические методы оптимизации, такие как градиентный спуск и методы квазиньютона. . Таким образом, BBO можно использовать для разрывных функций .

BBO оптимизирует проблему, поддерживая совокупность возможных решений и создавая новые возможные решения, комбинируя существующие по простой формуле. Таким образом, целевая функция рассматривается как черный ящик, который просто обеспечивает меру качества данного возможного решения, и градиент функции не требуется.

Как и многие эксперты, BBO руководствовался естественным процессом; в частности, BBO был мотивирован биогеографией , которая изучает распространение биологических видов во времени и пространстве. BBO был первоначально представлен Дэном Саймоном в 2008 году.

Основополагающие принципы

Математические модели биогеографии описывают видообразование (эволюцию новых видов ), миграцию видов (животных, рыб, птиц или насекомых) между островами и исчезновение видов. Говорят, что острова, благоприятные для жизни, имеют высокий индекс пригодности среды обитания (HSI). Характеристики, которые коррелируют с HSI, включают количество осадков, растительное разнообразие, топографическое разнообразие, площадь суши, температуру и другие. Определяющие характеристики называются переменными индекса пригодности (SIV). С точки зрения обитаемости, SIV являются независимыми переменными, а HSI — зависимой переменной.

На островах с высоким HSI могут обитать многие виды, а на островах с низким HSI — только несколько видов. На островах с высоким HSI обитает множество видов, которые мигрируют в близлежащие места обитания из-за больших популяций и большого количества видов, которые на них обитают. Обратите внимание, что эмиграция с острова с высоким HSI происходит не потому, что виды хотят покинуть свой дом; в конце концов, их родной остров — привлекательное место для жизни. Эмиграция происходит из-за накопления случайных воздействий на большое количество видов с большими популяциями. Эмиграция происходит, когда животные передвигаются по обломкам , плавают, летают или летают по ветру на соседние острова. Когда вид эмигрирует с острова, это не означает, что вид полностью исчезает со своего первоначального острова; эмигрируют лишь немногие представители, поэтому мигрирующий вид остается на своем первоначальном острове, одновременно мигрируя на соседний остров. Однако в BBO предполагается, что эмиграция с острова приводит к вымиранию с этого острова. Это предположение необходимо в BBO, поскольку виды представляют собой независимые переменные функции, а каждый остров представляет собой возможное решение проблемы оптимизации функции.

Острова с высоким HSI имеют не только высокий уровень эмиграции, но и низкий уровень иммиграции, поскольку на них уже обитает множество видов. Виды, мигрирующие на такие острова, будут иметь тенденцию вымирать, несмотря на высокий HSI острова, потому что существует слишком большая конкуренция за ресурсы со стороны других видов.

Острова с низким HSI имеют высокий уровень иммиграции из-за низкой численности населения. Опять же, это происходит не потому, что виды хотят иммигрировать на такие острова; в конце концов, эти острова — нежелательное место для жизни. Причина иммиграции на эти острова заключается в том, что здесь много места для дополнительных видов. Смогут ли иммигрирующие виды выжить в своем новом доме и как долго – это другой вопрос. Однако разнообразие видов коррелирует с HSI, поэтому, когда больше видов прибывает на остров с низким HSI, HSI острова будет иметь тенденцию к увеличению.

Рисунок справа иллюстрирует модель островной миграции. Уровень иммиграции $\lambda$ и уровень эмиграции $\mu$ являются функцией количества видов на острове. Максимально возможный уровень иммиграции $I$ происходит, когда на острове нет видов. По мере увеличения числа видов остров становится более густонаселенным, меньше видов способно пережить иммиграцию, а уровень иммиграции снижается. Максимально возможное количество видов, которое может поддерживать среда обитания, равно $S_{\max }$, в этот момент уровень иммиграции равен нулю. Если на острове нет видов, то уровень эмиграции равен нулю. По мере увеличения количества видов на острове он становится более перенаселенным, все больше представителей видов могут покинуть остров, а уровень эмиграции увеличивается. Когда на острове обитает наибольшее количество возможных видов $S_{\max }$, уровень эмиграции достигает максимально возможного значения $E$.

Модель иммиграции $\lambda$ и эмиграция $\mu$ вероятности. $S_{0}$ - равновесное количество видов, и $S_{\max }$ — максимальное количество видов, которые может поддерживать остров. $I$ и $E$ – максимальные уровни иммиграции и эмиграции соответственно.

В ББО, $\lambda _{k}$ это вероятность того, что данная независимая переменная в $k$-то решение-кандидат будет заменено; то есть, $\lambda _{k}$ вероятность иммиграции $x_{k}$. Если необходимо заменить независимую переменную, то решение-кандидат на эмиграцию выбирается с вероятностью, пропорциональной вероятности эмиграции. $\mu _{k}$. Обычно это выполняется с помощью выбора колеса рулетки .

${\text{Prob}}(x_{j}){\text{ is selected for emigration}}={\frac {\mu _{j}}{\sum _{i=1}^{N}\mu _{i}}}$

для $j=1,\cdots ,N$, где $N$ — количество решений-кандидатов в популяции.

Алгоритм

Как и большинство других советников, BBO включает мутацию . Базовый алгоритм BBO с размером популяции $N$ для оптимизации $n$-мерную функцию можно описать следующим образом.

Initialize a population of $N$ candidate solutions $\{x_{k}\}$ While not(termination criterion)    For each $x_{k}$, set emigration probability $\mu _{k}\propto$ fitness of $x_{k}$, do        with $\mu _{k}\in [0,1]$    For each $x_{k}$, set immigration probability $\lambda _{k}=1-\mu _{k}$ do    $\{z_{k}\}\leftarrow \{x_{k}\}$    For each individual $z_{k}(k=1,\cdots ,N)$ do        For each independent variable index $s\in [1,n]$ do            Use $\lambda _{k}$ to probabilistically decide whether to immigrate to $z_{k}$            If immigrating then                Use $\{\mu _{i}\}$ to probabilistically select the emigrating individual $x_{j}$                $z_{k}(s)\leftarrow x_{j}(s)$            End if        Next independent variable index: $s\leftarrow s+1$        Probabilistically mutate $z_{k}$    Next individual: $k\leftarrow k+1$    $\{x_{k}\}\leftarrow \{z_{k}\}$Next generation

Обсуждение алгоритма BBO

• Численность населения $N$ является параметром настройки. Если $N$ слишком мал или слишком велик, то производительность оптимизации BBO пострадает. Типичные реализации BBO используют значение $N$ где-то между 20 и 200.
• Начальная совокупность решений-кандидатов $\{x_{k}\}_{k=1}^{N}$ обычно генерируется случайным образом. Однако его можно сгенерировать в зависимости от задачи, основываясь на некоторых разумных предположениях или ранее известных хороших решениях задачи оптимизации.
• Критерий завершения зависит от проблемы, как и в любом другом советнике. В большинстве приложений критерием завершения является предел количества генераций или предел оценки функции (то есть частота вычисления целевой функции).
• $\{z_{k}\}$ является временной совокупностью, так что все эмигрирующие переменные могут происходить из совокупности, существующей в начале поколения, то есть $\{x_{k}\}$.

Алгоритмические варианты

Было предложено множество вариаций базового алгоритма BBO, среди которых следующие.

• Элитаризм реализован в большинстве советников, чтобы гарантировать, что лучшее решение-кандидат не потеряется от одного поколения к другому. Это можно реализовать разными способами, но один из распространенных способов — сохранять лучшие возможные решения в начале каждого поколения в наборе. $\mathbb {E}$; затем замените худшие возможные решения на $\mathbb {E}$ в конце поколения, после завершения миграции и мутации. Размер $\mathbb {E}$ является параметром настройки, но $\mathbb {E}$ обычно включает в себя двух лучших людей. для генетических алгоритмов . Первоначально элитизм был предложен ДеДжонгом Элитизм может существенно повлиять на производительность BBO, и его настоятельно рекомендуется использовать.
• Замена дубликатов часто реализуется в BBO. Это процедура в конце каждого поколения, которая заменяет повторяющихся особей в популяции. Сканирование дубликатов может потребовать больших вычислительных ресурсов, поскольку это $O(N^{2})$ операция, поэтому она часто выполняется только каждые несколько поколений, а не каждое поколение.
• Смешение может быть реализовано в BBO. Со смешиванием, вместо замены $z_{k}(s)$ в решении кандидата-иммигранта с $x_{j}(s)$ из решения эмигрирующего кандидата, $z_{k}(s)$ устанавливается равным линейной комбинации его исходного значения и $x_{j}(s)$:

$z_{k}(s)\leftarrow \alpha z_{k}(s)+(1-\alpha )x_{j}(s)$

где $\alpha \in [0,1]$, и $\alpha =0$ соответствует стандартной миграции, как показано в алгоритме выше. Blended BBO основан на смешанном скрещивании генетических алгоритмов. и было показано, что он превосходит стандартный BBO.

• Алгоритм BBO, представленный выше, называется BBO на основе частичной иммиграции, поскольку решение-иммигрирующий кандидат выбирается до того, как будет выбрано решение-эмигрирующий кандидат, и миграция для каждой независимой переменной в решении-кандидате-иммиграции выполняется независимо от всех других независимых переменных. Также были предложены другие подходы к выбору решений для иммигрантов и эмигрирующих кандидатов.
• Кривые миграции на рисунке выше линейны, но нелинейные кривые миграции часто дают лучшую производительность.

Гибридизация

• BBO был гибридизирован с несколькими другими советниками, включая оптимизацию роя частиц , дифференциальная эволюция , стратегия эволюции , основанные на оппозиции вычисления , рассуждение по прецедентам , алгоритм искусственной пчелиной семьи , оптимизация бактериального кормления, поиск гармонии , и симплексный алгоритм .
• BBO можно объединить с локальным поиском для создания меметического алгоритма , который работает намного лучше, чем один BBO.

Программное обеспечение

МАТЛАБ

• Следующий код MATLAB дает реализацию BBO для минимизации 20-мерной функции Розенброка . Обратите внимание, что следующий код очень прост, хотя и включает в себя элитарность. Серьезная реализация BBO должна включать некоторые из рассмотренных выше вариантов, такие как замена дубликатов, смешивание, нелинейная миграция и локальная оптимизация.

function BBO% Biogeography-based optimization (BBO) to minimize a continuous function% This program was tested with MATLAB R2012bGenerationLimit = 50; % generation count limit PopulationSize = 50; % population sizeProblemDimension = 20; % number of variables in each solution (i.e., problem dimension)MutationProbability = 0.04; % mutation probability per solution per independent variableNumberOfElites = 2; % how many of the best solutions to keep from one generation to the nextMinDomain = -2.048; % lower bound of each element of the function domainMaxDomain = +2.048; % upper bound of each element of the function domain% Initialize the populationrng(round(sum(100*clock))); % initialize the random number generatorx = zeros(PopulationSize, ProblemDimension); % allocate memory for the populationfor index = 1 : PopulationSize % randomly initialize the population    x(index, :) = MinDomain + (MaxDomain - MinDomain) * rand(1, ProblemDimension);endCost = RosenbrockCost(x); % compute the cost of each individual  [x, Cost] = PopulationSort(x, Cost); % sort the population from best to worstMinimumCost = zeros(GenerationLimit, 1); % allocate memoryMinimumCost(1) = Cost(1); % save the best cost at each generation in the MinimumCost arraydisp(['Generation 0 min cost = ', num2str(MinimumCost(1))]);z = zeros(PopulationSize, ProblemDimension); % allocate memory for the temporary population% Compute migration rates, assuming the population is sorted from most fit to least fitmu = (PopulationSize + 1 - (1:PopulationSize)) / (PopulationSize + 1); % emigration ratelambda = 1 - mu; % immigration ratefor Generation = 1 : GenerationLimit    % Save the best solutions and costs in the elite arrays    EliteSolutions = x(1 : NumberOfElites, :);    EliteCosts = Cost(1 : NumberOfElites);    % Use migration rates to decide how much information to share between solutions    for k = 1 : PopulationSize        % Probabilistic migration to the k-th solution        for j = 1 : ProblemDimension            if rand < lambda(k) % Should we immigrate?                % Yes - Pick a solution from which to emigrate (roulette wheel selection)                RandomNum = rand * sum(mu);                Select = mu(1);                SelectIndex = 1;                while (RandomNum > Select) && (SelectIndex < PopulationSize)                    SelectIndex = SelectIndex + 1;                    Select = Select + mu(SelectIndex);                end                z(k, j) = x(SelectIndex, j); % this is the migration step            else                z(k, j) = x(k, j); % no migration for this independent variable            end        end    end    % Mutation    for k = 1 : PopulationSize        for ParameterIndex = 1 : ProblemDimension            if rand < MutationProbability                z(k, ParameterIndex) = MinDomain + (MaxDomain - MinDomain) * rand;            end        end    end    x = z; % replace the solutions with their new migrated and mutated versions    Cost = RosenbrockCost(x); % calculate cost    [x, Cost] = PopulationSort(x, Cost); % sort the population and costs from best to worst    for k = 1 : NumberOfElites % replace the worst individuals with the previous generation's elites        x(PopulationSize-k+1, :) = EliteSolutions(k, :);        Cost(PopulationSize-k+1) = EliteCosts(k);    end    [x, Cost] = PopulationSort(x, Cost); % sort the population and costs from best to worst    MinimumCost(Generation+1) = Cost(1);    disp(['Generation ', num2str(Generation), ' min cost = ', num2str(MinimumCost(Generation+1))])end% Wrap it up by displaying the best solution and by plotting the resultsdisp(['Best solution found = ', num2str(x(1, :))])close allplot(0:GenerationLimit, MinimumCost);xlabel('Generation')ylabel('Minimum Cost')return%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%function [x, Cost] = PopulationSort(x, Cost)% Sort the population and costs from best to worst[Cost, indices] = sort(Cost, 'ascend');x = x(indices, :);return%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%function [Cost] = RosenbrockCost(x)% Compute the Rosenbrock function value of each element in xNumberOfDimensions = size(x, 2);Cost = zeros(size(x, 1), 1); % allocate memory for the Cost arrayfor PopulationIndex = 1 : length(x)    Cost(PopulationIndex) = 0;    for i = 1 : NumberOfDimensions-1        Temp1 = x(PopulationIndex, i);        Temp2 = x(PopulationIndex, i+1);        Cost(PopulationIndex) = Cost(PopulationIndex) + 100 * (Temp2 - Temp1^2)^2 + (Temp1 - 1)^2;    endendreturn

Р

• «bbo: Оптимизация на основе биогеографии» — это пакет R для непрерывного BBO.

Расширения

BBO был расширен до шумных функций (то есть функций, оценка пригодности которых искажена шумом); ограниченные функции; комбинаторные функции; и многоцелевые функции. Кроме того, был реализован алгоритм многокритериальной оптимизации, основанный на микробиогеографии (μBiMO): он подходит для решения многокритериальных оптимизаций в области промышленного дизайна, поскольку основан на небольшом количестве островов (отсюда и название μBiMO), т.е. требуется несколько вызовов целевой функции.

Математический анализ

BBO был математически проанализирован с использованием моделей Маркова. и модели динамических систем.

Приложения

Ученые применили BBO в различных академических и промышленных приложениях. Они обнаружили, что BBO работает лучше, чем современные методы глобальной оптимизации.

Например, Ван и др. доказал, что BBO показал равную производительность с FSCABC, но с более простыми кодами.

Ян и др. показало, что BBO превосходит GA, PSO и ABC.

Внешние ссылки

• Домашняя страница ББО