Как проверить генетический алгоритм

Question

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

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

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

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

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

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

Ссылки на очень хорошие книги по тестированию также будут оценены.

Answer 1

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

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

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

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

Answer 2

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

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

Answer 3

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

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

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

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

Answer 4

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

Answer 5

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

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

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

• Test Driven Лассе Kosela
• Working Effectively with Legacy Code Майкл Перья
• XUnit Test Patterns Джерард Месарош
• Next Generation Java™ Testing: TestNG and Advanced Concepts по Cédric Beust & Hani Suleiman

Answer 6

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

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

Answer 7

Я написал 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

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

Answer 8

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

Answer 9

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

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

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

Answer 10

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

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

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

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