Генетический алгоритм: природа в действии для оптимизации сложных задач (c примером на java)

Генетические алгоритмы (ГА) — это мощный инструмент для решения задач оптимизации, вдохновленный процессами эволюции в природе. Они применяются в таких областях, как маршрутизация, машинное обучение, финансовая аналитика, проектирование и многие другие. В этой статье я разберу принцип работы ГА и приведу пример решения, одной из самых популярных задач в алгоритмах на языке Java. Алгоритм основан на модели эволюции Дарвина. Его ключевые компоненты:

https://habr.com/ru/articles/861334/

#алгоритмы #структуры_данных #обучение_программированию #генетический_алгоритм #java #программирование #обучение #структуры_данных_задач #алгоритмы_поиска_пути #алгоритмы_на_графах

Муравьиный алгоритм. Решение задачи коммивояжера

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

https://habr.com/ru/articles/848590/

#алгоритмы #задача_коммивояжера #муравьиный_алгоритм #графы #golang #комбинаторная_оптимизация #эвристические_алгоритмы #алгоритмы_на_графах #транспортные_задачи #go

Эволюционный алгоритм для проверки планарности графов

В работе рассматривается приближенный алгоритм проверки планарности графов. В процессе работы алгоритма строится изображение графа c минимальным количеством пересечений рёбер. Алгоритм эффективно решает перечисленные задачи. Можно сделать обобщенный вывод о том, что эволюционный алгоритм эффективен для решения оптимизационных задач геометрии. Вычислительная сложность алгоритма определяется как , где – количество итераций алгоритма, – размер популяции (задаётся пользователем), – количество рёбер графа.[1]

https://habr.com/ru/articles/843342/

#граф #планарность #визуализация_графа #алгоритмы_на_графах #эволюционный_алгоритм #генетические_алгоритмы

[Перевод] Эвристики морских просторов: математическая оптимизация океанских контейнеровозов

Такие контейнеровозы называют «post-Panamax», потому что они слишком велики, чтобы поместиться в Панамском канале Посмотрите вокруг. Есть высокая вероятность того, что какие-то из окружающих вас предметов прибыли к вам по морю. 90% товаров в мире перемещается по океану, зачастую на ужасно огромных грузовых судах: длина четыреста метров, масса 250 тысяч тонн, вмещают в себя 12 тысяч контейнеров суммарной стоимостью в миллиард долларов. В отличие от самолётов, поездов и грузовых автомобилей, грузовые суда работают практически непрерывно, двигаясь по цикличным маршрутам в океанах. Но какими же будут наилучшие, наиболее оптимальные маршруты таких судов? Для специалиста по computer science это задача из теории графов; для бизнес-аналитика — это задача цепочки поставок. Если её решить плохо, то контейнеры будут простаивать в портах, суда впустую тратить время в открытом море, неспособные причалить, а в конечном итоге подорожают товары из-за того, что поток физических ценностей замедлится и станет менее предсказуемым. Каждой занимающейся контейнерными перевозками компании приходится справляться с этими задачами, но обычно они решаются по отдельности. При их комбинировании сложность умножается; насколько нам известно, эту задачу так пока и не удалось решить для самых крупных контейнерных операций (500 судов и 1500 портов). Команда Operations Research с гордостью представляет Shipping Network Design API , реализующий новое решение этой задачи. Наша методика лучше масштабируется, позволяя находить решения задач цепочек поставок общемирового уровня, будучи при этом быстрее, чем все остальные известные решения. Она способна удвоить прибыль компании-перевозчика, доставлять на 13% больше контейнеров, задействуя при этом на 15% меньше судов. В этой статье мы расскажем, как нам это удалось.

https://habr.com/ru/companies/ruvds/articles/820703/

#ruvds_переводы #контейнеровозы #алгоритмы_на_графах #грузоперевозки #оптимизация_перевозок #контейнерные_перевозки

[Перевод] Почему B-деревья быстрые?

B-дерево — это структура, помогающая выполнять поиск в больших объёмах данных. Она была изобретена более сорока лет назад, однако по-прежнему используется в большинстве современных баз данных. Хотя существуют и более новые структуры индексов, например, LSM-деревья, B-дерево пока никто не победил в обработке большинства запросов баз данных. После прочтения этого поста вы будете знать, как B-дерево упорядочивает данные и выполняет поисковые запросы.

https://habr.com/ru/articles/783012/

#btree #bдерево #индексация #базы_данных #алгоритмы_на_графах #двоичное_дерево_поиска