Муравьиный алгоритм

Решаем задачу коммивояжера приближенным методом, предложенным Марко Дориго (Marko Dorigo). Ребрам полного графа К5 приписываем длины и уровень феромона. Потом запускаем "муравья", который выбирает свой путь в зависимости от дальности города и уровня феромона. А уровень феромона определяется популярностью этого направления. Пройдя весь путь (каждая вершина проходится по одному разу), муравей оставляет феромон тем большего уровня, чем короче был путь. В лекции использованы работы Сергея Штовбы (Украина) из журнала Exponenta Pro, 2003, и автора ("Графы в Maple").

[@mesmeridze1]

Потрясающий лектор. Институт закончил и периодически смотрю ролики. Очень помогли на сессиях.

[@RudolfKlotz]

Михаил Николаевич, огромное спасибо за интереснейшую лекцию!

[@denispotapenko5610]

Отличное видео! Действительно хороший "туториал" :) Причем и человека приятно слушать и по теме рассказывает понятно, и смежные темы также успевает затронуть :) Спасибо за материал, продолжайте в том же духе!

[@dionraiden4554]

Из других ВУЗов тоже вас смотрим, очень качественно изложен материал, спасибо.

[@met4ltech]

Спасибо большое за прекрасное пояснение!

[@AnonExpert1]

Очень круто и понятно! Познакомился с вашими лекциями ещё на 1 курсе, сейчас 5 и снова актуально :)

[@user-jz6ug6do6g]

Все очень понятно. Спасибо большое.

[@MrProband]

Спасибо за Ваш ответ.

[@user-sg8dd1bq4m]

Спасибо большое за видео, очень полезное. Все четко и ясно. Приятно было слушать.

[@user-nr4uj8gc5j]

Ничего не понятно, но Ооооочень интересно😂 игнорирований само значение слова «алгоритм», как «порядок действий». При выборе каждого параметра ещё куча «но» присутствует. Короткий маршрут не бери, так жадные комерсы делают, на длинный не иди, так муравьи не советуют🤪🤪🤪🤣

[@FunFearShow]

Большое спасибо! помогли при написании курсовой )

[@pavellyakh5598]

Спасибо! Шикарное видео. Юмор про элиту на высоте! Учился у Белоусова А.И. в МГТУ, как и Вы он очень умный преподаватель, у него шутки тоже на высоте, но донесение материала мне больше Ваше нравится.

[@Ramooo25]

доступно,спасибо

[@meow_kis]

Спасибо большое! Очень помогли при подготовке к контрольной по эволюционным вычислениям!

[@happysandbox4085]

Я думал тут один из 2020😃

[@APL375]

Да ладно, не ёрничайте! Я говорю о том, что делать человеку нечего как проверять ваши расчеты. Главное - это идея. А тема раскрыта великолепно. Благодарю.

[@SadMelvin]

Спасибо!

[@user-kf8oq4gz3g]

Здорово, спасибо! : ) Единственное, наверное, что вы не упомянули - это условие остановки. Но тут уж можно найти, остальное было очень хорошо и очень понятно : )

[@xabikiqwe]

Спасибо. Диплом сделан. )))

[@Kirsanov2011]

Поздравляю!

[@ventilyator]

спасибо!

[@mozgotron12]

Блин, я тоже хочу себе такой галстук с синей лампочкой.

[@user-tz6zo2jl4i]

Спасибо большое за видео. Все четко и понятно. По вашему примеру реализовал алгоритм в game maker studio))по вашей примеру проход 1000 муравьев решает за пол секунды. С коррекцией ферамонов конечно сложновато. Приходится смотреть чего достигла 1000 и потом корректировать чтоб получилось более идеальное решение. Тут разве что делать отдельный алгоритм, который будет сам изменять значения коррекции феррамона для более оптимального решения

[@AlexNirt12]

5 х 4 х 3 х 2 = 120 вариантов на один город , спасибо за такие видео =))

[@OleksandrKravchuk-tg8yx]

Отличное объяснение. Смутило два момента: > для второй интерации сумарная вероятность, подсчитаная на доске, была ~93%, а не 100% > язык с - простой язык

[@tanyagnatyuk8268]

а какой коэффициент испарения лучше брать?

[@asd1qwe1]

норм мужик

[@DenisKozlov-MCP]

Спасибо, отличное видео! А вы будете Мультиагентные технологии рассматривать?

[@Kirsanov2011]

Ну, вот. Теперь ясно. Действительно, кое-что можно было и не расписывать. Ну это для тех, кто любит вычислять - фанатов чисел.

[@user-ii9xe4pu6x]

Здравствуйте! Я правильно понял, что в данном примере была показана одна итерация с одним муравьем?

[@denisfrolovru]

Первые 8 минут можно не смотреть - воду льет.

[@Walter_Sullivan]

Очень классная лекция! Доступно и подробно на пальцах объяснено применение этого алгоритма. Однако, сколько видео я не пересмотрел по этому алгоритму один вопрос так и остался непонятным - какой физический смысл у показателя феромона примирительно к какому нибудь реальному технологическому процессу? Например, если мы рассматриваем развозку почтовых бандеролей или развозку продуктов по магазинов? Также остаётся непонятен физический смысл процесса высыхания алгоритма Кроме того не совсем понятна операция с "шариком и рулеткой" - даже с учётом неравномерной вероятности выпасть может любой из городов (если он уже не был посещен конечно) и таким образом перебирать нужно все равно все итерации - тогда есть ли смысл в этой "рулетке"? Либо можно сославшись на наибольшую вероятность автоматически выбрать путь с наибольшей же вероятностью, но тогда все равно рулетка отпадает как механизм

[@MrSkySerfeR]

На 27-28 минутах видео при подсчёте вероятности того, что муравей пойдёт из города №4 в город №5 ( P4,5) допущена ошибка. Значение которое должно получиться 29.38747419. Наверняка это "описка". Сумма этих трёх вероятностей должна равняться 100, у Вас же она равняется 94, и это бросается в глаза.

[@mozgotron12]

Как отличить физика от математика? Всё просто: попросите его обойти столб кругом. Если спросит: "Зачем?" - значит физик. Если спросит: "По часовой стрелке или против?" - значит математик.

[@igorek9191]

Насчет обновления феромона. Если мы нашли новое решение, хуже старого, то соответственно нам лучше это решение "забыть". Получается обновлённый феромон нужно считать (1-р) * (t + delta t). Т.е. коэффициент испарения применять к обновлённому решению, а не к старому, прибавляя потом дельта тау...?

[@Kirsanov2011]

+Игорь Власюк "Высыхает" путь всегда, и хороший и плохой.

[@Kirsanov2011]

Ничего не понял! Это по-русски?

[@happysandbox4085]

Доброго времени суток! Мне интересно, прошло 7 лет, сейчас на вскидку того времени собрали все компьютеры в один(на данный момент самый слабый из теперешнего) и какие ваши впечатления, уже пробовали для себя реализовать вычисления Хамилтона?)) Спасибо за разъяснения!

[@Kirsanov2011]

Пробовали. Все отлично.

[@andreyhalushko4923]

норм

[@vandriichuk]

Очень интересно. Но не понял откуда изначально взялась длина расстояний и кол-во ферономов для каждого участка? Особенно, откуда изначально взялись значения феромонов для каждого отрезка?

[@Kirsanov2011]

Обычно начальные феромоны - случайные числа. А расстояния - даны по условию, например, расстояния между реальными объектами.

[@vandriichuk]

@@Kirsanov2011 подскажите, пожалуйста, я исследую взаимосвязи между алгоритмом муравьиной колонкии и reinforcement learning. Вы не сталкивались с информацией на эту тему? Может где-то есть что-то почитать? И еще я работаю над автоматизацией подбора параметров альфа и бета для муравьиной колонии. Ничего такого не встречали?

[@user-lw3tr6in3x]

Здравствуйте! Я внимательно прослушал, возникли вопросы: 1) чему равно Q 2) ответ в задаче какой? 3) мы явно один раз не прогоняем муравья, значит другие тоже бегают и выбирают путь, значит есть и другие пути? 4) когда выходить с цикла? С момента постоянного значения?

[@Kirsanov2011]

+виктор коледин 1) Q обычно подбирается экспериментально. Тут вообще классической науки еще мало, мало что строго доказано - больше опыт и интуиция... 2) Ответ - длина пути 3) есть и другие пути. Ищем минимальный 4) Выходить, когда "устаканится". Т.е. разность достигнет необходимой точности

[@user-lw3tr6in3x]

Муравьиный алгоритм оказал на меня большой интерес. Если бы еще эти константы знать я понимаю, что все экспериментально, но вот реализация .... Спасибо за ответ, вы очень полезную работу делаете это большой плюс для нас всех интересующихся алгоритмами, книга ваша книга Графы в Maple очень ценная все там понятно и ясно.

[@Kirsanov2011]

+виктор коледин Спасибо! Жаль там есть опечатки(но они очевидны и легко исправляются), на сайте своем (она там вложена) я стараюсь их исправлять... Еще одно замечание. Программы написаны в Maple 8, иногда в след версиях не работают, надо чуть исправить объявление with пакетов... Я как нибудь это сделаю централизованно...

[@user-lw3tr6in3x]

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

[@user-qb4sn5xr7d]

Я, вот только, одного не понял. Каким образом были выбраны "стартовые значения" тау?

[@Kirsanov2011]

Константин Приб В учебных целях произвольно. Да и в настоящих исследованиях тоже, но только там они мало все друг от друга отличаются. Настоящей теории выбора нет. Эксперимент. Но опыт показывает, что начальная картина быстро затирается и от нее мало что зависит.

[@sergeykodzha2621]

так откуда начальные значения феромонов брать? Если начинать с нулевых значений, все вероятности будут тоже 0.

[@Kirsanov2011]

Начальное распределение - случайное. И здесь важно качество псевдослучайных чисел.

[@Kirsanov2011]

Да. Осенью. Пока готовлю еще...

[@f0cus570]

Что за феромоны ? Я так и не понял Как их высчитать ?

[@Kirsanov2011]

просто назначить

[@f0cus570]

@@Kirsanov2011 если просто взять рандомные феромоны, то решение будет далеко от точного, верно?

[@Kirsanov2011]

Нет. Как раз это лучше для начального распределения. А потом уж путь муравьи оставляют свой след (феромоны) строго по правилу - чем длиннее путь, тем меньше феромонов. Тогда какой нормальный муравей пойдет по слабо затоптанному пути? Пойдет туда, где путь короче, а след толще. Не забывайте, что циклов должно быть много. Да еще и элитные муравьи делают свое дело.

[@user-ec8ui3ch9r]

Муравьи коммуниcты кcта, мораль - думайте cами

[@user-ex1wi2jr5b]

А у муровьев социолизм))

[@APL375]

не впадлу ж те было складывать)

[@igorek9191]

Псевдо кода нет на алгоритм?

[@Kirsanov2011]

+Игорь Власюк Игорь! Зачем? См. мою опубликованную программу для Maple в моей книге "Графы в Maple". В сети книга есть на eqworld.ru кажется

[@igorek9191]

+Kirsanov2011 спасибо, нашёл.

[@ivankumets4521]

ошибка в вычислениях садись два

[@Kirsanov2011]

На какой минуте?

[@aliyamaliya587]

Главное понятно как всё делать. А ошибки в вычислениях не важны, хотя я не проверяла, может их вообще нет

[@user-jz6ug6do6g]

любитель ловли мух

[@Kirsanov2011]

Куда садиться? За что?!

[@user-sd3jz9sq3d]

Очень сложно воспринимать таких преподов. Что то мямлит.

[@Kirsanov2011]

Да, у меня есть недостатки. Буду преодолевать.

[@aalex1812]

Спасибо!