TSP/TSPTW с различными семенами

Question

Я хотел бы спросить, можно ли запустить GA с разными семенами, чтобы генерировать начальное решение и проводить анализ?. Однако в начале применения GA вы должны создать ряд демографических решений. Например, вы запускаете генетический алгоритм с использованием семени «12345» для генерации исходного решения, а затем вы заполняете список случайных решений из этого первоначального решения и продолжаете применять шаги GA для решения проблемы.

Затем вы запускаете генетический с другим семенем, например «5678» для генерации исходного раствора, а затем заселить список случайных решений из этого исходного раствора и продолжают применять меры ГА для решения проблемы ..

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

Мой вопрос: есть ли способ использовать GA с разными семенами для сравнения и анализа? Если нет, то как я могу сравнивать и анализировать, должен ли я использовать только другой файл экземпляра для этой проблемы?

Answer 1

Для сравнения стохастических алгоритмов сначала вы обычно запускаете их несколько раз с различными случайными семенами. Полученный вами результат является случайной величиной. Затем вы можете оценить, лучше ли один алгоритм, чем другой, путем выполнения теста статистической гипотезы (ANOVA или Kruskal-Wallis для множественных сравнений, t-теста или теста Mann-Whitney U для парных сравнений) на полученных образцах. Если полученное значение p в этих тестах ниже вашего желаемого порога (обычно 0,05, но для более строгих доказательств вы должны установить это ниже, например 0,01), вы отклоните гипотезу H0 о том, что эти результаты равны, например. в отношении их средств. Таким образом, вы предполагаете, что результаты являются неравными и более высокими, что лучший с лучшим средним показателем является лучшим алгоритмом выбора (если вас интересует средняя производительность - «лучше», как правило, имеет много измерений).

Одно заставило меня задаться вопросом в комментариях:

При запуске алгоритма GA несколько раз с тем же семенем для исходного раствора, то результат будет совершенно иным

Я думаю, что вы внесли некоторые ошибки в ваш код. Вы должны использовать один и тот же случайный объект во всех случайных решениях, сделанных внутри вашего алгоритма, чтобы получить точно такой же результат. Где-то в вашем коде вы, вероятно, используете new Random() вместо того, который вы получили изначально с заданным семенем. Другая причина может заключаться в том, что вы используете параллельную обработку деталей, которые производят случайные числа. Вы никогда не можете гарантировать, что ваши потоки всегда выполняются в том же порядке, поэтому один временной поток 1 получает первое случайное число, а второй - второй, другой - второй, второй - первый и получает первое число.