Как я должен проверить генетический алгоритм - PullRequest
53 голосов
/ 24 июня 2009

Я сделал довольно мало генетических алгоритмов; они работают (они быстро находят разумное решение). Но теперь я обнаружил TDD . Есть ли способ написать генетический алгоритм (который сильно зависит от случайных чисел) способом TDD?

Чтобы сформулировать вопрос более широко, как вы тестируете недетерминированный метод / функцию. Вот что я подумал:

  1. Используйте конкретное семя. Что не поможет, если я сначала сделаю ошибку в коде, но поможет найти ошибки при рефакторинге.

  2. Использовать известный список номеров. Аналогично вышеописанному, но я мог бы выполнить код вручную (это было бы очень утомительно).

  3. Используйте постоянное число. По крайней мере, я знаю, чего ожидать. Было бы хорошо, чтобы кости всегда читали 6, когда RandomFloat (0,1) всегда возвращает 1.

  4. Постарайтесь вывести как можно больше недетерминированного кода из GA. который кажется глупым, потому что это основа его цели.

Буду признателен за ссылки на очень хорошие книги по тестированию.

Ответы [ 10 ]

14 голосов
/ 24 июня 2009

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

Для вариантов / разведения / наследования атрибутов в итерациях проверьте эти значения на границах каждой итерации и протестируйте глобальный вывод всех итераций на основе известных входных / выходных данных успешных итерационных подтестов ...

Поскольку алгоритм является итеративным, вы можете использовать индукцию в своем тестировании, чтобы убедиться, что он работает в течение 1 итерации, n + 1 итерации, чтобы доказать, что он даст правильные результаты (независимо от детерминизма данных) для данного ввода диапазон / домен и ограничения на возможные значения на входе.

Редактировать Я нашел эту стратегию для тестирования недетерминированных систем , которая может дать некоторое представление. Это может быть полезно для статистического анализа живых результатов, когда TDD / процесс разработки доказывает, что логика верна.

4 голосов
/ 24 июня 2009

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

2 голосов
/ 23 декабря 2012

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

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

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

Другим способом тестирования с генерацией случайных чисел является экстернализация этого поколения в другой класс, к которому можно получить доступ через контекст или загрузить из значения конфигурации, и использование другого для выполнения теста. Было бы две реализации этого класса, одна для производства, которая генерирует реальные случайные числа, и другая для тестирования, у которых были бы способы принять числа, которые позже будут сгенерированы. Затем в тесте вы можете указать определенные числа, которые класс предоставит в проверенный код.

2 голосов
/ 24 июня 2009

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

W / R / T ваш 4-й пункт, вывод недетерминированного кода из GA, я думаю, что этот подход, вероятно, стоит рассмотреть. Если вы можете разложить алгоритм и отделить недетерминированные задачи, это должно сделать тестирование детерминированных частей простым. Пока вы осторожны с тем, как вы называете вещи, я не думаю, что вы жертвуете здесь многим. Если я не пойму вас неправильно, GA все еще будет делегировать этот код, но он живет где-то еще.

Что касается ссылок на очень хорошие книги по тестированию (для разработчиков), то мои любимые:

1 голос
/ 05 июля 2011

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

Что касается тестирования параметров GA (частота мутаций, перекрестная стратегия и т. Д.), Если вы сами реализуете эти вещи, вы, безусловно, можете их протестировать (вы можете снова провести модульные тесты по логике мутации и т. Д.), Но вы выиграли не сможет проверить «тонкую настройку» ГА.

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

1 голос
/ 02 июля 2009

Я написал дидактическое приложение C # TDD Genetic Algorithm: http://code.google.com/p/evo-lisa-clone/

Давайте возьмем самый простой метод случайного результата в приложении: PointGenetics.Create, который создает случайную точку с учетом границ. Для этого метода я использовал 5 тестов, и ни один из них не основан на конкретном семени:

http://code.google.com/p/evo-lisa-clone/source/browse/trunk/EvoLisaClone/EvoLisaCloneTest/PointGeneticsTest.cs

Проверка на случайность проста: для большой границы (много возможностей) две сгенерированные подряд точки не должны быть равны. Остальные тесты проверяют другие ограничения.

1 голос
/ 24 июня 2009

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

Это для ваших юнит-тестов. Для ваших интеграционных тестов, если вы делаете это, вы можете изучить насмешливое генерирование случайных чисел, заменив его алгоритмом, который будет возвращать известные числа от 0 до n для каждого случайного числа, которое вам нужно сгенерировать.

1 голос
/ 24 июня 2009

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

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

0 голосов
/ 12 марта 2010

Я бы настоятельно рекомендовал изучить использование фиктивных объектов для ваших юнит-тестов (http://en.wikipedia.org/wiki/Mock_object).. Вы можете использовать их для макетирования объектов, которые дают случайные предположения, чтобы вместо этого получить ожидаемые результаты.

0 голосов
/ 24 июня 2009

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

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

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

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

...