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

Ответ 1

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

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

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

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

Ответ 2

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

Ответ 3

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

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

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

• Test Driven от Lasse Kosela
• Эффективная работа с устаревшим кодом Michael Feathers
• Шаблоны тестирования XUnit от Gerard Meszaros
• Тестирование следующего поколения Java ™: TestNG и расширенные концепции от Cédric Beust и Hani Suleiman

Ответ 4

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

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

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

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

Ответ 5

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

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

Ответ 6

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

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

Ответ 7

Я написал дидактическое приложение С# 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

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

Ответ 8

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

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

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

Ответ 9

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

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

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

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

Ответ 10

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