Генетическое программирование на C#

В прошлом году в MSDN была статья о генетическом программировании: Генетические алгоритмы: выживание наиболее приспособленных с помощью Windows Forms

Я видел хорошее обсуждение этого вопроса на канале 9 Майком Свенсоном на http://channel9.msdn.com/posts/Charles/Algorithms-and-Data-Structures-Mike-Swanson-Genetic-Session-Scheduler/

Вы имеете в виду реальное генетическое программирование, а не генетические алгоритмы в целом?

Если это так, то C# /. Net - не лучший язык для этого. LISP, например, всегда был опорой GP.

Однако при необходимости вы, вероятно, захотите динамически сгенерировать CIL / MSIL. Вы можете сделать это с помощью System.Reflection.Emit, однако я бы рекомендовал Mono.Cecil. В нем нет хороших документов (как будто они есть в Reflection emit). Но он предлагает намного лучшие ассемблерные эмиссии и отражения.

Другая проблема заключается в том, что загрузить код, а затем избавиться от него в инфраструктуре .NET, не так просто. По крайней мере, вы не можете выгружать сборки. Вы можете выгружать домены приложений, но весь бизнес по загрузке кода в отдельный домен приложения и его внешнему вызову может стать довольно беспорядочным. Материал System.Addin в .NET 3.5 должен упростить эту задачу.

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

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

Генетический алгоритм легче всего реализовать, когда целевой язык является функциональным и динамически типизирован. Вот почему большинство исследований генетических алгоритмов написано на LISP. В результате, если вы собираетесь реализовать его на C#, вам, вероятно, лучше определить свой собственный мини-«древовидный язык», заставить алгоритм генерировать деревья и просто интерпретировать деревья, когда придет время запускать каждую итерацию алгоритма. .

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

Это даст вам преимущество, заключающееся в том, что для работы будет доступно только одно представление (представление AST), которое оптимально подходит как для выполнения, так и для шагов «воспроизводства» генетического алгоритма.

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

С другой стороны, интерпретируемые AST могут собирать мусор, как и любой другой объект, и поэтому вам не нужно будет копаться в нескольких доменах приложений. Если по соображениям производительности вы хотите создать код для окончательного результата, вы можете добавить поддержку для этого позже. Однако я бы порекомендовал вам сделать это с помощью класса DynamicMethod. Это позволит вам динамически преобразовывать AST в скомпилированный делегат во время выполнения. Это позволит вам развернуть одну DLL, сохраняя при этом как можно более простой процесс генерации кода. Кроме того, экземпляры DynamicMethod являются сборщиками мусора, поэтому вы можете в конечном итоге использовать их как часть генетического алгоритма для ускорения работы.

Я сейчас читаю Полевое руководство по генетическому программированию (скачать PDF бесплатно). Он также доступен в мягкой обложке. В нем обсуждается использование библиотеки, написанной на Java, под названием TinyGP. Вы могли бы извлечь из этого некоторую выгоду. Я не начал заниматься программированием, но надеюсь применить некоторые концепции на C#.

Я поддерживаю порт ECJ на C#. Это великолепно.

После разработки мое собственное дидактическое приложение по генетическому программированию я нашел полную структуру генетического программирования под названием AForge.NET Генетика. Это часть Библиотека Aforge.NET. Под лицензией LGPL.

Я разветвил ECJ на C# .NET 4.0, если вас интересует полнофункциональная среда эволюционных вычислений. Пакет включает в себя все из исходного проекта ECJ Java, включая все рабочие образцы.

Я также написал 500 модульных тестов, чтобы проверить многие аспекты преобразования. Но нужно еще много тестов. В частности, не полностью протестированы аспекты распределенных вычислений. Это потому, что я планирую перейти от простого использования сокетов ECJ к более надежной стратегии с использованием WCF и WF. Я также буду переделывать фреймворк для использования TPL (библиотеки параллельных задач).

В любом случае, вы можете скачать первоначальную конвертацию здесь:

http://branecloud.codeplex.com

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

Бен

Если вас интересуют генетические алгоритмы или эвристическая оптимизация в целом, вы можете взглянуть на HeuristicLab. Он разрабатывается несколько лет, 1,5 года с момента выхода новой версии. Он написан на C# 4 и имеет приятный графический интерфейс. Уже доступно множество алгоритмов, таких как генетический алгоритм, генетическое программирование, стратегия эволюции, локальный поиск, поиск табу, оптимизация роя частиц, имитация отжига и другие. Также реализовано несколько задач, таких как задача маршрутизации транспортных средств, коммивояжер, оптимизация реальных функций, рюкзак, квадратичная задача назначения, классификация, регрессия и многие другие. Также есть учебные пособия, и у нас есть интегрированные буферы протоколов, чтобы вы могли общаться с внешними программами для оценки решения. Он находится под лицензией GPL. В 2009 году программное обеспечение получило награду Microsoft за инновации Microsoft Austria.

Мы также написали книгу на эту тему: Генетические алгоритмы и генетическое программирование.

Книга Мэннинга: «Метапрограммирование в .NET» посвящена большому разделу GP через деревья выражений.

Вы можете попробовать GeneticSharp.

В нем есть все классические операции GA, такие как отбор, кроссовер, мутация, повторная вставка и завершение.

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

Его можно использовать во многих приложениях, таких как библиотеки C# и 3D-игры Unity, есть образцы, запускающие его в Приложение GTK # и Игра Unity 3D-шашки.

Он также работает в Win и OSX.

Вот базовый пример использования библиотеки:

var selection = new EliteSelection();
var crossover = new OrderedCrossover();
var mutation = new ReverseSequenceMutation();
var fitness = new YourFitnessFunction();
var chromosome = new YourChromosome();
var population = new Population (50, 70, chromosome);

var ga = new GeneticAlgorithm(population, fitness, selection, crossover, mutation);

ga.Start();