Иногда «достаточно хорошо» достаточно.
Оптимизировать проблему означает найти лучшее возможное решение для той же самой или просто максимизировать или минимизировать проблему. Конечно, оптимизировать сложные алгоритмы непросто - довольно далеко от этого, но вдохновляющие решения привели к появлению нескольких интересных подходов к одной и той же метаэвристической процедуре.
Метаэвристика позволяет нам находить оптимизированные решения наиболее сложных проблем за счет включения следующих компонентов:
- Интенсификация и диверсификация
- Эксплуатация и разведка
Сложный баланс между ними может обеспечить конвергенцию около глобальных оптимумов, с чем борются классические неэвристические методы оптимизации, особенно если они застревают вблизи локальных оптимумов.
Однако к этому современному методу оптимизации следует относиться с недоверием; не все алгоритмы основаны на точной математике и надежной литературе. Ниже мы рассмотрим некоторые популярные метаэвристические техники и постараемся оценить их новизну.
Генетический алгоритм
Генетический алгоритм - это тип эволюционного алгоритма, вдохновленный теорией эволюции и естественного отбора Дарвина. Генетические алгоритмы в целом состоят из следующих этапов:
- Инициализация: алгоритм инициируется начальной «популяцией», каждый член обозначает решение возникшей проблемы.
- Выбор: функция фитнеса используется для определения того, насколько человек «подходит». Этот порог имитирует «выживание наиболее приспособленных», но отбирает для воспроизведения или кроссовера только тех членов, которые считаются подходящими.
- Кроссовер: новая популяция создается из выбранных особей с использованием различных точек кроссовера и техник спаривания.
- Мутация: некоторые особи подвергаются небольшим мутациям после кроссовера. Эти измененные «гены» подтверждают разнообразие и иногда гарантируют, что конвергенция не застрянет на локальных оптимумах.
Вышеупомянутый процесс продолжается до популяции, которая очень похожа на предыдущую. Эта сходимость используется как решение данной проблемы. Даже для скептиков и отрицателей увлекательного явления под названием «эволюция» ГА могут предоставить «достаточно хорошие» решения трудных проблем. Некоторые примеры - это NP-полные задачи, такие как задача о рюкзаке, упаковка корзины и раскраска графиков.
Оптимизация колонии муравьев
Используя опасную комбинацию феромонов и математики, алгоритмы оптимизации муравьиной колонии помогают достичь весьма замечательных оптимизаций с использованием искусственных муравьев и феромонов для смещения стохастического процесса для установки параметров как компонентов графа. Он вдохновлен крошечными рабочими, которые оставляют следы феромонов вдоль троп, на которых они находят пищу, в конечном итоге ограничивая переход муравьев на лучший путь - путь обжорства. В общих чертах алгоритм ACO можно описать с помощью задачи Коммивояжер следующим образом:
- Каждый муравей начинается со случайной вершины (или города)
- На каждой итерации задачи каждый муравей посещает город на краю графа и сохраняет маршрут в памяти.
- Муравьи избегают пути, ведущего в города, которые уже были посещены, но перемещаются в каждый город на графике, вероятностно выбирая край - в зависимости от количества феромона, связанного с путем. Чем выше количество феромонов, связанных с путем, тем выше шанс, что муравей выберет его. Однако для каждой итерации значение феромона уменьшается на процент.
- Решение создается для каждого муравья после его посещения. Маршруты феромонов назначаются дополнительно в зависимости от качества раствора.
Эти процессы повторяются до тех пор, пока решение не сойдется или не будет выполнено условие завершения. Алгоритмы ACO широко используются во многих областях, особенно в областях маршрутизации транспортных средств, планирования и постановки задач.
Искусственная пчелиная колония
Медоносные пчелы принадлежат к чрезвычайно умному рою, чья разделенная на секции иерархия вместе с невероятным механизмом виляющего танца делает их методы добычи пищи очень эффективными. Помимо того, что они талантливы в географии и танцах, пчелы также ответственны за 80% пищи, которую мы едим. Учитывая глобальный климатический кризис, пчелы уже находятся под угрозой исчезновения, и сокращение их численности имеет ужасные последствия. This может помочь вам с определенным контекстом и с тем, что мы можем сделать, чтобы спасти энтузиазм природы.
Алгоритм ABC использует три типа пчел:
- Работающие пчелы: они танцуют вокруг своего источника пищи. После того, как их источник пищи покинут, их переводят как рабочих.
- Зрители: они выбирают источники пищи на основе танцев работающих пчел.
- Разведчики / Рабочие: они делают первые открытия источников пищи.
В ABC количество источников пищи представляет собой количество возможных решений проблемы, их положение обозначает решение проблемы, а количество нектара является функцией приспособленности (качество решения). Каждая используемая пчела связана с одним кормом. источник (решение).
Initialization Phase REPEAT Employed Bees Phase Onlooker Bees Phase Scout Bees Phase Memorize the best solution achieved so far UNTIL(Cycle=Maximum Cycle Number or a Maximum CPU time)
Вышеупомянутый алгоритм просто описывает шаги для ABC. Этот метод оптимизации не только подтверждает, насколько хороши пчелы, но также применяется в таких задачах, как обучение нейронной сети для задачи XOR, структурная оптимизация и т. Д.
Некоторые другие крутые алгоритмы
Для краткости, вот список других метаэвристических алгоритмов, основанных на популяциях:
- Оптимизация роя частиц
- Имитация отжига
- Империалистический конкурентный алгоритм (старший брат генетического алгоритма, социальный алгоритм)
- Алгоритм оптимизации каракатицы
Несмотря на все его недостатки, метаэвристические подходы довольно хороши. Не углубляясь в математику того же самого, эта статья была нацелена на то, чтобы напомнить себе, как метафорическое и вдохновенное решение сложных проблем может быть новым. Также, как иногда бывает достаточно хорошо, достаточно хорошо.
использованная литература
Https://in.mathworks.com/help/gads/what-is-the-genetic-algorithm.html
Https://www.sciencedirect.com/science/article/pii/S2405656115000723
Https://en.wikipedia.org/wiki/Ant_colony_optimization_algorithms
Https://en.wikipedia.org/wiki/List_of_metaphor-based_metaheuristics
