TSP сегодня
Ilya.Lo...@gmail.com
Этим летом я проходил стажировку во фр. , приходилось в частности
найти алгоритм решения такой задачи на основе ген. алгоритмов.
В результате я получил программу на Visual C++, которая базировалось
на том, что можно найти на codesource. Однако я улучшил алгоритм и
позволил подключать туда файлы типа tsp библиотеки TSPLIB. В
Результате программа умеет решать задачи для большого количество
городов. для Нескольких тысяч ошибка составляет несколько процентов от
оптимума (за пару секунд).
Что тут сказать, это может быть лучшее что я видел в интернете на
основе ГА. Важним местом является использование 2opt heuristics.
К чему я пришел, прокопав эту задачу до дна за два месяца. Есть лучшие
решатели, такие как Concorde и LKH Келда Хелсгауна. Последняя версия
второго, наверное лучшее в мире средство, позвоялет решать задачи с
ошибкой до процента для 1.000.000 городов. Что помоему почти
фантастика, но поклон автору, приятный на внешность человек.
Идея, к которой я пришел - использовать открытую библиотеку LKH
(правда не последняя версия) и можно будет обучать особи там вместо
2opt модифицированным алгоритмом Лин-Кернигана. В результате мы может
оперировать небольшой популяцией особей, которые сами будут обучаться
по LKH, но и скрещиваться и мутировать нашими средствами. Так мы можем
получить одну из лучших в мире программу. Правда она будет работать
дольше, но в конце концов результат может быть лучше.
Вообще говоря, я почти написал такую программу, но время стажировки не
позволило и дожди в этом году меня совсем убили )
Это сообщение немного сумбурно и наверное более понятно тем, что уже
писал специфичные алгоритмы для проблем TSP.
И еще, хотел решить задачу TSP для России, но никто пока не создал
файл формата с описанием координат - обидно, даже у Африканских стран
есть. Можно было бы впервые решить для России ( кстати есть сайт, где
можно взять информацию, но нужно писать парсер)
В России в этой области очень слабо, задачи до 100-300 городов это
почти предел.
Илья
Yury
Очень интересное сообщение :) Тем более, что TSP часто приводят как
пример использования ГА. Жалко, что сам с этой проблемой как-то не
сталкивался, больше возился с численной оптимизацией и нейросетями.
Но, если позволите, попытаюсь прокомментировать Вашу идею алгоритма.
Если правильно понимаю, предполагается в каждом поколении в течение
некоторого времени дообучать особи алгоритмом LKH, а полученные
дообученные особи скрещивать, мутировать, а затем снова дообучать и
т.д. Другими словами, используется модель эволюции по Ламарку, в
которой навыки, приобретенные в процессе жизни особи, передаются по
наследству. По сути имеем гибрид, причем, на мой взгляд, один из самых
разумных вариантов, сочетающий и локальный и глобальный поиск, хотя
процесс настройки такого гибрида может получиться непростым (нужно
будет четко соблюсти баланс между локальной и глобальной
составляющими). Это вопрос очень интересный, но решаемый. Такой
вариант гибридизации известен с 1989 также как меметичный алгоритм
(memetic algorithm), основной сайт по этому направлению:
http://www.densis.fee.unicamp.br/~moscato/memetic_home.html
А вот что еще стало очень интересно. Как известно, TSP имеет
комбинаторную сложность, и сама задача для большого количества городов
считается NP-полной (вроде достаточно условия >300 городов), т.е.
точный ответ нельзя найти за полиномиальное время, поэтому найденное
решение нельзя за конечное время проверить на оптимальность. Однако,
выходит, что каким-то образом удается проанализировать решения для
десятков и сотен тысяч городов. Подсознание удивляется: каким
образом? :)
Первое, что приходит в голову по этому поводу, так это то, что граф
задачи строится некоторым детерминированным образом, например, сразу
же устанавливается кратчайший путь между двумя городами, а потом на
этот путь "наращиваются" оставшиеся тысячи вершин и ребер таким
образом, чтобы не получился путь, короче чем первоначальный. Еще
подумал, что возможно матрица связности, соответствующая графу задачи
очень сильно разрежена, поэтому удается разбить исходный большой граф
на большое количество маленьких, и решить задачу для них. Или
действуют как-то по-другому?
А для России, если информации по координатам городов нет в открытом
виде, то уверен, она должна быть в соответствующих органах, если их
заинтересовать, то, может быть, и поделятся ;)
Юрий
Ilya.Lo...@gmail.com
Я как и вы занимаюсь численной оптимизацией. Для меня задача TSP так
же была специфичной, но случай потребовал изучить эту область. Так
приятно когда можно реально определить качество работы твоего
алгоритма. Все - таки при численной оптимизации это много раз сложнее
чем при таких задачах.
Я больше специализируюсь на так называемом синтезе радиоэлектронных
устройств, так есть своя специфика, отдельный разговор.
Да , вы правильно поняли мою идею. Такой поход еще и потому разумен,
потому что чистый ГА не так уж и эффективен, хоть я и не хотел тому
верить. Без эвристики такие алгоритмы работают медленно.
Все дороги по этой теме так или иначе проходят через http://www.tsp.gatech.edu/
, очень хорошее место. можно просто почитать применение и так далее.
Я думаю моя идею отличительно от всех подобных лишь тем, что другие
люди использует например 2(3,4)opt heuristic, я предлагаю наглым но
эффективным образом использовать библиотеку LKH. Сам Келд Хелсгаун
вряд ли думал об этом, он вроде не занимается ГА. Те кто занимаются ГА
и TSP вряд ли добирались до LKH (небольшой процент), и тем более не
все смогли посидеть над сложной но ясно написанной библиотекой и смочь
ее прикрутить. Так что если кто хочет сделать лучшие в России
гибридные ГА для решения такой задачи, может браться - задача на 3-6
месяцев. Я с уважением отнесусь к такому человеку, я сам хотел это
сделать. Меня остановили мои собственные другие цели. Там типа тоже
"лучшее в Мире" ;) (нескромно:)
Кратчайшее расстояние определяется двумя путями : 1. по математике 2.
по принципу - "от лучшего решения лучшего алгоритма (он знает)"
Я нашел источник материалов городов и расстояний, возможно, можно
прийти в какую-то организацию да и взять там информацию, но
подозреваю, что в России так просто не получится. Разве что пошутить,
что пишу программу по гранту Сороса, которая ищет кратчайший путь
(сколько дней), который должен пройти Доктор чтобы вылечить каждый из
городов России от некой заразы химических террористов ;)
Илья