Привет! Большое спасибо за курс. Есть вопросы на счет видео 6 и 7. Как модифицировать программу, чтобы найти кратчайшее расстояние между двумя любыми вершинами. Будет ли работать программа, если количество вершин увеличить до 50, например. Большое спасибо за ответ.
Вот вариант как можно сохранить данные по модели: В конце файла добавляем cp = dict(population=population, halloffame=hof, logbook=logbook, rndstate=random.getstate()) with open("checkpoint_name.pkl", "wb") as cp_file: pickle.dump(cp, cp_file) А в месте где стартует цикл, добавляем это: if checkpoint(): cp = pd.read_pickle(r'checkpoint_name.pkl') population = cp["population"] hof = cp["halloffame"] logbook = cp["logbook"] random.setstate(cp["rndstate"]) population, logbook = algorithms.eaSimple(population, toolbox, cxpb=P_CROSSOVER/LENGTH_D, mutpb=P_MUTATION/LENGTH_D, ngen=MAX_GENERATIONS, halloffame=hof, stats=stats, verbose=True) else: population, logbook = algorithms.eaSimple(population, toolbox, cxpb=P_CROSSOVER/LENGTH_D, mutpb=P_MUTATION/LENGTH_D, ngen=MAX_GENERATIONS, halloffame=hof, stats=stats, verbose=True) В начале же нужно добавить checkpoint = False (при первом старте), при последующих = True. Тогда поколения будут начинать обучения с первого прогона. И так можно до бесконечности усложнять алгоритм
На больших графах, например от 10 вершин, работает очень медленно, даже с изменениями параметров. Другие алгоритмы и на ста вершинах за секунду минимальные пути находят. Подскажите, это проблема именно генетического алгоритма, или реализации? На питоне ясно немного медленнее работает, чем на си например.
Это, конечно, учебный пример. Данную задачу нет смысла решать с помощью ГА, есть гораздо более эффективные другие подходы. Вообще ГА целесообразно использовать в трудноформализуемых или вообще не формализуемых математически задачах. Например, научить ходить виртуальное существо в виртуальном мире. И тому подобное.
Понимаю, что это всего лишь учебный пример для демонстрации, но возникает следующий вопрос. Насколько применим генетический алгоритм для поиска оптимального пути в графе? (та же задача коммивояжера) Ведь иногда гораздо "дешевле" зайти из первой вершины во вторую, из второй вернуться в первую и уже из первой в третью Размерности каждой хромосомы будут разными попросту потому, что обойти весь граф можно за большее кол-во вершин и при этом за меньшую стоимость и наоборот. Возможно я что то упустил, буду рад если поправите
Что-то мне подсказывает, что можно длину хромосомы сделать равной количеству вершин (не думаю, что большая длина целесообразна). А дальше конец хромосомы заполнять нулями.
А почему списки в хромосомах представлены именно таким образом? Из нуля в ноль - ноль Из нуля в 1 - 1 Из нуля в два - также одно ребро Из нуля в три - также одно ребро, но магическим образом ставим в списке ноль
Замечательно! А если этот алгоритм скормить на другой граф. Что, будет доучиваться? Возможно ли его доучить до того, чтобы он решал любые графы? Судя по теории из ранних видео -- да. Интересно, как "геном" такой будет выглядеть технически.
Сергей, объясните пожалуйста 2:39 зачем мы заходим в 0 сначала в 4список(из 0 в 3),если в других так не делаем,и как мы вы проставили остальные цифры, по какой логике ?
Сергей, можете проконсультировать? Если есть цыфровая карта местности N строк на M столбцов. В каждой ячейке матрицы записана высота. Можно ли представить эту матрицу в виде графа, где вес ребер будут определять высоты, а вершины номера ячеек матрицы. Чтоб можно было вычислить кратчайший маршрут движения на минимальной высоте？Спасибо за ранее. Не знаю, как автоматизировать построеие матрицы смежности для данной задачи.
Так и не понял по какому принципу пронумерованы маршруты и как таблица смежности все это отображает и как потом все это понимает компьютер? Почему маршруты 3 и 4 повторяются дважды, и как потом машина понимает что это разные маршруты? П.С. Как саму таблицу смежности ввели в компьютер мне понятно (как матрицу).
Да, там в graph_show также нужно этот параметр установить в 2, не обратил на это внимание. Как доп. задание могу посоветовать сделать это через параметр функции graph_show.
Ваш канал очен интересен и доходчив, вы молодец, по больше таких видео！
Спасибо, Сергей!
Очень круто!
Привет! Большое спасибо за курс. Есть вопросы на счет видео 6 и 7. Как модифицировать программу, чтобы найти кратчайшее расстояние между двумя любыми вершинами. Будет ли работать программа, если количество вершин увеличить до 50, например. Большое спасибо за ответ.
Вот вариант как можно сохранить данные по модели:
В конце файла добавляем
cp = dict(population=population, halloffame=hof,
logbook=logbook, rndstate=random.getstate())
with open("checkpoint_name.pkl", "wb") as cp_file:
pickle.dump(cp, cp_file)
А в месте где стартует цикл, добавляем это:
if checkpoint():
cp = pd.read_pickle(r'checkpoint_name.pkl')
population = cp["population"]
hof = cp["halloffame"]
logbook = cp["logbook"]
random.setstate(cp["rndstate"])
population, logbook = algorithms.eaSimple(population, toolbox,
cxpb=P_CROSSOVER/LENGTH_D,
mutpb=P_MUTATION/LENGTH_D,
ngen=MAX_GENERATIONS,
halloffame=hof,
stats=stats,
verbose=True)
else:
population, logbook = algorithms.eaSimple(population, toolbox,
cxpb=P_CROSSOVER/LENGTH_D,
mutpb=P_MUTATION/LENGTH_D,
ngen=MAX_GENERATIONS,
halloffame=hof,
stats=stats,
verbose=True)
В начале же нужно добавить checkpoint = False (при первом старте), при последующих = True. Тогда поколения будут начинать обучения с первого прогона. И так можно до бесконечности усложнять алгоритм
На больших графах, например от 10 вершин, работает очень медленно, даже с изменениями параметров. Другие алгоритмы и на ста вершинах за секунду минимальные пути находят. Подскажите, это проблема именно генетического алгоритма, или реализации? На питоне ясно немного медленнее работает, чем на си например.
Это, конечно, учебный пример. Данную задачу нет смысла решать с помощью ГА, есть гораздо более эффективные другие подходы. Вообще ГА целесообразно использовать в трудноформализуемых или вообще не формализуемых математически задачах. Например, научить ходить виртуальное существо в виртуальном мире. И тому подобное.
👍
Понимаю, что это всего лишь учебный пример для демонстрации, но возникает следующий вопрос.
Насколько применим генетический алгоритм для поиска оптимального пути в графе? (та же задача коммивояжера)
Ведь иногда гораздо "дешевле" зайти из первой вершины во вторую, из второй вернуться в первую и уже из первой в третью
Размерности каждой хромосомы будут разными попросту потому, что обойти весь граф можно за большее кол-во вершин и при этом за меньшую стоимость и наоборот.
Возможно я что то упустил, буду рад если поправите
Что-то мне подсказывает, что можно длину хромосомы сделать равной количеству вершин (не думаю, что большая длина целесообразна). А дальше конец хромосомы заполнять нулями.
А почему списки в хромосомах представлены именно таким образом?
Из нуля в ноль - ноль
Из нуля в 1 - 1
Из нуля в два - также одно ребро
Из нуля в три - также одно ребро, но магическим образом ставим в списке ноль
Замечательно! А если этот алгоритм скормить на другой граф. Что, будет доучиваться? Возможно ли его доучить до того, чтобы он решал любые графы? Судя по теории из ранних видео -- да. Интересно, как "геном" такой будет выглядеть технически.
Доучивать можно, на вход подаете недооптимизированный граф и оптимизируете дальше )
Сергей, объясните пожалуйста 2:39 зачем мы заходим в 0 сначала в 4список(из 0 в 3),если в других так не делаем,и как мы вы проставили остальные цифры, по какой логике ?
Я не Сергей, но отвечу. Он их раскидал случайным образом. Ведь именно случайным образом эти данные будут генерироваться.
Сергей, можете проконсультировать? Если есть цыфровая карта местности N строк на M столбцов. В каждой ячейке матрицы записана высота. Можно ли представить эту матрицу в виде графа, где вес ребер будут определять высоты, а вершины номера ячеек матрицы. Чтоб можно было вычислить кратчайший маршрут движения на минимальной высоте？Спасибо за ранее. Не знаю, как автоматизировать построеие матрицы смежности для данной задачи.
Матрица связности, наверное будет достаточно. А задачу возможно лучше решить алгоритмом Дейкстры с некоторой модификацией с учетом высоты.
Так и не понял по какому принципу пронумерованы маршруты и как таблица смежности все это отображает и как потом все это понимает компьютер?
Почему маршруты 3 и 4 повторяются дважды, и как потом машина понимает что это разные маршруты?
П.С. Как саму таблицу смежности ввели в компьютер мне понятно (как матрицу).
Если задать начальную вершину startV=2, например, то show_graph выдаёт странный график.
Да, там в graph_show также нужно этот параметр установить в 2, не обратил на это внимание. Как доп. задание могу посоветовать сделать это через параметр функции graph_show.
@@selfedu_rus Спасибо за Урок и ДЗ. Жду новых.
Неудобно воспринимать, 0 это 1, 1 это 2....
не хотел из-за этого усложнять программу