Алгоритм поиска гармонии, адаптированный для коммивояжера

Я ищу адаптацию алгоритма поиска гармонии, который решил проблему коммивояжера. Я должен реализовать это и описать результаты. Я нашел несколько решений, таких как:

http://www.jtacs.org/archive/2013/1/4/JTACS_2013_01_04.pdf

но эти решения не являются хорошими и возвращают плохие результаты. Я не могу использовать какие-либо комбинации с другими алгоритмами, это должен быть чистый поиск гармонии (но модификации, конечно, разрешены). Я также искал его в книге «Алгоритм поиска гармонии, вдохновленный музыкой: теория и приложения» и нашел описание здесь, но этого недостаточно.

Я думаю, что я пробовал все. Я буду благодарен за любые источники/идеи/примеры, показывающие, как это сделать.


algorithm traveling-salesman
person Łukasz Gil    schedule 08.09.2015    source источник
comment
Учитывая отрицательные результаты исследования, что заставляет вас думать, что возможно использовать Harmony Search для получения хороших результатов для задачи коммивояжёра?   -  person RBarryYoung    schedule 08.09.2015
comment
Pdf по моей второй ссылке — это сравнение нескольких алгоритмов для TSP. ГС дает неплохие результаты.   -  person Łukasz Gil    schedule 08.09.2015
comment
Но вы сами говорите: эти решения нехороши и дают плохие результаты. Пожалуйста, объясните, в чем здесь настоящая проблема?   -  person RBarryYoung    schedule 09.09.2015
comment
Я думаю, что эти описания не полны, очень схематичны и ключ не описан. Я реализовал алгоритмы из приведенных выше ссылок и получил плохие результаты, но у авторов публикаций хорошие результаты.   -  person Łukasz Gil    schedule 09.09.2015

Ответы (2)


arrow_upward
3
arrow_downward

Я исследователь в области компьютерных наук. У меня были сомнения по поводу алгоритма поиска гармонии, так как я впервые увидел его на конференции. Оказалось, что поиск гармонии — это частный случай эволюционных стратегий, которые были предложены в 60-е годы. Выяснилось также, что нельзя доверять цифрам, сообщаемым в газетах по поиску гармонии, особенно "изобретателю" этого метода. Для меня поиск гармонии - это метод обмана, и "изобретатель" этого метода, скорее всего, занимался академическим мошенничеством.

Вкратце: если алгоритм у вас не работает, скорее всего, это не ваша вина.

Источники:

1) Алгоритм поиска гармонии — мой личный опыт работы с этой «новаторской» метаэвристикой

2) Тщательный анализ алгоритма поиска гармонии: как исследовательское сообщество может быть введено в заблуждение «новаторской» методологией (журнальная статья, опубликованная в 2010 г.)

3) Критический анализ алгоритма поиска гармонии - Как не решать судоку (журнальная статья, опубликованная в 2015 г.)

4) Чистые алгоритмы – поиск гармонии

person Dennis Weyland    schedule 02.10.2015

arrow_upward
0
arrow_downward

Я реализовал Harmony Search для выбора составного веб-сервиса. Поэтому я постараюсь создать всю модель.

Шаги: -

1) Инициализируйте параметры задачи и алгоритма.

Целевая функция с переменными решения. Для TSP переменными решения должны быть weight кратчайшего пути. Другие переменные Поиска гармонии могут быть установлены в соответствии с исполнением.

  • размер памяти гармонии (HMS), (количество примеров решений)
  • память гармоний с учетом скорости (HMCR)
  • скорость регулировки высоты тона (PAR)
  • Критерий завершения (максимальное количество поисков)

Эти переменные должны быть проверены на самом деле, запустив алгоритм и получив результаты с разными значениями для достижения наилучшей производительности.

2) Инициализируйте память гармонии.

На этом шаге вы должны заполнить память, создавая гармонии (случайные решения) и сохраняя их, чтобы с ними можно было работать позже.

3) Импровизируйте новую гармонию.

У вас есть 2 варианта создания новой гармонии (решения). Либо выберите один из уже созданных, либо создайте новый случайным образом. Это зависит от скорости учета памяти гармонии (HMCR). Это вероятность, с которой вы можете выбрать любой из способов, упомянутых выше.

4) Обновите память гармонии.

Вновь созданную гармонию (решение) необходимо сравнить с уже существующими. Если новая гармония (решение) лучше уже имеющейся наихудшей гармонии (при этом сравнивается общий вес пути этих решений), то новая гармония сохраняется вместо наихудшей.

5) Повторяйте шаги 3 и 4 до тех пор, пока не будет удовлетворен критерий завершения.

Проверьте, выполнено ли условие завершения. Это условие завершения может быть числом итераций или если соблюдается определенная степень точности.

Надеюсь, это решение поможет.

person Haris    schedule 08.09.2015
comment
Привет, харис, я знаю, как работает Harmony Search, я реализовал его, но классический HS возвращает неудовлетворительные результаты. Гармония улучшается очень медленно. Это должен быть лучший способ выбрать города для новой гармонии, я пытался получить ближайших соседей, но это привело к тому, что алгоритм получает локальный оптимум с плохим результатом. Должен быть другой способ получить лучшие гармонии. Адаптации для других задач являются модификациями классической HS и должны быть хорошей формой TSP. Извините за мой английский. - person Łukasz Gil; 08.09.2015