Вопрос по – Как я должен проверить генетический алгоритм

53

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

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

Use a specific seed. Which wont help if I make a mistake in the code in the first place but will help finding bugs when refactoring.

Use a known list of numbers. Similar to the above but I could follow the code through by hand (which would be very tedious).

Use a constant number. At least I know what to expect. It would be good to ensure that a dice always reads 6 when RandomFloat(0,1) always returns 1.

Try to move as much of the non-deterministic code out of the GA as possible. which seems silly as that is the core of it's purpose.

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

Ваш Ответ

10   ответов
1

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

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

Спасибо за ответ, я проверю код позже. Я сейчас провел тестирование и, по-моему, использовал немного похожий подход к вам. Я проверил множество вещей, которые, как я знал, должны происходить, когда я дал ему конкретные значения для моего 'random' apos; номера. Затем я проверил, что распределение было приблизительно что я ожидал более 10000 испытаний. Не идеально, но это подойдет. James Brooks
1

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

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

Спасибо за ответ, я проверю код позже. Я сейчас провел тестирование и, по-моему, использовал немного похожий подход к вам. Я проверил множество вещей, которые, как я знал, должны происходить, когда я дал ему конкретные значения для моего 'random' apos; номера. Затем я проверил, что распределение было приблизительно что я ожидал более 10000 испытаний. Не идеально, но это подойдет. James Brooks
1

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

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

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

0

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

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

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

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

14

Сдается мне, что единственный способ проверить егоconsistent logic это применитьconsistent input, ... или угощениеeach iteration как отдельный автомат, состояние которого проверяется до и после этой итерации, превращая всю недетерминированную систему в тестируемые компоненты, основанные на детерминированных значениях итерации.

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

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

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

@ Джеймс, просто помни с недетерминированными алгоритмами, что есть заметная разница между «проверкой логики»; и тестирование «ожидаемых результатов». Делай одно, потом другое. Если первое нарушено, второе не имеет смысла.
Спасибо за ответ. Я надеялся на какую-нибудь серебряную пулю, но, думаю, это не просто проверить. Если я тщательно выберу случайные числа, я могу проверить каждый путь выполнения. Я также проведу тест с известным фитнес-ландшафтом, чтобы увидеть, насколько хорошо он работает. James Brooks
2

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

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

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

2

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

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

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

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

1

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

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

0

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

4

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

Будет ли это не только оценивать распределение значений вокруг нормы, чем пригодность алгоритма для правильного распределения вокруг нормы? Сломанный алгоритм все равно будет сломан, если вы запустите его дважды. Если бы он делал результаты поиска, это было бы похоже на проверку результатов, содержащих ключевые слова, в качестве проверки порядка поиска.
Понимаю. Я думаю, что это может быть немного подвержено ошибкам для TDD. Я даже думаю, что статистический анализ на основе графиков, как в статье, с которой я связан, не должен бытьfirst порт захода для модульного / функционального тестирования логики, а не результатов на живых данных.
Я не сказал нормальное распределение, я сказал, что распределение должно соответствовать статистическим ожиданиям, то есть, если вам нужна случайная функция для возврата, например, случайных значений, соответствующих распределению Больцмана, вы должны проверить, достаточно ли велико число Тестовые прогоны формируют такой дистрибутив.

Похожие вопросы