Плохая рандомизация в структуре генетического алгоритма

Кто-нибудь видел убедительные результаты использования Genetic Algorithm Framework .Net?

Я вижу плохую рандомизацию в демо-версии задачи коммивояжера, предоставленной с помощью Genetic Algorithm Framework. Следующий вызов генерирует один и тот же порядок перетасовки генов в популяции исходных хромосом x 100:

chromosome.Genes.ShuffleFast();

Если я выполняю один шаг по коду, порядок генов выглядит случайным, поэтому я подозреваю, что в ShuffleFast() есть ошибка time/Rdn(), или же я пропускаю шаг настройки.

Я попытался обойти эту проблему путем предварительной перетасовки последовательностей хромосомных генов, и это привело к незначительным изменениям в результатах TSP. Однако консольный журнал запуска по-прежнему показывает, что GAF обнаружил только 4 потенциальных решения для 400 поколений населения. Это противоречит видеороликам GA на YouTube, показывающим реализации генетического алгоритма, ориентирующиеся на предлагаемое решение с большим дрожанием. Я цитирую это как еще одно указание на то, что у GAF есть системная внутренняя проблема с генерацией случайных чисел.

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

Шаги для воспроизведения = загрузите GAF из nuget, скомпилируйте и отладьте проект по умолчанию с точкой останова после цикла создания хромосом for, проверьте популяцию. Решения. Windows 7, VS2015, .Net 4.5 и 4.61. Отладка или выпуск.


c# genetic-algorithm genetic-programming
person camelCase    schedule 30.12.2015    source источник
comment
Можете ли вы опубликовать больше кода, чтобы показать контекст этого вызова. Могут быть проблемы с генераторами случайных чисел, если они не инициализированы должным образом.   -  person ChrisF    schedule 30.12.2015
comment
@ChrisF Внутренняя работа подпрограммы ShuffleFast() находится в библиотеке GAF, исходный код которой, как мне кажется, закрыт. Автору библиотеки нужно будет ответить, он активен на SO. До тех пор я буду искать другую библиотеку GA. Вызов ShuffleFast() выполняется 100 раз в узком цикле в списке из 16 целых чисел, если я вручную прерву его и нажму F10 в этом цикле, результаты Shuffle будут выглядеть случайными.   -  person camelCase    schedule 30.12.2015
comment
Вызов ShuffleFast() выполняется 100 раз в тесном цикле со списком из 16 целых чисел. Возможно, это и является причиной проблемы. Похоже, что генератор случайных чисел инициализируется на каждой итерации цикла. Шаги в отладчике замедляют его достаточно, чтобы выдавать случайные результаты. Вам нужно инициализировать генератор один раз вне цикла.   -  person ChrisF    schedule 30.12.2015
comment
Обратите внимание, что базовые GA на самом деле не лучший подход для решения TSP. Простая реализация муравьиной системы (AS) обычно превосходит GA для TSP: s, даже если в последнем включены проверенные скорости мутаций / расширенные схемы перекрестного перехода для сохранения кодирования перестановки неповрежденным. Вероятно, для видеороликов на YouTube, которые вы видели, хромосомы были инициализированы с помощью хороших эвристических решений, а также показаны окончательные результаты после настройки параметров для конкретной задачи.   -  person dfrib    schedule 31.12.2015

Ответы (2)


arrow_upward
3
arrow_downward

Глядя на код в дизассемблере, есть две версии ShuffleFast, определенные как методы расширения: одна принимает объект Random в качестве параметра, а другая создает новый, используя конструктор по умолчанию и использует его. В остальном они идентичны, выполняя стандартную перетасовку Фишера-Йейтса.

Итак, вам нужно создать свой собственный Random, а затем передать его:

Random r = new Random();
...
chromosome.Genes.ShuffleFast(r);
otherChromosome.Genes.ShuffleFast(r);
...

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

person Matthew Strawbridge    schedule 30.12.2015
comment
Я последовал вашему совету, используя перегрузку ShuffleFast(Random r) с r, объявленным вне цикла популяции хромосом. Теперь семенная популяция имеет случайные последовательности генов. Результаты теста по-прежнему выглядят странно, учитывая всего несколько изменений расстояния тура по городу за 400 поколений. Следующим моим шагом будет перенос тестовых данных GAF на альтернативную платформу GA .Net, чтобы увидеть, постепенно ли алгоритм находит лучший ответ. Я отмечу ваш ответ как принятый ответ, если автор GAF не предложит более глубокое описание результатов теста времени выполнения. - person camelCase; 31.12.2015

arrow_upward
3
arrow_downward

Извините за поздний ответ на вопрос. Проблема действительно с GAF. Метод Shuffle использует генератор чисел System.Random и создает новый при каждом вызове метода. Это вызывает проблемы из-за посева. Я исправил это (сегодня вечером) в GAF, и это будет в следующем выпуске. Я предлагаю использовать следующий код в качестве обходного пути.

var rnd = GAF.Threading.RandomProvider.GetThreadRandom ();
myList.ShuffleFast (rnd);

Каждый генератор случайных чисел, созданный с использованием приведенного выше кода, создает генератор случайных чисел с одним начальным числом на поток. Затем это можно передать методу Shuffle(), как описано Мэтью.

person John Newcombe    schedule 08.01.2016