Оптимизация на основе биогеографии - Biogeography-based optimization
Оптимизация на основе биогеографии (BBO) является эволюционный алгоритм (EA) что оптимизирует а функция к стохастически и итеративно улучшение возможные решения в отношении данной меры качества, или фитнес-функция. BBO относится к классу метаэвристика поскольку он включает в себя множество вариаций, и поскольку он не делает никаких предположений о проблеме и, следовательно, может применяться к широкому классу проблем.
BBO обычно используется для оптимизации многомерных функций с действительными значениями, но не использует градиент функции, что означает, что она не требует, чтобы функция была дифференцируемый в соответствии с требованиями классических методов оптимизации, таких как градиентный спуск и квазиньютоновские методы. Следовательно, BBO можно использовать на дисках.непрерывные функции.
BBO оптимизирует проблему, поддерживая набор возможных решений и создавая новые возможные решения, комбинируя существующие в соответствии с простой формулой. Таким образом целевая функция рассматривается как черный ящик, который просто обеспечивает меру качества данного возможного решения, и градиент функции не требуется.
Как и многие советники, BBO был мотивирован естественным процессом; в частности, BBO был мотивирован биогеография, который является изучением распределения биологических видов во времени и пространстве.[1] BBO был первоначально представлен Дэн Саймон в 2008.[2]
Основные принципы
Математические модели биогеография описывать видообразование (эволюция новых разновидность ), миграция видов (животных, рыб, птиц или насекомых) между островами и вымирание видов.[3] Считается, что острова, благоприятные для жизни, имеют высокий индекс пригодности среды обитания (HSI).[4] Характеристики, которые коррелируют с HSI, включают количество осадков, растительное разнообразие, топографическое разнообразие, площадь суши, температуру и другие. Определяющие характеристики называются переменными индекса пригодности (SIV). С точки зрения обитаемости, SIV являются независимыми переменными, а HSI - зависимой переменной.
Острова с высоким HSI могут поддерживать многие виды, а острова с низким HSI могут поддерживать только несколько видов. На островах с высоким HSI есть много видов, которые эмигрировать в близлежащие места обитания из-за больших популяций и большого количества видов, которые они содержат. Обратите внимание, что эмиграция с острова с высоким HSI не происходит, потому что виды хотеть покинуть свой дом; в конце концов, их родной остров - привлекательное место для жизни. Эмиграция происходит из-за накопления случайных воздействий на большое количество видов с большими популяциями. Эмиграция происходит во время езды животных обломки плавать, летать или кататься на ветру к соседним островам. Когда вид эмигрирует с острова, это не означает, что вид полностью исчезает с его первоначального острова; эмигрируют лишь несколько представителей, поэтому эмигрирующий вид остается на своем первоначальном острове, в то же время мигрируя на соседний остров. Однако в BBO предполагается, что эмиграция с острова приводит к исчезновению с этого острова. Это предположение необходимо в BBO, потому что виды представляют собой независимые переменные функции, а каждый остров представляет собой возможное решение задачи оптимизации функции.
Острова с высоким уровнем HSI не только имеют высокий уровень эмиграции, но и низкий уровень иммиграции, потому что они уже поддерживают многие виды. Виды, которые мигрируют на такие острова, будут иметь тенденцию к вымиранию, несмотря на высокий HSI острова, потому что существует слишком большая конкуренция за ресурсы со стороны других видов.
Острова с низким уровнем HSI имеют высокий уровень иммиграции из-за их низкой численности населения. Опять же, это не потому, что виды хотеть иммигрировать на такие острова; в конце концов, эти острова - нежелательное место для жизни. Причина иммиграции на эти острова заключается в том, что здесь много места для дополнительных видов. Другой вопрос, сможет ли иммигрантский вид выжить в своем новом доме и как долго. Тем не мение, видовое разнообразие коррелирует с HSI, поэтому, когда больше видов прибывает на остров с низким HSI, HSI острова будет иметь тенденцию к увеличению.[4]
На рисунке справа показана модель миграции с острова.[3] Скорость иммиграции и уровень эмиграции зависят от количества видов на острове. Максимально возможная иммиграционная ставка происходит, когда на острове нет ни одного вида. По мере увеличения числа видов остров становится более многолюдным, меньшее количество видов может выжить при иммиграции, а скорость иммиграции снижается. Максимально возможное количество видов, которые может поддерживать среда обитания, - это , после чего уровень иммиграции равен нулю. Если на острове нет видов, то уровень эмиграции равен нулю. По мере того, как количество видов на острове увеличивается, он становится более многолюдным, больше представителей видов могут покинуть остров, а скорость эмиграции увеличивается. Когда на острове обитает наибольшее количество возможных видов , темпы эмиграции достигают максимально возможного значения .
В BBO, вероятность того, что данная независимая переменная в -й вариант решения будет заменен; то есть, вероятность иммиграции . Если необходимо заменить независимую переменную, то решение кандидата на эмиграцию выбирается с вероятностью, которая пропорциональна вероятности эмиграции. . Обычно это выполняется с помощью выбор колеса рулетки.
за , куда количество возможных решений в популяции.
Алгоритм
Как и большинство других советников, BBO включает мутация. Базовый алгоритм BBO с размером популяции для оптимизации -мерную функцию можно описать следующим образом.
Инициализировать популяцию возможные решения В то время как не(критерий прекращения) Для каждого , установить вероятность эмиграции пригодность , делать с Для каждого , установить вероятность иммиграции делать Для каждого индивидуальный делать Для каждого индекс независимой переменной делать Использовать вероятностно решить, иммигрировать ли в Если иммигрант тогда Использовать для вероятностного отбора эмигрирующего человека Конец, если Следующий индекс независимой переменной: Вероятностно мутировать Следующее лицо: Следующее поколение
Обсуждение алгоритма BBO
- Численность населения - параметр настройки. Если слишком маленький или слишком большой, тогда производительность оптимизации BBO пострадает. Типичные реализации BBO используют значение где-то между 20 и 200.
- Начальная популяция возможных решений обычно генерируется случайным образом. Однако он может быть сгенерирован проблемно-зависимым образом на основе некоторых разумных предположений или ранее известных хороших решений проблемы оптимизации.
- Критерий прекращения зависит от проблемы, как и в любом другом советнике. В большинстве приложений критерием завершения является предел количества поколений или предел оценки функции (то есть, как часто оценивается целевая функция).
- - это временная популяция, так что все эмигрирующие переменные могут происходить из популяции, которая существует в начале поколения, то есть .
Алгоритмические вариации
Было предложено множество вариаций базового алгоритма BBO, среди которых можно выделить следующие.
- Элитарность реализована в большинстве советников, чтобы гарантировать, что лучший вариант решения не будет утерян от одного поколения к другому. Это может быть реализовано различными способами, но один из распространенных способов - сохранить лучшие варианты решений в начале каждого поколения в наборе. ; затем замените худшие возможные решения на в конце поколения, после завершения миграции и мутации. Размер параметр настройки, но обычно включает двух лучших людей. Первоначально элитарность предлагалась для генетические алгоритмы пользователя DeJong.[5] Элитарность может существенно повлиять на эффективность BBO, и поэтому настоятельно рекомендуется.
- В BBO часто применяется дублирующая замена. Это процедура в конце каждого поколения, которая заменяет повторяющихся особей в популяции. Поиск дубликатов может потребовать больших вычислительных ресурсов, потому что это операция, поэтому она часто выполняется только каждые несколько поколений, а не каждое поколение.
- Смешивание может быть реализовано в BBO. При смешивании вместо замены в решении иммиграционного кандидата с из решения эмигрантского кандидата, устанавливается равным линейной комбинации исходного значения и :
- куда , и соответствует стандартной миграции, как показано в алгоритме выше. Смешанный BBO основан на смешанном кроссовере в генетических алгоритмах,[6] и было показано, что он превосходит стандартный BBO.[7]
- Алгоритм BBO, представленный выше, называется BBO на основе частичной иммиграции, потому что решение кандидата на иммиграцию выбирается до выбора решения кандидата на иммиграцию, а миграция для каждой независимой переменной в решении кандидата на иммиграцию выполняется независимо от всех других независимых переменных. Также были предложены другие подходы к выбору возможных решений для иммиграции и эмиграции.[8][9]
- Кривые миграции на приведенном выше рисунке линейны, но нелинейные кривые миграции часто дают лучшие характеристики.[10]
Гибридизация
- BBO был гибридизирован с несколькими другими советниками, включая оптимизация роя частиц,[9][11] дифференциальная эволюция,[12] стратегия эволюции,[13] вычисления на основе оппозиции,[14] аргументация по делу,[15] алгоритм искусственной пчелиной семьи,[нужна цитата ] оптимизация бактериального кормления,[16] поиск гармонии,[17] и симплексный алгоритм.[18]
- BBO можно объединить с локальным поиском для создания меметический алгоритм это работает намного лучше, чем только BBO.[19]
Программного обеспечения
MATLAB
- Следующий код MATLAB дает реализацию BBO для минимизации 20-мерного Функция Розенброка. Обратите внимание, что следующий код очень простой, хотя и включает элитарность. Серьезная реализация BBO должна включать некоторые из описанных выше вариаций, таких как дублирующая замена, смешивание, нелинейная миграция и локальная оптимизация.
функция BBO% Оптимизация на основе биогеографии (BBO) для минимизации непрерывной функции% Эта программа была протестирована с MATLAB R2012bGenerationLimit = 50; % ограничение количества поколений Численность населения = 50; % численность населенияПроблема Размер = 20; % количество переменных в каждом решении (т. е. размер проблемы)Мутация Вероятность = 0.04; % вероятности мутации на решение по независимой переменнойNumberOfElites = 2; % сколько лучших решений передать от поколения к поколениюMinDomain = -2.048; % нижняя граница каждого элемента области функцииMaxDomain = +2.048; % верхняя граница каждого элемента области функции% Инициализировать популяциюrng(круглый(сумма(100*Часы))); % инициализировать генератор случайных чиселИкс = нули(Численность населения, Проблема Размер); % выделить память для населенияза индекс = 1 : Численность населения % случайно инициализировать совокупность Икс(индекс, :) = MinDomain + (MaxDomain - MinDomain) * ранд(1, Проблема Размер);конецРасходы = РозенброкСтоимость(Икс); % вычислить стоимость каждого человека [Икс, Расходы] = PopulationSort(Икс, Расходы); % отсортировать население от лучшего к худшемуMinimumCost = нули(GenerationLimit, 1); % выделить памятьMinimumCost(1) = Расходы(1); % экономия лучших затрат при каждом поколении в массиве MinimumCostдисп(['Генерация 0 мин. Стоимость =', num2str(MinimumCost(1))]);z = нули(Численность населения, Проблема Размер); % выделить память для временного населения% Вычислить коэффициенты миграции при условии, что совокупность отсортирована от наиболее подходящей к наименее подходящейму = (Численность населения + 1 - (1:Численность населения)) / (Численность населения + 1); % эмиграциилямбда = 1 - му; % иммиграционной ставкиза Поколение = 1 : GenerationLimit % Экономьте лучшие решения и затраты в элитных массивах Элитные решения = Икс(1 : NumberOfElites, :); EliteCosts = Расходы(1 : NumberOfElites); % Используйте скорость миграции, чтобы решить, какой объем информации следует разделять между решениями за k = 1 : Численность населения % Вероятностный переход к k-му решению за j = 1 : Проблема Размер если ранд < лямбда(k) % Следует ли нам иммигрировать? % Да - выберите решение, из которого эмигрировать (выбор колеса рулетки) RandomNum = ранд * сумма(му); Выбирать = му(1); SelectIndex = 1; пока (RandomNum > Выбирать) && (SelectIndex < Численность населения) SelectIndex = SelectIndex + 1; Выбирать = Выбирать + му(SelectIndex); конец z (k, j) = Икс(SelectIndex, j); % это шаг миграции еще z (k, j) = Икс(k, j); % нет миграции для этой независимой переменной конец конец конец % Мутация за k = 1 : Численность населения за ParameterIndex = 1 : Проблема Размер если ранд < Мутация Вероятность z(k, ParameterIndex) = MinDomain + (MaxDomain - MinDomain) * ранд; конец конец конец Икс = z; % заменяют решения их новыми перенесенными и измененными версиями Расходы = РозенброкСтоимость(Икс); % рассчитать стоимость [Икс, Расходы] = PopulationSort(Икс, Расходы); % сортировать совокупность и стоимость от лучшего к худшему за k = 1 : NumberOfElites % заменить худших людей элитой предыдущего поколения Икс(Численность населения-k+1, :) = Элитные решения(k, :); Расходы(Численность населения-k+1) = EliteCosts(k); конец [Икс, Расходы] = PopulationSort(Икс, Расходы); % сортировать совокупность и стоимость от лучшего к худшему MinimumCost(Поколение+1) = Расходы(1); дисп(['Поколение ', num2str(Поколение), 'минимальная стоимость =', num2str(MinimumCost(Поколение+1))])конец% Завершите его отображением лучшего решения и нанесением результатов на графикдисп(['Лучшее решение найдено =', num2str(Икс(1, :))])Закрыть всеучасток(0:GenerationLimit, MinimumCost);xlabel('Поколение')ярлык(«Минимальная стоимость»)возвращаться%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%функция[x, Стоимость] =PopulationSort(x, Стоимость)% Сортировка населения и затрат от лучшего к худшему[Расходы, индексы] = Сортировать(Расходы, 'ascend');Икс = Икс(индексы, :);возвращаться%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%функция[Расходы] =РозенброкСтоимость(Икс)% Вычислить значение функции Розенброка для каждого элемента в xNumberOfDimensions = размер(Икс, 2);Расходы = нули(размер(Икс, 1), 1); % выделить память для массива затратза PopulationIndex = 1 : длина(Икс) Расходы(PopulationIndex) = 0; за я = 1 : NumberOfDimensions-1 Temp1 = Икс(PopulationIndex, я); Temp2 = Икс(PopulationIndex, я+1); Расходы(PopulationIndex) = Расходы(PopulationIndex) + 100 * (Temp2 - Temp1^2)^2 + (Temp1 - 1)^2; конецконецвозвращаться
р
Расширения
BBO был расширен до шумных функций (то есть функций, оценка пригодности которых искажена шумом);[21] ограниченные функции;[22] комбинаторные функции;[23] и многоцелевые функции.[24][25]Кроме того, был реализован алгоритм многоцелевой оптимизации (μBiMO) на основе микробиогеографии: он подходит для решения многоцелевых оптимизаций в области промышленного дизайна, поскольку основан на небольшом количестве островов (отсюда и название μBiMO), т.е. требуется несколько вызовов целевой функции.[26]
Математический анализ
BBO был математически проанализирован с использованием марковских моделей.[27] и модели динамических систем.[28]
Приложения
Ученые применяют BBO в различных академических и промышленных приложениях. Они обнаружили, что BBO работает лучше, чем современные методы глобальной оптимизации.
Например, Wang et al. доказал, что BBO продемонстрировал равные характеристики с FSCABC, но с более простыми кодами.[29]
Ян и др. показал, что BBO превосходит GA, PSO и ABC.[30]
Рекомендации
- ^ Куаммен, Д. (1997). Песня Додо: биогеография острова в эпоху исчезновения. Скрибнер.
- ^ Саймон, Д. (2008). «Оптимизация на основе биогеографии» (PDF). IEEE Transactions по эволюционным вычислениям. 12 (6): 702–713. Дои:10.1109 / tevc.2008.919004.
- ^ а б MacArthur, R .; Уилсон, Э. (1967). Теория островной биогеографии. Издательство Принстонского университета.
- ^ а б Wesche, T .; Goertler, G .; Хуберт, В. (1987). «Модифицированная модель индекса пригодности среды обитания для кумжи в юго-восточном Вайоминге». Североамериканский журнал управления рыболовством. 7 (2): 232–237. Дои:10.1577 / 1548-8659 (1987) 7 <232: mhsimf> 2.0.co; 2.
- ^ Де Йонг, К. (1975). Анализ поведения одного класса генетических адаптивных систем (Кандидат наук.). Университет Мичигана.
- ^ Muhlenbein, H .; Шлиеркамп-Воозен, Д. (1993). «Прогнозные модели для генетического алгоритма селекционеров: I. Непрерывная оптимизация параметров». Эволюционные вычисления. 1 (1): 25–49. Дои:10.1162 / evco.1993.1.1.25.
- ^ Ma, H .; Саймон, Д. (2011). «Смешанная оптимизация на основе биогеографии для ограниченной оптимизации» (PDF). Инженерные приложения искусственного интеллекта. 24 (3): 517–525. Дои:10.1016 / j.engappai.2010.08.005.
- ^ Саймон, Д. (2013). Алгоритмы эволюционной оптимизации. Вайли.
- ^ а б Kundra, H .; Суд, М. (2010). «Поиск пути между странами с использованием гибридного подхода PSO и BBO» (PDF). Международный журнал компьютерных приложений. 7 (6): 15–19. Дои:10.5120/1167-1370.
- ^ Ма, Х. (2010). «Анализ равновесия моделей миграции для оптимизации на основе биогеографии» (PDF). Информационные науки. 180 (18): 3444–3464. Дои:10.1016 / j.ins.2010.05.035.
- ^ Чжан, Ю. (2015). «Патологическое обнаружение головного мозга при сканировании магнитно-резонансной томографии с помощью вейвлет-энтропии и гибридизации оптимизации на основе биогеографии и оптимизации роя частиц» (PDF). Прогресс в исследованиях в области электромагнетизма. 152: 41–58. Дои:10.2528 / pier15040602.
- ^ Бхаттачарья, А .; Чаттопадхьяй, П. (2010). «Гибридная дифференциальная эволюция с оптимизацией на основе биогеографии для решения экономичного распределения нагрузки». Транзакции IEEE в системах питания. 25 (4): 1955–1964. Bibcode:2010ITPSy..25.1955B. Дои:10.1109 / tpwrs.2010.2043270.
- ^ Ду, Д .; Саймон, Д .; Эргезер, М. (2009). «Оптимизация на основе биогеографии в сочетании с эволюционной стратегией и отказом от иммиграции» (PDF). Конференция IEEE по системам, человеку и кибернетике. Сан-Антонио, Техас. С. 1023–1028.
- ^ Эргезер, М .; Саймон, Д .; Ду, Д. (2009). «Оппозиционная оптимизация на основе биогеографии» (PDF). Конференция IEEE по системам, человеку и кибернетике. Сан-Антонио, Техас. С. 1035–1040.
- ^ Kundra, H .; Kaur, A .; Панчал, В. (2009). «Комплексный подход к оптимизации на основе биогеографии с аргументацией на основе конкретных случаев для изучения возможности подземных вод» (PDF). The Delving: журнал технологий и технических наук. 1 (1): 32–38.
- ^ Lohokare, M .; Pattnaik, S .; Devi, S .; Panigrahi, B .; Das, S .; Баквад, К. (2009). «Интеллектуальная оптимизация дискретных переменных на основе биогеографии». Всемирный конгресс по природе и биологически вдохновленным вычислениям. Коимбатур, Индия. С. 1088–1093. Дои:10.1109 / NABIC.2009.5393808.
- ^ Wang, G .; Guo, L .; Duan, H .; Wang, H .; Liu, L .; Шао, М. (2013). «Объединение поиска гармонии с оптимизацией на основе биогеографии для глобальной численной оптимизации». Журнал вычислительной и теоретической нанонауки. 10 (10): 2312–2322. Bibcode:2013JCTN ... 10,2312 Вт. Дои:10.1166 / jctn.2013.3207.
- ^ Wang, L .; Сюй, Ю. (2011). «Эффективный алгоритм оптимизации на основе гибридной биогеографии для оценки параметров хаотических систем». Экспертные системы с приложениями. 38 (12): 15103–15109. Дои:10.1016 / j.eswa.2011.05.011.
- ^ Саймон, Д .; Омран, М .; Клерк, М. «Оптимизация на основе линеаризованной биогеографии с повторной инициализацией и локальным поиском». Получено 6 сентября 2013.
- ^ "Bbo: оптимизация на основе биогеографии". 2014-09-18.
- ^ Ma, H .; Fei, M .; Саймон, Д .; Ю, М. «Оптимизация на основе биогеографии для шумных фитнес-функций». Получено 7 сентября 2013.
- ^ Рой, П .; Ghoshal, S .; Такур, С. (2010). «Оптимизация на основе биогеографии для оптимального потока энергии с несколькими ограничениями с выбросами и негладкой функцией затрат». Экспертные системы с приложениями. 37 (12): 8221–8228. Дои:10.1016 / j.eswa.2010.05.064.
- ^ Песня, Y .; Лю, М .; Ван, З. (2010). «Оптимизация на основе биогеографии для задач коммивояжера». Международная совместная конференция по вычислительным наукам и оптимизации. Хуаншань, Аньхой, Китай. С. 295–299.
- ^ Рой, П .; Ghoshal, S .; Такур, С. (2010). «Многоцелевой оптимальный поток энергии с использованием оптимизации на основе биогеографии». Компоненты и системы электроэнергетики. 38 (12): 1406–1426. Дои:10.1080/15325001003735176.
- ^ Di Barba, P .; Dughiero, F .; Mognaschi, M.E .; Савини, А .; Виак, С. (2016). «Оптимизация многоцелевого использования на основе биогеографии и проектирование МЭМС». IEEE Transactions on Magnetics. 52 (3): 1–4. Bibcode:2016ITM .... 5288982D. Дои:10.1109 / TMAG.2015.2488982.
- ^ Mognaschi, M.E. (2017). «Многоцелевая оптимизация на основе микробиогеографии для промышленного электромагнитного дизайна». Письма об электронике. 53 (22): 1458–1460. Дои:10.1049 / эл.2017.3072.
- ^ Саймон, Д .; Эргезер, М .; Ду, Д .; Рарик, Р. (2011). «Марковские модели для оптимизации на основе биогеографии» (PDF). Транзакции IEEE по системам, человеку и кибернетике - Часть B: Кибернетика. 41 (1): 299–306. Дои:10.1109 / tsmcb.2010.2051149. PMID 20595090.
- ^ Саймон, Д. (2011). «Модель динамической системы оптимизации на основе биогеографии» (PDF). Прикладные мягкие вычисления. 1 (8): 5652–5661. Дои:10.1016 / j.asoc.2011.03.028.
- ^ Ван, С. (2015). «Классификация фруктов с помощью вейвлет-энтропии и нейронной сети прямого распространения, обученной с помощью Хаотической ABC в масштабе фитнеса и оптимизации на основе биогеографии». Энтропия. 17 (8): 5711–5728. Bibcode:2015 Энтрп..17.5711Вт. Дои:10.3390 / e17085711.
- ^ Ян, G .; Ян, Дж. (2015). «Автоматическая классификация изображений мозга с использованием вейвлет-энергии и оптимизации на основе биогеографии». Мультимедийные инструменты и приложения. 75 (23): 15601–15617. Дои:10.1007 / s11042-015-2649-7.