Аннотация: Алгоритм интеллектуальной оптимизации, также известный как современный эвристический алгоритм, представляет собой алгоритм с производительностью глобальной оптимизации, высокой универсальностью и подходит для параллельной обработки. Эта статья в основном дает вам подробную интерпретацию генетического алгоритма и алгоритма муравьиной колонии.
Эта статья опубликована в сообществе HUAWEI CLOUD.«Алгоритм интеллектуальной оптимизации (1) — генетический алгоритм», Автор оригинала: Я большой арбуз.
Алгоритм интеллектуальной оптимизации, также известный как современный эвристический алгоритм, представляет собой алгоритм с производительностью глобальной оптимизации, высокой универсальностью и подходит для параллельной обработки. Этот тип алгоритма обычно имеет строгую теоретическую основу, а не опирается исключительно на опыт экспертов, он теоретически может найти оптимальное решение или приблизить оптимальное решение за определенный период времени. Обычно используемые интеллектуальные алгоритмы оптимизации: генетический алгоритм, алгоритм имитации отжига, алгоритм поиска табу, алгоритм роя частиц, алгоритм муравьиной колонии.
Эта статья в основном дает вам подробную интерпретацию генетического алгоритма и алгоритма муравьиной колонии.
1. Генетический алгоритм
Генетический алгоритм (ГА), моделирующий генетику и эволюцию организмов в естественной среде.адаптивный(Адаптивная настройка генетических параметров)Глобальная оптимизация(Случайная мутация постоянно находит глобальное оптимальное решение) алгоритм, основная идея которого заключается в «выживании наиболее приспособленных», это наиболее широко используемый и наиболее эффективный алгоритм интеллектуальной оптимизации.
1.1 Метод кодирования
Модель алгоритма выполняет двоичное кодирование (кодирование 01), кодирование натуральных чисел, кодирование действительных чисел и кодирование дерева для индивидуума (решение). При расчете пригодности индивидуума требуется декодирование для реализации взаимного преобразования между пространством решения задачи и пространством поиска алгоритма.
1.2 Фитнес-функция
У каждого человека есть фитнес-функция (фитнес), которая количественно оценивает плюсы и минусы индивидуума.Функция фитнеса является основой для алгоритма выполнения «выживания наиболее приспособленных и выживания наиболее приспособленных». Фитнес-функцию необходимо установить в соответствии с целевой функцией, пусть g(x)g(x) представляет собой целевую функцию, пусть G(x)G(x) представляет фитнес-функцию из целевой функции g(x)g(x) отображается в фитнес-функцию G(x)G(x) процесс называетсяКалибровка.
Для задачи максимальной оптимизации g(x) может быть непосредственноg(x) задается как фитнес-функция G(x)G(x), то есть G(x)=g(x)G(x)=g(x); для задачи минимальной оптимизации G(x)=-\min g(x)G(x)=−min_g_(x); в генетическом алгоритме функция пригодности является положительным значением, но две приведенные выше формулы не могут быть гарантированы, поэтому необходимо добавить минимальное или максимальное значение и кусочную функцию.
1.3 Выберите действие
Отбор заключается в отборе из текущей популяции особей с большим значением функции приспособленности, которые могут быть использованы в качестве родителей для выведения следующего поколения.Чем выше индивидуальная функция пригодности, тем больше вероятность быть выбранным в качестве родителя.(возможный!)
Алгоритмов выбора много, самый простой — алгоритм рулетки:
P_i =\frac{F_i}{\sum_{i=1}^{N}F_i}Pi_=∑_i=1_N__Fi__Fi_
Среди них P_i_Pi_представляет вероятность выбора индивидуума; F_i_Fi_представляет значение фитнес-функции индивидуума; N_N_ представляет размер популяции.
Разделите дисковое колесо на N_N_ частей в соответствии с вероятностью выбора P_i_Pi_, а центральный угол i_i_го сектора равен 2\pi P_i2_πPi_. Случайным образом сгенерируйте число r_r_, которое подчиняется равномерному распределению между 0 и 1, а совокупная вероятность попадания в i_i_th сектор равна Q_i = \sum_{j=1}^i P_j_Qi_=∑_j_=1_i__Pj_, затем выберите отдельные i_i_ , повторяющиеся N_N_ раз, могут быть выбраны N_N_ лиц.
1.4 Кроссовер
Две особи рекомбинируют, чтобы произвести новых особей путем обмена частью хромосомных генов посредством кроссинговера, то есть генерируются новые решения. Перед кроссовером требуется случайное спаривание.
Как правило, метод пересечения точек используется для двоично-кодированных лиц, то есть одна или несколько точек пересечения выбираются случайным образом между двумя парными строками, и некоторые подстроки обмениваются для создания новой строки.
Выполняют ли два человека операцию кроссовера, определяется вероятностью кроссовера,Более высокая вероятность кроссовера может заставить генетический алгоритм генерировать больше новых решений, поддерживать разнообразие популяции и предотвращать преждевременное созревание алгоритма., обычно около 0,9.
1.5 Операция мутации
Биологическая эволюция, может произойти определенная мутация хромосомного гена (мутация), что приведет к появлению новой хромосомы, что является еще одним важным способом создания нового решения.Операция кроссовера эквивалентна глобальному исследованию, а операция мутации эквивалентна локальному развитию, что также является двумя необходимыми возможностями поиска для интеллектуальных алгоритмов оптимизации..
Сможет ли особь мутировать, зависит от вероятности мутации: если она слишком мала, некоторые полезные гены не смогут войти в хромосому, и качество решения не может быть улучшено, если она слишком велика, то потомство потеряет отличные гены родителя, в результате чего алгоритм теряет способность учиться на прошлом опыте поиска, вероятность мутации составляет около 0,005.
Примечательно,Рудольф доказал с помощью теории корреляции цепей Маркова, что генетический алгоритм, использующий только операции отбора, скрещивания и мутации, не может сходиться к глобальному оптимальному решению, в то время как генетический алгоритм, использующий стратегию удержания элиты, глобально сходится..
Общий поток алгоритма показан на рисунке ниже:
1.6 Анализ алгоритма
Ключ к хорошему интеллектуальному алгоритму лежит в балансе между возможностями глобального исследования и локальной разработки. Цель глобального исследования — провести более всестороннее исследование пространства решений, а основная цель локального развития — выполнить более точный поиск в известной области, надеясь получить новые решения лучшего качества.
Генетические алгоритмы могут достичь баланса между глобальными исследованиями и местным развитием, устанавливая давление отбора. На начальном этапе работы алгоритма установка небольшого давления отбора может улучшить способность алгоритма к глобальному исследованию и выполнять поиск по обширной области; на более позднем этапе алгоритма установка большого давления отбора может заставить алгоритм выполнять относительно хороший локальный поиск.
Настройка давления выбора может быть откалибрована и выбрана с помощью фитнес-функции.
При калибровке фитнес-функции на ранней стадии алгоритма следует сузить индивидуальный разрыв в пригодности и уменьшить скорость исключения; на заключительном этапе работы алгоритма индивидуальный разрыв в пригодности следует расширить, чтобы гарантировать, что алгоритм может выполнять централизованный поиск в соответствующей области решения людей с высокой физической подготовкой и ускорять скорость сходимости алгоритма. Общие методы:
-
Линейное масштабирование H= aF+b_H_=aF+b
-
\sigma_σ_truncation H= F+(\hat F - c\sigma)H=F+(F^ -_ Cσ_)
-
Преобразование масштабирования по степенному закону H= F^\alpha_H_=Fα
Стратегия отбора, низкое давление отбора может выбрать различные типы людей, усилить поиск неизвестных областей решения и избежать попадания алгоритма в локальные экстремальные значения, но скорость оптимизации алгоритма станет медленной; высокое давление отбора может выбрать отличных людей, ускорить скорость оптимизации, но разнообразие популяции уменьшится, что уменьшит вероятность нахождения глобального оптимума. Помимо алгоритма рулетки, стратегиями выбора являются:
-
градуированный метод отбора
-
Метод выбора турнира
-
Метод выбора Больцмана
2. Алгоритм муравьиной колонии
2.1 Алгоритм оптимизации муравьиной колонии
Алгоритм оптимизации колонии муравьев (ACO) представляет собой алгоритм моделирования, основанный на естественном биологическом мире, и его идея поглощает характеристики поведения колонии муравьев в процессе поиска пищи. Алгоритм муравьиной колонии показал хорошие результаты оптимизации в задаче TSP, задаче квадратичного распределения, задаче раскраски графа, задаче планирования транспортных средств, задаче балансировки нагрузки в коммуникационной сети и т. д.
Муравьи в природе не имеют зрения и зависят от феромона, испускаемого тем же видом в окружающей среде, чтобы решить, куда идти. феромона на маршруте число, чем больше и больше муравьев проходит маршрут, тем лучше формируется маршрут (этот маршрут не обязательно является кратчайшим, но его достаточно для NP-сложных задач).
2.1.1 Алгоритмическая модель
Возьмем в качестве примера задачу коммивояжера (TSP), которая в теории графов называется минимальной проблемой Гамильтона.
Пусть G = (V,E)G=(V,E) — взвешенный граф, V=(1,2,3,...,N)V=(1,2,3,...,N) — множество вершин, E_E_ — множество ребер, известно расстояние d_{ij}_dij_ между вершинами (d_{ij}>0,d_{ii}=\infty,i,j\in V)( _dij_> 0,_dii_=∞,i,j_∈_V), установить x_{ij} = 1, если (i,j) находится на оптимальном цикле, иначе 0_xij_=1, если (i,j) на оптимальном цикле, иначе 0
Тогда классическая проблема TSP может быть выражена следующим образом:
\min Z =\sum_{i=1}^{n}\sum_{j=1}^{n}d_{ij}x_{ij}min_Z_=i=1∑_n__j_=1∑_n__dij__xij_
С учетом следующих ограничений:
-
Ограничение 1: \sum_{j=1}^{n}x_{ij}=1, i\in V∑_j_=1_n__xij_=1,i_∈_V
-
Ограничение 2: \sum_{i=1}^{n}x_{ij}=1, j\in V∑_i_=1_n__xij_=1,j_∈_V
-
Ограничение 3: \ SUM_ {i \ in s} \ SUM_ {J \ INS} X_ {ij} \ LE | S | -1, \ FORALL S \ ПОДМНОЖЕСТВО Vς_I_ ∈_s_ σ_j_ ∈_s_ _xij_ ≤|_S_|-1, ∀ _s_⊂_v_
-
Ограничение 4: X_ {ij} \ IN \ {0, 1 \} _ xij_ ∈ {0,1}
Где | s | |_s_| — количество вершин, содержащихся в наборе; ограничения 1 и 2 — только одна сторона каждой точки, то есть существует только один оптимальный маршрут между любыми двумя точками; ограничение 3 Гарантируется, что существует нет производства.
Когда d_{ij} = d_{ji}_dij_=dji_ задача называется симметричной ЗК, когда для всех 1\le i, j,k \le n1≤_i,j,k_≤_nКогда существует неравенство d_{ij}+d_{jk}\ge d_{ik}_dij_+_djk_≥_dik_, говорят, что задача удовлетворяет неравенству треугольника, обозначаемому как \DeltaΔTSP. Неравенство треугольника выполняется во многих случаях, и даже если оно не выполняется, его можно преобразовать в форму замыкания, чтобы найти эквивалентное оптимальное решение TSP.
Базовая модель алгоритма оптимизации муравьиной колонии:
1. Муравьиная колония всегда находит решение с минимальными затратами.
2. У муравьев есть память, они хранят информацию о текущем пути, строят допустимое решение, оценивают качество решения и отслеживают путь в обратном направлении.
3. Муравьи в текущем состоянии могут перемещаться в любую точку допустимой области.
4. Каждому муравью присваивается начальное состояние и несколько условий завершения.
5. Муравей рекурсивно строит решение от начального состояния до допустимого состояния предметной области, и процесс построения заканчивается, когда один муравей удовлетворяет хотя бы одному условию завершения.
6. Муравей перемещается к узлу домена в соответствии с определенным вероятностным решающим правилом.
7. Траектория феромона обновляется после перемещения, процесс называется «одноэтапное онлайн-обновление феромона».
8. Как только решение построено, муравьи следуют исходному пути и обновляют траекторию феромона, что называется «онлайн отложенное обновление феромона».
2.1.2 Анализ алгоритма
Сложность алгоритма O(nc\cdot n^2\cdot m)O(nc_⋅_n_2⋅_m), m — количество муравьев, nc — количество итераций или поисков, n — количество вершин. На эффект работы алгоритма влияют такие параметры, как \alpha, \beta_α_, _beta_, среди которых \beta_beta_ отражает постоянство траектории феромона.Если значение слишком мало, информация исчезает слишком быстро, если значение слишком большой, легко попасть в точку локального оптимума, поэтому его значение обычно составляет около 0,7.
В базовом алгоритме оптимизации муравьиной колонии он может комбинироваться с другими эвристическими алгоритмами.Наиболее типичным из них является встроенный алгоритм локального поиска.После того как каждый муравей формирует свой собственный маршрут, он использует метод локальной корректировки (2-opt, 3-opt Улучшение, кроме того, дает некоторый эффект в сочетании с генетическим алгоритмом, симулированным отжигом и табу-поиском.
Основные этапы алгоритма оптимизации гибридной муравьиной колонии:
1. Begin
2. Инициализация муравья;
3. ПЕТЛЯ:
4. Построение пути \quad ant;
5. \quad реализует алгоритм локального поиска муравья
6. Обновление траектории муравья \quad
7. \quad Если число итераций не достигнуто, перейти к LOOP;
8. Выведите текущее лучшее решение
9. End
Нажмите «Подписаться», чтобы впервые узнать о новых технологиях HUAWEI CLOUD~