Муравьиный алгоритм
Решаем задачу коммивояжера приближенным методом, предложенным Марко Дориго (Marko Dorigo). Ребрам полного графа К5 приписываем длины и уровень феромона. Потом запускаем "муравья", который выбирает свой путь в зависимости от дальности города и уровня феромона. А уровень феромона определяется популярностью этого направления. Пройдя весь путь (каждая вершина проходится по одному разу), муравей оставляет феромон тем большего уровня, чем короче был путь. В лекции использованы работы Сергея Штовбы (Украина) из журнала Exponenta Pro, 2003, и автора ("Графы в Maple").
Пікірлер: 71
Потрясающий лектор. Институт закончил и периодически смотрю ролики. Очень помогли на сессиях.
Михаил Николаевич, огромное спасибо за интереснейшую лекцию!
Из других ВУЗов тоже вас смотрим, очень качественно изложен материал, спасибо.
Отличное видео! Действительно хороший "туториал" :) Причем и человека приятно слушать и по теме рассказывает понятно, и смежные темы также успевает затронуть :) Спасибо за материал, продолжайте в том же духе!
Спасибо большое за прекрасное пояснение!
Все очень понятно. Спасибо большое.
Очень круто и понятно! Познакомился с вашими лекциями ещё на 1 курсе, сейчас 5 и снова актуально :)
Большое спасибо! помогли при написании курсовой )
Спасибо за Ваш ответ.
Спасибо большое за видео, очень полезное. Все четко и ясно. Приятно было слушать.
@user-nr4uj8gc5j
3 жыл бұрын
Ничего не понятно, но Ооооочень интересно😂 игнорирований само значение слова «алгоритм», как «порядок действий». При выборе каждого параметра ещё куча «но» присутствует. Короткий маршрут не бери, так жадные комерсы делают, на длинный не иди, так муравьи не советуют🤪🤪🤪🤣
Да ладно, не ёрничайте! Я говорю о том, что делать человеку нечего как проверять ваши расчеты. Главное - это идея. А тема раскрыта великолепно. Благодарю.
Спасибо! Шикарное видео. Юмор про элиту на высоте! Учился у Белоусова А.И. в МГТУ, как и Вы он очень умный преподаватель, у него шутки тоже на высоте, но донесение материала мне больше Ваше нравится.
Спасибо. Диплом сделан. )))
Спасибо большое! Очень помогли при подготовке к контрольной по эволюционным вычислениям!
@happysandbox4085
4 жыл бұрын
Я думал тут один из 2020😃
Блин, я тоже хочу себе такой галстук с синей лампочкой.
Поздравляю!
Здорово, спасибо! : ) Единственное, наверное, что вы не упомянули - это условие остановки. Но тут уж можно найти, остальное было очень хорошо и очень понятно : )
доступно,спасибо
Спасибо!
Первые 8 минут можно не смотреть - воду льет.
5 х 4 х 3 х 2 = 120 вариантов на один город , спасибо за такие видео =))
спасибо!
Спасибо, отличное видео! А вы будете Мультиагентные технологии рассматривать?
Спасибо большое за видео. Все четко и понятно. По вашему примеру реализовал алгоритм в game maker studio))по вашей примеру проход 1000 муравьев решает за пол секунды. С коррекцией ферамонов конечно сложновато. Приходится смотреть чего достигла 1000 и потом корректировать чтоб получилось более идеальное решение. Тут разве что делать отдельный алгоритм, который будет сам изменять значения коррекции феррамона для более оптимального решения
Отличное объяснение. Смутило два момента: > для второй интерации сумарная вероятность, подсчитаная на доске, была ~93%, а не 100% > язык с - простой язык
норм мужик
а какой коэффициент испарения лучше брать?
Как отличить физика от математика? Всё просто: попросите его обойти столб кругом. Если спросит: "Зачем?" - значит физик. Если спросит: "По часовой стрелке или против?" - значит математик.
Здравствуйте! Я правильно понял, что в данном примере была показана одна итерация с одним муравьем?
Ничего не понял! Это по-русски?
Ну, вот. Теперь ясно. Действительно, кое-что можно было и не расписывать. Ну это для тех, кто любит вычислять - фанатов чисел.
На 27-28 минутах видео при подсчёте вероятности того, что муравей пойдёт из города №4 в город №5 ( P4,5) допущена ошибка. Значение которое должно получиться 29.38747419. Наверняка это "описка". Сумма этих трёх вероятностей должна равняться 100, у Вас же она равняется 94, и это бросается в глаза.
Очень классная лекция! Доступно и подробно на пальцах объяснено применение этого алгоритма. Однако, сколько видео я не пересмотрел по этому алгоритму один вопрос так и остался непонятным - какой физический смысл у показателя феромона примирительно к какому нибудь реальному технологическому процессу? Например, если мы рассматриваем развозку почтовых бандеролей или развозку продуктов по магазинов? Также остаётся непонятен физический смысл процесса высыхания алгоритма Кроме того не совсем понятна операция с "шариком и рулеткой" - даже с учётом неравномерной вероятности выпасть может любой из городов (если он уже не был посещен конечно) и таким образом перебирать нужно все равно все итерации - тогда есть ли смысл в этой "рулетке"? Либо можно сославшись на наибольшую вероятность автоматически выбрать путь с наибольшей же вероятностью, но тогда все равно рулетка отпадает как механизм
Доброго времени суток! Мне интересно, прошло 7 лет, сейчас на вскидку того времени собрали все компьютеры в один(на данный момент самый слабый из теперешнего) и какие ваши впечатления, уже пробовали для себя реализовать вычисления Хамилтона?)) Спасибо за разъяснения!
@Kirsanov2011
4 жыл бұрын
Пробовали. Все отлично.
А у муровьев социолизм))
Насчет обновления феромона. Если мы нашли новое решение, хуже старого, то соответственно нам лучше это решение "забыть". Получается обновлённый феромон нужно считать (1-р) * (t + delta t). Т.е. коэффициент испарения применять к обновлённому решению, а не к старому, прибавляя потом дельта тау...?
@Kirsanov2011
8 жыл бұрын
+Игорь Власюк "Высыхает" путь всегда, и хороший и плохой.
Я, вот только, одного не понял. Каким образом были выбраны "стартовые значения" тау?
@Kirsanov2011
9 жыл бұрын
Константин Приб В учебных целях произвольно. Да и в настоящих исследованиях тоже, но только там они мало все друг от друга отличаются. Настоящей теории выбора нет. Эксперимент. Но опыт показывает, что начальная картина быстро затирается и от нее мало что зависит.
норм
Очень интересно. Но не понял откуда изначально взялась длина расстояний и кол-во ферономов для каждого участка? Особенно, откуда изначально взялись значения феромонов для каждого отрезка?
@Kirsanov2011
2 жыл бұрын
Обычно начальные феромоны - случайные числа. А расстояния - даны по условию, например, расстояния между реальными объектами.
@vandriichuk
2 жыл бұрын
@@Kirsanov2011 подскажите, пожалуйста, я исследую взаимосвязи между алгоритмом муравьиной колонкии и reinforcement learning. Вы не сталкивались с информацией на эту тему? Может где-то есть что-то почитать? И еще я работаю над автоматизацией подбора параметров альфа и бета для муравьиной колонии. Ничего такого не встречали?
Здравствуйте! Я внимательно прослушал, возникли вопросы: 1) чему равно Q 2) ответ в задаче какой? 3) мы явно один раз не прогоняем муравья, значит другие тоже бегают и выбирают путь, значит есть и другие пути? 4) когда выходить с цикла? С момента постоянного значения?
@Kirsanov2011
8 жыл бұрын
+виктор коледин 1) Q обычно подбирается экспериментально. Тут вообще классической науки еще мало, мало что строго доказано - больше опыт и интуиция... 2) Ответ - длина пути 3) есть и другие пути. Ищем минимальный 4) Выходить, когда "устаканится". Т.е. разность достигнет необходимой точности
@user-lw3tr6in3x
8 жыл бұрын
Муравьиный алгоритм оказал на меня большой интерес. Если бы еще эти константы знать я понимаю, что все экспериментально, но вот реализация .... Спасибо за ответ, вы очень полезную работу делаете это большой плюс для нас всех интересующихся алгоритмами, книга ваша книга Графы в Maple очень ценная все там понятно и ясно.
@Kirsanov2011
8 жыл бұрын
+виктор коледин Спасибо! Жаль там есть опечатки(но они очевидны и легко исправляются), на сайте своем (она там вложена) я стараюсь их исправлять... Еще одно замечание. Программы написаны в Maple 8, иногда в след версиях не работают, надо чуть исправить объявление with пакетов... Я как нибудь это сделаю централизованно...
@user-lw3tr6in3x
8 жыл бұрын
я тоже вижу, но в основном эти опечатки мелочи, умный человек видит простой язык в первую очередь вот это привлекает, чем проще тем лучше.
Муравьи коммуниcты кcта, мораль - думайте cами
Да. Осенью. Пока готовлю еще...
так откуда начальные значения феромонов брать? Если начинать с нулевых значений, все вероятности будут тоже 0.
@Kirsanov2011
4 жыл бұрын
Начальное распределение - случайное. И здесь важно качество псевдослучайных чисел.
Что за феромоны ? Я так и не понял Как их высчитать ?
@Kirsanov2011
5 жыл бұрын
просто назначить
@f0cus570
5 жыл бұрын
@@Kirsanov2011 если просто взять рандомные феромоны, то решение будет далеко от точного, верно?
@Kirsanov2011
5 жыл бұрын
Нет. Как раз это лучше для начального распределения. А потом уж путь муравьи оставляют свой след (феромоны) строго по правилу - чем длиннее путь, тем меньше феромонов. Тогда какой нормальный муравей пойдет по слабо затоптанному пути? Пойдет туда, где путь короче, а след толще. Не забывайте, что циклов должно быть много. Да еще и элитные муравьи делают свое дело.
Псевдо кода нет на алгоритм?
@Kirsanov2011
8 жыл бұрын
+Игорь Власюк Игорь! Зачем? См. мою опубликованную программу для Maple в моей книге "Графы в Maple". В сети книга есть на eqworld.ru кажется
@igorek9191
8 жыл бұрын
+Kirsanov2011 спасибо, нашёл.
не впадлу ж те было складывать)
ошибка в вычислениях садись два
@Kirsanov2011
6 жыл бұрын
На какой минуте?
@aliyamaliya587
6 жыл бұрын
Главное понятно как всё делать. А ошибки в вычислениях не важны, хотя я не проверяла, может их вообще нет
@user-jz6ug6do6g
5 жыл бұрын
любитель ловли мух
@Kirsanov2011
2 жыл бұрын
Куда садиться? За что?!
Очень сложно воспринимать таких преподов. Что то мямлит.
@Kirsanov2011
2 жыл бұрын
Да, у меня есть недостатки. Буду преодолевать.
Спасибо!